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/ADT/BitVector.h"
  16 #include "llvm/Analysis/AliasAnalysis.h"
  17 #include "llvm/CodeGen/SelectionDAGISel.h"
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/GlobalVariable.h"
  24 #include "llvm/InlineAsm.h"
  25 #include "llvm/Instructions.h"
  26 #include "llvm/Intrinsics.h"
  27 #include "llvm/IntrinsicInst.h"
  28 #include "llvm/ParameterAttributes.h"
  29 #include "llvm/CodeGen/MachineModuleInfo.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineFrameInfo.h"
  32 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  33 #include "llvm/CodeGen/MachineInstrBuilder.h"
  34 #include "llvm/CodeGen/SchedulerRegistry.h"
  35 #include "llvm/CodeGen/SelectionDAG.h"
  36 #include "llvm/CodeGen/SSARegMap.h"
  37 #include "llvm/Target/MRegisterInfo.h"
  38 #include "llvm/Target/TargetData.h"
  39 #include "llvm/Target/TargetFrameInfo.h"
  40 #include "llvm/Target/TargetInstrInfo.h"
  41 #include "llvm/Target/TargetLowering.h"
  42 #include "llvm/Target/TargetMachine.h"
  43 #include "llvm/Target/TargetOptions.h"
  44 #include "llvm/Support/MathExtras.h"
  45 #include "llvm/Support/Debug.h"
  46 #include "llvm/Support/Compiler.h"
  47 #include <algorithm>
  48 using namespace llvm;
  49
  50 #ifndef NDEBUG
  51 static cl::opt<bool>
  52 ViewISelDAGs("view-isel-dags", cl::Hidden,
  53           cl::desc("Pop up a window to show isel dags as they are selected"));
  54 static cl::opt<bool>
  55 ViewSchedDAGs("view-sched-dags", cl::Hidden,
  56           cl::desc("Pop up a window to show sched dags as they are processed"));
  57 #else
  58 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
  59 #endif
  60
  61 //===---------------------------------------------------------------------===//
  62 ///
  63 /// RegisterScheduler class - Track the registration of instruction schedulers.
  64 ///
  65 //===---------------------------------------------------------------------===//
  66 MachinePassRegistry RegisterScheduler::Registry;
  67
  68 //===---------------------------------------------------------------------===//
  69 ///
  70 /// ISHeuristic command line option for instruction schedulers.
  71 ///
  72 //===---------------------------------------------------------------------===//
  73 namespace {
  74   cl::opt<RegisterScheduler::FunctionPassCtor, false,
  75           RegisterPassParser<RegisterScheduler> >
  76   ISHeuristic("sched",
  77               cl::init(&createDefaultScheduler),
  78               cl::desc("Instruction schedulers available:"));
  79
  80   static RegisterScheduler
  81   defaultListDAGScheduler("default", "  Best scheduler for the target",
  82                           createDefaultScheduler);
  83 } // namespace
  84
  85 namespace {
  86   /// RegsForValue - This struct represents the physical registers that a
  87   /// particular value is assigned and the type information about the value.
  88   /// This is needed because values can be promoted into larger registers and
  89   /// expanded into multiple smaller registers than the value.
  90   struct VISIBILITY_HIDDEN RegsForValue {
  91     /// Regs - This list hold the register (for legal and promoted values)
  92     /// or register set (for expanded values) that the value should be assigned
  93     /// to.
  94     std::vector<unsigned> Regs;
  95
  96     /// RegVT - The value type of each register.
  97     ///
  98     MVT::ValueType RegVT;
  99
 100     /// ValueVT - The value type of the LLVM value, which may be promoted from
 101     /// RegVT or made from merging the two expanded parts.
 102     MVT::ValueType ValueVT;
 103
 104     RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {}
 105
 106     RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt)
 107       : RegVT(regvt), ValueVT(valuevt) {
 108         Regs.push_back(Reg);
 109     }
 110     RegsForValue(const std::vector<unsigned> &regs,
 111                  MVT::ValueType regvt, MVT::ValueType valuevt)
 112       : Regs(regs), RegVT(regvt), ValueVT(valuevt) {
 113     }
 114
 115     /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
 116     /// this value and returns the result as a ValueVT value.  This uses
 117     /// Chain/Flag as the input and updates them for the output Chain/Flag.
 118     SDOperand getCopyFromRegs(SelectionDAG &DAG,
 119                               SDOperand &Chain, SDOperand &Flag) const;
 120
 121     /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
 122     /// specified value into the registers specified by this object.  This uses
 123     /// Chain/Flag as the input and updates them for the output Chain/Flag.
 124     void getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
 125                        SDOperand &Chain, SDOperand &Flag,
 126                        MVT::ValueType PtrVT) const;
 127
 128     /// AddInlineAsmOperands - Add this value to the specified inlineasm node
 129     /// operand list.  This adds the code marker and includes the number of
 130     /// values added into it.
 131     void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
 132                               std::vector<SDOperand> &Ops) const;
 133   };
 134 }
 135
 136 namespace llvm {
 137   //===--------------------------------------------------------------------===//
 138   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 139   /// for the target.
 140   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 141                                       SelectionDAG *DAG,
 142                                       MachineBasicBlock *BB) {
 143     TargetLowering &TLI = IS->getTargetLowering();
 144
 145     if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
 146       return createTDListDAGScheduler(IS, DAG, BB);
 147     } else {
 148       assert(TLI.getSchedulingPreference() ==
 149            TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
 150       return createBURRListDAGScheduler(IS, DAG, BB);
 151     }
 152   }
 153
 154
 155   //===--------------------------------------------------------------------===//
 156   /// FunctionLoweringInfo - This contains information that is global to a
 157   /// function that is used when lowering a region of the function.
 158   class FunctionLoweringInfo {
 159   public:
 160     TargetLowering &TLI;
 161     Function &Fn;
 162     MachineFunction &MF;
 163     SSARegMap *RegMap;
 164
 165     FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
 166
 167     /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
 168     std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
 169
 170     /// ValueMap - Since we emit code for the function a basic block at a time,
 171     /// we must remember which virtual registers hold the values for
 172     /// cross-basic-block values.
 173     DenseMap<const Value*, unsigned> ValueMap;
 174
 175     /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
 176     /// the entry block.  This allows the allocas to be efficiently referenced
 177     /// anywhere in the function.
 178     std::map<const AllocaInst*, int> StaticAllocaMap;
 179
 180     unsigned MakeReg(MVT::ValueType VT) {
 181       return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
 182     }
 183
 184     /// isExportedInst - Return true if the specified value is an instruction
 185     /// exported from its block.
 186     bool isExportedInst(const Value *V) {
 187       return ValueMap.count(V);
 188     }
 189
 190     unsigned CreateRegForValue(const Value *V);
 191
 192     unsigned InitializeRegForValue(const Value *V) {
 193       unsigned &R = ValueMap[V];
 194       assert(R == 0 && "Already initialized this value register!");
 195       return R = CreateRegForValue(V);
 196     }
 197   };
 198 }
 199
 200 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
 201 /// PHI nodes or outside of the basic block that defines it, or used by a
 202 /// switch instruction, which may expand to multiple basic blocks.
 203 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
 204   if (isa<PHINode>(I)) return true;
 205   BasicBlock *BB = I->getParent();
 206   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
 207     if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
 208         // FIXME: Remove switchinst special case.
 209         isa<SwitchInst>(*UI))
 210       return true;
 211   return false;
 212 }
 213
 214 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
 215 /// entry block, return true.  This includes arguments used by switches, since
 216 /// the switch may expand into multiple basic blocks.
 217 static bool isOnlyUsedInEntryBlock(Argument *A) {
 218   BasicBlock *Entry = A->getParent()->begin();
 219   for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
 220     if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
 221       return false;  // Use not in entry block.
 222   return true;
 223 }
 224
 225 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
 226                                            Function &fn, MachineFunction &mf)
 227     : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
 228
 229   // Create a vreg for each argument register that is not dead and is used
 230   // outside of the entry block for the function.
 231   for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
 232        AI != E; ++AI)
 233     if (!isOnlyUsedInEntryBlock(AI))
 234       InitializeRegForValue(AI);
 235
 236   // Initialize the mapping of values to registers.  This is only set up for
 237   // instruction values that are used outside of the block that defines
 238   // them.
 239   Function::iterator BB = Fn.begin(), EB = Fn.end();
 240   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 241     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 242       if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
 243         const Type *Ty = AI->getAllocatedType();
 244         uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
 245         unsigned Align =
 246           std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
 247                    AI->getAlignment());
 248
 249         TySize *= CUI->getZExtValue();   // Get total allocated size.
 250         if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
 251         StaticAllocaMap[AI] =
 252           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
 253       }
 254
 255   for (; BB != EB; ++BB)
 256     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 257       if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
 258         if (!isa<AllocaInst>(I) ||
 259             !StaticAllocaMap.count(cast<AllocaInst>(I)))
 260           InitializeRegForValue(I);
 261
 262   // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
 263   // also creates the initial PHI MachineInstrs, though none of the input
 264   // operands are populated.
 265   for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
 266     MachineBasicBlock *MBB = new MachineBasicBlock(BB);
 267     MBBMap[BB] = MBB;
 268     MF.getBasicBlockList().push_back(MBB);
 269
 270     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
 271     // appropriate.
 272     PHINode *PN;
 273     for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
 274       if (PN->use_empty()) continue;
 275
 276       MVT::ValueType VT = TLI.getValueType(PN->getType());
 277       unsigned NumElements;
 278       if (VT != MVT::Vector)
 279         NumElements = TLI.getNumElements(VT);
 280       else {
 281         MVT::ValueType VT1,VT2;
 282         NumElements =
 283           TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
 284                                      VT1, VT2);
 285       }
 286       unsigned PHIReg = ValueMap[PN];
 287       assert(PHIReg && "PHI node does not have an assigned virtual register!");
 288       const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
 289       for (unsigned i = 0; i != NumElements; ++i)
 290         BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
 291     }
 292   }
 293 }
 294
 295 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
 296 /// the correctly promoted or expanded types.  Assign these registers
 297 /// consecutive vreg numbers and return the first assigned number.
 298 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
 299   MVT::ValueType VT = TLI.getValueType(V->getType());
 300
 301   // The number of multiples of registers that we need, to, e.g., split up
 302   // a <2 x int64> -> 4 x i32 registers.
 303   unsigned NumVectorRegs = 1;
 304
 305   // If this is a vector type, figure out what type it will decompose into
 306   // and how many of the elements it will use.
 307   if (VT == MVT::Vector) {
 308     const VectorType *PTy = cast<VectorType>(V->getType());
 309     unsigned NumElts = PTy->getNumElements();
 310     MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
 311
 312     // Divide the input until we get to a supported size.  This will always
 313     // end with a scalar if the target doesn't support vectors.
 314     while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) {
 315       NumElts >>= 1;
 316       NumVectorRegs <<= 1;
 317     }
 318     if (NumElts == 1)
 319       VT = EltTy;
 320     else
 321       VT = getVectorType(EltTy, NumElts);
 322   }
 323
 324   // The common case is that we will only create one register for this
 325   // value.  If we have that case, create and return the virtual register.
 326   unsigned NV = TLI.getNumElements(VT);
 327   if (NV == 1) {
 328     // If we are promoting this value, pick the next largest supported type.
 329     MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
 330     unsigned Reg = MakeReg(PromotedType);
 331     // If this is a vector of supported or promoted types (e.g. 4 x i16),
 332     // create all of the registers.
 333     for (unsigned i = 1; i != NumVectorRegs; ++i)
 334       MakeReg(PromotedType);
 335     return Reg;
 336   }
 337
 338   // If this value is represented with multiple target registers, make sure
 339   // to create enough consecutive registers of the right (smaller) type.
 340   VT = TLI.getTypeToExpandTo(VT);
 341   unsigned R = MakeReg(VT);
 342   for (unsigned i = 1; i != NV*NumVectorRegs; ++i)
 343     MakeReg(VT);
 344   return R;
 345 }
 346
 347 //===----------------------------------------------------------------------===//
 348 /// SelectionDAGLowering - This is the common target-independent lowering
 349 /// implementation that is parameterized by a TargetLowering object.
 350 /// Also, targets can overload any lowering method.
 351 ///
 352 namespace llvm {
 353 class SelectionDAGLowering {
 354   MachineBasicBlock *CurMBB;
 355
 356   DenseMap<const Value*, SDOperand> NodeMap;
 357
 358   /// PendingLoads - Loads are not emitted to the program immediately.  We bunch
 359   /// them up and then emit token factor nodes when possible.  This allows us to
 360   /// get simple disambiguation between loads without worrying about alias
 361   /// analysis.
 362   std::vector<SDOperand> PendingLoads;
 363
 364   /// Case - A struct to record the Value for a switch case, and the
 365   /// case's target basic block.
 366   struct Case {
 367     Constant* Low;
 368     Constant* High;
 369     MachineBasicBlock* BB;
 370
 371     Case() : Low(0), High(0), BB(0) { }
 372     Case(Constant* low, Constant* high, MachineBasicBlock* bb) :
 373       Low(low), High(high), BB(bb) { }
 374     uint64_t size() const {
 375       uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue();
 376       uint64_t rLow  = cast<ConstantInt>(Low)->getSExtValue();
 377       return (rHigh - rLow + 1ULL);
 378     }
 379   };
 380
 381   typedef std::vector<Case>           CaseVector;
 382   typedef CaseVector::iterator        CaseItr;
 383   typedef std::pair<CaseItr, CaseItr> CaseRange;
 384
 385   /// CaseRec - A struct with ctor used in lowering switches to a binary tree
 386   /// of conditional branches.
 387   struct CaseRec {
 388     CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) :
 389     CaseBB(bb), LT(lt), GE(ge), Range(r) {}
 390
 391     /// CaseBB - The MBB in which to emit the compare and branch
 392     MachineBasicBlock *CaseBB;
 393     /// LT, GE - If nonzero, we know the current case value must be less-than or
 394     /// greater-than-or-equal-to these Constants.
 395     Constant *LT;
 396     Constant *GE;
 397     /// Range - A pair of iterators representing the range of case values to be
 398     /// processed at this point in the binary search tree.
 399     CaseRange Range;
 400   };
 401
 402   typedef std::vector<CaseRec> CaseRecVector;
 403
 404   /// The comparison function for sorting the switch case values in the vector.
 405   /// WARNING: Case ranges should be disjoint!
 406   struct CaseCmp {
 407     bool operator () (const Case& C1,
 408                       const Case& C2) {
 409
 410       assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
 411       const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
 412       const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
 413       return CI1->getValue().slt(CI2->getValue());
 414     }
 415   };
 416
 417   unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI);
 418
 419 public:
 420   // TLI - This is information that describes the available target features we
 421   // need for lowering.  This indicates when operations are unavailable,
 422   // implemented with a libcall, etc.
 423   TargetLowering &TLI;
 424   SelectionDAG &DAG;
 425   const TargetData *TD;
 426
 427   /// SwitchCases - Vector of CaseBlock structures used to communicate
 428   /// SwitchInst code generation information.
 429   std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
 430   /// JTCases - Vector of JumpTable structures used to communicate
 431   /// SwitchInst code generation information.
 432   std::vector<SelectionDAGISel::JumpTableBlock> JTCases;
 433
 434   /// FuncInfo - Information about the function as a whole.
 435   ///
 436   FunctionLoweringInfo &FuncInfo;
 437
 438   SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
 439                        FunctionLoweringInfo &funcinfo)
 440     : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
 441       FuncInfo(funcinfo) {
 442   }
 443
 444   /// getRoot - Return the current virtual root of the Selection DAG.
 445   ///
 446   SDOperand getRoot() {
 447     if (PendingLoads.empty())
 448       return DAG.getRoot();
 449
 450     if (PendingLoads.size() == 1) {
 451       SDOperand Root = PendingLoads[0];
 452       DAG.setRoot(Root);
 453       PendingLoads.clear();
 454       return Root;
 455     }
 456
 457     // Otherwise, we have to make a token factor node.
 458     SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
 459                                  &PendingLoads[0], PendingLoads.size());
 460     PendingLoads.clear();
 461     DAG.setRoot(Root);
 462     return Root;
 463   }
 464
 465   SDOperand CopyValueToVirtualRegister(Value *V, unsigned Reg);
 466
 467   void visit(Instruction &I) { visit(I.getOpcode(), I); }
 468
 469   void visit(unsigned Opcode, User &I) {
 470     // Note: this doesn't use InstVisitor, because it has to work with
 471     // ConstantExpr's in addition to instructions.
 472     switch (Opcode) {
 473     default: assert(0 && "Unknown instruction type encountered!");
 474              abort();
 475       // Build the switch statement using the Instruction.def file.
 476 #define HANDLE_INST(NUM, OPCODE, CLASS) \
 477     case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
 478 #include "llvm/Instruction.def"
 479     }
 480   }
 481
 482   void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
 483
 484   SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr,
 485                         const Value *SV, SDOperand Root,
 486                         bool isVolatile);
 487
 488   SDOperand getIntPtrConstant(uint64_t Val) {
 489     return DAG.getConstant(Val, TLI.getPointerTy());
 490   }
 491
 492   SDOperand getValue(const Value *V);
 493
 494   void setValue(const Value *V, SDOperand NewN) {
 495     SDOperand &N = NodeMap[V];
 496     assert(N.Val == 0 && "Already set a value for this node!");
 497     N = NewN;
 498   }
 499
 500   RegsForValue GetRegistersForValue(const std::string &ConstrCode,
 501                                     MVT::ValueType VT,
 502                                     bool OutReg, bool InReg,
 503                                     std::set<unsigned> &OutputRegs,
 504                                     std::set<unsigned> &InputRegs);
 505
 506   void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
 507                             MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
 508                             unsigned Opc);
 509   bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
 510   void ExportFromCurrentBlock(Value *V);
 511   void LowerCallTo(Instruction &I,
 512                    const Type *CalledValueTy, unsigned CallingConv,
 513                    bool IsTailCall, SDOperand Callee, unsigned OpIdx);
 514
 515   // Terminator instructions.
 516   void visitRet(ReturnInst &I);
 517   void visitBr(BranchInst &I);
 518   void visitSwitch(SwitchInst &I);
 519   void visitUnreachable(UnreachableInst &I) { /* noop */ }
 520
 521   // Helpers for visitSwitch
 522   bool handleSmallSwitchRange(CaseRec& CR,
 523                               CaseRecVector& WorkList,
 524                               Value* SV,
 525                               MachineBasicBlock* Default);
 526   bool handleJTSwitchCase(CaseRec& CR,
 527                           CaseRecVector& WorkList,
 528                           Value* SV,
 529                           MachineBasicBlock* Default);
 530   bool handleBTSplitSwitchCase(CaseRec& CR,
 531                                CaseRecVector& WorkList,
 532                                Value* SV,
 533                                MachineBasicBlock* Default);
 534   void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
 535   void visitJumpTable(SelectionDAGISel::JumpTable &JT);
 536   void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
 537                             SelectionDAGISel::JumpTableHeader &JTH);
 538
 539   // These all get lowered before this pass.
 540   void visitInvoke(InvokeInst &I);
 541   void visitInvoke(InvokeInst &I, bool AsTerminator);
 542   void visitUnwind(UnwindInst &I);
 543
 544   void visitScalarBinary(User &I, unsigned OpCode);
 545   void visitVectorBinary(User &I, unsigned OpCode);
 546   void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp);
 547   void visitShift(User &I, unsigned Opcode);
 548   void visitAdd(User &I) {
 549     if (isa<VectorType>(I.getType()))
 550       visitVectorBinary(I, ISD::VADD);
 551     else if (I.getType()->isFloatingPoint())
 552       visitScalarBinary(I, ISD::FADD);
 553     else
 554       visitScalarBinary(I, ISD::ADD);
 555   }
 556   void visitSub(User &I);
 557   void visitMul(User &I) {
 558     if (isa<VectorType>(I.getType()))
 559       visitVectorBinary(I, ISD::VMUL);
 560     else if (I.getType()->isFloatingPoint())
 561       visitScalarBinary(I, ISD::FMUL);
 562     else
 563       visitScalarBinary(I, ISD::MUL);
 564   }
 565   void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); }
 566   void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); }
 567   void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); }
 568   void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); }
 569   void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); }
 570   void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); }
 571   void visitAnd (User &I) { visitEitherBinary(I, ISD::AND,  ISD::VAND ); }
 572   void visitOr  (User &I) { visitEitherBinary(I, ISD::OR,   ISD::VOR  ); }
 573   void visitXor (User &I) { visitEitherBinary(I, ISD::XOR,  ISD::VXOR ); }
 574   void visitShl (User &I) { visitShift(I, ISD::SHL); }
 575   void visitLShr(User &I) { visitShift(I, ISD::SRL); }
 576   void visitAShr(User &I) { visitShift(I, ISD::SRA); }
 577   void visitICmp(User &I);
 578   void visitFCmp(User &I);
 579   // Visit the conversion instructions
 580   void visitTrunc(User &I);
 581   void visitZExt(User &I);
 582   void visitSExt(User &I);
 583   void visitFPTrunc(User &I);
 584   void visitFPExt(User &I);
 585   void visitFPToUI(User &I);
 586   void visitFPToSI(User &I);
 587   void visitUIToFP(User &I);
 588   void visitSIToFP(User &I);
 589   void visitPtrToInt(User &I);
 590   void visitIntToPtr(User &I);
 591   void visitBitCast(User &I);
 592
 593   void visitExtractElement(User &I);
 594   void visitInsertElement(User &I);
 595   void visitShuffleVector(User &I);
 596
 597   void visitGetElementPtr(User &I);
 598   void visitSelect(User &I);
 599
 600   void visitMalloc(MallocInst &I);
 601   void visitFree(FreeInst &I);
 602   void visitAlloca(AllocaInst &I);
 603   void visitLoad(LoadInst &I);
 604   void visitStore(StoreInst &I);
 605   void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
 606   void visitCall(CallInst &I);
 607   void visitInlineAsm(CallInst &I);
 608   const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
 609   void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
 610
 611   void visitVAStart(CallInst &I);
 612   void visitVAArg(VAArgInst &I);
 613   void visitVAEnd(CallInst &I);
 614   void visitVACopy(CallInst &I);
 615
 616   void visitMemIntrinsic(CallInst &I, unsigned Op);
 617
 618   void visitUserOp1(Instruction &I) {
 619     assert(0 && "UserOp1 should not exist at instruction selection time!");
 620     abort();
 621   }
 622   void visitUserOp2(Instruction &I) {
 623     assert(0 && "UserOp2 should not exist at instruction selection time!");
 624     abort();
 625   }
 626 };
 627 } // end namespace llvm
 628
 629 SDOperand SelectionDAGLowering::getValue(const Value *V) {
 630   SDOperand &N = NodeMap[V];
 631   if (N.Val) return N;
 632
 633   const Type *VTy = V->getType();
 634   MVT::ValueType VT = TLI.getValueType(VTy);
 635   if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
 636     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 637       visit(CE->getOpcode(), *CE);
 638       SDOperand N1 = NodeMap[V];
 639       assert(N1.Val && "visit didn't populate the ValueMap!");
 640       return N1;
 641     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
 642       return N = DAG.getGlobalAddress(GV, VT);
 643     } else if (isa<ConstantPointerNull>(C)) {
 644       return N = DAG.getConstant(0, TLI.getPointerTy());
 645     } else if (isa<UndefValue>(C)) {
 646       if (!isa<VectorType>(VTy))
 647         return N = DAG.getNode(ISD::UNDEF, VT);
 648
 649       // Create a VBUILD_VECTOR of undef nodes.
 650       const VectorType *PTy = cast<VectorType>(VTy);
 651       unsigned NumElements = PTy->getNumElements();
 652       MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
 653
 654       SmallVector<SDOperand, 8> Ops;
 655       Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT));
 656
 657       // Create a VConstant node with generic Vector type.
 658       Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
 659       Ops.push_back(DAG.getValueType(PVT));
 660       return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
 661                              &Ops[0], Ops.size());
 662     } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 663       return N = DAG.getConstantFP(CFP->getValue(), VT);
 664     } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) {
 665       unsigned NumElements = PTy->getNumElements();
 666       MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
 667
 668       // Now that we know the number and type of the elements, push a
 669       // Constant or ConstantFP node onto the ops list for each element of
 670       // the packed constant.
 671       SmallVector<SDOperand, 8> Ops;
 672       if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
 673         for (unsigned i = 0; i != NumElements; ++i)
 674           Ops.push_back(getValue(CP->getOperand(i)));
 675       } else {
 676         assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
 677         SDOperand Op;
 678         if (MVT::isFloatingPoint(PVT))
 679           Op = DAG.getConstantFP(0, PVT);
 680         else
 681           Op = DAG.getConstant(0, PVT);
 682         Ops.assign(NumElements, Op);
 683       }
 684
 685       // Create a VBUILD_VECTOR node with generic Vector type.
 686       Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
 687       Ops.push_back(DAG.getValueType(PVT));
 688       return NodeMap[V] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0],
 689                                       Ops.size());
 690     } else {
 691       // Canonicalize all constant ints to be unsigned.
 692       return N = DAG.getConstant(cast<ConstantInt>(C)->getZExtValue(),VT);
 693     }
 694   }
 695
 696   if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 697     std::map<const AllocaInst*, int>::iterator SI =
 698     FuncInfo.StaticAllocaMap.find(AI);
 699     if (SI != FuncInfo.StaticAllocaMap.end())
 700       return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
 701   }
 702
 703   unsigned InReg = FuncInfo.ValueMap[V];
 704   assert(InReg && "Value not in map!");
 705
 706   // If this type is not legal, make it so now.
 707   if (VT != MVT::Vector) {
 708     if (TLI.getTypeAction(VT) == TargetLowering::Expand) {
 709       // Source must be expanded.  This input value is actually coming from the
 710       // register pair InReg and InReg+1.
 711       MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
 712       unsigned NumVals = TLI.getNumElements(VT);
 713       N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
 714       if (NumVals == 1)
 715         N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
 716       else {
 717         assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
 718         N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
 719                        DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
 720       }
 721     } else {
 722       MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
 723       N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
 724       if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case
 725         N = MVT::isFloatingPoint(VT)
 726           ? DAG.getNode(ISD::FP_ROUND, VT, N)
 727           : DAG.getNode(ISD::TRUNCATE, VT, N);
 728     }
 729   } else {
 730     // Otherwise, if this is a vector, make it available as a generic vector
 731     // here.
 732     MVT::ValueType PTyElementVT, PTyLegalElementVT;
 733     const VectorType *PTy = cast<VectorType>(VTy);
 734     unsigned NE = TLI.getVectorTypeBreakdown(PTy, PTyElementVT,
 735                                              PTyLegalElementVT);
 736
 737     // Build a VBUILD_VECTOR with the input registers.
 738     SmallVector<SDOperand, 8> Ops;
 739     if (PTyElementVT == PTyLegalElementVT) {
 740       // If the value types are legal, just VBUILD the CopyFromReg nodes.
 741       for (unsigned i = 0; i != NE; ++i)
 742         Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
 743                                          PTyElementVT));
 744     } else if (PTyElementVT < PTyLegalElementVT) {
 745       // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate.
 746       for (unsigned i = 0; i != NE; ++i) {
 747         SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
 748                                           PTyElementVT);
 749         if (MVT::isFloatingPoint(PTyElementVT))
 750           Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
 751         else
 752           Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op);
 753         Ops.push_back(Op);
 754       }
 755     } else {
 756       // If the register was expanded, use BUILD_PAIR.
 757       assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!");
 758       for (unsigned i = 0; i != NE/2; ++i) {
 759         SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
 760                                            PTyElementVT);
 761         SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
 762                                            PTyElementVT);
 763         Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1));
 764       }
 765     }
 766
 767     Ops.push_back(DAG.getConstant(NE, MVT::i32));
 768     Ops.push_back(DAG.getValueType(PTyLegalElementVT));
 769     N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
 770
 771     // Finally, use a VBIT_CONVERT to make this available as the appropriate
 772     // vector type.
 773     N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
 774                     DAG.getConstant(PTy->getNumElements(),
 775                                     MVT::i32),
 776                     DAG.getValueType(TLI.getValueType(PTy->getElementType())));
 777   }
 778
 779   return N;
 780 }
 781
 782
 783 void SelectionDAGLowering::visitRet(ReturnInst &I) {
 784   if (I.getNumOperands() == 0) {
 785     DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
 786     return;
 787   }
 788   SmallVector<SDOperand, 8> NewValues;
 789   NewValues.push_back(getRoot());
 790   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 791     SDOperand RetOp = getValue(I.getOperand(i));
 792
 793     // If this is an integer return value, we need to promote it ourselves to
 794     // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
 795     // than sign/zero.
 796     // FIXME: C calling convention requires the return type to be promoted to
 797     // at least 32-bit. But this is not necessary for non-C calling conventions.
 798     if (MVT::isInteger(RetOp.getValueType()) &&
 799         RetOp.getValueType() < MVT::i64) {
 800       MVT::ValueType TmpVT;
 801       if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
 802         TmpVT = TLI.getTypeToTransformTo(MVT::i32);
 803       else
 804         TmpVT = MVT::i32;
 805       const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
 806       const ParamAttrsList *Attrs = FTy->getParamAttrs();
 807       ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
 808       if (Attrs && Attrs->paramHasAttr(0, SExtAttribute))
 809         ExtendKind = ISD::SIGN_EXTEND;
 810       if (Attrs && Attrs->paramHasAttr(0, ZExtAttribute))
 811         ExtendKind = ISD::ZERO_EXTEND;
 812       RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
 813     }
 814     NewValues.push_back(RetOp);
 815     NewValues.push_back(DAG.getConstant(false, MVT::i32));
 816   }
 817   DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
 818                           &NewValues[0], NewValues.size()));
 819 }
 820
 821 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
 822 /// the current basic block, add it to ValueMap now so that we'll get a
 823 /// CopyTo/FromReg.
 824 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
 825   // No need to export constants.
 826   if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
 827
 828   // Already exported?
 829   if (FuncInfo.isExportedInst(V)) return;
 830
 831   unsigned Reg = FuncInfo.InitializeRegForValue(V);
 832   PendingLoads.push_back(CopyValueToVirtualRegister(V, Reg));
 833 }
 834
 835 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
 836                                                     const BasicBlock *FromBB) {
 837   // The operands of the setcc have to be in this block.  We don't know
 838   // how to export them from some other block.
 839   if (Instruction *VI = dyn_cast<Instruction>(V)) {
 840     // Can export from current BB.
 841     if (VI->getParent() == FromBB)
 842       return true;
 843
 844     // Is already exported, noop.
 845     return FuncInfo.isExportedInst(V);
 846   }
 847
 848   // If this is an argument, we can export it if the BB is the entry block or
 849   // if it is already exported.
 850   if (isa<Argument>(V)) {
 851     if (FromBB == &FromBB->getParent()->getEntryBlock())
 852       return true;
 853
 854     // Otherwise, can only export this if it is already exported.
 855     return FuncInfo.isExportedInst(V);
 856   }
 857
 858   // Otherwise, constants can always be exported.
 859   return true;
 860 }
 861
 862 static bool InBlock(const Value *V, const BasicBlock *BB) {
 863   if (const Instruction *I = dyn_cast<Instruction>(V))
 864     return I->getParent() == BB;
 865   return true;
 866 }
 867
 868 /// FindMergedConditions - If Cond is an expression like
 869 void SelectionDAGLowering::FindMergedConditions(Value *Cond,
 870                                                 MachineBasicBlock *TBB,
 871                                                 MachineBasicBlock *FBB,
 872                                                 MachineBasicBlock *CurBB,
 873                                                 unsigned Opc) {
 874   // If this node is not part of the or/and tree, emit it as a branch.
 875   Instruction *BOp = dyn_cast<Instruction>(Cond);
 876
 877   if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
 878       (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
 879       BOp->getParent() != CurBB->getBasicBlock() ||
 880       !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
 881       !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
 882     const BasicBlock *BB = CurBB->getBasicBlock();
 883
 884     // If the leaf of the tree is a comparison, merge the condition into
 885     // the caseblock.
 886     if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) &&
 887         // The operands of the cmp have to be in this block.  We don't know
 888         // how to export them from some other block.  If this is the first block
 889         // of the sequence, no exporting is needed.
 890         (CurBB == CurMBB ||
 891          (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
 892           isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) {
 893       BOp = cast<Instruction>(Cond);
 894       ISD::CondCode Condition;
 895       if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
 896         switch (IC->getPredicate()) {
 897         default: assert(0 && "Unknown icmp predicate opcode!");
 898         case ICmpInst::ICMP_EQ:  Condition = ISD::SETEQ;  break;
 899         case ICmpInst::ICMP_NE:  Condition = ISD::SETNE;  break;
 900         case ICmpInst::ICMP_SLE: Condition = ISD::SETLE;  break;
 901         case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break;
 902         case ICmpInst::ICMP_SGE: Condition = ISD::SETGE;  break;
 903         case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break;
 904         case ICmpInst::ICMP_SLT: Condition = ISD::SETLT;  break;
 905         case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break;
 906         case ICmpInst::ICMP_SGT: Condition = ISD::SETGT;  break;
 907         case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break;
 908         }
 909       } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
 910         ISD::CondCode FPC, FOC;
 911         switch (FC->getPredicate()) {
 912         default: assert(0 && "Unknown fcmp predicate opcode!");
 913         case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
 914         case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
 915         case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
 916         case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
 917         case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
 918         case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
 919         case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
 920         case FCmpInst::FCMP_ORD:   FOC = ISD::SETEQ; FPC = ISD::SETO;   break;
 921         case FCmpInst::FCMP_UNO:   FOC = ISD::SETNE; FPC = ISD::SETUO;  break;
 922         case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
 923         case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
 924         case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
 925         case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
 926         case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
 927         case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
 928         case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
 929         }
 930         if (FiniteOnlyFPMath())
 931           Condition = FOC;
 932         else
 933           Condition = FPC;
 934       } else {
 935         Condition = ISD::SETEQ; // silence warning.
 936         assert(0 && "Unknown compare instruction");
 937       }
 938
 939       SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
 940                                      BOp->getOperand(1), NULL, TBB, FBB, CurBB);
 941       SwitchCases.push_back(CB);
 942       return;
 943     }
 944
 945     // Create a CaseBlock record representing this branch.
 946     SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
 947                                    NULL, TBB, FBB, CurBB);
 948     SwitchCases.push_back(CB);
 949     return;
 950   }
 951
 952
 953   //  Create TmpBB after CurBB.
 954   MachineFunction::iterator BBI = CurBB;
 955   MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock());
 956   CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB);
 957
 958   if (Opc == Instruction::Or) {
 959     // Codegen X | Y as:
 960     //   jmp_if_X TBB
 961     //   jmp TmpBB
 962     // TmpBB:
 963     //   jmp_if_Y TBB
 964     //   jmp FBB
 965     //
 966
 967     // Emit the LHS condition.
 968     FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc);
 969
 970     // Emit the RHS condition into TmpBB.
 971     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
 972   } else {
 973     assert(Opc == Instruction::And && "Unknown merge op!");
 974     // Codegen X & Y as:
 975     //   jmp_if_X TmpBB
 976     //   jmp FBB
 977     // TmpBB:
 978     //   jmp_if_Y TBB
 979     //   jmp FBB
 980     //
 981     //  This requires creation of TmpBB after CurBB.
 982
 983     // Emit the LHS condition.
 984     FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc);
 985
 986     // Emit the RHS condition into TmpBB.
 987     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
 988   }
 989 }
 990
 991 /// If the set of cases should be emitted as a series of branches, return true.
 992 /// If we should emit this as a bunch of and/or'd together conditions, return
 993 /// false.
 994 static bool
 995 ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) {
 996   if (Cases.size() != 2) return true;
 997
 998   // If this is two comparisons of the same values or'd or and'd together, they
 999   // will get folded into a single comparison, so don't emit two blocks.
1000   if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
1001        Cases[0].CmpRHS == Cases[1].CmpRHS) ||
1002       (Cases[0].CmpRHS == Cases[1].CmpLHS &&
1003        Cases[0].CmpLHS == Cases[1].CmpRHS)) {
1004     return false;
1005   }
1006
1007   return true;
1008 }
1009
1010 void SelectionDAGLowering::visitBr(BranchInst &I) {
1011   // Update machine-CFG edges.
1012   MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
1013
1014   // Figure out which block is immediately after the current one.
1015   MachineBasicBlock *NextBlock = 0;
1016   MachineFunction::iterator BBI = CurMBB;
1017   if (++BBI != CurMBB->getParent()->end())
1018     NextBlock = BBI;
1019
1020   if (I.isUnconditional()) {
1021     // If this is not a fall-through branch, emit the branch.
1022     if (Succ0MBB != NextBlock)
1023       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1024                               DAG.getBasicBlock(Succ0MBB)));
1025
1026     // Update machine-CFG edges.
1027     CurMBB->addSuccessor(Succ0MBB);
1028
1029     return;
1030   }
1031
1032   // If this condition is one of the special cases we handle, do special stuff
1033   // now.
1034   Value *CondVal = I.getCondition();
1035   MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1036
1037   // If this is a series of conditions that are or'd or and'd together, emit
1038   // this as a sequence of branches instead of setcc's with and/or operations.
1039   // For example, instead of something like:
1040   //     cmp A, B
1041   //     C = seteq
1042   //     cmp D, E
1043   //     F = setle
1044   //     or C, F
1045   //     jnz foo
1046   // Emit:
1047   //     cmp A, B
1048   //     je foo
1049   //     cmp D, E
1050   //     jle foo
1051   //
1052   if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1053     if (BOp->hasOneUse() &&
1054         (BOp->getOpcode() == Instruction::And ||
1055          BOp->getOpcode() == Instruction::Or)) {
1056       FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode());
1057       // If the compares in later blocks need to use values not currently
1058       // exported from this block, export them now.  This block should always
1059       // be the first entry.
1060       assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!");
1061
1062       // Allow some cases to be rejected.
1063       if (ShouldEmitAsBranches(SwitchCases)) {
1064         for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1065           ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1066           ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1067         }
1068
1069         // Emit the branch for this block.
1070         visitSwitchCase(SwitchCases[0]);
1071         SwitchCases.erase(SwitchCases.begin());
1072         return;
1073       }
1074
1075       // Okay, we decided not to do this, remove any inserted MBB's and clear
1076       // SwitchCases.
1077       for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1078         CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB);
1079
1080       SwitchCases.clear();
1081     }
1082   }
1083
1084   // Create a CaseBlock record representing this branch.
1085   SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
1086                                  NULL, Succ0MBB, Succ1MBB, CurMBB);
1087   // Use visitSwitchCase to actually insert the fast branch sequence for this
1088   // cond branch.
1089   visitSwitchCase(CB);
1090 }
1091
1092 /// visitSwitchCase - Emits the necessary code to represent a single node in
1093 /// the binary search tree resulting from lowering a switch instruction.
1094 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
1095   SDOperand Cond;
1096   SDOperand CondLHS = getValue(CB.CmpLHS);
1097
1098   // Build the setcc now.
1099   if (CB.CmpMHS == NULL) {
1100     // Fold "(X == true)" to X and "(X == false)" to !X to
1101     // handle common cases produced by branch lowering.
1102     if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
1103       Cond = CondLHS;
1104     else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
1105       SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
1106       Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
1107     } else
1108       Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1109   } else {
1110     assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
1111
1112     uint64_t Low = cast<ConstantInt>(CB.CmpLHS)->getSExtValue();
1113     uint64_t High  = cast<ConstantInt>(CB.CmpRHS)->getSExtValue();
1114
1115     SDOperand CmpOp = getValue(CB.CmpMHS);
1116     MVT::ValueType VT = CmpOp.getValueType();
1117
1118     if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
1119       Cond = DAG.getSetCC(MVT::i1, CmpOp, DAG.getConstant(High, VT), ISD::SETLE);
1120     } else {
1121       SDOperand SUB = DAG.getNode(ISD::SUB, VT, CmpOp, DAG.getConstant(Low, VT));
1122       Cond = DAG.getSetCC(MVT::i1, SUB,
1123                           DAG.getConstant(High-Low, VT), ISD::SETULE);
1124     }
1125
1126   }
1127
1128   // Set NextBlock to be the MBB immediately after the current one, if any.
1129   // This is used to avoid emitting unnecessary branches to the next block.
1130   MachineBasicBlock *NextBlock = 0;
1131   MachineFunction::iterator BBI = CurMBB;
1132   if (++BBI != CurMBB->getParent()->end())
1133     NextBlock = BBI;
1134
1135   // If the lhs block is the next block, invert the condition so that we can
1136   // fall through to the lhs instead of the rhs block.
1137   if (CB.TrueBB == NextBlock) {
1138     std::swap(CB.TrueBB, CB.FalseBB);
1139     SDOperand True = DAG.getConstant(1, Cond.getValueType());
1140     Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
1141   }
1142   SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond,
1143                                  DAG.getBasicBlock(CB.TrueBB));
1144   if (CB.FalseBB == NextBlock)
1145     DAG.setRoot(BrCond);
1146   else
1147     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1148                             DAG.getBasicBlock(CB.FalseBB)));
1149   // Update successor info
1150   CurMBB->addSuccessor(CB.TrueBB);
1151   CurMBB->addSuccessor(CB.FalseBB);
1152 }
1153
1154 /// visitJumpTable - Emit JumpTable node in the current MBB
1155 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
1156   // Emit the code for the jump table
1157   assert(JT.Reg != -1UL && "Should lower JT Header first!");
1158   MVT::ValueType PTy = TLI.getPointerTy();
1159   SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
1160   SDOperand Table = DAG.getJumpTable(JT.JTI, PTy);
1161   DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1),
1162                           Table, Index));
1163   return;
1164 }
1165
1166 /// visitJumpTableHeader - This function emits necessary code to produce index
1167 /// in the JumpTable from switch case.
1168 void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
1169                                          SelectionDAGISel::JumpTableHeader &JTH) {
1170   // Subtract the lowest switch case value from the value being switched on
1171   // and conditional branch to default mbb if the result is greater than the
1172   // difference between smallest and largest cases.
1173   SDOperand SwitchOp = getValue(JTH.SValue);
1174   MVT::ValueType VT = SwitchOp.getValueType();
1175   SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1176                               DAG.getConstant(JTH.First, VT));
1177
1178   // The SDNode we just created, which holds the value being switched on
1179   // minus the the smallest case value, needs to be copied to a virtual
1180   // register so it can be used as an index into the jump table in a
1181   // subsequent basic block.  This value may be smaller or larger than the
1182   // target's pointer type, and therefore require extension or truncating.
1183   if (VT > TLI.getPointerTy())
1184     SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
1185   else
1186     SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
1187
1188   unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
1189   SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
1190   JT.Reg = JumpTableReg;
1191
1192   // Emit the range check for the jump table, and branch to the default
1193   // block for the switch statement if the value being switched on exceeds
1194   // the largest case in the switch.
1195   SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
1196                                DAG.getConstant(JTH.Last-JTH.First,VT),
1197                                ISD::SETUGT);
1198
1199   // Set NextBlock to be the MBB immediately after the current one, if any.
1200   // This is used to avoid emitting unnecessary branches to the next block.
1201   MachineBasicBlock *NextBlock = 0;
1202   MachineFunction::iterator BBI = CurMBB;
1203   if (++BBI != CurMBB->getParent()->end())
1204     NextBlock = BBI;
1205
1206   SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
1207                                  DAG.getBasicBlock(JT.Default));
1208
1209   if (JT.MBB == NextBlock)
1210     DAG.setRoot(BrCond);
1211   else
1212     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1213                             DAG.getBasicBlock(JT.MBB)));
1214 }
1215
1216
1217 void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
1218   assert(0 && "Should never be visited directly");
1219 }
1220 void SelectionDAGLowering::visitInvoke(InvokeInst &I, bool AsTerminator) {
1221   // Retrieve successors.
1222   MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1223   MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1224
1225   if (!AsTerminator) {
1226     // Mark landing pad so that it doesn't get deleted in branch folding.
1227     LandingPad->setIsLandingPad();
1228
1229     // Insert a label before the invoke call to mark the try range.
1230     // This can be used to detect deletion of the invoke via the
1231     // MachineModuleInfo.
1232     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
1233     unsigned BeginLabel = MMI->NextLabelID();
1234     DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1235                             DAG.getConstant(BeginLabel, MVT::i32)));
1236
1237     LowerCallTo(I, I.getCalledValue()->getType(),
1238                    I.getCallingConv(),
1239                    false,
1240                    getValue(I.getOperand(0)),
1241                    3);
1242
1243     // Insert a label before the invoke call to mark the try range.
1244     // This can be used to detect deletion of the invoke via the
1245     // MachineModuleInfo.
1246     unsigned EndLabel = MMI->NextLabelID();
1247     DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1248                             DAG.getConstant(EndLabel, MVT::i32)));
1249
1250     // Inform MachineModuleInfo of range.
1251     MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
1252
1253     // Update successor info
1254     CurMBB->addSuccessor(Return);
1255     CurMBB->addSuccessor(LandingPad);
1256   } else {
1257     // Drop into normal successor.
1258     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1259                             DAG.getBasicBlock(Return)));
1260   }
1261 }
1262
1263 void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
1264 }
1265
1266 /// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for
1267 /// small case ranges).
1268 bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
1269                                                   CaseRecVector& WorkList,
1270                                                   Value* SV,
1271                                                   MachineBasicBlock* Default) {
1272   Case& BackCase  = *(CR.Range.second-1);
1273
1274   // Size is the number of Cases represented by this range.
1275   unsigned Size = CR.Range.second - CR.Range.first;
1276   if (Size >=3)
1277     return false;
1278
1279   // Get the MachineFunction which holds the current MBB.  This is used when
1280   // inserting any additional MBBs necessary to represent the switch.
1281   MachineFunction *CurMF = CurMBB->getParent();
1282
1283   // Figure out which block is immediately after the current one.
1284   MachineBasicBlock *NextBlock = 0;
1285   MachineFunction::iterator BBI = CR.CaseBB;
1286
1287   if (++BBI != CurMBB->getParent()->end())
1288     NextBlock = BBI;
1289
1290   // TODO: If any two of the cases has the same destination, and if one value
1291   // is the same as the other, but has one bit unset that the other has set,
1292   // use bit manipulation to do two compares at once.  For example:
1293   // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
1294
1295   // Rearrange the case blocks so that the last one falls through if possible.
1296   if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) {
1297     // The last case block won't fall through into 'NextBlock' if we emit the
1298     // branches in this order.  See if rearranging a case value would help.
1299     for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
1300       if (I->BB == NextBlock) {
1301         std::swap(*I, BackCase);
1302         break;
1303       }
1304     }
1305   }
1306
1307   // Create a CaseBlock record representing a conditional branch to
1308   // the Case's target mbb if the value being switched on SV is equal
1309   // to C.
1310   MachineBasicBlock *CurBlock = CR.CaseBB;
1311   for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
1312     MachineBasicBlock *FallThrough;
1313     if (I != E-1) {
1314       FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock());
1315       CurMF->getBasicBlockList().insert(BBI, FallThrough);
1316     } else {
1317       // If the last case doesn't match, go to the default block.
1318       FallThrough = Default;
1319     }
1320
1321     Value *RHS, *LHS, *MHS;
1322     ISD::CondCode CC;
1323     if (I->High == I->Low) {
1324       // This is just small small case range :) containing exactly 1 case
1325       CC = ISD::SETEQ;
1326       LHS = SV; RHS = I->High; MHS = NULL;
1327     } else {
1328       CC = ISD::SETLE;
1329       LHS = I->Low; MHS = SV; RHS = I->High;
1330     }
1331     SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS,
1332                                    I->BB, FallThrough, CurBlock);
1333
1334     // If emitting the first comparison, just call visitSwitchCase to emit the
1335     // code into the current block.  Otherwise, push the CaseBlock onto the
1336     // vector to be later processed by SDISel, and insert the node's MBB
1337     // before the next MBB.
1338     if (CurBlock == CurMBB)
1339       visitSwitchCase(CB);
1340     else
1341       SwitchCases.push_back(CB);
1342
1343     CurBlock = FallThrough;
1344   }
1345
1346   return true;
1347 }
1348
1349 /// handleJTSwitchCase - Emit jumptable for current switch case range
1350 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
1351                                               CaseRecVector& WorkList,
1352                                               Value* SV,
1353                                               MachineBasicBlock* Default) {
1354   Case& FrontCase = *CR.Range.first;
1355   Case& BackCase  = *(CR.Range.second-1);
1356
1357   // Size is the number of Cases represented by this range.
1358   unsigned Size = CR.Range.second - CR.Range.first;
1359
1360   int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
1361   int64_t Last  = cast<ConstantInt>(BackCase.High)->getSExtValue();
1362
1363   uint64_t TSize = 0;
1364   for (CaseItr I = CR.Range.first, E = CR.Range.second;
1365        I!=E; ++I)
1366     TSize += I->size();
1367
1368   if ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
1369        !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
1370       Size <= 5)
1371     return false;
1372
1373   double Density = (double)TSize / (double)((Last - First) + 1ULL);
1374   if (Density < 0.4)
1375     return false;
1376
1377   DOUT << "Lowering jump table\n"
1378        << "First entry: " << First << ". Last entry: " << Last << "\n"
1379        << "Size: " << TSize << ". Density: " << Density << "\n";
1380
1381   // Get the MachineFunction which holds the current MBB.  This is used when
1382   // inserting any additional MBBs necessary to represent the switch.
1383   MachineFunction *CurMF = CurMBB->getParent();
1384
1385   // Figure out which block is immediately after the current one.
1386   MachineBasicBlock *NextBlock = 0;
1387   MachineFunction::iterator BBI = CR.CaseBB;
1388
1389   if (++BBI != CurMBB->getParent()->end())
1390     NextBlock = BBI;
1391
1392   const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1393
1394   // Create a new basic block to hold the code for loading the address
1395   // of the jump table, and jumping to it.  Update successor information;
1396   // we will either branch to the default case for the switch, or the jump
1397   // table.
1398   MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
1399   CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
1400   CR.CaseBB->addSuccessor(Default);
1401   CR.CaseBB->addSuccessor(JumpTableBB);
1402
1403   // Build a vector of destination BBs, corresponding to each target
1404   // of the jump table.  If the value of the jump table slot corresponds to
1405   // a case statement, push the case's BB onto the vector, otherwise, push
1406   // the default BB.
1407   std::vector<MachineBasicBlock*> DestBBs;
1408   int64_t TEI = First;
1409   for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) {
1410     int64_t Low = cast<ConstantInt>(I->Low)->getSExtValue();
1411     int64_t High = cast<ConstantInt>(I->High)->getSExtValue();
1412
1413     if ((Low <= TEI) && (TEI <= High)) {
1414       DestBBs.push_back(I->BB);
1415       if (TEI==High)
1416         ++I;
1417     } else {
1418       DestBBs.push_back(Default);
1419     }
1420   }
1421
1422   // Update successor info. Add one edge to each unique successor.
1423   BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs());
1424   for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
1425          E = DestBBs.end(); I != E; ++I) {
1426     if (!SuccsHandled[(*I)->getNumber()]) {
1427       SuccsHandled[(*I)->getNumber()] = true;
1428       JumpTableBB->addSuccessor(*I);
1429     }
1430   }
1431
1432   // Create a jump table index for this jump table, or return an existing
1433   // one.
1434   unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
1435
1436   // Set the jump table information so that we can codegen it as a second
1437   // MachineBasicBlock
1438   SelectionDAGISel::JumpTable JT(-1UL, JTI, JumpTableBB, Default);
1439   SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
1440                                         (CR.CaseBB == CurMBB));
1441   if (CR.CaseBB == CurMBB)
1442     visitJumpTableHeader(JT, JTH);
1443
1444   JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT));
1445
1446   return true;
1447 }
1448
1449 /// handleBTSplitSwitchCase - emit comparison and split binary search tree into
1450 /// 2 subtrees.
1451 bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
1452                                                    CaseRecVector& WorkList,
1453                                                    Value* SV,
1454                                                    MachineBasicBlock* Default) {
1455   // Get the MachineFunction which holds the current MBB.  This is used when
1456   // inserting any additional MBBs necessary to represent the switch.
1457   MachineFunction *CurMF = CurMBB->getParent();
1458
1459   // Figure out which block is immediately after the current one.
1460   MachineBasicBlock *NextBlock = 0;
1461   MachineFunction::iterator BBI = CR.CaseBB;
1462
1463   if (++BBI != CurMBB->getParent()->end())
1464     NextBlock = BBI;
1465
1466   Case& FrontCase = *CR.Range.first;
1467   Case& BackCase  = *(CR.Range.second-1);
1468   const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1469
1470   // Size is the number of Cases represented by this range.
1471   unsigned Size = CR.Range.second - CR.Range.first;
1472
1473   int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
1474   int64_t Last  = cast<ConstantInt>(BackCase.High)->getSExtValue();
1475   double Density = 0;
1476   CaseItr Pivot = CR.Range.first + Size/2;
1477
1478   // Select optimal pivot, maximizing sum density of LHS and RHS. This will
1479   // (heuristically) allow us to emit JumpTable's later.
1480   uint64_t TSize = 0;
1481   for (CaseItr I = CR.Range.first, E = CR.Range.second;
1482        I!=E; ++I)
1483     TSize += I->size();
1484
1485   uint64_t LSize = FrontCase.size();
1486   uint64_t RSize = TSize-LSize;
1487   for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
1488        J!=E; ++I, ++J) {
1489     int64_t LEnd = cast<ConstantInt>(I->High)->getSExtValue();
1490     int64_t RBegin = cast<ConstantInt>(J->Low)->getSExtValue();
1491     double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL);
1492     double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL);
1493     if (Density < (LDensity + RDensity)) {
1494       Pivot = J;
1495       Density = LDensity + RDensity;
1496     }
1497
1498     LSize += J->size();
1499     RSize -= J->size();
1500   }
1501
1502   CaseRange LHSR(CR.Range.first, Pivot);
1503   CaseRange RHSR(Pivot, CR.Range.second);
1504   Constant *C = Pivot->Low;
1505   MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
1506
1507   // We know that we branch to the LHS if the Value being switched on is
1508   // less than the Pivot value, C.  We use this to optimize our binary
1509   // tree a bit, by recognizing that if SV is greater than or equal to the
1510   // LHS's Case Value, and that Case Value is exactly one less than the
1511   // Pivot's Value, then we can branch directly to the LHS's Target,
1512   // rather than creating a leaf node for it.
1513   if ((LHSR.second - LHSR.first) == 1 &&
1514       LHSR.first->High == CR.GE &&
1515       cast<ConstantInt>(C)->getSExtValue() ==
1516       (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) {
1517     TrueBB = LHSR.first->BB;
1518   } else {
1519     TrueBB = new MachineBasicBlock(LLVMBB);
1520     CurMF->getBasicBlockList().insert(BBI, TrueBB);
1521     WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
1522   }
1523
1524   // Similar to the optimization above, if the Value being switched on is
1525   // known to be less than the Constant CR.LT, and the current Case Value
1526   // is CR.LT - 1, then we can branch directly to the target block for
1527   // the current Case Value, rather than emitting a RHS leaf node for it.
1528   if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
1529       cast<ConstantInt>(RHSR.first->Low)->getSExtValue() ==
1530       (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) {
1531     FalseBB = RHSR.first->BB;
1532   } else {
1533     FalseBB = new MachineBasicBlock(LLVMBB);
1534     CurMF->getBasicBlockList().insert(BBI, FalseBB);
1535     WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
1536   }
1537
1538   // Create a CaseBlock record representing a conditional branch to
1539   // the LHS node if the value being switched on SV is less than C.
1540   // Otherwise, branch to LHS.
1541   SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL,
1542                                  TrueBB, FalseBB, CR.CaseBB);
1543
1544   if (CR.CaseBB == CurMBB)
1545     visitSwitchCase(CB);
1546   else
1547     SwitchCases.push_back(CB);
1548
1549   return true;
1550 }
1551
1552 // Clusterify - Transform simple list of Cases into list of CaseRange's
1553 unsigned SelectionDAGLowering::Clusterify(CaseVector& Cases,
1554                                           const SwitchInst& SI) {
1555   unsigned numCmps = 0;
1556
1557   // Start with "simple" cases
1558   for (unsigned i = 1; i < SI.getNumSuccessors(); ++i) {
1559     MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)];
1560     Cases.push_back(Case(SI.getSuccessorValue(i),
1561                          SI.getSuccessorValue(i),
1562                          SMBB));
1563   }
1564   sort(Cases.begin(), Cases.end(), CaseCmp());
1565
1566   // Merge case into clusters
1567   if (Cases.size()>=2)
1568     for (CaseItr I=Cases.begin(), J=++(Cases.begin()), E=Cases.end(); J!=E; ) {
1569       int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue();
1570       int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue();
1571       MachineBasicBlock* nextBB = J->BB;
1572       MachineBasicBlock* currentBB = I->BB;
1573
1574       // If the two neighboring cases go to the same destination, merge them
1575       // into a single case.
1576       if ((nextValue-currentValue==1) && (currentBB == nextBB)) {
1577         I->High = J->High;
1578         J = Cases.erase(J);
1579       } else {
1580         I = J++;
1581       }
1582     }
1583
1584   for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
1585     if (I->Low != I->High)
1586       // A range counts double, since it requires two compares.
1587       ++numCmps;
1588   }
1589
1590   return numCmps;
1591 }
1592
1593 void SelectionDAGLowering::visitSwitch(SwitchInst &SI) {
1594   // Figure out which block is immediately after the current one.
1595   MachineBasicBlock *NextBlock = 0;
1596   MachineFunction::iterator BBI = CurMBB;
1597
1598   MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
1599
1600   // If there is only the default destination, branch to it if it is not the
1601   // next basic block.  Otherwise, just fall through.
1602   if (SI.getNumOperands() == 2) {
1603     // Update machine-CFG edges.
1604
1605     // If this is not a fall-through branch, emit the branch.
1606     if (Default != NextBlock)
1607       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1608                               DAG.getBasicBlock(Default)));
1609
1610     CurMBB->addSuccessor(Default);
1611     return;
1612   }
1613
1614   // If there are any non-default case statements, create a vector of Cases
1615   // representing each one, and sort the vector so that we can efficiently
1616   // create a binary search tree from them.
1617   CaseVector Cases;
1618   unsigned numCmps = Clusterify(Cases, SI);
1619   DOUT << "Clusterify finished. Total clusters: " << Cases.size()
1620        << ". Total compares: " << numCmps << "\n";
1621
1622   // Get the Value to be switched on and default basic blocks, which will be
1623   // inserted into CaseBlock records, representing basic blocks in the binary
1624   // search tree.
1625   Value *SV = SI.getOperand(0);
1626
1627   // Push the initial CaseRec onto the worklist
1628   CaseRecVector WorkList;
1629   WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
1630
1631   while (!WorkList.empty()) {
1632     // Grab a record representing a case range to process off the worklist
1633     CaseRec CR = WorkList.back();
1634     WorkList.pop_back();
1635
1636     // If the range has few cases (two or less) emit a series of specific
1637     // tests.
1638     if (handleSmallSwitchRange(CR, WorkList, SV, Default))
1639       continue;
1640
1641     // If the switch has more than 5 blocks, and at least 31.25% dense, and the
1642     // target supports indirect branches, then emit a jump table rather than
1643     // lowering the switch to a binary tree of conditional branches.
1644     if (handleJTSwitchCase(CR, WorkList, SV, Default))
1645       continue;
1646
1647     // Emit binary tree. We need to pick a pivot, and push left and right ranges
1648     // onto the worklist. Leafs are handled via handleSmallSwitchRange() call.
1649     handleBTSplitSwitchCase(CR, WorkList, SV, Default);
1650   }
1651 }
1652
1653
1654 void SelectionDAGLowering::visitSub(User &I) {
1655   // -0.0 - X --> fneg
1656   const Type *Ty = I.getType();
1657   if (isa<VectorType>(Ty)) {
1658     visitVectorBinary(I, ISD::VSUB);
1659   } else if (Ty->isFloatingPoint()) {
1660     if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
1661       if (CFP->isExactlyValue(-0.0)) {
1662         SDOperand Op2 = getValue(I.getOperand(1));
1663         setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
1664         return;
1665       }
1666     visitScalarBinary(I, ISD::FSUB);
1667   } else
1668     visitScalarBinary(I, ISD::SUB);
1669 }
1670
1671 void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) {
1672   SDOperand Op1 = getValue(I.getOperand(0));
1673   SDOperand Op2 = getValue(I.getOperand(1));
1674
1675   setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
1676 }
1677
1678 void
1679 SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) {
1680   assert(isa<VectorType>(I.getType()));
1681   const VectorType *Ty = cast<VectorType>(I.getType());
1682   SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType()));
1683
1684   setValue(&I, DAG.getNode(OpCode, MVT::Vector,
1685                            getValue(I.getOperand(0)),
1686                            getValue(I.getOperand(1)),
1687                            DAG.getConstant(Ty->getNumElements(), MVT::i32),
1688                            Typ));
1689 }
1690
1691 void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp,
1692                                              unsigned VectorOp) {
1693   if (isa<VectorType>(I.getType()))
1694     visitVectorBinary(I, VectorOp);
1695   else
1696     visitScalarBinary(I, ScalarOp);
1697 }
1698
1699 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
1700   SDOperand Op1 = getValue(I.getOperand(0));
1701   SDOperand Op2 = getValue(I.getOperand(1));
1702
1703   if (TLI.getShiftAmountTy() < Op2.getValueType())
1704     Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
1705   else if (TLI.getShiftAmountTy() > Op2.getValueType())
1706     Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
1707
1708   setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
1709 }
1710
1711 void SelectionDAGLowering::visitICmp(User &I) {
1712   ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
1713   if (ICmpInst *IC = dyn_cast<ICmpInst>(&I))
1714     predicate = IC->getPredicate();
1715   else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
1716     predicate = ICmpInst::Predicate(IC->getPredicate());
1717   SDOperand Op1 = getValue(I.getOperand(0));
1718   SDOperand Op2 = getValue(I.getOperand(1));
1719   ISD::CondCode Opcode;
1720   switch (predicate) {
1721     case ICmpInst::ICMP_EQ  : Opcode = ISD::SETEQ; break;
1722     case ICmpInst::ICMP_NE  : Opcode = ISD::SETNE; break;
1723     case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
1724     case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
1725     case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
1726     case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
1727     case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
1728     case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
1729     case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
1730     case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
1731     default:
1732       assert(!"Invalid ICmp predicate value");
1733       Opcode = ISD::SETEQ;
1734       break;
1735   }
1736   setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
1737 }
1738
1739 void SelectionDAGLowering::visitFCmp(User &I) {
1740   FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
1741   if (FCmpInst *FC = dyn_cast<FCmpInst>(&I))
1742     predicate = FC->getPredicate();
1743   else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
1744     predicate = FCmpInst::Predicate(FC->getPredicate());
1745   SDOperand Op1 = getValue(I.getOperand(0));
1746   SDOperand Op2 = getValue(I.getOperand(1));
1747   ISD::CondCode Condition, FOC, FPC;
1748   switch (predicate) {
1749     case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
1750     case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
1751     case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
1752     case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
1753     case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
1754     case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
1755     case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
1756     case FCmpInst::FCMP_ORD:   FOC = ISD::SETEQ; FPC = ISD::SETO;   break;
1757     case FCmpInst::FCMP_UNO:   FOC = ISD::SETNE; FPC = ISD::SETUO;  break;
1758     case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
1759     case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
1760     case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
1761     case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
1762     case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
1763     case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
1764     case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
1765     default:
1766       assert(!"Invalid FCmp predicate value");
1767       FOC = FPC = ISD::SETFALSE;
1768       break;
1769   }
1770   if (FiniteOnlyFPMath())
1771     Condition = FOC;
1772   else
1773     Condition = FPC;
1774   setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition));
1775 }
1776
1777 void SelectionDAGLowering::visitSelect(User &I) {
1778   SDOperand Cond     = getValue(I.getOperand(0));
1779   SDOperand TrueVal  = getValue(I.getOperand(1));
1780   SDOperand FalseVal = getValue(I.getOperand(2));
1781   if (!isa<VectorType>(I.getType())) {
1782     setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
1783                              TrueVal, FalseVal));
1784   } else {
1785     setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal,
1786                              *(TrueVal.Val->op_end()-2),
1787                              *(TrueVal.Val->op_end()-1)));
1788   }
1789 }
1790
1791
1792 void SelectionDAGLowering::visitTrunc(User &I) {
1793   // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
1794   SDOperand N = getValue(I.getOperand(0));
1795   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1796   setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1797 }
1798
1799 void SelectionDAGLowering::visitZExt(User &I) {
1800   // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1801   // ZExt also can't be a cast to bool for same reason. So, nothing much to do
1802   SDOperand N = getValue(I.getOperand(0));
1803   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1804   setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1805 }
1806
1807 void SelectionDAGLowering::visitSExt(User &I) {
1808   // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1809   // SExt also can't be a cast to bool for same reason. So, nothing much to do
1810   SDOperand N = getValue(I.getOperand(0));
1811   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1812   setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N));
1813 }
1814
1815 void SelectionDAGLowering::visitFPTrunc(User &I) {
1816   // FPTrunc is never a no-op cast, no need to check
1817   SDOperand N = getValue(I.getOperand(0));
1818   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1819   setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N));
1820 }
1821
1822 void SelectionDAGLowering::visitFPExt(User &I){
1823   // FPTrunc is never a no-op cast, no need to check
1824   SDOperand N = getValue(I.getOperand(0));
1825   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1826   setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N));
1827 }
1828
1829 void SelectionDAGLowering::visitFPToUI(User &I) {
1830   // FPToUI is never a no-op cast, no need to check
1831   SDOperand N = getValue(I.getOperand(0));
1832   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1833   setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N));
1834 }
1835
1836 void SelectionDAGLowering::visitFPToSI(User &I) {
1837   // FPToSI is never a no-op cast, no need to check
1838   SDOperand N = getValue(I.getOperand(0));
1839   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1840   setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N));
1841 }
1842
1843 void SelectionDAGLowering::visitUIToFP(User &I) {
1844   // UIToFP is never a no-op cast, no need to check
1845   SDOperand N = getValue(I.getOperand(0));
1846   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1847   setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N));
1848 }
1849
1850 void SelectionDAGLowering::visitSIToFP(User &I){
1851   // UIToFP is never a no-op cast, no need to check
1852   SDOperand N = getValue(I.getOperand(0));
1853   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1854   setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N));
1855 }
1856
1857 void SelectionDAGLowering::visitPtrToInt(User &I) {
1858   // What to do depends on the size of the integer and the size of the pointer.
1859   // We can either truncate, zero extend, or no-op, accordingly.
1860   SDOperand N = getValue(I.getOperand(0));
1861   MVT::ValueType SrcVT = N.getValueType();
1862   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1863   SDOperand Result;
1864   if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1865     Result = DAG.getNode(ISD::TRUNCATE, DestVT, N);
1866   else
1867     // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1868     Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N);
1869   setValue(&I, Result);
1870 }
1871
1872 void SelectionDAGLowering::visitIntToPtr(User &I) {
1873   // What to do depends on the size of the integer and the size of the pointer.
1874   // We can either truncate, zero extend, or no-op, accordingly.
1875   SDOperand N = getValue(I.getOperand(0));
1876   MVT::ValueType SrcVT = N.getValueType();
1877   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1878   if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1879     setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1880   else
1881     // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1882     setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1883 }
1884
1885 void SelectionDAGLowering::visitBitCast(User &I) {
1886   SDOperand N = getValue(I.getOperand(0));
1887   MVT::ValueType DestVT = TLI.getValueType(I.getType());
1888   if (DestVT == MVT::Vector) {
1889     // This is a cast to a vector from something else.
1890     // Get information about the output vector.
1891     const VectorType *DestTy = cast<VectorType>(I.getType());
1892     MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
1893     setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N,
1894                              DAG.getConstant(DestTy->getNumElements(),MVT::i32),
1895                              DAG.getValueType(EltVT)));
1896     return;
1897   }
1898   MVT::ValueType SrcVT = N.getValueType();
1899   if (SrcVT == MVT::Vector) {
1900     // This is a cast from a vctor to something else.
1901     // Get information about the input vector.
1902     setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N));
1903     return;
1904   }
1905
1906   // BitCast assures us that source and destination are the same size so this
1907   // is either a BIT_CONVERT or a no-op.
1908   if (DestVT != N.getValueType())
1909     setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types
1910   else
1911     setValue(&I, N); // noop cast.
1912 }
1913
1914 void SelectionDAGLowering::visitInsertElement(User &I) {
1915   SDOperand InVec = getValue(I.getOperand(0));
1916   SDOperand InVal = getValue(I.getOperand(1));
1917   SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1918                                 getValue(I.getOperand(2)));
1919
1920   SDOperand Num = *(InVec.Val->op_end()-2);
1921   SDOperand Typ = *(InVec.Val->op_end()-1);
1922   setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector,
1923                            InVec, InVal, InIdx, Num, Typ));
1924 }
1925
1926 void SelectionDAGLowering::visitExtractElement(User &I) {
1927   SDOperand InVec = getValue(I.getOperand(0));
1928   SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1929                                 getValue(I.getOperand(1)));
1930   SDOperand Typ = *(InVec.Val->op_end()-1);
1931   setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT,
1932                            TLI.getValueType(I.getType()), InVec, InIdx));
1933 }
1934
1935 void SelectionDAGLowering::visitShuffleVector(User &I) {
1936   SDOperand V1   = getValue(I.getOperand(0));
1937   SDOperand V2   = getValue(I.getOperand(1));
1938   SDOperand Mask = getValue(I.getOperand(2));
1939
1940   SDOperand Num = *(V1.Val->op_end()-2);
1941   SDOperand Typ = *(V2.Val->op_end()-1);
1942   setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
1943                            V1, V2, Mask, Num, Typ));
1944 }
1945
1946
1947 void SelectionDAGLowering::visitGetElementPtr(User &I) {
1948   SDOperand N = getValue(I.getOperand(0));
1949   const Type *Ty = I.getOperand(0)->getType();
1950
1951   for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
1952        OI != E; ++OI) {
1953     Value *Idx = *OI;
1954     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1955       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
1956       if (Field) {
1957         // N = N + Offset
1958         uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field);
1959         N = DAG.getNode(ISD::ADD, N.getValueType(), N,
1960                         getIntPtrConstant(Offset));
1961       }
1962       Ty = StTy->getElementType(Field);
1963     } else {
1964       Ty = cast<SequentialType>(Ty)->getElementType();
1965
1966       // If this is a constant subscript, handle it quickly.
1967       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
1968         if (CI->getZExtValue() == 0) continue;
1969         uint64_t Offs =
1970             TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
1971         N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
1972         continue;
1973       }
1974
1975       // N = N + Idx * ElementSize;
1976       uint64_t ElementSize = TD->getTypeSize(Ty);
1977       SDOperand IdxN = getValue(Idx);
1978
1979       // If the index is smaller or larger than intptr_t, truncate or extend
1980       // it.
1981       if (IdxN.getValueType() < N.getValueType()) {
1982         IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
1983       } else if (IdxN.getValueType() > N.getValueType())
1984         IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
1985
1986       // If this is a multiply by a power of two, turn it into a shl
1987       // immediately.  This is a very common case.
1988       if (isPowerOf2_64(ElementSize)) {
1989         unsigned Amt = Log2_64(ElementSize);
1990         IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
1991                            DAG.getConstant(Amt, TLI.getShiftAmountTy()));
1992         N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1993         continue;
1994       }
1995
1996       SDOperand Scale = getIntPtrConstant(ElementSize);
1997       IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
1998       N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1999     }
2000   }
2001   setValue(&I, N);
2002 }
2003
2004 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
2005   // If this is a fixed sized alloca in the entry block of the function,
2006   // allocate it statically on the stack.
2007   if (FuncInfo.StaticAllocaMap.count(&I))
2008     return;   // getValue will auto-populate this.
2009
2010   const Type *Ty = I.getAllocatedType();
2011   uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
2012   unsigned Align =
2013     std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
2014              I.getAlignment());
2015
2016   SDOperand AllocSize = getValue(I.getArraySize());
2017   MVT::ValueType IntPtr = TLI.getPointerTy();
2018   if (IntPtr < AllocSize.getValueType())
2019     AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
2020   else if (IntPtr > AllocSize.getValueType())
2021     AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
2022
2023   AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
2024                           getIntPtrConstant(TySize));
2025
2026   // Handle alignment.  If the requested alignment is less than or equal to the
2027   // stack alignment, ignore it and round the size of the allocation up to the
2028   // stack alignment size.  If the size is greater than the stack alignment, we
2029   // note this in the DYNAMIC_STACKALLOC node.
2030   unsigned StackAlign =
2031     TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
2032   if (Align <= StackAlign) {
2033     Align = 0;
2034     // Add SA-1 to the size.
2035     AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
2036                             getIntPtrConstant(StackAlign-1));
2037     // Mask out the low bits for alignment purposes.
2038     AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
2039                             getIntPtrConstant(~(uint64_t)(StackAlign-1)));
2040   }
2041
2042   SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) };
2043   const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
2044                                                     MVT::Other);
2045   SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3);
2046   setValue(&I, DSA);
2047   DAG.setRoot(DSA.getValue(1));
2048
2049   // Inform the Frame Information that we have just allocated a variable-sized
2050   // object.
2051   CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
2052 }
2053
2054 void SelectionDAGLowering::visitLoad(LoadInst &I) {
2055   SDOperand Ptr = getValue(I.getOperand(0));
2056
2057   SDOperand Root;
2058   if (I.isVolatile())
2059     Root = getRoot();
2060   else {
2061     // Do not serialize non-volatile loads against each other.
2062     Root = DAG.getRoot();
2063   }
2064
2065   setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0),
2066                            Root, I.isVolatile()));
2067 }
2068
2069 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr,
2070                                             const Value *SV, SDOperand Root,
2071                                             bool isVolatile) {
2072   SDOperand L;
2073   if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
2074     MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
2075     L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr,
2076                        DAG.getSrcValue(SV));
2077   } else {
2078     L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile);
2079   }
2080
2081   if (isVolatile)
2082     DAG.setRoot(L.getValue(1));
2083   else
2084     PendingLoads.push_back(L.getValue(1));
2085
2086   return L;
2087 }
2088
2089
2090 void SelectionDAGLowering::visitStore(StoreInst &I) {
2091   Value *SrcV = I.getOperand(0);
2092   SDOperand Src = getValue(SrcV);
2093   SDOperand Ptr = getValue(I.getOperand(1));
2094   DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
2095                            I.isVolatile()));
2096 }
2097
2098 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
2099 /// access memory and has no other side effects at all.
2100 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) {
2101 #define GET_NO_MEMORY_INTRINSICS
2102 #include "llvm/Intrinsics.gen"
2103 #undef GET_NO_MEMORY_INTRINSICS
2104   return false;
2105 }
2106
2107 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't
2108 // have any side-effects or if it only reads memory.
2109 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) {
2110 #define GET_SIDE_EFFECT_INFO
2111 #include "llvm/Intrinsics.gen"
2112 #undef GET_SIDE_EFFECT_INFO
2113   return false;
2114 }
2115
2116 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
2117 /// node.
2118 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
2119                                                 unsigned Intrinsic) {
2120   bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic);
2121   bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic);
2122
2123   // Build the operand list.
2124   SmallVector<SDOperand, 8> Ops;
2125   if (HasChain) {  // If this intrinsic has side-effects, chainify it.
2126     if (OnlyLoad) {
2127       // We don't need to serialize loads against other loads.
2128       Ops.push_back(DAG.getRoot());
2129     } else {
2130       Ops.push_back(getRoot());
2131     }
2132   }
2133
2134   // Add the intrinsic ID as an integer operand.
2135   Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy()));
2136
2137   // Add all operands of the call to the operand list.
2138   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
2139     SDOperand Op = getValue(I.getOperand(i));
2140
2141     // If this is a vector type, force it to the right vector type.
2142     if (Op.getValueType() == MVT::Vector) {
2143       const VectorType *OpTy = cast<VectorType>(I.getOperand(i)->getType());
2144       MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType());
2145
2146       MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements());
2147       assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?");
2148       Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op);
2149     }
2150
2151     assert(TLI.isTypeLegal(Op.getValueType()) &&
2152            "Intrinsic uses a non-legal type?");
2153     Ops.push_back(Op);
2154   }
2155
2156   std::vector<MVT::ValueType> VTs;
2157   if (I.getType() != Type::VoidTy) {
2158     MVT::ValueType VT = TLI.getValueType(I.getType());
2159     if (VT == MVT::Vector) {
2160       const VectorType *DestTy = cast<VectorType>(I.getType());
2161       MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
2162
2163       VT = MVT::getVectorType(EltVT, DestTy->getNumElements());
2164       assert(VT != MVT::Other && "Intrinsic uses a non-legal type?");
2165     }
2166
2167     assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?");
2168     VTs.push_back(VT);
2169   }
2170   if (HasChain)
2171     VTs.push_back(MVT::Other);
2172
2173   const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs);
2174
2175   // Create the node.
2176   SDOperand Result;
2177   if (!HasChain)
2178     Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(),
2179                          &Ops[0], Ops.size());
2180   else if (I.getType() != Type::VoidTy)
2181     Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(),
2182                          &Ops[0], Ops.size());
2183   else
2184     Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(),
2185                          &Ops[0], Ops.size());
2186
2187   if (HasChain) {
2188     SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1);
2189     if (OnlyLoad)
2190       PendingLoads.push_back(Chain);
2191     else
2192       DAG.setRoot(Chain);
2193   }
2194   if (I.getType() != Type::VoidTy) {
2195     if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
2196       MVT::ValueType EVT = TLI.getValueType(PTy->getElementType());
2197       Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
2198                            DAG.getConstant(PTy->getNumElements(), MVT::i32),
2199                            DAG.getValueType(EVT));
2200     }
2201     setValue(&I, Result);
2202   }
2203 }
2204
2205 /// visitIntrinsicCall - Lower the call to the specified intrinsic function.  If
2206 /// we want to emit this as a call to a named external function, return the name
2207 /// otherwise lower it and return null.
2208 const char *
2209 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
2210   switch (Intrinsic) {
2211   default:
2212     // By default, turn this into a target intrinsic node.
2213     visitTargetIntrinsic(I, Intrinsic);
2214     return 0;
2215   case Intrinsic::vastart:  visitVAStart(I); return 0;
2216   case Intrinsic::vaend:    visitVAEnd(I); return 0;
2217   case Intrinsic::vacopy:   visitVACopy(I); return 0;
2218   case Intrinsic::returnaddress:
2219     setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(),
2220                              getValue(I.getOperand(1))));
2221     return 0;
2222   case Intrinsic::frameaddress:
2223     setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(),
2224                              getValue(I.getOperand(1))));
2225     return 0;
2226   case Intrinsic::setjmp:
2227     return "_setjmp"+!TLI.usesUnderscoreSetJmp();
2228     break;
2229   case Intrinsic::longjmp:
2230     return "_longjmp"+!TLI.usesUnderscoreLongJmp();
2231     break;
2232   case Intrinsic::memcpy_i32:
2233   case Intrinsic::memcpy_i64:
2234     visitMemIntrinsic(I, ISD::MEMCPY);
2235     return 0;
2236   case Intrinsic::memset_i32:
2237   case Intrinsic::memset_i64:
2238     visitMemIntrinsic(I, ISD::MEMSET);
2239     return 0;
2240   case Intrinsic::memmove_i32:
2241   case Intrinsic::memmove_i64:
2242     visitMemIntrinsic(I, ISD::MEMMOVE);
2243     return 0;
2244
2245   case Intrinsic::dbg_stoppoint: {
2246     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2247     DbgStopPointInst &SPI = cast<DbgStopPointInst>(I);
2248     if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) {
2249       SDOperand Ops[5];
2250
2251       Ops[0] = getRoot();
2252       Ops[1] = getValue(SPI.getLineValue());
2253       Ops[2] = getValue(SPI.getColumnValue());
2254
2255       DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext());
2256       assert(DD && "Not a debug information descriptor");
2257       CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD);
2258
2259       Ops[3] = DAG.getString(CompileUnit->getFileName());
2260       Ops[4] = DAG.getString(CompileUnit->getDirectory());
2261
2262       DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5));
2263     }
2264
2265     return 0;
2266   }
2267   case Intrinsic::dbg_region_start: {
2268     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2269     DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I);
2270     if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) {
2271       unsigned LabelID = MMI->RecordRegionStart(RSI.getContext());
2272       DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2273                               DAG.getConstant(LabelID, MVT::i32)));
2274     }
2275
2276     return 0;
2277   }
2278   case Intrinsic::dbg_region_end: {
2279     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2280     DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I);
2281     if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) {
2282       unsigned LabelID = MMI->RecordRegionEnd(REI.getContext());
2283       DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2284                               getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2285     }
2286
2287     return 0;
2288   }
2289   case Intrinsic::dbg_func_start: {
2290     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2291     DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I);
2292     if (MMI && FSI.getSubprogram() &&
2293         MMI->Verify(FSI.getSubprogram())) {
2294       unsigned LabelID = MMI->RecordRegionStart(FSI.getSubprogram());
2295       DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2296                   getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2297     }
2298
2299     return 0;
2300   }
2301   case Intrinsic::dbg_declare: {
2302     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2303     DbgDeclareInst &DI = cast<DbgDeclareInst>(I);
2304     if (MMI && DI.getVariable() && MMI->Verify(DI.getVariable())) {
2305       SDOperand AddressOp  = getValue(DI.getAddress());
2306       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp))
2307         MMI->RecordVariable(DI.getVariable(), FI->getIndex());
2308     }
2309
2310     return 0;
2311   }
2312
2313   case Intrinsic::eh_exception: {
2314     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2315
2316     if (MMI) {
2317       // Add a label to mark the beginning of the landing pad.  Deletion of the
2318       // landing pad can thus be detected via the MachineModuleInfo.
2319       unsigned LabelID = MMI->addLandingPad(CurMBB);
2320       DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
2321                               DAG.getConstant(LabelID, MVT::i32)));
2322
2323       // Mark exception register as live in.
2324       unsigned Reg = TLI.getExceptionAddressRegister();
2325       if (Reg) CurMBB->addLiveIn(Reg);
2326
2327       // Insert the EXCEPTIONADDR instruction.
2328       SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
2329       SDOperand Ops[1];
2330       Ops[0] = DAG.getRoot();
2331       SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
2332       setValue(&I, Op);
2333       DAG.setRoot(Op.getValue(1));
2334     } else {
2335       setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
2336     }
2337     return 0;
2338   }
2339
2340   case Intrinsic::eh_selector:
2341   case Intrinsic::eh_filter:{
2342     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2343
2344     if (MMI) {
2345       // Inform the MachineModuleInfo of the personality for this landing pad.
2346       ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(2));
2347       assert(CE && CE->getOpcode() == Instruction::BitCast &&
2348              isa<Function>(CE->getOperand(0)) &&
2349              "Personality should be a function");
2350       MMI->addPersonality(CurMBB, cast<Function>(CE->getOperand(0)));
2351       if (Intrinsic == Intrinsic::eh_filter)
2352         MMI->setIsFilterLandingPad(CurMBB);
2353
2354       // Gather all the type infos for this landing pad and pass them along to
2355       // MachineModuleInfo.
2356       std::vector<GlobalVariable *> TyInfo;
2357       for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
2358         ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i));
2359         if (CE && CE->getOpcode() == Instruction::BitCast &&
2360             isa<GlobalVariable>(CE->getOperand(0))) {
2361           TyInfo.push_back(cast<GlobalVariable>(CE->getOperand(0)));
2362         } else {
2363           ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i));
2364           assert(CI && CI->getZExtValue() == 0 &&
2365             "TypeInfo must be a global variable typeinfo or NULL");
2366           TyInfo.push_back(NULL);
2367         }
2368       }
2369       MMI->addCatchTypeInfo(CurMBB, TyInfo);
2370
2371       // Mark exception selector register as live in.
2372       unsigned Reg = TLI.getExceptionSelectorRegister();
2373       if (Reg) CurMBB->addLiveIn(Reg);
2374
2375       // Insert the EHSELECTION instruction.
2376       SDVTList VTs = DAG.getVTList(MVT::i32, MVT::Other);
2377       SDOperand Ops[2];
2378       Ops[0] = getValue(I.getOperand(1));
2379       Ops[1] = getRoot();
2380       SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
2381       setValue(&I, Op);
2382       DAG.setRoot(Op.getValue(1));
2383     } else {
2384       setValue(&I, DAG.getConstant(0, MVT::i32));
2385     }
2386
2387     return 0;
2388   }
2389
2390   case Intrinsic::eh_typeid_for: {
2391     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2392
2393     if (MMI) {
2394       // Find the type id for the given typeinfo.
2395       GlobalVariable *GV = NULL;
2396       ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(1));
2397       if (CE && CE->getOpcode() == Instruction::BitCast &&
2398           isa<GlobalVariable>(CE->getOperand(0))) {
2399         GV = cast<GlobalVariable>(CE->getOperand(0));
2400       } else {
2401         ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
2402         assert(CI && CI->getZExtValue() == 0 &&
2403           "TypeInfo must be a global variable typeinfo or NULL");
2404         GV = NULL;
2405       }
2406
2407       unsigned TypeID = MMI->getTypeIDFor(GV);
2408       setValue(&I, DAG.getConstant(TypeID, MVT::i32));
2409     } else {
2410       setValue(&I, DAG.getConstant(0, MVT::i32));
2411     }
2412
2413     return 0;
2414   }
2415
2416   case Intrinsic::sqrt_f32:
2417   case Intrinsic::sqrt_f64:
2418     setValue(&I, DAG.getNode(ISD::FSQRT,
2419                              getValue(I.getOperand(1)).getValueType(),
2420                              getValue(I.getOperand(1))));
2421     return 0;
2422   case Intrinsic::powi_f32:
2423   case Intrinsic::powi_f64:
2424     setValue(&I, DAG.getNode(ISD::FPOWI,
2425                              getValue(I.getOperand(1)).getValueType(),
2426                              getValue(I.getOperand(1)),
2427                              getValue(I.getOperand(2))));
2428     return 0;
2429   case Intrinsic::pcmarker: {
2430     SDOperand Tmp = getValue(I.getOperand(1));
2431     DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
2432     return 0;
2433   }
2434   case Intrinsic::readcyclecounter: {
2435     SDOperand Op = getRoot();
2436     SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER,
2437                                 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2,
2438                                 &Op, 1);
2439     setValue(&I, Tmp);
2440     DAG.setRoot(Tmp.getValue(1));
2441     return 0;
2442   }
2443   case Intrinsic::bit_part_select: {
2444     // Currently not implemented: just abort
2445     assert(0 && "bit_part_select intrinsic not implemented");
2446     abort();
2447   }
2448   case Intrinsic::bswap:
2449     setValue(&I, DAG.getNode(ISD::BSWAP,
2450                              getValue(I.getOperand(1)).getValueType(),
2451                              getValue(I.getOperand(1))));
2452     return 0;
2453   case Intrinsic::cttz: {
2454     SDOperand Arg = getValue(I.getOperand(1));
2455     MVT::ValueType Ty = Arg.getValueType();
2456     SDOperand result = DAG.getNode(ISD::CTTZ, Ty, Arg);
2457     if (Ty < MVT::i32)
2458       result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2459     else if (Ty > MVT::i32)
2460       result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2461     setValue(&I, result);
2462     return 0;
2463   }
2464   case Intrinsic::ctlz: {
2465     SDOperand Arg = getValue(I.getOperand(1));
2466     MVT::ValueType Ty = Arg.getValueType();
2467     SDOperand result = DAG.getNode(ISD::CTLZ, Ty, Arg);
2468     if (Ty < MVT::i32)
2469       result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2470     else if (Ty > MVT::i32)
2471       result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2472     setValue(&I, result);
2473     return 0;
2474   }
2475   case Intrinsic::ctpop: {
2476     SDOperand Arg = getValue(I.getOperand(1));
2477     MVT::ValueType Ty = Arg.getValueType();
2478     SDOperand result = DAG.getNode(ISD::CTPOP, Ty, Arg);
2479     if (Ty < MVT::i32)
2480       result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2481     else if (Ty > MVT::i32)
2482       result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2483     setValue(&I, result);
2484     return 0;
2485   }
2486   case Intrinsic::stacksave: {
2487     SDOperand Op = getRoot();
2488     SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
2489               DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1);
2490     setValue(&I, Tmp);
2491     DAG.setRoot(Tmp.getValue(1));
2492     return 0;
2493   }
2494   case Intrinsic::stackrestore: {
2495     SDOperand Tmp = getValue(I.getOperand(1));
2496     DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
2497     return 0;
2498   }
2499   case Intrinsic::prefetch:
2500     // FIXME: Currently discarding prefetches.
2501     return 0;
2502   }
2503 }
2504
2505
2506 void SelectionDAGLowering::LowerCallTo(Instruction &I,
2507                                        const Type *CalledValueTy,
2508                                        unsigned CallingConv,
2509                                        bool IsTailCall,
2510                                        SDOperand Callee, unsigned OpIdx) {
2511   const PointerType *PT = cast<PointerType>(CalledValueTy);
2512   const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
2513   const ParamAttrsList *Attrs = FTy->getParamAttrs();
2514
2515   TargetLowering::ArgListTy Args;
2516   TargetLowering::ArgListEntry Entry;
2517   Args.reserve(I.getNumOperands());
2518   for (unsigned i = OpIdx, e = I.getNumOperands(); i != e; ++i) {
2519     Value *Arg = I.getOperand(i);
2520     SDOperand ArgNode = getValue(Arg);
2521     Entry.Node = ArgNode; Entry.Ty = Arg->getType();
2522     Entry.isSExt   = Attrs && Attrs->paramHasAttr(i, SExtAttribute);
2523     Entry.isZExt   = Attrs && Attrs->paramHasAttr(i, ZExtAttribute);
2524     Entry.isInReg  = Attrs && Attrs->paramHasAttr(i, InRegAttribute);
2525     Entry.isSRet   = Attrs && Attrs->paramHasAttr(i, StructRetAttribute);
2526     Args.push_back(Entry);
2527   }
2528
2529   std::pair<SDOperand,SDOperand> Result =
2530     TLI.LowerCallTo(getRoot(), I.getType(),
2531                     Attrs && Attrs->paramHasAttr(0, SExtAttribute),
2532                     FTy->isVarArg(), CallingConv, IsTailCall,
2533                     Callee, Args, DAG);
2534   if (I.getType() != Type::VoidTy)
2535     setValue(&I, Result.first);
2536   DAG.setRoot(Result.second);
2537 }
2538
2539
2540 void SelectionDAGLowering::visitCall(CallInst &I) {
2541   const char *RenameFn = 0;
2542   if (Function *F = I.getCalledFunction()) {
2543     if (F->isDeclaration())
2544       if (unsigned IID = F->getIntrinsicID()) {
2545         RenameFn = visitIntrinsicCall(I, IID);
2546         if (!RenameFn)
2547           return;
2548       } else {    // Not an LLVM intrinsic.
2549         const std::string &Name = F->getName();
2550         if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) {
2551           if (I.getNumOperands() == 3 &&   // Basic sanity checks.
2552               I.getOperand(1)->getType()->isFloatingPoint() &&
2553               I.getType() == I.getOperand(1)->getType() &&
2554               I.getType() == I.getOperand(2)->getType()) {
2555             SDOperand LHS = getValue(I.getOperand(1));
2556             SDOperand RHS = getValue(I.getOperand(2));
2557             setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
2558                                      LHS, RHS));
2559             return;
2560           }
2561         } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
2562           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
2563               I.getOperand(1)->getType()->isFloatingPoint() &&
2564               I.getType() == I.getOperand(1)->getType()) {
2565             SDOperand Tmp = getValue(I.getOperand(1));
2566             setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
2567             return;
2568           }
2569         } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
2570           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
2571               I.getOperand(1)->getType()->isFloatingPoint() &&
2572               I.getType() == I.getOperand(1)->getType()) {
2573             SDOperand Tmp = getValue(I.getOperand(1));
2574             setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
2575             return;
2576           }
2577         } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
2578           if (I.getNumOperands() == 2 &&   // Basic sanity checks.
2579               I.getOperand(1)->getType()->isFloatingPoint() &&
2580               I.getType() == I.getOperand(1)->getType()) {
2581             SDOperand Tmp = getValue(I.getOperand(1));
2582             setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
2583             return;
2584           }
2585         }
2586       }
2587   } else if (isa<InlineAsm>(I.getOperand(0))) {
2588     visitInlineAsm(I);
2589     return;
2590   }
2591
2592   SDOperand Callee;
2593   if (!RenameFn)
2594     Callee = getValue(I.getOperand(0));
2595   else
2596     Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
2597
2598   LowerCallTo(I, I.getCalledValue()->getType(),
2599                  I.getCallingConv(),
2600                  I.isTailCall(),
2601                  Callee,
2602                  1);
2603 }
2604
2605
2606 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
2607                                         SDOperand &Chain, SDOperand &Flag)const{
2608   SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag);
2609   Chain = Val.getValue(1);
2610   Flag  = Val.getValue(2);
2611
2612   // If the result was expanded, copy from the top part.
2613   if (Regs.size() > 1) {
2614     assert(Regs.size() == 2 &&
2615            "Cannot expand to more than 2 elts yet!");
2616     SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag);
2617     Chain = Hi.getValue(1);
2618     Flag  = Hi.getValue(2);
2619     if (DAG.getTargetLoweringInfo().isLittleEndian())
2620       return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
2621     else
2622       return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val);
2623   }
2624
2625   // Otherwise, if the return value was promoted or extended, truncate it to the
2626   // appropriate type.
2627   if (RegVT == ValueVT)
2628     return Val;
2629
2630   if (MVT::isVector(RegVT)) {
2631     assert(ValueVT == MVT::Vector && "Unknown vector conversion!");
2632     return DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
2633                        DAG.getConstant(MVT::getVectorNumElements(RegVT),
2634                                        MVT::i32),
2635                        DAG.getValueType(MVT::getVectorBaseType(RegVT)));
2636   }
2637
2638   if (MVT::isInteger(RegVT)) {
2639     if (ValueVT < RegVT)
2640       return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
2641     else
2642       return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
2643   }
2644
2645   assert(MVT::isFloatingPoint(RegVT) && MVT::isFloatingPoint(ValueVT));
2646   return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
2647 }
2648
2649 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
2650 /// specified value into the registers specified by this object.  This uses
2651 /// Chain/Flag as the input and updates them for the output Chain/Flag.
2652 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
2653                                  SDOperand &Chain, SDOperand &Flag,
2654                                  MVT::ValueType PtrVT) const {
2655   if (Regs.size() == 1) {
2656     // If there is a single register and the types differ, this must be
2657     // a promotion.
2658     if (RegVT != ValueVT) {
2659       if (MVT::isVector(RegVT)) {
2660         assert(Val.getValueType() == MVT::Vector &&"Not a vector-vector cast?");
2661         Val = DAG.getNode(ISD::VBIT_CONVERT, RegVT, Val);
2662       } else if (MVT::isInteger(RegVT) && MVT::isInteger(Val.getValueType())) {
2663         if (RegVT < ValueVT)
2664           Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
2665         else
2666           Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
2667       } else if (MVT::isFloatingPoint(RegVT) &&
2668                  MVT::isFloatingPoint(Val.getValueType())) {
2669         Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
2670       } else if (MVT::getSizeInBits(RegVT) ==
2671                  MVT::getSizeInBits(Val.getValueType())) {
2672         Val = DAG.getNode(ISD::BIT_CONVERT, RegVT, Val);
2673       } else {
2674         assert(0 && "Unknown mismatch!");
2675       }
2676     }
2677     Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
2678     Flag = Chain.getValue(1);
2679   } else {
2680     std::vector<unsigned> R(Regs);
2681     if (!DAG.getTargetLoweringInfo().isLittleEndian())
2682       std::reverse(R.begin(), R.end());
2683
2684     for (unsigned i = 0, e = R.size(); i != e; ++i) {
2685       SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
2686                                    DAG.getConstant(i, PtrVT));
2687       Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
2688       Flag = Chain.getValue(1);
2689     }
2690   }
2691 }
2692
2693 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
2694 /// operand list.  This adds the code marker and includes the number of
2695 /// values added into it.
2696 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
2697                                         std::vector<SDOperand> &Ops) const {
2698   MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
2699   Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
2700   for (unsigned i = 0, e = Regs.size(); i != e; ++i)
2701     Ops.push_back(DAG.getRegister(Regs[i], RegVT));
2702 }
2703
2704 /// isAllocatableRegister - If the specified register is safe to allocate,
2705 /// i.e. it isn't a stack pointer or some other special register, return the
2706 /// register class for the register.  Otherwise, return null.
2707 static const TargetRegisterClass *
2708 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
2709                       const TargetLowering &TLI, const MRegisterInfo *MRI) {
2710   MVT::ValueType FoundVT = MVT::Other;
2711   const TargetRegisterClass *FoundRC = 0;
2712   for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
2713        E = MRI->regclass_end(); RCI != E; ++RCI) {
2714     MVT::ValueType ThisVT = MVT::Other;
2715
2716     const TargetRegisterClass *RC = *RCI;
2717     // If none of the the value types for this register class are valid, we
2718     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
2719     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
2720          I != E; ++I) {
2721       if (TLI.isTypeLegal(*I)) {
2722         // If we have already found this register in a different register class,
2723         // choose the one with the largest VT specified.  For example, on
2724         // PowerPC, we favor f64 register classes over f32.
2725         if (FoundVT == MVT::Other ||
2726             MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
2727           ThisVT = *I;
2728           break;
2729         }
2730       }
2731     }
2732
2733     if (ThisVT == MVT::Other) continue;
2734
2735     // NOTE: This isn't ideal.  In particular, this might allocate the
2736     // frame pointer in functions that need it (due to them not being taken
2737     // out of allocation, because a variable sized allocation hasn't been seen
2738     // yet).  This is a slight code pessimization, but should still work.
2739     for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
2740          E = RC->allocation_order_end(MF); I != E; ++I)
2741       if (*I == Reg) {
2742         // We found a matching register class.  Keep looking at others in case
2743         // we find one with larger registers that this physreg is also in.
2744         FoundRC = RC;
2745         FoundVT = ThisVT;
2746         break;
2747       }
2748   }
2749   return FoundRC;
2750 }
2751
2752 RegsForValue SelectionDAGLowering::
2753 GetRegistersForValue(const std::string &ConstrCode,
2754                      MVT::ValueType VT, bool isOutReg, bool isInReg,
2755                      std::set<unsigned> &OutputRegs,
2756                      std::set<unsigned> &InputRegs) {
2757   std::pair<unsigned, const TargetRegisterClass*> PhysReg =
2758     TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
2759   std::vector<unsigned> Regs;
2760
2761   unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
2762   MVT::ValueType RegVT;
2763   MVT::ValueType ValueVT = VT;
2764
2765   // If this is a constraint for a specific physical register, like {r17},
2766   // assign it now.
2767   if (PhysReg.first) {
2768     if (VT == MVT::Other)
2769       ValueVT = *PhysReg.second->vt_begin();
2770
2771     // Get the actual register value type.  This is important, because the user
2772     // may have asked for (e.g.) the AX register in i32 type.  We need to
2773     // remember that AX is actually i16 to get the right extension.
2774     RegVT = *PhysReg.second->vt_begin();
2775
2776     // This is a explicit reference to a physical register.
2777     Regs.push_back(PhysReg.first);
2778
2779     // If this is an expanded reference, add the rest of the regs to Regs.
2780     if (NumRegs != 1) {
2781       TargetRegisterClass::iterator I = PhysReg.second->begin();
2782       TargetRegisterClass::iterator E = PhysReg.second->end();
2783       for (; *I != PhysReg.first; ++I)
2784         assert(I != E && "Didn't find reg!");
2785
2786       // Already added the first reg.
2787       --NumRegs; ++I;
2788       for (; NumRegs; --NumRegs, ++I) {
2789         assert(I != E && "Ran out of registers to allocate!");
2790         Regs.push_back(*I);
2791       }
2792     }
2793     return RegsForValue(Regs, RegVT, ValueVT);
2794   }
2795
2796   // Otherwise, if this was a reference to an LLVM register class, create vregs
2797   // for this reference.
2798   std::vector<unsigned> RegClassRegs;
2799   if (PhysReg.second) {
2800     // If this is an early clobber or tied register, our regalloc doesn't know
2801     // how to maintain the constraint.  If it isn't, go ahead and create vreg
2802     // and let the regalloc do the right thing.
2803     if (!isOutReg || !isInReg) {
2804       if (VT == MVT::Other)
2805         ValueVT = *PhysReg.second->vt_begin();
2806       RegVT = *PhysReg.second->vt_begin();
2807
2808       // Create the appropriate number of virtual registers.
2809       SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
2810       for (; NumRegs; --NumRegs)
2811         Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
2812
2813       return RegsForValue(Regs, RegVT, ValueVT);
2814     }
2815
2816     // Otherwise, we can't allocate it.  Let the code below figure out how to
2817     // maintain these constraints.
2818     RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
2819
2820   } else {
2821     // This is a reference to a register class that doesn't directly correspond
2822     // to an LLVM register class.  Allocate NumRegs consecutive, available,
2823     // registers from the class.
2824     RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
2825   }
2826
2827   const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
2828   MachineFunction &MF = *CurMBB->getParent();
2829   unsigned NumAllocated = 0;
2830   for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
2831     unsigned Reg = RegClassRegs[i];
2832     // See if this register is available.
2833     if ((isOutReg && OutputRegs.count(Reg)) ||   // Already used.
2834         (isInReg  && InputRegs.count(Reg))) {    // Already used.
2835       // Make sure we find consecutive registers.
2836       NumAllocated = 0;
2837       continue;
2838     }
2839
2840     // Check to see if this register is allocatable (i.e. don't give out the
2841     // stack pointer).
2842     const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
2843     if (!RC) {
2844       // Make sure we find consecutive registers.
2845       NumAllocated = 0;
2846       continue;
2847     }
2848
2849     // Okay, this register is good, we can use it.
2850     ++NumAllocated;
2851
2852     // If we allocated enough consecutive registers, succeed.
2853     if (NumAllocated == NumRegs) {
2854       unsigned RegStart = (i-NumAllocated)+1;
2855       unsigned RegEnd   = i+1;
2856       // Mark all of the allocated registers used.
2857       for (unsigned i = RegStart; i != RegEnd; ++i) {
2858         unsigned Reg = RegClassRegs[i];
2859         Regs.push_back(Reg);
2860         if (isOutReg) OutputRegs.insert(Reg);    // Mark reg used.
2861         if (isInReg)  InputRegs.insert(Reg);     // Mark reg used.
2862       }
2863
2864       return RegsForValue(Regs, *RC->vt_begin(), VT);
2865     }
2866   }
2867
2868   // Otherwise, we couldn't allocate enough registers for this.
2869   return RegsForValue();
2870 }
2871
2872 /// getConstraintGenerality - Return an integer indicating how general CT is.
2873 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
2874   switch (CT) {
2875   default: assert(0 && "Unknown constraint type!");
2876   case TargetLowering::C_Other:
2877   case TargetLowering::C_Unknown:
2878     return 0;
2879   case TargetLowering::C_Register:
2880     return 1;
2881   case TargetLowering::C_RegisterClass:
2882     return 2;
2883   case TargetLowering::C_Memory:
2884     return 3;
2885   }
2886 }
2887
2888 static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
2889                                             const TargetLowering &TLI) {
2890   assert(!C.empty() && "Must have at least one constraint");
2891   if (C.size() == 1) return C[0];
2892
2893   std::string *Current = &C[0];
2894   // If we have multiple constraints, try to pick the most general one ahead
2895   // of time.  This isn't a wonderful solution, but handles common cases.
2896   TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
2897   for (unsigned j = 1, e = C.size(); j != e; ++j) {
2898     TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
2899     if (getConstraintGenerality(ThisFlavor) >
2900         getConstraintGenerality(Flavor)) {
2901       // This constraint letter is more general than the previous one,
2902       // use it.
2903       Flavor = ThisFlavor;
2904       Current = &C[j];
2905     }
2906   }
2907   return *Current;
2908 }
2909
2910
2911 /// visitInlineAsm - Handle a call to an InlineAsm object.
2912 ///
2913 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
2914   InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
2915
2916   SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
2917                                                  MVT::Other);
2918
2919   std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
2920   std::vector<MVT::ValueType> ConstraintVTs;
2921
2922   /// AsmNodeOperands - A list of pairs.  The first element is a register, the
2923   /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
2924   /// if it is a def of that register.
2925   std::vector<SDOperand> AsmNodeOperands;
2926   AsmNodeOperands.push_back(SDOperand());  // reserve space for input chain
2927   AsmNodeOperands.push_back(AsmStr);
2928
2929   SDOperand Chain = getRoot();
2930   SDOperand Flag;
2931
2932   // We fully assign registers here at isel time.  This is not optimal, but
2933   // should work.  For register classes that correspond to LLVM classes, we
2934   // could let the LLVM RA do its thing, but we currently don't.  Do a prepass
2935   // over the constraints, collecting fixed registers that we know we can't use.
2936   std::set<unsigned> OutputRegs, InputRegs;
2937   unsigned OpNum = 1;
2938   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2939     std::string ConstraintCode =
2940       GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2941
2942     MVT::ValueType OpVT;
2943
2944     // Compute the value type for each operand and add it to ConstraintVTs.
2945     switch (Constraints[i].Type) {
2946     case InlineAsm::isOutput:
2947       if (!Constraints[i].isIndirectOutput) {
2948         assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2949         OpVT = TLI.getValueType(I.getType());
2950       } else {
2951         const Type *OpTy = I.getOperand(OpNum)->getType();
2952         OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
2953         OpNum++;  // Consumes a call operand.
2954       }
2955       break;
2956     case InlineAsm::isInput:
2957       OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
2958       OpNum++;  // Consumes a call operand.
2959       break;
2960     case InlineAsm::isClobber:
2961       OpVT = MVT::Other;
2962       break;
2963     }
2964
2965     ConstraintVTs.push_back(OpVT);
2966
2967     if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
2968       continue;  // Not assigned a fixed reg.
2969
2970     // Build a list of regs that this operand uses.  This always has a single
2971     // element for promoted/expanded operands.
2972     RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
2973                                              false, false,
2974                                              OutputRegs, InputRegs);
2975
2976     switch (Constraints[i].Type) {
2977     case InlineAsm::isOutput:
2978       // We can't assign any other output to this register.
2979       OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2980       // If this is an early-clobber output, it cannot be assigned to the same
2981       // value as the input reg.
2982       if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2983         InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2984       break;
2985     case InlineAsm::isInput:
2986       // We can't assign any other input to this register.
2987       InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2988       break;
2989     case InlineAsm::isClobber:
2990       // Clobbered regs cannot be used as inputs or outputs.
2991       InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2992       OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2993       break;
2994     }
2995   }
2996
2997   // Loop over all of the inputs, copying the operand values into the
2998   // appropriate registers and processing the output regs.
2999   RegsForValue RetValRegs;
3000   std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
3001   OpNum = 1;
3002
3003   for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
3004     std::string ConstraintCode =
3005       GetMostGeneralConstraint(Constraints[i].Codes, TLI);
3006
3007     switch (Constraints[i].Type) {
3008     case InlineAsm::isOutput: {
3009       TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3010       if (ConstraintCode.size() == 1)   // not a physreg name.
3011         CTy = TLI.getConstraintType(ConstraintCode);
3012
3013       if (CTy == TargetLowering::C_Memory) {
3014         // Memory output.
3015         SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3016
3017         // Check that the operand (the address to store to) isn't a float.
3018         if (!MVT::isInteger(InOperandVal.getValueType()))
3019           assert(0 && "MATCH FAIL!");
3020
3021         if (!Constraints[i].isIndirectOutput)
3022           assert(0 && "MATCH FAIL!");
3023
3024         OpNum++;  // Consumes a call operand.
3025
3026         // Extend/truncate to the right pointer type if needed.
3027         MVT::ValueType PtrType = TLI.getPointerTy();
3028         if (InOperandVal.getValueType() < PtrType)
3029           InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3030         else if (InOperandVal.getValueType() > PtrType)
3031           InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3032
3033         // Add information to the INLINEASM node to know about this output.
3034         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3035         AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3036         AsmNodeOperands.push_back(InOperandVal);
3037         break;
3038       }
3039
3040       // Otherwise, this is a register output.
3041       assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3042
3043       // If this is an early-clobber output, or if there is an input
3044       // constraint that matches this, we need to reserve the input register
3045       // so no other inputs allocate to it.
3046       bool UsesInputRegister = false;
3047       if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
3048         UsesInputRegister = true;
3049
3050       // Copy the output from the appropriate register.  Find a register that
3051       // we can use.
3052       RegsForValue Regs =
3053         GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3054                              true, UsesInputRegister,
3055                              OutputRegs, InputRegs);
3056       if (Regs.Regs.empty()) {
3057         cerr << "Couldn't allocate output reg for contraint '"
3058              << ConstraintCode << "'!\n";
3059         exit(1);
3060       }
3061
3062       if (!Constraints[i].isIndirectOutput) {
3063         assert(RetValRegs.Regs.empty() &&
3064                "Cannot have multiple output constraints yet!");
3065         assert(I.getType() != Type::VoidTy && "Bad inline asm!");
3066         RetValRegs = Regs;
3067       } else {
3068         IndirectStoresToEmit.push_back(std::make_pair(Regs,
3069                                                       I.getOperand(OpNum)));
3070         OpNum++;  // Consumes a call operand.
3071       }
3072
3073       // Add information to the INLINEASM node to know that this register is
3074       // set.
3075       Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
3076       break;
3077     }
3078     case InlineAsm::isInput: {
3079       SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3080       OpNum++;  // Consumes a call operand.
3081
3082       if (isdigit(ConstraintCode[0])) {    // Matching constraint?
3083         // If this is required to match an output register we have already set,
3084         // just use its register.
3085         unsigned OperandNo = atoi(ConstraintCode.c_str());
3086
3087         // Scan until we find the definition we already emitted of this operand.
3088         // When we find it, create a RegsForValue operand.
3089         unsigned CurOp = 2;  // The first operand.
3090         for (; OperandNo; --OperandNo) {
3091           // Advance to the next operand.
3092           unsigned NumOps =
3093             cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3094           assert(((NumOps & 7) == 2 /*REGDEF*/ ||
3095                   (NumOps & 7) == 4 /*MEM*/) &&
3096                  "Skipped past definitions?");
3097           CurOp += (NumOps>>3)+1;
3098         }
3099
3100         unsigned NumOps =
3101           cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3102         if ((NumOps & 7) == 2 /*REGDEF*/) {
3103           // Add NumOps>>3 registers to MatchedRegs.
3104           RegsForValue MatchedRegs;
3105           MatchedRegs.ValueVT = InOperandVal.getValueType();
3106           MatchedRegs.RegVT   = AsmNodeOperands[CurOp+1].getValueType();
3107           for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
3108             unsigned Reg =
3109               cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
3110             MatchedRegs.Regs.push_back(Reg);
3111           }
3112
3113           // Use the produced MatchedRegs object to
3114           MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
3115                                     TLI.getPointerTy());
3116           MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
3117           break;
3118         } else {
3119           assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
3120           assert(0 && "matching constraints for memory operands unimp");
3121         }
3122       }
3123
3124       TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3125       if (ConstraintCode.size() == 1)   // not a physreg name.
3126         CTy = TLI.getConstraintType(ConstraintCode);
3127
3128       if (CTy == TargetLowering::C_Other) {
3129         InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
3130                                                        ConstraintCode[0], DAG);
3131         if (!InOperandVal.Val) {
3132           cerr << "Invalid operand for inline asm constraint '"
3133                << ConstraintCode << "'!\n";
3134           exit(1);
3135         }
3136
3137         // Add information to the INLINEASM node to know about this input.
3138         unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
3139         AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3140         AsmNodeOperands.push_back(InOperandVal);
3141         break;
3142       } else if (CTy == TargetLowering::C_Memory) {
3143         // Memory input.
3144
3145         // If the operand is a float, spill to a constant pool entry to get its
3146         // address.
3147         if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
3148           InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
3149
3150         if (!MVT::isInteger(InOperandVal.getValueType())) {
3151           cerr << "Match failed, cannot handle this yet!\n";
3152           InOperandVal.Val->dump();
3153           exit(1);
3154         }
3155
3156         // Extend/truncate to the right pointer type if needed.
3157         MVT::ValueType PtrType = TLI.getPointerTy();
3158         if (InOperandVal.getValueType() < PtrType)
3159           InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3160         else if (InOperandVal.getValueType() > PtrType)
3161           InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3162
3163         // Add information to the INLINEASM node to know about this input.
3164         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3165         AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3166         AsmNodeOperands.push_back(InOperandVal);
3167         break;
3168       }
3169
3170       assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3171
3172       // Copy the input into the appropriate registers.
3173       RegsForValue InRegs =
3174         GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3175                              false, true, OutputRegs, InputRegs);
3176       // FIXME: should be match fail.
3177       assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
3178
3179       InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
3180
3181       InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
3182       break;
3183     }
3184     case InlineAsm::isClobber: {
3185       RegsForValue ClobberedRegs =
3186         GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
3187                              OutputRegs, InputRegs);
3188       // Add the clobbered value to the operand list, so that the register
3189       // allocator is aware that the physreg got clobbered.
3190       if (!ClobberedRegs.Regs.empty())
3191         ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
3192       break;
3193     }
3194     }
3195   }
3196
3197   // Finish up input operands.
3198   AsmNodeOperands[0] = Chain;
3199   if (Flag.Val) AsmNodeOperands.push_back(Flag);
3200
3201   Chain = DAG.getNode(ISD::INLINEASM,
3202                       DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
3203                       &AsmNodeOperands[0], AsmNodeOperands.size());
3204   Flag = Chain.getValue(1);
3205
3206   // If this asm returns a register value, copy the result from that register
3207   // and set it as the value of the call.
3208   if (!RetValRegs.Regs.empty())
3209     setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
3210
3211   std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
3212
3213   // Process indirect outputs, first output all of the flagged copies out of
3214   // physregs.
3215   for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
3216     RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
3217     Value *Ptr = IndirectStoresToEmit[i].second;
3218     SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
3219     StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
3220   }
3221
3222   // Emit the non-flagged stores from the physregs.
3223   SmallVector<SDOperand, 8> OutChains;
3224   for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
3225     OutChains.push_back(DAG.getStore(Chain,  StoresToEmit[i].first,
3226                                     getValue(StoresToEmit[i].second),
3227                                     StoresToEmit[i].second, 0));
3228   if (!OutChains.empty())
3229     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3230                         &OutChains[0], OutChains.size());
3231   DAG.setRoot(Chain);
3232 }
3233
3234
3235 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
3236   SDOperand Src = getValue(I.getOperand(0));
3237
3238   MVT::ValueType IntPtr = TLI.getPointerTy();
3239
3240   if (IntPtr < Src.getValueType())
3241     Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
3242   else if (IntPtr > Src.getValueType())
3243     Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
3244
3245   // Scale the source by the type size.
3246   uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
3247   Src = DAG.getNode(ISD::MUL, Src.getValueType(),
3248                     Src, getIntPtrConstant(ElementSize));
3249
3250   TargetLowering::ArgListTy Args;
3251   TargetLowering::ArgListEntry Entry;
3252   Entry.Node = Src;
3253   Entry.Ty = TLI.getTargetData()->getIntPtrType();
3254   Args.push_back(Entry);
3255
3256   std::pair<SDOperand,SDOperand> Result =
3257     TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3258                     DAG.getExternalSymbol("malloc", IntPtr),
3259                     Args, DAG);
3260   setValue(&I, Result.first);  // Pointers always fit in registers
3261   DAG.setRoot(Result.second);
3262 }
3263
3264 void SelectionDAGLowering::visitFree(FreeInst &I) {
3265   TargetLowering::ArgListTy Args;
3266   TargetLowering::ArgListEntry Entry;
3267   Entry.Node = getValue(I.getOperand(0));
3268   Entry.Ty = TLI.getTargetData()->getIntPtrType();
3269   Args.push_back(Entry);
3270   MVT::ValueType IntPtr = TLI.getPointerTy();
3271   std::pair<SDOperand,SDOperand> Result =
3272     TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3273                     DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3274   DAG.setRoot(Result.second);
3275 }
3276
3277 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3278 // mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
3279 // instructions are special in various ways, which require special support to
3280 // insert.  The specified MachineInstr is created but not inserted into any
3281 // basic blocks, and the scheduler passes ownership of it to this method.
3282 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3283                                                        MachineBasicBlock *MBB) {
3284   cerr << "If a target marks an instruction with "
3285        << "'usesCustomDAGSchedInserter', it must implement "
3286        << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3287   abort();
3288   return 0;
3289 }
3290
3291 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3292   DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
3293                           getValue(I.getOperand(1)),
3294                           DAG.getSrcValue(I.getOperand(1))));
3295 }
3296
3297 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3298   SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3299                              getValue(I.getOperand(0)),
3300                              DAG.getSrcValue(I.getOperand(0)));
3301   setValue(&I, V);
3302   DAG.setRoot(V.getValue(1));
3303 }
3304
3305 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3306   DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3307                           getValue(I.getOperand(1)),
3308                           DAG.getSrcValue(I.getOperand(1))));
3309 }
3310
3311 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3312   DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
3313                           getValue(I.getOperand(1)),
3314                           getValue(I.getOperand(2)),
3315                           DAG.getSrcValue(I.getOperand(1)),
3316                           DAG.getSrcValue(I.getOperand(2))));
3317 }
3318
3319 /// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
3320 /// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
3321 static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
3322                                         unsigned &i, SelectionDAG &DAG,
3323                                         TargetLowering &TLI) {
3324   if (TLI.getTypeAction(VT) != TargetLowering::Expand)
3325     return SDOperand(Arg, i++);
3326
3327   MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3328   unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3329   if (NumVals == 1) {
3330     return DAG.getNode(ISD::BIT_CONVERT, VT,
3331                        ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
3332   } else if (NumVals == 2) {
3333     SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3334     SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3335     if (!TLI.isLittleEndian())
3336       std::swap(Lo, Hi);
3337     return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
3338   } else {
3339     // Value scalarized into many values.  Unimp for now.
3340     assert(0 && "Cannot expand i64 -> i16 yet!");
3341   }
3342   return SDOperand();
3343 }
3344
3345 /// TargetLowering::LowerArguments - This is the default LowerArguments
3346 /// implementation, which just inserts a FORMAL_ARGUMENTS node.  FIXME: When all
3347 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
3348 /// integrated into SDISel.
3349 std::vector<SDOperand>
3350 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3351   const FunctionType *FTy = F.getFunctionType();
3352   const ParamAttrsList *Attrs = FTy->getParamAttrs();
3353   // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3354   std::vector<SDOperand> Ops;
3355   Ops.push_back(DAG.getRoot());
3356   Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3357   Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3358
3359   // Add one result value for each formal argument.
3360   std::vector<MVT::ValueType> RetVals;
3361   unsigned j = 1;
3362   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3363        I != E; ++I, ++j) {
3364     MVT::ValueType VT = getValueType(I->getType());
3365     unsigned Flags = ISD::ParamFlags::NoFlagSet;
3366     unsigned OriginalAlignment =
3367       getTargetData()->getABITypeAlignment(I->getType());
3368
3369     // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3370     // that is zero extended!
3371     if (Attrs && Attrs->paramHasAttr(j, ZExtAttribute))
3372       Flags &= ~(ISD::ParamFlags::SExt);
3373     if (Attrs && Attrs->paramHasAttr(j, SExtAttribute))
3374       Flags |= ISD::ParamFlags::SExt;
3375     if (Attrs && Attrs->paramHasAttr(j, InRegAttribute))
3376       Flags |= ISD::ParamFlags::InReg;
3377     if (Attrs && Attrs->paramHasAttr(j, StructRetAttribute))
3378       Flags |= ISD::ParamFlags::StructReturn;
3379     Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3380
3381     switch (getTypeAction(VT)) {
3382     default: assert(0 && "Unknown type action!");
3383     case Legal:
3384       RetVals.push_back(VT);
3385       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3386       break;
3387     case Promote:
3388       RetVals.push_back(getTypeToTransformTo(VT));
3389       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3390       break;
3391     case Expand:
3392       if (VT != MVT::Vector) {
3393         // If this is a large integer, it needs to be broken up into small
3394         // integers.  Figure out what the destination type is and how many small
3395         // integers it turns into.
3396         MVT::ValueType NVT = getTypeToExpandTo(VT);
3397         unsigned NumVals = getNumElements(VT);
3398         for (unsigned i = 0; i != NumVals; ++i) {
3399           RetVals.push_back(NVT);
3400           // if it isn't first piece, alignment must be 1
3401           if (i > 0)
3402             Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3403               (1 << ISD::ParamFlags::OrigAlignmentOffs);
3404           Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3405         }
3406       } else {
3407         // Otherwise, this is a vector type.  We only support legal vectors
3408         // right now.
3409         unsigned NumElems = cast<VectorType>(I->getType())->getNumElements();
3410         const Type *EltTy = cast<VectorType>(I->getType())->getElementType();
3411
3412         // Figure out if there is a Packed type corresponding to this Vector
3413         // type.  If so, convert to the vector type.
3414         MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3415         if (TVT != MVT::Other && isTypeLegal(TVT)) {
3416           RetVals.push_back(TVT);
3417           Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3418         } else {
3419           assert(0 && "Don't support illegal by-val vector arguments yet!");
3420         }
3421       }
3422       break;
3423     }
3424   }
3425
3426   RetVals.push_back(MVT::Other);
3427
3428   // Create the node.
3429   SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3430                                DAG.getNodeValueTypes(RetVals), RetVals.size(),
3431                                &Ops[0], Ops.size()).Val;
3432
3433   DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
3434
3435   // Set up the return result vector.
3436   Ops.clear();
3437   unsigned i = 0;
3438   unsigned Idx = 1;
3439   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
3440       ++I, ++Idx) {
3441     MVT::ValueType VT = getValueType(I->getType());
3442
3443     switch (getTypeAction(VT)) {
3444     default: assert(0 && "Unknown type action!");
3445     case Legal:
3446       Ops.push_back(SDOperand(Result, i++));
3447       break;
3448     case Promote: {
3449       SDOperand Op(Result, i++);
3450       if (MVT::isInteger(VT)) {
3451         if (Attrs && Attrs->paramHasAttr(Idx, SExtAttribute))
3452           Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3453                            DAG.getValueType(VT));
3454         else if (Attrs && Attrs->paramHasAttr(Idx, ZExtAttribute))
3455           Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3456                            DAG.getValueType(VT));
3457         Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3458       } else {
3459         assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3460         Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
3461       }
3462       Ops.push_back(Op);
3463       break;
3464     }
3465     case Expand:
3466       if (VT != MVT::Vector) {
3467         // If this is a large integer or a floating point node that needs to be
3468         // expanded, it needs to be reassembled from small integers.  Figure out
3469         // what the source elt type is and how many small integers it is.
3470         Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
3471       } else {
3472         // Otherwise, this is a vector type.  We only support legal vectors
3473         // right now.
3474         const VectorType *PTy = cast<VectorType>(I->getType());
3475         unsigned NumElems = PTy->getNumElements();
3476         const Type *EltTy = PTy->getElementType();
3477
3478         // Figure out if there is a Packed type corresponding to this Vector
3479         // type.  If so, convert to the vector type.
3480         MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3481         if (TVT != MVT::Other && isTypeLegal(TVT)) {
3482           SDOperand N = SDOperand(Result, i++);
3483           // Handle copies from generic vectors to registers.
3484           N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
3485                           DAG.getConstant(NumElems, MVT::i32),
3486                           DAG.getValueType(getValueType(EltTy)));
3487           Ops.push_back(N);
3488         } else {
3489           assert(0 && "Don't support illegal by-val vector arguments yet!");
3490           abort();
3491         }
3492       }
3493       break;
3494     }
3495   }
3496   return Ops;
3497 }
3498
3499
3500 /// ExpandScalarCallArgs - Recursively expand call argument node by
3501 /// bit_converting it or extract a pair of elements from the larger  node.
3502 static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
3503                                  unsigned Flags,
3504                                  SmallVector<SDOperand, 32> &Ops,
3505                                  SelectionDAG &DAG,
3506                                  TargetLowering &TLI,
3507                                  bool isFirst = true) {
3508
3509   if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
3510     // if it isn't first piece, alignment must be 1
3511     if (!isFirst)
3512       Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3513         (1 << ISD::ParamFlags::OrigAlignmentOffs);
3514     Ops.push_back(Arg);
3515     Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3516     return;
3517   }
3518
3519   MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3520   unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3521   if (NumVals == 1) {
3522     Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
3523     ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI, isFirst);
3524   } else if (NumVals == 2) {
3525     SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3526                                DAG.getConstant(0, TLI.getPointerTy()));
3527     SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3528                                DAG.getConstant(1, TLI.getPointerTy()));
3529     if (!TLI.isLittleEndian())
3530       std::swap(Lo, Hi);
3531     ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI, isFirst);
3532     ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI, false);
3533   } else {
3534     // Value scalarized into many values.  Unimp for now.
3535     assert(0 && "Cannot expand i64 -> i16 yet!");
3536   }
3537 }
3538
3539 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
3540 /// implementation, which just inserts an ISD::CALL node, which is later custom
3541 /// lowered by the target to something concrete.  FIXME: When all targets are
3542 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
3543 std::pair<SDOperand, SDOperand>
3544 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
3545                             bool RetTyIsSigned, bool isVarArg,
3546                             unsigned CallingConv, bool isTailCall,
3547                             SDOperand Callee,
3548                             ArgListTy &Args, SelectionDAG &DAG) {
3549   SmallVector<SDOperand, 32> Ops;
3550   Ops.push_back(Chain);   // Op#0 - Chain
3551   Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
3552   Ops.push_back(DAG.getConstant(isVarArg, getPointerTy()));    // Op#2 - VarArg
3553   Ops.push_back(DAG.getConstant(isTailCall, getPointerTy()));  // Op#3 - Tail
3554   Ops.push_back(Callee);
3555
3556   // Handle all of the outgoing arguments.
3557   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
3558     MVT::ValueType VT = getValueType(Args[i].Ty);
3559     SDOperand Op = Args[i].Node;
3560     unsigned Flags = ISD::ParamFlags::NoFlagSet;
3561     unsigned OriginalAlignment =
3562       getTargetData()->getABITypeAlignment(Args[i].Ty);
3563
3564     if (Args[i].isSExt)
3565       Flags |= ISD::ParamFlags::SExt;
3566     if (Args[i].isZExt)
3567       Flags |= ISD::ParamFlags::ZExt;
3568     if (Args[i].isInReg)
3569       Flags |= ISD::ParamFlags::InReg;
3570     if (Args[i].isSRet)
3571       Flags |= ISD::ParamFlags::StructReturn;
3572     Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
3573
3574     switch (getTypeAction(VT)) {
3575     default: assert(0 && "Unknown type action!");
3576     case Legal:
3577       Ops.push_back(Op);
3578       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3579       break;
3580     case Promote:
3581       if (MVT::isInteger(VT)) {
3582         unsigned ExtOp;
3583         if (Args[i].isSExt)
3584           ExtOp = ISD::SIGN_EXTEND;
3585         else if (Args[i].isZExt)
3586           ExtOp = ISD::ZERO_EXTEND;
3587         else
3588           ExtOp = ISD::ANY_EXTEND;
3589         Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
3590       } else {
3591         assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3592         Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
3593       }
3594       Ops.push_back(Op);
3595       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3596       break;
3597     case Expand:
3598       if (VT != MVT::Vector) {
3599         // If this is a large integer, it needs to be broken down into small
3600         // integers.  Figure out what the source elt type is and how many small
3601         // integers it is.
3602         ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
3603       } else {
3604         // Otherwise, this is a vector type.  We only support legal vectors
3605         // right now.
3606         const VectorType *PTy = cast<VectorType>(Args[i].Ty);
3607         unsigned NumElems = PTy->getNumElements();
3608         const Type *EltTy = PTy->getElementType();
3609
3610         // Figure out if there is a Packed type corresponding to this Vector
3611         // type.  If so, convert to the vector type.
3612         MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3613         if (TVT != MVT::Other && isTypeLegal(TVT)) {
3614           // Insert a VBIT_CONVERT of the MVT::Vector type to the vector type.
3615           Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
3616           Ops.push_back(Op);
3617           Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3618         } else {
3619           assert(0 && "Don't support illegal by-val vector call args yet!");
3620           abort();
3621         }
3622       }
3623       break;
3624     }
3625   }
3626
3627   // Figure out the result value types.
3628   SmallVector<MVT::ValueType, 4> RetTys;
3629
3630   if (RetTy != Type::VoidTy) {
3631     MVT::ValueType VT = getValueType(RetTy);
3632     switch (getTypeAction(VT)) {
3633     default: assert(0 && "Unknown type action!");
3634     case Legal:
3635       RetTys.push_back(VT);
3636       break;
3637     case Promote:
3638       RetTys.push_back(getTypeToTransformTo(VT));
3639       break;
3640     case Expand:
3641       if (VT != MVT::Vector) {
3642         // If this is a large integer, it needs to be reassembled from small
3643         // integers.  Figure out what the source elt type is and how many small
3644         // integers it is.
3645         MVT::ValueType NVT = getTypeToExpandTo(VT);
3646         unsigned NumVals = getNumElements(VT);
3647         for (unsigned i = 0; i != NumVals; ++i)
3648           RetTys.push_back(NVT);
3649       } else {
3650         // Otherwise, this is a vector type.  We only support legal vectors
3651         // right now.
3652         const VectorType *PTy = cast<VectorType>(RetTy);
3653         unsigned NumElems = PTy->getNumElements();
3654         const Type *EltTy = PTy->getElementType();
3655
3656         // Figure out if there is a Packed type corresponding to this Vector
3657         // type.  If so, convert to the vector type.
3658         MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3659         if (TVT != MVT::Other && isTypeLegal(TVT)) {
3660           RetTys.push_back(TVT);
3661         } else {
3662           assert(0 && "Don't support illegal by-val vector call results yet!");
3663           abort();
3664         }
3665       }
3666     }
3667   }
3668
3669   RetTys.push_back(MVT::Other);  // Always has a chain.
3670
3671   // Finally, create the CALL node.
3672   SDOperand Res = DAG.getNode(ISD::CALL,
3673                               DAG.getVTList(&RetTys[0], RetTys.size()),
3674                               &Ops[0], Ops.size());
3675
3676   // This returns a pair of operands.  The first element is the
3677   // return value for the function (if RetTy is not VoidTy).  The second
3678   // element is the outgoing token chain.
3679   SDOperand ResVal;
3680   if (RetTys.size() != 1) {
3681     MVT::ValueType VT = getValueType(RetTy);
3682     if (RetTys.size() == 2) {
3683       ResVal = Res;
3684
3685       // If this value was promoted, truncate it down.
3686       if (ResVal.getValueType() != VT) {
3687         if (VT == MVT::Vector) {
3688           // Insert a VBIT_CONVERT to convert from the packed result type to the
3689           // MVT::Vector type.
3690           unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
3691           const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
3692
3693           // Figure out if there is a Packed type corresponding to this Vector
3694           // type.  If so, convert to the vector type.
3695           MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
3696           if (TVT != MVT::Other && isTypeLegal(TVT)) {
3697             // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
3698             // "N x PTyElementVT" MVT::Vector type.
3699             ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
3700                                  DAG.getConstant(NumElems, MVT::i32),
3701                                  DAG.getValueType(getValueType(EltTy)));
3702           } else {
3703             abort();
3704           }
3705         } else if (MVT::isInteger(VT)) {
3706           unsigned AssertOp = ISD::AssertSext;
3707           if (!RetTyIsSigned)
3708             AssertOp = ISD::AssertZext;
3709           ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
3710                                DAG.getValueType(VT));
3711           ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
3712         } else {
3713           assert(MVT::isFloatingPoint(VT));
3714           if (getTypeAction(VT) == Expand)
3715             ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
3716           else
3717             ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
3718         }
3719       }
3720     } else if (RetTys.size() == 3) {
3721       ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
3722                            Res.getValue(0), Res.getValue(1));
3723
3724     } else {
3725       assert(0 && "Case not handled yet!");
3726     }
3727   }
3728
3729   return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
3730 }
3731
3732 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
3733   assert(0 && "LowerOperation not implemented for this target!");
3734   abort();
3735   return SDOperand();
3736 }
3737
3738 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
3739                                                  SelectionDAG &DAG) {
3740   assert(0 && "CustomPromoteOperation not implemented for this target!");
3741   abort();
3742   return SDOperand();
3743 }
3744
3745 /// getMemsetValue - Vectorized representation of the memset value
3746 /// operand.
3747 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
3748                                 SelectionDAG &DAG) {
3749   MVT::ValueType CurVT = VT;
3750   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3751     uint64_t Val   = C->getValue() & 255;
3752     unsigned Shift = 8;
3753     while (CurVT != MVT::i8) {
3754       Val = (Val << Shift) | Val;
3755       Shift <<= 1;
3756       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3757     }
3758     return DAG.getConstant(Val, VT);
3759   } else {
3760     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
3761     unsigned Shift = 8;
3762     while (CurVT != MVT::i8) {
3763       Value =
3764         DAG.getNode(ISD::OR, VT,
3765                     DAG.getNode(ISD::SHL, VT, Value,
3766                                 DAG.getConstant(Shift, MVT::i8)), Value);
3767       Shift <<= 1;
3768       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3769     }
3770
3771     return Value;
3772   }
3773 }
3774
3775 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3776 /// used when a memcpy is turned into a memset when the source is a constant
3777 /// string ptr.
3778 static SDOperand getMemsetStringVal(MVT::ValueType VT,
3779                                     SelectionDAG &DAG, TargetLowering &TLI,
3780                                     std::string &Str, unsigned Offset) {
3781   uint64_t Val = 0;
3782   unsigned MSB = getSizeInBits(VT) / 8;
3783   if (TLI.isLittleEndian())
3784     Offset = Offset + MSB - 1;
3785   for (unsigned i = 0; i != MSB; ++i) {
3786     Val = (Val << 8) | (unsigned char)Str[Offset];
3787     Offset += TLI.isLittleEndian() ? -1 : 1;
3788   }
3789   return DAG.getConstant(Val, VT);
3790 }
3791
3792 /// getMemBasePlusOffset - Returns base and offset node for the
3793 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
3794                                       SelectionDAG &DAG, TargetLowering &TLI) {
3795   MVT::ValueType VT = Base.getValueType();
3796   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
3797 }
3798
3799 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
3800 /// to replace the memset / memcpy is below the threshold. It also returns the
3801 /// types of the sequence of  memory ops to perform memset / memcpy.
3802 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
3803                                      unsigned Limit, uint64_t Size,
3804                                      unsigned Align, TargetLowering &TLI) {
3805   MVT::ValueType VT;
3806
3807   if (TLI.allowsUnalignedMemoryAccesses()) {
3808     VT = MVT::i64;
3809   } else {
3810     switch (Align & 7) {
3811     case 0:
3812       VT = MVT::i64;
3813       break;
3814     case 4:
3815       VT = MVT::i32;
3816       break;
3817     case 2:
3818       VT = MVT::i16;
3819       break;
3820     default:
3821       VT = MVT::i8;
3822       break;
3823     }
3824   }
3825
3826   MVT::ValueType LVT = MVT::i64;
3827   while (!TLI.isTypeLegal(LVT))
3828     LVT = (MVT::ValueType)((unsigned)LVT - 1);
3829   assert(MVT::isInteger(LVT));
3830
3831   if (VT > LVT)
3832     VT = LVT;
3833
3834   unsigned NumMemOps = 0;
3835   while (Size != 0) {
3836     unsigned VTSize = getSizeInBits(VT) / 8;
3837     while (VTSize > Size) {
3838       VT = (MVT::ValueType)((unsigned)VT - 1);
3839       VTSize >>= 1;
3840     }
3841     assert(MVT::isInteger(VT));
3842
3843     if (++NumMemOps > Limit)
3844       return false;
3845     MemOps.push_back(VT);
3846     Size -= VTSize;
3847   }
3848
3849   return true;
3850 }
3851
3852 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
3853   SDOperand Op1 = getValue(I.getOperand(1));
3854   SDOperand Op2 = getValue(I.getOperand(2));
3855   SDOperand Op3 = getValue(I.getOperand(3));
3856   SDOperand Op4 = getValue(I.getOperand(4));
3857   unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
3858   if (Align == 0) Align = 1;
3859
3860   if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
3861     std::vector<MVT::ValueType> MemOps;
3862
3863     // Expand memset / memcpy to a series of load / store ops
3864     // if the size operand falls below a certain threshold.
3865     SmallVector<SDOperand, 8> OutChains;
3866     switch (Op) {
3867     default: break;  // Do nothing for now.
3868     case ISD::MEMSET: {
3869       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
3870                                    Size->getValue(), Align, TLI)) {
3871         unsigned NumMemOps = MemOps.size();
3872         unsigned Offset = 0;
3873         for (unsigned i = 0; i < NumMemOps; i++) {
3874           MVT::ValueType VT = MemOps[i];
3875           unsigned VTSize = getSizeInBits(VT) / 8;
3876           SDOperand Value = getMemsetValue(Op2, VT, DAG);
3877           SDOperand Store = DAG.getStore(getRoot(), Value,
3878                                     getMemBasePlusOffset(Op1, Offset, DAG, TLI),
3879                                          I.getOperand(1), Offset);
3880           OutChains.push_back(Store);
3881           Offset += VTSize;
3882         }
3883       }
3884       break;
3885     }
3886     case ISD::MEMCPY: {
3887       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
3888                                    Size->getValue(), Align, TLI)) {
3889         unsigned NumMemOps = MemOps.size();
3890         unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
3891         GlobalAddressSDNode *G = NULL;
3892         std::string Str;
3893         bool CopyFromStr = false;
3894
3895         if (Op2.getOpcode() == ISD::GlobalAddress)
3896           G = cast<GlobalAddressSDNode>(Op2);
3897         else if (Op2.getOpcode() == ISD::ADD &&
3898                  Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3899                  Op2.getOperand(1).getOpcode() == ISD::Constant) {
3900           G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
3901           SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
3902         }
3903         if (G) {
3904           GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3905           if (GV && GV->isConstant()) {
3906             Str = GV->getStringValue(false);
3907             if (!Str.empty()) {
3908               CopyFromStr = true;
3909               SrcOff += SrcDelta;
3910             }
3911           }
3912         }
3913
3914         for (unsigned i = 0; i < NumMemOps; i++) {
3915           MVT::ValueType VT = MemOps[i];
3916           unsigned VTSize = getSizeInBits(VT) / 8;
3917           SDOperand Value, Chain, Store;
3918
3919           if (CopyFromStr) {
3920             Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
3921             Chain = getRoot();
3922             Store =
3923               DAG.getStore(Chain, Value,
3924                            getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3925                            I.getOperand(1), DstOff);
3926           } else {
3927             Value = DAG.getLoad(VT, getRoot(),
3928                         getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
3929                         I.getOperand(2), SrcOff);
3930             Chain = Value.getValue(1);
3931             Store =
3932               DAG.getStore(Chain, Value,
3933                            getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3934                            I.getOperand(1), DstOff);
3935           }
3936           OutChains.push_back(Store);
3937           SrcOff += VTSize;
3938           DstOff += VTSize;
3939         }
3940       }
3941       break;
3942     }
3943     }
3944
3945     if (!OutChains.empty()) {
3946       DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
3947                   &OutChains[0], OutChains.size()));
3948       return;
3949     }
3950   }
3951
3952   DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
3953 }
3954
3955 //===----------------------------------------------------------------------===//
3956 // SelectionDAGISel code
3957 //===----------------------------------------------------------------------===//
3958
3959 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
3960   return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
3961 }
3962
3963 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
3964   AU.addRequired<AliasAnalysis>();
3965   AU.setPreservesAll();
3966 }
3967
3968
3969
3970 bool SelectionDAGISel::runOnFunction(Function &Fn) {
3971   MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
3972   RegMap = MF.getSSARegMap();
3973   DOUT << "\n\n\n=== " << Fn.getName() << "\n";
3974
3975   FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
3976
3977   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
3978     SelectBasicBlock(I, MF, FuncInfo);
3979
3980   // Add function live-ins to entry block live-in set.
3981   BasicBlock *EntryBB = &Fn.getEntryBlock();
3982   BB = FuncInfo.MBBMap[EntryBB];
3983   if (!MF.livein_empty())
3984     for (MachineFunction::livein_iterator I = MF.livein_begin(),
3985            E = MF.livein_end(); I != E; ++I)
3986       BB->addLiveIn(I->first);
3987
3988   return true;
3989 }
3990
3991 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V,
3992                                                            unsigned Reg) {
3993   SDOperand Op = getValue(V);
3994   assert((Op.getOpcode() != ISD::CopyFromReg ||
3995           cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
3996          "Copy from a reg to the same reg!");
3997
3998   // If this type is not legal, we must make sure to not create an invalid
3999   // register use.
4000   MVT::ValueType SrcVT = Op.getValueType();
4001   MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
4002   if (SrcVT == DestVT) {
4003     return DAG.getCopyToReg(getRoot(), Reg, Op);
4004   } else if (SrcVT == MVT::Vector) {
4005     // Handle copies from generic vectors to registers.
4006     MVT::ValueType PTyElementVT, PTyLegalElementVT;
4007     unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
4008                                              PTyElementVT, PTyLegalElementVT);
4009
4010     // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
4011     // MVT::Vector type.
4012     Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
4013                      DAG.getConstant(NE, MVT::i32),
4014                      DAG.getValueType(PTyElementVT));
4015
4016     // Loop over all of the elements of the resultant vector,
4017     // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
4018     // copying them into output registers.
4019     SmallVector<SDOperand, 8> OutChains;
4020     SDOperand Root = getRoot();
4021     for (unsigned i = 0; i != NE; ++i) {
4022       SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
4023                                   Op, DAG.getConstant(i, TLI.getPointerTy()));
4024       if (PTyElementVT == PTyLegalElementVT) {
4025         // Elements are legal.
4026         OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4027       } else if (PTyLegalElementVT > PTyElementVT) {
4028         // Elements are promoted.
4029         if (MVT::isFloatingPoint(PTyLegalElementVT))
4030           Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
4031         else
4032           Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
4033         OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4034       } else {
4035         // Elements are expanded.
4036         // The src value is expanded into multiple registers.
4037         SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4038                                    Elt, DAG.getConstant(0, TLI.getPointerTy()));
4039         SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4040                                    Elt, DAG.getConstant(1, TLI.getPointerTy()));
4041         OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
4042         OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
4043       }
4044     }
4045     return DAG.getNode(ISD::TokenFactor, MVT::Other,
4046                        &OutChains[0], OutChains.size());
4047   } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
4048     // The src value is promoted to the register.
4049     if (MVT::isFloatingPoint(SrcVT))
4050       Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
4051     else
4052       Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
4053     return DAG.getCopyToReg(getRoot(), Reg, Op);
4054   } else  {
4055     DestVT = TLI.getTypeToExpandTo(SrcVT);
4056     unsigned NumVals = TLI.getNumElements(SrcVT);
4057     if (NumVals == 1)
4058       return DAG.getCopyToReg(getRoot(), Reg,
4059                               DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
4060     assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
4061     // The src value is expanded into multiple registers.
4062     SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4063                                Op, DAG.getConstant(0, TLI.getPointerTy()));
4064     SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4065                                Op, DAG.getConstant(1, TLI.getPointerTy()));
4066     Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
4067     return DAG.getCopyToReg(Op, Reg+1, Hi);
4068   }
4069 }
4070
4071 void SelectionDAGISel::
4072 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
4073                std::vector<SDOperand> &UnorderedChains) {
4074   // If this is the entry block, emit arguments.
4075   Function &F = *LLVMBB->getParent();
4076   FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4077   SDOperand OldRoot = SDL.DAG.getRoot();
4078   std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
4079
4080   unsigned a = 0;
4081   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4082        AI != E; ++AI, ++a)
4083     if (!AI->use_empty()) {
4084       SDL.setValue(AI, Args[a]);
4085
4086       // If this argument is live outside of the entry block, insert a copy from
4087       // whereever we got it to the vreg that other BB's will reference it as.
4088       DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4089       if (VMI != FuncInfo.ValueMap.end()) {
4090         SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
4091         UnorderedChains.push_back(Copy);
4092       }
4093     }
4094
4095   // Finally, if the target has anything special to do, allow it to do so.
4096   // FIXME: this should insert code into the DAG!
4097   EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4098 }
4099
4100 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
4101        std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
4102                                          FunctionLoweringInfo &FuncInfo) {
4103   SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
4104
4105   std::vector<SDOperand> UnorderedChains;
4106
4107   // Lower any arguments needed in this block if this is the entry block.
4108   if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
4109     LowerArguments(LLVMBB, SDL, UnorderedChains);
4110
4111   BB = FuncInfo.MBBMap[LLVMBB];
4112   SDL.setCurrentBasicBlock(BB);
4113
4114   // Lower all of the non-terminator instructions.
4115   for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
4116        I != E; ++I)
4117     SDL.visit(*I);
4118
4119   // Lower call part of invoke.
4120   InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
4121   if (Invoke) SDL.visitInvoke(*Invoke, false);
4122
4123   // Ensure that all instructions which are used outside of their defining
4124   // blocks are available as virtual registers.
4125   for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
4126     if (!I->use_empty() && !isa<PHINode>(I)) {
4127       DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4128       if (VMI != FuncInfo.ValueMap.end())
4129         UnorderedChains.push_back(
4130                                 SDL.CopyValueToVirtualRegister(I, VMI->second));
4131     }
4132
4133   // Handle PHI nodes in successor blocks.  Emit code into the SelectionDAG to
4134   // ensure constants are generated when needed.  Remember the virtual registers
4135   // that need to be added to the Machine PHI nodes as input.  We cannot just
4136   // directly add them, because expansion might result in multiple MBB's for one
4137   // BB.  As such, the start of the BB might correspond to a different MBB than
4138   // the end.
4139   //
4140   TerminatorInst *TI = LLVMBB->getTerminator();
4141
4142   // Emit constants only once even if used by multiple PHI nodes.
4143   std::map<Constant*, unsigned> ConstantsOut;
4144
4145   // Vector bool would be better, but vector<bool> is really slow.
4146   std::vector<unsigned char> SuccsHandled;
4147   if (TI->getNumSuccessors())
4148     SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4149
4150   // Check successor nodes PHI nodes that expect a constant to be available from
4151   // this block.
4152   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4153     BasicBlock *SuccBB = TI->getSuccessor(succ);
4154     if (!isa<PHINode>(SuccBB->begin())) continue;
4155     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4156
4157     // If this terminator has multiple identical successors (common for
4158     // switches), only handle each succ once.
4159     unsigned SuccMBBNo = SuccMBB->getNumber();
4160     if (SuccsHandled[SuccMBBNo]) continue;
4161     SuccsHandled[SuccMBBNo] = true;
4162
4163     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4164     PHINode *PN;
4165
4166     // At this point we know that there is a 1-1 correspondence between LLVM PHI
4167     // nodes and Machine PHI nodes, but the incoming operands have not been
4168     // emitted yet.
4169     for (BasicBlock::iterator I = SuccBB->begin();
4170          (PN = dyn_cast<PHINode>(I)); ++I) {
4171       // Ignore dead phi's.
4172       if (PN->use_empty()) continue;
4173
4174       unsigned Reg;
4175       Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4176
4177       if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4178         unsigned &RegOut = ConstantsOut[C];
4179         if (RegOut == 0) {
4180           RegOut = FuncInfo.CreateRegForValue(C);
4181           UnorderedChains.push_back(
4182                            SDL.CopyValueToVirtualRegister(C, RegOut));
4183         }
4184         Reg = RegOut;
4185       } else {
4186         Reg = FuncInfo.ValueMap[PHIOp];
4187         if (Reg == 0) {
4188           assert(isa<AllocaInst>(PHIOp) &&
4189                  FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4190                  "Didn't codegen value into a register!??");
4191           Reg = FuncInfo.CreateRegForValue(PHIOp);
4192           UnorderedChains.push_back(
4193                            SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4194         }
4195       }
4196
4197       // Remember that this register needs to added to the machine PHI node as
4198       // the input for this MBB.
4199       MVT::ValueType VT = TLI.getValueType(PN->getType());
4200       unsigned NumElements;
4201       if (VT != MVT::Vector)
4202         NumElements = TLI.getNumElements(VT);
4203       else {
4204         MVT::ValueType VT1,VT2;
4205         NumElements =
4206           TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
4207                                      VT1, VT2);
4208       }
4209       for (unsigned i = 0, e = NumElements; i != e; ++i)
4210         PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4211     }
4212   }
4213   ConstantsOut.clear();
4214
4215   // Turn all of the unordered chains into one factored node.
4216   if (!UnorderedChains.empty()) {
4217     SDOperand Root = SDL.getRoot();
4218     if (Root.getOpcode() != ISD::EntryToken) {
4219       unsigned i = 0, e = UnorderedChains.size();
4220       for (; i != e; ++i) {
4221         assert(UnorderedChains[i].Val->getNumOperands() > 1);
4222         if (UnorderedChains[i].Val->getOperand(0) == Root)
4223           break;  // Don't add the root if we already indirectly depend on it.
4224       }
4225
4226       if (i == e)
4227         UnorderedChains.push_back(Root);
4228     }
4229     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4230                             &UnorderedChains[0], UnorderedChains.size()));
4231   }
4232
4233   // Lower the terminator after the copies are emitted.
4234   if (Invoke) {
4235     // Just the branch part of invoke.
4236     SDL.visitInvoke(*Invoke, true);
4237   } else {
4238     SDL.visit(*LLVMBB->getTerminator());
4239   }
4240
4241   // Copy over any CaseBlock records that may now exist due to SwitchInst
4242   // lowering, as well as any jump table information.
4243   SwitchCases.clear();
4244   SwitchCases = SDL.SwitchCases;
4245   JTCases.clear();
4246   JTCases = SDL.JTCases;
4247
4248   // Make sure the root of the DAG is up-to-date.
4249   DAG.setRoot(SDL.getRoot());
4250 }
4251
4252 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4253   // Get alias analysis for load/store combining.
4254   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
4255
4256   // Run the DAG combiner in pre-legalize mode.
4257   DAG.Combine(false, AA);
4258
4259   DOUT << "Lowered selection DAG:\n";
4260   DEBUG(DAG.dump());
4261
4262   // Second step, hack on the DAG until it only uses operations and types that
4263   // the target supports.
4264   DAG.Legalize();
4265
4266   DOUT << "Legalized selection DAG:\n";
4267   DEBUG(DAG.dump());
4268
4269   // Run the DAG combiner in post-legalize mode.
4270   DAG.Combine(true, AA);
4271
4272   if (ViewISelDAGs) DAG.viewGraph();
4273
4274   // Third, instruction select all of the operations to machine code, adding the
4275   // code to the MachineBasicBlock.
4276   InstructionSelectBasicBlock(DAG);
4277
4278   DOUT << "Selected machine code:\n";
4279   DEBUG(BB->dump());
4280 }
4281
4282 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4283                                         FunctionLoweringInfo &FuncInfo) {
4284   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4285   {
4286     SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4287     CurDAG = &DAG;
4288
4289     // First step, lower LLVM code to some DAG.  This DAG may use operations and
4290     // types that are not supported by the target.
4291     BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4292
4293     // Second step, emit the lowered DAG as machine code.
4294     CodeGenAndEmitDAG(DAG);
4295   }
4296
4297   // Next, now that we know what the last MBB the LLVM BB expanded is, update
4298   // PHI nodes in successors.
4299   if (SwitchCases.empty() && JTCases.empty()) {
4300     for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4301       MachineInstr *PHI = PHINodesToUpdate[i].first;
4302       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4303              "This is not a machine PHI node that we are updating!");
4304       PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4305       PHI->addMachineBasicBlockOperand(BB);
4306     }
4307     return;
4308   }
4309
4310   // If the JumpTable record is filled in, then we need to emit a jump table.
4311   // Updating the PHI nodes is tricky in this case, since we need to determine
4312   // whether the PHI is a successor of the range check MBB or the jump table MBB
4313   for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
4314     // Lower header first, if it wasn't already lowered
4315     if (!JTCases[i].first.Emitted) {
4316       SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4317       CurDAG = &HSDAG;
4318       SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
4319       // Set the current basic block to the mbb we wish to insert the code into
4320       BB = JTCases[i].first.HeaderBB;
4321       HSDL.setCurrentBasicBlock(BB);
4322       // Emit the code
4323       HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
4324       HSDAG.setRoot(HSDL.getRoot());
4325       CodeGenAndEmitDAG(HSDAG);
4326     }
4327
4328     SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4329     CurDAG = &JSDAG;
4330     SelectionDAGLowering JSDL(JSDAG, TLI, FuncInfo);
4331     // Set the current basic block to the mbb we wish to insert the code into
4332     BB = JTCases[i].second.MBB;
4333     JSDL.setCurrentBasicBlock(BB);
4334     // Emit the code
4335     JSDL.visitJumpTable(JTCases[i].second);
4336     JSDAG.setRoot(JSDL.getRoot());
4337     CodeGenAndEmitDAG(JSDAG);
4338
4339     // Update PHI Nodes
4340     for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4341       MachineInstr *PHI = PHINodesToUpdate[pi].first;
4342       MachineBasicBlock *PHIBB = PHI->getParent();
4343       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4344              "This is not a machine PHI node that we are updating!");
4345       if (PHIBB == JTCases[i].second.Default) {
4346         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4347         PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
4348       }
4349       if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4350         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4351         PHI->addMachineBasicBlockOperand(BB);
4352       }
4353     }
4354   }
4355
4356   // If the switch block involved a branch to one of the actual successors, we
4357   // need to update PHI nodes in that block.
4358   for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4359     MachineInstr *PHI = PHINodesToUpdate[i].first;
4360     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4361            "This is not a machine PHI node that we are updating!");
4362     if (BB->isSuccessor(PHI->getParent())) {
4363       PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4364       PHI->addMachineBasicBlockOperand(BB);
4365     }
4366   }
4367
4368   // If we generated any switch lowering information, build and codegen any
4369   // additional DAGs necessary.
4370   for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4371     SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4372     CurDAG = &SDAG;
4373     SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4374
4375     // Set the current basic block to the mbb we wish to insert the code into
4376     BB = SwitchCases[i].ThisBB;
4377     SDL.setCurrentBasicBlock(BB);
4378
4379     // Emit the code
4380     SDL.visitSwitchCase(SwitchCases[i]);
4381     SDAG.setRoot(SDL.getRoot());
4382     CodeGenAndEmitDAG(SDAG);
4383
4384     // Handle any PHI nodes in successors of this chunk, as if we were coming
4385     // from the original BB before switch expansion.  Note that PHI nodes can
4386     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
4387     // handle them the right number of times.
4388     while ((BB = SwitchCases[i].TrueBB)) {  // Handle LHS and RHS.
4389       for (MachineBasicBlock::iterator Phi = BB->begin();
4390            Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4391         // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4392         for (unsigned pn = 0; ; ++pn) {
4393           assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4394           if (PHINodesToUpdate[pn].first == Phi) {
4395             Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4396             Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4397             break;
4398           }
4399         }
4400       }
4401
4402       // Don't process RHS if same block as LHS.
4403       if (BB == SwitchCases[i].FalseBB)
4404         SwitchCases[i].FalseBB = 0;
4405
4406       // If we haven't handled the RHS, do so now.  Otherwise, we're done.
4407       SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4408       SwitchCases[i].FalseBB = 0;
4409     }
4410     assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4411   }
4412 }
4413
4414
4415 //===----------------------------------------------------------------------===//
4416 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4417 /// target node in the graph.
4418 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4419   if (ViewSchedDAGs) DAG.viewGraph();
4420
4421   RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4422
4423   if (!Ctor) {
4424     Ctor = ISHeuristic;
4425     RegisterScheduler::setDefault(Ctor);
4426   }
4427
4428   ScheduleDAG *SL = Ctor(this, &DAG, BB);
4429   BB = SL->Run();
4430   delete SL;
4431 }
4432
4433
4434 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4435   return new HazardRecognizer();
4436 }
4437
4438 //===----------------------------------------------------------------------===//
4439 // Helper functions used by the generated instruction selector.
4440 //===----------------------------------------------------------------------===//
4441 // Calls to these methods are generated by tblgen.
4442
4443 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
4444 /// the dag combiner simplified the 255, we still want to match.  RHS is the
4445 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
4446 /// specified in the .td file (e.g. 255).
4447 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
4448                                     int64_t DesiredMaskS) {
4449   uint64_t ActualMask = RHS->getValue();
4450   uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4451
4452   // If the actual mask exactly matches, success!
4453   if (ActualMask == DesiredMask)
4454     return true;
4455
4456   // If the actual AND mask is allowing unallowed bits, this doesn't match.
4457   if (ActualMask & ~DesiredMask)
4458     return false;
4459
4460   // Otherwise, the DAG Combiner may have proven that the value coming in is
4461   // either already zero or is not demanded.  Check for known zero input bits.
4462   uint64_t NeededMask = DesiredMask & ~ActualMask;
4463   if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
4464     return true;
4465
4466   // TODO: check to see if missing bits are just not demanded.
4467
4468   // Otherwise, this pattern doesn't match.
4469   return false;
4470 }
4471
4472 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
4473 /// the dag combiner simplified the 255, we still want to match.  RHS is the
4474 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
4475 /// specified in the .td file (e.g. 255).
4476 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
4477                                     int64_t DesiredMaskS) {
4478   uint64_t ActualMask = RHS->getValue();
4479   uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4480
4481   // If the actual mask exactly matches, success!
4482   if (ActualMask == DesiredMask)
4483     return true;
4484
4485   // If the actual AND mask is allowing unallowed bits, this doesn't match.
4486   if (ActualMask & ~DesiredMask)
4487     return false;
4488
4489   // Otherwise, the DAG Combiner may have proven that the value coming in is
4490   // either already zero or is not demanded.  Check for known zero input bits.
4491   uint64_t NeededMask = DesiredMask & ~ActualMask;
4492
4493   uint64_t KnownZero, KnownOne;
4494   getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
4495
4496   // If all the missing bits in the or are already known to be set, match!
4497   if ((NeededMask & KnownOne) == NeededMask)
4498     return true;
4499
4500   // TODO: check to see if missing bits are just not demanded.
4501
4502   // Otherwise, this pattern doesn't match.
4503   return false;
4504 }
4505
4506
4507 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
4508 /// by tblgen.  Others should not call it.
4509 void SelectionDAGISel::
4510 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
4511   std::vector<SDOperand> InOps;
4512   std::swap(InOps, Ops);
4513
4514   Ops.push_back(InOps[0]);  // input chain.
4515   Ops.push_back(InOps[1]);  // input asm string.
4516
4517   unsigned i = 2, e = InOps.size();
4518   if (InOps[e-1].getValueType() == MVT::Flag)
4519     --e;  // Don't process a flag operand if it is here.
4520
4521   while (i != e) {
4522     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
4523     if ((Flags & 7) != 4 /*MEM*/) {
4524       // Just skip over this operand, copying the operands verbatim.
4525       Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
4526       i += (Flags >> 3) + 1;
4527     } else {
4528       assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
4529       // Otherwise, this is a memory operand.  Ask the target to select it.
4530       std::vector<SDOperand> SelOps;
4531       if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
4532         cerr << "Could not match memory address.  Inline asm failure!\n";
4533         exit(1);
4534       }
4535
4536       // Add this to the output node.
4537       MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
4538       Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
4539                                           IntPtrTy));
4540       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
4541       i += 2;
4542     }
4543   }
4544
4545   // Add the flag input back if present.
4546   if (e != InOps.size())
4547     Ops.push_back(InOps.back());
4548 }