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