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   MachineFunction *MF = BB->getParent();
135   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
136   return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
137 }
138 
139 /// ComplexPattern used on MipsInstrInfo
140 /// Used on Mips Load/Store instructions
141 bool MipsDAGToDAGISel::
142 SelectAddr(SDValue Op, SDValue Addr, SDValue &Offset, SDValue &Base)
143 {
144   // if Address is FI, get the TargetFrameIndex.
145   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
146     Base   = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
147     Offset = CurDAG->getTargetConstant(0, MVT::i32);
148     return true;
149   }
150 
151   // on PIC code Load GA
152   if (TM.getRelocationModel() == Reloc::PIC_) {
153     if ((Addr.getOpcode() == ISD::TargetGlobalAddress) ||
154         (Addr.getOpcode() == ISD::TargetJumpTable)){
155       Base   = CurDAG->getRegister(Mips::GP, MVT::i32);
156       Offset = Addr;
157       return true;
158     }
159   } else {
160     if ((Addr.getOpcode() == ISD::TargetExternalSymbol ||
161         Addr.getOpcode() == ISD::TargetGlobalAddress))
162       return false;
163   }
164 
165   // Operand is a result from an ADD.
166   if (Addr.getOpcode() == ISD::ADD) {
167     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) {
168       if (Predicate_immSExt16(CN)) {
169 
170         // If the first operand is a FI, get the TargetFI Node
171         if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>
172                                     (Addr.getOperand(0))) {
173           Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
174         } else {
175           Base = Addr.getOperand(0);
176         }
177 
178         Offset = CurDAG->getTargetConstant(CN->getZExtValue(), MVT::i32);
179         return true;
180       }
181     }
182   }
183 
184   Base   = Addr;
185   Offset = CurDAG->getTargetConstant(0, MVT::i32);
186   return true;
187 }
188 
189 /// Select instructions not customized! Used for
190 /// expanded, promoted and normal instructions
191 SDNode* MipsDAGToDAGISel::
192 Select(SDValue N)
193 {
194   SDNode *Node = N.getNode();
195   unsigned Opcode = Node->getOpcode();
196   DebugLoc dl = Node->getDebugLoc();
197 
198   // Dump information about the Node being selected
199   #ifndef NDEBUG
200   DOUT << std::string(Indent, ' ') << "Selecting: ";
201   DEBUG(Node->dump(CurDAG));
202   DOUT << "\n";
203   Indent += 2;
204   #endif
205 
206   // If we have a custom node, we already have selected!
207   if (Node->isMachineOpcode()) {
208     #ifndef NDEBUG
209     DOUT << std::string(Indent-2, ' ') << "== ";
210     DEBUG(Node->dump(CurDAG));
211     DOUT << "\n";
212     Indent -= 2;
213     #endif
214     return NULL;
215   }
216 
217   ///
218   // Instruction Selection not handled by the auto-generated
219   // tablegen selection should be handled here.
220   ///
221   switch(Opcode) {
222 
223     default: break;
224 
225     case ISD::SUBE:
226     case ISD::ADDE: {
227       SDValue InFlag = Node->getOperand(2), CmpLHS;
228       unsigned Opc = InFlag.getOpcode(); Opc=Opc;
229       assert(((Opc == ISD::ADDC || Opc == ISD::ADDE) ||
230               (Opc == ISD::SUBC || Opc == ISD::SUBE)) &&
231              "(ADD|SUB)E flag operand must come from (ADD|SUB)C/E insn");
232 
233       unsigned MOp;
234       if (Opcode == ISD::ADDE) {
235         CmpLHS = InFlag.getValue(0);
236         MOp = Mips::ADDu;
237       } else {
238         CmpLHS = InFlag.getOperand(0);
239         MOp = Mips::SUBu;
240       }
241 
242       SDValue Ops[] = { CmpLHS, InFlag.getOperand(1) };
243 
244       SDValue LHS = Node->getOperand(0);
245       SDValue RHS = Node->getOperand(1);
246 
247       MVT VT = LHS.getValueType();
248       SDNode *Carry = CurDAG->getTargetNode(Mips::SLTu, dl, VT, Ops, 2);
249       SDNode *AddCarry = CurDAG->getTargetNode(Mips::ADDu, dl, VT,
250                                                SDValue(Carry,0), RHS);
251 
252       return CurDAG->SelectNodeTo(N.getNode(), MOp, VT, MVT::Flag,
253                                   LHS, SDValue(AddCarry,0));
254     }
255 
256     /// Mul/Div with two results
257     case ISD::SDIVREM:
258     case ISD::UDIVREM:
259     case ISD::SMUL_LOHI:
260     case ISD::UMUL_LOHI: {
261       SDValue Op1 = Node->getOperand(0);
262       SDValue Op2 = Node->getOperand(1);
263 
264       unsigned Op;
265       if (Opcode == ISD::UMUL_LOHI || Opcode == ISD::SMUL_LOHI)
266         Op = (Opcode == ISD::UMUL_LOHI ? Mips::MULTu : Mips::MULT);
267       else
268         Op = (Opcode == ISD::UDIVREM ? Mips::DIVu : Mips::DIV);
269 
270       SDNode *Node = CurDAG->getTargetNode(Op, dl, MVT::Flag, Op1, Op2);
271 
272       SDValue InFlag = SDValue(Node, 0);
273       SDNode *Lo = CurDAG->getTargetNode(Mips::MFLO, dl, MVT::i32,
274                                          MVT::Flag, InFlag);
275       InFlag = SDValue(Lo,1);
276       SDNode *Hi = CurDAG->getTargetNode(Mips::MFHI, dl, MVT::i32, InFlag);
277 
278       if (!N.getValue(0).use_empty())
279         ReplaceUses(N.getValue(0), SDValue(Lo,0));
280 
281       if (!N.getValue(1).use_empty())
282         ReplaceUses(N.getValue(1), SDValue(Hi,0));
283 
284       return NULL;
285     }
286 
287     /// Special Muls
288     case ISD::MUL:
289     case ISD::MULHS:
290     case ISD::MULHU: {
291       SDValue MulOp1 = Node->getOperand(0);
292       SDValue MulOp2 = Node->getOperand(1);
293 
294       unsigned MulOp  = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
295       SDNode *MulNode = CurDAG->getTargetNode(MulOp, dl,
296                                               MVT::Flag, MulOp1, MulOp2);
297 
298       SDValue InFlag = SDValue(MulNode, 0);
299 
300       if (MulOp == ISD::MUL)
301         return CurDAG->getTargetNode(Mips::MFLO, dl, MVT::i32, InFlag);
302       else
303         return CurDAG->getTargetNode(Mips::MFHI, dl, MVT::i32, InFlag);
304     }
305 
306     /// Div/Rem operations
307     case ISD::SREM:
308     case ISD::UREM:
309     case ISD::SDIV:
310     case ISD::UDIV: {
311       SDValue Op1 = Node->getOperand(0);
312       SDValue Op2 = Node->getOperand(1);
313 
314       unsigned Op, MOp;
315       if (Opcode == ISD::SDIV || Opcode == ISD::UDIV) {
316         Op  = (Opcode == ISD::SDIV ? Mips::DIV : Mips::DIVu);
317         MOp = Mips::MFLO;
318       } else {
319         Op  = (Opcode == ISD::SREM ? Mips::DIV : Mips::DIVu);
320         MOp = Mips::MFHI;
321       }
322       SDNode *Node = CurDAG->getTargetNode(Op, dl, MVT::Flag, Op1, Op2);
323 
324       SDValue InFlag = SDValue(Node, 0);
325       return CurDAG->getTargetNode(MOp, dl, MVT::i32, InFlag);
326     }
327 
328     // Get target GOT address.
329     case ISD::GLOBAL_OFFSET_TABLE:
330       return getGlobalBaseReg();
331 
332     /// Handle direct and indirect calls when using PIC. On PIC, when
333     /// GOT is smaller than about 64k (small code) the GA target is
334     /// loaded with only one instruction. Otherwise GA's target must
335     /// be loaded with 3 instructions.
336     case MipsISD::JmpLink: {
337       if (TM.getRelocationModel() == Reloc::PIC_) {
338         //bool isCodeLarge = (TM.getCodeModel() == CodeModel::Large);
339         SDValue Chain  = Node->getOperand(0);
340         SDValue Callee = Node->getOperand(1);
341         SDValue T9Reg = CurDAG->getRegister(Mips::T9, MVT::i32);
342         SDValue InFlag(0, 0);
343 
344         if ( (isa<GlobalAddressSDNode>(Callee)) ||
345              (isa<ExternalSymbolSDNode>(Callee)) )
346         {
347           /// Direct call for global addresses and external symbols
348           SDValue GPReg = CurDAG->getRegister(Mips::GP, MVT::i32);
349 
350           // Use load to get GOT target
351           SDValue Ops[] = { Callee, GPReg, Chain };
352           SDValue Load = SDValue(CurDAG->getTargetNode(Mips::LW, dl, MVT::i32,
353                                      MVT::Other, Ops, 3), 0);
354           Chain = Load.getValue(1);
355 
356           // Call target must be on T9
357           Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Load, InFlag);
358         } else
359           /// Indirect call
360           Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Callee, InFlag);
361 
362         // Emit Jump and Link Register
363         SDNode *ResNode = CurDAG->getTargetNode(Mips::JALR, dl, MVT::Other,
364                                   MVT::Flag, T9Reg, Chain);
365         Chain  = SDValue(ResNode, 0);
366         InFlag = SDValue(ResNode, 1);
367         ReplaceUses(SDValue(Node, 0), Chain);
368         ReplaceUses(SDValue(Node, 1), InFlag);
369         return ResNode;
370       }
371     }
372   }
373 
374   // Select the default instruction
375   SDNode *ResNode = SelectCode(N);
376 
377   #ifndef NDEBUG
378   DOUT << std::string(Indent-2, ' ') << "=> ";
379   if (ResNode == NULL || ResNode == N.getNode())
380     DEBUG(N.getNode()->dump(CurDAG));
381   else
382     DEBUG(ResNode->dump(CurDAG));
383   DOUT << "\n";
384   Indent -= 2;
385   #endif
386 
387   return ResNode;
388 }
389 
390 /// createMipsISelDag - This pass converts a legalized DAG into a
391 /// MIPS-specific DAG, ready for instruction scheduling.
392 FunctionPass *llvm::createMipsISelDag(MipsTargetMachine &TM) {
393   return new MipsDAGToDAGISel(TM);
394 }
395