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/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineInstrBuilder.h"
  24 #include "llvm/CodeGen/SelectionDAG.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/TargetData.h"
  27 #include "llvm/Target/TargetFrameInfo.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include <map>
  34 #include <iostream>
  35 using namespace llvm;
  36
  37 #ifndef _NDEBUG
  38 static cl::opt<bool>
  39 ViewDAGs("view-isel-dags", cl::Hidden,
  40          cl::desc("Pop up a window to show isel dags as they are selected"));
  41 #else
  42 static const bool ViewDAGS = 0;
  43 #endif
  44
  45 namespace llvm {
  46   //===--------------------------------------------------------------------===//
  47   /// FunctionLoweringInfo - This contains information that is global to a
  48   /// function that is used when lowering a region of the function.
  49   class FunctionLoweringInfo {
  50   public:
  51     TargetLowering &TLI;
  52     Function &Fn;
  53     MachineFunction &MF;
  54     SSARegMap *RegMap;
  55
  56     FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
  57
  58     /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
  59     std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
  60
  61     /// ValueMap - Since we emit code for the function a basic block at a time,
  62     /// we must remember which virtual registers hold the values for
  63     /// cross-basic-block values.
  64     std::map<const Value*, unsigned> ValueMap;
  65
  66     /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
  67     /// the entry block.  This allows the allocas to be efficiently referenced
  68     /// anywhere in the function.
  69     std::map<const AllocaInst*, int> StaticAllocaMap;
  70
  71     /// BlockLocalArguments - If any arguments are only used in a single basic
  72     /// block, and if the target can access the arguments without side-effects,
  73     /// avoid emitting CopyToReg nodes for those arguments.  This map keeps
  74     /// track of which arguments are local to each BB.
  75     std::multimap<BasicBlock*, std::pair<Argument*,
  76                                          unsigned> > BlockLocalArguments;
  77
  78
  79     unsigned MakeReg(MVT::ValueType VT) {
  80       return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
  81     }
  82
  83     unsigned CreateRegForValue(const Value *V) {
  84       MVT::ValueType VT = TLI.getValueType(V->getType());
  85       // The common case is that we will only create one register for this
  86       // value.  If we have that case, create and return the virtual register.
  87       unsigned NV = TLI.getNumElements(VT);
  88       if (NV == 1) {
  89         // If we are promoting this value, pick the next largest supported type.
  90         return MakeReg(TLI.getTypeToTransformTo(VT));
  91       }
  92
  93       // If this value is represented with multiple target registers, make sure
  94       // to create enough consequtive registers of the right (smaller) type.
  95       unsigned NT = VT-1;  // Find the type to use.
  96       while (TLI.getNumElements((MVT::ValueType)NT) != 1)
  97         --NT;
  98
  99       unsigned R = MakeReg((MVT::ValueType)NT);
 100       for (unsigned i = 1; i != NV; ++i)
 101         MakeReg((MVT::ValueType)NT);
 102       return R;
 103     }
 104
 105     unsigned InitializeRegForValue(const Value *V) {
 106       unsigned &R = ValueMap[V];
 107       assert(R == 0 && "Already initialized this value register!");
 108       return R = CreateRegForValue(V);
 109     }
 110   };
 111 }
 112
 113 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
 114 /// PHI nodes or outside of the basic block that defines it.
 115 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
 116   if (isa<PHINode>(I)) return true;
 117   BasicBlock *BB = I->getParent();
 118   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
 119     if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI))
 120       return true;
 121   return false;
 122 }
 123
 124 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
 125                                            Function &fn, MachineFunction &mf)
 126     : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
 127
 128   // Initialize the mapping of values to registers.  This is only set up for
 129   // instruction values that are used outside of the block that defines
 130   // them.
 131   for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI)
 132     InitializeRegForValue(AI);
 133
 134   Function::iterator BB = Fn.begin(), E = Fn.end();
 135   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 136     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 137       if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) {
 138         const Type *Ty = AI->getAllocatedType();
 139         uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
 140         unsigned Align = TLI.getTargetData().getTypeAlignment(Ty);
 141         TySize *= CUI->getValue();   // Get total allocated size.
 142         StaticAllocaMap[AI] =
 143           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
 144       }
 145
 146   for (; BB != E; ++BB)
 147     for (BasicBlock::iterator I = BB->begin(), e = BB->end(); I != e; ++I)
 148       if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
 149         if (!isa<AllocaInst>(I) ||
 150             !StaticAllocaMap.count(cast<AllocaInst>(I)))
 151           InitializeRegForValue(I);
 152
 153   // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
 154   // also creates the initial PHI MachineInstrs, though none of the input
 155   // operands are populated.
 156   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 157     MachineBasicBlock *MBB = new MachineBasicBlock(BB);
 158     MBBMap[BB] = MBB;
 159     MF.getBasicBlockList().push_back(MBB);
 160
 161     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
 162     // appropriate.
 163     PHINode *PN;
 164     for (BasicBlock::iterator I = BB->begin();
 165          (PN = dyn_cast<PHINode>(I)); ++I)
 166       if (!PN->use_empty()) {
 167         unsigned NumElements =
 168           TLI.getNumElements(TLI.getValueType(PN->getType()));
 169         unsigned PHIReg = ValueMap[PN];
 170         assert(PHIReg &&"PHI node does not have an assigned virtual register!");
 171         for (unsigned i = 0; i != NumElements; ++i)
 172           BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i);
 173       }
 174   }
 175 }
 176
 177
 178
 179 //===----------------------------------------------------------------------===//
 180 /// SelectionDAGLowering - This is the common target-independent lowering
 181 /// implementation that is parameterized by a TargetLowering object.
 182 /// Also, targets can overload any lowering method.
 183 ///
 184 namespace llvm {
 185 class SelectionDAGLowering {
 186   MachineBasicBlock *CurMBB;
 187
 188   std::map<const Value*, SDOperand> NodeMap;
 189
 190 public:
 191   // TLI - This is information that describes the available target features we
 192   // need for lowering.  This indicates when operations are unavailable,
 193   // implemented with a libcall, etc.
 194   TargetLowering &TLI;
 195   SelectionDAG &DAG;
 196   const TargetData &TD;
 197
 198   /// FuncInfo - Information about the function as a whole.
 199   ///
 200   FunctionLoweringInfo &FuncInfo;
 201
 202   SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
 203                        FunctionLoweringInfo &funcinfo)
 204     : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
 205       FuncInfo(funcinfo) {
 206   }
 207
 208   void visit(Instruction &I) { visit(I.getOpcode(), I); }
 209
 210   void visit(unsigned Opcode, User &I) {
 211     switch (Opcode) {
 212     default: assert(0 && "Unknown instruction type encountered!");
 213              abort();
 214       // Build the switch statement using the Instruction.def file.
 215 #define HANDLE_INST(NUM, OPCODE, CLASS) \
 216     case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
 217 #include "llvm/Instruction.def"
 218     }
 219   }
 220
 221   void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
 222
 223
 224   SDOperand getIntPtrConstant(uint64_t Val) {
 225     return DAG.getConstant(Val, TLI.getPointerTy());
 226   }
 227
 228   SDOperand getValue(const Value *V) {
 229     SDOperand &N = NodeMap[V];
 230     if (N.Val) return N;
 231
 232     MVT::ValueType VT = TLI.getValueType(V->getType());
 233     if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V)))
 234       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 235         visit(CE->getOpcode(), *CE);
 236         assert(N.Val && "visit didn't populate the ValueMap!");
 237         return N;
 238       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
 239         return N = DAG.getGlobalAddress(GV, VT);
 240       } else if (isa<ConstantPointerNull>(C)) {
 241         return N = DAG.getConstant(0, TLI.getPointerTy());
 242       } else if (isa<UndefValue>(C)) {
 243         /// FIXME: Implement UNDEFVALUE better.
 244         if (MVT::isInteger(VT))
 245           return N = DAG.getConstant(0, VT);
 246         else if (MVT::isFloatingPoint(VT))
 247           return N = DAG.getConstantFP(0, VT);
 248         else
 249           assert(0 && "Unknown value type!");
 250
 251       } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 252         return N = DAG.getConstantFP(CFP->getValue(), VT);
 253       } else {
 254         // Canonicalize all constant ints to be unsigned.
 255         return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT);
 256       }
 257
 258     if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 259       std::map<const AllocaInst*, int>::iterator SI =
 260         FuncInfo.StaticAllocaMap.find(AI);
 261       if (SI != FuncInfo.StaticAllocaMap.end())
 262         return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
 263     }
 264
 265     std::map<const Value*, unsigned>::const_iterator VMI =
 266       FuncInfo.ValueMap.find(V);
 267     assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!");
 268
 269     MVT::ValueType RegVT = VT;
 270     if (TLI.getTypeAction(VT) == 1)          // Must promote this value?
 271       RegVT = TLI.getTypeToTransformTo(VT);
 272
 273     N = DAG.getCopyFromReg(VMI->second, RegVT, DAG.getEntryNode());
 274
 275     if (RegVT != VT)
 276       if (MVT::isFloatingPoint(VT))
 277         N = DAG.getNode(ISD::FP_ROUND, VT, N);
 278       else
 279         N = DAG.getNode(ISD::TRUNCATE, VT, N);
 280
 281     return N;
 282   }
 283
 284   const SDOperand &setValue(const Value *V, SDOperand NewN) {
 285     SDOperand &N = NodeMap[V];
 286     assert(N.Val == 0 && "Already set a value for this node!");
 287     return N = NewN;
 288   }
 289
 290   // Terminator instructions.
 291   void visitRet(ReturnInst &I);
 292   void visitBr(BranchInst &I);
 293   void visitUnreachable(UnreachableInst &I) { /* noop */ }
 294
 295   // These all get lowered before this pass.
 296   void visitSwitch(SwitchInst &I) { assert(0 && "TODO"); }
 297   void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); }
 298   void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); }
 299
 300   //
 301   void visitBinary(User &I, unsigned Opcode);
 302   void visitAdd(User &I) { visitBinary(I, ISD::ADD); }
 303   void visitSub(User &I) { visitBinary(I, ISD::SUB); }
 304   void visitMul(User &I) { visitBinary(I, ISD::MUL); }
 305   void visitDiv(User &I) {
 306     visitBinary(I, I.getType()->isUnsigned() ? ISD::UDIV : ISD::SDIV);
 307   }
 308   void visitRem(User &I) {
 309     visitBinary(I, I.getType()->isUnsigned() ? ISD::UREM : ISD::SREM);
 310   }
 311   void visitAnd(User &I) { visitBinary(I, ISD::AND); }
 312   void visitOr (User &I) { visitBinary(I, ISD::OR); }
 313   void visitXor(User &I) { visitBinary(I, ISD::XOR); }
 314   void visitShl(User &I) { visitBinary(I, ISD::SHL); }
 315   void visitShr(User &I) {
 316     visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA);
 317   }
 318
 319   void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc);
 320   void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); }
 321   void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); }
 322   void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); }
 323   void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); }
 324   void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); }
 325   void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); }
 326
 327   void visitGetElementPtr(User &I);
 328   void visitCast(User &I);
 329   void visitSelect(User &I);
 330   //
 331
 332   void visitMalloc(MallocInst &I);
 333   void visitFree(FreeInst &I);
 334   void visitAlloca(AllocaInst &I);
 335   void visitLoad(LoadInst &I);
 336   void visitStore(StoreInst &I);
 337   void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
 338   void visitCall(CallInst &I);
 339
 340   void visitVAStart(CallInst &I);
 341   void visitVANext(VANextInst &I);
 342   void visitVAArg(VAArgInst &I);
 343   void visitVAEnd(CallInst &I);
 344   void visitVACopy(CallInst &I);
 345   void visitFrameReturnAddress(CallInst &I, bool isFrameAddress);
 346
 347   void visitMemIntrinsic(CallInst &I, unsigned Op);
 348
 349   void visitUserOp1(Instruction &I) {
 350     assert(0 && "UserOp1 should not exist at instruction selection time!");
 351     abort();
 352   }
 353   void visitUserOp2(Instruction &I) {
 354     assert(0 && "UserOp2 should not exist at instruction selection time!");
 355     abort();
 356   }
 357 };
 358 } // end namespace llvm
 359
 360 void SelectionDAGLowering::visitRet(ReturnInst &I) {
 361   if (I.getNumOperands() == 0) {
 362     DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, DAG.getRoot()));
 363     return;
 364   }
 365
 366   SDOperand Op1 = getValue(I.getOperand(0));
 367   switch (Op1.getValueType()) {
 368   default: assert(0 && "Unknown value type!");
 369   case MVT::i1:
 370   case MVT::i8:
 371   case MVT::i16:
 372     // Extend integer types to 32-bits.
 373     if (I.getOperand(0)->getType()->isSigned())
 374       Op1 = DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Op1);
 375     else
 376       Op1 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Op1);
 377     break;
 378   case MVT::f32:
 379     // Extend float to double.
 380     Op1 = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Op1);
 381     break;
 382   case MVT::i32:
 383   case MVT::i64:
 384   case MVT::f64:
 385     break; // No extension needed!
 386   }
 387
 388   DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, DAG.getRoot(), Op1));
 389 }
 390
 391 void SelectionDAGLowering::visitBr(BranchInst &I) {
 392   // Update machine-CFG edges.
 393   MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
 394   CurMBB->addSuccessor(Succ0MBB);
 395
 396   // Figure out which block is immediately after the current one.
 397   MachineBasicBlock *NextBlock = 0;
 398   MachineFunction::iterator BBI = CurMBB;
 399   if (++BBI != CurMBB->getParent()->end())
 400     NextBlock = BBI;
 401
 402   if (I.isUnconditional()) {
 403     // If this is not a fall-through branch, emit the branch.
 404     if (Succ0MBB != NextBlock)
 405       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, DAG.getRoot(),
 406                               DAG.getBasicBlock(Succ0MBB)));
 407   } else {
 408     MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
 409     CurMBB->addSuccessor(Succ1MBB);
 410
 411     SDOperand Cond = getValue(I.getCondition());
 412
 413     if (Succ1MBB == NextBlock) {
 414       // If the condition is false, fall through.  This means we should branch
 415       // if the condition is true to Succ #0.
 416       DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(),
 417                               Cond, DAG.getBasicBlock(Succ0MBB)));
 418     } else if (Succ0MBB == NextBlock) {
 419       // If the condition is true, fall through.  This means we should branch if
 420       // the condition is false to Succ #1.  Invert the condition first.
 421       SDOperand True = DAG.getConstant(1, Cond.getValueType());
 422       Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
 423       DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(),
 424                               Cond, DAG.getBasicBlock(Succ1MBB)));
 425     } else {
 426       // Neither edge is a fall through.  If the comparison is true, jump to
 427       // Succ#0, otherwise branch unconditionally to succ #1.
 428       DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(),
 429                               Cond, DAG.getBasicBlock(Succ0MBB)));
 430       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, DAG.getRoot(),
 431                               DAG.getBasicBlock(Succ1MBB)));
 432     }
 433   }
 434 }
 435
 436 void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode) {
 437   SDOperand Op1 = getValue(I.getOperand(0));
 438   SDOperand Op2 = getValue(I.getOperand(1));
 439   setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
 440 }
 441
 442 void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode,
 443                                       ISD::CondCode UnsignedOpcode) {
 444   SDOperand Op1 = getValue(I.getOperand(0));
 445   SDOperand Op2 = getValue(I.getOperand(1));
 446   ISD::CondCode Opcode = SignedOpcode;
 447   if (I.getOperand(0)->getType()->isUnsigned())
 448     Opcode = UnsignedOpcode;
 449   setValue(&I, DAG.getSetCC(Opcode, Op1, Op2));
 450 }
 451
 452 void SelectionDAGLowering::visitSelect(User &I) {
 453   SDOperand Cond     = getValue(I.getOperand(0));
 454   SDOperand TrueVal  = getValue(I.getOperand(1));
 455   SDOperand FalseVal = getValue(I.getOperand(2));
 456   setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
 457                            TrueVal, FalseVal));
 458 }
 459
 460 void SelectionDAGLowering::visitCast(User &I) {
 461   SDOperand N = getValue(I.getOperand(0));
 462   MVT::ValueType SrcTy = TLI.getValueType(I.getOperand(0)->getType());
 463   MVT::ValueType DestTy = TLI.getValueType(I.getType());
 464
 465   if (N.getValueType() == DestTy) {
 466     setValue(&I, N);  // noop cast.
 467   } else if (isInteger(SrcTy)) {
 468     if (isInteger(DestTy)) {        // Int -> Int cast
 469       if (DestTy < SrcTy)   // Truncating cast?
 470         setValue(&I, DAG.getNode(ISD::TRUNCATE, DestTy, N));
 471       else if (I.getOperand(0)->getType()->isSigned())
 472         setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestTy, N));
 473       else
 474         setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestTy, N));
 475     } else {                        // Int -> FP cast
 476       if (I.getOperand(0)->getType()->isSigned())
 477         setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestTy, N));
 478       else
 479         setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestTy, N));
 480     }
 481   } else {
 482     assert(isFloatingPoint(SrcTy) && "Unknown value type!");
 483     if (isFloatingPoint(DestTy)) {  // FP -> FP cast
 484       if (DestTy < SrcTy)   // Rounding cast?
 485         setValue(&I, DAG.getNode(ISD::FP_ROUND, DestTy, N));
 486       else
 487         setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestTy, N));
 488     } else {                        // FP -> Int cast.
 489       if (I.getType()->isSigned())
 490         setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestTy, N));
 491       else
 492         setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestTy, N));
 493     }
 494   }
 495 }
 496
 497 void SelectionDAGLowering::visitGetElementPtr(User &I) {
 498   SDOperand N = getValue(I.getOperand(0));
 499   const Type *Ty = I.getOperand(0)->getType();
 500   const Type *UIntPtrTy = TD.getIntPtrType();
 501
 502   for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
 503        OI != E; ++OI) {
 504     Value *Idx = *OI;
 505     if (const StructType *StTy = dyn_cast<StructType> (Ty)) {
 506       unsigned Field = cast<ConstantUInt>(Idx)->getValue();
 507       if (Field) {
 508         // N = N + Offset
 509         uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field];
 510         N = DAG.getNode(ISD::ADD, N.getValueType(), N,
 511                         getIntPtrConstant(Offset));
 512       }
 513       Ty = StTy->getElementType(Field);
 514     } else {
 515       Ty = cast<SequentialType>(Ty)->getElementType();
 516       if (!isa<Constant>(Idx) || !cast<Constant>(Idx)->isNullValue()) {
 517         // N = N + Idx * ElementSize;
 518         uint64_t ElementSize = TD.getTypeSize(Ty);
 519         SDOperand IdxN = getValue(Idx), Scale = getIntPtrConstant(ElementSize);
 520
 521         // If the index is smaller or larger than intptr_t, truncate or extend
 522         // it.
 523         if (IdxN.getValueType() < Scale.getValueType()) {
 524           if (Idx->getType()->isSigned())
 525             IdxN = DAG.getNode(ISD::SIGN_EXTEND, Scale.getValueType(), IdxN);
 526           else
 527             IdxN = DAG.getNode(ISD::ZERO_EXTEND, Scale.getValueType(), IdxN);
 528         } else if (IdxN.getValueType() > Scale.getValueType())
 529           IdxN = DAG.getNode(ISD::TRUNCATE, Scale.getValueType(), IdxN);
 530
 531         IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
 532
 533         N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
 534       }
 535     }
 536   }
 537   setValue(&I, N);
 538 }
 539
 540 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
 541   // If this is a fixed sized alloca in the entry block of the function,
 542   // allocate it statically on the stack.
 543   if (FuncInfo.StaticAllocaMap.count(&I))
 544     return;   // getValue will auto-populate this.
 545
 546   const Type *Ty = I.getAllocatedType();
 547   uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
 548   unsigned Align = TLI.getTargetData().getTypeAlignment(Ty);
 549
 550   SDOperand AllocSize = getValue(I.getArraySize());
 551
 552   assert(AllocSize.getValueType() == TLI.getPointerTy() &&
 553          "FIXME: should extend or truncate to pointer size!");
 554
 555   AllocSize = DAG.getNode(ISD::MUL, TLI.getPointerTy(), AllocSize,
 556                           getIntPtrConstant(TySize));
 557
 558   // Handle alignment.  If the requested alignment is less than or equal to the
 559   // stack alignment, ignore it and round the size of the allocation up to the
 560   // stack alignment size.  If the size is greater than the stack alignment, we
 561   // note this in the DYNAMIC_STACKALLOC node.
 562   unsigned StackAlign =
 563     TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
 564   if (Align <= StackAlign) {
 565     Align = 0;
 566     // Add SA-1 to the size.
 567     AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
 568                             getIntPtrConstant(StackAlign-1));
 569     // Mask out the low bits for alignment purposes.
 570     AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
 571                             getIntPtrConstant(~(uint64_t)(StackAlign-1)));
 572   }
 573
 574   SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, AllocSize.getValueType(),
 575                               DAG.getRoot(), AllocSize,
 576                               getIntPtrConstant(Align));
 577   DAG.setRoot(setValue(&I, DSA).getValue(1));
 578
 579   // Inform the Frame Information that we have just allocated a variable-sized
 580   // object.
 581   CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
 582 }
 583
 584
 585 void SelectionDAGLowering::visitLoad(LoadInst &I) {
 586   SDOperand Ptr = getValue(I.getOperand(0));
 587   SDOperand L = DAG.getLoad(TLI.getValueType(I.getType()), DAG.getRoot(), Ptr);
 588   DAG.setRoot(setValue(&I, L).getValue(1));
 589 }
 590
 591
 592 void SelectionDAGLowering::visitStore(StoreInst &I) {
 593   Value *SrcV = I.getOperand(0);
 594   SDOperand Src = getValue(SrcV);
 595   SDOperand Ptr = getValue(I.getOperand(1));
 596   DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, DAG.getRoot(), Src, Ptr));
 597 }
 598
 599 void SelectionDAGLowering::visitCall(CallInst &I) {
 600   const char *RenameFn = 0;
 601   if (Function *F = I.getCalledFunction())
 602     switch (F->getIntrinsicID()) {
 603     case 0: break;  // Not an intrinsic.
 604     case Intrinsic::vastart:  visitVAStart(I); return;
 605     case Intrinsic::vaend:    visitVAEnd(I); return;
 606     case Intrinsic::vacopy:   visitVACopy(I); return;
 607     case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return;
 608     case Intrinsic::frameaddress:  visitFrameReturnAddress(I, true); return;
 609     default:
 610       // FIXME: IMPLEMENT THESE.
 611       // readport, writeport, readio, writeio
 612       assert(0 && "This intrinsic is not implemented yet!");
 613       return;
 614     case Intrinsic::setjmp:  RenameFn = "setjmp"; break;
 615     case Intrinsic::longjmp: RenameFn = "longjmp"; break;
 616     case Intrinsic::memcpy:  visitMemIntrinsic(I, ISD::MEMCPY); return;
 617     case Intrinsic::memset:  visitMemIntrinsic(I, ISD::MEMSET); return;
 618     case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return;
 619
 620     case Intrinsic::isunordered:
 621       setValue(&I, DAG.getSetCC(ISD::SETUO, getValue(I.getOperand(1)),
 622                                 getValue(I.getOperand(2))));
 623       return;
 624     }
 625
 626   SDOperand Callee;
 627   if (!RenameFn)
 628     Callee = getValue(I.getOperand(0));
 629   else
 630     Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
 631   std::vector<std::pair<SDOperand, const Type*> > Args;
 632
 633   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
 634     Value *Arg = I.getOperand(i);
 635     SDOperand ArgNode = getValue(Arg);
 636     Args.push_back(std::make_pair(ArgNode, Arg->getType()));
 637   }
 638
 639   std::pair<SDOperand,SDOperand> Result =
 640     TLI.LowerCallTo(DAG.getRoot(), I.getType(), Callee, Args, DAG);
 641   if (I.getType() != Type::VoidTy)
 642     setValue(&I, Result.first);
 643   DAG.setRoot(Result.second);
 644 }
 645
 646 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
 647   SDOperand Src = getValue(I.getOperand(0));
 648
 649   MVT::ValueType IntPtr = TLI.getPointerTy();
 650   // FIXME: Extend or truncate to the intptr size.
 651   assert(Src.getValueType() == IntPtr && "Need to adjust the amount!");
 652
 653   // Scale the source by the type size.
 654   uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType());
 655   Src = DAG.getNode(ISD::MUL, Src.getValueType(),
 656                     Src, getIntPtrConstant(ElementSize));
 657
 658   std::vector<std::pair<SDOperand, const Type*> > Args;
 659   Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType()));
 660
 661   std::pair<SDOperand,SDOperand> Result =
 662     TLI.LowerCallTo(DAG.getRoot(), I.getType(),
 663                     DAG.getExternalSymbol("malloc", IntPtr),
 664                     Args, DAG);
 665   setValue(&I, Result.first);  // Pointers always fit in registers
 666   DAG.setRoot(Result.second);
 667 }
 668
 669 void SelectionDAGLowering::visitFree(FreeInst &I) {
 670   std::vector<std::pair<SDOperand, const Type*> > Args;
 671   Args.push_back(std::make_pair(getValue(I.getOperand(0)),
 672                                 TLI.getTargetData().getIntPtrType()));
 673   MVT::ValueType IntPtr = TLI.getPointerTy();
 674   std::pair<SDOperand,SDOperand> Result =
 675     TLI.LowerCallTo(DAG.getRoot(), Type::VoidTy,
 676                     DAG.getExternalSymbol("free", IntPtr), Args, DAG);
 677   DAG.setRoot(Result.second);
 678 }
 679
 680 std::pair<SDOperand, SDOperand>
 681 TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 682   // We have no sane default behavior, just emit a useful error message and bail
 683   // out.
 684   std::cerr << "Variable arguments handling not implemented on this target!\n";
 685   abort();
 686 }
 687
 688 SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand L,
 689                                      SelectionDAG &DAG) {
 690   // Default to a noop.
 691   return Chain;
 692 }
 693
 694 std::pair<SDOperand,SDOperand>
 695 TargetLowering::LowerVACopy(SDOperand Chain, SDOperand L, SelectionDAG &DAG) {
 696   // Default to returning the input list.
 697   return std::make_pair(L, Chain);
 698 }
 699
 700 std::pair<SDOperand,SDOperand>
 701 TargetLowering::LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 702                                const Type *ArgTy, SelectionDAG &DAG) {
 703   // We have no sane default behavior, just emit a useful error message and bail
 704   // out.
 705   std::cerr << "Variable arguments handling not implemented on this target!\n";
 706   abort();
 707 }
 708
 709
 710 void SelectionDAGLowering::visitVAStart(CallInst &I) {
 711   std::pair<SDOperand,SDOperand> Result = TLI.LowerVAStart(DAG.getRoot(), DAG);
 712   setValue(&I, Result.first);
 713   DAG.setRoot(Result.second);
 714 }
 715
 716 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
 717   std::pair<SDOperand,SDOperand> Result =
 718     TLI.LowerVAArgNext(false, DAG.getRoot(), getValue(I.getOperand(0)),
 719                        I.getType(), DAG);
 720   setValue(&I, Result.first);
 721   DAG.setRoot(Result.second);
 722 }
 723
 724 void SelectionDAGLowering::visitVANext(VANextInst &I) {
 725   std::pair<SDOperand,SDOperand> Result =
 726     TLI.LowerVAArgNext(true, DAG.getRoot(), getValue(I.getOperand(0)),
 727                        I.getArgType(), DAG);
 728   setValue(&I, Result.first);
 729   DAG.setRoot(Result.second);
 730 }
 731
 732 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
 733   DAG.setRoot(TLI.LowerVAEnd(DAG.getRoot(), getValue(I.getOperand(1)), DAG));
 734 }
 735
 736 void SelectionDAGLowering::visitVACopy(CallInst &I) {
 737   std::pair<SDOperand,SDOperand> Result =
 738     TLI.LowerVACopy(DAG.getRoot(), getValue(I.getOperand(1)), DAG);
 739   setValue(&I, Result.first);
 740   DAG.setRoot(Result.second);
 741 }
 742
 743
 744 // It is always conservatively correct for llvm.returnaddress and
 745 // llvm.frameaddress to return 0.
 746 std::pair<SDOperand, SDOperand>
 747 TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain,
 748                                         unsigned Depth, SelectionDAG &DAG) {
 749   return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain);
 750 }
 751
 752 SDOperand TargetLowering::LowerOperation(SDOperand Op) {
 753   assert(0 && "LowerOperation not implemented for this target!");
 754   abort();
 755 }
 756
 757 void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) {
 758   unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue();
 759   std::pair<SDOperand,SDOperand> Result =
 760     TLI.LowerFrameReturnAddress(isFrame, DAG.getRoot(), Depth, DAG);
 761   setValue(&I, Result.first);
 762   DAG.setRoot(Result.second);
 763 }
 764
 765 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
 766   std::vector<SDOperand> Ops;
 767   Ops.push_back(DAG.getRoot());
 768   Ops.push_back(getValue(I.getOperand(1)));
 769   Ops.push_back(getValue(I.getOperand(2)));
 770   Ops.push_back(getValue(I.getOperand(3)));
 771   Ops.push_back(getValue(I.getOperand(4)));
 772   DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops));
 773 }
 774
 775 //===----------------------------------------------------------------------===//
 776 // SelectionDAGISel code
 777 //===----------------------------------------------------------------------===//
 778
 779 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
 780   return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
 781 }
 782
 783
 784
 785 bool SelectionDAGISel::runOnFunction(Function &Fn) {
 786   MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
 787   RegMap = MF.getSSARegMap();
 788   DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n");
 789
 790   FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
 791
 792   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 793     SelectBasicBlock(I, MF, FuncInfo);
 794
 795   return true;
 796 }
 797
 798
 799 SDOperand SelectionDAGISel::
 800 CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) {
 801   SelectionDAG &DAG = SDL.DAG;
 802   SDOperand Op = SDL.getValue(V);
 803   assert((Op.getOpcode() != ISD::CopyFromReg ||
 804           cast<RegSDNode>(Op)->getReg() != Reg) &&
 805          "Copy from a reg to the same reg!");
 806   MVT::ValueType VT = Op.getValueType();
 807   if (TLI.getTypeAction(VT) == 1) {       // Must promote this value?
 808     if (MVT::isFloatingPoint(VT))
 809       Op = DAG.getNode(ISD::FP_EXTEND, TLI.getTypeToTransformTo(VT), Op);
 810     else
 811       Op = DAG.getNode(ISD::ZERO_EXTEND, TLI.getTypeToTransformTo(VT), Op);
 812   }
 813
 814   return DAG.getCopyToReg(DAG.getRoot(), Op, Reg);
 815 }
 816
 817 /// IsOnlyUsedInOneBasicBlock - If the specified argument is only used in a
 818 /// single basic block, return that block.  Otherwise, return a null pointer.
 819 static BasicBlock *IsOnlyUsedInOneBasicBlock(Argument *A) {
 820   if (A->use_empty()) return 0;
 821   BasicBlock *BB = cast<Instruction>(A->use_back())->getParent();
 822   for (Argument::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E;
 823        ++UI)
 824     if (isa<PHINode>(*UI) || cast<Instruction>(*UI)->getParent() != BB)
 825       return 0;  // Disagreement among the users?
 826   return BB;
 827 }
 828
 829 void SelectionDAGISel::
 830 LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL,
 831                std::vector<SDOperand> &UnorderedChains) {
 832   // If this is the entry block, emit arguments.
 833   Function &F = *BB->getParent();
 834   FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
 835
 836   if (BB == &F.front()) {
 837     SDOperand OldRoot = SDL.DAG.getRoot();
 838
 839     std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
 840
 841     // If there were side effects accessing the argument list, do not do
 842     // anything special.
 843     if (OldRoot != SDL.DAG.getRoot()) {
 844       unsigned a = 0;
 845       for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI,++a)
 846         if (!AI->use_empty()) {
 847           SDL.setValue(AI, Args[a]);
 848           SDOperand Copy =
 849             CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
 850           UnorderedChains.push_back(Copy);
 851         }
 852     } else {
 853       // Otherwise, if any argument is only accessed in a single basic block,
 854       // emit that argument only to that basic block.
 855       unsigned a = 0;
 856       for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI,++a)
 857         if (!AI->use_empty()) {
 858           if (BasicBlock *BBU = IsOnlyUsedInOneBasicBlock(AI)) {
 859             FuncInfo.BlockLocalArguments.insert(std::make_pair(BBU,
 860                                                       std::make_pair(AI, a)));
 861           } else {
 862             SDL.setValue(AI, Args[a]);
 863             SDOperand Copy =
 864               CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
 865             UnorderedChains.push_back(Copy);
 866           }
 867         }
 868     }
 869   }
 870
 871   // See if there are any block-local arguments that need to be emitted in this
 872   // block.
 873
 874   if (!FuncInfo.BlockLocalArguments.empty()) {
 875     std::multimap<BasicBlock*, std::pair<Argument*, unsigned> >::iterator BLAI =
 876       FuncInfo.BlockLocalArguments.lower_bound(BB);
 877     if (BLAI != FuncInfo.BlockLocalArguments.end() && BLAI->first == BB) {
 878       // Lower the arguments into this block.
 879       std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
 880
 881       // Set up the value mapping for the local arguments.
 882       for (; BLAI != FuncInfo.BlockLocalArguments.end() && BLAI->first == BB;
 883            ++BLAI)
 884         SDL.setValue(BLAI->second.first, Args[BLAI->second.second]);
 885
 886       // Any dead arguments will just be ignored here.
 887     }
 888   }
 889 }
 890
 891
 892 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
 893        std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
 894                                     FunctionLoweringInfo &FuncInfo) {
 895   SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
 896
 897   std::vector<SDOperand> UnorderedChains;
 898
 899   // Lower any arguments needed in this block.
 900   LowerArguments(LLVMBB, SDL, UnorderedChains);
 901
 902   BB = FuncInfo.MBBMap[LLVMBB];
 903   SDL.setCurrentBasicBlock(BB);
 904
 905   // Lower all of the non-terminator instructions.
 906   for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
 907        I != E; ++I)
 908     SDL.visit(*I);
 909
 910   // Ensure that all instructions which are used outside of their defining
 911   // blocks are available as virtual registers.
 912   for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
 913     if (!I->use_empty() && !isa<PHINode>(I)) {
 914       std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
 915       if (VMI != FuncInfo.ValueMap.end())
 916         UnorderedChains.push_back(
 917                            CopyValueToVirtualRegister(SDL, I, VMI->second));
 918     }
 919
 920   // Handle PHI nodes in successor blocks.  Emit code into the SelectionDAG to
 921   // ensure constants are generated when needed.  Remember the virtual registers
 922   // that need to be added to the Machine PHI nodes as input.  We cannot just
 923   // directly add them, because expansion might result in multiple MBB's for one
 924   // BB.  As such, the start of the BB might correspond to a different MBB than
 925   // the end.
 926   //
 927
 928   // Emit constants only once even if used by multiple PHI nodes.
 929   std::map<Constant*, unsigned> ConstantsOut;
 930
 931   // Check successor nodes PHI nodes that expect a constant to be available from
 932   // this block.
 933   TerminatorInst *TI = LLVMBB->getTerminator();
 934   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
 935     BasicBlock *SuccBB = TI->getSuccessor(succ);
 936     MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin();
 937     PHINode *PN;
 938
 939     // At this point we know that there is a 1-1 correspondence between LLVM PHI
 940     // nodes and Machine PHI nodes, but the incoming operands have not been
 941     // emitted yet.
 942     for (BasicBlock::iterator I = SuccBB->begin();
 943          (PN = dyn_cast<PHINode>(I)); ++I)
 944       if (!PN->use_empty()) {
 945         unsigned Reg;
 946         Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
 947         if (Constant *C = dyn_cast<Constant>(PHIOp)) {
 948           unsigned &RegOut = ConstantsOut[C];
 949           if (RegOut == 0) {
 950             RegOut = FuncInfo.CreateRegForValue(C);
 951             UnorderedChains.push_back(
 952                              CopyValueToVirtualRegister(SDL, C, RegOut));
 953           }
 954           Reg = RegOut;
 955         } else {
 956           Reg = FuncInfo.ValueMap[PHIOp];
 957           if (Reg == 0) {
 958             assert(isa<AllocaInst>(PHIOp) &&
 959                    FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
 960                    "Didn't codegen value into a register!??");
 961             Reg = FuncInfo.CreateRegForValue(PHIOp);
 962             UnorderedChains.push_back(
 963                              CopyValueToVirtualRegister(SDL, PHIOp, Reg));
 964           }
 965         }
 966
 967         // Remember that this register needs to added to the machine PHI node as
 968         // the input for this MBB.
 969         unsigned NumElements =
 970           TLI.getNumElements(TLI.getValueType(PN->getType()));
 971         for (unsigned i = 0, e = NumElements; i != e; ++i)
 972           PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
 973       }
 974   }
 975   ConstantsOut.clear();
 976
 977   // Turn all of the unordered chains into one factored node.
 978   if (!UnorderedChains.empty()) {
 979     UnorderedChains.push_back(DAG.getRoot());
 980     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains));
 981   }
 982
 983   // Lower the terminator after the copies are emitted.
 984   SDL.visit(*LLVMBB->getTerminator());
 985 }
 986
 987 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
 988                                         FunctionLoweringInfo &FuncInfo) {
 989   SelectionDAG DAG(TLI.getTargetMachine(), MF);
 990   CurDAG = &DAG;
 991   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
 992
 993   // First step, lower LLVM code to some DAG.  This DAG may use operations and
 994   // types that are not supported by the target.
 995   BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
 996
 997   DEBUG(std::cerr << "Lowered selection DAG:\n");
 998   DEBUG(DAG.dump());
 999
1000   // Second step, hack on the DAG until it only uses operations and types that
1001   // the target supports.
1002   DAG.Legalize(TLI);
1003
1004   DEBUG(std::cerr << "Legalized selection DAG:\n");
1005   DEBUG(DAG.dump());
1006
1007   // Finally, instruction select all of the operations to machine code, adding
1008   // the code to the MachineBasicBlock.
1009   InstructionSelectBasicBlock(DAG);
1010
1011   if (ViewDAGs) DAG.viewGraph();
1012
1013   DEBUG(std::cerr << "Selected machine code:\n");
1014   DEBUG(BB->dump());
1015
1016   // Finally, now that we know what the last MBB the LLVM BB expanded is, update
1017   // PHI nodes in successors.
1018   for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
1019     MachineInstr *PHI = PHINodesToUpdate[i].first;
1020     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
1021            "This is not a machine PHI node that we are updating!");
1022     PHI->addRegOperand(PHINodesToUpdate[i].second);
1023     PHI->addMachineBasicBlockOperand(BB);
1024   }
1025 }