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