Several changes:
[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()->getABITypeSize(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   std::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()->getABITypeSize(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   case Intrinsic::flt_rounds: {
2934     setValue(&I, DAG.getNode(ISD::FLT_ROUNDS, MVT::i32));
2935     return 0;
2936   }
2937   }
2938 }
2939
2940
2941 void SelectionDAGLowering::LowerCallTo(Instruction &I,
2942                                        const Type *CalledValueTy,
2943                                        unsigned CallingConv,
2944                                        bool IsTailCall,
2945                                        SDOperand Callee, unsigned OpIdx,
2946                                        MachineBasicBlock *LandingPad) {
2947   const PointerType *PT = cast<PointerType>(CalledValueTy);
2948   const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
2949   const ParamAttrsList *Attrs = FTy->getParamAttrs();
2950   MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2951   unsigned BeginLabel = 0, EndLabel = 0;
2952     
2953   TargetLowering::ArgListTy Args;
2954   TargetLowering::ArgListEntry Entry;
2955   Args.reserve(I.getNumOperands());
2956   for (unsigned i = OpIdx, e = I.getNumOperands(); i != e; ++i) {
2957     Value *Arg = I.getOperand(i);
2958     SDOperand ArgNode = getValue(Arg);
2959     Entry.Node = ArgNode; Entry.Ty = Arg->getType();
2960
2961     unsigned attrInd = i - OpIdx + 1;
2962     Entry.isSExt  = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::SExt);
2963     Entry.isZExt  = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::ZExt);
2964     Entry.isInReg = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::InReg);
2965     Entry.isSRet  = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::StructRet);
2966     Entry.isNest  = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::Nest);
2967     Entry.isByVal = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::ByVal);
2968     Args.push_back(Entry);
2969   }
2970
2971   if (ExceptionHandling && MMI && LandingPad) {
2972     // Insert a label before the invoke call to mark the try range.  This can be
2973     // used to detect deletion of the invoke via the MachineModuleInfo.
2974     BeginLabel = MMI->NextLabelID();
2975     DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2976                             DAG.getConstant(BeginLabel, MVT::i32)));
2977   }
2978   
2979   std::pair<SDOperand,SDOperand> Result =
2980     TLI.LowerCallTo(getRoot(), I.getType(), 
2981                     Attrs && Attrs->paramHasAttr(0, ParamAttr::SExt),
2982                     FTy->isVarArg(), CallingConv, IsTailCall, 
2983                     Callee, Args, DAG);
2984   if (I.getType() != Type::VoidTy)
2985     setValue(&I, Result.first);
2986   DAG.setRoot(Result.second);
2987
2988   if (ExceptionHandling && MMI && LandingPad) {
2989     // Insert a label at the end of the invoke call to mark the try range.  This
2990     // can be used to detect deletion of the invoke via the MachineModuleInfo.
2991     EndLabel = MMI->NextLabelID();
2992     DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2993                             DAG.getConstant(EndLabel, MVT::i32)));
2994
2995     // Inform MachineModuleInfo of range.    
2996     MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
2997   }
2998 }
2999
3000
3001 void SelectionDAGLowering::visitCall(CallInst &I) {
3002   const char *RenameFn = 0;
3003   if (Function *F = I.getCalledFunction()) {
3004     if (F->isDeclaration()) {
3005       if (unsigned IID = F->getIntrinsicID()) {
3006         RenameFn = visitIntrinsicCall(I, IID);
3007         if (!RenameFn)
3008           return;
3009       }
3010     }
3011
3012     // Check for well-known libc/libm calls.  If the function is internal, it
3013     // can't be a library call.
3014     unsigned NameLen = F->getNameLen();
3015     if (!F->hasInternalLinkage() && NameLen) {
3016       const char *NameStr = F->getNameStart();
3017       if (NameStr[0] == 'c' &&
3018           ((NameLen == 8 && !strcmp(NameStr, "copysign")) ||
3019            (NameLen == 9 && !strcmp(NameStr, "copysignf")))) {
3020         if (I.getNumOperands() == 3 &&   // Basic sanity checks.
3021             I.getOperand(1)->getType()->isFloatingPoint() &&
3022             I.getType() == I.getOperand(1)->getType() &&
3023             I.getType() == I.getOperand(2)->getType()) {
3024           SDOperand LHS = getValue(I.getOperand(1));
3025           SDOperand RHS = getValue(I.getOperand(2));
3026           setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
3027                                    LHS, RHS));
3028           return;
3029         }
3030       } else if (NameStr[0] == 'f' &&
3031                  ((NameLen == 4 && !strcmp(NameStr, "fabs")) ||
3032                   (NameLen == 5 && !strcmp(NameStr, "fabsf")) ||
3033                   (NameLen == 5 && !strcmp(NameStr, "fabsl")))) {
3034         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3035             I.getOperand(1)->getType()->isFloatingPoint() &&
3036             I.getType() == I.getOperand(1)->getType()) {
3037           SDOperand Tmp = getValue(I.getOperand(1));
3038           setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
3039           return;
3040         }
3041       } else if (NameStr[0] == 's' && 
3042                  ((NameLen == 3 && !strcmp(NameStr, "sin")) ||
3043                   (NameLen == 4 && !strcmp(NameStr, "sinf")) ||
3044                   (NameLen == 4 && !strcmp(NameStr, "sinl")))) {
3045         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3046             I.getOperand(1)->getType()->isFloatingPoint() &&
3047             I.getType() == I.getOperand(1)->getType()) {
3048           SDOperand Tmp = getValue(I.getOperand(1));
3049           setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
3050           return;
3051         }
3052       } else if (NameStr[0] == 'c' &&
3053                  ((NameLen == 3 && !strcmp(NameStr, "cos")) ||
3054                   (NameLen == 4 && !strcmp(NameStr, "cosf")) ||
3055                   (NameLen == 4 && !strcmp(NameStr, "cosl")))) {
3056         if (I.getNumOperands() == 2 &&   // Basic sanity checks.
3057             I.getOperand(1)->getType()->isFloatingPoint() &&
3058             I.getType() == I.getOperand(1)->getType()) {
3059           SDOperand Tmp = getValue(I.getOperand(1));
3060           setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
3061           return;
3062         }
3063       }
3064     }
3065   } else if (isa<InlineAsm>(I.getOperand(0))) {
3066     visitInlineAsm(I);
3067     return;
3068   }
3069
3070   SDOperand Callee;
3071   if (!RenameFn)
3072     Callee = getValue(I.getOperand(0));
3073   else
3074     Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
3075
3076   LowerCallTo(I, I.getCalledValue()->getType(),
3077               I.getCallingConv(),
3078               I.isTailCall(),
3079               Callee,
3080               1);
3081 }
3082
3083
3084 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
3085 /// this value and returns the result as a ValueVT value.  This uses 
3086 /// Chain/Flag as the input and updates them for the output Chain/Flag.
3087 /// If the Flag pointer is NULL, no flag is used.
3088 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
3089                                         SDOperand &Chain, SDOperand *Flag)const{
3090   // Copy the legal parts from the registers.
3091   unsigned NumParts = Regs.size();
3092   SmallVector<SDOperand, 8> Parts(NumParts);
3093   for (unsigned i = 0; i != NumParts; ++i) {
3094     SDOperand Part = Flag ?
3095                      DAG.getCopyFromReg(Chain, Regs[i], RegVT, *Flag) :
3096                      DAG.getCopyFromReg(Chain, Regs[i], RegVT);
3097     Chain = Part.getValue(1);
3098     if (Flag)
3099       *Flag = Part.getValue(2);
3100     Parts[i] = Part;
3101   }
3102   
3103   // Assemble the legal parts into the final value.
3104   return getCopyFromParts(DAG, &Parts[0], NumParts, RegVT, ValueVT);
3105 }
3106
3107 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
3108 /// specified value into the registers specified by this object.  This uses 
3109 /// Chain/Flag as the input and updates them for the output Chain/Flag.
3110 /// If the Flag pointer is NULL, no flag is used.
3111 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
3112                                  SDOperand &Chain, SDOperand *Flag) const {
3113   // Get the list of the values's legal parts.
3114   unsigned NumParts = Regs.size();
3115   SmallVector<SDOperand, 8> Parts(NumParts);
3116   getCopyToParts(DAG, Val, &Parts[0], NumParts, RegVT);
3117
3118   // Copy the parts into the registers.
3119   for (unsigned i = 0; i != NumParts; ++i) {
3120     SDOperand Part = Flag ?
3121                      DAG.getCopyToReg(Chain, Regs[i], Parts[i], *Flag) :
3122                      DAG.getCopyToReg(Chain, Regs[i], Parts[i]);
3123     Chain = Part.getValue(0);
3124     if (Flag)
3125       *Flag = Part.getValue(1);
3126   }
3127 }
3128
3129 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
3130 /// operand list.  This adds the code marker and includes the number of 
3131 /// values added into it.
3132 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
3133                                         std::vector<SDOperand> &Ops) const {
3134   MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
3135   Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
3136   for (unsigned i = 0, e = Regs.size(); i != e; ++i)
3137     Ops.push_back(DAG.getRegister(Regs[i], RegVT));
3138 }
3139
3140 /// isAllocatableRegister - If the specified register is safe to allocate, 
3141 /// i.e. it isn't a stack pointer or some other special register, return the
3142 /// register class for the register.  Otherwise, return null.
3143 static const TargetRegisterClass *
3144 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
3145                       const TargetLowering &TLI, const MRegisterInfo *MRI) {
3146   MVT::ValueType FoundVT = MVT::Other;
3147   const TargetRegisterClass *FoundRC = 0;
3148   for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
3149        E = MRI->regclass_end(); RCI != E; ++RCI) {
3150     MVT::ValueType ThisVT = MVT::Other;
3151
3152     const TargetRegisterClass *RC = *RCI;
3153     // If none of the the value types for this register class are valid, we 
3154     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
3155     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
3156          I != E; ++I) {
3157       if (TLI.isTypeLegal(*I)) {
3158         // If we have already found this register in a different register class,
3159         // choose the one with the largest VT specified.  For example, on
3160         // PowerPC, we favor f64 register classes over f32.
3161         if (FoundVT == MVT::Other || 
3162             MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
3163           ThisVT = *I;
3164           break;
3165         }
3166       }
3167     }
3168     
3169     if (ThisVT == MVT::Other) continue;
3170     
3171     // NOTE: This isn't ideal.  In particular, this might allocate the
3172     // frame pointer in functions that need it (due to them not being taken
3173     // out of allocation, because a variable sized allocation hasn't been seen
3174     // yet).  This is a slight code pessimization, but should still work.
3175     for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
3176          E = RC->allocation_order_end(MF); I != E; ++I)
3177       if (*I == Reg) {
3178         // We found a matching register class.  Keep looking at others in case
3179         // we find one with larger registers that this physreg is also in.
3180         FoundRC = RC;
3181         FoundVT = ThisVT;
3182         break;
3183       }
3184   }
3185   return FoundRC;
3186 }    
3187
3188
3189 namespace {
3190 /// AsmOperandInfo - This contains information for each constraint that we are
3191 /// lowering.
3192 struct AsmOperandInfo : public InlineAsm::ConstraintInfo {
3193   /// ConstraintCode - This contains the actual string for the code, like "m".
3194   std::string ConstraintCode;
3195
3196   /// ConstraintType - Information about the constraint code, e.g. Register,
3197   /// RegisterClass, Memory, Other, Unknown.
3198   TargetLowering::ConstraintType ConstraintType;
3199   
3200   /// CallOperand/CallOperandval - If this is the result output operand or a
3201   /// clobber, this is null, otherwise it is the incoming operand to the
3202   /// CallInst.  This gets modified as the asm is processed.
3203   SDOperand CallOperand;
3204   Value *CallOperandVal;
3205   
3206   /// ConstraintVT - The ValueType for the operand value.
3207   MVT::ValueType ConstraintVT;
3208   
3209   /// AssignedRegs - If this is a register or register class operand, this
3210   /// contains the set of register corresponding to the operand.
3211   RegsForValue AssignedRegs;
3212   
3213   AsmOperandInfo(const InlineAsm::ConstraintInfo &info)
3214     : InlineAsm::ConstraintInfo(info), 
3215       ConstraintType(TargetLowering::C_Unknown),
3216       CallOperand(0,0), CallOperandVal(0), ConstraintVT(MVT::Other) {
3217   }
3218   
3219   void ComputeConstraintToUse(const TargetLowering &TLI);
3220   
3221   /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers
3222   /// busy in OutputRegs/InputRegs.
3223   void MarkAllocatedRegs(bool isOutReg, bool isInReg,
3224                          std::set<unsigned> &OutputRegs, 
3225                          std::set<unsigned> &InputRegs) const {
3226      if (isOutReg)
3227        OutputRegs.insert(AssignedRegs.Regs.begin(), AssignedRegs.Regs.end());
3228      if (isInReg)
3229        InputRegs.insert(AssignedRegs.Regs.begin(), AssignedRegs.Regs.end());
3230    }
3231 };
3232 } // end anon namespace.
3233
3234 /// getConstraintGenerality - Return an integer indicating how general CT is.
3235 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
3236   switch (CT) {
3237     default: assert(0 && "Unknown constraint type!");
3238     case TargetLowering::C_Other:
3239     case TargetLowering::C_Unknown:
3240       return 0;
3241     case TargetLowering::C_Register:
3242       return 1;
3243     case TargetLowering::C_RegisterClass:
3244       return 2;
3245     case TargetLowering::C_Memory:
3246       return 3;
3247   }
3248 }
3249
3250 void AsmOperandInfo::ComputeConstraintToUse(const TargetLowering &TLI) {
3251   assert(!Codes.empty() && "Must have at least one constraint");
3252   
3253   std::string *Current = &Codes[0];
3254   TargetLowering::ConstraintType CurType = TLI.getConstraintType(*Current);
3255   if (Codes.size() == 1) {   // Single-letter constraints ('r') are very common.
3256     ConstraintCode = *Current;
3257     ConstraintType = CurType;
3258     return;
3259   }
3260   
3261   unsigned CurGenerality = getConstraintGenerality(CurType);
3262   
3263   // If we have multiple constraints, try to pick the most general one ahead
3264   // of time.  This isn't a wonderful solution, but handles common cases.
3265   for (unsigned j = 1, e = Codes.size(); j != e; ++j) {
3266     TargetLowering::ConstraintType ThisType = TLI.getConstraintType(Codes[j]);
3267     unsigned ThisGenerality = getConstraintGenerality(ThisType);
3268     if (ThisGenerality > CurGenerality) {
3269       // This constraint letter is more general than the previous one,
3270       // use it.
3271       CurType = ThisType;
3272       Current = &Codes[j];
3273       CurGenerality = ThisGenerality;
3274     }
3275   }
3276   
3277   ConstraintCode = *Current;
3278   ConstraintType = CurType;
3279 }
3280
3281
3282 void SelectionDAGLowering::
3283 GetRegistersForValue(AsmOperandInfo &OpInfo, bool HasEarlyClobber,
3284                      std::set<unsigned> &OutputRegs, 
3285                      std::set<unsigned> &InputRegs) {
3286   // Compute whether this value requires an input register, an output register,
3287   // or both.
3288   bool isOutReg = false;
3289   bool isInReg = false;
3290   switch (OpInfo.Type) {
3291   case InlineAsm::isOutput:
3292     isOutReg = true;
3293     
3294     // If this is an early-clobber output, or if there is an input
3295     // constraint that matches this, we need to reserve the input register
3296     // so no other inputs allocate to it.
3297     isInReg = OpInfo.isEarlyClobber || OpInfo.hasMatchingInput;
3298     break;
3299   case InlineAsm::isInput:
3300     isInReg = true;
3301     isOutReg = false;
3302     break;
3303   case InlineAsm::isClobber:
3304     isOutReg = true;
3305     isInReg = true;
3306     break;
3307   }
3308   
3309   
3310   MachineFunction &MF = DAG.getMachineFunction();
3311   std::vector<unsigned> Regs;
3312   
3313   // If this is a constraint for a single physreg, or a constraint for a
3314   // register class, find it.
3315   std::pair<unsigned, const TargetRegisterClass*> PhysReg = 
3316     TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode,
3317                                      OpInfo.ConstraintVT);
3318
3319   unsigned NumRegs = 1;
3320   if (OpInfo.ConstraintVT != MVT::Other)
3321     NumRegs = TLI.getNumRegisters(OpInfo.ConstraintVT);
3322   MVT::ValueType RegVT;
3323   MVT::ValueType ValueVT = OpInfo.ConstraintVT;
3324   
3325
3326   // If this is a constraint for a specific physical register, like {r17},
3327   // assign it now.
3328   if (PhysReg.first) {
3329     if (OpInfo.ConstraintVT == MVT::Other)
3330       ValueVT = *PhysReg.second->vt_begin();
3331     
3332     // Get the actual register value type.  This is important, because the user
3333     // may have asked for (e.g.) the AX register in i32 type.  We need to
3334     // remember that AX is actually i16 to get the right extension.
3335     RegVT = *PhysReg.second->vt_begin();
3336     
3337     // This is a explicit reference to a physical register.
3338     Regs.push_back(PhysReg.first);
3339
3340     // If this is an expanded reference, add the rest of the regs to Regs.
3341     if (NumRegs != 1) {
3342       TargetRegisterClass::iterator I = PhysReg.second->begin();
3343       TargetRegisterClass::iterator E = PhysReg.second->end();
3344       for (; *I != PhysReg.first; ++I)
3345         assert(I != E && "Didn't find reg!"); 
3346       
3347       // Already added the first reg.
3348       --NumRegs; ++I;
3349       for (; NumRegs; --NumRegs, ++I) {
3350         assert(I != E && "Ran out of registers to allocate!");
3351         Regs.push_back(*I);
3352       }
3353     }
3354     OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT);
3355     OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
3356     return;
3357   }
3358   
3359   // Otherwise, if this was a reference to an LLVM register class, create vregs
3360   // for this reference.
3361   std::vector<unsigned> RegClassRegs;
3362   const TargetRegisterClass *RC = PhysReg.second;
3363   if (RC) {
3364     // If this is an early clobber or tied register, our regalloc doesn't know
3365     // how to maintain the constraint.  If it isn't, go ahead and create vreg
3366     // and let the regalloc do the right thing.
3367     if (!OpInfo.hasMatchingInput && !OpInfo.isEarlyClobber &&
3368         // If there is some other early clobber and this is an input register,
3369         // then we are forced to pre-allocate the input reg so it doesn't
3370         // conflict with the earlyclobber.
3371         !(OpInfo.Type == InlineAsm::isInput && HasEarlyClobber)) {
3372       RegVT = *PhysReg.second->vt_begin();
3373       
3374       if (OpInfo.ConstraintVT == MVT::Other)
3375         ValueVT = RegVT;
3376
3377       // Create the appropriate number of virtual registers.
3378       SSARegMap *RegMap = MF.getSSARegMap();
3379       for (; NumRegs; --NumRegs)
3380         Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
3381       
3382       OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT);
3383       OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
3384       return;
3385     }
3386     
3387     // Otherwise, we can't allocate it.  Let the code below figure out how to
3388     // maintain these constraints.
3389     RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
3390     
3391   } else {
3392     // This is a reference to a register class that doesn't directly correspond
3393     // to an LLVM register class.  Allocate NumRegs consecutive, available,
3394     // registers from the class.
3395     RegClassRegs = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode,
3396                                                          OpInfo.ConstraintVT);
3397   }
3398   
3399   const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
3400   unsigned NumAllocated = 0;
3401   for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
3402     unsigned Reg = RegClassRegs[i];
3403     // See if this register is available.
3404     if ((isOutReg && OutputRegs.count(Reg)) ||   // Already used.
3405         (isInReg  && InputRegs.count(Reg))) {    // Already used.
3406       // Make sure we find consecutive registers.
3407       NumAllocated = 0;
3408       continue;
3409     }
3410     
3411     // Check to see if this register is allocatable (i.e. don't give out the
3412     // stack pointer).
3413     if (RC == 0) {
3414       RC = isAllocatableRegister(Reg, MF, TLI, MRI);
3415       if (!RC) {        // Couldn't allocate this register.
3416         // Reset NumAllocated to make sure we return consecutive registers.
3417         NumAllocated = 0;
3418         continue;
3419       }
3420     }
3421     
3422     // Okay, this register is good, we can use it.
3423     ++NumAllocated;
3424
3425     // If we allocated enough consecutive registers, succeed.
3426     if (NumAllocated == NumRegs) {
3427       unsigned RegStart = (i-NumAllocated)+1;
3428       unsigned RegEnd   = i+1;
3429       // Mark all of the allocated registers used.
3430       for (unsigned i = RegStart; i != RegEnd; ++i)
3431         Regs.push_back(RegClassRegs[i]);
3432       
3433       OpInfo.AssignedRegs = RegsForValue(Regs, *RC->vt_begin(), 
3434                                          OpInfo.ConstraintVT);
3435       OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
3436       return;
3437     }
3438   }
3439   
3440   // Otherwise, we couldn't allocate enough registers for this.
3441   return;
3442 }
3443
3444
3445 /// visitInlineAsm - Handle a call to an InlineAsm object.
3446 ///
3447 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
3448   InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
3449
3450   /// ConstraintOperands - Information about all of the constraints.
3451   std::vector<AsmOperandInfo> ConstraintOperands;
3452   
3453   SDOperand Chain = getRoot();
3454   SDOperand Flag;
3455   
3456   std::set<unsigned> OutputRegs, InputRegs;
3457
3458   // Do a prepass over the constraints, canonicalizing them, and building up the
3459   // ConstraintOperands list.
3460   std::vector<InlineAsm::ConstraintInfo>
3461     ConstraintInfos = IA->ParseConstraints();
3462
3463   // SawEarlyClobber - Keep track of whether we saw an earlyclobber output
3464   // constraint.  If so, we can't let the register allocator allocate any input
3465   // registers, because it will not know to avoid the earlyclobbered output reg.
3466   bool SawEarlyClobber = false;
3467   
3468   unsigned OpNo = 1;   // OpNo - The operand of the CallInst.
3469   for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) {
3470     ConstraintOperands.push_back(AsmOperandInfo(ConstraintInfos[i]));
3471     AsmOperandInfo &OpInfo = ConstraintOperands.back();
3472     
3473     MVT::ValueType OpVT = MVT::Other;
3474
3475     // Compute the value type for each operand.
3476     switch (OpInfo.Type) {
3477     case InlineAsm::isOutput:
3478       if (!OpInfo.isIndirect) {
3479         // The return value of the call is this value.  As such, there is no
3480         // corresponding argument.
3481         assert(I.getType() != Type::VoidTy && "Bad inline asm!");
3482         OpVT = TLI.getValueType(I.getType());
3483       } else {
3484         OpInfo.CallOperandVal = I.getOperand(OpNo++);
3485       }
3486       break;
3487     case InlineAsm::isInput:
3488       OpInfo.CallOperandVal = I.getOperand(OpNo++);
3489       break;
3490     case InlineAsm::isClobber:
3491       // Nothing to do.
3492       break;
3493     }
3494
3495     // If this is an input or an indirect output, process the call argument.
3496     // BasicBlocks are labels, currently appearing only in asm's.
3497     if (OpInfo.CallOperandVal) {
3498       if (isa<BasicBlock>(OpInfo.CallOperandVal))
3499         OpInfo.CallOperand = 
3500           DAG.getBasicBlock(FuncInfo.MBBMap[cast<BasicBlock>(OpInfo.CallOperandVal)]);
3501       else {
3502         OpInfo.CallOperand = getValue(OpInfo.CallOperandVal);
3503         const Type *OpTy = OpInfo.CallOperandVal->getType();
3504         // If this is an indirect operand, the operand is a pointer to the
3505         // accessed type.
3506         if (OpInfo.isIndirect)
3507           OpTy = cast<PointerType>(OpTy)->getElementType();
3508
3509         // If OpTy is not a first-class value, it may be a struct/union that we
3510         // can tile with integers.
3511         if (!OpTy->isFirstClassType() && OpTy->isSized()) {
3512           unsigned BitSize = TD->getTypeSizeInBits(OpTy);
3513           switch (BitSize) {
3514           default: break;
3515           case 1:
3516           case 8:
3517           case 16:
3518           case 32:
3519           case 64:
3520             OpTy = IntegerType::get(BitSize);
3521             break;
3522           }
3523         }
3524
3525         OpVT = TLI.getValueType(OpTy, true);
3526       }
3527     }
3528     
3529     OpInfo.ConstraintVT = OpVT;
3530     
3531     // Compute the constraint code and ConstraintType to use.
3532     OpInfo.ComputeConstraintToUse(TLI);
3533
3534     // Keep track of whether we see an earlyclobber.
3535     SawEarlyClobber |= OpInfo.isEarlyClobber;
3536     
3537     // If this is a memory input, and if the operand is not indirect, do what we
3538     // need to to provide an address for the memory input.
3539     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
3540         !OpInfo.isIndirect) {
3541       assert(OpInfo.Type == InlineAsm::isInput &&
3542              "Can only indirectify direct input operands!");
3543       
3544       // Memory operands really want the address of the value.  If we don't have
3545       // an indirect input, put it in the constpool if we can, otherwise spill
3546       // it to a stack slot.
3547       
3548       // If the operand is a float, integer, or vector constant, spill to a
3549       // constant pool entry to get its address.
3550       Value *OpVal = OpInfo.CallOperandVal;
3551       if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) ||
3552           isa<ConstantVector>(OpVal)) {
3553         OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal),
3554                                                  TLI.getPointerTy());
3555       } else {
3556         // Otherwise, create a stack slot and emit a store to it before the
3557         // asm.
3558         const Type *Ty = OpVal->getType();
3559         uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
3560         unsigned Align  = TLI.getTargetData()->getPrefTypeAlignment(Ty);
3561         MachineFunction &MF = DAG.getMachineFunction();
3562         int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align);
3563         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
3564         Chain = DAG.getStore(Chain, OpInfo.CallOperand, StackSlot, NULL, 0);
3565         OpInfo.CallOperand = StackSlot;
3566       }
3567      
3568       // There is no longer a Value* corresponding to this operand.
3569       OpInfo.CallOperandVal = 0;
3570       // It is now an indirect operand.
3571       OpInfo.isIndirect = true;
3572     }
3573     
3574     // If this constraint is for a specific register, allocate it before
3575     // anything else.
3576     if (OpInfo.ConstraintType == TargetLowering::C_Register)
3577       GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
3578   }
3579   ConstraintInfos.clear();
3580   
3581   
3582   // Second pass - Loop over all of the operands, assigning virtual or physregs
3583   // to registerclass operands.
3584   for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
3585     AsmOperandInfo &OpInfo = ConstraintOperands[i];
3586     
3587     // C_Register operands have already been allocated, Other/Memory don't need
3588     // to be.
3589     if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass)
3590       GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
3591   }    
3592   
3593   // AsmNodeOperands - The operands for the ISD::INLINEASM node.
3594   std::vector<SDOperand> AsmNodeOperands;
3595   AsmNodeOperands.push_back(SDOperand());  // reserve space for input chain
3596   AsmNodeOperands.push_back(
3597           DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other));
3598   
3599   
3600   // Loop over all of the inputs, copying the operand values into the
3601   // appropriate registers and processing the output regs.
3602   RegsForValue RetValRegs;
3603   
3604   // IndirectStoresToEmit - The set of stores to emit after the inline asm node.
3605   std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
3606   
3607   for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
3608     AsmOperandInfo &OpInfo = ConstraintOperands[i];
3609
3610     switch (OpInfo.Type) {
3611     case InlineAsm::isOutput: {
3612       if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass &&
3613           OpInfo.ConstraintType != TargetLowering::C_Register) {
3614         // Memory output, or 'other' output (e.g. 'X' constraint).
3615         assert(OpInfo.isIndirect && "Memory output must be indirect operand");
3616
3617         // Add information to the INLINEASM node to know about this output.
3618         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3619         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 
3620                                                         TLI.getPointerTy()));
3621         AsmNodeOperands.push_back(OpInfo.CallOperand);
3622         break;
3623       }
3624
3625       // Otherwise, this is a register or register class output.
3626
3627       // Copy the output from the appropriate register.  Find a register that
3628       // we can use.
3629       if (OpInfo.AssignedRegs.Regs.empty()) {
3630         cerr << "Couldn't allocate output reg for contraint '"
3631              << OpInfo.ConstraintCode << "'!\n";
3632         exit(1);
3633       }
3634
3635       if (!OpInfo.isIndirect) {
3636         // This is the result value of the call.
3637         assert(RetValRegs.Regs.empty() &&
3638                "Cannot have multiple output constraints yet!");
3639         assert(I.getType() != Type::VoidTy && "Bad inline asm!");
3640         RetValRegs = OpInfo.AssignedRegs;
3641       } else {
3642         IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs,
3643                                                       OpInfo.CallOperandVal));
3644       }
3645       
3646       // Add information to the INLINEASM node to know that this register is
3647       // set.
3648       OpInfo.AssignedRegs.AddInlineAsmOperands(2 /*REGDEF*/, DAG,
3649                                                AsmNodeOperands);
3650       break;
3651     }
3652     case InlineAsm::isInput: {
3653       SDOperand InOperandVal = OpInfo.CallOperand;
3654       
3655       if (isdigit(OpInfo.ConstraintCode[0])) {    // Matching constraint?
3656         // If this is required to match an output register we have already set,
3657         // just use its register.
3658         unsigned OperandNo = atoi(OpInfo.ConstraintCode.c_str());
3659         
3660         // Scan until we find the definition we already emitted of this operand.
3661         // When we find it, create a RegsForValue operand.
3662         unsigned CurOp = 2;  // The first operand.
3663         for (; OperandNo; --OperandNo) {
3664           // Advance to the next operand.
3665           unsigned NumOps = 
3666             cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3667           assert(((NumOps & 7) == 2 /*REGDEF*/ ||
3668                   (NumOps & 7) == 4 /*MEM*/) &&
3669                  "Skipped past definitions?");
3670           CurOp += (NumOps>>3)+1;
3671         }
3672
3673         unsigned NumOps = 
3674           cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3675         if ((NumOps & 7) == 2 /*REGDEF*/) {
3676           // Add NumOps>>3 registers to MatchedRegs.
3677           RegsForValue MatchedRegs;
3678           MatchedRegs.ValueVT = InOperandVal.getValueType();
3679           MatchedRegs.RegVT   = AsmNodeOperands[CurOp+1].getValueType();
3680           for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
3681             unsigned Reg =
3682               cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
3683             MatchedRegs.Regs.push_back(Reg);
3684           }
3685         
3686           // Use the produced MatchedRegs object to 
3687           MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag);
3688           MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
3689           break;
3690         } else {
3691           assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
3692           assert(0 && "matching constraints for memory operands unimp");
3693         }
3694       }
3695       
3696       if (OpInfo.ConstraintType == TargetLowering::C_Other) {
3697         assert(!OpInfo.isIndirect && 
3698                "Don't know how to handle indirect other inputs yet!");
3699         
3700         std::vector<SDOperand> Ops;
3701         TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0],
3702                                          Ops, DAG);
3703         if (Ops.empty()) {
3704           cerr << "Invalid operand for inline asm constraint '"
3705                << OpInfo.ConstraintCode << "'!\n";
3706           exit(1);
3707         }
3708         
3709         // Add information to the INLINEASM node to know about this input.
3710         unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3);
3711         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 
3712                                                         TLI.getPointerTy()));
3713         AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end());
3714         break;
3715       } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) {
3716         assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!");
3717         assert(InOperandVal.getValueType() == TLI.getPointerTy() &&
3718                "Memory operands expect pointer values");
3719                
3720         // Add information to the INLINEASM node to know about this input.
3721         unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3722         AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
3723                                                         TLI.getPointerTy()));
3724         AsmNodeOperands.push_back(InOperandVal);
3725         break;
3726       }
3727         
3728       assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass ||
3729               OpInfo.ConstraintType == TargetLowering::C_Register) &&
3730              "Unknown constraint type!");
3731       assert(!OpInfo.isIndirect && 
3732              "Don't know how to handle indirect register inputs yet!");
3733
3734       // Copy the input into the appropriate registers.
3735       assert(!OpInfo.AssignedRegs.Regs.empty() &&
3736              "Couldn't allocate input reg!");
3737
3738       OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag);
3739       
3740       OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG,
3741                                                AsmNodeOperands);
3742       break;
3743     }
3744     case InlineAsm::isClobber: {
3745       // Add the clobbered value to the operand list, so that the register
3746       // allocator is aware that the physreg got clobbered.
3747       if (!OpInfo.AssignedRegs.Regs.empty())
3748         OpInfo.AssignedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG,
3749                                                  AsmNodeOperands);
3750       break;
3751     }
3752     }
3753   }
3754   
3755   // Finish up input operands.
3756   AsmNodeOperands[0] = Chain;
3757   if (Flag.Val) AsmNodeOperands.push_back(Flag);
3758   
3759   Chain = DAG.getNode(ISD::INLINEASM, 
3760                       DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
3761                       &AsmNodeOperands[0], AsmNodeOperands.size());
3762   Flag = Chain.getValue(1);
3763
3764   // If this asm returns a register value, copy the result from that register
3765   // and set it as the value of the call.
3766   if (!RetValRegs.Regs.empty()) {
3767     SDOperand Val = RetValRegs.getCopyFromRegs(DAG, Chain, &Flag);
3768     
3769     // If the result of the inline asm is a vector, it may have the wrong
3770     // width/num elts.  Make sure to convert it to the right type with
3771     // bit_convert.
3772     if (MVT::isVector(Val.getValueType())) {
3773       const VectorType *VTy = cast<VectorType>(I.getType());
3774       MVT::ValueType DesiredVT = TLI.getValueType(VTy);
3775       
3776       Val = DAG.getNode(ISD::BIT_CONVERT, DesiredVT, Val);
3777     }
3778     
3779     setValue(&I, Val);
3780   }
3781   
3782   std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
3783   
3784   // Process indirect outputs, first output all of the flagged copies out of
3785   // physregs.
3786   for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
3787     RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
3788     Value *Ptr = IndirectStoresToEmit[i].second;
3789     SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, &Flag);
3790     StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
3791   }
3792   
3793   // Emit the non-flagged stores from the physregs.
3794   SmallVector<SDOperand, 8> OutChains;
3795   for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
3796     OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
3797                                     getValue(StoresToEmit[i].second),
3798                                     StoresToEmit[i].second, 0));
3799   if (!OutChains.empty())
3800     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3801                         &OutChains[0], OutChains.size());
3802   DAG.setRoot(Chain);
3803 }
3804
3805
3806 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
3807   SDOperand Src = getValue(I.getOperand(0));
3808
3809   MVT::ValueType IntPtr = TLI.getPointerTy();
3810
3811   if (IntPtr < Src.getValueType())
3812     Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
3813   else if (IntPtr > Src.getValueType())
3814     Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
3815
3816   // Scale the source by the type size.
3817   uint64_t ElementSize = TD->getABITypeSize(I.getType()->getElementType());
3818   Src = DAG.getNode(ISD::MUL, Src.getValueType(),
3819                     Src, getIntPtrConstant(ElementSize));
3820
3821   TargetLowering::ArgListTy Args;
3822   TargetLowering::ArgListEntry Entry;
3823   Entry.Node = Src;
3824   Entry.Ty = TLI.getTargetData()->getIntPtrType();
3825   Args.push_back(Entry);
3826
3827   std::pair<SDOperand,SDOperand> Result =
3828     TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3829                     DAG.getExternalSymbol("malloc", IntPtr),
3830                     Args, DAG);
3831   setValue(&I, Result.first);  // Pointers always fit in registers
3832   DAG.setRoot(Result.second);
3833 }
3834
3835 void SelectionDAGLowering::visitFree(FreeInst &I) {
3836   TargetLowering::ArgListTy Args;
3837   TargetLowering::ArgListEntry Entry;
3838   Entry.Node = getValue(I.getOperand(0));
3839   Entry.Ty = TLI.getTargetData()->getIntPtrType();
3840   Args.push_back(Entry);
3841   MVT::ValueType IntPtr = TLI.getPointerTy();
3842   std::pair<SDOperand,SDOperand> Result =
3843     TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3844                     DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3845   DAG.setRoot(Result.second);
3846 }
3847
3848 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3849 // mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
3850 // instructions are special in various ways, which require special support to
3851 // insert.  The specified MachineInstr is created but not inserted into any
3852 // basic blocks, and the scheduler passes ownership of it to this method.
3853 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3854                                                        MachineBasicBlock *MBB) {
3855   cerr << "If a target marks an instruction with "
3856        << "'usesCustomDAGSchedInserter', it must implement "
3857        << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3858   abort();
3859   return 0;  
3860 }
3861
3862 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3863   DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 
3864                           getValue(I.getOperand(1)), 
3865                           DAG.getSrcValue(I.getOperand(1))));
3866 }
3867
3868 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3869   SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3870                              getValue(I.getOperand(0)),
3871                              DAG.getSrcValue(I.getOperand(0)));
3872   setValue(&I, V);
3873   DAG.setRoot(V.getValue(1));
3874 }
3875
3876 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3877   DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3878                           getValue(I.getOperand(1)), 
3879                           DAG.getSrcValue(I.getOperand(1))));
3880 }
3881
3882 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3883   DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 
3884                           getValue(I.getOperand(1)), 
3885                           getValue(I.getOperand(2)),
3886                           DAG.getSrcValue(I.getOperand(1)),
3887                           DAG.getSrcValue(I.getOperand(2))));
3888 }
3889
3890 /// TargetLowering::LowerArguments - This is the default LowerArguments
3891 /// implementation, which just inserts a FORMAL_ARGUMENTS node.  FIXME: When all
3892 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be 
3893 /// integrated into SDISel.
3894 std::vector<SDOperand> 
3895 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3896   const FunctionType *FTy = F.getFunctionType();
3897   const ParamAttrsList *Attrs = FTy->getParamAttrs();
3898   // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3899   std::vector<SDOperand> Ops;
3900   Ops.push_back(DAG.getRoot());
3901   Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3902   Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3903
3904   // Add one result value for each formal argument.
3905   std::vector<MVT::ValueType> RetVals;
3906   unsigned j = 1;
3907   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3908        I != E; ++I, ++j) {
3909     MVT::ValueType VT = getValueType(I->getType());
3910     unsigned Flags = ISD::ParamFlags::NoFlagSet;
3911     unsigned OriginalAlignment =
3912       getTargetData()->getABITypeAlignment(I->getType());
3913
3914     // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3915     // that is zero extended!
3916     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::ZExt))
3917       Flags &= ~(ISD::ParamFlags::SExt);
3918     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::SExt))
3919       Flags |= ISD::ParamFlags::SExt;
3920     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::InReg))
3921       Flags |= ISD::ParamFlags::InReg;
3922     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::StructRet))
3923       Flags |= ISD::ParamFlags::StructReturn;
3924     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::ByVal)) {
3925       Flags |= ISD::ParamFlags::ByVal;
3926       const PointerType *Ty = cast<PointerType>(I->getType());
3927       const StructType *STy = cast<StructType>(Ty->getElementType());
3928       unsigned StructAlign =
3929           Log2_32(getTargetData()->getCallFrameTypeAlignment(STy));
3930       unsigned StructSize  = getTargetData()->getABITypeSize(STy);
3931       Flags |= (StructAlign << ISD::ParamFlags::ByValAlignOffs);
3932       Flags |= (StructSize  << ISD::ParamFlags::ByValSizeOffs);
3933     }
3934     if (Attrs && Attrs->paramHasAttr(j, ParamAttr::Nest))
3935       Flags |= ISD::ParamFlags::Nest;
3936     Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3937     
3938     switch (getTypeAction(VT)) {
3939     default: assert(0 && "Unknown type action!");
3940     case Legal: 
3941       RetVals.push_back(VT);
3942       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3943       break;
3944     case Promote:
3945       RetVals.push_back(getTypeToTransformTo(VT));
3946       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3947       break;
3948     case Expand: {
3949       // If this is an illegal type, it needs to be broken up to fit into 
3950       // registers.
3951       MVT::ValueType RegisterVT = getRegisterType(VT);
3952       unsigned NumRegs = getNumRegisters(VT);
3953       for (unsigned i = 0; i != NumRegs; ++i) {
3954         RetVals.push_back(RegisterVT);
3955         // if it isn't first piece, alignment must be 1
3956         if (i > 0)
3957           Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3958             (1 << ISD::ParamFlags::OrigAlignmentOffs);
3959         Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3960       }
3961       break;
3962     }
3963     }
3964   }
3965
3966   RetVals.push_back(MVT::Other);
3967   
3968   // Create the node.
3969   SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3970                                DAG.getNodeValueTypes(RetVals), RetVals.size(),
3971                                &Ops[0], Ops.size()).Val;
3972   unsigned NumArgRegs = Result->getNumValues() - 1;
3973   DAG.setRoot(SDOperand(Result, NumArgRegs));
3974
3975   // Set up the return result vector.
3976   Ops.clear();
3977   unsigned i = 0;
3978   unsigned Idx = 1;
3979   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; 
3980       ++I, ++Idx) {
3981     MVT::ValueType VT = getValueType(I->getType());
3982     
3983     switch (getTypeAction(VT)) {
3984     default: assert(0 && "Unknown type action!");
3985     case Legal: 
3986       Ops.push_back(SDOperand(Result, i++));
3987       break;
3988     case Promote: {
3989       SDOperand Op(Result, i++);
3990       if (MVT::isInteger(VT)) {
3991         if (Attrs && Attrs->paramHasAttr(Idx, ParamAttr::SExt))
3992           Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3993                            DAG.getValueType(VT));
3994         else if (Attrs && Attrs->paramHasAttr(Idx, ParamAttr::ZExt))
3995           Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3996                            DAG.getValueType(VT));
3997         Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3998       } else {
3999         assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
4000         Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
4001       }
4002       Ops.push_back(Op);
4003       break;
4004     }
4005     case Expand: {
4006       MVT::ValueType PartVT = getRegisterType(VT);
4007       unsigned NumParts = getNumRegisters(VT);
4008       SmallVector<SDOperand, 4> Parts(NumParts);
4009       for (unsigned j = 0; j != NumParts; ++j)
4010         Parts[j] = SDOperand(Result, i++);
4011       Ops.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT));
4012       break;
4013     }
4014     }
4015   }
4016   assert(i == NumArgRegs && "Argument register count mismatch!");
4017   return Ops;
4018 }
4019
4020
4021 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
4022 /// implementation, which just inserts an ISD::CALL node, which is later custom
4023 /// lowered by the target to something concrete.  FIXME: When all targets are
4024 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
4025 std::pair<SDOperand, SDOperand>
4026 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, 
4027                             bool RetTyIsSigned, bool isVarArg,
4028                             unsigned CallingConv, bool isTailCall, 
4029                             SDOperand Callee,
4030                             ArgListTy &Args, SelectionDAG &DAG) {
4031   SmallVector<SDOperand, 32> Ops;
4032   Ops.push_back(Chain);   // Op#0 - Chain
4033   Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
4034   Ops.push_back(DAG.getConstant(isVarArg, getPointerTy()));    // Op#2 - VarArg
4035   Ops.push_back(DAG.getConstant(isTailCall, getPointerTy()));  // Op#3 - Tail
4036   Ops.push_back(Callee);
4037   
4038   // Handle all of the outgoing arguments.
4039   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
4040     MVT::ValueType VT = getValueType(Args[i].Ty);
4041     SDOperand Op = Args[i].Node;
4042     unsigned Flags = ISD::ParamFlags::NoFlagSet;
4043     unsigned OriginalAlignment =
4044       getTargetData()->getABITypeAlignment(Args[i].Ty);
4045     
4046     if (Args[i].isSExt)
4047       Flags |= ISD::ParamFlags::SExt;
4048     if (Args[i].isZExt)
4049       Flags |= ISD::ParamFlags::ZExt;
4050     if (Args[i].isInReg)
4051       Flags |= ISD::ParamFlags::InReg;
4052     if (Args[i].isSRet)
4053       Flags |= ISD::ParamFlags::StructReturn;
4054     if (Args[i].isByVal) {
4055       Flags |= ISD::ParamFlags::ByVal;
4056       const PointerType *Ty = cast<PointerType>(Args[i].Ty);
4057       const StructType *STy = cast<StructType>(Ty->getElementType());
4058       unsigned StructAlign =
4059           Log2_32(getTargetData()->getCallFrameTypeAlignment(STy));
4060       unsigned StructSize  = getTargetData()->getABITypeSize(STy);
4061       Flags |= (StructAlign << ISD::ParamFlags::ByValAlignOffs);
4062       Flags |= (StructSize  << ISD::ParamFlags::ByValSizeOffs);
4063     }
4064     if (Args[i].isNest)
4065       Flags |= ISD::ParamFlags::Nest;
4066     Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
4067     
4068     switch (getTypeAction(VT)) {
4069     default: assert(0 && "Unknown type action!");
4070     case Legal:
4071       Ops.push_back(Op);
4072       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
4073       break;
4074     case Promote:
4075       if (MVT::isInteger(VT)) {
4076         unsigned ExtOp;
4077         if (Args[i].isSExt)
4078           ExtOp = ISD::SIGN_EXTEND;
4079         else if (Args[i].isZExt)
4080           ExtOp = ISD::ZERO_EXTEND;
4081         else
4082           ExtOp = ISD::ANY_EXTEND;
4083         Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
4084       } else {
4085         assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
4086         Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
4087       }
4088       Ops.push_back(Op);
4089       Ops.push_back(DAG.getConstant(Flags, MVT::i32));
4090       break;
4091     case Expand: {
4092       MVT::ValueType PartVT = getRegisterType(VT);
4093       unsigned NumParts = getNumRegisters(VT);
4094       SmallVector<SDOperand, 4> Parts(NumParts);
4095       getCopyToParts(DAG, Op, &Parts[0], NumParts, PartVT);
4096       for (unsigned i = 0; i != NumParts; ++i) {
4097         // if it isn't first piece, alignment must be 1
4098         unsigned MyFlags = Flags;
4099         if (i != 0)
4100           MyFlags = (MyFlags & (~ISD::ParamFlags::OrigAlignment)) |
4101             (1 << ISD::ParamFlags::OrigAlignmentOffs);
4102
4103         Ops.push_back(Parts[i]);
4104         Ops.push_back(DAG.getConstant(MyFlags, MVT::i32));
4105       }
4106       break;
4107     }
4108     }
4109   }
4110   
4111   // Figure out the result value types.
4112   MVT::ValueType VT = getValueType(RetTy);
4113   MVT::ValueType RegisterVT = getRegisterType(VT);
4114   unsigned NumRegs = getNumRegisters(VT);
4115   SmallVector<MVT::ValueType, 4> RetTys(NumRegs);
4116   for (unsigned i = 0; i != NumRegs; ++i)
4117     RetTys[i] = RegisterVT;
4118   
4119   RetTys.push_back(MVT::Other);  // Always has a chain.
4120   
4121   // Create the CALL node.
4122   SDOperand Res = DAG.getNode(ISD::CALL,
4123                               DAG.getVTList(&RetTys[0], NumRegs + 1),
4124                               &Ops[0], Ops.size());
4125   Chain = Res.getValue(NumRegs);
4126
4127   // Gather up the call result into a single value.
4128   if (RetTy != Type::VoidTy) {
4129     ISD::NodeType AssertOp = ISD::AssertSext;
4130     if (!RetTyIsSigned)
4131       AssertOp = ISD::AssertZext;
4132     SmallVector<SDOperand, 4> Results(NumRegs);
4133     for (unsigned i = 0; i != NumRegs; ++i)
4134       Results[i] = Res.getValue(i);
4135     Res = getCopyFromParts(DAG, &Results[0], NumRegs, RegisterVT, VT, AssertOp);
4136   }
4137
4138   return std::make_pair(Res, Chain);
4139 }
4140
4141 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
4142   assert(0 && "LowerOperation not implemented for this target!");
4143   abort();
4144   return SDOperand();
4145 }
4146
4147 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
4148                                                  SelectionDAG &DAG) {
4149   assert(0 && "CustomPromoteOperation not implemented for this target!");
4150   abort();
4151   return SDOperand();
4152 }
4153
4154 /// getMemsetValue - Vectorized representation of the memset value
4155 /// operand.
4156 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
4157                                 SelectionDAG &DAG) {
4158   MVT::ValueType CurVT = VT;
4159   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4160     uint64_t Val   = C->getValue() & 255;
4161     unsigned Shift = 8;
4162     while (CurVT != MVT::i8) {
4163       Val = (Val << Shift) | Val;
4164       Shift <<= 1;
4165       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
4166     }
4167     return DAG.getConstant(Val, VT);
4168   } else {
4169     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
4170     unsigned Shift = 8;
4171     while (CurVT != MVT::i8) {
4172       Value =
4173         DAG.getNode(ISD::OR, VT,
4174                     DAG.getNode(ISD::SHL, VT, Value,
4175                                 DAG.getConstant(Shift, MVT::i8)), Value);
4176       Shift <<= 1;
4177       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
4178     }
4179
4180     return Value;
4181   }
4182 }
4183
4184 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4185 /// used when a memcpy is turned into a memset when the source is a constant
4186 /// string ptr.
4187 static SDOperand getMemsetStringVal(MVT::ValueType VT,
4188                                     SelectionDAG &DAG, TargetLowering &TLI,
4189                                     std::string &Str, unsigned Offset) {
4190   uint64_t Val = 0;
4191   unsigned MSB = MVT::getSizeInBits(VT) / 8;
4192   if (TLI.isLittleEndian())
4193     Offset = Offset + MSB - 1;
4194   for (unsigned i = 0; i != MSB; ++i) {
4195     Val = (Val << 8) | (unsigned char)Str[Offset];
4196     Offset += TLI.isLittleEndian() ? -1 : 1;
4197   }
4198   return DAG.getConstant(Val, VT);
4199 }
4200
4201 /// getMemBasePlusOffset - Returns base and offset node for the 
4202 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
4203                                       SelectionDAG &DAG, TargetLowering &TLI) {
4204   MVT::ValueType VT = Base.getValueType();
4205   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
4206 }
4207
4208 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
4209 /// to replace the memset / memcpy is below the threshold. It also returns the
4210 /// types of the sequence of  memory ops to perform memset / memcpy.
4211 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
4212                                      unsigned Limit, uint64_t Size,
4213                                      unsigned Align, TargetLowering &TLI) {
4214   MVT::ValueType VT;
4215
4216   if (TLI.allowsUnalignedMemoryAccesses()) {
4217     VT = MVT::i64;
4218   } else {
4219     switch (Align & 7) {
4220     case 0:
4221       VT = MVT::i64;
4222       break;
4223     case 4:
4224       VT = MVT::i32;
4225       break;
4226     case 2:
4227       VT = MVT::i16;
4228       break;
4229     default:
4230       VT = MVT::i8;
4231       break;
4232     }
4233   }
4234
4235   MVT::ValueType LVT = MVT::i64;
4236   while (!TLI.isTypeLegal(LVT))
4237     LVT = (MVT::ValueType)((unsigned)LVT - 1);
4238   assert(MVT::isInteger(LVT));
4239
4240   if (VT > LVT)
4241     VT = LVT;
4242
4243   unsigned NumMemOps = 0;
4244   while (Size != 0) {
4245     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
4246     while (VTSize > Size) {
4247       VT = (MVT::ValueType)((unsigned)VT - 1);
4248       VTSize >>= 1;
4249     }
4250     assert(MVT::isInteger(VT));
4251
4252     if (++NumMemOps > Limit)
4253       return false;
4254     MemOps.push_back(VT);
4255     Size -= VTSize;
4256   }
4257
4258   return true;
4259 }
4260
4261 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
4262   SDOperand Op1 = getValue(I.getOperand(1));
4263   SDOperand Op2 = getValue(I.getOperand(2));
4264   SDOperand Op3 = getValue(I.getOperand(3));
4265   SDOperand Op4 = getValue(I.getOperand(4));
4266   unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
4267   if (Align == 0) Align = 1;
4268
4269   // If the source and destination are known to not be aliases, we can
4270   // lower memmove as memcpy.
4271   if (Op == ISD::MEMMOVE) {
4272     uint64_t Size = -1ULL;
4273     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op3))
4274       Size = C->getValue();
4275     if (AA.alias(I.getOperand(1), Size, I.getOperand(2), Size) ==
4276         AliasAnalysis::NoAlias)
4277       Op = ISD::MEMCPY;
4278   }
4279
4280   if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
4281     std::vector<MVT::ValueType> MemOps;
4282
4283     // Expand memset / memcpy to a series of load / store ops
4284     // if the size operand falls below a certain threshold.
4285     SmallVector<SDOperand, 8> OutChains;
4286     switch (Op) {
4287     default: break;  // Do nothing for now.
4288     case ISD::MEMSET: {
4289       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
4290                                    Size->getValue(), Align, TLI)) {
4291         unsigned NumMemOps = MemOps.size();
4292         unsigned Offset = 0;
4293         for (unsigned i = 0; i < NumMemOps; i++) {
4294           MVT::ValueType VT = MemOps[i];
4295           unsigned VTSize = MVT::getSizeInBits(VT) / 8;
4296           SDOperand Value = getMemsetValue(Op2, VT, DAG);
4297           SDOperand Store = DAG.getStore(getRoot(), Value,
4298                                     getMemBasePlusOffset(Op1, Offset, DAG, TLI),
4299                                          I.getOperand(1), Offset);
4300           OutChains.push_back(Store);
4301           Offset += VTSize;
4302         }
4303       }
4304       break;
4305     }
4306     case ISD::MEMCPY: {
4307       if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
4308                                    Size->getValue(), Align, TLI)) {
4309         unsigned NumMemOps = MemOps.size();
4310         unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
4311         GlobalAddressSDNode *G = NULL;
4312         std::string Str;
4313         bool CopyFromStr = false;
4314
4315         if (Op2.getOpcode() == ISD::GlobalAddress)
4316           G = cast<GlobalAddressSDNode>(Op2);
4317         else if (Op2.getOpcode() == ISD::ADD &&
4318                  Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4319                  Op2.getOperand(1).getOpcode() == ISD::Constant) {
4320           G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
4321           SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
4322         }
4323         if (G) {
4324           GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
4325           if (GV && GV->isConstant()) {
4326             Str = GV->getStringValue(false);
4327             if (!Str.empty()) {
4328               CopyFromStr = true;
4329               SrcOff += SrcDelta;
4330             }
4331           }
4332         }
4333
4334         for (unsigned i = 0; i < NumMemOps; i++) {
4335           MVT::ValueType VT = MemOps[i];
4336           unsigned VTSize = MVT::getSizeInBits(VT) / 8;
4337           SDOperand Value, Chain, Store;
4338
4339           if (CopyFromStr) {
4340             Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
4341             Chain = getRoot();
4342             Store =
4343               DAG.getStore(Chain, Value,
4344                            getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
4345                            I.getOperand(1), DstOff);
4346           } else {
4347             Value = DAG.getLoad(VT, getRoot(),
4348                                 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
4349                                 I.getOperand(2), SrcOff, false, Align);
4350             Chain = Value.getValue(1);
4351             Store =
4352               DAG.getStore(Chain, Value,
4353                            getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
4354                            I.getOperand(1), DstOff, false, Align);
4355           }
4356           OutChains.push_back(Store);
4357           SrcOff += VTSize;
4358           DstOff += VTSize;
4359         }
4360       }
4361       break;
4362     }
4363     }
4364
4365     if (!OutChains.empty()) {
4366       DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4367                   &OutChains[0], OutChains.size()));
4368       return;
4369     }
4370   }
4371
4372   SDOperand AlwaysInline = DAG.getConstant(0, MVT::i1);
4373   SDOperand Node;
4374   switch(Op) {
4375     default:
4376       assert(0 && "Unknown Op");
4377     case ISD::MEMCPY:
4378       Node = DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
4379       break;
4380     case ISD::MEMMOVE:
4381       Node = DAG.getMemmove(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
4382       break;
4383     case ISD::MEMSET:
4384       Node = DAG.getMemset(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
4385       break;
4386   }
4387   DAG.setRoot(Node);
4388 }
4389
4390 //===----------------------------------------------------------------------===//
4391 // SelectionDAGISel code
4392 //===----------------------------------------------------------------------===//
4393
4394 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
4395   return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
4396 }
4397
4398 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
4399   AU.addRequired<AliasAnalysis>();
4400   AU.setPreservesAll();
4401 }
4402
4403
4404
4405 bool SelectionDAGISel::runOnFunction(Function &Fn) {
4406   // Get alias analysis for load/store combining.
4407   AA = &getAnalysis<AliasAnalysis>();
4408
4409   MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
4410   RegMap = MF.getSSARegMap();
4411   DOUT << "\n\n\n=== " << Fn.getName() << "\n";
4412
4413   FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
4414
4415   if (ExceptionHandling)
4416     for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
4417       if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
4418         // Mark landing pad.
4419         FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
4420
4421   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
4422     SelectBasicBlock(I, MF, FuncInfo);
4423
4424   // Add function live-ins to entry block live-in set.
4425   BasicBlock *EntryBB = &Fn.getEntryBlock();
4426   BB = FuncInfo.MBBMap[EntryBB];
4427   if (!MF.livein_empty())
4428     for (MachineFunction::livein_iterator I = MF.livein_begin(),
4429            E = MF.livein_end(); I != E; ++I)
4430       BB->addLiveIn(I->first);
4431
4432 #ifndef NDEBUG
4433   assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() &&
4434          "Not all catch info was assigned to a landing pad!");
4435 #endif
4436
4437   return true;
4438 }
4439
4440 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, 
4441                                                            unsigned Reg) {
4442   SDOperand Op = getValue(V);
4443   assert((Op.getOpcode() != ISD::CopyFromReg ||
4444           cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
4445          "Copy from a reg to the same reg!");
4446   
4447   MVT::ValueType SrcVT = Op.getValueType();
4448   MVT::ValueType RegisterVT = TLI.getRegisterType(SrcVT);
4449   unsigned NumRegs = TLI.getNumRegisters(SrcVT);
4450   SmallVector<SDOperand, 8> Regs(NumRegs);
4451   SmallVector<SDOperand, 8> Chains(NumRegs);
4452
4453   // Copy the value by legal parts into sequential virtual registers.
4454   getCopyToParts(DAG, Op, &Regs[0], NumRegs, RegisterVT);
4455   for (unsigned i = 0; i != NumRegs; ++i)
4456     Chains[i] = DAG.getCopyToReg(getRoot(), Reg + i, Regs[i]);
4457   return DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumRegs);
4458 }
4459
4460 void SelectionDAGISel::
4461 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
4462                std::vector<SDOperand> &UnorderedChains) {
4463   // If this is the entry block, emit arguments.
4464   Function &F = *LLVMBB->getParent();
4465   FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4466   SDOperand OldRoot = SDL.DAG.getRoot();
4467   std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
4468
4469   unsigned a = 0;
4470   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4471        AI != E; ++AI, ++a)
4472     if (!AI->use_empty()) {
4473       SDL.setValue(AI, Args[a]);
4474
4475       // If this argument is live outside of the entry block, insert a copy from
4476       // whereever we got it to the vreg that other BB's will reference it as.
4477       DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4478       if (VMI != FuncInfo.ValueMap.end()) {
4479         SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
4480         UnorderedChains.push_back(Copy);
4481       }
4482     }
4483
4484   // Finally, if the target has anything special to do, allow it to do so.
4485   // FIXME: this should insert code into the DAG!
4486   EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4487 }
4488
4489 static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
4490                           MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
4491   for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
4492     if (isSelector(I)) {
4493       // Apply the catch info to DestBB.
4494       addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]);
4495 #ifndef NDEBUG
4496       if (!FLI.MBBMap[SrcBB]->isLandingPad())
4497         FLI.CatchInfoFound.insert(I);
4498 #endif
4499     }
4500 }
4501
4502 /// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the
4503 /// DAG and fixes their tailcall attribute operand.
4504 static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, 
4505                                            TargetLowering& TLI) {
4506   SDNode * Ret = NULL;
4507   SDOperand Terminator = DAG.getRoot();
4508
4509   // Find RET node.
4510   if (Terminator.getOpcode() == ISD::RET) {
4511     Ret = Terminator.Val;
4512   }
4513  
4514   // Fix tail call attribute of CALL nodes.
4515   for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
4516          BI = prior(DAG.allnodes_end()); BI != BE; --BI) {
4517     if (BI->getOpcode() == ISD::CALL) {
4518       SDOperand OpRet(Ret, 0);
4519       SDOperand OpCall(static_cast<SDNode*>(BI), 0);
4520       bool isMarkedTailCall = 
4521         cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0;
4522       // If CALL node has tail call attribute set to true and the call is not
4523       // eligible (no RET or the target rejects) the attribute is fixed to
4524       // false. The TargetLowering::IsEligibleForTailCallOptimization function
4525       // must correctly identify tail call optimizable calls.
4526       if (isMarkedTailCall && 
4527           (Ret==NULL || 
4528            !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG))) {
4529         SmallVector<SDOperand, 32> Ops;
4530         unsigned idx=0;
4531         for(SDNode::op_iterator I =OpCall.Val->op_begin(), 
4532               E=OpCall.Val->op_end(); I!=E; I++, idx++) {
4533           if (idx!=3)
4534             Ops.push_back(*I);
4535           else 
4536             Ops.push_back(DAG.getConstant(false, TLI.getPointerTy()));
4537         }
4538         DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
4539       }
4540     }
4541   }
4542 }
4543
4544 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
4545        std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
4546                                          FunctionLoweringInfo &FuncInfo) {
4547   SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo);
4548
4549   std::vector<SDOperand> UnorderedChains;
4550
4551   // Lower any arguments needed in this block if this is the entry block.
4552   if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
4553     LowerArguments(LLVMBB, SDL, UnorderedChains);
4554
4555   BB = FuncInfo.MBBMap[LLVMBB];
4556   SDL.setCurrentBasicBlock(BB);
4557
4558   MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
4559
4560   if (ExceptionHandling && MMI && BB->isLandingPad()) {
4561     // Add a label to mark the beginning of the landing pad.  Deletion of the
4562     // landing pad can thus be detected via the MachineModuleInfo.
4563     unsigned LabelID = MMI->addLandingPad(BB);
4564     DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
4565                             DAG.getConstant(LabelID, MVT::i32)));
4566
4567     // Mark exception register as live in.
4568     unsigned Reg = TLI.getExceptionAddressRegister();
4569     if (Reg) BB->addLiveIn(Reg);
4570
4571     // Mark exception selector register as live in.
4572     Reg = TLI.getExceptionSelectorRegister();
4573     if (Reg) BB->addLiveIn(Reg);
4574
4575     // FIXME: Hack around an exception handling flaw (PR1508): the personality
4576     // function and list of typeids logically belong to the invoke (or, if you
4577     // like, the basic block containing the invoke), and need to be associated
4578     // with it in the dwarf exception handling tables.  Currently however the
4579     // information is provided by an intrinsic (eh.selector) that can be moved
4580     // to unexpected places by the optimizers: if the unwind edge is critical,
4581     // then breaking it can result in the intrinsics being in the successor of
4582     // the landing pad, not the landing pad itself.  This results in exceptions
4583     // not being caught because no typeids are associated with the invoke.
4584     // This may not be the only way things can go wrong, but it is the only way
4585     // we try to work around for the moment.
4586     BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
4587
4588     if (Br && Br->isUnconditional()) { // Critical edge?
4589       BasicBlock::iterator I, E;
4590       for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
4591         if (isSelector(I))
4592           break;
4593
4594       if (I == E)
4595         // No catch info found - try to extract some from the successor.
4596         copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo);
4597     }
4598   }
4599
4600   // Lower all of the non-terminator instructions.
4601   for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
4602        I != E; ++I)
4603     SDL.visit(*I);
4604
4605   // Ensure that all instructions which are used outside of their defining
4606   // blocks are available as virtual registers.  Invoke is handled elsewhere.
4607   for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
4608     if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) {
4609       DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4610       if (VMI != FuncInfo.ValueMap.end())
4611         UnorderedChains.push_back(
4612                                 SDL.CopyValueToVirtualRegister(I, VMI->second));
4613     }
4614
4615   // Handle PHI nodes in successor blocks.  Emit code into the SelectionDAG to
4616   // ensure constants are generated when needed.  Remember the virtual registers
4617   // that need to be added to the Machine PHI nodes as input.  We cannot just
4618   // directly add them, because expansion might result in multiple MBB's for one
4619   // BB.  As such, the start of the BB might correspond to a different MBB than
4620   // the end.
4621   //
4622   TerminatorInst *TI = LLVMBB->getTerminator();
4623
4624   // Emit constants only once even if used by multiple PHI nodes.
4625   std::map<Constant*, unsigned> ConstantsOut;
4626   
4627   // Vector bool would be better, but vector<bool> is really slow.
4628   std::vector<unsigned char> SuccsHandled;
4629   if (TI->getNumSuccessors())
4630     SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4631     
4632   // Check successor nodes' PHI nodes that expect a constant to be available
4633   // from this block.
4634   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4635     BasicBlock *SuccBB = TI->getSuccessor(succ);
4636     if (!isa<PHINode>(SuccBB->begin())) continue;
4637     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4638     
4639     // If this terminator has multiple identical successors (common for
4640     // switches), only handle each succ once.
4641     unsigned SuccMBBNo = SuccMBB->getNumber();
4642     if (SuccsHandled[SuccMBBNo]) continue;
4643     SuccsHandled[SuccMBBNo] = true;
4644     
4645     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4646     PHINode *PN;
4647
4648     // At this point we know that there is a 1-1 correspondence between LLVM PHI
4649     // nodes and Machine PHI nodes, but the incoming operands have not been
4650     // emitted yet.
4651     for (BasicBlock::iterator I = SuccBB->begin();
4652          (PN = dyn_cast<PHINode>(I)); ++I) {
4653       // Ignore dead phi's.
4654       if (PN->use_empty()) continue;
4655       
4656       unsigned Reg;
4657       Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4658       
4659       if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4660         unsigned &RegOut = ConstantsOut[C];
4661         if (RegOut == 0) {
4662           RegOut = FuncInfo.CreateRegForValue(C);
4663           UnorderedChains.push_back(
4664                            SDL.CopyValueToVirtualRegister(C, RegOut));
4665         }
4666         Reg = RegOut;
4667       } else {
4668         Reg = FuncInfo.ValueMap[PHIOp];
4669         if (Reg == 0) {
4670           assert(isa<AllocaInst>(PHIOp) &&
4671                  FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4672                  "Didn't codegen value into a register!??");
4673           Reg = FuncInfo.CreateRegForValue(PHIOp);
4674           UnorderedChains.push_back(
4675                            SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4676         }
4677       }
4678
4679       // Remember that this register needs to added to the machine PHI node as
4680       // the input for this MBB.
4681       MVT::ValueType VT = TLI.getValueType(PN->getType());
4682       unsigned NumRegisters = TLI.getNumRegisters(VT);
4683       for (unsigned i = 0, e = NumRegisters; i != e; ++i)
4684         PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4685     }
4686   }
4687   ConstantsOut.clear();
4688
4689   // Turn all of the unordered chains into one factored node.
4690   if (!UnorderedChains.empty()) {
4691     SDOperand Root = SDL.getRoot();
4692     if (Root.getOpcode() != ISD::EntryToken) {
4693       unsigned i = 0, e = UnorderedChains.size();
4694       for (; i != e; ++i) {
4695         assert(UnorderedChains[i].Val->getNumOperands() > 1);
4696         if (UnorderedChains[i].Val->getOperand(0) == Root)
4697           break;  // Don't add the root if we already indirectly depend on it.
4698       }
4699         
4700       if (i == e)
4701         UnorderedChains.push_back(Root);
4702     }
4703     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4704                             &UnorderedChains[0], UnorderedChains.size()));
4705   }
4706
4707   // Lower the terminator after the copies are emitted.
4708   SDL.visit(*LLVMBB->getTerminator());
4709
4710   // Copy over any CaseBlock records that may now exist due to SwitchInst
4711   // lowering, as well as any jump table information.
4712   SwitchCases.clear();
4713   SwitchCases = SDL.SwitchCases;
4714   JTCases.clear();
4715   JTCases = SDL.JTCases;
4716   BitTestCases.clear();
4717   BitTestCases = SDL.BitTestCases;
4718     
4719   // Make sure the root of the DAG is up-to-date.
4720   DAG.setRoot(SDL.getRoot());
4721
4722   // Check whether calls in this block are real tail calls. Fix up CALL nodes
4723   // with correct tailcall attribute so that the target can rely on the tailcall
4724   // attribute indicating whether the call is really eligible for tail call
4725   // optimization.
4726   CheckDAGForTailCallsAndFixThem(DAG, TLI);
4727 }
4728
4729 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4730   DOUT << "Lowered selection DAG:\n";
4731   DEBUG(DAG.dump());
4732
4733   // Run the DAG combiner in pre-legalize mode.
4734   DAG.Combine(false, *AA);
4735   
4736   DOUT << "Optimized lowered selection DAG:\n";
4737   DEBUG(DAG.dump());
4738   
4739   // Second step, hack on the DAG until it only uses operations and types that
4740   // the target supports.
4741 #if 0  // Enable this some day.
4742   DAG.LegalizeTypes();
4743   // Someday even later, enable a dag combine pass here.
4744 #endif
4745   DAG.Legalize();
4746   
4747   DOUT << "Legalized selection DAG:\n";
4748   DEBUG(DAG.dump());
4749   
4750   // Run the DAG combiner in post-legalize mode.
4751   DAG.Combine(true, *AA);
4752   
4753   DOUT << "Optimized legalized selection DAG:\n";
4754   DEBUG(DAG.dump());
4755
4756   if (ViewISelDAGs) DAG.viewGraph();
4757
4758   // Third, instruction select all of the operations to machine code, adding the
4759   // code to the MachineBasicBlock.
4760   InstructionSelectBasicBlock(DAG);
4761   
4762   DOUT << "Selected machine code:\n";
4763   DEBUG(BB->dump());
4764 }  
4765
4766 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4767                                         FunctionLoweringInfo &FuncInfo) {
4768   std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4769   {
4770     SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4771     CurDAG = &DAG;
4772   
4773     // First step, lower LLVM code to some DAG.  This DAG may use operations and
4774     // types that are not supported by the target.
4775     BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4776
4777     // Second step, emit the lowered DAG as machine code.
4778     CodeGenAndEmitDAG(DAG);
4779   }
4780
4781   DOUT << "Total amount of phi nodes to update: "
4782        << PHINodesToUpdate.size() << "\n";
4783   DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i)
4784           DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first
4785                << ", " << PHINodesToUpdate[i].second << ")\n";);
4786   
4787   // Next, now that we know what the last MBB the LLVM BB expanded is, update
4788   // PHI nodes in successors.
4789   if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) {
4790     for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4791       MachineInstr *PHI = PHINodesToUpdate[i].first;
4792       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4793              "This is not a machine PHI node that we are updating!");
4794       PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4795       PHI->addMachineBasicBlockOperand(BB);
4796     }
4797     return;
4798   }
4799
4800   for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) {
4801     // Lower header first, if it wasn't already lowered
4802     if (!BitTestCases[i].Emitted) {
4803       SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4804       CurDAG = &HSDAG;
4805       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo);
4806       // Set the current basic block to the mbb we wish to insert the code into
4807       BB = BitTestCases[i].Parent;
4808       HSDL.setCurrentBasicBlock(BB);
4809       // Emit the code
4810       HSDL.visitBitTestHeader(BitTestCases[i]);
4811       HSDAG.setRoot(HSDL.getRoot());
4812       CodeGenAndEmitDAG(HSDAG);
4813     }    
4814
4815     for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
4816       SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4817       CurDAG = &BSDAG;
4818       SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo);
4819       // Set the current basic block to the mbb we wish to insert the code into
4820       BB = BitTestCases[i].Cases[j].ThisBB;
4821       BSDL.setCurrentBasicBlock(BB);
4822       // Emit the code
4823       if (j+1 != ej)
4824         BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB,
4825                               BitTestCases[i].Reg,
4826                               BitTestCases[i].Cases[j]);
4827       else
4828         BSDL.visitBitTestCase(BitTestCases[i].Default,
4829                               BitTestCases[i].Reg,
4830                               BitTestCases[i].Cases[j]);
4831         
4832         
4833       BSDAG.setRoot(BSDL.getRoot());
4834       CodeGenAndEmitDAG(BSDAG);
4835     }
4836
4837     // Update PHI Nodes
4838     for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4839       MachineInstr *PHI = PHINodesToUpdate[pi].first;
4840       MachineBasicBlock *PHIBB = PHI->getParent();
4841       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4842              "This is not a machine PHI node that we are updating!");
4843       // This is "default" BB. We have two jumps to it. From "header" BB and
4844       // from last "case" BB.
4845       if (PHIBB == BitTestCases[i].Default) {
4846         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4847         PHI->addMachineBasicBlockOperand(BitTestCases[i].Parent);
4848         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4849         PHI->addMachineBasicBlockOperand(BitTestCases[i].Cases.back().ThisBB);
4850       }
4851       // One of "cases" BB.
4852       for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
4853         MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB;
4854         if (cBB->succ_end() !=
4855             std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
4856           PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4857           PHI->addMachineBasicBlockOperand(cBB);
4858         }
4859       }
4860     }
4861   }
4862
4863   // If the JumpTable record is filled in, then we need to emit a jump table.
4864   // Updating the PHI nodes is tricky in this case, since we need to determine
4865   // whether the PHI is a successor of the range check MBB or the jump table MBB
4866   for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
4867     // Lower header first, if it wasn't already lowered
4868     if (!JTCases[i].first.Emitted) {
4869       SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4870       CurDAG = &HSDAG;
4871       SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo);
4872       // Set the current basic block to the mbb we wish to insert the code into
4873       BB = JTCases[i].first.HeaderBB;
4874       HSDL.setCurrentBasicBlock(BB);
4875       // Emit the code
4876       HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
4877       HSDAG.setRoot(HSDL.getRoot());
4878       CodeGenAndEmitDAG(HSDAG);
4879     }
4880     
4881     SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4882     CurDAG = &JSDAG;
4883     SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo);
4884     // Set the current basic block to the mbb we wish to insert the code into
4885     BB = JTCases[i].second.MBB;
4886     JSDL.setCurrentBasicBlock(BB);
4887     // Emit the code
4888     JSDL.visitJumpTable(JTCases[i].second);
4889     JSDAG.setRoot(JSDL.getRoot());
4890     CodeGenAndEmitDAG(JSDAG);
4891     
4892     // Update PHI Nodes
4893     for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4894       MachineInstr *PHI = PHINodesToUpdate[pi].first;
4895       MachineBasicBlock *PHIBB = PHI->getParent();
4896       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4897              "This is not a machine PHI node that we are updating!");
4898       // "default" BB. We can go there only from header BB.
4899       if (PHIBB == JTCases[i].second.Default) {
4900         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4901         PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
4902       }
4903       // JT BB. Just iterate over successors here
4904       if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4905         PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4906         PHI->addMachineBasicBlockOperand(BB);
4907       }
4908     }
4909   }
4910   
4911   // If the switch block involved a branch to one of the actual successors, we
4912   // need to update PHI nodes in that block.
4913   for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4914     MachineInstr *PHI = PHINodesToUpdate[i].first;
4915     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4916            "This is not a machine PHI node that we are updating!");
4917     if (BB->isSuccessor(PHI->getParent())) {
4918       PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4919       PHI->addMachineBasicBlockOperand(BB);
4920     }
4921   }
4922   
4923   // If we generated any switch lowering information, build and codegen any
4924   // additional DAGs necessary.
4925   for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4926     SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4927     CurDAG = &SDAG;
4928     SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo);
4929     
4930     // Set the current basic block to the mbb we wish to insert the code into
4931     BB = SwitchCases[i].ThisBB;
4932     SDL.setCurrentBasicBlock(BB);
4933     
4934     // Emit the code
4935     SDL.visitSwitchCase(SwitchCases[i]);
4936     SDAG.setRoot(SDL.getRoot());
4937     CodeGenAndEmitDAG(SDAG);
4938     
4939     // Handle any PHI nodes in successors of this chunk, as if we were coming
4940     // from the original BB before switch expansion.  Note that PHI nodes can
4941     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
4942     // handle them the right number of times.
4943     while ((BB = SwitchCases[i].TrueBB)) {  // Handle LHS and RHS.
4944       for (MachineBasicBlock::iterator Phi = BB->begin();
4945            Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4946         // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4947         for (unsigned pn = 0; ; ++pn) {
4948           assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4949           if (PHINodesToUpdate[pn].first == Phi) {
4950             Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4951             Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4952             break;
4953           }
4954         }
4955       }
4956       
4957       // Don't process RHS if same block as LHS.
4958       if (BB == SwitchCases[i].FalseBB)
4959         SwitchCases[i].FalseBB = 0;
4960       
4961       // If we haven't handled the RHS, do so now.  Otherwise, we're done.
4962       SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4963       SwitchCases[i].FalseBB = 0;
4964     }
4965     assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4966   }
4967 }
4968
4969
4970 //===----------------------------------------------------------------------===//
4971 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4972 /// target node in the graph.
4973 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4974   if (ViewSchedDAGs) DAG.viewGraph();
4975
4976   RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4977   
4978   if (!Ctor) {
4979     Ctor = ISHeuristic;
4980     RegisterScheduler::setDefault(Ctor);
4981   }
4982   
4983   ScheduleDAG *SL = Ctor(this, &DAG, BB);
4984   BB = SL->Run();
4985
4986   if (ViewSUnitDAGs) SL->viewGraph();
4987
4988   delete SL;
4989 }
4990
4991
4992 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4993   return new HazardRecognizer();
4994 }
4995
4996 //===----------------------------------------------------------------------===//
4997 // Helper functions used by the generated instruction selector.
4998 //===----------------------------------------------------------------------===//
4999 // Calls to these methods are generated by tblgen.
5000
5001 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
5002 /// the dag combiner simplified the 255, we still want to match.  RHS is the
5003 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
5004 /// specified in the .td file (e.g. 255).
5005 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS, 
5006                                     int64_t DesiredMaskS) const {
5007   uint64_t ActualMask = RHS->getValue();
5008   uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
5009   
5010   // If the actual mask exactly matches, success!
5011   if (ActualMask == DesiredMask)
5012     return true;
5013   
5014   // If the actual AND mask is allowing unallowed bits, this doesn't match.
5015   if (ActualMask & ~DesiredMask)
5016     return false;
5017   
5018   // Otherwise, the DAG Combiner may have proven that the value coming in is
5019   // either already zero or is not demanded.  Check for known zero input bits.
5020   uint64_t NeededMask = DesiredMask & ~ActualMask;
5021   if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
5022     return true;
5023   
5024   // TODO: check to see if missing bits are just not demanded.
5025
5026   // Otherwise, this pattern doesn't match.
5027   return false;
5028 }
5029
5030 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
5031 /// the dag combiner simplified the 255, we still want to match.  RHS is the
5032 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
5033 /// specified in the .td file (e.g. 255).
5034 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS, 
5035                                     int64_t DesiredMaskS) const {
5036   uint64_t ActualMask = RHS->getValue();
5037   uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
5038   
5039   // If the actual mask exactly matches, success!
5040   if (ActualMask == DesiredMask)
5041     return true;
5042   
5043   // If the actual AND mask is allowing unallowed bits, this doesn't match.
5044   if (ActualMask & ~DesiredMask)
5045     return false;
5046   
5047   // Otherwise, the DAG Combiner may have proven that the value coming in is
5048   // either already zero or is not demanded.  Check for known zero input bits.
5049   uint64_t NeededMask = DesiredMask & ~ActualMask;
5050   
5051   uint64_t KnownZero, KnownOne;
5052   CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
5053   
5054   // If all the missing bits in the or are already known to be set, match!
5055   if ((NeededMask & KnownOne) == NeededMask)
5056     return true;
5057   
5058   // TODO: check to see if missing bits are just not demanded.
5059   
5060   // Otherwise, this pattern doesn't match.
5061   return false;
5062 }
5063
5064
5065 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
5066 /// by tblgen.  Others should not call it.
5067 void SelectionDAGISel::
5068 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
5069   std::vector<SDOperand> InOps;
5070   std::swap(InOps, Ops);
5071
5072   Ops.push_back(InOps[0]);  // input chain.
5073   Ops.push_back(InOps[1]);  // input asm string.
5074
5075   unsigned i = 2, e = InOps.size();
5076   if (InOps[e-1].getValueType() == MVT::Flag)
5077     --e;  // Don't process a flag operand if it is here.
5078   
5079   while (i != e) {
5080     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
5081     if ((Flags & 7) != 4 /*MEM*/) {
5082       // Just skip over this operand, copying the operands verbatim.
5083       Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
5084       i += (Flags >> 3) + 1;
5085     } else {
5086       assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
5087       // Otherwise, this is a memory operand.  Ask the target to select it.
5088       std::vector<SDOperand> SelOps;
5089       if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
5090         cerr << "Could not match memory address.  Inline asm failure!\n";
5091         exit(1);
5092       }
5093       
5094       // Add this to the output node.
5095       MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
5096       Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
5097                                           IntPtrTy));
5098       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
5099       i += 2;
5100     }
5101   }
5102   
5103   // Add the flag input back if present.
5104   if (e != InOps.size())
5105     Ops.push_back(InOps.back());
5106 }
5107
5108 char SelectionDAGISel::ID = 0;