Add explicit keywords.
[oota-llvm.git] / lib / Target / Mips / MipsISelDAGToDAG.cpp
1 //===-- MipsISelDAGToDAG.cpp - A dag to dag inst selector for Mips --------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines an instruction selector for the MIPS target.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #define DEBUG_TYPE "mips-isel"
15 #include "Mips.h"
16 #include "MipsISelLowering.h"
17 #include "MipsMachineFunction.h"
18 #include "MipsRegisterInfo.h"
19 #include "MipsSubtarget.h"
20 #include "MipsTargetMachine.h"
21 #include "llvm/GlobalValue.h"
22 #include "llvm/Instructions.h"
23 #include "llvm/Intrinsics.h"
24 #include "llvm/Support/CFG.h"
25 #include "llvm/Type.h"
26 #include "llvm/CodeGen/MachineConstantPool.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineFrameInfo.h"
29 #include "llvm/CodeGen/MachineInstrBuilder.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/SelectionDAGISel.h"
32 #include "llvm/Target/TargetMachine.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
35 #include <queue>
36 #include <set>
37
38 using namespace llvm;
39
40 //===----------------------------------------------------------------------===//
41 // Instruction Selector Implementation
42 //===----------------------------------------------------------------------===//
43
44 //===----------------------------------------------------------------------===//
45 // MipsDAGToDAGISel - MIPS specific code to select MIPS machine
46 // instructions for SelectionDAG operations.
47 //===----------------------------------------------------------------------===//
48 namespace {
49
50 class VISIBILITY_HIDDEN MipsDAGToDAGISel : public SelectionDAGISel {
51
52   /// TM - Keep a reference to MipsTargetMachine.
53   MipsTargetMachine &TM;
54
55   /// MipsLowering - This object fully describes how to lower LLVM code to an
56   /// Mips-specific SelectionDAG.
57   MipsTargetLowering MipsLowering;
58
59   /// Subtarget - Keep a pointer to the MipsSubtarget around so that we can
60   /// make the right decision when generating code for different targets.
61   const MipsSubtarget &Subtarget;
62  
63 public:
64   explicit MipsDAGToDAGISel(MipsTargetMachine &tm) :
65   SelectionDAGISel(MipsLowering),
66   TM(tm), MipsLowering(*TM.getTargetLowering()), 
67   Subtarget(tm.getSubtarget<MipsSubtarget>()) {}
68   
69   virtual void InstructionSelect(SelectionDAG &SD);
70
71   // Pass Name
72   virtual const char *getPassName() const {
73     return "MIPS DAG->DAG Pattern Instruction Selection";
74   } 
75   
76
77 private:  
78   // Include the pieces autogenerated from the target description.
79   #include "MipsGenDAGISel.inc"
80
81   SDOperand getGlobalBaseReg();
82   SDNode *Select(SDOperand N);
83
84   // Complex Pattern.
85   bool SelectAddr(SDOperand Op, SDOperand N, 
86                   SDOperand &Base, SDOperand &Offset);
87
88
89   // getI32Imm - Return a target constant with the specified
90   // value, of type i32.
91   inline SDOperand getI32Imm(unsigned Imm) {
92     return CurDAG->getTargetConstant(Imm, MVT::i32);
93   }
94
95
96   #ifndef NDEBUG
97   unsigned Indent;
98   #endif
99 };
100
101 }
102
103 /// InstructionSelect - This callback is invoked by
104 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
105 void MipsDAGToDAGISel::
106 InstructionSelect(SelectionDAG &SD) 
107 {
108   DEBUG(BB->dump());
109   // Codegen the basic block.
110   #ifndef NDEBUG
111   DOUT << "===== Instruction selection begins:\n";
112   Indent = 0;
113   #endif
114
115   // Select target instructions for the DAG.
116   SD.setRoot(SelectRoot(SD.getRoot()));
117
118   #ifndef NDEBUG
119   DOUT << "===== Instruction selection ends:\n";
120   #endif
121
122   SD.RemoveDeadNodes();
123 }
124
125 /// getGlobalBaseReg - Output the instructions required to put the
126 /// GOT address into a register.
127 SDOperand MipsDAGToDAGISel::getGlobalBaseReg() {
128   MachineFunction* MF = BB->getParent();
129   unsigned GP = 0;
130   for(MachineRegisterInfo::livein_iterator ii = MF->getRegInfo().livein_begin(),
131         ee = MF->getRegInfo().livein_end(); ii != ee; ++ii)
132     if (ii->first == Mips::GP) {
133       GP = ii->second;
134       break;
135     }
136   assert(GP && "GOT PTR not in liveins");
137   return CurDAG->getCopyFromReg(CurDAG->getEntryNode(), 
138                                 GP, MVT::i32);
139 }
140
141 /// ComplexPattern used on MipsInstrInfo
142 /// Used on Mips Load/Store instructions
143 bool MipsDAGToDAGISel::
144 SelectAddr(SDOperand Op, SDOperand Addr, SDOperand &Offset, SDOperand &Base)
145 {
146   // if Address is FI, get the TargetFrameIndex.
147   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
148     Base   = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
149     Offset = CurDAG->getTargetConstant(0, MVT::i32);
150     return true;
151   }
152     
153   // on PIC code Load GA
154   if (TM.getRelocationModel() == Reloc::PIC_) {
155     if ((Addr.getOpcode() == ISD::TargetGlobalAddress) || 
156         (Addr.getOpcode() == ISD::TargetJumpTable)){
157       Base   = CurDAG->getRegister(Mips::GP, MVT::i32);
158       Offset = Addr;
159       return true;
160     }
161   } else {
162     if ((Addr.getOpcode() == ISD::TargetExternalSymbol ||
163         Addr.getOpcode() == ISD::TargetGlobalAddress))
164       return false;
165   }    
166   
167   // Operand is a result from an ADD.
168   if (Addr.getOpcode() == ISD::ADD) {
169     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) {
170       if (Predicate_immSExt16(CN)) {
171
172         // If the first operand is a FI, get the TargetFI Node
173         if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>
174                                     (Addr.getOperand(0))) {
175           Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
176         } else {
177           Base = Addr.getOperand(0);
178         }
179
180         Offset = CurDAG->getTargetConstant(CN->getValue(), MVT::i32);
181         return true;
182       }
183     }
184   }
185
186   Base   = Addr;
187   Offset = CurDAG->getTargetConstant(0, MVT::i32);
188   return true;
189 }
190
191 /// Select instructions not customized! Used for
192 /// expanded, promoted and normal instructions
193 SDNode* MipsDAGToDAGISel::
194 Select(SDOperand N) 
195 {
196   SDNode *Node = N.Val;
197   unsigned Opcode = Node->getOpcode();
198
199   // Dump information about the Node being selected
200   #ifndef NDEBUG
201   DOUT << std::string(Indent, ' ') << "Selecting: ";
202   DEBUG(Node->dump(CurDAG));
203   DOUT << "\n";
204   Indent += 2;
205   #endif
206
207   // If we have a custom node, we already have selected!
208   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < MipsISD::FIRST_NUMBER) {
209     #ifndef NDEBUG
210     DOUT << std::string(Indent-2, ' ') << "== ";
211     DEBUG(Node->dump(CurDAG));
212     DOUT << "\n";
213     Indent -= 2;
214     #endif
215     return NULL;
216   }
217
218   ///
219   // Instruction Selection not handled by the auto-generated 
220   // tablegen selection should be handled here.
221   /// 
222   switch(Opcode) {
223
224     default: break;
225
226     case ISD::SUBE: 
227     case ISD::ADDE: {
228       SDOperand InFlag = Node->getOperand(2), CmpLHS;
229       unsigned Opc = InFlag.getOpcode(), MOp;
230
231       assert(((Opc == ISD::ADDC || Opc == ISD::ADDE) || 
232               (Opc == ISD::SUBC || Opc == ISD::SUBE)) &&  
233              "(ADD|SUB)E flag operand must come from (ADD|SUB)C/E insn");
234
235       if (Opcode == ISD::ADDE) {
236         CmpLHS = InFlag.getValue(0);
237         MOp = Mips::ADDu;
238       } else { 
239         CmpLHS = InFlag.getOperand(0);
240         MOp = Mips::SUBu;
241       }
242
243       SDOperand Ops[] = { CmpLHS, InFlag.getOperand(1) };
244
245       SDOperand LHS = Node->getOperand(0);
246       SDOperand RHS = Node->getOperand(1);
247       AddToISelQueue(LHS);
248       AddToISelQueue(RHS);
249
250       MVT VT = LHS.getValueType();
251       SDNode *Carry = CurDAG->getTargetNode(Mips::SLTu, VT, Ops, 2);
252       SDNode *AddCarry = CurDAG->getTargetNode(Mips::ADDu, VT, 
253                                                SDOperand(Carry,0), RHS);
254
255       return CurDAG->SelectNodeTo(N.Val, MOp, VT, MVT::Flag, 
256                                   LHS, SDOperand(AddCarry,0));
257     }
258
259     /// Mul/Div with two results
260     case ISD::SDIVREM:
261     case ISD::UDIVREM:
262     case ISD::SMUL_LOHI:
263     case ISD::UMUL_LOHI: {
264       SDOperand Op1 = Node->getOperand(0);
265       SDOperand Op2 = Node->getOperand(1);
266       AddToISelQueue(Op1);
267       AddToISelQueue(Op2);
268
269       unsigned Op;
270       if (Opcode == ISD::UMUL_LOHI || Opcode == ISD::SMUL_LOHI)
271         Op = (Opcode == ISD::UMUL_LOHI ? Mips::MULTu : Mips::MULT);
272       else
273         Op = (Opcode == ISD::UDIVREM ? Mips::DIVu : Mips::DIV);
274
275       SDNode *Node = CurDAG->getTargetNode(Op, MVT::Flag, Op1, Op2);
276
277       SDOperand InFlag = SDOperand(Node, 0);
278       SDNode *Lo = CurDAG->getTargetNode(Mips::MFLO, MVT::i32, MVT::Flag, InFlag);
279
280       InFlag = SDOperand(Lo,1);
281       SDNode *Hi = CurDAG->getTargetNode(Mips::MFHI, MVT::i32, InFlag);
282
283       if (!N.getValue(0).use_empty()) 
284         ReplaceUses(N.getValue(0), SDOperand(Lo,0));
285
286       if (!N.getValue(1).use_empty()) 
287         ReplaceUses(N.getValue(1), SDOperand(Hi,0));
288
289       return NULL;
290     }
291
292     /// Special Muls
293     case ISD::MUL: 
294     case ISD::MULHS:
295     case ISD::MULHU: {
296       SDOperand MulOp1 = Node->getOperand(0);
297       SDOperand MulOp2 = Node->getOperand(1);
298       AddToISelQueue(MulOp1);
299       AddToISelQueue(MulOp2);
300
301       unsigned MulOp  = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
302       SDNode *MulNode = CurDAG->getTargetNode(MulOp, MVT::Flag, MulOp1, MulOp2);
303
304       SDOperand InFlag = SDOperand(MulNode, 0);
305
306       if (MulOp == ISD::MUL)
307         return CurDAG->getTargetNode(Mips::MFLO, MVT::i32, InFlag);
308       else
309         return CurDAG->getTargetNode(Mips::MFHI, MVT::i32, InFlag);
310     }
311
312     /// Div/Rem operations
313     case ISD::SREM:
314     case ISD::UREM:
315     case ISD::SDIV: 
316     case ISD::UDIV: {
317       SDOperand Op1 = Node->getOperand(0);
318       SDOperand Op2 = Node->getOperand(1);
319       AddToISelQueue(Op1);
320       AddToISelQueue(Op2);
321
322       unsigned Op, MOp;
323       if (Opcode == ISD::SDIV || Opcode == ISD::UDIV) {
324         Op  = (Opcode == ISD::SDIV ? Mips::DIV : Mips::DIVu);
325         MOp = Mips::MFLO;
326       } else {
327         Op  = (Opcode == ISD::SREM ? Mips::DIV : Mips::DIVu);
328         MOp = Mips::MFHI;
329       }
330       SDNode *Node = CurDAG->getTargetNode(Op, MVT::Flag, Op1, Op2);
331
332       SDOperand InFlag = SDOperand(Node, 0);
333       return CurDAG->getTargetNode(MOp, MVT::i32, InFlag);
334     }
335
336     // Get target GOT address.
337     case ISD::GLOBAL_OFFSET_TABLE: {
338       SDOperand Result = getGlobalBaseReg();
339       ReplaceUses(N, Result);
340       return NULL;
341     }
342
343     /// Handle direct and indirect calls when using PIC. On PIC, when 
344     /// GOT is smaller than about 64k (small code) the GA target is 
345     /// loaded with only one instruction. Otherwise GA's target must 
346     /// be loaded with 3 instructions. 
347     case MipsISD::JmpLink: {
348       if (TM.getRelocationModel() == Reloc::PIC_) {
349         //bool isCodeLarge = (TM.getCodeModel() == CodeModel::Large);
350         SDOperand Chain  = Node->getOperand(0);
351         SDOperand Callee = Node->getOperand(1);
352         AddToISelQueue(Chain);
353         SDOperand T9Reg = CurDAG->getRegister(Mips::T9, MVT::i32);
354         SDOperand InFlag(0, 0);
355
356         if ( (isa<GlobalAddressSDNode>(Callee)) ||
357              (isa<ExternalSymbolSDNode>(Callee)) )
358         {
359           /// Direct call for global addresses and external symbols
360           SDOperand GPReg = CurDAG->getRegister(Mips::GP, MVT::i32);
361
362           // Use load to get GOT target
363           SDOperand Ops[] = { Callee, GPReg, Chain };
364           SDOperand Load = SDOperand(CurDAG->getTargetNode(Mips::LW, MVT::i32, 
365                                      MVT::Other, Ops, 3), 0);
366           Chain = Load.getValue(1);
367           AddToISelQueue(Chain);
368
369           // Call target must be on T9
370           Chain = CurDAG->getCopyToReg(Chain, T9Reg, Load, InFlag);
371         } else 
372           /// Indirect call
373           Chain = CurDAG->getCopyToReg(Chain, T9Reg, Callee, InFlag);
374
375         AddToISelQueue(Chain);
376
377         // Emit Jump and Link Register
378         SDNode *ResNode = CurDAG->getTargetNode(Mips::JALR, MVT::Other,
379                                   MVT::Flag, T9Reg, Chain);
380         Chain  = SDOperand(ResNode, 0);
381         InFlag = SDOperand(ResNode, 1);
382         ReplaceUses(SDOperand(Node, 0), Chain);
383         ReplaceUses(SDOperand(Node, 1), InFlag);
384         return ResNode;
385       } 
386     }
387   }
388
389   // Select the default instruction
390   SDNode *ResNode = SelectCode(N);
391
392   #ifndef NDEBUG
393   DOUT << std::string(Indent-2, ' ') << "=> ";
394   if (ResNode == NULL || ResNode == N.Val)
395     DEBUG(N.Val->dump(CurDAG));
396   else
397     DEBUG(ResNode->dump(CurDAG));
398   DOUT << "\n";
399   Indent -= 2;
400   #endif
401
402   return ResNode;
403 }
404
405 /// createMipsISelDag - This pass converts a legalized DAG into a 
406 /// MIPS-specific DAG, ready for instruction scheduling.
407 FunctionPass *llvm::createMipsISelDag(MipsTargetMachine &TM) {
408   return new MipsDAGToDAGISel(TM);
409 }