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