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