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 > 2)
 457     Complexity += 2;
 458   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg
 459   else if (AM.Scale > 1)
 460     Complexity++;
 461
 462   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
 463   // to a LEA. This is determined with some expermentation but is by no means
 464   // optimal (especially for code size consideration). LEA is nice because of
 465   // its three-address nature. Tweak the cost function again when we can run
 466   // convertToThreeAddress() at register allocation time.
 467   if (AM.GV || AM.CP)
 468     Complexity += 2;
 469
 470   if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val))
 471     Complexity++;
 472
 473   if (Complexity > 2) {
 474     getAddressOperands(AM, Base, Scale, Index, Disp);
 475     return true;
 476   }
 477
 478   return false;
 479 }
 480
 481 bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N,
 482                                   SDOperand &Base, SDOperand &Scale,
 483                                   SDOperand &Index, SDOperand &Disp) {
 484   if (N.getOpcode() == ISD::LOAD &&
 485       N.hasOneUse() &&
 486       !CodeGenMap.count(N.getValue(0)) &&
 487       (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val)))
 488     return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp);
 489   return false;
 490 }
 491
 492 static bool isRegister0(SDOperand Op) {
 493   if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op))
 494     return (R->getReg() == 0);
 495   return false;
 496 }
 497
 498 /// getGlobalBaseReg - Output the instructions required to put the
 499 /// base address to use for accessing globals into a register.
 500 ///
 501 SDOperand X86DAGToDAGISel::getGlobalBaseReg() {
 502   if (!GlobalBaseReg) {
 503     // Insert the set of GlobalBaseReg into the first MBB of the function
 504     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 505     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 506     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 507     // FIXME: when we get to LP64, we will need to create the appropriate
 508     // type of register here.
 509     GlobalBaseReg = RegMap->createVirtualRegister(X86::R32RegisterClass);
 510     BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0);
 511     BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg);
 512   }
 513   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
 514 }
 515
 516 void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) {
 517   SDNode *Node = N.Val;
 518   MVT::ValueType NVT = Node->getValueType(0);
 519   unsigned Opc, MOpc;
 520   unsigned Opcode = Node->getOpcode();
 521
 522 #ifndef NDEBUG
 523   DEBUG(std::cerr << std::string(Indent, ' '));
 524   DEBUG(std::cerr << "Selecting: ");
 525   DEBUG(Node->dump(CurDAG));
 526   DEBUG(std::cerr << "\n");
 527   Indent += 2;
 528 #endif
 529
 530   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) {
 531     Result = N;
 532 #ifndef NDEBUG
 533     DEBUG(std::cerr << std::string(Indent-2, ' '));
 534     DEBUG(std::cerr << "== ");
 535     DEBUG(Node->dump(CurDAG));
 536     DEBUG(std::cerr << "\n");
 537     Indent -= 2;
 538 #endif
 539     return;   // Already selected.
 540   }
 541
 542   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);
 543   if (CGMI != CodeGenMap.end()) {
 544     Result = CGMI->second;
 545 #ifndef NDEBUG
 546     DEBUG(std::cerr << std::string(Indent-2, ' '));
 547     DEBUG(std::cerr << "== ");
 548     DEBUG(Result.Val->dump(CurDAG));
 549     DEBUG(std::cerr << "\n");
 550     Indent -= 2;
 551 #endif
 552     return;
 553   }
 554
 555   switch (Opcode) {
 556     default: break;
 557     case X86ISD::GlobalBaseReg:
 558       Result = getGlobalBaseReg();
 559       return;
 560
 561     case ISD::ADD: {
 562       // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd
 563       // code and is matched first so to prevent it from being turned into
 564       // LEA32r X+c.
 565       SDOperand N0 = N.getOperand(0);
 566       SDOperand N1 = N.getOperand(1);
 567       if (N.Val->getValueType(0) == MVT::i32 &&
 568           N0.getOpcode() == X86ISD::Wrapper &&
 569           N1.getOpcode() == ISD::Constant) {
 570         unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue();
 571         SDOperand C(0, 0);
 572         // TODO: handle ExternalSymbolSDNode.
 573         if (GlobalAddressSDNode *G =
 574             dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) {
 575           C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32,
 576                                              G->getOffset() + Offset);
 577         } else if (ConstantPoolSDNode *CP =
 578                    dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) {
 579           C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32,
 580                                             CP->getAlignment(),
 581                                             CP->getOffset()+Offset);
 582         }
 583
 584         if (C.Val) {
 585           if (N.Val->hasOneUse()) {
 586             Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C);
 587           } else {
 588             SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C);
 589             Result = CodeGenMap[N] = SDOperand(ResNode, 0);
 590           }
 591           return;
 592         }
 593       }
 594
 595       // Other cases are handled by auto-generated code.
 596       break;
 597     }
 598
 599     case ISD::MULHU:
 600     case ISD::MULHS: {
 601       if (Opcode == ISD::MULHU)
 602         switch (NVT) {
 603         default: assert(0 && "Unsupported VT!");
 604         case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
 605         case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
 606         case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
 607         }
 608       else
 609         switch (NVT) {
 610         default: assert(0 && "Unsupported VT!");
 611         case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
 612         case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
 613         case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
 614         }
 615
 616       unsigned LoReg, HiReg;
 617       switch (NVT) {
 618       default: assert(0 && "Unsupported VT!");
 619       case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
 620       case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
 621       case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
 622       }
 623
 624       SDOperand N0 = Node->getOperand(0);
 625       SDOperand N1 = Node->getOperand(1);
 626
 627       bool foldedLoad = false;
 628       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
 629       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
 630       // MULHU and MULHS are commmutative
 631       if (!foldedLoad) {
 632         foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3);
 633         if (foldedLoad) {
 634           N0 = Node->getOperand(1);
 635           N1 = Node->getOperand(0);
 636         }
 637       }
 638
 639       SDOperand Chain;
 640       if (foldedLoad)
 641         Select(Chain, N1.getOperand(0));
 642       else
 643         Chain = CurDAG->getEntryNode();
 644
 645       SDOperand InFlag(0, 0);
 646       Select(N0, N0);
 647       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
 648                                     N0, InFlag);
 649       InFlag = Chain.getValue(1);
 650
 651       if (foldedLoad) {
 652         Select(Tmp0, Tmp0);
 653         Select(Tmp1, Tmp1);
 654         Select(Tmp2, Tmp2);
 655         Select(Tmp3, Tmp3);
 656         SDNode *CNode =
 657           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
 658                                 Tmp2, Tmp3, Chain, InFlag);
 659         Chain  = SDOperand(CNode, 0);
 660         InFlag = SDOperand(CNode, 1);
 661       } else {
 662         Select(N1, N1);
 663         InFlag =
 664           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
 665       }
 666
 667       Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag);
 668       CodeGenMap[N.getValue(0)] = Result;
 669       if (foldedLoad) {
 670         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
 671         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
 672       }
 673
 674 #ifndef NDEBUG
 675       DEBUG(std::cerr << std::string(Indent-2, ' '));
 676       DEBUG(std::cerr << "== ");
 677       DEBUG(Result.Val->dump(CurDAG));
 678       DEBUG(std::cerr << "\n");
 679       Indent -= 2;
 680 #endif
 681       return;
 682     }
 683
 684     case ISD::SDIV:
 685     case ISD::UDIV:
 686     case ISD::SREM:
 687     case ISD::UREM: {
 688       bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM;
 689       bool isDiv    = Opcode == ISD::SDIV || Opcode == ISD::UDIV;
 690       if (!isSigned)
 691         switch (NVT) {
 692         default: assert(0 && "Unsupported VT!");
 693         case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
 694         case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
 695         case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
 696         }
 697       else
 698         switch (NVT) {
 699         default: assert(0 && "Unsupported VT!");
 700         case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
 701         case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
 702         case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
 703         }
 704
 705       unsigned LoReg, HiReg;
 706       unsigned ClrOpcode, SExtOpcode;
 707       switch (NVT) {
 708       default: assert(0 && "Unsupported VT!");
 709       case MVT::i8:
 710         LoReg = X86::AL;  HiReg = X86::AH;
 711         ClrOpcode  = X86::MOV8ri;
 712         SExtOpcode = X86::CBW;
 713         break;
 714       case MVT::i16:
 715         LoReg = X86::AX;  HiReg = X86::DX;
 716         ClrOpcode  = X86::MOV16ri;
 717         SExtOpcode = X86::CWD;
 718         break;
 719       case MVT::i32:
 720         LoReg = X86::EAX; HiReg = X86::EDX;
 721         ClrOpcode  = X86::MOV32ri;
 722         SExtOpcode = X86::CDQ;
 723         break;
 724       }
 725
 726       SDOperand N0 = Node->getOperand(0);
 727       SDOperand N1 = Node->getOperand(1);
 728
 729       bool foldedLoad = false;
 730       SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
 731       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
 732       SDOperand Chain;
 733       if (foldedLoad)
 734         Select(Chain, N1.getOperand(0));
 735       else
 736         Chain = CurDAG->getEntryNode();
 737
 738       SDOperand InFlag(0, 0);
 739       Select(N0, N0);
 740       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
 741                                     N0, InFlag);
 742       InFlag = Chain.getValue(1);
 743
 744       if (isSigned) {
 745         // Sign extend the low part into the high part.
 746         InFlag =
 747           SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0);
 748       } else {
 749         // Zero out the high part, effectively zero extending the input.
 750         SDOperand ClrNode =
 751           SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT,
 752                                          CurDAG->getTargetConstant(0, NVT)), 0);
 753         Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT),
 754                                       ClrNode, InFlag);
 755         InFlag = Chain.getValue(1);
 756       }
 757
 758       if (foldedLoad) {
 759         Select(Tmp0, Tmp0);
 760         Select(Tmp1, Tmp1);
 761         Select(Tmp2, Tmp2);
 762         Select(Tmp3, Tmp3);
 763         SDNode *CNode =
 764           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
 765                                 Tmp2, Tmp3, Chain, InFlag);
 766         Chain  = SDOperand(CNode, 0);
 767         InFlag = SDOperand(CNode, 1);
 768       } else {
 769         Select(N1, N1);
 770         InFlag =
 771           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
 772       }
 773
 774       Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg,
 775                                       NVT, InFlag);
 776       CodeGenMap[N.getValue(0)] = Result;
 777       if (foldedLoad) {
 778         CodeGenMap[N1.getValue(1)] = Result.getValue(1);
 779         AddHandleReplacement(N1.Val, 1, Result.Val, 1);
 780       }
 781
 782 #ifndef NDEBUG
 783       DEBUG(std::cerr << std::string(Indent-2, ' '));
 784       DEBUG(std::cerr << "== ");
 785       DEBUG(Result.Val->dump(CurDAG));
 786       DEBUG(std::cerr << "\n");
 787       Indent -= 2;
 788 #endif
 789       return;
 790     }
 791
 792     case ISD::TRUNCATE: {
 793       unsigned Reg;
 794       MVT::ValueType VT;
 795       switch (Node->getOperand(0).getValueType()) {
 796         default: assert(0 && "Unknown truncate!");
 797         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 798         case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break;
 799       }
 800       SDOperand Tmp0, Tmp1;
 801       Select(Tmp0, Node->getOperand(0));
 802       Select(Tmp1, SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0));
 803       SDOperand InFlag = SDOperand(0,0);
 804       Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(), Reg, Tmp1, InFlag);
 805       SDOperand Chain = Result.getValue(0);
 806       InFlag = Result.getValue(1);
 807
 808       switch (NVT) {
 809         default: assert(0 && "Unknown truncate!");
 810         case MVT::i8:  Reg = X86::AL;  Opc = X86::MOV8rr;  VT = MVT::i8;  break;
 811         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 812       }
 813
 814       Result = CurDAG->getCopyFromReg(Chain, Reg, VT, InFlag);
 815       if (N.Val->hasOneUse())
 816         Result = CurDAG->SelectNodeTo(N.Val, Opc, VT, Result);
 817       else
 818         Result = CodeGenMap[N] =
 819           SDOperand(CurDAG->getTargetNode(Opc, VT, Result), 0);
 820
 821 #ifndef NDEBUG
 822       DEBUG(std::cerr << std::string(Indent-2, ' '));
 823       DEBUG(std::cerr << "== ");
 824       DEBUG(Result.Val->dump(CurDAG));
 825       DEBUG(std::cerr << "\n");
 826       Indent -= 2;
 827 #endif
 828       return;
 829     }
 830   }
 831
 832   SelectCode(Result, N);
 833 #ifndef NDEBUG
 834   DEBUG(std::cerr << std::string(Indent-2, ' '));
 835   DEBUG(std::cerr << "=> ");
 836   DEBUG(Result.Val->dump(CurDAG));
 837   DEBUG(std::cerr << "\n");
 838   Indent -= 2;
 839 #endif
 840 }
 841
 842 /// createX86ISelDag - This pass converts a legalized DAG into a
 843 /// X86-specific DAG, ready for instruction scheduling.
 844 ///
 845 FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
 846   return new X86DAGToDAGISel(TM);
 847 }