lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

   1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Collector.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineFrameInfo.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  34 #include "llvm/CodeGen/MachineModuleInfo.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/SchedulerRegistry.h"
  37 #include "llvm/CodeGen/SelectionDAG.h"
  38 #include "llvm/Target/TargetRegisterInfo.h"
  39 #include "llvm/Target/TargetData.h"
  40 #include "llvm/Target/TargetFrameInfo.h"
  41 #include "llvm/Target/TargetInstrInfo.h"
  42 #include "llvm/Target/TargetLowering.h"
  43 #include "llvm/Target/TargetMachine.h"
  44 #include "llvm/Target/TargetOptions.h"
  45 #include "llvm/Support/Compiler.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Support/MathExtras.h"
  48 #include "llvm/Support/Timer.h"
  49 #include <algorithm>
  50 using namespace llvm;
  51
  52 static cl::opt<bool>
  53 EnableValueProp("enable-value-prop", cl::Hidden);
  54 static cl::opt<bool>
  55 EnableLegalizeTypes("enable-legalize-types", cl::Hidden);
  56
  57
  58 #ifndef NDEBUG
  59 static cl::opt<bool>
  60 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
  61           cl::desc("Pop up a window to show dags before the first "
  62                    "dag combine pass"));
  63 static cl::opt<bool>
  64 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
  65           cl::desc("Pop up a window to show dags before legalize types"));
  66 static cl::opt<bool>
  67 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
  68           cl::desc("Pop up a window to show dags before legalize"));
  69 static cl::opt<bool>
  70 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
  71           cl::desc("Pop up a window to show dags before the second "
  72                    "dag combine pass"));
  73 static cl::opt<bool>
  74 ViewISelDAGs("view-isel-dags", cl::Hidden,
  75           cl::desc("Pop up a window to show isel dags as they are selected"));
  76 static cl::opt<bool>
  77 ViewSchedDAGs("view-sched-dags", cl::Hidden,
  78           cl::desc("Pop up a window to show sched dags as they are processed"));
  79 static cl::opt<bool>
  80 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
  81       cl::desc("Pop up a window to show SUnit dags after they are processed"));
  82 #else
  83 static const bool ViewDAGCombine1 = false,
  84                   ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
  85                   ViewDAGCombine2 = false,
  86                   ViewISelDAGs = false, ViewSchedDAGs = false,
  87                   ViewSUnitDAGs = false;
  88 #endif
  89
  90 //===---------------------------------------------------------------------===//
  91 ///
  92 /// RegisterScheduler class - Track the registration of instruction schedulers.
  93 ///
  94 //===---------------------------------------------------------------------===//
  95 MachinePassRegistry RegisterScheduler::Registry;
  96
  97 //===---------------------------------------------------------------------===//
  98 ///
  99 /// ISHeuristic command line option for instruction schedulers.
 100 ///
 101 //===---------------------------------------------------------------------===//
 102 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
 103                RegisterPassParser<RegisterScheduler> >
 104 ISHeuristic("pre-RA-sched",
 105             cl::init(&createDefaultScheduler),
 106             cl::desc("Instruction schedulers available (before register"
 107                      " allocation):"));
 108
 109 static RegisterScheduler
 110 defaultListDAGScheduler("default", "  Best scheduler for the target",
 111                         createDefaultScheduler);
 112
 113 namespace { struct SDISelAsmOperandInfo; }
 114
 115 /// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence
 116 /// insertvalue or extractvalue indices that identify a member, return
 117 /// the linearized index of the start of the member.
 118 ///
 119 static unsigned ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty,
 120                                    const unsigned *Indices,
 121                                    const unsigned *IndicesEnd,
 122                                    unsigned CurIndex = 0) {
 123   // Base case: We're done.
 124   if (Indices && Indices == IndicesEnd)
 125     return CurIndex;
 126
 127   // Given a struct type, recursively traverse the elements.
 128   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 129     for (StructType::element_iterator EB = STy->element_begin(),
 130                                       EI = EB,
 131                                       EE = STy->element_end();
 132         EI != EE; ++EI) {
 133       if (Indices && *Indices == unsigned(EI - EB))
 134         return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex);
 135       CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex);
 136     }
 137   }
 138   // Given an array type, recursively traverse the elements.
 139   else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 140     const Type *EltTy = ATy->getElementType();
 141     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
 142       if (Indices && *Indices == i)
 143         return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex);
 144       CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex);
 145     }
 146   }
 147   // We haven't found the type we're looking for, so keep searching.
 148   return CurIndex + 1;
 149 }
 150
 151 /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
 152 /// MVTs that represent all the individual underlying
 153 /// non-aggregate types that comprise it.
 154 ///
 155 /// If Offsets is non-null, it points to a vector to be filled in
 156 /// with the in-memory offsets of each of the individual values.
 157 ///
 158 static void ComputeValueVTs(const TargetLowering &TLI, const Type *Ty,
 159                             SmallVectorImpl<MVT> &ValueVTs,
 160                             SmallVectorImpl<uint64_t> *Offsets = 0,
 161                             uint64_t StartingOffset = 0) {
 162   // Given a struct type, recursively traverse the elements.
 163   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 164     const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy);
 165     for (StructType::element_iterator EB = STy->element_begin(),
 166                                       EI = EB,
 167                                       EE = STy->element_end();
 168          EI != EE; ++EI)
 169       ComputeValueVTs(TLI, *EI, ValueVTs, Offsets,
 170                       StartingOffset + SL->getElementOffset(EI - EB));
 171     return;
 172   }
 173   // Given an array type, recursively traverse the elements.
 174   if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 175     const Type *EltTy = ATy->getElementType();
 176     uint64_t EltSize = TLI.getTargetData()->getABITypeSize(EltTy);
 177     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
 178       ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets,
 179                       StartingOffset + i * EltSize);
 180     return;
 181   }
 182   // Base case: we can get an MVT for this LLVM IR type.
 183   ValueVTs.push_back(TLI.getValueType(Ty));
 184   if (Offsets)
 185     Offsets->push_back(StartingOffset);
 186 }
 187
 188 namespace {
 189   /// RegsForValue - This struct represents the registers (physical or virtual)
 190   /// that a particular set of values is assigned, and the type information about
 191   /// the value. The most common situation is to represent one value at a time,
 192   /// but struct or array values are handled element-wise as multiple values.
 193   /// The splitting of aggregates is performed recursively, so that we never
 194   /// have aggregate-typed registers. The values at this point do not necessarily
 195   /// have legal types, so each value may require one or more registers of some
 196   /// legal type.
 197   ///
 198   struct VISIBILITY_HIDDEN RegsForValue {
 199     /// TLI - The TargetLowering object.
 200     ///
 201     const TargetLowering *TLI;
 202
 203     /// ValueVTs - The value types of the values, which may not be legal, and
 204     /// may need be promoted or synthesized from one or more registers.
 205     ///
 206     SmallVector<MVT, 4> ValueVTs;
 207
 208     /// RegVTs - The value types of the registers. This is the same size as
 209     /// ValueVTs and it records, for each value, what the type of the assigned
 210     /// register or registers are. (Individual values are never synthesized
 211     /// from more than one type of register.)
 212     ///
 213     /// With virtual registers, the contents of RegVTs is redundant with TLI's
 214     /// getRegisterType member function, however when with physical registers
 215     /// it is necessary to have a separate record of the types.
 216     ///
 217     SmallVector<MVT, 4> RegVTs;
 218
 219     /// Regs - This list holds the registers assigned to the values.
 220     /// Each legal or promoted value requires one register, and each
 221     /// expanded value requires multiple registers.
 222     ///
 223     SmallVector<unsigned, 4> Regs;
 224
 225     RegsForValue() : TLI(0) {}
 226
 227     RegsForValue(const TargetLowering &tli,
 228                  const SmallVector<unsigned, 4> &regs,
 229                  MVT regvt, MVT valuevt)
 230       : TLI(&tli),  ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs) {}
 231     RegsForValue(const TargetLowering &tli,
 232                  const SmallVector<unsigned, 4> &regs,
 233                  const SmallVector<MVT, 4> &regvts,
 234                  const SmallVector<MVT, 4> &valuevts)
 235       : TLI(&tli), ValueVTs(valuevts), RegVTs(regvts), Regs(regs) {}
 236     RegsForValue(const TargetLowering &tli,
 237                  unsigned Reg, const Type *Ty) : TLI(&tli) {
 238       ComputeValueVTs(tli, Ty, ValueVTs);
 239
 240       for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
 241         MVT ValueVT = ValueVTs[Value];
 242         unsigned NumRegs = TLI->getNumRegisters(ValueVT);
 243         MVT RegisterVT = TLI->getRegisterType(ValueVT);
 244         for (unsigned i = 0; i != NumRegs; ++i)
 245           Regs.push_back(Reg + i);
 246         RegVTs.push_back(RegisterVT);
 247         Reg += NumRegs;
 248       }
 249     }
 250
 251     /// append - Add the specified values to this one.
 252     void append(const RegsForValue &RHS) {
 253       TLI = RHS.TLI;
 254       ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
 255       RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
 256       Regs.append(RHS.Regs.begin(), RHS.Regs.end());
 257     }
 258
 259
 260     /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
 261     /// this value and returns the result as a ValueVTs value.  This uses
 262     /// Chain/Flag as the input and updates them for the output Chain/Flag.
 263     /// If the Flag pointer is NULL, no flag is used.
 264     SDValue getCopyFromRegs(SelectionDAG &DAG,
 265                               SDValue &Chain, SDValue *Flag) const;
 266
 267     /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
 268     /// specified value into the registers specified by this object.  This uses
 269     /// Chain/Flag as the input and updates them for the output Chain/Flag.
 270     /// If the Flag pointer is NULL, no flag is used.
 271     void getCopyToRegs(SDValue Val, SelectionDAG &DAG,
 272                        SDValue &Chain, SDValue *Flag) const;
 273
 274     /// AddInlineAsmOperands - Add this value to the specified inlineasm node
 275     /// operand list.  This adds the code marker and includes the number of
 276     /// values added into it.
 277     void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
 278                               std::vector<SDValue> &Ops) const;
 279   };
 280 }
 281
 282 namespace llvm {
 283   //===--------------------------------------------------------------------===//
 284   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 285   /// for the target.
 286   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 287                                       SelectionDAG *DAG,
 288                                       MachineBasicBlock *BB,
 289                                       bool Fast) {
 290     TargetLowering &TLI = IS->getTargetLowering();
 291
 292     if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
 293       return createTDListDAGScheduler(IS, DAG, BB, Fast);
 294     } else {
 295       assert(TLI.getSchedulingPreference() ==
 296            TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
 297       return createBURRListDAGScheduler(IS, DAG, BB, Fast);
 298     }
 299   }
 300
 301
 302   //===--------------------------------------------------------------------===//
 303   /// FunctionLoweringInfo - This contains information that is global to a
 304   /// function that is used when lowering a region of the function.
 305   class FunctionLoweringInfo {
 306   public:
 307     TargetLowering &TLI;
 308     Function &Fn;
 309     MachineFunction &MF;
 310     MachineRegisterInfo &RegInfo;
 311
 312     FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
 313
 314     /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
 315     std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
 316
 317     /// ValueMap - Since we emit code for the function a basic block at a time,
 318     /// we must remember which virtual registers hold the values for
 319     /// cross-basic-block values.
 320     DenseMap<const Value*, unsigned> ValueMap;
 321
 322     /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
 323     /// the entry block.  This allows the allocas to be efficiently referenced
 324     /// anywhere in the function.
 325     std::map<const AllocaInst*, int> StaticAllocaMap;
 326
 327 #ifndef NDEBUG
 328     SmallSet<Instruction*, 8> CatchInfoLost;
 329     SmallSet<Instruction*, 8> CatchInfoFound;
 330 #endif
 331
 332     unsigned MakeReg(MVT VT) {
 333       return RegInfo.createVirtualRegister(TLI.getRegClassFor(VT));
 334     }
 335
 336     /// isExportedInst - Return true if the specified value is an instruction
 337     /// exported from its block.
 338     bool isExportedInst(const Value *V) {
 339       return ValueMap.count(V);
 340     }
 341
 342     unsigned CreateRegForValue(const Value *V);
 343
 344     unsigned InitializeRegForValue(const Value *V) {
 345       unsigned &R = ValueMap[V];
 346       assert(R == 0 && "Already initialized this value register!");
 347       return R = CreateRegForValue(V);
 348     }
 349
 350     struct LiveOutInfo {
 351       unsigned NumSignBits;
 352       APInt KnownOne, KnownZero;
 353       LiveOutInfo() : NumSignBits(0) {}
 354     };
 355
 356     /// LiveOutRegInfo - Information about live out vregs, indexed by their
 357     /// register number offset by 'FirstVirtualRegister'.
 358     std::vector<LiveOutInfo> LiveOutRegInfo;
 359   };
 360 }
 361
 362 /// isSelector - Return true if this instruction is a call to the
 363 /// eh.selector intrinsic.
 364 static bool isSelector(Instruction *I) {
 365   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
 366     return (II->getIntrinsicID() == Intrinsic::eh_selector_i32 ||
 367             II->getIntrinsicID() == Intrinsic::eh_selector_i64);
 368   return false;
 369 }
 370
 371 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
 372 /// PHI nodes or outside of the basic block that defines it, or used by a
 373 /// switch or atomic instruction, which may expand to multiple basic blocks.
 374 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
 375   if (isa<PHINode>(I)) return true;
 376   BasicBlock *BB = I->getParent();
 377   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
 378     if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
 379         // FIXME: Remove switchinst special case.
 380         isa<SwitchInst>(*UI))
 381       return true;
 382   return false;
 383 }
 384
 385 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
 386 /// entry block, return true.  This includes arguments used by switches, since
 387 /// the switch may expand into multiple basic blocks.
 388 static bool isOnlyUsedInEntryBlock(Argument *A) {
 389   BasicBlock *Entry = A->getParent()->begin();
 390   for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
 391     if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
 392       return false;  // Use not in entry block.
 393   return true;
 394 }
 395
 396 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
 397                                            Function &fn, MachineFunction &mf)
 398     : TLI(tli), Fn(fn), MF(mf), RegInfo(MF.getRegInfo()) {
 399
 400   // Create a vreg for each argument register that is not dead and is used
 401   // outside of the entry block for the function.
 402   for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
 403        AI != E; ++AI)
 404     if (!isOnlyUsedInEntryBlock(AI))
 405       InitializeRegForValue(AI);
 406
 407   // Initialize the mapping of values to registers.  This is only set up for
 408   // instruction values that are used outside of the block that defines
 409   // them.
 410   Function::iterator BB = Fn.begin(), EB = Fn.end();
 411   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 412     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 413       if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
 414         const Type *Ty = AI->getAllocatedType();
 415         uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
 416         unsigned Align =
 417           std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
 418                    AI->getAlignment());
 419
 420         TySize *= CUI->getZExtValue();   // Get total allocated size.
 421         if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
 422         StaticAllocaMap[AI] =
 423           MF.getFrameInfo()->CreateStackObject(TySize, Align);
 424       }
 425
 426   for (; BB != EB; ++BB)
 427     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 428       if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
 429         if (!isa<AllocaInst>(I) ||
 430             !StaticAllocaMap.count(cast<AllocaInst>(I)))
 431           InitializeRegForValue(I);
 432
 433   // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
 434   // also creates the initial PHI MachineInstrs, though none of the input
 435   // operands are populated.
 436   for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
 437     MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
 438     MBBMap[BB] = MBB;
 439     MF.push_back(MBB);
 440
 441     // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
 442     // appropriate.
 443     PHINode *PN;
 444     for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
 445       if (PN->use_empty()) continue;
 446
 447       unsigned PHIReg = ValueMap[PN];
 448       assert(PHIReg && "PHI node does not have an assigned virtual register!");
 449
 450       SmallVector<MVT, 4> ValueVTs;
 451       ComputeValueVTs(TLI, PN->getType(), ValueVTs);
 452       for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
 453         MVT VT = ValueVTs[vti];
 454         unsigned NumRegisters = TLI.getNumRegisters(VT);
 455         const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
 456         for (unsigned i = 0; i != NumRegisters; ++i)
 457           BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
 458         PHIReg += NumRegisters;
 459       }
 460     }
 461   }
 462 }
 463
 464 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
 465 /// the correctly promoted or expanded types.  Assign these registers
 466 /// consecutive vreg numbers and return the first assigned number.
 467 ///
 468 /// In the case that the given value has struct or array type, this function
 469 /// will assign registers for each member or element.
 470 ///
 471 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
 472   SmallVector<MVT, 4> ValueVTs;
 473   ComputeValueVTs(TLI, V->getType(), ValueVTs);
 474
 475   unsigned FirstReg = 0;
 476   for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
 477     MVT ValueVT = ValueVTs[Value];
 478     MVT RegisterVT = TLI.getRegisterType(ValueVT);
 479
 480     unsigned NumRegs = TLI.getNumRegisters(ValueVT);
 481     for (unsigned i = 0; i != NumRegs; ++i) {
 482       unsigned R = MakeReg(RegisterVT);
 483       if (!FirstReg) FirstReg = R;
 484     }
 485   }
 486   return FirstReg;
 487 }
 488
 489 //===----------------------------------------------------------------------===//
 490 /// SelectionDAGLowering - This is the common target-independent lowering
 491 /// implementation that is parameterized by a TargetLowering object.
 492 /// Also, targets can overload any lowering method.
 493 ///
 494 namespace llvm {
 495 class SelectionDAGLowering {
 496   MachineBasicBlock *CurMBB;
 497
 498   DenseMap<const Value*, SDValue> NodeMap;
 499
 500   /// PendingLoads - Loads are not emitted to the program immediately.  We bunch
 501   /// them up and then emit token factor nodes when possible.  This allows us to
 502   /// get simple disambiguation between loads without worrying about alias
 503   /// analysis.
 504   SmallVector<SDValue, 8> PendingLoads;
 505
 506   /// PendingExports - CopyToReg nodes that copy values to virtual registers
 507   /// for export to other blocks need to be emitted before any terminator
 508   /// instruction, but they have no other ordering requirements. We bunch them
 509   /// up and the emit a single tokenfactor for them just before terminator
 510   /// instructions.
 511   std::vector<SDValue> PendingExports;
 512
 513   /// Case - A struct to record the Value for a switch case, and the
 514   /// case's target basic block.
 515   struct Case {
 516     Constant* Low;
 517     Constant* High;
 518     MachineBasicBlock* BB;
 519
 520     Case() : Low(0), High(0), BB(0) { }
 521     Case(Constant* low, Constant* high, MachineBasicBlock* bb) :
 522       Low(low), High(high), BB(bb) { }
 523     uint64_t size() const {
 524       uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue();
 525       uint64_t rLow  = cast<ConstantInt>(Low)->getSExtValue();
 526       return (rHigh - rLow + 1ULL);
 527     }
 528   };
 529
 530   struct CaseBits {
 531     uint64_t Mask;
 532     MachineBasicBlock* BB;
 533     unsigned Bits;
 534
 535     CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits):
 536       Mask(mask), BB(bb), Bits(bits) { }
 537   };
 538
 539   typedef std::vector<Case>           CaseVector;
 540   typedef std::vector<CaseBits>       CaseBitsVector;
 541   typedef CaseVector::iterator        CaseItr;
 542   typedef std::pair<CaseItr, CaseItr> CaseRange;
 543
 544   /// CaseRec - A struct with ctor used in lowering switches to a binary tree
 545   /// of conditional branches.
 546   struct CaseRec {
 547     CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) :
 548     CaseBB(bb), LT(lt), GE(ge), Range(r) {}
 549
 550     /// CaseBB - The MBB in which to emit the compare and branch
 551     MachineBasicBlock *CaseBB;
 552     /// LT, GE - If nonzero, we know the current case value must be less-than or
 553     /// greater-than-or-equal-to these Constants.
 554     Constant *LT;
 555     Constant *GE;
 556     /// Range - A pair of iterators representing the range of case values to be
 557     /// processed at this point in the binary search tree.
 558     CaseRange Range;
 559   };
 560
 561   typedef std::vector<CaseRec> CaseRecVector;
 562
 563   /// The comparison function for sorting the switch case values in the vector.
 564   /// WARNING: Case ranges should be disjoint!
 565   struct CaseCmp {
 566     bool operator () (const Case& C1, const Case& C2) {
 567       assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
 568       const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
 569       const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
 570       return CI1->getValue().slt(CI2->getValue());
 571     }
 572   };
 573
 574   struct CaseBitsCmp {
 575     bool operator () (const CaseBits& C1, const CaseBits& C2) {
 576       return C1.Bits > C2.Bits;
 577     }
 578   };
 579
 580   unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI);
 581
 582 public:
 583   // TLI - This is information that describes the available target features we
 584   // need for lowering.  This indicates when operations are unavailable,
 585   // implemented with a libcall, etc.
 586   TargetLowering &TLI;
 587   SelectionDAG &DAG;
 588   const TargetData *TD;
 589   AliasAnalysis &AA;
 590
 591   /// SwitchCases - Vector of CaseBlock structures used to communicate
 592   /// SwitchInst code generation information.
 593   std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
 594   /// JTCases - Vector of JumpTable structures used to communicate
 595   /// SwitchInst code generation information.
 596   std::vector<SelectionDAGISel::JumpTableBlock> JTCases;
 597   std::vector<SelectionDAGISel::BitTestBlock> BitTestCases;
 598
 599   /// FuncInfo - Information about the function as a whole.
 600   ///
 601   FunctionLoweringInfo &FuncInfo;
 602
 603   /// GCI - Garbage collection metadata for the function.
 604   CollectorMetadata *GCI;
 605
 606   SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
 607                        AliasAnalysis &aa,
 608                        FunctionLoweringInfo &funcinfo,
 609                        CollectorMetadata *gci)
 610     : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), AA(aa),
 611       FuncInfo(funcinfo), GCI(gci) {
 612   }
 613
 614   /// getRoot - Return the current virtual root of the Selection DAG,
 615   /// flushing any PendingLoad items. This must be done before emitting
 616   /// a store or any other node that may need to be ordered after any
 617   /// prior load instructions.
 618   ///
 619   SDValue getRoot() {
 620     if (PendingLoads.empty())
 621       return DAG.getRoot();
 622
 623     if (PendingLoads.size() == 1) {
 624       SDValue Root = PendingLoads[0];
 625       DAG.setRoot(Root);
 626       PendingLoads.clear();
 627       return Root;
 628     }
 629
 630     // Otherwise, we have to make a token factor node.
 631     SDValue Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
 632                                  &PendingLoads[0], PendingLoads.size());
 633     PendingLoads.clear();
 634     DAG.setRoot(Root);
 635     return Root;
 636   }
 637
 638   /// getControlRoot - Similar to getRoot, but instead of flushing all the
 639   /// PendingLoad items, flush all the PendingExports items. It is necessary
 640   /// to do this before emitting a terminator instruction.
 641   ///
 642   SDValue getControlRoot() {
 643     SDValue Root = DAG.getRoot();
 644
 645     if (PendingExports.empty())
 646       return Root;
 647
 648     // Turn all of the CopyToReg chains into one factored node.
 649     if (Root.getOpcode() != ISD::EntryToken) {
 650       unsigned i = 0, e = PendingExports.size();
 651       for (; i != e; ++i) {
 652         assert(PendingExports[i].Val->getNumOperands() > 1);
 653         if (PendingExports[i].Val->getOperand(0) == Root)
 654           break;  // Don't add the root if we already indirectly depend on it.
 655       }
 656
 657       if (i == e)
 658         PendingExports.push_back(Root);
 659     }
 660
 661     Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
 662                        &PendingExports[0],
 663                        PendingExports.size());
 664     PendingExports.clear();
 665     DAG.setRoot(Root);
 666     return Root;
 667   }
 668
 669   void CopyValueToVirtualRegister(Value *V, unsigned Reg);
 670
 671   void visit(Instruction &I) { visit(I.getOpcode(), I); }
 672
 673   void visit(unsigned Opcode, User &I) {
 674     // Note: this doesn't use InstVisitor, because it has to work with
 675     // ConstantExpr's in addition to instructions.
 676     switch (Opcode) {
 677     default: assert(0 && "Unknown instruction type encountered!");
 678              abort();
 679       // Build the switch statement using the Instruction.def file.
 680 #define HANDLE_INST(NUM, OPCODE, CLASS) \
 681     case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
 682 #include "llvm/Instruction.def"
 683     }
 684   }
 685
 686   void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
 687
 688   SDValue getValue(const Value *V);
 689
 690   void setValue(const Value *V, SDValue NewN) {
 691     SDValue &N = NodeMap[V];
 692     assert(N.Val == 0 && "Already set a value for this node!");
 693     N = NewN;
 694   }
 695
 696   void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, bool HasEarlyClobber,
 697                             std::set<unsigned> &OutputRegs,
 698                             std::set<unsigned> &InputRegs);
 699
 700   void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
 701                             MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
 702                             unsigned Opc);
 703   bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
 704   void ExportFromCurrentBlock(Value *V);
 705   void LowerCallTo(CallSite CS, SDValue Callee, bool IsTailCall,
 706                    MachineBasicBlock *LandingPad = NULL);
 707
 708   // Terminator instructions.
 709   void visitRet(ReturnInst &I);
 710   void visitBr(BranchInst &I);
 711   void visitSwitch(SwitchInst &I);
 712   void visitUnreachable(UnreachableInst &I) { /* noop */ }
 713
 714   // Helpers for visitSwitch
 715   bool handleSmallSwitchRange(CaseRec& CR,
 716                               CaseRecVector& WorkList,
 717                               Value* SV,
 718                               MachineBasicBlock* Default);
 719   bool handleJTSwitchCase(CaseRec& CR,
 720                           CaseRecVector& WorkList,
 721                           Value* SV,
 722                           MachineBasicBlock* Default);
 723   bool handleBTSplitSwitchCase(CaseRec& CR,
 724                                CaseRecVector& WorkList,
 725                                Value* SV,
 726                                MachineBasicBlock* Default);
 727   bool handleBitTestsSwitchCase(CaseRec& CR,
 728                                 CaseRecVector& WorkList,
 729                                 Value* SV,
 730                                 MachineBasicBlock* Default);
 731   void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
 732   void visitBitTestHeader(SelectionDAGISel::BitTestBlock &B);
 733   void visitBitTestCase(MachineBasicBlock* NextMBB,
 734                         unsigned Reg,
 735                         SelectionDAGISel::BitTestCase &B);
 736   void visitJumpTable(SelectionDAGISel::JumpTable &JT);
 737   void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
 738                             SelectionDAGISel::JumpTableHeader &JTH);
 739
 740   // These all get lowered before this pass.
 741   void visitInvoke(InvokeInst &I);
 742   void visitUnwind(UnwindInst &I);
 743
 744   void visitBinary(User &I, unsigned OpCode);
 745   void visitShift(User &I, unsigned Opcode);
 746   void visitAdd(User &I) {
 747     if (I.getType()->isFPOrFPVector())
 748       visitBinary(I, ISD::FADD);
 749     else
 750       visitBinary(I, ISD::ADD);
 751   }
 752   void visitSub(User &I);
 753   void visitMul(User &I) {
 754     if (I.getType()->isFPOrFPVector())
 755       visitBinary(I, ISD::FMUL);
 756     else
 757       visitBinary(I, ISD::MUL);
 758   }
 759   void visitURem(User &I) { visitBinary(I, ISD::UREM); }
 760   void visitSRem(User &I) { visitBinary(I, ISD::SREM); }
 761   void visitFRem(User &I) { visitBinary(I, ISD::FREM); }
 762   void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); }
 763   void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); }
 764   void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); }
 765   void visitAnd (User &I) { visitBinary(I, ISD::AND); }
 766   void visitOr  (User &I) { visitBinary(I, ISD::OR); }
 767   void visitXor (User &I) { visitBinary(I, ISD::XOR); }
 768   void visitShl (User &I) { visitShift(I, ISD::SHL); }
 769   void visitLShr(User &I) { visitShift(I, ISD::SRL); }
 770   void visitAShr(User &I) { visitShift(I, ISD::SRA); }
 771   void visitICmp(User &I);
 772   void visitFCmp(User &I);
 773   void visitVICmp(User &I);
 774   void visitVFCmp(User &I);
 775   // Visit the conversion instructions
 776   void visitTrunc(User &I);
 777   void visitZExt(User &I);
 778   void visitSExt(User &I);
 779   void visitFPTrunc(User &I);
 780   void visitFPExt(User &I);
 781   void visitFPToUI(User &I);
 782   void visitFPToSI(User &I);
 783   void visitUIToFP(User &I);
 784   void visitSIToFP(User &I);
 785   void visitPtrToInt(User &I);
 786   void visitIntToPtr(User &I);
 787   void visitBitCast(User &I);
 788
 789   void visitExtractElement(User &I);
 790   void visitInsertElement(User &I);
 791   void visitShuffleVector(User &I);
 792
 793   void visitExtractValue(ExtractValueInst &I);
 794   void visitInsertValue(InsertValueInst &I);
 795
 796   void visitGetElementPtr(User &I);
 797   void visitSelect(User &I);
 798
 799   void visitMalloc(MallocInst &I);
 800   void visitFree(FreeInst &I);
 801   void visitAlloca(AllocaInst &I);
 802   void visitLoad(LoadInst &I);
 803   void visitStore(StoreInst &I);
 804   void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
 805   void visitCall(CallInst &I);
 806   void visitInlineAsm(CallSite CS);
 807   const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
 808   void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
 809
 810   void visitVAStart(CallInst &I);
 811   void visitVAArg(VAArgInst &I);
 812   void visitVAEnd(CallInst &I);
 813   void visitVACopy(CallInst &I);
 814
 815   void visitUserOp1(Instruction &I) {
 816     assert(0 && "UserOp1 should not exist at instruction selection time!");
 817     abort();
 818   }
 819   void visitUserOp2(Instruction &I) {
 820     assert(0 && "UserOp2 should not exist at instruction selection time!");
 821     abort();
 822   }
 823
 824 private:
 825   inline const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op);
 826
 827 };
 828 } // end namespace llvm
 829
 830
 831 /// getCopyFromParts - Create a value that contains the specified legal parts
 832 /// combined into the value they represent.  If the parts combine to a type
 833 /// larger then ValueVT then AssertOp can be used to specify whether the extra
 834 /// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT
 835 /// (ISD::AssertSext).
 836 static SDValue getCopyFromParts(SelectionDAG &DAG,
 837                                   const SDValue *Parts,
 838                                   unsigned NumParts,
 839                                   MVT PartVT,
 840                                   MVT ValueVT,
 841                                   ISD::NodeType AssertOp = ISD::DELETED_NODE) {
 842   assert(NumParts > 0 && "No parts to assemble!");
 843   TargetLowering &TLI = DAG.getTargetLoweringInfo();
 844   SDValue Val = Parts[0];
 845
 846   if (NumParts > 1) {
 847     // Assemble the value from multiple parts.
 848     if (!ValueVT.isVector()) {
 849       unsigned PartBits = PartVT.getSizeInBits();
 850       unsigned ValueBits = ValueVT.getSizeInBits();
 851
 852       // Assemble the power of 2 part.
 853       unsigned RoundParts = NumParts & (NumParts - 1) ?
 854         1 << Log2_32(NumParts) : NumParts;
 855       unsigned RoundBits = PartBits * RoundParts;
 856       MVT RoundVT = RoundBits == ValueBits ?
 857         ValueVT : MVT::getIntegerVT(RoundBits);
 858       SDValue Lo, Hi;
 859
 860       if (RoundParts > 2) {
 861         MVT HalfVT = MVT::getIntegerVT(RoundBits/2);
 862         Lo = getCopyFromParts(DAG, Parts, RoundParts/2, PartVT, HalfVT);
 863         Hi = getCopyFromParts(DAG, Parts+RoundParts/2, RoundParts/2,
 864                               PartVT, HalfVT);
 865       } else {
 866         Lo = Parts[0];
 867         Hi = Parts[1];
 868       }
 869       if (TLI.isBigEndian())
 870         std::swap(Lo, Hi);
 871       Val = DAG.getNode(ISD::BUILD_PAIR, RoundVT, Lo, Hi);
 872
 873       if (RoundParts < NumParts) {
 874         // Assemble the trailing non-power-of-2 part.
 875         unsigned OddParts = NumParts - RoundParts;
 876         MVT OddVT = MVT::getIntegerVT(OddParts * PartBits);
 877         Hi = getCopyFromParts(DAG, Parts+RoundParts, OddParts, PartVT, OddVT);
 878
 879         // Combine the round and odd parts.
 880         Lo = Val;
 881         if (TLI.isBigEndian())
 882           std::swap(Lo, Hi);
 883         MVT TotalVT = MVT::getIntegerVT(NumParts * PartBits);
 884         Hi = DAG.getNode(ISD::ANY_EXTEND, TotalVT, Hi);
 885         Hi = DAG.getNode(ISD::SHL, TotalVT, Hi,
 886                          DAG.getConstant(Lo.getValueType().getSizeInBits(),
 887                                          TLI.getShiftAmountTy()));
 888         Lo = DAG.getNode(ISD::ZERO_EXTEND, TotalVT, Lo);
 889         Val = DAG.getNode(ISD::OR, TotalVT, Lo, Hi);
 890       }
 891     } else {
 892       // Handle a multi-element vector.
 893       MVT IntermediateVT, RegisterVT;
 894       unsigned NumIntermediates;
 895       unsigned NumRegs =
 896         TLI.getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
 897                                    RegisterVT);
 898       assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
 899       NumParts = NumRegs; // Silence a compiler warning.
 900       assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
 901       assert(RegisterVT == Parts[0].getValueType() &&
 902              "Part type doesn't match part!");
 903
 904       // Assemble the parts into intermediate operands.
 905       SmallVector<SDValue, 8> Ops(NumIntermediates);
 906       if (NumIntermediates == NumParts) {
 907         // If the register was not expanded, truncate or copy the value,
 908         // as appropriate.
 909         for (unsigned i = 0; i != NumParts; ++i)
 910           Ops[i] = getCopyFromParts(DAG, &Parts[i], 1,
 911                                     PartVT, IntermediateVT);
 912       } else if (NumParts > 0) {
 913         // If the intermediate type was expanded, build the intermediate operands
 914         // from the parts.
 915         assert(NumParts % NumIntermediates == 0 &&
 916                "Must expand into a divisible number of parts!");
 917         unsigned Factor = NumParts / NumIntermediates;
 918         for (unsigned i = 0; i != NumIntermediates; ++i)
 919           Ops[i] = getCopyFromParts(DAG, &Parts[i * Factor], Factor,
 920                                     PartVT, IntermediateVT);
 921       }
 922
 923       // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the intermediate
 924       // operands.
 925       Val = DAG.getNode(IntermediateVT.isVector() ?
 926                         ISD::CONCAT_VECTORS : ISD::BUILD_VECTOR,
 927                         ValueVT, &Ops[0], NumIntermediates);
 928     }
 929   }
 930
 931   // There is now one part, held in Val.  Correct it to match ValueVT.
 932   PartVT = Val.getValueType();
 933
 934   if (PartVT == ValueVT)
 935     return Val;
 936
 937   if (PartVT.isVector()) {
 938     assert(ValueVT.isVector() && "Unknown vector conversion!");
 939     return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);
 940   }
 941
 942   if (ValueVT.isVector()) {
 943     assert(ValueVT.getVectorElementType() == PartVT &&
 944            ValueVT.getVectorNumElements() == 1 &&
 945            "Only trivial scalar-to-vector conversions should get here!");
 946     return DAG.getNode(ISD::BUILD_VECTOR, ValueVT, Val);
 947   }
 948
 949   if (PartVT.isInteger() &&
 950       ValueVT.isInteger()) {
 951     if (ValueVT.bitsLT(PartVT)) {
 952       // For a truncate, see if we have any information to
 953       // indicate whether the truncated bits will always be
 954       // zero or sign-extension.
 955       if (AssertOp != ISD::DELETED_NODE)
 956         Val = DAG.getNode(AssertOp, PartVT, Val,
 957                           DAG.getValueType(ValueVT));
 958       return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
 959     } else {
 960       return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
 961     }
 962   }
 963
 964   if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
 965     if (ValueVT.bitsLT(Val.getValueType()))
 966       // FP_ROUND's are always exact here.
 967       return DAG.getNode(ISD::FP_ROUND, ValueVT, Val,
 968                          DAG.getIntPtrConstant(1));
 969     return DAG.getNode(ISD::FP_EXTEND, ValueVT, Val);
 970   }
 971
 972   if (PartVT.getSizeInBits() == ValueVT.getSizeInBits())
 973     return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);
 974
 975   assert(0 && "Unknown mismatch!");
 976   return SDValue();
 977 }
 978
 979 /// getCopyToParts - Create a series of nodes that contain the specified value
 980 /// split into legal parts.  If the parts contain more bits than Val, then, for
 981 /// integers, ExtendKind can be used to specify how to generate the extra bits.
 982 static void getCopyToParts(SelectionDAG &DAG,
 983                            SDValue Val,
 984                            SDValue *Parts,
 985                            unsigned NumParts,
 986                            MVT PartVT,
 987                            ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
 988   TargetLowering &TLI = DAG.getTargetLoweringInfo();
 989   MVT PtrVT = TLI.getPointerTy();
 990   MVT ValueVT = Val.getValueType();
 991   unsigned PartBits = PartVT.getSizeInBits();
 992   assert(TLI.isTypeLegal(PartVT) && "Copying to an illegal type!");
 993
 994   if (!NumParts)
 995     return;
 996
 997   if (!ValueVT.isVector()) {
 998     if (PartVT == ValueVT) {
 999       assert(NumParts == 1 && "No-op copy with multiple parts!");
1000       Parts[0] = Val;
1001       return;
1002     }
1003
1004     if (NumParts * PartBits > ValueVT.getSizeInBits()) {
1005       // If the parts cover more bits than the value has, promote the value.
1006       if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
1007         assert(NumParts == 1 && "Do not know what to promote to!");
1008         Val = DAG.getNode(ISD::FP_EXTEND, PartVT, Val);
1009       } else if (PartVT.isInteger() && ValueVT.isInteger()) {
1010         ValueVT = MVT::getIntegerVT(NumParts * PartBits);
1011         Val = DAG.getNode(ExtendKind, ValueVT, Val);
1012       } else {
1013         assert(0 && "Unknown mismatch!");
1014       }
1015     } else if (PartBits == ValueVT.getSizeInBits()) {
1016       // Different types of the same size.
1017       assert(NumParts == 1 && PartVT != ValueVT);
1018       Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
1019     } else if (NumParts * PartBits < ValueVT.getSizeInBits()) {
1020       // If the parts cover less bits than value has, truncate the value.
1021       if (PartVT.isInteger() && ValueVT.isInteger()) {
1022         ValueVT = MVT::getIntegerVT(NumParts * PartBits);
1023         Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
1024       } else {
1025         assert(0 && "Unknown mismatch!");
1026       }
1027     }
1028
1029     // The value may have changed - recompute ValueVT.
1030     ValueVT = Val.getValueType();
1031     assert(NumParts * PartBits == ValueVT.getSizeInBits() &&
1032            "Failed to tile the value with PartVT!");
1033
1034     if (NumParts == 1) {
1035       assert(PartVT == ValueVT && "Type conversion failed!");
1036       Parts[0] = Val;
1037       return;
1038     }
1039
1040     // Expand the value into multiple parts.
1041     if (NumParts & (NumParts - 1)) {
1042       // The number of parts is not a power of 2.  Split off and copy the tail.
1043       assert(PartVT.isInteger() && ValueVT.isInteger() &&
1044              "Do not know what to expand to!");
1045       unsigned RoundParts = 1 << Log2_32(NumParts);
1046       unsigned RoundBits = RoundParts * PartBits;
1047       unsigned OddParts = NumParts - RoundParts;
1048       SDValue OddVal = DAG.getNode(ISD::SRL, ValueVT, Val,
1049                                      DAG.getConstant(RoundBits,
1050                                                      TLI.getShiftAmountTy()));
1051       getCopyToParts(DAG, OddVal, Parts + RoundParts, OddParts, PartVT);
1052       if (TLI.isBigEndian())
1053         // The odd parts were reversed by getCopyToParts - unreverse them.
1054         std::reverse(Parts + RoundParts, Parts + NumParts);
1055       NumParts = RoundParts;
1056       ValueVT = MVT::getIntegerVT(NumParts * PartBits);
1057       Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
1058     }
1059
1060     // The number of parts is a power of 2.  Repeatedly bisect the value using
1061     // EXTRACT_ELEMENT.
1062     Parts[0] = DAG.getNode(ISD::BIT_CONVERT,
1063                            MVT::getIntegerVT(ValueVT.getSizeInBits()),
1064                            Val);
1065     for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
1066       for (unsigned i = 0; i < NumParts; i += StepSize) {
1067         unsigned ThisBits = StepSize * PartBits / 2;
1068         MVT ThisVT = MVT::getIntegerVT (ThisBits);
1069         SDValue &Part0 = Parts[i];
1070         SDValue &Part1 = Parts[i+StepSize/2];
1071
1072         Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0,
1073                             DAG.getConstant(1, PtrVT));
1074         Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0,
1075                             DAG.getConstant(0, PtrVT));
1076
1077         if (ThisBits == PartBits && ThisVT != PartVT) {
1078           Part0 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part0);
1079           Part1 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part1);
1080         }
1081       }
1082     }
1083
1084     if (TLI.isBigEndian())
1085       std::reverse(Parts, Parts + NumParts);
1086
1087     return;
1088   }
1089
1090   // Vector ValueVT.
1091   if (NumParts == 1) {
1092     if (PartVT != ValueVT) {
1093       if (PartVT.isVector()) {
1094         Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
1095       } else {
1096         assert(ValueVT.getVectorElementType() == PartVT &&
1097                ValueVT.getVectorNumElements() == 1 &&
1098                "Only trivial vector-to-scalar conversions should get here!");
1099         Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, PartVT, Val,
1100                           DAG.getConstant(0, PtrVT));
1101       }
1102     }
1103
1104     Parts[0] = Val;
1105     return;
1106   }
1107
1108   // Handle a multi-element vector.
1109   MVT IntermediateVT, RegisterVT;
1110   unsigned NumIntermediates;
1111   unsigned NumRegs =
1112     DAG.getTargetLoweringInfo()
1113       .getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
1114                               RegisterVT);
1115   unsigned NumElements = ValueVT.getVectorNumElements();
1116
1117   assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
1118   NumParts = NumRegs; // Silence a compiler warning.
1119   assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
1120
1121   // Split the vector into intermediate operands.
1122   SmallVector<SDValue, 8> Ops(NumIntermediates);
1123   for (unsigned i = 0; i != NumIntermediates; ++i)
1124     if (IntermediateVT.isVector())
1125       Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR,
1126                            IntermediateVT, Val,
1127                            DAG.getConstant(i * (NumElements / NumIntermediates),
1128                                            PtrVT));
1129     else
1130       Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
1131                            IntermediateVT, Val,
1132                            DAG.getConstant(i, PtrVT));
1133
1134   // Split the intermediate operands into legal parts.
1135   if (NumParts == NumIntermediates) {
1136     // If the register was not expanded, promote or copy the value,
1137     // as appropriate.
1138     for (unsigned i = 0; i != NumParts; ++i)
1139       getCopyToParts(DAG, Ops[i], &Parts[i], 1, PartVT);
1140   } else if (NumParts > 0) {
1141     // If the intermediate type was expanded, split each the value into
1142     // legal parts.
1143     assert(NumParts % NumIntermediates == 0 &&
1144            "Must expand into a divisible number of parts!");
1145     unsigned Factor = NumParts / NumIntermediates;
1146     for (unsigned i = 0; i != NumIntermediates; ++i)
1147       getCopyToParts(DAG, Ops[i], &Parts[i * Factor], Factor, PartVT);
1148   }
1149 }
1150
1151
1152 SDValue SelectionDAGLowering::getValue(const Value *V) {
1153   SDValue &N = NodeMap[V];
1154   if (N.Val) return N;
1155
1156   if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
1157     MVT VT = TLI.getValueType(V->getType(), true);
1158
1159     if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
1160       return N = DAG.getConstant(CI->getValue(), VT);
1161
1162     if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
1163       return N = DAG.getGlobalAddress(GV, VT);
1164
1165     if (isa<ConstantPointerNull>(C))
1166       return N = DAG.getConstant(0, TLI.getPointerTy());
1167
1168     if (ConstantFP *CFP = dyn_cast<ConstantFP>(C))
1169       return N = DAG.getConstantFP(CFP->getValueAPF(), VT);
1170
1171     if (isa<UndefValue>(C) && !isa<VectorType>(V->getType()) &&
1172         !V->getType()->isAggregateType())
1173       return N = DAG.getNode(ISD::UNDEF, VT);
1174
1175     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1176       visit(CE->getOpcode(), *CE);
1177       SDValue N1 = NodeMap[V];
1178       assert(N1.Val && "visit didn't populate the ValueMap!");
1179       return N1;
1180     }
1181
1182     if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {
1183       SmallVector<SDValue, 4> Constants;
1184       for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end();
1185            OI != OE; ++OI) {
1186         SDNode *Val = getValue(*OI).Val;
1187         for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
1188           Constants.push_back(SDValue(Val, i));
1189       }
1190       return DAG.getMergeValues(&Constants[0], Constants.size());
1191     }
1192
1193     if (isa<StructType>(C->getType()) || isa<ArrayType>(C->getType())) {
1194       assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
1195              "Unknown struct or array constant!");
1196
1197       SmallVector<MVT, 4> ValueVTs;
1198       ComputeValueVTs(TLI, C->getType(), ValueVTs);
1199       unsigned NumElts = ValueVTs.size();
1200       if (NumElts == 0)
1201         return SDValue(); // empty struct
1202       SmallVector<SDValue, 4> Constants(NumElts);
1203       for (unsigned i = 0; i != NumElts; ++i) {
1204         MVT EltVT = ValueVTs[i];
1205         if (isa<UndefValue>(C))
1206           Constants[i] = DAG.getNode(ISD::UNDEF, EltVT);
1207         else if (EltVT.isFloatingPoint())
1208           Constants[i] = DAG.getConstantFP(0, EltVT);
1209         else
1210           Constants[i] = DAG.getConstant(0, EltVT);
1211       }
1212       return DAG.getMergeValues(&Constants[0], NumElts);
1213     }
1214
1215     const VectorType *VecTy = cast<VectorType>(V->getType());
1216     unsigned NumElements = VecTy->getNumElements();
1217
1218     // Now that we know the number and type of the elements, get that number of
1219     // elements into the Ops array based on what kind of constant it is.
1220     SmallVector<SDValue, 16> Ops;
1221     if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
1222       for (unsigned i = 0; i != NumElements; ++i)
1223         Ops.push_back(getValue(CP->getOperand(i)));
1224     } else {
1225       assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
1226              "Unknown vector constant!");
1227       MVT EltVT = TLI.getValueType(VecTy->getElementType());
1228
1229       SDValue Op;
1230       if (isa<UndefValue>(C))
1231         Op = DAG.getNode(ISD::UNDEF, EltVT);
1232       else if (EltVT.isFloatingPoint())
1233         Op = DAG.getConstantFP(0, EltVT);
1234       else
1235         Op = DAG.getConstant(0, EltVT);
1236       Ops.assign(NumElements, Op);
1237     }
1238
1239     // Create a BUILD_VECTOR node.
1240     return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
1241   }
1242
1243   // If this is a static alloca, generate it as the frameindex instead of
1244   // computation.
1245   if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1246     std::map<const AllocaInst*, int>::iterator SI =
1247       FuncInfo.StaticAllocaMap.find(AI);
1248     if (SI != FuncInfo.StaticAllocaMap.end())
1249       return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
1250   }
1251
1252   unsigned InReg = FuncInfo.ValueMap[V];
1253   assert(InReg && "Value not in map!");
1254
1255   RegsForValue RFV(TLI, InReg, V->getType());
1256   SDValue Chain = DAG.getEntryNode();
1257   return RFV.getCopyFromRegs(DAG, Chain, NULL);
1258 }
1259
1260
1261 void SelectionDAGLowering::visitRet(ReturnInst &I) {
1262   if (I.getNumOperands() == 0) {
1263     DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getControlRoot()));
1264     return;
1265   }
1266
1267   SmallVector<SDValue, 8> NewValues;
1268   NewValues.push_back(getControlRoot());
1269   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1270     SDValue RetOp = getValue(I.getOperand(i));
1271
1272     SmallVector<MVT, 4> ValueVTs;
1273     ComputeValueVTs(TLI, I.getOperand(i)->getType(), ValueVTs);
1274     for (unsigned j = 0, f = ValueVTs.size(); j != f; ++j) {
1275       MVT VT = ValueVTs[j];
1276
1277       // FIXME: C calling convention requires the return type to be promoted to
1278       // at least 32-bit. But this is not necessary for non-C calling conventions.
1279       if (VT.isInteger()) {
1280         MVT MinVT = TLI.getRegisterType(MVT::i32);
1281         if (VT.bitsLT(MinVT))
1282           VT = MinVT;
1283       }
1284
1285       unsigned NumParts = TLI.getNumRegisters(VT);
1286       MVT PartVT = TLI.getRegisterType(VT);
1287       SmallVector<SDValue, 4> Parts(NumParts);
1288       ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
1289
1290       const Function *F = I.getParent()->getParent();
1291       if (F->paramHasAttr(0, ParamAttr::SExt))
1292         ExtendKind = ISD::SIGN_EXTEND;
1293       else if (F->paramHasAttr(0, ParamAttr::ZExt))
1294         ExtendKind = ISD::ZERO_EXTEND;
1295
1296       getCopyToParts(DAG, SDValue(RetOp.Val, RetOp.ResNo + j),
1297                      &Parts[0], NumParts, PartVT, ExtendKind);
1298
1299       for (unsigned i = 0; i < NumParts; ++i) {
1300         NewValues.push_back(Parts[i]);
1301         NewValues.push_back(DAG.getArgFlags(ISD::ArgFlagsTy()));
1302       }
1303     }
1304   }
1305   DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
1306                           &NewValues[0], NewValues.size()));
1307 }
1308
1309 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
1310 /// the current basic block, add it to ValueMap now so that we'll get a
1311 /// CopyTo/FromReg.
1312 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
1313   // No need to export constants.
1314   if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
1315
1316   // Already exported?
1317   if (FuncInfo.isExportedInst(V)) return;
1318
1319   unsigned Reg = FuncInfo.InitializeRegForValue(V);
1320   CopyValueToVirtualRegister(V, Reg);
1321 }
1322
1323 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
1324                                                     const BasicBlock *FromBB) {
1325   // The operands of the setcc have to be in this block.  We don't know
1326   // how to export them from some other block.
1327   if (Instruction *VI = dyn_cast<Instruction>(V)) {
1328     // Can export from current BB.
1329     if (VI->getParent() == FromBB)
1330       return true;
1331
1332     // Is already exported, noop.
1333     return FuncInfo.isExportedInst(V);
1334   }
1335
1336   // If this is an argument, we can export it if the BB is the entry block or
1337   // if it is already exported.
1338   if (isa<Argument>(V)) {
1339     if (FromBB == &FromBB->getParent()->getEntryBlock())
1340       return true;
1341
1342     // Otherwise, can only export this if it is already exported.
1343     return FuncInfo.isExportedInst(V);
1344   }
1345
1346   // Otherwise, constants can always be exported.
1347   return true;
1348 }
1349
1350 static bool InBlock(const Value *V, const BasicBlock *BB) {
1351   if (const Instruction *I = dyn_cast<Instruction>(V))
1352     return I->getParent() == BB;
1353   return true;
1354 }
1355
1356 /// FindMergedConditions - If Cond is an expression like
1357 void SelectionDAGLowering::FindMergedConditions(Value *Cond,
1358                                                 MachineBasicBlock *TBB,
1359                                                 MachineBasicBlock *FBB,
1360                                                 MachineBasicBlock *CurBB,
1361                                                 unsigned Opc) {
1362   // If this node is not part of the or/and tree, emit it as a branch.
1363   Instruction *BOp = dyn_cast<Instruction>(Cond);
1364
1365   if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
1366       (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
1367       BOp->getParent() != CurBB->getBasicBlock() ||
1368       !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
1369       !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
1370     const BasicBlock *BB = CurBB->getBasicBlock();
1371
1372     // If the leaf of the tree is a comparison, merge the condition into
1373     // the caseblock.
1374     if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) &&
1375         // The operands of the cmp have to be in this block.  We don't know
1376         // how to export them from some other block.  If this is the first block
1377         // of the sequence, no exporting is needed.
1378         (CurBB == CurMBB ||
1379          (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
1380           isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) {
1381       BOp = cast<Instruction>(Cond);
1382       ISD::CondCode Condition;
1383       if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
1384         switch (IC->getPredicate()) {
1385         default: assert(0 && "Unknown icmp predicate opcode!");
1386         case ICmpInst::ICMP_EQ:  Condition = ISD::SETEQ;  break;
1387         case ICmpInst::ICMP_NE:  Condition = ISD::SETNE;  break;
1388         case ICmpInst::ICMP_SLE: Condition = ISD::SETLE;  break;
1389         case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break;
1390         case ICmpInst::ICMP_SGE: Condition = ISD::SETGE;  break;
1391         case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break;
1392         case ICmpInst::ICMP_SLT: Condition = ISD::SETLT;  break;
1393         case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break;
1394         case ICmpInst::ICMP_SGT: Condition = ISD::SETGT;  break;
1395         case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break;
1396         }
1397       } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
1398         ISD::CondCode FPC, FOC;
1399         switch (FC->getPredicate()) {
1400         default: assert(0 && "Unknown fcmp predicate opcode!");
1401         case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
1402         case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
1403         case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
1404         case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
1405         case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
1406         case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
1407         case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
1408         case FCmpInst::FCMP_ORD:   FOC = FPC = ISD::SETO;   break;
1409         case FCmpInst::FCMP_UNO:   FOC = FPC = ISD::SETUO;  break;
1410         case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
1411         case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
1412         case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
1413         case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
1414         case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
1415         case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
1416         case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
1417         }
1418         if (FiniteOnlyFPMath())
1419           Condition = FOC;
1420         else
1421           Condition = FPC;
1422       } else {
1423         Condition = ISD::SETEQ; // silence warning.
1424         assert(0 && "Unknown compare instruction");
1425       }
1426
1427       SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
1428                                      BOp->getOperand(1), NULL, TBB, FBB, CurBB);
1429       SwitchCases.push_back(CB);
1430       return;
1431     }
1432
1433     // Create a CaseBlock record representing this branch.
1434     SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
1435                                    NULL, TBB, FBB, CurBB);
1436     SwitchCases.push_back(CB);
1437     return;
1438   }
1439
1440
1441   //  Create TmpBB after CurBB.
1442   MachineFunction::iterator BBI = CurBB;
1443   MachineFunction &MF = DAG.getMachineFunction();
1444   MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
1445   CurBB->getParent()->insert(++BBI, TmpBB);
1446
1447   if (Opc == Instruction::Or) {
1448     // Codegen X | Y as:
1449     //   jmp_if_X TBB
1450     //   jmp TmpBB
1451     // TmpBB:
1452     //   jmp_if_Y TBB
1453     //   jmp FBB
1454     //
1455
1456     // Emit the LHS condition.
1457     FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc);
1458
1459     // Emit the RHS condition into TmpBB.
1460     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
1461   } else {
1462     assert(Opc == Instruction::And && "Unknown merge op!");
1463     // Codegen X & Y as:
1464     //   jmp_if_X TmpBB
1465     //   jmp FBB
1466     // TmpBB:
1467     //   jmp_if_Y TBB
1468     //   jmp FBB
1469     //
1470     //  This requires creation of TmpBB after CurBB.
1471
1472     // Emit the LHS condition.
1473     FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc);
1474
1475     // Emit the RHS condition into TmpBB.
1476     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
1477   }
1478 }
1479
1480 /// If the set of cases should be emitted as a series of branches, return true.
1481 /// If we should emit this as a bunch of and/or'd together conditions, return
1482 /// false.
1483 static bool
1484 ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) {
1485   if (Cases.size() != 2) return true;
1486
1487   // If this is two comparisons of the same values or'd or and'd together, they
1488   // will get folded into a single comparison, so don't emit two blocks.
1489   if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
1490        Cases[0].CmpRHS == Cases[1].CmpRHS) ||
1491       (Cases[0].CmpRHS == Cases[1].CmpLHS &&
1492        Cases[0].CmpLHS == Cases[1].CmpRHS)) {
1493     return false;
1494   }
1495
1496   return true;
1497 }
1498
1499 void SelectionDAGLowering::visitBr(BranchInst &I) {
1500   // Update machine-CFG edges.
1501   MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
1502
1503   // Figure out which block is immediately after the current one.
1504   MachineBasicBlock *NextBlock = 0;
1505   MachineFunction::iterator BBI = CurMBB;
1506   if (++BBI != CurMBB->getParent()->end())
1507     NextBlock = BBI;
1508
1509   if (I.isUnconditional()) {
1510     // Update machine-CFG edges.
1511     CurMBB->addSuccessor(Succ0MBB);
1512
1513     // If this is not a fall-through branch, emit the branch.
1514     if (Succ0MBB != NextBlock)
1515       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(),
1516                               DAG.getBasicBlock(Succ0MBB)));
1517     return;
1518   }
1519
1520   // If this condition is one of the special cases we handle, do special stuff
1521   // now.
1522   Value *CondVal = I.getCondition();
1523   MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1524
1525   // If this is a series of conditions that are or'd or and'd together, emit
1526   // this as a sequence of branches instead of setcc's with and/or operations.
1527   // For example, instead of something like:
1528   //     cmp A, B
1529   //     C = seteq
1530   //     cmp D, E
1531   //     F = setle
1532   //     or C, F
1533   //     jnz foo
1534   // Emit:
1535   //     cmp A, B
1536   //     je foo
1537   //     cmp D, E
1538   //     jle foo
1539   //
1540   if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1541     if (BOp->hasOneUse() &&
1542         (BOp->getOpcode() == Instruction::And ||
1543          BOp->getOpcode() == Instruction::Or)) {
1544       FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode());
1545       // If the compares in later blocks need to use values not currently
1546       // exported from this block, export them now.  This block should always
1547       // be the first entry.
1548       assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!");
1549
1550       // Allow some cases to be rejected.
1551       if (ShouldEmitAsBranches(SwitchCases)) {
1552         for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1553           ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1554           ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1555         }
1556
1557         // Emit the branch for this block.
1558         visitSwitchCase(SwitchCases[0]);
1559         SwitchCases.erase(SwitchCases.begin());
1560         return;
1561       }
1562
1563       // Okay, we decided not to do this, remove any inserted MBB's and clear
1564       // SwitchCases.
1565       for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1566         CurMBB->getParent()->erase(SwitchCases[i].ThisBB);
1567
1568       SwitchCases.clear();
1569     }
1570   }
1571
1572   // Create a CaseBlock record representing this branch.
1573   SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
1574                                  NULL, Succ0MBB, Succ1MBB, CurMBB);
1575   // Use visitSwitchCase to actually insert the fast branch sequence for this
1576   // cond branch.
1577   visitSwitchCase(CB);
1578 }
1579
1580 /// visitSwitchCase - Emits the necessary code to represent a single node in
1581 /// the binary search tree resulting from lowering a switch instruction.
1582 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
1583   SDValue Cond;
1584   SDValue CondLHS = getValue(CB.CmpLHS);
1585
1586   // Build the setcc now.
1587   if (CB.CmpMHS == NULL) {
1588     // Fold "(X == true)" to X and "(X == false)" to !X to
1589     // handle common cases produced by branch lowering.
1590     if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
1591       Cond = CondLHS;
1592     else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
1593       SDValue True = DAG.getConstant(1, CondLHS.getValueType());
1594       Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
1595     } else
1596       Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1597   } else {
1598     assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
1599
1600     uint64_t Low = cast<ConstantInt>(CB.CmpLHS)->getSExtValue();
1601     uint64_t High  = cast<ConstantInt>(CB.CmpRHS)->getSExtValue();
1602
1603     SDValue CmpOp = getValue(CB.CmpMHS);
1604     MVT VT = CmpOp.getValueType();
1605
1606     if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
1607       Cond = DAG.getSetCC(MVT::i1, CmpOp, DAG.getConstant(High, VT), ISD::SETLE);
1608     } else {
1609       SDValue SUB = DAG.getNode(ISD::SUB, VT, CmpOp, DAG.getConstant(Low, VT));
1610       Cond = DAG.getSetCC(MVT::i1, SUB,
1611                           DAG.getConstant(High-Low, VT), ISD::SETULE);
1612     }
1613   }
1614
1615   // Update successor info
1616   CurMBB->addSuccessor(CB.TrueBB);
1617   CurMBB->addSuccessor(CB.FalseBB);
1618
1619   // Set NextBlock to be the MBB immediately after the current one, if any.
1620   // This is used to avoid emitting unnecessary branches to the next block.
1621   MachineBasicBlock *NextBlock = 0;
1622   MachineFunction::iterator BBI = CurMBB;
1623   if (++BBI != CurMBB->getParent()->end())
1624     NextBlock = BBI;
1625
1626   // If the lhs block is the next block, invert the condition so that we can
1627   // fall through to the lhs instead of the rhs block.
1628   if (CB.TrueBB == NextBlock) {
1629     std::swap(CB.TrueBB, CB.FalseBB);
1630     SDValue True = DAG.getConstant(1, Cond.getValueType());
1631     Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
1632   }
1633   SDValue BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(), Cond,
1634                                  DAG.getBasicBlock(CB.TrueBB));
1635
1636   // If the branch was constant folded, fix up the CFG.
1637   if (BrCond.getOpcode() == ISD::BR) {
1638     CurMBB->removeSuccessor(CB.FalseBB);
1639     DAG.setRoot(BrCond);
1640   } else {
1641     // Otherwise, go ahead and insert the false branch.
1642     if (BrCond == getControlRoot())
1643       CurMBB->removeSuccessor(CB.TrueBB);
1644
1645     if (CB.FalseBB == NextBlock)
1646       DAG.setRoot(BrCond);
1647     else
1648       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1649                               DAG.getBasicBlock(CB.FalseBB)));
1650   }
1651 }
1652
1653 /// visitJumpTable - Emit JumpTable node in the current MBB
1654 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
1655   // Emit the code for the jump table
1656   assert(JT.Reg != -1U && "Should lower JT Header first!");
1657   MVT PTy = TLI.getPointerTy();
1658   SDValue Index = DAG.getCopyFromReg(getControlRoot(), JT.Reg, PTy);
1659   SDValue Table = DAG.getJumpTable(JT.JTI, PTy);
1660   DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1),
1661                           Table, Index));
1662   return;
1663 }
1664
1665 /// visitJumpTableHeader - This function emits necessary code to produce index
1666 /// in the JumpTable from switch case.
1667 void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
1668                                          SelectionDAGISel::JumpTableHeader &JTH) {
1669   // Subtract the lowest switch case value from the value being switched on
1670   // and conditional branch to default mbb if the result is greater than the
1671   // difference between smallest and largest cases.
1672   SDValue SwitchOp = getValue(JTH.SValue);
1673   MVT VT = SwitchOp.getValueType();
1674   SDValue SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1675                               DAG.getConstant(JTH.First, VT));
1676
1677   // The SDNode we just created, which holds the value being switched on
1678   // minus the the smallest case value, needs to be copied to a virtual
1679   // register so it can be used as an index into the jump table in a
1680   // subsequent basic block.  This value may be smaller or larger than the
1681   // target's pointer type, and therefore require extension or truncating.
1682   if (VT.bitsGT(TLI.getPointerTy()))
1683     SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
1684   else
1685     SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
1686
1687   unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
1688   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), JumpTableReg, SwitchOp);
1689   JT.Reg = JumpTableReg;
1690
1691   // Emit the range check for the jump table, and branch to the default
1692   // block for the switch statement if the value being switched on exceeds
1693   // the largest case in the switch.
1694   SDValue CMP = DAG.getSetCC(TLI.getSetCCResultType(SUB), SUB,
1695                                DAG.getConstant(JTH.Last-JTH.First,VT),
1696                                ISD::SETUGT);
1697
1698   // Set NextBlock to be the MBB immediately after the current one, if any.
1699   // This is used to avoid emitting unnecessary branches to the next block.
1700   MachineBasicBlock *NextBlock = 0;
1701   MachineFunction::iterator BBI = CurMBB;
1702   if (++BBI != CurMBB->getParent()->end())
1703     NextBlock = BBI;
1704
1705   SDValue BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
1706                                  DAG.getBasicBlock(JT.Default));
1707
1708   if (JT.MBB == NextBlock)
1709     DAG.setRoot(BrCond);
1710   else
1711     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1712                             DAG.getBasicBlock(JT.MBB)));
1713
1714   return;
1715 }
1716
1717 /// visitBitTestHeader - This function emits necessary code to produce value
1718 /// suitable for "bit tests"
1719 void SelectionDAGLowering::visitBitTestHeader(SelectionDAGISel::BitTestBlock &B) {
1720   // Subtract the minimum value
1721   SDValue SwitchOp = getValue(B.SValue);
1722   MVT VT = SwitchOp.getValueType();
1723   SDValue SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1724                               DAG.getConstant(B.First, VT));
1725
1726   // Check range
1727   SDValue RangeCmp = DAG.getSetCC(TLI.getSetCCResultType(SUB), SUB,
1728                                     DAG.getConstant(B.Range, VT),
1729                                     ISD::SETUGT);
1730
1731   SDValue ShiftOp;
1732   if (VT.bitsGT(TLI.getShiftAmountTy()))
1733     ShiftOp = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), SUB);
1734   else
1735     ShiftOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), SUB);
1736
1737   // Make desired shift
1738   SDValue SwitchVal = DAG.getNode(ISD::SHL, TLI.getPointerTy(),
1739                                     DAG.getConstant(1, TLI.getPointerTy()),
1740                                     ShiftOp);
1741
1742   unsigned SwitchReg = FuncInfo.MakeReg(TLI.getPointerTy());
1743   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), SwitchReg, SwitchVal);
1744   B.Reg = SwitchReg;
1745
1746   // Set NextBlock to be the MBB immediately after the current one, if any.
1747   // This is used to avoid emitting unnecessary branches to the next block.
1748   MachineBasicBlock *NextBlock = 0;
1749   MachineFunction::iterator BBI = CurMBB;
1750   if (++BBI != CurMBB->getParent()->end())
1751     NextBlock = BBI;
1752
1753   MachineBasicBlock* MBB = B.Cases[0].ThisBB;
1754
1755   CurMBB->addSuccessor(B.Default);
1756   CurMBB->addSuccessor(MBB);
1757
1758   SDValue BrRange = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, RangeCmp,
1759                                   DAG.getBasicBlock(B.Default));
1760
1761   if (MBB == NextBlock)
1762     DAG.setRoot(BrRange);
1763   else
1764     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, CopyTo,
1765                             DAG.getBasicBlock(MBB)));
1766
1767   return;
1768 }
1769
1770 /// visitBitTestCase - this function produces one "bit test"
1771 void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB,
1772                                             unsigned Reg,
1773                                             SelectionDAGISel::BitTestCase &B) {
1774   // Emit bit tests and jumps
1775   SDValue SwitchVal = DAG.getCopyFromReg(getControlRoot(), Reg,
1776                                            TLI.getPointerTy());
1777
1778   SDValue AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(), SwitchVal,
1779                                 DAG.getConstant(B.Mask, TLI.getPointerTy()));
1780   SDValue AndCmp = DAG.getSetCC(TLI.getSetCCResultType(AndOp), AndOp,
1781                                   DAG.getConstant(0, TLI.getPointerTy()),
1782                                   ISD::SETNE);
1783
1784   CurMBB->addSuccessor(B.TargetBB);
1785   CurMBB->addSuccessor(NextMBB);
1786
1787   SDValue BrAnd = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(),
1788                                 AndCmp, DAG.getBasicBlock(B.TargetBB));
1789
1790   // Set NextBlock to be the MBB immediately after the current one, if any.
1791   // This is used to avoid emitting unnecessary branches to the next block.
1792   MachineBasicBlock *NextBlock = 0;
1793   MachineFunction::iterator BBI = CurMBB;
1794   if (++BBI != CurMBB->getParent()->end())
1795     NextBlock = BBI;
1796
1797   if (NextMBB == NextBlock)
1798     DAG.setRoot(BrAnd);
1799   else
1800     DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrAnd,
1801                             DAG.getBasicBlock(NextMBB)));
1802
1803   return;
1804 }
1805
1806 void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
1807   // Retrieve successors.
1808   MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1809   MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1810
1811   if (isa<InlineAsm>(I.getCalledValue()))
1812     visitInlineAsm(&I);
1813   else
1814     LowerCallTo(&I, getValue(I.getOperand(0)), false, LandingPad);
1815
1816   // If the value of the invoke is used outside of its defining block, make it
1817   // available as a virtual register.
1818   if (!I.use_empty()) {
1819     DenseMap<const Value*, unsigned>::iterator VMI = FuncInfo.ValueMap.find(&I);
1820     if (VMI != FuncInfo.ValueMap.end())
1821       CopyValueToVirtualRegister(&I, VMI->second);
1822   }
1823
1824   // Update successor info
1825   CurMBB->addSuccessor(Return);
1826   CurMBB->addSuccessor(LandingPad);
1827
1828   // Drop into normal successor.
1829   DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(),
1830                           DAG.getBasicBlock(Return)));
1831 }
1832
1833 void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
1834 }
1835
1836 /// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for
1837 /// small case ranges).
1838 bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
1839                                                   CaseRecVector& WorkList,
1840                                                   Value* SV,
1841                                                   MachineBasicBlock* Default) {
1842   Case& BackCase  = *(CR.Range.second-1);
1843
1844   // Size is the number of Cases represented by this range.
1845   unsigned Size = CR.Range.second - CR.Range.first;
1846   if (Size > 3)
1847     return false;
1848
1849   // Get the MachineFunction which holds the current MBB.  This is used when
1850   // inserting any additional MBBs necessary to represent the switch.
1851   MachineFunction *CurMF = CurMBB->getParent();
1852
1853   // Figure out which block is immediately after the current one.
1854   MachineBasicBlock *NextBlock = 0;
1855   MachineFunction::iterator BBI = CR.CaseBB;
1856
1857   if (++BBI != CurMBB->getParent()->end())
1858     NextBlock = BBI;
1859
1860   // TODO: If any two of the cases has the same destination, and if one value
1861   // is the same as the other, but has one bit unset that the other has set,
1862   // use bit manipulation to do two compares at once.  For example:
1863   // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
1864
1865   // Rearrange the case blocks so that the last one falls through if possible.
1866   if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) {
1867     // The last case block won't fall through into 'NextBlock' if we emit the
1868     // branches in this order.  See if rearranging a case value would help.
1869     for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
1870       if (I->BB == NextBlock) {
1871         std::swap(*I, BackCase);
1872         break;
1873       }
1874     }
1875   }
1876
1877   // Create a CaseBlock record representing a conditional branch to
1878   // the Case's target mbb if the value being switched on SV is equal
1879   // to C.
1880   MachineBasicBlock *CurBlock = CR.CaseBB;
1881   for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
1882     MachineBasicBlock *FallThrough;
1883     if (I != E-1) {
1884       FallThrough = CurMF->CreateMachineBasicBlock(CurBlock->getBasicBlock());
1885       CurMF->insert(BBI, FallThrough);
1886     } else {
1887       // If the last case doesn't match, go to the default block.
1888       FallThrough = Default;
1889     }
1890
1891     Value *RHS, *LHS, *MHS;
1892     ISD::CondCode CC;
1893     if (I->High == I->Low) {
1894       // This is just small small case range :) containing exactly 1 case
1895       CC = ISD::SETEQ;
1896       LHS = SV; RHS = I->High; MHS = NULL;
1897     } else {
1898       CC = ISD::SETLE;
1899       LHS = I->Low; MHS = SV; RHS = I->High;
1900     }
1901     SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS,
1902                                    I->BB, FallThrough, CurBlock);
1903
1904     // If emitting the first comparison, just call visitSwitchCase to emit the
1905     // code into the current block.  Otherwise, push the CaseBlock onto the
1906     // vector to be later processed by SDISel, and insert the node's MBB
1907     // before the next MBB.
1908     if (CurBlock == CurMBB)
1909       visitSwitchCase(CB);
1910     else
1911       SwitchCases.push_back(CB);
1912
1913     CurBlock = FallThrough;
1914   }
1915
1916   return true;
1917 }
1918
1919 static inline bool areJTsAllowed(const TargetLowering &TLI) {
1920   return !DisableJumpTables &&
1921           (TLI.isOperationLegal(ISD::BR_JT, MVT::Other) ||
1922            TLI.isOperationLegal(ISD::BRIND, MVT::Other));
1923 }
1924
1925 /// handleJTSwitchCase - Emit jumptable for current switch case range
1926 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
1927                                               CaseRecVector& WorkList,
1928                                               Value* SV,
1929                                               MachineBasicBlock* Default) {
1930   Case& FrontCase = *CR.Range.first;
1931   Case& BackCase  = *(CR.Range.second-1);
1932
1933   int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
1934   int64_t Last  = cast<ConstantInt>(BackCase.High)->getSExtValue();
1935
1936   uint64_t TSize = 0;
1937   for (CaseItr I = CR.Range.first, E = CR.Range.second;
1938        I!=E; ++I)
1939     TSize += I->size();
1940
1941   if (!areJTsAllowed(TLI) || TSize <= 3)
1942     return false;
1943
1944   double Density = (double)TSize / (double)((Last - First) + 1ULL);
1945   if (Density < 0.4)
1946     return false;
1947
1948   DOUT << "Lowering jump table\n"
1949        << "First entry: " << First << ". Last entry: " << Last << "\n"
1950        << "Size: " << TSize << ". Density: " << Density << "\n\n";
1951
1952   // Get the MachineFunction which holds the current MBB.  This is used when
1953   // inserting any additional MBBs necessary to represent the switch.
1954   MachineFunction *CurMF = CurMBB->getParent();
1955
1956   // Figure out which block is immediately after the current one.
1957   MachineBasicBlock *NextBlock = 0;
1958   MachineFunction::iterator BBI = CR.CaseBB;
1959
1960   if (++BBI != CurMBB->getParent()->end())
1961     NextBlock = BBI;
1962
1963   const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1964
1965   // Create a new basic block to hold the code for loading the address
1966   // of the jump table, and jumping to it.  Update successor information;
1967   // we will either branch to the default case for the switch, or the jump
1968   // table.
1969   MachineBasicBlock *JumpTableBB = CurMF->CreateMachineBasicBlock(LLVMBB);
1970   CurMF->insert(BBI, JumpTableBB);
1971   CR.CaseBB->addSuccessor(Default);
1972   CR.CaseBB->addSuccessor(JumpTableBB);
1973
1974   // Build a vector of destination BBs, corresponding to each target
1975   // of the jump table. If the value of the jump table slot corresponds to
1976   // a case statement, push the case's BB onto the vector, otherwise, push
1977   // the default BB.
1978   std::vector<MachineBasicBlock*> DestBBs;
1979   int64_t TEI = First;
1980   for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) {
1981     int64_t Low = cast<ConstantInt>(I->Low)->getSExtValue();
1982     int64_t High = cast<ConstantInt>(I->High)->getSExtValue();
1983
1984     if ((Low <= TEI) && (TEI <= High)) {
1985       DestBBs.push_back(I->BB);
1986       if (TEI==High)
1987         ++I;
1988     } else {
1989       DestBBs.push_back(Default);
1990     }
1991   }
1992
1993   // Update successor info. Add one edge to each unique successor.
1994   BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs());
1995   for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
1996          E = DestBBs.end(); I != E; ++I) {
1997     if (!SuccsHandled[(*I)->getNumber()]) {
1998       SuccsHandled[(*I)->getNumber()] = true;
1999       JumpTableBB->addSuccessor(*I);
2000     }
2001   }
2002
2003   // Create a jump table index for this jump table, or return an existing
2004   // one.
2005   unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
2006
2007   // Set the jump table information so that we can codegen it as a second
2008   // MachineBasicBlock
2009   SelectionDAGISel::JumpTable JT(-1U, JTI, JumpTableBB, Default);
2010   SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
2011                                         (CR.CaseBB == CurMBB));
2012   if (CR.CaseBB == CurMBB)
2013     visitJumpTableHeader(JT, JTH);
2014
2015   JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT));
2016
2017   return true;
2018 }
2019
2020 /// handleBTSplitSwitchCase - emit comparison and split binary search tree into
2021 /// 2 subtrees.
2022 bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
2023                                                    CaseRecVector& WorkList,
2024                                                    Value* SV,
2025                                                    MachineBasicBlock* Default) {
2026   // Get the MachineFunction which holds the current MBB.  This is used when
2027   // inserting any additional MBBs necessary to represent the switch.
2028   MachineFunction *CurMF = CurMBB->getParent();
2029
2030   // Figure out which block is immediately after the current one.
2031   MachineBasicBlock *NextBlock = 0;
2032   MachineFunction::iterator BBI = CR.CaseBB;
2033
2034   if (++BBI != CurMBB->getParent()->end())
2035     NextBlock = BBI;
2036
2037   Case& FrontCase = *CR.Range.first;
2038   Case& BackCase  = *(CR.Range.second-1);
2039   const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
2040
2041   // Size is the number of Cases represented by this range.
2042   unsigned Size = CR.Range.second - CR.Range.first;
2043
2044   int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
2045   int64_t Last  = cast<ConstantInt>(BackCase.High)->getSExtValue();
2046   double FMetric = 0;
2047   CaseItr Pivot = CR.Range.first + Size/2;
2048
2049   // Select optimal pivot, maximizing sum density of LHS and RHS. This will
2050   // (heuristically) allow us to emit JumpTable's later.
2051   uint64_t TSize = 0;
2052   for (CaseItr I = CR.Range.first, E = CR.Range.second;
2053        I!=E; ++I)
2054     TSize += I->size();
2055
2056   uint64_t LSize = FrontCase.size();
2057   uint64_t RSize = TSize-LSize;
2058   DOUT << "Selecting best pivot: \n"
2059        << "First: " << First << ", Last: " << Last <<"\n"
2060        << "LSize: " << LSize << ", RSize: " << RSize << "\n";
2061   for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
2062        J!=E; ++I, ++J) {
2063     int64_t LEnd = cast<ConstantInt>(I->High)->getSExtValue();
2064     int64_t RBegin = cast<ConstantInt>(J->Low)->getSExtValue();
2065     assert((RBegin-LEnd>=1) && "Invalid case distance");
2066     double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL);
2067     double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL);
2068     double Metric = Log2_64(RBegin-LEnd)*(LDensity+RDensity);
2069     // Should always split in some non-trivial place
2070     DOUT <<"=>Step\n"
2071          << "LEnd: " << LEnd << ", RBegin: " << RBegin << "\n"
2072          << "LDensity: " << LDensity << ", RDensity: " << RDensity << "\n"
2073          << "Metric: " << Metric << "\n";
2074     if (FMetric < Metric) {
2075       Pivot = J;
2076       FMetric = Metric;
2077       DOUT << "Current metric set to: " << FMetric << "\n";
2078     }
2079
2080     LSize += J->size();
2081     RSize -= J->size();
2082   }
2083   if (areJTsAllowed(TLI)) {
2084     // If our case is dense we *really* should handle it earlier!
2085     assert((FMetric > 0) && "Should handle dense range earlier!");
2086   } else {
2087     Pivot = CR.Range.first + Size/2;
2088   }
2089
2090   CaseRange LHSR(CR.Range.first, Pivot);
2091   CaseRange RHSR(Pivot, CR.Range.second);
2092   Constant *C = Pivot->Low;
2093   MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
2094
2095   // We know that we branch to the LHS if the Value being switched on is
2096   // less than the Pivot value, C.  We use this to optimize our binary
2097   // tree a bit, by recognizing that if SV is greater than or equal to the
2098   // LHS's Case Value, and that Case Value is exactly one less than the
2099   // Pivot's Value, then we can branch directly to the LHS's Target,
2100   // rather than creating a leaf node for it.
2101   if ((LHSR.second - LHSR.first) == 1 &&
2102       LHSR.first->High == CR.GE &&
2103       cast<ConstantInt>(C)->getSExtValue() ==
2104       (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) {
2105     TrueBB = LHSR.first->BB;
2106   } else {
2107     TrueBB = CurMF->CreateMachineBasicBlock(LLVMBB);
2108     CurMF->insert(BBI, TrueBB);
2109     WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
2110   }
2111
2112   // Similar to the optimization above, if the Value being switched on is
2113   // known to be less than the Constant CR.LT, and the current Case Value
2114   // is CR.LT - 1, then we can branch directly to the target block for
2115   // the current Case Value, rather than emitting a RHS leaf node for it.
2116   if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
2117       cast<ConstantInt>(RHSR.first->Low)->getSExtValue() ==
2118       (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) {
2119     FalseBB = RHSR.first->BB;
2120   } else {
2121     FalseBB = CurMF->CreateMachineBasicBlock(LLVMBB);
2122     CurMF->insert(BBI, FalseBB);
2123     WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
2124   }
2125
2126   // Create a CaseBlock record representing a conditional branch to
2127   // the LHS node if the value being switched on SV is less than C.
2128   // Otherwise, branch to LHS.
2129   SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL,
2130                                  TrueBB, FalseBB, CR.CaseBB);
2131
2132   if (CR.CaseBB == CurMBB)
2133     visitSwitchCase(CB);
2134   else
2135     SwitchCases.push_back(CB);
2136
2137   return true;
2138 }
2139
2140 /// handleBitTestsSwitchCase - if current case range has few destination and
2141 /// range span less, than machine word bitwidth, encode case range into series
2142 /// of masks and emit bit tests with these masks.
2143 bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR,
2144                                                     CaseRecVector& WorkList,
2145                                                     Value* SV,
2146                                                     MachineBasicBlock* Default){
2147   unsigned IntPtrBits = TLI.getPointerTy().getSizeInBits();
2148
2149   Case& FrontCase = *CR.Range.first;
2150   Case& BackCase  = *(CR.Range.second-1);
2151
2152   // Get the MachineFunction which holds the current MBB.  This is used when
2153   // inserting any additional MBBs necessary to represent the switch.
2154   MachineFunction *CurMF = CurMBB->getParent();
2155
2156   unsigned numCmps = 0;
2157   for (CaseItr I = CR.Range.first, E = CR.Range.second;
2158        I!=E; ++I) {
2159     // Single case counts one, case range - two.
2160     if (I->Low == I->High)
2161       numCmps +=1;
2162     else
2163       numCmps +=2;
2164   }
2165
2166   // Count unique destinations
2167   SmallSet<MachineBasicBlock*, 4> Dests;
2168   for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) {
2169     Dests.insert(I->BB);
2170     if (Dests.size() > 3)
2171       // Don't bother the code below, if there are too much unique destinations
2172       return false;
2173   }
2174   DOUT << "Total number of unique destinations: " << Dests.size() << "\n"
2175        << "Total number of comparisons: " << numCmps << "\n";
2176
2177   // Compute span of values.
2178   Constant* minValue = FrontCase.Low;
2179   Constant* maxValue = BackCase.High;
2180   uint64_t range = cast<ConstantInt>(maxValue)->getSExtValue() -
2181                    cast<ConstantInt>(minValue)->getSExtValue();
2182   DOUT << "Compare range: " << range << "\n"
2183        << "Low bound: " << cast<ConstantInt>(minValue)->getSExtValue() << "\n"
2184        << "High bound: " << cast<ConstantInt>(maxValue)->getSExtValue() << "\n";
2185
2186   if (range>=IntPtrBits ||
2187       (!(Dests.size() == 1 && numCmps >= 3) &&
2188        !(Dests.size() == 2 && numCmps >= 5) &&
2189        !(Dests.size() >= 3 && numCmps >= 6)))
2190     return false;
2191
2192   DOUT << "Emitting bit tests\n";
2193   int64_t lowBound = 0;
2194
2195   // Optimize the case where all the case values fit in a
2196   // word without having to subtract minValue. In this case,
2197   // we can optimize away the subtraction.
2198   if (cast<ConstantInt>(minValue)->getSExtValue() >= 0 &&
2199       cast<ConstantInt>(maxValue)->getSExtValue() <  IntPtrBits) {
2200     range = cast<ConstantInt>(maxValue)->getSExtValue();
2201   } else {
2202     lowBound = cast<ConstantInt>(minValue)->getSExtValue();
2203   }
2204
2205   CaseBitsVector CasesBits;
2206   unsigned i, count = 0;
2207
2208   for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) {
2209     MachineBasicBlock* Dest = I->BB;
2210     for (i = 0; i < count; ++i)
2211       if (Dest == CasesBits[i].BB)
2212         break;
2213
2214     if (i == count) {
2215       assert((count < 3) && "Too much destinations to test!");
2216       CasesBits.push_back(CaseBits(0, Dest, 0));
2217       count++;
2218     }
2219
2220     uint64_t lo = cast<ConstantInt>(I->Low)->getSExtValue() - lowBound;
2221     uint64_t hi = cast<ConstantInt>(I->High)->getSExtValue() - lowBound;
2222
2223     for (uint64_t j = lo; j <= hi; j++) {
2224       CasesBits[i].Mask |=  1ULL << j;
2225       CasesBits[i].Bits++;
2226     }
2227
2228   }
2229   std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp());
2230
2231   SelectionDAGISel::BitTestInfo BTC;
2232
2233   // Figure out which block is immediately after the current one.
2234   MachineFunction::iterator BBI = CR.CaseBB;
2235   ++BBI;
2236
2237   const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
2238
2239   DOUT << "Cases:\n";
2240   for (unsigned i = 0, e = CasesBits.size(); i!=e; ++i) {
2241     DOUT << "Mask: " << CasesBits[i].Mask << ", Bits: " << CasesBits[i].Bits
2242          << ", BB: " << CasesBits[i].BB << "\n";
2243
2244     MachineBasicBlock *CaseBB = CurMF->CreateMachineBasicBlock(LLVMBB);
2245     CurMF->insert(BBI, CaseBB);
2246     BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask,
2247                                                 CaseBB,
2248                                                 CasesBits[i].BB));
2249   }
2250
2251   SelectionDAGISel::BitTestBlock BTB(lowBound, range, SV,
2252                                      -1U, (CR.CaseBB == CurMBB),
2253                                      CR.CaseBB, Default, BTC);
2254
2255   if (CR.CaseBB == CurMBB)
2256     visitBitTestHeader(BTB);
2257
2258   BitTestCases.push_back(BTB);
2259
2260   return true;
2261 }
2262
2263
2264 /// Clusterify - Transform simple list of Cases into list of CaseRange's
2265 unsigned SelectionDAGLowering::Clusterify(CaseVector& Cases,
2266                                           const SwitchInst& SI) {
2267   unsigned numCmps = 0;
2268
2269   // Start with "simple" cases
2270   for (unsigned i = 1; i < SI.getNumSuccessors(); ++i) {
2271     MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)];
2272     Cases.push_back(Case(SI.getSuccessorValue(i),
2273                          SI.getSuccessorValue(i),
2274                          SMBB));
2275   }
2276   std::sort(Cases.begin(), Cases.end(), CaseCmp());
2277
2278   // Merge case into clusters
2279   if (Cases.size()>=2)
2280     // Must recompute end() each iteration because it may be
2281     // invalidated by erase if we hold on to it
2282     for (CaseItr I=Cases.begin(), J=++(Cases.begin()); J!=Cases.end(); ) {
2283       int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue();
2284       int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue();
2285       MachineBasicBlock* nextBB = J->BB;
2286       MachineBasicBlock* currentBB = I->BB;
2287
2288       // If the two neighboring cases go to the same destination, merge them
2289       // into a single case.
2290       if ((nextValue-currentValue==1) && (currentBB == nextBB)) {
2291         I->High = J->High;
2292         J = Cases.erase(J);
2293       } else {
2294         I = J++;
2295       }
2296     }
2297
2298   for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
2299     if (I->Low != I->High)
2300       // A range counts double, since it requires two compares.
2301       ++numCmps;
2302   }
2303
2304   return numCmps;
2305 }
2306
2307 void SelectionDAGLowering::visitSwitch(SwitchInst &SI) {
2308   // Figure out which block is immediately after the current one.
2309   MachineBasicBlock *NextBlock = 0;
2310   MachineFunction::iterator BBI = CurMBB;
2311
2312   MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
2313
2314   // If there is only the default destination, branch to it if it is not the
2315   // next basic block.  Otherwise, just fall through.
2316   if (SI.getNumOperands() == 2) {
2317     // Update machine-CFG edges.
2318
2319     // If this is not a fall-through branch, emit the branch.
2320     CurMBB->addSuccessor(Default);
2321     if (Default != NextBlock)
2322       DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(),
2323                               DAG.getBasicBlock(Default)));
2324
2325     return;
2326   }
2327
2328   // If there are any non-default case statements, create a vector of Cases
2329   // representing each one, and sort the vector so that we can efficiently
2330   // create a binary search tree from them.
2331   CaseVector Cases;
2332   unsigned numCmps = Clusterify(Cases, SI);
2333   DOUT << "Clusterify finished. Total clusters: " << Cases.size()
2334        << ". Total compares: " << numCmps << "\n";
2335
2336   // Get the Value to be switched on and default basic blocks, which will be
2337   // inserted into CaseBlock records, representing basic blocks in the binary
2338   // search tree.
2339   Value *SV = SI.getOperand(0);
2340
2341   // Push the initial CaseRec onto the worklist
2342   CaseRecVector WorkList;
2343   WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
2344
2345   while (!WorkList.empty()) {
2346     // Grab a record representing a case range to process off the worklist
2347     CaseRec CR = WorkList.back();
2348     WorkList.pop_back();
2349
2350     if (handleBitTestsSwitchCase(CR, WorkList, SV, Default))
2351       continue;
2352
2353     // If the range has few cases (two or less) emit a series of specific
2354     // tests.
2355     if (handleSmallSwitchRange(CR, WorkList, SV, Default))
2356       continue;
2357
2358     // If the switch has more than 5 blocks, and at least 40% dense, and the
2359     // target supports indirect branches, then emit a jump table rather than
2360     // lowering the switch to a binary tree of conditional branches.
2361     if (handleJTSwitchCase(CR, WorkList, SV, Default))
2362       continue;
2363
2364     // Emit binary tree. We need to pick a pivot, and push left and right ranges
2365     // onto the worklist. Leafs are handled via handleSmallSwitchRange() call.
2366     handleBTSplitSwitchCase(CR, WorkList, SV, Default);
2367   }
2368 }
2369
2370
2371 void SelectionDAGLowering::visitSub(User &I) {
2372   // -0.0 - X --> fneg
2373   const Type *Ty = I.getType();
2374   if (isa<VectorType>(Ty)) {
2375     if (ConstantVector *CV = dyn_cast<ConstantVector>(I.getOperand(0))) {
2376       const VectorType *DestTy = cast<VectorType>(I.getType());
2377       const Type *ElTy = DestTy->getElementType();
2378       if (ElTy->isFloatingPoint()) {
2379         unsigned VL = DestTy->getNumElements();
2380         std::vector<Constant*> NZ(VL, ConstantFP::getNegativeZero(ElTy));
2381         Constant *CNZ = ConstantVector::get(&NZ[0], NZ.size());
2382         if (CV == CNZ) {
2383           SDValue Op2 = getValue(I.getOperand(1));
2384           setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
2385           return;
2386         }
2387       }
2388     }
2389   }
2390   if (Ty->isFloatingPoint()) {
2391     if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
2392       if (CFP->isExactlyValue(ConstantFP::getNegativeZero(Ty)->getValueAPF())) {
2393         SDValue Op2 = getValue(I.getOperand(1));
2394         setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
2395         return;
2396       }
2397   }
2398
2399   visitBinary(I, Ty->isFPOrFPVector() ? ISD::FSUB : ISD::SUB);
2400 }
2401
2402 void SelectionDAGLowering::visitBinary(User &I, unsigned OpCode) {
2403   SDValue Op1 = getValue(I.getOperand(0));
2404   SDValue Op2 = getValue(I.getOperand(1));
2405
2406   setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
2407 }
2408
2409 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
2410   SDValue Op1 = getValue(I.getOperand(0));
2411   SDValue Op2 = getValue(I.getOperand(1));
2412   if (!isa<VectorType>(I.getType())) {
2413     if (TLI.getShiftAmountTy().bitsLT(Op2.getValueType()))
2414       Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
2415     else if (TLI.getShiftAmountTy().bitsGT(Op2.getValueType()))
2416       Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
2417   }
2418
2419   setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
2420 }
2421
2422 void SelectionDAGLowering::visitICmp(User &I) {
2423   ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
2424   if (ICmpInst *IC = dyn_cast<ICmpInst>(&I))
2425     predicate = IC->getPredicate();
2426   else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
2427     predicate = ICmpInst::Predicate(IC->getPredicate());
2428   SDValue Op1 = getValue(I.getOperand(0));
2429   SDValue Op2 = getValue(I.getOperand(1));
2430   ISD::CondCode Opcode;
2431   switch (predicate) {
2432     case ICmpInst::ICMP_EQ  : Opcode = ISD::SETEQ; break;
2433     case ICmpInst::ICMP_NE  : Opcode = ISD::SETNE; break;
2434     case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
2435     case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
2436     case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
2437     case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
2438     case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
2439     case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
2440     case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
2441     case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
2442     default:
2443       assert(!"Invalid ICmp predicate value");
2444       Opcode = ISD::SETEQ;
2445       break;
2446   }
2447   setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
2448 }
2449
2450 void SelectionDAGLowering::visitFCmp(User &I) {
2451   FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
2452   if (FCmpInst *FC = dyn_cast<FCmpInst>(&I))
2453     predicate = FC->getPredicate();
2454   else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
2455     predicate = FCmpInst::Predicate(FC->getPredicate());
2456   SDValue Op1 = getValue(I.getOperand(0));
2457   SDValue Op2 = getValue(I.getOperand(1));
2458   ISD::CondCode Condition, FOC, FPC;
2459   switch (predicate) {
2460     case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
2461     case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
2462     case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
2463     case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
2464     case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
2465     case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
2466     case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
2467     case FCmpInst::FCMP_ORD:   FOC = FPC = ISD::SETO;   break;
2468     case FCmpInst::FCMP_UNO:   FOC = FPC = ISD::SETUO;  break;
2469     case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
2470     case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
2471     case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
2472     case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
2473     case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
2474     case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
2475     case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
2476     default:
2477       assert(!"Invalid FCmp predicate value");
2478       FOC = FPC = ISD::SETFALSE;
2479       break;
2480   }
2481   if (FiniteOnlyFPMath())
2482     Condition = FOC;
2483   else
2484     Condition = FPC;
2485   setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition));
2486 }
2487
2488 void SelectionDAGLowering::visitVICmp(User &I) {
2489   ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
2490   if (VICmpInst *IC = dyn_cast<VICmpInst>(&I))
2491     predicate = IC->getPredicate();
2492   else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
2493     predicate = ICmpInst::Predicate(IC->getPredicate());
2494   SDValue Op1 = getValue(I.getOperand(0));
2495   SDValue Op2 = getValue(I.getOperand(1));
2496   ISD::CondCode Opcode;
2497   switch (predicate) {
2498     case ICmpInst::ICMP_EQ  : Opcode = ISD::SETEQ; break;
2499     case ICmpInst::ICMP_NE  : Opcode = ISD::SETNE; break;
2500     case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
2501     case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
2502     case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
2503     case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
2504     case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
2505     case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
2506     case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
2507     case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
2508     default:
2509       assert(!"Invalid ICmp predicate value");
2510       Opcode = ISD::SETEQ;
2511       break;
2512   }
2513   setValue(&I, DAG.getVSetCC(Op1.getValueType(), Op1, Op2, Opcode));
2514 }
2515
2516 void SelectionDAGLowering::visitVFCmp(User &I) {
2517   FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
2518   if (VFCmpInst *FC = dyn_cast<VFCmpInst>(&I))
2519     predicate = FC->getPredicate();
2520   else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
2521     predicate = FCmpInst::Predicate(FC->getPredicate());
2522   SDValue Op1 = getValue(I.getOperand(0));
2523   SDValue Op2 = getValue(I.getOperand(1));
2524   ISD::CondCode Condition, FOC, FPC;
2525   switch (predicate) {
2526     case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
2527     case FCmpInst::FCMP_OEQ:   FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
2528     case FCmpInst::FCMP_OGT:   FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
2529     case FCmpInst::FCMP_OGE:   FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
2530     case FCmpInst::FCMP_OLT:   FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
2531     case FCmpInst::FCMP_OLE:   FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
2532     case FCmpInst::FCMP_ONE:   FOC = ISD::SETNE; FPC = ISD::SETONE; break;
2533     case FCmpInst::FCMP_ORD:   FOC = FPC = ISD::SETO;   break;
2534     case FCmpInst::FCMP_UNO:   FOC = FPC = ISD::SETUO;  break;
2535     case FCmpInst::FCMP_UEQ:   FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
2536     case FCmpInst::FCMP_UGT:   FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
2537     case FCmpInst::FCMP_UGE:   FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
2538     case FCmpInst::FCMP_ULT:   FOC = ISD::SETLT; FPC = ISD::SETULT; break;
2539     case FCmpInst::FCMP_ULE:   FOC = ISD::SETLE; FPC = ISD::SETULE; break;
2540     case FCmpInst::FCMP_UNE:   FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
2541     case FCmpInst::FCMP_TRUE:  FOC = FPC = ISD::SETTRUE; break;
2542     default:
2543       assert(!"Invalid VFCmp predicate value");
2544       FOC = FPC = ISD::SETFALSE;
2545       break;
2546   }
2547   if (FiniteOnlyFPMath())
2548     Condition = FOC;
2549   else
2550     Condition = FPC;
2551
2552   MVT DestVT = TLI.getValueType(I.getType());
2553
2554   setValue(&I, DAG.getVSetCC(DestVT, Op1, Op2, Condition));
2555 }
2556
2557 void SelectionDAGLowering::visitSelect(User &I) {
2558   SDValue Cond     = getValue(I.getOperand(0));
2559   SDValue TrueVal  = getValue(I.getOperand(1));
2560   SDValue FalseVal = getValue(I.getOperand(2));
2561   setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
2562                            TrueVal, FalseVal));
2563 }
2564
2565
2566 void SelectionDAGLowering::visitTrunc(User &I) {
2567   // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
2568   SDValue N = getValue(I.getOperand(0));
2569   MVT DestVT = TLI.getValueType(I.getType());
2570   setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
2571 }
2572
2573 void SelectionDAGLowering::visitZExt(User &I) {
2574   // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
2575   // ZExt also can't be a cast to bool for same reason. So, nothing much to do
2576   SDValue N = getValue(I.getOperand(0));
2577   MVT DestVT = TLI.getValueType(I.getType());
2578   setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
2579 }
2580
2581 void SelectionDAGLowering::visitSExt(User &I) {
2582   // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
2583   // SExt also can't be a cast to bool for same reason. So, nothing much to do
2584   SDValue N = getValue(I.getOperand(0));
2585   MVT DestVT = TLI.getValueType(I.getType());
2586   setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N));
2587 }
2588
2589 void SelectionDAGLowering::visitFPTrunc(User &I) {
2590   // FPTrunc is never a no-op cast, no need to check
2591   SDValue N = getValue(I.getOperand(0));
2592   MVT DestVT = TLI.getValueType(I.getType());
2593   setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N, DAG.getIntPtrConstant(0)));
2594 }
2595
2596 void SelectionDAGLowering::visitFPExt(User &I){
2597   // FPTrunc is never a no-op cast, no need to check
2598   SDValue N = getValue(I.getOperand(0));
2599   MVT DestVT = TLI.getValueType(I.getType());
2600   setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N));
2601 }
2602
2603 void SelectionDAGLowering::visitFPToUI(User &I) {
2604   // FPToUI is never a no-op cast, no need to check
2605   SDValue N = getValue(I.getOperand(0));
2606   MVT DestVT = TLI.getValueType(I.getType());
2607   setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N));
2608 }
2609
2610 void SelectionDAGLowering::visitFPToSI(User &I) {
2611   // FPToSI is never a no-op cast, no need to check
2612   SDValue N = getValue(I.getOperand(0));
2613   MVT DestVT = TLI.getValueType(I.getType());
2614   setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N));
2615 }
2616
2617 void SelectionDAGLowering::visitUIToFP(User &I) {
2618   // UIToFP is never a no-op cast, no need to check
2619   SDValue N = getValue(I.getOperand(0));
2620   MVT DestVT = TLI.getValueType(I.getType());
2621   setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N));
2622 }
2623
2624 void SelectionDAGLowering::visitSIToFP(User &I){
2625   // UIToFP is never a no-op cast, no need to check
2626   SDValue N = getValue(I.getOperand(0));
2627   MVT DestVT = TLI.getValueType(I.getType());
2628   setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N));
2629 }
2630
2631 void SelectionDAGLowering::visitPtrToInt(User &I) {
2632   // What to do depends on the size of the integer and the size of the pointer.
2633   // We can either truncate, zero extend, or no-op, accordingly.
2634   SDValue N = getValue(I.getOperand(0));
2635   MVT SrcVT = N.getValueType();
2636   MVT DestVT = TLI.getValueType(I.getType());
2637   SDValue Result;
2638   if (DestVT.bitsLT(SrcVT))
2639     Result = DAG.getNode(ISD::TRUNCATE, DestVT, N);
2640   else
2641     // Note: ZERO_EXTEND can handle cases where the sizes are equal too
2642     Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N);
2643   setValue(&I, Result);
2644 }
2645
2646 void SelectionDAGLowering::visitIntToPtr(User &I) {
2647   // What to do depends on the size of the integer and the size of the pointer.
2648   // We can either truncate, zero extend, or no-op, accordingly.
2649   SDValue N = getValue(I.getOperand(0));
2650   MVT SrcVT = N.getValueType();
2651   MVT DestVT = TLI.getValueType(I.getType());
2652   if (DestVT.bitsLT(SrcVT))
2653     setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
2654   else
2655     // Note: ZERO_EXTEND can handle cases where the sizes are equal too
2656     setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
2657 }
2658
2659 void SelectionDAGLowering::visitBitCast(User &I) {
2660   SDValue N = getValue(I.getOperand(0));
2661   MVT DestVT = TLI.getValueType(I.getType());
2662
2663   // BitCast assures us that source and destination are the same size so this
2664   // is either a BIT_CONVERT or a no-op.
2665   if (DestVT != N.getValueType())
2666     setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types
2667   else
2668     setValue(&I, N); // noop cast.
2669 }
2670
2671 void SelectionDAGLowering::visitInsertElement(User &I) {
2672   SDValue InVec = getValue(I.getOperand(0));
2673   SDValue InVal = getValue(I.getOperand(1));
2674   SDValue InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
2675                                 getValue(I.getOperand(2)));
2676
2677   setValue(&I, DAG.getNode(ISD::INSERT_VECTOR_ELT,
2678                            TLI.getValueType(I.getType()),
2679                            InVec, InVal, InIdx));
2680 }
2681
2682 void SelectionDAGLowering::visitExtractElement(User &I) {
2683   SDValue InVec = getValue(I.getOperand(0));
2684   SDValue InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
2685                                 getValue(I.getOperand(1)));
2686   setValue(&I, DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
2687                            TLI.getValueType(I.getType()), InVec, InIdx));
2688 }
2689
2690 void SelectionDAGLowering::visitShuffleVector(User &I) {
2691   SDValue V1   = getValue(I.getOperand(0));
2692   SDValue V2   = getValue(I.getOperand(1));
2693   SDValue Mask = getValue(I.getOperand(2));
2694
2695   setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE,
2696                            TLI.getValueType(I.getType()),
2697                            V1, V2, Mask));
2698 }
2699
2700 void SelectionDAGLowering::visitInsertValue(InsertValueInst &I) {
2701   const Value *Op0 = I.getOperand(0);
2702   const Value *Op1 = I.getOperand(1);
2703   const Type *AggTy = I.getType();
2704   const Type *ValTy = Op1->getType();
2705   bool IntoUndef = isa<UndefValue>(Op0);
2706   bool FromUndef = isa<UndefValue>(Op1);
2707
2708   unsigned LinearIndex = ComputeLinearIndex(TLI, AggTy,
2709                                             I.idx_begin(), I.idx_end());
2710
2711   SmallVector<MVT, 4> AggValueVTs;
2712   ComputeValueVTs(TLI, AggTy, AggValueVTs);
2713   SmallVector<MVT, 4> ValValueVTs;
2714   ComputeValueVTs(TLI, ValTy, ValValueVTs);
2715
2716   unsigned NumAggValues = AggValueVTs.size();
2717   unsigned NumValValues = ValValueVTs.size();
2718   SmallVector<SDValue, 4> Values(NumAggValues);
2719
2720   SDValue Agg = getValue(Op0);
2721   SDValue Val = getValue(Op1);
2722   unsigned i = 0;
2723   // Copy the beginning value(s) from the original aggregate.
2724   for (; i != LinearIndex; ++i)
2725     Values[i] = IntoUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) :
2726                 SDValue(Agg.Val, Agg.ResNo + i);
2727   // Copy values from the inserted value(s).
2728   for (; i != LinearIndex + NumValValues; ++i)
2729     Values[i] = FromUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) :
2730                 SDValue(Val.Val, Val.ResNo + i - LinearIndex);
2731   // Copy remaining value(s) from the original aggregate.
2732   for (; i != NumAggValues; ++i)
2733     Values[i] = IntoUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) :
2734                 SDValue(Agg.Val, Agg.ResNo + i);
2735
2736   setValue(&I, DAG.getMergeValues(DAG.getVTList(&AggValueVTs[0], NumAggValues),
2737                                   &Values[0], NumAggValues));
2738 }
2739
2740 void SelectionDAGLowering::visitExtractValue(ExtractValueInst &I) {
2741   const Value *Op0 = I.getOperand(0);
2742   const Type *AggTy = Op0->getType();
2743   const Type *ValTy = I.getType();
2744   bool OutOfUndef = isa<UndefValue>(Op0);
2745
2746   unsigned LinearIndex = ComputeLinearIndex(TLI, AggTy,
2747                                             I.idx_begin(), I.idx_end());
2748
2749   SmallVector<MVT, 4> ValValueVTs;
2750   ComputeValueVTs(TLI, ValTy, ValValueVTs);
2751
2752   unsigned NumValValues = ValValueVTs.size();
2753   SmallVector<SDValue, 4> Values(NumValValues);
2754
2755   SDValue Agg = getValue(Op0);
2756   // Copy out the selected value(s).
2757   for (unsigned i = LinearIndex; i != LinearIndex + NumValValues; ++i)
2758     Values[i - LinearIndex] =
2759       OutOfUndef ? DAG.getNode(ISD::UNDEF, Agg.Val->getValueType(Agg.ResNo + i)) :
2760                    SDValue(Agg.Val, Agg.ResNo + i);
2761
2762   setValue(&I, DAG.getMergeValues(DAG.getVTList(&ValValueVTs[0], NumValValues),
2763                                   &Values[0], NumValValues));
2764 }
2765
2766
2767 void SelectionDAGLowering::visitGetElementPtr(User &I) {
2768   SDValue N = getValue(I.getOperand(0));
2769   const Type *Ty = I.getOperand(0)->getType();
2770
2771   for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
2772        OI != E; ++OI) {
2773     Value *Idx = *OI;
2774     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
2775       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
2776       if (Field) {
2777         // N = N + Offset
2778         uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field);
2779         N = DAG.getNode(ISD::ADD, N.getValueType(), N,
2780                         DAG.getIntPtrConstant(Offset));
2781       }
2782       Ty = StTy->getElementType(Field);
2783     } else {
2784       Ty = cast<SequentialType>(Ty)->getElementType();
2785
2786       // If this is a constant subscript, handle it quickly.
2787       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
2788         if (CI->getZExtValue() == 0) continue;
2789         uint64_t Offs =
2790             TD->getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
2791         N = DAG.getNode(ISD::ADD, N.getValueType(), N,
2792                         DAG.getIntPtrConstant(Offs));
2793         continue;
2794       }
2795
2796       // N = N + Idx * ElementSize;
2797       uint64_t ElementSize = TD->getABITypeSize(Ty);
2798       SDValue IdxN = getValue(Idx);
2799
2800       // If the index is smaller or larger than intptr_t, truncate or extend
2801       // it.
2802       if (IdxN.getValueType().bitsLT(N.getValueType())) {
2803         IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
2804       } else if (IdxN.getValueType().bitsGT(N.getValueType()))
2805         IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
2806
2807       // If this is a multiply by a power of two, turn it into a shl
2808       // immediately.  This is a very common case.
2809       if (isPowerOf2_64(ElementSize)) {
2810         unsigned Amt = Log2_64(ElementSize);
2811         IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
2812                            DAG.getConstant(Amt, TLI.getShiftAmountTy()));
2813         N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
2814         continue;
2815       }
2816
2817       SDValue Scale = DAG.getIntPtrConstant(ElementSize);
2818       IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
2819       N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
2820     }
2821   }
2822   setValue(&I, N);
2823 }
2824
2825 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
2826   // If this is a fixed sized alloca in the entry block of the function,
2827   // allocate it statically on the stack.
2828   if (FuncInfo.StaticAllocaMap.count(&I))
2829     return;   // getValue will auto-populate this.
2830
2831   const Type *Ty = I.getAllocatedType();
2832   uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
2833   unsigned Align =
2834     std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
2835              I.getAlignment());
2836
2837   SDValue AllocSize = getValue(I.getArraySize());
2838   MVT IntPtr = TLI.getPointerTy();
2839   if (IntPtr.bitsLT(AllocSize.getValueType()))
2840     AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
2841   else if (IntPtr.bitsGT(AllocSize.getValueType()))
2842     AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
2843
2844   AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
2845                           DAG.getIntPtrConstant(TySize));
2846
2847   // Handle alignment.  If the requested alignment is less than or equal to
2848   // the stack alignment, ignore it.  If the size is greater than or equal to
2849   // the stack alignment, we note this in the DYNAMIC_STACKALLOC node.
2850   unsigned StackAlign =
2851     TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
2852   if (Align <= StackAlign)
2853     Align = 0;
2854
2855   // Round the size of the allocation up to the stack alignment size
2856   // by add SA-1 to the size.
2857   AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
2858                           DAG.getIntPtrConstant(StackAlign-1));
2859   // Mask out the low bits for alignment purposes.
2860   AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
2861                           DAG.getIntPtrConstant(~(uint64_t)(StackAlign-1)));
2862
2863   SDValue Ops[] = { getRoot(), AllocSize, DAG.getIntPtrConstant(Align) };
2864   const MVT *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
2865                                                     MVT::Other);
2866   SDValue DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3);
2867   setValue(&I, DSA);
2868   DAG.setRoot(DSA.getValue(1));
2869
2870   // Inform the Frame Information that we have just allocated a variable-sized
2871   // object.
2872   CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
2873 }
2874
2875 void SelectionDAGLowering::visitLoad(LoadInst &I) {
2876   const Value *SV = I.getOperand(0);
2877   SDValue Ptr = getValue(SV);
2878
2879   const Type *Ty = I.getType();
2880   bool isVolatile = I.isVolatile();
2881   unsigned Alignment = I.getAlignment();
2882
2883   SmallVector<MVT, 4> ValueVTs;
2884   SmallVector<uint64_t, 4> Offsets;
2885   ComputeValueVTs(TLI, Ty, ValueVTs, &Offsets);
2886   unsigned NumValues = ValueVTs.size();
2887   if (NumValues == 0)
2888     return;
2889
2890   SDValue Root;
2891   bool ConstantMemory = false;
2892   if (I.isVolatile())
2893     // Serialize volatile loads with other side effects.
2894     Root = getRoot();
2895   else if (AA.pointsToConstantMemory(SV)) {
2896     // Do not serialize (non-volatile) loads of constant memory with anything.
2897     Root = DAG.getEntryNode();
2898     ConstantMemory = true;
2899   } else {
2900     // Do not serialize non-volatile loads against each other.
2901     Root = DAG.getRoot();
2902   }
2903
2904   SmallVector<SDValue, 4> Values(NumValues);
2905   SmallVector<SDValue, 4> Chains(NumValues);
2906   MVT PtrVT = Ptr.getValueType();
2907   for (unsigned i = 0; i != NumValues; ++i) {
2908     SDValue L = DAG.getLoad(ValueVTs[i], Root,
2909                               DAG.getNode(ISD::ADD, PtrVT, Ptr,
2910                                           DAG.getConstant(Offsets[i], PtrVT)),
2911                               SV, Offsets[i],
2912                               isVolatile, Alignment);
2913     Values[i] = L;
2914     Chains[i] = L.getValue(1);
2915   }
2916
2917   if (!ConstantMemory) {
2918     SDValue Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
2919                                   &Chains[0], NumValues);
2920     if (isVolatile)
2921       DAG.setRoot(Chain);
2922     else
2923       PendingLoads.push_back(Chain);
2924   }
2925
2926   setValue(&I, DAG.getMergeValues(DAG.getVTList(&ValueVTs[0], NumValues),
2927                                   &Values[0], NumValues));
2928 }
2929
2930
2931 void SelectionDAGLowering::visitStore(StoreInst &I) {
2932   Value *SrcV = I.getOperand(0);
2933   Value *PtrV = I.getOperand(1);
2934
2935   SmallVector<MVT, 4> ValueVTs;
2936   SmallVector<uint64_t, 4> Offsets;
2937   ComputeValueVTs(TLI, SrcV->getType(), ValueVTs, &Offsets);
2938   unsigned NumValues = ValueVTs.size();
2939   if (NumValues == 0)
2940     return;
2941
2942   // Get the lowered operands. Note that we do this after
2943   // checking if NumResults is zero, because with zero results
2944   // the operands won't have values in the map.
2945   SDValue Src = getValue(SrcV);
2946   SDValue Ptr = getValue(PtrV);
2947
2948   SDValue Root = getRoot();
2949   SmallVector<SDValue, 4> Chains(NumValues);
2950   MVT PtrVT = Ptr.getValueType();
2951   bool isVolatile = I.isVolatile();
2952   unsigned Alignment = I.getAlignment();
2953   for (unsigned i = 0; i != NumValues; ++i)
2954     Chains[i] = DAG.getStore(Root, SDValue(Src.Val, Src.ResNo + i),
2955                              DAG.getNode(ISD::ADD, PtrVT, Ptr,
2956                                          DAG.getConstant(Offsets[i], PtrVT)),
2957                              PtrV, Offsets[i],
2958                              isVolatile, Alignment);
2959
2960   DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumValues));
2961 }
2962
2963 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
2964 /// node.
2965 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
2966                                                 unsigned Intrinsic) {
2967   bool HasChain = !I.doesNotAccessMemory();
2968   bool OnlyLoad = HasChain && I.onlyReadsMemory();
2969
2970   // Build the operand list.
2971   SmallVector<SDValue, 8> Ops;
2972   if (HasChain) {  // If this intrinsic has side-effects, chainify it.
2973     if (OnlyLoad) {
2974       // We don't need to serialize loads against other loads.
2975       Ops.push_back(DAG.getRoot());
2976     } else {
2977       Ops.push_back(getRoot());
2978     }
2979   }
2980
2981   // Add the intrinsic ID as an integer operand.
2982   Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy()));
2983
2984   // Add all operands of the call to the operand list.
2985   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
2986     SDValue Op = getValue(I.getOperand(i));
2987     assert(TLI.isTypeLegal(Op.getValueType()) &&
2988            "Intrinsic uses a non-legal type?");
2989     Ops.push_back(Op);
2990   }
2991
2992   std::vector<MVT> VTs;
2993   if (I.getType() != Type::VoidTy) {
2994     MVT VT = TLI.getValueType(I.getType());
2995     if (VT.isVector()) {
2996       const VectorType *DestTy = cast<VectorType>(I.getType());
2997       MVT EltVT = TLI.getValueType(DestTy->getElementType());
2998
2999       VT = MVT::getVectorVT(EltVT, DestTy->getNumElements());
3000       assert(VT != MVT::Other && "Intrinsic uses a non-legal type?");
3001     }
3002
3003     assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?");
3004     VTs.push_back(VT);
3005   }
3006   if (HasChain)
3007     VTs.push_back(MVT::Other);
3008
3009   const MVT *VTList = DAG.getNodeValueTypes(VTs);
3010
3011   // Create the node.
3012   SDValue Result;
3013   if (!HasChain)
3014     Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(),
3015                          &Ops[0], Ops.size());
3016   else if (I.getType() != Type::VoidTy)
3017     Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(),
3018                          &Ops[0], Ops.size());
3019   else
3020     Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(),
3021                          &Ops[0], Ops.size());
3022
3023   if (HasChain) {
3024     SDValue Chain = Result.getValue(Result.Val->getNumValues()-1);
3025     if (OnlyLoad)
3026       PendingLoads.push_back(Chain);
3027     else
3028       DAG.setRoot(Chain);
3029   }
3030   if (I.getType() != Type::VoidTy) {
3031     if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
3032       MVT VT = TLI.getValueType(PTy);
3033       Result = DAG.getNode(ISD::BIT_CONVERT, VT, Result);
3034     }
3035     setValue(&I, Result);
3036   }
3037 }
3038
3039 /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
3040 static GlobalVariable *ExtractTypeInfo (Value *V) {
3041   V = V->stripPointerCasts();
3042   GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
3043   assert ((GV || isa<ConstantPointerNull>(V)) &&
3044           "TypeInfo must be a global variable or NULL");
3045   return GV;
3046 }
3047
3048 /// addCatchInfo - Extract the personality and type infos from an eh.selector
3049 /// call, and add them to the specified machine basic block.
3050 static void addCatchInfo(CallInst &I, MachineModuleInfo *MMI,
3051                          MachineBasicBlock *MBB) {
3052   // Inform the MachineModuleInfo of the personality for this landing pad.
3053   ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2));
3054   assert(CE->getOpcode() == Instruction::BitCast &&
3055          isa<Function>(CE->getOperand(0)) &&
3056          "Personality should be a function");
3057   MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
3058
3059   // Gather all the type infos for this landing pad and pass them along to
3060   // MachineModuleInfo.
3061   std::vector<GlobalVariable *> TyInfo;
3062   unsigned N = I.getNumOperands();
3063
3064   for (unsigned i = N - 1; i > 2; --i) {
3065     if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) {
3066       unsigned FilterLength = CI->getZExtValue();
3067       unsigned FirstCatch = i + FilterLength + !FilterLength;
3068       assert (FirstCatch <= N && "Invalid filter length");
3069
3070       if (FirstCatch < N) {
3071         TyInfo.reserve(N - FirstCatch);
3072         for (unsigned j = FirstCatch; j < N; ++j)
3073           TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
3074         MMI->addCatchTypeInfo(MBB, TyInfo);
3075         TyInfo.clear();
3076       }
3077
3078       if (!FilterLength) {
3079         // Cleanup.
3080         MMI->addCleanup(MBB);
3081       } else {
3082         // Filter.
3083         TyInfo.reserve(FilterLength - 1);
3084         for (unsigned j = i + 1; j < FirstCatch; ++j)
3085           TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
3086         MMI->addFilterTypeInfo(MBB, TyInfo);
3087         TyInfo.clear();
3088       }
3089
3090       N = i;
3091     }
3092   }
3093
3094   if (N > 3) {
3095     TyInfo.reserve(N - 3);
3096     for (unsigned j = 3; j < N; ++j)
3097       TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
3098     MMI->addCatchTypeInfo(MBB, TyInfo);
3099   }
3100 }
3101
3102
3103 /// Inlined utility function to implement binary input atomic intrinsics for
3104 // visitIntrinsicCall: I is a call instruction
3105 //                     Op is the associated NodeType for I
3106 const char *
3107 SelectionDAGLowering::implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op) {
3108   SDValue Root = getRoot();
3109   SDValue L = DAG.getAtomic(Op, Root,
3110                               getValue(I.getOperand(1)),
3111                               getValue(I.getOperand(2)),
3112                               I.getOperand(1));
3113   setValue(&I, L);
3114   DAG.setRoot(L.getValue(1));
3115   return 0;
3116 }
3117
3118 /// visitIntrinsicCall - Lower the call to the specified intrinsic function.  If
3119 /// we want to emit this as a call to a named external function, return the name
3120 /// otherwise lower it and return null.
3121 const char *
3122 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
3123   switch (Intrinsic) {
3124   default:
3125     // By default, turn this into a target intrinsic node.
3126     visitTargetIntrinsic(I, Intrinsic);
3127     return 0;
3128   case Intrinsic::vastart:  visitVAStart(I); return 0;
3129   case Intrinsic::vaend:    visitVAEnd(I); return 0;
3130   case Intrinsic::vacopy:   visitVACopy(I); return 0;
3131   case Intrinsic::returnaddress:
3132     setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(),
3133                              getValue(I.getOperand(1))));
3134     return 0;
3135   case Intrinsic::frameaddress:
3136     setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(),
3137                              getValue(I.getOperand(1))));
3138     return 0;
3139   case Intrinsic::setjmp:
3140     return "_setjmp"+!TLI.usesUnderscoreSetJmp();
3141     break;
3142   case Intrinsic::longjmp:
3143     return "_longjmp"+!TLI.usesUnderscoreLongJmp();
3144     break;
3145   case Intrinsic::memcpy_i32:
3146   case Intrinsic::memcpy_i64: {
3147     SDValue Op1 = getValue(I.getOperand(1));
3148     SDValue Op2 = getValue(I.getOperand(2));
3149     SDValue Op3 = getValue(I.getOperand(3));
3150     unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue();
3151     DAG.setRoot(DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Align, false,
3152                               I.getOperand(1), 0, I.getOperand(2), 0));
3153     return 0;
3154   }
3155   case Intrinsic::memset_i32:
3156   case Intrinsic::memset_i64: {
3157     SDValue Op1 = getValue(I.getOperand(1));
3158     SDValue Op2 = getValue(I.getOperand(2));
3159     SDValue Op3 = getValue(I.getOperand(3));
3160     unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue();
3161     DAG.setRoot(DAG.getMemset(getRoot(), Op1, Op2, Op3, Align,
3162                               I.getOperand(1), 0));
3163     return 0;
3164   }
3165   case Intrinsic::memmove_i32:
3166   case Intrinsic::memmove_i64: {
3167     SDValue Op1 = getValue(I.getOperand(1));
3168     SDValue Op2 = getValue(I.getOperand(2));
3169     SDValue Op3 = getValue(I.getOperand(3));
3170     unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue();
3171
3172     // If the source and destination are known to not be aliases, we can
3173     // lower memmove as memcpy.
3174     uint64_t Size = -1ULL;
3175     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op3))
3176       Size = C->getValue();
3177     if (AA.alias(I.getOperand(1), Size, I.getOperand(2), Size) ==
3178         AliasAnalysis::NoAlias) {
3179       DAG.setRoot(DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Align, false,
3180                                 I.getOperand(1), 0, I.getOperand(2), 0));
3181       return 0;
3182     }
3183
3184     DAG.setRoot(DAG.getMemmove(getRoot(), Op1, Op2, Op3, Align,
3185                                I.getOperand(1), 0, I.getOperand(2), 0));
3186     return 0;
3187   }
3188   case Intrinsic::dbg_stoppoint: {
3189     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3190     DbgStopPointInst &SPI = cast<DbgStopPointInst>(I);
3191     if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) {
3192       DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext());
3193       assert(DD && "Not a debug information descriptor");
3194       DAG.setRoot(DAG.getDbgStopPoint(getRoot(),
3195                                       SPI.getLine(),
3196                                       SPI.getColumn(),
3197                                       cast<CompileUnitDesc>(DD)));
3198     }
3199
3200     return 0;
3201   }
3202   case Intrinsic::dbg_region_start: {
3203     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3204     DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I);
3205     if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) {
3206       unsigned LabelID = MMI->RecordRegionStart(RSI.getContext());
3207       DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getRoot(), LabelID));
3208     }
3209
3210     return 0;
3211   }
3212   case Intrinsic::dbg_region_end: {
3213     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3214     DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I);
3215     if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) {
3216       unsigned LabelID = MMI->RecordRegionEnd(REI.getContext());
3217       DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getRoot(), LabelID));
3218     }
3219
3220     return 0;
3221   }
3222   case Intrinsic::dbg_func_start: {
3223     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3224     if (!MMI) return 0;
3225     DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I);
3226     Value *SP = FSI.getSubprogram();
3227     if (SP && MMI->Verify(SP)) {
3228       // llvm.dbg.func.start implicitly defines a dbg_stoppoint which is
3229       // what (most?) gdb expects.
3230       DebugInfoDesc *DD = MMI->getDescFor(SP);
3231       assert(DD && "Not a debug information descriptor");
3232       SubprogramDesc *Subprogram = cast<SubprogramDesc>(DD);
3233       const CompileUnitDesc *CompileUnit = Subprogram->getFile();
3234       unsigned SrcFile = MMI->RecordSource(CompileUnit);
3235       // Record the source line but does create a label. It will be emitted
3236       // at asm emission time.
3237       MMI->RecordSourceLine(Subprogram->getLine(), 0, SrcFile);
3238     }
3239
3240     return 0;
3241   }
3242   case Intrinsic::dbg_declare: {
3243     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3244     DbgDeclareInst &DI = cast<DbgDeclareInst>(I);
3245     Value *Variable = DI.getVariable();
3246     if (MMI && Variable && MMI->Verify(Variable))
3247       DAG.setRoot(DAG.getNode(ISD::DECLARE, MVT::Other, getRoot(),
3248                               getValue(DI.getAddress()), getValue(Variable)));
3249     return 0;
3250   }
3251
3252   case Intrinsic::eh_exception: {
3253     if (!CurMBB->isLandingPad()) {
3254       // FIXME: Mark exception register as live in.  Hack for PR1508.
3255       unsigned Reg = TLI.getExceptionAddressRegister();
3256       if (Reg) CurMBB->addLiveIn(Reg);
3257     }
3258     // Insert the EXCEPTIONADDR instruction.
3259     SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
3260     SDValue Ops[1];
3261     Ops[0] = DAG.getRoot();
3262     SDValue Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
3263     setValue(&I, Op);
3264     DAG.setRoot(Op.getValue(1));
3265     return 0;
3266   }
3267
3268   case Intrinsic::eh_selector_i32:
3269   case Intrinsic::eh_selector_i64: {
3270     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3271     MVT VT = (Intrinsic == Intrinsic::eh_selector_i32 ?
3272                          MVT::i32 : MVT::i64);
3273
3274     if (MMI) {
3275       if (CurMBB->isLandingPad())
3276         addCatchInfo(I, MMI, CurMBB);
3277       else {
3278 #ifndef NDEBUG
3279         FuncInfo.CatchInfoLost.insert(&I);
3280 #endif
3281         // FIXME: Mark exception selector register as live in.  Hack for PR1508.
3282         unsigned Reg = TLI.getExceptionSelectorRegister();
3283         if (Reg) CurMBB->addLiveIn(Reg);
3284       }
3285
3286       // Insert the EHSELECTION instruction.
3287       SDVTList VTs = DAG.getVTList(VT, MVT::Other);
3288       SDValue Ops[2];
3289       Ops[0] = getValue(I.getOperand(1));
3290       Ops[1] = getRoot();
3291       SDValue Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
3292       setValue(&I, Op);
3293       DAG.setRoot(Op.getValue(1));
3294     } else {
3295       setValue(&I, DAG.getConstant(0, VT));
3296     }
3297
3298     return 0;
3299   }
3300
3301   case Intrinsic::eh_typeid_for_i32:
3302   case Intrinsic::eh_typeid_for_i64: {
3303     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3304     MVT VT = (Intrinsic == Intrinsic::eh_typeid_for_i32 ?
3305                          MVT::i32 : MVT::i64);
3306
3307     if (MMI) {
3308       // Find the type id for the given typeinfo.
3309       GlobalVariable *GV = ExtractTypeInfo(I.getOperand(1));
3310
3311       unsigned TypeID = MMI->getTypeIDFor(GV);
3312       setValue(&I, DAG.getConstant(TypeID, VT));
3313     } else {
3314       // Return something different to eh_selector.
3315       setValue(&I, DAG.getConstant(1, VT));
3316     }
3317
3318     return 0;
3319   }
3320
3321   case Intrinsic::eh_return: {
3322     MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3323
3324     if (MMI) {
3325       MMI->setCallsEHReturn(true);
3326       DAG.setRoot(DAG.getNode(ISD::EH_RETURN,
3327                               MVT::Other,
3328                               getControlRoot(),
3329                               getValue(I.getOperand(1)),
3330                               getValue(I.getOperand(2))));
3331     } else {
3332       setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
3333     }
3334
3335     return 0;
3336   }
3337
3338    case Intrinsic::eh_unwind_init: {
3339      if (MachineModuleInfo *MMI = DAG.getMachineModuleInfo()) {
3340        MMI->setCallsUnwindInit(true);
3341      }
3342
3343      return 0;
3344    }
3345
3346    case Intrinsic::eh_dwarf_cfa: {
3347      MVT VT = getValue(I.getOperand(1)).getValueType();
3348      SDValue CfaArg;
3349      if (VT.bitsGT(TLI.getPointerTy()))
3350        CfaArg = DAG.getNode(ISD::TRUNCATE,
3351                             TLI.getPointerTy(), getValue(I.getOperand(1)));
3352      else
3353        CfaArg = DAG.getNode(ISD::SIGN_EXTEND,
3354                             TLI.getPointerTy(), getValue(I.getOperand(1)));
3355
3356      SDValue Offset = DAG.getNode(ISD::ADD,
3357                                     TLI.getPointerTy(),
3358                                     DAG.getNode(ISD::FRAME_TO_ARGS_OFFSET,
3359                                                 TLI.getPointerTy()),
3360                                     CfaArg);
3361      setValue(&I, DAG.getNode(ISD::ADD,
3362                               TLI.getPointerTy(),
3363                               DAG.getNode(ISD::FRAMEADDR,
3364                                           TLI.getPointerTy(),
3365                                           DAG.getConstant(0,
3366                                                           TLI.getPointerTy())),
3367                               Offset));
3368      return 0;
3369   }
3370
3371   case Intrinsic::sqrt:
3372     setValue(&I, DAG.getNode(ISD::FSQRT,
3373                              getValue(I.getOperand(1)).getValueType(),
3374                              getValue(I.getOperand(1))));
3375     return 0;
3376   case Intrinsic::powi:
3377     setValue(&I, DAG.getNode(ISD::FPOWI,
3378                              getValue(I.getOperand(1)).getValueType(),
3379                              getValue(I.getOperand(1)),
3380                              getValue(I.getOperand(2))));
3381     return 0;
3382   case Intrinsic::sin:
3383     setValue(&I, DAG.getNode(ISD::FSIN,
3384                              getValue(I.getOperand(1)).getValueType(),
3385                              getValue(I.getOperand(1))));
3386     return 0;
3387   case Intrinsic::cos:
3388     setValue(&I, DAG.getNode(ISD::FCOS,
3389                              getValue(I.getOperand(1)).getValueType(),
3390                              getValue(I.getOperand(1))));
3391     return 0;
3392   case Intrinsic::pow:
3393     setValue(&I, DAG.getNode(ISD::FPOW,
3394                              getValue(I.getOperand(1)).getValueType(),
3395                              getValue(I.getOperand(1)),
3396                              getValue(I.getOperand(2))));
3397     return 0;
3398   case Intrinsic::pcmarker: {
3399     SDValue Tmp = getValue(I.getOperand(1));
3400     DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
3401     return 0;
3402   }
3403   case Intrinsic::readcyclecounter: {
3404     SDValue Op = getRoot();
3405     SDValue Tmp = DAG.getNode(ISD::READCYCLECOUNTER,
3406                                 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2,
3407                                 &Op, 1);
3408     setValue(&I, Tmp);
3409     DAG.setRoot(Tmp.getValue(1));
3410     return 0;
3411   }
3412   case Intrinsic::part_select: {
3413     // Currently not implemented: just abort
3414     assert(0 && "part_select intrinsic not implemented");
3415     abort();
3416   }
3417   case Intrinsic::part_set: {
3418     // Currently not implemented: just abort
3419     assert(0 && "part_set intrinsic not implemented");
3420     abort();
3421   }
3422   case Intrinsic::bswap:
3423     setValue(&I, DAG.getNode(ISD::BSWAP,
3424                              getValue(I.getOperand(1)).getValueType(),
3425                              getValue(I.getOperand(1))));
3426     return 0;
3427   case Intrinsic::cttz: {
3428     SDValue Arg = getValue(I.getOperand(1));
3429     MVT Ty = Arg.getValueType();
3430     SDValue result = DAG.getNode(ISD::CTTZ, Ty, Arg);
3431     setValue(&I, result);
3432     return 0;
3433   }
3434   case Intrinsic::ctlz: {
3435     SDValue Arg = getValue(I.getOperand(1));
3436     MVT Ty = Arg.getValueType();
3437     SDValue result = DAG.getNode(ISD::CTLZ, Ty, Arg);
3438     setValue(&I, result);
3439     return 0;
3440   }
3441   case Intrinsic::ctpop: {
3442     SDValue Arg = getValue(I.getOperand(1));
3443     MVT Ty = Arg.getValueType();
3444     SDValue result = DAG.getNode(ISD::CTPOP, Ty, Arg);
3445     setValue(&I, result);
3446     return 0;
3447   }
3448   case Intrinsic::stacksave: {
3449     SDValue Op = getRoot();
3450     SDValue Tmp = DAG.getNode(ISD::STACKSAVE,
3451               DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1);
3452     setValue(&I, Tmp);
3453     DAG.setRoot(Tmp.getValue(1));
3454     return 0;
3455   }
3456   case Intrinsic::stackrestore: {
3457     SDValue Tmp = getValue(I.getOperand(1));
3458     DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
3459     return 0;
3460   }
3461   case Intrinsic::var_annotation:
3462     // Discard annotate attributes
3463     return 0;
3464
3465   case Intrinsic::init_trampoline: {
3466     const Function *F = cast<Function>(I.getOperand(2)->stripPointerCasts());
3467
3468     SDValue Ops[6];
3469     Ops[0] = getRoot();
3470     Ops[1] = getValue(I.getOperand(1));
3471     Ops[2] = getValue(I.getOperand(2));
3472     Ops[3] = getValue(I.getOperand(3));
3473     Ops[4] = DAG.getSrcValue(I.getOperand(1));
3474     Ops[5] = DAG.getSrcValue(F);
3475
3476     SDValue Tmp = DAG.getNode(ISD::TRAMPOLINE,
3477                                 DAG.getNodeValueTypes(TLI.getPointerTy(),
3478                                                       MVT::Other), 2,
3479                                 Ops, 6);
3480
3481     setValue(&I, Tmp);
3482     DAG.setRoot(Tmp.getValue(1));
3483     return 0;
3484   }
3485
3486   case Intrinsic::gcroot:
3487     if (GCI) {
3488       Value *Alloca = I.getOperand(1);
3489       Constant *TypeMap = cast<Constant>(I.getOperand(2));
3490
3491       FrameIndexSDNode *FI = cast<FrameIndexSDNode>(getValue(Alloca).Val);
3492       GCI->addStackRoot(FI->getIndex(), TypeMap);
3493     }
3494     return 0;
3495
3496   case Intrinsic::gcread:
3497   case Intrinsic::gcwrite:
3498     assert(0 && "Collector failed to lower gcread/gcwrite intrinsics!");
3499     return 0;
3500
3501   case Intrinsic::flt_rounds: {
3502     setValue(&I, DAG.getNode(ISD::FLT_ROUNDS_, MVT::i32));
3503     return 0;
3504   }
3505
3506   case Intrinsic::trap: {
3507     DAG.setRoot(DAG.getNode(ISD::TRAP, MVT::Other, getRoot()));
3508     return 0;
3509   }
3510   case Intrinsic::prefetch: {
3511     SDValue Ops[4];
3512     Ops[0] = getRoot();
3513     Ops[1] = getValue(I.getOperand(1));
3514     Ops[2] = getValue(I.getOperand(2));
3515     Ops[3] = getValue(I.getOperand(3));
3516     DAG.setRoot(DAG.getNode(ISD::PREFETCH, MVT::Other, &Ops[0], 4));
3517     return 0;
3518   }
3519
3520   case Intrinsic::memory_barrier: {
3521     SDValue Ops[6];
3522     Ops[0] = getRoot();
3523     for (int x = 1; x < 6; ++x)
3524       Ops[x] = getValue(I.getOperand(x));
3525
3526     DAG.setRoot(DAG.getNode(ISD::MEMBARRIER, MVT::Other, &Ops[0], 6));
3527     return 0;
3528   }
3529   case Intrinsic::atomic_cmp_swap: {
3530     SDValue Root = getRoot();
3531     SDValue L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP, Root,
3532                                 getValue(I.getOperand(1)),
3533                                 getValue(I.getOperand(2)),
3534                                 getValue(I.getOperand(3)),
3535                                 I.getOperand(1));
3536     setValue(&I, L);
3537     DAG.setRoot(L.getValue(1));
3538     return 0;
3539   }
3540   case Intrinsic::atomic_load_add:
3541     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD);
3542   case Intrinsic::atomic_load_sub:
3543     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB);
3544   case Intrinsic::atomic_load_and:
3545     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND);
3546   case Intrinsic::atomic_load_or:
3547     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR);
3548   case Intrinsic::atomic_load_xor:
3549     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR);
3550   case Intrinsic::atomic_load_nand:
3551     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND);
3552   case Intrinsic::atomic_load_min:
3553     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN);
3554   case Intrinsic::atomic_load_max:
3555     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX);
3556   case Intrinsic::atomic_load_umin:
3557     return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN);
3558   case Intrinsic::atomic_load_umax:
3559       return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX);
3560   case Intrinsic::atomic_swap:
3561     return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP);
3562   }
3563 }
3564
3565
3566 void SelectionDAGLowering::LowerCallTo(CallSite CS, SDValue Callee,
3567                                        bool IsTailCall,
3568                                        MachineBasicBlock *LandingPad) {
3569   const PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
3570   const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
3571   MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
3572   unsigned BeginLabel = 0, EndLabel = 0;
3573
3574   TargetLowering::ArgListTy Args;
3575   TargetLowering::ArgListEntry Entry;
3576   Args.reserve(CS.arg_size());
3577   for (CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
3578        i != e; ++i) {
3579     SDValue ArgNode = getValue(*i);
3580     Entry.Node = ArgNode; Entry.Ty = (*i)->getType();
3581
3582     unsigned attrInd = i - CS.arg_begin() + 1;
3583     Entry.isSExt  = CS.paramHasAttr(attrInd, ParamAttr::SExt);
3584     Entry.isZExt  = CS.paramHasAttr(attrInd, ParamAttr::ZExt);
3585     Entry.isInReg = CS.paramHasAttr(attrInd, ParamAttr::InReg);
3586     Entry.isSRet  = CS.paramHasAttr(attrInd, ParamAttr::StructRet);
3587     Entry.isNest  = CS.paramHasAttr(attrInd, ParamAttr::Nest);
3588     Entry.isByVal = CS.paramHasAttr(attrInd, ParamAttr::ByVal);
3589     Entry.Alignment = CS.getParamAlignment(attrInd);
3590     Args.push_back(Entry);
3591   }
3592
3593   if (LandingPad && MMI) {
3594     // Insert a label before the invoke call to mark the try range.  This can be
3595     // used to detect deletion of the invoke via the MachineModuleInfo.
3596     BeginLabel = MMI->NextLabelID();
3597     // Both PendingLoads and PendingExports must be flushed here;
3598     // this call might not return.
3599     (void)getRoot();
3600     DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getControlRoot(), BeginLabel));
3601   }
3602
3603   std::pair<SDValue,SDValue> Result =
3604     TLI.LowerCallTo(getRoot(), CS.getType(),
3605                     CS.paramHasAttr(0, ParamAttr::SExt),
3606                     CS.paramHasAttr(0, ParamAttr::ZExt),
3607                     FTy->isVarArg(), CS.getCallingConv(), IsTailCall,
3608                     Callee, Args, DAG);
3609   if (CS.getType() != Type::VoidTy)
3610     setValue(CS.getInstruction(), Result.first);
3611   DAG.setRoot(Result.second);
3612
3613   if (LandingPad && MMI) {
3614     // Insert a label at the end of the invoke call to mark the try range.  This
3615     // can be used to detect deletion of the invoke via the MachineModuleInfo.
3616     EndLabel = MMI->NextLabelID();
3617     DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getRoot(), EndLabel));
3618
3619     // Inform MachineModuleInfo of range.
3620     MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
3621   }
3622 }
3623
3624
3625 void SelectionDAGLowering::visitCall(CallInst &I) {
3626   const char *RenameFn = 0;
3627   if (Function *F = I.getCalledFunction()) {
3628     if (F->isDeclaration()) {
3629       if (unsigned IID = F->getIntrinsicID()) {
3630         RenameFn = visitIntrinsicCall(I, IID);
3631         if (!RenameFn)
3632           return;
3633       }
3634     }
3635
3636     // Check for well-known libc/libm calls.  If the function is internal, it
3637     // can't be a library call.
3638     unsigned NameLen = F->getNameLen();
3639     if (!F->hasInternalLinkage() && NameLen) {
3640       const char *NameStr = F->getNameStart();
3641       if (NameStr[0] == 'c' &&
3642           ((NameLen == 8 && !strcmp(NameStr, "copysign")) ||
3643            (NameLen == 9 && !strcmp(NameStr, "copysignf")))) {
3644         if (I.getNumOperands() == 3 &&   // Basic sanity checks.
3645             I.getOperand(1)->getType()->isFloatingPoint() &&
3646             I.getType() == I.getOperand(1)->getType() &&
3647             I.getType() == I.getOperand(2)->getType()) {
3648           SDValue LHS = getValue(I.getOperand(1));
3649           SDValue RHS = getValue(I.getOperand(2));
3650           setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
3651                                    LHS, RHS));
3652           return;
3653         }
3654       } else if (NameStr[0] == 'f' &&
3655                  ((NameLen == 4 && !strcmp(NameStr, "fabs")) ||
3656                   (NameLen == 5 && !strcmp(NameStr, "fabsf")) ||
3657                   (NameLen == 5 && !strcmp(NameStr, "fabsl")))) {
3658         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3659             I.getOperand(1)->getType()->isFloatingPoint() &&
3660             I.getType() == I.getOperand(1)->getType()) {
3661           SDValue Tmp = getValue(I.getOperand(1));
3662           setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
3663           return;
3664         }
3665       } else if (NameStr[0] == 's' &&
3666                  ((NameLen == 3 && !strcmp(NameStr, "sin")) ||
3667                   (NameLen == 4 && !strcmp(NameStr, "sinf")) ||
3668                   (NameLen == 4 && !strcmp(NameStr, "sinl")))) {
3669         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3670             I.getOperand(1)->getType()->isFloatingPoint() &&
3671             I.getType() == I.getOperand(1)->getType()) {
3672           SDValue Tmp = getValue(I.getOperand(1));
3673           setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
3674           return;
3675         }
3676       } else if (NameStr[0] == 'c' &&
3677                  ((NameLen == 3 && !strcmp(NameStr, "cos")) ||
3678                   (NameLen == 4 && !strcmp(NameStr, "cosf")) ||
3679                   (NameLen == 4 && !strcmp(NameStr, "cosl")))) {
3680         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3681             I.getOperand(1)->getType()->isFloatingPoint() &&
3682             I.getType() == I.getOperand(1)->getType()) {
3683           SDValue Tmp = getValue(I.getOperand(1));
3684           setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
3685           return;
3686         }
3687       }
3688     }
3689   } else if (isa<InlineAsm>(I.getOperand(0))) {
3690     visitInlineAsm(&I);
3691     return;
3692   }
3693
3694   SDValue Callee;
3695   if (!RenameFn)
3696     Callee = getValue(I.getOperand(0));
3697   else
3698     Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
3699
3700   LowerCallTo(&I, Callee, I.isTailCall());
3701 }
3702
3703
3704 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
3705 /// this value and returns the result as a ValueVT value.  This uses
3706 /// Chain/Flag as the input and updates them for the output Chain/Flag.
3707 /// If the Flag pointer is NULL, no flag is used.
3708 SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
3709                                       SDValue &Chain,
3710                                       SDValue *Flag) const {
3711   // Assemble the legal parts into the final values.
3712   SmallVector<SDValue, 4> Values(ValueVTs.size());
3713   SmallVector<SDValue, 8> Parts;
3714   for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
3715     // Copy the legal parts from the registers.
3716     MVT ValueVT = ValueVTs[Value];
3717     unsigned NumRegs = TLI->getNumRegisters(ValueVT);
3718     MVT RegisterVT = RegVTs[Value];
3719
3720     Parts.resize(NumRegs);
3721     for (unsigned i = 0; i != NumRegs; ++i) {
3722       SDValue P;
3723       if (Flag == 0)
3724         P = DAG.getCopyFromReg(Chain, Regs[Part+i], RegisterVT);
3725       else {
3726         P = DAG.getCopyFromReg(Chain, Regs[Part+i], RegisterVT, *Flag);
3727         *Flag = P.getValue(2);
3728       }
3729       Chain = P.getValue(1);
3730
3731       // If the source register was virtual and if we know something about it,
3732       // add an assert node.
3733       if (TargetRegisterInfo::isVirtualRegister(Regs[Part+i]) &&
3734           RegisterVT.isInteger() && !RegisterVT.isVector()) {
3735         unsigned SlotNo = Regs[Part+i]-TargetRegisterInfo::FirstVirtualRegister;
3736         FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo();
3737         if (FLI.LiveOutRegInfo.size() > SlotNo) {
3738           FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[SlotNo];
3739
3740           unsigned RegSize = RegisterVT.getSizeInBits();
3741           unsigned NumSignBits = LOI.NumSignBits;
3742           unsigned NumZeroBits = LOI.KnownZero.countLeadingOnes();
3743
3744           // FIXME: We capture more information than the dag can represent.  For
3745           // now, just use the tightest assertzext/assertsext possible.
3746           bool isSExt = true;
3747           MVT FromVT(MVT::Other);
3748           if (NumSignBits == RegSize)
3749             isSExt = true, FromVT = MVT::i1;   // ASSERT SEXT 1
3750           else if (NumZeroBits >= RegSize-1)
3751             isSExt = false, FromVT = MVT::i1;  // ASSERT ZEXT 1
3752           else if (NumSignBits > RegSize-8)
3753             isSExt = true, FromVT = MVT::i8;   // ASSERT SEXT 8
3754           else if (NumZeroBits >= RegSize-9)
3755             isSExt = false, FromVT = MVT::i8;  // ASSERT ZEXT 8
3756           else if (NumSignBits > RegSize-16)
3757             isSExt = true, FromVT = MVT::i16;   // ASSERT SEXT 16
3758           else if (NumZeroBits >= RegSize-17)
3759             isSExt = false, FromVT = MVT::i16;  // ASSERT ZEXT 16
3760           else if (NumSignBits > RegSize-32)
3761             isSExt = true, FromVT = MVT::i32;   // ASSERT SEXT 32
3762           else if (NumZeroBits >= RegSize-33)
3763             isSExt = false, FromVT = MVT::i32;  // ASSERT ZEXT 32
3764
3765           if (FromVT != MVT::Other) {
3766             P = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext,
3767                             RegisterVT, P, DAG.getValueType(FromVT));
3768
3769           }
3770         }
3771       }
3772
3773       Parts[Part+i] = P;
3774     }
3775
3776     Values[Value] = getCopyFromParts(DAG, &Parts[Part], NumRegs, RegisterVT,
3777                                      ValueVT);
3778     Part += NumRegs;
3779   }
3780
3781   return DAG.getMergeValues(DAG.getVTList(&ValueVTs[0], ValueVTs.size()),
3782                             &Values[0], ValueVTs.size());
3783 }
3784
3785 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
3786 /// specified value into the registers specified by this object.  This uses
3787 /// Chain/Flag as the input and updates them for the output Chain/Flag.
3788 /// If the Flag pointer is NULL, no flag is used.
3789 void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG,
3790                                  SDValue &Chain, SDValue *Flag) const {
3791   // Get the list of the values's legal parts.
3792   unsigned NumRegs = Regs.size();
3793   SmallVector<SDValue, 8> Parts(NumRegs);
3794   for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) {
3795     MVT ValueVT = ValueVTs[Value];
3796     unsigned NumParts = TLI->getNumRegisters(ValueVT);
3797     MVT RegisterVT = RegVTs[Value];
3798
3799     getCopyToParts(DAG, Val.getValue(Val.ResNo + Value),
3800                    &Parts[Part], NumParts, RegisterVT);
3801     Part += NumParts;
3802   }
3803
3804   // Copy the parts into the registers.
3805   SmallVector<SDValue, 8> Chains(NumRegs);
3806   for (unsigned i = 0; i != NumRegs; ++i) {
3807     SDValue Part;
3808     if (Flag == 0)
3809       Part = DAG.getCopyToReg(Chain, Regs[i], Parts[i]);
3810     else {
3811       Part = DAG.getCopyToReg(Chain, Regs[i], Parts[i], *Flag);
3812       *Flag = Part.getValue(1);
3813     }
3814     Chains[i] = Part.getValue(0);
3815   }
3816
3817   if (NumRegs == 1 || Flag)
3818     // If NumRegs > 1 && Flag is used then the use of the last CopyToReg is
3819     // flagged to it. That is the CopyToReg nodes and the user are considered
3820     // a single scheduling unit. If we create a TokenFactor and return it as
3821     // chain, then the TokenFactor is both a predecessor (operand) of the
3822     // user as well as a successor (the TF operands are flagged to the user).
3823     // c1, f1 = CopyToReg
3824     // c2, f2 = CopyToReg
3825     // c3     = TokenFactor c1, c2
3826     // ...
3827     //        = op c3, ..., f2
3828     Chain = Chains[NumRegs-1];
3829   else
3830     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumRegs);
3831 }
3832
3833 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
3834 /// operand list.  This adds the code marker and includes the number of
3835 /// values added into it.
3836 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
3837                                         std::vector<SDValue> &Ops) const {
3838   MVT IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
3839   Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
3840   for (unsigned Value = 0, Reg = 0, e = ValueVTs.size(); Value != e; ++Value) {
3841     unsigned NumRegs = TLI->getNumRegisters(ValueVTs[Value]);
3842     MVT RegisterVT = RegVTs[Value];
3843     for (unsigned i = 0; i != NumRegs; ++i)
3844       Ops.push_back(DAG.getRegister(Regs[Reg++], RegisterVT));
3845   }
3846 }
3847
3848 /// isAllocatableRegister - If the specified register is safe to allocate,
3849 /// i.e. it isn't a stack pointer or some other special register, return the
3850 /// register class for the register.  Otherwise, return null.
3851 static const TargetRegisterClass *
3852 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
3853                       const TargetLowering &TLI,
3854                       const TargetRegisterInfo *TRI) {
3855   MVT FoundVT = MVT::Other;
3856   const TargetRegisterClass *FoundRC = 0;
3857   for (TargetRegisterInfo::regclass_iterator RCI = TRI->regclass_begin(),
3858        E = TRI->regclass_end(); RCI != E; ++RCI) {
3859     MVT ThisVT = MVT::Other;
3860
3861     const TargetRegisterClass *RC = *RCI;
3862     // If none of the the value types for this register class are valid, we
3863     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
3864     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
3865          I != E; ++I) {
3866       if (TLI.isTypeLegal(*I)) {
3867         // If we have already found this register in a different register class,
3868         // choose the one with the largest VT specified.  For example, on
3869         // PowerPC, we favor f64 register classes over f32.
3870         if (FoundVT == MVT::Other || FoundVT.bitsLT(*I)) {
3871           ThisVT = *I;
3872           break;
3873         }
3874       }
3875     }
3876
3877     if (ThisVT == MVT::Other) continue;
3878
3879     // NOTE: This isn't ideal.  In particular, this might allocate the
3880     // frame pointer in functions that need it (due to them not being taken
3881     // out of allocation, because a variable sized allocation hasn't been seen
3882     // yet).  This is a slight code pessimization, but should still work.
3883     for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
3884          E = RC->allocation_order_end(MF); I != E; ++I)
3885       if (*I == Reg) {
3886         // We found a matching register class.  Keep looking at others in case
3887         // we find one with larger registers that this physreg is also in.
3888         FoundRC = RC;
3889         FoundVT = ThisVT;
3890         break;
3891       }
3892   }
3893   return FoundRC;
3894 }
3895
3896
3897 namespace {
3898 /// AsmOperandInfo - This contains information for each constraint that we are
3899 /// lowering.
3900 struct SDISelAsmOperandInfo : public TargetLowering::AsmOperandInfo {
3901   /// CallOperand - If this is the result output operand or a clobber
3902   /// this is null, otherwise it is the incoming operand to the CallInst.
3903   /// This gets modified as the asm is processed.
3904   SDValue CallOperand;
3905
3906   /// AssignedRegs - If this is a register or register class operand, this
3907   /// contains the set of register corresponding to the operand.
3908   RegsForValue AssignedRegs;
3909
3910   explicit SDISelAsmOperandInfo(const InlineAsm::ConstraintInfo &info)
3911     : TargetLowering::AsmOperandInfo(info), CallOperand(0,0) {
3912   }
3913
3914   /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers
3915   /// busy in OutputRegs/InputRegs.
3916   void MarkAllocatedRegs(bool isOutReg, bool isInReg,
3917                          std::set<unsigned> &OutputRegs,
3918                          std::set<unsigned> &InputRegs,
3919                          const TargetRegisterInfo &TRI) const {
3920     if (isOutReg) {
3921       for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i)
3922         MarkRegAndAliases(AssignedRegs.Regs[i], OutputRegs, TRI);
3923     }
3924     if (isInReg) {
3925       for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i)
3926         MarkRegAndAliases(AssignedRegs.Regs[i], InputRegs, TRI);
3927     }
3928   }
3929
3930 private:
3931   /// MarkRegAndAliases - Mark the specified register and all aliases in the
3932   /// specified set.
3933   static void MarkRegAndAliases(unsigned Reg, std::set<unsigned> &Regs,
3934                                 const TargetRegisterInfo &TRI) {
3935     assert(TargetRegisterInfo::isPhysicalRegister(Reg) && "Isn't a physreg");
3936     Regs.insert(Reg);
3937     if (const unsigned *Aliases = TRI.getAliasSet(Reg))
3938       for (; *Aliases; ++Aliases)
3939         Regs.insert(*Aliases);
3940   }
3941 };
3942 } // end anon namespace.
3943
3944
3945 /// GetRegistersForValue - Assign registers (virtual or physical) for the
3946 /// specified operand.  We prefer to assign virtual registers, to allow the
3947 /// register allocator handle the assignment process.  However, if the asm uses
3948 /// features that we can't model on machineinstrs, we have SDISel do the
3949 /// allocation.  This produces generally horrible, but correct, code.
3950 ///
3951 ///   OpInfo describes the operand.
3952 ///   HasEarlyClobber is true if there are any early clobber constraints (=&r)
3953 ///     or any explicitly clobbered registers.
3954 ///   Input and OutputRegs are the set of already allocated physical registers.
3955 ///
3956 void SelectionDAGLowering::
3957 GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, bool HasEarlyClobber,
3958                      std::set<unsigned> &OutputRegs,
3959                      std::set<unsigned> &InputRegs) {
3960   // Compute whether this value requires an input register, an output register,
3961   // or both.
3962   bool isOutReg = false;
3963   bool isInReg = false;
3964   switch (OpInfo.Type) {
3965   case InlineAsm::isOutput:
3966     isOutReg = true;
3967
3968     // If this is an early-clobber output, or if there is an input
3969     // constraint that matches this, we need to reserve the input register
3970     // so no other inputs allocate to it.
3971     isInReg = OpInfo.isEarlyClobber || OpInfo.hasMatchingInput;
3972     break;
3973   case InlineAsm::isInput:
3974     isInReg = true;
3975     isOutReg = false;
3976     break;
3977   case InlineAsm::isClobber:
3978     isOutReg = true;
3979     isInReg = true;
3980     break;
3981   }
3982
3983
3984   MachineFunction &MF = DAG.getMachineFunction();
3985   SmallVector<unsigned, 4> Regs;
3986
3987   // If this is a constraint for a single physreg, or a constraint for a
3988   // register class, find it.
3989   std::pair<unsigned, const TargetRegisterClass*> PhysReg =
3990     TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode,
3991                                      OpInfo.ConstraintVT);
3992
3993   unsigned NumRegs = 1;
3994   if (OpInfo.ConstraintVT != MVT::Other)
3995     NumRegs = TLI.getNumRegisters(OpInfo.ConstraintVT);
3996   MVT RegVT;
3997   MVT ValueVT = OpInfo.ConstraintVT;
3998
3999
4000   // If this is a constraint for a specific physical register, like {r17},
4001   // assign it now.
4002   if (PhysReg.first) {
4003     if (OpInfo.ConstraintVT == MVT::Other)
4004       ValueVT = *PhysReg.second->vt_begin();
4005
4006     // Get the actual register value type.  This is important, because the user
4007     // may have asked for (e.g.) the AX register in i32 type.  We need to
4008     // remember that AX is actually i16 to get the right extension.
4009     RegVT = *PhysReg.second->vt_begin();
4010
4011     // This is a explicit reference to a physical register.
4012     Regs.push_back(PhysReg.first);
4013
4014     // If this is an expanded reference, add the rest of the regs to Regs.
4015     if (NumRegs != 1) {
4016       TargetRegisterClass::iterator I = PhysReg.second->begin();
4017       for (; *I != PhysReg.first; ++I)
4018         assert(I != PhysReg.second->end() && "Didn't find reg!");
4019
4020       // Already added the first reg.
4021       --NumRegs; ++I;
4022       for (; NumRegs; --NumRegs, ++I) {
4023         assert(I != PhysReg.second->end() && "Ran out of registers to allocate!");
4024         Regs.push_back(*I);
4025       }
4026     }
4027     OpInfo.AssignedRegs = RegsForValue(TLI, Regs, RegVT, ValueVT);
4028     const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo();
4029     OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI);
4030     return;
4031   }
4032
4033   // Otherwise, if this was a reference to an LLVM register class, create vregs
4034   // for this reference.
4035   std::vector<unsigned> RegClassRegs;
4036   const TargetRegisterClass *RC = PhysReg.second;
4037   if (RC) {
4038     // If this is an early clobber or tied register, our regalloc doesn't know
4039     // how to maintain the constraint.  If it isn't, go ahead and create vreg
4040     // and let the regalloc do the right thing.
4041     if (!OpInfo.hasMatchingInput && !OpInfo.isEarlyClobber &&
4042         // If there is some other early clobber and this is an input register,
4043         // then we are forced to pre-allocate the input reg so it doesn't
4044         // conflict with the earlyclobber.
4045         !(OpInfo.Type == InlineAsm::isInput && HasEarlyClobber)) {
4046       RegVT = *PhysReg.second->vt_begin();
4047
4048       if (OpInfo.ConstraintVT == MVT::Other)
4049         ValueVT = RegVT;
4050
4051       // Create the appropriate number of virtual registers.
4052       MachineRegisterInfo &RegInfo = MF.getRegInfo();
4053       for (; NumRegs; --NumRegs)
4054         Regs.push_back(RegInfo.createVirtualRegister(PhysReg.second));
4055
4056       OpInfo.AssignedRegs = RegsForValue(TLI, Regs, RegVT, ValueVT);
4057       return;
4058     }
4059
4060     // Otherwise, we can't allocate it.  Let the code below figure out how to
4061     // maintain these constraints.
4062     RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
4063
4064   } else {
4065     // This is a reference to a register class that doesn't directly correspond
4066     // to an LLVM register class.  Allocate NumRegs consecutive, available,
4067     // registers from the class.
4068     RegClassRegs = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode,
4069                                                          OpInfo.ConstraintVT);
4070   }
4071
4072   const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo();
4073   unsigned NumAllocated = 0;
4074   for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
4075     unsigned Reg = RegClassRegs[i];
4076     // See if this register is available.
4077     if ((isOutReg && OutputRegs.count(Reg)) ||   // Already used.
4078         (isInReg  && InputRegs.count(Reg))) {    // Already used.
4079       // Make sure we find consecutive registers.
4080       NumAllocated = 0;
4081       continue;
4082     }
4083
4084     // Check to see if this register is allocatable (i.e. don't give out the
4085     // stack pointer).
4086     if (RC == 0) {
4087       RC = isAllocatableRegister(Reg, MF, TLI, TRI);
4088       if (!RC) {        // Couldn't allocate this register.
4089         // Reset NumAllocated to make sure we return consecutive registers.
4090         NumAllocated = 0;
4091         continue;
4092       }
4093     }
4094
4095     // Okay, this register is good, we can use it.
4096     ++NumAllocated;
4097
4098     // If we allocated enough consecutive registers, succeed.
4099     if (NumAllocated == NumRegs) {
4100       unsigned RegStart = (i-NumAllocated)+1;
4101       unsigned RegEnd   = i+1;
4102       // Mark all of the allocated registers used.
4103       for (unsigned i = RegStart; i != RegEnd; ++i)
4104         Regs.push_back(RegClassRegs[i]);
4105
4106       OpInfo.AssignedRegs = RegsForValue(TLI, Regs, *RC->vt_begin(),
4107                                          OpInfo.ConstraintVT);
4108       OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI);
4109       return;
4110     }
4111   }
4112
4113   // Otherwise, we couldn't allocate enough registers for this.
4114 }
4115
4116
4117 /// visitInlineAsm - Handle a call to an InlineAsm object.
4118 ///
4119 void SelectionDAGLowering::visitInlineAsm(CallSite CS) {
4120   InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
4121
4122   /// ConstraintOperands - Information about all of the constraints.
4123   std::vector<SDISelAsmOperandInfo> ConstraintOperands;
4124
4125   SDValue Chain = getRoot();
4126   SDValue Flag;
4127
4128   std::set<unsigned> OutputRegs, InputRegs;
4129
4130   // Do a prepass over the constraints, canonicalizing them, and building up the
4131   // ConstraintOperands list.
4132   std::vector<InlineAsm::ConstraintInfo>
4133     ConstraintInfos = IA->ParseConstraints();
4134
4135   // SawEarlyClobber - Keep track of whether we saw an earlyclobber output
4136   // constraint.  If so, we can't let the register allocator allocate any input
4137   // registers, because it will not know to avoid the earlyclobbered output reg.
4138   bool SawEarlyClobber = false;
4139
4140   unsigned ArgNo = 0;   // ArgNo - The argument of the CallInst.
4141   unsigned ResNo = 0;   // ResNo - The result number of the next output.
4142   for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) {
4143     ConstraintOperands.push_back(SDISelAsmOperandInfo(ConstraintInfos[i]));
4144     SDISelAsmOperandInfo &OpInfo = ConstraintOperands.back();
4145
4146     MVT OpVT = MVT::Other;
4147
4148     // Compute the value type for each operand.
4149     switch (OpInfo.Type) {
4150     case InlineAsm::isOutput:
4151       // Indirect outputs just consume an argument.
4152       if (OpInfo.isIndirect) {
4153         OpInfo.CallOperandVal = CS.getArgument(ArgNo++);
4154         break;
4155       }
4156       // The return value of the call is this value.  As such, there is no
4157       // corresponding argument.
4158       assert(CS.getType() != Type::VoidTy && "Bad inline asm!");
4159       if (const StructType *STy = dyn_cast<StructType>(CS.getType())) {
4160         OpVT = TLI.getValueType(STy->getElementType(ResNo));
4161       } else {
4162         assert(ResNo == 0 && "Asm only has one result!");
4163         OpVT = TLI.getValueType(CS.getType());
4164       }
4165       ++ResNo;
4166       break;
4167     case InlineAsm::isInput:
4168       OpInfo.CallOperandVal = CS.getArgument(ArgNo++);
4169       break;
4170     case InlineAsm::isClobber:
4171       // Nothing to do.
4172       break;
4173     }
4174
4175     // If this is an input or an indirect output, process the call argument.
4176     // BasicBlocks are labels, currently appearing only in asm's.
4177     if (OpInfo.CallOperandVal) {
4178       if (BasicBlock *BB = dyn_cast<BasicBlock>(OpInfo.CallOperandVal))
4179         OpInfo.CallOperand = DAG.getBasicBlock(FuncInfo.MBBMap[BB]);
4180       else {
4181         OpInfo.CallOperand = getValue(OpInfo.CallOperandVal);
4182         const Type *OpTy = OpInfo.CallOperandVal->getType();
4183         // If this is an indirect operand, the operand is a pointer to the
4184         // accessed type.
4185         if (OpInfo.isIndirect)
4186           OpTy = cast<PointerType>(OpTy)->getElementType();
4187
4188         // If OpTy is not a single value, it may be a struct/union that we
4189         // can tile with integers.
4190         if (!OpTy->isSingleValueType() && OpTy->isSized()) {
4191           unsigned BitSize = TD->getTypeSizeInBits(OpTy);
4192           switch (BitSize) {
4193           default: break;
4194           case 1:
4195           case 8:
4196           case 16:
4197           case 32:
4198           case 64:
4199             OpTy = IntegerType::get(BitSize);
4200             break;
4201           }
4202         }
4203
4204         OpVT = TLI.getValueType(OpTy, true);
4205       }
4206     }
4207
4208     OpInfo.ConstraintVT = OpVT;
4209
4210     // Compute the constraint code and ConstraintType to use.
4211     TLI.ComputeConstraintToUse(OpInfo, OpInfo.CallOperand, &DAG);
4212
4213     // Keep track of whether we see an earlyclobber.
4214     SawEarlyClobber |= OpInfo.isEarlyClobber;
4215
4216     // If we see a clobber of a register, it is an early clobber.
4217     if (!SawEarlyClobber &&
4218         OpInfo.Type == InlineAsm::isClobber &&
4219         OpInfo.ConstraintType == TargetLowering::C_Register) {
4220       // Note that we want to ignore things that we don't trick here, like
4221       // dirflag, fpsr, flags, etc.
4222       std::pair<unsigned, const TargetRegisterClass*> PhysReg =
4223         TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode,
4224                                          OpInfo.ConstraintVT);
4225       if (PhysReg.first || PhysReg.second) {
4226         // This is a register we know of.
4227         SawEarlyClobber = true;
4228       }
4229     }
4230
4231     // If this is a memory input, and if the operand is not indirect, do what we
4232     // need to to provide an address for the memory input.
4233     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
4234         !OpInfo.isIndirect) {
4235       assert(OpInfo.Type == InlineAsm::isInput &&
4236              "Can only indirectify direct input operands!");
4237
4238       // Memory operands really want the address of the value.  If we don't have
4239       // an indirect input, put it in the constpool if we can, otherwise spill
4240       // it to a stack slot.
4241
4242       // If the operand is a float, integer, or vector constant, spill to a
4243       // constant pool entry to get its address.
4244       Value *OpVal = OpInfo.CallOperandVal;
4245       if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) ||
4246           isa<ConstantVector>(OpVal)) {
4247         OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal),
4248                                                  TLI.getPointerTy());
4249       } else {
4250         // Otherwise, create a stack slot and emit a store to it before the
4251         // asm.
4252         const Type *Ty = OpVal->getType();
4253         uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
4254         unsigned Align  = TLI.getTargetData()->getPrefTypeAlignment(Ty);
4255         MachineFunction &MF = DAG.getMachineFunction();
4256         int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align);
4257         SDValue StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
4258         Chain = DAG.getStore(Chain, OpInfo.CallOperand, StackSlot, NULL, 0);
4259         OpInfo.CallOperand = StackSlot;
4260       }
4261
4262       // There is no longer a Value* corresponding to this operand.
4263       OpInfo.CallOperandVal = 0;
4264       // It is now an indirect operand.
4265       OpInfo.isIndirect = true;
4266     }
4267
4268     // If this constraint is for a specific register, allocate it before
4269     // anything else.
4270     if (OpInfo.ConstraintType == TargetLowering::C_Register)
4271       GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
4272   }
4273   ConstraintInfos.clear();
4274
4275
4276   // Second pass - Loop over all of the operands, assigning virtual or physregs
4277   // to registerclass operands.
4278   for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
4279     SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i];
4280
4281     // C_Register operands have already been allocated, Other/Memory don't need
4282     // to be.
4283     if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass)
4284       GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
4285   }
4286
4287   // AsmNodeOperands - The operands for the ISD::INLINEASM node.
4288   std::vector<SDValue> AsmNodeOperands;
4289   AsmNodeOperands.push_back(SDValue());  // reserve space for input chain
4290   AsmNodeOperands.push_back(
4291           DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other));
4292
4293
4294   // Loop over all of the inputs, copying the operand values into the
4295   // appropriate registers and processing the output regs.
4296   RegsForValue RetValRegs;
4297
4298   // IndirectStoresToEmit - The set of stores to emit after the inline asm node.
4299   std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
4300
4301   for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
4302     SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i];
4303
4304     switch (OpInfo.Type) {
4305     case InlineAsm::isOutput: {
4306       if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass &&
4307           OpInfo.ConstraintType != TargetLowering::C_Register) {
4308         // Memory output, or 'other' output (e.g. 'X' constraint).
4309         assert(OpInfo.isIndirect && "Memory output must be indirect operand");
4310
4311         // Add information to the INLINEASM node to know about this output.
4312         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
4313         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
4314                                                         TLI.getPointerTy()));
4315         AsmNodeOperands.push_back(OpInfo.CallOperand);
4316         break;
4317       }
4318
4319       // Otherwise, this is a register or register class output.
4320
4321       // Copy the output from the appropriate register.  Find a register that
4322       // we can use.
4323       if (OpInfo.AssignedRegs.Regs.empty()) {
4324         cerr << "Couldn't allocate output reg for constraint '"
4325              << OpInfo.ConstraintCode << "'!\n";
4326         exit(1);
4327       }
4328
4329       // If this is an indirect operand, store through the pointer after the
4330       // asm.
4331       if (OpInfo.isIndirect) {
4332         IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs,
4333                                                       OpInfo.CallOperandVal));
4334       } else {
4335         // This is the result value of the call.
4336         assert(CS.getType() != Type::VoidTy && "Bad inline asm!");
4337         // Concatenate this output onto the outputs list.
4338         RetValRegs.append(OpInfo.AssignedRegs);
4339       }
4340
4341       // Add information to the INLINEASM node to know that this register is
4342       // set.
4343       OpInfo.AssignedRegs.AddInlineAsmOperands(2 /*REGDEF*/, DAG,
4344                                                AsmNodeOperands);
4345       break;
4346     }
4347     case InlineAsm::isInput: {
4348       SDValue InOperandVal = OpInfo.CallOperand;
4349
4350       if (isdigit(OpInfo.ConstraintCode[0])) {    // Matching constraint?
4351         // If this is required to match an output register we have already set,
4352         // just use its register.
4353         unsigned OperandNo = atoi(OpInfo.ConstraintCode.c_str());
4354
4355         // Scan until we find the definition we already emitted of this operand.
4356         // When we find it, create a RegsForValue operand.
4357         unsigned CurOp = 2;  // The first operand.
4358         for (; OperandNo; --OperandNo) {
4359           // Advance to the next operand.
4360           unsigned NumOps =
4361             cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
4362           assert(((NumOps & 7) == 2 /*REGDEF*/ ||
4363                   (NumOps & 7) == 4 /*MEM*/) &&
4364                  "Skipped past definitions?");
4365           CurOp += (NumOps>>3)+1;
4366         }
4367
4368         unsigned NumOps =
4369           cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
4370         if ((NumOps & 7) == 2 /*REGDEF*/) {
4371           // Add NumOps>>3 registers to MatchedRegs.
4372           RegsForValue MatchedRegs;
4373           MatchedRegs.TLI = &TLI;
4374           MatchedRegs.ValueVTs.push_back(InOperandVal.getValueType());
4375           MatchedRegs.RegVTs.push_back(AsmNodeOperands[CurOp+1].getValueType());
4376           for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
4377             unsigned Reg =
4378               cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
4379             MatchedRegs.Regs.push_back(Reg);
4380           }
4381
4382           // Use the produced MatchedRegs object to
4383           MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag);
4384           MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
4385           break;
4386         } else {
4387           assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
4388           assert((NumOps >> 3) == 1 && "Unexpected number of operands");
4389           // Add information to the INLINEASM node to know about this input.
4390           unsigned ResOpType = 4/*MEM*/ | (1 << 3);
4391           AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
4392                                                           TLI.getPointerTy()));
4393           AsmNodeOperands.push_back(AsmNodeOperands[CurOp+1]);
4394           break;
4395         }
4396       }
4397
4398       if (OpInfo.ConstraintType == TargetLowering::C_Other) {
4399         assert(!OpInfo.isIndirect &&
4400                "Don't know how to handle indirect other inputs yet!");
4401
4402         std::vector<SDValue> Ops;
4403         TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0],
4404                                          Ops, DAG);
4405         if (Ops.empty()) {
4406           cerr << "Invalid operand for inline asm constraint '"
4407                << OpInfo.ConstraintCode << "'!\n";
4408           exit(1);
4409         }
4410
4411         // Add information to the INLINEASM node to know about this input.
4412         unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3);
4413         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
4414                                                         TLI.getPointerTy()));
4415         AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end());
4416         break;
4417       } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) {
4418         assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!");
4419         assert(InOperandVal.getValueType() == TLI.getPointerTy() &&
4420                "Memory operands expect pointer values");
4421
4422         // Add information to the INLINEASM node to know about this input.
4423         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
4424         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
4425                                                         TLI.getPointerTy()));
4426         AsmNodeOperands.push_back(InOperandVal);
4427         break;
4428       }
4429
4430       assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass ||
4431               OpInfo.ConstraintType == TargetLowering::C_Register) &&
4432              "Unknown constraint type!");
4433       assert(!OpInfo.isIndirect &&
4434              "Don't know how to handle indirect register inputs yet!");
4435
4436       // Copy the input into the appropriate registers.
4437       assert(!OpInfo.AssignedRegs.Regs.empty() &&
4438              "Couldn't allocate input reg!");
4439
4440       OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag);
4441
4442       OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG,
4443                                                AsmNodeOperands);
4444       break;
4445     }
4446     case InlineAsm::isClobber: {
4447       // Add the clobbered value to the operand list, so that the register
4448       // allocator is aware that the physreg got clobbered.
4449       if (!OpInfo.AssignedRegs.Regs.empty())
4450         OpInfo.AssignedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG,
4451                                                  AsmNodeOperands);
4452       break;
4453     }
4454     }
4455   }
4456
4457   // Finish up input operands.
4458   AsmNodeOperands[0] = Chain;
4459   if (Flag.Val) AsmNodeOperands.push_back(Flag);
4460
4461   Chain = DAG.getNode(ISD::INLINEASM,
4462                       DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
4463                       &AsmNodeOperands[0], AsmNodeOperands.size());
4464   Flag = Chain.getValue(1);
4465
4466   // If this asm returns a register value, copy the result from that register
4467   // and set it as the value of the call.
4468   if (!RetValRegs.Regs.empty()) {
4469     SDValue Val = RetValRegs.getCopyFromRegs(DAG, Chain, &Flag);
4470
4471     // If any of the results of the inline asm is a vector, it may have the
4472     // wrong width/num elts.  This can happen for register classes that can
4473     // contain multiple different value types.  The preg or vreg allocated may
4474     // not have the same VT as was expected.  Convert it to the right type with
4475     // bit_convert.
4476     if (const StructType *ResSTy = dyn_cast<StructType>(CS.getType())) {
4477       for (unsigned i = 0, e = ResSTy->getNumElements(); i != e; ++i) {
4478         if (Val.Val->getValueType(i).isVector())
4479           Val = DAG.getNode(ISD::BIT_CONVERT,
4480                             TLI.getValueType(ResSTy->getElementType(i)), Val);
4481       }
4482     } else {
4483       if (Val.getValueType().isVector())
4484         Val = DAG.getNode(ISD::BIT_CONVERT, TLI.getValueType(CS.getType()),
4485                           Val);
4486     }
4487
4488     setValue(CS.getInstruction(), Val);
4489   }
4490
4491   std::vector<std::pair<SDValue, Value*> > StoresToEmit;
4492
4493   // Process indirect outputs, first output all of the flagged copies out of
4494   // physregs.
4495   for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
4496     RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
4497     Value *Ptr = IndirectStoresToEmit[i].second;
4498     SDValue OutVal = OutRegs.getCopyFromRegs(DAG, Chain, &Flag);
4499     StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
4500   }
4501
4502   // Emit the non-flagged stores from the physregs.
4503   SmallVector<SDValue, 8> OutChains;
4504   for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
4505     OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
4506                                     getValue(StoresToEmit[i].second),
4507                                     StoresToEmit[i].second, 0));
4508   if (!OutChains.empty())
4509     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
4510                         &OutChains[0], OutChains.size());
4511   DAG.setRoot(Chain);
4512 }
4513
4514
4515 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
4516   SDValue Src = getValue(I.getOperand(0));
4517
4518   MVT IntPtr = TLI.getPointerTy();
4519
4520   if (IntPtr.bitsLT(Src.getValueType()))
4521     Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
4522   else if (IntPtr.bitsGT(Src.getValueType()))
4523     Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
4524
4525   // Scale the source by the type size.
4526   uint64_t ElementSize = TD->getABITypeSize(I.getType()->getElementType());
4527   Src = DAG.getNode(ISD::MUL, Src.getValueType(),
4528                     Src, DAG.getIntPtrConstant(ElementSize));
4529
4530   TargetLowering::ArgListTy Args;
4531   TargetLowering::ArgListEntry Entry;
4532   Entry.Node = Src;
4533   Entry.Ty = TLI.getTargetData()->getIntPtrType();
4534   Args.push_back(Entry);
4535
4536   std::pair<SDValue,SDValue> Result =
4537     TLI.LowerCallTo(getRoot(), I.getType(), false, false, false, CallingConv::C,
4538                     true, DAG.getExternalSymbol("malloc", IntPtr), Args, DAG);
4539   setValue(&I, Result.first);  // Pointers always fit in registers
4540   DAG.setRoot(Result.second);
4541 }
4542
4543 void SelectionDAGLowering::visitFree(FreeInst &I) {
4544   TargetLowering::ArgListTy Args;
4545   TargetLowering::ArgListEntry Entry;
4546   Entry.Node = getValue(I.getOperand(0));
4547   Entry.Ty = TLI.getTargetData()->getIntPtrType();
4548   Args.push_back(Entry);
4549   MVT IntPtr = TLI.getPointerTy();
4550   std::pair<SDValue,SDValue> Result =
4551     TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, false,
4552                     CallingConv::C, true,
4553                     DAG.getExternalSymbol("free", IntPtr), Args, DAG);
4554   DAG.setRoot(Result.second);
4555 }
4556
4557 // EmitInstrWithCustomInserter - This method should be implemented by targets
4558 // that mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
4559 // instructions are special in various ways, which require special support to
4560 // insert.  The specified MachineInstr is created but not inserted into any
4561 // basic blocks, and the scheduler passes ownership of it to this method.
4562 MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
4563                                                        MachineBasicBlock *MBB) {
4564   cerr << "If a target marks an instruction with "
4565        << "'usesCustomDAGSchedInserter', it must implement "
4566        << "TargetLowering::EmitInstrWithCustomInserter!\n";
4567   abort();
4568   return 0;
4569 }
4570
4571 void SelectionDAGLowering::visitVAStart(CallInst &I) {
4572   DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
4573                           getValue(I.getOperand(1)),
4574                           DAG.getSrcValue(I.getOperand(1))));
4575 }
4576
4577 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
4578   SDValue V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
4579                              getValue(I.getOperand(0)),
4580                              DAG.getSrcValue(I.getOperand(0)));
4581   setValue(&I, V);
4582   DAG.setRoot(V.getValue(1));
4583 }
4584
4585 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
4586   DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
4587                           getValue(I.getOperand(1)),
4588                           DAG.getSrcValue(I.getOperand(1))));
4589 }
4590
4591 void SelectionDAGLowering::visitVACopy(CallInst &I) {
4592   DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
4593                           getValue(I.getOperand(1)),
4594                           getValue(I.getOperand(2)),
4595                           DAG.getSrcValue(I.getOperand(1)),
4596                           DAG.getSrcValue(I.getOperand(2))));
4597 }
4598
4599 /// TargetLowering::LowerArguments - This is the default LowerArguments
4600 /// implementation, which just inserts a FORMAL_ARGUMENTS node.  FIXME: When all
4601 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
4602 /// integrated into SDISel.
4603 void TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG,
4604                                     SmallVectorImpl<SDValue> &ArgValues) {
4605   // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
4606   SmallVector<SDValue, 3+16> Ops;
4607   Ops.push_back(DAG.getRoot());
4608   Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
4609   Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
4610
4611   // Add one result value for each formal argument.
4612   SmallVector<MVT, 16> RetVals;
4613   unsigned j = 1;
4614   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
4615        I != E; ++I, ++j) {
4616     SmallVector<MVT, 4> ValueVTs;
4617     ComputeValueVTs(*this, I->getType(), ValueVTs);
4618     for (unsigned Value = 0, NumValues = ValueVTs.size();
4619          Value != NumValues; ++Value) {
4620       MVT VT = ValueVTs[Value];
4621       const Type *ArgTy = VT.getTypeForMVT();
4622       ISD::ArgFlagsTy Flags;
4623       unsigned OriginalAlignment =
4624         getTargetData()->getABITypeAlignment(ArgTy);
4625
4626       if (F.paramHasAttr(j, ParamAttr::ZExt))
4627         Flags.setZExt();
4628       if (F.paramHasAttr(j, ParamAttr::SExt))
4629         Flags.setSExt();
4630       if (F.paramHasAttr(j, ParamAttr::InReg))
4631         Flags.setInReg();
4632       if (F.paramHasAttr(j, ParamAttr::StructRet))
4633         Flags.setSRet();
4634       if (F.paramHasAttr(j, ParamAttr::ByVal)) {
4635         Flags.setByVal();
4636         const PointerType *Ty = cast<PointerType>(I->getType());
4637         const Type *ElementTy = Ty->getElementType();
4638         unsigned FrameAlign = getByValTypeAlignment(ElementTy);
4639         unsigned FrameSize  = getTargetData()->getABITypeSize(ElementTy);
4640         // For ByVal, alignment should be passed from FE.  BE will guess if
4641         // this info is not there but there are cases it cannot get right.
4642         if (F.getParamAlignment(j))
4643           FrameAlign = F.getParamAlignment(j);
4644         Flags.setByValAlign(FrameAlign);
4645         Flags.setByValSize(FrameSize);
4646       }
4647       if (F.paramHasAttr(j, ParamAttr::Nest))
4648         Flags.setNest();
4649       Flags.setOrigAlign(OriginalAlignment);
4650
4651       MVT RegisterVT = getRegisterType(VT);
4652       unsigned NumRegs = getNumRegisters(VT);
4653       for (unsigned i = 0; i != NumRegs; ++i) {
4654         RetVals.push_back(RegisterVT);
4655         ISD::ArgFlagsTy MyFlags = Flags;
4656         if (NumRegs > 1 && i == 0)
4657           MyFlags.setSplit();
4658         // if it isn't first piece, alignment must be 1
4659         else if (i > 0)
4660           MyFlags.setOrigAlign(1);
4661         Ops.push_back(DAG.getArgFlags(MyFlags));
4662       }
4663     }
4664   }
4665
4666   RetVals.push_back(MVT::Other);
4667
4668   // Create the node.
4669   SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
4670                                DAG.getVTList(&RetVals[0], RetVals.size()),
4671                                &Ops[0], Ops.size()).Val;
4672
4673   // Prelower FORMAL_ARGUMENTS.  This isn't required for functionality, but
4674   // allows exposing the loads that may be part of the argument access to the
4675   // first DAGCombiner pass.
4676   SDValue TmpRes = LowerOperation(SDValue(Result, 0), DAG);
4677
4678   // The number of results should match up, except that the lowered one may have
4679   // an extra flag result.
4680   assert((Result->getNumValues() == TmpRes.Val->getNumValues() ||
4681           (Result->getNumValues()+1 == TmpRes.Val->getNumValues() &&
4682            TmpRes.getValue(Result->getNumValues()).getValueType() == MVT::Flag))
4683          && "Lowering produced unexpected number of results!");
4684
4685   // The FORMAL_ARGUMENTS node itself is likely no longer needed.
4686   if (Result != TmpRes.Val && Result->use_empty()) {
4687     HandleSDNode Dummy(DAG.getRoot());
4688     DAG.RemoveDeadNode(Result);
4689   }
4690
4691   Result = TmpRes.Val;
4692
4693   unsigned NumArgRegs = Result->getNumValues() - 1;
4694   DAG.setRoot(SDValue(Result, NumArgRegs));
4695
4696   // Set up the return result vector.
4697   unsigned i = 0;
4698   unsigned Idx = 1;
4699   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
4700       ++I, ++Idx) {
4701     SmallVector<MVT, 4> ValueVTs;
4702     ComputeValueVTs(*this, I->getType(), ValueVTs);
4703     for (unsigned Value = 0, NumValues = ValueVTs.size();
4704          Value != NumValues; ++Value) {
4705       MVT VT = ValueVTs[Value];
4706       MVT PartVT = getRegisterType(VT);
4707
4708       unsigned NumParts = getNumRegisters(VT);
4709       SmallVector<SDValue, 4> Parts(NumParts);
4710       for (unsigned j = 0; j != NumParts; ++j)
4711         Parts[j] = SDValue(Result, i++);
4712
4713       ISD::NodeType AssertOp = ISD::DELETED_NODE;
4714       if (F.paramHasAttr(Idx, ParamAttr::SExt))
4715         AssertOp = ISD::AssertSext;
4716       else if (F.paramHasAttr(Idx, ParamAttr::ZExt))
4717         AssertOp = ISD::AssertZext;
4718
4719       ArgValues.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT,
4720                                            AssertOp));
4721     }
4722   }
4723   assert(i == NumArgRegs && "Argument register count mismatch!");
4724 }
4725
4726
4727 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
4728 /// implementation, which just inserts an ISD::CALL node, which is later custom
4729 /// lowered by the target to something concrete.  FIXME: When all targets are
4730 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
4731 std::pair<SDValue, SDValue>
4732 TargetLowering::LowerCallTo(SDValue Chain, const Type *RetTy,
4733                             bool RetSExt, bool RetZExt, bool isVarArg,
4734                             unsigned CallingConv, bool isTailCall,
4735                             SDValue Callee,
4736                             ArgListTy &Args, SelectionDAG &DAG) {
4737   SmallVector<SDValue, 32> Ops;
4738   Ops.push_back(Chain);   // Op#0 - Chain
4739   Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
4740   Ops.push_back(DAG.getConstant(isVarArg, getPointerTy()));    // Op#2 - VarArg
4741   Ops.push_back(DAG.getConstant(isTailCall, getPointerTy()));  // Op#3 - Tail
4742   Ops.push_back(Callee);
4743
4744   // Handle all of the outgoing arguments.
4745   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
4746     SmallVector<MVT, 4> ValueVTs;
4747     ComputeValueVTs(*this, Args[i].Ty, ValueVTs);
4748     for (unsigned Value = 0, NumValues = ValueVTs.size();
4749          Value != NumValues; ++Value) {
4750       MVT VT = ValueVTs[Value];
4751       const Type *ArgTy = VT.getTypeForMVT();
4752       SDValue Op = SDValue(Args[i].Node.Val, Args[i].Node.ResNo + Value);
4753       ISD::ArgFlagsTy Flags;
4754       unsigned OriginalAlignment =
4755         getTargetData()->getABITypeAlignment(ArgTy);
4756
4757       if (Args[i].isZExt)
4758         Flags.setZExt();
4759       if (Args[i].isSExt)
4760         Flags.setSExt();
4761       if (Args[i].isInReg)
4762         Flags.setInReg();
4763       if (Args[i].isSRet)
4764         Flags.setSRet();
4765       if (Args[i].isByVal) {
4766         Flags.setByVal();
4767         const PointerType *Ty = cast<PointerType>(Args[i].Ty);
4768         const Type *ElementTy = Ty->getElementType();
4769         unsigned FrameAlign = getByValTypeAlignment(ElementTy);
4770         unsigned FrameSize  = getTargetData()->getABITypeSize(ElementTy);
4771         // For ByVal, alignment should come from FE.  BE will guess if this
4772         // info is not there but there are cases it cannot get right.
4773         if (Args[i].Alignment)
4774           FrameAlign = Args[i].Alignment;
4775         Flags.setByValAlign(FrameAlign);
4776         Flags.setByValSize(FrameSize);
4777       }
4778       if (Args[i].isNest)
4779         Flags.setNest();
4780       Flags.setOrigAlign(OriginalAlignment);
4781
4782       MVT PartVT = getRegisterType(VT);
4783       unsigned NumParts = getNumRegisters(VT);
4784       SmallVector<SDValue, 4> Parts(NumParts);
4785       ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
4786
4787       if (Args[i].isSExt)
4788         ExtendKind = ISD::SIGN_EXTEND;
4789       else if (Args[i].isZExt)
4790         ExtendKind = ISD::ZERO_EXTEND;
4791
4792       getCopyToParts(DAG, Op, &Parts[0], NumParts, PartVT, ExtendKind);
4793
4794       for (unsigned i = 0; i != NumParts; ++i) {
4795         // if it isn't first piece, alignment must be 1
4796         ISD::ArgFlagsTy MyFlags = Flags;
4797         if (NumParts > 1 && i == 0)
4798           MyFlags.setSplit();
4799         else if (i != 0)
4800           MyFlags.setOrigAlign(1);
4801
4802         Ops.push_back(Parts[i]);
4803         Ops.push_back(DAG.getArgFlags(MyFlags));
4804       }
4805     }
4806   }
4807
4808   // Figure out the result value types. We start by making a list of
4809   // the potentially illegal return value types.
4810   SmallVector<MVT, 4> LoweredRetTys;
4811   SmallVector<MVT, 4> RetTys;
4812   ComputeValueVTs(*this, RetTy, RetTys);
4813
4814   // Then we translate that to a list of legal types.
4815   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
4816     MVT VT = RetTys[I];
4817     MVT RegisterVT = getRegisterType(VT);
4818     unsigned NumRegs = getNumRegisters(VT);
4819     for (unsigned i = 0; i != NumRegs; ++i)
4820       LoweredRetTys.push_back(RegisterVT);
4821   }
4822
4823   LoweredRetTys.push_back(MVT::Other);  // Always has a chain.
4824
4825   // Create the CALL node.
4826   SDValue Res = DAG.getNode(ISD::CALL,
4827                               DAG.getVTList(&LoweredRetTys[0],
4828                                             LoweredRetTys.size()),
4829                               &Ops[0], Ops.size());
4830   Chain = Res.getValue(LoweredRetTys.size() - 1);
4831
4832   // Gather up the call result into a single value.
4833   if (RetTy != Type::VoidTy) {
4834     ISD::NodeType AssertOp = ISD::DELETED_NODE;
4835
4836     if (RetSExt)
4837       AssertOp = ISD::AssertSext;
4838     else if (RetZExt)
4839       AssertOp = ISD::AssertZext;
4840
4841     SmallVector<SDValue, 4> ReturnValues;
4842     unsigned RegNo = 0;
4843     for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
4844       MVT VT = RetTys[I];
4845       MVT RegisterVT = getRegisterType(VT);
4846       unsigned NumRegs = getNumRegisters(VT);
4847       unsigned RegNoEnd = NumRegs + RegNo;
4848       SmallVector<SDValue, 4> Results;
4849       for (; RegNo != RegNoEnd; ++RegNo)
4850         Results.push_back(Res.getValue(RegNo));
4851       SDValue ReturnValue =
4852         getCopyFromParts(DAG, &Results[0], NumRegs, RegisterVT, VT,
4853                          AssertOp);
4854       ReturnValues.push_back(ReturnValue);
4855     }
4856     Res = DAG.getMergeValues(DAG.getVTList(&RetTys[0], RetTys.size()),
4857                              &ReturnValues[0], ReturnValues.size());
4858   }
4859
4860   return std::make_pair(Res, Chain);
4861 }
4862
4863 SDValue TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) {
4864   assert(0 && "LowerOperation not implemented for this target!");
4865   abort();
4866   return SDValue();
4867 }
4868
4869
4870 //===----------------------------------------------------------------------===//
4871 // SelectionDAGISel code
4872 //===----------------------------------------------------------------------===//
4873
4874 unsigned SelectionDAGISel::MakeReg(MVT VT) {
4875   return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
4876 }
4877
4878 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
4879   AU.addRequired<AliasAnalysis>();
4880   AU.addRequired<CollectorModuleMetadata>();
4881   AU.setPreservesAll();
4882 }
4883
4884 bool SelectionDAGISel::runOnFunction(Function &Fn) {
4885   // Get alias analysis for load/store combining.
4886   AA = &getAnalysis<AliasAnalysis>();
4887
4888   MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
4889   if (MF.getFunction()->hasCollector())
4890     GCI = &getAnalysis<CollectorModuleMetadata>().get(*MF.getFunction());
4891   else
4892     GCI = 0;
4893   RegInfo = &MF.getRegInfo();
4894   DOUT << "\n\n\n=== " << Fn.getName() << "\n";
4895
4896   FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
4897
4898   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
4899     if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
4900       // Mark landing pad.
4901       FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
4902
4903   SelectAllBasicBlocks(Fn, MF, FuncInfo);
4904
4905   // Add function live-ins to entry block live-in set.
4906   BasicBlock *EntryBB = &Fn.getEntryBlock();
4907   BB = FuncInfo.MBBMap[EntryBB];
4908   if (!RegInfo->livein_empty())
4909     for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
4910            E = RegInfo->livein_end(); I != E; ++I)
4911       BB->addLiveIn(I->first);
4912
4913 #ifndef NDEBUG
4914   assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() &&
4915          "Not all catch info was assigned to a landing pad!");
4916 #endif
4917
4918   return true;
4919 }
4920
4921 void SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, unsigned Reg) {
4922   SDValue Op = getValue(V);
4923   assert((Op.getOpcode() != ISD::CopyFromReg ||
4924           cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
4925          "Copy from a reg to the same reg!");
4926   assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && "Is a physreg");
4927
4928   RegsForValue RFV(TLI, Reg, V->getType());
4929   SDValue Chain = DAG.getEntryNode();
4930   RFV.getCopyToRegs(Op, DAG, Chain, 0);
4931   PendingExports.push_back(Chain);
4932 }
4933
4934 void SelectionDAGISel::
4935 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) {
4936   // If this is the entry block, emit arguments.
4937   Function &F = *LLVMBB->getParent();
4938   FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4939   SDValue OldRoot = SDL.DAG.getRoot();
4940   SmallVector<SDValue, 16> Args;
4941   TLI.LowerArguments(F, SDL.DAG, Args);
4942
4943   unsigned a = 0;
4944   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4945        AI != E; ++AI) {
4946     SmallVector<MVT, 4> ValueVTs;
4947     ComputeValueVTs(TLI, AI->getType(), ValueVTs);
4948     unsigned NumValues = ValueVTs.size();
4949     if (!AI->use_empty()) {
4950       SDL.setValue(AI, SDL.DAG.getMergeValues(&Args[a], NumValues));
4951       // If this argument is live outside of the entry block, insert a copy from
4952       // whereever we got it to the vreg that other BB's will reference it as.
4953       DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4954       if (VMI != FuncInfo.ValueMap.end()) {
4955         SDL.CopyValueToVirtualRegister(AI, VMI->second);
4956       }
4957     }
4958     a += NumValues;
4959   }
4960
4961   // Finally, if the target has anything special to do, allow it to do so.
4962   // FIXME: this should insert code into the DAG!
4963   EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4964 }
4965
4966 static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
4967                           MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
4968   for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
4969     if (isSelector(I)) {
4970       // Apply the catch info to DestBB.
4971       addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]);
4972 #ifndef NDEBUG
4973       if (!FLI.MBBMap[SrcBB]->isLandingPad())
4974         FLI.CatchInfoFound.insert(I);
4975 #endif
4976     }
4977 }
4978
4979 /// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and
4980 /// whether object offset >= 0.
4981 static bool
4982 IsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) {
4983   if (!isa<FrameIndexSDNode>(Op)) return false;
4984
4985   FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op);
4986   int FrameIdx =  FrameIdxNode->getIndex();
4987   return MFI->isFixedObjectIndex(FrameIdx) &&
4988     MFI->getObjectOffset(FrameIdx) >= 0;
4989 }
4990
4991 /// IsPossiblyOverwrittenArgumentOfTailCall - Check if the operand could
4992 /// possibly be overwritten when lowering the outgoing arguments in a tail
4993 /// call. Currently the implementation of this call is very conservative and
4994 /// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with
4995 /// virtual registers would be overwritten by direct lowering.
4996 static bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op,
4997                                                     MachineFrameInfo * MFI) {
4998   RegisterSDNode * OpReg = NULL;
4999   if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS ||
5000       (Op.getOpcode()== ISD::CopyFromReg &&
5001        (OpReg = dyn_cast<RegisterSDNode>(Op.getOperand(1))) &&
5002        (OpReg->getReg() >= TargetRegisterInfo::FirstVirtualRegister)) ||
5003       (Op.getOpcode() == ISD::LOAD &&
5004        IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) ||
5005       (Op.getOpcode() == ISD::MERGE_VALUES &&
5006        Op.getOperand(Op.ResNo).getOpcode() == ISD::LOAD &&
5007        IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.ResNo).
5008                                        getOperand(1))))
5009     return true;
5010   return false;
5011 }
5012
5013 /// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the
5014 /// DAG and fixes their tailcall attribute operand.
5015 static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG,
5016                                            TargetLowering& TLI) {
5017   SDNode * Ret = NULL;
5018   SDValue Terminator = DAG.getRoot();
5019
5020   // Find RET node.
5021   if (Terminator.getOpcode() == ISD::RET) {
5022     Ret = Terminator.Val;
5023   }
5024
5025   // Fix tail call attribute of CALL nodes.
5026   for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
5027          BI = DAG.allnodes_end(); BI != BE; ) {
5028     --BI;
5029     if (BI->getOpcode() == ISD::CALL) {
5030       SDValue OpRet(Ret, 0);
5031       SDValue OpCall(BI, 0);
5032       bool isMarkedTailCall =
5033         cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0;
5034       // If CALL node has tail call attribute set to true and the call is not
5035       // eligible (no RET or the target rejects) the attribute is fixed to
5036       // false. The TargetLowering::IsEligibleForTailCallOptimization function
5037       // must correctly identify tail call optimizable calls.
5038       if (!isMarkedTailCall) continue;
5039       if (Ret==NULL ||
5040           !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG)) {
5041         // Not eligible. Mark CALL node as non tail call.
5042         SmallVector<SDValue, 32> Ops;
5043         unsigned idx=0;
5044         for(SDNode::op_iterator I =OpCall.Val->op_begin(),
5045               E = OpCall.Val->op_end(); I != E; I++, idx++) {
5046           if (idx!=3)
5047             Ops.push_back(*I);
5048           else
5049             Ops.push_back(DAG.getConstant(false, TLI.getPointerTy()));
5050         }
5051         DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
5052       } else {
5053         // Look for tail call clobbered arguments. Emit a series of
5054         // copyto/copyfrom virtual register nodes to protect them.
5055         SmallVector<SDValue, 32> Ops;
5056         SDValue Chain = OpCall.getOperand(0), InFlag;
5057         unsigned idx=0;
5058         for(SDNode::op_iterator I = OpCall.Val->op_begin(),
5059               E = OpCall.Val->op_end(); I != E; I++, idx++) {
5060           SDValue Arg = *I;
5061           if (idx > 4 && (idx % 2)) {
5062             bool isByVal = cast<ARG_FLAGSSDNode>(OpCall.getOperand(idx+1))->
5063               getArgFlags().isByVal();
5064             MachineFunction &MF = DAG.getMachineFunction();
5065             MachineFrameInfo *MFI = MF.getFrameInfo();
5066             if (!isByVal &&
5067                 IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) {
5068               MVT VT = Arg.getValueType();
5069               unsigned VReg = MF.getRegInfo().
5070                 createVirtualRegister(TLI.getRegClassFor(VT));
5071               Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag);
5072               InFlag = Chain.getValue(1);
5073               Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag);
5074               Chain = Arg.getValue(1);
5075               InFlag = Arg.getValue(2);
5076             }
5077           }
5078           Ops.push_back(Arg);
5079         }
5080         // Link in chain of CopyTo/CopyFromReg.
5081         Ops[0] = Chain;
5082         DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
5083       }
5084     }
5085   }
5086 }
5087
5088 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
5089        std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
5090                                          FunctionLoweringInfo &FuncInfo) {
5091   SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo, GCI);
5092
5093   // Lower any arguments needed in this block if this is the entry block.
5094   if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
5095     LowerArguments(LLVMBB, SDL);
5096
5097   BB = FuncInfo.MBBMap[LLVMBB];
5098   SDL.setCurrentBasicBlock(BB);
5099
5100   MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
5101
5102   if (MMI && BB->isLandingPad()) {
5103     // Add a label to mark the beginning of the landing pad.  Deletion of the
5104     // landing pad can thus be detected via the MachineModuleInfo.
5105     unsigned LabelID = MMI->addLandingPad(BB);
5106     DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, DAG.getEntryNode(), LabelID));
5107
5108     // Mark exception register as live in.
5109     unsigned Reg = TLI.getExceptionAddressRegister();
5110     if (Reg) BB->addLiveIn(Reg);
5111
5112     // Mark exception selector register as live in.
5113     Reg = TLI.getExceptionSelectorRegister();
5114     if (Reg) BB->addLiveIn(Reg);
5115
5116     // FIXME: Hack around an exception handling flaw (PR1508): the personality
5117     // function and list of typeids logically belong to the invoke (or, if you
5118     // like, the basic block containing the invoke), and need to be associated
5119     // with it in the dwarf exception handling tables.  Currently however the
5120     // information is provided by an intrinsic (eh.selector) that can be moved
5121     // to unexpected places by the optimizers: if the unwind edge is critical,
5122     // then breaking it can result in the intrinsics being in the successor of
5123     // the landing pad, not the landing pad itself.  This results in exceptions
5124     // not being caught because no typeids are associated with the invoke.
5125     // This may not be the only way things can go wrong, but it is the only way
5126     // we try to work around for the moment.
5127     BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
5128
5129     if (Br && Br->isUnconditional()) { // Critical edge?
5130       BasicBlock::iterator I, E;
5131       for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
5132         if (isSelector(I))
5133           break;
5134
5135       if (I == E)
5136         // No catch info found - try to extract some from the successor.
5137         copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo);
5138     }
5139   }
5140
5141   // Lower all of the non-terminator instructions.
5142   for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
5143        I != E; ++I)
5144     SDL.visit(*I);
5145
5146   // Ensure that all instructions which are used outside of their defining
5147   // blocks are available as virtual registers.  Invoke is handled elsewhere.
5148   for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
5149     if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) {
5150       DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
5151       if (VMI != FuncInfo.ValueMap.end())
5152         SDL.CopyValueToVirtualRegister(I, VMI->second);
5153     }
5154
5155   // Handle PHI nodes in successor blocks.  Emit code into the SelectionDAG to
5156   // ensure constants are generated when needed.  Remember the virtual registers
5157   // that need to be added to the Machine PHI nodes as input.  We cannot just
5158   // directly add them, because expansion might result in multiple MBB's for one
5159   // BB.  As such, the start of the BB might correspond to a different MBB than
5160   // the end.
5161   //
5162   TerminatorInst *TI = LLVMBB->getTerminator();
5163
5164   // Emit constants only once even if used by multiple PHI nodes.
5165   std::map<Constant*, unsigned> ConstantsOut;
5166
5167   // Vector bool would be better, but vector<bool> is really slow.
5168   std::vector<unsigned char> SuccsHandled;
5169   if (TI->getNumSuccessors())
5170     SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
5171
5172   // Check successor nodes' PHI nodes that expect a constant to be available
5173   // from this block.
5174   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
5175     BasicBlock *SuccBB = TI->getSuccessor(succ);
5176     if (!isa<PHINode>(SuccBB->begin())) continue;
5177     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
5178
5179     // If this terminator has multiple identical successors (common for
5180     // switches), only handle each succ once.
5181     unsigned SuccMBBNo = SuccMBB->getNumber();
5182     if (SuccsHandled[SuccMBBNo]) continue;
5183     SuccsHandled[SuccMBBNo] = true;
5184
5185     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
5186     PHINode *PN;
5187
5188     // At this point we know that there is a 1-1 correspondence between LLVM PHI
5189     // nodes and Machine PHI nodes, but the incoming operands have not been
5190     // emitted yet.
5191     for (BasicBlock::iterator I = SuccBB->begin();
5192          (PN = dyn_cast<PHINode>(I)); ++I) {
5193       // Ignore dead phi's.
5194       if (PN->use_empty()) continue;
5195
5196       unsigned Reg;
5197       Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
5198
5199       if (Constant *C = dyn_cast<Constant>(PHIOp)) {
5200         unsigned &RegOut = ConstantsOut[C];
5201         if (RegOut == 0) {
5202           RegOut = FuncInfo.CreateRegForValue(C);
5203           SDL.CopyValueToVirtualRegister(C, RegOut);
5204         }
5205         Reg = RegOut;
5206       } else {
5207         Reg = FuncInfo.ValueMap[PHIOp];
5208         if (Reg == 0) {
5209           assert(isa<AllocaInst>(PHIOp) &&
5210                  FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
5211                  "Didn't codegen value into a register!??");
5212           Reg = FuncInfo.CreateRegForValue(PHIOp);
5213           SDL.CopyValueToVirtualRegister(PHIOp, Reg);
5214         }
5215       }
5216
5217       // Remember that this register needs to added to the machine PHI node as
5218       // the input for this MBB.
5219       SmallVector<MVT, 4> ValueVTs;
5220       ComputeValueVTs(TLI, PN->getType(), ValueVTs);
5221       for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
5222         MVT VT = ValueVTs[vti];
5223         unsigned NumRegisters = TLI.getNumRegisters(VT);
5224         for (unsigned i = 0, e = NumRegisters; i != e; ++i)
5225           PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
5226         Reg += NumRegisters;
5227       }
5228     }
5229   }
5230   ConstantsOut.clear();
5231
5232   // Lower the terminator after the copies are emitted.
5233   SDL.visit(*LLVMBB->getTerminator());
5234
5235   // Copy over any CaseBlock records that may now exist due to SwitchInst
5236   // lowering, as well as any jump table information.
5237   SwitchCases.clear();
5238   SwitchCases = SDL.SwitchCases;
5239   JTCases.clear();
5240   JTCases = SDL.JTCases;
5241   BitTestCases.clear();
5242   BitTestCases = SDL.BitTestCases;
5243
5244   // Make sure the root of the DAG is up-to-date.
5245   DAG.setRoot(SDL.getControlRoot());
5246
5247   // Check whether calls in this block are real tail calls. Fix up CALL nodes
5248   // with correct tailcall attribute so that the target can rely on the tailcall
5249   // attribute indicating whether the call is really eligible for tail call
5250   // optimization.
5251   CheckDAGForTailCallsAndFixThem(DAG, TLI);
5252 }
5253
5254 void SelectionDAGISel::ComputeLiveOutVRegInfo(SelectionDAG &DAG) {
5255   SmallPtrSet<SDNode*, 128> VisitedNodes;
5256   SmallVector<SDNode*, 128> Worklist;
5257
5258   Worklist.push_back(DAG.getRoot().Val);
5259
5260   APInt Mask;
5261   APInt KnownZero;
5262   APInt KnownOne;
5263
5264   while (!Worklist.empty()) {
5265     SDNode *N = Worklist.back();
5266     Worklist.pop_back();
5267
5268     // If we've already seen this node, ignore it.
5269     if (!VisitedNodes.insert(N))
5270       continue;
5271
5272     // Otherwise, add all chain operands to the worklist.
5273     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5274       if (N->getOperand(i).getValueType() == MVT::Other)
5275         Worklist.push_back(N->getOperand(i).Val);
5276
5277     // If this is a CopyToReg with a vreg dest, process it.
5278     if (N->getOpcode() != ISD::CopyToReg)
5279       continue;
5280
5281     unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
5282     if (!TargetRegisterInfo::isVirtualRegister(DestReg))
5283       continue;
5284
5285     // Ignore non-scalar or non-integer values.
5286     SDValue Src = N->getOperand(2);
5287     MVT SrcVT = Src.getValueType();
5288     if (!SrcVT.isInteger() || SrcVT.isVector())
5289       continue;
5290
5291     unsigned NumSignBits = DAG.ComputeNumSignBits(Src);
5292     Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits());
5293     DAG.ComputeMaskedBits(Src, Mask, KnownZero, KnownOne);
5294
5295     // Only install this information if it tells us something.
5296     if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) {
5297       DestReg -= TargetRegisterInfo::FirstVirtualRegister;
5298       FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo();
5299       if (DestReg >= FLI.LiveOutRegInfo.size())
5300         FLI.LiveOutRegInfo.resize(DestReg+1);
5301       FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg];
5302       LOI.NumSignBits = NumSignBits;
5303       LOI.KnownOne = NumSignBits;
5304       LOI.KnownZero = NumSignBits;
5305     }
5306   }
5307 }
5308
5309 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
5310   std::string GroupName;
5311   if (TimePassesIsEnabled)
5312     GroupName = "Instruction Selection and Scheduling";
5313   std::string BlockName;
5314   if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
5315       ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs)
5316     BlockName = DAG.getMachineFunction().getFunction()->getName() + ':' +
5317                 BB->getBasicBlock()->getName();
5318
5319   DOUT << "Initial selection DAG:\n";
5320   DEBUG(DAG.dump());
5321
5322   if (ViewDAGCombine1) DAG.viewGraph("dag-combine1 input for " + BlockName);
5323
5324   // Run the DAG combiner in pre-legalize mode.
5325   if (TimePassesIsEnabled) {
5326     NamedRegionTimer T("DAG Combining 1", GroupName);
5327     DAG.Combine(false, *AA);
5328   } else {
5329     DAG.Combine(false, *AA);
5330   }
5331
5332   DOUT << "Optimized lowered selection DAG:\n";
5333   DEBUG(DAG.dump());
5334
5335   // Second step, hack on the DAG until it only uses operations and types that
5336   // the target supports.
5337   if (EnableLegalizeTypes) {// Enable this some day.
5338     if (ViewLegalizeTypesDAGs) DAG.viewGraph("legalize-types input for " +
5339                                              BlockName);
5340
5341     if (TimePassesIsEnabled) {
5342       NamedRegionTimer T("Type Legalization", GroupName);
5343       DAG.LegalizeTypes();
5344     } else {
5345       DAG.LegalizeTypes();
5346     }
5347
5348     DOUT << "Type-legalized selection DAG:\n";
5349     DEBUG(DAG.dump());
5350
5351     // TODO: enable a dag combine pass here.
5352   }
5353
5354   if (ViewLegalizeDAGs) DAG.viewGraph("legalize input for " + BlockName);
5355
5356   if (TimePassesIsEnabled) {
5357     NamedRegionTimer T("DAG Legalization", GroupName);
5358     DAG.Legalize();
5359   } else {
5360     DAG.Legalize();
5361   }
5362
5363   DOUT << "Legalized selection DAG:\n";
5364   DEBUG(DAG.dump());
5365
5366   if (ViewDAGCombine2) DAG.viewGraph("dag-combine2 input for " + BlockName);
5367
5368   // Run the DAG combiner in post-legalize mode.
5369   if (TimePassesIsEnabled) {
5370     NamedRegionTimer T("DAG Combining 2", GroupName);
5371     DAG.Combine(true, *AA);
5372   } else {
5373     DAG.Combine(true, *AA);
5374   }
5375
5376   DOUT << "Optimized legalized selection DAG:\n";
5377   DEBUG(DAG.dump());
5378
5379   if (ViewISelDAGs) DAG.viewGraph("isel input for " + BlockName);
5380
5381   if (!FastISel && EnableValueProp)
5382     ComputeLiveOutVRegInfo(DAG);
5383
5384   // Third, instruction select all of the operations to machine code, adding the
5385   // code to the MachineBasicBlock.
5386   if (TimePassesIsEnabled) {
5387     NamedRegionTimer T("Instruction Selection", GroupName);
5388     InstructionSelect(DAG);
5389   } else {
5390     InstructionSelect(DAG);
5391   }
5392
5393   DOUT << "Selected selection DAG:\n";
5394   DEBUG(DAG.dump());
5395
5396   if (ViewSchedDAGs) DAG.viewGraph("scheduler input for " + BlockName);
5397
5398   // Schedule machine code.
5399   ScheduleDAG *Scheduler;
5400   if (TimePassesIsEnabled) {
5401     NamedRegionTimer T("Instruction Scheduling", GroupName);
5402     Scheduler = Schedule(DAG);
5403   } else {
5404     Scheduler = Schedule(DAG);
5405   }
5406
5407   if (ViewSUnitDAGs) Scheduler->viewGraph();
5408
5409   // Emit machine code to BB.  This can change 'BB' to the last block being
5410   // inserted into.
5411   if (TimePassesIsEnabled) {
5412     NamedRegionTimer T("Instruction Creation", GroupName);
5413     BB = Scheduler->EmitSchedule();
5414   } else {
5415     BB = Scheduler->EmitSchedule();
5416   }
5417
5418   // Free the scheduler state.
5419   if (TimePassesIsEnabled) {
5420     NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName);
5421     delete Scheduler;
5422   } else {
5423     delete Scheduler;
5424   }
5425
5426   // Perform target specific isel post processing.
5427   if (TimePassesIsEnabled) {
5428     NamedRegionTimer T("Instruction Selection Post Processing", GroupName);
5429     InstructionSelectPostProcessing();
5430   } else {
5431     InstructionSelectPostProcessing();
5432   }
5433
5434   DOUT << "Selected machine code:\n";
5435   DEBUG(BB->dump());
5436 }
5437
5438 void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
5439                                             FunctionLoweringInfo &FuncInfo) {
5440   // Define NodeAllocator here so that memory allocation is reused for
5441   // each basic block.
5442   NodeAllocatorType NodeAllocator;
5443
5444   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
5445   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
5446     BasicBlock *LLVMBB = &*I;
5447     PHINodesToUpdate.clear();
5448     SelectBasicBlock(LLVMBB, MF, FuncInfo, PHINodesToUpdate, NodeAllocator);
5449     FinishBasicBlock(LLVMBB, MF, FuncInfo, PHINodesToUpdate, NodeAllocator);
5450   }
5451 }
5452
5453 void
5454 SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
5455                                    FunctionLoweringInfo &FuncInfo,
5456              std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
5457                                    NodeAllocatorType &NodeAllocator) {
5458   SelectionDAG DAG(TLI, MF, FuncInfo,
5459                    getAnalysisToUpdate<MachineModuleInfo>(),
5460                    NodeAllocator);
5461   CurDAG = &DAG;
5462
5463   // First step, lower LLVM code to some DAG.  This DAG may use operations and
5464   // types that are not supported by the target.
5465   BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
5466
5467   // Second step, emit the lowered DAG as machine code.
5468   CodeGenAndEmitDAG(DAG);
5469 }
5470
5471 void
5472 SelectionDAGISel::FinishBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
5473                                    FunctionLoweringInfo &FuncInfo,
5474              std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
5475                                    NodeAllocatorType &NodeAllocator) {
5476   DOUT << "Total amount of phi nodes to update: "
5477        << PHINodesToUpdate.size() << "\n";
5478   DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i)
5479           DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first
5480                << ", " << PHINodesToUpdate[i].second << ")\n";);
5481
5482   // Next, now that we know what the last MBB the LLVM BB expanded is, update
5483   // PHI nodes in successors.
5484   if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) {
5485     for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
5486       MachineInstr *PHI = PHINodesToUpdate[i].first;
5487       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
5488              "This is not a machine PHI node that we are updating!");
5489       PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second,
5490                                                 false));
5491       PHI->addOperand(MachineOperand::CreateMBB(BB));
5492     }
5493     return;
5494   }
5495
5496   for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) {
5497     // Lower header first, if it wasn't already lowered
5498     if (!BitTestCases[i].Emitted) {
5499       SelectionDAG HSDAG(TLI, MF, FuncInfo,
5500                          getAnalysisToUpdate<MachineModuleInfo>(),
5501                          NodeAllocator);
5502       CurDAG = &HSDAG;
5503       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
5504       // Set the current basic block to the mbb we wish to insert the code into
5505       BB = BitTestCases[i].Parent;
5506       HSDL.setCurrentBasicBlock(BB);
5507       // Emit the code
5508       HSDL.visitBitTestHeader(BitTestCases[i]);
5509       HSDAG.setRoot(HSDL.getRoot());
5510       CodeGenAndEmitDAG(HSDAG);
5511     }
5512
5513     for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
5514       SelectionDAG BSDAG(TLI, MF, FuncInfo,
5515                          getAnalysisToUpdate<MachineModuleInfo>(),
5516                          NodeAllocator);
5517       CurDAG = &BSDAG;
5518       SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI);
5519       // Set the current basic block to the mbb we wish to insert the code into
5520       BB = BitTestCases[i].Cases[j].ThisBB;
5521       BSDL.setCurrentBasicBlock(BB);
5522       // Emit the code
5523       if (j+1 != ej)
5524         BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB,
5525                               BitTestCases[i].Reg,
5526                               BitTestCases[i].Cases[j]);
5527       else
5528         BSDL.visitBitTestCase(BitTestCases[i].Default,
5529                               BitTestCases[i].Reg,
5530                               BitTestCases[i].Cases[j]);
5531
5532
5533       BSDAG.setRoot(BSDL.getRoot());
5534       CodeGenAndEmitDAG(BSDAG);
5535     }
5536
5537     // Update PHI Nodes
5538     for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
5539       MachineInstr *PHI = PHINodesToUpdate[pi].first;
5540       MachineBasicBlock *PHIBB = PHI->getParent();
5541       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
5542              "This is not a machine PHI node that we are updating!");
5543       // This is "default" BB. We have two jumps to it. From "header" BB and
5544       // from last "case" BB.
5545       if (PHIBB == BitTestCases[i].Default) {
5546         PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
5547                                                   false));
5548         PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Parent));
5549         PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
5550                                                   false));
5551         PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Cases.
5552                                                   back().ThisBB));
5553       }
5554       // One of "cases" BB.
5555       for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
5556         MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB;
5557         if (cBB->succ_end() !=
5558             std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
5559           PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
5560                                                     false));
5561           PHI->addOperand(MachineOperand::CreateMBB(cBB));
5562         }
5563       }
5564     }
5565   }
5566
5567   // If the JumpTable record is filled in, then we need to emit a jump table.
5568   // Updating the PHI nodes is tricky in this case, since we need to determine
5569   // whether the PHI is a successor of the range check MBB or the jump table MBB
5570   for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
5571     // Lower header first, if it wasn't already lowered
5572     if (!JTCases[i].first.Emitted) {
5573       SelectionDAG HSDAG(TLI, MF, FuncInfo,
5574                          getAnalysisToUpdate<MachineModuleInfo>(),
5575                          NodeAllocator);
5576       CurDAG = &HSDAG;
5577       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
5578       // Set the current basic block to the mbb we wish to insert the code into
5579       BB = JTCases[i].first.HeaderBB;
5580       HSDL.setCurrentBasicBlock(BB);
5581       // Emit the code
5582       HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
5583       HSDAG.setRoot(HSDL.getRoot());
5584       CodeGenAndEmitDAG(HSDAG);
5585     }
5586
5587     SelectionDAG JSDAG(TLI, MF, FuncInfo,
5588                        getAnalysisToUpdate<MachineModuleInfo>(),
5589                        NodeAllocator);
5590     CurDAG = &JSDAG;
5591     SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI);
5592     // Set the current basic block to the mbb we wish to insert the code into
5593     BB = JTCases[i].second.MBB;
5594     JSDL.setCurrentBasicBlock(BB);
5595     // Emit the code
5596     JSDL.visitJumpTable(JTCases[i].second);
5597     JSDAG.setRoot(JSDL.getRoot());
5598     CodeGenAndEmitDAG(JSDAG);
5599
5600     // Update PHI Nodes
5601     for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
5602       MachineInstr *PHI = PHINodesToUpdate[pi].first;
5603       MachineBasicBlock *PHIBB = PHI->getParent();
5604       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
5605              "This is not a machine PHI node that we are updating!");
5606       // "default" BB. We can go there only from header BB.
5607       if (PHIBB == JTCases[i].second.Default) {
5608         PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
5609                                                   false));
5610         PHI->addOperand(MachineOperand::CreateMBB(JTCases[i].first.HeaderBB));
5611       }
5612       // JT BB. Just iterate over successors here
5613       if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
5614         PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
5615                                                   false));
5616         PHI->addOperand(MachineOperand::CreateMBB(BB));
5617       }
5618     }
5619   }
5620
5621   // If the switch block involved a branch to one of the actual successors, we
5622   // need to update PHI nodes in that block.
5623   for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
5624     MachineInstr *PHI = PHINodesToUpdate[i].first;
5625     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
5626            "This is not a machine PHI node that we are updating!");
5627     if (BB->isSuccessor(PHI->getParent())) {
5628       PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second,
5629                                                 false));
5630       PHI->addOperand(MachineOperand::CreateMBB(BB));
5631     }
5632   }
5633
5634   // If we generated any switch lowering information, build and codegen any
5635   // additional DAGs necessary.
5636   for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
5637     SelectionDAG SDAG(TLI, MF, FuncInfo,
5638                       getAnalysisToUpdate<MachineModuleInfo>(),
5639                       NodeAllocator);
5640     CurDAG = &SDAG;
5641     SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI);
5642
5643     // Set the current basic block to the mbb we wish to insert the code into
5644     BB = SwitchCases[i].ThisBB;
5645     SDL.setCurrentBasicBlock(BB);
5646
5647     // Emit the code
5648     SDL.visitSwitchCase(SwitchCases[i]);
5649     SDAG.setRoot(SDL.getRoot());
5650     CodeGenAndEmitDAG(SDAG);
5651
5652     // Handle any PHI nodes in successors of this chunk, as if we were coming
5653     // from the original BB before switch expansion.  Note that PHI nodes can
5654     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
5655     // handle them the right number of times.
5656     while ((BB = SwitchCases[i].TrueBB)) {  // Handle LHS and RHS.
5657       for (MachineBasicBlock::iterator Phi = BB->begin();
5658            Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
5659         // This value for this PHI node is recorded in PHINodesToUpdate, get it.
5660         for (unsigned pn = 0; ; ++pn) {
5661           assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
5662           if (PHINodesToUpdate[pn].first == Phi) {
5663             Phi->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pn].
5664                                                       second, false));
5665             Phi->addOperand(MachineOperand::CreateMBB(SwitchCases[i].ThisBB));
5666             break;
5667           }
5668         }
5669       }
5670
5671       // Don't process RHS if same block as LHS.
5672       if (BB == SwitchCases[i].FalseBB)
5673         SwitchCases[i].FalseBB = 0;
5674
5675       // If we haven't handled the RHS, do so now.  Otherwise, we're done.
5676       SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
5677       SwitchCases[i].FalseBB = 0;
5678     }
5679     assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
5680   }
5681 }
5682
5683
5684 /// Schedule - Pick a safe ordering for instructions for each
5685 /// target node in the graph.
5686 ///
5687 ScheduleDAG *SelectionDAGISel::Schedule(SelectionDAG &DAG) {
5688   RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
5689
5690   if (!Ctor) {
5691     Ctor = ISHeuristic;
5692     RegisterScheduler::setDefault(Ctor);
5693   }
5694
5695   ScheduleDAG *Scheduler = Ctor(this, &DAG, BB, FastISel);
5696   Scheduler->Run();
5697
5698   return Scheduler;
5699 }
5700
5701
5702 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
5703   return new HazardRecognizer();
5704 }
5705
5706 //===----------------------------------------------------------------------===//
5707 // Helper functions used by the generated instruction selector.
5708 //===----------------------------------------------------------------------===//
5709 // Calls to these methods are generated by tblgen.
5710
5711 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
5712 /// the dag combiner simplified the 255, we still want to match.  RHS is the
5713 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
5714 /// specified in the .td file (e.g. 255).
5715 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
5716                                     int64_t DesiredMaskS) const {
5717   const APInt &ActualMask = RHS->getAPIntValue();
5718   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
5719
5720   // If the actual mask exactly matches, success!
5721   if (ActualMask == DesiredMask)
5722     return true;
5723
5724   // If the actual AND mask is allowing unallowed bits, this doesn't match.
5725   if (ActualMask.intersects(~DesiredMask))
5726     return false;
5727
5728   // Otherwise, the DAG Combiner may have proven that the value coming in is
5729   // either already zero or is not demanded.  Check for known zero input bits.
5730   APInt NeededMask = DesiredMask & ~ActualMask;
5731   if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
5732     return true;
5733
5734   // TODO: check to see if missing bits are just not demanded.
5735
5736   // Otherwise, this pattern doesn't match.
5737   return false;
5738 }
5739
5740 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
5741 /// the dag combiner simplified the 255, we still want to match.  RHS is the
5742 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
5743 /// specified in the .td file (e.g. 255).
5744 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
5745                                    int64_t DesiredMaskS) const {
5746   const APInt &ActualMask = RHS->getAPIntValue();
5747   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
5748
5749   // If the actual mask exactly matches, success!
5750   if (ActualMask == DesiredMask)
5751     return true;
5752
5753   // If the actual AND mask is allowing unallowed bits, this doesn't match.
5754   if (ActualMask.intersects(~DesiredMask))
5755     return false;
5756
5757   // Otherwise, the DAG Combiner may have proven that the value coming in is
5758   // either already zero or is not demanded.  Check for known zero input bits.
5759   APInt NeededMask = DesiredMask & ~ActualMask;
5760
5761   APInt KnownZero, KnownOne;
5762   CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
5763
5764   // If all the missing bits in the or are already known to be set, match!
5765   if ((NeededMask & KnownOne) == NeededMask)
5766     return true;
5767
5768   // TODO: check to see if missing bits are just not demanded.
5769
5770   // Otherwise, this pattern doesn't match.
5771   return false;
5772 }
5773
5774
5775 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
5776 /// by tblgen.  Others should not call it.
5777 void SelectionDAGISel::
5778 SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops, SelectionDAG &DAG) {
5779   std::vector<SDValue> InOps;
5780   std::swap(InOps, Ops);
5781
5782   Ops.push_back(InOps[0]);  // input chain.
5783   Ops.push_back(InOps[1]);  // input asm string.
5784
5785   unsigned i = 2, e = InOps.size();
5786   if (InOps[e-1].getValueType() == MVT::Flag)
5787     --e;  // Don't process a flag operand if it is here.
5788
5789   while (i != e) {
5790     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
5791     if ((Flags & 7) != 4 /*MEM*/) {
5792       // Just skip over this operand, copying the operands verbatim.
5793       Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
5794       i += (Flags >> 3) + 1;
5795     } else {
5796       assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
5797       // Otherwise, this is a memory operand.  Ask the target to select it.
5798       std::vector<SDValue> SelOps;
5799       if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
5800         cerr << "Could not match memory address.  Inline asm failure!\n";
5801         exit(1);
5802       }
5803
5804       // Add this to the output node.
5805       MVT IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
5806       Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
5807                                           IntPtrTy));
5808       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
5809       i += 2;
5810     }
5811   }
5812
5813   // Add the flag input back if present.
5814   if (e != InOps.size())
5815     Ops.push_back(InOps.back());
5816 }
5817
5818 char SelectionDAGISel::ID = 0;