lib/Target/X86/X86ISelDAGToDAG.cpp

   1 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Evan Cheng and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a DAG pattern matching instruction selector for X86,
  11 // converting from a legalized dag to a X86 dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "isel"
  16 #include "X86.h"
  17 #include "X86InstrBuilder.h"
  18 #include "X86RegisterInfo.h"
  19 #include "X86Subtarget.h"
  20 #include "X86ISelLowering.h"
  21 #include "llvm/GlobalValue.h"
  22 #include "llvm/Instructions.h"
  23 #include "llvm/Support/CFG.h"
  24 #include "llvm/CodeGen/MachineConstantPool.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFrameInfo.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/SSARegMap.h"
  29 #include "llvm/CodeGen/SelectionDAGISel.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include <iostream>
  34 #include <set>
  35 using namespace llvm;
  36
  37 //===----------------------------------------------------------------------===//
  38 //                      Pattern Matcher Implementation
  39 //===----------------------------------------------------------------------===//
  40
  41 namespace {
  42   /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
  43   /// SDOperand's instead of register numbers for the leaves of the matched
  44   /// tree.
  45   struct X86ISelAddressMode {
  46     enum {
  47       RegBase,
  48       FrameIndexBase,
  49     } BaseType;
  50
  51     struct {            // This is really a union, discriminated by BaseType!
  52       SDOperand Reg;
  53       int FrameIndex;
  54     } Base;
  55
  56     unsigned Scale;
  57     SDOperand IndexReg;
  58     unsigned Disp;
  59     GlobalValue *GV;
  60     Constant *CP;
  61     unsigned Align;    // CP alignment.
  62
  63     X86ISelAddressMode()
  64       : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0),
  65         CP(0), Align(0) {
  66     }
  67   };
  68 }
  69
  70 namespace {
  71   Statistic<>
  72   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
  73
  74   //===--------------------------------------------------------------------===//
  75   /// ISel - X86 specific code to select X86 machine instructions for
  76   /// SelectionDAG operations.
  77   ///
  78   class X86DAGToDAGISel : public SelectionDAGISel {
  79     /// ContainsFPCode - Every instruction we select that uses or defines a FP
  80     /// register should set this to true.
  81     bool ContainsFPCode;
  82
  83     /// X86Lowering - This object fully describes how to lower LLVM code to an
  84     /// X86-specific SelectionDAG.
  85     X86TargetLowering X86Lowering;
  86
  87     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
  88     /// make the right decision when generating code for different targets.
  89     const X86Subtarget *Subtarget;
  90
  91     unsigned GlobalBaseReg;
  92   public:
  93     X86DAGToDAGISel(TargetMachine &TM)
  94       : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
  95       Subtarget = &TM.getSubtarget<X86Subtarget>();
  96     }
  97
  98     virtual bool runOnFunction(Function &Fn) {
  99       // Make sure we re-emit a set of the global base reg if necessary
 100       GlobalBaseReg = 0;
 101       return SelectionDAGISel::runOnFunction(Fn);
 102     }
 103
 104     virtual const char *getPassName() const {
 105       return "X86 DAG->DAG Instruction Selection";
 106     }
 107
 108     /// InstructionSelectBasicBlock - This callback is invoked by
 109     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 110     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
 111
 112     virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF);
 113
 114 // Include the pieces autogenerated from the target description.
 115 #include "X86GenDAGISel.inc"
 116
 117   private:
 118     void Select(SDOperand &Result, SDOperand N);
 119
 120     bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true);
 121     bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
 122                     SDOperand &Index, SDOperand &Disp);
 123     bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
 124                        SDOperand &Index, SDOperand &Disp);
 125     bool TryFoldLoad(SDOperand P, SDOperand N,
 126                      SDOperand &Base, SDOperand &Scale,
 127                      SDOperand &Index, SDOperand &Disp);
 128
 129     inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base,
 130                                    SDOperand &Scale, SDOperand &Index,
 131                                    SDOperand &Disp) {
 132       Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
 133         CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg;
 134       Scale = getI8Imm(AM.Scale);
 135       Index = AM.IndexReg;
 136       Disp  = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
 137         : (AM.CP ?
 138            CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp)
 139            : getI32Imm(AM.Disp));
 140     }
 141
 142     /// getI8Imm - Return a target constant with the specified value, of type
 143     /// i8.
 144     inline SDOperand getI8Imm(unsigned Imm) {
 145       return CurDAG->getTargetConstant(Imm, MVT::i8);
 146     }
 147
 148     /// getI16Imm - Return a target constant with the specified value, of type
 149     /// i16.
 150     inline SDOperand getI16Imm(unsigned Imm) {
 151       return CurDAG->getTargetConstant(Imm, MVT::i16);
 152     }
 153
 154     /// getI32Imm - Return a target constant with the specified value, of type
 155     /// i32.
 156     inline SDOperand getI32Imm(unsigned Imm) {
 157       return CurDAG->getTargetConstant(Imm, MVT::i32);
 158     }
 159
 160     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
 161     /// base register.  Return the virtual register that holds this value.
 162     SDOperand getGlobalBaseReg();
 163
 164 #ifndef NDEBUG
 165     unsigned Indent;
 166 #endif
 167   };
 168 }
 169
 170 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 171 /// when it has created a SelectionDAG for us to codegen.
 172 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 173   DEBUG(BB->dump());
 174   MachineFunction::iterator FirstMBB = BB;
 175
 176   // Codegen the basic block.
 177 #ifndef NDEBUG
 178   DEBUG(std::cerr << "===== Instruction selection begins:\n");
 179   Indent = 0;
 180 #endif
 181   DAG.setRoot(SelectRoot(DAG.getRoot()));
 182 #ifndef NDEBUG
 183   DEBUG(std::cerr << "===== Instruction selection ends:\n");
 184 #endif
 185   CodeGenMap.clear();
 186   DAG.RemoveDeadNodes();
 187
 188   // Emit machine code to BB.
 189   ScheduleAndEmitDAG(DAG);
 190
 191   // If we are emitting FP stack code, scan the basic block to determine if this
 192   // block defines any FP values.  If so, put an FP_REG_KILL instruction before
 193   // the terminator of the block.
 194   if (!Subtarget->hasSSE2()) {
 195     // Note that FP stack instructions *are* used in SSE code when returning
 196     // values, but these are not live out of the basic block, so we don't need
 197     // an FP_REG_KILL in this case either.
 198     bool ContainsFPCode = false;
 199
 200     // Scan all of the machine instructions in these MBBs, checking for FP
 201     // stores.
 202     MachineFunction::iterator MBBI = FirstMBB;
 203     do {
 204       for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end();
 205            !ContainsFPCode && I != E; ++I) {
 206         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
 207           if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() &&
 208               MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) &&
 209               RegMap->getRegClass(I->getOperand(0).getReg()) ==
 210                 X86::RFPRegisterClass) {
 211             ContainsFPCode = true;
 212             break;
 213           }
 214         }
 215       }
 216     } while (!ContainsFPCode && &*(MBBI++) != BB);
 217
 218     // Check PHI nodes in successor blocks.  These PHI's will be lowered to have
 219     // a copy of the input value in this block.
 220     if (!ContainsFPCode) {
 221       // Final check, check LLVM BB's that are successors to the LLVM BB
 222       // corresponding to BB for FP PHI nodes.
 223       const BasicBlock *LLVMBB = BB->getBasicBlock();
 224       const PHINode *PN;
 225       for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB);
 226            !ContainsFPCode && SI != E; ++SI) {
 227         for (BasicBlock::const_iterator II = SI->begin();
 228              (PN = dyn_cast<PHINode>(II)); ++II) {
 229           if (PN->getType()->isFloatingPoint()) {
 230             ContainsFPCode = true;
 231             break;
 232           }
 233         }
 234       }
 235     }
 236
 237     // Finally, if we found any FP code, emit the FP_REG_KILL instruction.
 238     if (ContainsFPCode) {
 239       BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 240       ++NumFPKill;
 241     }
 242   }
 243 }
 244
 245 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
 246 /// the main function.
 247 static void EmitSpecialCodeForMain(MachineBasicBlock *BB,
 248                                    MachineFrameInfo *MFI) {
 249   // Switch the FPU to 64-bit precision mode for better compatibility and speed.
 250   int CWFrameIdx = MFI->CreateStackObject(2, 2);
 251   addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
 252
 253   // Set the high part to be 64-bit precision.
 254   addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
 255                     CWFrameIdx, 1).addImm(2);
 256
 257   // Reload the modified control word now.
 258   addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
 259 }
 260
 261 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {
 262   // If this is main, emit special code for main.
 263   MachineBasicBlock *BB = MF.begin();
 264   if (Fn.hasExternalLinkage() && Fn.getName() == "main")
 265     EmitSpecialCodeForMain(BB, MF.getFrameInfo());
 266 }
 267
 268 /// MatchAddress - Add the specified node to the specified addressing mode,
 269 /// returning true if it cannot be done.  This just pattern matches for the
 270 /// addressing mode
 271 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM,
 272                                    bool isRoot) {
 273   bool Available = false;
 274   // If N has already been selected, reuse the result unless in some very
 275   // specific cases.
 276   std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0));
 277   if (CGMI != CodeGenMap.end()) {
 278     Available = true;
 279   }
 280
 281   switch (N.getOpcode()) {
 282   default: break;
 283   case ISD::Constant:
 284     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 285     return false;
 286
 287   case X86ISD::Wrapper:
 288     // If both base and index components have been picked, we can't fit
 289     // the result available in the register in the addressing mode. Duplicate
 290     // GlobalAddress or ConstantPool as displacement.
 291     if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) {
 292       if (ConstantPoolSDNode *CP =
 293           dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) {
 294         if (AM.CP == 0) {
 295           AM.CP = CP->get();
 296           AM.Align = CP->getAlignment();
 297           AM.Disp += CP->getOffset();
 298           return false;
 299         }
 300       } else if (GlobalAddressSDNode *G =
 301                  dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) {
 302         if (AM.GV == 0) {
 303           AM.GV = G->getGlobal();
 304           AM.Disp += G->getOffset();
 305           return false;
 306         }
 307       }
 308     }
 309     break;
 310
 311   case ISD::FrameIndex:
 312     if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
 313       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
 314       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 315       return false;
 316     }
 317     break;
 318
 319   case ISD::SHL:
 320     if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1)
 321       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 322         unsigned Val = CN->getValue();
 323         if (Val == 1 || Val == 2 || Val == 3) {
 324           AM.Scale = 1 << Val;
 325           SDOperand ShVal = N.Val->getOperand(0);
 326
 327           // Okay, we know that we have a scale by now.  However, if the scaled
 328           // value is an add of something and a constant, we can fold the
 329           // constant into the disp field here.
 330           if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
 331               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
 332             AM.IndexReg = ShVal.Val->getOperand(0);
 333             ConstantSDNode *AddVal =
 334               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
 335             AM.Disp += AddVal->getValue() << Val;
 336           } else {
 337             AM.IndexReg = ShVal;
 338           }
 339           return false;
 340         }
 341       }
 342     break;
 343
 344   case ISD::MUL:
 345     // X*[3,5,9] -> X+X*[2,4,8]
 346     if (!Available &&
 347         AM.BaseType == X86ISelAddressMode::RegBase &&
 348         AM.Base.Reg.Val == 0 &&
 349         AM.IndexReg.Val == 0)
 350       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
 351         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
 352           AM.Scale = unsigned(CN->getValue())-1;
 353
 354           SDOperand MulVal = N.Val->getOperand(0);
 355           SDOperand Reg;
 356
 357           // Okay, we know that we have a scale by now.  However, if the scaled
 358           // value is an add of something and a constant, we can fold the
 359           // constant into the disp field here.
 360           if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
 361               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
 362             Reg = MulVal.Val->getOperand(0);
 363             ConstantSDNode *AddVal =
 364               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
 365             AM.Disp += AddVal->getValue() * CN->getValue();
 366           } else {
 367             Reg = N.Val->getOperand(0);
 368           }
 369
 370           AM.IndexReg = AM.Base.Reg = Reg;
 371           return false;
 372         }
 373     break;
 374
 375   case ISD::ADD: {
 376     if (!Available) {
 377       X86ISelAddressMode Backup = AM;
 378       if (!MatchAddress(N.Val->getOperand(0), AM, false) &&
 379           !MatchAddress(N.Val->getOperand(1), AM, false))
 380         return false;
 381       AM = Backup;
 382       if (!MatchAddress(N.Val->getOperand(1), AM, false) &&
 383           !MatchAddress(N.Val->getOperand(0), AM, false))
 384         return false;
 385       AM = Backup;
 386     }
 387     break;
 388   }
 389   }
 390
 391   // Is the base register already occupied?
 392   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
 393     // If so, check to see if the scale index register is set.
 394     if (AM.IndexReg.Val == 0) {
 395       AM.IndexReg = N;
 396       AM.Scale = 1;
 397       return false;
 398     }
 399
 400     // Otherwise, we cannot select it.
 401     return true;
 402   }
 403
 404   // Default, generate it as a register.
 405   AM.BaseType = X86ISelAddressMode::RegBase;
 406   AM.Base.Reg = N;
 407   return false;
 408 }
 409
 410 /// SelectAddr - returns true if it is able pattern match an addressing mode.
 411 /// It returns the operands which make up the maximal addressing mode it can
 412 /// match by reference.
 413 bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
 414                                  SDOperand &Index, SDOperand &Disp) {
 415   X86ISelAddressMode AM;
 416   if (MatchAddress(N, AM))
 417     return false;
 418
 419   if (AM.BaseType == X86ISelAddressMode::RegBase) {
 420     if (!AM.Base.Reg.Val)
 421       AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
 422   }
 423
 424   if (!AM.IndexReg.Val)
 425     AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
 426
 427   getAddressOperands(AM, Base, Scale, Index, Disp);
 428
 429   return true;
 430 }
 431
 432 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
 433 /// mode it matches can be cost effectively emitted as an LEA instruction.
 434 /// For X86, it always is unless it's just a (Reg + const).
 435 bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base,
 436                                     SDOperand &Scale,
 437                                     SDOperand &Index, SDOperand &Disp) {
 438   X86ISelAddressMode AM;
 439   if (MatchAddress(N, AM))
 440     return false;
 441
 442   unsigned Complexity = 0;
 443   if (AM.BaseType == X86ISelAddressMode::RegBase)
 444     if (AM.Base.Reg.Val)
 445       Complexity = 1;
 446     else
 447       AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
 448   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
 449     Complexity = 4;
 450
 451   if (AM.IndexReg.Val)
 452     Complexity++;
 453   else
 454     AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
 455
 456   if (AM.Scale > 1)
 457     Complexity += 2;
 458
 459   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
 460   // to a LEA. This is determined with some expermentation but is by no means
 461   // optimal (especially for code size consideration). LEA is nice because of
 462   // its three-address nature. Tweak the cost function again when we can run
 463   // convertToThreeAddress() at register allocation time.
 464   if (AM.GV || AM.CP)
 465     Complexity += 2;
 466
 467   if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val))
 468     Complexity++;
 469
 470   if (Complexity > 2) {
 471     getAddressOperands(AM, Base, Scale, Index, Disp);
 472     return true;
 473   }
 474
 475   return false;
 476 }
 477
 478 bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N,
 479                                   SDOperand &Base, SDOperand &Scale,
 480                                   SDOperand &Index, SDOperand &Disp) {
 481   if (N.getOpcode() == ISD::LOAD &&
 482       N.hasOneUse() &&
 483       !CodeGenMap.count(N.getValue(0)) &&
 484       (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val)))
 485     return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp);
 486   return false;
 487 }
 488
 489 static bool isRegister0(SDOperand Op) {
 490   if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op))
 491     return (R->getReg() == 0);
 492   return false;
 493 }
 494
 495 /// getGlobalBaseReg - Output the instructions required to put the
 496 /// base address to use for accessing globals into a register.
 497 ///
 498 SDOperand X86DAGToDAGISel::getGlobalBaseReg() {
 499   if (!GlobalBaseReg) {
 500     // Insert the set of GlobalBaseReg into the first MBB of the function
 501     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 502     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 503     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 504     // FIXME: when we get to LP64, we will need to create the appropriate
 505     // type of register here.
 506     GlobalBaseReg = RegMap->createVirtualRegister(X86::R32RegisterClass);
 507     BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0);
 508     BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg);
 509   }
 510   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
 511 }
 512
 513 void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) {
 514   SDNode *Node = N.Val;
 515   MVT::ValueType NVT = Node->getValueType(0);
 516   unsigned Opc, MOpc;
 517   unsigned Opcode = Node->getOpcode();
 518
 519 #ifndef NDEBUG
 520   DEBUG(std::cerr << std::string(Indent, ' '));
 521   DEBUG(std::cerr << "Selecting: ");
 522   DEBUG(Node->dump(CurDAG));
 523   DEBUG(std::cerr << "\n");
 524   Indent += 2;
 525 #endif
 526
 527   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) {
 528     Result = N;
 529 #ifndef NDEBUG
 530     DEBUG(std::cerr << std::string(Indent-2, ' '));
 531     DEBUG(std::cerr << "== ");
 532     DEBUG(Node->dump(CurDAG));
 533     DEBUG(std::cerr << "\n");
 534     Indent -= 2;
 535 #endif
 536     return;   // Already selected.
 537   }
 538
 539   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);
 540   if (CGMI != CodeGenMap.end()) {
 541     Result = CGMI->second;
 542 #ifndef NDEBUG
 543     DEBUG(std::cerr << std::string(Indent-2, ' '));
 544     DEBUG(std::cerr << "== ");
 545     DEBUG(Result.Val->dump(CurDAG));
 546     DEBUG(std::cerr << "\n");
 547     Indent -= 2;
 548 #endif
 549     return;
 550   }
 551
 552   switch (Opcode) {
 553     default: break;
 554     case X86ISD::GlobalBaseReg:
 555       Result = getGlobalBaseReg();
 556       return;
 557
 558     case ISD::ADD: {
 559       // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd
 560       // code and is matched first so to prevent it from being turned into
 561       // LEA32r X+c.
 562       SDOperand N0 = N.getOperand(0);
 563       SDOperand N1 = N.getOperand(1);
 564       if (N.Val->getValueType(0) == MVT::i32 &&
 565           N0.getOpcode() == X86ISD::Wrapper &&
 566           N1.getOpcode() == ISD::Constant) {
 567         unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue();
 568         SDOperand C(0, 0);
 569         // TODO: handle ExternalSymbolSDNode.
 570         if (GlobalAddressSDNode *G =
 571             dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) {
 572           C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32,
 573                                              G->getOffset() + Offset);
 574         } else if (ConstantPoolSDNode *CP =
 575                    dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) {
 576           C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32,
 577                                             CP->getAlignment(),
 578                                             CP->getOffset()+Offset);
 579         }
 580
 581         if (C.Val) {
 582           if (N.Val->hasOneUse()) {
 583             Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C);
 584           } else {
 585             SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C);
 586             Result = CodeGenMap[N] = SDOperand(ResNode, 0);
 587           }
 588           return;
 589         }
 590       }
 591
 592       // Other cases are handled by auto-generated code.
 593       break;
 594     }
 595
 596     case ISD::MULHU:
 597     case ISD::MULHS: {
 598       if (Opcode == ISD::MULHU)
 599         switch (NVT) {
 600         default: assert(0 && "Unsupported VT!");
 601         case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
 602         case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
 603         case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
 604         }
 605       else
 606         switch (NVT) {
 607         default: assert(0 && "Unsupported VT!");
 608         case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
 609         case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
 610         case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
 611         }
 612
 613       unsigned LoReg, HiReg;
 614       switch (NVT) {
 615       default: assert(0 && "Unsupported VT!");
 616       case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
 617       case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
 618       case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
 619       }
 620
 621       SDOperand N0 = Node->getOperand(0);
 622       SDOperand N1 = Node->getOperand(1);
 623
 624       bool foldedLoad = false;
 625       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
 626       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
 627       // MULHU and MULHS are commmutative
 628       if (!foldedLoad) {
 629         foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3);
 630         if (foldedLoad) {
 631           N0 = Node->getOperand(1);
 632           N1 = Node->getOperand(0);
 633         }
 634       }
 635
 636       SDOperand Chain;
 637       if (foldedLoad)
 638         Select(Chain, N1.getOperand(0));
 639       else
 640         Chain = CurDAG->getEntryNode();
 641
 642       SDOperand InFlag(0, 0);
 643       Select(N0, N0);
 644       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
 645                                     N0, InFlag);
 646       InFlag = Chain.getValue(1);
 647
 648       if (foldedLoad) {
 649         Select(Tmp0, Tmp0);
 650         Select(Tmp1, Tmp1);
 651         Select(Tmp2, Tmp2);
 652         Select(Tmp3, Tmp3);
 653         SDNode *CNode =
 654           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
 655                                 Tmp2, Tmp3, Chain, InFlag);
 656         Chain  = SDOperand(CNode, 0);
 657         InFlag = SDOperand(CNode, 1);
 658       } else {
 659         Select(N1, N1);
 660         InFlag =
 661           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
 662       }
 663
 664       Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag);
 665       CodeGenMap[N.getValue(0)] = Result;
 666       if (foldedLoad) {
 667         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
 668         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
 669       }
 670
 671 #ifndef NDEBUG
 672       DEBUG(std::cerr << std::string(Indent-2, ' '));
 673       DEBUG(std::cerr << "== ");
 674       DEBUG(Result.Val->dump(CurDAG));
 675       DEBUG(std::cerr << "\n");
 676       Indent -= 2;
 677 #endif
 678       return;
 679     }
 680
 681     case ISD::SDIV:
 682     case ISD::UDIV:
 683     case ISD::SREM:
 684     case ISD::UREM: {
 685       bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM;
 686       bool isDiv    = Opcode == ISD::SDIV || Opcode == ISD::UDIV;
 687       if (!isSigned)
 688         switch (NVT) {
 689         default: assert(0 && "Unsupported VT!");
 690         case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
 691         case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
 692         case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
 693         }
 694       else
 695         switch (NVT) {
 696         default: assert(0 && "Unsupported VT!");
 697         case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
 698         case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
 699         case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
 700         }
 701
 702       unsigned LoReg, HiReg;
 703       unsigned ClrOpcode, SExtOpcode;
 704       switch (NVT) {
 705       default: assert(0 && "Unsupported VT!");
 706       case MVT::i8:
 707         LoReg = X86::AL;  HiReg = X86::AH;
 708         ClrOpcode  = X86::MOV8ri;
 709         SExtOpcode = X86::CBW;
 710         break;
 711       case MVT::i16:
 712         LoReg = X86::AX;  HiReg = X86::DX;
 713         ClrOpcode  = X86::MOV16ri;
 714         SExtOpcode = X86::CWD;
 715         break;
 716       case MVT::i32:
 717         LoReg = X86::EAX; HiReg = X86::EDX;
 718         ClrOpcode  = X86::MOV32ri;
 719         SExtOpcode = X86::CDQ;
 720         break;
 721       }
 722
 723       SDOperand N0 = Node->getOperand(0);
 724       SDOperand N1 = Node->getOperand(1);
 725
 726       bool foldedLoad = false;
 727       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
 728       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
 729       SDOperand Chain;
 730       if (foldedLoad)
 731         Select(Chain, N1.getOperand(0));
 732       else
 733         Chain = CurDAG->getEntryNode();
 734
 735       SDOperand InFlag(0, 0);
 736       Select(N0, N0);
 737       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
 738                                     N0, InFlag);
 739       InFlag = Chain.getValue(1);
 740
 741       if (isSigned) {
 742         // Sign extend the low part into the high part.
 743         InFlag =
 744           SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0);
 745       } else {
 746         // Zero out the high part, effectively zero extending the input.
 747         SDOperand ClrNode =
 748           SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT,
 749                                          CurDAG->getTargetConstant(0, NVT)), 0);
 750         Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT),
 751                                       ClrNode, InFlag);
 752         InFlag = Chain.getValue(1);
 753       }
 754
 755       if (foldedLoad) {
 756         Select(Tmp0, Tmp0);
 757         Select(Tmp1, Tmp1);
 758         Select(Tmp2, Tmp2);
 759         Select(Tmp3, Tmp3);
 760         SDNode *CNode =
 761           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
 762                                 Tmp2, Tmp3, Chain, InFlag);
 763         Chain  = SDOperand(CNode, 0);
 764         InFlag = SDOperand(CNode, 1);
 765       } else {
 766         Select(N1, N1);
 767         InFlag =
 768           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
 769       }
 770
 771       Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg,
 772                                       NVT, InFlag);
 773       CodeGenMap[N.getValue(0)] = Result;
 774       if (foldedLoad) {
 775         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
 776         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
 777       }
 778
 779 #ifndef NDEBUG
 780       DEBUG(std::cerr << std::string(Indent-2, ' '));
 781       DEBUG(std::cerr << "== ");
 782       DEBUG(Result.Val->dump(CurDAG));
 783       DEBUG(std::cerr << "\n");
 784       Indent -= 2;
 785 #endif
 786       return;
 787     }
 788
 789     case ISD::TRUNCATE: {
 790       unsigned Reg;
 791       MVT::ValueType VT;
 792       switch (Node->getOperand(0).getValueType()) {
 793         default: assert(0 && "Unknown truncate!");
 794         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 795         case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break;
 796       }
 797       SDOperand Tmp0, Tmp1;
 798       Select(Tmp0, Node->getOperand(0));
 799       Select(Tmp1, SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0));
 800       SDOperand InFlag = SDOperand(0,0);
 801       Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(), Reg, Tmp1, InFlag);
 802       SDOperand Chain = Result.getValue(0);
 803       InFlag = Result.getValue(1);
 804
 805       switch (NVT) {
 806         default: assert(0 && "Unknown truncate!");
 807         case MVT::i8:  Reg = X86::AL;  Opc = X86::MOV8rr;  VT = MVT::i8;  break;
 808         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 809       }
 810
 811       Result = CurDAG->getCopyFromReg(Chain, Reg, VT, InFlag);
 812       if (N.Val->hasOneUse())
 813         Result = CurDAG->SelectNodeTo(N.Val, Opc, VT, Result);
 814       else
 815         Result = CodeGenMap[N] =
 816           SDOperand(CurDAG->getTargetNode(Opc, VT, Result), 0);
 817
 818 #ifndef NDEBUG
 819       DEBUG(std::cerr << std::string(Indent-2, ' '));
 820       DEBUG(std::cerr << "== ");
 821       DEBUG(Result.Val->dump(CurDAG));
 822       DEBUG(std::cerr << "\n");
 823       Indent -= 2;
 824 #endif
 825       return;
 826     }
 827   }
 828
 829   SelectCode(Result, N);
 830 #ifndef NDEBUG
 831   DEBUG(std::cerr << std::string(Indent-2, ' '));
 832   DEBUG(std::cerr << "=> ");
 833   DEBUG(Result.Val->dump(CurDAG));
 834   DEBUG(std::cerr << "\n");
 835   Indent -= 2;
 836 #endif
 837 }
 838
 839 /// createX86ISelDag - This pass converts a legalized DAG into a
 840 /// X86-specific DAG, ready for instruction scheduling.
 841 ///
 842 FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
 843   return new X86DAGToDAGISel(TM);
 844 }