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) && MVT::isInteger(Val.getValueType())) {
2660 if (RegVT < ValueVT)
2661 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
2663 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
2664 } else if (MVT::isFloatingPoint(RegVT) &&
2665 MVT::isFloatingPoint(Val.getValueType())) {
2666 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
2667 } else if (MVT::getSizeInBits(RegVT) ==
2668 MVT::getSizeInBits(Val.getValueType())) {
2669 Val = DAG.getNode(ISD::BIT_CONVERT, RegVT, Val);
2671 assert(0 && "Unknown mismatch!");
2674 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
2675 Flag = Chain.getValue(1);
2677 std::vector<unsigned> R(Regs);
2678 if (!DAG.getTargetLoweringInfo().isLittleEndian())
2679 std::reverse(R.begin(), R.end());
2681 for (unsigned i = 0, e = R.size(); i != e; ++i) {
2682 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
2683 DAG.getConstant(i, PtrVT));
2684 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
2685 Flag = Chain.getValue(1);
2690 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
2691 /// operand list. This adds the code marker and includes the number of
2692 /// values added into it.
2693 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
2694 std::vector<SDOperand> &Ops) const {
2695 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
2696 Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
2697 for (unsigned i = 0, e = Regs.size(); i != e; ++i)
2698 Ops.push_back(DAG.getRegister(Regs[i], RegVT));
2701 /// isAllocatableRegister - If the specified register is safe to allocate,
2702 /// i.e. it isn't a stack pointer or some other special register, return the
2703 /// register class for the register. Otherwise, return null.
2704 static const TargetRegisterClass *
2705 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
2706 const TargetLowering &TLI, const MRegisterInfo *MRI) {
2707 MVT::ValueType FoundVT = MVT::Other;
2708 const TargetRegisterClass *FoundRC = 0;
2709 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
2710 E = MRI->regclass_end(); RCI != E; ++RCI) {
2711 MVT::ValueType ThisVT = MVT::Other;
2713 const TargetRegisterClass *RC = *RCI;
2714 // If none of the the value types for this register class are valid, we
2715 // can't use it. For example, 64-bit reg classes on 32-bit targets.
2716 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
2718 if (TLI.isTypeLegal(*I)) {
2719 // If we have already found this register in a different register class,
2720 // choose the one with the largest VT specified. For example, on
2721 // PowerPC, we favor f64 register classes over f32.
2722 if (FoundVT == MVT::Other ||
2723 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
2730 if (ThisVT == MVT::Other) continue;
2732 // NOTE: This isn't ideal. In particular, this might allocate the
2733 // frame pointer in functions that need it (due to them not being taken
2734 // out of allocation, because a variable sized allocation hasn't been seen
2735 // yet). This is a slight code pessimization, but should still work.
2736 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
2737 E = RC->allocation_order_end(MF); I != E; ++I)
2739 // We found a matching register class. Keep looking at others in case
2740 // we find one with larger registers that this physreg is also in.
2749 RegsForValue SelectionDAGLowering::
2750 GetRegistersForValue(const std::string &ConstrCode,
2751 MVT::ValueType VT, bool isOutReg, bool isInReg,
2752 std::set<unsigned> &OutputRegs,
2753 std::set<unsigned> &InputRegs) {
2754 std::pair<unsigned, const TargetRegisterClass*> PhysReg =
2755 TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
2756 std::vector<unsigned> Regs;
2758 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
2759 MVT::ValueType RegVT;
2760 MVT::ValueType ValueVT = VT;
2762 // If this is a constraint for a specific physical register, like {r17},
2764 if (PhysReg.first) {
2765 if (VT == MVT::Other)
2766 ValueVT = *PhysReg.second->vt_begin();
2768 // Get the actual register value type. This is important, because the user
2769 // may have asked for (e.g.) the AX register in i32 type. We need to
2770 // remember that AX is actually i16 to get the right extension.
2771 RegVT = *PhysReg.second->vt_begin();
2773 // This is a explicit reference to a physical register.
2774 Regs.push_back(PhysReg.first);
2776 // If this is an expanded reference, add the rest of the regs to Regs.
2778 TargetRegisterClass::iterator I = PhysReg.second->begin();
2779 TargetRegisterClass::iterator E = PhysReg.second->end();
2780 for (; *I != PhysReg.first; ++I)
2781 assert(I != E && "Didn't find reg!");
2783 // Already added the first reg.
2785 for (; NumRegs; --NumRegs, ++I) {
2786 assert(I != E && "Ran out of registers to allocate!");
2790 return RegsForValue(Regs, RegVT, ValueVT);
2793 // Otherwise, if this was a reference to an LLVM register class, create vregs
2794 // for this reference.
2795 std::vector<unsigned> RegClassRegs;
2796 if (PhysReg.second) {
2797 // If this is an early clobber or tied register, our regalloc doesn't know
2798 // how to maintain the constraint. If it isn't, go ahead and create vreg
2799 // and let the regalloc do the right thing.
2800 if (!isOutReg || !isInReg) {
2801 if (VT == MVT::Other)
2802 ValueVT = *PhysReg.second->vt_begin();
2803 RegVT = *PhysReg.second->vt_begin();
2805 // Create the appropriate number of virtual registers.
2806 SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
2807 for (; NumRegs; --NumRegs)
2808 Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
2810 return RegsForValue(Regs, RegVT, ValueVT);
2813 // Otherwise, we can't allocate it. Let the code below figure out how to
2814 // maintain these constraints.
2815 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
2818 // This is a reference to a register class that doesn't directly correspond
2819 // to an LLVM register class. Allocate NumRegs consecutive, available,
2820 // registers from the class.
2821 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
2824 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
2825 MachineFunction &MF = *CurMBB->getParent();
2826 unsigned NumAllocated = 0;
2827 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
2828 unsigned Reg = RegClassRegs[i];
2829 // See if this register is available.
2830 if ((isOutReg && OutputRegs.count(Reg)) || // Already used.
2831 (isInReg && InputRegs.count(Reg))) { // Already used.
2832 // Make sure we find consecutive registers.
2837 // Check to see if this register is allocatable (i.e. don't give out the
2839 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
2841 // Make sure we find consecutive registers.
2846 // Okay, this register is good, we can use it.
2849 // If we allocated enough consecutive registers, succeed.
2850 if (NumAllocated == NumRegs) {
2851 unsigned RegStart = (i-NumAllocated)+1;
2852 unsigned RegEnd = i+1;
2853 // Mark all of the allocated registers used.
2854 for (unsigned i = RegStart; i != RegEnd; ++i) {
2855 unsigned Reg = RegClassRegs[i];
2856 Regs.push_back(Reg);
2857 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used.
2858 if (isInReg) InputRegs.insert(Reg); // Mark reg used.
2861 return RegsForValue(Regs, *RC->vt_begin(), VT);
2865 // Otherwise, we couldn't allocate enough registers for this.
2866 return RegsForValue();
2869 /// getConstraintGenerality - Return an integer indicating how general CT is.
2870 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
2872 default: assert(0 && "Unknown constraint type!");
2873 case TargetLowering::C_Other:
2874 case TargetLowering::C_Unknown:
2876 case TargetLowering::C_Register:
2878 case TargetLowering::C_RegisterClass:
2880 case TargetLowering::C_Memory:
2885 static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
2886 const TargetLowering &TLI) {
2887 assert(!C.empty() && "Must have at least one constraint");
2888 if (C.size() == 1) return C[0];
2890 std::string *Current = &C[0];
2891 // If we have multiple constraints, try to pick the most general one ahead
2892 // of time. This isn't a wonderful solution, but handles common cases.
2893 TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
2894 for (unsigned j = 1, e = C.size(); j != e; ++j) {
2895 TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
2896 if (getConstraintGenerality(ThisFlavor) >
2897 getConstraintGenerality(Flavor)) {
2898 // This constraint letter is more general than the previous one,
2900 Flavor = ThisFlavor;
2908 /// visitInlineAsm - Handle a call to an InlineAsm object.
2910 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
2911 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
2913 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
2916 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
2917 std::vector<MVT::ValueType> ConstraintVTs;
2919 /// AsmNodeOperands - A list of pairs. The first element is a register, the
2920 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
2921 /// if it is a def of that register.
2922 std::vector<SDOperand> AsmNodeOperands;
2923 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
2924 AsmNodeOperands.push_back(AsmStr);
2926 SDOperand Chain = getRoot();
2929 // We fully assign registers here at isel time. This is not optimal, but
2930 // should work. For register classes that correspond to LLVM classes, we
2931 // could let the LLVM RA do its thing, but we currently don't. Do a prepass
2932 // over the constraints, collecting fixed registers that we know we can't use.
2933 std::set<unsigned> OutputRegs, InputRegs;
2935 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2936 std::string ConstraintCode =
2937 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2939 MVT::ValueType OpVT;
2941 // Compute the value type for each operand and add it to ConstraintVTs.
2942 switch (Constraints[i].Type) {
2943 case InlineAsm::isOutput:
2944 if (!Constraints[i].isIndirectOutput) {
2945 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2946 OpVT = TLI.getValueType(I.getType());
2948 const Type *OpTy = I.getOperand(OpNum)->getType();
2949 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
2950 OpNum++; // Consumes a call operand.
2953 case InlineAsm::isInput:
2954 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
2955 OpNum++; // Consumes a call operand.
2957 case InlineAsm::isClobber:
2962 ConstraintVTs.push_back(OpVT);
2964 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
2965 continue; // Not assigned a fixed reg.
2967 // Build a list of regs that this operand uses. This always has a single
2968 // element for promoted/expanded operands.
2969 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
2971 OutputRegs, InputRegs);
2973 switch (Constraints[i].Type) {
2974 case InlineAsm::isOutput:
2975 // We can't assign any other output to this register.
2976 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2977 // If this is an early-clobber output, it cannot be assigned to the same
2978 // value as the input reg.
2979 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2980 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2982 case InlineAsm::isInput:
2983 // We can't assign any other input to this register.
2984 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2986 case InlineAsm::isClobber:
2987 // Clobbered regs cannot be used as inputs or outputs.
2988 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2989 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2994 // Loop over all of the inputs, copying the operand values into the
2995 // appropriate registers and processing the output regs.
2996 RegsForValue RetValRegs;
2997 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
3000 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
3001 std::string ConstraintCode =
3002 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
3004 switch (Constraints[i].Type) {
3005 case InlineAsm::isOutput: {
3006 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3007 if (ConstraintCode.size() == 1) // not a physreg name.
3008 CTy = TLI.getConstraintType(ConstraintCode);
3010 if (CTy == TargetLowering::C_Memory) {
3012 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3014 // Check that the operand (the address to store to) isn't a float.
3015 if (!MVT::isInteger(InOperandVal.getValueType()))
3016 assert(0 && "MATCH FAIL!");
3018 if (!Constraints[i].isIndirectOutput)
3019 assert(0 && "MATCH FAIL!");
3021 OpNum++; // Consumes a call operand.
3023 // Extend/truncate to the right pointer type if needed.
3024 MVT::ValueType PtrType = TLI.getPointerTy();
3025 if (InOperandVal.getValueType() < PtrType)
3026 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3027 else if (InOperandVal.getValueType() > PtrType)
3028 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3030 // Add information to the INLINEASM node to know about this output.
3031 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3032 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3033 AsmNodeOperands.push_back(InOperandVal);
3037 // Otherwise, this is a register output.
3038 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3040 // If this is an early-clobber output, or if there is an input
3041 // constraint that matches this, we need to reserve the input register
3042 // so no other inputs allocate to it.
3043 bool UsesInputRegister = false;
3044 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
3045 UsesInputRegister = true;
3047 // Copy the output from the appropriate register. Find a register that
3050 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3051 true, UsesInputRegister,
3052 OutputRegs, InputRegs);
3053 if (Regs.Regs.empty()) {
3054 cerr << "Couldn't allocate output reg for contraint '"
3055 << ConstraintCode << "'!\n";
3059 if (!Constraints[i].isIndirectOutput) {
3060 assert(RetValRegs.Regs.empty() &&
3061 "Cannot have multiple output constraints yet!");
3062 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
3065 IndirectStoresToEmit.push_back(std::make_pair(Regs,
3066 I.getOperand(OpNum)));
3067 OpNum++; // Consumes a call operand.
3070 // Add information to the INLINEASM node to know that this register is
3072 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
3075 case InlineAsm::isInput: {
3076 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
3077 OpNum++; // Consumes a call operand.
3079 if (isdigit(ConstraintCode[0])) { // Matching constraint?
3080 // If this is required to match an output register we have already set,
3081 // just use its register.
3082 unsigned OperandNo = atoi(ConstraintCode.c_str());
3084 // Scan until we find the definition we already emitted of this operand.
3085 // When we find it, create a RegsForValue operand.
3086 unsigned CurOp = 2; // The first operand.
3087 for (; OperandNo; --OperandNo) {
3088 // Advance to the next operand.
3090 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3091 assert(((NumOps & 7) == 2 /*REGDEF*/ ||
3092 (NumOps & 7) == 4 /*MEM*/) &&
3093 "Skipped past definitions?");
3094 CurOp += (NumOps>>3)+1;
3098 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
3099 if ((NumOps & 7) == 2 /*REGDEF*/) {
3100 // Add NumOps>>3 registers to MatchedRegs.
3101 RegsForValue MatchedRegs;
3102 MatchedRegs.ValueVT = InOperandVal.getValueType();
3103 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType();
3104 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
3106 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
3107 MatchedRegs.Regs.push_back(Reg);
3110 // Use the produced MatchedRegs object to
3111 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
3112 TLI.getPointerTy());
3113 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
3116 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
3117 assert(0 && "matching constraints for memory operands unimp");
3121 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
3122 if (ConstraintCode.size() == 1) // not a physreg name.
3123 CTy = TLI.getConstraintType(ConstraintCode);
3125 if (CTy == TargetLowering::C_Other) {
3126 InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
3127 ConstraintCode[0], DAG);
3128 if (!InOperandVal.Val) {
3129 cerr << "Invalid operand for inline asm constraint '"
3130 << ConstraintCode << "'!\n";
3134 // Add information to the INLINEASM node to know about this input.
3135 unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
3136 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3137 AsmNodeOperands.push_back(InOperandVal);
3139 } else if (CTy == TargetLowering::C_Memory) {
3142 // If the operand is a float, spill to a constant pool entry to get its
3144 if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
3145 InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
3147 if (!MVT::isInteger(InOperandVal.getValueType())) {
3148 cerr << "Match failed, cannot handle this yet!\n";
3149 InOperandVal.Val->dump();
3153 // Extend/truncate to the right pointer type if needed.
3154 MVT::ValueType PtrType = TLI.getPointerTy();
3155 if (InOperandVal.getValueType() < PtrType)
3156 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
3157 else if (InOperandVal.getValueType() > PtrType)
3158 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
3160 // Add information to the INLINEASM node to know about this input.
3161 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
3162 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
3163 AsmNodeOperands.push_back(InOperandVal);
3167 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
3169 // Copy the input into the appropriate registers.
3170 RegsForValue InRegs =
3171 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
3172 false, true, OutputRegs, InputRegs);
3173 // FIXME: should be match fail.
3174 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
3176 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
3178 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
3181 case InlineAsm::isClobber: {
3182 RegsForValue ClobberedRegs =
3183 GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
3184 OutputRegs, InputRegs);
3185 // Add the clobbered value to the operand list, so that the register
3186 // allocator is aware that the physreg got clobbered.
3187 if (!ClobberedRegs.Regs.empty())
3188 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
3194 // Finish up input operands.
3195 AsmNodeOperands[0] = Chain;
3196 if (Flag.Val) AsmNodeOperands.push_back(Flag);
3198 Chain = DAG.getNode(ISD::INLINEASM,
3199 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
3200 &AsmNodeOperands[0], AsmNodeOperands.size());
3201 Flag = Chain.getValue(1);
3203 // If this asm returns a register value, copy the result from that register
3204 // and set it as the value of the call.
3205 if (!RetValRegs.Regs.empty())
3206 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
3208 std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
3210 // Process indirect outputs, first output all of the flagged copies out of
3212 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
3213 RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
3214 Value *Ptr = IndirectStoresToEmit[i].second;
3215 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
3216 StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
3219 // Emit the non-flagged stores from the physregs.
3220 SmallVector<SDOperand, 8> OutChains;
3221 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
3222 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
3223 getValue(StoresToEmit[i].second),
3224 StoresToEmit[i].second, 0));
3225 if (!OutChains.empty())
3226 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3227 &OutChains[0], OutChains.size());
3232 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
3233 SDOperand Src = getValue(I.getOperand(0));
3235 MVT::ValueType IntPtr = TLI.getPointerTy();
3237 if (IntPtr < Src.getValueType())
3238 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
3239 else if (IntPtr > Src.getValueType())
3240 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
3242 // Scale the source by the type size.
3243 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
3244 Src = DAG.getNode(ISD::MUL, Src.getValueType(),
3245 Src, getIntPtrConstant(ElementSize));
3247 TargetLowering::ArgListTy Args;
3248 TargetLowering::ArgListEntry Entry;
3250 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3251 Args.push_back(Entry);
3253 std::pair<SDOperand,SDOperand> Result =
3254 TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3255 DAG.getExternalSymbol("malloc", IntPtr),
3257 setValue(&I, Result.first); // Pointers always fit in registers
3258 DAG.setRoot(Result.second);
3261 void SelectionDAGLowering::visitFree(FreeInst &I) {
3262 TargetLowering::ArgListTy Args;
3263 TargetLowering::ArgListEntry Entry;
3264 Entry.Node = getValue(I.getOperand(0));
3265 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3266 Args.push_back(Entry);
3267 MVT::ValueType IntPtr = TLI.getPointerTy();
3268 std::pair<SDOperand,SDOperand> Result =
3269 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3270 DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3271 DAG.setRoot(Result.second);
3274 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3275 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These
3276 // instructions are special in various ways, which require special support to
3277 // insert. The specified MachineInstr is created but not inserted into any
3278 // basic blocks, and the scheduler passes ownership of it to this method.
3279 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3280 MachineBasicBlock *MBB) {
3281 cerr << "If a target marks an instruction with "
3282 << "'usesCustomDAGSchedInserter', it must implement "
3283 << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3288 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3289 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
3290 getValue(I.getOperand(1)),
3291 DAG.getSrcValue(I.getOperand(1))));
3294 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3295 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3296 getValue(I.getOperand(0)),
3297 DAG.getSrcValue(I.getOperand(0)));
3299 DAG.setRoot(V.getValue(1));
3302 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3303 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3304 getValue(I.getOperand(1)),
3305 DAG.getSrcValue(I.getOperand(1))));
3308 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3309 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
3310 getValue(I.getOperand(1)),
3311 getValue(I.getOperand(2)),
3312 DAG.getSrcValue(I.getOperand(1)),
3313 DAG.getSrcValue(I.getOperand(2))));
3316 /// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
3317 /// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
3318 static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
3319 unsigned &i, SelectionDAG &DAG,
3320 TargetLowering &TLI) {
3321 if (TLI.getTypeAction(VT) != TargetLowering::Expand)
3322 return SDOperand(Arg, i++);
3324 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3325 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3327 return DAG.getNode(ISD::BIT_CONVERT, VT,
3328 ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
3329 } else if (NumVals == 2) {
3330 SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3331 SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3332 if (!TLI.isLittleEndian())
3334 return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
3336 // Value scalarized into many values. Unimp for now.
3337 assert(0 && "Cannot expand i64 -> i16 yet!");
3342 /// TargetLowering::LowerArguments - This is the default LowerArguments
3343 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all
3344 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
3345 /// integrated into SDISel.
3346 std::vector<SDOperand>
3347 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3348 const FunctionType *FTy = F.getFunctionType();
3349 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3350 std::vector<SDOperand> Ops;
3351 Ops.push_back(DAG.getRoot());
3352 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3353 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3355 // Add one result value for each formal argument.
3356 std::vector<MVT::ValueType> RetVals;
3358 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3360 MVT::ValueType VT = getValueType(I->getType());
3361 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3362 unsigned OriginalAlignment =
3363 getTargetData()->getABITypeAlignment(I->getType());
3365 // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3366 // that is zero extended!
3367 if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
3368 Flags &= ~(ISD::ParamFlags::SExt);
3369 if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
3370 Flags |= ISD::ParamFlags::SExt;
3371 if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
3372 Flags |= ISD::ParamFlags::InReg;
3373 if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
3374 Flags |= ISD::ParamFlags::StructReturn;
3375 Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3377 switch (getTypeAction(VT)) {
3378 default: assert(0 && "Unknown type action!");
3380 RetVals.push_back(VT);
3381 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3384 RetVals.push_back(getTypeToTransformTo(VT));
3385 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3388 if (VT != MVT::Vector) {
3389 // If this is a large integer, it needs to be broken up into small
3390 // integers. Figure out what the destination type is and how many small
3391 // integers it turns into.
3392 MVT::ValueType NVT = getTypeToExpandTo(VT);
3393 unsigned NumVals = getNumElements(VT);
3394 for (unsigned i = 0; i != NumVals; ++i) {
3395 RetVals.push_back(NVT);
3396 // if it isn't first piece, alignment must be 1
3398 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3399 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3400 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3403 // Otherwise, this is a vector type. We only support legal vectors
3405 unsigned NumElems = cast<VectorType>(I->getType())->getNumElements();
3406 const Type *EltTy = cast<VectorType>(I->getType())->getElementType();
3408 // Figure out if there is a Packed type corresponding to this Vector
3409 // type. If so, convert to the vector type.
3410 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3411 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3412 RetVals.push_back(TVT);
3413 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3415 assert(0 && "Don't support illegal by-val vector arguments yet!");
3422 RetVals.push_back(MVT::Other);
3425 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3426 DAG.getNodeValueTypes(RetVals), RetVals.size(),
3427 &Ops[0], Ops.size()).Val;
3429 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
3431 // Set up the return result vector.
3435 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
3437 MVT::ValueType VT = getValueType(I->getType());
3439 switch (getTypeAction(VT)) {
3440 default: assert(0 && "Unknown type action!");
3442 Ops.push_back(SDOperand(Result, i++));
3445 SDOperand Op(Result, i++);
3446 if (MVT::isInteger(VT)) {
3447 if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
3448 Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3449 DAG.getValueType(VT));
3450 else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
3451 Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3452 DAG.getValueType(VT));
3453 Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3455 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3456 Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
3462 if (VT != MVT::Vector) {
3463 // If this is a large integer or a floating point node that needs to be
3464 // expanded, it needs to be reassembled from small integers. Figure out
3465 // what the source elt type is and how many small integers it is.
3466 Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
3468 // Otherwise, this is a vector type. We only support legal vectors
3470 const VectorType *PTy = cast<VectorType>(I->getType());
3471 unsigned NumElems = PTy->getNumElements();
3472 const Type *EltTy = PTy->getElementType();
3474 // Figure out if there is a Packed type corresponding to this Vector
3475 // type. If so, convert to the vector type.
3476 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3477 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3478 SDOperand N = SDOperand(Result, i++);
3479 // Handle copies from generic vectors to registers.
3480 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
3481 DAG.getConstant(NumElems, MVT::i32),
3482 DAG.getValueType(getValueType(EltTy)));
3485 assert(0 && "Don't support illegal by-val vector arguments yet!");
3496 /// ExpandScalarCallArgs - Recursively expand call argument node by
3497 /// bit_converting it or extract a pair of elements from the larger node.
3498 static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
3500 SmallVector<SDOperand, 32> &Ops,
3502 TargetLowering &TLI,
3503 bool isFirst = true) {
3505 if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
3506 // if it isn't first piece, alignment must be 1
3508 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3509 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3511 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3515 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3516 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3518 Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
3519 ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI, isFirst);
3520 } else if (NumVals == 2) {
3521 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3522 DAG.getConstant(0, TLI.getPointerTy()));
3523 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3524 DAG.getConstant(1, TLI.getPointerTy()));
3525 if (!TLI.isLittleEndian())
3527 ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI, isFirst);
3528 ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI, false);
3530 // Value scalarized into many values. Unimp for now.
3531 assert(0 && "Cannot expand i64 -> i16 yet!");
3535 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
3536 /// implementation, which just inserts an ISD::CALL node, which is later custom
3537 /// lowered by the target to something concrete. FIXME: When all targets are
3538 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
3539 std::pair<SDOperand, SDOperand>
3540 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
3541 bool RetTyIsSigned, bool isVarArg,
3542 unsigned CallingConv, bool isTailCall,
3544 ArgListTy &Args, SelectionDAG &DAG) {
3545 SmallVector<SDOperand, 32> Ops;
3546 Ops.push_back(Chain); // Op#0 - Chain
3547 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
3548 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg
3549 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail
3550 Ops.push_back(Callee);
3552 // Handle all of the outgoing arguments.
3553 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
3554 MVT::ValueType VT = getValueType(Args[i].Ty);
3555 SDOperand Op = Args[i].Node;
3556 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3557 unsigned OriginalAlignment =
3558 getTargetData()->getABITypeAlignment(Args[i].Ty);
3561 Flags |= ISD::ParamFlags::SExt;
3563 Flags |= ISD::ParamFlags::ZExt;
3564 if (Args[i].isInReg)
3565 Flags |= ISD::ParamFlags::InReg;
3567 Flags |= ISD::ParamFlags::StructReturn;
3568 Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
3570 switch (getTypeAction(VT)) {
3571 default: assert(0 && "Unknown type action!");
3574 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3577 if (MVT::isInteger(VT)) {
3580 ExtOp = ISD::SIGN_EXTEND;
3581 else if (Args[i].isZExt)
3582 ExtOp = ISD::ZERO_EXTEND;
3584 ExtOp = ISD::ANY_EXTEND;
3585 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
3587 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3588 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
3591 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3594 if (VT != MVT::Vector) {
3595 // If this is a large integer, it needs to be broken down into small
3596 // integers. Figure out what the source elt type is and how many small
3598 ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
3600 // Otherwise, this is a vector type. We only support legal vectors
3602 const VectorType *PTy = cast<VectorType>(Args[i].Ty);
3603 unsigned NumElems = PTy->getNumElements();
3604 const Type *EltTy = PTy->getElementType();
3606 // Figure out if there is a Packed type corresponding to this Vector
3607 // type. If so, convert to the vector type.
3608 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3609 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3610 // Insert a VBIT_CONVERT of the MVT::Vector type to the vector type.
3611 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
3613 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3615 assert(0 && "Don't support illegal by-val vector call args yet!");
3623 // Figure out the result value types.
3624 SmallVector<MVT::ValueType, 4> RetTys;
3626 if (RetTy != Type::VoidTy) {
3627 MVT::ValueType VT = getValueType(RetTy);
3628 switch (getTypeAction(VT)) {
3629 default: assert(0 && "Unknown type action!");
3631 RetTys.push_back(VT);
3634 RetTys.push_back(getTypeToTransformTo(VT));
3637 if (VT != MVT::Vector) {
3638 // If this is a large integer, it needs to be reassembled from small
3639 // integers. Figure out what the source elt type is and how many small
3641 MVT::ValueType NVT = getTypeToExpandTo(VT);
3642 unsigned NumVals = getNumElements(VT);
3643 for (unsigned i = 0; i != NumVals; ++i)
3644 RetTys.push_back(NVT);
3646 // Otherwise, this is a vector type. We only support legal vectors
3648 const VectorType *PTy = cast<VectorType>(RetTy);
3649 unsigned NumElems = PTy->getNumElements();
3650 const Type *EltTy = PTy->getElementType();
3652 // Figure out if there is a Packed type corresponding to this Vector
3653 // type. If so, convert to the vector type.
3654 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3655 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3656 RetTys.push_back(TVT);
3658 assert(0 && "Don't support illegal by-val vector call results yet!");
3665 RetTys.push_back(MVT::Other); // Always has a chain.
3667 // Finally, create the CALL node.
3668 SDOperand Res = DAG.getNode(ISD::CALL,
3669 DAG.getVTList(&RetTys[0], RetTys.size()),
3670 &Ops[0], Ops.size());
3672 // This returns a pair of operands. The first element is the
3673 // return value for the function (if RetTy is not VoidTy). The second
3674 // element is the outgoing token chain.
3676 if (RetTys.size() != 1) {
3677 MVT::ValueType VT = getValueType(RetTy);
3678 if (RetTys.size() == 2) {
3681 // If this value was promoted, truncate it down.
3682 if (ResVal.getValueType() != VT) {
3683 if (VT == MVT::Vector) {
3684 // Insert a VBIT_CONVERT to convert from the packed result type to the
3685 // MVT::Vector type.
3686 unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
3687 const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
3689 // Figure out if there is a Packed type corresponding to this Vector
3690 // type. If so, convert to the vector type.
3691 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
3692 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3693 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
3694 // "N x PTyElementVT" MVT::Vector type.
3695 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
3696 DAG.getConstant(NumElems, MVT::i32),
3697 DAG.getValueType(getValueType(EltTy)));
3701 } else if (MVT::isInteger(VT)) {
3702 unsigned AssertOp = ISD::AssertSext;
3704 AssertOp = ISD::AssertZext;
3705 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
3706 DAG.getValueType(VT));
3707 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
3709 assert(MVT::isFloatingPoint(VT));
3710 if (getTypeAction(VT) == Expand)
3711 ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
3713 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
3716 } else if (RetTys.size() == 3) {
3717 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
3718 Res.getValue(0), Res.getValue(1));
3721 assert(0 && "Case not handled yet!");
3725 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
3728 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
3729 assert(0 && "LowerOperation not implemented for this target!");
3734 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
3735 SelectionDAG &DAG) {
3736 assert(0 && "CustomPromoteOperation not implemented for this target!");
3741 /// getMemsetValue - Vectorized representation of the memset value
3743 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
3744 SelectionDAG &DAG) {
3745 MVT::ValueType CurVT = VT;
3746 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3747 uint64_t Val = C->getValue() & 255;
3749 while (CurVT != MVT::i8) {
3750 Val = (Val << Shift) | Val;
3752 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3754 return DAG.getConstant(Val, VT);
3756 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
3758 while (CurVT != MVT::i8) {
3760 DAG.getNode(ISD::OR, VT,
3761 DAG.getNode(ISD::SHL, VT, Value,
3762 DAG.getConstant(Shift, MVT::i8)), Value);
3764 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3771 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3772 /// used when a memcpy is turned into a memset when the source is a constant
3774 static SDOperand getMemsetStringVal(MVT::ValueType VT,
3775 SelectionDAG &DAG, TargetLowering &TLI,
3776 std::string &Str, unsigned Offset) {
3778 unsigned MSB = getSizeInBits(VT) / 8;
3779 if (TLI.isLittleEndian())
3780 Offset = Offset + MSB - 1;
3781 for (unsigned i = 0; i != MSB; ++i) {
3782 Val = (Val << 8) | (unsigned char)Str[Offset];
3783 Offset += TLI.isLittleEndian() ? -1 : 1;
3785 return DAG.getConstant(Val, VT);
3788 /// getMemBasePlusOffset - Returns base and offset node for the
3789 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
3790 SelectionDAG &DAG, TargetLowering &TLI) {
3791 MVT::ValueType VT = Base.getValueType();
3792 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
3795 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
3796 /// to replace the memset / memcpy is below the threshold. It also returns the
3797 /// types of the sequence of memory ops to perform memset / memcpy.
3798 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
3799 unsigned Limit, uint64_t Size,
3800 unsigned Align, TargetLowering &TLI) {
3803 if (TLI.allowsUnalignedMemoryAccesses()) {
3806 switch (Align & 7) {
3822 MVT::ValueType LVT = MVT::i64;
3823 while (!TLI.isTypeLegal(LVT))
3824 LVT = (MVT::ValueType)((unsigned)LVT - 1);
3825 assert(MVT::isInteger(LVT));
3830 unsigned NumMemOps = 0;
3832 unsigned VTSize = getSizeInBits(VT) / 8;
3833 while (VTSize > Size) {
3834 VT = (MVT::ValueType)((unsigned)VT - 1);
3837 assert(MVT::isInteger(VT));
3839 if (++NumMemOps > Limit)
3841 MemOps.push_back(VT);
3848 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
3849 SDOperand Op1 = getValue(I.getOperand(1));
3850 SDOperand Op2 = getValue(I.getOperand(2));
3851 SDOperand Op3 = getValue(I.getOperand(3));
3852 SDOperand Op4 = getValue(I.getOperand(4));
3853 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
3854 if (Align == 0) Align = 1;
3856 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
3857 std::vector<MVT::ValueType> MemOps;
3859 // Expand memset / memcpy to a series of load / store ops
3860 // if the size operand falls below a certain threshold.
3861 SmallVector<SDOperand, 8> OutChains;
3863 default: break; // Do nothing for now.
3865 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
3866 Size->getValue(), Align, TLI)) {
3867 unsigned NumMemOps = MemOps.size();
3868 unsigned Offset = 0;
3869 for (unsigned i = 0; i < NumMemOps; i++) {
3870 MVT::ValueType VT = MemOps[i];
3871 unsigned VTSize = getSizeInBits(VT) / 8;
3872 SDOperand Value = getMemsetValue(Op2, VT, DAG);
3873 SDOperand Store = DAG.getStore(getRoot(), Value,
3874 getMemBasePlusOffset(Op1, Offset, DAG, TLI),
3875 I.getOperand(1), Offset);
3876 OutChains.push_back(Store);
3883 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
3884 Size->getValue(), Align, TLI)) {
3885 unsigned NumMemOps = MemOps.size();
3886 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
3887 GlobalAddressSDNode *G = NULL;
3889 bool CopyFromStr = false;
3891 if (Op2.getOpcode() == ISD::GlobalAddress)
3892 G = cast<GlobalAddressSDNode>(Op2);
3893 else if (Op2.getOpcode() == ISD::ADD &&
3894 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3895 Op2.getOperand(1).getOpcode() == ISD::Constant) {
3896 G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
3897 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
3900 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3901 if (GV && GV->isConstant()) {
3902 Str = GV->getStringValue(false);
3910 for (unsigned i = 0; i < NumMemOps; i++) {
3911 MVT::ValueType VT = MemOps[i];
3912 unsigned VTSize = getSizeInBits(VT) / 8;
3913 SDOperand Value, Chain, Store;
3916 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
3919 DAG.getStore(Chain, Value,
3920 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3921 I.getOperand(1), DstOff);
3923 Value = DAG.getLoad(VT, getRoot(),
3924 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
3925 I.getOperand(2), SrcOff);
3926 Chain = Value.getValue(1);
3928 DAG.getStore(Chain, Value,
3929 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3930 I.getOperand(1), DstOff);
3932 OutChains.push_back(Store);
3941 if (!OutChains.empty()) {
3942 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
3943 &OutChains[0], OutChains.size()));
3948 DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
3951 //===----------------------------------------------------------------------===//
3952 // SelectionDAGISel code
3953 //===----------------------------------------------------------------------===//
3955 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
3956 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
3959 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
3960 AU.addRequired<AliasAnalysis>();
3961 AU.setPreservesAll();
3966 bool SelectionDAGISel::runOnFunction(Function &Fn) {
3967 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
3968 RegMap = MF.getSSARegMap();
3969 DOUT << "\n\n\n=== " << Fn.getName() << "\n";
3971 FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
3973 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
3974 SelectBasicBlock(I, MF, FuncInfo);
3976 // Add function live-ins to entry block live-in set.
3977 BasicBlock *EntryBB = &Fn.getEntryBlock();
3978 BB = FuncInfo.MBBMap[EntryBB];
3979 if (!MF.livein_empty())
3980 for (MachineFunction::livein_iterator I = MF.livein_begin(),
3981 E = MF.livein_end(); I != E; ++I)
3982 BB->addLiveIn(I->first);
3987 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V,
3989 SDOperand Op = getValue(V);
3990 assert((Op.getOpcode() != ISD::CopyFromReg ||
3991 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
3992 "Copy from a reg to the same reg!");
3994 // If this type is not legal, we must make sure to not create an invalid
3996 MVT::ValueType SrcVT = Op.getValueType();
3997 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
3998 if (SrcVT == DestVT) {
3999 return DAG.getCopyToReg(getRoot(), Reg, Op);
4000 } else if (SrcVT == MVT::Vector) {
4001 // Handle copies from generic vectors to registers.
4002 MVT::ValueType PTyElementVT, PTyLegalElementVT;
4003 unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
4004 PTyElementVT, PTyLegalElementVT);
4006 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
4007 // MVT::Vector type.
4008 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
4009 DAG.getConstant(NE, MVT::i32),
4010 DAG.getValueType(PTyElementVT));
4012 // Loop over all of the elements of the resultant vector,
4013 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
4014 // copying them into output registers.
4015 SmallVector<SDOperand, 8> OutChains;
4016 SDOperand Root = getRoot();
4017 for (unsigned i = 0; i != NE; ++i) {
4018 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
4019 Op, DAG.getConstant(i, TLI.getPointerTy()));
4020 if (PTyElementVT == PTyLegalElementVT) {
4021 // Elements are legal.
4022 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4023 } else if (PTyLegalElementVT > PTyElementVT) {
4024 // Elements are promoted.
4025 if (MVT::isFloatingPoint(PTyLegalElementVT))
4026 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
4028 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
4029 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4031 // Elements are expanded.
4032 // The src value is expanded into multiple registers.
4033 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4034 Elt, DAG.getConstant(0, TLI.getPointerTy()));
4035 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4036 Elt, DAG.getConstant(1, TLI.getPointerTy()));
4037 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
4038 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
4041 return DAG.getNode(ISD::TokenFactor, MVT::Other,
4042 &OutChains[0], OutChains.size());
4043 } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
4044 // The src value is promoted to the register.
4045 if (MVT::isFloatingPoint(SrcVT))
4046 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
4048 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
4049 return DAG.getCopyToReg(getRoot(), Reg, Op);
4051 DestVT = TLI.getTypeToExpandTo(SrcVT);
4052 unsigned NumVals = TLI.getNumElements(SrcVT);
4054 return DAG.getCopyToReg(getRoot(), Reg,
4055 DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
4056 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
4057 // The src value is expanded into multiple registers.
4058 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4059 Op, DAG.getConstant(0, TLI.getPointerTy()));
4060 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4061 Op, DAG.getConstant(1, TLI.getPointerTy()));
4062 Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
4063 return DAG.getCopyToReg(Op, Reg+1, Hi);
4067 void SelectionDAGISel::
4068 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
4069 std::vector<SDOperand> &UnorderedChains) {
4070 // If this is the entry block, emit arguments.
4071 Function &F = *LLVMBB->getParent();
4072 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4073 SDOperand OldRoot = SDL.DAG.getRoot();
4074 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
4077 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4079 if (!AI->use_empty()) {
4080 SDL.setValue(AI, Args[a]);
4082 // If this argument is live outside of the entry block, insert a copy from
4083 // whereever we got it to the vreg that other BB's will reference it as.
4084 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4085 if (VMI != FuncInfo.ValueMap.end()) {
4086 SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
4087 UnorderedChains.push_back(Copy);
4091 // Finally, if the target has anything special to do, allow it to do so.
4092 // FIXME: this should insert code into the DAG!
4093 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4096 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
4097 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
4098 FunctionLoweringInfo &FuncInfo) {
4099 SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
4101 std::vector<SDOperand> UnorderedChains;
4103 // Lower any arguments needed in this block if this is the entry block.
4104 if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
4105 LowerArguments(LLVMBB, SDL, UnorderedChains);
4107 BB = FuncInfo.MBBMap[LLVMBB];
4108 SDL.setCurrentBasicBlock(BB);
4110 // Lower all of the non-terminator instructions.
4111 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
4115 // Lower call part of invoke.
4116 InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
4117 if (Invoke) SDL.visitInvoke(*Invoke, false);
4119 // Ensure that all instructions which are used outside of their defining
4120 // blocks are available as virtual registers.
4121 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
4122 if (!I->use_empty() && !isa<PHINode>(I)) {
4123 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4124 if (VMI != FuncInfo.ValueMap.end())
4125 UnorderedChains.push_back(
4126 SDL.CopyValueToVirtualRegister(I, VMI->second));
4129 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to
4130 // ensure constants are generated when needed. Remember the virtual registers
4131 // that need to be added to the Machine PHI nodes as input. We cannot just
4132 // directly add them, because expansion might result in multiple MBB's for one
4133 // BB. As such, the start of the BB might correspond to a different MBB than
4136 TerminatorInst *TI = LLVMBB->getTerminator();
4138 // Emit constants only once even if used by multiple PHI nodes.
4139 std::map<Constant*, unsigned> ConstantsOut;
4141 // Vector bool would be better, but vector<bool> is really slow.
4142 std::vector<unsigned char> SuccsHandled;
4143 if (TI->getNumSuccessors())
4144 SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4146 // Check successor nodes PHI nodes that expect a constant to be available from
4148 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4149 BasicBlock *SuccBB = TI->getSuccessor(succ);
4150 if (!isa<PHINode>(SuccBB->begin())) continue;
4151 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4153 // If this terminator has multiple identical successors (common for
4154 // switches), only handle each succ once.
4155 unsigned SuccMBBNo = SuccMBB->getNumber();
4156 if (SuccsHandled[SuccMBBNo]) continue;
4157 SuccsHandled[SuccMBBNo] = true;
4159 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4162 // At this point we know that there is a 1-1 correspondence between LLVM PHI
4163 // nodes and Machine PHI nodes, but the incoming operands have not been
4165 for (BasicBlock::iterator I = SuccBB->begin();
4166 (PN = dyn_cast<PHINode>(I)); ++I) {
4167 // Ignore dead phi's.
4168 if (PN->use_empty()) continue;
4171 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4173 if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4174 unsigned &RegOut = ConstantsOut[C];
4176 RegOut = FuncInfo.CreateRegForValue(C);
4177 UnorderedChains.push_back(
4178 SDL.CopyValueToVirtualRegister(C, RegOut));
4182 Reg = FuncInfo.ValueMap[PHIOp];
4184 assert(isa<AllocaInst>(PHIOp) &&
4185 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4186 "Didn't codegen value into a register!??");
4187 Reg = FuncInfo.CreateRegForValue(PHIOp);
4188 UnorderedChains.push_back(
4189 SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4193 // Remember that this register needs to added to the machine PHI node as
4194 // the input for this MBB.
4195 MVT::ValueType VT = TLI.getValueType(PN->getType());
4196 unsigned NumElements;
4197 if (VT != MVT::Vector)
4198 NumElements = TLI.getNumElements(VT);
4200 MVT::ValueType VT1,VT2;
4202 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
4205 for (unsigned i = 0, e = NumElements; i != e; ++i)
4206 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4209 ConstantsOut.clear();
4211 // Turn all of the unordered chains into one factored node.
4212 if (!UnorderedChains.empty()) {
4213 SDOperand Root = SDL.getRoot();
4214 if (Root.getOpcode() != ISD::EntryToken) {
4215 unsigned i = 0, e = UnorderedChains.size();
4216 for (; i != e; ++i) {
4217 assert(UnorderedChains[i].Val->getNumOperands() > 1);
4218 if (UnorderedChains[i].Val->getOperand(0) == Root)
4219 break; // Don't add the root if we already indirectly depend on it.
4223 UnorderedChains.push_back(Root);
4225 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4226 &UnorderedChains[0], UnorderedChains.size()));
4229 // Lower the terminator after the copies are emitted.
4231 // Just the branch part of invoke.
4232 SDL.visitInvoke(*Invoke, true);
4234 SDL.visit(*LLVMBB->getTerminator());
4237 // Copy over any CaseBlock records that may now exist due to SwitchInst
4238 // lowering, as well as any jump table information.
4239 SwitchCases.clear();
4240 SwitchCases = SDL.SwitchCases;
4242 JTCases = SDL.JTCases;
4244 // Make sure the root of the DAG is up-to-date.
4245 DAG.setRoot(SDL.getRoot());
4248 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4249 // Get alias analysis for load/store combining.
4250 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
4252 // Run the DAG combiner in pre-legalize mode.
4253 DAG.Combine(false, AA);
4255 DOUT << "Lowered selection DAG:\n";
4258 // Second step, hack on the DAG until it only uses operations and types that
4259 // the target supports.
4262 DOUT << "Legalized selection DAG:\n";
4265 // Run the DAG combiner in post-legalize mode.
4266 DAG.Combine(true, AA);
4268 if (ViewISelDAGs) DAG.viewGraph();
4270 // Third, instruction select all of the operations to machine code, adding the
4271 // code to the MachineBasicBlock.
4272 InstructionSelectBasicBlock(DAG);
4274 DOUT << "Selected machine code:\n";
4278 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4279 FunctionLoweringInfo &FuncInfo) {
4280 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4282 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4285 // First step, lower LLVM code to some DAG. This DAG may use operations and
4286 // types that are not supported by the target.
4287 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4289 // Second step, emit the lowered DAG as machine code.
4290 CodeGenAndEmitDAG(DAG);
4293 // Next, now that we know what the last MBB the LLVM BB expanded is, update
4294 // PHI nodes in successors.
4295 if (SwitchCases.empty() && JTCases.empty()) {
4296 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4297 MachineInstr *PHI = PHINodesToUpdate[i].first;
4298 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4299 "This is not a machine PHI node that we are updating!");
4300 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4301 PHI->addMachineBasicBlockOperand(BB);
4306 // If the JumpTable record is filled in, then we need to emit a jump table.
4307 // Updating the PHI nodes is tricky in this case, since we need to determine
4308 // whether the PHI is a successor of the range check MBB or the jump table MBB
4309 for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
4310 // Lower header first, if it wasn't already lowered
4311 if (!JTCases[i].first.Emitted) {
4312 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4314 SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
4315 // Set the current basic block to the mbb we wish to insert the code into
4316 BB = JTCases[i].first.HeaderBB;
4317 HSDL.setCurrentBasicBlock(BB);
4319 HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
4320 HSDAG.setRoot(HSDL.getRoot());
4321 CodeGenAndEmitDAG(HSDAG);
4324 SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4326 SelectionDAGLowering JSDL(JSDAG, TLI, FuncInfo);
4327 // Set the current basic block to the mbb we wish to insert the code into
4328 BB = JTCases[i].second.MBB;
4329 JSDL.setCurrentBasicBlock(BB);
4331 JSDL.visitJumpTable(JTCases[i].second);
4332 JSDAG.setRoot(JSDL.getRoot());
4333 CodeGenAndEmitDAG(JSDAG);
4336 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4337 MachineInstr *PHI = PHINodesToUpdate[pi].first;
4338 MachineBasicBlock *PHIBB = PHI->getParent();
4339 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4340 "This is not a machine PHI node that we are updating!");
4341 if (PHIBB == JTCases[i].second.Default) {
4342 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4343 PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
4345 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4346 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4347 PHI->addMachineBasicBlockOperand(BB);
4352 // If the switch block involved a branch to one of the actual successors, we
4353 // need to update PHI nodes in that block.
4354 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4355 MachineInstr *PHI = PHINodesToUpdate[i].first;
4356 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4357 "This is not a machine PHI node that we are updating!");
4358 if (BB->isSuccessor(PHI->getParent())) {
4359 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4360 PHI->addMachineBasicBlockOperand(BB);
4364 // If we generated any switch lowering information, build and codegen any
4365 // additional DAGs necessary.
4366 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4367 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4369 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4371 // Set the current basic block to the mbb we wish to insert the code into
4372 BB = SwitchCases[i].ThisBB;
4373 SDL.setCurrentBasicBlock(BB);
4376 SDL.visitSwitchCase(SwitchCases[i]);
4377 SDAG.setRoot(SDL.getRoot());
4378 CodeGenAndEmitDAG(SDAG);
4380 // Handle any PHI nodes in successors of this chunk, as if we were coming
4381 // from the original BB before switch expansion. Note that PHI nodes can
4382 // occur multiple times in PHINodesToUpdate. We have to be very careful to
4383 // handle them the right number of times.
4384 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS.
4385 for (MachineBasicBlock::iterator Phi = BB->begin();
4386 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4387 // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4388 for (unsigned pn = 0; ; ++pn) {
4389 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4390 if (PHINodesToUpdate[pn].first == Phi) {
4391 Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4392 Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4398 // Don't process RHS if same block as LHS.
4399 if (BB == SwitchCases[i].FalseBB)
4400 SwitchCases[i].FalseBB = 0;
4402 // If we haven't handled the RHS, do so now. Otherwise, we're done.
4403 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4404 SwitchCases[i].FalseBB = 0;
4406 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4411 //===----------------------------------------------------------------------===//
4412 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4413 /// target node in the graph.
4414 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4415 if (ViewSchedDAGs) DAG.viewGraph();
4417 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4421 RegisterScheduler::setDefault(Ctor);
4424 ScheduleDAG *SL = Ctor(this, &DAG, BB);
4430 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4431 return new HazardRecognizer();
4434 //===----------------------------------------------------------------------===//
4435 // Helper functions used by the generated instruction selector.
4436 //===----------------------------------------------------------------------===//
4437 // Calls to these methods are generated by tblgen.
4439 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
4440 /// the dag combiner simplified the 255, we still want to match. RHS is the
4441 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
4442 /// specified in the .td file (e.g. 255).
4443 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
4444 int64_t DesiredMaskS) {
4445 uint64_t ActualMask = RHS->getValue();
4446 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4448 // If the actual mask exactly matches, success!
4449 if (ActualMask == DesiredMask)
4452 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4453 if (ActualMask & ~DesiredMask)
4456 // Otherwise, the DAG Combiner may have proven that the value coming in is
4457 // either already zero or is not demanded. Check for known zero input bits.
4458 uint64_t NeededMask = DesiredMask & ~ActualMask;
4459 if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
4462 // TODO: check to see if missing bits are just not demanded.
4464 // Otherwise, this pattern doesn't match.
4468 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
4469 /// the dag combiner simplified the 255, we still want to match. RHS is the
4470 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
4471 /// specified in the .td file (e.g. 255).
4472 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
4473 int64_t DesiredMaskS) {
4474 uint64_t ActualMask = RHS->getValue();
4475 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4477 // If the actual mask exactly matches, success!
4478 if (ActualMask == DesiredMask)
4481 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4482 if (ActualMask & ~DesiredMask)
4485 // Otherwise, the DAG Combiner may have proven that the value coming in is
4486 // either already zero or is not demanded. Check for known zero input bits.
4487 uint64_t NeededMask = DesiredMask & ~ActualMask;
4489 uint64_t KnownZero, KnownOne;
4490 getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
4492 // If all the missing bits in the or are already known to be set, match!
4493 if ((NeededMask & KnownOne) == NeededMask)
4496 // TODO: check to see if missing bits are just not demanded.
4498 // Otherwise, this pattern doesn't match.
4503 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
4504 /// by tblgen. Others should not call it.
4505 void SelectionDAGISel::
4506 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
4507 std::vector<SDOperand> InOps;
4508 std::swap(InOps, Ops);
4510 Ops.push_back(InOps[0]); // input chain.
4511 Ops.push_back(InOps[1]); // input asm string.
4513 unsigned i = 2, e = InOps.size();
4514 if (InOps[e-1].getValueType() == MVT::Flag)
4515 --e; // Don't process a flag operand if it is here.
4518 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
4519 if ((Flags & 7) != 4 /*MEM*/) {
4520 // Just skip over this operand, copying the operands verbatim.
4521 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
4522 i += (Flags >> 3) + 1;
4524 assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
4525 // Otherwise, this is a memory operand. Ask the target to select it.
4526 std::vector<SDOperand> SelOps;
4527 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
4528 cerr << "Could not match memory address. Inline asm failure!\n";
4532 // Add this to the output node.
4533 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
4534 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
4536 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
4541 // Add the flag input back if present.
4542 if (e != InOps.size())
4543 Ops.push_back(InOps.back());