1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAGISel class.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "isel"
15 #include "llvm/Analysis/AliasAnalysis.h"
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/CodeGen/SelectionDAGISel.h"
18 #include "llvm/CodeGen/ScheduleDAG.h"
19 #include "llvm/CallingConv.h"
20 #include "llvm/Constants.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/TargetAsmInfo.h"
38 #include "llvm/Target/TargetData.h"
39 #include "llvm/Target/TargetFrameInfo.h"
40 #include "llvm/Target/TargetInstrInfo.h"
41 #include "llvm/Target/TargetLowering.h"
42 #include "llvm/Target/TargetMachine.h"
43 #include "llvm/Target/TargetOptions.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Support/MathExtras.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/Compiler.h"
53 ViewISelDAGs("view-isel-dags", cl::Hidden,
54 cl::desc("Pop up a window to show isel dags as they are selected"));
56 ViewSchedDAGs("view-sched-dags", cl::Hidden,
57 cl::desc("Pop up a window to show sched dags as they are processed"));
59 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
63 EnableGEPIndexSink("enable-gep-index-sinking", cl::Hidden,
64 cl::desc("Sink invariant GEP index computation into use blocks"));
66 //===---------------------------------------------------------------------===//
68 /// RegisterScheduler class - Track the registration of instruction schedulers.
70 //===---------------------------------------------------------------------===//
71 MachinePassRegistry RegisterScheduler::Registry;
73 //===---------------------------------------------------------------------===//
75 /// ISHeuristic command line option for instruction schedulers.
77 //===---------------------------------------------------------------------===//
79 cl::opt<RegisterScheduler::FunctionPassCtor, false,
80 RegisterPassParser<RegisterScheduler> >
82 cl::init(&createDefaultScheduler),
83 cl::desc("Instruction schedulers available:"));
85 static RegisterScheduler
86 defaultListDAGScheduler("default", " Best scheduler for the target",
87 createDefaultScheduler);
91 /// RegsForValue - This struct represents the physical registers that a
92 /// particular value is assigned and the type information about the value.
93 /// This is needed because values can be promoted into larger registers and
94 /// expanded into multiple smaller registers than the value.
95 struct VISIBILITY_HIDDEN RegsForValue {
96 /// Regs - This list hold the register (for legal and promoted values)
97 /// or register set (for expanded values) that the value should be assigned
99 std::vector<unsigned> Regs;
101 /// RegVT - The value type of each register.
103 MVT::ValueType RegVT;
105 /// ValueVT - The value type of the LLVM value, which may be promoted from
106 /// RegVT or made from merging the two expanded parts.
107 MVT::ValueType ValueVT;
109 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {}
111 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt)
112 : RegVT(regvt), ValueVT(valuevt) {
115 RegsForValue(const std::vector<unsigned> ®s,
116 MVT::ValueType regvt, MVT::ValueType valuevt)
117 : Regs(regs), RegVT(regvt), ValueVT(valuevt) {
120 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
121 /// this value and returns the result as a ValueVT value. This uses
122 /// Chain/Flag as the input and updates them for the output Chain/Flag.
123 SDOperand getCopyFromRegs(SelectionDAG &DAG,
124 SDOperand &Chain, SDOperand &Flag) const;
126 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
127 /// specified value into the registers specified by this object. This uses
128 /// Chain/Flag as the input and updates them for the output Chain/Flag.
129 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
130 SDOperand &Chain, SDOperand &Flag,
131 MVT::ValueType PtrVT) const;
133 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
134 /// operand list. This adds the code marker and includes the number of
135 /// values added into it.
136 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
137 std::vector<SDOperand> &Ops) const;
142 //===--------------------------------------------------------------------===//
143 /// createDefaultScheduler - This creates an instruction scheduler appropriate
145 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
147 MachineBasicBlock *BB) {
148 TargetLowering &TLI = IS->getTargetLowering();
150 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
151 return createTDListDAGScheduler(IS, DAG, BB);
153 assert(TLI.getSchedulingPreference() ==
154 TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
155 return createBURRListDAGScheduler(IS, DAG, BB);
160 //===--------------------------------------------------------------------===//
161 /// FunctionLoweringInfo - This contains information that is global to a
162 /// function that is used when lowering a region of the function.
163 class FunctionLoweringInfo {
170 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
172 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
173 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
175 /// ValueMap - Since we emit code for the function a basic block at a time,
176 /// we must remember which virtual registers hold the values for
177 /// cross-basic-block values.
178 DenseMap<const Value*, unsigned> ValueMap;
180 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
181 /// the entry block. This allows the allocas to be efficiently referenced
182 /// anywhere in the function.
183 std::map<const AllocaInst*, int> StaticAllocaMap;
185 unsigned MakeReg(MVT::ValueType VT) {
186 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
189 /// isExportedInst - Return true if the specified value is an instruction
190 /// exported from its block.
191 bool isExportedInst(const Value *V) {
192 return ValueMap.count(V);
195 unsigned CreateRegForValue(const Value *V);
197 unsigned InitializeRegForValue(const Value *V) {
198 unsigned &R = ValueMap[V];
199 assert(R == 0 && "Already initialized this value register!");
200 return R = CreateRegForValue(V);
205 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
206 /// PHI nodes or outside of the basic block that defines it, or used by a
207 /// switch instruction, which may expand to multiple basic blocks.
208 static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
209 if (isa<PHINode>(I)) return true;
210 BasicBlock *BB = I->getParent();
211 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
212 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
213 // FIXME: Remove switchinst special case.
214 isa<SwitchInst>(*UI))
219 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the
220 /// entry block, return true. This includes arguments used by switches, since
221 /// the switch may expand into multiple basic blocks.
222 static bool isOnlyUsedInEntryBlock(Argument *A) {
223 BasicBlock *Entry = A->getParent()->begin();
224 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
225 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
226 return false; // Use not in entry block.
230 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
231 Function &fn, MachineFunction &mf)
232 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
234 // Create a vreg for each argument register that is not dead and is used
235 // outside of the entry block for the function.
236 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
238 if (!isOnlyUsedInEntryBlock(AI))
239 InitializeRegForValue(AI);
241 // Initialize the mapping of values to registers. This is only set up for
242 // instruction values that are used outside of the block that defines
244 Function::iterator BB = Fn.begin(), EB = Fn.end();
245 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
246 if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
247 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
248 const Type *Ty = AI->getAllocatedType();
249 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
251 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
254 TySize *= CUI->getZExtValue(); // Get total allocated size.
255 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
256 StaticAllocaMap[AI] =
257 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
260 for (; BB != EB; ++BB)
261 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
262 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
263 if (!isa<AllocaInst>(I) ||
264 !StaticAllocaMap.count(cast<AllocaInst>(I)))
265 InitializeRegForValue(I);
267 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This
268 // also creates the initial PHI MachineInstrs, though none of the input
269 // operands are populated.
270 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
271 MachineBasicBlock *MBB = new MachineBasicBlock(BB);
273 MF.getBasicBlockList().push_back(MBB);
275 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
278 for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
279 if (PN->use_empty()) continue;
281 MVT::ValueType VT = TLI.getValueType(PN->getType());
282 unsigned NumElements;
283 if (VT != MVT::Vector)
284 NumElements = TLI.getNumElements(VT);
286 MVT::ValueType VT1,VT2;
288 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
291 unsigned PHIReg = ValueMap[PN];
292 assert(PHIReg && "PHI node does not have an assigned virtual register!");
293 const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
294 for (unsigned i = 0; i != NumElements; ++i)
295 BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
300 /// CreateRegForValue - Allocate the appropriate number of virtual registers of
301 /// the correctly promoted or expanded types. Assign these registers
302 /// consecutive vreg numbers and return the first assigned number.
303 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
304 MVT::ValueType VT = TLI.getValueType(V->getType());
306 // The number of multiples of registers that we need, to, e.g., split up
307 // a <2 x int64> -> 4 x i32 registers.
308 unsigned NumVectorRegs = 1;
310 // If this is a vector type, figure out what type it will decompose into
311 // and how many of the elements it will use.
312 if (VT == MVT::Vector) {
313 const VectorType *PTy = cast<VectorType>(V->getType());
314 unsigned NumElts = PTy->getNumElements();
315 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
317 // Divide the input until we get to a supported size. This will always
318 // end with a scalar if the target doesn't support vectors.
319 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) {
326 VT = getVectorType(EltTy, NumElts);
329 // The common case is that we will only create one register for this
330 // value. If we have that case, create and return the virtual register.
331 unsigned NV = TLI.getNumElements(VT);
333 // If we are promoting this value, pick the next largest supported type.
334 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
335 unsigned Reg = MakeReg(PromotedType);
336 // If this is a vector of supported or promoted types (e.g. 4 x i16),
337 // create all of the registers.
338 for (unsigned i = 1; i != NumVectorRegs; ++i)
339 MakeReg(PromotedType);
343 // If this value is represented with multiple target registers, make sure
344 // to create enough consecutive registers of the right (smaller) type.
345 VT = TLI.getTypeToExpandTo(VT);
346 unsigned R = MakeReg(VT);
347 for (unsigned i = 1; i != NV*NumVectorRegs; ++i)
352 //===----------------------------------------------------------------------===//
353 /// SelectionDAGLowering - This is the common target-independent lowering
354 /// implementation that is parameterized by a TargetLowering object.
355 /// Also, targets can overload any lowering method.
358 class SelectionDAGLowering {
359 MachineBasicBlock *CurMBB;
361 DenseMap<const Value*, SDOperand> NodeMap;
363 /// PendingLoads - Loads are not emitted to the program immediately. We bunch
364 /// them up and then emit token factor nodes when possible. This allows us to
365 /// get simple disambiguation between loads without worrying about alias
367 std::vector<SDOperand> PendingLoads;
369 /// Case - A pair of values to record the Value for a switch case, and the
370 /// case's target basic block.
371 typedef std::pair<Constant*, MachineBasicBlock*> Case;
372 typedef std::vector<Case>::iterator CaseItr;
373 typedef std::pair<CaseItr, CaseItr> CaseRange;
375 /// CaseRec - A struct with ctor used in lowering switches to a binary tree
376 /// of conditional branches.
378 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) :
379 CaseBB(bb), LT(lt), GE(ge), Range(r) {}
381 /// CaseBB - The MBB in which to emit the compare and branch
382 MachineBasicBlock *CaseBB;
383 /// LT, GE - If nonzero, we know the current case value must be less-than or
384 /// greater-than-or-equal-to these Constants.
387 /// Range - A pair of iterators representing the range of case values to be
388 /// processed at this point in the binary search tree.
392 /// The comparison function for sorting Case values.
394 bool operator () (const Case& C1, const Case& C2) {
395 assert(isa<ConstantInt>(C1.first) && isa<ConstantInt>(C2.first));
396 return cast<const ConstantInt>(C1.first)->getSExtValue() <
397 cast<const ConstantInt>(C2.first)->getSExtValue();
402 // TLI - This is information that describes the available target features we
403 // need for lowering. This indicates when operations are unavailable,
404 // implemented with a libcall, etc.
407 const TargetData *TD;
409 /// SwitchCases - Vector of CaseBlock structures used to communicate
410 /// SwitchInst code generation information.
411 std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
412 SelectionDAGISel::JumpTable JT;
414 /// FuncInfo - Information about the function as a whole.
416 FunctionLoweringInfo &FuncInfo;
418 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
419 FunctionLoweringInfo &funcinfo)
420 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
421 JT(0,0,0,0), FuncInfo(funcinfo) {
424 /// getRoot - Return the current virtual root of the Selection DAG.
426 SDOperand getRoot() {
427 if (PendingLoads.empty())
428 return DAG.getRoot();
430 if (PendingLoads.size() == 1) {
431 SDOperand Root = PendingLoads[0];
433 PendingLoads.clear();
437 // Otherwise, we have to make a token factor node.
438 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
439 &PendingLoads[0], PendingLoads.size());
440 PendingLoads.clear();
445 SDOperand CopyValueToVirtualRegister(Value *V, unsigned Reg);
447 void visit(Instruction &I) { visit(I.getOpcode(), I); }
449 void visit(unsigned Opcode, User &I) {
450 // Note: this doesn't use InstVisitor, because it has to work with
451 // ConstantExpr's in addition to instructions.
453 default: assert(0 && "Unknown instruction type encountered!");
455 // Build the switch statement using the Instruction.def file.
456 #define HANDLE_INST(NUM, OPCODE, CLASS) \
457 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
458 #include "llvm/Instruction.def"
462 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
464 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr,
465 const Value *SV, SDOperand Root,
468 SDOperand getIntPtrConstant(uint64_t Val) {
469 return DAG.getConstant(Val, TLI.getPointerTy());
472 SDOperand getValue(const Value *V);
474 void setValue(const Value *V, SDOperand NewN) {
475 SDOperand &N = NodeMap[V];
476 assert(N.Val == 0 && "Already set a value for this node!");
480 RegsForValue GetRegistersForValue(const std::string &ConstrCode,
482 bool OutReg, bool InReg,
483 std::set<unsigned> &OutputRegs,
484 std::set<unsigned> &InputRegs);
486 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
487 MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
489 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
490 void ExportFromCurrentBlock(Value *V);
491 void LowerCallTo(Instruction &I,
492 const Type *CalledValueTy, unsigned CallingConv,
493 bool IsTailCall, SDOperand Callee, unsigned OpIdx);
495 // Terminator instructions.
496 void visitRet(ReturnInst &I);
497 void visitBr(BranchInst &I);
498 void visitSwitch(SwitchInst &I);
499 void visitUnreachable(UnreachableInst &I) { /* noop */ }
501 // Helper for visitSwitch
502 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
503 void visitJumpTable(SelectionDAGISel::JumpTable &JT);
505 // These all get lowered before this pass.
506 void visitInvoke(InvokeInst &I);
507 void visitInvoke(InvokeInst &I, bool AsTerminator);
508 void visitUnwind(UnwindInst &I);
510 void visitScalarBinary(User &I, unsigned OpCode);
511 void visitVectorBinary(User &I, unsigned OpCode);
512 void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp);
513 void visitShift(User &I, unsigned Opcode);
514 void visitAdd(User &I) {
515 if (isa<VectorType>(I.getType()))
516 visitVectorBinary(I, ISD::VADD);
517 else if (I.getType()->isFloatingPoint())
518 visitScalarBinary(I, ISD::FADD);
520 visitScalarBinary(I, ISD::ADD);
522 void visitSub(User &I);
523 void visitMul(User &I) {
524 if (isa<VectorType>(I.getType()))
525 visitVectorBinary(I, ISD::VMUL);
526 else if (I.getType()->isFloatingPoint())
527 visitScalarBinary(I, ISD::FMUL);
529 visitScalarBinary(I, ISD::MUL);
531 void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); }
532 void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); }
533 void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); }
534 void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); }
535 void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); }
536 void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); }
537 void visitAnd (User &I) { visitEitherBinary(I, ISD::AND, ISD::VAND ); }
538 void visitOr (User &I) { visitEitherBinary(I, ISD::OR, ISD::VOR ); }
539 void visitXor (User &I) { visitEitherBinary(I, ISD::XOR, ISD::VXOR ); }
540 void visitShl (User &I) { visitShift(I, ISD::SHL); }
541 void visitLShr(User &I) { visitShift(I, ISD::SRL); }
542 void visitAShr(User &I) { visitShift(I, ISD::SRA); }
543 void visitICmp(User &I);
544 void visitFCmp(User &I);
545 // Visit the conversion instructions
546 void visitTrunc(User &I);
547 void visitZExt(User &I);
548 void visitSExt(User &I);
549 void visitFPTrunc(User &I);
550 void visitFPExt(User &I);
551 void visitFPToUI(User &I);
552 void visitFPToSI(User &I);
553 void visitUIToFP(User &I);
554 void visitSIToFP(User &I);
555 void visitPtrToInt(User &I);
556 void visitIntToPtr(User &I);
557 void visitBitCast(User &I);
559 void visitExtractElement(User &I);
560 void visitInsertElement(User &I);
561 void visitShuffleVector(User &I);
563 void visitGetElementPtr(User &I);
564 void visitSelect(User &I);
566 void visitMalloc(MallocInst &I);
567 void visitFree(FreeInst &I);
568 void visitAlloca(AllocaInst &I);
569 void visitLoad(LoadInst &I);
570 void visitStore(StoreInst &I);
571 void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
572 void visitCall(CallInst &I);
573 void visitInlineAsm(CallInst &I);
574 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
575 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
577 void visitVAStart(CallInst &I);
578 void visitVAArg(VAArgInst &I);
579 void visitVAEnd(CallInst &I);
580 void visitVACopy(CallInst &I);
582 void visitMemIntrinsic(CallInst &I, unsigned Op);
584 void visitUserOp1(Instruction &I) {
585 assert(0 && "UserOp1 should not exist at instruction selection time!");
588 void visitUserOp2(Instruction &I) {
589 assert(0 && "UserOp2 should not exist at instruction selection time!");
593 } // end namespace llvm
595 SDOperand SelectionDAGLowering::getValue(const Value *V) {
596 SDOperand &N = NodeMap[V];
599 const Type *VTy = V->getType();
600 MVT::ValueType VT = TLI.getValueType(VTy);
601 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
602 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
603 visit(CE->getOpcode(), *CE);
604 SDOperand N1 = NodeMap[V];
605 assert(N1.Val && "visit didn't populate the ValueMap!");
607 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
608 return N = DAG.getGlobalAddress(GV, VT);
609 } else if (isa<ConstantPointerNull>(C)) {
610 return N = DAG.getConstant(0, TLI.getPointerTy());
611 } else if (isa<UndefValue>(C)) {
612 if (!isa<VectorType>(VTy))
613 return N = DAG.getNode(ISD::UNDEF, VT);
615 // Create a VBUILD_VECTOR of undef nodes.
616 const VectorType *PTy = cast<VectorType>(VTy);
617 unsigned NumElements = PTy->getNumElements();
618 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
620 SmallVector<SDOperand, 8> Ops;
621 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT));
623 // Create a VConstant node with generic Vector type.
624 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
625 Ops.push_back(DAG.getValueType(PVT));
626 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
627 &Ops[0], Ops.size());
628 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
629 return N = DAG.getConstantFP(CFP->getValue(), VT);
630 } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) {
631 unsigned NumElements = PTy->getNumElements();
632 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
634 // Now that we know the number and type of the elements, push a
635 // Constant or ConstantFP node onto the ops list for each element of
636 // the packed constant.
637 SmallVector<SDOperand, 8> Ops;
638 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
639 for (unsigned i = 0; i != NumElements; ++i)
640 Ops.push_back(getValue(CP->getOperand(i)));
642 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
644 if (MVT::isFloatingPoint(PVT))
645 Op = DAG.getConstantFP(0, PVT);
647 Op = DAG.getConstant(0, PVT);
648 Ops.assign(NumElements, Op);
651 // Create a VBUILD_VECTOR node with generic Vector type.
652 Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
653 Ops.push_back(DAG.getValueType(PVT));
654 return NodeMap[V] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0],
657 // Canonicalize all constant ints to be unsigned.
658 return N = DAG.getConstant(cast<ConstantInt>(C)->getZExtValue(),VT);
662 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
663 std::map<const AllocaInst*, int>::iterator SI =
664 FuncInfo.StaticAllocaMap.find(AI);
665 if (SI != FuncInfo.StaticAllocaMap.end())
666 return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
669 unsigned InReg = FuncInfo.ValueMap[V];
670 assert(InReg && "Value not in map!");
672 // If this type is not legal, make it so now.
673 if (VT != MVT::Vector) {
674 if (TLI.getTypeAction(VT) == TargetLowering::Expand) {
675 // Source must be expanded. This input value is actually coming from the
676 // register pair InReg and InReg+1.
677 MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
678 unsigned NumVals = TLI.getNumElements(VT);
679 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
681 N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
683 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
684 N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
685 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
688 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
689 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
690 if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case
691 N = MVT::isFloatingPoint(VT)
692 ? DAG.getNode(ISD::FP_ROUND, VT, N)
693 : DAG.getNode(ISD::TRUNCATE, VT, N);
696 // Otherwise, if this is a vector, make it available as a generic vector
698 MVT::ValueType PTyElementVT, PTyLegalElementVT;
699 const VectorType *PTy = cast<VectorType>(VTy);
700 unsigned NE = TLI.getVectorTypeBreakdown(PTy, PTyElementVT,
703 // Build a VBUILD_VECTOR with the input registers.
704 SmallVector<SDOperand, 8> Ops;
705 if (PTyElementVT == PTyLegalElementVT) {
706 // If the value types are legal, just VBUILD the CopyFromReg nodes.
707 for (unsigned i = 0; i != NE; ++i)
708 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
710 } else if (PTyElementVT < PTyLegalElementVT) {
711 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate.
712 for (unsigned i = 0; i != NE; ++i) {
713 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
715 if (MVT::isFloatingPoint(PTyElementVT))
716 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
718 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op);
722 // If the register was expanded, use BUILD_PAIR.
723 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!");
724 for (unsigned i = 0; i != NE/2; ++i) {
725 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
727 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
729 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1));
733 Ops.push_back(DAG.getConstant(NE, MVT::i32));
734 Ops.push_back(DAG.getValueType(PTyLegalElementVT));
735 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
737 // Finally, use a VBIT_CONVERT to make this available as the appropriate
739 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
740 DAG.getConstant(PTy->getNumElements(),
742 DAG.getValueType(TLI.getValueType(PTy->getElementType())));
749 void SelectionDAGLowering::visitRet(ReturnInst &I) {
750 if (I.getNumOperands() == 0) {
751 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
754 SmallVector<SDOperand, 8> NewValues;
755 NewValues.push_back(getRoot());
756 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
757 SDOperand RetOp = getValue(I.getOperand(i));
759 // If this is an integer return value, we need to promote it ourselves to
760 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
762 // FIXME: C calling convention requires the return type to be promoted to
763 // at least 32-bit. But this is not necessary for non-C calling conventions.
764 if (MVT::isInteger(RetOp.getValueType()) &&
765 RetOp.getValueType() < MVT::i64) {
766 MVT::ValueType TmpVT;
767 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
768 TmpVT = TLI.getTypeToTransformTo(MVT::i32);
771 const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
772 ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
773 if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
774 ExtendKind = ISD::SIGN_EXTEND;
775 if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
776 ExtendKind = ISD::ZERO_EXTEND;
777 RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
779 NewValues.push_back(RetOp);
780 NewValues.push_back(DAG.getConstant(false, MVT::i32));
782 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
783 &NewValues[0], NewValues.size()));
786 /// ExportFromCurrentBlock - If this condition isn't known to be exported from
787 /// the current basic block, add it to ValueMap now so that we'll get a
789 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
790 // No need to export constants.
791 if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
794 if (FuncInfo.isExportedInst(V)) return;
796 unsigned Reg = FuncInfo.InitializeRegForValue(V);
797 PendingLoads.push_back(CopyValueToVirtualRegister(V, Reg));
800 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
801 const BasicBlock *FromBB) {
802 // The operands of the setcc have to be in this block. We don't know
803 // how to export them from some other block.
804 if (Instruction *VI = dyn_cast<Instruction>(V)) {
805 // Can export from current BB.
806 if (VI->getParent() == FromBB)
809 // Is already exported, noop.
810 return FuncInfo.isExportedInst(V);
813 // If this is an argument, we can export it if the BB is the entry block or
814 // if it is already exported.
815 if (isa<Argument>(V)) {
816 if (FromBB == &FromBB->getParent()->getEntryBlock())
819 // Otherwise, can only export this if it is already exported.
820 return FuncInfo.isExportedInst(V);
823 // Otherwise, constants can always be exported.
827 static bool InBlock(const Value *V, const BasicBlock *BB) {
828 if (const Instruction *I = dyn_cast<Instruction>(V))
829 return I->getParent() == BB;
833 /// FindMergedConditions - If Cond is an expression like
834 void SelectionDAGLowering::FindMergedConditions(Value *Cond,
835 MachineBasicBlock *TBB,
836 MachineBasicBlock *FBB,
837 MachineBasicBlock *CurBB,
839 // If this node is not part of the or/and tree, emit it as a branch.
840 Instruction *BOp = dyn_cast<Instruction>(Cond);
842 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
843 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
844 BOp->getParent() != CurBB->getBasicBlock() ||
845 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
846 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
847 const BasicBlock *BB = CurBB->getBasicBlock();
849 // If the leaf of the tree is a comparison, merge the condition into
851 if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) &&
852 // The operands of the cmp have to be in this block. We don't know
853 // how to export them from some other block. If this is the first block
854 // of the sequence, no exporting is needed.
856 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
857 isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) {
858 BOp = cast<Instruction>(Cond);
859 ISD::CondCode Condition;
860 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
861 switch (IC->getPredicate()) {
862 default: assert(0 && "Unknown icmp predicate opcode!");
863 case ICmpInst::ICMP_EQ: Condition = ISD::SETEQ; break;
864 case ICmpInst::ICMP_NE: Condition = ISD::SETNE; break;
865 case ICmpInst::ICMP_SLE: Condition = ISD::SETLE; break;
866 case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break;
867 case ICmpInst::ICMP_SGE: Condition = ISD::SETGE; break;
868 case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break;
869 case ICmpInst::ICMP_SLT: Condition = ISD::SETLT; break;
870 case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break;
871 case ICmpInst::ICMP_SGT: Condition = ISD::SETGT; break;
872 case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break;
874 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) {
875 ISD::CondCode FPC, FOC;
876 switch (FC->getPredicate()) {
877 default: assert(0 && "Unknown fcmp predicate opcode!");
878 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
879 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
880 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
881 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
882 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
883 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
884 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
885 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
886 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
887 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
888 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
889 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
890 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
891 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
892 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
893 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
895 if (FiniteOnlyFPMath())
900 Condition = ISD::SETEQ; // silence warning.
901 assert(0 && "Unknown compare instruction");
904 SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
905 BOp->getOperand(1), TBB, FBB, CurBB);
906 SwitchCases.push_back(CB);
910 // Create a CaseBlock record representing this branch.
911 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
913 SwitchCases.push_back(CB);
918 // Create TmpBB after CurBB.
919 MachineFunction::iterator BBI = CurBB;
920 MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock());
921 CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB);
923 if (Opc == Instruction::Or) {
932 // Emit the LHS condition.
933 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc);
935 // Emit the RHS condition into TmpBB.
936 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
938 assert(Opc == Instruction::And && "Unknown merge op!");
946 // This requires creation of TmpBB after CurBB.
948 // Emit the LHS condition.
949 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc);
951 // Emit the RHS condition into TmpBB.
952 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc);
956 /// If the set of cases should be emitted as a series of branches, return true.
957 /// If we should emit this as a bunch of and/or'd together conditions, return
960 ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) {
961 if (Cases.size() != 2) return true;
963 // If this is two comparisons of the same values or'd or and'd together, they
964 // will get folded into a single comparison, so don't emit two blocks.
965 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
966 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
967 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
968 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
975 void SelectionDAGLowering::visitBr(BranchInst &I) {
976 // Update machine-CFG edges.
977 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
979 // Figure out which block is immediately after the current one.
980 MachineBasicBlock *NextBlock = 0;
981 MachineFunction::iterator BBI = CurMBB;
982 if (++BBI != CurMBB->getParent()->end())
985 if (I.isUnconditional()) {
986 // If this is not a fall-through branch, emit the branch.
987 if (Succ0MBB != NextBlock)
988 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
989 DAG.getBasicBlock(Succ0MBB)));
991 // Update machine-CFG edges.
992 CurMBB->addSuccessor(Succ0MBB);
997 // If this condition is one of the special cases we handle, do special stuff
999 Value *CondVal = I.getCondition();
1000 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
1002 // If this is a series of conditions that are or'd or and'd together, emit
1003 // this as a sequence of branches instead of setcc's with and/or operations.
1004 // For example, instead of something like:
1017 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
1018 if (BOp->hasOneUse() &&
1019 (BOp->getOpcode() == Instruction::And ||
1020 BOp->getOpcode() == Instruction::Or)) {
1021 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode());
1022 // If the compares in later blocks need to use values not currently
1023 // exported from this block, export them now. This block should always
1024 // be the first entry.
1025 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!");
1027 // Allow some cases to be rejected.
1028 if (ShouldEmitAsBranches(SwitchCases)) {
1029 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {
1030 ExportFromCurrentBlock(SwitchCases[i].CmpLHS);
1031 ExportFromCurrentBlock(SwitchCases[i].CmpRHS);
1034 // Emit the branch for this block.
1035 visitSwitchCase(SwitchCases[0]);
1036 SwitchCases.erase(SwitchCases.begin());
1040 // Okay, we decided not to do this, remove any inserted MBB's and clear
1042 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i)
1043 CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB);
1045 SwitchCases.clear();
1049 // Create a CaseBlock record representing this branch.
1050 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
1051 Succ0MBB, Succ1MBB, CurMBB);
1052 // Use visitSwitchCase to actually insert the fast branch sequence for this
1054 visitSwitchCase(CB);
1057 /// visitSwitchCase - Emits the necessary code to represent a single node in
1058 /// the binary search tree resulting from lowering a switch instruction.
1059 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
1061 SDOperand CondLHS = getValue(CB.CmpLHS);
1063 // Build the setcc now, fold "(X == true)" to X and "(X == false)" to !X to
1064 // handle common cases produced by branch lowering.
1065 if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
1067 else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
1068 SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
1069 Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
1071 Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
1073 // Set NextBlock to be the MBB immediately after the current one, if any.
1074 // This is used to avoid emitting unnecessary branches to the next block.
1075 MachineBasicBlock *NextBlock = 0;
1076 MachineFunction::iterator BBI = CurMBB;
1077 if (++BBI != CurMBB->getParent()->end())
1080 // If the lhs block is the next block, invert the condition so that we can
1081 // fall through to the lhs instead of the rhs block.
1082 if (CB.TrueBB == NextBlock) {
1083 std::swap(CB.TrueBB, CB.FalseBB);
1084 SDOperand True = DAG.getConstant(1, Cond.getValueType());
1085 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
1087 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond,
1088 DAG.getBasicBlock(CB.TrueBB));
1089 if (CB.FalseBB == NextBlock)
1090 DAG.setRoot(BrCond);
1092 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
1093 DAG.getBasicBlock(CB.FalseBB)));
1094 // Update successor info
1095 CurMBB->addSuccessor(CB.TrueBB);
1096 CurMBB->addSuccessor(CB.FalseBB);
1099 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
1100 // Emit the code for the jump table
1101 MVT::ValueType PTy = TLI.getPointerTy();
1102 SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
1103 SDOperand Table = DAG.getJumpTable(JT.JTI, PTy);
1104 DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1),
1109 void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
1110 assert(0 && "Should never be visited directly");
1112 void SelectionDAGLowering::visitInvoke(InvokeInst &I, bool AsTerminator) {
1113 // Retrieve successors.
1114 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
1115 MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
1117 if (!AsTerminator) {
1118 // Mark landing pad so that it doesn't get deleted in branch folding.
1119 LandingPad->setIsLandingPad();
1121 // Insert a label before the invoke call to mark the try range.
1122 // This can be used to detect deletion of the invoke via the
1123 // MachineModuleInfo.
1124 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
1125 unsigned BeginLabel = MMI->NextLabelID();
1126 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1127 DAG.getConstant(BeginLabel, MVT::i32)));
1129 LowerCallTo(I, I.getCalledValue()->getType(),
1132 getValue(I.getOperand(0)),
1135 // Insert a label before the invoke call to mark the try range.
1136 // This can be used to detect deletion of the invoke via the
1137 // MachineModuleInfo.
1138 unsigned EndLabel = MMI->NextLabelID();
1139 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
1140 DAG.getConstant(EndLabel, MVT::i32)));
1142 // Inform MachineModuleInfo of range.
1143 MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
1145 // Update successor info
1146 CurMBB->addSuccessor(Return);
1147 CurMBB->addSuccessor(LandingPad);
1149 // Drop into normal successor.
1150 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1151 DAG.getBasicBlock(Return)));
1155 void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
1158 void SelectionDAGLowering::visitSwitch(SwitchInst &I) {
1159 // Figure out which block is immediately after the current one.
1160 MachineBasicBlock *NextBlock = 0;
1161 MachineFunction::iterator BBI = CurMBB;
1163 if (++BBI != CurMBB->getParent()->end())
1166 MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()];
1168 // If there is only the default destination, branch to it if it is not the
1169 // next basic block. Otherwise, just fall through.
1170 if (I.getNumOperands() == 2) {
1171 // Update machine-CFG edges.
1173 // If this is not a fall-through branch, emit the branch.
1174 if (Default != NextBlock)
1175 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
1176 DAG.getBasicBlock(Default)));
1178 CurMBB->addSuccessor(Default);
1182 // If there are any non-default case statements, create a vector of Cases
1183 // representing each one, and sort the vector so that we can efficiently
1184 // create a binary search tree from them.
1185 std::vector<Case> Cases;
1187 for (unsigned i = 1; i < I.getNumSuccessors(); ++i) {
1188 MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)];
1189 Cases.push_back(Case(I.getSuccessorValue(i), SMBB));
1192 std::sort(Cases.begin(), Cases.end(), CaseCmp());
1194 // Get the Value to be switched on and default basic blocks, which will be
1195 // inserted into CaseBlock records, representing basic blocks in the binary
1197 Value *SV = I.getOperand(0);
1199 // Get the MachineFunction which holds the current MBB. This is used during
1200 // emission of jump tables, and when inserting any additional MBBs necessary
1201 // to represent the switch.
1202 MachineFunction *CurMF = CurMBB->getParent();
1203 const BasicBlock *LLVMBB = CurMBB->getBasicBlock();
1205 // If the switch has few cases (two or less) emit a series of specific
1207 if (Cases.size() < 3) {
1208 // TODO: If any two of the cases has the same destination, and if one value
1209 // is the same as the other, but has one bit unset that the other has set,
1210 // use bit manipulation to do two compares at once. For example:
1211 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
1213 // Rearrange the case blocks so that the last one falls through if possible.
1214 if (NextBlock && Default != NextBlock && Cases.back().second != NextBlock) {
1215 // The last case block won't fall through into 'NextBlock' if we emit the
1216 // branches in this order. See if rearranging a case value would help.
1217 for (unsigned i = 0, e = Cases.size()-1; i != e; ++i) {
1218 if (Cases[i].second == NextBlock) {
1219 std::swap(Cases[i], Cases.back());
1225 // Create a CaseBlock record representing a conditional branch to
1226 // the Case's target mbb if the value being switched on SV is equal
1228 MachineBasicBlock *CurBlock = CurMBB;
1229 for (unsigned i = 0, e = Cases.size(); i != e; ++i) {
1230 MachineBasicBlock *FallThrough;
1232 FallThrough = new MachineBasicBlock(CurMBB->getBasicBlock());
1233 CurMF->getBasicBlockList().insert(BBI, FallThrough);
1235 // If the last case doesn't match, go to the default block.
1236 FallThrough = Default;
1239 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, Cases[i].first,
1240 Cases[i].second, FallThrough, CurBlock);
1242 // If emitting the first comparison, just call visitSwitchCase to emit the
1243 // code into the current block. Otherwise, push the CaseBlock onto the
1244 // vector to be later processed by SDISel, and insert the node's MBB
1245 // before the next MBB.
1246 if (CurBlock == CurMBB)
1247 visitSwitchCase(CB);
1249 SwitchCases.push_back(CB);
1251 CurBlock = FallThrough;
1256 // If the switch has more than 5 blocks, and at least 31.25% dense, and the
1257 // target supports indirect branches, then emit a jump table rather than
1258 // lowering the switch to a binary tree of conditional branches.
1259 if ((TLI.isOperationLegal(ISD::BR_JT, MVT::Other) ||
1260 TLI.isOperationLegal(ISD::BRIND, MVT::Other)) &&
1262 uint64_t First =cast<ConstantInt>(Cases.front().first)->getSExtValue();
1263 uint64_t Last = cast<ConstantInt>(Cases.back().first)->getSExtValue();
1264 double Density = (double)Cases.size() / (double)((Last - First) + 1ULL);
1266 if (Density >= 0.3125) {
1267 // Create a new basic block to hold the code for loading the address
1268 // of the jump table, and jumping to it. Update successor information;
1269 // we will either branch to the default case for the switch, or the jump
1271 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
1272 CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
1273 CurMBB->addSuccessor(Default);
1274 CurMBB->addSuccessor(JumpTableBB);
1276 // Subtract the lowest switch case value from the value being switched on
1277 // and conditional branch to default mbb if the result is greater than the
1278 // difference between smallest and largest cases.
1279 SDOperand SwitchOp = getValue(SV);
1280 MVT::ValueType VT = SwitchOp.getValueType();
1281 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
1282 DAG.getConstant(First, VT));
1284 // The SDNode we just created, which holds the value being switched on
1285 // minus the the smallest case value, needs to be copied to a virtual
1286 // register so it can be used as an index into the jump table in a
1287 // subsequent basic block. This value may be smaller or larger than the
1288 // target's pointer type, and therefore require extension or truncating.
1289 if (VT > TLI.getPointerTy())
1290 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
1292 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
1294 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
1295 SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
1297 // Emit the range check for the jump table, and branch to the default
1298 // block for the switch statement if the value being switched on exceeds
1299 // the largest case in the switch.
1300 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
1301 DAG.getConstant(Last-First,VT), ISD::SETUGT);
1302 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
1303 DAG.getBasicBlock(Default)));
1305 // Build a vector of destination BBs, corresponding to each target
1306 // of the jump table. If the value of the jump table slot corresponds to
1307 // a case statement, push the case's BB onto the vector, otherwise, push
1309 std::vector<MachineBasicBlock*> DestBBs;
1310 int64_t TEI = First;
1311 for (CaseItr ii = Cases.begin(), ee = Cases.end(); ii != ee; ++TEI)
1312 if (cast<ConstantInt>(ii->first)->getSExtValue() == TEI) {
1313 DestBBs.push_back(ii->second);
1316 DestBBs.push_back(Default);
1319 // Update successor info. Add one edge to each unique successor.
1320 // Vector bool would be better, but vector<bool> is really slow.
1321 std::vector<unsigned char> SuccsHandled;
1322 SuccsHandled.resize(CurMBB->getParent()->getNumBlockIDs());
1324 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
1325 E = DestBBs.end(); I != E; ++I) {
1326 if (!SuccsHandled[(*I)->getNumber()]) {
1327 SuccsHandled[(*I)->getNumber()] = true;
1328 JumpTableBB->addSuccessor(*I);
1332 // Create a jump table index for this jump table, or return an existing
1334 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
1336 // Set the jump table information so that we can codegen it as a second
1337 // MachineBasicBlock
1338 JT.Reg = JumpTableReg;
1340 JT.MBB = JumpTableBB;
1341 JT.Default = Default;
1346 // Push the initial CaseRec onto the worklist
1347 std::vector<CaseRec> CaseVec;
1348 CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
1350 while (!CaseVec.empty()) {
1351 // Grab a record representing a case range to process off the worklist
1352 CaseRec CR = CaseVec.back();
1355 // Size is the number of Cases represented by this range. If Size is 1,
1356 // then we are processing a leaf of the binary search tree. Otherwise,
1357 // we need to pick a pivot, and push left and right ranges onto the
1359 unsigned Size = CR.Range.second - CR.Range.first;
1362 // Create a CaseBlock record representing a conditional branch to
1363 // the Case's target mbb if the value being switched on SV is equal
1364 // to C. Otherwise, branch to default.
1365 Constant *C = CR.Range.first->first;
1366 MachineBasicBlock *Target = CR.Range.first->second;
1367 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, C, Target, Default,
1370 // If the MBB representing the leaf node is the current MBB, then just
1371 // call visitSwitchCase to emit the code into the current block.
1372 // Otherwise, push the CaseBlock onto the vector to be later processed
1373 // by SDISel, and insert the node's MBB before the next MBB.
1374 if (CR.CaseBB == CurMBB)
1375 visitSwitchCase(CB);
1377 SwitchCases.push_back(CB);
1379 // split case range at pivot
1380 CaseItr Pivot = CR.Range.first + (Size / 2);
1381 CaseRange LHSR(CR.Range.first, Pivot);
1382 CaseRange RHSR(Pivot, CR.Range.second);
1383 Constant *C = Pivot->first;
1384 MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
1386 // We know that we branch to the LHS if the Value being switched on is
1387 // less than the Pivot value, C. We use this to optimize our binary
1388 // tree a bit, by recognizing that if SV is greater than or equal to the
1389 // LHS's Case Value, and that Case Value is exactly one less than the
1390 // Pivot's Value, then we can branch directly to the LHS's Target,
1391 // rather than creating a leaf node for it.
1392 if ((LHSR.second - LHSR.first) == 1 &&
1393 LHSR.first->first == CR.GE &&
1394 cast<ConstantInt>(C)->getZExtValue() ==
1395 (cast<ConstantInt>(CR.GE)->getZExtValue() + 1ULL)) {
1396 TrueBB = LHSR.first->second;
1398 TrueBB = new MachineBasicBlock(LLVMBB);
1399 CurMF->getBasicBlockList().insert(BBI, TrueBB);
1400 CaseVec.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
1403 // Similar to the optimization above, if the Value being switched on is
1404 // known to be less than the Constant CR.LT, and the current Case Value
1405 // is CR.LT - 1, then we can branch directly to the target block for
1406 // the current Case Value, rather than emitting a RHS leaf node for it.
1407 if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
1408 cast<ConstantInt>(RHSR.first->first)->getZExtValue() ==
1409 (cast<ConstantInt>(CR.LT)->getZExtValue() - 1ULL)) {
1410 FalseBB = RHSR.first->second;
1412 FalseBB = new MachineBasicBlock(LLVMBB);
1413 CurMF->getBasicBlockList().insert(BBI, FalseBB);
1414 CaseVec.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
1417 // Create a CaseBlock record representing a conditional branch to
1418 // the LHS node if the value being switched on SV is less than C.
1419 // Otherwise, branch to LHS.
1420 SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, TrueBB, FalseBB,
1423 if (CR.CaseBB == CurMBB)
1424 visitSwitchCase(CB);
1426 SwitchCases.push_back(CB);
1431 void SelectionDAGLowering::visitSub(User &I) {
1432 // -0.0 - X --> fneg
1433 const Type *Ty = I.getType();
1434 if (isa<VectorType>(Ty)) {
1435 visitVectorBinary(I, ISD::VSUB);
1436 } else if (Ty->isFloatingPoint()) {
1437 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
1438 if (CFP->isExactlyValue(-0.0)) {
1439 SDOperand Op2 = getValue(I.getOperand(1));
1440 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
1443 visitScalarBinary(I, ISD::FSUB);
1445 visitScalarBinary(I, ISD::SUB);
1448 void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) {
1449 SDOperand Op1 = getValue(I.getOperand(0));
1450 SDOperand Op2 = getValue(I.getOperand(1));
1452 setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
1456 SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) {
1457 assert(isa<VectorType>(I.getType()));
1458 const VectorType *Ty = cast<VectorType>(I.getType());
1459 SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType()));
1461 setValue(&I, DAG.getNode(OpCode, MVT::Vector,
1462 getValue(I.getOperand(0)),
1463 getValue(I.getOperand(1)),
1464 DAG.getConstant(Ty->getNumElements(), MVT::i32),
1468 void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp,
1469 unsigned VectorOp) {
1470 if (isa<VectorType>(I.getType()))
1471 visitVectorBinary(I, VectorOp);
1473 visitScalarBinary(I, ScalarOp);
1476 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
1477 SDOperand Op1 = getValue(I.getOperand(0));
1478 SDOperand Op2 = getValue(I.getOperand(1));
1480 if (TLI.getShiftAmountTy() < Op2.getValueType())
1481 Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
1482 else if (TLI.getShiftAmountTy() > Op2.getValueType())
1483 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
1485 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
1488 void SelectionDAGLowering::visitICmp(User &I) {
1489 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE;
1490 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I))
1491 predicate = IC->getPredicate();
1492 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I))
1493 predicate = ICmpInst::Predicate(IC->getPredicate());
1494 SDOperand Op1 = getValue(I.getOperand(0));
1495 SDOperand Op2 = getValue(I.getOperand(1));
1496 ISD::CondCode Opcode;
1497 switch (predicate) {
1498 case ICmpInst::ICMP_EQ : Opcode = ISD::SETEQ; break;
1499 case ICmpInst::ICMP_NE : Opcode = ISD::SETNE; break;
1500 case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break;
1501 case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break;
1502 case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break;
1503 case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break;
1504 case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break;
1505 case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break;
1506 case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break;
1507 case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break;
1509 assert(!"Invalid ICmp predicate value");
1510 Opcode = ISD::SETEQ;
1513 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
1516 void SelectionDAGLowering::visitFCmp(User &I) {
1517 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE;
1518 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I))
1519 predicate = FC->getPredicate();
1520 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I))
1521 predicate = FCmpInst::Predicate(FC->getPredicate());
1522 SDOperand Op1 = getValue(I.getOperand(0));
1523 SDOperand Op2 = getValue(I.getOperand(1));
1524 ISD::CondCode Condition, FOC, FPC;
1525 switch (predicate) {
1526 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
1527 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
1528 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
1529 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
1530 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break;
1531 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break;
1532 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break;
1533 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break;
1534 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break;
1535 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break;
1536 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break;
1537 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break;
1538 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break;
1539 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break;
1540 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break;
1541 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break;
1543 assert(!"Invalid FCmp predicate value");
1544 FOC = FPC = ISD::SETFALSE;
1547 if (FiniteOnlyFPMath())
1551 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition));
1554 void SelectionDAGLowering::visitSelect(User &I) {
1555 SDOperand Cond = getValue(I.getOperand(0));
1556 SDOperand TrueVal = getValue(I.getOperand(1));
1557 SDOperand FalseVal = getValue(I.getOperand(2));
1558 if (!isa<VectorType>(I.getType())) {
1559 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
1560 TrueVal, FalseVal));
1562 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal,
1563 *(TrueVal.Val->op_end()-2),
1564 *(TrueVal.Val->op_end()-1)));
1569 void SelectionDAGLowering::visitTrunc(User &I) {
1570 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).
1571 SDOperand N = getValue(I.getOperand(0));
1572 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1573 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1576 void SelectionDAGLowering::visitZExt(User &I) {
1577 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1578 // ZExt also can't be a cast to bool for same reason. So, nothing much to do
1579 SDOperand N = getValue(I.getOperand(0));
1580 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1581 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1584 void SelectionDAGLowering::visitSExt(User &I) {
1585 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest).
1586 // SExt also can't be a cast to bool for same reason. So, nothing much to do
1587 SDOperand N = getValue(I.getOperand(0));
1588 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1589 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N));
1592 void SelectionDAGLowering::visitFPTrunc(User &I) {
1593 // FPTrunc is never a no-op cast, no need to check
1594 SDOperand N = getValue(I.getOperand(0));
1595 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1596 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N));
1599 void SelectionDAGLowering::visitFPExt(User &I){
1600 // FPTrunc is never a no-op cast, no need to check
1601 SDOperand N = getValue(I.getOperand(0));
1602 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1603 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N));
1606 void SelectionDAGLowering::visitFPToUI(User &I) {
1607 // FPToUI is never a no-op cast, no need to check
1608 SDOperand N = getValue(I.getOperand(0));
1609 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1610 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N));
1613 void SelectionDAGLowering::visitFPToSI(User &I) {
1614 // FPToSI is never a no-op cast, no need to check
1615 SDOperand N = getValue(I.getOperand(0));
1616 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1617 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N));
1620 void SelectionDAGLowering::visitUIToFP(User &I) {
1621 // UIToFP is never a no-op cast, no need to check
1622 SDOperand N = getValue(I.getOperand(0));
1623 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1624 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N));
1627 void SelectionDAGLowering::visitSIToFP(User &I){
1628 // UIToFP is never a no-op cast, no need to check
1629 SDOperand N = getValue(I.getOperand(0));
1630 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1631 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N));
1634 void SelectionDAGLowering::visitPtrToInt(User &I) {
1635 // What to do depends on the size of the integer and the size of the pointer.
1636 // We can either truncate, zero extend, or no-op, accordingly.
1637 SDOperand N = getValue(I.getOperand(0));
1638 MVT::ValueType SrcVT = N.getValueType();
1639 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1641 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1642 Result = DAG.getNode(ISD::TRUNCATE, DestVT, N);
1644 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1645 Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N);
1646 setValue(&I, Result);
1649 void SelectionDAGLowering::visitIntToPtr(User &I) {
1650 // What to do depends on the size of the integer and the size of the pointer.
1651 // We can either truncate, zero extend, or no-op, accordingly.
1652 SDOperand N = getValue(I.getOperand(0));
1653 MVT::ValueType SrcVT = N.getValueType();
1654 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1655 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT))
1656 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N));
1658 // Note: ZERO_EXTEND can handle cases where the sizes are equal too
1659 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N));
1662 void SelectionDAGLowering::visitBitCast(User &I) {
1663 SDOperand N = getValue(I.getOperand(0));
1664 MVT::ValueType DestVT = TLI.getValueType(I.getType());
1665 if (DestVT == MVT::Vector) {
1666 // This is a cast to a vector from something else.
1667 // Get information about the output vector.
1668 const VectorType *DestTy = cast<VectorType>(I.getType());
1669 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
1670 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N,
1671 DAG.getConstant(DestTy->getNumElements(),MVT::i32),
1672 DAG.getValueType(EltVT)));
1675 MVT::ValueType SrcVT = N.getValueType();
1676 if (SrcVT == MVT::Vector) {
1677 // This is a cast from a vctor to something else.
1678 // Get information about the input vector.
1679 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N));
1683 // BitCast assures us that source and destination are the same size so this
1684 // is either a BIT_CONVERT or a no-op.
1685 if (DestVT != N.getValueType())
1686 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types
1688 setValue(&I, N); // noop cast.
1691 void SelectionDAGLowering::visitInsertElement(User &I) {
1692 SDOperand InVec = getValue(I.getOperand(0));
1693 SDOperand InVal = getValue(I.getOperand(1));
1694 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1695 getValue(I.getOperand(2)));
1697 SDOperand Num = *(InVec.Val->op_end()-2);
1698 SDOperand Typ = *(InVec.Val->op_end()-1);
1699 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector,
1700 InVec, InVal, InIdx, Num, Typ));
1703 void SelectionDAGLowering::visitExtractElement(User &I) {
1704 SDOperand InVec = getValue(I.getOperand(0));
1705 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
1706 getValue(I.getOperand(1)));
1707 SDOperand Typ = *(InVec.Val->op_end()-1);
1708 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT,
1709 TLI.getValueType(I.getType()), InVec, InIdx));
1712 void SelectionDAGLowering::visitShuffleVector(User &I) {
1713 SDOperand V1 = getValue(I.getOperand(0));
1714 SDOperand V2 = getValue(I.getOperand(1));
1715 SDOperand Mask = getValue(I.getOperand(2));
1717 SDOperand Num = *(V1.Val->op_end()-2);
1718 SDOperand Typ = *(V2.Val->op_end()-1);
1719 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
1720 V1, V2, Mask, Num, Typ));
1724 void SelectionDAGLowering::visitGetElementPtr(User &I) {
1725 SDOperand N = getValue(I.getOperand(0));
1726 const Type *Ty = I.getOperand(0)->getType();
1728 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
1731 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
1732 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
1735 uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field);
1736 N = DAG.getNode(ISD::ADD, N.getValueType(), N,
1737 getIntPtrConstant(Offset));
1739 Ty = StTy->getElementType(Field);
1741 Ty = cast<SequentialType>(Ty)->getElementType();
1743 // If this is a constant subscript, handle it quickly.
1744 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
1745 if (CI->getZExtValue() == 0) continue;
1747 TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
1748 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
1752 // N = N + Idx * ElementSize;
1753 uint64_t ElementSize = TD->getTypeSize(Ty);
1754 SDOperand IdxN = getValue(Idx);
1756 // If the index is smaller or larger than intptr_t, truncate or extend
1758 if (IdxN.getValueType() < N.getValueType()) {
1759 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
1760 } else if (IdxN.getValueType() > N.getValueType())
1761 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
1763 // If this is a multiply by a power of two, turn it into a shl
1764 // immediately. This is a very common case.
1765 if (isPowerOf2_64(ElementSize)) {
1766 unsigned Amt = Log2_64(ElementSize);
1767 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
1768 DAG.getConstant(Amt, TLI.getShiftAmountTy()));
1769 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1773 SDOperand Scale = getIntPtrConstant(ElementSize);
1774 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
1775 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
1781 void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
1782 // If this is a fixed sized alloca in the entry block of the function,
1783 // allocate it statically on the stack.
1784 if (FuncInfo.StaticAllocaMap.count(&I))
1785 return; // getValue will auto-populate this.
1787 const Type *Ty = I.getAllocatedType();
1788 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
1790 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
1793 SDOperand AllocSize = getValue(I.getArraySize());
1794 MVT::ValueType IntPtr = TLI.getPointerTy();
1795 if (IntPtr < AllocSize.getValueType())
1796 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
1797 else if (IntPtr > AllocSize.getValueType())
1798 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
1800 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
1801 getIntPtrConstant(TySize));
1803 // Handle alignment. If the requested alignment is less than or equal to the
1804 // stack alignment, ignore it and round the size of the allocation up to the
1805 // stack alignment size. If the size is greater than the stack alignment, we
1806 // note this in the DYNAMIC_STACKALLOC node.
1807 unsigned StackAlign =
1808 TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
1809 if (Align <= StackAlign) {
1811 // Add SA-1 to the size.
1812 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
1813 getIntPtrConstant(StackAlign-1));
1814 // Mask out the low bits for alignment purposes.
1815 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
1816 getIntPtrConstant(~(uint64_t)(StackAlign-1)));
1819 SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) };
1820 const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
1822 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3);
1824 DAG.setRoot(DSA.getValue(1));
1826 // Inform the Frame Information that we have just allocated a variable-sized
1828 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
1831 void SelectionDAGLowering::visitLoad(LoadInst &I) {
1832 SDOperand Ptr = getValue(I.getOperand(0));
1838 // Do not serialize non-volatile loads against each other.
1839 Root = DAG.getRoot();
1842 setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0),
1843 Root, I.isVolatile()));
1846 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr,
1847 const Value *SV, SDOperand Root,
1850 if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
1851 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
1852 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr,
1853 DAG.getSrcValue(SV));
1855 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile);
1859 DAG.setRoot(L.getValue(1));
1861 PendingLoads.push_back(L.getValue(1));
1867 void SelectionDAGLowering::visitStore(StoreInst &I) {
1868 Value *SrcV = I.getOperand(0);
1869 SDOperand Src = getValue(SrcV);
1870 SDOperand Ptr = getValue(I.getOperand(1));
1871 DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
1875 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
1876 /// access memory and has no other side effects at all.
1877 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) {
1878 #define GET_NO_MEMORY_INTRINSICS
1879 #include "llvm/Intrinsics.gen"
1880 #undef GET_NO_MEMORY_INTRINSICS
1884 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't
1885 // have any side-effects or if it only reads memory.
1886 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) {
1887 #define GET_SIDE_EFFECT_INFO
1888 #include "llvm/Intrinsics.gen"
1889 #undef GET_SIDE_EFFECT_INFO
1893 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
1895 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
1896 unsigned Intrinsic) {
1897 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic);
1898 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic);
1900 // Build the operand list.
1901 SmallVector<SDOperand, 8> Ops;
1902 if (HasChain) { // If this intrinsic has side-effects, chainify it.
1904 // We don't need to serialize loads against other loads.
1905 Ops.push_back(DAG.getRoot());
1907 Ops.push_back(getRoot());
1911 // Add the intrinsic ID as an integer operand.
1912 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy()));
1914 // Add all operands of the call to the operand list.
1915 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
1916 SDOperand Op = getValue(I.getOperand(i));
1918 // If this is a vector type, force it to the right vector type.
1919 if (Op.getValueType() == MVT::Vector) {
1920 const VectorType *OpTy = cast<VectorType>(I.getOperand(i)->getType());
1921 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType());
1923 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements());
1924 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?");
1925 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op);
1928 assert(TLI.isTypeLegal(Op.getValueType()) &&
1929 "Intrinsic uses a non-legal type?");
1933 std::vector<MVT::ValueType> VTs;
1934 if (I.getType() != Type::VoidTy) {
1935 MVT::ValueType VT = TLI.getValueType(I.getType());
1936 if (VT == MVT::Vector) {
1937 const VectorType *DestTy = cast<VectorType>(I.getType());
1938 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
1940 VT = MVT::getVectorType(EltVT, DestTy->getNumElements());
1941 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?");
1944 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?");
1948 VTs.push_back(MVT::Other);
1950 const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs);
1955 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(),
1956 &Ops[0], Ops.size());
1957 else if (I.getType() != Type::VoidTy)
1958 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(),
1959 &Ops[0], Ops.size());
1961 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(),
1962 &Ops[0], Ops.size());
1965 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1);
1967 PendingLoads.push_back(Chain);
1971 if (I.getType() != Type::VoidTy) {
1972 if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
1973 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType());
1974 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
1975 DAG.getConstant(PTy->getNumElements(), MVT::i32),
1976 DAG.getValueType(EVT));
1978 setValue(&I, Result);
1982 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If
1983 /// we want to emit this as a call to a named external function, return the name
1984 /// otherwise lower it and return null.
1986 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
1987 switch (Intrinsic) {
1989 // By default, turn this into a target intrinsic node.
1990 visitTargetIntrinsic(I, Intrinsic);
1992 case Intrinsic::vastart: visitVAStart(I); return 0;
1993 case Intrinsic::vaend: visitVAEnd(I); return 0;
1994 case Intrinsic::vacopy: visitVACopy(I); return 0;
1995 case Intrinsic::returnaddress:
1996 setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(),
1997 getValue(I.getOperand(1))));
1999 case Intrinsic::frameaddress:
2000 setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(),
2001 getValue(I.getOperand(1))));
2003 case Intrinsic::setjmp:
2004 return "_setjmp"+!TLI.usesUnderscoreSetJmp();
2006 case Intrinsic::longjmp:
2007 return "_longjmp"+!TLI.usesUnderscoreLongJmp();
2009 case Intrinsic::memcpy_i32:
2010 case Intrinsic::memcpy_i64:
2011 visitMemIntrinsic(I, ISD::MEMCPY);
2013 case Intrinsic::memset_i32:
2014 case Intrinsic::memset_i64:
2015 visitMemIntrinsic(I, ISD::MEMSET);
2017 case Intrinsic::memmove_i32:
2018 case Intrinsic::memmove_i64:
2019 visitMemIntrinsic(I, ISD::MEMMOVE);
2022 case Intrinsic::dbg_stoppoint: {
2023 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2024 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I);
2025 if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) {
2029 Ops[1] = getValue(SPI.getLineValue());
2030 Ops[2] = getValue(SPI.getColumnValue());
2032 DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext());
2033 assert(DD && "Not a debug information descriptor");
2034 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD);
2036 Ops[3] = DAG.getString(CompileUnit->getFileName());
2037 Ops[4] = DAG.getString(CompileUnit->getDirectory());
2039 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5));
2044 case Intrinsic::dbg_region_start: {
2045 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2046 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I);
2047 if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) {
2048 unsigned LabelID = MMI->RecordRegionStart(RSI.getContext());
2049 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
2050 DAG.getConstant(LabelID, MVT::i32)));
2055 case Intrinsic::dbg_region_end: {
2056 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2057 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I);
2058 if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) {
2059 unsigned LabelID = MMI->RecordRegionEnd(REI.getContext());
2060 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2061 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2066 case Intrinsic::dbg_func_start: {
2067 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2068 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I);
2069 if (MMI && FSI.getSubprogram() &&
2070 MMI->Verify(FSI.getSubprogram())) {
2071 unsigned LabelID = MMI->RecordRegionStart(FSI.getSubprogram());
2072 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other,
2073 getRoot(), DAG.getConstant(LabelID, MVT::i32)));
2078 case Intrinsic::dbg_declare: {
2079 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2080 DbgDeclareInst &DI = cast<DbgDeclareInst>(I);
2081 if (MMI && DI.getVariable() && MMI->Verify(DI.getVariable())) {
2082 SDOperand AddressOp = getValue(DI.getAddress());
2083 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp))
2084 MMI->RecordVariable(DI.getVariable(), FI->getIndex());
2090 case Intrinsic::eh_exception: {
2091 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2094 // Add a label to mark the beginning of the landing pad. Deletion of the
2095 // landing pad can thus be detected via the MachineModuleInfo.
2096 unsigned LabelID = MMI->addLandingPad(CurMBB);
2097 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
2098 DAG.getConstant(LabelID, MVT::i32)));
2100 // Mark exception register as live in.
2101 unsigned Reg = TLI.getExceptionAddressRegister();
2102 if (Reg) CurMBB->addLiveIn(Reg);
2104 // Insert the EXCEPTIONADDR instruction.
2105 SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
2107 Ops[0] = DAG.getRoot();
2108 SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
2110 DAG.setRoot(Op.getValue(1));
2112 setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
2117 case Intrinsic::eh_selector:
2118 case Intrinsic::eh_filter:{
2119 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2122 // Inform the MachineModuleInfo of the personality for this landing pad.
2123 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(2));
2124 assert(CE && CE->getOpcode() == Instruction::BitCast &&
2125 isa<Function>(CE->getOperand(0)) &&
2126 "Personality should be a function");
2127 MMI->addPersonality(CurMBB, cast<Function>(CE->getOperand(0)));
2128 if (Intrinsic == Intrinsic::eh_filter)
2129 MMI->setIsFilterLandingPad(CurMBB);
2131 // Gather all the type infos for this landing pad and pass them along to
2132 // MachineModuleInfo.
2133 std::vector<GlobalVariable *> TyInfo;
2134 for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
2135 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i));
2136 if (CE && CE->getOpcode() == Instruction::BitCast &&
2137 isa<GlobalVariable>(CE->getOperand(0))) {
2138 TyInfo.push_back(cast<GlobalVariable>(CE->getOperand(0)));
2140 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i));
2141 assert(CI && CI->getZExtValue() == 0 &&
2142 "TypeInfo must be a global variable typeinfo or NULL");
2143 TyInfo.push_back(NULL);
2146 MMI->addCatchTypeInfo(CurMBB, TyInfo);
2148 // Mark exception selector register as live in.
2149 unsigned Reg = TLI.getExceptionSelectorRegister();
2150 if (Reg) CurMBB->addLiveIn(Reg);
2152 // Insert the EHSELECTION instruction.
2153 SDVTList VTs = DAG.getVTList(MVT::i32, MVT::Other);
2155 Ops[0] = getValue(I.getOperand(1));
2157 SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
2159 DAG.setRoot(Op.getValue(1));
2161 setValue(&I, DAG.getConstant(0, MVT::i32));
2167 case Intrinsic::eh_typeid_for: {
2168 MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
2171 // Find the type id for the given typeinfo.
2172 GlobalVariable *GV = NULL;
2173 ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(1));
2174 if (CE && CE->getOpcode() == Instruction::BitCast &&
2175 isa<GlobalVariable>(CE->getOperand(0))) {
2176 GV = cast<GlobalVariable>(CE->getOperand(0));
2178 ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
2179 assert(CI && CI->getZExtValue() == 0 &&
2180 "TypeInfo must be a global variable typeinfo or NULL");
2184 unsigned TypeID = MMI->getTypeIDFor(GV);
2185 setValue(&I, DAG.getConstant(TypeID, MVT::i32));
2187 setValue(&I, DAG.getConstant(0, MVT::i32));
2193 case Intrinsic::sqrt_f32:
2194 case Intrinsic::sqrt_f64:
2195 setValue(&I, DAG.getNode(ISD::FSQRT,
2196 getValue(I.getOperand(1)).getValueType(),
2197 getValue(I.getOperand(1))));
2199 case Intrinsic::powi_f32:
2200 case Intrinsic::powi_f64:
2201 setValue(&I, DAG.getNode(ISD::FPOWI,
2202 getValue(I.getOperand(1)).getValueType(),
2203 getValue(I.getOperand(1)),
2204 getValue(I.getOperand(2))));
2206 case Intrinsic::pcmarker: {
2207 SDOperand Tmp = getValue(I.getOperand(1));
2208 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
2211 case Intrinsic::readcyclecounter: {
2212 SDOperand Op = getRoot();
2213 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER,
2214 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2,
2217 DAG.setRoot(Tmp.getValue(1));
2220 case Intrinsic::bswap_i16:
2221 case Intrinsic::bswap_i32:
2222 case Intrinsic::bswap_i64:
2223 setValue(&I, DAG.getNode(ISD::BSWAP,
2224 getValue(I.getOperand(1)).getValueType(),
2225 getValue(I.getOperand(1))));
2227 case Intrinsic::cttz_i8:
2228 case Intrinsic::cttz_i16:
2229 case Intrinsic::cttz_i32:
2230 case Intrinsic::cttz_i64:
2231 setValue(&I, DAG.getNode(ISD::CTTZ,
2232 getValue(I.getOperand(1)).getValueType(),
2233 getValue(I.getOperand(1))));
2235 case Intrinsic::ctlz_i8:
2236 case Intrinsic::ctlz_i16:
2237 case Intrinsic::ctlz_i32:
2238 case Intrinsic::ctlz_i64:
2239 setValue(&I, DAG.getNode(ISD::CTLZ,
2240 getValue(I.getOperand(1)).getValueType(),
2241 getValue(I.getOperand(1))));
2243 case Intrinsic::ctpop_i8:
2244 case Intrinsic::ctpop_i16:
2245 case Intrinsic::ctpop_i32:
2246 case Intrinsic::ctpop_i64:
2247 setValue(&I, DAG.getNode(ISD::CTPOP,
2248 getValue(I.getOperand(1)).getValueType(),
2249 getValue(I.getOperand(1))));
2251 case Intrinsic::stacksave: {
2252 SDOperand Op = getRoot();
2253 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
2254 DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1);
2256 DAG.setRoot(Tmp.getValue(1));
2259 case Intrinsic::stackrestore: {
2260 SDOperand Tmp = getValue(I.getOperand(1));
2261 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp));
2264 case Intrinsic::prefetch:
2265 // FIXME: Currently discarding prefetches.
2271 void SelectionDAGLowering::LowerCallTo(Instruction &I,
2272 const Type *CalledValueTy,
2273 unsigned CallingConv,
2275 SDOperand Callee, unsigned OpIdx) {
2276 const PointerType *PT = cast<PointerType>(CalledValueTy);
2277 const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
2279 TargetLowering::ArgListTy Args;
2280 TargetLowering::ArgListEntry Entry;
2281 Args.reserve(I.getNumOperands());
2282 for (unsigned i = OpIdx, e = I.getNumOperands(); i != e; ++i) {
2283 Value *Arg = I.getOperand(i);
2284 SDOperand ArgNode = getValue(Arg);
2285 Entry.Node = ArgNode; Entry.Ty = Arg->getType();
2286 Entry.isSExt = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
2287 Entry.isZExt = FTy->paramHasAttr(i, FunctionType::ZExtAttribute);
2288 Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
2289 Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
2290 Args.push_back(Entry);
2293 std::pair<SDOperand,SDOperand> Result =
2294 TLI.LowerCallTo(getRoot(), I.getType(),
2295 FTy->paramHasAttr(0,FunctionType::SExtAttribute),
2296 FTy->isVarArg(), CallingConv, IsTailCall,
2298 if (I.getType() != Type::VoidTy)
2299 setValue(&I, Result.first);
2300 DAG.setRoot(Result.second);
2304 void SelectionDAGLowering::visitCall(CallInst &I) {
2305 const char *RenameFn = 0;
2306 if (Function *F = I.getCalledFunction()) {
2307 if (F->isDeclaration())
2308 if (unsigned IID = F->getIntrinsicID()) {
2309 RenameFn = visitIntrinsicCall(I, IID);
2312 } else { // Not an LLVM intrinsic.
2313 const std::string &Name = F->getName();
2314 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) {
2315 if (I.getNumOperands() == 3 && // Basic sanity checks.
2316 I.getOperand(1)->getType()->isFloatingPoint() &&
2317 I.getType() == I.getOperand(1)->getType() &&
2318 I.getType() == I.getOperand(2)->getType()) {
2319 SDOperand LHS = getValue(I.getOperand(1));
2320 SDOperand RHS = getValue(I.getOperand(2));
2321 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
2325 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
2326 if (I.getNumOperands() == 2 && // Basic sanity checks.
2327 I.getOperand(1)->getType()->isFloatingPoint() &&
2328 I.getType() == I.getOperand(1)->getType()) {
2329 SDOperand Tmp = getValue(I.getOperand(1));
2330 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
2333 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
2334 if (I.getNumOperands() == 2 && // Basic sanity checks.
2335 I.getOperand(1)->getType()->isFloatingPoint() &&
2336 I.getType() == I.getOperand(1)->getType()) {
2337 SDOperand Tmp = getValue(I.getOperand(1));
2338 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
2341 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
2342 if (I.getNumOperands() == 2 && // Basic sanity checks.
2343 I.getOperand(1)->getType()->isFloatingPoint() &&
2344 I.getType() == I.getOperand(1)->getType()) {
2345 SDOperand Tmp = getValue(I.getOperand(1));
2346 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
2351 } else if (isa<InlineAsm>(I.getOperand(0))) {
2358 Callee = getValue(I.getOperand(0));
2360 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
2362 LowerCallTo(I, I.getCalledValue()->getType(),
2370 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
2371 SDOperand &Chain, SDOperand &Flag)const{
2372 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag);
2373 Chain = Val.getValue(1);
2374 Flag = Val.getValue(2);
2376 // If the result was expanded, copy from the top part.
2377 if (Regs.size() > 1) {
2378 assert(Regs.size() == 2 &&
2379 "Cannot expand to more than 2 elts yet!");
2380 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag);
2381 Chain = Hi.getValue(1);
2382 Flag = Hi.getValue(2);
2383 if (DAG.getTargetLoweringInfo().isLittleEndian())
2384 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
2386 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val);
2389 // Otherwise, if the return value was promoted or extended, truncate it to the
2390 // appropriate type.
2391 if (RegVT == ValueVT)
2394 if (MVT::isInteger(RegVT)) {
2395 if (ValueVT < RegVT)
2396 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
2398 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
2400 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
2404 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
2405 /// specified value into the registers specified by this object. This uses
2406 /// Chain/Flag as the input and updates them for the output Chain/Flag.
2407 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
2408 SDOperand &Chain, SDOperand &Flag,
2409 MVT::ValueType PtrVT) const {
2410 if (Regs.size() == 1) {
2411 // If there is a single register and the types differ, this must be
2413 if (RegVT != ValueVT) {
2414 if (MVT::isInteger(RegVT)) {
2415 if (RegVT < ValueVT)
2416 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
2418 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
2420 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
2422 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
2423 Flag = Chain.getValue(1);
2425 std::vector<unsigned> R(Regs);
2426 if (!DAG.getTargetLoweringInfo().isLittleEndian())
2427 std::reverse(R.begin(), R.end());
2429 for (unsigned i = 0, e = R.size(); i != e; ++i) {
2430 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
2431 DAG.getConstant(i, PtrVT));
2432 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
2433 Flag = Chain.getValue(1);
2438 /// AddInlineAsmOperands - Add this value to the specified inlineasm node
2439 /// operand list. This adds the code marker and includes the number of
2440 /// values added into it.
2441 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
2442 std::vector<SDOperand> &Ops) const {
2443 Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32));
2444 for (unsigned i = 0, e = Regs.size(); i != e; ++i)
2445 Ops.push_back(DAG.getRegister(Regs[i], RegVT));
2448 /// isAllocatableRegister - If the specified register is safe to allocate,
2449 /// i.e. it isn't a stack pointer or some other special register, return the
2450 /// register class for the register. Otherwise, return null.
2451 static const TargetRegisterClass *
2452 isAllocatableRegister(unsigned Reg, MachineFunction &MF,
2453 const TargetLowering &TLI, const MRegisterInfo *MRI) {
2454 MVT::ValueType FoundVT = MVT::Other;
2455 const TargetRegisterClass *FoundRC = 0;
2456 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
2457 E = MRI->regclass_end(); RCI != E; ++RCI) {
2458 MVT::ValueType ThisVT = MVT::Other;
2460 const TargetRegisterClass *RC = *RCI;
2461 // If none of the the value types for this register class are valid, we
2462 // can't use it. For example, 64-bit reg classes on 32-bit targets.
2463 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
2465 if (TLI.isTypeLegal(*I)) {
2466 // If we have already found this register in a different register class,
2467 // choose the one with the largest VT specified. For example, on
2468 // PowerPC, we favor f64 register classes over f32.
2469 if (FoundVT == MVT::Other ||
2470 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) {
2477 if (ThisVT == MVT::Other) continue;
2479 // NOTE: This isn't ideal. In particular, this might allocate the
2480 // frame pointer in functions that need it (due to them not being taken
2481 // out of allocation, because a variable sized allocation hasn't been seen
2482 // yet). This is a slight code pessimization, but should still work.
2483 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
2484 E = RC->allocation_order_end(MF); I != E; ++I)
2486 // We found a matching register class. Keep looking at others in case
2487 // we find one with larger registers that this physreg is also in.
2496 RegsForValue SelectionDAGLowering::
2497 GetRegistersForValue(const std::string &ConstrCode,
2498 MVT::ValueType VT, bool isOutReg, bool isInReg,
2499 std::set<unsigned> &OutputRegs,
2500 std::set<unsigned> &InputRegs) {
2501 std::pair<unsigned, const TargetRegisterClass*> PhysReg =
2502 TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
2503 std::vector<unsigned> Regs;
2505 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
2506 MVT::ValueType RegVT;
2507 MVT::ValueType ValueVT = VT;
2509 // If this is a constraint for a specific physical register, like {r17},
2511 if (PhysReg.first) {
2512 if (VT == MVT::Other)
2513 ValueVT = *PhysReg.second->vt_begin();
2515 // Get the actual register value type. This is important, because the user
2516 // may have asked for (e.g.) the AX register in i32 type. We need to
2517 // remember that AX is actually i16 to get the right extension.
2518 RegVT = *PhysReg.second->vt_begin();
2520 // This is a explicit reference to a physical register.
2521 Regs.push_back(PhysReg.first);
2523 // If this is an expanded reference, add the rest of the regs to Regs.
2525 TargetRegisterClass::iterator I = PhysReg.second->begin();
2526 TargetRegisterClass::iterator E = PhysReg.second->end();
2527 for (; *I != PhysReg.first; ++I)
2528 assert(I != E && "Didn't find reg!");
2530 // Already added the first reg.
2532 for (; NumRegs; --NumRegs, ++I) {
2533 assert(I != E && "Ran out of registers to allocate!");
2537 return RegsForValue(Regs, RegVT, ValueVT);
2540 // Otherwise, if this was a reference to an LLVM register class, create vregs
2541 // for this reference.
2542 std::vector<unsigned> RegClassRegs;
2543 if (PhysReg.second) {
2544 // If this is an early clobber or tied register, our regalloc doesn't know
2545 // how to maintain the constraint. If it isn't, go ahead and create vreg
2546 // and let the regalloc do the right thing.
2547 if (!isOutReg || !isInReg) {
2548 if (VT == MVT::Other)
2549 ValueVT = *PhysReg.second->vt_begin();
2550 RegVT = *PhysReg.second->vt_begin();
2552 // Create the appropriate number of virtual registers.
2553 SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
2554 for (; NumRegs; --NumRegs)
2555 Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
2557 return RegsForValue(Regs, RegVT, ValueVT);
2560 // Otherwise, we can't allocate it. Let the code below figure out how to
2561 // maintain these constraints.
2562 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end());
2565 // This is a reference to a register class that doesn't directly correspond
2566 // to an LLVM register class. Allocate NumRegs consecutive, available,
2567 // registers from the class.
2568 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
2571 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
2572 MachineFunction &MF = *CurMBB->getParent();
2573 unsigned NumAllocated = 0;
2574 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
2575 unsigned Reg = RegClassRegs[i];
2576 // See if this register is available.
2577 if ((isOutReg && OutputRegs.count(Reg)) || // Already used.
2578 (isInReg && InputRegs.count(Reg))) { // Already used.
2579 // Make sure we find consecutive registers.
2584 // Check to see if this register is allocatable (i.e. don't give out the
2586 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
2588 // Make sure we find consecutive registers.
2593 // Okay, this register is good, we can use it.
2596 // If we allocated enough consecutive
2597 if (NumAllocated == NumRegs) {
2598 unsigned RegStart = (i-NumAllocated)+1;
2599 unsigned RegEnd = i+1;
2600 // Mark all of the allocated registers used.
2601 for (unsigned i = RegStart; i != RegEnd; ++i) {
2602 unsigned Reg = RegClassRegs[i];
2603 Regs.push_back(Reg);
2604 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used.
2605 if (isInReg) InputRegs.insert(Reg); // Mark reg used.
2608 return RegsForValue(Regs, *RC->vt_begin(), VT);
2612 // Otherwise, we couldn't allocate enough registers for this.
2613 return RegsForValue();
2616 /// getConstraintGenerality - Return an integer indicating how general CT is.
2617 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
2619 default: assert(0 && "Unknown constraint type!");
2620 case TargetLowering::C_Other:
2621 case TargetLowering::C_Unknown:
2623 case TargetLowering::C_Register:
2625 case TargetLowering::C_RegisterClass:
2627 case TargetLowering::C_Memory:
2632 static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
2633 const TargetLowering &TLI) {
2634 assert(!C.empty() && "Must have at least one constraint");
2635 if (C.size() == 1) return C[0];
2637 std::string *Current = &C[0];
2638 // If we have multiple constraints, try to pick the most general one ahead
2639 // of time. This isn't a wonderful solution, but handles common cases.
2640 TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0][0]);
2641 for (unsigned j = 1, e = C.size(); j != e; ++j) {
2642 TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j][0]);
2643 if (getConstraintGenerality(ThisFlavor) >
2644 getConstraintGenerality(Flavor)) {
2645 // This constraint letter is more general than the previous one,
2647 Flavor = ThisFlavor;
2655 /// visitInlineAsm - Handle a call to an InlineAsm object.
2657 void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
2658 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
2660 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
2663 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
2664 std::vector<MVT::ValueType> ConstraintVTs;
2666 /// AsmNodeOperands - A list of pairs. The first element is a register, the
2667 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
2668 /// if it is a def of that register.
2669 std::vector<SDOperand> AsmNodeOperands;
2670 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
2671 AsmNodeOperands.push_back(AsmStr);
2673 SDOperand Chain = getRoot();
2676 // We fully assign registers here at isel time. This is not optimal, but
2677 // should work. For register classes that correspond to LLVM classes, we
2678 // could let the LLVM RA do its thing, but we currently don't. Do a prepass
2679 // over the constraints, collecting fixed registers that we know we can't use.
2680 std::set<unsigned> OutputRegs, InputRegs;
2682 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2683 std::string ConstraintCode =
2684 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2686 MVT::ValueType OpVT;
2688 // Compute the value type for each operand and add it to ConstraintVTs.
2689 switch (Constraints[i].Type) {
2690 case InlineAsm::isOutput:
2691 if (!Constraints[i].isIndirectOutput) {
2692 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2693 OpVT = TLI.getValueType(I.getType());
2695 const Type *OpTy = I.getOperand(OpNum)->getType();
2696 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
2697 OpNum++; // Consumes a call operand.
2700 case InlineAsm::isInput:
2701 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
2702 OpNum++; // Consumes a call operand.
2704 case InlineAsm::isClobber:
2709 ConstraintVTs.push_back(OpVT);
2711 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
2712 continue; // Not assigned a fixed reg.
2714 // Build a list of regs that this operand uses. This always has a single
2715 // element for promoted/expanded operands.
2716 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
2718 OutputRegs, InputRegs);
2720 switch (Constraints[i].Type) {
2721 case InlineAsm::isOutput:
2722 // We can't assign any other output to this register.
2723 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2724 // If this is an early-clobber output, it cannot be assigned to the same
2725 // value as the input reg.
2726 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2727 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2729 case InlineAsm::isInput:
2730 // We can't assign any other input to this register.
2731 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2733 case InlineAsm::isClobber:
2734 // Clobbered regs cannot be used as inputs or outputs.
2735 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2736 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
2741 // Loop over all of the inputs, copying the operand values into the
2742 // appropriate registers and processing the output regs.
2743 RegsForValue RetValRegs;
2744 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
2747 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
2748 std::string ConstraintCode =
2749 GetMostGeneralConstraint(Constraints[i].Codes, TLI);
2751 switch (Constraints[i].Type) {
2752 case InlineAsm::isOutput: {
2753 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
2754 if (ConstraintCode.size() == 1) // not a physreg name.
2755 CTy = TLI.getConstraintType(ConstraintCode[0]);
2757 if (CTy == TargetLowering::C_Memory) {
2759 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
2761 // Check that the operand (the address to store to) isn't a float.
2762 if (!MVT::isInteger(InOperandVal.getValueType()))
2763 assert(0 && "MATCH FAIL!");
2765 if (!Constraints[i].isIndirectOutput)
2766 assert(0 && "MATCH FAIL!");
2768 OpNum++; // Consumes a call operand.
2770 // Extend/truncate to the right pointer type if needed.
2771 MVT::ValueType PtrType = TLI.getPointerTy();
2772 if (InOperandVal.getValueType() < PtrType)
2773 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
2774 else if (InOperandVal.getValueType() > PtrType)
2775 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
2777 // Add information to the INLINEASM node to know about this output.
2778 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
2779 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
2780 AsmNodeOperands.push_back(InOperandVal);
2784 // Otherwise, this is a register output.
2785 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
2787 // If this is an early-clobber output, or if there is an input
2788 // constraint that matches this, we need to reserve the input register
2789 // so no other inputs allocate to it.
2790 bool UsesInputRegister = false;
2791 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
2792 UsesInputRegister = true;
2794 // Copy the output from the appropriate register. Find a register that
2797 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
2798 true, UsesInputRegister,
2799 OutputRegs, InputRegs);
2800 if (Regs.Regs.empty()) {
2801 cerr << "Couldn't allocate output reg for contraint '"
2802 << ConstraintCode << "'!\n";
2806 if (!Constraints[i].isIndirectOutput) {
2807 assert(RetValRegs.Regs.empty() &&
2808 "Cannot have multiple output constraints yet!");
2809 assert(I.getType() != Type::VoidTy && "Bad inline asm!");
2812 IndirectStoresToEmit.push_back(std::make_pair(Regs,
2813 I.getOperand(OpNum)));
2814 OpNum++; // Consumes a call operand.
2817 // Add information to the INLINEASM node to know that this register is
2819 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
2822 case InlineAsm::isInput: {
2823 SDOperand InOperandVal = getValue(I.getOperand(OpNum));
2824 OpNum++; // Consumes a call operand.
2826 if (isdigit(ConstraintCode[0])) { // Matching constraint?
2827 // If this is required to match an output register we have already set,
2828 // just use its register.
2829 unsigned OperandNo = atoi(ConstraintCode.c_str());
2831 // Scan until we find the definition we already emitted of this operand.
2832 // When we find it, create a RegsForValue operand.
2833 unsigned CurOp = 2; // The first operand.
2834 for (; OperandNo; --OperandNo) {
2835 // Advance to the next operand.
2837 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
2838 assert(((NumOps & 7) == 2 /*REGDEF*/ ||
2839 (NumOps & 7) == 4 /*MEM*/) &&
2840 "Skipped past definitions?");
2841 CurOp += (NumOps>>3)+1;
2845 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue();
2846 if ((NumOps & 7) == 2 /*REGDEF*/) {
2847 // Add NumOps>>3 registers to MatchedRegs.
2848 RegsForValue MatchedRegs;
2849 MatchedRegs.ValueVT = InOperandVal.getValueType();
2850 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType();
2851 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) {
2853 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg();
2854 MatchedRegs.Regs.push_back(Reg);
2857 // Use the produced MatchedRegs object to
2858 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
2859 TLI.getPointerTy());
2860 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
2863 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!");
2864 assert(0 && "matching constraints for memory operands unimp");
2868 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
2869 if (ConstraintCode.size() == 1) // not a physreg name.
2870 CTy = TLI.getConstraintType(ConstraintCode[0]);
2872 if (CTy == TargetLowering::C_Other) {
2873 InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
2874 ConstraintCode[0], DAG);
2875 if (!InOperandVal.Val) {
2876 cerr << "Invalid operand for inline asm constraint '"
2877 << ConstraintCode << "'!\n";
2881 // Add information to the INLINEASM node to know about this input.
2882 unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
2883 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
2884 AsmNodeOperands.push_back(InOperandVal);
2886 } else if (CTy == TargetLowering::C_Memory) {
2889 // If the operand is a float, spill to a constant pool entry to get its
2891 if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
2892 InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
2894 if (!MVT::isInteger(InOperandVal.getValueType())) {
2895 cerr << "Match failed, cannot handle this yet!\n";
2896 InOperandVal.Val->dump();
2900 // Extend/truncate to the right pointer type if needed.
2901 MVT::ValueType PtrType = TLI.getPointerTy();
2902 if (InOperandVal.getValueType() < PtrType)
2903 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
2904 else if (InOperandVal.getValueType() > PtrType)
2905 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
2907 // Add information to the INLINEASM node to know about this input.
2908 unsigned ResOpType = 4/*MEM*/ | (1 << 3);
2909 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
2910 AsmNodeOperands.push_back(InOperandVal);
2914 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
2916 // Copy the input into the appropriate registers.
2917 RegsForValue InRegs =
2918 GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
2919 false, true, OutputRegs, InputRegs);
2920 // FIXME: should be match fail.
2921 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
2923 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
2925 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
2928 case InlineAsm::isClobber: {
2929 RegsForValue ClobberedRegs =
2930 GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
2931 OutputRegs, InputRegs);
2932 // Add the clobbered value to the operand list, so that the register
2933 // allocator is aware that the physreg got clobbered.
2934 if (!ClobberedRegs.Regs.empty())
2935 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
2941 // Finish up input operands.
2942 AsmNodeOperands[0] = Chain;
2943 if (Flag.Val) AsmNodeOperands.push_back(Flag);
2945 Chain = DAG.getNode(ISD::INLINEASM,
2946 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2,
2947 &AsmNodeOperands[0], AsmNodeOperands.size());
2948 Flag = Chain.getValue(1);
2950 // If this asm returns a register value, copy the result from that register
2951 // and set it as the value of the call.
2952 if (!RetValRegs.Regs.empty())
2953 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
2955 std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
2957 // Process indirect outputs, first output all of the flagged copies out of
2959 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
2960 RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
2961 Value *Ptr = IndirectStoresToEmit[i].second;
2962 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
2963 StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
2966 // Emit the non-flagged stores from the physregs.
2967 SmallVector<SDOperand, 8> OutChains;
2968 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
2969 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
2970 getValue(StoresToEmit[i].second),
2971 StoresToEmit[i].second, 0));
2972 if (!OutChains.empty())
2973 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
2974 &OutChains[0], OutChains.size());
2979 void SelectionDAGLowering::visitMalloc(MallocInst &I) {
2980 SDOperand Src = getValue(I.getOperand(0));
2982 MVT::ValueType IntPtr = TLI.getPointerTy();
2984 if (IntPtr < Src.getValueType())
2985 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
2986 else if (IntPtr > Src.getValueType())
2987 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
2989 // Scale the source by the type size.
2990 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
2991 Src = DAG.getNode(ISD::MUL, Src.getValueType(),
2992 Src, getIntPtrConstant(ElementSize));
2994 TargetLowering::ArgListTy Args;
2995 TargetLowering::ArgListEntry Entry;
2997 Entry.Ty = TLI.getTargetData()->getIntPtrType();
2998 Args.push_back(Entry);
3000 std::pair<SDOperand,SDOperand> Result =
3001 TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true,
3002 DAG.getExternalSymbol("malloc", IntPtr),
3004 setValue(&I, Result.first); // Pointers always fit in registers
3005 DAG.setRoot(Result.second);
3008 void SelectionDAGLowering::visitFree(FreeInst &I) {
3009 TargetLowering::ArgListTy Args;
3010 TargetLowering::ArgListEntry Entry;
3011 Entry.Node = getValue(I.getOperand(0));
3012 Entry.Ty = TLI.getTargetData()->getIntPtrType();
3013 Args.push_back(Entry);
3014 MVT::ValueType IntPtr = TLI.getPointerTy();
3015 std::pair<SDOperand,SDOperand> Result =
3016 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true,
3017 DAG.getExternalSymbol("free", IntPtr), Args, DAG);
3018 DAG.setRoot(Result.second);
3021 // InsertAtEndOfBasicBlock - This method should be implemented by targets that
3022 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These
3023 // instructions are special in various ways, which require special support to
3024 // insert. The specified MachineInstr is created but not inserted into any
3025 // basic blocks, and the scheduler passes ownership of it to this method.
3026 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
3027 MachineBasicBlock *MBB) {
3028 cerr << "If a target marks an instruction with "
3029 << "'usesCustomDAGSchedInserter', it must implement "
3030 << "TargetLowering::InsertAtEndOfBasicBlock!\n";
3035 void SelectionDAGLowering::visitVAStart(CallInst &I) {
3036 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(),
3037 getValue(I.getOperand(1)),
3038 DAG.getSrcValue(I.getOperand(1))));
3041 void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
3042 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(),
3043 getValue(I.getOperand(0)),
3044 DAG.getSrcValue(I.getOperand(0)));
3046 DAG.setRoot(V.getValue(1));
3049 void SelectionDAGLowering::visitVAEnd(CallInst &I) {
3050 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(),
3051 getValue(I.getOperand(1)),
3052 DAG.getSrcValue(I.getOperand(1))));
3055 void SelectionDAGLowering::visitVACopy(CallInst &I) {
3056 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(),
3057 getValue(I.getOperand(1)),
3058 getValue(I.getOperand(2)),
3059 DAG.getSrcValue(I.getOperand(1)),
3060 DAG.getSrcValue(I.getOperand(2))));
3063 /// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
3064 /// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
3065 static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
3066 unsigned &i, SelectionDAG &DAG,
3067 TargetLowering &TLI) {
3068 if (TLI.getTypeAction(VT) != TargetLowering::Expand)
3069 return SDOperand(Arg, i++);
3071 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3072 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3074 return DAG.getNode(ISD::BIT_CONVERT, VT,
3075 ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
3076 } else if (NumVals == 2) {
3077 SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3078 SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
3079 if (!TLI.isLittleEndian())
3081 return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
3083 // Value scalarized into many values. Unimp for now.
3084 assert(0 && "Cannot expand i64 -> i16 yet!");
3089 /// TargetLowering::LowerArguments - This is the default LowerArguments
3090 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all
3091 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be
3092 /// integrated into SDISel.
3093 std::vector<SDOperand>
3094 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
3095 const FunctionType *FTy = F.getFunctionType();
3096 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
3097 std::vector<SDOperand> Ops;
3098 Ops.push_back(DAG.getRoot());
3099 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy()));
3100 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy()));
3102 // Add one result value for each formal argument.
3103 std::vector<MVT::ValueType> RetVals;
3105 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
3107 MVT::ValueType VT = getValueType(I->getType());
3108 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3109 unsigned OriginalAlignment =
3110 getTargetData()->getABITypeAlignment(I->getType());
3112 // FIXME: Distinguish between a formal with no [sz]ext attribute from one
3113 // that is zero extended!
3114 if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
3115 Flags &= ~(ISD::ParamFlags::SExt);
3116 if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
3117 Flags |= ISD::ParamFlags::SExt;
3118 if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
3119 Flags |= ISD::ParamFlags::InReg;
3120 if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
3121 Flags |= ISD::ParamFlags::StructReturn;
3122 Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
3124 switch (getTypeAction(VT)) {
3125 default: assert(0 && "Unknown type action!");
3127 RetVals.push_back(VT);
3128 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3131 RetVals.push_back(getTypeToTransformTo(VT));
3132 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3135 if (VT != MVT::Vector) {
3136 // If this is a large integer, it needs to be broken up into small
3137 // integers. Figure out what the destination type is and how many small
3138 // integers it turns into.
3139 MVT::ValueType NVT = getTypeToExpandTo(VT);
3140 unsigned NumVals = getNumElements(VT);
3141 for (unsigned i = 0; i != NumVals; ++i) {
3142 RetVals.push_back(NVT);
3143 // if it isn't first piece, alignment must be 1
3145 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3146 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3147 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3150 // Otherwise, this is a vector type. We only support legal vectors
3152 unsigned NumElems = cast<VectorType>(I->getType())->getNumElements();
3153 const Type *EltTy = cast<VectorType>(I->getType())->getElementType();
3155 // Figure out if there is a Packed type corresponding to this Vector
3156 // type. If so, convert to the vector type.
3157 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3158 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3159 RetVals.push_back(TVT);
3160 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3162 assert(0 && "Don't support illegal by-val vector arguments yet!");
3169 RetVals.push_back(MVT::Other);
3172 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
3173 DAG.getNodeValueTypes(RetVals), RetVals.size(),
3174 &Ops[0], Ops.size()).Val;
3176 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
3178 // Set up the return result vector.
3182 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
3184 MVT::ValueType VT = getValueType(I->getType());
3186 switch (getTypeAction(VT)) {
3187 default: assert(0 && "Unknown type action!");
3189 Ops.push_back(SDOperand(Result, i++));
3192 SDOperand Op(Result, i++);
3193 if (MVT::isInteger(VT)) {
3194 if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
3195 Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
3196 DAG.getValueType(VT));
3197 else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
3198 Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
3199 DAG.getValueType(VT));
3200 Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
3202 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3203 Op = DAG.getNode(ISD::FP_ROUND, VT, Op);
3209 if (VT != MVT::Vector) {
3210 // If this is a large integer or a floating point node that needs to be
3211 // expanded, it needs to be reassembled from small integers. Figure out
3212 // what the source elt type is and how many small integers it is.
3213 Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
3215 // Otherwise, this is a vector type. We only support legal vectors
3217 const VectorType *PTy = cast<VectorType>(I->getType());
3218 unsigned NumElems = PTy->getNumElements();
3219 const Type *EltTy = PTy->getElementType();
3221 // Figure out if there is a Packed type corresponding to this Vector
3222 // type. If so, convert to the vector type.
3223 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3224 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3225 SDOperand N = SDOperand(Result, i++);
3226 // Handle copies from generic vectors to registers.
3227 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
3228 DAG.getConstant(NumElems, MVT::i32),
3229 DAG.getValueType(getValueType(EltTy)));
3232 assert(0 && "Don't support illegal by-val vector arguments yet!");
3243 /// ExpandScalarCallArgs - Recursively expand call argument node by
3244 /// bit_converting it or extract a pair of elements from the larger node.
3245 static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
3247 SmallVector<SDOperand, 32> &Ops,
3249 TargetLowering &TLI,
3250 bool isFirst = true) {
3252 if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
3253 // if it isn't first piece, alignment must be 1
3255 Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
3256 (1 << ISD::ParamFlags::OrigAlignmentOffs);
3258 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3262 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
3263 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
3265 Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
3266 ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI, isFirst);
3267 } else if (NumVals == 2) {
3268 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3269 DAG.getConstant(0, TLI.getPointerTy()));
3270 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
3271 DAG.getConstant(1, TLI.getPointerTy()));
3272 if (!TLI.isLittleEndian())
3274 ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI, isFirst);
3275 ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI, false);
3277 // Value scalarized into many values. Unimp for now.
3278 assert(0 && "Cannot expand i64 -> i16 yet!");
3282 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
3283 /// implementation, which just inserts an ISD::CALL node, which is later custom
3284 /// lowered by the target to something concrete. FIXME: When all targets are
3285 /// migrated to using ISD::CALL, this hook should be integrated into SDISel.
3286 std::pair<SDOperand, SDOperand>
3287 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
3288 bool RetTyIsSigned, bool isVarArg,
3289 unsigned CallingConv, bool isTailCall,
3291 ArgListTy &Args, SelectionDAG &DAG) {
3292 SmallVector<SDOperand, 32> Ops;
3293 Ops.push_back(Chain); // Op#0 - Chain
3294 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC
3295 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg
3296 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail
3297 Ops.push_back(Callee);
3299 // Handle all of the outgoing arguments.
3300 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
3301 MVT::ValueType VT = getValueType(Args[i].Ty);
3302 SDOperand Op = Args[i].Node;
3303 unsigned Flags = ISD::ParamFlags::NoFlagSet;
3304 unsigned OriginalAlignment =
3305 getTargetData()->getABITypeAlignment(Args[i].Ty);
3308 Flags |= ISD::ParamFlags::SExt;
3310 Flags |= ISD::ParamFlags::ZExt;
3311 if (Args[i].isInReg)
3312 Flags |= ISD::ParamFlags::InReg;
3314 Flags |= ISD::ParamFlags::StructReturn;
3315 Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
3317 switch (getTypeAction(VT)) {
3318 default: assert(0 && "Unknown type action!");
3321 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3324 if (MVT::isInteger(VT)) {
3327 ExtOp = ISD::SIGN_EXTEND;
3328 else if (Args[i].isZExt)
3329 ExtOp = ISD::ZERO_EXTEND;
3331 ExtOp = ISD::ANY_EXTEND;
3332 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
3334 assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
3335 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
3338 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3341 if (VT != MVT::Vector) {
3342 // If this is a large integer, it needs to be broken down into small
3343 // integers. Figure out what the source elt type is and how many small
3345 ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
3347 // Otherwise, this is a vector type. We only support legal vectors
3349 const VectorType *PTy = cast<VectorType>(Args[i].Ty);
3350 unsigned NumElems = PTy->getNumElements();
3351 const Type *EltTy = PTy->getElementType();
3353 // Figure out if there is a Packed type corresponding to this Vector
3354 // type. If so, convert to the vector type.
3355 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3356 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3357 // Insert a VBIT_CONVERT of the MVT::Vector type to the vector type.
3358 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
3360 Ops.push_back(DAG.getConstant(Flags, MVT::i32));
3362 assert(0 && "Don't support illegal by-val vector call args yet!");
3370 // Figure out the result value types.
3371 SmallVector<MVT::ValueType, 4> RetTys;
3373 if (RetTy != Type::VoidTy) {
3374 MVT::ValueType VT = getValueType(RetTy);
3375 switch (getTypeAction(VT)) {
3376 default: assert(0 && "Unknown type action!");
3378 RetTys.push_back(VT);
3381 RetTys.push_back(getTypeToTransformTo(VT));
3384 if (VT != MVT::Vector) {
3385 // If this is a large integer, it needs to be reassembled from small
3386 // integers. Figure out what the source elt type is and how many small
3388 MVT::ValueType NVT = getTypeToExpandTo(VT);
3389 unsigned NumVals = getNumElements(VT);
3390 for (unsigned i = 0; i != NumVals; ++i)
3391 RetTys.push_back(NVT);
3393 // Otherwise, this is a vector type. We only support legal vectors
3395 const VectorType *PTy = cast<VectorType>(RetTy);
3396 unsigned NumElems = PTy->getNumElements();
3397 const Type *EltTy = PTy->getElementType();
3399 // Figure out if there is a Packed type corresponding to this Vector
3400 // type. If so, convert to the vector type.
3401 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
3402 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3403 RetTys.push_back(TVT);
3405 assert(0 && "Don't support illegal by-val vector call results yet!");
3412 RetTys.push_back(MVT::Other); // Always has a chain.
3414 // Finally, create the CALL node.
3415 SDOperand Res = DAG.getNode(ISD::CALL,
3416 DAG.getVTList(&RetTys[0], RetTys.size()),
3417 &Ops[0], Ops.size());
3419 // This returns a pair of operands. The first element is the
3420 // return value for the function (if RetTy is not VoidTy). The second
3421 // element is the outgoing token chain.
3423 if (RetTys.size() != 1) {
3424 MVT::ValueType VT = getValueType(RetTy);
3425 if (RetTys.size() == 2) {
3428 // If this value was promoted, truncate it down.
3429 if (ResVal.getValueType() != VT) {
3430 if (VT == MVT::Vector) {
3431 // Insert a VBITCONVERT to convert from the packed result type to the
3432 // MVT::Vector type.
3433 unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
3434 const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
3436 // Figure out if there is a Packed type corresponding to this Vector
3437 // type. If so, convert to the vector type.
3438 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
3439 if (TVT != MVT::Other && isTypeLegal(TVT)) {
3440 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
3441 // "N x PTyElementVT" MVT::Vector type.
3442 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
3443 DAG.getConstant(NumElems, MVT::i32),
3444 DAG.getValueType(getValueType(EltTy)));
3448 } else if (MVT::isInteger(VT)) {
3449 unsigned AssertOp = ISD::AssertSext;
3451 AssertOp = ISD::AssertZext;
3452 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
3453 DAG.getValueType(VT));
3454 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
3456 assert(MVT::isFloatingPoint(VT));
3457 if (getTypeAction(VT) == Expand)
3458 ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
3460 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
3463 } else if (RetTys.size() == 3) {
3464 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
3465 Res.getValue(0), Res.getValue(1));
3468 assert(0 && "Case not handled yet!");
3472 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
3475 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
3476 assert(0 && "LowerOperation not implemented for this target!");
3481 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op,
3482 SelectionDAG &DAG) {
3483 assert(0 && "CustomPromoteOperation not implemented for this target!");
3488 /// getMemsetValue - Vectorized representation of the memset value
3490 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
3491 SelectionDAG &DAG) {
3492 MVT::ValueType CurVT = VT;
3493 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3494 uint64_t Val = C->getValue() & 255;
3496 while (CurVT != MVT::i8) {
3497 Val = (Val << Shift) | Val;
3499 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3501 return DAG.getConstant(Val, VT);
3503 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
3505 while (CurVT != MVT::i8) {
3507 DAG.getNode(ISD::OR, VT,
3508 DAG.getNode(ISD::SHL, VT, Value,
3509 DAG.getConstant(Shift, MVT::i8)), Value);
3511 CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
3518 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3519 /// used when a memcpy is turned into a memset when the source is a constant
3521 static SDOperand getMemsetStringVal(MVT::ValueType VT,
3522 SelectionDAG &DAG, TargetLowering &TLI,
3523 std::string &Str, unsigned Offset) {
3525 unsigned MSB = getSizeInBits(VT) / 8;
3526 if (TLI.isLittleEndian())
3527 Offset = Offset + MSB - 1;
3528 for (unsigned i = 0; i != MSB; ++i) {
3529 Val = (Val << 8) | (unsigned char)Str[Offset];
3530 Offset += TLI.isLittleEndian() ? -1 : 1;
3532 return DAG.getConstant(Val, VT);
3535 /// getMemBasePlusOffset - Returns base and offset node for the
3536 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
3537 SelectionDAG &DAG, TargetLowering &TLI) {
3538 MVT::ValueType VT = Base.getValueType();
3539 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
3542 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
3543 /// to replace the memset / memcpy is below the threshold. It also returns the
3544 /// types of the sequence of memory ops to perform memset / memcpy.
3545 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
3546 unsigned Limit, uint64_t Size,
3547 unsigned Align, TargetLowering &TLI) {
3550 if (TLI.allowsUnalignedMemoryAccesses()) {
3553 switch (Align & 7) {
3569 MVT::ValueType LVT = MVT::i64;
3570 while (!TLI.isTypeLegal(LVT))
3571 LVT = (MVT::ValueType)((unsigned)LVT - 1);
3572 assert(MVT::isInteger(LVT));
3577 unsigned NumMemOps = 0;
3579 unsigned VTSize = getSizeInBits(VT) / 8;
3580 while (VTSize > Size) {
3581 VT = (MVT::ValueType)((unsigned)VT - 1);
3584 assert(MVT::isInteger(VT));
3586 if (++NumMemOps > Limit)
3588 MemOps.push_back(VT);
3595 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
3596 SDOperand Op1 = getValue(I.getOperand(1));
3597 SDOperand Op2 = getValue(I.getOperand(2));
3598 SDOperand Op3 = getValue(I.getOperand(3));
3599 SDOperand Op4 = getValue(I.getOperand(4));
3600 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
3601 if (Align == 0) Align = 1;
3603 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
3604 std::vector<MVT::ValueType> MemOps;
3606 // Expand memset / memcpy to a series of load / store ops
3607 // if the size operand falls below a certain threshold.
3608 SmallVector<SDOperand, 8> OutChains;
3610 default: break; // Do nothing for now.
3612 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
3613 Size->getValue(), Align, TLI)) {
3614 unsigned NumMemOps = MemOps.size();
3615 unsigned Offset = 0;
3616 for (unsigned i = 0; i < NumMemOps; i++) {
3617 MVT::ValueType VT = MemOps[i];
3618 unsigned VTSize = getSizeInBits(VT) / 8;
3619 SDOperand Value = getMemsetValue(Op2, VT, DAG);
3620 SDOperand Store = DAG.getStore(getRoot(), Value,
3621 getMemBasePlusOffset(Op1, Offset, DAG, TLI),
3622 I.getOperand(1), Offset);
3623 OutChains.push_back(Store);
3630 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(),
3631 Size->getValue(), Align, TLI)) {
3632 unsigned NumMemOps = MemOps.size();
3633 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0;
3634 GlobalAddressSDNode *G = NULL;
3636 bool CopyFromStr = false;
3638 if (Op2.getOpcode() == ISD::GlobalAddress)
3639 G = cast<GlobalAddressSDNode>(Op2);
3640 else if (Op2.getOpcode() == ISD::ADD &&
3641 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3642 Op2.getOperand(1).getOpcode() == ISD::Constant) {
3643 G = cast<GlobalAddressSDNode>(Op2.getOperand(0));
3644 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue();
3647 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3648 if (GV && GV->isConstant()) {
3649 Str = GV->getStringValue(false);
3657 for (unsigned i = 0; i < NumMemOps; i++) {
3658 MVT::ValueType VT = MemOps[i];
3659 unsigned VTSize = getSizeInBits(VT) / 8;
3660 SDOperand Value, Chain, Store;
3663 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
3666 DAG.getStore(Chain, Value,
3667 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3668 I.getOperand(1), DstOff);
3670 Value = DAG.getLoad(VT, getRoot(),
3671 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
3672 I.getOperand(2), SrcOff);
3673 Chain = Value.getValue(1);
3675 DAG.getStore(Chain, Value,
3676 getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
3677 I.getOperand(1), DstOff);
3679 OutChains.push_back(Store);
3688 if (!OutChains.empty()) {
3689 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
3690 &OutChains[0], OutChains.size()));
3695 DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
3698 //===----------------------------------------------------------------------===//
3699 // SelectionDAGISel code
3700 //===----------------------------------------------------------------------===//
3702 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
3703 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
3706 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
3707 // FIXME: we only modify the CFG to split critical edges. This
3708 // updates dom and loop info.
3709 AU.addRequired<AliasAnalysis>();
3710 AU.addRequired<LoopInfo>();
3711 AU.setPreservesAll();
3715 /// OptimizeNoopCopyExpression - We have determined that the specified cast
3716 /// instruction is a noop copy (e.g. it's casting from one pointer type to
3717 /// another, int->uint, or int->sbyte on PPC.
3719 /// Return true if any changes are made.
3720 static bool OptimizeNoopCopyExpression(CastInst *CI) {
3721 BasicBlock *DefBB = CI->getParent();
3723 /// InsertedCasts - Only insert a cast in each block once.
3724 std::map<BasicBlock*, CastInst*> InsertedCasts;
3726 bool MadeChange = false;
3727 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
3729 Use &TheUse = UI.getUse();
3730 Instruction *User = cast<Instruction>(*UI);
3732 // Figure out which BB this cast is used in. For PHI's this is the
3733 // appropriate predecessor block.
3734 BasicBlock *UserBB = User->getParent();
3735 if (PHINode *PN = dyn_cast<PHINode>(User)) {
3736 unsigned OpVal = UI.getOperandNo()/2;
3737 UserBB = PN->getIncomingBlock(OpVal);
3740 // Preincrement use iterator so we don't invalidate it.
3743 // If this user is in the same block as the cast, don't change the cast.
3744 if (UserBB == DefBB) continue;
3746 // If we have already inserted a cast into this block, use it.
3747 CastInst *&InsertedCast = InsertedCasts[UserBB];
3749 if (!InsertedCast) {
3750 BasicBlock::iterator InsertPt = UserBB->begin();
3751 while (isa<PHINode>(InsertPt)) ++InsertPt;
3754 CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
3759 // Replace a use of the cast with a use of the new casat.
3760 TheUse = InsertedCast;
3763 // If we removed all uses, nuke the cast.
3764 if (CI->use_empty())
3765 CI->eraseFromParent();
3770 /// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset,
3771 /// casting to the type of GEPI.
3772 static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB,
3773 Instruction *GEPI, Value *Ptr,
3775 if (V) return V; // Already computed.
3777 // Figure out the insertion point
3778 BasicBlock::iterator InsertPt;
3779 if (BB == GEPI->getParent()) {
3780 // If GEP is already inserted into BB, insert right after the GEP.
3784 // Otherwise, insert at the top of BB, after any PHI nodes
3785 InsertPt = BB->begin();
3786 while (isa<PHINode>(InsertPt)) ++InsertPt;
3789 // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into
3790 // BB so that there is only one value live across basic blocks (the cast
3792 if (CastInst *CI = dyn_cast<CastInst>(Ptr))
3793 if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType()))
3794 Ptr = CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(),
3797 // Add the offset, cast it to the right type.
3798 Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt);
3799 // Ptr is an integer type, GEPI is pointer type ==> IntToPtr
3800 return V = CastInst::create(Instruction::IntToPtr, Ptr, GEPI->getType(),
3804 /// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to
3805 /// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One
3806 /// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's
3807 /// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to
3808 /// sink PtrOffset into user blocks where doing so will likely allow us to fold
3809 /// the constant add into a load or store instruction. Additionally, if a user
3810 /// is a pointer-pointer cast, we look through it to find its users.
3811 static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr,
3812 Constant *PtrOffset, BasicBlock *DefBB,
3813 GetElementPtrInst *GEPI,
3814 std::map<BasicBlock*,Instruction*> &InsertedExprs) {
3815 while (!RepPtr->use_empty()) {
3816 Instruction *User = cast<Instruction>(RepPtr->use_back());
3818 // If the user is a Pointer-Pointer cast, recurse. Only BitCast can be
3819 // used for a Pointer-Pointer cast.
3820 if (isa<BitCastInst>(User)) {
3821 ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
3823 // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we
3824 // could invalidate an iterator.
3825 User->setOperand(0, UndefValue::get(RepPtr->getType()));
3829 // If this is a load of the pointer, or a store through the pointer, emit
3830 // the increment into the load/store block.
3831 Instruction *NewVal;
3832 if (isa<LoadInst>(User) ||
3833 (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) {
3834 NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()],
3835 User->getParent(), GEPI,
3838 // If this use is not foldable into the addressing mode, use a version
3839 // emitted in the GEP block.
3840 NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI,
3844 if (GEPI->getType() != RepPtr->getType()) {
3845 BasicBlock::iterator IP = NewVal;
3847 // NewVal must be a GEP which must be pointer type, so BitCast
3848 NewVal = new BitCastInst(NewVal, RepPtr->getType(), "", IP);
3850 User->replaceUsesOfWith(RepPtr, NewVal);
3855 /// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction
3856 /// selection, we want to be a bit careful about some things. In particular, if
3857 /// we have a GEP instruction that is used in a different block than it is
3858 /// defined, the addressing expression of the GEP cannot be folded into loads or
3859 /// stores that use it. In this case, decompose the GEP and move constant
3860 /// indices into blocks that use it.
3861 static bool OptimizeGEPExpression(GetElementPtrInst *GEPI,
3862 const TargetData *TD) {
3863 // If this GEP is only used inside the block it is defined in, there is no
3864 // need to rewrite it.
3865 bool isUsedOutsideDefBB = false;
3866 BasicBlock *DefBB = GEPI->getParent();
3867 for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end();
3869 if (cast<Instruction>(*UI)->getParent() != DefBB) {
3870 isUsedOutsideDefBB = true;
3874 if (!isUsedOutsideDefBB) return false;
3876 // If this GEP has no non-zero constant indices, there is nothing we can do,
3878 bool hasConstantIndex = false;
3879 bool hasVariableIndex = false;
3880 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
3881 E = GEPI->op_end(); OI != E; ++OI) {
3882 if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) {
3883 if (CI->getZExtValue()) {
3884 hasConstantIndex = true;
3888 hasVariableIndex = true;
3892 // If this is a "GEP X, 0, 0, 0", turn this into a cast.
3893 if (!hasConstantIndex && !hasVariableIndex) {
3894 /// The GEP operand must be a pointer, so must its result -> BitCast
3895 Value *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
3896 GEPI->getName(), GEPI);
3897 GEPI->replaceAllUsesWith(NC);
3898 GEPI->eraseFromParent();
3902 // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses.
3903 if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0)))
3906 // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the
3907 // constant offset (which we now know is non-zero) and deal with it later.
3908 uint64_t ConstantOffset = 0;
3909 const Type *UIntPtrTy = TD->getIntPtrType();
3910 Value *Ptr = new PtrToIntInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI);
3911 const Type *Ty = GEPI->getOperand(0)->getType();
3913 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
3914 E = GEPI->op_end(); OI != E; ++OI) {
3916 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
3917 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
3919 ConstantOffset += TD->getStructLayout(StTy)->getElementOffset(Field);
3920 Ty = StTy->getElementType(Field);
3922 Ty = cast<SequentialType>(Ty)->getElementType();
3924 // Handle constant subscripts.
3925 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
3926 if (CI->getZExtValue() == 0) continue;
3927 ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CI->getSExtValue();
3931 // Ptr = Ptr + Idx * ElementSize;
3933 // Cast Idx to UIntPtrTy if needed.
3934 Idx = CastInst::createIntegerCast(Idx, UIntPtrTy, true/*SExt*/, "", GEPI);
3936 uint64_t ElementSize = TD->getTypeSize(Ty);
3937 // Mask off bits that should not be set.
3938 ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
3939 Constant *SizeCst = ConstantInt::get(UIntPtrTy, ElementSize);
3941 // Multiply by the element size and add to the base.
3942 Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI);
3943 Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI);
3947 // Make sure that the offset fits in uintptr_t.
3948 ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
3949 Constant *PtrOffset = ConstantInt::get(UIntPtrTy, ConstantOffset);
3951 // Okay, we have now emitted all of the variable index parts to the BB that
3952 // the GEP is defined in. Loop over all of the using instructions, inserting
3953 // an "add Ptr, ConstantOffset" into each block that uses it and update the
3954 // instruction to use the newly computed value, making GEPI dead. When the
3955 // user is a load or store instruction address, we emit the add into the user
3956 // block, otherwise we use a canonical version right next to the gep (these
3957 // won't be foldable as addresses, so we might as well share the computation).
3959 std::map<BasicBlock*,Instruction*> InsertedExprs;
3960 ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
3962 // Finally, the GEP is dead, remove it.
3963 GEPI->eraseFromParent();
3968 /// isLoopInvariantInst - Returns true if all operands of the instruction are
3969 /// loop invariants in the specified loop.
3970 static bool isLoopInvariantInst(Instruction *I, Loop *L) {
3971 // The instruction is loop invariant if all of its operands are loop-invariant
3972 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
3973 if (!L->isLoopInvariant(I->getOperand(i)))
3978 /// SinkInvariantGEPIndex - If a GEP instruction has a variable index that has
3979 /// been hoisted out of the loop by LICM pass, sink it back into the use BB
3980 /// if it can be determined that the index computation can be folded into the
3981 /// addressing mode of the load / store uses.
3982 static bool SinkInvariantGEPIndex(BinaryOperator *BinOp, LoopInfo *loopInfo,
3983 const TargetLowering &TLI) {
3984 if (!EnableGEPIndexSink)
3987 // Only look at Add / Sub for now.
3988 if (BinOp->getOpcode() != Instruction::Add &&
3989 BinOp->getOpcode() != Instruction::Sub)
3992 /// InsertedOps - Only insert a duplicate in each block once.
3993 std::map<BasicBlock*, BinaryOperator*> InsertedOps;
3995 bool MadeChange = false;
3996 BasicBlock *DefBB = BinOp->getParent();
3997 for (Value::use_iterator UI = BinOp->use_begin(), E = BinOp->use_end();
3999 Instruction *User = cast<Instruction>(*UI);
4001 // Preincrement use iterator so we don't invalidate it.
4004 // Only look for GEP use in another block.
4005 if (User->getParent() == DefBB) continue;
4007 if (isa<GetElementPtrInst>(User)) {
4008 BasicBlock *UserBB = User->getParent();
4009 Loop *L = loopInfo->getLoopFor(UserBB);
4011 // Only sink if expression is a loop invariant in the use BB.
4012 if (L && isLoopInvariantInst(BinOp, L) && !User->use_empty()) {
4013 const Type *UseTy = NULL;
4014 // FIXME: We are assuming all the uses of the GEP will have the
4016 Instruction *GEPUser = cast<Instruction>(*User->use_begin());
4017 if (LoadInst *Load = dyn_cast<LoadInst>(GEPUser))
4018 UseTy = Load->getType();
4019 else if (StoreInst *Store = dyn_cast<StoreInst>(GEPUser))
4020 UseTy = Store->getOperand(0)->getType();
4022 // Check if it is possible to fold the expression to address mode.
4024 TLI.isLegalAddressExpression(Instruction::Add, BinOp->getOperand(0),
4025 BinOp->getOperand(1), UseTy)) {
4026 // Sink it into user block.
4027 BinaryOperator *&InsertedOp = InsertedOps[UserBB];
4029 BasicBlock::iterator InsertPt = UserBB->begin();
4030 while (isa<PHINode>(InsertPt)) ++InsertPt;
4033 BinaryOperator::create(BinOp->getOpcode(), BinOp->getOperand(0),
4034 BinOp->getOperand(1), "", InsertPt);
4037 User->replaceUsesOfWith(BinOp, InsertedOp);
4044 if (BinOp->use_empty())
4045 BinOp->eraseFromParent();
4051 /// SplitEdgeNicely - Split the critical edge from TI to it's specified
4052 /// successor if it will improve codegen. We only do this if the successor has
4053 /// phi nodes (otherwise critical edges are ok). If there is already another
4054 /// predecessor of the succ that is empty (and thus has no phi nodes), use it
4055 /// instead of introducing a new block.
4056 static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
4057 BasicBlock *TIBB = TI->getParent();
4058 BasicBlock *Dest = TI->getSuccessor(SuccNum);
4059 assert(isa<PHINode>(Dest->begin()) &&
4060 "This should only be called if Dest has a PHI!");
4062 /// TIPHIValues - This array is lazily computed to determine the values of
4063 /// PHIs in Dest that TI would provide.
4064 std::vector<Value*> TIPHIValues;
4066 // Check to see if Dest has any blocks that can be used as a split edge for
4068 for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) {
4069 BasicBlock *Pred = *PI;
4070 // To be usable, the pred has to end with an uncond branch to the dest.
4071 BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator());
4072 if (!PredBr || !PredBr->isUnconditional() ||
4073 // Must be empty other than the branch.
4074 &Pred->front() != PredBr)
4077 // Finally, since we know that Dest has phi nodes in it, we have to make
4078 // sure that jumping to Pred will have the same affect as going to Dest in
4079 // terms of PHI values.
4082 bool FoundMatch = true;
4083 for (BasicBlock::iterator I = Dest->begin();
4084 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) {
4085 if (PHINo == TIPHIValues.size())
4086 TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB));
4088 // If the PHI entry doesn't work, we can't use this pred.
4089 if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) {
4095 // If we found a workable predecessor, change TI to branch to Succ.
4097 Dest->removePredecessor(TIBB);
4098 TI->setSuccessor(SuccNum, Pred);
4103 SplitCriticalEdge(TI, SuccNum, P, true);
4107 bool SelectionDAGISel::runOnFunction(Function &Fn) {
4108 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
4109 RegMap = MF.getSSARegMap();
4110 DOUT << "\n\n\n=== " << Fn.getName() << "\n";
4112 LoopInfo *loopInfo = &getAnalysis<LoopInfo>();
4114 // First, split all critical edges.
4116 // In this pass we also look for GEP and cast instructions that are used
4117 // across basic blocks and rewrite them to improve basic-block-at-a-time
4120 bool MadeChange = true;
4121 while (MadeChange) {
4123 for (Function::iterator FNI = Fn.begin(), E = Fn.end(); FNI != E; ++FNI) {
4124 // Split all critical edges where the dest block has a PHI.
4125 TerminatorInst *BBTI = FNI->getTerminator();
4126 if (BBTI->getNumSuccessors() > 1) {
4127 for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i)
4128 if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) &&
4129 isCriticalEdge(BBTI, i, true))
4130 SplitEdgeNicely(BBTI, i, this);
4134 for (BasicBlock::iterator BBI = FNI->begin(), E = FNI->end(); BBI != E; ) {
4135 Instruction *I = BBI++;
4137 if (CallInst *CI = dyn_cast<CallInst>(I)) {
4138 // If we found an inline asm expession, and if the target knows how to
4139 // lower it to normal LLVM code, do so now.
4140 if (isa<InlineAsm>(CI->getCalledValue()))
4141 if (const TargetAsmInfo *TAI =
4142 TLI.getTargetMachine().getTargetAsmInfo()) {
4143 if (TAI->ExpandInlineAsm(CI))
4146 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
4147 MadeChange |= OptimizeGEPExpression(GEPI, TLI.getTargetData());
4148 } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
4149 // If the source of the cast is a constant, then this should have
4150 // already been constant folded. The only reason NOT to constant fold
4151 // it is if something (e.g. LSR) was careful to place the constant
4152 // evaluation in a block other than then one that uses it (e.g. to hoist
4153 // the address of globals out of a loop). If this is the case, we don't
4154 // want to forward-subst the cast.
4155 if (isa<Constant>(CI->getOperand(0)))
4158 // If this is a noop copy, sink it into user blocks to reduce the number
4159 // of virtual registers that must be created and coallesced.
4160 MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
4161 MVT::ValueType DstVT = TLI.getValueType(CI->getType());
4163 // This is an fp<->int conversion?
4164 if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT))
4167 // If this is an extension, it will be a zero or sign extension, which
4169 if (SrcVT < DstVT) continue;
4171 // If these values will be promoted, find out what they will be promoted
4172 // to. This helps us consider truncates on PPC as noop copies when they
4174 if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote)
4175 SrcVT = TLI.getTypeToTransformTo(SrcVT);
4176 if (TLI.getTypeAction(DstVT) == TargetLowering::Promote)
4177 DstVT = TLI.getTypeToTransformTo(DstVT);
4179 // If, after promotion, these are the same types, this is a noop copy.
4181 MadeChange |= OptimizeNoopCopyExpression(CI);
4182 } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I)) {
4183 MadeChange |= SinkInvariantGEPIndex(BinOp, loopInfo, TLI);
4189 FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
4191 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
4192 SelectBasicBlock(I, MF, FuncInfo);
4194 // Add function live-ins to entry block live-in set.
4195 BasicBlock *EntryBB = &Fn.getEntryBlock();
4196 BB = FuncInfo.MBBMap[EntryBB];
4197 if (!MF.livein_empty())
4198 for (MachineFunction::livein_iterator I = MF.livein_begin(),
4199 E = MF.livein_end(); I != E; ++I)
4200 BB->addLiveIn(I->first);
4205 SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V,
4207 SDOperand Op = getValue(V);
4208 assert((Op.getOpcode() != ISD::CopyFromReg ||
4209 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
4210 "Copy from a reg to the same reg!");
4212 // If this type is not legal, we must make sure to not create an invalid
4214 MVT::ValueType SrcVT = Op.getValueType();
4215 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
4216 if (SrcVT == DestVT) {
4217 return DAG.getCopyToReg(getRoot(), Reg, Op);
4218 } else if (SrcVT == MVT::Vector) {
4219 // Handle copies from generic vectors to registers.
4220 MVT::ValueType PTyElementVT, PTyLegalElementVT;
4221 unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
4222 PTyElementVT, PTyLegalElementVT);
4224 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
4225 // MVT::Vector type.
4226 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
4227 DAG.getConstant(NE, MVT::i32),
4228 DAG.getValueType(PTyElementVT));
4230 // Loop over all of the elements of the resultant vector,
4231 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
4232 // copying them into output registers.
4233 SmallVector<SDOperand, 8> OutChains;
4234 SDOperand Root = getRoot();
4235 for (unsigned i = 0; i != NE; ++i) {
4236 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
4237 Op, DAG.getConstant(i, TLI.getPointerTy()));
4238 if (PTyElementVT == PTyLegalElementVT) {
4239 // Elements are legal.
4240 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4241 } else if (PTyLegalElementVT > PTyElementVT) {
4242 // Elements are promoted.
4243 if (MVT::isFloatingPoint(PTyLegalElementVT))
4244 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
4246 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
4247 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
4249 // Elements are expanded.
4250 // The src value is expanded into multiple registers.
4251 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4252 Elt, DAG.getConstant(0, TLI.getPointerTy()));
4253 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
4254 Elt, DAG.getConstant(1, TLI.getPointerTy()));
4255 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
4256 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
4259 return DAG.getNode(ISD::TokenFactor, MVT::Other,
4260 &OutChains[0], OutChains.size());
4261 } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
4262 // The src value is promoted to the register.
4263 if (MVT::isFloatingPoint(SrcVT))
4264 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
4266 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
4267 return DAG.getCopyToReg(getRoot(), Reg, Op);
4269 DestVT = TLI.getTypeToExpandTo(SrcVT);
4270 unsigned NumVals = TLI.getNumElements(SrcVT);
4272 return DAG.getCopyToReg(getRoot(), Reg,
4273 DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
4274 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
4275 // The src value is expanded into multiple registers.
4276 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4277 Op, DAG.getConstant(0, TLI.getPointerTy()));
4278 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
4279 Op, DAG.getConstant(1, TLI.getPointerTy()));
4280 Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
4281 return DAG.getCopyToReg(Op, Reg+1, Hi);
4285 void SelectionDAGISel::
4286 LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL,
4287 std::vector<SDOperand> &UnorderedChains) {
4288 // If this is the entry block, emit arguments.
4289 Function &F = *LLVMBB->getParent();
4290 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
4291 SDOperand OldRoot = SDL.DAG.getRoot();
4292 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
4295 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
4297 if (!AI->use_empty()) {
4298 SDL.setValue(AI, Args[a]);
4300 // If this argument is live outside of the entry block, insert a copy from
4301 // whereever we got it to the vreg that other BB's will reference it as.
4302 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
4303 if (VMI != FuncInfo.ValueMap.end()) {
4304 SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
4305 UnorderedChains.push_back(Copy);
4309 // Finally, if the target has anything special to do, allow it to do so.
4310 // FIXME: this should insert code into the DAG!
4311 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
4314 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
4315 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
4316 FunctionLoweringInfo &FuncInfo) {
4317 SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
4319 std::vector<SDOperand> UnorderedChains;
4321 // Lower any arguments needed in this block if this is the entry block.
4322 if (LLVMBB == &LLVMBB->getParent()->front())
4323 LowerArguments(LLVMBB, SDL, UnorderedChains);
4325 BB = FuncInfo.MBBMap[LLVMBB];
4326 SDL.setCurrentBasicBlock(BB);
4328 // Lower all of the non-terminator instructions.
4329 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
4333 // Lower call part of invoke.
4334 InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
4335 if (Invoke) SDL.visitInvoke(*Invoke, false);
4337 // Ensure that all instructions which are used outside of their defining
4338 // blocks are available as virtual registers.
4339 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
4340 if (!I->use_empty() && !isa<PHINode>(I)) {
4341 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
4342 if (VMI != FuncInfo.ValueMap.end())
4343 UnorderedChains.push_back(
4344 SDL.CopyValueToVirtualRegister(I, VMI->second));
4347 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to
4348 // ensure constants are generated when needed. Remember the virtual registers
4349 // that need to be added to the Machine PHI nodes as input. We cannot just
4350 // directly add them, because expansion might result in multiple MBB's for one
4351 // BB. As such, the start of the BB might correspond to a different MBB than
4354 TerminatorInst *TI = LLVMBB->getTerminator();
4356 // Emit constants only once even if used by multiple PHI nodes.
4357 std::map<Constant*, unsigned> ConstantsOut;
4359 // Vector bool would be better, but vector<bool> is really slow.
4360 std::vector<unsigned char> SuccsHandled;
4361 if (TI->getNumSuccessors())
4362 SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
4364 // Check successor nodes PHI nodes that expect a constant to be available from
4366 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
4367 BasicBlock *SuccBB = TI->getSuccessor(succ);
4368 if (!isa<PHINode>(SuccBB->begin())) continue;
4369 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
4371 // If this terminator has multiple identical successors (common for
4372 // switches), only handle each succ once.
4373 unsigned SuccMBBNo = SuccMBB->getNumber();
4374 if (SuccsHandled[SuccMBBNo]) continue;
4375 SuccsHandled[SuccMBBNo] = true;
4377 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
4380 // At this point we know that there is a 1-1 correspondence between LLVM PHI
4381 // nodes and Machine PHI nodes, but the incoming operands have not been
4383 for (BasicBlock::iterator I = SuccBB->begin();
4384 (PN = dyn_cast<PHINode>(I)); ++I) {
4385 // Ignore dead phi's.
4386 if (PN->use_empty()) continue;
4389 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
4391 if (Constant *C = dyn_cast<Constant>(PHIOp)) {
4392 unsigned &RegOut = ConstantsOut[C];
4394 RegOut = FuncInfo.CreateRegForValue(C);
4395 UnorderedChains.push_back(
4396 SDL.CopyValueToVirtualRegister(C, RegOut));
4400 Reg = FuncInfo.ValueMap[PHIOp];
4402 assert(isa<AllocaInst>(PHIOp) &&
4403 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
4404 "Didn't codegen value into a register!??");
4405 Reg = FuncInfo.CreateRegForValue(PHIOp);
4406 UnorderedChains.push_back(
4407 SDL.CopyValueToVirtualRegister(PHIOp, Reg));
4411 // Remember that this register needs to added to the machine PHI node as
4412 // the input for this MBB.
4413 MVT::ValueType VT = TLI.getValueType(PN->getType());
4414 unsigned NumElements;
4415 if (VT != MVT::Vector)
4416 NumElements = TLI.getNumElements(VT);
4418 MVT::ValueType VT1,VT2;
4420 TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
4423 for (unsigned i = 0, e = NumElements; i != e; ++i)
4424 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
4427 ConstantsOut.clear();
4429 // Turn all of the unordered chains into one factored node.
4430 if (!UnorderedChains.empty()) {
4431 SDOperand Root = SDL.getRoot();
4432 if (Root.getOpcode() != ISD::EntryToken) {
4433 unsigned i = 0, e = UnorderedChains.size();
4434 for (; i != e; ++i) {
4435 assert(UnorderedChains[i].Val->getNumOperands() > 1);
4436 if (UnorderedChains[i].Val->getOperand(0) == Root)
4437 break; // Don't add the root if we already indirectly depend on it.
4441 UnorderedChains.push_back(Root);
4443 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other,
4444 &UnorderedChains[0], UnorderedChains.size()));
4447 // Lower the terminator after the copies are emitted.
4449 // Just the branch part of invoke.
4450 SDL.visitInvoke(*Invoke, true);
4452 SDL.visit(*LLVMBB->getTerminator());
4455 // Copy over any CaseBlock records that may now exist due to SwitchInst
4456 // lowering, as well as any jump table information.
4457 SwitchCases.clear();
4458 SwitchCases = SDL.SwitchCases;
4461 // Make sure the root of the DAG is up-to-date.
4462 DAG.setRoot(SDL.getRoot());
4465 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
4466 // Get alias analysis for load/store combining.
4467 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
4469 // Run the DAG combiner in pre-legalize mode.
4470 DAG.Combine(false, AA);
4472 DOUT << "Lowered selection DAG:\n";
4475 // Second step, hack on the DAG until it only uses operations and types that
4476 // the target supports.
4479 DOUT << "Legalized selection DAG:\n";
4482 // Run the DAG combiner in post-legalize mode.
4483 DAG.Combine(true, AA);
4485 if (ViewISelDAGs) DAG.viewGraph();
4487 // Third, instruction select all of the operations to machine code, adding the
4488 // code to the MachineBasicBlock.
4489 InstructionSelectBasicBlock(DAG);
4491 DOUT << "Selected machine code:\n";
4495 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
4496 FunctionLoweringInfo &FuncInfo) {
4497 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
4499 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4502 // First step, lower LLVM code to some DAG. This DAG may use operations and
4503 // types that are not supported by the target.
4504 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
4506 // Second step, emit the lowered DAG as machine code.
4507 CodeGenAndEmitDAG(DAG);
4510 // Next, now that we know what the last MBB the LLVM BB expanded is, update
4511 // PHI nodes in successors.
4512 if (SwitchCases.empty() && JT.Reg == 0) {
4513 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4514 MachineInstr *PHI = PHINodesToUpdate[i].first;
4515 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4516 "This is not a machine PHI node that we are updating!");
4517 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4518 PHI->addMachineBasicBlockOperand(BB);
4523 // If the JumpTable record is filled in, then we need to emit a jump table.
4524 // Updating the PHI nodes is tricky in this case, since we need to determine
4525 // whether the PHI is a successor of the range check MBB or the jump table MBB
4527 assert(SwitchCases.empty() && "Cannot have jump table and lowered switch");
4528 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4530 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4531 MachineBasicBlock *RangeBB = BB;
4532 // Set the current basic block to the mbb we wish to insert the code into
4534 SDL.setCurrentBasicBlock(BB);
4536 SDL.visitJumpTable(JT);
4537 SDAG.setRoot(SDL.getRoot());
4538 CodeGenAndEmitDAG(SDAG);
4540 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
4541 MachineInstr *PHI = PHINodesToUpdate[pi].first;
4542 MachineBasicBlock *PHIBB = PHI->getParent();
4543 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4544 "This is not a machine PHI node that we are updating!");
4545 if (PHIBB == JT.Default) {
4546 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4547 PHI->addMachineBasicBlockOperand(RangeBB);
4549 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
4550 PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
4551 PHI->addMachineBasicBlockOperand(BB);
4557 // If the switch block involved a branch to one of the actual successors, we
4558 // need to update PHI nodes in that block.
4559 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
4560 MachineInstr *PHI = PHINodesToUpdate[i].first;
4561 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
4562 "This is not a machine PHI node that we are updating!");
4563 if (BB->isSuccessor(PHI->getParent())) {
4564 PHI->addRegOperand(PHINodesToUpdate[i].second, false);
4565 PHI->addMachineBasicBlockOperand(BB);
4569 // If we generated any switch lowering information, build and codegen any
4570 // additional DAGs necessary.
4571 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
4572 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
4574 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
4576 // Set the current basic block to the mbb we wish to insert the code into
4577 BB = SwitchCases[i].ThisBB;
4578 SDL.setCurrentBasicBlock(BB);
4581 SDL.visitSwitchCase(SwitchCases[i]);
4582 SDAG.setRoot(SDL.getRoot());
4583 CodeGenAndEmitDAG(SDAG);
4585 // Handle any PHI nodes in successors of this chunk, as if we were coming
4586 // from the original BB before switch expansion. Note that PHI nodes can
4587 // occur multiple times in PHINodesToUpdate. We have to be very careful to
4588 // handle them the right number of times.
4589 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS.
4590 for (MachineBasicBlock::iterator Phi = BB->begin();
4591 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
4592 // This value for this PHI node is recorded in PHINodesToUpdate, get it.
4593 for (unsigned pn = 0; ; ++pn) {
4594 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
4595 if (PHINodesToUpdate[pn].first == Phi) {
4596 Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
4597 Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
4603 // Don't process RHS if same block as LHS.
4604 if (BB == SwitchCases[i].FalseBB)
4605 SwitchCases[i].FalseBB = 0;
4607 // If we haven't handled the RHS, do so now. Otherwise, we're done.
4608 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB;
4609 SwitchCases[i].FalseBB = 0;
4611 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0);
4616 //===----------------------------------------------------------------------===//
4617 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
4618 /// target node in the graph.
4619 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) {
4620 if (ViewSchedDAGs) DAG.viewGraph();
4622 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
4626 RegisterScheduler::setDefault(Ctor);
4629 ScheduleDAG *SL = Ctor(this, &DAG, BB);
4635 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
4636 return new HazardRecognizer();
4639 //===----------------------------------------------------------------------===//
4640 // Helper functions used by the generated instruction selector.
4641 //===----------------------------------------------------------------------===//
4642 // Calls to these methods are generated by tblgen.
4644 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
4645 /// the dag combiner simplified the 255, we still want to match. RHS is the
4646 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
4647 /// specified in the .td file (e.g. 255).
4648 bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
4649 int64_t DesiredMaskS) {
4650 uint64_t ActualMask = RHS->getValue();
4651 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4653 // If the actual mask exactly matches, success!
4654 if (ActualMask == DesiredMask)
4657 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4658 if (ActualMask & ~DesiredMask)
4661 // Otherwise, the DAG Combiner may have proven that the value coming in is
4662 // either already zero or is not demanded. Check for known zero input bits.
4663 uint64_t NeededMask = DesiredMask & ~ActualMask;
4664 if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
4667 // TODO: check to see if missing bits are just not demanded.
4669 // Otherwise, this pattern doesn't match.
4673 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
4674 /// the dag combiner simplified the 255, we still want to match. RHS is the
4675 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
4676 /// specified in the .td file (e.g. 255).
4677 bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
4678 int64_t DesiredMaskS) {
4679 uint64_t ActualMask = RHS->getValue();
4680 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
4682 // If the actual mask exactly matches, success!
4683 if (ActualMask == DesiredMask)
4686 // If the actual AND mask is allowing unallowed bits, this doesn't match.
4687 if (ActualMask & ~DesiredMask)
4690 // Otherwise, the DAG Combiner may have proven that the value coming in is
4691 // either already zero or is not demanded. Check for known zero input bits.
4692 uint64_t NeededMask = DesiredMask & ~ActualMask;
4694 uint64_t KnownZero, KnownOne;
4695 getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
4697 // If all the missing bits in the or are already known to be set, match!
4698 if ((NeededMask & KnownOne) == NeededMask)
4701 // TODO: check to see if missing bits are just not demanded.
4703 // Otherwise, this pattern doesn't match.
4708 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
4709 /// by tblgen. Others should not call it.
4710 void SelectionDAGISel::
4711 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) {
4712 std::vector<SDOperand> InOps;
4713 std::swap(InOps, Ops);
4715 Ops.push_back(InOps[0]); // input chain.
4716 Ops.push_back(InOps[1]); // input asm string.
4718 unsigned i = 2, e = InOps.size();
4719 if (InOps[e-1].getValueType() == MVT::Flag)
4720 --e; // Don't process a flag operand if it is here.
4723 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
4724 if ((Flags & 7) != 4 /*MEM*/) {
4725 // Just skip over this operand, copying the operands verbatim.
4726 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
4727 i += (Flags >> 3) + 1;
4729 assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
4730 // Otherwise, this is a memory operand. Ask the target to select it.
4731 std::vector<SDOperand> SelOps;
4732 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) {
4733 cerr << "Could not match memory address. Inline asm failure!\n";
4737 // Add this to the output node.
4738 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
4740 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
4745 // Add the flag input back if present.
4746 if (e != InOps.size())
4747 Ops.push_back(InOps.back());