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 was developed by Bruno Cardoso Lopes is distributed under the
   6 // University of Illinois Open Source 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
  16 #include "Mips.h"
  17 #include "MipsISelLowering.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/SelectionDAGISel.h"
  31 #include "llvm/Target/TargetMachine.h"
  32 #include "llvm/Support/Compiler.h"
  33 #include "llvm/Support/Debug.h"
  34 #include <queue>
  35 #include <set>
  36
  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   /// MipsLowering - This object fully describes how to lower LLVM code to an
  55   /// Mips-specific SelectionDAG.
  56   MipsTargetLowering MipsLowering;
  57
  58   /// Subtarget - Keep a pointer to the MipsSubtarget around so that we can
  59   /// make the right decision when generating code for different targets.
  60   //TODO: add initialization on constructor
  61   //const MipsSubtarget *Subtarget;
  62
  63 public:
  64   MipsDAGToDAGISel(MipsTargetMachine &tm) :
  65         SelectionDAGISel(MipsLowering),
  66         TM(tm), MipsLowering(*TM.getTargetLowering()) {}
  67
  68   virtual void InstructionSelectBasicBlock(SelectionDAG &SD);
  69
  70   // Pass Name
  71   virtual const char *getPassName() const {
  72     return "MIPS DAG->DAG Pattern Instruction Selection";
  73   }
  74
  75
  76 private:
  77   // Include the pieces autogenerated from the target description.
  78   #include "MipsGenDAGISel.inc"
  79
  80   SDNode *Select(SDOperand N);
  81
  82   // Complex Pattern.
  83   bool SelectAddr(SDOperand Op, SDOperand N,
  84                   SDOperand &Base, SDOperand &Offset);
  85
  86
  87   // getI32Imm - Return a target constant with the specified
  88   // value, of type i32.
  89   inline SDOperand getI32Imm(unsigned Imm) {
  90     return CurDAG->getTargetConstant(Imm, MVT::i32);
  91   }
  92
  93
  94   #ifndef NDEBUG
  95   unsigned Indent;
  96   #endif
  97 };
  98
  99 }
 100
 101 /// InstructionSelectBasicBlock - This callback is invoked by
 102 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 103 void MipsDAGToDAGISel::
 104 InstructionSelectBasicBlock(SelectionDAG &SD)
 105 {
 106   DEBUG(BB->dump());
 107   // Codegen the basic block.
 108   #ifndef NDEBUG
 109   DOUT << "===== Instruction selection begins:\n";
 110   Indent = 0;
 111   #endif
 112
 113   // Select target instructions for the DAG.
 114   SD.setRoot(SelectRoot(SD.getRoot()));
 115
 116   #ifndef NDEBUG
 117   DOUT << "===== Instruction selection ends:\n";
 118   #endif
 119
 120   SD.RemoveDeadNodes();
 121
 122   // Emit machine code to BB.
 123   ScheduleAndEmitDAG(SD);
 124 }
 125
 126 /// ComplexPattern used on MipsInstrInfo
 127 /// Used on Mips Load/Store instructions
 128 bool MipsDAGToDAGISel::
 129 SelectAddr(SDOperand Op, SDOperand Addr, SDOperand &Offset, SDOperand &Base)
 130 {
 131   // if Address is FI, get the TargetFrameIndex.
 132   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
 133     Base   = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
 134     Offset = CurDAG->getTargetConstant(0, MVT::i32);
 135     return true;
 136   }
 137
 138   // TargetExternalSymbol and TargetGlobalAddress are
 139   // lowered and their addresses go into registers, so
 140   // they should not be touched here.
 141   if ((Addr.getOpcode() == ISD::TargetExternalSymbol ||
 142        Addr.getOpcode() == ISD::TargetGlobalAddress))
 143     return false;
 144
 145   // Operand is a result from an ADD.
 146   if (Addr.getOpcode() == ISD::ADD)
 147   {
 148     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1)))
 149     {
 150       if (Predicate_immSExt16(CN))
 151       {
 152         // If the first operand is a FI, get the TargetFI Node
 153         if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>
 154                                     (Addr.getOperand(0))) {
 155           Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
 156         } else {
 157           Base = Addr.getOperand(0);
 158         }
 159
 160         Offset = CurDAG->getTargetConstant(CN->getValue(), MVT::i32);
 161         return true;
 162       }
 163     }
 164   }
 165
 166   Base   = Addr;
 167   Offset = CurDAG->getTargetConstant(0, MVT::i32);
 168   return true;
 169 }
 170
 171 /// Select instructions not customized! Used for
 172 /// expanded, promoted and normal instructions
 173 SDNode* MipsDAGToDAGISel::
 174 Select(SDOperand N)
 175 {
 176   SDNode *Node = N.Val;
 177   unsigned Opcode = Node->getOpcode();
 178
 179   // Dump information about the Node being selected
 180   #ifndef NDEBUG
 181   DOUT << std::string(Indent, ' ') << "Selecting: ";
 182   DEBUG(Node->dump(CurDAG));
 183   DOUT << "\n";
 184   Indent += 2;
 185   #endif
 186
 187   // If we have a custom node, we already have selected!
 188   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < MipsISD::FIRST_NUMBER) {
 189     #ifndef NDEBUG
 190     DOUT << std::string(Indent-2, ' ') << "== ";
 191     DEBUG(Node->dump(CurDAG));
 192     DOUT << "\n";
 193     Indent -= 2;
 194     #endif
 195     return NULL;
 196   }
 197
 198   ///
 199   // Instruction Selection not handled by custom or by the
 200   // auto-generated tablegen selection should be handled here
 201   ///
 202   switch(Opcode) {
 203
 204     default: break;
 205
 206     /// Special Mul operations
 207     case ISD::MULHS:
 208     case ISD::MULHU: {
 209       SDOperand MulOp1 = Node->getOperand(0);
 210       SDOperand MulOp2 = Node->getOperand(1);
 211       AddToISelQueue(MulOp1);
 212       AddToISelQueue(MulOp2);
 213
 214       unsigned MulOp  = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
 215       SDNode *MulNode = CurDAG->getTargetNode(MulOp, MVT::Flag, MulOp1, MulOp2);
 216
 217       SDOperand MFInFlag = SDOperand(MulNode, 0);
 218       return CurDAG->getTargetNode(Mips::MFHI, MVT::i32, MFInFlag);
 219     }
 220
 221     /// Div operations
 222     case ISD::SDIV:
 223     case ISD::UDIV: {
 224       SDOperand DivOp1 = Node->getOperand(0);
 225       SDOperand DivOp2 = Node->getOperand(1);
 226       AddToISelQueue(DivOp1);
 227       AddToISelQueue(DivOp2);
 228
 229       unsigned DivOp  = (Opcode == ISD::SDIV ? Mips::DIV : Mips::DIVu);
 230       SDNode *DivNode = CurDAG->getTargetNode(DivOp, MVT::Flag, DivOp1, DivOp2);
 231
 232       SDOperand MFInFlag = SDOperand(DivNode, 0);
 233       return CurDAG->getTargetNode(Mips::MFLO, MVT::i32, MFInFlag);
 234     }
 235
 236     /// Rem operations
 237     case ISD::SREM:
 238     case ISD::UREM: {
 239       SDOperand RemOp1 = Node->getOperand(0);
 240       SDOperand RemOp2 = Node->getOperand(1);
 241       AddToISelQueue(RemOp1);
 242       AddToISelQueue(RemOp2);
 243
 244       unsigned RemOp  = (Opcode == ISD::SREM ? Mips::DIV : Mips::DIVu);
 245       SDNode *RemNode = CurDAG->getTargetNode(RemOp, MVT::Flag, RemOp1, RemOp2);
 246
 247       SDOperand MFInFlag = SDOperand(RemNode, 0);
 248       return CurDAG->getTargetNode(Mips::MFHI, MVT::i32, MFInFlag);
 249     }
 250   }
 251
 252   // Select the default instruction
 253   SDNode *ResNode = SelectCode(N);
 254
 255   #ifndef NDEBUG
 256   DOUT << std::string(Indent-2, ' ') << "=> ";
 257   if (ResNode == NULL || ResNode == N.Val)
 258     DEBUG(N.Val->dump(CurDAG));
 259   else
 260     DEBUG(ResNode->dump(CurDAG));
 261   DOUT << "\n";
 262   Indent -= 2;
 263   #endif
 264
 265   return ResNode;
 266 }
 267
 268 /// createMipsISelDag - This pass converts a legalized DAG into a
 269 /// MIPS-specific DAG, ready for instruction scheduling.
 270 FunctionPass *llvm::createMipsISelDag(MipsTargetMachine &TM) {
 271   return new MipsDAGToDAGISel(TM);
 272 }