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