lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

   1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAGISel class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "isel"
  15 #include "llvm/CodeGen/SelectionDAGISel.h"
  16 #include "llvm/CodeGen/ScheduleDAG.h"
  17 #include "llvm/CallingConv.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/GlobalVariable.h"
  22 #include "llvm/InlineAsm.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Intrinsics.h"
  25 #include "llvm/CodeGen/IntrinsicLowering.h"
  26 #include "llvm/CodeGen/MachineDebugInfo.h"
  27 #include "llvm/CodeGen/MachineFunction.h"
  28 #include "llvm/CodeGen/MachineFrameInfo.h"
  29 #include "llvm/CodeGen/MachineInstrBuilder.h"
  30 #include "llvm/CodeGen/SelectionDAG.h"
  31 #include "llvm/CodeGen/SSARegMap.h"
  32 #include "llvm/Target/MRegisterInfo.h"
  33 #include "llvm/Target/TargetData.h"
  34 #include "llvm/Target/TargetFrameInfo.h"
  35 #include "llvm/Target/TargetInstrInfo.h"
  36 #include "llvm/Target/TargetLowering.h"
  37 #include "llvm/Target/TargetMachine.h"
  38 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "llvm/Support/MathExtras.h"
  41 #include "llvm/Support/Debug.h"
  42 #include <map>
  43 #include <set>
  44 #include <iostream>
  45 using namespace llvm;
  46
  47 #ifndef NDEBUG
  48 static cl::opt<bool>
  49 ViewISelDAGs("view-isel-dags", cl::Hidden,
  50           cl::desc("Pop up a window to show isel dags as they are selected"));
  51 static cl::opt<bool>
  52 ViewSchedDAGs("view-sched-dags", cl::Hidden,
  53           cl::desc("Pop up a window to show sched dags as they are processed"));
  54 #else
  55 static const bool ViewISelDAGs = 0;
  56 static const bool ViewSchedDAGs = 0;
  57 #endif
  58
  59 namespace {
  60   cl::opt<SchedHeuristics>
  61   ISHeuristic(
  62     "sched",
  63     cl::desc("Choose scheduling style"),
  64     cl::init(defaultScheduling),
  65     cl::values(
  66       clEnumValN(defaultScheduling, "default",
  67                  "Target preferred scheduling style"),
  68       clEnumValN(noScheduling, "none",
  69                  "No scheduling: breadth first sequencing"),
  70       clEnumValN(simpleScheduling, "simple",
  71                  "Simple two pass scheduling: minimize critical path "
  72                  "and maximize processor utilization"),
  73       clEnumValN(simpleNoItinScheduling, "simple-noitin",
  74                  "Simple two pass scheduling: Same as simple "
  75                  "except using generic latency"),
  76       clEnumValN(listSchedulingBURR, "list-burr",
  77                  "Bottom up register reduction list scheduling"),
  78       clEnumValEnd));
  79 } // namespace
  80
  81
  82 namespace llvm {
  83   //===--------------------------------------------------------------------===//
  84   /// FunctionLoweringInfo - This contains information that is global to a
  85   /// function that is used when lowering a region of the function.
  86   class FunctionLoweringInfo {
  87   public:
  88     TargetLowering &TLI;
  89     Function &Fn;
  90     MachineFunction &MF;
  91     SSARegMap *RegMap;
  92
  93     FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
  94
  95     /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
  96     std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
  97
  98     /// ValueMap - Since we emit code for the function a basic block at a time,
  99     /// we must remember which virtual registers hold the values for
 100     /// cross-basic-block values.
 101     std::map<const Value*, unsigned> ValueMap;
 102
 103     /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
 104     /// the entry block.  This allows the allocas to be efficiently referenced
 105     /// anywhere in the function.
 106     std::map<const AllocaInst*, int> StaticAllocaMap;
 107
 108     unsigned MakeReg(MVT::ValueType VT) {
 109       return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
 110     }
 111
 112     unsigned CreateRegForValue(const Value *V) {
 113       MVT::ValueType VT = TLI.getValueType(V->getType());
 114       // The common case is that we will only create one register for this
 115       // value.  If we have that case, create and return the virtual register.
 116       unsigned NV = TLI.getNumElements(VT);
 117       if (NV == 1) {
 118         // If we are promoting this value, pick the next largest supported type.
 119         return MakeReg(TLI.getTypeToTransformTo(VT));
 120       }
 121
 122       // If this value is represented with multiple target registers, make sure
 123       // to create enough consequtive registers of the right (smaller) type.
 124       unsigned NT = VT-1;  // Find the type to use.
 125       while (TLI.getNumElements((MVT::ValueType)NT) != 1)
 126         --NT;
 127
 128       unsigned R = MakeReg((MVT::ValueType)NT);
 129       for (unsigned i = 1; i != NV; ++i)
 130         MakeReg((MVT::ValueType)NT);
 131       return R;
 132     }
 133
 134     unsigned InitializeRegForValue(const Value *V) {
 135       unsigned &R = ValueMap[V];
 136       assert(R == 0 && "Already initialized this value register!");
 137       return R = CreateRegForValue(V);
 138     }
 139   };
 140 }
 141
 142 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
 143 /// PHI nodes or outside of the basic block that defines it.
 144 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
 145   if (isa<PHINode>(I)) return true;
 146   BasicBlock *BB = I->getParent();
 147   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
 148     if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI))
 149       return true;
 150   return false;
 151 }
 152
 153 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
 154 /// entry block, return true.
 155 static bool isOnlyUsedInEntryBlock(Argument *A) {
 156   BasicBlock *Entry = A->getParent()->begin();
 157   for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
 158     if (cast<Instruction>(*UI)->getParent() != Entry)
 159       return false;  // Use not in entry block.
 160   return true;
 161 }
 162
 163 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
 164                                            Function &fn, MachineFunction &mf)
 165     : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
 166
 167   // Create a vreg for each argument register that is not dead and is used
 168   // outside of the entry block for the function.
 169   for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
 170        AI != E; ++AI)
 171     if (!isOnlyUsedInEntryBlock(AI))
 172       InitializeRegForValue(AI);
 173
 174   // Initialize the mapping of values to registers.  This is only set up for
 175   // instruction values that are used outside of the block that defines
 176   // them.
 177   Function::iterator BB = Fn.begin(), EB = Fn.end();
 178   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 179     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 180       if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) {
 181         const Type *Ty = AI->getAllocatedType();
 182         uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
 183         unsigned Align =
 184           std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty),
 185                    AI->getAlignment());
 186
 187         // If the alignment of the value is smaller than the size of the value,
 188         // and if the size of the value is particularly small (<= 8 bytes),
 189         // round up to the size of the value for potentially better performance.
 190         //
 191         // FIXME: This could be made better with a preferred alignment hook in
 192         // TargetData.  It serves primarily to 8-byte align doubles for X86.
 193         if (Align < TySize && TySize <= 8) Align = TySize;
 194         TySize *= CUI->getValue();   // Get total allocated size.
 195         if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
 196         StaticAllocaMap[AI] =
 197           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
 198       }
 199
 200   for (; BB != EB; ++BB)
 201     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 202       if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
 203         if (!isa<AllocaInst>(I) ||
 204             !StaticAllocaMap.count(cast<AllocaInst>(I)))
 205           InitializeRegForValue(I);
 206
 207   // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
 208   // also creates the initial PHI MachineInstrs, though none of the input
 209   // operands are populated.
 210   for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
 211     MachineBasicBlock *MBB = new MachineBasicBlock(BB);
 212     MBBMap[BB] = MBB;
 213     MF.getBasicBlockList().push_back(MBB);
 214
 215     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
 216     // appropriate.
 217     PHINode *PN;
 218     for (BasicBlock::iterator I = BB->begin();
 219          (PN = dyn_cast<PHINode>(I)); ++I)
 220       if (!PN->use_empty()) {
 221         unsigned NumElements =
 222           TLI.getNumElements(TLI.getValueType(PN->getType()));
 223         unsigned PHIReg = ValueMap[PN];
 224         assert(PHIReg &&"PHI node does not have an assigned virtual register!");
 225         for (unsigned i = 0; i != NumElements; ++i)
 226           BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i);
 227       }
 228   }
 229 }
 230
 231
 232
 233 //===----------------------------------------------------------------------===//
 234 /// SelectionDAGLowering - This is the common target-independent lowering
 235 /// implementation that is parameterized by a TargetLowering object.
 236 /// Also, targets can overload any lowering method.
 237 ///
 238 namespace llvm {
 239 class SelectionDAGLowering {
 240   MachineBasicBlock *CurMBB;
 241
 242   std::map<const Value*, SDOperand> NodeMap;
 243
 244   /// PendingLoads - Loads are not emitted to the program immediately.  We bunch
 245   /// them up and then emit token factor nodes when possible.  This allows us to
 246   /// get simple disambiguation between loads without worrying about alias
 247   /// analysis.
 248   std::vector<SDOperand> PendingLoads;
 249
 250 public:
 251   // TLI - This is information that describes the available target features we
 252   // need for lowering.  This indicates when operations are unavailable,
 253   // implemented with a libcall, etc.
 254   TargetLowering &TLI;
 255   SelectionDAG &DAG;
 256   const TargetData &TD;
 257
 258   /// FuncInfo - Information about the function as a whole.
 259   ///
 260   FunctionLoweringInfo &FuncInfo;
 261
 262   SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
 263                        FunctionLoweringInfo &funcinfo)
 264     : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
 265       FuncInfo(funcinfo) {
 266   }
 267
 268   /// getRoot - Return the current virtual root of the Selection DAG.
 269   ///
 270   SDOperand getRoot() {
 271     if (PendingLoads.empty())
 272       return DAG.getRoot();
 273
 274     if (PendingLoads.size() == 1) {
 275       SDOperand Root = PendingLoads[0];
 276       DAG.setRoot(Root);
 277       PendingLoads.clear();
 278       return Root;
 279     }
 280
 281     // Otherwise, we have to make a token factor node.
 282     SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, PendingLoads);
 283     PendingLoads.clear();
 284     DAG.setRoot(Root);
 285     return Root;
 286   }
 287
 288   void visit(Instruction &I) { visit(I.getOpcode(), I); }
 289
 290   void visit(unsigned Opcode, User &I) {
 291     switch (Opcode) {
 292     default: assert(0 && "Unknown instruction type encountered!");
 293              abort();
 294       // Build the switch statement using the Instruction.def file.
 295 #define HANDLE_INST(NUM, OPCODE, CLASS) \
 296     case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
 297 #include "llvm/Instruction.def"
 298     }
 299   }
 300
 301   void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
 302
 303
 304   SDOperand getIntPtrConstant(uint64_t Val) {
 305     return DAG.getConstant(Val, TLI.getPointerTy());
 306   }
 307
 308   SDOperand getValue(const Value *V) {
 309     SDOperand &N = NodeMap[V];
 310     if (N.Val) return N;
 311
 312     const Type *VTy = V->getType();
 313     MVT::ValueType VT = TLI.getValueType(VTy);
 314     if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V)))
 315       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 316         visit(CE->getOpcode(), *CE);
 317         assert(N.Val && "visit didn't populate the ValueMap!");
 318         return N;
 319       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
 320         return N = DAG.getGlobalAddress(GV, VT);
 321       } else if (isa<ConstantPointerNull>(C)) {
 322         return N = DAG.getConstant(0, TLI.getPointerTy());
 323       } else if (isa<UndefValue>(C)) {
 324         return N = DAG.getNode(ISD::UNDEF, VT);
 325       } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 326         return N = DAG.getConstantFP(CFP->getValue(), VT);
 327       } else if (const PackedType *PTy = dyn_cast<PackedType>(VTy)) {
 328         unsigned NumElements = PTy->getNumElements();
 329         MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
 330         MVT::ValueType TVT = MVT::getVectorType(PVT, NumElements);
 331
 332         // Now that we know the number and type of the elements, push a
 333         // Constant or ConstantFP node onto the ops list for each element of
 334         // the packed constant.
 335         std::vector<SDOperand> Ops;
 336         if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) {
 337           if (MVT::isFloatingPoint(PVT)) {
 338             for (unsigned i = 0; i != NumElements; ++i) {
 339               const ConstantFP *El = cast<ConstantFP>(CP->getOperand(i));
 340               Ops.push_back(DAG.getConstantFP(El->getValue(), PVT));
 341             }
 342           } else {
 343             for (unsigned i = 0; i != NumElements; ++i) {
 344               const ConstantIntegral *El =
 345                 cast<ConstantIntegral>(CP->getOperand(i));
 346               Ops.push_back(DAG.getConstant(El->getRawValue(), PVT));
 347             }
 348           }
 349         } else {
 350           assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
 351           SDOperand Op;
 352           if (MVT::isFloatingPoint(PVT))
 353             Op = DAG.getConstantFP(0, PVT);
 354           else
 355             Op = DAG.getConstant(0, PVT);
 356           Ops.assign(NumElements, Op);
 357         }
 358
 359         // Handle the case where we have a 1-element vector, in which
 360         // case we want to immediately turn it into a scalar constant.
 361         if (Ops.size() == 1) {
 362           return N = Ops[0];
 363         } else if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
 364           return N = DAG.getNode(ISD::ConstantVec, TVT, Ops);
 365         } else {
 366           // If the packed type isn't legal, then create a ConstantVec node with
 367           // generic Vector type instead.
 368           return N = DAG.getNode(ISD::ConstantVec, MVT::Vector, Ops);
 369         }
 370       } else {
 371         // Canonicalize all constant ints to be unsigned.
 372         return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT);
 373       }
 374
 375     if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 376       std::map<const AllocaInst*, int>::iterator SI =
 377         FuncInfo.StaticAllocaMap.find(AI);
 378       if (SI != FuncInfo.StaticAllocaMap.end())
 379         return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
 380     }
 381
 382     std::map<const Value*, unsigned>::const_iterator VMI =
 383       FuncInfo.ValueMap.find(V);
 384     assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!");
 385
 386     unsigned InReg = VMI->second;
 387
 388     // If this type is not legal, make it so now.
 389     MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
 390
 391     N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
 392     if (DestVT < VT) {
 393       // Source must be expanded.  This input value is actually coming from the
 394       // register pair VMI->second and VMI->second+1.
 395       N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
 396                       DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
 397     } else {
 398       if (DestVT > VT) { // Promotion case
 399         if (MVT::isFloatingPoint(VT))
 400           N = DAG.getNode(ISD::FP_ROUND, VT, N);
 401         else
 402           N = DAG.getNode(ISD::TRUNCATE, VT, N);
 403       }
 404     }
 405
 406     return N;
 407   }
 408
 409   const SDOperand &setValue(const Value *V, SDOperand NewN) {
 410     SDOperand &N = NodeMap[V];
 411     assert(N.Val == 0 && "Already set a value for this node!");
 412     return N = NewN;
 413   }
 414
 415   unsigned GetAvailableRegister(bool OutReg, bool InReg,
 416                                 const std::vector<unsigned> &RegChoices,
 417                                 std::set<unsigned> &OutputRegs,
 418                                 std::set<unsigned> &InputRegs);
 419
 420   // Terminator instructions.
 421   void visitRet(ReturnInst &I);
 422   void visitBr(BranchInst &I);
 423   void visitUnreachable(UnreachableInst &I) { /* noop */ }
 424
 425   // These all get lowered before this pass.
 426   void visitExtractElement(ExtractElementInst &I) { assert(0 && "TODO"); }
 427   void visitInsertElement(InsertElementInst &I) { assert(0 && "TODO"); }
 428   void visitSwitch(SwitchInst &I) { assert(0 && "TODO"); }
 429   void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); }
 430   void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); }
 431
 432   //
 433   void visitBinary(User &I, unsigned IntOp, unsigned FPOp, unsigned VecOp);
 434   void visitShift(User &I, unsigned Opcode);
 435   void visitAdd(User &I) {
 436     visitBinary(I, ISD::ADD, ISD::FADD, ISD::VADD);
 437   }
 438   void visitSub(User &I);
 439   void visitMul(User &I) {
 440     visitBinary(I, ISD::MUL, ISD::FMUL, ISD::VMUL);
 441   }
 442   void visitDiv(User &I) {
 443     const Type *Ty = I.getType();
 444     visitBinary(I, Ty->isSigned() ? ISD::SDIV : ISD::UDIV, ISD::FDIV, 0);
 445   }
 446   void visitRem(User &I) {
 447     const Type *Ty = I.getType();
 448     visitBinary(I, Ty->isSigned() ? ISD::SREM : ISD::UREM, ISD::FREM, 0);
 449   }
 450   void visitAnd(User &I) { visitBinary(I, ISD::AND, 0, 0); }
 451   void visitOr (User &I) { visitBinary(I, ISD::OR,  0, 0); }
 452   void visitXor(User &I) { visitBinary(I, ISD::XOR, 0, 0); }
 453   void visitShl(User &I) { visitShift(I, ISD::SHL); }
 454   void visitShr(User &I) {
 455     visitShift(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA);
 456   }
 457
 458   void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc);
 459   void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); }
 460   void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); }
 461   void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); }
 462   void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); }
 463   void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); }
 464   void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); }
 465
 466   void visitGetElementPtr(User &I);
 467   void visitCast(User &I);
 468   void visitSelect(User &I);
 469   //
 470
 471   void visitMalloc(MallocInst &I);
 472   void visitFree(FreeInst &I);
 473   void visitAlloca(AllocaInst &I);
 474   void visitLoad(LoadInst &I);
 475   void visitStore(StoreInst &I);
 476   void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
 477   void visitCall(CallInst &I);
 478   void visitInlineAsm(CallInst &I);
 479   const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
 480
 481   void visitVAStart(CallInst &I);
 482   void visitVAArg(VAArgInst &I);
 483   void visitVAEnd(CallInst &I);
 484   void visitVACopy(CallInst &I);
 485   void visitFrameReturnAddress(CallInst &I, bool isFrameAddress);
 486
 487   void visitMemIntrinsic(CallInst &I, unsigned Op);
 488
 489   void visitUserOp1(Instruction &I) {
 490     assert(0 && "UserOp1 should not exist at instruction selection time!");
 491     abort();
 492   }
 493   void visitUserOp2(Instruction &I) {
 494     assert(0 && "UserOp2 should not exist at instruction selection time!");
 495     abort();
 496   }
 497 };
 498 } // end namespace llvm
 499
 500 void SelectionDAGLowering::visitRet(ReturnInst &I) {
 501   if (I.getNumOperands() == 0) {
 502     DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
 503     return;
 504   }
 505   std::vector<SDOperand> NewValues;
 506   NewValues.push_back(getRoot());
 507   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 508     SDOperand RetOp = getValue(I.getOperand(i));
 509
 510     // If this is an integer return value, we need to promote it ourselves to
 511     // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
 512     // than sign/zero.
 513     if (MVT::isInteger(RetOp.getValueType()) &&
 514         RetOp.getValueType() < MVT::i64) {
 515       MVT::ValueType TmpVT;
 516       if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
 517         TmpVT = TLI.getTypeToTransformTo(MVT::i32);
 518       else
 519         TmpVT = MVT::i32;
 520
 521       if (I.getOperand(i)->getType()->isSigned())
 522         RetOp = DAG.getNode(ISD::SIGN_EXTEND, TmpVT, RetOp);
 523       else
 524         RetOp = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, RetOp);
 525     }
 526     NewValues.push_back(RetOp);
 527   }
 528   DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, NewValues));
 529 }
 530
 531 void SelectionDAGLowering::visitBr(BranchInst &I) {
 532   // Update machine-CFG edges.
 533   MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
 534
 535   // Figure out which block is immediately after the current one.
 536   MachineBasicBlock *NextBlock = 0;
 537   MachineFunction::iterator BBI = CurMBB;
 538   if (++BBI != CurMBB->getParent()->end())
 539     NextBlock = BBI;
 540
 541   if (I.isUnconditional()) {
 542     // If this is not a fall-through branch, emit the branch.
 543     if (Succ0MBB != NextBlock)
 544       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
 545                               DAG.getBasicBlock(Succ0MBB)));
 546   } else {
 547     MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
 548
 549     SDOperand Cond = getValue(I.getCondition());
 550     if (Succ1MBB == NextBlock) {
 551       // If the condition is false, fall through.  This means we should branch
 552       // if the condition is true to Succ #0.
 553       DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
 554                               Cond, DAG.getBasicBlock(Succ0MBB)));
 555     } else if (Succ0MBB == NextBlock) {
 556       // If the condition is true, fall through.  This means we should branch if
 557       // the condition is false to Succ #1.  Invert the condition first.
 558       SDOperand True = DAG.getConstant(1, Cond.getValueType());
 559       Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
 560       DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
 561                               Cond, DAG.getBasicBlock(Succ1MBB)));
 562     } else {
 563       std::vector<SDOperand> Ops;
 564       Ops.push_back(getRoot());
 565       // If the false case is the current basic block, then this is a self
 566       // loop. We do not want to emit "Loop: ... brcond Out; br Loop", as it
 567       // adds an extra instruction in the loop.  Instead, invert the
 568       // condition and emit "Loop: ... br!cond Loop; br Out.
 569       if (CurMBB == Succ1MBB) {
 570         std::swap(Succ0MBB, Succ1MBB);
 571         SDOperand True = DAG.getConstant(1, Cond.getValueType());
 572         Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
 573       }
 574       Ops.push_back(Cond);
 575       Ops.push_back(DAG.getBasicBlock(Succ0MBB));
 576       Ops.push_back(DAG.getBasicBlock(Succ1MBB));
 577       DAG.setRoot(DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops));
 578     }
 579   }
 580 }
 581
 582 void SelectionDAGLowering::visitSub(User &I) {
 583   // -0.0 - X --> fneg
 584   if (I.getType()->isFloatingPoint()) {
 585     if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
 586       if (CFP->isExactlyValue(-0.0)) {
 587         SDOperand Op2 = getValue(I.getOperand(1));
 588         setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
 589         return;
 590       }
 591   }
 592   visitBinary(I, ISD::SUB, ISD::FSUB, ISD::VSUB);
 593 }
 594
 595 void SelectionDAGLowering::visitBinary(User &I, unsigned IntOp, unsigned FPOp,
 596                                        unsigned VecOp) {
 597   const Type *Ty = I.getType();
 598   SDOperand Op1 = getValue(I.getOperand(0));
 599   SDOperand Op2 = getValue(I.getOperand(1));
 600
 601   if (Ty->isIntegral()) {
 602     setValue(&I, DAG.getNode(IntOp, Op1.getValueType(), Op1, Op2));
 603   } else if (Ty->isFloatingPoint()) {
 604     setValue(&I, DAG.getNode(FPOp, Op1.getValueType(), Op1, Op2));
 605   } else {
 606     const PackedType *PTy = cast<PackedType>(Ty);
 607     unsigned NumElements = PTy->getNumElements();
 608     MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
 609     MVT::ValueType TVT = MVT::getVectorType(PVT, NumElements);
 610
 611     // Immediately scalarize packed types containing only one element, so that
 612     // the Legalize pass does not have to deal with them.  Similarly, if the
 613     // abstract vector is going to turn into one that the target natively
 614     // supports, generate that type now so that Legalize doesn't have to deal
 615     // with that either.  These steps ensure that Legalize only has to handle
 616     // vector types in its Expand case.
 617     unsigned Opc = MVT::isFloatingPoint(PVT) ? FPOp : IntOp;
 618     if (NumElements == 1) {
 619       setValue(&I, DAG.getNode(Opc, PVT, Op1, Op2));
 620     } else if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
 621       setValue(&I, DAG.getNode(Opc, TVT, Op1, Op2));
 622     } else {
 623       SDOperand Num = DAG.getConstant(NumElements, MVT::i32);
 624       SDOperand Typ = DAG.getValueType(PVT);
 625       setValue(&I, DAG.getNode(VecOp, MVT::Vector, Op1, Op2, Num, Typ));
 626     }
 627   }
 628 }
 629
 630 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
 631   SDOperand Op1 = getValue(I.getOperand(0));
 632   SDOperand Op2 = getValue(I.getOperand(1));
 633
 634   Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
 635
 636   setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
 637 }
 638
 639 void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode,
 640                                       ISD::CondCode UnsignedOpcode) {
 641   SDOperand Op1 = getValue(I.getOperand(0));
 642   SDOperand Op2 = getValue(I.getOperand(1));
 643   ISD::CondCode Opcode = SignedOpcode;
 644   if (I.getOperand(0)->getType()->isUnsigned())
 645     Opcode = UnsignedOpcode;
 646   setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
 647 }
 648
 649 void SelectionDAGLowering::visitSelect(User &I) {
 650   SDOperand Cond     = getValue(I.getOperand(0));
 651   SDOperand TrueVal  = getValue(I.getOperand(1));
 652   SDOperand FalseVal = getValue(I.getOperand(2));
 653   setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
 654                            TrueVal, FalseVal));
 655 }
 656
 657 void SelectionDAGLowering::visitCast(User &I) {
 658   SDOperand N = getValue(I.getOperand(0));
 659   MVT::ValueType SrcTy = TLI.getValueType(I.getOperand(0)->getType());
 660   MVT::ValueType DestTy = TLI.getValueType(I.getType());
 661
 662   if (N.getValueType() == DestTy) {
 663     setValue(&I, N);  // noop cast.
 664   } else if (DestTy == MVT::i1) {
 665     // Cast to bool is a comparison against zero, not truncation to zero.
 666     SDOperand Zero = isInteger(SrcTy) ? DAG.getConstant(0, N.getValueType()) :
 667                                        DAG.getConstantFP(0.0, N.getValueType());
 668     setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE));
 669   } else if (isInteger(SrcTy)) {
 670     if (isInteger(DestTy)) {        // Int -> Int cast
 671       if (DestTy < SrcTy)   // Truncating cast?
 672         setValue(&I, DAG.getNode(ISD::TRUNCATE, DestTy, N));
 673       else if (I.getOperand(0)->getType()->isSigned())
 674         setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestTy, N));
 675       else
 676         setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestTy, N));
 677     } else {                        // Int -> FP cast
 678       if (I.getOperand(0)->getType()->isSigned())
 679         setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestTy, N));
 680       else
 681         setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestTy, N));
 682     }
 683   } else {
 684     assert(isFloatingPoint(SrcTy) && "Unknown value type!");
 685     if (isFloatingPoint(DestTy)) {  // FP -> FP cast
 686       if (DestTy < SrcTy)   // Rounding cast?
 687         setValue(&I, DAG.getNode(ISD::FP_ROUND, DestTy, N));
 688       else
 689         setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestTy, N));
 690     } else {                        // FP -> Int cast.
 691       if (I.getType()->isSigned())
 692         setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestTy, N));
 693       else
 694         setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestTy, N));
 695     }
 696   }
 697 }
 698
 699 void SelectionDAGLowering::visitGetElementPtr(User &I) {
 700   SDOperand N = getValue(I.getOperand(0));
 701   const Type *Ty = I.getOperand(0)->getType();
 702   const Type *UIntPtrTy = TD.getIntPtrType();
 703
 704   for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
 705        OI != E; ++OI) {
 706     Value *Idx = *OI;
 707     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
 708       unsigned Field = cast<ConstantUInt>(Idx)->getValue();
 709       if (Field) {
 710         // N = N + Offset
 711         uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field];
 712         N = DAG.getNode(ISD::ADD, N.getValueType(), N,
 713                         getIntPtrConstant(Offset));
 714       }
 715       Ty = StTy->getElementType(Field);
 716     } else {
 717       Ty = cast<SequentialType>(Ty)->getElementType();
 718
 719       // If this is a constant subscript, handle it quickly.
 720       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
 721         if (CI->getRawValue() == 0) continue;
 722
 723         uint64_t Offs;
 724         if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI))
 725           Offs = (int64_t)TD.getTypeSize(Ty)*CSI->getValue();
 726         else
 727           Offs = TD.getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue();
 728         N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
 729         continue;
 730       }
 731
 732       // N = N + Idx * ElementSize;
 733       uint64_t ElementSize = TD.getTypeSize(Ty);
 734       SDOperand IdxN = getValue(Idx);
 735
 736       // If the index is smaller or larger than intptr_t, truncate or extend
 737       // it.
 738       if (IdxN.getValueType() < N.getValueType()) {
 739         if (Idx->getType()->isSigned())
 740           IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
 741         else
 742           IdxN = DAG.getNode(ISD::ZERO_EXTEND, N.getValueType(), IdxN);
 743       } else if (IdxN.getValueType() > N.getValueType())
 744         IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
 745
 746       // If this is a multiply by a power of two, turn it into a shl
 747       // immediately.  This is a very common case.
 748       if (isPowerOf2_64(ElementSize)) {
 749         unsigned Amt = Log2_64(ElementSize);
 750         IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
 751                            DAG.getConstant(Amt, TLI.getShiftAmountTy()));
 752         N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
 753         continue;
 754       }
 755
 756       SDOperand Scale = getIntPtrConstant(ElementSize);
 757       IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
 758       N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
 759     }
 760   }
 761   setValue(&I, N);
 762 }
 763
 764 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
 765   // If this is a fixed sized alloca in the entry block of the function,
 766   // allocate it statically on the stack.
 767   if (FuncInfo.StaticAllocaMap.count(&I))
 768     return;   // getValue will auto-populate this.
 769
 770   const Type *Ty = I.getAllocatedType();
 771   uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
 772   unsigned Align = std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty),
 773                             I.getAlignment());
 774
 775   SDOperand AllocSize = getValue(I.getArraySize());
 776   MVT::ValueType IntPtr = TLI.getPointerTy();
 777   if (IntPtr < AllocSize.getValueType())
 778     AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
 779   else if (IntPtr > AllocSize.getValueType())
 780     AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
 781
 782   AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
 783                           getIntPtrConstant(TySize));
 784
 785   // Handle alignment.  If the requested alignment is less than or equal to the
 786   // stack alignment, ignore it and round the size of the allocation up to the
 787   // stack alignment size.  If the size is greater than the stack alignment, we
 788   // note this in the DYNAMIC_STACKALLOC node.
 789   unsigned StackAlign =
 790     TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
 791   if (Align <= StackAlign) {
 792     Align = 0;
 793     // Add SA-1 to the size.
 794     AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
 795                             getIntPtrConstant(StackAlign-1));
 796     // Mask out the low bits for alignment purposes.
 797     AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
 798                             getIntPtrConstant(~(uint64_t)(StackAlign-1)));
 799   }
 800
 801   std::vector<MVT::ValueType> VTs;
 802   VTs.push_back(AllocSize.getValueType());
 803   VTs.push_back(MVT::Other);
 804   std::vector<SDOperand> Ops;
 805   Ops.push_back(getRoot());
 806   Ops.push_back(AllocSize);
 807   Ops.push_back(getIntPtrConstant(Align));
 808   SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops);
 809   DAG.setRoot(setValue(&I, DSA).getValue(1));
 810
 811   // Inform the Frame Information that we have just allocated a variable-sized
 812   // object.
 813   CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
 814 }
 815
 816 /// getStringValue - Turn an LLVM constant pointer that eventually points to a
 817 /// global into a string value.  Return an empty string if we can't do it.
 818 ///
 819 static std::string getStringValue(GlobalVariable *GV, unsigned Offset = 0) {
 820   if (GV->hasInitializer() && isa<ConstantArray>(GV->getInitializer())) {
 821     ConstantArray *Init = cast<ConstantArray>(GV->getInitializer());
 822     if (Init->isString()) {
 823       std::string Result = Init->getAsString();
 824       if (Offset < Result.size()) {
 825         // If we are pointing INTO The string, erase the beginning...
 826         Result.erase(Result.begin(), Result.begin()+Offset);
 827         return Result;
 828       }
 829     }
 830   }
 831   return "";
 832 }
 833
 834 void SelectionDAGLowering::visitLoad(LoadInst &I) {
 835   SDOperand Ptr = getValue(I.getOperand(0));
 836
 837   SDOperand Root;
 838   if (I.isVolatile())
 839     Root = getRoot();
 840   else {
 841     // Do not serialize non-volatile loads against each other.
 842     Root = DAG.getRoot();
 843   }
 844
 845   const Type *Ty = I.getType();
 846   SDOperand L;
 847
 848   if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) {
 849     unsigned NumElements = PTy->getNumElements();
 850     MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
 851     MVT::ValueType TVT = MVT::getVectorType(PVT, NumElements);
 852
 853     // Immediately scalarize packed types containing only one element, so that
 854     // the Legalize pass does not have to deal with them.
 855     if (NumElements == 1) {
 856       L = DAG.getLoad(PVT, Root, Ptr, DAG.getSrcValue(I.getOperand(0)));
 857     } else if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
 858       L = DAG.getLoad(TVT, Root, Ptr, DAG.getSrcValue(I.getOperand(0)));
 859     } else {
 860       L = DAG.getVecLoad(NumElements, PVT, Root, Ptr,
 861                          DAG.getSrcValue(I.getOperand(0)));
 862     }
 863   } else {
 864     L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr,
 865                     DAG.getSrcValue(I.getOperand(0)));
 866   }
 867   setValue(&I, L);
 868
 869   if (I.isVolatile())
 870     DAG.setRoot(L.getValue(1));
 871   else
 872     PendingLoads.push_back(L.getValue(1));
 873 }
 874
 875
 876 void SelectionDAGLowering::visitStore(StoreInst &I) {
 877   Value *SrcV = I.getOperand(0);
 878   SDOperand Src = getValue(SrcV);
 879   SDOperand Ptr = getValue(I.getOperand(1));
 880   DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr,
 881                           DAG.getSrcValue(I.getOperand(1))));
 882 }
 883
 884 /// visitIntrinsicCall - Lower the call to the specified intrinsic function.  If
 885 /// we want to emit this as a call to a named external function, return the name
 886 /// otherwise lower it and return null.
 887 const char *
 888 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
 889   switch (Intrinsic) {
 890   case Intrinsic::vastart:  visitVAStart(I); return 0;
 891   case Intrinsic::vaend:    visitVAEnd(I); return 0;
 892   case Intrinsic::vacopy:   visitVACopy(I); return 0;
 893   case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return 0;
 894   case Intrinsic::frameaddress:  visitFrameReturnAddress(I, true); return 0;
 895   case Intrinsic::setjmp:
 896     return "_setjmp"+!TLI.usesUnderscoreSetJmpLongJmp();
 897     break;
 898   case Intrinsic::longjmp:
 899     return "_longjmp"+!TLI.usesUnderscoreSetJmpLongJmp();
 900     break;
 901   case Intrinsic::memcpy:  visitMemIntrinsic(I, ISD::MEMCPY); return 0;
 902   case Intrinsic::memset:  visitMemIntrinsic(I, ISD::MEMSET); return 0;
 903   case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return 0;
 904
 905   case Intrinsic::readport:
 906   case Intrinsic::readio: {
 907     std::vector<MVT::ValueType> VTs;
 908     VTs.push_back(TLI.getValueType(I.getType()));
 909     VTs.push_back(MVT::Other);
 910     std::vector<SDOperand> Ops;
 911     Ops.push_back(getRoot());
 912     Ops.push_back(getValue(I.getOperand(1)));
 913     SDOperand Tmp = DAG.getNode(Intrinsic == Intrinsic::readport ?
 914                                 ISD::READPORT : ISD::READIO, VTs, Ops);
 915
 916     setValue(&I, Tmp);
 917     DAG.setRoot(Tmp.getValue(1));
 918     return 0;
 919   }
 920   case Intrinsic::writeport:
 921   case Intrinsic::writeio:
 922     DAG.setRoot(DAG.getNode(Intrinsic == Intrinsic::writeport ?
 923                             ISD::WRITEPORT : ISD::WRITEIO, MVT::Other,
 924                             getRoot(), getValue(I.getOperand(1)),
 925                             getValue(I.getOperand(2))));
 926     return 0;
 927
 928   case Intrinsic::dbg_stoppoint: {
 929     if (TLI.getTargetMachine().getIntrinsicLowering().EmitDebugFunctions())
 930       return "llvm_debugger_stop";
 931
 932     MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo();
 933     if (DebugInfo &&  DebugInfo->Verify(I.getOperand(4))) {
 934       std::vector<SDOperand> Ops;
 935
 936       // Input Chain
 937       Ops.push_back(getRoot());
 938
 939       // line number
 940       Ops.push_back(getValue(I.getOperand(2)));
 941
 942       // column
 943       Ops.push_back(getValue(I.getOperand(3)));
 944
 945       DebugInfoDesc *DD = DebugInfo->getDescFor(I.getOperand(4));
 946       assert(DD && "Not a debug information descriptor");
 947       CompileUnitDesc *CompileUnit = dyn_cast<CompileUnitDesc>(DD);
 948       assert(CompileUnit && "Not a compile unit");
 949       Ops.push_back(DAG.getString(CompileUnit->getFileName()));
 950       Ops.push_back(DAG.getString(CompileUnit->getDirectory()));
 951
 952       if (Ops.size() == 5)  // Found filename/workingdir.
 953         DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops));
 954     }
 955
 956     setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
 957     return 0;
 958   }
 959   case Intrinsic::dbg_region_start:
 960     if (TLI.getTargetMachine().getIntrinsicLowering().EmitDebugFunctions())
 961       return "llvm_dbg_region_start";
 962     if (I.getType() != Type::VoidTy)
 963       setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
 964     return 0;
 965   case Intrinsic::dbg_region_end:
 966     if (TLI.getTargetMachine().getIntrinsicLowering().EmitDebugFunctions())
 967       return "llvm_dbg_region_end";
 968     if (I.getType() != Type::VoidTy)
 969       setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
 970     return 0;
 971   case Intrinsic::dbg_func_start:
 972     if (TLI.getTargetMachine().getIntrinsicLowering().EmitDebugFunctions())
 973       return "llvm_dbg_subprogram";
 974     if (I.getType() != Type::VoidTy)
 975       setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
 976     return 0;
 977   case Intrinsic::dbg_declare:
 978     if (I.getType() != Type::VoidTy)
 979       setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
 980     return 0;
 981
 982   case Intrinsic::isunordered_f32:
 983   case Intrinsic::isunordered_f64:
 984     setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)),
 985                               getValue(I.getOperand(2)), ISD::SETUO));
 986     return 0;
 987
 988   case Intrinsic::sqrt_f32:
 989   case Intrinsic::sqrt_f64:
 990     setValue(&I, DAG.getNode(ISD::FSQRT,
 991                              getValue(I.getOperand(1)).getValueType(),
 992                              getValue(I.getOperand(1))));
 993     return 0;
 994   case Intrinsic::pcmarker: {
 995     SDOperand Tmp = getValue(I.getOperand(1));
 996     DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
 997     return 0;
 998   }
 999   case Intrinsic::readcyclecounter: {
1000     std::vector<MVT::ValueType> VTs;
1001     VTs.push_back(MVT::i64);
1002     VTs.push_back(MVT::Other);
1003     std::vector<SDOperand> Ops;
1004     Ops.push_back(getRoot());
1005     SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, VTs, Ops);
1006     setValue(&I, Tmp);
1007     DAG.setRoot(Tmp.getValue(1));
1008     return 0;
1009   }
1010   case Intrinsic::bswap_i16:
1011   case Intrinsic::bswap_i32:
1012   case Intrinsic::bswap_i64:
1013     setValue(&I, DAG.getNode(ISD::BSWAP,
1014                              getValue(I.getOperand(1)).getValueType(),
1015                              getValue(I.getOperand(1))));
1016     return 0;
1017   case Intrinsic::cttz_i8:
1018   case Intrinsic::cttz_i16:
1019   case Intrinsic::cttz_i32:
1020   case Intrinsic::cttz_i64:
1021     setValue(&I, DAG.getNode(ISD::CTTZ,
1022                              getValue(I.getOperand(1)).getValueType(),
1023                              getValue(I.getOperand(1))));
1024     return 0;
1025   case Intrinsic::ctlz_i8:
1026   case Intrinsic::ctlz_i16:
1027   case Intrinsic::ctlz_i32:
1028   case Intrinsic::ctlz_i64:
1029     setValue(&I, DAG.getNode(ISD::CTLZ,
1030                              getValue(I.getOperand(1)).getValueType(),
1031                              getValue(I.getOperand(1))));
1032     return 0;
1033   case Intrinsic::ctpop_i8:
1034   case Intrinsic::ctpop_i16:
1035   case Intrinsic::ctpop_i32:
1036   case Intrinsic::ctpop_i64:
1037     setValue(&I, DAG.getNode(ISD::CTPOP,
1038                              getValue(I.getOperand(1)).getValueType(),
1039                              getValue(I.getOperand(1))));
1040     return 0;
1041   case Intrinsic::stacksave: {
1042     std::vector<MVT::ValueType> VTs;
1043     VTs.push_back(TLI.getPointerTy());
1044     VTs.push_back(MVT::Other);
1045     std::vector<SDOperand> Ops;
1046     Ops.push_back(getRoot());
1047     SDOperand Tmp = DAG.getNode(ISD::STACKSAVE, VTs, Ops);
1048     setValue(&I, Tmp);
1049     DAG.setRoot(Tmp.getValue(1));
1050     return 0;
1051   }
1052   case Intrinsic::stackrestore: {
1053     SDOperand Tmp = getValue(I.getOperand(1));
1054     DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
1055     return 0;
1056   }
1057   case Intrinsic::prefetch:
1058     // FIXME: Currently discarding prefetches.
1059     return 0;
1060   default:
1061     std::cerr << I;
1062     assert(0 && "This intrinsic is not implemented yet!");
1063     return 0;
1064   }
1065 }
1066
1067
1068 void SelectionDAGLowering::visitCall(CallInst &I) {
1069   const char *RenameFn = 0;
1070   if (Function *F = I.getCalledFunction()) {
1071     if (F->isExternal())
1072       if (unsigned IID = F->getIntrinsicID()) {
1073         RenameFn = visitIntrinsicCall(I, IID);
1074         if (!RenameFn)
1075           return;
1076       } else {    // Not an LLVM intrinsic.
1077         const std::string &Name = F->getName();
1078         if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
1079           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
1080               I.getOperand(1)->getType()->isFloatingPoint() &&
1081               I.getType() == I.getOperand(1)->getType()) {
1082             SDOperand Tmp = getValue(I.getOperand(1));
1083             setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
1084             return;
1085           }
1086         } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
1087           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
1088               I.getOperand(1)->getType()->isFloatingPoint() &&
1089               I.getType() == I.getOperand(1)->getType()) {
1090             SDOperand Tmp = getValue(I.getOperand(1));
1091             setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
1092             return;
1093           }
1094         } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
1095           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
1096               I.getOperand(1)->getType()->isFloatingPoint() &&
1097               I.getType() == I.getOperand(1)->getType()) {
1098             SDOperand Tmp = getValue(I.getOperand(1));
1099             setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
1100             return;
1101           }
1102         }
1103       }
1104   } else if (isa<InlineAsm>(I.getOperand(0))) {
1105     visitInlineAsm(I);
1106     return;
1107   }
1108
1109   SDOperand Callee;
1110   if (!RenameFn)
1111     Callee = getValue(I.getOperand(0));
1112   else
1113     Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
1114   std::vector<std::pair<SDOperand, const Type*> > Args;
1115   Args.reserve(I.getNumOperands());
1116   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
1117     Value *Arg = I.getOperand(i);
1118     SDOperand ArgNode = getValue(Arg);
1119     Args.push_back(std::make_pair(ArgNode, Arg->getType()));
1120   }
1121
1122   const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType());
1123   const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
1124
1125   std::pair<SDOperand,SDOperand> Result =
1126     TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(),
1127                     I.isTailCall(), Callee, Args, DAG);
1128   if (I.getType() != Type::VoidTy)
1129     setValue(&I, Result.first);
1130   DAG.setRoot(Result.second);
1131 }
1132
1133 /// GetAvailableRegister - Pick a register from RegChoices that is available
1134 /// for input and/or output as specified by isOutReg/isInReg.  If an allocatable
1135 /// register is found, it is returned and added to the specified set of used
1136 /// registers.  If not, zero is returned.
1137 unsigned SelectionDAGLowering::
1138 GetAvailableRegister(bool isOutReg, bool isInReg,
1139                      const std::vector<unsigned> &RegChoices,
1140                      std::set<unsigned> &OutputRegs,
1141                      std::set<unsigned> &InputRegs) {
1142   const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
1143   MachineFunction &MF = *CurMBB->getParent();
1144   for (unsigned i = 0, e = RegChoices.size(); i != e; ++i) {
1145     unsigned Reg = RegChoices[i];
1146     // See if this register is available.
1147     if (isOutReg && OutputRegs.count(Reg)) continue;  // Already used.
1148     if (isInReg  && InputRegs.count(Reg)) continue;  // Already used.
1149
1150     // Check to see if this register is allocatable (i.e. don't give out the
1151     // stack pointer).
1152     bool Found = false;
1153     for (MRegisterInfo::regclass_iterator RC = MRI->regclass_begin(),
1154          E = MRI->regclass_end(); !Found && RC != E; ++RC) {
1155       // NOTE: This isn't ideal.  In particular, this might allocate the
1156       // frame pointer in functions that need it (due to them not being taken
1157       // out of allocation, because a variable sized allocation hasn't been seen
1158       // yet).  This is a slight code pessimization, but should still work.
1159       for (TargetRegisterClass::iterator I = (*RC)->allocation_order_begin(MF),
1160            E = (*RC)->allocation_order_end(MF); I != E; ++I)
1161         if (*I == Reg) {
1162           Found = true;
1163           break;
1164         }
1165     }
1166     if (!Found) continue;
1167
1168     // Okay, this register is good, return it.
1169     if (isOutReg) OutputRegs.insert(Reg);  // Mark used.
1170     if (isInReg)  InputRegs.insert(Reg);   // Mark used.
1171     return Reg;
1172   }
1173   return 0;
1174 }
1175
1176 /// visitInlineAsm - Handle a call to an InlineAsm object.
1177 ///
1178 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
1179   InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
1180
1181   SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
1182                                                  MVT::Other);
1183
1184   // Note, we treat inline asms both with and without side-effects as the same.
1185   // If an inline asm doesn't have side effects and doesn't access memory, we
1186   // could not choose to not chain it.
1187   bool hasSideEffects = IA->hasSideEffects();
1188
1189   std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
1190
1191   /// AsmNodeOperands - A list of pairs.  The first element is a register, the
1192   /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
1193   /// if it is a def of that register.
1194   std::vector<SDOperand> AsmNodeOperands;
1195   AsmNodeOperands.push_back(SDOperand());  // reserve space for input chain
1196   AsmNodeOperands.push_back(AsmStr);
1197
1198   SDOperand Chain = getRoot();
1199   SDOperand Flag;
1200
1201   // We fully assign registers here at isel time.  This is not optimal, but
1202   // should work.  For register classes that correspond to LLVM classes, we
1203   // could let the LLVM RA do its thing, but we currently don't.  Do a prepass
1204   // over the constraints, collecting fixed registers that we know we can't use.
1205   std::set<unsigned> OutputRegs, InputRegs;
1206   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
1207     assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!");
1208     std::string &ConstraintCode = Constraints[i].Codes[0];
1209
1210     std::vector<unsigned> Regs =
1211       TLI.getRegForInlineAsmConstraint(ConstraintCode, MVT::Other);
1212     if (Regs.size() != 1) continue;  // Not assigned a fixed reg.
1213     unsigned TheReg = Regs[0];
1214
1215     switch (Constraints[i].Type) {
1216     case InlineAsm::isOutput:
1217       // We can't assign any other output to this register.
1218       OutputRegs.insert(TheReg);
1219       // If this is an early-clobber output, it cannot be assigned to the same
1220       // value as the input reg.
1221       if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
1222         InputRegs.insert(TheReg);
1223       break;
1224     case InlineAsm::isClobber:
1225       // Clobbered regs cannot be used as inputs or outputs.
1226       InputRegs.insert(TheReg);
1227       OutputRegs.insert(TheReg);
1228       break;
1229     case InlineAsm::isInput:
1230       // We can't assign any other input to this register.
1231       InputRegs.insert(TheReg);
1232       break;
1233     }
1234   }
1235
1236   // Loop over all of the inputs, copying the operand values into the
1237   // appropriate registers and processing the output regs.
1238   unsigned RetValReg = 0;
1239   std::vector<std::pair<unsigned, Value*> > IndirectStoresToEmit;
1240   bool FoundOutputConstraint = false;
1241   unsigned OpNum = 1;
1242
1243   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
1244     assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!");
1245     std::string &ConstraintCode = Constraints[i].Codes[0];
1246     Value *CallOperand = I.getOperand(OpNum);
1247     MVT::ValueType CallOpVT = TLI.getValueType(CallOperand->getType());
1248     switch (Constraints[i].Type) {
1249     case InlineAsm::isOutput: {
1250       // Copy the output from the appropriate register.
1251       std::vector<unsigned> Regs =
1252         TLI.getRegForInlineAsmConstraint(ConstraintCode, CallOpVT);
1253
1254       // Find a regsister that we can use.
1255       unsigned DestReg;
1256       if (Regs.size() == 1)
1257         DestReg = Regs[0];
1258       else {
1259         bool UsesInputRegister = false;
1260         // If this is an early-clobber output, or if there is an input
1261         // constraint that matches this, we need to reserve the input register
1262         // so no other inputs allocate to it.
1263         if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
1264           UsesInputRegister = true;
1265         DestReg = GetAvailableRegister(true, UsesInputRegister,
1266                                        Regs, OutputRegs, InputRegs);
1267       }
1268
1269       assert(DestReg && "Couldn't allocate output reg!");
1270
1271       const Type *OpTy;
1272       if (!Constraints[i].isIndirectOutput) {
1273         assert(!FoundOutputConstraint &&
1274                "Cannot have multiple output constraints yet!");
1275         FoundOutputConstraint = true;
1276         assert(I.getType() != Type::VoidTy && "Bad inline asm!");
1277
1278         RetValReg = DestReg;
1279         OpTy = I.getType();
1280       } else {
1281         IndirectStoresToEmit.push_back(std::make_pair(DestReg, CallOperand));
1282         OpTy = CallOperand->getType();
1283         OpTy = cast<PointerType>(OpTy)->getElementType();
1284         OpNum++;  // Consumes a call operand.
1285       }
1286
1287       // Add information to the INLINEASM node to know that this register is
1288       // set.
1289       AsmNodeOperands.push_back(DAG.getRegister(DestReg,
1290                                                 TLI.getValueType(OpTy)));
1291       AsmNodeOperands.push_back(DAG.getConstant(2, MVT::i32)); // ISDEF
1292
1293       break;
1294     }
1295     case InlineAsm::isInput: {
1296       const Type *OpTy = CallOperand->getType();
1297       OpNum++;  // Consumes a call operand.
1298
1299       unsigned SrcReg;
1300       SDOperand ResOp;
1301       unsigned ResOpType;
1302       SDOperand InOperandVal = getValue(CallOperand);
1303
1304       if (isdigit(ConstraintCode[0])) {    // Matching constraint?
1305         // If this is required to match an output register we have already set,
1306         // just use its register.
1307         unsigned OperandNo = atoi(ConstraintCode.c_str());
1308         SrcReg = cast<RegisterSDNode>(AsmNodeOperands[OperandNo*2+2])->getReg();
1309         ResOp = DAG.getRegister(SrcReg, CallOpVT);
1310         ResOpType = 1;
1311
1312         Chain = DAG.getCopyToReg(Chain, SrcReg, InOperandVal, Flag);
1313         Flag = Chain.getValue(1);
1314       } else {
1315         TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
1316         if (ConstraintCode.size() == 1)   // not a physreg name.
1317           CTy = TLI.getConstraintType(ConstraintCode[0]);
1318
1319         switch (CTy) {
1320         default: assert(0 && "Unknown constraint type! FAIL!");
1321         case TargetLowering::C_RegisterClass: {
1322           // Copy the input into the appropriate register.
1323           std::vector<unsigned> Regs =
1324             TLI.getRegForInlineAsmConstraint(ConstraintCode, CallOpVT);
1325           if (Regs.size() == 1)
1326             SrcReg = Regs[0];
1327           else
1328             SrcReg = GetAvailableRegister(false, true, Regs,
1329                                           OutputRegs, InputRegs);
1330           // FIXME: should be match fail.
1331           assert(SrcReg && "Wasn't able to allocate register!");
1332           Chain = DAG.getCopyToReg(Chain, SrcReg, InOperandVal, Flag);
1333           Flag = Chain.getValue(1);
1334
1335           ResOp = DAG.getRegister(SrcReg, CallOpVT);
1336           ResOpType = 1;
1337           break;
1338         }
1339         case TargetLowering::C_Other:
1340           if (!TLI.isOperandValidForConstraint(InOperandVal, ConstraintCode[0]))
1341             assert(0 && "MATCH FAIL!");
1342           ResOp = InOperandVal;
1343           ResOpType = 3;
1344           break;
1345         }
1346       }
1347
1348       // Add information to the INLINEASM node to know about this input.
1349       AsmNodeOperands.push_back(ResOp);
1350       AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
1351       break;
1352     }
1353     case InlineAsm::isClobber:
1354       // Nothing to do.
1355       break;
1356     }
1357   }
1358
1359   // Finish up input operands.
1360   AsmNodeOperands[0] = Chain;
1361   if (Flag.Val) AsmNodeOperands.push_back(Flag);
1362
1363   std::vector<MVT::ValueType> VTs;
1364   VTs.push_back(MVT::Other);
1365   VTs.push_back(MVT::Flag);
1366   Chain = DAG.getNode(ISD::INLINEASM, VTs, AsmNodeOperands);
1367   Flag = Chain.getValue(1);
1368
1369   // If this asm returns a register value, copy the result from that register
1370   // and set it as the value of the call.
1371   if (RetValReg) {
1372     SDOperand Val = DAG.getCopyFromReg(Chain, RetValReg,
1373                                        TLI.getValueType(I.getType()), Flag);
1374     Chain = Val.getValue(1);
1375     Flag  = Val.getValue(2);
1376     setValue(&I, Val);
1377   }
1378
1379   std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
1380
1381   // Process indirect outputs, first output all of the flagged copies out of
1382   // physregs.
1383   for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
1384     Value *Ptr = IndirectStoresToEmit[i].second;
1385     const Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
1386     SDOperand Val = DAG.getCopyFromReg(Chain, IndirectStoresToEmit[i].first,
1387                                        TLI.getValueType(Ty), Flag);
1388     Chain = Val.getValue(1);
1389     Flag  = Val.getValue(2);
1390     StoresToEmit.push_back(std::make_pair(Val, Ptr));
1391   }
1392
1393   // Emit the non-flagged stores from the physregs.
1394   std::vector<SDOperand> OutChains;
1395   for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
1396     OutChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
1397                                     StoresToEmit[i].first,
1398                                     getValue(StoresToEmit[i].second),
1399                                     DAG.getSrcValue(StoresToEmit[i].second)));
1400   if (!OutChains.empty())
1401     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains);
1402   DAG.setRoot(Chain);
1403 }
1404
1405
1406 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
1407   SDOperand Src = getValue(I.getOperand(0));
1408
1409   MVT::ValueType IntPtr = TLI.getPointerTy();
1410
1411   if (IntPtr < Src.getValueType())
1412     Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
1413   else if (IntPtr > Src.getValueType())
1414     Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
1415
1416   // Scale the source by the type size.
1417   uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType());
1418   Src = DAG.getNode(ISD::MUL, Src.getValueType(),
1419                     Src, getIntPtrConstant(ElementSize));
1420
1421   std::vector<std::pair<SDOperand, const Type*> > Args;
1422   Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType()));
1423
1424   std::pair<SDOperand,SDOperand> Result =
1425     TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true,
1426                     DAG.getExternalSymbol("malloc", IntPtr),
1427                     Args, DAG);
1428   setValue(&I, Result.first);  // Pointers always fit in registers
1429   DAG.setRoot(Result.second);
1430 }
1431
1432 void SelectionDAGLowering::visitFree(FreeInst &I) {
1433   std::vector<std::pair<SDOperand, const Type*> > Args;
1434   Args.push_back(std::make_pair(getValue(I.getOperand(0)),
1435                                 TLI.getTargetData().getIntPtrType()));
1436   MVT::ValueType IntPtr = TLI.getPointerTy();
1437   std::pair<SDOperand,SDOperand> Result =
1438     TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true,
1439                     DAG.getExternalSymbol("free", IntPtr), Args, DAG);
1440   DAG.setRoot(Result.second);
1441 }
1442
1443 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
1444 // mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
1445 // instructions are special in various ways, which require special support to
1446 // insert.  The specified MachineInstr is created but not inserted into any
1447 // basic blocks, and the scheduler passes ownership of it to this method.
1448 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
1449                                                        MachineBasicBlock *MBB) {
1450   std::cerr << "If a target marks an instruction with "
1451                "'usesCustomDAGSchedInserter', it must implement "
1452                "TargetLowering::InsertAtEndOfBasicBlock!\n";
1453   abort();
1454   return 0;
1455 }
1456
1457 void SelectionDAGLowering::visitVAStart(CallInst &I) {
1458   DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
1459                           getValue(I.getOperand(1)),
1460                           DAG.getSrcValue(I.getOperand(1))));
1461 }
1462
1463 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
1464   SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
1465                              getValue(I.getOperand(0)),
1466                              DAG.getSrcValue(I.getOperand(0)));
1467   setValue(&I, V);
1468   DAG.setRoot(V.getValue(1));
1469 }
1470
1471 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
1472   DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
1473                           getValue(I.getOperand(1)),
1474                           DAG.getSrcValue(I.getOperand(1))));
1475 }
1476
1477 void SelectionDAGLowering::visitVACopy(CallInst &I) {
1478   DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
1479                           getValue(I.getOperand(1)),
1480                           getValue(I.getOperand(2)),
1481                           DAG.getSrcValue(I.getOperand(1)),
1482                           DAG.getSrcValue(I.getOperand(2))));
1483 }
1484
1485 // It is always conservatively correct for llvm.returnaddress and
1486 // llvm.frameaddress to return 0.
1487 std::pair<SDOperand, SDOperand>
1488 TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain,
1489                                         unsigned Depth, SelectionDAG &DAG) {
1490   return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain);
1491 }
1492
1493 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
1494   assert(0 && "LowerOperation not implemented for this target!");
1495   abort();
1496   return SDOperand();
1497 }
1498
1499 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
1500                                                  SelectionDAG &DAG) {
1501   assert(0 && "CustomPromoteOperation not implemented for this target!");
1502   abort();
1503   return SDOperand();
1504 }
1505
1506 void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) {
1507   unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue();
1508   std::pair<SDOperand,SDOperand> Result =
1509     TLI.LowerFrameReturnAddress(isFrame, getRoot(), Depth, DAG);
1510   setValue(&I, Result.first);
1511   DAG.setRoot(Result.second);
1512 }
1513
1514 /// getMemsetValue - Vectorized representation of the memset value
1515 /// operand.
1516 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
1517                                 SelectionDAG &DAG) {
1518   MVT::ValueType CurVT = VT;
1519   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
1520     uint64_t Val   = C->getValue() & 255;
1521     unsigned Shift = 8;
1522     while (CurVT != MVT::i8) {
1523       Val = (Val << Shift) | Val;
1524       Shift <<= 1;
1525       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
1526     }
1527     return DAG.getConstant(Val, VT);
1528   } else {
1529     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
1530     unsigned Shift = 8;
1531     while (CurVT != MVT::i8) {
1532       Value =
1533         DAG.getNode(ISD::OR, VT,
1534                     DAG.getNode(ISD::SHL, VT, Value,
1535                                 DAG.getConstant(Shift, MVT::i8)), Value);
1536       Shift <<= 1;
1537       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
1538     }
1539
1540     return Value;
1541   }
1542 }
1543
1544 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
1545 /// used when a memcpy is turned into a memset when the source is a constant
1546 /// string ptr.
1547 static SDOperand getMemsetStringVal(MVT::ValueType VT,
1548                                     SelectionDAG &DAG, TargetLowering &TLI,
1549                                     std::string &Str, unsigned Offset) {
1550   MVT::ValueType CurVT = VT;
1551   uint64_t Val = 0;
1552   unsigned MSB = getSizeInBits(VT) / 8;
1553   if (TLI.isLittleEndian())
1554     Offset = Offset + MSB - 1;
1555   for (unsigned i = 0; i != MSB; ++i) {
1556     Val = (Val << 8) | Str[Offset];
1557     Offset += TLI.isLittleEndian() ? -1 : 1;
1558   }
1559   return DAG.getConstant(Val, VT);
1560 }
1561
1562 /// getMemBasePlusOffset - Returns base and offset node for the
1563 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
1564                                       SelectionDAG &DAG, TargetLowering &TLI) {
1565   MVT::ValueType VT = Base.getValueType();
1566   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
1567 }
1568
1569 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
1570 /// to replace the memset / memcpy is below the threshold. It also returns the
1571 /// types of the sequence of  memory ops to perform memset / memcpy.
1572 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
1573                                      unsigned Limit, uint64_t Size,
1574                                      unsigned Align, TargetLowering &TLI) {
1575   MVT::ValueType VT;
1576
1577   if (TLI.allowsUnalignedMemoryAccesses()) {
1578     VT = MVT::i64;
1579   } else {
1580     switch (Align & 7) {
1581     case 0:
1582       VT = MVT::i64;
1583       break;
1584     case 4:
1585       VT = MVT::i32;
1586       break;
1587     case 2:
1588       VT = MVT::i16;
1589       break;
1590     default:
1591       VT = MVT::i8;
1592       break;
1593     }
1594   }
1595
1596   MVT::ValueType LVT = MVT::i64;
1597   while (!TLI.isTypeLegal(LVT))
1598     LVT = (MVT::ValueType)((unsigned)LVT - 1);
1599   assert(MVT::isInteger(LVT));
1600
1601   if (VT > LVT)
1602     VT = LVT;
1603
1604   unsigned NumMemOps = 0;
1605   while (Size != 0) {
1606     unsigned VTSize = getSizeInBits(VT) / 8;
1607     while (VTSize > Size) {
1608       VT = (MVT::ValueType)((unsigned)VT - 1);
1609       VTSize >>= 1;
1610     }
1611     assert(MVT::isInteger(VT));
1612
1613     if (++NumMemOps > Limit)
1614       return false;
1615     MemOps.push_back(VT);
1616     Size -= VTSize;
1617   }
1618
1619   return true;
1620 }
1621
1622 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
1623   SDOperand Op1 = getValue(I.getOperand(1));
1624   SDOperand Op2 = getValue(I.getOperand(2));
1625   SDOperand Op3 = getValue(I.getOperand(3));
1626   SDOperand Op4 = getValue(I.getOperand(4));
1627   unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
1628   if (Align == 0) Align = 1;
1629
1630   if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
1631     std::vector<MVT::ValueType> MemOps;
1632
1633     // Expand memset / memcpy to a series of load / store ops
1634     // if the size operand falls below a certain threshold.
1635     std::vector<SDOperand> OutChains;
1636     switch (Op) {
1637     default: break;  // Do nothing for now.
1638     case ISD::MEMSET: {
1639       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
1640                                    Size->getValue(), Align, TLI)) {
1641         unsigned NumMemOps = MemOps.size();
1642         unsigned Offset = 0;
1643         for (unsigned i = 0; i < NumMemOps; i++) {
1644           MVT::ValueType VT = MemOps[i];
1645           unsigned VTSize = getSizeInBits(VT) / 8;
1646           SDOperand Value = getMemsetValue(Op2, VT, DAG);
1647           SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, getRoot(),
1648                                         Value,
1649                                         getMemBasePlusOffset(Op1, Offset, DAG, TLI),
1650                                         DAG.getSrcValue(I.getOperand(1), Offset));
1651           OutChains.push_back(Store);
1652           Offset += VTSize;
1653         }
1654       }
1655       break;
1656     }
1657     case ISD::MEMCPY: {
1658       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
1659                                    Size->getValue(), Align, TLI)) {
1660         unsigned NumMemOps = MemOps.size();
1661         unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
1662         GlobalAddressSDNode *G = NULL;
1663         std::string Str;
1664         bool CopyFromStr = false;
1665
1666         if (Op2.getOpcode() == ISD::GlobalAddress)
1667           G = cast<GlobalAddressSDNode>(Op2);
1668         else if (Op2.getOpcode() == ISD::ADD &&
1669                  Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
1670                  Op2.getOperand(1).getOpcode() == ISD::Constant) {
1671           G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
1672           SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
1673         }
1674         if (G) {
1675           GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
1676           if (GV) {
1677             Str = getStringValue(GV);
1678             if (!Str.empty()) {
1679               CopyFromStr = true;
1680               SrcOff += SrcDelta;
1681             }
1682           }
1683         }
1684
1685         for (unsigned i = 0; i < NumMemOps; i++) {
1686           MVT::ValueType VT = MemOps[i];
1687           unsigned VTSize = getSizeInBits(VT) / 8;
1688           SDOperand Value, Chain, Store;
1689
1690           if (CopyFromStr) {
1691             Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
1692             Chain = getRoot();
1693             Store =
1694               DAG.getNode(ISD::STORE, MVT::Other, Chain, Value,
1695                           getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
1696                           DAG.getSrcValue(I.getOperand(1), DstOff));
1697           } else {
1698             Value = DAG.getLoad(VT, getRoot(),
1699                         getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
1700                         DAG.getSrcValue(I.getOperand(2), SrcOff));
1701             Chain = Value.getValue(1);
1702             Store =
1703               DAG.getNode(ISD::STORE, MVT::Other, Chain, Value,
1704                           getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
1705                           DAG.getSrcValue(I.getOperand(1), DstOff));
1706           }
1707           OutChains.push_back(Store);
1708           SrcOff += VTSize;
1709           DstOff += VTSize;
1710         }
1711       }
1712       break;
1713     }
1714     }
1715
1716     if (!OutChains.empty()) {
1717       DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains));
1718       return;
1719     }
1720   }
1721
1722   std::vector<SDOperand> Ops;
1723   Ops.push_back(getRoot());
1724   Ops.push_back(Op1);
1725   Ops.push_back(Op2);
1726   Ops.push_back(Op3);
1727   Ops.push_back(Op4);
1728   DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops));
1729 }
1730
1731 //===----------------------------------------------------------------------===//
1732 // SelectionDAGISel code
1733 //===----------------------------------------------------------------------===//
1734
1735 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
1736   return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
1737 }
1738
1739 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
1740   // FIXME: we only modify the CFG to split critical edges.  This
1741   // updates dom and loop info.
1742 }
1743
1744
1745 /// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset,
1746 /// casting to the type of GEPI.
1747 static Value *InsertGEPComputeCode(Value *&V, BasicBlock *BB, Instruction *GEPI,
1748                                    Value *Ptr, Value *PtrOffset) {
1749   if (V) return V;   // Already computed.
1750
1751   BasicBlock::iterator InsertPt;
1752   if (BB == GEPI->getParent()) {
1753     // If insert into the GEP's block, insert right after the GEP.
1754     InsertPt = GEPI;
1755     ++InsertPt;
1756   } else {
1757     // Otherwise, insert at the top of BB, after any PHI nodes
1758     InsertPt = BB->begin();
1759     while (isa<PHINode>(InsertPt)) ++InsertPt;
1760   }
1761
1762   // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into
1763   // BB so that there is only one value live across basic blocks (the cast
1764   // operand).
1765   if (CastInst *CI = dyn_cast<CastInst>(Ptr))
1766     if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType()))
1767       Ptr = new CastInst(CI->getOperand(0), CI->getType(), "", InsertPt);
1768
1769   // Add the offset, cast it to the right type.
1770   Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt);
1771   Ptr = new CastInst(Ptr, GEPI->getType(), "", InsertPt);
1772   return V = Ptr;
1773 }
1774
1775
1776 /// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction
1777 /// selection, we want to be a bit careful about some things.  In particular, if
1778 /// we have a GEP instruction that is used in a different block than it is
1779 /// defined, the addressing expression of the GEP cannot be folded into loads or
1780 /// stores that use it.  In this case, decompose the GEP and move constant
1781 /// indices into blocks that use it.
1782 static void OptimizeGEPExpression(GetElementPtrInst *GEPI,
1783                                   const TargetData &TD) {
1784   // If this GEP is only used inside the block it is defined in, there is no
1785   // need to rewrite it.
1786   bool isUsedOutsideDefBB = false;
1787   BasicBlock *DefBB = GEPI->getParent();
1788   for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end();
1789        UI != E; ++UI) {
1790     if (cast<Instruction>(*UI)->getParent() != DefBB) {
1791       isUsedOutsideDefBB = true;
1792       break;
1793     }
1794   }
1795   if (!isUsedOutsideDefBB) return;
1796
1797   // If this GEP has no non-zero constant indices, there is nothing we can do,
1798   // ignore it.
1799   bool hasConstantIndex = false;
1800   for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
1801        E = GEPI->op_end(); OI != E; ++OI) {
1802     if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI))
1803       if (CI->getRawValue()) {
1804         hasConstantIndex = true;
1805         break;
1806       }
1807   }
1808   // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses.
1809   if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0))) return;
1810
1811   // Otherwise, decompose the GEP instruction into multiplies and adds.  Sum the
1812   // constant offset (which we now know is non-zero) and deal with it later.
1813   uint64_t ConstantOffset = 0;
1814   const Type *UIntPtrTy = TD.getIntPtrType();
1815   Value *Ptr = new CastInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI);
1816   const Type *Ty = GEPI->getOperand(0)->getType();
1817
1818   for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
1819        E = GEPI->op_end(); OI != E; ++OI) {
1820     Value *Idx = *OI;
1821     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1822       unsigned Field = cast<ConstantUInt>(Idx)->getValue();
1823       if (Field)
1824         ConstantOffset += TD.getStructLayout(StTy)->MemberOffsets[Field];
1825       Ty = StTy->getElementType(Field);
1826     } else {
1827       Ty = cast<SequentialType>(Ty)->getElementType();
1828
1829       // Handle constant subscripts.
1830       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
1831         if (CI->getRawValue() == 0) continue;
1832
1833         if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI))
1834           ConstantOffset += (int64_t)TD.getTypeSize(Ty)*CSI->getValue();
1835         else
1836           ConstantOffset+=TD.getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue();
1837         continue;
1838       }
1839
1840       // Ptr = Ptr + Idx * ElementSize;
1841
1842       // Cast Idx to UIntPtrTy if needed.
1843       Idx = new CastInst(Idx, UIntPtrTy, "", GEPI);
1844
1845       uint64_t ElementSize = TD.getTypeSize(Ty);
1846       // Mask off bits that should not be set.
1847       ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
1848       Constant *SizeCst = ConstantUInt::get(UIntPtrTy, ElementSize);
1849
1850       // Multiply by the element size and add to the base.
1851       Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI);
1852       Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI);
1853     }
1854   }
1855
1856   // Make sure that the offset fits in uintptr_t.
1857   ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
1858   Constant *PtrOffset = ConstantUInt::get(UIntPtrTy, ConstantOffset);
1859
1860   // Okay, we have now emitted all of the variable index parts to the BB that
1861   // the GEP is defined in.  Loop over all of the using instructions, inserting
1862   // an "add Ptr, ConstantOffset" into each block that uses it and update the
1863   // instruction to use the newly computed value, making GEPI dead.  When the
1864   // user is a load or store instruction address, we emit the add into the user
1865   // block, otherwise we use a canonical version right next to the gep (these
1866   // won't be foldable as addresses, so we might as well share the computation).
1867
1868   std::map<BasicBlock*,Value*> InsertedExprs;
1869   while (!GEPI->use_empty()) {
1870     Instruction *User = cast<Instruction>(GEPI->use_back());
1871
1872     // If this use is not foldable into the addressing mode, use a version
1873     // emitted in the GEP block.
1874     Value *NewVal;
1875     if (!isa<LoadInst>(User) &&
1876         (!isa<StoreInst>(User) || User->getOperand(0) == GEPI)) {
1877       NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI,
1878                                     Ptr, PtrOffset);
1879     } else {
1880       // Otherwise, insert the code in the User's block so it can be folded into
1881       // any users in that block.
1882       NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()],
1883                                     User->getParent(), GEPI,
1884                                     Ptr, PtrOffset);
1885     }
1886     User->replaceUsesOfWith(GEPI, NewVal);
1887   }
1888
1889   // Finally, the GEP is dead, remove it.
1890   GEPI->eraseFromParent();
1891 }
1892
1893 bool SelectionDAGISel::runOnFunction(Function &Fn) {
1894   MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
1895   RegMap = MF.getSSARegMap();
1896   DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n");
1897
1898   // First, split all critical edges for PHI nodes with incoming values that are
1899   // constants, this way the load of the constant into a vreg will not be placed
1900   // into MBBs that are used some other way.
1901   //
1902   // In this pass we also look for GEP instructions that are used across basic
1903   // blocks and rewrites them to improve basic-block-at-a-time selection.
1904   //
1905   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
1906     PHINode *PN;
1907     BasicBlock::iterator BBI;
1908     for (BBI = BB->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI)
1909       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1910         if (isa<Constant>(PN->getIncomingValue(i)))
1911           SplitCriticalEdge(PN->getIncomingBlock(i), BB);
1912
1913     for (BasicBlock::iterator E = BB->end(); BBI != E; )
1914       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(BBI++))
1915         OptimizeGEPExpression(GEPI, TLI.getTargetData());
1916   }
1917
1918   FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
1919
1920   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
1921     SelectBasicBlock(I, MF, FuncInfo);
1922
1923   return true;
1924 }
1925
1926
1927 SDOperand SelectionDAGISel::
1928 CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) {
1929   SDOperand Op = SDL.getValue(V);
1930   assert((Op.getOpcode() != ISD::CopyFromReg ||
1931           cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
1932          "Copy from a reg to the same reg!");
1933
1934   // If this type is not legal, we must make sure to not create an invalid
1935   // register use.
1936   MVT::ValueType SrcVT = Op.getValueType();
1937   MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
1938   SelectionDAG &DAG = SDL.DAG;
1939   if (SrcVT == DestVT) {
1940     return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
1941   } else if (SrcVT < DestVT) {
1942     // The src value is promoted to the register.
1943     if (MVT::isFloatingPoint(SrcVT))
1944       Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
1945     else
1946       Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
1947     return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
1948   } else  {
1949     // The src value is expanded into multiple registers.
1950     SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
1951                                Op, DAG.getConstant(0, MVT::i32));
1952     SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
1953                                Op, DAG.getConstant(1, MVT::i32));
1954     Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo);
1955     return DAG.getCopyToReg(Op, Reg+1, Hi);
1956   }
1957 }
1958
1959 void SelectionDAGISel::
1960 LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL,
1961                std::vector<SDOperand> &UnorderedChains) {
1962   // If this is the entry block, emit arguments.
1963   Function &F = *BB->getParent();
1964   FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
1965   SDOperand OldRoot = SDL.DAG.getRoot();
1966   std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
1967
1968   unsigned a = 0;
1969   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
1970        AI != E; ++AI, ++a)
1971     if (!AI->use_empty()) {
1972       SDL.setValue(AI, Args[a]);
1973
1974       // If this argument is live outside of the entry block, insert a copy from
1975       // whereever we got it to the vreg that other BB's will reference it as.
1976       if (FuncInfo.ValueMap.count(AI)) {
1977         SDOperand Copy =
1978           CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
1979         UnorderedChains.push_back(Copy);
1980       }
1981     }
1982
1983   // Next, if the function has live ins that need to be copied into vregs,
1984   // emit the copies now, into the top of the block.
1985   MachineFunction &MF = SDL.DAG.getMachineFunction();
1986   if (MF.livein_begin() != MF.livein_end()) {
1987     SSARegMap *RegMap = MF.getSSARegMap();
1988     const MRegisterInfo &MRI = *MF.getTarget().getRegisterInfo();
1989     for (MachineFunction::livein_iterator LI = MF.livein_begin(),
1990          E = MF.livein_end(); LI != E; ++LI)
1991       if (LI->second)
1992         MRI.copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second,
1993                          LI->first, RegMap->getRegClass(LI->second));
1994   }
1995
1996   // Finally, if the target has anything special to do, allow it to do so.
1997   EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
1998 }
1999
2000
2001 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
2002        std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
2003                                     FunctionLoweringInfo &FuncInfo) {
2004   SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
2005
2006   std::vector<SDOperand> UnorderedChains;
2007
2008   // Lower any arguments needed in this block if this is the entry block.
2009   if (LLVMBB == &LLVMBB->getParent()->front())
2010     LowerArguments(LLVMBB, SDL, UnorderedChains);
2011
2012   BB = FuncInfo.MBBMap[LLVMBB];
2013   SDL.setCurrentBasicBlock(BB);
2014
2015   // Lower all of the non-terminator instructions.
2016   for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
2017        I != E; ++I)
2018     SDL.visit(*I);
2019
2020   // Ensure that all instructions which are used outside of their defining
2021   // blocks are available as virtual registers.
2022   for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
2023     if (!I->use_empty() && !isa<PHINode>(I)) {
2024       std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
2025       if (VMI != FuncInfo.ValueMap.end())
2026         UnorderedChains.push_back(
2027                            CopyValueToVirtualRegister(SDL, I, VMI->second));
2028     }
2029
2030   // Handle PHI nodes in successor blocks.  Emit code into the SelectionDAG to
2031   // ensure constants are generated when needed.  Remember the virtual registers
2032   // that need to be added to the Machine PHI nodes as input.  We cannot just
2033   // directly add them, because expansion might result in multiple MBB's for one
2034   // BB.  As such, the start of the BB might correspond to a different MBB than
2035   // the end.
2036   //
2037
2038   // Emit constants only once even if used by multiple PHI nodes.
2039   std::map<Constant*, unsigned> ConstantsOut;
2040
2041   // Check successor nodes PHI nodes that expect a constant to be available from
2042   // this block.
2043   TerminatorInst *TI = LLVMBB->getTerminator();
2044   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
2045     BasicBlock *SuccBB = TI->getSuccessor(succ);
2046     MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin();
2047     PHINode *PN;
2048
2049     // At this point we know that there is a 1-1 correspondence between LLVM PHI
2050     // nodes and Machine PHI nodes, but the incoming operands have not been
2051     // emitted yet.
2052     for (BasicBlock::iterator I = SuccBB->begin();
2053          (PN = dyn_cast<PHINode>(I)); ++I)
2054       if (!PN->use_empty()) {
2055         unsigned Reg;
2056         Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
2057         if (Constant *C = dyn_cast<Constant>(PHIOp)) {
2058           unsigned &RegOut = ConstantsOut[C];
2059           if (RegOut == 0) {
2060             RegOut = FuncInfo.CreateRegForValue(C);
2061             UnorderedChains.push_back(
2062                              CopyValueToVirtualRegister(SDL, C, RegOut));
2063           }
2064           Reg = RegOut;
2065         } else {
2066           Reg = FuncInfo.ValueMap[PHIOp];
2067           if (Reg == 0) {
2068             assert(isa<AllocaInst>(PHIOp) &&
2069                    FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
2070                    "Didn't codegen value into a register!??");
2071             Reg = FuncInfo.CreateRegForValue(PHIOp);
2072             UnorderedChains.push_back(
2073                              CopyValueToVirtualRegister(SDL, PHIOp, Reg));
2074           }
2075         }
2076
2077         // Remember that this register needs to added to the machine PHI node as
2078         // the input for this MBB.
2079         unsigned NumElements =
2080           TLI.getNumElements(TLI.getValueType(PN->getType()));
2081         for (unsigned i = 0, e = NumElements; i != e; ++i)
2082           PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
2083       }
2084   }
2085   ConstantsOut.clear();
2086
2087   // Turn all of the unordered chains into one factored node.
2088   if (!UnorderedChains.empty()) {
2089     SDOperand Root = SDL.getRoot();
2090     if (Root.getOpcode() != ISD::EntryToken) {
2091       unsigned i = 0, e = UnorderedChains.size();
2092       for (; i != e; ++i) {
2093         assert(UnorderedChains[i].Val->getNumOperands() > 1);
2094         if (UnorderedChains[i].Val->getOperand(0) == Root)
2095           break;  // Don't add the root if we already indirectly depend on it.
2096       }
2097
2098       if (i == e)
2099         UnorderedChains.push_back(Root);
2100     }
2101     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains));
2102   }
2103
2104   // Lower the terminator after the copies are emitted.
2105   SDL.visit(*LLVMBB->getTerminator());
2106
2107   // Make sure the root of the DAG is up-to-date.
2108   DAG.setRoot(SDL.getRoot());
2109 }
2110
2111 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
2112                                         FunctionLoweringInfo &FuncInfo) {
2113   SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>());
2114   CurDAG = &DAG;
2115   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
2116
2117   // First step, lower LLVM code to some DAG.  This DAG may use operations and
2118   // types that are not supported by the target.
2119   BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
2120
2121   // Run the DAG combiner in pre-legalize mode.
2122   DAG.Combine(false);
2123
2124   DEBUG(std::cerr << "Lowered selection DAG:\n");
2125   DEBUG(DAG.dump());
2126
2127   // Second step, hack on the DAG until it only uses operations and types that
2128   // the target supports.
2129   DAG.Legalize();
2130
2131   DEBUG(std::cerr << "Legalized selection DAG:\n");
2132   DEBUG(DAG.dump());
2133
2134   // Run the DAG combiner in post-legalize mode.
2135   DAG.Combine(true);
2136
2137   if (ViewISelDAGs) DAG.viewGraph();
2138
2139   // Third, instruction select all of the operations to machine code, adding the
2140   // code to the MachineBasicBlock.
2141   InstructionSelectBasicBlock(DAG);
2142
2143   DEBUG(std::cerr << "Selected machine code:\n");
2144   DEBUG(BB->dump());
2145
2146   // Next, now that we know what the last MBB the LLVM BB expanded is, update
2147   // PHI nodes in successors.
2148   for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
2149     MachineInstr *PHI = PHINodesToUpdate[i].first;
2150     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
2151            "This is not a machine PHI node that we are updating!");
2152     PHI->addRegOperand(PHINodesToUpdate[i].second);
2153     PHI->addMachineBasicBlockOperand(BB);
2154   }
2155
2156   // Finally, add the CFG edges from the last selected MBB to the successor
2157   // MBBs.
2158   TerminatorInst *TI = LLVMBB->getTerminator();
2159   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
2160     MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[TI->getSuccessor(i)];
2161     BB->addSuccessor(Succ0MBB);
2162   }
2163 }
2164
2165 //===----------------------------------------------------------------------===//
2166 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
2167 /// target node in the graph.
2168 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
2169   if (ViewSchedDAGs) DAG.viewGraph();
2170   ScheduleDAG *SL = NULL;
2171
2172   switch (ISHeuristic) {
2173   default: assert(0 && "Unrecognized scheduling heuristic");
2174   case defaultScheduling:
2175     if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency)
2176       SL = createSimpleDAGScheduler(noScheduling, DAG, BB);
2177     else /* TargetLowering::SchedulingForRegPressure */
2178       SL = createBURRListDAGScheduler(DAG, BB);
2179     break;
2180   case noScheduling:
2181   case simpleScheduling:
2182   case simpleNoItinScheduling:
2183     SL = createSimpleDAGScheduler(ISHeuristic, DAG, BB);
2184     break;
2185   case listSchedulingBURR:
2186     SL = createBURRListDAGScheduler(DAG, BB);
2187   }
2188   BB = SL->Run();
2189   delete SL;
2190 }