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/ADT/BitVector.h"
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/CodeGen/SelectionDAGISel.h"
18 #include "llvm/CodeGen/ScheduleDAG.h"
19 #include "llvm/Constants.h"
20 #include "llvm/CallingConv.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/Function.h"
23 #include "llvm/GlobalVariable.h"
24 #include "llvm/InlineAsm.h"
25 #include "llvm/Instructions.h"
26 #include "llvm/Intrinsics.h"
27 #include "llvm/IntrinsicInst.h"
28 #include "llvm/CodeGen/MachineModuleInfo.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineFrameInfo.h"
31 #include "llvm/CodeGen/MachineJumpTableInfo.h"
32 #include "llvm/CodeGen/MachineInstrBuilder.h"
33 #include "llvm/CodeGen/SchedulerRegistry.h"
34 #include "llvm/CodeGen/SelectionDAG.h"
35 #include "llvm/CodeGen/SSARegMap.h"
36 #include "llvm/Target/MRegisterInfo.h"
37 #include "llvm/Target/TargetData.h"
38 #include "llvm/Target/TargetFrameInfo.h"
39 #include "llvm/Target/TargetInstrInfo.h"
40 #include "llvm/Target/TargetLowering.h"
41 #include "llvm/Target/TargetMachine.h"
42 #include "llvm/Target/TargetOptions.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/Compiler.h"
51 ViewISelDAGs("view-isel-dags", cl::Hidden,
52 cl::desc("Pop up a window to show isel dags as they are selected"));
54 ViewSchedDAGs("view-sched-dags", cl::Hidden,
55 cl::desc("Pop up a window to show sched dags as they are processed"));
57 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
60 //===---------------------------------------------------------------------===//
62 /// RegisterScheduler class - Track the registration of instruction schedulers.
64 //===---------------------------------------------------------------------===//
65 MachinePassRegistry RegisterScheduler::Registry;
67 //===---------------------------------------------------------------------===//
69 /// ISHeuristic command line option for instruction schedulers.
71 //===---------------------------------------------------------------------===//
73 cl::opt<RegisterScheduler::FunctionPassCtor, false,
74 RegisterPassParser<RegisterScheduler> >
76 cl::init(&createDefaultScheduler),
77 cl::desc("Instruction schedulers available:"));
79 static RegisterScheduler
80 defaultListDAGScheduler("default", " Best scheduler for the target",
81 createDefaultScheduler);
85 /// RegsForValue - This struct represents the physical registers that a
86 /// particular value is assigned and the type information about the value.
87 /// This is needed because values can be promoted into larger registers and
88 /// expanded into multiple smaller registers than the value.
89 struct VISIBILITY_HIDDEN RegsForValue {
90 /// Regs - This list hold the register (for legal and promoted values)
91 /// or register set (for expanded values) that the value should be assigned
93 std::vector<unsigned> Regs;
95 /// RegVT - The value type of each register.
99 /// ValueVT - The value type of the LLVM value, which may be promoted from
100 /// RegVT or made from merging the two expanded parts.
101 MVT::ValueType ValueVT;
103 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {}
105 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt)
106 : RegVT(regvt), ValueVT(valuevt) {
109 RegsForValue(const std::vector<unsigned> ®s,
110 MVT::ValueType regvt, MVT::ValueType valuevt)
111 : Regs(regs), RegVT(regvt), ValueVT(valuevt) {
114 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
115 /// this value and returns the result as a ValueVT value. This uses
116 /// Chain/Flag as the input and updates them for the output Chain/Flag.
117 SDOperand getCopyFromRegs(SelectionDAG &DAG,
118 SDOperand &Chain, SDOperand &Flag) const;
120 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
121 /// specified value into the registers specified by this object. This uses
122 /// Chain/Flag as the input and updates them for the output Chain/Flag.
123 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
124 SDOperand &Chain, SDOperand &Flag,
125 MVT::ValueType PtrVT) const;
127 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
128 /// operand list. This adds the code marker and includes the number of
129 /// values added into it.
130 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
131 std::vector<SDOperand> &Ops) const;
136 //===--------------------------------------------------------------------===//
137 /// createDefaultScheduler - This creates an instruction scheduler appropriate
139 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
141 MachineBasicBlock *BB) {
142 TargetLowering &TLI = IS->getTargetLowering();
144 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
145 return createTDListDAGScheduler(IS, DAG, BB);
147 assert(TLI.getSchedulingPreference() ==
148 TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
149 return createBURRListDAGScheduler(IS, DAG, BB);
154 //===--------------------------------------------------------------------===//
155 /// FunctionLoweringInfo - This contains information that is global to a
156 /// function that is used when lowering a region of the function.
157 class FunctionLoweringInfo {
164 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
166 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
167 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
169 /// ValueMap - Since we emit code for the function a basic block at a time,
170 /// we must remember which virtual registers hold the values for
171 /// cross-basic-block values.
172 DenseMap<const Value*, unsigned> ValueMap;
174 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
175 /// the entry block. This allows the allocas to be efficiently referenced
176 /// anywhere in the function.
177 std::map<const AllocaInst*, int> StaticAllocaMap;
179 unsigned MakeReg(MVT::ValueType VT) {
180 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
183 /// isExportedInst - Return true if the specified value is an instruction
184 /// exported from its block.
185 bool isExportedInst(const Value *V) {
186 return ValueMap.count(V);
189 unsigned CreateRegForValue(const Value *V);
191 unsigned InitializeRegForValue(const Value *V) {
192 unsigned &R = ValueMap[V];
193 assert(R == 0 && "Already initialized this value register!");
194 return R = CreateRegForValue(V);
199 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
200 /// PHI nodes or outside of the basic block that defines it, or used by a
201 /// switch instruction, which may expand to multiple basic blocks.
202 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
203 if (isa<PHINode>(I)) return true;
204 BasicBlock *BB = I->getParent();
205 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
206 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
207 // FIXME: Remove switchinst special case.
208 isa<SwitchInst>(*UI))
213 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
214 /// entry block, return true. This includes arguments used by switches, since
215 /// the switch may expand into multiple basic blocks.
216 static bool isOnlyUsedInEntryBlock(Argument *A) {
217 BasicBlock *Entry = A->getParent()->begin();
218 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
219 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
220 return false; // Use not in entry block.
224 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
225 Function &fn, MachineFunction &mf)
226 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
228 // Create a vreg for each argument register that is not dead and is used
229 // outside of the entry block for the function.
230 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
232 if (!isOnlyUsedInEntryBlock(AI))
233 InitializeRegForValue(AI);
235 // Initialize the mapping of values to registers. This is only set up for
236 // instruction values that are used outside of the block that defines
238 Function::iterator BB = Fn.begin(), EB = Fn.end();
239 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
240 if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
241 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
242 const Type *Ty = AI->getAllocatedType();
243 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
245 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
248 TySize *= CUI->getZExtValue(); // Get total allocated size.
249 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
250 StaticAllocaMap[AI] =
251 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
254 for (; BB != EB; ++BB)
255 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
256 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
257 if (!isa<AllocaInst>(I) ||
258 !StaticAllocaMap.count(cast<AllocaInst>(I)))
259 InitializeRegForValue(I);
261 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This
262 // also creates the initial PHI MachineInstrs, though none of the input
263 // operands are populated.
264 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
265 MachineBasicBlock *MBB = new MachineBasicBlock(BB);
267 MF.getBasicBlockList().push_back(MBB);
269 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
272 for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
273 if (PN->use_empty()) continue;
275 MVT::ValueType VT = TLI.getValueType(PN->getType());
276 unsigned NumElements;
277 if (VT != MVT::Vector)
278 NumElements = TLI.getNumElements(VT);
280 MVT::ValueType VT1,VT2;
282 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
285 unsigned PHIReg = ValueMap[PN];
286 assert(PHIReg && "PHI node does not have an assigned virtual register!");
287 const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
288 for (unsigned i = 0; i != NumElements; ++i)
289 BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
294 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
295 /// the correctly promoted or expanded types. Assign these registers
296 /// consecutive vreg numbers and return the first assigned number.
297 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
298 MVT::ValueType VT = TLI.getValueType(V->getType());
300 // The number of multiples of registers that we need, to, e.g., split up
301 // a <2 x int64> -> 4 x i32 registers.
302 unsigned NumVectorRegs = 1;
304 // If this is a vector type, figure out what type it will decompose into
305 // and how many of the elements it will use.
306 if (VT == MVT::Vector) {
307 const VectorType *PTy = cast<VectorType>(V->getType());
308 unsigned NumElts = PTy->getNumElements();
309 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
311 // Divide the input until we get to a supported size. This will always
312 // end with a scalar if the target doesn't support vectors.
313 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) {
320 VT = getVectorType(EltTy, NumElts);
323 // The common case is that we will only create one register for this
324 // value. If we have that case, create and return the virtual register.
325 unsigned NV = TLI.getNumElements(VT);
327 // If we are promoting this value, pick the next largest supported type.
328 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
329 unsigned Reg = MakeReg(PromotedType);
330 // If this is a vector of supported or promoted types (e.g. 4 x i16),
331 // create all of the registers.
332 for (unsigned i = 1; i != NumVectorRegs; ++i)
333 MakeReg(PromotedType);
337 // If this value is represented with multiple target registers, make sure
338 // to create enough consecutive registers of the right (smaller) type.
339 VT = TLI.getTypeToExpandTo(VT);
340 unsigned R = MakeReg(VT);
341 for (unsigned i = 1; i != NV*NumVectorRegs; ++i)
346 //===----------------------------------------------------------------------===//
347 /// SelectionDAGLowering - This is the common target-independent lowering
348 /// implementation that is parameterized by a TargetLowering object.
349 /// Also, targets can overload any lowering method.
352 class SelectionDAGLowering {
353 MachineBasicBlock *CurMBB;
355 DenseMap<const Value*, SDOperand> NodeMap;
357 /// PendingLoads - Loads are not emitted to the program immediately. We bunch
358 /// them up and then emit token factor nodes when possible. This allows us to
359 /// get simple disambiguation between loads without worrying about alias
361 std::vector<SDOperand> PendingLoads;
363 /// Case - A struct to record the Value for a switch case, and the
364 /// case's target basic block.
368 MachineBasicBlock* BB;
370 Case() : Low(0), High(0), BB(0) { }
371 Case(Constant* low, Constant* high, MachineBasicBlock* bb) :
372 Low(low), High(high), BB(bb) { }
373 uint64_t size() const {
374 uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue();
375 uint64_t rLow = cast<ConstantInt>(Low)->getSExtValue();
376 return (rHigh - rLow + 1ULL);
380 typedef std::vector<Case> CaseVector;
381 typedef CaseVector::iterator CaseItr;
382 typedef std::pair<CaseItr, CaseItr> CaseRange;
384 /// CaseRec - A struct with ctor used in lowering switches to a binary tree
385 /// of conditional branches.
387 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) :
388 CaseBB(bb), LT(lt), GE(ge), Range(r) {}
390 /// CaseBB - The MBB in which to emit the compare and branch
391 MachineBasicBlock *CaseBB;
392 /// LT, GE - If nonzero, we know the current case value must be less-than or
393 /// greater-than-or-equal-to these Constants.
396 /// Range - A pair of iterators representing the range of case values to be
397 /// processed at this point in the binary search tree.
401 typedef std::vector<CaseRec> CaseRecVector;
403 /// The comparison function for sorting the switch case values in the vector.
404 /// WARNING: Case ranges should be disjoint!
406 bool operator () (const Case& C1,
409 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
410 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
411 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
412 return CI1->getValue().slt(CI2->getValue());
416 unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI);
419 // TLI - This is information that describes the available target features we
420 // need for lowering. This indicates when operations are unavailable,
421 // implemented with a libcall, etc.
424 const TargetData *TD;
426 /// SwitchCases - Vector of CaseBlock structures used to communicate
427 /// SwitchInst code generation information.
428 std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
429 /// JTCases - Vector of JumpTable structures used to communicate
430 /// SwitchInst code generation information.
431 std::vector<SelectionDAGISel::JumpTableBlock> JTCases;
433 /// FuncInfo - Information about the function as a whole.
435 FunctionLoweringInfo &FuncInfo;
437 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
438 FunctionLoweringInfo &funcinfo)
439 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
443 /// getRoot - Return the current virtual root of the Selection DAG.
445 SDOperand getRoot() {
446 if (PendingLoads.empty())
447 return DAG.getRoot();
449 if (PendingLoads.size() == 1) {
450 SDOperand Root = PendingLoads[0];
452 PendingLoads.clear();
456 // Otherwise, we have to make a token factor node.
457 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
458 &PendingLoads[0], PendingLoads.size());
459 PendingLoads.clear();
464 SDOperand CopyValueToVirtualRegister(Value *V, unsigned Reg);
466 void visit(Instruction &I) { visit(I.getOpcode(), I); }
468 void visit(unsigned Opcode, User &I) {
469 // Note: this doesn't use InstVisitor, because it has to work with
470 // ConstantExpr's in addition to instructions.
472 default: assert(0 && "Unknown instruction type encountered!");
474 // Build the switch statement using the Instruction.def file.
475 #define HANDLE_INST(NUM, OPCODE, CLASS) \
476 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
477 #include "llvm/Instruction.def"
481 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
483 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr,
484 const Value *SV, SDOperand Root,
487 SDOperand getIntPtrConstant(uint64_t Val) {
488 return DAG.getConstant(Val, TLI.getPointerTy());
491 SDOperand getValue(const Value *V);
493 void setValue(const Value *V, SDOperand NewN) {
494 SDOperand &N = NodeMap[V];
495 assert(N.Val == 0 && "Already set a value for this node!");
499 RegsForValue GetRegistersForValue(const std::string &ConstrCode,
501 bool OutReg, bool InReg,
502 std::set<unsigned> &OutputRegs,
503 std::set<unsigned> &InputRegs);
505 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
506 MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
508 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
509 void ExportFromCurrentBlock(Value *V);
510 void LowerCallTo(Instruction &I,
511 const Type *CalledValueTy, unsigned CallingConv,
512 bool IsTailCall, SDOperand Callee, unsigned OpIdx);
514 // Terminator instructions.
515 void visitRet(ReturnInst &I);
516 void visitBr(BranchInst &I);
517 void visitSwitch(SwitchInst &I);
518 void visitUnreachable(UnreachableInst &I) { /* noop */ }
520 // Helpers for visitSwitch
521 bool handleSmallSwitchRange(CaseRec& CR,
522 CaseRecVector& WorkList,
524 MachineBasicBlock* Default);
525 bool handleJTSwitchCase(CaseRec& CR,
526 CaseRecVector& WorkList,
528 MachineBasicBlock* Default);
529 bool handleBTSplitSwitchCase(CaseRec& CR,
530 CaseRecVector& WorkList,
532 MachineBasicBlock* Default);
533 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
534 void visitJumpTable(SelectionDAGISel::JumpTable &JT);
535 void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
536 SelectionDAGISel::JumpTableHeader &JTH);
538 // These all get lowered before this pass.
539 void visitInvoke(InvokeInst &I);
540 void visitInvoke(InvokeInst &I, bool AsTerminator);
541 void visitUnwind(UnwindInst &I);
543 void visitScalarBinary(User &I, unsigned OpCode);
544 void visitVectorBinary(User &I, unsigned OpCode);
545 void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp);
546 void visitShift(User &I, unsigned Opcode);
547 void visitAdd(User &I) {
548 if (isa<VectorType>(I.getType()))
549 visitVectorBinary(I, ISD::VADD);
550 else if (I.getType()->isFloatingPoint())
551 visitScalarBinary(I, ISD::FADD);
553 visitScalarBinary(I, ISD::ADD);
555 void visitSub(User &I);
556 void visitMul(User &I) {
557 if (isa<VectorType>(I.getType()))
558 visitVectorBinary(I, ISD::VMUL);
559 else if (I.getType()->isFloatingPoint())
560 visitScalarBinary(I, ISD::FMUL);
562 visitScalarBinary(I, ISD::MUL);
564 void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); }
565 void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); }
566 void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); }
567 void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); }
568 void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); }
569 void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); }
570 void visitAnd (User &I) { visitEitherBinary(I, ISD::AND, ISD::VAND ); }
571 void visitOr (User &I) { visitEitherBinary(I, ISD::OR, ISD::VOR ); }
572 void visitXor (User &I) { visitEitherBinary(I, ISD::XOR, ISD::VXOR ); }
573 void visitShl (User &I) { visitShift(I, ISD::SHL); }
574 void visitLShr(User &I) { visitShift(I, ISD::SRL); }
575 void visitAShr(User &I) { visitShift(I, ISD::SRA); }
576 void visitICmp(User &I);
577 void visitFCmp(User &I);
578 // Visit the conversion instructions
579 void visitTrunc(User &I);
580 void visitZExt(User &I);
581 void visitSExt(User &I);
582 void visitFPTrunc(User &I);
583 void visitFPExt(User &I);
584 void visitFPToUI(User &I);
585 void visitFPToSI(User &I);
586 void visitUIToFP(User &I);
587 void visitSIToFP(User &I);
588 void visitPtrToInt(User &I);
589 void visitIntToPtr(User &I);
590 void visitBitCast(User &I);
592 void visitExtractElement(User &I);
593 void visitInsertElement(User &I);
594 void visitShuffleVector(User &I);
596 void visitGetElementPtr(User &I);
597 void visitSelect(User &I);
599 void visitMalloc(MallocInst &I);
600 void visitFree(FreeInst &I);
601 void visitAlloca(AllocaInst &I);
602 void visitLoad(LoadInst &I);
603 void visitStore(StoreInst &I);
604 void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
605 void visitCall(CallInst &I);
606 void visitInlineAsm(CallInst &I);
607 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
608 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
610 void visitVAStart(CallInst &I);
611 void visitVAArg(VAArgInst &I);
612 void visitVAEnd(CallInst &I);
613 void visitVACopy(CallInst &I);
615 void visitMemIntrinsic(CallInst &I, unsigned Op);
617 void visitUserOp1(Instruction &I) {
618 assert(0 && "UserOp1 should not exist at instruction selection time!");
621 void visitUserOp2(Instruction &I) {
622 assert(0 && "UserOp2 should not exist at instruction selection time!");
626 } // end namespace llvm
628 SDOperand SelectionDAGLowering::getValue(const Value *V) {
629 SDOperand &N = NodeMap[V];
632 const Type *VTy = V->getType();
633 MVT::ValueType VT = TLI.getValueType(VTy);
634 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
635 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
636 visit(CE->getOpcode(), *CE);
637 SDOperand N1 = NodeMap[V];
638 assert(N1.Val && "visit didn't populate the ValueMap!");
640 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
641 return N = DAG.getGlobalAddress(GV, VT);
642 } else if (isa<ConstantPointerNull>(C)) {
643 return N = DAG.getConstant(0, TLI.getPointerTy());
644 } else if (isa<UndefValue>(C)) {
645 if (!isa<VectorType>(VTy))
646 return N = DAG.getNode(ISD::UNDEF, VT);
648 // Create a VBUILD_VECTOR of undef nodes.
649 const VectorType *PTy = cast<VectorType>(VTy);
650 unsigned NumElements = PTy->getNumElements();
651 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
653 SmallVector<SDOperand, 8> Ops;
654 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT));
656 // Create a VConstant node with generic Vector type.
657 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
658 Ops.push_back(DAG.getValueType(PVT));
659 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
660 &Ops[0], Ops.size());
661 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
662 return N = DAG.getConstantFP(CFP->getValue(), VT);
663 } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) {
664 unsigned NumElements = PTy->getNumElements();
665 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
667 // Now that we know the number and type of the elements, push a
668 // Constant or ConstantFP node onto the ops list for each element of
669 // the packed constant.
670 SmallVector<SDOperand, 8> Ops;
671 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
672 for (unsigned i = 0; i != NumElements; ++i)
673 Ops.push_back(getValue(CP->getOperand(i)));
675 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
677 if (MVT::isFloatingPoint(PVT))
678 Op = DAG.getConstantFP(0, PVT);
680 Op = DAG.getConstant(0, PVT);
681 Ops.assign(NumElements, Op);
684 // Create a VBUILD_VECTOR node with generic Vector type.
685 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
686 Ops.push_back(DAG.getValueType(PVT));
687 return NodeMap[V] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0],
690 // Canonicalize all constant ints to be unsigned.
691 return N = DAG.getConstant(cast<ConstantInt>(C)->getZExtValue(),VT);
695 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
696 std::map<const AllocaInst*, int>::iterator SI =
697 FuncInfo.StaticAllocaMap.find(AI);
698 if (SI != FuncInfo.StaticAllocaMap.end())
699 return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
702 unsigned InReg = FuncInfo.ValueMap[V];
703 assert(InReg && "Value not in map!");
705 // If this type is not legal, make it so now.
706 if (VT != MVT::Vector) {
707 if (TLI.getTypeAction(VT) == TargetLowering::Expand) {
708 // Source must be expanded. This input value is actually coming from the
709 // register pair InReg and InReg+1.
710 MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
711 unsigned NumVals = TLI.getNumElements(VT);
712 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
714 N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
716 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
717 N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
718 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
721 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
722 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
723 if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case
724 N = MVT::isFloatingPoint(VT)
725 ? DAG.getNode(ISD::FP_ROUND, VT, N)
726 : DAG.getNode(ISD::TRUNCATE, VT, N);
729 // Otherwise, if this is a vector, make it available as a generic vector
731 MVT::ValueType PTyElementVT, PTyLegalElementVT;
732 const VectorType *PTy = cast<VectorType>(VTy);
733 unsigned NE = TLI.getVectorTypeBreakdown(PTy, PTyElementVT,
736 // Build a VBUILD_VECTOR with the input registers.
737 SmallVector<SDOperand, 8> Ops;
738 if (PTyElementVT == PTyLegalElementVT) {
739 // If the value types are legal, just VBUILD the CopyFromReg nodes.
740 for (unsigned i = 0; i != NE; ++i)
741 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
743 } else if (PTyElementVT < PTyLegalElementVT) {
744 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate.
745 for (unsigned i = 0; i != NE; ++i) {
746 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
748 if (MVT::isFloatingPoint(PTyElementVT))
749 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
751 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op);
755 // If the register was expanded, use BUILD_PAIR.
756 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!");
757 for (unsigned i = 0; i != NE/2; ++i) {
758 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
760 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
762 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1));
766 Ops.push_back(DAG.getConstant(NE, MVT::i32));
767 Ops.push_back(DAG.getValueType(PTyLegalElementVT));
768 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
770 // Finally, use a VBIT_CONVERT to make this available as the appropriate
772 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
773 DAG.getConstant(PTy->getNumElements(),
775 DAG.getValueType(TLI.getValueType(PTy->getElementType())));
782 void SelectionDAGLowering::visitRet(ReturnInst &I) {
783 if (I.getNumOperands() == 0) {
784 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
787 SmallVector<SDOperand, 8> NewValues;
788 NewValues.push_back(getRoot());
789 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
790 SDOperand RetOp = getValue(I.getOperand(i));
792 // If this is an integer return value, we need to promote it ourselves to
793 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
795 // FIXME: C calling convention requires the return type to be promoted to
796 // at least 32-bit. But this is not necessary for non-C calling conventions.
797 if (MVT::isInteger(RetOp.getValueType()) &&
798 RetOp.getValueType() < MVT::i64) {
799 MVT::ValueType TmpVT;
800 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
801 TmpVT = TLI.getTypeToTransformTo(MVT::i32);
804 const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
805 ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
806 if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
807 ExtendKind = ISD::SIGN_EXTEND;
808 if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
809 ExtendKind = ISD::ZERO_EXTEND;
810 RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
812 NewValues.push_back(RetOp);
813 NewValues.push_back(DAG.getConstant(false, MVT::i32));
815 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
816 &NewValues[0], NewValues.size()));
819 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
820 /// the current basic block, add it to ValueMap now so that we'll get a
822 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
823 // No need to export constants.
824 if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
827 if (FuncInfo.isExportedInst(V)) return;
829 unsigned Reg = FuncInfo.InitializeRegForValue(V);
830 PendingLoads.push_back(CopyValueToVirtualRegister(V, Reg));
833 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
834 const BasicBlock *FromBB) {
835 // The operands of the setcc have to be in this block. We don't know
836 // how to export them from some other block.
837 if (Instruction *VI = dyn_cast<Instruction>(V)) {
838 // Can export from current BB.
839 if (VI->getParent() == FromBB)
842 // Is already exported, noop.
843 return FuncInfo.isExportedInst(V);
846 // If this is an argument, we can export it if the BB is the entry block or
847 // if it is already exported.
848 if (isa<Argument>(V)) {
849 if (FromBB == &FromBB->getParent()->getEntryBlock())
852 // Otherwise, can only export this if it is already exported.
853 return FuncInfo.isExportedInst(V);
856 // Otherwise, constants can always be exported.
860 static bool InBlock(const Value *V, const BasicBlock *BB) {
861 if (const Instruction *I = dyn_cast<Instruction>(V))
862 return I->getParent() == BB;
866 /// FindMergedConditions - If Cond is an expression like
867 void SelectionDAGLowering::FindMergedConditions(Value *Cond,
868 MachineBasicBlock *TBB,
869 MachineBasicBlock *FBB,
870 MachineBasicBlock *CurBB,
872 // If this node is not part of the or/and tree, emit it as a branch.
873 Instruction *BOp = dyn_cast<Instruction>(Cond);
875 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
876 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
877 BOp->getParent() != CurBB->getBasicBlock() ||
878 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
879 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
880 const BasicBlock *BB = CurBB->getBasicBlock();
882 // If the leaf of the tree is a comparison, merge the condition into
884 if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) &&
885 // The operands of the cmp have to be in this block. We don't know
886 // how to export them from some other block. If this is the first block
887 // of the sequence, no exporting is needed.
889 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
890 isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) {
891 BOp = cast<Instruction>(Cond);
892 ISD::CondCode Condition;
893 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
894 switch (IC->getPredicate()) {
895 default: assert(0 && "Unknown icmp predicate opcode!");
896 case ICmpInst::ICMP_EQ: Condition = ISD::SETEQ; break;
897 case ICmpInst::ICMP_NE: Condition = ISD::SETNE; break;
898 case ICmpInst::ICMP_SLE: Condition = ISD::SETLE; break;
899 case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break;
900 case ICmpInst::ICMP_SGE: Condition = ISD::SETGE; break;
901 case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break;
902 case ICmpInst::ICMP_SLT: Condition = ISD::SETLT; break;
903 case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break;
904 case ICmpInst::ICMP_SGT: Condition = ISD::SETGT; break;
905 case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break;
907 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
908 ISD::CondCode FPC, FOC;
909 switch (FC->getPredicate()) {
910 default: assert(0 && "Unknown fcmp predicate opcode!");
911 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
912 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
913 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
914 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
915 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
916 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
917 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
918 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
919 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
920 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
921 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
922 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
923 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
924 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
925 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
926 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
928 if (FiniteOnlyFPMath())
933 Condition = ISD::SETEQ; // silence warning.
934 assert(0 && "Unknown compare instruction");
937 SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
938 BOp->getOperand(1), NULL, TBB, FBB, CurBB);
939 SwitchCases.push_back(CB);
943 // Create a CaseBlock record representing this branch.
944 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
945 NULL, TBB, FBB, CurBB);
946 SwitchCases.push_back(CB);
951 // Create TmpBB after CurBB.
952 MachineFunction::iterator BBI = CurBB;
953 MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock());
954 CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB);
956 if (Opc == Instruction::Or) {
965 // Emit the LHS condition.
966 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc);
968 // Emit the RHS condition into TmpBB.
969 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
971 assert(Opc == Instruction::And && "Unknown merge op!");
979 // This requires creation of TmpBB after CurBB.
981 // Emit the LHS condition.
982 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc);
984 // Emit the RHS condition into TmpBB.
985 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
989 /// If the set of cases should be emitted as a series of branches, return true.
990 /// If we should emit this as a bunch of and/or'd together conditions, return
993 ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) {
994 if (Cases.size() != 2) return true;
996 // If this is two comparisons of the same values or'd or and'd together, they
997 // will get folded into a single comparison, so don't emit two blocks.
998 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
999 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
1000 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
1001 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
1008 void SelectionDAGLowering::visitBr(BranchInst &I) {
1009 // Update machine-CFG edges.
1010 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
1012 // Figure out which block is immediately after the current one.
1013 MachineBasicBlock *NextBlock = 0;
1014 MachineFunction::iterator BBI = CurMBB;
1015 if (++BBI != CurMBB->getParent()->end())
1018 if (I.isUnconditional()) {
1019 // If this is not a fall-through branch, emit the branch.
1020 if (Succ0MBB != NextBlock)
1021 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1022 DAG.getBasicBlock(Succ0MBB)));
1024 // Update machine-CFG edges.
1025 CurMBB->addSuccessor(Succ0MBB);
1030 // If this condition is one of the special cases we handle, do special stuff
1032 Value *CondVal = I.getCondition();
1033 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1035 // If this is a series of conditions that are or'd or and'd together, emit
1036 // this as a sequence of branches instead of setcc's with and/or operations.
1037 // For example, instead of something like:
1050 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1051 if (BOp->hasOneUse() &&
1052 (BOp->getOpcode() == Instruction::And ||
1053 BOp->getOpcode() == Instruction::Or)) {
1054 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode());
1055 // If the compares in later blocks need to use values not currently
1056 // exported from this block, export them now. This block should always
1057 // be the first entry.
1058 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!");
1060 // Allow some cases to be rejected.
1061 if (ShouldEmitAsBranches(SwitchCases)) {
1062 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1063 ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1064 ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1067 // Emit the branch for this block.
1068 visitSwitchCase(SwitchCases[0]);
1069 SwitchCases.erase(SwitchCases.begin());
1073 // Okay, we decided not to do this, remove any inserted MBB's and clear
1075 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1076 CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB);
1078 SwitchCases.clear();
1082 // Create a CaseBlock record representing this branch.
1083 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
1084 NULL, Succ0MBB, Succ1MBB, CurMBB);
1085 // Use visitSwitchCase to actually insert the fast branch sequence for this
1087 visitSwitchCase(CB);
1090 /// visitSwitchCase - Emits the necessary code to represent a single node in
1091 /// the binary search tree resulting from lowering a switch instruction.
1092 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
1094 SDOperand CondLHS = getValue(CB.CmpLHS);
1096 // Build the setcc now.
1097 if (CB.CmpMHS == NULL) {
1098 // Fold "(X == true)" to X and "(X == false)" to !X to
1099 // handle common cases produced by branch lowering.
1100 if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
1102 else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
1103 SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
1104 Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
1106 Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1108 assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
1110 uint64_t Low = cast<ConstantInt>(CB.CmpLHS)->getSExtValue();
1111 uint64_t High = cast<ConstantInt>(CB.CmpRHS)->getSExtValue();
1113 SDOperand CmpOp = getValue(CB.CmpMHS);
1114 MVT::ValueType VT = CmpOp.getValueType();
1116 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
1117 Cond = DAG.getSetCC(MVT::i1, CmpOp, DAG.getConstant(High, VT), ISD::SETLE);
1119 SDOperand SUB = DAG.getNode(ISD::SUB, VT, CmpOp, DAG.getConstant(Low, VT));
1120 Cond = DAG.getSetCC(MVT::i1, SUB,
1121 DAG.getConstant(High-Low, VT), ISD::SETULE);
1126 // Set NextBlock to be the MBB immediately after the current one, if any.
1127 // This is used to avoid emitting unnecessary branches to the next block.
1128 MachineBasicBlock *NextBlock = 0;
1129 MachineFunction::iterator BBI = CurMBB;
1130 if (++BBI != CurMBB->getParent()->end())
1133 // If the lhs block is the next block, invert the condition so that we can
1134 // fall through to the lhs instead of the rhs block.
1135 if (CB.TrueBB == NextBlock) {
1136 std::swap(CB.TrueBB, CB.FalseBB);
1137 SDOperand True = DAG.getConstant(1, Cond.getValueType());
1138 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
1140 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond,
1141 DAG.getBasicBlock(CB.TrueBB));
1142 if (CB.FalseBB == NextBlock)
1143 DAG.setRoot(BrCond);
1145 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1146 DAG.getBasicBlock(CB.FalseBB)));
1147 // Update successor info
1148 CurMBB->addSuccessor(CB.TrueBB);
1149 CurMBB->addSuccessor(CB.FalseBB);
1152 /// visitJumpTable - Emit JumpTable node in the current MBB
1153 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
1154 // Emit the code for the jump table
1155 assert(JT.Reg != -1UL && "Should lower JT Header first!");
1156 MVT::ValueType PTy = TLI.getPointerTy();
1157 SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
1158 SDOperand Table = DAG.getJumpTable(JT.JTI, PTy);
1159 DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1),
1164 /// visitJumpTableHeader - This function emits necessary code to produce index
1165 /// in the JumpTable from switch case.
1166 void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
1167 SelectionDAGISel::JumpTableHeader &JTH) {
1168 // Subtract the lowest switch case value from the value being switched on
1169 // and conditional branch to default mbb if the result is greater than the
1170 // difference between smallest and largest cases.
1171 SDOperand SwitchOp = getValue(JTH.SValue);
1172 MVT::ValueType VT = SwitchOp.getValueType();
1173 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1174 DAG.getConstant(JTH.First, VT));
1176 // The SDNode we just created, which holds the value being switched on
1177 // minus the the smallest case value, needs to be copied to a virtual
1178 // register so it can be used as an index into the jump table in a
1179 // subsequent basic block. This value may be smaller or larger than the
1180 // target's pointer type, and therefore require extension or truncating.
1181 if (VT > TLI.getPointerTy())
1182 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
1184 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
1186 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
1187 SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
1188 JT.Reg = JumpTableReg;
1190 // Emit the range check for the jump table, and branch to the default
1191 // block for the switch statement if the value being switched on exceeds
1192 // the largest case in the switch.
1193 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
1194 DAG.getConstant(JTH.Last-JTH.First,VT),
1197 // Set NextBlock to be the MBB immediately after the current one, if any.
1198 // This is used to avoid emitting unnecessary branches to the next block.
1199 MachineBasicBlock *NextBlock = 0;
1200 MachineFunction::iterator BBI = CurMBB;
1201 if (++BBI != CurMBB->getParent()->end())
1204 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
1205 DAG.getBasicBlock(JT.Default));
1207 if (JT.MBB == NextBlock)
1208 DAG.setRoot(BrCond);
1210 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1211 DAG.getBasicBlock(JT.MBB)));
1215 void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
1216 assert(0 && "Should never be visited directly");
1218 void SelectionDAGLowering::visitInvoke(InvokeInst &I, bool AsTerminator) {
1219 // Retrieve successors.
1220 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1221 MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1223 if (!AsTerminator) {
1224 // Mark landing pad so that it doesn't get deleted in branch folding.
1225 LandingPad->setIsLandingPad();
1227 // Insert a label before the invoke call to mark the try range.
1228 // This can be used to detect deletion of the invoke via the
1229 // MachineModuleInfo.
1230 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
1231 unsigned BeginLabel = MMI->NextLabelID();
1232 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1233 DAG.getConstant(BeginLabel, MVT::i32)));
1235 LowerCallTo(I, I.getCalledValue()->getType(),
1238 getValue(I.getOperand(0)),
1241 // Insert a label before the invoke call to mark the try range.
1242 // This can be used to detect deletion of the invoke via the
1243 // MachineModuleInfo.
1244 unsigned EndLabel = MMI->NextLabelID();
1245 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1246 DAG.getConstant(EndLabel, MVT::i32)));
1248 // Inform MachineModuleInfo of range.
1249 MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
1251 // Update successor info
1252 CurMBB->addSuccessor(Return);
1253 CurMBB->addSuccessor(LandingPad);
1255 // Drop into normal successor.
1256 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1257 DAG.getBasicBlock(Return)));
1261 void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
1264 /// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for
1265 /// small case ranges).
1266 bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
1267 CaseRecVector& WorkList,
1269 MachineBasicBlock* Default) {
1270 Case& BackCase = *(CR.Range.second-1);
1272 // Size is the number of Cases represented by this range.
1273 unsigned Size = CR.Range.second - CR.Range.first;
1277 // Get the MachineFunction which holds the current MBB. This is used when
1278 // inserting any additional MBBs necessary to represent the switch.
1279 MachineFunction *CurMF = CurMBB->getParent();
1281 // Figure out which block is immediately after the current one.
1282 MachineBasicBlock *NextBlock = 0;
1283 MachineFunction::iterator BBI = CR.CaseBB;
1285 if (++BBI != CurMBB->getParent()->end())
1288 // TODO: If any two of the cases has the same destination, and if one value
1289 // is the same as the other, but has one bit unset that the other has set,
1290 // use bit manipulation to do two compares at once. For example:
1291 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
1293 // Rearrange the case blocks so that the last one falls through if possible.
1294 if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) {
1295 // The last case block won't fall through into 'NextBlock' if we emit the
1296 // branches in this order. See if rearranging a case value would help.
1297 for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
1298 if (I->BB == NextBlock) {
1299 std::swap(*I, BackCase);
1305 // Create a CaseBlock record representing a conditional branch to
1306 // the Case's target mbb if the value being switched on SV is equal
1308 MachineBasicBlock *CurBlock = CR.CaseBB;
1309 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
1310 MachineBasicBlock *FallThrough;
1312 FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock());
1313 CurMF->getBasicBlockList().insert(BBI, FallThrough);
1315 // If the last case doesn't match, go to the default block.
1316 FallThrough = Default;
1319 Value *RHS, *LHS, *MHS;
1321 if (I->High == I->Low) {
1322 // This is just small small case range :) containing exactly 1 case
1324 LHS = SV; RHS = I->High; MHS = NULL;
1327 LHS = I->Low; MHS = SV; RHS = I->High;
1329 SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS,
1330 I->BB, FallThrough, CurBlock);
1332 // If emitting the first comparison, just call visitSwitchCase to emit the
1333 // code into the current block. Otherwise, push the CaseBlock onto the
1334 // vector to be later processed by SDISel, and insert the node's MBB
1335 // before the next MBB.
1336 if (CurBlock == CurMBB)
1337 visitSwitchCase(CB);
1339 SwitchCases.push_back(CB);
1341 CurBlock = FallThrough;
1347 /// handleJTSwitchCase - Emit jumptable for current switch case range
1348 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
1349 CaseRecVector& WorkList,
1351 MachineBasicBlock* Default) {
1352 Case& FrontCase = *CR.Range.first;
1353 Case& BackCase = *(CR.Range.second-1);
1355 // Size is the number of Cases represented by this range.
1356 unsigned Size = CR.Range.second - CR.Range.first;
1358 int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
1359 int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue();
1362 for (CaseItr I = CR.Range.first, E = CR.Range.second;
1366 if ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
1367 !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
1371 double Density = (double)TSize / (double)((Last - First) + 1ULL);
1375 DOUT << "Lowering jump table\n"
1376 << "First entry: " << First << ". Last entry: " << Last << "\n"
1377 << "Size: " << TSize << ". Density: " << Density << "\n";
1379 // Get the MachineFunction which holds the current MBB. This is used when
1380 // inserting any additional MBBs necessary to represent the switch.
1381 MachineFunction *CurMF = CurMBB->getParent();
1383 // Figure out which block is immediately after the current one.
1384 MachineBasicBlock *NextBlock = 0;
1385 MachineFunction::iterator BBI = CR.CaseBB;
1387 if (++BBI != CurMBB->getParent()->end())
1390 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1392 // Create a new basic block to hold the code for loading the address
1393 // of the jump table, and jumping to it. Update successor information;
1394 // we will either branch to the default case for the switch, or the jump
1396 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
1397 CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
1398 CR.CaseBB->addSuccessor(Default);
1399 CR.CaseBB->addSuccessor(JumpTableBB);
1401 // Build a vector of destination BBs, corresponding to each target
1402 // of the jump table. If the value of the jump table slot corresponds to
1403 // a case statement, push the case's BB onto the vector, otherwise, push
1405 std::vector<MachineBasicBlock*> DestBBs;
1406 int64_t TEI = First;
1407 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) {
1408 int64_t Low = cast<ConstantInt>(I->Low)->getSExtValue();
1409 int64_t High = cast<ConstantInt>(I->High)->getSExtValue();
1411 if ((Low <= TEI) && (TEI <= High)) {
1412 DestBBs.push_back(I->BB);
1416 DestBBs.push_back(Default);
1420 // Update successor info. Add one edge to each unique successor.
1421 BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs());
1422 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
1423 E = DestBBs.end(); I != E; ++I) {
1424 if (!SuccsHandled[(*I)->getNumber()]) {
1425 SuccsHandled[(*I)->getNumber()] = true;
1426 JumpTableBB->addSuccessor(*I);
1430 // Create a jump table index for this jump table, or return an existing
1432 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
1434 // Set the jump table information so that we can codegen it as a second
1435 // MachineBasicBlock
1436 SelectionDAGISel::JumpTable JT(-1UL, JTI, JumpTableBB, Default);
1437 SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
1438 (CR.CaseBB == CurMBB));
1439 if (CR.CaseBB == CurMBB)
1440 visitJumpTableHeader(JT, JTH);
1442 JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT));
1447 /// handleBTSplitSwitchCase - emit comparison and split binary search tree into
1449 bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
1450 CaseRecVector& WorkList,
1452 MachineBasicBlock* Default) {
1453 // Get the MachineFunction which holds the current MBB. This is used when
1454 // inserting any additional MBBs necessary to represent the switch.
1455 MachineFunction *CurMF = CurMBB->getParent();
1457 // Figure out which block is immediately after the current one.
1458 MachineBasicBlock *NextBlock = 0;
1459 MachineFunction::iterator BBI = CR.CaseBB;
1461 if (++BBI != CurMBB->getParent()->end())
1464 Case& FrontCase = *CR.Range.first;
1465 Case& BackCase = *(CR.Range.second-1);
1466 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
1468 // Size is the number of Cases represented by this range.
1469 unsigned Size = CR.Range.second - CR.Range.first;
1471 int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
1472 int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue();
1474 CaseItr Pivot = CR.Range.first + Size/2;
1476 // Select optimal pivot, maximizing sum density of LHS and RHS. This will
1477 // (heuristically) allow us to emit JumpTable's later.
1479 for (CaseItr I = CR.Range.first, E = CR.Range.second;
1483 uint64_t LSize = FrontCase.size();
1484 uint64_t RSize = TSize-LSize;
1485 for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
1487 int64_t LEnd = cast<ConstantInt>(I->High)->getSExtValue();
1488 int64_t RBegin = cast<ConstantInt>(J->Low)->getSExtValue();
1489 double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL);
1490 double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL);
1491 if (Density < (LDensity + RDensity)) {
1493 Density = LDensity + RDensity;
1500 CaseRange LHSR(CR.Range.first, Pivot);
1501 CaseRange RHSR(Pivot, CR.Range.second);
1502 Constant *C = Pivot->Low;
1503 MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
1505 // We know that we branch to the LHS if the Value being switched on is
1506 // less than the Pivot value, C. We use this to optimize our binary
1507 // tree a bit, by recognizing that if SV is greater than or equal to the
1508 // LHS's Case Value, and that Case Value is exactly one less than the
1509 // Pivot's Value, then we can branch directly to the LHS's Target,
1510 // rather than creating a leaf node for it.
1511 if ((LHSR.second - LHSR.first) == 1 &&
1512 LHSR.first->High == CR.GE &&
1513 cast<ConstantInt>(C)->getSExtValue() ==
1514 (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) {
1515 TrueBB = LHSR.first->BB;
1517 TrueBB = new MachineBasicBlock(LLVMBB);
1518 CurMF->getBasicBlockList().insert(BBI, TrueBB);
1519 WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
1522 // Similar to the optimization above, if the Value being switched on is
1523 // known to be less than the Constant CR.LT, and the current Case Value
1524 // is CR.LT - 1, then we can branch directly to the target block for
1525 // the current Case Value, rather than emitting a RHS leaf node for it.
1526 if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
1527 cast<ConstantInt>(RHSR.first->Low)->getSExtValue() ==
1528 (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) {
1529 FalseBB = RHSR.first->BB;
1531 FalseBB = new MachineBasicBlock(LLVMBB);
1532 CurMF->getBasicBlockList().insert(BBI, FalseBB);
1533 WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
1536 // Create a CaseBlock record representing a conditional branch to
1537 // the LHS node if the value being switched on SV is less than C.
1538 // Otherwise, branch to LHS.
1539 SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL,
1540 TrueBB, FalseBB, CR.CaseBB);
1542 if (CR.CaseBB == CurMBB)
1543 visitSwitchCase(CB);
1545 SwitchCases.push_back(CB);
1550 // Clusterify - Transform simple list of Cases into list of CaseRange's
1551 unsigned SelectionDAGLowering::Clusterify(CaseVector& Cases,
1552 const SwitchInst& SI) {
1553 unsigned numCmps = 0;
1555 // Start with "simple" cases
1556 for (unsigned i = 1; i < SI.getNumSuccessors(); ++i) {
1557 MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)];
1558 Cases.push_back(Case(SI.getSuccessorValue(i),
1559 SI.getSuccessorValue(i),
1562 sort(Cases.begin(), Cases.end(), CaseCmp());
1564 // Merge case into clusters
1565 if (Cases.size()>=2)
1566 for (CaseItr I=Cases.begin(), J=++(Cases.begin()), E=Cases.end(); J!=E; ) {
1567 int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue();
1568 int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue();
1569 MachineBasicBlock* nextBB = J->BB;
1570 MachineBasicBlock* currentBB = I->BB;
1572 // If the two neighboring cases go to the same destination, merge them
1573 // into a single case.
1574 if ((nextValue-currentValue==1) && (currentBB == nextBB)) {
1582 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
1583 if (I->Low != I->High)
1584 // A range counts double, since it requires two compares.
1591 void SelectionDAGLowering::visitSwitch(SwitchInst &SI) {
1592 // Figure out which block is immediately after the current one.
1593 MachineBasicBlock *NextBlock = 0;
1594 MachineFunction::iterator BBI = CurMBB;
1596 MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
1598 // If there is only the default destination, branch to it if it is not the
1599 // next basic block. Otherwise, just fall through.
1600 if (SI.getNumOperands() == 2) {
1601 // Update machine-CFG edges.
1603 // If this is not a fall-through branch, emit the branch.
1604 if (Default != NextBlock)
1605 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1606 DAG.getBasicBlock(Default)));
1608 CurMBB->addSuccessor(Default);
1612 // If there are any non-default case statements, create a vector of Cases
1613 // representing each one, and sort the vector so that we can efficiently
1614 // create a binary search tree from them.
1616 unsigned numCmps = Clusterify(Cases, SI);
1617 DOUT << "Clusterify finished. Total clusters: " << Cases.size()
1618 << ". Total compares: " << numCmps << "\n";
1620 // Get the Value to be switched on and default basic blocks, which will be
1621 // inserted into CaseBlock records, representing basic blocks in the binary
1623 Value *SV = SI.getOperand(0);
1625 // Push the initial CaseRec onto the worklist
1626 CaseRecVector WorkList;
1627 WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
1629 while (!WorkList.empty()) {
1630 // Grab a record representing a case range to process off the worklist
1631 CaseRec CR = WorkList.back();
1632 WorkList.pop_back();
1634 // If the range has few cases (two or less) emit a series of specific
1636 if (handleSmallSwitchRange(CR, WorkList, SV, Default))
1639 // If the switch has more than 5 blocks, and at least 31.25% dense, and the
1640 // target supports indirect branches, then emit a jump table rather than
1641 // lowering the switch to a binary tree of conditional branches.
1642 if (handleJTSwitchCase(CR, WorkList, SV, Default))
1645 // Emit binary tree. We need to pick a pivot, and push left and right ranges
1646 // onto the worklist. Leafs are handled via handleSmallSwitchRange() call.
1647 handleBTSplitSwitchCase(CR, WorkList, SV, Default);
1652 void SelectionDAGLowering::visitSub(User &I) {
1653 // -0.0 - X --> fneg
1654 const Type *Ty = I.getType();
1655 if (isa<VectorType>(Ty)) {
1656 visitVectorBinary(I, ISD::VSUB);
1657 } else if (Ty->isFloatingPoint()) {
1658 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
1659 if (CFP->isExactlyValue(-0.0)) {
1660 SDOperand Op2 = getValue(I.getOperand(1));
1661 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
1664 visitScalarBinary(I, ISD::FSUB);
1666 visitScalarBinary(I, ISD::SUB);
1669 void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) {
1670 SDOperand Op1 = getValue(I.getOperand(0));
1671 SDOperand Op2 = getValue(I.getOperand(1));
1673 setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
1677 SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) {
1678 assert(isa<VectorType>(I.getType()));
1679 const VectorType *Ty = cast<VectorType>(I.getType());
1680 SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType()));
1682 setValue(&I, DAG.getNode(OpCode, MVT::Vector,
1683 getValue(I.getOperand(0)),
1684 getValue(I.getOperand(1)),
1685 DAG.getConstant(Ty->getNumElements(), MVT::i32),
1689 void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp,
1690 unsigned VectorOp) {
1691 if (isa<VectorType>(I.getType()))
1692 visitVectorBinary(I, VectorOp);
1694 visitScalarBinary(I, ScalarOp);
1697 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
1698 SDOperand Op1 = getValue(I.getOperand(0));
1699 SDOperand Op2 = getValue(I.getOperand(1));
1701 if (TLI.getShiftAmountTy() < Op2.getValueType())
1702 Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
1703 else if (TLI.getShiftAmountTy() > Op2.getValueType())
1704 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
1706 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
1709 void SelectionDAGLowering::visitICmp(User &I) {
1710 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
1711 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I))
1712 predicate = IC->getPredicate();
1713 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
1714 predicate = ICmpInst::Predicate(IC->getPredicate());
1715 SDOperand Op1 = getValue(I.getOperand(0));
1716 SDOperand Op2 = getValue(I.getOperand(1));
1717 ISD::CondCode Opcode;
1718 switch (predicate) {
1719 case ICmpInst::ICMP_EQ : Opcode = ISD::SETEQ; break;
1720 case ICmpInst::ICMP_NE : Opcode = ISD::SETNE; break;
1721 case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
1722 case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
1723 case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
1724 case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
1725 case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
1726 case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
1727 case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
1728 case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
1730 assert(!"Invalid ICmp predicate value");
1731 Opcode = ISD::SETEQ;
1734 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
1737 void SelectionDAGLowering::visitFCmp(User &I) {
1738 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
1739 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I))
1740 predicate = FC->getPredicate();
1741 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
1742 predicate = FCmpInst::Predicate(FC->getPredicate());
1743 SDOperand Op1 = getValue(I.getOperand(0));
1744 SDOperand Op2 = getValue(I.getOperand(1));
1745 ISD::CondCode Condition, FOC, FPC;
1746 switch (predicate) {
1747 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
1748 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
1749 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
1750 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
1751 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
1752 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
1753 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
1754 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
1755 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
1756 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
1757 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
1758 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
1759 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
1760 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
1761 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
1762 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
1764 assert(!"Invalid FCmp predicate value");
1765 FOC = FPC = ISD::SETFALSE;
1768 if (FiniteOnlyFPMath())
1772 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition));
1775 void SelectionDAGLowering::visitSelect(User &I) {
1776 SDOperand Cond = getValue(I.getOperand(0));
1777 SDOperand TrueVal = getValue(I.getOperand(1));
1778 SDOperand FalseVal = getValue(I.getOperand(2));
1779 if (!isa<VectorType>(I.getType())) {
1780 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
1781 TrueVal, FalseVal));
1783 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal,
1784 *(TrueVal.Val->op_end()-2),
1785 *(TrueVal.Val->op_end()-1)));
1790 void SelectionDAGLowering::visitTrunc(User &I) {
1791 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
1792 SDOperand N = getValue(I.getOperand(0));
1793 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1794 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1797 void SelectionDAGLowering::visitZExt(User &I) {
1798 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1799 // ZExt also can't be a cast to bool for same reason. So, nothing much to do
1800 SDOperand N = getValue(I.getOperand(0));
1801 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1802 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1805 void SelectionDAGLowering::visitSExt(User &I) {
1806 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1807 // SExt also can't be a cast to bool for same reason. So, nothing much to do
1808 SDOperand N = getValue(I.getOperand(0));
1809 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1810 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N));
1813 void SelectionDAGLowering::visitFPTrunc(User &I) {
1814 // FPTrunc is never a no-op cast, no need to check
1815 SDOperand N = getValue(I.getOperand(0));
1816 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1817 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N));
1820 void SelectionDAGLowering::visitFPExt(User &I){
1821 // FPTrunc is never a no-op cast, no need to check
1822 SDOperand N = getValue(I.getOperand(0));
1823 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1824 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N));
1827 void SelectionDAGLowering::visitFPToUI(User &I) {
1828 // FPToUI is never a no-op cast, no need to check
1829 SDOperand N = getValue(I.getOperand(0));
1830 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1831 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N));
1834 void SelectionDAGLowering::visitFPToSI(User &I) {
1835 // FPToSI is never a no-op cast, no need to check
1836 SDOperand N = getValue(I.getOperand(0));
1837 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1838 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N));
1841 void SelectionDAGLowering::visitUIToFP(User &I) {
1842 // UIToFP is never a no-op cast, no need to check
1843 SDOperand N = getValue(I.getOperand(0));
1844 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1845 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N));
1848 void SelectionDAGLowering::visitSIToFP(User &I){
1849 // UIToFP is never a no-op cast, no need to check
1850 SDOperand N = getValue(I.getOperand(0));
1851 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1852 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N));
1855 void SelectionDAGLowering::visitPtrToInt(User &I) {
1856 // What to do depends on the size of the integer and the size of the pointer.
1857 // We can either truncate, zero extend, or no-op, accordingly.
1858 SDOperand N = getValue(I.getOperand(0));
1859 MVT::ValueType SrcVT = N.getValueType();
1860 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1862 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1863 Result = DAG.getNode(ISD::TRUNCATE, DestVT, N);
1865 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1866 Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N);
1867 setValue(&I, Result);
1870 void SelectionDAGLowering::visitIntToPtr(User &I) {
1871 // What to do depends on the size of the integer and the size of the pointer.
1872 // We can either truncate, zero extend, or no-op, accordingly.
1873 SDOperand N = getValue(I.getOperand(0));
1874 MVT::ValueType SrcVT = N.getValueType();
1875 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1876 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1877 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1879 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1880 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1883 void SelectionDAGLowering::visitBitCast(User &I) {
1884 SDOperand N = getValue(I.getOperand(0));
1885 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1886 if (DestVT == MVT::Vector) {
1887 // This is a cast to a vector from something else.
1888 // Get information about the output vector.
1889 const VectorType *DestTy = cast<VectorType>(I.getType());
1890 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
1891 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N,
1892 DAG.getConstant(DestTy->getNumElements(),MVT::i32),
1893 DAG.getValueType(EltVT)));
1896 MVT::ValueType SrcVT = N.getValueType();
1897 if (SrcVT == MVT::Vector) {
1898 // This is a cast from a vctor to something else.
1899 // Get information about the input vector.
1900 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N));
1904 // BitCast assures us that source and destination are the same size so this
1905 // is either a BIT_CONVERT or a no-op.
1906 if (DestVT != N.getValueType())
1907 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types
1909 setValue(&I, N); // noop cast.
1912 void SelectionDAGLowering::visitInsertElement(User &I) {
1913 SDOperand InVec = getValue(I.getOperand(0));
1914 SDOperand InVal = getValue(I.getOperand(1));
1915 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1916 getValue(I.getOperand(2)));
1918 SDOperand Num = *(InVec.Val->op_end()-2);
1919 SDOperand Typ = *(InVec.Val->op_end()-1);
1920 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector,
1921 InVec, InVal, InIdx, Num, Typ));
1924 void SelectionDAGLowering::visitExtractElement(User &I) {
1925 SDOperand InVec = getValue(I.getOperand(0));
1926 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1927 getValue(I.getOperand(1)));
1928 SDOperand Typ = *(InVec.Val->op_end()-1);
1929 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT,
1930 TLI.getValueType(I.getType()), InVec, InIdx));
1933 void SelectionDAGLowering::visitShuffleVector(User &I) {
1934 SDOperand V1 = getValue(I.getOperand(0));
1935 SDOperand V2 = getValue(I.getOperand(1));
1936 SDOperand Mask = getValue(I.getOperand(2));
1938 SDOperand Num = *(V1.Val->op_end()-2);
1939 SDOperand Typ = *(V2.Val->op_end()-1);
1940 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
1941 V1, V2, Mask, Num, Typ));
1945 void SelectionDAGLowering::visitGetElementPtr(User &I) {
1946 SDOperand N = getValue(I.getOperand(0));
1947 const Type *Ty = I.getOperand(0)->getType();
1949 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
1952 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1953 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
1956 uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field);
1957 N = DAG.getNode(ISD::ADD, N.getValueType(), N,
1958 getIntPtrConstant(Offset));
1960 Ty = StTy->getElementType(Field);
1962 Ty = cast<SequentialType>(Ty)->getElementType();
1964 // If this is a constant subscript, handle it quickly.
1965 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
1966 if (CI->getZExtValue() == 0) continue;
1968 TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
1969 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
1973 // N = N + Idx * ElementSize;
1974 uint64_t ElementSize = TD->getTypeSize(Ty);
1975 SDOperand IdxN = getValue(Idx);
1977 // If the index is smaller or larger than intptr_t, truncate or extend
1979 if (IdxN.getValueType() < N.getValueType()) {
1980 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
1981 } else if (IdxN.getValueType() > N.getValueType())
1982 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
1984 // If this is a multiply by a power of two, turn it into a shl
1985 // immediately. This is a very common case.
1986 if (isPowerOf2_64(ElementSize)) {
1987 unsigned Amt = Log2_64(ElementSize);
1988 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
1989 DAG.getConstant(Amt, TLI.getShiftAmountTy()));
1990 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1994 SDOperand Scale = getIntPtrConstant(ElementSize);
1995 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
1996 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
2002 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
2003 // If this is a fixed sized alloca in the entry block of the function,
2004 // allocate it statically on the stack.
2005 if (FuncInfo.StaticAllocaMap.count(&I))
2006 return; // getValue will auto-populate this.
2008 const Type *Ty = I.getAllocatedType();
2009 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
2011 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
2014 SDOperand AllocSize = getValue(I.getArraySize());
2015 MVT::ValueType IntPtr = TLI.getPointerTy();
2016 if (IntPtr < AllocSize.getValueType())
2017 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
2018 else if (IntPtr > AllocSize.getValueType())
2019 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
2021 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
2022 getIntPtrConstant(TySize));
2024 // Handle alignment. If the requested alignment is less than or equal to the
2025 // stack alignment, ignore it and round the size of the allocation up to the
2026 // stack alignment size. If the size is greater than the stack alignment, we
2027 // note this in the DYNAMIC_STACKALLOC node.
2028 unsigned StackAlign =
2029 TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
2030 if (Align <= StackAlign) {
2032 // Add SA-1 to the size.
2033 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
2034 getIntPtrConstant(StackAlign-1));
2035 // Mask out the low bits for alignment purposes.
2036 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
2037 getIntPtrConstant(~(uint64_t)(StackAlign-1)));
2040 SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) };
2041 const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
2043 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3);
2045 DAG.setRoot(DSA.getValue(1));
2047 // Inform the Frame Information that we have just allocated a variable-sized
2049 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
2052 void SelectionDAGLowering::visitLoad(LoadInst &I) {
2053 SDOperand Ptr = getValue(I.getOperand(0));
2059 // Do not serialize non-volatile loads against each other.
2060 Root = DAG.getRoot();
2063 setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0),
2064 Root, I.isVolatile()));
2067 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr,
2068 const Value *SV, SDOperand Root,
2071 if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
2072 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
2073 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr,
2074 DAG.getSrcValue(SV));
2076 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile);
2080 DAG.setRoot(L.getValue(1));
2082 PendingLoads.push_back(L.getValue(1));
2088 void SelectionDAGLowering::visitStore(StoreInst &I) {
2089 Value *SrcV = I.getOperand(0);
2090 SDOperand Src = getValue(SrcV);
2091 SDOperand Ptr = getValue(I.getOperand(1));
2092 DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
2096 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
2097 /// access memory and has no other side effects at all.
2098 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) {
2099 #define GET_NO_MEMORY_INTRINSICS
2100 #include "llvm/Intrinsics.gen"
2101 #undef GET_NO_MEMORY_INTRINSICS
2105 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't
2106 // have any side-effects or if it only reads memory.
2107 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) {
2108 #define GET_SIDE_EFFECT_INFO
2109 #include "llvm/Intrinsics.gen"
2110 #undef GET_SIDE_EFFECT_INFO
2114 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
2116 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
2117 unsigned Intrinsic) {
2118 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic);
2119 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic);
2121 // Build the operand list.
2122 SmallVector<SDOperand, 8> Ops;
2123 if (HasChain) { // If this intrinsic has side-effects, chainify it.
2125 // We don't need to serialize loads against other loads.
2126 Ops.push_back(DAG.getRoot());
2128 Ops.push_back(getRoot());
2132 // Add the intrinsic ID as an integer operand.
2133 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy()));
2135 // Add all operands of the call to the operand list.
2136 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
2137 SDOperand Op = getValue(I.getOperand(i));
2139 // If this is a vector type, force it to the right vector type.
2140 if (Op.getValueType() == MVT::Vector) {
2141 const VectorType *OpTy = cast<VectorType>(I.getOperand(i)->getType());
2142 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType());
2144 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements());
2145 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?");
2146 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op);
2149 assert(TLI.isTypeLegal(Op.getValueType()) &&
2150 "Intrinsic uses a non-legal type?");
2154 std::vector<MVT::ValueType> VTs;
2155 if (I.getType() != Type::VoidTy) {
2156 MVT::ValueType VT = TLI.getValueType(I.getType());
2157 if (VT == MVT::Vector) {
2158 const VectorType *DestTy = cast<VectorType>(I.getType());
2159 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
2161 VT = MVT::getVectorType(EltVT, DestTy->getNumElements());
2162 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?");
2165 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?");
2169 VTs.push_back(MVT::Other);
2171 const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs);
2176 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(),
2177 &Ops[0], Ops.size());
2178 else if (I.getType() != Type::VoidTy)
2179 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(),
2180 &Ops[0], Ops.size());
2182 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(),
2183 &Ops[0], Ops.size());
2186 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1);
2188 PendingLoads.push_back(Chain);
2192 if (I.getType() != Type::VoidTy) {
2193 if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
2194 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType());
2195 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
2196 DAG.getConstant(PTy->getNumElements(), MVT::i32),
2197 DAG.getValueType(EVT));
2199 setValue(&I, Result);
2203 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If
2204 /// we want to emit this as a call to a named external function, return the name
2205 /// otherwise lower it and return null.
2207 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
2208 switch (Intrinsic) {
2210 // By default, turn this into a target intrinsic node.
2211 visitTargetIntrinsic(I, Intrinsic);
2213 case Intrinsic::vastart: visitVAStart(I); return 0;
2214 case Intrinsic::vaend: visitVAEnd(I); return 0;
2215 case Intrinsic::vacopy: visitVACopy(I); return 0;
2216 case Intrinsic::returnaddress:
2217 setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(),
2218 getValue(I.getOperand(1))));
2220 case Intrinsic::frameaddress:
2221 setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(),
2222 getValue(I.getOperand(1))));
2224 case Intrinsic::setjmp:
2225 return "_setjmp"+!TLI.usesUnderscoreSetJmp();
2227 case Intrinsic::longjmp:
2228 return "_longjmp"+!TLI.usesUnderscoreLongJmp();
2230 case Intrinsic::memcpy_i32:
2231 case Intrinsic::memcpy_i64:
2232 visitMemIntrinsic(I, ISD::MEMCPY);
2234 case Intrinsic::memset_i32:
2235 case Intrinsic::memset_i64:
2236 visitMemIntrinsic(I, ISD::MEMSET);
2238 case Intrinsic::memmove_i32:
2239 case Intrinsic::memmove_i64:
2240 visitMemIntrinsic(I, ISD::MEMMOVE);
2243 case Intrinsic::dbg_stoppoint: {
2244 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2245 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I);
2246 if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) {
2250 Ops[1] = getValue(SPI.getLineValue());
2251 Ops[2] = getValue(SPI.getColumnValue());
2253 DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext());
2254 assert(DD && "Not a debug information descriptor");
2255 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD);
2257 Ops[3] = DAG.getString(CompileUnit->getFileName());
2258 Ops[4] = DAG.getString(CompileUnit->getDirectory());
2260 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5));
2265 case Intrinsic::dbg_region_start: {
2266 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2267 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I);
2268 if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) {
2269 unsigned LabelID = MMI->RecordRegionStart(RSI.getContext());
2270 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2271 DAG.getConstant(LabelID, MVT::i32)));
2276 case Intrinsic::dbg_region_end: {
2277 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2278 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I);
2279 if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) {
2280 unsigned LabelID = MMI->RecordRegionEnd(REI.getContext());
2281 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2282 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2287 case Intrinsic::dbg_func_start: {
2288 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2289 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I);
2290 if (MMI && FSI.getSubprogram() &&
2291 MMI->Verify(FSI.getSubprogram())) {
2292 unsigned LabelID = MMI->RecordRegionStart(FSI.getSubprogram());
2293 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2294 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2299 case Intrinsic::dbg_declare: {
2300 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2301 DbgDeclareInst &DI = cast<DbgDeclareInst>(I);
2302 if (MMI && DI.getVariable() && MMI->Verify(DI.getVariable())) {
2303 SDOperand AddressOp = getValue(DI.getAddress());
2304 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp))
2305 MMI->RecordVariable(DI.getVariable(), FI->getIndex());
2311 case Intrinsic::eh_exception: {
2312 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2315 // Add a label to mark the beginning of the landing pad. Deletion of the
2316 // landing pad can thus be detected via the MachineModuleInfo.
2317 unsigned LabelID = MMI->addLandingPad(CurMBB);
2318 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
2319 DAG.getConstant(LabelID, MVT::i32)));
2321 // Mark exception register as live in.
2322 unsigned Reg = TLI.getExceptionAddressRegister();
2323 if (Reg) CurMBB->addLiveIn(Reg);
2325 // Insert the EXCEPTIONADDR instruction.
2326 SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
2328 Ops[0] = DAG.getRoot();
2329 SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
2331 DAG.setRoot(Op.getValue(1));
2333 setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
2338 case Intrinsic::eh_selector:
2339 case Intrinsic::eh_filter:{
2340 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2343 // Inform the MachineModuleInfo of the personality for this landing pad.
2344 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(2));
2345 assert(CE && CE->getOpcode() == Instruction::BitCast &&
2346 isa<Function>(CE->getOperand(0)) &&
2347 "Personality should be a function");
2348 MMI->addPersonality(CurMBB, cast<Function>(CE->getOperand(0)));
2349 if (Intrinsic == Intrinsic::eh_filter)
2350 MMI->setIsFilterLandingPad(CurMBB);
2352 // Gather all the type infos for this landing pad and pass them along to
2353 // MachineModuleInfo.
2354 std::vector<GlobalVariable *> TyInfo;
2355 for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
2356 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i));
2357 if (CE && CE->getOpcode() == Instruction::BitCast &&
2358 isa<GlobalVariable>(CE->getOperand(0))) {
2359 TyInfo.push_back(cast<GlobalVariable>(CE->getOperand(0)));
2361 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i));
2362 assert(CI && CI->getZExtValue() == 0 &&
2363 "TypeInfo must be a global variable typeinfo or NULL");
2364 TyInfo.push_back(NULL);
2367 MMI->addCatchTypeInfo(CurMBB, TyInfo);
2369 // Mark exception selector register as live in.
2370 unsigned Reg = TLI.getExceptionSelectorRegister();
2371 if (Reg) CurMBB->addLiveIn(Reg);
2373 // Insert the EHSELECTION instruction.
2374 SDVTList VTs = DAG.getVTList(MVT::i32, MVT::Other);
2376 Ops[0] = getValue(I.getOperand(1));
2378 SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
2380 DAG.setRoot(Op.getValue(1));
2382 setValue(&I, DAG.getConstant(0, MVT::i32));
2388 case Intrinsic::eh_typeid_for: {
2389 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2392 // Find the type id for the given typeinfo.
2393 GlobalVariable *GV = NULL;
2394 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(1));
2395 if (CE && CE->getOpcode() == Instruction::BitCast &&
2396 isa<GlobalVariable>(CE->getOperand(0))) {
2397 GV = cast<GlobalVariable>(CE->getOperand(0));
2399 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
2400 assert(CI && CI->getZExtValue() == 0 &&
2401 "TypeInfo must be a global variable typeinfo or NULL");
2405 unsigned TypeID = MMI->getTypeIDFor(GV);
2406 setValue(&I, DAG.getConstant(TypeID, MVT::i32));
2408 setValue(&I, DAG.getConstant(0, MVT::i32));
2414 case Intrinsic::sqrt_f32:
2415 case Intrinsic::sqrt_f64:
2416 setValue(&I, DAG.getNode(ISD::FSQRT,
2417 getValue(I.getOperand(1)).getValueType(),
2418 getValue(I.getOperand(1))));
2420 case Intrinsic::powi_f32:
2421 case Intrinsic::powi_f64:
2422 setValue(&I, DAG.getNode(ISD::FPOWI,
2423 getValue(I.getOperand(1)).getValueType(),
2424 getValue(I.getOperand(1)),
2425 getValue(I.getOperand(2))));
2427 case Intrinsic::pcmarker: {
2428 SDOperand Tmp = getValue(I.getOperand(1));
2429 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
2432 case Intrinsic::readcyclecounter: {
2433 SDOperand Op = getRoot();
2434 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER,
2435 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2,
2438 DAG.setRoot(Tmp.getValue(1));
2441 case Intrinsic::bit_part_select: {
2442 // Currently not implemented: just abort
2443 assert(0 && "bit_part_select intrinsic not implemented");
2446 case Intrinsic::bswap:
2447 setValue(&I, DAG.getNode(ISD::BSWAP,
2448 getValue(I.getOperand(1)).getValueType(),
2449 getValue(I.getOperand(1))));
2451 case Intrinsic::cttz: {
2452 SDOperand Arg = getValue(I.getOperand(1));
2453 MVT::ValueType Ty = Arg.getValueType();
2454 SDOperand result = DAG.getNode(ISD::CTTZ, Ty, Arg);
2456 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2457 else if (Ty > MVT::i32)
2458 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2459 setValue(&I, result);
2462 case Intrinsic::ctlz: {
2463 SDOperand Arg = getValue(I.getOperand(1));
2464 MVT::ValueType Ty = Arg.getValueType();
2465 SDOperand result = DAG.getNode(ISD::CTLZ, Ty, Arg);
2467 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2468 else if (Ty > MVT::i32)
2469 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2470 setValue(&I, result);
2473 case Intrinsic::ctpop: {
2474 SDOperand Arg = getValue(I.getOperand(1));
2475 MVT::ValueType Ty = Arg.getValueType();
2476 SDOperand result = DAG.getNode(ISD::CTPOP, Ty, Arg);
2478 result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
2479 else if (Ty > MVT::i32)
2480 result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
2481 setValue(&I, result);
2484 case Intrinsic::stacksave: {
2485 SDOperand Op = getRoot();
2486 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
2487 DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1);
2489 DAG.setRoot(Tmp.getValue(1));
2492 case Intrinsic::stackrestore: {
2493 SDOperand Tmp = getValue(I.getOperand(1));
2494 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
2497 case Intrinsic::prefetch:
2498 // FIXME: Currently discarding prefetches.
2504 void SelectionDAGLowering::LowerCallTo(Instruction &I,
2505 const Type *CalledValueTy,
2506 unsigned CallingConv,
2508 SDOperand Callee, unsigned OpIdx) {
2509 const PointerType *PT = cast<PointerType>(CalledValueTy);
2510 const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
2512 TargetLowering::ArgListTy Args;
2513 TargetLowering::ArgListEntry Entry;
2514 Args.reserve(I.getNumOperands());
2515 for (unsigned i = OpIdx, e = I.getNumOperands(); i != e; ++i) {
2516 Value *Arg = I.getOperand(i);
2517 SDOperand ArgNode = getValue(Arg);
2518 Entry.Node = ArgNode; Entry.Ty = Arg->getType();
2519 Entry.isSExt = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
2520 Entry.isZExt = FTy->paramHasAttr(i, FunctionType::ZExtAttribute);
2521 Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
2522 Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
2523 Args.push_back(Entry);
2526 std::pair<SDOperand,SDOperand> Result =
2527 TLI.LowerCallTo(getRoot(), I.getType(),
2528 FTy->paramHasAttr(0,FunctionType::SExtAttribute),
2529 FTy->isVarArg(), CallingConv, IsTailCall,
2531 if (I.getType() != Type::VoidTy)
2532 setValue(&I, Result.first);
2533 DAG.setRoot(Result.second);
2537 void SelectionDAGLowering::visitCall(CallInst &I) {
2538 const char *RenameFn = 0;
2539 if (Function *F = I.getCalledFunction()) {
2540 if (F->isDeclaration())
2541 if (unsigned IID = F->getIntrinsicID()) {
2542 RenameFn = visitIntrinsicCall(I, IID);
2545 } else { // Not an LLVM intrinsic.
2546 const std::string &Name = F->getName();
2547 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) {
2548 if (I.getNumOperands() == 3 && // Basic sanity checks.
2549 I.getOperand(1)->getType()->isFloatingPoint() &&
2550 I.getType() == I.getOperand(1)->getType() &&
2551 I.getType() == I.getOperand(2)->getType()) {
2552 SDOperand LHS = getValue(I.getOperand(1));
2553 SDOperand RHS = getValue(I.getOperand(2));
2554 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
2558 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
2559 if (I.getNumOperands() == 2 && // Basic sanity checks.
2560 I.getOperand(1)->getType()->isFloatingPoint() &&
2561 I.getType() == I.getOperand(1)->getType()) {
2562 SDOperand Tmp = getValue(I.getOperand(1));
2563 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
2566 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
2567 if (I.getNumOperands() == 2 && // Basic sanity checks.
2568 I.getOperand(1)->getType()->isFloatingPoint() &&
2569 I.getType() == I.getOperand(1)->getType()) {
2570 SDOperand Tmp = getValue(I.getOperand(1));
2571 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
2574 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
2575 if (I.getNumOperands() == 2 && // Basic sanity checks.
2576 I.getOperand(1)->getType()->isFloatingPoint() &&
2577 I.getType() == I.getOperand(1)->getType()) {
2578 SDOperand Tmp = getValue(I.getOperand(1));
2579 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
2584 } else if (isa<InlineAsm>(I.getOperand(0))) {
2591 Callee = getValue(I.getOperand(0));
2593 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
2595 LowerCallTo(I, I.getCalledValue()->getType(),
2603 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
2604 SDOperand &Chain, SDOperand &Flag)const{
2605 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag);
2606 Chain = Val.getValue(1);
2607 Flag = Val.getValue(2);
2609 // If the result was expanded, copy from the top part.
2610 if (Regs.size() > 1) {
2611 assert(Regs.size() == 2 &&
2612 "Cannot expand to more than 2 elts yet!");
2613 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag);
2614 Chain = Hi.getValue(1);
2615 Flag = Hi.getValue(2);
2616 if (DAG.getTargetLoweringInfo().isLittleEndian())
2617 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
2619 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val);
2622 // Otherwise, if the return value was promoted or extended, truncate it to the
2623 // appropriate type.
2624 if (RegVT == ValueVT)
2627 if (MVT::isVector(RegVT)) {
2628 assert(ValueVT == MVT::Vector && "Unknown vector conversion!");
2629 return DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
2630 DAG.getConstant(MVT::getVectorNumElements(RegVT),
2632 DAG.getValueType(MVT::getVectorBaseType(RegVT)));
2635 if (MVT::isInteger(RegVT)) {
2636 if (ValueVT < RegVT)
2637 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
2639 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
2642 assert(MVT::isFloatingPoint(RegVT) && MVT::isFloatingPoint(ValueVT));
2643 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
2646 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
2647 /// specified value into the registers specified by this object. This uses
2648 /// Chain/Flag as the input and updates them for the output Chain/Flag.
2649 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
2650 SDOperand &Chain, SDOperand &Flag,
2651 MVT::ValueType PtrVT) const {
2652 if (Regs.size() == 1) {
2653 // If there is a single register and the types differ, this must be
2655 if (RegVT != ValueVT) {
2656 if (MVT::isVector(RegVT)) {
2657 assert(Val.getValueType() == MVT::Vector &&"Not a vector-vector cast?");
2658 Val = DAG.getNode(ISD::VBIT_CONVERT, RegVT, Val);
2659 } else if (MVT::isInteger(RegVT)) {
2660 if (RegVT < ValueVT)
2661 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
2663 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
2665 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
2667 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
2668 Flag = Chain.getValue(1);
2670 std::vector<unsigned> R(Regs);
2671 if (!DAG.getTargetLoweringInfo().isLittleEndian())
2672 std::reverse(R.begin(), R.end());
2674 for (unsigned i = 0, e = R.size(); i != e; ++i) {
2675 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
2676 DAG.getConstant(i, PtrVT));
2677 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
2678 Flag = Chain.getValue(1);
2683 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
2684 /// operand list. This adds the code marker and includes the number of
2685 /// values added into it.
2686 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
2687 std::vector<SDOperand> &Ops) const {
2688 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
2689 Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
2690 for (unsigned i = 0, e = Regs.size(); i != e; ++i)
2691 Ops.push_back(DAG.getRegister(Regs[i], RegVT));
2694 /// isAllocatableRegister - If the specified register is safe to allocate,
2695 /// i.e. it isn't a stack pointer or some other special register, return the
2696 /// register class for the register. Otherwise, return null.
2697 static const TargetRegisterClass *
2698 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
2699 const TargetLowering &TLI, const MRegisterInfo *MRI) {
2700 MVT::ValueType FoundVT = MVT::Other;
2701 const TargetRegisterClass *FoundRC = 0;
2702 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
2703 E = MRI->regclass_end(); RCI != E; ++RCI) {
2704 MVT::ValueType ThisVT = MVT::Other;
2706 const TargetRegisterClass *RC = *RCI;
2707 // If none of the the value types for this register class are valid, we
2708 // can't use it. For example, 64-bit reg classes on 32-bit targets.
2709 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
2711 if (TLI.isTypeLegal(*I)) {
2712 // If we have already found this register in a different register class,
2713 // choose the one with the largest VT specified. For example, on
2714 // PowerPC, we favor f64 register classes over f32.
2715 if (FoundVT == MVT::Other ||
2716 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
2723 if (ThisVT == MVT::Other) continue;
2725 // NOTE: This isn't ideal. In particular, this might allocate the
2726 // frame pointer in functions that need it (due to them not being taken
2727 // out of allocation, because a variable sized allocation hasn't been seen
2728 // yet). This is a slight code pessimization, but should still work.
2729 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
2730 E = RC->allocation_order_end(MF); I != E; ++I)
2732 // We found a matching register class. Keep looking at others in case
2733 // we find one with larger registers that this physreg is also in.
2742 RegsForValue SelectionDAGLowering::
2743 GetRegistersForValue(const std::string &ConstrCode,
2744 MVT::ValueType VT, bool isOutReg, bool isInReg,
2745 std::set<unsigned> &OutputRegs,
2746 std::set<unsigned> &InputRegs) {
2747 std::pair<unsigned, const TargetRegisterClass*> PhysReg =
2748 TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
2749 std::vector<unsigned> Regs;
2751 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
2752 MVT::ValueType RegVT;
2753 MVT::ValueType ValueVT = VT;
2755 // If this is a constraint for a specific physical register, like {r17},
2757 if (PhysReg.first) {
2758 if (VT == MVT::Other)
2759 ValueVT = *PhysReg.second->vt_begin();
2761 // Get the actual register value type. This is important, because the user
2762 // may have asked for (e.g.) the AX register in i32 type. We need to
2763 // remember that AX is actually i16 to get the right extension.
2764 RegVT = *PhysReg.second->vt_begin();
2766 // This is a explicit reference to a physical register.
2767 Regs.push_back(PhysReg.first);
2769 // If this is an expanded reference, add the rest of the regs to Regs.
2771 TargetRegisterClass::iterator I = PhysReg.second->begin();
2772 TargetRegisterClass::iterator E = PhysReg.second->end();
2773 for (; *I != PhysReg.first; ++I)
2774 assert(I != E && "Didn't find reg!");
2776 // Already added the first reg.
2778 for (; NumRegs; --NumRegs, ++I) {
2779 assert(I != E && "Ran out of registers to allocate!");
2783 return RegsForValue(Regs, RegVT, ValueVT);
2786 // Otherwise, if this was a reference to an LLVM register class, create vregs
2787 // for this reference.
2788 std::vector<unsigned> RegClassRegs;
2789 if (PhysReg.second) {
2790 // If this is an early clobber or tied register, our regalloc doesn't know
2791 // how to maintain the constraint. If it isn't, go ahead and create vreg
2792 // and let the regalloc do the right thing.
2793 if (!isOutReg || !isInReg) {
2794 if (VT == MVT::Other)
2795 ValueVT = *PhysReg.second->vt_begin();
2796 RegVT = *PhysReg.second->vt_begin();
2798 // Create the appropriate number of virtual registers.
2799 SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
2800 for (; NumRegs; --NumRegs)
2801 Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
2803 return RegsForValue(Regs, RegVT, ValueVT);
2806 // Otherwise, we can't allocate it. Let the code below figure out how to
2807 // maintain these constraints.
2808 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
2811 // This is a reference to a register class that doesn't directly correspond
2812 // to an LLVM register class. Allocate NumRegs consecutive, available,
2813 // registers from the class.
2814 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
2817 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
2818 MachineFunction &MF = *CurMBB->getParent();
2819 unsigned NumAllocated = 0;
2820 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
2821 unsigned Reg = RegClassRegs[i];
2822 // See if this register is available.
2823 if ((isOutReg && OutputRegs.count(Reg)) || // Already used.
2824 (isInReg && InputRegs.count(Reg))) { // Already used.
2825 // Make sure we find consecutive registers.
2830 // Check to see if this register is allocatable (i.e. don't give out the
2832 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
2834 // Make sure we find consecutive registers.
2839 // Okay, this register is good, we can use it.
2842 // If we allocated enough consecutive registers, succeed.
2843 if (NumAllocated == NumRegs) {
2844 unsigned RegStart = (i-NumAllocated)+1;
2845 unsigned RegEnd = i+1;
2846 // Mark all of the allocated registers used.
2847 for (unsigned i = RegStart; i != RegEnd; ++i) {
2848 unsigned Reg = RegClassRegs[i];
2849 Regs.push_back(Reg);
2850 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used.
2851 if (isInReg) InputRegs.insert(Reg); // Mark reg used.
2854 return RegsForValue(Regs, *RC->vt_begin(), VT);
2858 // Otherwise, we couldn't allocate enough registers for this.
2859 return RegsForValue();
2862 /// getConstraintGenerality - Return an integer indicating how general CT is.
2863 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
2865 default: assert(0 && "Unknown constraint type!");
2866 case TargetLowering::C_Other:
2867 case TargetLowering::C_Unknown:
2869 case TargetLowering::C_Register:
2871 case TargetLowering::C_RegisterClass:
2873 case TargetLowering::C_Memory:
2878 static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
2879 const TargetLowering &TLI) {
2880 assert(!C.empty() && "Must have at least one constraint");
2881 if (C.size() == 1) return C[0];
2883 std::string *Current = &C[0];
2884 // If we have multiple constraints, try to pick the most general one ahead
2885 // of time. This isn't a wonderful solution, but handles common cases.
2886 TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
2887 for (unsigned j = 1, e = C.size(); j != e; ++j) {
2888 TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
2889 if (getConstraintGenerality(ThisFlavor) >
2890 getConstraintGenerality(Flavor)) {
2891 // This constraint letter is more general than the previous one,
2893 Flavor = ThisFlavor;
2901 /// visitInlineAsm - Handle a call to an InlineAsm object.
2903 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
2904 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
2906 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
2909 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
2910 std::vector<MVT::ValueType> ConstraintVTs;
2912 /// AsmNodeOperands - A list of pairs. The first element is a register, the
2913 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
2914 /// if it is a def of that register.
2915 std::vector<SDOperand> AsmNodeOperands;
2916 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
2917 AsmNodeOperands.push_back(AsmStr);
2919 SDOperand Chain = getRoot();
2922 // We fully assign registers here at isel time. This is not optimal, but
2923 // should work. For register classes that correspond to LLVM classes, we
2924 // could let the LLVM RA do its thing, but we currently don't. Do a prepass
2925 // over the constraints, collecting fixed registers that we know we can't use.
2926 std::set<unsigned> OutputRegs, InputRegs;
2928 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2929 std::string ConstraintCode =
2930 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2932 MVT::ValueType OpVT;
2934 // Compute the value type for each operand and add it to ConstraintVTs.
2935 switch (Constraints[i].Type) {
2936 case InlineAsm::isOutput:
2937 if (!Constraints[i].isIndirectOutput) {
2938 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2939 OpVT = TLI.getValueType(I.getType());
2941 const Type *OpTy = I.getOperand(OpNum)->getType();
2942 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
2943 OpNum++; // Consumes a call operand.
2946 case InlineAsm::isInput:
2947 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
2948 OpNum++; // Consumes a call operand.
2950 case InlineAsm::isClobber:
2955 ConstraintVTs.push_back(OpVT);
2957 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
2958 continue; // Not assigned a fixed reg.
2960 // Build a list of regs that this operand uses. This always has a single
2961 // element for promoted/expanded operands.
2962 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
2964 OutputRegs, InputRegs);
2966 switch (Constraints[i].Type) {
2967 case InlineAsm::isOutput:
2968 // We can't assign any other output to this register.
2969 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2970 // If this is an early-clobber output, it cannot be assigned to the same
2971 // value as the input reg.
2972 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2973 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2975 case InlineAsm::isInput:
2976 // We can't assign any other input to this register.
2977 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2979 case InlineAsm::isClobber:
2980 // Clobbered regs cannot be used as inputs or outputs.
2981 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2982 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2987 // Loop over all of the inputs, copying the operand values into the
2988 // appropriate registers and processing the output regs.
2989 RegsForValue RetValRegs;
2990 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
2993 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2994 std::string ConstraintCode =
2995 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2997 switch (Constraints[i].Type) {
2998 case InlineAsm::isOutput: {
2999 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3000 if (ConstraintCode.size() == 1) // not a physreg name.
3001 CTy = TLI.getConstraintType(ConstraintCode);
3003 if (CTy == TargetLowering::C_Memory) {
3005 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3007 // Check that the operand (the address to store to) isn't a float.
3008 if (!MVT::isInteger(InOperandVal.getValueType()))
3009 assert(0 && "MATCH FAIL!");
3011 if (!Constraints[i].isIndirectOutput)
3012 assert(0 && "MATCH FAIL!");
3014 OpNum++; // Consumes a call operand.
3016 // Extend/truncate to the right pointer type if needed.
3017 MVT::ValueType PtrType = TLI.getPointerTy();
3018 if (InOperandVal.getValueType() < PtrType)
3019 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3020 else if (InOperandVal.getValueType() > PtrType)
3021 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3023 // Add information to the INLINEASM node to know about this output.
3024 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3025 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3026 AsmNodeOperands.push_back(InOperandVal);
3030 // Otherwise, this is a register output.
3031 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3033 // If this is an early-clobber output, or if there is an input
3034 // constraint that matches this, we need to reserve the input register
3035 // so no other inputs allocate to it.
3036 bool UsesInputRegister = false;
3037 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
3038 UsesInputRegister = true;
3040 // Copy the output from the appropriate register. Find a register that
3043 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3044 true, UsesInputRegister,
3045 OutputRegs, InputRegs);
3046 if (Regs.Regs.empty()) {
3047 cerr << "Couldn't allocate output reg for contraint '"
3048 << ConstraintCode << "'!\n";
3052 if (!Constraints[i].isIndirectOutput) {
3053 assert(RetValRegs.Regs.empty() &&
3054 "Cannot have multiple output constraints yet!");
3055 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
3058 IndirectStoresToEmit.push_back(std::make_pair(Regs,
3059 I.getOperand(OpNum)));
3060 OpNum++; // Consumes a call operand.
3063 // Add information to the INLINEASM node to know that this register is
3065 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
3068 case InlineAsm::isInput: {
3069 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3070 OpNum++; // Consumes a call operand.
3072 if (isdigit(ConstraintCode[0])) { // Matching constraint?
3073 // If this is required to match an output register we have already set,
3074 // just use its register.
3075 unsigned OperandNo = atoi(ConstraintCode.c_str());
3077 // Scan until we find the definition we already emitted of this operand.
3078 // When we find it, create a RegsForValue operand.
3079 unsigned CurOp = 2; // The first operand.
3080 for (; OperandNo; --OperandNo) {
3081 // Advance to the next operand.
3083 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3084 assert(((NumOps & 7) == 2 /*REGDEF*/ ||
3085 (NumOps & 7) == 4 /*MEM*/) &&
3086 "Skipped past definitions?");
3087 CurOp += (NumOps>>3)+1;
3091 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3092 if ((NumOps & 7) == 2 /*REGDEF*/) {
3093 // Add NumOps>>3 registers to MatchedRegs.
3094 RegsForValue MatchedRegs;
3095 MatchedRegs.ValueVT = InOperandVal.getValueType();
3096 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType();
3097 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
3099 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
3100 MatchedRegs.Regs.push_back(Reg);
3103 // Use the produced MatchedRegs object to
3104 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
3105 TLI.getPointerTy());
3106 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
3109 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
3110 assert(0 && "matching constraints for memory operands unimp");
3114 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3115 if (ConstraintCode.size() == 1) // not a physreg name.
3116 CTy = TLI.getConstraintType(ConstraintCode);
3118 if (CTy == TargetLowering::C_Other) {
3119 InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
3120 ConstraintCode[0], DAG);
3121 if (!InOperandVal.Val) {
3122 cerr << "Invalid operand for inline asm constraint '"
3123 << ConstraintCode << "'!\n";
3127 // Add information to the INLINEASM node to know about this input.
3128 unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
3129 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3130 AsmNodeOperands.push_back(InOperandVal);
3132 } else if (CTy == TargetLowering::C_Memory) {
3135 // If the operand is a float, spill to a constant pool entry to get its
3137 if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
3138 InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
3140 if (!MVT::isInteger(InOperandVal.getValueType())) {
3141 cerr << "Match failed, cannot handle this yet!\n";
3142 InOperandVal.Val->dump();
3146 // Extend/truncate to the right pointer type if needed.
3147 MVT::ValueType PtrType = TLI.getPointerTy();
3148 if (InOperandVal.getValueType() < PtrType)
3149 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3150 else if (InOperandVal.getValueType() > PtrType)
3151 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3153 // Add information to the INLINEASM node to know about this input.
3154 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3155 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3156 AsmNodeOperands.push_back(InOperandVal);
3160 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3162 // Copy the input into the appropriate registers.
3163 RegsForValue InRegs =
3164 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3165 false, true, OutputRegs, InputRegs);
3166 // FIXME: should be match fail.
3167 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
3169 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
3171 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
3174 case InlineAsm::isClobber: {
3175 RegsForValue ClobberedRegs =
3176 GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
3177 OutputRegs, InputRegs);
3178 // Add the clobbered value to the operand list, so that the register
3179 // allocator is aware that the physreg got clobbered.
3180 if (!ClobberedRegs.Regs.empty())
3181 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
3187 // Finish up input operands.
3188 AsmNodeOperands[0] = Chain;
3189 if (Flag.Val) AsmNodeOperands.push_back(Flag);
3191 Chain = DAG.getNode(ISD::INLINEASM,
3192 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
3193 &AsmNodeOperands[0], AsmNodeOperands.size());
3194 Flag = Chain.getValue(1);
3196 // If this asm returns a register value, copy the result from that register
3197 // and set it as the value of the call.
3198 if (!RetValRegs.Regs.empty())
3199 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
3201 std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
3203 // Process indirect outputs, first output all of the flagged copies out of
3205 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
3206 RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
3207 Value *Ptr = IndirectStoresToEmit[i].second;
3208 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
3209 StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
3212 // Emit the non-flagged stores from the physregs.
3213 SmallVector<SDOperand, 8> OutChains;
3214 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
3215 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
3216 getValue(StoresToEmit[i].second),
3217 StoresToEmit[i].second, 0));
3218 if (!OutChains.empty())
3219 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3220 &OutChains[0], OutChains.size());
3225 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
3226 SDOperand Src = getValue(I.getOperand(0));
3228 MVT::ValueType IntPtr = TLI.getPointerTy();
3230 if (IntPtr < Src.getValueType())
3231 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
3232 else if (IntPtr > Src.getValueType())
3233 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
3235 // Scale the source by the type size.
3236 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
3237 Src = DAG.getNode(ISD::MUL, Src.getValueType(),
3238 Src, getIntPtrConstant(ElementSize));
3240 TargetLowering::ArgListTy Args;
3241 TargetLowering::ArgListEntry Entry;
3243 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3244 Args.push_back(Entry);
3246 std::pair<SDOperand,SDOperand> Result =
3247 TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3248 DAG.getExternalSymbol("malloc", IntPtr),
3250 setValue(&I, Result.first); // Pointers always fit in registers
3251 DAG.setRoot(Result.second);
3254 void SelectionDAGLowering::visitFree(FreeInst &I) {
3255 TargetLowering::ArgListTy Args;
3256 TargetLowering::ArgListEntry Entry;
3257 Entry.Node = getValue(I.getOperand(0));
3258 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3259 Args.push_back(Entry);
3260 MVT::ValueType IntPtr = TLI.getPointerTy();
3261 std::pair<SDOperand,SDOperand> Result =
3262 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3263 DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3264 DAG.setRoot(Result.second);
3267 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3268 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These
3269 // instructions are special in various ways, which require special support to
3270 // insert. The specified MachineInstr is created but not inserted into any
3271 // basic blocks, and the scheduler passes ownership of it to this method.
3272 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3273 MachineBasicBlock *MBB) {
3274 cerr << "If a target marks an instruction with "
3275 << "'usesCustomDAGSchedInserter', it must implement "
3276 << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3281 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3282 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
3283 getValue(I.getOperand(1)),
3284 DAG.getSrcValue(I.getOperand(1))));
3287 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3288 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3289 getValue(I.getOperand(0)),
3290 DAG.getSrcValue(I.getOperand(0)));
3292 DAG.setRoot(V.getValue(1));
3295 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3296 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3297 getValue(I.getOperand(1)),
3298 DAG.getSrcValue(I.getOperand(1))));
3301 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3302 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
3303 getValue(I.getOperand(1)),
3304 getValue(I.getOperand(2)),
3305 DAG.getSrcValue(I.getOperand(1)),
3306 DAG.getSrcValue(I.getOperand(2))));
3309 /// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
3310 /// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
3311 static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
3312 unsigned &i, SelectionDAG &DAG,
3313 TargetLowering &TLI) {
3314 if (TLI.getTypeAction(VT) != TargetLowering::Expand)
3315 return SDOperand(Arg, i++);
3317 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3318 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3320 return DAG.getNode(ISD::BIT_CONVERT, VT,
3321 ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
3322 } else if (NumVals == 2) {
3323 SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3324 SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3325 if (!TLI.isLittleEndian())
3327 return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
3329 // Value scalarized into many values. Unimp for now.
3330 assert(0 && "Cannot expand i64 -> i16 yet!");
3335 /// TargetLowering::LowerArguments - This is the default LowerArguments
3336 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all
3337 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
3338 /// integrated into SDISel.
3339 std::vector<SDOperand>
3340 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3341 const FunctionType *FTy = F.getFunctionType();
3342 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3343 std::vector<SDOperand> Ops;
3344 Ops.push_back(DAG.getRoot());
3345 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3346 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3348 // Add one result value for each formal argument.
3349 std::vector<MVT::ValueType> RetVals;
3351 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3353 MVT::ValueType VT = getValueType(I->getType());
3354 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3355 unsigned OriginalAlignment =
3356 getTargetData()->getABITypeAlignment(I->getType());
3358 // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3359 // that is zero extended!
3360 if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
3361 Flags &= ~(ISD::ParamFlags::SExt);
3362 if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
3363 Flags |= ISD::ParamFlags::SExt;
3364 if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
3365 Flags |= ISD::ParamFlags::InReg;
3366 if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
3367 Flags |= ISD::ParamFlags::StructReturn;
3368 Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3370 switch (getTypeAction(VT)) {
3371 default: assert(0 && "Unknown type action!");
3373 RetVals.push_back(VT);
3374 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3377 RetVals.push_back(getTypeToTransformTo(VT));
3378 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3381 if (VT != MVT::Vector) {
3382 // If this is a large integer, it needs to be broken up into small
3383 // integers. Figure out what the destination type is and how many small
3384 // integers it turns into.
3385 MVT::ValueType NVT = getTypeToExpandTo(VT);
3386 unsigned NumVals = getNumElements(VT);
3387 for (unsigned i = 0; i != NumVals; ++i) {
3388 RetVals.push_back(NVT);
3389 // if it isn't first piece, alignment must be 1
3391 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3392 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3393 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3396 // Otherwise, this is a vector type. We only support legal vectors
3398 unsigned NumElems = cast<VectorType>(I->getType())->getNumElements();
3399 const Type *EltTy = cast<VectorType>(I->getType())->getElementType();
3401 // Figure out if there is a Packed type corresponding to this Vector
3402 // type. If so, convert to the vector type.
3403 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3404 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3405 RetVals.push_back(TVT);
3406 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3408 assert(0 && "Don't support illegal by-val vector arguments yet!");
3415 RetVals.push_back(MVT::Other);
3418 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3419 DAG.getNodeValueTypes(RetVals), RetVals.size(),
3420 &Ops[0], Ops.size()).Val;
3422 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
3424 // Set up the return result vector.
3428 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
3430 MVT::ValueType VT = getValueType(I->getType());
3432 switch (getTypeAction(VT)) {
3433 default: assert(0 && "Unknown type action!");
3435 Ops.push_back(SDOperand(Result, i++));
3438 SDOperand Op(Result, i++);
3439 if (MVT::isInteger(VT)) {
3440 if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
3441 Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3442 DAG.getValueType(VT));
3443 else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
3444 Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3445 DAG.getValueType(VT));
3446 Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3448 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3449 Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
3455 if (VT != MVT::Vector) {
3456 // If this is a large integer or a floating point node that needs to be
3457 // expanded, it needs to be reassembled from small integers. Figure out
3458 // what the source elt type is and how many small integers it is.
3459 Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
3461 // Otherwise, this is a vector type. We only support legal vectors
3463 const VectorType *PTy = cast<VectorType>(I->getType());
3464 unsigned NumElems = PTy->getNumElements();
3465 const Type *EltTy = PTy->getElementType();
3467 // Figure out if there is a Packed type corresponding to this Vector
3468 // type. If so, convert to the vector type.
3469 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3470 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3471 SDOperand N = SDOperand(Result, i++);
3472 // Handle copies from generic vectors to registers.
3473 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
3474 DAG.getConstant(NumElems, MVT::i32),
3475 DAG.getValueType(getValueType(EltTy)));
3478 assert(0 && "Don't support illegal by-val vector arguments yet!");
3489 /// ExpandScalarCallArgs - Recursively expand call argument node by
3490 /// bit_converting it or extract a pair of elements from the larger node.
3491 static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
3493 SmallVector<SDOperand, 32> &Ops,
3495 TargetLowering &TLI,
3496 bool isFirst = true) {
3498 if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
3499 // if it isn't first piece, alignment must be 1
3501 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3502 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3504 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3508 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3509 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3511 Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
3512 ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI, isFirst);
3513 } else if (NumVals == 2) {
3514 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3515 DAG.getConstant(0, TLI.getPointerTy()));
3516 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3517 DAG.getConstant(1, TLI.getPointerTy()));
3518 if (!TLI.isLittleEndian())
3520 ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI, isFirst);
3521 ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI, false);
3523 // Value scalarized into many values. Unimp for now.
3524 assert(0 && "Cannot expand i64 -> i16 yet!");
3528 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
3529 /// implementation, which just inserts an ISD::CALL node, which is later custom
3530 /// lowered by the target to something concrete. FIXME: When all targets are
3531 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
3532 std::pair<SDOperand, SDOperand>
3533 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
3534 bool RetTyIsSigned, bool isVarArg,
3535 unsigned CallingConv, bool isTailCall,
3537 ArgListTy &Args, SelectionDAG &DAG) {
3538 SmallVector<SDOperand, 32> Ops;
3539 Ops.push_back(Chain); // Op#0 - Chain
3540 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
3541 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg
3542 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail
3543 Ops.push_back(Callee);
3545 // Handle all of the outgoing arguments.
3546 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
3547 MVT::ValueType VT = getValueType(Args[i].Ty);
3548 SDOperand Op = Args[i].Node;
3549 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3550 unsigned OriginalAlignment =
3551 getTargetData()->getABITypeAlignment(Args[i].Ty);
3554 Flags |= ISD::ParamFlags::SExt;
3556 Flags |= ISD::ParamFlags::ZExt;
3557 if (Args[i].isInReg)
3558 Flags |= ISD::ParamFlags::InReg;
3560 Flags |= ISD::ParamFlags::StructReturn;
3561 Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
3563 switch (getTypeAction(VT)) {
3564 default: assert(0 && "Unknown type action!");
3567 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3570 if (MVT::isInteger(VT)) {
3573 ExtOp = ISD::SIGN_EXTEND;
3574 else if (Args[i].isZExt)
3575 ExtOp = ISD::ZERO_EXTEND;
3577 ExtOp = ISD::ANY_EXTEND;
3578 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
3580 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3581 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
3584 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3587 if (VT != MVT::Vector) {
3588 // If this is a large integer, it needs to be broken down into small
3589 // integers. Figure out what the source elt type is and how many small
3591 ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
3593 // Otherwise, this is a vector type. We only support legal vectors
3595 const VectorType *PTy = cast<VectorType>(Args[i].Ty);
3596 unsigned NumElems = PTy->getNumElements();
3597 const Type *EltTy = PTy->getElementType();
3599 // Figure out if there is a Packed type corresponding to this Vector
3600 // type. If so, convert to the vector type.
3601 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3602 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3603 // Insert a VBIT_CONVERT of the MVT::Vector type to the vector type.
3604 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
3606 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3608 assert(0 && "Don't support illegal by-val vector call args yet!");
3616 // Figure out the result value types.
3617 SmallVector<MVT::ValueType, 4> RetTys;
3619 if (RetTy != Type::VoidTy) {
3620 MVT::ValueType VT = getValueType(RetTy);
3621 switch (getTypeAction(VT)) {
3622 default: assert(0 && "Unknown type action!");
3624 RetTys.push_back(VT);
3627 RetTys.push_back(getTypeToTransformTo(VT));
3630 if (VT != MVT::Vector) {
3631 // If this is a large integer, it needs to be reassembled from small
3632 // integers. Figure out what the source elt type is and how many small
3634 MVT::ValueType NVT = getTypeToExpandTo(VT);
3635 unsigned NumVals = getNumElements(VT);
3636 for (unsigned i = 0; i != NumVals; ++i)
3637 RetTys.push_back(NVT);
3639 // Otherwise, this is a vector type. We only support legal vectors
3641 const VectorType *PTy = cast<VectorType>(RetTy);
3642 unsigned NumElems = PTy->getNumElements();
3643 const Type *EltTy = PTy->getElementType();
3645 // Figure out if there is a Packed type corresponding to this Vector
3646 // type. If so, convert to the vector type.
3647 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3648 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3649 RetTys.push_back(TVT);
3651 assert(0 && "Don't support illegal by-val vector call results yet!");
3658 RetTys.push_back(MVT::Other); // Always has a chain.
3660 // Finally, create the CALL node.
3661 SDOperand Res = DAG.getNode(ISD::CALL,
3662 DAG.getVTList(&RetTys[0], RetTys.size()),
3663 &Ops[0], Ops.size());
3665 // This returns a pair of operands. The first element is the
3666 // return value for the function (if RetTy is not VoidTy). The second
3667 // element is the outgoing token chain.
3669 if (RetTys.size() != 1) {
3670 MVT::ValueType VT = getValueType(RetTy);
3671 if (RetTys.size() == 2) {
3674 // If this value was promoted, truncate it down.
3675 if (ResVal.getValueType() != VT) {
3676 if (VT == MVT::Vector) {
3677 // Insert a VBIT_CONVERT to convert from the packed result type to the
3678 // MVT::Vector type.
3679 unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
3680 const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
3682 // Figure out if there is a Packed type corresponding to this Vector
3683 // type. If so, convert to the vector type.
3684 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
3685 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3686 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
3687 // "N x PTyElementVT" MVT::Vector type.
3688 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
3689 DAG.getConstant(NumElems, MVT::i32),
3690 DAG.getValueType(getValueType(EltTy)));
3694 } else if (MVT::isInteger(VT)) {
3695 unsigned AssertOp = ISD::AssertSext;
3697 AssertOp = ISD::AssertZext;
3698 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
3699 DAG.getValueType(VT));
3700 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
3702 assert(MVT::isFloatingPoint(VT));
3703 if (getTypeAction(VT) == Expand)
3704 ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
3706 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
3709 } else if (RetTys.size() == 3) {
3710 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
3711 Res.getValue(0), Res.getValue(1));
3714 assert(0 && "Case not handled yet!");
3718 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
3721 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
3722 assert(0 && "LowerOperation not implemented for this target!");
3727 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
3728 SelectionDAG &DAG) {
3729 assert(0 && "CustomPromoteOperation not implemented for this target!");
3734 /// getMemsetValue - Vectorized representation of the memset value
3736 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
3737 SelectionDAG &DAG) {
3738 MVT::ValueType CurVT = VT;
3739 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3740 uint64_t Val = C->getValue() & 255;
3742 while (CurVT != MVT::i8) {
3743 Val = (Val << Shift) | Val;
3745 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3747 return DAG.getConstant(Val, VT);
3749 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
3751 while (CurVT != MVT::i8) {
3753 DAG.getNode(ISD::OR, VT,
3754 DAG.getNode(ISD::SHL, VT, Value,
3755 DAG.getConstant(Shift, MVT::i8)), Value);
3757 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3764 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3765 /// used when a memcpy is turned into a memset when the source is a constant
3767 static SDOperand getMemsetStringVal(MVT::ValueType VT,
3768 SelectionDAG &DAG, TargetLowering &TLI,
3769 std::string &Str, unsigned Offset) {
3771 unsigned MSB = getSizeInBits(VT) / 8;
3772 if (TLI.isLittleEndian())
3773 Offset = Offset + MSB - 1;
3774 for (unsigned i = 0; i != MSB; ++i) {
3775 Val = (Val << 8) | (unsigned char)Str[Offset];
3776 Offset += TLI.isLittleEndian() ? -1 : 1;
3778 return DAG.getConstant(Val, VT);
3781 /// getMemBasePlusOffset - Returns base and offset node for the
3782 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
3783 SelectionDAG &DAG, TargetLowering &TLI) {
3784 MVT::ValueType VT = Base.getValueType();
3785 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
3788 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
3789 /// to replace the memset / memcpy is below the threshold. It also returns the
3790 /// types of the sequence of memory ops to perform memset / memcpy.
3791 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
3792 unsigned Limit, uint64_t Size,
3793 unsigned Align, TargetLowering &TLI) {
3796 if (TLI.allowsUnalignedMemoryAccesses()) {
3799 switch (Align & 7) {
3815 MVT::ValueType LVT = MVT::i64;
3816 while (!TLI.isTypeLegal(LVT))
3817 LVT = (MVT::ValueType)((unsigned)LVT - 1);
3818 assert(MVT::isInteger(LVT));
3823 unsigned NumMemOps = 0;
3825 unsigned VTSize = getSizeInBits(VT) / 8;
3826 while (VTSize > Size) {
3827 VT = (MVT::ValueType)((unsigned)VT - 1);
3830 assert(MVT::isInteger(VT));
3832 if (++NumMemOps > Limit)
3834 MemOps.push_back(VT);
3841 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
3842 SDOperand Op1 = getValue(I.getOperand(1));
3843 SDOperand Op2 = getValue(I.getOperand(2));
3844 SDOperand Op3 = getValue(I.getOperand(3));
3845 SDOperand Op4 = getValue(I.getOperand(4));
3846 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
3847 if (Align == 0) Align = 1;
3849 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
3850 std::vector<MVT::ValueType> MemOps;
3852 // Expand memset / memcpy to a series of load / store ops
3853 // if the size operand falls below a certain threshold.
3854 SmallVector<SDOperand, 8> OutChains;
3856 default: break; // Do nothing for now.
3858 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
3859 Size->getValue(), Align, TLI)) {
3860 unsigned NumMemOps = MemOps.size();
3861 unsigned Offset = 0;
3862 for (unsigned i = 0; i < NumMemOps; i++) {
3863 MVT::ValueType VT = MemOps[i];
3864 unsigned VTSize = getSizeInBits(VT) / 8;
3865 SDOperand Value = getMemsetValue(Op2, VT, DAG);
3866 SDOperand Store = DAG.getStore(getRoot(), Value,
3867 getMemBasePlusOffset(Op1, Offset, DAG, TLI),
3868 I.getOperand(1), Offset);
3869 OutChains.push_back(Store);
3876 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
3877 Size->getValue(), Align, TLI)) {
3878 unsigned NumMemOps = MemOps.size();
3879 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
3880 GlobalAddressSDNode *G = NULL;
3882 bool CopyFromStr = false;
3884 if (Op2.getOpcode() == ISD::GlobalAddress)
3885 G = cast<GlobalAddressSDNode>(Op2);
3886 else if (Op2.getOpcode() == ISD::ADD &&
3887 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3888 Op2.getOperand(1).getOpcode() == ISD::Constant) {
3889 G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
3890 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
3893 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3894 if (GV && GV->isConstant()) {
3895 Str = GV->getStringValue(false);
3903 for (unsigned i = 0; i < NumMemOps; i++) {
3904 MVT::ValueType VT = MemOps[i];
3905 unsigned VTSize = getSizeInBits(VT) / 8;
3906 SDOperand Value, Chain, Store;
3909 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
3912 DAG.getStore(Chain, Value,
3913 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3914 I.getOperand(1), DstOff);
3916 Value = DAG.getLoad(VT, getRoot(),
3917 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
3918 I.getOperand(2), SrcOff);
3919 Chain = Value.getValue(1);
3921 DAG.getStore(Chain, Value,
3922 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3923 I.getOperand(1), DstOff);
3925 OutChains.push_back(Store);
3934 if (!OutChains.empty()) {
3935 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
3936 &OutChains[0], OutChains.size()));
3941 DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
3944 //===----------------------------------------------------------------------===//
3945 // SelectionDAGISel code
3946 //===----------------------------------------------------------------------===//
3948 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
3949 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
3952 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
3953 AU.addRequired<AliasAnalysis>();
3954 AU.setPreservesAll();
3959 bool SelectionDAGISel::runOnFunction(Function &Fn) {
3960 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
3961 RegMap = MF.getSSARegMap();
3962 DOUT << "\n\n\n=== " << Fn.getName() << "\n";
3964 FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
3966 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
3967 SelectBasicBlock(I, MF, FuncInfo);
3969 // Add function live-ins to entry block live-in set.
3970 BasicBlock *EntryBB = &Fn.getEntryBlock();
3971 BB = FuncInfo.MBBMap[EntryBB];
3972 if (!MF.livein_empty())
3973 for (MachineFunction::livein_iterator I = MF.livein_begin(),
3974 E = MF.livein_end(); I != E; ++I)
3975 BB->addLiveIn(I->first);
3980 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V,
3982 SDOperand Op = getValue(V);
3983 assert((Op.getOpcode() != ISD::CopyFromReg ||
3984 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
3985 "Copy from a reg to the same reg!");
3987 // If this type is not legal, we must make sure to not create an invalid
3989 MVT::ValueType SrcVT = Op.getValueType();
3990 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
3991 if (SrcVT == DestVT) {
3992 return DAG.getCopyToReg(getRoot(), Reg, Op);
3993 } else if (SrcVT == MVT::Vector) {
3994 // Handle copies from generic vectors to registers.
3995 MVT::ValueType PTyElementVT, PTyLegalElementVT;
3996 unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
3997 PTyElementVT, PTyLegalElementVT);
3999 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
4000 // MVT::Vector type.
4001 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
4002 DAG.getConstant(NE, MVT::i32),
4003 DAG.getValueType(PTyElementVT));
4005 // Loop over all of the elements of the resultant vector,
4006 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
4007 // copying them into output registers.
4008 SmallVector<SDOperand, 8> OutChains;
4009 SDOperand Root = getRoot();
4010 for (unsigned i = 0; i != NE; ++i) {
4011 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
4012 Op, DAG.getConstant(i, TLI.getPointerTy()));
4013 if (PTyElementVT == PTyLegalElementVT) {
4014 // Elements are legal.
4015 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4016 } else if (PTyLegalElementVT > PTyElementVT) {
4017 // Elements are promoted.
4018 if (MVT::isFloatingPoint(PTyLegalElementVT))
4019 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
4021 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
4022 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4024 // Elements are expanded.
4025 // The src value is expanded into multiple registers.
4026 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4027 Elt, DAG.getConstant(0, TLI.getPointerTy()));
4028 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4029 Elt, DAG.getConstant(1, TLI.getPointerTy()));
4030 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
4031 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
4034 return DAG.getNode(ISD::TokenFactor, MVT::Other,
4035 &OutChains[0], OutChains.size());
4036 } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
4037 // The src value is promoted to the register.
4038 if (MVT::isFloatingPoint(SrcVT))
4039 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
4041 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
4042 return DAG.getCopyToReg(getRoot(), Reg, Op);
4044 DestVT = TLI.getTypeToExpandTo(SrcVT);
4045 unsigned NumVals = TLI.getNumElements(SrcVT);
4047 return DAG.getCopyToReg(getRoot(), Reg,
4048 DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
4049 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
4050 // The src value is expanded into multiple registers.
4051 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4052 Op, DAG.getConstant(0, TLI.getPointerTy()));
4053 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4054 Op, DAG.getConstant(1, TLI.getPointerTy()));
4055 Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
4056 return DAG.getCopyToReg(Op, Reg+1, Hi);
4060 void SelectionDAGISel::
4061 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
4062 std::vector<SDOperand> &UnorderedChains) {
4063 // If this is the entry block, emit arguments.
4064 Function &F = *LLVMBB->getParent();
4065 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4066 SDOperand OldRoot = SDL.DAG.getRoot();
4067 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
4070 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4072 if (!AI->use_empty()) {
4073 SDL.setValue(AI, Args[a]);
4075 // If this argument is live outside of the entry block, insert a copy from
4076 // whereever we got it to the vreg that other BB's will reference it as.
4077 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4078 if (VMI != FuncInfo.ValueMap.end()) {
4079 SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
4080 UnorderedChains.push_back(Copy);
4084 // Finally, if the target has anything special to do, allow it to do so.
4085 // FIXME: this should insert code into the DAG!
4086 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4089 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
4090 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
4091 FunctionLoweringInfo &FuncInfo) {
4092 SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
4094 std::vector<SDOperand> UnorderedChains;
4096 // Lower any arguments needed in this block if this is the entry block.
4097 if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
4098 LowerArguments(LLVMBB, SDL, UnorderedChains);
4100 BB = FuncInfo.MBBMap[LLVMBB];
4101 SDL.setCurrentBasicBlock(BB);
4103 // Lower all of the non-terminator instructions.
4104 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
4108 // Lower call part of invoke.
4109 InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
4110 if (Invoke) SDL.visitInvoke(*Invoke, false);
4112 // Ensure that all instructions which are used outside of their defining
4113 // blocks are available as virtual registers.
4114 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
4115 if (!I->use_empty() && !isa<PHINode>(I)) {
4116 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4117 if (VMI != FuncInfo.ValueMap.end())
4118 UnorderedChains.push_back(
4119 SDL.CopyValueToVirtualRegister(I, VMI->second));
4122 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to
4123 // ensure constants are generated when needed. Remember the virtual registers
4124 // that need to be added to the Machine PHI nodes as input. We cannot just
4125 // directly add them, because expansion might result in multiple MBB's for one
4126 // BB. As such, the start of the BB might correspond to a different MBB than
4129 TerminatorInst *TI = LLVMBB->getTerminator();
4131 // Emit constants only once even if used by multiple PHI nodes.
4132 std::map<Constant*, unsigned> ConstantsOut;
4134 // Vector bool would be better, but vector<bool> is really slow.
4135 std::vector<unsigned char> SuccsHandled;
4136 if (TI->getNumSuccessors())
4137 SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4139 // Check successor nodes PHI nodes that expect a constant to be available from
4141 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4142 BasicBlock *SuccBB = TI->getSuccessor(succ);
4143 if (!isa<PHINode>(SuccBB->begin())) continue;
4144 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4146 // If this terminator has multiple identical successors (common for
4147 // switches), only handle each succ once.
4148 unsigned SuccMBBNo = SuccMBB->getNumber();
4149 if (SuccsHandled[SuccMBBNo]) continue;
4150 SuccsHandled[SuccMBBNo] = true;
4152 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4155 // At this point we know that there is a 1-1 correspondence between LLVM PHI
4156 // nodes and Machine PHI nodes, but the incoming operands have not been
4158 for (BasicBlock::iterator I = SuccBB->begin();
4159 (PN = dyn_cast<PHINode>(I)); ++I) {
4160 // Ignore dead phi's.
4161 if (PN->use_empty()) continue;
4164 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4166 if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4167 unsigned &RegOut = ConstantsOut[C];
4169 RegOut = FuncInfo.CreateRegForValue(C);
4170 UnorderedChains.push_back(
4171 SDL.CopyValueToVirtualRegister(C, RegOut));
4175 Reg = FuncInfo.ValueMap[PHIOp];
4177 assert(isa<AllocaInst>(PHIOp) &&
4178 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4179 "Didn't codegen value into a register!??");
4180 Reg = FuncInfo.CreateRegForValue(PHIOp);
4181 UnorderedChains.push_back(
4182 SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4186 // Remember that this register needs to added to the machine PHI node as
4187 // the input for this MBB.
4188 MVT::ValueType VT = TLI.getValueType(PN->getType());
4189 unsigned NumElements;
4190 if (VT != MVT::Vector)
4191 NumElements = TLI.getNumElements(VT);
4193 MVT::ValueType VT1,VT2;
4195 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
4198 for (unsigned i = 0, e = NumElements; i != e; ++i)
4199 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4202 ConstantsOut.clear();
4204 // Turn all of the unordered chains into one factored node.
4205 if (!UnorderedChains.empty()) {
4206 SDOperand Root = SDL.getRoot();
4207 if (Root.getOpcode() != ISD::EntryToken) {
4208 unsigned i = 0, e = UnorderedChains.size();
4209 for (; i != e; ++i) {
4210 assert(UnorderedChains[i].Val->getNumOperands() > 1);
4211 if (UnorderedChains[i].Val->getOperand(0) == Root)
4212 break; // Don't add the root if we already indirectly depend on it.
4216 UnorderedChains.push_back(Root);
4218 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4219 &UnorderedChains[0], UnorderedChains.size()));
4222 // Lower the terminator after the copies are emitted.
4224 // Just the branch part of invoke.
4225 SDL.visitInvoke(*Invoke, true);
4227 SDL.visit(*LLVMBB->getTerminator());
4230 // Copy over any CaseBlock records that may now exist due to SwitchInst
4231 // lowering, as well as any jump table information.
4232 SwitchCases.clear();
4233 SwitchCases = SDL.SwitchCases;
4235 JTCases = SDL.JTCases;
4237 // Make sure the root of the DAG is up-to-date.
4238 DAG.setRoot(SDL.getRoot());
4241 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4242 // Get alias analysis for load/store combining.
4243 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
4245 // Run the DAG combiner in pre-legalize mode.
4246 DAG.Combine(false, AA);
4248 DOUT << "Lowered selection DAG:\n";
4251 // Second step, hack on the DAG until it only uses operations and types that
4252 // the target supports.
4255 DOUT << "Legalized selection DAG:\n";
4258 // Run the DAG combiner in post-legalize mode.
4259 DAG.Combine(true, AA);
4261 if (ViewISelDAGs) DAG.viewGraph();
4263 // Third, instruction select all of the operations to machine code, adding the
4264 // code to the MachineBasicBlock.
4265 InstructionSelectBasicBlock(DAG);
4267 DOUT << "Selected machine code:\n";
4271 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4272 FunctionLoweringInfo &FuncInfo) {
4273 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4275 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4278 // First step, lower LLVM code to some DAG. This DAG may use operations and
4279 // types that are not supported by the target.
4280 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4282 // Second step, emit the lowered DAG as machine code.
4283 CodeGenAndEmitDAG(DAG);
4286 // Next, now that we know what the last MBB the LLVM BB expanded is, update
4287 // PHI nodes in successors.
4288 if (SwitchCases.empty() && JTCases.empty()) {
4289 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4290 MachineInstr *PHI = PHINodesToUpdate[i].first;
4291 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4292 "This is not a machine PHI node that we are updating!");
4293 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4294 PHI->addMachineBasicBlockOperand(BB);
4299 // If the JumpTable record is filled in, then we need to emit a jump table.
4300 // Updating the PHI nodes is tricky in this case, since we need to determine
4301 // whether the PHI is a successor of the range check MBB or the jump table MBB
4302 for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
4303 // Lower header first, if it wasn't already lowered
4304 if (!JTCases[i].first.Emitted) {
4305 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4307 SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
4308 // Set the current basic block to the mbb we wish to insert the code into
4309 BB = JTCases[i].first.HeaderBB;
4310 HSDL.setCurrentBasicBlock(BB);
4312 HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
4313 HSDAG.setRoot(HSDL.getRoot());
4314 CodeGenAndEmitDAG(HSDAG);
4317 SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4319 SelectionDAGLowering JSDL(JSDAG, TLI, FuncInfo);
4320 // Set the current basic block to the mbb we wish to insert the code into
4321 BB = JTCases[i].second.MBB;
4322 JSDL.setCurrentBasicBlock(BB);
4324 JSDL.visitJumpTable(JTCases[i].second);
4325 JSDAG.setRoot(JSDL.getRoot());
4326 CodeGenAndEmitDAG(JSDAG);
4329 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4330 MachineInstr *PHI = PHINodesToUpdate[pi].first;
4331 MachineBasicBlock *PHIBB = PHI->getParent();
4332 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4333 "This is not a machine PHI node that we are updating!");
4334 if (PHIBB == JTCases[i].second.Default) {
4335 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4336 PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
4338 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4339 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4340 PHI->addMachineBasicBlockOperand(BB);
4345 // If the switch block involved a branch to one of the actual successors, we
4346 // need to update PHI nodes in that block.
4347 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4348 MachineInstr *PHI = PHINodesToUpdate[i].first;
4349 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4350 "This is not a machine PHI node that we are updating!");
4351 if (BB->isSuccessor(PHI->getParent())) {
4352 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4353 PHI->addMachineBasicBlockOperand(BB);
4357 // If we generated any switch lowering information, build and codegen any
4358 // additional DAGs necessary.
4359 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4360 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4362 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4364 // Set the current basic block to the mbb we wish to insert the code into
4365 BB = SwitchCases[i].ThisBB;
4366 SDL.setCurrentBasicBlock(BB);
4369 SDL.visitSwitchCase(SwitchCases[i]);
4370 SDAG.setRoot(SDL.getRoot());
4371 CodeGenAndEmitDAG(SDAG);
4373 // Handle any PHI nodes in successors of this chunk, as if we were coming
4374 // from the original BB before switch expansion. Note that PHI nodes can
4375 // occur multiple times in PHINodesToUpdate. We have to be very careful to
4376 // handle them the right number of times.
4377 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS.
4378 for (MachineBasicBlock::iterator Phi = BB->begin();
4379 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4380 // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4381 for (unsigned pn = 0; ; ++pn) {
4382 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4383 if (PHINodesToUpdate[pn].first == Phi) {
4384 Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4385 Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4391 // Don't process RHS if same block as LHS.
4392 if (BB == SwitchCases[i].FalseBB)
4393 SwitchCases[i].FalseBB = 0;
4395 // If we haven't handled the RHS, do so now. Otherwise, we're done.
4396 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4397 SwitchCases[i].FalseBB = 0;
4399 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4404 //===----------------------------------------------------------------------===//
4405 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4406 /// target node in the graph.
4407 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4408 if (ViewSchedDAGs) DAG.viewGraph();
4410 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4414 RegisterScheduler::setDefault(Ctor);
4417 ScheduleDAG *SL = Ctor(this, &DAG, BB);
4423 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4424 return new HazardRecognizer();
4427 //===----------------------------------------------------------------------===//
4428 // Helper functions used by the generated instruction selector.
4429 //===----------------------------------------------------------------------===//
4430 // Calls to these methods are generated by tblgen.
4432 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
4433 /// the dag combiner simplified the 255, we still want to match. RHS is the
4434 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
4435 /// specified in the .td file (e.g. 255).
4436 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
4437 int64_t DesiredMaskS) {
4438 uint64_t ActualMask = RHS->getValue();
4439 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4441 // If the actual mask exactly matches, success!
4442 if (ActualMask == DesiredMask)
4445 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4446 if (ActualMask & ~DesiredMask)
4449 // Otherwise, the DAG Combiner may have proven that the value coming in is
4450 // either already zero or is not demanded. Check for known zero input bits.
4451 uint64_t NeededMask = DesiredMask & ~ActualMask;
4452 if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
4455 // TODO: check to see if missing bits are just not demanded.
4457 // Otherwise, this pattern doesn't match.
4461 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
4462 /// the dag combiner simplified the 255, we still want to match. RHS is the
4463 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
4464 /// specified in the .td file (e.g. 255).
4465 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
4466 int64_t DesiredMaskS) {
4467 uint64_t ActualMask = RHS->getValue();
4468 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4470 // If the actual mask exactly matches, success!
4471 if (ActualMask == DesiredMask)
4474 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4475 if (ActualMask & ~DesiredMask)
4478 // Otherwise, the DAG Combiner may have proven that the value coming in is
4479 // either already zero or is not demanded. Check for known zero input bits.
4480 uint64_t NeededMask = DesiredMask & ~ActualMask;
4482 uint64_t KnownZero, KnownOne;
4483 getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
4485 // If all the missing bits in the or are already known to be set, match!
4486 if ((NeededMask & KnownOne) == NeededMask)
4489 // TODO: check to see if missing bits are just not demanded.
4491 // Otherwise, this pattern doesn't match.
4496 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
4497 /// by tblgen. Others should not call it.
4498 void SelectionDAGISel::
4499 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
4500 std::vector<SDOperand> InOps;
4501 std::swap(InOps, Ops);
4503 Ops.push_back(InOps[0]); // input chain.
4504 Ops.push_back(InOps[1]); // input asm string.
4506 unsigned i = 2, e = InOps.size();
4507 if (InOps[e-1].getValueType() == MVT::Flag)
4508 --e; // Don't process a flag operand if it is here.
4511 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
4512 if ((Flags & 7) != 4 /*MEM*/) {
4513 // Just skip over this operand, copying the operands verbatim.
4514 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
4515 i += (Flags >> 3) + 1;
4517 assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
4518 // Otherwise, this is a memory operand. Ask the target to select it.
4519 std::vector<SDOperand> SelOps;
4520 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
4521 cerr << "Could not match memory address. Inline asm failure!\n";
4525 // Add this to the output node.
4526 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
4527 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
4529 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
4534 // Add the flag input back if present.
4535 if (e != InOps.size())
4536 Ops.push_back(InOps.back());