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