LLVM API Documentation

X86ISelDAGToDAG.cpp

Go to the documentation of this file.
00001 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the Evan Cheng and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines a DAG pattern matching instruction selector for X86,
00011 // converting from a legalized dag to a X86 dag.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "isel"
00016 #include "X86.h"
00017 #include "X86InstrBuilder.h"
00018 #include "X86ISelLowering.h"
00019 #include "X86RegisterInfo.h"
00020 #include "X86Subtarget.h"
00021 #include "X86TargetMachine.h"
00022 #include "llvm/GlobalValue.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/Intrinsics.h"
00025 #include "llvm/Support/CFG.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/SSARegMap.h"
00031 #include "llvm/CodeGen/SelectionDAGISel.h"
00032 #include "llvm/Target/TargetMachine.h"
00033 #include "llvm/Support/Debug.h"
00034 #include "llvm/Support/Visibility.h"
00035 #include "llvm/ADT/Statistic.h"
00036 #include <iostream>
00037 #include <set>
00038 using namespace llvm;
00039 
00040 //===----------------------------------------------------------------------===//
00041 //                      Pattern Matcher Implementation
00042 //===----------------------------------------------------------------------===//
00043 
00044 namespace {
00045   /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
00046   /// SDOperand's instead of register numbers for the leaves of the matched
00047   /// tree.
00048   struct X86ISelAddressMode {
00049     enum {
00050       RegBase,
00051       FrameIndexBase
00052     } BaseType;
00053 
00054     struct {            // This is really a union, discriminated by BaseType!
00055       SDOperand Reg;
00056       int FrameIndex;
00057     } Base;
00058 
00059     unsigned Scale;
00060     SDOperand IndexReg; 
00061     unsigned Disp;
00062     GlobalValue *GV;
00063     Constant *CP;
00064     unsigned Align;    // CP alignment.
00065 
00066     X86ISelAddressMode()
00067       : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0),
00068         CP(0), Align(0) {
00069     }
00070   };
00071 }
00072 
00073 namespace {
00074   Statistic<>
00075   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
00076 
00077   //===--------------------------------------------------------------------===//
00078   /// ISel - X86 specific code to select X86 machine instructions for
00079   /// SelectionDAG operations.
00080   ///
00081   class VISIBILITY_HIDDEN X86DAGToDAGISel : public SelectionDAGISel {
00082     /// ContainsFPCode - Every instruction we select that uses or defines a FP
00083     /// register should set this to true.
00084     bool ContainsFPCode;
00085 
00086     /// X86Lowering - This object fully describes how to lower LLVM code to an
00087     /// X86-specific SelectionDAG.
00088     X86TargetLowering X86Lowering;
00089 
00090     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
00091     /// make the right decision when generating code for different targets.
00092     const X86Subtarget *Subtarget;
00093 
00094     unsigned GlobalBaseReg;
00095   public:
00096     X86DAGToDAGISel(X86TargetMachine &TM)
00097       : SelectionDAGISel(X86Lowering),
00098         X86Lowering(*TM.getTargetLowering()) {
00099       Subtarget = &TM.getSubtarget<X86Subtarget>();
00100     }
00101 
00102     virtual bool runOnFunction(Function &Fn) {
00103       // Make sure we re-emit a set of the global base reg if necessary
00104       GlobalBaseReg = 0;
00105       return SelectionDAGISel::runOnFunction(Fn);
00106     }
00107    
00108     virtual const char *getPassName() const {
00109       return "X86 DAG->DAG Instruction Selection";
00110     }
00111 
00112     /// InstructionSelectBasicBlock - This callback is invoked by
00113     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
00114     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
00115 
00116     virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF);
00117 
00118 // Include the pieces autogenerated from the target description.
00119 #include "X86GenDAGISel.inc"
00120 
00121   private:
00122     void Select(SDOperand &Result, SDOperand N);
00123 
00124     bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true);
00125     bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
00126                     SDOperand &Index, SDOperand &Disp);
00127     bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
00128                        SDOperand &Index, SDOperand &Disp);
00129     bool TryFoldLoad(SDOperand P, SDOperand N,
00130                      SDOperand &Base, SDOperand &Scale,
00131                      SDOperand &Index, SDOperand &Disp);
00132     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
00133     /// inline asm expressions.
00134     virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
00135                                               char ConstraintCode,
00136                                               std::vector<SDOperand> &OutOps,
00137                                               SelectionDAG &DAG);
00138     
00139     void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI);
00140 
00141     inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base, 
00142                                    SDOperand &Scale, SDOperand &Index,
00143                                    SDOperand &Disp) {
00144       Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
00145         CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg;
00146       Scale = getI8Imm(AM.Scale);
00147       Index = AM.IndexReg;
00148       Disp  = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
00149         : (AM.CP ?
00150            CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp)
00151            : getI32Imm(AM.Disp));
00152     }
00153 
00154     /// getI8Imm - Return a target constant with the specified value, of type
00155     /// i8.
00156     inline SDOperand getI8Imm(unsigned Imm) {
00157       return CurDAG->getTargetConstant(Imm, MVT::i8);
00158     }
00159 
00160     /// getI16Imm - Return a target constant with the specified value, of type
00161     /// i16.
00162     inline SDOperand getI16Imm(unsigned Imm) {
00163       return CurDAG->getTargetConstant(Imm, MVT::i16);
00164     }
00165 
00166     /// getI32Imm - Return a target constant with the specified value, of type
00167     /// i32.
00168     inline SDOperand getI32Imm(unsigned Imm) {
00169       return CurDAG->getTargetConstant(Imm, MVT::i32);
00170     }
00171 
00172     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
00173     /// base register.  Return the virtual register that holds this value.
00174     SDOperand getGlobalBaseReg();
00175 
00176 #ifndef NDEBUG
00177     unsigned Indent;
00178 #endif
00179   };
00180 }
00181 
00182 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
00183 /// when it has created a SelectionDAG for us to codegen.
00184 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
00185   DEBUG(BB->dump());
00186   MachineFunction::iterator FirstMBB = BB;
00187 
00188   // Codegen the basic block.
00189 #ifndef NDEBUG
00190   DEBUG(std::cerr << "===== Instruction selection begins:\n");
00191   Indent = 0;
00192 #endif
00193   DAG.setRoot(SelectRoot(DAG.getRoot()));
00194   assert(InFlightSet.empty() && "ISel InFlightSet has not been emptied!");
00195 #ifndef NDEBUG
00196   DEBUG(std::cerr << "===== Instruction selection ends:\n");
00197 #endif
00198   CodeGenMap.clear();
00199   HandleMap.clear();
00200   ReplaceMap.clear();
00201   DAG.RemoveDeadNodes();
00202 
00203   // Emit machine code to BB. 
00204   ScheduleAndEmitDAG(DAG);
00205   
00206   // If we are emitting FP stack code, scan the basic block to determine if this
00207   // block defines any FP values.  If so, put an FP_REG_KILL instruction before
00208   // the terminator of the block.
00209   if (!Subtarget->hasSSE2()) {
00210     // Note that FP stack instructions *are* used in SSE code when returning
00211     // values, but these are not live out of the basic block, so we don't need
00212     // an FP_REG_KILL in this case either.
00213     bool ContainsFPCode = false;
00214     
00215     // Scan all of the machine instructions in these MBBs, checking for FP
00216     // stores.
00217     MachineFunction::iterator MBBI = FirstMBB;
00218     do {
00219       for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end();
00220            !ContainsFPCode && I != E; ++I) {
00221         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
00222           if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() &&
00223               MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) &&
00224               RegMap->getRegClass(I->getOperand(0).getReg()) == 
00225                 X86::RFPRegisterClass) {
00226             ContainsFPCode = true;
00227             break;
00228           }
00229         }
00230       }
00231     } while (!ContainsFPCode && &*(MBBI++) != BB);
00232     
00233     // Check PHI nodes in successor blocks.  These PHI's will be lowered to have
00234     // a copy of the input value in this block.
00235     if (!ContainsFPCode) {
00236       // Final check, check LLVM BB's that are successors to the LLVM BB
00237       // corresponding to BB for FP PHI nodes.
00238       const BasicBlock *LLVMBB = BB->getBasicBlock();
00239       const PHINode *PN;
00240       for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB);
00241            !ContainsFPCode && SI != E; ++SI) {
00242         for (BasicBlock::const_iterator II = SI->begin();
00243              (PN = dyn_cast<PHINode>(II)); ++II) {
00244           if (PN->getType()->isFloatingPoint()) {
00245             ContainsFPCode = true;
00246             break;
00247           }
00248         }
00249       }
00250     }
00251 
00252     // Finally, if we found any FP code, emit the FP_REG_KILL instruction.
00253     if (ContainsFPCode) {
00254       BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
00255       ++NumFPKill;
00256     }
00257   }
00258 }
00259 
00260 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
00261 /// the main function.
00262 void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB,
00263                                              MachineFrameInfo *MFI) {
00264   if (Subtarget->TargetType == X86Subtarget::isCygwin)
00265     BuildMI(BB, X86::CALLpcrel32, 1).addExternalSymbol("__main");
00266 
00267   // Switch the FPU to 64-bit precision mode for better compatibility and speed.
00268   int CWFrameIdx = MFI->CreateStackObject(2, 2);
00269   addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
00270 
00271   // Set the high part to be 64-bit precision.
00272   addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
00273                     CWFrameIdx, 1).addImm(2);
00274 
00275   // Reload the modified control word now.
00276   addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
00277 }
00278 
00279 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {
00280   // If this is main, emit special code for main.
00281   MachineBasicBlock *BB = MF.begin();
00282   if (Fn.hasExternalLinkage() && Fn.getName() == "main")
00283     EmitSpecialCodeForMain(BB, MF.getFrameInfo());
00284 }
00285 
00286 /// MatchAddress - Add the specified node to the specified addressing mode,
00287 /// returning true if it cannot be done.  This just pattern matches for the
00288 /// addressing mode
00289 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM,
00290                                    bool isRoot) {
00291   bool Available = false;
00292   // If N has already been selected, reuse the result unless in some very
00293   // specific cases.
00294   std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0));
00295   if (CGMI != CodeGenMap.end()) {
00296     Available = true;
00297   }
00298 
00299   switch (N.getOpcode()) {
00300   default: break;
00301   case ISD::Constant:
00302     AM.Disp += cast<ConstantSDNode>(N)->getValue();
00303     return false;
00304 
00305   case X86ISD::Wrapper:
00306     // If both base and index components have been picked, we can't fit
00307     // the result available in the register in the addressing mode. Duplicate
00308     // GlobalAddress or ConstantPool as displacement.
00309     if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) {
00310       if (ConstantPoolSDNode *CP =
00311           dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) {
00312         if (AM.CP == 0) {
00313           AM.CP = CP->get();
00314           AM.Align = CP->getAlignment();
00315           AM.Disp += CP->getOffset();
00316           return false;
00317         }
00318       } else if (GlobalAddressSDNode *G =
00319                  dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) {
00320         if (AM.GV == 0) {
00321           AM.GV = G->getGlobal();
00322           AM.Disp += G->getOffset();
00323           return false;
00324         }
00325       }
00326     }
00327     break;
00328 
00329   case ISD::FrameIndex:
00330     if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
00331       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
00332       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
00333       return false;
00334     }
00335     break;
00336 
00337   case ISD::SHL:
00338     if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1)
00339       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
00340         unsigned Val = CN->getValue();
00341         if (Val == 1 || Val == 2 || Val == 3) {
00342           AM.Scale = 1 << Val;
00343           SDOperand ShVal = N.Val->getOperand(0);
00344 
00345           // Okay, we know that we have a scale by now.  However, if the scaled
00346           // value is an add of something and a constant, we can fold the
00347           // constant into the disp field here.
00348           if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
00349               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
00350             AM.IndexReg = ShVal.Val->getOperand(0);
00351             ConstantSDNode *AddVal =
00352               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
00353             AM.Disp += AddVal->getValue() << Val;
00354           } else {
00355             AM.IndexReg = ShVal;
00356           }
00357           return false;
00358         }
00359       }
00360     break;
00361 
00362   case ISD::MUL:
00363     // X*[3,5,9] -> X+X*[2,4,8]
00364     if (!Available &&
00365         AM.BaseType == X86ISelAddressMode::RegBase &&
00366         AM.Base.Reg.Val == 0 &&
00367         AM.IndexReg.Val == 0)
00368       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
00369         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
00370           AM.Scale = unsigned(CN->getValue())-1;
00371 
00372           SDOperand MulVal = N.Val->getOperand(0);
00373           SDOperand Reg;
00374 
00375           // Okay, we know that we have a scale by now.  However, if the scaled
00376           // value is an add of something and a constant, we can fold the
00377           // constant into the disp field here.
00378           if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
00379               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
00380             Reg = MulVal.Val->getOperand(0);
00381             ConstantSDNode *AddVal =
00382               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
00383             AM.Disp += AddVal->getValue() * CN->getValue();
00384           } else {
00385             Reg = N.Val->getOperand(0);
00386           }
00387 
00388           AM.IndexReg = AM.Base.Reg = Reg;
00389           return false;
00390         }
00391     break;
00392 
00393   case ISD::ADD: {
00394     if (!Available) {
00395       X86ISelAddressMode Backup = AM;
00396       if (!MatchAddress(N.Val->getOperand(0), AM, false) &&
00397           !MatchAddress(N.Val->getOperand(1), AM, false))
00398         return false;
00399       AM = Backup;
00400       if (!MatchAddress(N.Val->getOperand(1), AM, false) &&
00401           !MatchAddress(N.Val->getOperand(0), AM, false))
00402         return false;
00403       AM = Backup;
00404     }
00405     break;
00406   }
00407 
00408   case ISD::OR: {
00409     if (!Available) {
00410       X86ISelAddressMode Backup = AM;
00411       // Look for (x << c1) | c2 where (c2 < c1)
00412       ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(0));
00413       if (CN && !MatchAddress(N.Val->getOperand(1), AM, false)) {
00414         if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) {
00415           AM.Disp = CN->getValue();
00416           return false;
00417         }
00418       }
00419       AM = Backup;
00420       CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1));
00421       if (CN && !MatchAddress(N.Val->getOperand(0), AM, false)) {
00422         if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) {
00423           AM.Disp = CN->getValue();
00424           return false;
00425         }
00426       }
00427       AM = Backup;
00428     }
00429     break;
00430   }
00431   }
00432 
00433   // Is the base register already occupied?
00434   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
00435     // If so, check to see if the scale index register is set.
00436     if (AM.IndexReg.Val == 0) {
00437       AM.IndexReg = N;
00438       AM.Scale = 1;
00439       return false;
00440     }
00441 
00442     // Otherwise, we cannot select it.
00443     return true;
00444   }
00445 
00446   // Default, generate it as a register.
00447   AM.BaseType = X86ISelAddressMode::RegBase;
00448   AM.Base.Reg = N;
00449   return false;
00450 }
00451 
00452 /// SelectAddr - returns true if it is able pattern match an addressing mode.
00453 /// It returns the operands which make up the maximal addressing mode it can
00454 /// match by reference.
00455 bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
00456                                  SDOperand &Index, SDOperand &Disp) {
00457   X86ISelAddressMode AM;
00458   if (MatchAddress(N, AM))
00459     return false;
00460 
00461   if (AM.BaseType == X86ISelAddressMode::RegBase) {
00462     if (!AM.Base.Reg.Val)
00463       AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
00464   }
00465 
00466   if (!AM.IndexReg.Val)
00467     AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
00468 
00469   getAddressOperands(AM, Base, Scale, Index, Disp);
00470 
00471   return true;
00472 }
00473 
00474 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
00475 /// mode it matches can be cost effectively emitted as an LEA instruction.
00476 bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base,
00477                                     SDOperand &Scale,
00478                                     SDOperand &Index, SDOperand &Disp) {
00479   X86ISelAddressMode AM;
00480   if (MatchAddress(N, AM))
00481     return false;
00482 
00483   unsigned Complexity = 0;
00484   if (AM.BaseType == X86ISelAddressMode::RegBase)
00485     if (AM.Base.Reg.Val)
00486       Complexity = 1;
00487     else
00488       AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
00489   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
00490     Complexity = 4;
00491 
00492   if (AM.IndexReg.Val)
00493     Complexity++;
00494   else
00495     AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
00496 
00497   if (AM.Scale > 2) 
00498     Complexity += 2;
00499   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg
00500   else if (AM.Scale > 1)
00501     Complexity++;
00502 
00503   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
00504   // to a LEA. This is determined with some expermentation but is by no means
00505   // optimal (especially for code size consideration). LEA is nice because of
00506   // its three-address nature. Tweak the cost function again when we can run
00507   // convertToThreeAddress() at register allocation time.
00508   if (AM.GV || AM.CP)
00509     Complexity += 2;
00510 
00511   if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val))
00512     Complexity++;
00513 
00514   if (Complexity > 2) {
00515     getAddressOperands(AM, Base, Scale, Index, Disp);
00516     return true;
00517   }
00518 
00519   return false;
00520 }
00521 
00522 bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N,
00523                                   SDOperand &Base, SDOperand &Scale,
00524                                   SDOperand &Index, SDOperand &Disp) {
00525   if (N.getOpcode() == ISD::LOAD &&
00526       N.hasOneUse() &&
00527       !CodeGenMap.count(N.getValue(0)) &&
00528       (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val)))
00529     return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp);
00530   return false;
00531 }
00532 
00533 static bool isRegister0(SDOperand Op) {
00534   if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op))
00535     return (R->getReg() == 0);
00536   return false;
00537 }
00538 
00539 /// getGlobalBaseReg - Output the instructions required to put the
00540 /// base address to use for accessing globals into a register.
00541 ///
00542 SDOperand X86DAGToDAGISel::getGlobalBaseReg() {
00543   if (!GlobalBaseReg) {
00544     // Insert the set of GlobalBaseReg into the first MBB of the function
00545     MachineBasicBlock &FirstMBB = BB->getParent()->front();
00546     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
00547     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
00548     // FIXME: when we get to LP64, we will need to create the appropriate
00549     // type of register here.
00550     GlobalBaseReg = RegMap->createVirtualRegister(X86::GR32RegisterClass);
00551     BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0);
00552     BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg);
00553   }
00554   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
00555 }
00556 
00557 static SDNode *FindCallStartFromCall(SDNode *Node) {
00558   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
00559     assert(Node->getOperand(0).getValueType() == MVT::Other &&
00560          "Node doesn't have a token chain argument!");
00561   return FindCallStartFromCall(Node->getOperand(0).Val);
00562 }
00563 
00564 void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) {
00565   SDNode *Node = N.Val;
00566   MVT::ValueType NVT = Node->getValueType(0);
00567   unsigned Opc, MOpc;
00568   unsigned Opcode = Node->getOpcode();
00569 
00570 #ifndef NDEBUG
00571   DEBUG(std::cerr << std::string(Indent, ' '));
00572   DEBUG(std::cerr << "Selecting: ");
00573   DEBUG(Node->dump(CurDAG));
00574   DEBUG(std::cerr << "\n");
00575   Indent += 2;
00576 #endif
00577 
00578   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) {
00579     Result = N;
00580 #ifndef NDEBUG
00581     DEBUG(std::cerr << std::string(Indent-2, ' '));
00582     DEBUG(std::cerr << "== ");
00583     DEBUG(Node->dump(CurDAG));
00584     DEBUG(std::cerr << "\n");
00585     Indent -= 2;
00586 #endif
00587     return;   // Already selected.
00588   }
00589 
00590   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);
00591   if (CGMI != CodeGenMap.end()) {
00592     Result = CGMI->second;
00593 #ifndef NDEBUG
00594     DEBUG(std::cerr << std::string(Indent-2, ' '));
00595     DEBUG(std::cerr << "== ");
00596     DEBUG(Result.Val->dump(CurDAG));
00597     DEBUG(std::cerr << "\n");
00598     Indent -= 2;
00599 #endif
00600     return;
00601   }
00602   
00603   switch (Opcode) {
00604     default: break;
00605     case X86ISD::GlobalBaseReg: 
00606       Result = getGlobalBaseReg();
00607       return;
00608 
00609     case ISD::ADD: {
00610       // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd
00611       // code and is matched first so to prevent it from being turned into
00612       // LEA32r X+c.
00613       SDOperand N0 = N.getOperand(0);
00614       SDOperand N1 = N.getOperand(1);
00615       if (N.Val->getValueType(0) == MVT::i32 &&
00616           N0.getOpcode() == X86ISD::Wrapper &&
00617           N1.getOpcode() == ISD::Constant) {
00618         unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue();
00619         SDOperand C(0, 0);
00620         // TODO: handle ExternalSymbolSDNode.
00621         if (GlobalAddressSDNode *G =
00622             dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) {
00623           C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32,
00624                                              G->getOffset() + Offset);
00625         } else if (ConstantPoolSDNode *CP =
00626                    dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) {
00627           C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32,
00628                                             CP->getAlignment(),
00629                                             CP->getOffset()+Offset);
00630         }
00631 
00632         if (C.Val) {
00633           if (N.Val->hasOneUse()) {
00634             Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C);
00635           } else {
00636             SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C);
00637             Result = CodeGenMap[N] = SDOperand(ResNode, 0);
00638           }
00639           return;
00640         }
00641       }
00642 
00643       // Other cases are handled by auto-generated code.
00644       break;
00645     }
00646 
00647     case ISD::MULHU:
00648     case ISD::MULHS: {
00649       if (Opcode == ISD::MULHU)
00650         switch (NVT) {
00651         default: assert(0 && "Unsupported VT!");
00652         case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
00653         case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
00654         case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
00655         }
00656       else
00657         switch (NVT) {
00658         default: assert(0 && "Unsupported VT!");
00659         case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
00660         case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
00661         case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
00662         }
00663 
00664       unsigned LoReg, HiReg;
00665       switch (NVT) {
00666       default: assert(0 && "Unsupported VT!");
00667       case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
00668       case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
00669       case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
00670       }
00671 
00672       SDOperand N0 = Node->getOperand(0);
00673       SDOperand N1 = Node->getOperand(1);
00674 
00675       bool foldedLoad = false;
00676       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
00677       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
00678       // MULHU and MULHS are commmutative
00679       if (!foldedLoad) {
00680         foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3);
00681         if (foldedLoad) {
00682           N0 = Node->getOperand(1);
00683           N1 = Node->getOperand(0);
00684         }
00685       }
00686 
00687       SDOperand Chain;
00688       if (foldedLoad)
00689         Select(Chain, N1.getOperand(0));
00690       else
00691         Chain = CurDAG->getEntryNode();
00692 
00693       SDOperand InFlag(0, 0);
00694       Select(N0, N0);
00695       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
00696                                     N0, InFlag);
00697       InFlag = Chain.getValue(1);
00698 
00699       if (foldedLoad) {
00700         Select(Tmp0, Tmp0);
00701         Select(Tmp1, Tmp1);
00702         Select(Tmp2, Tmp2);
00703         Select(Tmp3, Tmp3);
00704         SDNode *CNode =
00705           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
00706                                 Tmp2, Tmp3, Chain, InFlag);
00707         Chain  = SDOperand(CNode, 0);
00708         InFlag = SDOperand(CNode, 1);
00709       } else {
00710         Select(N1, N1);
00711         InFlag =
00712           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
00713       }
00714 
00715       Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag);
00716       CodeGenMap[N.getValue(0)] = Result;
00717       if (foldedLoad) {
00718         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
00719         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
00720       }
00721 
00722 #ifndef NDEBUG
00723       DEBUG(std::cerr << std::string(Indent-2, ' '));
00724       DEBUG(std::cerr << "== ");
00725       DEBUG(Result.Val->dump(CurDAG));
00726       DEBUG(std::cerr << "\n");
00727       Indent -= 2;
00728 #endif
00729       return;
00730     }
00731       
00732     case ISD::SDIV:
00733     case ISD::UDIV:
00734     case ISD::SREM:
00735     case ISD::UREM: {
00736       bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM;
00737       bool isDiv    = Opcode == ISD::SDIV || Opcode == ISD::UDIV;
00738       if (!isSigned)
00739         switch (NVT) {
00740         default: assert(0 && "Unsupported VT!");
00741         case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
00742         case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
00743         case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
00744         }
00745       else
00746         switch (NVT) {
00747         default: assert(0 && "Unsupported VT!");
00748         case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
00749         case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
00750         case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
00751         }
00752 
00753       unsigned LoReg, HiReg;
00754       unsigned ClrOpcode, SExtOpcode;
00755       switch (NVT) {
00756       default: assert(0 && "Unsupported VT!");
00757       case MVT::i8:
00758         LoReg = X86::AL;  HiReg = X86::AH;
00759         ClrOpcode  = X86::MOV8r0;
00760         SExtOpcode = X86::CBW;
00761         break;
00762       case MVT::i16:
00763         LoReg = X86::AX;  HiReg = X86::DX;
00764         ClrOpcode  = X86::MOV16r0;
00765         SExtOpcode = X86::CWD;
00766         break;
00767       case MVT::i32:
00768         LoReg = X86::EAX; HiReg = X86::EDX;
00769         ClrOpcode  = X86::MOV32r0;
00770         SExtOpcode = X86::CDQ;
00771         break;
00772       }
00773 
00774       SDOperand N0 = Node->getOperand(0);
00775       SDOperand N1 = Node->getOperand(1);
00776 
00777       bool foldedLoad = false;
00778       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
00779       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
00780       SDOperand Chain;
00781       if (foldedLoad)
00782         Select(Chain, N1.getOperand(0));
00783       else
00784         Chain = CurDAG->getEntryNode();
00785 
00786       SDOperand InFlag(0, 0);
00787       Select(N0, N0);
00788       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
00789                                     N0, InFlag);
00790       InFlag = Chain.getValue(1);
00791 
00792       if (isSigned) {
00793         // Sign extend the low part into the high part.
00794         InFlag =
00795           SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0);
00796       } else {
00797         // Zero out the high part, effectively zero extending the input.
00798         SDOperand ClrNode = SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT), 0);
00799         Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT),
00800                                       ClrNode, InFlag);
00801         InFlag = Chain.getValue(1);
00802       }
00803 
00804       if (foldedLoad) {
00805         Select(Tmp0, Tmp0);
00806         Select(Tmp1, Tmp1);
00807         Select(Tmp2, Tmp2);
00808         Select(Tmp3, Tmp3);
00809         SDNode *CNode =
00810           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
00811                                 Tmp2, Tmp3, Chain, InFlag);
00812         Chain  = SDOperand(CNode, 0);
00813         InFlag = SDOperand(CNode, 1);
00814       } else {
00815         Select(N1, N1);
00816         InFlag =
00817           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
00818       }
00819 
00820       Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg,
00821                                       NVT, InFlag);
00822       CodeGenMap[N.getValue(0)] = Result;
00823       if (foldedLoad) {
00824         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
00825         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
00826       }
00827 
00828 #ifndef NDEBUG
00829       DEBUG(std::cerr << std::string(Indent-2, ' '));
00830       DEBUG(std::cerr << "== ");
00831       DEBUG(Result.Val->dump(CurDAG));
00832       DEBUG(std::cerr << "\n");
00833       Indent -= 2;
00834 #endif
00835       return;
00836     }
00837 
00838     case ISD::TRUNCATE: {
00839       if (NVT == MVT::i8) {
00840         unsigned Opc2;
00841         MVT::ValueType VT;
00842         switch (Node->getOperand(0).getValueType()) {
00843         default: assert(0 && "Unknown truncate!");
00844         case MVT::i16:
00845           Opc = X86::MOV16to16_;
00846           VT = MVT::i16;
00847           Opc2 = X86::TRUNC_GR16_GR8;
00848           break;
00849         case MVT::i32:
00850           Opc = X86::MOV32to32_;
00851           VT = MVT::i32;
00852           Opc2 = X86::TRUNC_GR32_GR8;
00853           break;
00854         }
00855 
00856         SDOperand Tmp0, Tmp1;
00857         Select(Tmp0, Node->getOperand(0));
00858         Tmp1 = SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0);
00859         Result = CodeGenMap[N] =
00860           SDOperand(CurDAG->getTargetNode(Opc2, NVT, Tmp1), 0);
00861       
00862 #ifndef NDEBUG
00863         DEBUG(std::cerr << std::string(Indent-2, ' '));
00864         DEBUG(std::cerr << "== ");
00865         DEBUG(Result.Val->dump(CurDAG));
00866         DEBUG(std::cerr << "\n");
00867         Indent -= 2;
00868 #endif
00869         return;
00870       }
00871 
00872       break;
00873     }
00874   }
00875 
00876   SelectCode(Result, N);
00877 #ifndef NDEBUG
00878   DEBUG(std::cerr << std::string(Indent-2, ' '));
00879   DEBUG(std::cerr << "=> ");
00880   DEBUG(Result.Val->dump(CurDAG));
00881   DEBUG(std::cerr << "\n");
00882   Indent -= 2;
00883 #endif
00884 }
00885 
00886 bool X86DAGToDAGISel::
00887 SelectInlineAsmMemoryOperand(const SDOperand &Op, char ConstraintCode,
00888                              std::vector<SDOperand> &OutOps, SelectionDAG &DAG){
00889   SDOperand Op0, Op1, Op2, Op3;
00890   switch (ConstraintCode) {
00891   case 'o':   // offsetable        ??
00892   case 'v':   // not offsetable    ??
00893   default: return true;
00894   case 'm':   // memory
00895     if (!SelectAddr(Op, Op0, Op1, Op2, Op3))
00896       return true;
00897     break;
00898   }
00899   
00900   OutOps.resize(4);
00901   Select(OutOps[0], Op0);
00902   Select(OutOps[1], Op1);
00903   Select(OutOps[2], Op2);
00904   Select(OutOps[3], Op3);
00905   return false;
00906 }
00907 
00908 /// createX86ISelDag - This pass converts a legalized DAG into a 
00909 /// X86-specific DAG, ready for instruction scheduling.
00910 ///
00911 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM) {
00912   return new X86DAGToDAGISel(TM);
00913 }