1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAGISel class.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "isel"
15 #include "llvm/Analysis/AliasAnalysis.h"
16 #include "llvm/CodeGen/SelectionDAGISel.h"
17 #include "llvm/CodeGen/ScheduleDAG.h"
18 #include "llvm/CallingConv.h"
19 #include "llvm/DerivedTypes.h"
20 #include "llvm/Function.h"
21 #include "llvm/GlobalVariable.h"
22 #include "llvm/InlineAsm.h"
23 #include "llvm/Instructions.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/IntrinsicInst.h"
26 #include "llvm/CodeGen/MachineModuleInfo.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineFrameInfo.h"
29 #include "llvm/CodeGen/MachineJumpTableInfo.h"
30 #include "llvm/CodeGen/MachineInstrBuilder.h"
31 #include "llvm/CodeGen/SchedulerRegistry.h"
32 #include "llvm/CodeGen/SelectionDAG.h"
33 #include "llvm/CodeGen/SSARegMap.h"
34 #include "llvm/Target/MRegisterInfo.h"
35 #include "llvm/Target/TargetData.h"
36 #include "llvm/Target/TargetFrameInfo.h"
37 #include "llvm/Target/TargetInstrInfo.h"
38 #include "llvm/Target/TargetLowering.h"
39 #include "llvm/Target/TargetMachine.h"
40 #include "llvm/Target/TargetOptions.h"
41 #include "llvm/Support/MathExtras.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/Compiler.h"
49 ViewISelDAGs("view-isel-dags", cl::Hidden,
50 cl::desc("Pop up a window to show isel dags as they are selected"));
52 ViewSchedDAGs("view-sched-dags", cl::Hidden,
53 cl::desc("Pop up a window to show sched dags as they are processed"));
55 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
58 //===---------------------------------------------------------------------===//
60 /// RegisterScheduler class - Track the registration of instruction schedulers.
62 //===---------------------------------------------------------------------===//
63 MachinePassRegistry RegisterScheduler::Registry;
65 //===---------------------------------------------------------------------===//
67 /// ISHeuristic command line option for instruction schedulers.
69 //===---------------------------------------------------------------------===//
71 cl::opt<RegisterScheduler::FunctionPassCtor, false,
72 RegisterPassParser<RegisterScheduler> >
74 cl::init(&createDefaultScheduler),
75 cl::desc("Instruction schedulers available:"));
77 static RegisterScheduler
78 defaultListDAGScheduler("default", " Best scheduler for the target",
79 createDefaultScheduler);
83 /// RegsForValue - This struct represents the physical registers that a
84 /// particular value is assigned and the type information about the value.
85 /// This is needed because values can be promoted into larger registers and
86 /// expanded into multiple smaller registers than the value.
87 struct VISIBILITY_HIDDEN RegsForValue {
88 /// Regs - This list hold the register (for legal and promoted values)
89 /// or register set (for expanded values) that the value should be assigned
91 std::vector<unsigned> Regs;
93 /// RegVT - The value type of each register.
97 /// ValueVT - The value type of the LLVM value, which may be promoted from
98 /// RegVT or made from merging the two expanded parts.
99 MVT::ValueType ValueVT;
101 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {}
103 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt)
104 : RegVT(regvt), ValueVT(valuevt) {
107 RegsForValue(const std::vector<unsigned> ®s,
108 MVT::ValueType regvt, MVT::ValueType valuevt)
109 : Regs(regs), RegVT(regvt), ValueVT(valuevt) {
112 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
113 /// this value and returns the result as a ValueVT value. This uses
114 /// Chain/Flag as the input and updates them for the output Chain/Flag.
115 SDOperand getCopyFromRegs(SelectionDAG &DAG,
116 SDOperand &Chain, SDOperand &Flag) const;
118 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
119 /// specified value into the registers specified by this object. This uses
120 /// Chain/Flag as the input and updates them for the output Chain/Flag.
121 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
122 SDOperand &Chain, SDOperand &Flag,
123 MVT::ValueType PtrVT) const;
125 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
126 /// operand list. This adds the code marker and includes the number of
127 /// values added into it.
128 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
129 std::vector<SDOperand> &Ops) const;
134 //===--------------------------------------------------------------------===//
135 /// createDefaultScheduler - This creates an instruction scheduler appropriate
137 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
139 MachineBasicBlock *BB) {
140 TargetLowering &TLI = IS->getTargetLowering();
142 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
143 return createTDListDAGScheduler(IS, DAG, BB);
145 assert(TLI.getSchedulingPreference() ==
146 TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
147 return createBURRListDAGScheduler(IS, DAG, BB);
152 //===--------------------------------------------------------------------===//
153 /// FunctionLoweringInfo - This contains information that is global to a
154 /// function that is used when lowering a region of the function.
155 class FunctionLoweringInfo {
162 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
164 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
165 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
167 /// ValueMap - Since we emit code for the function a basic block at a time,
168 /// we must remember which virtual registers hold the values for
169 /// cross-basic-block values.
170 DenseMap<const Value*, unsigned> ValueMap;
172 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
173 /// the entry block. This allows the allocas to be efficiently referenced
174 /// anywhere in the function.
175 std::map<const AllocaInst*, int> StaticAllocaMap;
177 unsigned MakeReg(MVT::ValueType VT) {
178 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
181 /// isExportedInst - Return true if the specified value is an instruction
182 /// exported from its block.
183 bool isExportedInst(const Value *V) {
184 return ValueMap.count(V);
187 unsigned CreateRegForValue(const Value *V);
189 unsigned InitializeRegForValue(const Value *V) {
190 unsigned &R = ValueMap[V];
191 assert(R == 0 && "Already initialized this value register!");
192 return R = CreateRegForValue(V);
197 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
198 /// PHI nodes or outside of the basic block that defines it, or used by a
199 /// switch instruction, which may expand to multiple basic blocks.
200 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
201 if (isa<PHINode>(I)) return true;
202 BasicBlock *BB = I->getParent();
203 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
204 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
205 // FIXME: Remove switchinst special case.
206 isa<SwitchInst>(*UI))
211 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
212 /// entry block, return true. This includes arguments used by switches, since
213 /// the switch may expand into multiple basic blocks.
214 static bool isOnlyUsedInEntryBlock(Argument *A) {
215 BasicBlock *Entry = A->getParent()->begin();
216 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
217 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
218 return false; // Use not in entry block.
222 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
223 Function &fn, MachineFunction &mf)
224 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
226 // Create a vreg for each argument register that is not dead and is used
227 // outside of the entry block for the function.
228 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
230 if (!isOnlyUsedInEntryBlock(AI))
231 InitializeRegForValue(AI);
233 // Initialize the mapping of values to registers. This is only set up for
234 // instruction values that are used outside of the block that defines
236 Function::iterator BB = Fn.begin(), EB = Fn.end();
237 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
238 if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
239 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
240 const Type *Ty = AI->getAllocatedType();
241 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
243 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
246 TySize *= CUI->getZExtValue(); // Get total allocated size.
247 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
248 StaticAllocaMap[AI] =
249 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
252 for (; BB != EB; ++BB)
253 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
254 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
255 if (!isa<AllocaInst>(I) ||
256 !StaticAllocaMap.count(cast<AllocaInst>(I)))
257 InitializeRegForValue(I);
259 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This
260 // also creates the initial PHI MachineInstrs, though none of the input
261 // operands are populated.
262 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
263 MachineBasicBlock *MBB = new MachineBasicBlock(BB);
265 MF.getBasicBlockList().push_back(MBB);
267 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
270 for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
271 if (PN->use_empty()) continue;
273 MVT::ValueType VT = TLI.getValueType(PN->getType());
274 unsigned NumElements;
275 if (VT != MVT::Vector)
276 NumElements = TLI.getNumElements(VT);
278 MVT::ValueType VT1,VT2;
280 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
283 unsigned PHIReg = ValueMap[PN];
284 assert(PHIReg && "PHI node does not have an assigned virtual register!");
285 const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
286 for (unsigned i = 0; i != NumElements; ++i)
287 BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
292 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
293 /// the correctly promoted or expanded types. Assign these registers
294 /// consecutive vreg numbers and return the first assigned number.
295 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
296 MVT::ValueType VT = TLI.getValueType(V->getType());
298 // The number of multiples of registers that we need, to, e.g., split up
299 // a <2 x int64> -> 4 x i32 registers.
300 unsigned NumVectorRegs = 1;
302 // If this is a vector type, figure out what type it will decompose into
303 // and how many of the elements it will use.
304 if (VT == MVT::Vector) {
305 const VectorType *PTy = cast<VectorType>(V->getType());
306 unsigned NumElts = PTy->getNumElements();
307 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
309 // Divide the input until we get to a supported size. This will always
310 // end with a scalar if the target doesn't support vectors.
311 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) {
318 VT = getVectorType(EltTy, NumElts);
321 // The common case is that we will only create one register for this
322 // value. If we have that case, create and return the virtual register.
323 unsigned NV = TLI.getNumElements(VT);
325 // If we are promoting this value, pick the next largest supported type.
326 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
327 unsigned Reg = MakeReg(PromotedType);
328 // If this is a vector of supported or promoted types (e.g. 4 x i16),
329 // create all of the registers.
330 for (unsigned i = 1; i != NumVectorRegs; ++i)
331 MakeReg(PromotedType);
335 // If this value is represented with multiple target registers, make sure
336 // to create enough consecutive registers of the right (smaller) type.
337 VT = TLI.getTypeToExpandTo(VT);
338 unsigned R = MakeReg(VT);
339 for (unsigned i = 1; i != NV*NumVectorRegs; ++i)
344 //===----------------------------------------------------------------------===//
345 /// SelectionDAGLowering - This is the common target-independent lowering
346 /// implementation that is parameterized by a TargetLowering object.
347 /// Also, targets can overload any lowering method.
350 class SelectionDAGLowering {
351 MachineBasicBlock *CurMBB;
353 DenseMap<const Value*, SDOperand> NodeMap;
355 /// PendingLoads - Loads are not emitted to the program immediately. We bunch
356 /// them up and then emit token factor nodes when possible. This allows us to
357 /// get simple disambiguation between loads without worrying about alias
359 std::vector<SDOperand> PendingLoads;
361 /// Case - A pair of values to record the Value for a switch case, and the
362 /// case's target basic block.
363 typedef std::pair<Constant*, MachineBasicBlock*> Case;
364 typedef std::vector<Case>::iterator CaseItr;
365 typedef std::pair<CaseItr, CaseItr> CaseRange;
367 /// CaseRec - A struct with ctor used in lowering switches to a binary tree
368 /// of conditional branches.
370 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) :
371 CaseBB(bb), LT(lt), GE(ge), Range(r) {}
373 /// CaseBB - The MBB in which to emit the compare and branch
374 MachineBasicBlock *CaseBB;
375 /// LT, GE - If nonzero, we know the current case value must be less-than or
376 /// greater-than-or-equal-to these Constants.
379 /// Range - A pair of iterators representing the range of case values to be
380 /// processed at this point in the binary search tree.
384 typedef std::vector<CaseRec> CaseRecVector;
386 /// The comparison function for sorting Case values.
388 bool operator () (const Case& C1, const Case& C2) {
389 assert(isa<ConstantInt>(C1.first) && isa<ConstantInt>(C2.first));
390 return cast<const ConstantInt>(C1.first)->getSExtValue() <
391 cast<const ConstantInt>(C2.first)->getSExtValue();
396 // TLI - This is information that describes the available target features we
397 // need for lowering. This indicates when operations are unavailable,
398 // implemented with a libcall, etc.
401 const TargetData *TD;
403 /// SwitchCases - Vector of CaseBlock structures used to communicate
404 /// SwitchInst code generation information.
405 std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
406 /// JTCases - Vector of JumpTable structures used to communicate
407 /// SwitchInst code generation information.
408 std::vector<SelectionDAGISel::JumpTableBlock> JTCases;
410 /// FuncInfo - Information about the function as a whole.
412 FunctionLoweringInfo &FuncInfo;
414 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
415 FunctionLoweringInfo &funcinfo)
416 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
420 /// getRoot - Return the current virtual root of the Selection DAG.
422 SDOperand getRoot() {
423 if (PendingLoads.empty())
424 return DAG.getRoot();
426 if (PendingLoads.size() == 1) {
427 SDOperand Root = PendingLoads[0];
429 PendingLoads.clear();
433 // Otherwise, we have to make a token factor node.
434 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
435 &PendingLoads[0], PendingLoads.size());
436 PendingLoads.clear();
441 SDOperand CopyValueToVirtualRegister(Value *V, unsigned Reg);
443 void visit(Instruction &I) { visit(I.getOpcode(), I); }
445 void visit(unsigned Opcode, User &I) {
446 // Note: this doesn't use InstVisitor, because it has to work with
447 // ConstantExpr's in addition to instructions.
449 default: assert(0 && "Unknown instruction type encountered!");
451 // Build the switch statement using the Instruction.def file.
452 #define HANDLE_INST(NUM, OPCODE, CLASS) \
453 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
454 #include "llvm/Instruction.def"
458 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
460 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr,
461 const Value *SV, SDOperand Root,
464 SDOperand getIntPtrConstant(uint64_t Val) {
465 return DAG.getConstant(Val, TLI.getPointerTy());
468 SDOperand getValue(const Value *V);
470 void setValue(const Value *V, SDOperand NewN) {
471 SDOperand &N = NodeMap[V];
472 assert(N.Val == 0 && "Already set a value for this node!");
476 RegsForValue GetRegistersForValue(const std::string &ConstrCode,
478 bool OutReg, bool InReg,
479 std::set<unsigned> &OutputRegs,
480 std::set<unsigned> &InputRegs);
482 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
483 MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
485 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
486 void ExportFromCurrentBlock(Value *V);
487 void LowerCallTo(Instruction &I,
488 const Type *CalledValueTy, unsigned CallingConv,
489 bool IsTailCall, SDOperand Callee, unsigned OpIdx);
491 // Terminator instructions.
492 void visitRet(ReturnInst &I);
493 void visitBr(BranchInst &I);
494 void visitSwitch(SwitchInst &I);
495 void visitUnreachable(UnreachableInst &I) { /* noop */ }
497 // Helpers for visitSwitch
498 bool handleSmallSwitchRange(CaseRec& CR,
499 CaseRecVector& WorkList,
501 MachineBasicBlock* Default);
502 bool handleJTSwitchCase(CaseRec& CR,
503 CaseRecVector& WorkList,
505 MachineBasicBlock* Default);
506 bool handleBTSplitSwitchCase(CaseRec& CR,
507 CaseRecVector& WorkList,
509 MachineBasicBlock* Default);
510 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
511 void visitJumpTable(SelectionDAGISel::JumpTable &JT);
512 void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
513 SelectionDAGISel::JumpTableHeader &JTH);
515 // These all get lowered before this pass.
516 void visitInvoke(InvokeInst &I);
517 void visitInvoke(InvokeInst &I, bool AsTerminator);
518 void visitUnwind(UnwindInst &I);
520 void visitScalarBinary(User &I, unsigned OpCode);
521 void visitVectorBinary(User &I, unsigned OpCode);
522 void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp);
523 void visitShift(User &I, unsigned Opcode);
524 void visitAdd(User &I) {
525 if (isa<VectorType>(I.getType()))
526 visitVectorBinary(I, ISD::VADD);
527 else if (I.getType()->isFloatingPoint())
528 visitScalarBinary(I, ISD::FADD);
530 visitScalarBinary(I, ISD::ADD);
532 void visitSub(User &I);
533 void visitMul(User &I) {
534 if (isa<VectorType>(I.getType()))
535 visitVectorBinary(I, ISD::VMUL);
536 else if (I.getType()->isFloatingPoint())
537 visitScalarBinary(I, ISD::FMUL);
539 visitScalarBinary(I, ISD::MUL);
541 void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); }
542 void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); }
543 void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); }
544 void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); }
545 void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); }
546 void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); }
547 void visitAnd (User &I) { visitEitherBinary(I, ISD::AND, ISD::VAND ); }
548 void visitOr (User &I) { visitEitherBinary(I, ISD::OR, ISD::VOR ); }
549 void visitXor (User &I) { visitEitherBinary(I, ISD::XOR, ISD::VXOR ); }
550 void visitShl (User &I) { visitShift(I, ISD::SHL); }
551 void visitLShr(User &I) { visitShift(I, ISD::SRL); }
552 void visitAShr(User &I) { visitShift(I, ISD::SRA); }
553 void visitICmp(User &I);
554 void visitFCmp(User &I);
555 // Visit the conversion instructions
556 void visitTrunc(User &I);
557 void visitZExt(User &I);
558 void visitSExt(User &I);
559 void visitFPTrunc(User &I);
560 void visitFPExt(User &I);
561 void visitFPToUI(User &I);
562 void visitFPToSI(User &I);
563 void visitUIToFP(User &I);
564 void visitSIToFP(User &I);
565 void visitPtrToInt(User &I);
566 void visitIntToPtr(User &I);
567 void visitBitCast(User &I);
569 void visitExtractElement(User &I);
570 void visitInsertElement(User &I);
571 void visitShuffleVector(User &I);
573 void visitGetElementPtr(User &I);
574 void visitSelect(User &I);
576 void visitMalloc(MallocInst &I);
577 void visitFree(FreeInst &I);
578 void visitAlloca(AllocaInst &I);
579 void visitLoad(LoadInst &I);
580 void visitStore(StoreInst &I);
581 void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
582 void visitCall(CallInst &I);
583 void visitInlineAsm(CallInst &I);
584 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
585 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
587 void visitVAStart(CallInst &I);
588 void visitVAArg(VAArgInst &I);
589 void visitVAEnd(CallInst &I);
590 void visitVACopy(CallInst &I);
592 void visitMemIntrinsic(CallInst &I, unsigned Op);
594 void visitUserOp1(Instruction &I) {
595 assert(0 && "UserOp1 should not exist at instruction selection time!");
598 void visitUserOp2(Instruction &I) {
599 assert(0 && "UserOp2 should not exist at instruction selection time!");
603 } // end namespace llvm
605 SDOperand SelectionDAGLowering::getValue(const Value *V) {
606 SDOperand &N = NodeMap[V];
609 const Type *VTy = V->getType();
610 MVT::ValueType VT = TLI.getValueType(VTy);
611 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
612 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
613 visit(CE->getOpcode(), *CE);
614 SDOperand N1 = NodeMap[V];
615 assert(N1.Val && "visit didn't populate the ValueMap!");
617 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
618 return N = DAG.getGlobalAddress(GV, VT);
619 } else if (isa<ConstantPointerNull>(C)) {
620 return N = DAG.getConstant(0, TLI.getPointerTy());
621 } else if (isa<UndefValue>(C)) {
622 if (!isa<VectorType>(VTy))
623 return N = DAG.getNode(ISD::UNDEF, VT);
625 // Create a VBUILD_VECTOR of undef nodes.
626 const VectorType *PTy = cast<VectorType>(VTy);
627 unsigned NumElements = PTy->getNumElements();
628 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
630 SmallVector<SDOperand, 8> Ops;
631 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT));
633 // Create a VConstant node with generic Vector type.
634 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
635 Ops.push_back(DAG.getValueType(PVT));
636 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
637 &Ops[0], Ops.size());
638 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
639 return N = DAG.getConstantFP(CFP->getValue(), VT);
640 } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) {
641 unsigned NumElements = PTy->getNumElements();
642 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
644 // Now that we know the number and type of the elements, push a
645 // Constant or ConstantFP node onto the ops list for each element of
646 // the packed constant.
647 SmallVector<SDOperand, 8> Ops;
648 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
649 for (unsigned i = 0; i != NumElements; ++i)
650 Ops.push_back(getValue(CP->getOperand(i)));
652 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
654 if (MVT::isFloatingPoint(PVT))
655 Op = DAG.getConstantFP(0, PVT);
657 Op = DAG.getConstant(0, PVT);
658 Ops.assign(NumElements, Op);
661 // Create a VBUILD_VECTOR node with generic Vector type.
662 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
663 Ops.push_back(DAG.getValueType(PVT));
664 return NodeMap[V] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0],
667 // Canonicalize all constant ints to be unsigned.
668 return N = DAG.getConstant(cast<ConstantInt>(C)->getZExtValue(),VT);
672 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
673 std::map<const AllocaInst*, int>::iterator SI =
674 FuncInfo.StaticAllocaMap.find(AI);
675 if (SI != FuncInfo.StaticAllocaMap.end())
676 return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
679 unsigned InReg = FuncInfo.ValueMap[V];
680 assert(InReg && "Value not in map!");
682 // If this type is not legal, make it so now.
683 if (VT != MVT::Vector) {
684 if (TLI.getTypeAction(VT) == TargetLowering::Expand) {
685 // Source must be expanded. This input value is actually coming from the
686 // register pair InReg and InReg+1.
687 MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
688 unsigned NumVals = TLI.getNumElements(VT);
689 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
691 N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
693 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
694 N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
695 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
698 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
699 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
700 if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case
701 N = MVT::isFloatingPoint(VT)
702 ? DAG.getNode(ISD::FP_ROUND, VT, N)
703 : DAG.getNode(ISD::TRUNCATE, VT, N);
706 // Otherwise, if this is a vector, make it available as a generic vector
708 MVT::ValueType PTyElementVT, PTyLegalElementVT;
709 const VectorType *PTy = cast<VectorType>(VTy);
710 unsigned NE = TLI.getVectorTypeBreakdown(PTy, PTyElementVT,
713 // Build a VBUILD_VECTOR with the input registers.
714 SmallVector<SDOperand, 8> Ops;
715 if (PTyElementVT == PTyLegalElementVT) {
716 // If the value types are legal, just VBUILD the CopyFromReg nodes.
717 for (unsigned i = 0; i != NE; ++i)
718 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
720 } else if (PTyElementVT < PTyLegalElementVT) {
721 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate.
722 for (unsigned i = 0; i != NE; ++i) {
723 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
725 if (MVT::isFloatingPoint(PTyElementVT))
726 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
728 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op);
732 // If the register was expanded, use BUILD_PAIR.
733 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!");
734 for (unsigned i = 0; i != NE/2; ++i) {
735 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
737 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
739 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1));
743 Ops.push_back(DAG.getConstant(NE, MVT::i32));
744 Ops.push_back(DAG.getValueType(PTyLegalElementVT));
745 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
747 // Finally, use a VBIT_CONVERT to make this available as the appropriate
749 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
750 DAG.getConstant(PTy->getNumElements(),
752 DAG.getValueType(TLI.getValueType(PTy->getElementType())));
759 void SelectionDAGLowering::visitRet(ReturnInst &I) {
760 if (I.getNumOperands() == 0) {
761 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
764 SmallVector<SDOperand, 8> NewValues;
765 NewValues.push_back(getRoot());
766 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
767 SDOperand RetOp = getValue(I.getOperand(i));
769 // If this is an integer return value, we need to promote it ourselves to
770 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
772 // FIXME: C calling convention requires the return type to be promoted to
773 // at least 32-bit. But this is not necessary for non-C calling conventions.
774 if (MVT::isInteger(RetOp.getValueType()) &&
775 RetOp.getValueType() < MVT::i64) {
776 MVT::ValueType TmpVT;
777 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
778 TmpVT = TLI.getTypeToTransformTo(MVT::i32);
781 const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
782 ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
783 if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
784 ExtendKind = ISD::SIGN_EXTEND;
785 if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
786 ExtendKind = ISD::ZERO_EXTEND;
787 RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
789 NewValues.push_back(RetOp);
790 NewValues.push_back(DAG.getConstant(false, MVT::i32));
792 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
793 &NewValues[0], NewValues.size()));
796 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
797 /// the current basic block, add it to ValueMap now so that we'll get a
799 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
800 // No need to export constants.
801 if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
804 if (FuncInfo.isExportedInst(V)) return;
806 unsigned Reg = FuncInfo.InitializeRegForValue(V);
807 PendingLoads.push_back(CopyValueToVirtualRegister(V, Reg));
810 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
811 const BasicBlock *FromBB) {
812 // The operands of the setcc have to be in this block. We don't know
813 // how to export them from some other block.
814 if (Instruction *VI = dyn_cast<Instruction>(V)) {
815 // Can export from current BB.
816 if (VI->getParent() == FromBB)
819 // Is already exported, noop.
820 return FuncInfo.isExportedInst(V);
823 // If this is an argument, we can export it if the BB is the entry block or
824 // if it is already exported.
825 if (isa<Argument>(V)) {
826 if (FromBB == &FromBB->getParent()->getEntryBlock())
829 // Otherwise, can only export this if it is already exported.
830 return FuncInfo.isExportedInst(V);
833 // Otherwise, constants can always be exported.
837 static bool InBlock(const Value *V, const BasicBlock *BB) {
838 if (const Instruction *I = dyn_cast<Instruction>(V))
839 return I->getParent() == BB;
843 /// FindMergedConditions - If Cond is an expression like
844 void SelectionDAGLowering::FindMergedConditions(Value *Cond,
845 MachineBasicBlock *TBB,
846 MachineBasicBlock *FBB,
847 MachineBasicBlock *CurBB,
849 // If this node is not part of the or/and tree, emit it as a branch.
850 Instruction *BOp = dyn_cast<Instruction>(Cond);
852 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
853 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
854 BOp->getParent() != CurBB->getBasicBlock() ||
855 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
856 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
857 const BasicBlock *BB = CurBB->getBasicBlock();
859 // If the leaf of the tree is a comparison, merge the condition into
861 if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) &&
862 // The operands of the cmp have to be in this block. We don't know
863 // how to export them from some other block. If this is the first block
864 // of the sequence, no exporting is needed.
866 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
867 isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) {
868 BOp = cast<Instruction>(Cond);
869 ISD::CondCode Condition;
870 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
871 switch (IC->getPredicate()) {
872 default: assert(0 && "Unknown icmp predicate opcode!");
873 case ICmpInst::ICMP_EQ: Condition = ISD::SETEQ; break;
874 case ICmpInst::ICMP_NE: Condition = ISD::SETNE; break;
875 case ICmpInst::ICMP_SLE: Condition = ISD::SETLE; break;
876 case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break;
877 case ICmpInst::ICMP_SGE: Condition = ISD::SETGE; break;
878 case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break;
879 case ICmpInst::ICMP_SLT: Condition = ISD::SETLT; break;
880 case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break;
881 case ICmpInst::ICMP_SGT: Condition = ISD::SETGT; break;
882 case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break;
884 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
885 ISD::CondCode FPC, FOC;
886 switch (FC->getPredicate()) {
887 default: assert(0 && "Unknown fcmp predicate opcode!");
888 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
889 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
890 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
891 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
892 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
893 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
894 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
895 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
896 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
897 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
898 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
899 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
900 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
901 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
902 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
903 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
905 if (FiniteOnlyFPMath())
910 Condition = ISD::SETEQ; // silence warning.
911 assert(0 && "Unknown compare instruction");
914 SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
915 BOp->getOperand(1), TBB, FBB, CurBB);
916 SwitchCases.push_back(CB);
920 // Create a CaseBlock record representing this branch.
921 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
923 SwitchCases.push_back(CB);
928 // Create TmpBB after CurBB.
929 MachineFunction::iterator BBI = CurBB;
930 MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock());
931 CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB);
933 if (Opc == Instruction::Or) {
942 // Emit the LHS condition.
943 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc);
945 // Emit the RHS condition into TmpBB.
946 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
948 assert(Opc == Instruction::And && "Unknown merge op!");
956 // This requires creation of TmpBB after CurBB.
958 // Emit the LHS condition.
959 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc);
961 // Emit the RHS condition into TmpBB.
962 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
966 /// If the set of cases should be emitted as a series of branches, return true.
967 /// If we should emit this as a bunch of and/or'd together conditions, return
970 ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) {
971 if (Cases.size() != 2) return true;
973 // If this is two comparisons of the same values or'd or and'd together, they
974 // will get folded into a single comparison, so don't emit two blocks.
975 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
976 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
977 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
978 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
985 void SelectionDAGLowering::visitBr(BranchInst &I) {
986 // Update machine-CFG edges.
987 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
989 // Figure out which block is immediately after the current one.
990 MachineBasicBlock *NextBlock = 0;
991 MachineFunction::iterator BBI = CurMBB;
992 if (++BBI != CurMBB->getParent()->end())
995 if (I.isUnconditional()) {
996 // If this is not a fall-through branch, emit the branch.
997 if (Succ0MBB != NextBlock)
998 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
999 DAG.getBasicBlock(Succ0MBB)));
1001 // Update machine-CFG edges.
1002 CurMBB->addSuccessor(Succ0MBB);
1007 // If this condition is one of the special cases we handle, do special stuff
1009 Value *CondVal = I.getCondition();
1010 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1012 // If this is a series of conditions that are or'd or and'd together, emit
1013 // this as a sequence of branches instead of setcc's with and/or operations.
1014 // For example, instead of something like:
1027 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1028 if (BOp->hasOneUse() &&
1029 (BOp->getOpcode() == Instruction::And ||
1030 BOp->getOpcode() == Instruction::Or)) {
1031 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode());
1032 // If the compares in later blocks need to use values not currently
1033 // exported from this block, export them now. This block should always
1034 // be the first entry.
1035 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!");
1037 // Allow some cases to be rejected.
1038 if (ShouldEmitAsBranches(SwitchCases)) {
1039 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1040 ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1041 ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1044 // Emit the branch for this block.
1045 visitSwitchCase(SwitchCases[0]);
1046 SwitchCases.erase(SwitchCases.begin());
1050 // Okay, we decided not to do this, remove any inserted MBB's and clear
1052 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1053 CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB);
1055 SwitchCases.clear();
1059 // Create a CaseBlock record representing this branch.
1060 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
1061 Succ0MBB, Succ1MBB, CurMBB);
1062 // Use visitSwitchCase to actually insert the fast branch sequence for this
1064 visitSwitchCase(CB);
1067 /// visitSwitchCase - Emits the necessary code to represent a single node in
1068 /// the binary search tree resulting from lowering a switch instruction.
1069 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
1071 SDOperand CondLHS = getValue(CB.CmpLHS);
1073 // Build the setcc now, fold "(X == true)" to X and "(X == false)" to !X to
1074 // handle common cases produced by branch lowering.
1075 if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
1077 else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
1078 SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
1079 Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
1081 Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1083 // Set NextBlock to be the MBB immediately after the current one, if any.
1084 // This is used to avoid emitting unnecessary branches to the next block.
1085 MachineBasicBlock *NextBlock = 0;
1086 MachineFunction::iterator BBI = CurMBB;
1087 if (++BBI != CurMBB->getParent()->end())
1090 // If the lhs block is the next block, invert the condition so that we can
1091 // fall through to the lhs instead of the rhs block.
1092 if (CB.TrueBB == NextBlock) {
1093 std::swap(CB.TrueBB, CB.FalseBB);
1094 SDOperand True = DAG.getConstant(1, Cond.getValueType());
1095 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
1097 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond,
1098 DAG.getBasicBlock(CB.TrueBB));
1099 if (CB.FalseBB == NextBlock)
1100 DAG.setRoot(BrCond);
1102 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1103 DAG.getBasicBlock(CB.FalseBB)));
1104 // Update successor info
1105 CurMBB->addSuccessor(CB.TrueBB);
1106 CurMBB->addSuccessor(CB.FalseBB);
1109 /// visitJumpTable - Emit JumpTable node in the current MBB
1110 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
1111 // Emit the code for the jump table
1112 assert(JT.Reg != -1UL && "Should lower JT Header first!");
1113 MVT::ValueType PTy = TLI.getPointerTy();
1114 SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
1115 SDOperand Table = DAG.getJumpTable(JT.JTI, PTy);
1116 DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1),
1121 /// visitJumpTableHeader - This function emits necessary code to produce index
1122 /// in the JumpTable from switch case.
1123 void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
1124 SelectionDAGISel::JumpTableHeader &JTH) {
1125 // Subtract the lowest switch case value from the value being switched on
1126 // and conditional branch to default mbb if the result is greater than the
1127 // difference between smallest and largest cases.
1128 SDOperand SwitchOp = getValue(JTH.SValue);
1129 MVT::ValueType VT = SwitchOp.getValueType();
1130 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1131 DAG.getConstant(JTH.First, VT));
1133 // The SDNode we just created, which holds the value being switched on
1134 // minus the the smallest case value, needs to be copied to a virtual
1135 // register so it can be used as an index into the jump table in a
1136 // subsequent basic block. This value may be smaller or larger than the
1137 // target's pointer type, and therefore require extension or truncating.
1138 if (VT > TLI.getPointerTy())
1139 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
1141 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
1143 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
1144 SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
1145 JT.Reg = JumpTableReg;
1147 // Emit the range check for the jump table, and branch to the default
1148 // block for the switch statement if the value being switched on exceeds
1149 // the largest case in the switch.
1150 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
1151 DAG.getConstant(JTH.Last-JTH.First,VT),
1154 // Set NextBlock to be the MBB immediately after the current one, if any.
1155 // This is used to avoid emitting unnecessary branches to the next block.
1156 MachineBasicBlock *NextBlock = 0;
1157 MachineFunction::iterator BBI = CurMBB;
1158 if (++BBI != CurMBB->getParent()->end())
1161 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
1162 DAG.getBasicBlock(JT.Default));
1164 if (JT.MBB == NextBlock)
1165 DAG.setRoot(BrCond);
1167 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1168 DAG.getBasicBlock(JT.MBB)));
1172 void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
1173 assert(0 && "Should never be visited directly");
1175 void SelectionDAGLowering::visitInvoke(InvokeInst &I, bool AsTerminator) {
1176 // Retrieve successors.
1177 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1178 MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1180 if (!AsTerminator) {
1181 // Mark landing pad so that it doesn't get deleted in branch folding.
1182 LandingPad->setIsLandingPad();
1184 // Insert a label before the invoke call to mark the try range.
1185 // This can be used to detect deletion of the invoke via the
1186 // MachineModuleInfo.
1187 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
1188 unsigned BeginLabel = MMI->NextLabelID();
1189 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1190 DAG.getConstant(BeginLabel, MVT::i32)));
1192 LowerCallTo(I, I.getCalledValue()->getType(),
1195 getValue(I.getOperand(0)),
1198 // Insert a label before the invoke call to mark the try range.
1199 // This can be used to detect deletion of the invoke via the
1200 // MachineModuleInfo.
1201 unsigned EndLabel = MMI->NextLabelID();
1202 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1203 DAG.getConstant(EndLabel, MVT::i32)));
1205 // Inform MachineModuleInfo of range.
1206 MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
1208 // Update successor info
1209 CurMBB->addSuccessor(Return);
1210 CurMBB->addSuccessor(LandingPad);
1212 // Drop into normal successor.
1213 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1214 DAG.getBasicBlock(Return)));
1218 void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
1221 /// handleSmaaSwitchCaseRange - Emit a series of specific tests (suitable for
1222 /// small case ranges).
1223 bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
1224 CaseRecVector& WorkList,
1226 MachineBasicBlock* Default) {
1227 Case& BackCase = *(CR.Range.second-1);
1229 // Size is the number of Cases represented by this range.
1230 unsigned Size = CR.Range.second - CR.Range.first;
1234 // Get the MachineFunction which holds the current MBB. This is used when
1235 // inserting any additional MBBs necessary to represent the switch.
1236 MachineFunction *CurMF = CurMBB->getParent();
1238 // Figure out which block is immediately after the current one.
1239 MachineBasicBlock *NextBlock = 0;
1240 MachineFunction::iterator BBI = CR.CaseBB;
1242 if (++BBI != CurMBB->getParent()->end())
1245 // TODO: If any two of the cases has the same destination, and if one value
1246 // is the same as the other, but has one bit unset that the other has set,
1247 // use bit manipulation to do two compares at once. For example:
1248 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
1250 // Rearrange the case blocks so that the last one falls through if possible.
1251 if (NextBlock && Default != NextBlock && BackCase.second != NextBlock) {
1252 // The last case block won't fall through into 'NextBlock' if we emit the
1253 // branches in this order. See if rearranging a case value would help.
1254 for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
1255 if (I->second == NextBlock) {
1256 std::swap(*I, BackCase);
1262 // Create a CaseBlock record representing a conditional branch to
1263 // the Case's target mbb if the value being switched on SV is equal
1265 MachineBasicBlock *CurBlock = CR.CaseBB;
1266 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
1267 MachineBasicBlock *FallThrough;
1269 FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock());
1270 CurMF->getBasicBlockList().insert(BBI, FallThrough);
1272 // If the last case doesn't match, go to the default block.
1273 FallThrough = Default;
1276 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, I->first,
1277 I->second, FallThrough, CurBlock);
1279 // If emitting the first comparison, just call visitSwitchCase to emit the
1280 // code into the current block. Otherwise, push the CaseBlock onto the
1281 // vector to be later processed by SDISel, and insert the node's MBB
1282 // before the next MBB.
1283 if (CurBlock == CurMBB)
1284 visitSwitchCase(CB);
1286 SwitchCases.push_back(CB);
1288 CurBlock = FallThrough;
1294 /// handleJTSwitchCase - Emit jumptable for current switch case range
1295 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
1296 CaseRecVector& WorkList,
1298 MachineBasicBlock* Default) {
1299 Case& FrontCase = *CR.Range.first;
1300 Case& BackCase = *(CR.Range.second-1);
1302 // Size is the number of Cases represented by this range.
1303 unsigned Size = CR.Range.second - CR.Range.first;
1305 uint64_t First = cast<ConstantInt>(FrontCase.first)->getSExtValue();
1306 uint64_t Last = cast<ConstantInt>(BackCase.first)->getSExtValue();
1308 if ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
1309 !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
1313 double Density = (double)Size / (double)((Last - First) + 1ULL);
1314 if (Density < 0.3125)
1317 // Get the MachineFunction which holds the current MBB. This is used when
1318 // inserting any additional MBBs necessary to represent the switch.
1319 MachineFunction *CurMF = CurMBB->getParent();
1321 // Figure out which block is immediately after the current one.
1322 MachineBasicBlock *NextBlock = 0;
1323 MachineFunction::iterator BBI = CR.CaseBB;
1325 if (++BBI != CurMBB->getParent()->end())
1328 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1330 // Create a new basic block to hold the code for loading the address
1331 // of the jump table, and jumping to it. Update successor information;
1332 // we will either branch to the default case for the switch, or the jump
1334 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
1335 CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
1336 CR.CaseBB->addSuccessor(Default);
1337 CR.CaseBB->addSuccessor(JumpTableBB);
1339 // Build a vector of destination BBs, corresponding to each target
1340 // of the jump table. If the value of the jump table slot corresponds to
1341 // a case statement, push the case's BB onto the vector, otherwise, push
1343 std::vector<MachineBasicBlock*> DestBBs;
1344 int64_t TEI = First;
1345 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI)
1346 if (cast<ConstantInt>(I->first)->getSExtValue() == TEI) {
1347 DestBBs.push_back(I->second);
1350 DestBBs.push_back(Default);
1353 // Update successor info. Add one edge to each unique successor.
1354 // Vector bool would be better, but vector<bool> is really slow.
1355 std::vector<unsigned char> SuccsHandled;
1356 SuccsHandled.resize(CR.CaseBB->getParent()->getNumBlockIDs());
1358 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
1359 E = DestBBs.end(); I != E; ++I) {
1360 if (!SuccsHandled[(*I)->getNumber()]) {
1361 SuccsHandled[(*I)->getNumber()] = true;
1362 JumpTableBB->addSuccessor(*I);
1366 // Create a jump table index for this jump table, or return an existing
1368 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
1370 // Set the jump table information so that we can codegen it as a second
1371 // MachineBasicBlock
1372 SelectionDAGISel::JumpTable JT(-1UL, JTI, JumpTableBB, Default);
1373 SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
1374 (CR.CaseBB == CurMBB));
1375 if (CR.CaseBB == CurMBB)
1376 visitJumpTableHeader(JT, JTH);
1378 JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT));
1383 /// handleBTSplitSwitchCase - emit comparison and split binary search tree into
1385 bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
1386 CaseRecVector& WorkList,
1388 MachineBasicBlock* Default) {
1389 // Get the MachineFunction which holds the current MBB. This is used when
1390 // inserting any additional MBBs necessary to represent the switch.
1391 MachineFunction *CurMF = CurMBB->getParent();
1393 // Figure out which block is immediately after the current one.
1394 MachineBasicBlock *NextBlock = 0;
1395 MachineFunction::iterator BBI = CR.CaseBB;
1397 if (++BBI != CurMBB->getParent()->end())
1400 Case& FrontCase = *CR.Range.first;
1401 Case& BackCase = *(CR.Range.second-1);
1402 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1404 // Size is the number of Cases represented by this range.
1405 unsigned Size = CR.Range.second - CR.Range.first;
1407 uint64_t First = cast<ConstantInt>(FrontCase.first)->getSExtValue();
1408 uint64_t Last = cast<ConstantInt>(BackCase.first)->getSExtValue();
1412 // Select optimal pivot, maximizing sum density of LHS and RHS. This will
1413 // (heuristically) allow us to emit JumpTable's later.
1415 unsigned RSize = Size-1;
1416 for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
1417 J!=E; ++I, ++J, ++LSize, --RSize) {
1418 uint64_t LEnd = cast<ConstantInt>(I->first)->getSExtValue();
1419 uint64_t RBegin = cast<ConstantInt>(J->first)->getSExtValue();
1420 double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL);
1421 double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL);
1422 if (Density < (LDensity + RDensity)) {
1424 Density = LDensity + RDensity;
1428 CaseRange LHSR(CR.Range.first, Pivot);
1429 CaseRange RHSR(Pivot, CR.Range.second);
1430 Constant *C = Pivot->first;
1431 MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
1433 // We know that we branch to the LHS if the Value being switched on is
1434 // less than the Pivot value, C. We use this to optimize our binary
1435 // tree a bit, by recognizing that if SV is greater than or equal to the
1436 // LHS's Case Value, and that Case Value is exactly one less than the
1437 // Pivot's Value, then we can branch directly to the LHS's Target,
1438 // rather than creating a leaf node for it.
1439 if ((LHSR.second - LHSR.first) == 1 &&
1440 LHSR.first->first == CR.GE &&
1441 cast<ConstantInt>(C)->getZExtValue() ==
1442 (cast<ConstantInt>(CR.GE)->getZExtValue() + 1ULL)) {
1443 TrueBB = LHSR.first->second;
1445 TrueBB = new MachineBasicBlock(LLVMBB);
1446 CurMF->getBasicBlockList().insert(BBI, TrueBB);
1447 WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
1450 // Similar to the optimization above, if the Value being switched on is
1451 // known to be less than the Constant CR.LT, and the current Case Value
1452 // is CR.LT - 1, then we can branch directly to the target block for
1453 // the current Case Value, rather than emitting a RHS leaf node for it.
1454 if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
1455 cast<ConstantInt>(RHSR.first->first)->getZExtValue() ==
1456 (cast<ConstantInt>(CR.LT)->getZExtValue() - 1ULL)) {
1457 FalseBB = RHSR.first->second;
1459 FalseBB = new MachineBasicBlock(LLVMBB);
1460 CurMF->getBasicBlockList().insert(BBI, FalseBB);
1461 WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
1464 // Create a CaseBlock record representing a conditional branch to
1465 // the LHS node if the value being switched on SV is less than C.
1466 // Otherwise, branch to LHS.
1467 SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, TrueBB, FalseBB,
1470 if (CR.CaseBB == CurMBB)
1471 visitSwitchCase(CB);
1473 SwitchCases.push_back(CB);
1478 void SelectionDAGLowering::visitSwitch(SwitchInst &I) {
1479 // Figure out which block is immediately after the current one.
1480 MachineBasicBlock *NextBlock = 0;
1481 MachineFunction::iterator BBI = CurMBB;
1483 MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()];
1485 // If there is only the default destination, branch to it if it is not the
1486 // next basic block. Otherwise, just fall through.
1487 if (I.getNumOperands() == 2) {
1488 // Update machine-CFG edges.
1490 // If this is not a fall-through branch, emit the branch.
1491 if (Default != NextBlock)
1492 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1493 DAG.getBasicBlock(Default)));
1495 CurMBB->addSuccessor(Default);
1499 // If there are any non-default case statements, create a vector of Cases
1500 // representing each one, and sort the vector so that we can efficiently
1501 // create a binary search tree from them.
1502 std::vector<Case> Cases;
1504 for (unsigned i = 1; i < I.getNumSuccessors(); ++i) {
1505 MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)];
1506 Cases.push_back(Case(I.getSuccessorValue(i), SMBB));
1508 std::sort(Cases.begin(), Cases.end(), CaseCmp());
1510 // Get the Value to be switched on and default basic blocks, which will be
1511 // inserted into CaseBlock records, representing basic blocks in the binary
1513 Value *SV = I.getOperand(0);
1515 // Push the initial CaseRec onto the worklist
1516 CaseRecVector WorkList;
1517 WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
1519 while (!WorkList.empty()) {
1520 // Grab a record representing a case range to process off the worklist
1521 CaseRec CR = WorkList.back();
1522 WorkList.pop_back();
1524 // If the range has few cases (two or less) emit a series of specific
1526 if (handleSmallSwitchRange(CR, WorkList, SV, Default))
1529 // If the switch has more than 5 blocks, and at least 31.25% dense, and the
1530 // target supports indirect branches, then emit a jump table rather than
1531 // lowering the switch to a binary tree of conditional branches.
1532 if (handleJTSwitchCase(CR, WorkList, SV, Default))
1535 // Emit binary tree. We need to pick a pivot, and push left and right ranges
1536 // onto the worklist. Leafs are handled via handleSmallSwitchRange() call.
1537 handleBTSplitSwitchCase(CR, WorkList, SV, Default);
1542 void SelectionDAGLowering::visitSub(User &I) {
1543 // -0.0 - X --> fneg
1544 const Type *Ty = I.getType();
1545 if (isa<VectorType>(Ty)) {
1546 visitVectorBinary(I, ISD::VSUB);
1547 } else if (Ty->isFloatingPoint()) {
1548 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
1549 if (CFP->isExactlyValue(-0.0)) {
1550 SDOperand Op2 = getValue(I.getOperand(1));
1551 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
1554 visitScalarBinary(I, ISD::FSUB);
1556 visitScalarBinary(I, ISD::SUB);
1559 void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) {
1560 SDOperand Op1 = getValue(I.getOperand(0));
1561 SDOperand Op2 = getValue(I.getOperand(1));
1563 setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
1567 SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) {
1568 assert(isa<VectorType>(I.getType()));
1569 const VectorType *Ty = cast<VectorType>(I.getType());
1570 SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType()));
1572 setValue(&I, DAG.getNode(OpCode, MVT::Vector,
1573 getValue(I.getOperand(0)),
1574 getValue(I.getOperand(1)),
1575 DAG.getConstant(Ty->getNumElements(), MVT::i32),
1579 void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp,
1580 unsigned VectorOp) {
1581 if (isa<VectorType>(I.getType()))
1582 visitVectorBinary(I, VectorOp);
1584 visitScalarBinary(I, ScalarOp);
1587 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
1588 SDOperand Op1 = getValue(I.getOperand(0));
1589 SDOperand Op2 = getValue(I.getOperand(1));
1591 if (TLI.getShiftAmountTy() < Op2.getValueType())
1592 Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
1593 else if (TLI.getShiftAmountTy() > Op2.getValueType())
1594 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
1596 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
1599 void SelectionDAGLowering::visitICmp(User &I) {
1600 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
1601 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I))
1602 predicate = IC->getPredicate();
1603 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
1604 predicate = ICmpInst::Predicate(IC->getPredicate());
1605 SDOperand Op1 = getValue(I.getOperand(0));
1606 SDOperand Op2 = getValue(I.getOperand(1));
1607 ISD::CondCode Opcode;
1608 switch (predicate) {
1609 case ICmpInst::ICMP_EQ : Opcode = ISD::SETEQ; break;
1610 case ICmpInst::ICMP_NE : Opcode = ISD::SETNE; break;
1611 case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
1612 case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
1613 case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
1614 case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
1615 case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
1616 case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
1617 case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
1618 case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
1620 assert(!"Invalid ICmp predicate value");
1621 Opcode = ISD::SETEQ;
1624 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
1627 void SelectionDAGLowering::visitFCmp(User &I) {
1628 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
1629 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I))
1630 predicate = FC->getPredicate();
1631 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
1632 predicate = FCmpInst::Predicate(FC->getPredicate());
1633 SDOperand Op1 = getValue(I.getOperand(0));
1634 SDOperand Op2 = getValue(I.getOperand(1));
1635 ISD::CondCode Condition, FOC, FPC;
1636 switch (predicate) {
1637 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
1638 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
1639 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
1640 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
1641 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
1642 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
1643 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
1644 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
1645 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
1646 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
1647 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
1648 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
1649 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
1650 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
1651 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
1652 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
1654 assert(!"Invalid FCmp predicate value");
1655 FOC = FPC = ISD::SETFALSE;
1658 if (FiniteOnlyFPMath())
1662 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition));
1665 void SelectionDAGLowering::visitSelect(User &I) {
1666 SDOperand Cond = getValue(I.getOperand(0));
1667 SDOperand TrueVal = getValue(I.getOperand(1));
1668 SDOperand FalseVal = getValue(I.getOperand(2));
1669 if (!isa<VectorType>(I.getType())) {
1670 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
1671 TrueVal, FalseVal));
1673 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal,
1674 *(TrueVal.Val->op_end()-2),
1675 *(TrueVal.Val->op_end()-1)));
1680 void SelectionDAGLowering::visitTrunc(User &I) {
1681 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
1682 SDOperand N = getValue(I.getOperand(0));
1683 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1684 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1687 void SelectionDAGLowering::visitZExt(User &I) {
1688 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1689 // ZExt also can't be a cast to bool for same reason. So, nothing much to do
1690 SDOperand N = getValue(I.getOperand(0));
1691 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1692 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1695 void SelectionDAGLowering::visitSExt(User &I) {
1696 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1697 // SExt also can't be a cast to bool for same reason. So, nothing much to do
1698 SDOperand N = getValue(I.getOperand(0));
1699 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1700 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N));
1703 void SelectionDAGLowering::visitFPTrunc(User &I) {
1704 // FPTrunc is never a no-op cast, no need to check
1705 SDOperand N = getValue(I.getOperand(0));
1706 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1707 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N));
1710 void SelectionDAGLowering::visitFPExt(User &I){
1711 // FPTrunc is never a no-op cast, no need to check
1712 SDOperand N = getValue(I.getOperand(0));
1713 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1714 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N));
1717 void SelectionDAGLowering::visitFPToUI(User &I) {
1718 // FPToUI is never a no-op cast, no need to check
1719 SDOperand N = getValue(I.getOperand(0));
1720 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1721 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N));
1724 void SelectionDAGLowering::visitFPToSI(User &I) {
1725 // FPToSI is never a no-op cast, no need to check
1726 SDOperand N = getValue(I.getOperand(0));
1727 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1728 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N));
1731 void SelectionDAGLowering::visitUIToFP(User &I) {
1732 // UIToFP is never a no-op cast, no need to check
1733 SDOperand N = getValue(I.getOperand(0));
1734 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1735 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N));
1738 void SelectionDAGLowering::visitSIToFP(User &I){
1739 // UIToFP is never a no-op cast, no need to check
1740 SDOperand N = getValue(I.getOperand(0));
1741 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1742 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N));
1745 void SelectionDAGLowering::visitPtrToInt(User &I) {
1746 // What to do depends on the size of the integer and the size of the pointer.
1747 // We can either truncate, zero extend, or no-op, accordingly.
1748 SDOperand N = getValue(I.getOperand(0));
1749 MVT::ValueType SrcVT = N.getValueType();
1750 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1752 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1753 Result = DAG.getNode(ISD::TRUNCATE, DestVT, N);
1755 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1756 Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N);
1757 setValue(&I, Result);
1760 void SelectionDAGLowering::visitIntToPtr(User &I) {
1761 // What to do depends on the size of the integer and the size of the pointer.
1762 // We can either truncate, zero extend, or no-op, accordingly.
1763 SDOperand N = getValue(I.getOperand(0));
1764 MVT::ValueType SrcVT = N.getValueType();
1765 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1766 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1767 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1769 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1770 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1773 void SelectionDAGLowering::visitBitCast(User &I) {
1774 SDOperand N = getValue(I.getOperand(0));
1775 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1776 if (DestVT == MVT::Vector) {
1777 // This is a cast to a vector from something else.
1778 // Get information about the output vector.
1779 const VectorType *DestTy = cast<VectorType>(I.getType());
1780 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
1781 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N,
1782 DAG.getConstant(DestTy->getNumElements(),MVT::i32),
1783 DAG.getValueType(EltVT)));
1786 MVT::ValueType SrcVT = N.getValueType();
1787 if (SrcVT == MVT::Vector) {
1788 // This is a cast from a vctor to something else.
1789 // Get information about the input vector.
1790 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N));
1794 // BitCast assures us that source and destination are the same size so this
1795 // is either a BIT_CONVERT or a no-op.
1796 if (DestVT != N.getValueType())
1797 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types
1799 setValue(&I, N); // noop cast.
1802 void SelectionDAGLowering::visitInsertElement(User &I) {
1803 SDOperand InVec = getValue(I.getOperand(0));
1804 SDOperand InVal = getValue(I.getOperand(1));
1805 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1806 getValue(I.getOperand(2)));
1808 SDOperand Num = *(InVec.Val->op_end()-2);
1809 SDOperand Typ = *(InVec.Val->op_end()-1);
1810 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector,
1811 InVec, InVal, InIdx, Num, Typ));
1814 void SelectionDAGLowering::visitExtractElement(User &I) {
1815 SDOperand InVec = getValue(I.getOperand(0));
1816 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1817 getValue(I.getOperand(1)));
1818 SDOperand Typ = *(InVec.Val->op_end()-1);
1819 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT,
1820 TLI.getValueType(I.getType()), InVec, InIdx));
1823 void SelectionDAGLowering::visitShuffleVector(User &I) {
1824 SDOperand V1 = getValue(I.getOperand(0));
1825 SDOperand V2 = getValue(I.getOperand(1));
1826 SDOperand Mask = getValue(I.getOperand(2));
1828 SDOperand Num = *(V1.Val->op_end()-2);
1829 SDOperand Typ = *(V2.Val->op_end()-1);
1830 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
1831 V1, V2, Mask, Num, Typ));
1835 void SelectionDAGLowering::visitGetElementPtr(User &I) {
1836 SDOperand N = getValue(I.getOperand(0));
1837 const Type *Ty = I.getOperand(0)->getType();
1839 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
1842 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1843 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
1846 uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field);
1847 N = DAG.getNode(ISD::ADD, N.getValueType(), N,
1848 getIntPtrConstant(Offset));
1850 Ty = StTy->getElementType(Field);
1852 Ty = cast<SequentialType>(Ty)->getElementType();
1854 // If this is a constant subscript, handle it quickly.
1855 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
1856 if (CI->getZExtValue() == 0) continue;
1858 TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
1859 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
1863 // N = N + Idx * ElementSize;
1864 uint64_t ElementSize = TD->getTypeSize(Ty);
1865 SDOperand IdxN = getValue(Idx);
1867 // If the index is smaller or larger than intptr_t, truncate or extend
1869 if (IdxN.getValueType() < N.getValueType()) {
1870 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
1871 } else if (IdxN.getValueType() > N.getValueType())
1872 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
1874 // If this is a multiply by a power of two, turn it into a shl
1875 // immediately. This is a very common case.
1876 if (isPowerOf2_64(ElementSize)) {
1877 unsigned Amt = Log2_64(ElementSize);
1878 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
1879 DAG.getConstant(Amt, TLI.getShiftAmountTy()));
1880 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1884 SDOperand Scale = getIntPtrConstant(ElementSize);
1885 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
1886 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1892 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
1893 // If this is a fixed sized alloca in the entry block of the function,
1894 // allocate it statically on the stack.
1895 if (FuncInfo.StaticAllocaMap.count(&I))
1896 return; // getValue will auto-populate this.
1898 const Type *Ty = I.getAllocatedType();
1899 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
1901 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
1904 SDOperand AllocSize = getValue(I.getArraySize());
1905 MVT::ValueType IntPtr = TLI.getPointerTy();
1906 if (IntPtr < AllocSize.getValueType())
1907 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
1908 else if (IntPtr > AllocSize.getValueType())
1909 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
1911 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
1912 getIntPtrConstant(TySize));
1914 // Handle alignment. If the requested alignment is less than or equal to the
1915 // stack alignment, ignore it and round the size of the allocation up to the
1916 // stack alignment size. If the size is greater than the stack alignment, we
1917 // note this in the DYNAMIC_STACKALLOC node.
1918 unsigned StackAlign =
1919 TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
1920 if (Align <= StackAlign) {
1922 // Add SA-1 to the size.
1923 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
1924 getIntPtrConstant(StackAlign-1));
1925 // Mask out the low bits for alignment purposes.
1926 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
1927 getIntPtrConstant(~(uint64_t)(StackAlign-1)));
1930 SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) };
1931 const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
1933 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3);
1935 DAG.setRoot(DSA.getValue(1));
1937 // Inform the Frame Information that we have just allocated a variable-sized
1939 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
1942 void SelectionDAGLowering::visitLoad(LoadInst &I) {
1943 SDOperand Ptr = getValue(I.getOperand(0));
1949 // Do not serialize non-volatile loads against each other.
1950 Root = DAG.getRoot();
1953 setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0),
1954 Root, I.isVolatile()));
1957 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr,
1958 const Value *SV, SDOperand Root,
1961 if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
1962 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
1963 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr,
1964 DAG.getSrcValue(SV));
1966 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile);
1970 DAG.setRoot(L.getValue(1));
1972 PendingLoads.push_back(L.getValue(1));
1978 void SelectionDAGLowering::visitStore(StoreInst &I) {
1979 Value *SrcV = I.getOperand(0);
1980 SDOperand Src = getValue(SrcV);
1981 SDOperand Ptr = getValue(I.getOperand(1));
1982 DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
1986 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
1987 /// access memory and has no other side effects at all.
1988 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) {
1989 #define GET_NO_MEMORY_INTRINSICS
1990 #include "llvm/Intrinsics.gen"
1991 #undef GET_NO_MEMORY_INTRINSICS
1995 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't
1996 // have any side-effects or if it only reads memory.
1997 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) {
1998 #define GET_SIDE_EFFECT_INFO
1999 #include "llvm/Intrinsics.gen"
2000 #undef GET_SIDE_EFFECT_INFO
2004 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
2006 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
2007 unsigned Intrinsic) {
2008 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic);
2009 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic);
2011 // Build the operand list.
2012 SmallVector<SDOperand, 8> Ops;
2013 if (HasChain) { // If this intrinsic has side-effects, chainify it.
2015 // We don't need to serialize loads against other loads.
2016 Ops.push_back(DAG.getRoot());
2018 Ops.push_back(getRoot());
2022 // Add the intrinsic ID as an integer operand.
2023 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy()));
2025 // Add all operands of the call to the operand list.
2026 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
2027 SDOperand Op = getValue(I.getOperand(i));
2029 // If this is a vector type, force it to the right vector type.
2030 if (Op.getValueType() == MVT::Vector) {
2031 const VectorType *OpTy = cast<VectorType>(I.getOperand(i)->getType());
2032 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType());
2034 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements());
2035 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?");
2036 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op);
2039 assert(TLI.isTypeLegal(Op.getValueType()) &&
2040 "Intrinsic uses a non-legal type?");
2044 std::vector<MVT::ValueType> VTs;
2045 if (I.getType() != Type::VoidTy) {
2046 MVT::ValueType VT = TLI.getValueType(I.getType());
2047 if (VT == MVT::Vector) {
2048 const VectorType *DestTy = cast<VectorType>(I.getType());
2049 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
2051 VT = MVT::getVectorType(EltVT, DestTy->getNumElements());
2052 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?");
2055 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?");
2059 VTs.push_back(MVT::Other);
2061 const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs);
2066 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(),
2067 &Ops[0], Ops.size());
2068 else if (I.getType() != Type::VoidTy)
2069 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(),
2070 &Ops[0], Ops.size());
2072 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(),
2073 &Ops[0], Ops.size());
2076 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1);
2078 PendingLoads.push_back(Chain);
2082 if (I.getType() != Type::VoidTy) {
2083 if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
2084 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType());
2085 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
2086 DAG.getConstant(PTy->getNumElements(), MVT::i32),
2087 DAG.getValueType(EVT));
2089 setValue(&I, Result);
2093 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If
2094 /// we want to emit this as a call to a named external function, return the name
2095 /// otherwise lower it and return null.
2097 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
2098 switch (Intrinsic) {
2100 // By default, turn this into a target intrinsic node.
2101 visitTargetIntrinsic(I, Intrinsic);
2103 case Intrinsic::vastart: visitVAStart(I); return 0;
2104 case Intrinsic::vaend: visitVAEnd(I); return 0;
2105 case Intrinsic::vacopy: visitVACopy(I); return 0;
2106 case Intrinsic::returnaddress:
2107 setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(),
2108 getValue(I.getOperand(1))));
2110 case Intrinsic::frameaddress:
2111 setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(),
2112 getValue(I.getOperand(1))));
2114 case Intrinsic::setjmp:
2115 return "_setjmp"+!TLI.usesUnderscoreSetJmp();
2117 case Intrinsic::longjmp:
2118 return "_longjmp"+!TLI.usesUnderscoreLongJmp();
2120 case Intrinsic::memcpy_i32:
2121 case Intrinsic::memcpy_i64:
2122 visitMemIntrinsic(I, ISD::MEMCPY);
2124 case Intrinsic::memset_i32:
2125 case Intrinsic::memset_i64:
2126 visitMemIntrinsic(I, ISD::MEMSET);
2128 case Intrinsic::memmove_i32:
2129 case Intrinsic::memmove_i64:
2130 visitMemIntrinsic(I, ISD::MEMMOVE);
2133 case Intrinsic::dbg_stoppoint: {
2134 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2135 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I);
2136 if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) {
2140 Ops[1] = getValue(SPI.getLineValue());
2141 Ops[2] = getValue(SPI.getColumnValue());
2143 DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext());
2144 assert(DD && "Not a debug information descriptor");
2145 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD);
2147 Ops[3] = DAG.getString(CompileUnit->getFileName());
2148 Ops[4] = DAG.getString(CompileUnit->getDirectory());
2150 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5));
2155 case Intrinsic::dbg_region_start: {
2156 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2157 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I);
2158 if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) {
2159 unsigned LabelID = MMI->RecordRegionStart(RSI.getContext());
2160 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2161 DAG.getConstant(LabelID, MVT::i32)));
2166 case Intrinsic::dbg_region_end: {
2167 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2168 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I);
2169 if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) {
2170 unsigned LabelID = MMI->RecordRegionEnd(REI.getContext());
2171 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2172 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2177 case Intrinsic::dbg_func_start: {
2178 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2179 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I);
2180 if (MMI && FSI.getSubprogram() &&
2181 MMI->Verify(FSI.getSubprogram())) {
2182 unsigned LabelID = MMI->RecordRegionStart(FSI.getSubprogram());
2183 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2184 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2189 case Intrinsic::dbg_declare: {
2190 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2191 DbgDeclareInst &DI = cast<DbgDeclareInst>(I);
2192 if (MMI && DI.getVariable() && MMI->Verify(DI.getVariable())) {
2193 SDOperand AddressOp = getValue(DI.getAddress());
2194 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp))
2195 MMI->RecordVariable(DI.getVariable(), FI->getIndex());
2201 case Intrinsic::eh_exception: {
2202 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2205 // Add a label to mark the beginning of the landing pad. Deletion of the
2206 // landing pad can thus be detected via the MachineModuleInfo.
2207 unsigned LabelID = MMI->addLandingPad(CurMBB);
2208 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
2209 DAG.getConstant(LabelID, MVT::i32)));
2211 // Mark exception register as live in.
2212 unsigned Reg = TLI.getExceptionAddressRegister();
2213 if (Reg) CurMBB->addLiveIn(Reg);
2215 // Insert the EXCEPTIONADDR instruction.
2216 SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
2218 Ops[0] = DAG.getRoot();
2219 SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
2221 DAG.setRoot(Op.getValue(1));
2223 setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
2228 case Intrinsic::eh_selector:
2229 case Intrinsic::eh_filter:{
2230 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2233 // Inform the MachineModuleInfo of the personality for this landing pad.
2234 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(2));
2235 assert(CE && CE->getOpcode() == Instruction::BitCast &&
2236 isa<Function>(CE->getOperand(0)) &&
2237 "Personality should be a function");
2238 MMI->addPersonality(CurMBB, cast<Function>(CE->getOperand(0)));
2239 if (Intrinsic == Intrinsic::eh_filter)
2240 MMI->setIsFilterLandingPad(CurMBB);
2242 // Gather all the type infos for this landing pad and pass them along to
2243 // MachineModuleInfo.
2244 std::vector<GlobalVariable *> TyInfo;
2245 for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
2246 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i));
2247 if (CE && CE->getOpcode() == Instruction::BitCast &&
2248 isa<GlobalVariable>(CE->getOperand(0))) {
2249 TyInfo.push_back(cast<GlobalVariable>(CE->getOperand(0)));
2251 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i));
2252 assert(CI && CI->getZExtValue() == 0 &&
2253 "TypeInfo must be a global variable typeinfo or NULL");
2254 TyInfo.push_back(NULL);
2257 MMI->addCatchTypeInfo(CurMBB, TyInfo);
2259 // Mark exception selector register as live in.
2260 unsigned Reg = TLI.getExceptionSelectorRegister();
2261 if (Reg) CurMBB->addLiveIn(Reg);
2263 // Insert the EHSELECTION instruction.
2264 SDVTList VTs = DAG.getVTList(MVT::i32, MVT::Other);
2266 Ops[0] = getValue(I.getOperand(1));
2268 SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
2270 DAG.setRoot(Op.getValue(1));
2272 setValue(&I, DAG.getConstant(0, MVT::i32));
2278 case Intrinsic::eh_typeid_for: {
2279 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2282 // Find the type id for the given typeinfo.
2283 GlobalVariable *GV = NULL;
2284 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(1));
2285 if (CE && CE->getOpcode() == Instruction::BitCast &&
2286 isa<GlobalVariable>(CE->getOperand(0))) {
2287 GV = cast<GlobalVariable>(CE->getOperand(0));
2289 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
2290 assert(CI && CI->getZExtValue() == 0 &&
2291 "TypeInfo must be a global variable typeinfo or NULL");
2295 unsigned TypeID = MMI->getTypeIDFor(GV);
2296 setValue(&I, DAG.getConstant(TypeID, MVT::i32));
2298 setValue(&I, DAG.getConstant(0, MVT::i32));
2304 case Intrinsic::sqrt_f32:
2305 case Intrinsic::sqrt_f64:
2306 setValue(&I, DAG.getNode(ISD::FSQRT,
2307 getValue(I.getOperand(1)).getValueType(),
2308 getValue(I.getOperand(1))));
2310 case Intrinsic::powi_f32:
2311 case Intrinsic::powi_f64:
2312 setValue(&I, DAG.getNode(ISD::FPOWI,
2313 getValue(I.getOperand(1)).getValueType(),
2314 getValue(I.getOperand(1)),
2315 getValue(I.getOperand(2))));
2317 case Intrinsic::pcmarker: {
2318 SDOperand Tmp = getValue(I.getOperand(1));
2319 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
2322 case Intrinsic::readcyclecounter: {
2323 SDOperand Op = getRoot();
2324 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER,
2325 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2,
2328 DAG.setRoot(Tmp.getValue(1));
2331 case Intrinsic::bswap:
2332 setValue(&I, DAG.getNode(ISD::BSWAP,
2333 getValue(I.getOperand(1)).getValueType(),
2334 getValue(I.getOperand(1))));
2336 case Intrinsic::cttz: {
2337 SDOperand Arg = getValue(I.getOperand(1));
2338 MVT::ValueType Ty = Arg.getValueType();
2339 SDOperand result = DAG.getNode(ISD::CTTZ, Ty, Arg);
2341 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2342 else if (Ty > MVT::i32)
2343 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2344 setValue(&I, result);
2347 case Intrinsic::ctlz: {
2348 SDOperand Arg = getValue(I.getOperand(1));
2349 MVT::ValueType Ty = Arg.getValueType();
2350 SDOperand result = DAG.getNode(ISD::CTLZ, Ty, Arg);
2352 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2353 else if (Ty > MVT::i32)
2354 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2355 setValue(&I, result);
2358 case Intrinsic::ctpop: {
2359 SDOperand Arg = getValue(I.getOperand(1));
2360 MVT::ValueType Ty = Arg.getValueType();
2361 SDOperand result = DAG.getNode(ISD::CTPOP, Ty, Arg);
2363 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2364 else if (Ty > MVT::i32)
2365 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2366 setValue(&I, result);
2369 case Intrinsic::stacksave: {
2370 SDOperand Op = getRoot();
2371 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
2372 DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1);
2374 DAG.setRoot(Tmp.getValue(1));
2377 case Intrinsic::stackrestore: {
2378 SDOperand Tmp = getValue(I.getOperand(1));
2379 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
2382 case Intrinsic::prefetch:
2383 // FIXME: Currently discarding prefetches.
2389 void SelectionDAGLowering::LowerCallTo(Instruction &I,
2390 const Type *CalledValueTy,
2391 unsigned CallingConv,
2393 SDOperand Callee, unsigned OpIdx) {
2394 const PointerType *PT = cast<PointerType>(CalledValueTy);
2395 const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
2397 TargetLowering::ArgListTy Args;
2398 TargetLowering::ArgListEntry Entry;
2399 Args.reserve(I.getNumOperands());
2400 for (unsigned i = OpIdx, e = I.getNumOperands(); i != e; ++i) {
2401 Value *Arg = I.getOperand(i);
2402 SDOperand ArgNode = getValue(Arg);
2403 Entry.Node = ArgNode; Entry.Ty = Arg->getType();
2404 Entry.isSExt = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
2405 Entry.isZExt = FTy->paramHasAttr(i, FunctionType::ZExtAttribute);
2406 Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
2407 Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
2408 Args.push_back(Entry);
2411 std::pair<SDOperand,SDOperand> Result =
2412 TLI.LowerCallTo(getRoot(), I.getType(),
2413 FTy->paramHasAttr(0,FunctionType::SExtAttribute),
2414 FTy->isVarArg(), CallingConv, IsTailCall,
2416 if (I.getType() != Type::VoidTy)
2417 setValue(&I, Result.first);
2418 DAG.setRoot(Result.second);
2422 void SelectionDAGLowering::visitCall(CallInst &I) {
2423 const char *RenameFn = 0;
2424 if (Function *F = I.getCalledFunction()) {
2425 if (F->isDeclaration())
2426 if (unsigned IID = F->getIntrinsicID()) {
2427 RenameFn = visitIntrinsicCall(I, IID);
2430 } else { // Not an LLVM intrinsic.
2431 const std::string &Name = F->getName();
2432 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) {
2433 if (I.getNumOperands() == 3 && // Basic sanity checks.
2434 I.getOperand(1)->getType()->isFloatingPoint() &&
2435 I.getType() == I.getOperand(1)->getType() &&
2436 I.getType() == I.getOperand(2)->getType()) {
2437 SDOperand LHS = getValue(I.getOperand(1));
2438 SDOperand RHS = getValue(I.getOperand(2));
2439 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
2443 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
2444 if (I.getNumOperands() == 2 && // Basic sanity checks.
2445 I.getOperand(1)->getType()->isFloatingPoint() &&
2446 I.getType() == I.getOperand(1)->getType()) {
2447 SDOperand Tmp = getValue(I.getOperand(1));
2448 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
2451 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
2452 if (I.getNumOperands() == 2 && // Basic sanity checks.
2453 I.getOperand(1)->getType()->isFloatingPoint() &&
2454 I.getType() == I.getOperand(1)->getType()) {
2455 SDOperand Tmp = getValue(I.getOperand(1));
2456 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
2459 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
2460 if (I.getNumOperands() == 2 && // Basic sanity checks.
2461 I.getOperand(1)->getType()->isFloatingPoint() &&
2462 I.getType() == I.getOperand(1)->getType()) {
2463 SDOperand Tmp = getValue(I.getOperand(1));
2464 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
2469 } else if (isa<InlineAsm>(I.getOperand(0))) {
2476 Callee = getValue(I.getOperand(0));
2478 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
2480 LowerCallTo(I, I.getCalledValue()->getType(),
2488 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
2489 SDOperand &Chain, SDOperand &Flag)const{
2490 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag);
2491 Chain = Val.getValue(1);
2492 Flag = Val.getValue(2);
2494 // If the result was expanded, copy from the top part.
2495 if (Regs.size() > 1) {
2496 assert(Regs.size() == 2 &&
2497 "Cannot expand to more than 2 elts yet!");
2498 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag);
2499 Chain = Hi.getValue(1);
2500 Flag = Hi.getValue(2);
2501 if (DAG.getTargetLoweringInfo().isLittleEndian())
2502 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
2504 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val);
2507 // Otherwise, if the return value was promoted or extended, truncate it to the
2508 // appropriate type.
2509 if (RegVT == ValueVT)
2512 if (MVT::isVector(RegVT)) {
2513 assert(ValueVT == MVT::Vector && "Unknown vector conversion!");
2514 return DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
2515 DAG.getConstant(MVT::getVectorNumElements(RegVT),
2517 DAG.getValueType(MVT::getVectorBaseType(RegVT)));
2520 if (MVT::isInteger(RegVT)) {
2521 if (ValueVT < RegVT)
2522 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
2524 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
2527 assert(MVT::isFloatingPoint(RegVT) && MVT::isFloatingPoint(ValueVT));
2528 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
2531 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
2532 /// specified value into the registers specified by this object. This uses
2533 /// Chain/Flag as the input and updates them for the output Chain/Flag.
2534 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
2535 SDOperand &Chain, SDOperand &Flag,
2536 MVT::ValueType PtrVT) const {
2537 if (Regs.size() == 1) {
2538 // If there is a single register and the types differ, this must be
2540 if (RegVT != ValueVT) {
2541 if (MVT::isVector(RegVT)) {
2542 assert(Val.getValueType() == MVT::Vector &&"Not a vector-vector cast?");
2543 Val = DAG.getNode(ISD::VBIT_CONVERT, RegVT, Val);
2544 } else if (MVT::isInteger(RegVT)) {
2545 if (RegVT < ValueVT)
2546 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
2548 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
2550 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
2552 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
2553 Flag = Chain.getValue(1);
2555 std::vector<unsigned> R(Regs);
2556 if (!DAG.getTargetLoweringInfo().isLittleEndian())
2557 std::reverse(R.begin(), R.end());
2559 for (unsigned i = 0, e = R.size(); i != e; ++i) {
2560 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
2561 DAG.getConstant(i, PtrVT));
2562 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
2563 Flag = Chain.getValue(1);
2568 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
2569 /// operand list. This adds the code marker and includes the number of
2570 /// values added into it.
2571 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
2572 std::vector<SDOperand> &Ops) const {
2573 Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32));
2574 for (unsigned i = 0, e = Regs.size(); i != e; ++i)
2575 Ops.push_back(DAG.getRegister(Regs[i], RegVT));
2578 /// isAllocatableRegister - If the specified register is safe to allocate,
2579 /// i.e. it isn't a stack pointer or some other special register, return the
2580 /// register class for the register. Otherwise, return null.
2581 static const TargetRegisterClass *
2582 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
2583 const TargetLowering &TLI, const MRegisterInfo *MRI) {
2584 MVT::ValueType FoundVT = MVT::Other;
2585 const TargetRegisterClass *FoundRC = 0;
2586 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
2587 E = MRI->regclass_end(); RCI != E; ++RCI) {
2588 MVT::ValueType ThisVT = MVT::Other;
2590 const TargetRegisterClass *RC = *RCI;
2591 // If none of the the value types for this register class are valid, we
2592 // can't use it. For example, 64-bit reg classes on 32-bit targets.
2593 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
2595 if (TLI.isTypeLegal(*I)) {
2596 // If we have already found this register in a different register class,
2597 // choose the one with the largest VT specified. For example, on
2598 // PowerPC, we favor f64 register classes over f32.
2599 if (FoundVT == MVT::Other ||
2600 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
2607 if (ThisVT == MVT::Other) continue;
2609 // NOTE: This isn't ideal. In particular, this might allocate the
2610 // frame pointer in functions that need it (due to them not being taken
2611 // out of allocation, because a variable sized allocation hasn't been seen
2612 // yet). This is a slight code pessimization, but should still work.
2613 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
2614 E = RC->allocation_order_end(MF); I != E; ++I)
2616 // We found a matching register class. Keep looking at others in case
2617 // we find one with larger registers that this physreg is also in.
2626 RegsForValue SelectionDAGLowering::
2627 GetRegistersForValue(const std::string &ConstrCode,
2628 MVT::ValueType VT, bool isOutReg, bool isInReg,
2629 std::set<unsigned> &OutputRegs,
2630 std::set<unsigned> &InputRegs) {
2631 std::pair<unsigned, const TargetRegisterClass*> PhysReg =
2632 TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
2633 std::vector<unsigned> Regs;
2635 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
2636 MVT::ValueType RegVT;
2637 MVT::ValueType ValueVT = VT;
2639 // If this is a constraint for a specific physical register, like {r17},
2641 if (PhysReg.first) {
2642 if (VT == MVT::Other)
2643 ValueVT = *PhysReg.second->vt_begin();
2645 // Get the actual register value type. This is important, because the user
2646 // may have asked for (e.g.) the AX register in i32 type. We need to
2647 // remember that AX is actually i16 to get the right extension.
2648 RegVT = *PhysReg.second->vt_begin();
2650 // This is a explicit reference to a physical register.
2651 Regs.push_back(PhysReg.first);
2653 // If this is an expanded reference, add the rest of the regs to Regs.
2655 TargetRegisterClass::iterator I = PhysReg.second->begin();
2656 TargetRegisterClass::iterator E = PhysReg.second->end();
2657 for (; *I != PhysReg.first; ++I)
2658 assert(I != E && "Didn't find reg!");
2660 // Already added the first reg.
2662 for (; NumRegs; --NumRegs, ++I) {
2663 assert(I != E && "Ran out of registers to allocate!");
2667 return RegsForValue(Regs, RegVT, ValueVT);
2670 // Otherwise, if this was a reference to an LLVM register class, create vregs
2671 // for this reference.
2672 std::vector<unsigned> RegClassRegs;
2673 if (PhysReg.second) {
2674 // If this is an early clobber or tied register, our regalloc doesn't know
2675 // how to maintain the constraint. If it isn't, go ahead and create vreg
2676 // and let the regalloc do the right thing.
2677 if (!isOutReg || !isInReg) {
2678 if (VT == MVT::Other)
2679 ValueVT = *PhysReg.second->vt_begin();
2680 RegVT = *PhysReg.second->vt_begin();
2682 // Create the appropriate number of virtual registers.
2683 SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
2684 for (; NumRegs; --NumRegs)
2685 Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
2687 return RegsForValue(Regs, RegVT, ValueVT);
2690 // Otherwise, we can't allocate it. Let the code below figure out how to
2691 // maintain these constraints.
2692 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
2695 // This is a reference to a register class that doesn't directly correspond
2696 // to an LLVM register class. Allocate NumRegs consecutive, available,
2697 // registers from the class.
2698 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
2701 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
2702 MachineFunction &MF = *CurMBB->getParent();
2703 unsigned NumAllocated = 0;
2704 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
2705 unsigned Reg = RegClassRegs[i];
2706 // See if this register is available.
2707 if ((isOutReg && OutputRegs.count(Reg)) || // Already used.
2708 (isInReg && InputRegs.count(Reg))) { // Already used.
2709 // Make sure we find consecutive registers.
2714 // Check to see if this register is allocatable (i.e. don't give out the
2716 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
2718 // Make sure we find consecutive registers.
2723 // Okay, this register is good, we can use it.
2726 // If we allocated enough consecutive
2727 if (NumAllocated == NumRegs) {
2728 unsigned RegStart = (i-NumAllocated)+1;
2729 unsigned RegEnd = i+1;
2730 // Mark all of the allocated registers used.
2731 for (unsigned i = RegStart; i != RegEnd; ++i) {
2732 unsigned Reg = RegClassRegs[i];
2733 Regs.push_back(Reg);
2734 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used.
2735 if (isInReg) InputRegs.insert(Reg); // Mark reg used.
2738 return RegsForValue(Regs, *RC->vt_begin(), VT);
2742 // Otherwise, we couldn't allocate enough registers for this.
2743 return RegsForValue();
2746 /// getConstraintGenerality - Return an integer indicating how general CT is.
2747 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
2749 default: assert(0 && "Unknown constraint type!");
2750 case TargetLowering::C_Other:
2751 case TargetLowering::C_Unknown:
2753 case TargetLowering::C_Register:
2755 case TargetLowering::C_RegisterClass:
2757 case TargetLowering::C_Memory:
2762 static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
2763 const TargetLowering &TLI) {
2764 assert(!C.empty() && "Must have at least one constraint");
2765 if (C.size() == 1) return C[0];
2767 std::string *Current = &C[0];
2768 // If we have multiple constraints, try to pick the most general one ahead
2769 // of time. This isn't a wonderful solution, but handles common cases.
2770 TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
2771 for (unsigned j = 1, e = C.size(); j != e; ++j) {
2772 TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
2773 if (getConstraintGenerality(ThisFlavor) >
2774 getConstraintGenerality(Flavor)) {
2775 // This constraint letter is more general than the previous one,
2777 Flavor = ThisFlavor;
2785 /// visitInlineAsm - Handle a call to an InlineAsm object.
2787 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
2788 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
2790 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
2793 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
2794 std::vector<MVT::ValueType> ConstraintVTs;
2796 /// AsmNodeOperands - A list of pairs. The first element is a register, the
2797 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
2798 /// if it is a def of that register.
2799 std::vector<SDOperand> AsmNodeOperands;
2800 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
2801 AsmNodeOperands.push_back(AsmStr);
2803 SDOperand Chain = getRoot();
2806 // We fully assign registers here at isel time. This is not optimal, but
2807 // should work. For register classes that correspond to LLVM classes, we
2808 // could let the LLVM RA do its thing, but we currently don't. Do a prepass
2809 // over the constraints, collecting fixed registers that we know we can't use.
2810 std::set<unsigned> OutputRegs, InputRegs;
2812 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2813 std::string ConstraintCode =
2814 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2816 MVT::ValueType OpVT;
2818 // Compute the value type for each operand and add it to ConstraintVTs.
2819 switch (Constraints[i].Type) {
2820 case InlineAsm::isOutput:
2821 if (!Constraints[i].isIndirectOutput) {
2822 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2823 OpVT = TLI.getValueType(I.getType());
2825 const Type *OpTy = I.getOperand(OpNum)->getType();
2826 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
2827 OpNum++; // Consumes a call operand.
2830 case InlineAsm::isInput:
2831 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
2832 OpNum++; // Consumes a call operand.
2834 case InlineAsm::isClobber:
2839 ConstraintVTs.push_back(OpVT);
2841 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
2842 continue; // Not assigned a fixed reg.
2844 // Build a list of regs that this operand uses. This always has a single
2845 // element for promoted/expanded operands.
2846 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
2848 OutputRegs, InputRegs);
2850 switch (Constraints[i].Type) {
2851 case InlineAsm::isOutput:
2852 // We can't assign any other output to this register.
2853 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2854 // If this is an early-clobber output, it cannot be assigned to the same
2855 // value as the input reg.
2856 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2857 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2859 case InlineAsm::isInput:
2860 // We can't assign any other input to this register.
2861 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2863 case InlineAsm::isClobber:
2864 // Clobbered regs cannot be used as inputs or outputs.
2865 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2866 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2871 // Loop over all of the inputs, copying the operand values into the
2872 // appropriate registers and processing the output regs.
2873 RegsForValue RetValRegs;
2874 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
2877 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2878 std::string ConstraintCode =
2879 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2881 switch (Constraints[i].Type) {
2882 case InlineAsm::isOutput: {
2883 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
2884 if (ConstraintCode.size() == 1) // not a physreg name.
2885 CTy = TLI.getConstraintType(ConstraintCode);
2887 if (CTy == TargetLowering::C_Memory) {
2889 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
2891 // Check that the operand (the address to store to) isn't a float.
2892 if (!MVT::isInteger(InOperandVal.getValueType()))
2893 assert(0 && "MATCH FAIL!");
2895 if (!Constraints[i].isIndirectOutput)
2896 assert(0 && "MATCH FAIL!");
2898 OpNum++; // Consumes a call operand.
2900 // Extend/truncate to the right pointer type if needed.
2901 MVT::ValueType PtrType = TLI.getPointerTy();
2902 if (InOperandVal.getValueType() < PtrType)
2903 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
2904 else if (InOperandVal.getValueType() > PtrType)
2905 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
2907 // Add information to the INLINEASM node to know about this output.
2908 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
2909 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
2910 AsmNodeOperands.push_back(InOperandVal);
2914 // Otherwise, this is a register output.
2915 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
2917 // If this is an early-clobber output, or if there is an input
2918 // constraint that matches this, we need to reserve the input register
2919 // so no other inputs allocate to it.
2920 bool UsesInputRegister = false;
2921 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2922 UsesInputRegister = true;
2924 // Copy the output from the appropriate register. Find a register that
2927 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
2928 true, UsesInputRegister,
2929 OutputRegs, InputRegs);
2930 if (Regs.Regs.empty()) {
2931 cerr << "Couldn't allocate output reg for contraint '"
2932 << ConstraintCode << "'!\n";
2936 if (!Constraints[i].isIndirectOutput) {
2937 assert(RetValRegs.Regs.empty() &&
2938 "Cannot have multiple output constraints yet!");
2939 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2942 IndirectStoresToEmit.push_back(std::make_pair(Regs,
2943 I.getOperand(OpNum)));
2944 OpNum++; // Consumes a call operand.
2947 // Add information to the INLINEASM node to know that this register is
2949 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
2952 case InlineAsm::isInput: {
2953 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
2954 OpNum++; // Consumes a call operand.
2956 if (isdigit(ConstraintCode[0])) { // Matching constraint?
2957 // If this is required to match an output register we have already set,
2958 // just use its register.
2959 unsigned OperandNo = atoi(ConstraintCode.c_str());
2961 // Scan until we find the definition we already emitted of this operand.
2962 // When we find it, create a RegsForValue operand.
2963 unsigned CurOp = 2; // The first operand.
2964 for (; OperandNo; --OperandNo) {
2965 // Advance to the next operand.
2967 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
2968 assert(((NumOps & 7) == 2 /*REGDEF*/ ||
2969 (NumOps & 7) == 4 /*MEM*/) &&
2970 "Skipped past definitions?");
2971 CurOp += (NumOps>>3)+1;
2975 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
2976 if ((NumOps & 7) == 2 /*REGDEF*/) {
2977 // Add NumOps>>3 registers to MatchedRegs.
2978 RegsForValue MatchedRegs;
2979 MatchedRegs.ValueVT = InOperandVal.getValueType();
2980 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType();
2981 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
2983 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
2984 MatchedRegs.Regs.push_back(Reg);
2987 // Use the produced MatchedRegs object to
2988 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
2989 TLI.getPointerTy());
2990 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
2993 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
2994 assert(0 && "matching constraints for memory operands unimp");
2998 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
2999 if (ConstraintCode.size() == 1) // not a physreg name.
3000 CTy = TLI.getConstraintType(ConstraintCode);
3002 if (CTy == TargetLowering::C_Other) {
3003 InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
3004 ConstraintCode[0], DAG);
3005 if (!InOperandVal.Val) {
3006 cerr << "Invalid operand for inline asm constraint '"
3007 << ConstraintCode << "'!\n";
3011 // Add information to the INLINEASM node to know about this input.
3012 unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
3013 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3014 AsmNodeOperands.push_back(InOperandVal);
3016 } else if (CTy == TargetLowering::C_Memory) {
3019 // If the operand is a float, spill to a constant pool entry to get its
3021 if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
3022 InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
3024 if (!MVT::isInteger(InOperandVal.getValueType())) {
3025 cerr << "Match failed, cannot handle this yet!\n";
3026 InOperandVal.Val->dump();
3030 // Extend/truncate to the right pointer type if needed.
3031 MVT::ValueType PtrType = TLI.getPointerTy();
3032 if (InOperandVal.getValueType() < PtrType)
3033 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3034 else if (InOperandVal.getValueType() > PtrType)
3035 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3037 // Add information to the INLINEASM node to know about this input.
3038 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3039 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3040 AsmNodeOperands.push_back(InOperandVal);
3044 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3046 // Copy the input into the appropriate registers.
3047 RegsForValue InRegs =
3048 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3049 false, true, OutputRegs, InputRegs);
3050 // FIXME: should be match fail.
3051 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
3053 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
3055 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
3058 case InlineAsm::isClobber: {
3059 RegsForValue ClobberedRegs =
3060 GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
3061 OutputRegs, InputRegs);
3062 // Add the clobbered value to the operand list, so that the register
3063 // allocator is aware that the physreg got clobbered.
3064 if (!ClobberedRegs.Regs.empty())
3065 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
3071 // Finish up input operands.
3072 AsmNodeOperands[0] = Chain;
3073 if (Flag.Val) AsmNodeOperands.push_back(Flag);
3075 Chain = DAG.getNode(ISD::INLINEASM,
3076 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
3077 &AsmNodeOperands[0], AsmNodeOperands.size());
3078 Flag = Chain.getValue(1);
3080 // If this asm returns a register value, copy the result from that register
3081 // and set it as the value of the call.
3082 if (!RetValRegs.Regs.empty())
3083 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
3085 std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
3087 // Process indirect outputs, first output all of the flagged copies out of
3089 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
3090 RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
3091 Value *Ptr = IndirectStoresToEmit[i].second;
3092 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
3093 StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
3096 // Emit the non-flagged stores from the physregs.
3097 SmallVector<SDOperand, 8> OutChains;
3098 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
3099 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
3100 getValue(StoresToEmit[i].second),
3101 StoresToEmit[i].second, 0));
3102 if (!OutChains.empty())
3103 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3104 &OutChains[0], OutChains.size());
3109 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
3110 SDOperand Src = getValue(I.getOperand(0));
3112 MVT::ValueType IntPtr = TLI.getPointerTy();
3114 if (IntPtr < Src.getValueType())
3115 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
3116 else if (IntPtr > Src.getValueType())
3117 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
3119 // Scale the source by the type size.
3120 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
3121 Src = DAG.getNode(ISD::MUL, Src.getValueType(),
3122 Src, getIntPtrConstant(ElementSize));
3124 TargetLowering::ArgListTy Args;
3125 TargetLowering::ArgListEntry Entry;
3127 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3128 Args.push_back(Entry);
3130 std::pair<SDOperand,SDOperand> Result =
3131 TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3132 DAG.getExternalSymbol("malloc", IntPtr),
3134 setValue(&I, Result.first); // Pointers always fit in registers
3135 DAG.setRoot(Result.second);
3138 void SelectionDAGLowering::visitFree(FreeInst &I) {
3139 TargetLowering::ArgListTy Args;
3140 TargetLowering::ArgListEntry Entry;
3141 Entry.Node = getValue(I.getOperand(0));
3142 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3143 Args.push_back(Entry);
3144 MVT::ValueType IntPtr = TLI.getPointerTy();
3145 std::pair<SDOperand,SDOperand> Result =
3146 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3147 DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3148 DAG.setRoot(Result.second);
3151 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3152 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These
3153 // instructions are special in various ways, which require special support to
3154 // insert. The specified MachineInstr is created but not inserted into any
3155 // basic blocks, and the scheduler passes ownership of it to this method.
3156 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3157 MachineBasicBlock *MBB) {
3158 cerr << "If a target marks an instruction with "
3159 << "'usesCustomDAGSchedInserter', it must implement "
3160 << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3165 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3166 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
3167 getValue(I.getOperand(1)),
3168 DAG.getSrcValue(I.getOperand(1))));
3171 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3172 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3173 getValue(I.getOperand(0)),
3174 DAG.getSrcValue(I.getOperand(0)));
3176 DAG.setRoot(V.getValue(1));
3179 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3180 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3181 getValue(I.getOperand(1)),
3182 DAG.getSrcValue(I.getOperand(1))));
3185 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3186 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
3187 getValue(I.getOperand(1)),
3188 getValue(I.getOperand(2)),
3189 DAG.getSrcValue(I.getOperand(1)),
3190 DAG.getSrcValue(I.getOperand(2))));
3193 /// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
3194 /// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
3195 static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
3196 unsigned &i, SelectionDAG &DAG,
3197 TargetLowering &TLI) {
3198 if (TLI.getTypeAction(VT) != TargetLowering::Expand)
3199 return SDOperand(Arg, i++);
3201 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3202 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3204 return DAG.getNode(ISD::BIT_CONVERT, VT,
3205 ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
3206 } else if (NumVals == 2) {
3207 SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3208 SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3209 if (!TLI.isLittleEndian())
3211 return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
3213 // Value scalarized into many values. Unimp for now.
3214 assert(0 && "Cannot expand i64 -> i16 yet!");
3219 /// TargetLowering::LowerArguments - This is the default LowerArguments
3220 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all
3221 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
3222 /// integrated into SDISel.
3223 std::vector<SDOperand>
3224 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3225 const FunctionType *FTy = F.getFunctionType();
3226 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3227 std::vector<SDOperand> Ops;
3228 Ops.push_back(DAG.getRoot());
3229 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3230 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3232 // Add one result value for each formal argument.
3233 std::vector<MVT::ValueType> RetVals;
3235 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3237 MVT::ValueType VT = getValueType(I->getType());
3238 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3239 unsigned OriginalAlignment =
3240 getTargetData()->getABITypeAlignment(I->getType());
3242 // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3243 // that is zero extended!
3244 if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
3245 Flags &= ~(ISD::ParamFlags::SExt);
3246 if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
3247 Flags |= ISD::ParamFlags::SExt;
3248 if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
3249 Flags |= ISD::ParamFlags::InReg;
3250 if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
3251 Flags |= ISD::ParamFlags::StructReturn;
3252 Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3254 switch (getTypeAction(VT)) {
3255 default: assert(0 && "Unknown type action!");
3257 RetVals.push_back(VT);
3258 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3261 RetVals.push_back(getTypeToTransformTo(VT));
3262 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3265 if (VT != MVT::Vector) {
3266 // If this is a large integer, it needs to be broken up into small
3267 // integers. Figure out what the destination type is and how many small
3268 // integers it turns into.
3269 MVT::ValueType NVT = getTypeToExpandTo(VT);
3270 unsigned NumVals = getNumElements(VT);
3271 for (unsigned i = 0; i != NumVals; ++i) {
3272 RetVals.push_back(NVT);
3273 // if it isn't first piece, alignment must be 1
3275 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3276 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3277 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3280 // Otherwise, this is a vector type. We only support legal vectors
3282 unsigned NumElems = cast<VectorType>(I->getType())->getNumElements();
3283 const Type *EltTy = cast<VectorType>(I->getType())->getElementType();
3285 // Figure out if there is a Packed type corresponding to this Vector
3286 // type. If so, convert to the vector type.
3287 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3288 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3289 RetVals.push_back(TVT);
3290 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3292 assert(0 && "Don't support illegal by-val vector arguments yet!");
3299 RetVals.push_back(MVT::Other);
3302 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3303 DAG.getNodeValueTypes(RetVals), RetVals.size(),
3304 &Ops[0], Ops.size()).Val;
3306 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
3308 // Set up the return result vector.
3312 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
3314 MVT::ValueType VT = getValueType(I->getType());
3316 switch (getTypeAction(VT)) {
3317 default: assert(0 && "Unknown type action!");
3319 Ops.push_back(SDOperand(Result, i++));
3322 SDOperand Op(Result, i++);
3323 if (MVT::isInteger(VT)) {
3324 if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
3325 Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3326 DAG.getValueType(VT));
3327 else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
3328 Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3329 DAG.getValueType(VT));
3330 Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3332 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3333 Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
3339 if (VT != MVT::Vector) {
3340 // If this is a large integer or a floating point node that needs to be
3341 // expanded, it needs to be reassembled from small integers. Figure out
3342 // what the source elt type is and how many small integers it is.
3343 Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
3345 // Otherwise, this is a vector type. We only support legal vectors
3347 const VectorType *PTy = cast<VectorType>(I->getType());
3348 unsigned NumElems = PTy->getNumElements();
3349 const Type *EltTy = PTy->getElementType();
3351 // Figure out if there is a Packed type corresponding to this Vector
3352 // type. If so, convert to the vector type.
3353 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3354 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3355 SDOperand N = SDOperand(Result, i++);
3356 // Handle copies from generic vectors to registers.
3357 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
3358 DAG.getConstant(NumElems, MVT::i32),
3359 DAG.getValueType(getValueType(EltTy)));
3362 assert(0 && "Don't support illegal by-val vector arguments yet!");
3373 /// ExpandScalarCallArgs - Recursively expand call argument node by
3374 /// bit_converting it or extract a pair of elements from the larger node.
3375 static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
3377 SmallVector<SDOperand, 32> &Ops,
3379 TargetLowering &TLI,
3380 bool isFirst = true) {
3382 if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
3383 // if it isn't first piece, alignment must be 1
3385 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3386 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3388 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3392 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3393 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3395 Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
3396 ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI, isFirst);
3397 } else if (NumVals == 2) {
3398 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3399 DAG.getConstant(0, TLI.getPointerTy()));
3400 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3401 DAG.getConstant(1, TLI.getPointerTy()));
3402 if (!TLI.isLittleEndian())
3404 ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI, isFirst);
3405 ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI, false);
3407 // Value scalarized into many values. Unimp for now.
3408 assert(0 && "Cannot expand i64 -> i16 yet!");
3412 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
3413 /// implementation, which just inserts an ISD::CALL node, which is later custom
3414 /// lowered by the target to something concrete. FIXME: When all targets are
3415 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
3416 std::pair<SDOperand, SDOperand>
3417 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
3418 bool RetTyIsSigned, bool isVarArg,
3419 unsigned CallingConv, bool isTailCall,
3421 ArgListTy &Args, SelectionDAG &DAG) {
3422 SmallVector<SDOperand, 32> Ops;
3423 Ops.push_back(Chain); // Op#0 - Chain
3424 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
3425 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg
3426 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail
3427 Ops.push_back(Callee);
3429 // Handle all of the outgoing arguments.
3430 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
3431 MVT::ValueType VT = getValueType(Args[i].Ty);
3432 SDOperand Op = Args[i].Node;
3433 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3434 unsigned OriginalAlignment =
3435 getTargetData()->getABITypeAlignment(Args[i].Ty);
3438 Flags |= ISD::ParamFlags::SExt;
3440 Flags |= ISD::ParamFlags::ZExt;
3441 if (Args[i].isInReg)
3442 Flags |= ISD::ParamFlags::InReg;
3444 Flags |= ISD::ParamFlags::StructReturn;
3445 Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
3447 switch (getTypeAction(VT)) {
3448 default: assert(0 && "Unknown type action!");
3451 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3454 if (MVT::isInteger(VT)) {
3457 ExtOp = ISD::SIGN_EXTEND;
3458 else if (Args[i].isZExt)
3459 ExtOp = ISD::ZERO_EXTEND;
3461 ExtOp = ISD::ANY_EXTEND;
3462 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
3464 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3465 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
3468 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3471 if (VT != MVT::Vector) {
3472 // If this is a large integer, it needs to be broken down into small
3473 // integers. Figure out what the source elt type is and how many small
3475 ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
3477 // Otherwise, this is a vector type. We only support legal vectors
3479 const VectorType *PTy = cast<VectorType>(Args[i].Ty);
3480 unsigned NumElems = PTy->getNumElements();
3481 const Type *EltTy = PTy->getElementType();
3483 // Figure out if there is a Packed type corresponding to this Vector
3484 // type. If so, convert to the vector type.
3485 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3486 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3487 // Insert a VBIT_CONVERT of the MVT::Vector type to the vector type.
3488 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
3490 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3492 assert(0 && "Don't support illegal by-val vector call args yet!");
3500 // Figure out the result value types.
3501 SmallVector<MVT::ValueType, 4> RetTys;
3503 if (RetTy != Type::VoidTy) {
3504 MVT::ValueType VT = getValueType(RetTy);
3505 switch (getTypeAction(VT)) {
3506 default: assert(0 && "Unknown type action!");
3508 RetTys.push_back(VT);
3511 RetTys.push_back(getTypeToTransformTo(VT));
3514 if (VT != MVT::Vector) {
3515 // If this is a large integer, it needs to be reassembled from small
3516 // integers. Figure out what the source elt type is and how many small
3518 MVT::ValueType NVT = getTypeToExpandTo(VT);
3519 unsigned NumVals = getNumElements(VT);
3520 for (unsigned i = 0; i != NumVals; ++i)
3521 RetTys.push_back(NVT);
3523 // Otherwise, this is a vector type. We only support legal vectors
3525 const VectorType *PTy = cast<VectorType>(RetTy);
3526 unsigned NumElems = PTy->getNumElements();
3527 const Type *EltTy = PTy->getElementType();
3529 // Figure out if there is a Packed type corresponding to this Vector
3530 // type. If so, convert to the vector type.
3531 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3532 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3533 RetTys.push_back(TVT);
3535 assert(0 && "Don't support illegal by-val vector call results yet!");
3542 RetTys.push_back(MVT::Other); // Always has a chain.
3544 // Finally, create the CALL node.
3545 SDOperand Res = DAG.getNode(ISD::CALL,
3546 DAG.getVTList(&RetTys[0], RetTys.size()),
3547 &Ops[0], Ops.size());
3549 // This returns a pair of operands. The first element is the
3550 // return value for the function (if RetTy is not VoidTy). The second
3551 // element is the outgoing token chain.
3553 if (RetTys.size() != 1) {
3554 MVT::ValueType VT = getValueType(RetTy);
3555 if (RetTys.size() == 2) {
3558 // If this value was promoted, truncate it down.
3559 if (ResVal.getValueType() != VT) {
3560 if (VT == MVT::Vector) {
3561 // Insert a VBIT_CONVERT to convert from the packed result type to the
3562 // MVT::Vector type.
3563 unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
3564 const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
3566 // Figure out if there is a Packed type corresponding to this Vector
3567 // type. If so, convert to the vector type.
3568 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
3569 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3570 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
3571 // "N x PTyElementVT" MVT::Vector type.
3572 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
3573 DAG.getConstant(NumElems, MVT::i32),
3574 DAG.getValueType(getValueType(EltTy)));
3578 } else if (MVT::isInteger(VT)) {
3579 unsigned AssertOp = ISD::AssertSext;
3581 AssertOp = ISD::AssertZext;
3582 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
3583 DAG.getValueType(VT));
3584 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
3586 assert(MVT::isFloatingPoint(VT));
3587 if (getTypeAction(VT) == Expand)
3588 ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
3590 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
3593 } else if (RetTys.size() == 3) {
3594 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
3595 Res.getValue(0), Res.getValue(1));
3598 assert(0 && "Case not handled yet!");
3602 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
3605 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
3606 assert(0 && "LowerOperation not implemented for this target!");
3611 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
3612 SelectionDAG &DAG) {
3613 assert(0 && "CustomPromoteOperation not implemented for this target!");
3618 /// getMemsetValue - Vectorized representation of the memset value
3620 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
3621 SelectionDAG &DAG) {
3622 MVT::ValueType CurVT = VT;
3623 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3624 uint64_t Val = C->getValue() & 255;
3626 while (CurVT != MVT::i8) {
3627 Val = (Val << Shift) | Val;
3629 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3631 return DAG.getConstant(Val, VT);
3633 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
3635 while (CurVT != MVT::i8) {
3637 DAG.getNode(ISD::OR, VT,
3638 DAG.getNode(ISD::SHL, VT, Value,
3639 DAG.getConstant(Shift, MVT::i8)), Value);
3641 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3648 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3649 /// used when a memcpy is turned into a memset when the source is a constant
3651 static SDOperand getMemsetStringVal(MVT::ValueType VT,
3652 SelectionDAG &DAG, TargetLowering &TLI,
3653 std::string &Str, unsigned Offset) {
3655 unsigned MSB = getSizeInBits(VT) / 8;
3656 if (TLI.isLittleEndian())
3657 Offset = Offset + MSB - 1;
3658 for (unsigned i = 0; i != MSB; ++i) {
3659 Val = (Val << 8) | (unsigned char)Str[Offset];
3660 Offset += TLI.isLittleEndian() ? -1 : 1;
3662 return DAG.getConstant(Val, VT);
3665 /// getMemBasePlusOffset - Returns base and offset node for the
3666 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
3667 SelectionDAG &DAG, TargetLowering &TLI) {
3668 MVT::ValueType VT = Base.getValueType();
3669 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
3672 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
3673 /// to replace the memset / memcpy is below the threshold. It also returns the
3674 /// types of the sequence of memory ops to perform memset / memcpy.
3675 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
3676 unsigned Limit, uint64_t Size,
3677 unsigned Align, TargetLowering &TLI) {
3680 if (TLI.allowsUnalignedMemoryAccesses()) {
3683 switch (Align & 7) {
3699 MVT::ValueType LVT = MVT::i64;
3700 while (!TLI.isTypeLegal(LVT))
3701 LVT = (MVT::ValueType)((unsigned)LVT - 1);
3702 assert(MVT::isInteger(LVT));
3707 unsigned NumMemOps = 0;
3709 unsigned VTSize = getSizeInBits(VT) / 8;
3710 while (VTSize > Size) {
3711 VT = (MVT::ValueType)((unsigned)VT - 1);
3714 assert(MVT::isInteger(VT));
3716 if (++NumMemOps > Limit)
3718 MemOps.push_back(VT);
3725 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
3726 SDOperand Op1 = getValue(I.getOperand(1));
3727 SDOperand Op2 = getValue(I.getOperand(2));
3728 SDOperand Op3 = getValue(I.getOperand(3));
3729 SDOperand Op4 = getValue(I.getOperand(4));
3730 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
3731 if (Align == 0) Align = 1;
3733 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
3734 std::vector<MVT::ValueType> MemOps;
3736 // Expand memset / memcpy to a series of load / store ops
3737 // if the size operand falls below a certain threshold.
3738 SmallVector<SDOperand, 8> OutChains;
3740 default: break; // Do nothing for now.
3742 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
3743 Size->getValue(), Align, TLI)) {
3744 unsigned NumMemOps = MemOps.size();
3745 unsigned Offset = 0;
3746 for (unsigned i = 0; i < NumMemOps; i++) {
3747 MVT::ValueType VT = MemOps[i];
3748 unsigned VTSize = getSizeInBits(VT) / 8;
3749 SDOperand Value = getMemsetValue(Op2, VT, DAG);
3750 SDOperand Store = DAG.getStore(getRoot(), Value,
3751 getMemBasePlusOffset(Op1, Offset, DAG, TLI),
3752 I.getOperand(1), Offset);
3753 OutChains.push_back(Store);
3760 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
3761 Size->getValue(), Align, TLI)) {
3762 unsigned NumMemOps = MemOps.size();
3763 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
3764 GlobalAddressSDNode *G = NULL;
3766 bool CopyFromStr = false;
3768 if (Op2.getOpcode() == ISD::GlobalAddress)
3769 G = cast<GlobalAddressSDNode>(Op2);
3770 else if (Op2.getOpcode() == ISD::ADD &&
3771 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3772 Op2.getOperand(1).getOpcode() == ISD::Constant) {
3773 G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
3774 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
3777 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3778 if (GV && GV->isConstant()) {
3779 Str = GV->getStringValue(false);
3787 for (unsigned i = 0; i < NumMemOps; i++) {
3788 MVT::ValueType VT = MemOps[i];
3789 unsigned VTSize = getSizeInBits(VT) / 8;
3790 SDOperand Value, Chain, Store;
3793 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
3796 DAG.getStore(Chain, Value,
3797 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3798 I.getOperand(1), DstOff);
3800 Value = DAG.getLoad(VT, getRoot(),
3801 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
3802 I.getOperand(2), SrcOff);
3803 Chain = Value.getValue(1);
3805 DAG.getStore(Chain, Value,
3806 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3807 I.getOperand(1), DstOff);
3809 OutChains.push_back(Store);
3818 if (!OutChains.empty()) {
3819 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
3820 &OutChains[0], OutChains.size()));
3825 DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
3828 //===----------------------------------------------------------------------===//
3829 // SelectionDAGISel code
3830 //===----------------------------------------------------------------------===//
3832 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
3833 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
3836 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
3837 AU.addRequired<AliasAnalysis>();
3838 AU.setPreservesAll();
3843 bool SelectionDAGISel::runOnFunction(Function &Fn) {
3844 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
3845 RegMap = MF.getSSARegMap();
3846 DOUT << "\n\n\n=== " << Fn.getName() << "\n";
3848 FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
3850 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
3851 SelectBasicBlock(I, MF, FuncInfo);
3853 // Add function live-ins to entry block live-in set.
3854 BasicBlock *EntryBB = &Fn.getEntryBlock();
3855 BB = FuncInfo.MBBMap[EntryBB];
3856 if (!MF.livein_empty())
3857 for (MachineFunction::livein_iterator I = MF.livein_begin(),
3858 E = MF.livein_end(); I != E; ++I)
3859 BB->addLiveIn(I->first);
3864 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V,
3866 SDOperand Op = getValue(V);
3867 assert((Op.getOpcode() != ISD::CopyFromReg ||
3868 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
3869 "Copy from a reg to the same reg!");
3871 // If this type is not legal, we must make sure to not create an invalid
3873 MVT::ValueType SrcVT = Op.getValueType();
3874 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
3875 if (SrcVT == DestVT) {
3876 return DAG.getCopyToReg(getRoot(), Reg, Op);
3877 } else if (SrcVT == MVT::Vector) {
3878 // Handle copies from generic vectors to registers.
3879 MVT::ValueType PTyElementVT, PTyLegalElementVT;
3880 unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
3881 PTyElementVT, PTyLegalElementVT);
3883 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
3884 // MVT::Vector type.
3885 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
3886 DAG.getConstant(NE, MVT::i32),
3887 DAG.getValueType(PTyElementVT));
3889 // Loop over all of the elements of the resultant vector,
3890 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
3891 // copying them into output registers.
3892 SmallVector<SDOperand, 8> OutChains;
3893 SDOperand Root = getRoot();
3894 for (unsigned i = 0; i != NE; ++i) {
3895 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
3896 Op, DAG.getConstant(i, TLI.getPointerTy()));
3897 if (PTyElementVT == PTyLegalElementVT) {
3898 // Elements are legal.
3899 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
3900 } else if (PTyLegalElementVT > PTyElementVT) {
3901 // Elements are promoted.
3902 if (MVT::isFloatingPoint(PTyLegalElementVT))
3903 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
3905 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
3906 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
3908 // Elements are expanded.
3909 // The src value is expanded into multiple registers.
3910 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
3911 Elt, DAG.getConstant(0, TLI.getPointerTy()));
3912 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
3913 Elt, DAG.getConstant(1, TLI.getPointerTy()));
3914 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
3915 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
3918 return DAG.getNode(ISD::TokenFactor, MVT::Other,
3919 &OutChains[0], OutChains.size());
3920 } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
3921 // The src value is promoted to the register.
3922 if (MVT::isFloatingPoint(SrcVT))
3923 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
3925 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
3926 return DAG.getCopyToReg(getRoot(), Reg, Op);
3928 DestVT = TLI.getTypeToExpandTo(SrcVT);
3929 unsigned NumVals = TLI.getNumElements(SrcVT);
3931 return DAG.getCopyToReg(getRoot(), Reg,
3932 DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
3933 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
3934 // The src value is expanded into multiple registers.
3935 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
3936 Op, DAG.getConstant(0, TLI.getPointerTy()));
3937 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
3938 Op, DAG.getConstant(1, TLI.getPointerTy()));
3939 Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
3940 return DAG.getCopyToReg(Op, Reg+1, Hi);
3944 void SelectionDAGISel::
3945 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
3946 std::vector<SDOperand> &UnorderedChains) {
3947 // If this is the entry block, emit arguments.
3948 Function &F = *LLVMBB->getParent();
3949 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
3950 SDOperand OldRoot = SDL.DAG.getRoot();
3951 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
3954 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
3956 if (!AI->use_empty()) {
3957 SDL.setValue(AI, Args[a]);
3959 // If this argument is live outside of the entry block, insert a copy from
3960 // whereever we got it to the vreg that other BB's will reference it as.
3961 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
3962 if (VMI != FuncInfo.ValueMap.end()) {
3963 SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
3964 UnorderedChains.push_back(Copy);
3968 // Finally, if the target has anything special to do, allow it to do so.
3969 // FIXME: this should insert code into the DAG!
3970 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
3973 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
3974 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
3975 FunctionLoweringInfo &FuncInfo) {
3976 SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
3978 std::vector<SDOperand> UnorderedChains;
3980 // Lower any arguments needed in this block if this is the entry block.
3981 if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
3982 LowerArguments(LLVMBB, SDL, UnorderedChains);
3984 BB = FuncInfo.MBBMap[LLVMBB];
3985 SDL.setCurrentBasicBlock(BB);
3987 // Lower all of the non-terminator instructions.
3988 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
3992 // Lower call part of invoke.
3993 InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
3994 if (Invoke) SDL.visitInvoke(*Invoke, false);
3996 // Ensure that all instructions which are used outside of their defining
3997 // blocks are available as virtual registers.
3998 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
3999 if (!I->use_empty() && !isa<PHINode>(I)) {
4000 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4001 if (VMI != FuncInfo.ValueMap.end())
4002 UnorderedChains.push_back(
4003 SDL.CopyValueToVirtualRegister(I, VMI->second));
4006 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to
4007 // ensure constants are generated when needed. Remember the virtual registers
4008 // that need to be added to the Machine PHI nodes as input. We cannot just
4009 // directly add them, because expansion might result in multiple MBB's for one
4010 // BB. As such, the start of the BB might correspond to a different MBB than
4013 TerminatorInst *TI = LLVMBB->getTerminator();
4015 // Emit constants only once even if used by multiple PHI nodes.
4016 std::map<Constant*, unsigned> ConstantsOut;
4018 // Vector bool would be better, but vector<bool> is really slow.
4019 std::vector<unsigned char> SuccsHandled;
4020 if (TI->getNumSuccessors())
4021 SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4023 // Check successor nodes PHI nodes that expect a constant to be available from
4025 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4026 BasicBlock *SuccBB = TI->getSuccessor(succ);
4027 if (!isa<PHINode>(SuccBB->begin())) continue;
4028 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4030 // If this terminator has multiple identical successors (common for
4031 // switches), only handle each succ once.
4032 unsigned SuccMBBNo = SuccMBB->getNumber();
4033 if (SuccsHandled[SuccMBBNo]) continue;
4034 SuccsHandled[SuccMBBNo] = true;
4036 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4039 // At this point we know that there is a 1-1 correspondence between LLVM PHI
4040 // nodes and Machine PHI nodes, but the incoming operands have not been
4042 for (BasicBlock::iterator I = SuccBB->begin();
4043 (PN = dyn_cast<PHINode>(I)); ++I) {
4044 // Ignore dead phi's.
4045 if (PN->use_empty()) continue;
4048 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4050 if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4051 unsigned &RegOut = ConstantsOut[C];
4053 RegOut = FuncInfo.CreateRegForValue(C);
4054 UnorderedChains.push_back(
4055 SDL.CopyValueToVirtualRegister(C, RegOut));
4059 Reg = FuncInfo.ValueMap[PHIOp];
4061 assert(isa<AllocaInst>(PHIOp) &&
4062 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4063 "Didn't codegen value into a register!??");
4064 Reg = FuncInfo.CreateRegForValue(PHIOp);
4065 UnorderedChains.push_back(
4066 SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4070 // Remember that this register needs to added to the machine PHI node as
4071 // the input for this MBB.
4072 MVT::ValueType VT = TLI.getValueType(PN->getType());
4073 unsigned NumElements;
4074 if (VT != MVT::Vector)
4075 NumElements = TLI.getNumElements(VT);
4077 MVT::ValueType VT1,VT2;
4079 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
4082 for (unsigned i = 0, e = NumElements; i != e; ++i)
4083 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4086 ConstantsOut.clear();
4088 // Turn all of the unordered chains into one factored node.
4089 if (!UnorderedChains.empty()) {
4090 SDOperand Root = SDL.getRoot();
4091 if (Root.getOpcode() != ISD::EntryToken) {
4092 unsigned i = 0, e = UnorderedChains.size();
4093 for (; i != e; ++i) {
4094 assert(UnorderedChains[i].Val->getNumOperands() > 1);
4095 if (UnorderedChains[i].Val->getOperand(0) == Root)
4096 break; // Don't add the root if we already indirectly depend on it.
4100 UnorderedChains.push_back(Root);
4102 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4103 &UnorderedChains[0], UnorderedChains.size()));
4106 // Lower the terminator after the copies are emitted.
4108 // Just the branch part of invoke.
4109 SDL.visitInvoke(*Invoke, true);
4111 SDL.visit(*LLVMBB->getTerminator());
4114 // Copy over any CaseBlock records that may now exist due to SwitchInst
4115 // lowering, as well as any jump table information.
4116 SwitchCases.clear();
4117 SwitchCases = SDL.SwitchCases;
4119 JTCases = SDL.JTCases;
4121 // Make sure the root of the DAG is up-to-date.
4122 DAG.setRoot(SDL.getRoot());
4125 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4126 // Get alias analysis for load/store combining.
4127 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
4129 // Run the DAG combiner in pre-legalize mode.
4130 DAG.Combine(false, AA);
4132 DOUT << "Lowered selection DAG:\n";
4135 // Second step, hack on the DAG until it only uses operations and types that
4136 // the target supports.
4139 DOUT << "Legalized selection DAG:\n";
4142 // Run the DAG combiner in post-legalize mode.
4143 DAG.Combine(true, AA);
4145 if (ViewISelDAGs) DAG.viewGraph();
4147 // Third, instruction select all of the operations to machine code, adding the
4148 // code to the MachineBasicBlock.
4149 InstructionSelectBasicBlock(DAG);
4151 DOUT << "Selected machine code:\n";
4155 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4156 FunctionLoweringInfo &FuncInfo) {
4157 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4159 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4162 // First step, lower LLVM code to some DAG. This DAG may use operations and
4163 // types that are not supported by the target.
4164 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4166 // Second step, emit the lowered DAG as machine code.
4167 CodeGenAndEmitDAG(DAG);
4170 // Next, now that we know what the last MBB the LLVM BB expanded is, update
4171 // PHI nodes in successors.
4172 if (SwitchCases.empty() && JTCases.empty()) {
4173 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4174 MachineInstr *PHI = PHINodesToUpdate[i].first;
4175 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4176 "This is not a machine PHI node that we are updating!");
4177 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4178 PHI->addMachineBasicBlockOperand(BB);
4183 // If the JumpTable record is filled in, then we need to emit a jump table.
4184 // Updating the PHI nodes is tricky in this case, since we need to determine
4185 // whether the PHI is a successor of the range check MBB or the jump table MBB
4186 for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
4187 // Lower header first, if it wasn't already lowered
4188 if (!JTCases[i].first.Emitted) {
4189 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4191 SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
4192 // Set the current basic block to the mbb we wish to insert the code into
4193 BB = JTCases[i].first.HeaderBB;
4194 HSDL.setCurrentBasicBlock(BB);
4196 HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
4197 HSDAG.setRoot(HSDL.getRoot());
4198 CodeGenAndEmitDAG(HSDAG);
4201 SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4203 SelectionDAGLowering JSDL(JSDAG, TLI, FuncInfo);
4204 // Set the current basic block to the mbb we wish to insert the code into
4205 BB = JTCases[i].second.MBB;
4206 JSDL.setCurrentBasicBlock(BB);
4208 JSDL.visitJumpTable(JTCases[i].second);
4209 JSDAG.setRoot(JSDL.getRoot());
4210 CodeGenAndEmitDAG(JSDAG);
4213 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4214 MachineInstr *PHI = PHINodesToUpdate[pi].first;
4215 MachineBasicBlock *PHIBB = PHI->getParent();
4216 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4217 "This is not a machine PHI node that we are updating!");
4218 if (PHIBB == JTCases[i].second.Default) {
4219 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4220 PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
4222 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4223 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4224 PHI->addMachineBasicBlockOperand(BB);
4229 // If the switch block involved a branch to one of the actual successors, we
4230 // need to update PHI nodes in that block.
4231 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4232 MachineInstr *PHI = PHINodesToUpdate[i].first;
4233 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4234 "This is not a machine PHI node that we are updating!");
4235 if (BB->isSuccessor(PHI->getParent())) {
4236 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4237 PHI->addMachineBasicBlockOperand(BB);
4241 // If we generated any switch lowering information, build and codegen any
4242 // additional DAGs necessary.
4243 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4244 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4246 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4248 // Set the current basic block to the mbb we wish to insert the code into
4249 BB = SwitchCases[i].ThisBB;
4250 SDL.setCurrentBasicBlock(BB);
4253 SDL.visitSwitchCase(SwitchCases[i]);
4254 SDAG.setRoot(SDL.getRoot());
4255 CodeGenAndEmitDAG(SDAG);
4257 // Handle any PHI nodes in successors of this chunk, as if we were coming
4258 // from the original BB before switch expansion. Note that PHI nodes can
4259 // occur multiple times in PHINodesToUpdate. We have to be very careful to
4260 // handle them the right number of times.
4261 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS.
4262 for (MachineBasicBlock::iterator Phi = BB->begin();
4263 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4264 // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4265 for (unsigned pn = 0; ; ++pn) {
4266 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4267 if (PHINodesToUpdate[pn].first == Phi) {
4268 Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4269 Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4275 // Don't process RHS if same block as LHS.
4276 if (BB == SwitchCases[i].FalseBB)
4277 SwitchCases[i].FalseBB = 0;
4279 // If we haven't handled the RHS, do so now. Otherwise, we're done.
4280 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4281 SwitchCases[i].FalseBB = 0;
4283 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4288 //===----------------------------------------------------------------------===//
4289 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4290 /// target node in the graph.
4291 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4292 if (ViewSchedDAGs) DAG.viewGraph();
4294 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4298 RegisterScheduler::setDefault(Ctor);
4301 ScheduleDAG *SL = Ctor(this, &DAG, BB);
4307 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4308 return new HazardRecognizer();
4311 //===----------------------------------------------------------------------===//
4312 // Helper functions used by the generated instruction selector.
4313 //===----------------------------------------------------------------------===//
4314 // Calls to these methods are generated by tblgen.
4316 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
4317 /// the dag combiner simplified the 255, we still want to match. RHS is the
4318 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
4319 /// specified in the .td file (e.g. 255).
4320 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
4321 int64_t DesiredMaskS) {
4322 uint64_t ActualMask = RHS->getValue();
4323 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4325 // If the actual mask exactly matches, success!
4326 if (ActualMask == DesiredMask)
4329 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4330 if (ActualMask & ~DesiredMask)
4333 // Otherwise, the DAG Combiner may have proven that the value coming in is
4334 // either already zero or is not demanded. Check for known zero input bits.
4335 uint64_t NeededMask = DesiredMask & ~ActualMask;
4336 if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
4339 // TODO: check to see if missing bits are just not demanded.
4341 // Otherwise, this pattern doesn't match.
4345 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
4346 /// the dag combiner simplified the 255, we still want to match. RHS is the
4347 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
4348 /// specified in the .td file (e.g. 255).
4349 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
4350 int64_t DesiredMaskS) {
4351 uint64_t ActualMask = RHS->getValue();
4352 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4354 // If the actual mask exactly matches, success!
4355 if (ActualMask == DesiredMask)
4358 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4359 if (ActualMask & ~DesiredMask)
4362 // Otherwise, the DAG Combiner may have proven that the value coming in is
4363 // either already zero or is not demanded. Check for known zero input bits.
4364 uint64_t NeededMask = DesiredMask & ~ActualMask;
4366 uint64_t KnownZero, KnownOne;
4367 getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
4369 // If all the missing bits in the or are already known to be set, match!
4370 if ((NeededMask & KnownOne) == NeededMask)
4373 // TODO: check to see if missing bits are just not demanded.
4375 // Otherwise, this pattern doesn't match.
4380 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
4381 /// by tblgen. Others should not call it.
4382 void SelectionDAGISel::
4383 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
4384 std::vector<SDOperand> InOps;
4385 std::swap(InOps, Ops);
4387 Ops.push_back(InOps[0]); // input chain.
4388 Ops.push_back(InOps[1]); // input asm string.
4390 unsigned i = 2, e = InOps.size();
4391 if (InOps[e-1].getValueType() == MVT::Flag)
4392 --e; // Don't process a flag operand if it is here.
4395 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
4396 if ((Flags & 7) != 4 /*MEM*/) {
4397 // Just skip over this operand, copying the operands verbatim.
4398 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
4399 i += (Flags >> 3) + 1;
4401 assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
4402 // Otherwise, this is a memory operand. Ask the target to select it.
4403 std::vector<SDOperand> SelOps;
4404 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
4405 cerr << "Could not match memory address. Inline asm failure!\n";
4409 // Add this to the output node.
4410 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
4412 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
4417 // Add the flag input back if present.
4418 if (e != InOps.size())
4419 Ops.push_back(InOps.back());