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