LLVM API Documentation

MipsISelDAGToDAG.cpp

Go to the documentation of this file.
00001 //===-- MipsISelDAGToDAG.cpp - A dag to dag inst selector for Mips --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines an instruction selector for the MIPS target.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "mips-isel"
00015 #include "Mips.h"
00016 #include "MipsISelLowering.h"
00017 #include "MipsMachineFunction.h"
00018 #include "MipsRegisterInfo.h"
00019 #include "MipsSubtarget.h"
00020 #include "MipsTargetMachine.h"
00021 #include "llvm/GlobalValue.h"
00022 #include "llvm/Instructions.h"
00023 #include "llvm/Intrinsics.h"
00024 #include "llvm/Support/CFG.h"
00025 #include "llvm/Type.h"
00026 #include "llvm/CodeGen/MachineConstantPool.h"
00027 #include "llvm/CodeGen/MachineFunction.h"
00028 #include "llvm/CodeGen/MachineFrameInfo.h"
00029 #include "llvm/CodeGen/MachineInstrBuilder.h"
00030 #include "llvm/CodeGen/MachineRegisterInfo.h"
00031 #include "llvm/CodeGen/SelectionDAGISel.h"
00032 #include "llvm/Target/TargetMachine.h"
00033 #include "llvm/Support/Compiler.h"
00034 #include "llvm/Support/Debug.h"
00035 #include "llvm/Support/ErrorHandling.h"
00036 #include "llvm/Support/raw_ostream.h"
00037 using namespace llvm;
00038 
00039 //===----------------------------------------------------------------------===//
00040 // Instruction Selector Implementation
00041 //===----------------------------------------------------------------------===//
00042 
00043 //===----------------------------------------------------------------------===//
00044 // MipsDAGToDAGISel - MIPS specific code to select MIPS machine
00045 // instructions for SelectionDAG operations.
00046 //===----------------------------------------------------------------------===//
00047 namespace {
00048 
00049 class VISIBILITY_HIDDEN MipsDAGToDAGISel : public SelectionDAGISel {
00050 
00051   /// TM - Keep a reference to MipsTargetMachine.
00052   MipsTargetMachine &TM;
00053 
00054   /// Subtarget - Keep a pointer to the MipsSubtarget around so that we can
00055   /// make the right decision when generating code for different targets.
00056   const MipsSubtarget &Subtarget;
00057  
00058 public:
00059   explicit MipsDAGToDAGISel(MipsTargetMachine &tm) :
00060   SelectionDAGISel(tm),
00061   TM(tm), Subtarget(tm.getSubtarget<MipsSubtarget>()) {}
00062   
00063   virtual void InstructionSelect();
00064 
00065   // Pass Name
00066   virtual const char *getPassName() const {
00067     return "MIPS DAG->DAG Pattern Instruction Selection";
00068   } 
00069   
00070 
00071 private:  
00072   // Include the pieces autogenerated from the target description.
00073   #include "MipsGenDAGISel.inc"
00074 
00075   /// getTargetMachine - Return a reference to the TargetMachine, casted
00076   /// to the target-specific type.
00077   const MipsTargetMachine &getTargetMachine() {
00078     return static_cast<const MipsTargetMachine &>(TM);
00079   }
00080 
00081   /// getInstrInfo - Return a reference to the TargetInstrInfo, casted
00082   /// to the target-specific type.
00083   const MipsInstrInfo *getInstrInfo() {
00084     return getTargetMachine().getInstrInfo();
00085   }
00086 
00087   SDNode *getGlobalBaseReg();
00088   SDNode *Select(SDValue N);
00089 
00090   // Complex Pattern.
00091   bool SelectAddr(SDValue Op, SDValue N, 
00092                   SDValue &Base, SDValue &Offset);
00093 
00094 
00095   // getI32Imm - Return a target constant with the specified
00096   // value, of type i32.
00097   inline SDValue getI32Imm(unsigned Imm) {
00098     return CurDAG->getTargetConstant(Imm, MVT::i32);
00099   }
00100 
00101 
00102   #ifndef NDEBUG
00103   unsigned Indent;
00104   #endif
00105 };
00106 
00107 }
00108 
00109 /// InstructionSelect - This callback is invoked by
00110 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
00111 void MipsDAGToDAGISel::
00112 InstructionSelect() 
00113 {
00114   DEBUG(BB->dump());
00115   // Codegen the basic block.
00116   #ifndef NDEBUG
00117   DOUT << "===== Instruction selection begins:\n";
00118   Indent = 0;
00119   #endif
00120 
00121   // Select target instructions for the DAG.
00122   SelectRoot(*CurDAG);
00123 
00124   #ifndef NDEBUG
00125   DOUT << "===== Instruction selection ends:\n";
00126   #endif
00127 
00128   CurDAG->RemoveDeadNodes();
00129 }
00130 
00131 /// getGlobalBaseReg - Output the instructions required to put the
00132 /// GOT address into a register.
00133 SDNode *MipsDAGToDAGISel::getGlobalBaseReg() {
00134   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
00135   return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
00136 }
00137 
00138 /// ComplexPattern used on MipsInstrInfo
00139 /// Used on Mips Load/Store instructions
00140 bool MipsDAGToDAGISel::
00141 SelectAddr(SDValue Op, SDValue Addr, SDValue &Offset, SDValue &Base)
00142 {
00143   // if Address is FI, get the TargetFrameIndex.
00144   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
00145     Base   = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
00146     Offset = CurDAG->getTargetConstant(0, MVT::i32);
00147     return true;
00148   }
00149     
00150   // on PIC code Load GA
00151   if (TM.getRelocationModel() == Reloc::PIC_) {
00152     if ((Addr.getOpcode() == ISD::TargetGlobalAddress) || 
00153         (Addr.getOpcode() == ISD::TargetJumpTable)){
00154       Base   = CurDAG->getRegister(Mips::GP, MVT::i32);
00155       Offset = Addr;
00156       return true;
00157     }
00158   } else {
00159     if ((Addr.getOpcode() == ISD::TargetExternalSymbol ||
00160         Addr.getOpcode() == ISD::TargetGlobalAddress))
00161       return false;
00162   }    
00163   
00164   // Operand is a result from an ADD.
00165   if (Addr.getOpcode() == ISD::ADD) {
00166     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) {
00167       if (Predicate_immSExt16(CN)) {
00168 
00169         // If the first operand is a FI, get the TargetFI Node
00170         if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>
00171                                     (Addr.getOperand(0))) {
00172           Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
00173         } else {
00174           Base = Addr.getOperand(0);
00175         }
00176 
00177         Offset = CurDAG->getTargetConstant(CN->getZExtValue(), MVT::i32);
00178         return true;
00179       }
00180     }
00181   }
00182 
00183   Base   = Addr;
00184   Offset = CurDAG->getTargetConstant(0, MVT::i32);
00185   return true;
00186 }
00187 
00188 /// Select instructions not customized! Used for
00189 /// expanded, promoted and normal instructions
00190 SDNode* MipsDAGToDAGISel::
00191 Select(SDValue N) 
00192 {
00193   SDNode *Node = N.getNode();
00194   unsigned Opcode = Node->getOpcode();
00195   DebugLoc dl = Node->getDebugLoc();
00196 
00197   // Dump information about the Node being selected
00198   #ifndef NDEBUG
00199   DOUT << std::string(Indent, ' ') << "Selecting: ";
00200   DEBUG(Node->dump(CurDAG));
00201   DOUT << "\n";
00202   Indent += 2;
00203   #endif
00204 
00205   // If we have a custom node, we already have selected!
00206   if (Node->isMachineOpcode()) {
00207     #ifndef NDEBUG
00208     DOUT << std::string(Indent-2, ' ') << "== ";
00209     DEBUG(Node->dump(CurDAG));
00210     DOUT << "\n";
00211     Indent -= 2;
00212     #endif
00213     return NULL;
00214   }
00215 
00216   ///
00217   // Instruction Selection not handled by the auto-generated 
00218   // tablegen selection should be handled here.
00219   /// 
00220   switch(Opcode) {
00221 
00222     default: break;
00223 
00224     case ISD::SUBE: 
00225     case ISD::ADDE: {
00226       SDValue InFlag = Node->getOperand(2), CmpLHS;
00227       unsigned Opc = InFlag.getOpcode(); Opc=Opc;
00228       assert(((Opc == ISD::ADDC || Opc == ISD::ADDE) || 
00229               (Opc == ISD::SUBC || Opc == ISD::SUBE)) &&  
00230              "(ADD|SUB)E flag operand must come from (ADD|SUB)C/E insn");
00231 
00232       unsigned MOp;
00233       if (Opcode == ISD::ADDE) {
00234         CmpLHS = InFlag.getValue(0);
00235         MOp = Mips::ADDu;
00236       } else { 
00237         CmpLHS = InFlag.getOperand(0);
00238         MOp = Mips::SUBu;
00239       }
00240 
00241       SDValue Ops[] = { CmpLHS, InFlag.getOperand(1) };
00242 
00243       SDValue LHS = Node->getOperand(0);
00244       SDValue RHS = Node->getOperand(1);
00245 
00246       EVT VT = LHS.getValueType();
00247       SDNode *Carry = CurDAG->getTargetNode(Mips::SLTu, dl, VT, Ops, 2);
00248       SDNode *AddCarry = CurDAG->getTargetNode(Mips::ADDu, dl, VT, 
00249                                                SDValue(Carry,0), RHS);
00250 
00251       return CurDAG->SelectNodeTo(N.getNode(), MOp, VT, MVT::Flag,
00252                                   LHS, SDValue(AddCarry,0));
00253     }
00254 
00255     /// Mul/Div with two results
00256     case ISD::SDIVREM:
00257     case ISD::UDIVREM:
00258     case ISD::SMUL_LOHI:
00259     case ISD::UMUL_LOHI: {
00260       SDValue Op1 = Node->getOperand(0);
00261       SDValue Op2 = Node->getOperand(1);
00262 
00263       unsigned Op;
00264       if (Opcode == ISD::UMUL_LOHI || Opcode == ISD::SMUL_LOHI)
00265         Op = (Opcode == ISD::UMUL_LOHI ? Mips::MULTu : Mips::MULT);
00266       else
00267         Op = (Opcode == ISD::UDIVREM ? Mips::DIVu : Mips::DIV);
00268 
00269       SDNode *Node = CurDAG->getTargetNode(Op, dl, MVT::Flag, Op1, Op2);
00270 
00271       SDValue InFlag = SDValue(Node, 0);
00272       SDNode *Lo = CurDAG->getTargetNode(Mips::MFLO, dl, MVT::i32, 
00273                                          MVT::Flag, InFlag);
00274       InFlag = SDValue(Lo,1);
00275       SDNode *Hi = CurDAG->getTargetNode(Mips::MFHI, dl, MVT::i32, InFlag);
00276 
00277       if (!N.getValue(0).use_empty()) 
00278         ReplaceUses(N.getValue(0), SDValue(Lo,0));
00279 
00280       if (!N.getValue(1).use_empty()) 
00281         ReplaceUses(N.getValue(1), SDValue(Hi,0));
00282 
00283       return NULL;
00284     }
00285 
00286     /// Special Muls
00287     case ISD::MUL: 
00288     case ISD::MULHS:
00289     case ISD::MULHU: {
00290       SDValue MulOp1 = Node->getOperand(0);
00291       SDValue MulOp2 = Node->getOperand(1);
00292 
00293       unsigned MulOp  = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
00294       SDNode *MulNode = CurDAG->getTargetNode(MulOp, dl, 
00295                                               MVT::Flag, MulOp1, MulOp2);
00296 
00297       SDValue InFlag = SDValue(MulNode, 0);
00298 
00299       if (MulOp == ISD::MUL)
00300         return CurDAG->getTargetNode(Mips::MFLO, dl, MVT::i32, InFlag);
00301       else
00302         return CurDAG->getTargetNode(Mips::MFHI, dl, MVT::i32, InFlag);
00303     }
00304 
00305     /// Div/Rem operations
00306     case ISD::SREM:
00307     case ISD::UREM:
00308     case ISD::SDIV: 
00309     case ISD::UDIV: {
00310       SDValue Op1 = Node->getOperand(0);
00311       SDValue Op2 = Node->getOperand(1);
00312 
00313       unsigned Op, MOp;
00314       if (Opcode == ISD::SDIV || Opcode == ISD::UDIV) {
00315         Op  = (Opcode == ISD::SDIV ? Mips::DIV : Mips::DIVu);
00316         MOp = Mips::MFLO;
00317       } else {
00318         Op  = (Opcode == ISD::SREM ? Mips::DIV : Mips::DIVu);
00319         MOp = Mips::MFHI;
00320       }
00321       SDNode *Node = CurDAG->getTargetNode(Op, dl, MVT::Flag, Op1, Op2);
00322 
00323       SDValue InFlag = SDValue(Node, 0);
00324       return CurDAG->getTargetNode(MOp, dl, MVT::i32, InFlag);
00325     }
00326 
00327     // Get target GOT address.
00328     case ISD::GLOBAL_OFFSET_TABLE:
00329       return getGlobalBaseReg();
00330 
00331     /// Handle direct and indirect calls when using PIC. On PIC, when 
00332     /// GOT is smaller than about 64k (small code) the GA target is 
00333     /// loaded with only one instruction. Otherwise GA's target must 
00334     /// be loaded with 3 instructions. 
00335     case MipsISD::JmpLink: {
00336       if (TM.getRelocationModel() == Reloc::PIC_) {
00337         //bool isCodeLarge = (TM.getCodeModel() == CodeModel::Large);
00338         SDValue Chain  = Node->getOperand(0);
00339         SDValue Callee = Node->getOperand(1);
00340         SDValue T9Reg = CurDAG->getRegister(Mips::T9, MVT::i32);
00341         SDValue InFlag(0, 0);
00342 
00343         if ( (isa<GlobalAddressSDNode>(Callee)) ||
00344              (isa<ExternalSymbolSDNode>(Callee)) )
00345         {
00346           /// Direct call for global addresses and external symbols
00347           SDValue GPReg = CurDAG->getRegister(Mips::GP, MVT::i32);
00348 
00349           // Use load to get GOT target
00350           SDValue Ops[] = { Callee, GPReg, Chain };
00351           SDValue Load = SDValue(CurDAG->getTargetNode(Mips::LW, dl, MVT::i32, 
00352                                      MVT::Other, Ops, 3), 0);
00353           Chain = Load.getValue(1);
00354 
00355           // Call target must be on T9
00356           Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Load, InFlag);
00357         } else 
00358           /// Indirect call
00359           Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Callee, InFlag);
00360 
00361         // Emit Jump and Link Register
00362         SDNode *ResNode = CurDAG->getTargetNode(Mips::JALR, dl, MVT::Other,
00363                                   MVT::Flag, T9Reg, Chain);
00364         Chain  = SDValue(ResNode, 0);
00365         InFlag = SDValue(ResNode, 1);
00366         ReplaceUses(SDValue(Node, 0), Chain);
00367         ReplaceUses(SDValue(Node, 1), InFlag);
00368         return ResNode;
00369       } 
00370     }
00371   }
00372 
00373   // Select the default instruction
00374   SDNode *ResNode = SelectCode(N);
00375 
00376   #ifndef NDEBUG
00377   DOUT << std::string(Indent-2, ' ') << "=> ";
00378   if (ResNode == NULL || ResNode == N.getNode())
00379     DEBUG(N.getNode()->dump(CurDAG));
00380   else
00381     DEBUG(ResNode->dump(CurDAG));
00382   DOUT << "\n";
00383   Indent -= 2;
00384   #endif
00385 
00386   return ResNode;
00387 }
00388 
00389 /// createMipsISelDag - This pass converts a legalized DAG into a 
00390 /// MIPS-specific DAG, ready for instruction scheduling.
00391 FunctionPass *llvm::createMipsISelDag(MipsTargetMachine &TM) {
00392   return new MipsDAGToDAGISel(TM);
00393 }