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