LLVM API Documentation
00001 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the SelectionDAGISel class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "isel" 00015 #include "llvm/CodeGen/SelectionDAGISel.h" 00016 #include "llvm/CodeGen/ScheduleDAG.h" 00017 #include "llvm/CallingConv.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Function.h" 00021 #include "llvm/GlobalVariable.h" 00022 #include "llvm/InlineAsm.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Intrinsics.h" 00025 #include "llvm/IntrinsicInst.h" 00026 #include "llvm/CodeGen/IntrinsicLowering.h" 00027 #include "llvm/CodeGen/MachineDebugInfo.h" 00028 #include "llvm/CodeGen/MachineFunction.h" 00029 #include "llvm/CodeGen/MachineFrameInfo.h" 00030 #include "llvm/CodeGen/MachineJumpTableInfo.h" 00031 #include "llvm/CodeGen/MachineInstrBuilder.h" 00032 #include "llvm/CodeGen/SelectionDAG.h" 00033 #include "llvm/CodeGen/SSARegMap.h" 00034 #include "llvm/Target/MRegisterInfo.h" 00035 #include "llvm/Target/TargetData.h" 00036 #include "llvm/Target/TargetFrameInfo.h" 00037 #include "llvm/Target/TargetInstrInfo.h" 00038 #include "llvm/Target/TargetLowering.h" 00039 #include "llvm/Target/TargetMachine.h" 00040 #include "llvm/Target/TargetOptions.h" 00041 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00042 #include "llvm/Support/CommandLine.h" 00043 #include "llvm/Support/MathExtras.h" 00044 #include "llvm/Support/Debug.h" 00045 #include "llvm/Support/Visibility.h" 00046 #include <map> 00047 #include <set> 00048 #include <iostream> 00049 #include <algorithm> 00050 using namespace llvm; 00051 00052 #ifndef NDEBUG 00053 static cl::opt<bool> 00054 ViewISelDAGs("view-isel-dags", cl::Hidden, 00055 cl::desc("Pop up a window to show isel dags as they are selected")); 00056 static cl::opt<bool> 00057 ViewSchedDAGs("view-sched-dags", cl::Hidden, 00058 cl::desc("Pop up a window to show sched dags as they are processed")); 00059 #else 00060 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0; 00061 #endif 00062 00063 // Scheduling heuristics 00064 enum SchedHeuristics { 00065 defaultScheduling, // Let the target specify its preference. 00066 noScheduling, // No scheduling, emit breadth first sequence. 00067 simpleScheduling, // Two pass, min. critical path, max. utilization. 00068 simpleNoItinScheduling, // Same as above exact using generic latency. 00069 listSchedulingBURR, // Bottom-up reg reduction list scheduling. 00070 listSchedulingTDRR, // Top-down reg reduction list scheduling. 00071 listSchedulingTD // Top-down list scheduler. 00072 }; 00073 00074 namespace { 00075 cl::opt<SchedHeuristics> 00076 ISHeuristic( 00077 "sched", 00078 cl::desc("Choose scheduling style"), 00079 cl::init(defaultScheduling), 00080 cl::values( 00081 clEnumValN(defaultScheduling, "default", 00082 "Target preferred scheduling style"), 00083 clEnumValN(noScheduling, "none", 00084 "No scheduling: breadth first sequencing"), 00085 clEnumValN(simpleScheduling, "simple", 00086 "Simple two pass scheduling: minimize critical path " 00087 "and maximize processor utilization"), 00088 clEnumValN(simpleNoItinScheduling, "simple-noitin", 00089 "Simple two pass scheduling: Same as simple " 00090 "except using generic latency"), 00091 clEnumValN(listSchedulingBURR, "list-burr", 00092 "Bottom-up register reduction list scheduling"), 00093 clEnumValN(listSchedulingTDRR, "list-tdrr", 00094 "Top-down register reduction list scheduling"), 00095 clEnumValN(listSchedulingTD, "list-td", 00096 "Top-down list scheduler"), 00097 clEnumValEnd)); 00098 } // namespace 00099 00100 namespace { 00101 /// RegsForValue - This struct represents the physical registers that a 00102 /// particular value is assigned and the type information about the value. 00103 /// This is needed because values can be promoted into larger registers and 00104 /// expanded into multiple smaller registers than the value. 00105 struct VISIBILITY_HIDDEN RegsForValue { 00106 /// Regs - This list hold the register (for legal and promoted values) 00107 /// or register set (for expanded values) that the value should be assigned 00108 /// to. 00109 std::vector<unsigned> Regs; 00110 00111 /// RegVT - The value type of each register. 00112 /// 00113 MVT::ValueType RegVT; 00114 00115 /// ValueVT - The value type of the LLVM value, which may be promoted from 00116 /// RegVT or made from merging the two expanded parts. 00117 MVT::ValueType ValueVT; 00118 00119 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {} 00120 00121 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt) 00122 : RegVT(regvt), ValueVT(valuevt) { 00123 Regs.push_back(Reg); 00124 } 00125 RegsForValue(const std::vector<unsigned> ®s, 00126 MVT::ValueType regvt, MVT::ValueType valuevt) 00127 : Regs(regs), RegVT(regvt), ValueVT(valuevt) { 00128 } 00129 00130 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 00131 /// this value and returns the result as a ValueVT value. This uses 00132 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00133 SDOperand getCopyFromRegs(SelectionDAG &DAG, 00134 SDOperand &Chain, SDOperand &Flag) const; 00135 00136 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 00137 /// specified value into the registers specified by this object. This uses 00138 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00139 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 00140 SDOperand &Chain, SDOperand &Flag, 00141 MVT::ValueType PtrVT) const; 00142 00143 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 00144 /// operand list. This adds the code marker and includes the number of 00145 /// values added into it. 00146 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 00147 std::vector<SDOperand> &Ops) const; 00148 }; 00149 } 00150 00151 namespace llvm { 00152 //===--------------------------------------------------------------------===// 00153 /// FunctionLoweringInfo - This contains information that is global to a 00154 /// function that is used when lowering a region of the function. 00155 class FunctionLoweringInfo { 00156 public: 00157 TargetLowering &TLI; 00158 Function &Fn; 00159 MachineFunction &MF; 00160 SSARegMap *RegMap; 00161 00162 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 00163 00164 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 00165 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 00166 00167 /// ValueMap - Since we emit code for the function a basic block at a time, 00168 /// we must remember which virtual registers hold the values for 00169 /// cross-basic-block values. 00170 std::map<const Value*, unsigned> ValueMap; 00171 00172 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 00173 /// the entry block. This allows the allocas to be efficiently referenced 00174 /// anywhere in the function. 00175 std::map<const AllocaInst*, int> StaticAllocaMap; 00176 00177 unsigned MakeReg(MVT::ValueType VT) { 00178 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 00179 } 00180 00181 unsigned CreateRegForValue(const Value *V); 00182 00183 unsigned InitializeRegForValue(const Value *V) { 00184 unsigned &R = ValueMap[V]; 00185 assert(R == 0 && "Already initialized this value register!"); 00186 return R = CreateRegForValue(V); 00187 } 00188 }; 00189 } 00190 00191 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 00192 /// PHI nodes or outside of the basic block that defines it, or used by a 00193 /// switch instruction, which may expand to multiple basic blocks. 00194 static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 00195 if (isa<PHINode>(I)) return true; 00196 BasicBlock *BB = I->getParent(); 00197 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 00198 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) || 00199 isa<SwitchInst>(*UI)) 00200 return true; 00201 return false; 00202 } 00203 00204 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the 00205 /// entry block, return true. This includes arguments used by switches, since 00206 /// the switch may expand into multiple basic blocks. 00207 static bool isOnlyUsedInEntryBlock(Argument *A) { 00208 BasicBlock *Entry = A->getParent()->begin(); 00209 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) 00210 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI)) 00211 return false; // Use not in entry block. 00212 return true; 00213 } 00214 00215 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 00216 Function &fn, MachineFunction &mf) 00217 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) { 00218 00219 // Create a vreg for each argument register that is not dead and is used 00220 // outside of the entry block for the function. 00221 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); 00222 AI != E; ++AI) 00223 if (!isOnlyUsedInEntryBlock(AI)) 00224 InitializeRegForValue(AI); 00225 00226 // Initialize the mapping of values to registers. This is only set up for 00227 // instruction values that are used outside of the block that defines 00228 // them. 00229 Function::iterator BB = Fn.begin(), EB = Fn.end(); 00230 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00231 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 00232 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) { 00233 const Type *Ty = AI->getAllocatedType(); 00234 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty); 00235 unsigned Align = 00236 std::max((unsigned)TLI.getTargetData()->getTypeAlignment(Ty), 00237 AI->getAlignment()); 00238 00239 // If the alignment of the value is smaller than the size of the value, 00240 // and if the size of the value is particularly small (<= 8 bytes), 00241 // round up to the size of the value for potentially better performance. 00242 // 00243 // FIXME: This could be made better with a preferred alignment hook in 00244 // TargetData. It serves primarily to 8-byte align doubles for X86. 00245 if (Align < TySize && TySize <= 8) Align = TySize; 00246 TySize *= CUI->getValue(); // Get total allocated size. 00247 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. 00248 StaticAllocaMap[AI] = 00249 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 00250 } 00251 00252 for (; BB != EB; ++BB) 00253 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00254 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 00255 if (!isa<AllocaInst>(I) || 00256 !StaticAllocaMap.count(cast<AllocaInst>(I))) 00257 InitializeRegForValue(I); 00258 00259 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 00260 // also creates the initial PHI MachineInstrs, though none of the input 00261 // operands are populated. 00262 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { 00263 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 00264 MBBMap[BB] = MBB; 00265 MF.getBasicBlockList().push_back(MBB); 00266 00267 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 00268 // appropriate. 00269 PHINode *PN; 00270 for (BasicBlock::iterator I = BB->begin(); 00271 (PN = dyn_cast<PHINode>(I)); ++I) 00272 if (!PN->use_empty()) { 00273 MVT::ValueType VT = TLI.getValueType(PN->getType()); 00274 unsigned NumElements; 00275 if (VT != MVT::Vector) 00276 NumElements = TLI.getNumElements(VT); 00277 else { 00278 MVT::ValueType VT1,VT2; 00279 NumElements = 00280 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 00281 VT1, VT2); 00282 } 00283 unsigned PHIReg = ValueMap[PN]; 00284 assert(PHIReg &&"PHI node does not have an assigned virtual register!"); 00285 for (unsigned i = 0; i != NumElements; ++i) 00286 BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i); 00287 } 00288 } 00289 } 00290 00291 /// CreateRegForValue - Allocate the appropriate number of virtual registers of 00292 /// the correctly promoted or expanded types. Assign these registers 00293 /// consecutive vreg numbers and return the first assigned number. 00294 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { 00295 MVT::ValueType VT = TLI.getValueType(V->getType()); 00296 00297 // The number of multiples of registers that we need, to, e.g., split up 00298 // a <2 x int64> -> 4 x i32 registers. 00299 unsigned NumVectorRegs = 1; 00300 00301 // If this is a packed type, figure out what type it will decompose into 00302 // and how many of the elements it will use. 00303 if (VT == MVT::Vector) { 00304 const PackedType *PTy = cast<PackedType>(V->getType()); 00305 unsigned NumElts = PTy->getNumElements(); 00306 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType()); 00307 00308 // Divide the input until we get to a supported size. This will always 00309 // end with a scalar if the target doesn't support vectors. 00310 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) { 00311 NumElts >>= 1; 00312 NumVectorRegs <<= 1; 00313 } 00314 if (NumElts == 1) 00315 VT = EltTy; 00316 else 00317 VT = getVectorType(EltTy, NumElts); 00318 } 00319 00320 // The common case is that we will only create one register for this 00321 // value. If we have that case, create and return the virtual register. 00322 unsigned NV = TLI.getNumElements(VT); 00323 if (NV == 1) { 00324 // If we are promoting this value, pick the next largest supported type. 00325 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT); 00326 unsigned Reg = MakeReg(PromotedType); 00327 // If this is a vector of supported or promoted types (e.g. 4 x i16), 00328 // create all of the registers. 00329 for (unsigned i = 1; i != NumVectorRegs; ++i) 00330 MakeReg(PromotedType); 00331 return Reg; 00332 } 00333 00334 // If this value is represented with multiple target registers, make sure 00335 // to create enough consecutive registers of the right (smaller) type. 00336 unsigned NT = VT-1; // Find the type to use. 00337 while (TLI.getNumElements((MVT::ValueType)NT) != 1) 00338 --NT; 00339 00340 unsigned R = MakeReg((MVT::ValueType)NT); 00341 for (unsigned i = 1; i != NV*NumVectorRegs; ++i) 00342 MakeReg((MVT::ValueType)NT); 00343 return R; 00344 } 00345 00346 //===----------------------------------------------------------------------===// 00347 /// SelectionDAGLowering - This is the common target-independent lowering 00348 /// implementation that is parameterized by a TargetLowering object. 00349 /// Also, targets can overload any lowering method. 00350 /// 00351 namespace llvm { 00352 class SelectionDAGLowering { 00353 MachineBasicBlock *CurMBB; 00354 00355 std::map<const Value*, SDOperand> NodeMap; 00356 00357 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 00358 /// them up and then emit token factor nodes when possible. This allows us to 00359 /// get simple disambiguation between loads without worrying about alias 00360 /// analysis. 00361 std::vector<SDOperand> PendingLoads; 00362 00363 /// Case - A pair of values to record the Value for a switch case, and the 00364 /// case's target basic block. 00365 typedef std::pair<Constant*, MachineBasicBlock*> Case; 00366 typedef std::vector<Case>::iterator CaseItr; 00367 typedef std::pair<CaseItr, CaseItr> CaseRange; 00368 00369 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 00370 /// of conditional branches. 00371 struct CaseRec { 00372 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 00373 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 00374 00375 /// CaseBB - The MBB in which to emit the compare and branch 00376 MachineBasicBlock *CaseBB; 00377 /// LT, GE - If nonzero, we know the current case value must be less-than or 00378 /// greater-than-or-equal-to these Constants. 00379 Constant *LT; 00380 Constant *GE; 00381 /// Range - A pair of iterators representing the range of case values to be 00382 /// processed at this point in the binary search tree. 00383 CaseRange Range; 00384 }; 00385 00386 /// The comparison function for sorting Case values. 00387 struct CaseCmp { 00388 bool operator () (const Case& C1, const Case& C2) { 00389 if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first)) 00390 return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue(); 00391 00392 const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first); 00393 return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue(); 00394 } 00395 }; 00396 00397 public: 00398 // TLI - This is information that describes the available target features we 00399 // need for lowering. This indicates when operations are unavailable, 00400 // implemented with a libcall, etc. 00401 TargetLowering &TLI; 00402 SelectionDAG &DAG; 00403 const TargetData *TD; 00404 00405 /// SwitchCases - Vector of CaseBlock structures used to communicate 00406 /// SwitchInst code generation information. 00407 std::vector<SelectionDAGISel::CaseBlock> SwitchCases; 00408 SelectionDAGISel::JumpTable JT; 00409 00410 /// FuncInfo - Information about the function as a whole. 00411 /// 00412 FunctionLoweringInfo &FuncInfo; 00413 00414 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 00415 FunctionLoweringInfo &funcinfo) 00416 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), 00417 JT(0,0,0,0), FuncInfo(funcinfo) { 00418 } 00419 00420 /// getRoot - Return the current virtual root of the Selection DAG. 00421 /// 00422 SDOperand getRoot() { 00423 if (PendingLoads.empty()) 00424 return DAG.getRoot(); 00425 00426 if (PendingLoads.size() == 1) { 00427 SDOperand Root = PendingLoads[0]; 00428 DAG.setRoot(Root); 00429 PendingLoads.clear(); 00430 return Root; 00431 } 00432 00433 // Otherwise, we have to make a token factor node. 00434 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, PendingLoads); 00435 PendingLoads.clear(); 00436 DAG.setRoot(Root); 00437 return Root; 00438 } 00439 00440 void visit(Instruction &I) { visit(I.getOpcode(), I); } 00441 00442 void visit(unsigned Opcode, User &I) { 00443 switch (Opcode) { 00444 default: assert(0 && "Unknown instruction type encountered!"); 00445 abort(); 00446 // Build the switch statement using the Instruction.def file. 00447 #define HANDLE_INST(NUM, OPCODE, CLASS) \ 00448 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 00449 #include "llvm/Instruction.def" 00450 } 00451 } 00452 00453 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 00454 00455 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr, 00456 SDOperand SrcValue, SDOperand Root, 00457 bool isVolatile); 00458 00459 SDOperand getIntPtrConstant(uint64_t Val) { 00460 return DAG.getConstant(Val, TLI.getPointerTy()); 00461 } 00462 00463 SDOperand getValue(const Value *V); 00464 00465 const SDOperand &setValue(const Value *V, SDOperand NewN) { 00466 SDOperand &N = NodeMap[V]; 00467 assert(N.Val == 0 && "Already set a value for this node!"); 00468 return N = NewN; 00469 } 00470 00471 RegsForValue GetRegistersForValue(const std::string &ConstrCode, 00472 MVT::ValueType VT, 00473 bool OutReg, bool InReg, 00474 std::set<unsigned> &OutputRegs, 00475 std::set<unsigned> &InputRegs); 00476 00477 // Terminator instructions. 00478 void visitRet(ReturnInst &I); 00479 void visitBr(BranchInst &I); 00480 void visitSwitch(SwitchInst &I); 00481 void visitUnreachable(UnreachableInst &I) { /* noop */ } 00482 00483 // Helper for visitSwitch 00484 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB); 00485 void visitJumpTable(SelectionDAGISel::JumpTable &JT); 00486 00487 // These all get lowered before this pass. 00488 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); } 00489 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); } 00490 00491 void visitBinary(User &I, unsigned IntOp, unsigned FPOp, unsigned VecOp); 00492 void visitShift(User &I, unsigned Opcode); 00493 void visitAdd(User &I) { 00494 visitBinary(I, ISD::ADD, ISD::FADD, ISD::VADD); 00495 } 00496 void visitSub(User &I); 00497 void visitMul(User &I) { 00498 visitBinary(I, ISD::MUL, ISD::FMUL, ISD::VMUL); 00499 } 00500 void visitDiv(User &I) { 00501 const Type *Ty = I.getType(); 00502 visitBinary(I, 00503 Ty->isSigned() ? ISD::SDIV : ISD::UDIV, ISD::FDIV, 00504 Ty->isSigned() ? ISD::VSDIV : ISD::VUDIV); 00505 } 00506 void visitRem(User &I) { 00507 const Type *Ty = I.getType(); 00508 visitBinary(I, Ty->isSigned() ? ISD::SREM : ISD::UREM, ISD::FREM, 0); 00509 } 00510 void visitAnd(User &I) { visitBinary(I, ISD::AND, 0, ISD::VAND); } 00511 void visitOr (User &I) { visitBinary(I, ISD::OR, 0, ISD::VOR); } 00512 void visitXor(User &I) { visitBinary(I, ISD::XOR, 0, ISD::VXOR); } 00513 void visitShl(User &I) { visitShift(I, ISD::SHL); } 00514 void visitShr(User &I) { 00515 visitShift(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA); 00516 } 00517 00518 void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc, 00519 ISD::CondCode FPOpc); 00520 void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ, 00521 ISD::SETOEQ); } 00522 void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE, 00523 ISD::SETUNE); } 00524 void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE, 00525 ISD::SETOLE); } 00526 void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE, 00527 ISD::SETOGE); } 00528 void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT, 00529 ISD::SETOLT); } 00530 void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT, 00531 ISD::SETOGT); } 00532 00533 void visitExtractElement(User &I); 00534 void visitInsertElement(User &I); 00535 void visitShuffleVector(User &I); 00536 00537 void visitGetElementPtr(User &I); 00538 void visitCast(User &I); 00539 void visitSelect(User &I); 00540 00541 void visitMalloc(MallocInst &I); 00542 void visitFree(FreeInst &I); 00543 void visitAlloca(AllocaInst &I); 00544 void visitLoad(LoadInst &I); 00545 void visitStore(StoreInst &I); 00546 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 00547 void visitCall(CallInst &I); 00548 void visitInlineAsm(CallInst &I); 00549 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 00550 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 00551 00552 void visitVAStart(CallInst &I); 00553 void visitVAArg(VAArgInst &I); 00554 void visitVAEnd(CallInst &I); 00555 void visitVACopy(CallInst &I); 00556 void visitFrameReturnAddress(CallInst &I, bool isFrameAddress); 00557 00558 void visitMemIntrinsic(CallInst &I, unsigned Op); 00559 00560 void visitUserOp1(Instruction &I) { 00561 assert(0 && "UserOp1 should not exist at instruction selection time!"); 00562 abort(); 00563 } 00564 void visitUserOp2(Instruction &I) { 00565 assert(0 && "UserOp2 should not exist at instruction selection time!"); 00566 abort(); 00567 } 00568 }; 00569 } // end namespace llvm 00570 00571 SDOperand SelectionDAGLowering::getValue(const Value *V) { 00572 SDOperand &N = NodeMap[V]; 00573 if (N.Val) return N; 00574 00575 const Type *VTy = V->getType(); 00576 MVT::ValueType VT = TLI.getValueType(VTy); 00577 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) { 00578 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00579 visit(CE->getOpcode(), *CE); 00580 assert(N.Val && "visit didn't populate the ValueMap!"); 00581 return N; 00582 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 00583 return N = DAG.getGlobalAddress(GV, VT); 00584 } else if (isa<ConstantPointerNull>(C)) { 00585 return N = DAG.getConstant(0, TLI.getPointerTy()); 00586 } else if (isa<UndefValue>(C)) { 00587 if (!isa<PackedType>(VTy)) 00588 return N = DAG.getNode(ISD::UNDEF, VT); 00589 00590 // Create a VBUILD_VECTOR of undef nodes. 00591 const PackedType *PTy = cast<PackedType>(VTy); 00592 unsigned NumElements = PTy->getNumElements(); 00593 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 00594 00595 std::vector<SDOperand> Ops; 00596 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT)); 00597 00598 // Create a VConstant node with generic Vector type. 00599 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 00600 Ops.push_back(DAG.getValueType(PVT)); 00601 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00602 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 00603 return N = DAG.getConstantFP(CFP->getValue(), VT); 00604 } else if (const PackedType *PTy = dyn_cast<PackedType>(VTy)) { 00605 unsigned NumElements = PTy->getNumElements(); 00606 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 00607 00608 // Now that we know the number and type of the elements, push a 00609 // Constant or ConstantFP node onto the ops list for each element of 00610 // the packed constant. 00611 std::vector<SDOperand> Ops; 00612 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) { 00613 for (unsigned i = 0; i != NumElements; ++i) 00614 Ops.push_back(getValue(CP->getOperand(i))); 00615 } else { 00616 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!"); 00617 SDOperand Op; 00618 if (MVT::isFloatingPoint(PVT)) 00619 Op = DAG.getConstantFP(0, PVT); 00620 else 00621 Op = DAG.getConstant(0, PVT); 00622 Ops.assign(NumElements, Op); 00623 } 00624 00625 // Create a VBUILD_VECTOR node with generic Vector type. 00626 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 00627 Ops.push_back(DAG.getValueType(PVT)); 00628 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00629 } else { 00630 // Canonicalize all constant ints to be unsigned. 00631 return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT); 00632 } 00633 } 00634 00635 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 00636 std::map<const AllocaInst*, int>::iterator SI = 00637 FuncInfo.StaticAllocaMap.find(AI); 00638 if (SI != FuncInfo.StaticAllocaMap.end()) 00639 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 00640 } 00641 00642 std::map<const Value*, unsigned>::const_iterator VMI = 00643 FuncInfo.ValueMap.find(V); 00644 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!"); 00645 00646 unsigned InReg = VMI->second; 00647 00648 // If this type is not legal, make it so now. 00649 if (VT != MVT::Vector) { 00650 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT); 00651 00652 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT); 00653 if (DestVT < VT) { 00654 // Source must be expanded. This input value is actually coming from the 00655 // register pair VMI->second and VMI->second+1. 00656 N = DAG.getNode(ISD::BUILD_PAIR, VT, N, 00657 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT)); 00658 } else if (DestVT > VT) { // Promotion case 00659 if (MVT::isFloatingPoint(VT)) 00660 N = DAG.getNode(ISD::FP_ROUND, VT, N); 00661 else 00662 N = DAG.getNode(ISD::TRUNCATE, VT, N); 00663 } 00664 } else { 00665 // Otherwise, if this is a vector, make it available as a generic vector 00666 // here. 00667 MVT::ValueType PTyElementVT, PTyLegalElementVT; 00668 const PackedType *PTy = cast<PackedType>(VTy); 00669 unsigned NE = TLI.getPackedTypeBreakdown(PTy, PTyElementVT, 00670 PTyLegalElementVT); 00671 00672 // Build a VBUILD_VECTOR with the input registers. 00673 std::vector<SDOperand> Ops; 00674 if (PTyElementVT == PTyLegalElementVT) { 00675 // If the value types are legal, just VBUILD the CopyFromReg nodes. 00676 for (unsigned i = 0; i != NE; ++i) 00677 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00678 PTyElementVT)); 00679 } else if (PTyElementVT < PTyLegalElementVT) { 00680 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate. 00681 for (unsigned i = 0; i != NE; ++i) { 00682 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00683 PTyElementVT); 00684 if (MVT::isFloatingPoint(PTyElementVT)) 00685 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op); 00686 else 00687 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op); 00688 Ops.push_back(Op); 00689 } 00690 } else { 00691 // If the register was expanded, use BUILD_PAIR. 00692 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!"); 00693 for (unsigned i = 0; i != NE/2; ++i) { 00694 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00695 PTyElementVT); 00696 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00697 PTyElementVT); 00698 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1)); 00699 } 00700 } 00701 00702 Ops.push_back(DAG.getConstant(NE, MVT::i32)); 00703 Ops.push_back(DAG.getValueType(PTyLegalElementVT)); 00704 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00705 00706 // Finally, use a VBIT_CONVERT to make this available as the appropriate 00707 // vector type. 00708 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N, 00709 DAG.getConstant(PTy->getNumElements(), 00710 MVT::i32), 00711 DAG.getValueType(TLI.getValueType(PTy->getElementType()))); 00712 } 00713 00714 return N; 00715 } 00716 00717 00718 void SelectionDAGLowering::visitRet(ReturnInst &I) { 00719 if (I.getNumOperands() == 0) { 00720 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot())); 00721 return; 00722 } 00723 std::vector<SDOperand> NewValues; 00724 NewValues.push_back(getRoot()); 00725 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00726 SDOperand RetOp = getValue(I.getOperand(i)); 00727 bool isSigned = I.getOperand(i)->getType()->isSigned(); 00728 00729 // If this is an integer return value, we need to promote it ourselves to 00730 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather 00731 // than sign/zero. 00732 // FIXME: C calling convention requires the return type to be promoted to 00733 // at least 32-bit. But this is not necessary for non-C calling conventions. 00734 if (MVT::isInteger(RetOp.getValueType()) && 00735 RetOp.getValueType() < MVT::i64) { 00736 MVT::ValueType TmpVT; 00737 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote) 00738 TmpVT = TLI.getTypeToTransformTo(MVT::i32); 00739 else 00740 TmpVT = MVT::i32; 00741 00742 if (isSigned) 00743 RetOp = DAG.getNode(ISD::SIGN_EXTEND, TmpVT, RetOp); 00744 else 00745 RetOp = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, RetOp); 00746 } 00747 NewValues.push_back(RetOp); 00748 NewValues.push_back(DAG.getConstant(isSigned, MVT::i32)); 00749 } 00750 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, NewValues)); 00751 } 00752 00753 void SelectionDAGLowering::visitBr(BranchInst &I) { 00754 // Update machine-CFG edges. 00755 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 00756 CurMBB->addSuccessor(Succ0MBB); 00757 00758 // Figure out which block is immediately after the current one. 00759 MachineBasicBlock *NextBlock = 0; 00760 MachineFunction::iterator BBI = CurMBB; 00761 if (++BBI != CurMBB->getParent()->end()) 00762 NextBlock = BBI; 00763 00764 if (I.isUnconditional()) { 00765 // If this is not a fall-through branch, emit the branch. 00766 if (Succ0MBB != NextBlock) 00767 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 00768 DAG.getBasicBlock(Succ0MBB))); 00769 } else { 00770 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 00771 CurMBB->addSuccessor(Succ1MBB); 00772 00773 SDOperand Cond = getValue(I.getCondition()); 00774 if (Succ1MBB == NextBlock) { 00775 // If the condition is false, fall through. This means we should branch 00776 // if the condition is true to Succ #0. 00777 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 00778 Cond, DAG.getBasicBlock(Succ0MBB))); 00779 } else if (Succ0MBB == NextBlock) { 00780 // If the condition is true, fall through. This means we should branch if 00781 // the condition is false to Succ #1. Invert the condition first. 00782 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00783 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00784 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 00785 Cond, DAG.getBasicBlock(Succ1MBB))); 00786 } else { 00787 std::vector<SDOperand> Ops; 00788 Ops.push_back(getRoot()); 00789 // If the false case is the current basic block, then this is a self 00790 // loop. We do not want to emit "Loop: ... brcond Out; br Loop", as it 00791 // adds an extra instruction in the loop. Instead, invert the 00792 // condition and emit "Loop: ... br!cond Loop; br Out. 00793 if (CurMBB == Succ1MBB) { 00794 std::swap(Succ0MBB, Succ1MBB); 00795 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00796 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00797 } 00798 SDOperand True = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond, 00799 DAG.getBasicBlock(Succ0MBB)); 00800 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, True, 00801 DAG.getBasicBlock(Succ1MBB))); 00802 } 00803 } 00804 } 00805 00806 /// visitSwitchCase - Emits the necessary code to represent a single node in 00807 /// the binary search tree resulting from lowering a switch instruction. 00808 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { 00809 SDOperand SwitchOp = getValue(CB.SwitchV); 00810 SDOperand CaseOp = getValue(CB.CaseC); 00811 SDOperand Cond = DAG.getSetCC(MVT::i1, SwitchOp, CaseOp, CB.CC); 00812 00813 // Set NextBlock to be the MBB immediately after the current one, if any. 00814 // This is used to avoid emitting unnecessary branches to the next block. 00815 MachineBasicBlock *NextBlock = 0; 00816 MachineFunction::iterator BBI = CurMBB; 00817 if (++BBI != CurMBB->getParent()->end()) 00818 NextBlock = BBI; 00819 00820 // If the lhs block is the next block, invert the condition so that we can 00821 // fall through to the lhs instead of the rhs block. 00822 if (CB.LHSBB == NextBlock) { 00823 std::swap(CB.LHSBB, CB.RHSBB); 00824 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00825 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00826 } 00827 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond, 00828 DAG.getBasicBlock(CB.LHSBB)); 00829 if (CB.RHSBB == NextBlock) 00830 DAG.setRoot(BrCond); 00831 else 00832 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, 00833 DAG.getBasicBlock(CB.RHSBB))); 00834 // Update successor info 00835 CurMBB->addSuccessor(CB.LHSBB); 00836 CurMBB->addSuccessor(CB.RHSBB); 00837 } 00838 00839 /// visitSwitchCase - Emits the necessary code to represent a single node in 00840 /// the binary search tree resulting from lowering a switch instruction. 00841 void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) { 00842 // FIXME: Need to emit different code for PIC vs. Non-PIC, specifically, 00843 // we need to add the address of the jump table to the value loaded, since 00844 // the entries in the jump table will be differences rather than absolute 00845 // addresses. 00846 00847 // Emit the code for the jump table 00848 MVT::ValueType PTy = TLI.getPointerTy(); 00849 unsigned PTyBytes = MVT::getSizeInBits(PTy)/8; 00850 SDOperand Copy = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy); 00851 SDOperand IDX = DAG.getNode(ISD::MUL, PTy, Copy, 00852 DAG.getConstant(PTyBytes, PTy)); 00853 SDOperand TAB = DAG.getJumpTable(JT.JTI,PTy); 00854 SDOperand ADD = DAG.getNode(ISD::ADD, PTy, IDX, TAB); 00855 SDOperand LD = DAG.getLoad(PTy, Copy.getValue(1), ADD, DAG.getSrcValue(0)); 00856 if (TLI.getTargetMachine().getRelocationModel() == Reloc::PIC_) { 00857 ADD = DAG.getNode(ISD::ADD, PTy, LD.getValue(0), TAB); 00858 DAG.setRoot(DAG.getNode(ISD::BRIND, MVT::Other, LD.getValue(1), ADD)); 00859 } else { 00860 DAG.setRoot(DAG.getNode(ISD::BRIND, MVT::Other, LD.getValue(1), LD)); 00861 } 00862 } 00863 00864 void SelectionDAGLowering::visitSwitch(SwitchInst &I) { 00865 // Figure out which block is immediately after the current one. 00866 MachineBasicBlock *NextBlock = 0; 00867 MachineFunction::iterator BBI = CurMBB; 00868 if (++BBI != CurMBB->getParent()->end()) 00869 NextBlock = BBI; 00870 00871 // If there is only the default destination, branch to it if it is not the 00872 // next basic block. Otherwise, just fall through. 00873 if (I.getNumOperands() == 2) { 00874 // Update machine-CFG edges. 00875 MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[I.getDefaultDest()]; 00876 // If this is not a fall-through branch, emit the branch. 00877 if (DefaultMBB != NextBlock) 00878 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 00879 DAG.getBasicBlock(DefaultMBB))); 00880 CurMBB->addSuccessor(DefaultMBB); 00881 return; 00882 } 00883 00884 // If there are any non-default case statements, create a vector of Cases 00885 // representing each one, and sort the vector so that we can efficiently 00886 // create a binary search tree from them. 00887 std::vector<Case> Cases; 00888 for (unsigned i = 1; i < I.getNumSuccessors(); ++i) { 00889 MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)]; 00890 Cases.push_back(Case(I.getSuccessorValue(i), SMBB)); 00891 } 00892 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 00893 00894 // Get the Value to be switched on and default basic blocks, which will be 00895 // inserted into CaseBlock records, representing basic blocks in the binary 00896 // search tree. 00897 Value *SV = I.getOperand(0); 00898 MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()]; 00899 00900 // Get the MachineFunction which holds the current MBB. This is used during 00901 // emission of jump tables, and when inserting any additional MBBs necessary 00902 // to represent the switch. 00903 MachineFunction *CurMF = CurMBB->getParent(); 00904 const BasicBlock *LLVMBB = CurMBB->getBasicBlock(); 00905 00906 // If the switch has more than 5 blocks, and at least 31.25% dense, and the 00907 // target supports indirect branches, then emit a jump table rather than 00908 // lowering the switch to a binary tree of conditional branches. 00909 // FIXME: Make this work with PIC code 00910 if (TLI.isOperationLegal(ISD::BRIND, TLI.getPointerTy()) && 00911 Cases.size() > 5) { 00912 uint64_t First = cast<ConstantIntegral>(Cases.front().first)->getRawValue(); 00913 uint64_t Last = cast<ConstantIntegral>(Cases.back().first)->getRawValue(); 00914 double Density = (double)Cases.size() / (double)((Last - First) + 1ULL); 00915 00916 if (Density >= 0.3125) { 00917 Reloc::Model Relocs = TLI.getTargetMachine().getRelocationModel(); 00918 00919 // Create a new basic block to hold the code for loading the address 00920 // of the jump table, and jumping to it. Update successor information; 00921 // we will either branch to the default case for the switch, or the jump 00922 // table. 00923 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB); 00924 CurMF->getBasicBlockList().insert(BBI, JumpTableBB); 00925 CurMBB->addSuccessor(Default); 00926 CurMBB->addSuccessor(JumpTableBB); 00927 00928 // Subtract the lowest switch case value from the value being switched on 00929 // and conditional branch to default mbb if the result is greater than the 00930 // difference between smallest and largest cases. 00931 SDOperand SwitchOp = getValue(SV); 00932 MVT::ValueType VT = SwitchOp.getValueType(); 00933 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp, 00934 DAG.getConstant(First, VT)); 00935 00936 // The SDNode we just created, which holds the value being switched on 00937 // minus the the smallest case value, needs to be copied to a virtual 00938 // register so it can be used as an index into the jump table in a 00939 // subsequent basic block. This value may be smaller or larger than the 00940 // target's pointer type, and therefore require extension or truncating. 00941 if (VT > TLI.getPointerTy()) 00942 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB); 00943 else 00944 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB); 00945 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy()); 00946 SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp); 00947 00948 // Emit the range check for the jump table, and branch to the default 00949 // block for the switch statement if the value being switched on exceeds 00950 // the largest case in the switch. 00951 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB, 00952 DAG.getConstant(Last-First,VT), ISD::SETUGT); 00953 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP, 00954 DAG.getBasicBlock(Default))); 00955 00956 // Build a vector of destination BBs, corresponding to each target 00957 // of the jump table. If the value of the jump table slot corresponds to 00958 // a case statement, push the case's BB onto the vector, otherwise, push 00959 // the default BB. 00960 std::set<MachineBasicBlock*> UniqueBBs; 00961 std::vector<MachineBasicBlock*> DestBBs; 00962 uint64_t TEI = First; 00963 for (CaseItr ii = Cases.begin(), ee = Cases.end(); ii != ee; ++TEI) { 00964 if (cast<ConstantIntegral>(ii->first)->getRawValue() == TEI) { 00965 DestBBs.push_back(ii->second); 00966 UniqueBBs.insert(ii->second); 00967 ++ii; 00968 } else { 00969 DestBBs.push_back(Default); 00970 UniqueBBs.insert(Default); 00971 } 00972 } 00973 00974 // Update successor info 00975 for (std::set<MachineBasicBlock*>::iterator ii = UniqueBBs.begin(), 00976 ee = UniqueBBs.end(); ii != ee; ++ii) 00977 JumpTableBB->addSuccessor(*ii); 00978 00979 // Create a jump table index for this jump table, or return an existing 00980 // one. 00981 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs); 00982 00983 // Set the jump table information so that we can codegen it as a second 00984 // MachineBasicBlock 00985 JT.Reg = JumpTableReg; 00986 JT.JTI = JTI; 00987 JT.MBB = JumpTableBB; 00988 JT.Default = Default; 00989 return; 00990 } 00991 } 00992 00993 // Push the initial CaseRec onto the worklist 00994 std::vector<CaseRec> CaseVec; 00995 CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end()))); 00996 00997 while (!CaseVec.empty()) { 00998 // Grab a record representing a case range to process off the worklist 00999 CaseRec CR = CaseVec.back(); 01000 CaseVec.pop_back(); 01001 01002 // Size is the number of Cases represented by this range. If Size is 1, 01003 // then we are processing a leaf of the binary search tree. Otherwise, 01004 // we need to pick a pivot, and push left and right ranges onto the 01005 // worklist. 01006 unsigned Size = CR.Range.second - CR.Range.first; 01007 01008 if (Size == 1) { 01009 // Create a CaseBlock record representing a conditional branch to 01010 // the Case's target mbb if the value being switched on SV is equal 01011 // to C. Otherwise, branch to default. 01012 Constant *C = CR.Range.first->first; 01013 MachineBasicBlock *Target = CR.Range.first->second; 01014 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, C, Target, Default, 01015 CR.CaseBB); 01016 // If the MBB representing the leaf node is the current MBB, then just 01017 // call visitSwitchCase to emit the code into the current block. 01018 // Otherwise, push the CaseBlock onto the vector to be later processed 01019 // by SDISel, and insert the node's MBB before the next MBB. 01020 if (CR.CaseBB == CurMBB) 01021 visitSwitchCase(CB); 01022 else { 01023 SwitchCases.push_back(CB); 01024 CurMF->getBasicBlockList().insert(BBI, CR.CaseBB); 01025 } 01026 } else { 01027 // split case range at pivot 01028 CaseItr Pivot = CR.Range.first + (Size / 2); 01029 CaseRange LHSR(CR.Range.first, Pivot); 01030 CaseRange RHSR(Pivot, CR.Range.second); 01031 Constant *C = Pivot->first; 01032 MachineBasicBlock *RHSBB = 0, *LHSBB = 0; 01033 // We know that we branch to the LHS if the Value being switched on is 01034 // less than the Pivot value, C. We use this to optimize our binary 01035 // tree a bit, by recognizing that if SV is greater than or equal to the 01036 // LHS's Case Value, and that Case Value is exactly one less than the 01037 // Pivot's Value, then we can branch directly to the LHS's Target, 01038 // rather than creating a leaf node for it. 01039 if ((LHSR.second - LHSR.first) == 1 && 01040 LHSR.first->first == CR.GE && 01041 cast<ConstantIntegral>(C)->getRawValue() == 01042 (cast<ConstantIntegral>(CR.GE)->getRawValue() + 1ULL)) { 01043 LHSBB = LHSR.first->second; 01044 } else { 01045 LHSBB = new MachineBasicBlock(LLVMBB); 01046 CaseVec.push_back(CaseRec(LHSBB,C,CR.GE,LHSR)); 01047 } 01048 // Similar to the optimization above, if the Value being switched on is 01049 // known to be less than the Constant CR.LT, and the current Case Value 01050 // is CR.LT - 1, then we can branch directly to the target block for 01051 // the current Case Value, rather than emitting a RHS leaf node for it. 01052 if ((RHSR.second - RHSR.first) == 1 && CR.LT && 01053 cast<ConstantIntegral>(RHSR.first->first)->getRawValue() == 01054 (cast<ConstantIntegral>(CR.LT)->getRawValue() - 1ULL)) { 01055 RHSBB = RHSR.first->second; 01056 } else { 01057 RHSBB = new MachineBasicBlock(LLVMBB); 01058 CaseVec.push_back(CaseRec(RHSBB,CR.LT,C,RHSR)); 01059 } 01060 // Create a CaseBlock record representing a conditional branch to 01061 // the LHS node if the value being switched on SV is less than C. 01062 // Otherwise, branch to LHS. 01063 ISD::CondCode CC = C->getType()->isSigned() ? ISD::SETLT : ISD::SETULT; 01064 SelectionDAGISel::CaseBlock CB(CC, SV, C, LHSBB, RHSBB, CR.CaseBB); 01065 if (CR.CaseBB == CurMBB) 01066 visitSwitchCase(CB); 01067 else { 01068 SwitchCases.push_back(CB); 01069 CurMF->getBasicBlockList().insert(BBI, CR.CaseBB); 01070 } 01071 } 01072 } 01073 } 01074 01075 void SelectionDAGLowering::visitSub(User &I) { 01076 // -0.0 - X --> fneg 01077 if (I.getType()->isFloatingPoint()) { 01078 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 01079 if (CFP->isExactlyValue(-0.0)) { 01080 SDOperand Op2 = getValue(I.getOperand(1)); 01081 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 01082 return; 01083 } 01084 } 01085 visitBinary(I, ISD::SUB, ISD::FSUB, ISD::VSUB); 01086 } 01087 01088 void SelectionDAGLowering::visitBinary(User &I, unsigned IntOp, unsigned FPOp, 01089 unsigned VecOp) { 01090 const Type *Ty = I.getType(); 01091 SDOperand Op1 = getValue(I.getOperand(0)); 01092 SDOperand Op2 = getValue(I.getOperand(1)); 01093 01094 if (Ty->isIntegral()) { 01095 setValue(&I, DAG.getNode(IntOp, Op1.getValueType(), Op1, Op2)); 01096 } else if (Ty->isFloatingPoint()) { 01097 setValue(&I, DAG.getNode(FPOp, Op1.getValueType(), Op1, Op2)); 01098 } else { 01099 const PackedType *PTy = cast<PackedType>(Ty); 01100 SDOperand Num = DAG.getConstant(PTy->getNumElements(), MVT::i32); 01101 SDOperand Typ = DAG.getValueType(TLI.getValueType(PTy->getElementType())); 01102 setValue(&I, DAG.getNode(VecOp, MVT::Vector, Op1, Op2, Num, Typ)); 01103 } 01104 } 01105 01106 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) { 01107 SDOperand Op1 = getValue(I.getOperand(0)); 01108 SDOperand Op2 = getValue(I.getOperand(1)); 01109 01110 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2); 01111 01112 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 01113 } 01114 01115 void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode, 01116 ISD::CondCode UnsignedOpcode, 01117 ISD::CondCode FPOpcode) { 01118 SDOperand Op1 = getValue(I.getOperand(0)); 01119 SDOperand Op2 = getValue(I.getOperand(1)); 01120 ISD::CondCode Opcode = SignedOpcode; 01121 if (!FiniteOnlyFPMath() && I.getOperand(0)->getType()->isFloatingPoint()) 01122 Opcode = FPOpcode; 01123 else if (I.getOperand(0)->getType()->isUnsigned()) 01124 Opcode = UnsignedOpcode; 01125 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode)); 01126 } 01127 01128 void SelectionDAGLowering::visitSelect(User &I) { 01129 SDOperand Cond = getValue(I.getOperand(0)); 01130 SDOperand TrueVal = getValue(I.getOperand(1)); 01131 SDOperand FalseVal = getValue(I.getOperand(2)); 01132 if (!isa<PackedType>(I.getType())) { 01133 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 01134 TrueVal, FalseVal)); 01135 } else { 01136 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal, 01137 *(TrueVal.Val->op_end()-2), 01138 *(TrueVal.Val->op_end()-1))); 01139 } 01140 } 01141 01142 void SelectionDAGLowering::visitCast(User &I) { 01143 SDOperand N = getValue(I.getOperand(0)); 01144 MVT::ValueType SrcVT = N.getValueType(); 01145 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 01146 01147 if (DestVT == MVT::Vector) { 01148 // This is a cast to a vector from something else. This is always a bit 01149 // convert. Get information about the input vector. 01150 const PackedType *DestTy = cast<PackedType>(I.getType()); 01151 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 01152 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N, 01153 DAG.getConstant(DestTy->getNumElements(),MVT::i32), 01154 DAG.getValueType(EltVT))); 01155 } else if (SrcVT == DestVT) { 01156 setValue(&I, N); // noop cast. 01157 } else if (DestVT == MVT::i1) { 01158 // Cast to bool is a comparison against zero, not truncation to zero. 01159 SDOperand Zero = isInteger(SrcVT) ? DAG.getConstant(0, N.getValueType()) : 01160 DAG.getConstantFP(0.0, N.getValueType()); 01161 setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE)); 01162 } else if (isInteger(SrcVT)) { 01163 if (isInteger(DestVT)) { // Int -> Int cast 01164 if (DestVT < SrcVT) // Truncating cast? 01165 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 01166 else if (I.getOperand(0)->getType()->isSigned()) 01167 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N)); 01168 else 01169 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 01170 } else if (isFloatingPoint(DestVT)) { // Int -> FP cast 01171 if (I.getOperand(0)->getType()->isSigned()) 01172 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N)); 01173 else 01174 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N)); 01175 } else { 01176 assert(0 && "Unknown cast!"); 01177 } 01178 } else if (isFloatingPoint(SrcVT)) { 01179 if (isFloatingPoint(DestVT)) { // FP -> FP cast 01180 if (DestVT < SrcVT) // Rounding cast? 01181 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N)); 01182 else 01183 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N)); 01184 } else if (isInteger(DestVT)) { // FP -> Int cast. 01185 if (I.getType()->isSigned()) 01186 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N)); 01187 else 01188 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N)); 01189 } else { 01190 assert(0 && "Unknown cast!"); 01191 } 01192 } else { 01193 assert(SrcVT == MVT::Vector && "Unknown cast!"); 01194 assert(DestVT != MVT::Vector && "Casts to vector already handled!"); 01195 // This is a cast from a vector to something else. This is always a bit 01196 // convert. Get information about the input vector. 01197 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N)); 01198 } 01199 } 01200 01201 void SelectionDAGLowering::visitInsertElement(User &I) { 01202 SDOperand InVec = getValue(I.getOperand(0)); 01203 SDOperand InVal = getValue(I.getOperand(1)); 01204 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 01205 getValue(I.getOperand(2))); 01206 01207 SDOperand Num = *(InVec.Val->op_end()-2); 01208 SDOperand Typ = *(InVec.Val->op_end()-1); 01209 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector, 01210 InVec, InVal, InIdx, Num, Typ)); 01211 } 01212 01213 void SelectionDAGLowering::visitExtractElement(User &I) { 01214 SDOperand InVec = getValue(I.getOperand(0)); 01215 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 01216 getValue(I.getOperand(1))); 01217 SDOperand Typ = *(InVec.Val->op_end()-1); 01218 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, 01219 TLI.getValueType(I.getType()), InVec, InIdx)); 01220 } 01221 01222 void SelectionDAGLowering::visitShuffleVector(User &I) { 01223 SDOperand V1 = getValue(I.getOperand(0)); 01224 SDOperand V2 = getValue(I.getOperand(1)); 01225 SDOperand Mask = getValue(I.getOperand(2)); 01226 01227 SDOperand Num = *(V1.Val->op_end()-2); 01228 SDOperand Typ = *(V2.Val->op_end()-1); 01229 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 01230 V1, V2, Mask, Num, Typ)); 01231 } 01232 01233 01234 void SelectionDAGLowering::visitGetElementPtr(User &I) { 01235 SDOperand N = getValue(I.getOperand(0)); 01236 const Type *Ty = I.getOperand(0)->getType(); 01237 01238 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 01239 OI != E; ++OI) { 01240 Value *Idx = *OI; 01241 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 01242 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 01243 if (Field) { 01244 // N = N + Offset 01245 uint64_t Offset = TD->getStructLayout(StTy)->MemberOffsets[Field]; 01246 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 01247 getIntPtrConstant(Offset)); 01248 } 01249 Ty = StTy->getElementType(Field); 01250 } else { 01251 Ty = cast<SequentialType>(Ty)->getElementType(); 01252 01253 // If this is a constant subscript, handle it quickly. 01254 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 01255 if (CI->getRawValue() == 0) continue; 01256 01257 uint64_t Offs; 01258 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI)) 01259 Offs = (int64_t)TD->getTypeSize(Ty)*CSI->getValue(); 01260 else 01261 Offs = TD->getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue(); 01262 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs)); 01263 continue; 01264 } 01265 01266 // N = N + Idx * ElementSize; 01267 uint64_t ElementSize = TD->getTypeSize(Ty); 01268 SDOperand IdxN = getValue(Idx); 01269 01270 // If the index is smaller or larger than intptr_t, truncate or extend 01271 // it. 01272 if (IdxN.getValueType() < N.getValueType()) { 01273 if (Idx->getType()->isSigned()) 01274 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN); 01275 else 01276 IdxN = DAG.getNode(ISD::ZERO_EXTEND, N.getValueType(), IdxN); 01277 } else if (IdxN.getValueType() > N.getValueType()) 01278 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN); 01279 01280 // If this is a multiply by a power of two, turn it into a shl 01281 // immediately. This is a very common case. 01282 if (isPowerOf2_64(ElementSize)) { 01283 unsigned Amt = Log2_64(ElementSize); 01284 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, 01285 DAG.getConstant(Amt, TLI.getShiftAmountTy())); 01286 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 01287 continue; 01288 } 01289 01290 SDOperand Scale = getIntPtrConstant(ElementSize); 01291 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 01292 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 01293 } 01294 } 01295 setValue(&I, N); 01296 } 01297 01298 void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 01299 // If this is a fixed sized alloca in the entry block of the function, 01300 // allocate it statically on the stack. 01301 if (FuncInfo.StaticAllocaMap.count(&I)) 01302 return; // getValue will auto-populate this. 01303 01304 const Type *Ty = I.getAllocatedType(); 01305 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty); 01306 unsigned Align = std::max((unsigned)TLI.getTargetData()->getTypeAlignment(Ty), 01307 I.getAlignment()); 01308 01309 SDOperand AllocSize = getValue(I.getArraySize()); 01310 MVT::ValueType IntPtr = TLI.getPointerTy(); 01311 if (IntPtr < AllocSize.getValueType()) 01312 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize); 01313 else if (IntPtr > AllocSize.getValueType()) 01314 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize); 01315 01316 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize, 01317 getIntPtrConstant(TySize)); 01318 01319 // Handle alignment. If the requested alignment is less than or equal to the 01320 // stack alignment, ignore it and round the size of the allocation up to the 01321 // stack alignment size. If the size is greater than the stack alignment, we 01322 // note this in the DYNAMIC_STACKALLOC node. 01323 unsigned StackAlign = 01324 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 01325 if (Align <= StackAlign) { 01326 Align = 0; 01327 // Add SA-1 to the size. 01328 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 01329 getIntPtrConstant(StackAlign-1)); 01330 // Mask out the low bits for alignment purposes. 01331 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 01332 getIntPtrConstant(~(uint64_t)(StackAlign-1))); 01333 } 01334 01335 std::vector<MVT::ValueType> VTs; 01336 VTs.push_back(AllocSize.getValueType()); 01337 VTs.push_back(MVT::Other); 01338 std::vector<SDOperand> Ops; 01339 Ops.push_back(getRoot()); 01340 Ops.push_back(AllocSize); 01341 Ops.push_back(getIntPtrConstant(Align)); 01342 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops); 01343 DAG.setRoot(setValue(&I, DSA).getValue(1)); 01344 01345 // Inform the Frame Information that we have just allocated a variable-sized 01346 // object. 01347 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 01348 } 01349 01350 void SelectionDAGLowering::visitLoad(LoadInst &I) { 01351 SDOperand Ptr = getValue(I.getOperand(0)); 01352 01353 SDOperand Root; 01354 if (I.isVolatile()) 01355 Root = getRoot(); 01356 else { 01357 // Do not serialize non-volatile loads against each other. 01358 Root = DAG.getRoot(); 01359 } 01360 01361 setValue(&I, getLoadFrom(I.getType(), Ptr, DAG.getSrcValue(I.getOperand(0)), 01362 Root, I.isVolatile())); 01363 } 01364 01365 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr, 01366 SDOperand SrcValue, SDOperand Root, 01367 bool isVolatile) { 01368 SDOperand L; 01369 if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) { 01370 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 01371 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr, SrcValue); 01372 } else { 01373 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SrcValue); 01374 } 01375 01376 if (isVolatile) 01377 DAG.setRoot(L.getValue(1)); 01378 else 01379 PendingLoads.push_back(L.getValue(1)); 01380 01381 return L; 01382 } 01383 01384 01385 void SelectionDAGLowering::visitStore(StoreInst &I) { 01386 Value *SrcV = I.getOperand(0); 01387 SDOperand Src = getValue(SrcV); 01388 SDOperand Ptr = getValue(I.getOperand(1)); 01389 DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr, 01390 DAG.getSrcValue(I.getOperand(1)))); 01391 } 01392 01393 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot 01394 /// access memory and has no other side effects at all. 01395 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) { 01396 #define GET_NO_MEMORY_INTRINSICS 01397 #include "llvm/Intrinsics.gen" 01398 #undef GET_NO_MEMORY_INTRINSICS 01399 return false; 01400 } 01401 01402 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't 01403 // have any side-effects or if it only reads memory. 01404 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) { 01405 #define GET_SIDE_EFFECT_INFO 01406 #include "llvm/Intrinsics.gen" 01407 #undef GET_SIDE_EFFECT_INFO 01408 return false; 01409 } 01410 01411 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC 01412 /// node. 01413 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I, 01414 unsigned Intrinsic) { 01415 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic); 01416 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic); 01417 01418 // Build the operand list. 01419 std::vector<SDOperand> Ops; 01420 if (HasChain) { // If this intrinsic has side-effects, chainify it. 01421 if (OnlyLoad) { 01422 // We don't need to serialize loads against other loads. 01423 Ops.push_back(DAG.getRoot()); 01424 } else { 01425 Ops.push_back(getRoot()); 01426 } 01427 } 01428 01429 // Add the intrinsic ID as an integer operand. 01430 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy())); 01431 01432 // Add all operands of the call to the operand list. 01433 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 01434 SDOperand Op = getValue(I.getOperand(i)); 01435 01436 // If this is a vector type, force it to the right packed type. 01437 if (Op.getValueType() == MVT::Vector) { 01438 const PackedType *OpTy = cast<PackedType>(I.getOperand(i)->getType()); 01439 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType()); 01440 01441 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements()); 01442 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?"); 01443 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op); 01444 } 01445 01446 assert(TLI.isTypeLegal(Op.getValueType()) && 01447 "Intrinsic uses a non-legal type?"); 01448 Ops.push_back(Op); 01449 } 01450 01451 std::vector<MVT::ValueType> VTs; 01452 if (I.getType() != Type::VoidTy) { 01453 MVT::ValueType VT = TLI.getValueType(I.getType()); 01454 if (VT == MVT::Vector) { 01455 const PackedType *DestTy = cast<PackedType>(I.getType()); 01456 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 01457 01458 VT = MVT::getVectorType(EltVT, DestTy->getNumElements()); 01459 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?"); 01460 } 01461 01462 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?"); 01463 VTs.push_back(VT); 01464 } 01465 if (HasChain) 01466 VTs.push_back(MVT::Other); 01467 01468 // Create the node. 01469 SDOperand Result; 01470 if (!HasChain) 01471 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTs, Ops); 01472 else if (I.getType() != Type::VoidTy) 01473 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTs, Ops); 01474 else 01475 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTs, Ops); 01476 01477 if (HasChain) { 01478 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1); 01479 if (OnlyLoad) 01480 PendingLoads.push_back(Chain); 01481 else 01482 DAG.setRoot(Chain); 01483 } 01484 if (I.getType() != Type::VoidTy) { 01485 if (const PackedType *PTy = dyn_cast<PackedType>(I.getType())) { 01486 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType()); 01487 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 01488 DAG.getConstant(PTy->getNumElements(), MVT::i32), 01489 DAG.getValueType(EVT)); 01490 } 01491 setValue(&I, Result); 01492 } 01493 } 01494 01495 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If 01496 /// we want to emit this as a call to a named external function, return the name 01497 /// otherwise lower it and return null. 01498 const char * 01499 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { 01500 switch (Intrinsic) { 01501 default: 01502 // By default, turn this into a target intrinsic node. 01503 visitTargetIntrinsic(I, Intrinsic); 01504 return 0; 01505 case Intrinsic::vastart: visitVAStart(I); return 0; 01506 case Intrinsic::vaend: visitVAEnd(I); return 0; 01507 case Intrinsic::vacopy: visitVACopy(I); return 0; 01508 case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return 0; 01509 case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return 0; 01510 case Intrinsic::setjmp: 01511 return "_setjmp"+!TLI.usesUnderscoreSetJmpLongJmp(); 01512 break; 01513 case Intrinsic::longjmp: 01514 return "_longjmp"+!TLI.usesUnderscoreSetJmpLongJmp(); 01515 break; 01516 case Intrinsic::memcpy_i32: 01517 case Intrinsic::memcpy_i64: 01518 visitMemIntrinsic(I, ISD::MEMCPY); 01519 return 0; 01520 case Intrinsic::memset_i32: 01521 case Intrinsic::memset_i64: 01522 visitMemIntrinsic(I, ISD::MEMSET); 01523 return 0; 01524 case Intrinsic::memmove_i32: 01525 case Intrinsic::memmove_i64: 01526 visitMemIntrinsic(I, ISD::MEMMOVE); 01527 return 0; 01528 01529 case Intrinsic::dbg_stoppoint: { 01530 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01531 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I); 01532 if (DebugInfo && SPI.getContext() && DebugInfo->Verify(SPI.getContext())) { 01533 std::vector<SDOperand> Ops; 01534 01535 Ops.push_back(getRoot()); 01536 Ops.push_back(getValue(SPI.getLineValue())); 01537 Ops.push_back(getValue(SPI.getColumnValue())); 01538 01539 DebugInfoDesc *DD = DebugInfo->getDescFor(SPI.getContext()); 01540 assert(DD && "Not a debug information descriptor"); 01541 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD); 01542 01543 Ops.push_back(DAG.getString(CompileUnit->getFileName())); 01544 Ops.push_back(DAG.getString(CompileUnit->getDirectory())); 01545 01546 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops)); 01547 } 01548 01549 return 0; 01550 } 01551 case Intrinsic::dbg_region_start: { 01552 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01553 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I); 01554 if (DebugInfo && RSI.getContext() && DebugInfo->Verify(RSI.getContext())) { 01555 std::vector<SDOperand> Ops; 01556 01557 unsigned LabelID = DebugInfo->RecordRegionStart(RSI.getContext()); 01558 01559 Ops.push_back(getRoot()); 01560 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01561 01562 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01563 } 01564 01565 return 0; 01566 } 01567 case Intrinsic::dbg_region_end: { 01568 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01569 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I); 01570 if (DebugInfo && REI.getContext() && DebugInfo->Verify(REI.getContext())) { 01571 std::vector<SDOperand> Ops; 01572 01573 unsigned LabelID = DebugInfo->RecordRegionEnd(REI.getContext()); 01574 01575 Ops.push_back(getRoot()); 01576 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01577 01578 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01579 } 01580 01581 return 0; 01582 } 01583 case Intrinsic::dbg_func_start: { 01584 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01585 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I); 01586 if (DebugInfo && FSI.getSubprogram() && 01587 DebugInfo->Verify(FSI.getSubprogram())) { 01588 std::vector<SDOperand> Ops; 01589 01590 unsigned LabelID = DebugInfo->RecordRegionStart(FSI.getSubprogram()); 01591 01592 Ops.push_back(getRoot()); 01593 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01594 01595 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01596 } 01597 01598 return 0; 01599 } 01600 case Intrinsic::dbg_declare: { 01601 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01602 DbgDeclareInst &DI = cast<DbgDeclareInst>(I); 01603 if (DebugInfo && DI.getVariable() && DebugInfo->Verify(DI.getVariable())) { 01604 std::vector<SDOperand> Ops; 01605 01606 SDOperand AddressOp = getValue(DI.getAddress()); 01607 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp)) { 01608 DebugInfo->RecordVariable(DI.getVariable(), FI->getIndex()); 01609 } 01610 } 01611 01612 return 0; 01613 } 01614 01615 case Intrinsic::isunordered_f32: 01616 case Intrinsic::isunordered_f64: 01617 setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)), 01618 getValue(I.getOperand(2)), ISD::SETUO)); 01619 return 0; 01620 01621 case Intrinsic::sqrt_f32: 01622 case Intrinsic::sqrt_f64: 01623 setValue(&I, DAG.getNode(ISD::FSQRT, 01624 getValue(I.getOperand(1)).getValueType(), 01625 getValue(I.getOperand(1)))); 01626 return 0; 01627 case Intrinsic::pcmarker: { 01628 SDOperand Tmp = getValue(I.getOperand(1)); 01629 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp)); 01630 return 0; 01631 } 01632 case Intrinsic::readcyclecounter: { 01633 std::vector<MVT::ValueType> VTs; 01634 VTs.push_back(MVT::i64); 01635 VTs.push_back(MVT::Other); 01636 std::vector<SDOperand> Ops; 01637 Ops.push_back(getRoot()); 01638 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, VTs, Ops); 01639 setValue(&I, Tmp); 01640 DAG.setRoot(Tmp.getValue(1)); 01641 return 0; 01642 } 01643 case Intrinsic::bswap_i16: 01644 case Intrinsic::bswap_i32: 01645 case Intrinsic::bswap_i64: 01646 setValue(&I, DAG.getNode(ISD::BSWAP, 01647 getValue(I.getOperand(1)).getValueType(), 01648 getValue(I.getOperand(1)))); 01649 return 0; 01650 case Intrinsic::cttz_i8: 01651 case Intrinsic::cttz_i16: 01652 case Intrinsic::cttz_i32: 01653 case Intrinsic::cttz_i64: 01654 setValue(&I, DAG.getNode(ISD::CTTZ, 01655 getValue(I.getOperand(1)).getValueType(), 01656 getValue(I.getOperand(1)))); 01657 return 0; 01658 case Intrinsic::ctlz_i8: 01659 case Intrinsic::ctlz_i16: 01660 case Intrinsic::ctlz_i32: 01661 case Intrinsic::ctlz_i64: 01662 setValue(&I, DAG.getNode(ISD::CTLZ, 01663 getValue(I.getOperand(1)).getValueType(), 01664 getValue(I.getOperand(1)))); 01665 return 0; 01666 case Intrinsic::ctpop_i8: 01667 case Intrinsic::ctpop_i16: 01668 case Intrinsic::ctpop_i32: 01669 case Intrinsic::ctpop_i64: 01670 setValue(&I, DAG.getNode(ISD::CTPOP, 01671 getValue(I.getOperand(1)).getValueType(), 01672 getValue(I.getOperand(1)))); 01673 return 0; 01674 case Intrinsic::stacksave: { 01675 std::vector<MVT::ValueType> VTs; 01676 VTs.push_back(TLI.getPointerTy()); 01677 VTs.push_back(MVT::Other); 01678 std::vector<SDOperand> Ops; 01679 Ops.push_back(getRoot()); 01680 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE, VTs, Ops); 01681 setValue(&I, Tmp); 01682 DAG.setRoot(Tmp.getValue(1)); 01683 return 0; 01684 } 01685 case Intrinsic::stackrestore: { 01686 SDOperand Tmp = getValue(I.getOperand(1)); 01687 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp)); 01688 return 0; 01689 } 01690 case Intrinsic::prefetch: 01691 // FIXME: Currently discarding prefetches. 01692 return 0; 01693 } 01694 } 01695 01696 01697 void SelectionDAGLowering::visitCall(CallInst &I) { 01698 const char *RenameFn = 0; 01699 if (Function *F = I.getCalledFunction()) { 01700 if (F->isExternal()) 01701 if (unsigned IID = F->getIntrinsicID()) { 01702 RenameFn = visitIntrinsicCall(I, IID); 01703 if (!RenameFn) 01704 return; 01705 } else { // Not an LLVM intrinsic. 01706 const std::string &Name = F->getName(); 01707 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) { 01708 if (I.getNumOperands() == 3 && // Basic sanity checks. 01709 I.getOperand(1)->getType()->isFloatingPoint() && 01710 I.getType() == I.getOperand(1)->getType() && 01711 I.getType() == I.getOperand(2)->getType()) { 01712 SDOperand LHS = getValue(I.getOperand(1)); 01713 SDOperand RHS = getValue(I.getOperand(2)); 01714 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(), 01715 LHS, RHS)); 01716 return; 01717 } 01718 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) { 01719 if (I.getNumOperands() == 2 && // Basic sanity checks. 01720 I.getOperand(1)->getType()->isFloatingPoint() && 01721 I.getType() == I.getOperand(1)->getType()) { 01722 SDOperand Tmp = getValue(I.getOperand(1)); 01723 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp)); 01724 return; 01725 } 01726 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) { 01727 if (I.getNumOperands() == 2 && // Basic sanity checks. 01728 I.getOperand(1)->getType()->isFloatingPoint() && 01729 I.getType() == I.getOperand(1)->getType()) { 01730 SDOperand Tmp = getValue(I.getOperand(1)); 01731 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp)); 01732 return; 01733 } 01734 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) { 01735 if (I.getNumOperands() == 2 && // Basic sanity checks. 01736 I.getOperand(1)->getType()->isFloatingPoint() && 01737 I.getType() == I.getOperand(1)->getType()) { 01738 SDOperand Tmp = getValue(I.getOperand(1)); 01739 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp)); 01740 return; 01741 } 01742 } 01743 } 01744 } else if (isa<InlineAsm>(I.getOperand(0))) { 01745 visitInlineAsm(I); 01746 return; 01747 } 01748 01749 SDOperand Callee; 01750 if (!RenameFn) 01751 Callee = getValue(I.getOperand(0)); 01752 else 01753 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 01754 std::vector<std::pair<SDOperand, const Type*> > Args; 01755 Args.reserve(I.getNumOperands()); 01756 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 01757 Value *Arg = I.getOperand(i); 01758 SDOperand ArgNode = getValue(Arg); 01759 Args.push_back(std::make_pair(ArgNode, Arg->getType())); 01760 } 01761 01762 const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType()); 01763 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 01764 01765 std::pair<SDOperand,SDOperand> Result = 01766 TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(), 01767 I.isTailCall(), Callee, Args, DAG); 01768 if (I.getType() != Type::VoidTy) 01769 setValue(&I, Result.first); 01770 DAG.setRoot(Result.second); 01771 } 01772 01773 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, 01774 SDOperand &Chain, SDOperand &Flag)const{ 01775 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag); 01776 Chain = Val.getValue(1); 01777 Flag = Val.getValue(2); 01778 01779 // If the result was expanded, copy from the top part. 01780 if (Regs.size() > 1) { 01781 assert(Regs.size() == 2 && 01782 "Cannot expand to more than 2 elts yet!"); 01783 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag); 01784 Chain = Val.getValue(1); 01785 Flag = Val.getValue(2); 01786 if (DAG.getTargetLoweringInfo().isLittleEndian()) 01787 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi); 01788 else 01789 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val); 01790 } 01791 01792 // Otherwise, if the return value was promoted or extended, truncate it to the 01793 // appropriate type. 01794 if (RegVT == ValueVT) 01795 return Val; 01796 01797 if (MVT::isInteger(RegVT)) { 01798 if (ValueVT < RegVT) 01799 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 01800 else 01801 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val); 01802 } else { 01803 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val); 01804 } 01805 } 01806 01807 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 01808 /// specified value into the registers specified by this object. This uses 01809 /// Chain/Flag as the input and updates them for the output Chain/Flag. 01810 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 01811 SDOperand &Chain, SDOperand &Flag, 01812 MVT::ValueType PtrVT) const { 01813 if (Regs.size() == 1) { 01814 // If there is a single register and the types differ, this must be 01815 // a promotion. 01816 if (RegVT != ValueVT) { 01817 if (MVT::isInteger(RegVT)) { 01818 if (RegVT < ValueVT) 01819 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val); 01820 else 01821 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val); 01822 } else 01823 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val); 01824 } 01825 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag); 01826 Flag = Chain.getValue(1); 01827 } else { 01828 std::vector<unsigned> R(Regs); 01829 if (!DAG.getTargetLoweringInfo().isLittleEndian()) 01830 std::reverse(R.begin(), R.end()); 01831 01832 for (unsigned i = 0, e = R.size(); i != e; ++i) { 01833 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val, 01834 DAG.getConstant(i, PtrVT)); 01835 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag); 01836 Flag = Chain.getValue(1); 01837 } 01838 } 01839 } 01840 01841 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 01842 /// operand list. This adds the code marker and includes the number of 01843 /// values added into it. 01844 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 01845 std::vector<SDOperand> &Ops) const { 01846 Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32)); 01847 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 01848 Ops.push_back(DAG.getRegister(Regs[i], RegVT)); 01849 } 01850 01851 /// isAllocatableRegister - If the specified register is safe to allocate, 01852 /// i.e. it isn't a stack pointer or some other special register, return the 01853 /// register class for the register. Otherwise, return null. 01854 static const TargetRegisterClass * 01855 isAllocatableRegister(unsigned Reg, MachineFunction &MF, 01856 const TargetLowering &TLI, const MRegisterInfo *MRI) { 01857 MVT::ValueType FoundVT = MVT::Other; 01858 const TargetRegisterClass *FoundRC = 0; 01859 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(), 01860 E = MRI->regclass_end(); RCI != E; ++RCI) { 01861 MVT::ValueType ThisVT = MVT::Other; 01862 01863 const TargetRegisterClass *RC = *RCI; 01864 // If none of the the value types for this register class are valid, we 01865 // can't use it. For example, 64-bit reg classes on 32-bit targets. 01866 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 01867 I != E; ++I) { 01868 if (TLI.isTypeLegal(*I)) { 01869 // If we have already found this register in a different register class, 01870 // choose the one with the largest VT specified. For example, on 01871 // PowerPC, we favor f64 register classes over f32. 01872 if (FoundVT == MVT::Other || 01873 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) { 01874 ThisVT = *I; 01875 break; 01876 } 01877 } 01878 } 01879 01880 if (ThisVT == MVT::Other) continue; 01881 01882 // NOTE: This isn't ideal. In particular, this might allocate the 01883 // frame pointer in functions that need it (due to them not being taken 01884 // out of allocation, because a variable sized allocation hasn't been seen 01885 // yet). This is a slight code pessimization, but should still work. 01886 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 01887 E = RC->allocation_order_end(MF); I != E; ++I) 01888 if (*I == Reg) { 01889 // We found a matching register class. Keep looking at others in case 01890 // we find one with larger registers that this physreg is also in. 01891 FoundRC = RC; 01892 FoundVT = ThisVT; 01893 break; 01894 } 01895 } 01896 return FoundRC; 01897 } 01898 01899 RegsForValue SelectionDAGLowering:: 01900 GetRegistersForValue(const std::string &ConstrCode, 01901 MVT::ValueType VT, bool isOutReg, bool isInReg, 01902 std::set<unsigned> &OutputRegs, 01903 std::set<unsigned> &InputRegs) { 01904 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 01905 TLI.getRegForInlineAsmConstraint(ConstrCode, VT); 01906 std::vector<unsigned> Regs; 01907 01908 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1; 01909 MVT::ValueType RegVT; 01910 MVT::ValueType ValueVT = VT; 01911 01912 if (PhysReg.first) { 01913 if (VT == MVT::Other) 01914 ValueVT = *PhysReg.second->vt_begin(); 01915 01916 // Get the actual register value type. This is important, because the user 01917 // may have asked for (e.g.) the AX register in i32 type. We need to 01918 // remember that AX is actually i16 to get the right extension. 01919 RegVT = *PhysReg.second->vt_begin(); 01920 01921 // This is a explicit reference to a physical register. 01922 Regs.push_back(PhysReg.first); 01923 01924 // If this is an expanded reference, add the rest of the regs to Regs. 01925 if (NumRegs != 1) { 01926 TargetRegisterClass::iterator I = PhysReg.second->begin(); 01927 TargetRegisterClass::iterator E = PhysReg.second->end(); 01928 for (; *I != PhysReg.first; ++I) 01929 assert(I != E && "Didn't find reg!"); 01930 01931 // Already added the first reg. 01932 --NumRegs; ++I; 01933 for (; NumRegs; --NumRegs, ++I) { 01934 assert(I != E && "Ran out of registers to allocate!"); 01935 Regs.push_back(*I); 01936 } 01937 } 01938 return RegsForValue(Regs, RegVT, ValueVT); 01939 } 01940 01941 // This is a reference to a register class. Allocate NumRegs consecutive, 01942 // available, registers from the class. 01943 std::vector<unsigned> RegClassRegs = 01944 TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT); 01945 01946 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo(); 01947 MachineFunction &MF = *CurMBB->getParent(); 01948 unsigned NumAllocated = 0; 01949 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 01950 unsigned Reg = RegClassRegs[i]; 01951 // See if this register is available. 01952 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 01953 (isInReg && InputRegs.count(Reg))) { // Already used. 01954 // Make sure we find consecutive registers. 01955 NumAllocated = 0; 01956 continue; 01957 } 01958 01959 // Check to see if this register is allocatable (i.e. don't give out the 01960 // stack pointer). 01961 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI); 01962 if (!RC) { 01963 // Make sure we find consecutive registers. 01964 NumAllocated = 0; 01965 continue; 01966 } 01967 01968 // Okay, this register is good, we can use it. 01969 ++NumAllocated; 01970 01971 // If we allocated enough consecutive 01972 if (NumAllocated == NumRegs) { 01973 unsigned RegStart = (i-NumAllocated)+1; 01974 unsigned RegEnd = i+1; 01975 // Mark all of the allocated registers used. 01976 for (unsigned i = RegStart; i != RegEnd; ++i) { 01977 unsigned Reg = RegClassRegs[i]; 01978 Regs.push_back(Reg); 01979 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used. 01980 if (isInReg) InputRegs.insert(Reg); // Mark reg used. 01981 } 01982 01983 return RegsForValue(Regs, *RC->vt_begin(), VT); 01984 } 01985 } 01986 01987 // Otherwise, we couldn't allocate enough registers for this. 01988 return RegsForValue(); 01989 } 01990 01991 01992 /// visitInlineAsm - Handle a call to an InlineAsm object. 01993 /// 01994 void SelectionDAGLowering::visitInlineAsm(CallInst &I) { 01995 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0)); 01996 01997 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), 01998 MVT::Other); 01999 02000 // Note, we treat inline asms both with and without side-effects as the same. 02001 // If an inline asm doesn't have side effects and doesn't access memory, we 02002 // could not choose to not chain it. 02003 bool hasSideEffects = IA->hasSideEffects(); 02004 02005 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints(); 02006 std::vector<MVT::ValueType> ConstraintVTs; 02007 02008 /// AsmNodeOperands - A list of pairs. The first element is a register, the 02009 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set 02010 /// if it is a def of that register. 02011 std::vector<SDOperand> AsmNodeOperands; 02012 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain 02013 AsmNodeOperands.push_back(AsmStr); 02014 02015 SDOperand Chain = getRoot(); 02016 SDOperand Flag; 02017 02018 // We fully assign registers here at isel time. This is not optimal, but 02019 // should work. For register classes that correspond to LLVM classes, we 02020 // could let the LLVM RA do its thing, but we currently don't. Do a prepass 02021 // over the constraints, collecting fixed registers that we know we can't use. 02022 std::set<unsigned> OutputRegs, InputRegs; 02023 unsigned OpNum = 1; 02024 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 02025 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 02026 std::string &ConstraintCode = Constraints[i].Codes[0]; 02027 02028 MVT::ValueType OpVT; 02029 02030 // Compute the value type for each operand and add it to ConstraintVTs. 02031 switch (Constraints[i].Type) { 02032 case InlineAsm::isOutput: 02033 if (!Constraints[i].isIndirectOutput) { 02034 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 02035 OpVT = TLI.getValueType(I.getType()); 02036 } else { 02037 const Type *OpTy = I.getOperand(OpNum)->getType(); 02038 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType()); 02039 OpNum++; // Consumes a call operand. 02040 } 02041 break; 02042 case InlineAsm::isInput: 02043 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType()); 02044 OpNum++; // Consumes a call operand. 02045 break; 02046 case InlineAsm::isClobber: 02047 OpVT = MVT::Other; 02048 break; 02049 } 02050 02051 ConstraintVTs.push_back(OpVT); 02052 02053 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0) 02054 continue; // Not assigned a fixed reg. 02055 02056 // Build a list of regs that this operand uses. This always has a single 02057 // element for promoted/expanded operands. 02058 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT, 02059 false, false, 02060 OutputRegs, InputRegs); 02061 02062 switch (Constraints[i].Type) { 02063 case InlineAsm::isOutput: 02064 // We can't assign any other output to this register. 02065 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 02066 // If this is an early-clobber output, it cannot be assigned to the same 02067 // value as the input reg. 02068 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 02069 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 02070 break; 02071 case InlineAsm::isInput: 02072 // We can't assign any other input to this register. 02073 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 02074 break; 02075 case InlineAsm::isClobber: 02076 // Clobbered regs cannot be used as inputs or outputs. 02077 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 02078 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 02079 break; 02080 } 02081 } 02082 02083 // Loop over all of the inputs, copying the operand values into the 02084 // appropriate registers and processing the output regs. 02085 RegsForValue RetValRegs; 02086 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 02087 OpNum = 1; 02088 02089 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 02090 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 02091 std::string &ConstraintCode = Constraints[i].Codes[0]; 02092 02093 switch (Constraints[i].Type) { 02094 case InlineAsm::isOutput: { 02095 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 02096 if (ConstraintCode.size() == 1) // not a physreg name. 02097 CTy = TLI.getConstraintType(ConstraintCode[0]); 02098 02099 if (CTy == TargetLowering::C_Memory) { 02100 // Memory output. 02101 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 02102 02103 // Check that the operand (the address to store to) isn't a float. 02104 if (!MVT::isInteger(InOperandVal.getValueType())) 02105 assert(0 && "MATCH FAIL!"); 02106 02107 if (!Constraints[i].isIndirectOutput) 02108 assert(0 && "MATCH FAIL!"); 02109 02110 OpNum++; // Consumes a call operand. 02111 02112 // Extend/truncate to the right pointer type if needed. 02113 MVT::ValueType PtrType = TLI.getPointerTy(); 02114 if (InOperandVal.getValueType() < PtrType) 02115 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 02116 else if (InOperandVal.getValueType() > PtrType) 02117 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 02118 02119 // Add information to the INLINEASM node to know about this output. 02120 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 02121 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 02122 AsmNodeOperands.push_back(InOperandVal); 02123 break; 02124 } 02125 02126 // Otherwise, this is a register output. 02127 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 02128 02129 // If this is an early-clobber output, or if there is an input 02130 // constraint that matches this, we need to reserve the input register 02131 // so no other inputs allocate to it. 02132 bool UsesInputRegister = false; 02133 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 02134 UsesInputRegister = true; 02135 02136 // Copy the output from the appropriate register. Find a register that 02137 // we can use. 02138 RegsForValue Regs = 02139 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 02140 true, UsesInputRegister, 02141 OutputRegs, InputRegs); 02142 assert(!Regs.Regs.empty() && "Couldn't allocate output reg!"); 02143 02144 if (!Constraints[i].isIndirectOutput) { 02145 assert(RetValRegs.Regs.empty() && 02146 "Cannot have multiple output constraints yet!"); 02147 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 02148 RetValRegs = Regs; 02149 } else { 02150 IndirectStoresToEmit.push_back(std::make_pair(Regs, 02151 I.getOperand(OpNum))); 02152 OpNum++; // Consumes a call operand. 02153 } 02154 02155 // Add information to the INLINEASM node to know that this register is 02156 // set. 02157 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands); 02158 break; 02159 } 02160 case InlineAsm::isInput: { 02161 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 02162 OpNum++; // Consumes a call operand. 02163 02164 if (isdigit(ConstraintCode[0])) { // Matching constraint? 02165 // If this is required to match an output register we have already set, 02166 // just use its register. 02167 unsigned OperandNo = atoi(ConstraintCode.c_str()); 02168 02169 // Scan until we find the definition we already emitted of this operand. 02170 // When we find it, create a RegsForValue operand. 02171 unsigned CurOp = 2; // The first operand. 02172 for (; OperandNo; --OperandNo) { 02173 // Advance to the next operand. 02174 unsigned NumOps = 02175 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 02176 assert(((NumOps & 7) == 2 /*REGDEF*/ || 02177 (NumOps & 7) == 4 /*MEM*/) && 02178 "Skipped past definitions?"); 02179 CurOp += (NumOps>>3)+1; 02180 } 02181 02182 unsigned NumOps = 02183 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 02184 assert((NumOps & 7) == 2 /*REGDEF*/ && 02185 "Skipped past definitions?"); 02186 02187 // Add NumOps>>3 registers to MatchedRegs. 02188 RegsForValue MatchedRegs; 02189 MatchedRegs.ValueVT = InOperandVal.getValueType(); 02190 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType(); 02191 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) { 02192 unsigned Reg=cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg(); 02193 MatchedRegs.Regs.push_back(Reg); 02194 } 02195 02196 // Use the produced MatchedRegs object to 02197 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, 02198 TLI.getPointerTy()); 02199 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands); 02200 break; 02201 } 02202 02203 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 02204 if (ConstraintCode.size() == 1) // not a physreg name. 02205 CTy = TLI.getConstraintType(ConstraintCode[0]); 02206 02207 if (CTy == TargetLowering::C_Other) { 02208 if (!TLI.isOperandValidForConstraint(InOperandVal, ConstraintCode[0])) 02209 assert(0 && "MATCH FAIL!"); 02210 02211 // Add information to the INLINEASM node to know about this input. 02212 unsigned ResOpType = 3 /*IMM*/ | (1 << 3); 02213 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 02214 AsmNodeOperands.push_back(InOperandVal); 02215 break; 02216 } else if (CTy == TargetLowering::C_Memory) { 02217 // Memory input. 02218 02219 // Check that the operand isn't a float. 02220 if (!MVT::isInteger(InOperandVal.getValueType())) 02221 assert(0 && "MATCH FAIL!"); 02222 02223 // Extend/truncate to the right pointer type if needed. 02224 MVT::ValueType PtrType = TLI.getPointerTy(); 02225 if (InOperandVal.getValueType() < PtrType) 02226 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 02227 else if (InOperandVal.getValueType() > PtrType) 02228 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 02229 02230 // Add information to the INLINEASM node to know about this input. 02231 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 02232 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 02233 AsmNodeOperands.push_back(InOperandVal); 02234 break; 02235 } 02236 02237 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 02238 02239 // Copy the input into the appropriate registers. 02240 RegsForValue InRegs = 02241 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 02242 false, true, OutputRegs, InputRegs); 02243 // FIXME: should be match fail. 02244 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!"); 02245 02246 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy()); 02247 02248 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands); 02249 break; 02250 } 02251 case InlineAsm::isClobber: { 02252 RegsForValue ClobberedRegs = 02253 GetRegistersForValue(ConstraintCode, MVT::Other, false, false, 02254 OutputRegs, InputRegs); 02255 // Add the clobbered value to the operand list, so that the register 02256 // allocator is aware that the physreg got clobbered. 02257 if (!ClobberedRegs.Regs.empty()) 02258 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands); 02259 break; 02260 } 02261 } 02262 } 02263 02264 // Finish up input operands. 02265 AsmNodeOperands[0] = Chain; 02266 if (Flag.Val) AsmNodeOperands.push_back(Flag); 02267 02268 std::vector<MVT::ValueType> VTs; 02269 VTs.push_back(MVT::Other); 02270 VTs.push_back(MVT::Flag); 02271 Chain = DAG.getNode(ISD::INLINEASM, VTs, AsmNodeOperands); 02272 Flag = Chain.getValue(1); 02273 02274 // If this asm returns a register value, copy the result from that register 02275 // and set it as the value of the call. 02276 if (!RetValRegs.Regs.empty()) 02277 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag)); 02278 02279 std::vector<std::pair<SDOperand, Value*> > StoresToEmit; 02280 02281 // Process indirect outputs, first output all of the flagged copies out of 02282 // physregs. 02283 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 02284 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 02285 Value *Ptr = IndirectStoresToEmit[i].second; 02286 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag); 02287 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 02288 } 02289 02290 // Emit the non-flagged stores from the physregs. 02291 std::vector<SDOperand> OutChains; 02292 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 02293 OutChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain, 02294 StoresToEmit[i].first, 02295 getValue(StoresToEmit[i].second), 02296 DAG.getSrcValue(StoresToEmit[i].second))); 02297 if (!OutChains.empty()) 02298 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains); 02299 DAG.setRoot(Chain); 02300 } 02301 02302 02303 void SelectionDAGLowering::visitMalloc(MallocInst &I) { 02304 SDOperand Src = getValue(I.getOperand(0)); 02305 02306 MVT::ValueType IntPtr = TLI.getPointerTy(); 02307 02308 if (IntPtr < Src.getValueType()) 02309 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 02310 else if (IntPtr > Src.getValueType()) 02311 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 02312 02313 // Scale the source by the type size. 02314 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType()); 02315 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 02316 Src, getIntPtrConstant(ElementSize)); 02317 02318 std::vector<std::pair<SDOperand, const Type*> > Args; 02319 Args.push_back(std::make_pair(Src, TLI.getTargetData()->getIntPtrType())); 02320 02321 std::pair<SDOperand,SDOperand> Result = 02322 TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true, 02323 DAG.getExternalSymbol("malloc", IntPtr), 02324 Args, DAG); 02325 setValue(&I, Result.first); // Pointers always fit in registers 02326 DAG.setRoot(Result.second); 02327 } 02328 02329 void SelectionDAGLowering::visitFree(FreeInst &I) { 02330 std::vector<std::pair<SDOperand, const Type*> > Args; 02331 Args.push_back(std::make_pair(getValue(I.getOperand(0)), 02332 TLI.getTargetData()->getIntPtrType())); 02333 MVT::ValueType IntPtr = TLI.getPointerTy(); 02334 std::pair<SDOperand,SDOperand> Result = 02335 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true, 02336 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 02337 DAG.setRoot(Result.second); 02338 } 02339 02340 // InsertAtEndOfBasicBlock - This method should be implemented by targets that 02341 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These 02342 // instructions are special in various ways, which require special support to 02343 // insert. The specified MachineInstr is created but not inserted into any 02344 // basic blocks, and the scheduler passes ownership of it to this method. 02345 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI, 02346 MachineBasicBlock *MBB) { 02347 std::cerr << "If a target marks an instruction with " 02348 "'usesCustomDAGSchedInserter', it must implement " 02349 "TargetLowering::InsertAtEndOfBasicBlock!\n"; 02350 abort(); 02351 return 0; 02352 } 02353 02354 void SelectionDAGLowering::visitVAStart(CallInst &I) { 02355 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 02356 getValue(I.getOperand(1)), 02357 DAG.getSrcValue(I.getOperand(1)))); 02358 } 02359 02360 void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 02361 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(), 02362 getValue(I.getOperand(0)), 02363 DAG.getSrcValue(I.getOperand(0))); 02364 setValue(&I, V); 02365 DAG.setRoot(V.getValue(1)); 02366 } 02367 02368 void SelectionDAGLowering::visitVAEnd(CallInst &I) { 02369 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(), 02370 getValue(I.getOperand(1)), 02371 DAG.getSrcValue(I.getOperand(1)))); 02372 } 02373 02374 void SelectionDAGLowering::visitVACopy(CallInst &I) { 02375 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 02376 getValue(I.getOperand(1)), 02377 getValue(I.getOperand(2)), 02378 DAG.getSrcValue(I.getOperand(1)), 02379 DAG.getSrcValue(I.getOperand(2)))); 02380 } 02381 02382 /// TargetLowering::LowerArguments - This is the default LowerArguments 02383 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all 02384 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be 02385 /// integrated into SDISel. 02386 std::vector<SDOperand> 02387 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { 02388 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. 02389 std::vector<SDOperand> Ops; 02390 Ops.push_back(DAG.getRoot()); 02391 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); 02392 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); 02393 02394 // Add one result value for each formal argument. 02395 std::vector<MVT::ValueType> RetVals; 02396 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) { 02397 MVT::ValueType VT = getValueType(I->getType()); 02398 02399 switch (getTypeAction(VT)) { 02400 default: assert(0 && "Unknown type action!"); 02401 case Legal: 02402 RetVals.push_back(VT); 02403 break; 02404 case Promote: 02405 RetVals.push_back(getTypeToTransformTo(VT)); 02406 break; 02407 case Expand: 02408 if (VT != MVT::Vector) { 02409 // If this is a large integer, it needs to be broken up into small 02410 // integers. Figure out what the destination type is and how many small 02411 // integers it turns into. 02412 MVT::ValueType NVT = getTypeToTransformTo(VT); 02413 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02414 for (unsigned i = 0; i != NumVals; ++i) 02415 RetVals.push_back(NVT); 02416 } else { 02417 // Otherwise, this is a vector type. We only support legal vectors 02418 // right now. 02419 unsigned NumElems = cast<PackedType>(I->getType())->getNumElements(); 02420 const Type *EltTy = cast<PackedType>(I->getType())->getElementType(); 02421 02422 // Figure out if there is a Packed type corresponding to this Vector 02423 // type. If so, convert to the packed type. 02424 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02425 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02426 RetVals.push_back(TVT); 02427 } else { 02428 assert(0 && "Don't support illegal by-val vector arguments yet!"); 02429 } 02430 } 02431 break; 02432 } 02433 } 02434 02435 RetVals.push_back(MVT::Other); 02436 02437 // Create the node. 02438 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS, RetVals, Ops).Val; 02439 02440 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1)); 02441 02442 // Set up the return result vector. 02443 Ops.clear(); 02444 unsigned i = 0; 02445 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) { 02446 MVT::ValueType VT = getValueType(I->getType()); 02447 02448 switch (getTypeAction(VT)) { 02449 default: assert(0 && "Unknown type action!"); 02450 case Legal: 02451 Ops.push_back(SDOperand(Result, i++)); 02452 break; 02453 case Promote: { 02454 SDOperand Op(Result, i++); 02455 if (MVT::isInteger(VT)) { 02456 unsigned AssertOp = I->getType()->isSigned() ? ISD::AssertSext 02457 : ISD::AssertZext; 02458 Op = DAG.getNode(AssertOp, Op.getValueType(), Op, DAG.getValueType(VT)); 02459 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 02460 } else { 02461 assert(MVT::isFloatingPoint(VT) && "Not int or FP?"); 02462 Op = DAG.getNode(ISD::FP_ROUND, VT, Op); 02463 } 02464 Ops.push_back(Op); 02465 break; 02466 } 02467 case Expand: 02468 if (VT != MVT::Vector) { 02469 // If this is a large integer, it needs to be reassembled from small 02470 // integers. Figure out what the source elt type is and how many small 02471 // integers it is. 02472 MVT::ValueType NVT = getTypeToTransformTo(VT); 02473 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02474 if (NumVals == 2) { 02475 SDOperand Lo = SDOperand(Result, i++); 02476 SDOperand Hi = SDOperand(Result, i++); 02477 02478 if (!isLittleEndian()) 02479 std::swap(Lo, Hi); 02480 02481 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi)); 02482 } else { 02483 // Value scalarized into many values. Unimp for now. 02484 assert(0 && "Cannot expand i64 -> i16 yet!"); 02485 } 02486 } else { 02487 // Otherwise, this is a vector type. We only support legal vectors 02488 // right now. 02489 const PackedType *PTy = cast<PackedType>(I->getType()); 02490 unsigned NumElems = PTy->getNumElements(); 02491 const Type *EltTy = PTy->getElementType(); 02492 02493 // Figure out if there is a Packed type corresponding to this Vector 02494 // type. If so, convert to the packed type. 02495 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02496 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02497 SDOperand N = SDOperand(Result, i++); 02498 // Handle copies from generic vectors to registers. 02499 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N, 02500 DAG.getConstant(NumElems, MVT::i32), 02501 DAG.getValueType(getValueType(EltTy))); 02502 Ops.push_back(N); 02503 } else { 02504 assert(0 && "Don't support illegal by-val vector arguments yet!"); 02505 abort(); 02506 } 02507 } 02508 break; 02509 } 02510 } 02511 return Ops; 02512 } 02513 02514 02515 /// TargetLowering::LowerCallTo - This is the default LowerCallTo 02516 /// implementation, which just inserts an ISD::CALL node, which is later custom 02517 /// lowered by the target to something concrete. FIXME: When all targets are 02518 /// migrated to using ISD::CALL, this hook should be integrated into SDISel. 02519 std::pair<SDOperand, SDOperand> 02520 TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg, 02521 unsigned CallingConv, bool isTailCall, 02522 SDOperand Callee, 02523 ArgListTy &Args, SelectionDAG &DAG) { 02524 std::vector<SDOperand> Ops; 02525 Ops.push_back(Chain); // Op#0 - Chain 02526 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC 02527 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg 02528 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail 02529 Ops.push_back(Callee); 02530 02531 // Handle all of the outgoing arguments. 02532 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 02533 MVT::ValueType VT = getValueType(Args[i].second); 02534 SDOperand Op = Args[i].first; 02535 bool isSigned = Args[i].second->isSigned(); 02536 switch (getTypeAction(VT)) { 02537 default: assert(0 && "Unknown type action!"); 02538 case Legal: 02539 Ops.push_back(Op); 02540 Ops.push_back(DAG.getConstant(isSigned, MVT::i32)); 02541 break; 02542 case Promote: 02543 if (MVT::isInteger(VT)) { 02544 unsigned ExtOp = isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; 02545 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op); 02546 } else { 02547 assert(MVT::isFloatingPoint(VT) && "Not int or FP?"); 02548 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op); 02549 } 02550 Ops.push_back(Op); 02551 Ops.push_back(DAG.getConstant(isSigned, MVT::i32)); 02552 break; 02553 case Expand: 02554 if (VT != MVT::Vector) { 02555 // If this is a large integer, it needs to be broken down into small 02556 // integers. Figure out what the source elt type is and how many small 02557 // integers it is. 02558 MVT::ValueType NVT = getTypeToTransformTo(VT); 02559 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02560 if (NumVals == 2) { 02561 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, NVT, Op, 02562 DAG.getConstant(0, getPointerTy())); 02563 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, NVT, Op, 02564 DAG.getConstant(1, getPointerTy())); 02565 if (!isLittleEndian()) 02566 std::swap(Lo, Hi); 02567 02568 Ops.push_back(Lo); 02569 Ops.push_back(DAG.getConstant(isSigned, MVT::i32)); 02570 Ops.push_back(Hi); 02571 Ops.push_back(DAG.getConstant(isSigned, MVT::i32)); 02572 } else { 02573 // Value scalarized into many values. Unimp for now. 02574 assert(0 && "Cannot expand i64 -> i16 yet!"); 02575 } 02576 } else { 02577 // Otherwise, this is a vector type. We only support legal vectors 02578 // right now. 02579 const PackedType *PTy = cast<PackedType>(Args[i].second); 02580 unsigned NumElems = PTy->getNumElements(); 02581 const Type *EltTy = PTy->getElementType(); 02582 02583 // Figure out if there is a Packed type corresponding to this Vector 02584 // type. If so, convert to the packed type. 02585 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02586 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02587 // Insert a VBIT_CONVERT of the MVT::Vector type to the packed type. 02588 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op); 02589 Ops.push_back(Op); 02590 Ops.push_back(DAG.getConstant(isSigned, MVT::i32)); 02591 } else { 02592 assert(0 && "Don't support illegal by-val vector call args yet!"); 02593 abort(); 02594 } 02595 } 02596 break; 02597 } 02598 } 02599 02600 // Figure out the result value types. 02601 std::vector<MVT::ValueType> RetTys; 02602 02603 if (RetTy != Type::VoidTy) { 02604 MVT::ValueType VT = getValueType(RetTy); 02605 switch (getTypeAction(VT)) { 02606 default: assert(0 && "Unknown type action!"); 02607 case Legal: 02608 RetTys.push_back(VT); 02609 break; 02610 case Promote: 02611 RetTys.push_back(getTypeToTransformTo(VT)); 02612 break; 02613 case Expand: 02614 if (VT != MVT::Vector) { 02615 // If this is a large integer, it needs to be reassembled from small 02616 // integers. Figure out what the source elt type is and how many small 02617 // integers it is. 02618 MVT::ValueType NVT = getTypeToTransformTo(VT); 02619 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02620 for (unsigned i = 0; i != NumVals; ++i) 02621 RetTys.push_back(NVT); 02622 } else { 02623 // Otherwise, this is a vector type. We only support legal vectors 02624 // right now. 02625 const PackedType *PTy = cast<PackedType>(RetTy); 02626 unsigned NumElems = PTy->getNumElements(); 02627 const Type *EltTy = PTy->getElementType(); 02628 02629 // Figure out if there is a Packed type corresponding to this Vector 02630 // type. If so, convert to the packed type. 02631 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02632 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02633 RetTys.push_back(TVT); 02634 } else { 02635 assert(0 && "Don't support illegal by-val vector call results yet!"); 02636 abort(); 02637 } 02638 } 02639 } 02640 } 02641 02642 RetTys.push_back(MVT::Other); // Always has a chain. 02643 02644 // Finally, create the CALL node. 02645 SDOperand Res = DAG.getNode(ISD::CALL, RetTys, Ops); 02646 02647 // This returns a pair of operands. The first element is the 02648 // return value for the function (if RetTy is not VoidTy). The second 02649 // element is the outgoing token chain. 02650 SDOperand ResVal; 02651 if (RetTys.size() != 1) { 02652 MVT::ValueType VT = getValueType(RetTy); 02653 if (RetTys.size() == 2) { 02654 ResVal = Res; 02655 02656 // If this value was promoted, truncate it down. 02657 if (ResVal.getValueType() != VT) { 02658 if (VT == MVT::Vector) { 02659 // Insert a VBITCONVERT to convert from the packed result type to the 02660 // MVT::Vector type. 02661 unsigned NumElems = cast<PackedType>(RetTy)->getNumElements(); 02662 const Type *EltTy = cast<PackedType>(RetTy)->getElementType(); 02663 02664 // Figure out if there is a Packed type corresponding to this Vector 02665 // type. If so, convert to the packed type. 02666 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02667 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02668 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a 02669 // "N x PTyElementVT" MVT::Vector type. 02670 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal, 02671 DAG.getConstant(NumElems, MVT::i32), 02672 DAG.getValueType(getValueType(EltTy))); 02673 } else { 02674 abort(); 02675 } 02676 } else if (MVT::isInteger(VT)) { 02677 unsigned AssertOp = RetTy->isSigned() ? 02678 ISD::AssertSext : ISD::AssertZext; 02679 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal, 02680 DAG.getValueType(VT)); 02681 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal); 02682 } else { 02683 assert(MVT::isFloatingPoint(VT)); 02684 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal); 02685 } 02686 } 02687 } else if (RetTys.size() == 3) { 02688 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT, 02689 Res.getValue(0), Res.getValue(1)); 02690 02691 } else { 02692 assert(0 && "Case not handled yet!"); 02693 } 02694 } 02695 02696 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1)); 02697 } 02698 02699 02700 02701 // It is always conservatively correct for llvm.returnaddress and 02702 // llvm.frameaddress to return 0. 02703 // 02704 // FIXME: Change this to insert a FRAMEADDR/RETURNADDR node, and have that be 02705 // expanded to 0 if the target wants. 02706 std::pair<SDOperand, SDOperand> 02707 TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, 02708 unsigned Depth, SelectionDAG &DAG) { 02709 return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain); 02710 } 02711 02712 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 02713 assert(0 && "LowerOperation not implemented for this target!"); 02714 abort(); 02715 return SDOperand(); 02716 } 02717 02718 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, 02719 SelectionDAG &DAG) { 02720 assert(0 && "CustomPromoteOperation not implemented for this target!"); 02721 abort(); 02722 return SDOperand(); 02723 } 02724 02725 void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) { 02726 unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue(); 02727 std::pair<SDOperand,SDOperand> Result = 02728 TLI.LowerFrameReturnAddress(isFrame, getRoot(), Depth, DAG); 02729 setValue(&I, Result.first); 02730 DAG.setRoot(Result.second); 02731 } 02732 02733 /// getMemsetValue - Vectorized representation of the memset value 02734 /// operand. 02735 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT, 02736 SelectionDAG &DAG) { 02737 MVT::ValueType CurVT = VT; 02738 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 02739 uint64_t Val = C->getValue() & 255; 02740 unsigned Shift = 8; 02741 while (CurVT != MVT::i8) { 02742 Val = (Val << Shift) | Val; 02743 Shift <<= 1; 02744 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 02745 } 02746 return DAG.getConstant(Val, VT); 02747 } else { 02748 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value); 02749 unsigned Shift = 8; 02750 while (CurVT != MVT::i8) { 02751 Value = 02752 DAG.getNode(ISD::OR, VT, 02753 DAG.getNode(ISD::SHL, VT, Value, 02754 DAG.getConstant(Shift, MVT::i8)), Value); 02755 Shift <<= 1; 02756 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 02757 } 02758 02759 return Value; 02760 } 02761 } 02762 02763 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only 02764 /// used when a memcpy is turned into a memset when the source is a constant 02765 /// string ptr. 02766 static SDOperand getMemsetStringVal(MVT::ValueType VT, 02767 SelectionDAG &DAG, TargetLowering &TLI, 02768 std::string &Str, unsigned Offset) { 02769 MVT::ValueType CurVT = VT; 02770 uint64_t Val = 0; 02771 unsigned MSB = getSizeInBits(VT) / 8; 02772 if (TLI.isLittleEndian()) 02773 Offset = Offset + MSB - 1; 02774 for (unsigned i = 0; i != MSB; ++i) { 02775 Val = (Val << 8) | Str[Offset]; 02776 Offset += TLI.isLittleEndian() ? -1 : 1; 02777 } 02778 return DAG.getConstant(Val, VT); 02779 } 02780 02781 /// getMemBasePlusOffset - Returns base and offset node for the 02782 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset, 02783 SelectionDAG &DAG, TargetLowering &TLI) { 02784 MVT::ValueType VT = Base.getValueType(); 02785 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT)); 02786 } 02787 02788 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required 02789 /// to replace the memset / memcpy is below the threshold. It also returns the 02790 /// types of the sequence of memory ops to perform memset / memcpy. 02791 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps, 02792 unsigned Limit, uint64_t Size, 02793 unsigned Align, TargetLowering &TLI) { 02794 MVT::ValueType VT; 02795 02796 if (TLI.allowsUnalignedMemoryAccesses()) { 02797 VT = MVT::i64; 02798 } else { 02799 switch (Align & 7) { 02800 case 0: 02801 VT = MVT::i64; 02802 break; 02803 case 4: 02804 VT = MVT::i32; 02805 break; 02806 case 2: 02807 VT = MVT::i16; 02808 break; 02809 default: 02810 VT = MVT::i8; 02811 break; 02812 } 02813 } 02814 02815 MVT::ValueType LVT = MVT::i64; 02816 while (!TLI.isTypeLegal(LVT)) 02817 LVT = (MVT::ValueType)((unsigned)LVT - 1); 02818 assert(MVT::isInteger(LVT)); 02819 02820 if (VT > LVT) 02821 VT = LVT; 02822 02823 unsigned NumMemOps = 0; 02824 while (Size != 0) { 02825 unsigned VTSize = getSizeInBits(VT) / 8; 02826 while (VTSize > Size) { 02827 VT = (MVT::ValueType)((unsigned)VT - 1); 02828 VTSize >>= 1; 02829 } 02830 assert(MVT::isInteger(VT)); 02831 02832 if (++NumMemOps > Limit) 02833 return false; 02834 MemOps.push_back(VT); 02835 Size -= VTSize; 02836 } 02837 02838 return true; 02839 } 02840 02841 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) { 02842 SDOperand Op1 = getValue(I.getOperand(1)); 02843 SDOperand Op2 = getValue(I.getOperand(2)); 02844 SDOperand Op3 = getValue(I.getOperand(3)); 02845 SDOperand Op4 = getValue(I.getOperand(4)); 02846 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue(); 02847 if (Align == 0) Align = 1; 02848 02849 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) { 02850 std::vector<MVT::ValueType> MemOps; 02851 02852 // Expand memset / memcpy to a series of load / store ops 02853 // if the size operand falls below a certain threshold. 02854 std::vector<SDOperand> OutChains; 02855 switch (Op) { 02856 default: break; // Do nothing for now. 02857 case ISD::MEMSET: { 02858 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(), 02859 Size->getValue(), Align, TLI)) { 02860 unsigned NumMemOps = MemOps.size(); 02861 unsigned Offset = 0; 02862 for (unsigned i = 0; i < NumMemOps; i++) { 02863 MVT::ValueType VT = MemOps[i]; 02864 unsigned VTSize = getSizeInBits(VT) / 8; 02865 SDOperand Value = getMemsetValue(Op2, VT, DAG); 02866 SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, getRoot(), 02867 Value, 02868 getMemBasePlusOffset(Op1, Offset, DAG, TLI), 02869 DAG.getSrcValue(I.getOperand(1), Offset)); 02870 OutChains.push_back(Store); 02871 Offset += VTSize; 02872 } 02873 } 02874 break; 02875 } 02876 case ISD::MEMCPY: { 02877 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(), 02878 Size->getValue(), Align, TLI)) { 02879 unsigned NumMemOps = MemOps.size(); 02880 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0; 02881 GlobalAddressSDNode *G = NULL; 02882 std::string Str; 02883 bool CopyFromStr = false; 02884 02885 if (Op2.getOpcode() == ISD::GlobalAddress) 02886 G = cast<GlobalAddressSDNode>(Op2); 02887 else if (Op2.getOpcode() == ISD::ADD && 02888 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress && 02889 Op2.getOperand(1).getOpcode() == ISD::Constant) { 02890 G = cast<GlobalAddressSDNode>(Op2.getOperand(0)); 02891 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue(); 02892 } 02893 if (G) { 02894 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal()); 02895 if (GV) { 02896 Str = GV->getStringValue(false); 02897 if (!Str.empty()) { 02898 CopyFromStr = true; 02899 SrcOff += SrcDelta; 02900 } 02901 } 02902 } 02903 02904 for (unsigned i = 0; i < NumMemOps; i++) { 02905 MVT::ValueType VT = MemOps[i]; 02906 unsigned VTSize = getSizeInBits(VT) / 8; 02907 SDOperand Value, Chain, Store; 02908 02909 if (CopyFromStr) { 02910 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff); 02911 Chain = getRoot(); 02912 Store = 02913 DAG.getNode(ISD::STORE, MVT::Other, Chain, Value, 02914 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 02915 DAG.getSrcValue(I.getOperand(1), DstOff)); 02916 } else { 02917 Value = DAG.getLoad(VT, getRoot(), 02918 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI), 02919 DAG.getSrcValue(I.getOperand(2), SrcOff)); 02920 Chain = Value.getValue(1); 02921 Store = 02922 DAG.getNode(ISD::STORE, MVT::Other, Chain, Value, 02923 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 02924 DAG.getSrcValue(I.getOperand(1), DstOff)); 02925 } 02926 OutChains.push_back(Store); 02927 SrcOff += VTSize; 02928 DstOff += VTSize; 02929 } 02930 } 02931 break; 02932 } 02933 } 02934 02935 if (!OutChains.empty()) { 02936 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains)); 02937 return; 02938 } 02939 } 02940 02941 std::vector<SDOperand> Ops; 02942 Ops.push_back(getRoot()); 02943 Ops.push_back(Op1); 02944 Ops.push_back(Op2); 02945 Ops.push_back(Op3); 02946 Ops.push_back(Op4); 02947 DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops)); 02948 } 02949 02950 //===----------------------------------------------------------------------===// 02951 // SelectionDAGISel code 02952 //===----------------------------------------------------------------------===// 02953 02954 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 02955 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 02956 } 02957 02958 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 02959 // FIXME: we only modify the CFG to split critical edges. This 02960 // updates dom and loop info. 02961 } 02962 02963 02964 /// OptimizeNoopCopyExpression - We have determined that the specified cast 02965 /// instruction is a noop copy (e.g. it's casting from one pointer type to 02966 /// another, int->uint, or int->sbyte on PPC. 02967 /// 02968 /// Return true if any changes are made. 02969 static bool OptimizeNoopCopyExpression(CastInst *CI) { 02970 BasicBlock *DefBB = CI->getParent(); 02971 02972 /// InsertedCasts - Only insert a cast in each block once. 02973 std::map<BasicBlock*, CastInst*> InsertedCasts; 02974 02975 bool MadeChange = false; 02976 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 02977 UI != E; ) { 02978 Use &TheUse = UI.getUse(); 02979 Instruction *User = cast<Instruction>(*UI); 02980 02981 // Figure out which BB this cast is used in. For PHI's this is the 02982 // appropriate predecessor block. 02983 BasicBlock *UserBB = User->getParent(); 02984 if (PHINode *PN = dyn_cast<PHINode>(User)) { 02985 unsigned OpVal = UI.getOperandNo()/2; 02986 UserBB = PN->getIncomingBlock(OpVal); 02987 } 02988 02989 // Preincrement use iterator so we don't invalidate it. 02990 ++UI; 02991 02992 // If this user is in the same block as the cast, don't change the cast. 02993 if (UserBB == DefBB) continue; 02994 02995 // If we have already inserted a cast into this block, use it. 02996 CastInst *&InsertedCast = InsertedCasts[UserBB]; 02997 02998 if (!InsertedCast) { 02999 BasicBlock::iterator InsertPt = UserBB->begin(); 03000 while (isa<PHINode>(InsertPt)) ++InsertPt; 03001 03002 InsertedCast = 03003 new CastInst(CI->getOperand(0), CI->getType(), "", InsertPt); 03004 MadeChange = true; 03005 } 03006 03007 // Replace a use of the cast with a use of the new casat. 03008 TheUse = InsertedCast; 03009 } 03010 03011 // If we removed all uses, nuke the cast. 03012 if (CI->use_empty()) 03013 CI->eraseFromParent(); 03014 03015 return MadeChange; 03016 } 03017 03018 /// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset, 03019 /// casting to the type of GEPI. 03020 static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB, 03021 Instruction *GEPI, Value *Ptr, 03022 Value *PtrOffset) { 03023 if (V) return V; // Already computed. 03024 03025 BasicBlock::iterator InsertPt; 03026 if (BB == GEPI->getParent()) { 03027 // If insert into the GEP's block, insert right after the GEP. 03028 InsertPt = GEPI; 03029 ++InsertPt; 03030 } else { 03031 // Otherwise, insert at the top of BB, after any PHI nodes 03032 InsertPt = BB->begin(); 03033 while (isa<PHINode>(InsertPt)) ++InsertPt; 03034 } 03035 03036 // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into 03037 // BB so that there is only one value live across basic blocks (the cast 03038 // operand). 03039 if (CastInst *CI = dyn_cast<CastInst>(Ptr)) 03040 if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType())) 03041 Ptr = new CastInst(CI->getOperand(0), CI->getType(), "", InsertPt); 03042 03043 // Add the offset, cast it to the right type. 03044 Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt); 03045 return V = new CastInst(Ptr, GEPI->getType(), "", InsertPt); 03046 } 03047 03048 /// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to 03049 /// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One 03050 /// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's 03051 /// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to 03052 /// sink PtrOffset into user blocks where doing so will likely allow us to fold 03053 /// the constant add into a load or store instruction. Additionally, if a user 03054 /// is a pointer-pointer cast, we look through it to find its users. 03055 static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr, 03056 Constant *PtrOffset, BasicBlock *DefBB, 03057 GetElementPtrInst *GEPI, 03058 std::map<BasicBlock*,Instruction*> &InsertedExprs) { 03059 while (!RepPtr->use_empty()) { 03060 Instruction *User = cast<Instruction>(RepPtr->use_back()); 03061 03062 // If the user is a Pointer-Pointer cast, recurse. 03063 if (isa<CastInst>(User) && isa<PointerType>(User->getType())) { 03064 ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 03065 03066 // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we 03067 // could invalidate an iterator. 03068 User->setOperand(0, UndefValue::get(RepPtr->getType())); 03069 continue; 03070 } 03071 03072 // If this is a load of the pointer, or a store through the pointer, emit 03073 // the increment into the load/store block. 03074 Instruction *NewVal; 03075 if (isa<LoadInst>(User) || 03076 (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) { 03077 NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()], 03078 User->getParent(), GEPI, 03079 Ptr, PtrOffset); 03080 } else { 03081 // If this use is not foldable into the addressing mode, use a version 03082 // emitted in the GEP block. 03083 NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI, 03084 Ptr, PtrOffset); 03085 } 03086 03087 if (GEPI->getType() != RepPtr->getType()) { 03088 BasicBlock::iterator IP = NewVal; 03089 ++IP; 03090 NewVal = new CastInst(NewVal, RepPtr->getType(), "", IP); 03091 } 03092 User->replaceUsesOfWith(RepPtr, NewVal); 03093 } 03094 } 03095 03096 03097 /// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction 03098 /// selection, we want to be a bit careful about some things. In particular, if 03099 /// we have a GEP instruction that is used in a different block than it is 03100 /// defined, the addressing expression of the GEP cannot be folded into loads or 03101 /// stores that use it. In this case, decompose the GEP and move constant 03102 /// indices into blocks that use it. 03103 static bool OptimizeGEPExpression(GetElementPtrInst *GEPI, 03104 const TargetData *TD) { 03105 // If this GEP is only used inside the block it is defined in, there is no 03106 // need to rewrite it. 03107 bool isUsedOutsideDefBB = false; 03108 BasicBlock *DefBB = GEPI->getParent(); 03109 for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end(); 03110 UI != E; ++UI) { 03111 if (cast<Instruction>(*UI)->getParent() != DefBB) { 03112 isUsedOutsideDefBB = true; 03113 break; 03114 } 03115 } 03116 if (!isUsedOutsideDefBB) return false; 03117 03118 // If this GEP has no non-zero constant indices, there is nothing we can do, 03119 // ignore it. 03120 bool hasConstantIndex = false; 03121 bool hasVariableIndex = false; 03122 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 03123 E = GEPI->op_end(); OI != E; ++OI) { 03124 if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) { 03125 if (CI->getRawValue()) { 03126 hasConstantIndex = true; 03127 break; 03128 } 03129 } else { 03130 hasVariableIndex = true; 03131 } 03132 } 03133 03134 // If this is a "GEP X, 0, 0, 0", turn this into a cast. 03135 if (!hasConstantIndex && !hasVariableIndex) { 03136 Value *NC = new CastInst(GEPI->getOperand(0), GEPI->getType(), 03137 GEPI->getName(), GEPI); 03138 GEPI->replaceAllUsesWith(NC); 03139 GEPI->eraseFromParent(); 03140 return true; 03141 } 03142 03143 // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses. 03144 if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0))) 03145 return false; 03146 03147 // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the 03148 // constant offset (which we now know is non-zero) and deal with it later. 03149 uint64_t ConstantOffset = 0; 03150 const Type *UIntPtrTy = TD->getIntPtrType(); 03151 Value *Ptr = new CastInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI); 03152 const Type *Ty = GEPI->getOperand(0)->getType(); 03153 03154 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 03155 E = GEPI->op_end(); OI != E; ++OI) { 03156 Value *Idx = *OI; 03157 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 03158 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 03159 if (Field) 03160 ConstantOffset += TD->getStructLayout(StTy)->MemberOffsets[Field]; 03161 Ty = StTy->getElementType(Field); 03162 } else { 03163 Ty = cast<SequentialType>(Ty)->getElementType(); 03164 03165 // Handle constant subscripts. 03166 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 03167 if (CI->getRawValue() == 0) continue; 03168 03169 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI)) 03170 ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CSI->getValue(); 03171 else 03172 ConstantOffset+=TD->getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue(); 03173 continue; 03174 } 03175 03176 // Ptr = Ptr + Idx * ElementSize; 03177 03178 // Cast Idx to UIntPtrTy if needed. 03179 Idx = new CastInst(Idx, UIntPtrTy, "", GEPI); 03180 03181 uint64_t ElementSize = TD->getTypeSize(Ty); 03182 // Mask off bits that should not be set. 03183 ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 03184 Constant *SizeCst = ConstantUInt::get(UIntPtrTy, ElementSize); 03185 03186 // Multiply by the element size and add to the base. 03187 Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI); 03188 Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI); 03189 } 03190 } 03191 03192 // Make sure that the offset fits in uintptr_t. 03193 ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 03194 Constant *PtrOffset = ConstantUInt::get(UIntPtrTy, ConstantOffset); 03195 03196 // Okay, we have now emitted all of the variable index parts to the BB that 03197 // the GEP is defined in. Loop over all of the using instructions, inserting 03198 // an "add Ptr, ConstantOffset" into each block that uses it and update the 03199 // instruction to use the newly computed value, making GEPI dead. When the 03200 // user is a load or store instruction address, we emit the add into the user 03201 // block, otherwise we use a canonical version right next to the gep (these 03202 // won't be foldable as addresses, so we might as well share the computation). 03203 03204 std::map<BasicBlock*,Instruction*> InsertedExprs; 03205 ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 03206 03207 // Finally, the GEP is dead, remove it. 03208 GEPI->eraseFromParent(); 03209 03210 return true; 03211 } 03212 03213 bool SelectionDAGISel::runOnFunction(Function &Fn) { 03214 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 03215 RegMap = MF.getSSARegMap(); 03216 DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n"); 03217 03218 // First, split all critical edges for PHI nodes with incoming values that are 03219 // constants, this way the load of the constant into a vreg will not be placed 03220 // into MBBs that are used some other way. 03221 // 03222 // In this pass we also look for GEP and cast instructions that are used 03223 // across basic blocks and rewrite them to improve basic-block-at-a-time 03224 // selection. 03225 // 03226 // 03227 bool MadeChange = true; 03228 while (MadeChange) { 03229 MadeChange = false; 03230 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 03231 PHINode *PN; 03232 BasicBlock::iterator BBI; 03233 for (BBI = BB->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI) 03234 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 03235 if (isa<Constant>(PN->getIncomingValue(i))) 03236 SplitCriticalEdge(PN->getIncomingBlock(i), BB); 03237 03238 for (BasicBlock::iterator E = BB->end(); BBI != E; ) { 03239 Instruction *I = BBI++; 03240 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 03241 MadeChange |= OptimizeGEPExpression(GEPI, TLI.getTargetData()); 03242 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 03243 // If this is a noop copy, sink it into user blocks to reduce the number 03244 // of virtual registers that must be created and coallesced. 03245 MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 03246 MVT::ValueType DstVT = TLI.getValueType(CI->getType()); 03247 03248 // This is an fp<->int conversion? 03249 if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) 03250 continue; 03251 03252 // If this is an extension, it will be a zero or sign extension, which 03253 // isn't a noop. 03254 if (SrcVT < DstVT) continue; 03255 03256 // If these values will be promoted, find out what they will be promoted 03257 // to. This helps us consider truncates on PPC as noop copies when they 03258 // are. 03259 if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 03260 SrcVT = TLI.getTypeToTransformTo(SrcVT); 03261 if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 03262 DstVT = TLI.getTypeToTransformTo(DstVT); 03263 03264 // If, after promotion, these are the same types, this is a noop copy. 03265 if (SrcVT == DstVT) 03266 MadeChange |= OptimizeNoopCopyExpression(CI); 03267 } 03268 } 03269 } 03270 } 03271 03272 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 03273 03274 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 03275 SelectBasicBlock(I, MF, FuncInfo); 03276 03277 return true; 03278 } 03279 03280 03281 SDOperand SelectionDAGISel:: 03282 CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) { 03283 SDOperand Op = SDL.getValue(V); 03284 assert((Op.getOpcode() != ISD::CopyFromReg || 03285 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 03286 "Copy from a reg to the same reg!"); 03287 03288 // If this type is not legal, we must make sure to not create an invalid 03289 // register use. 03290 MVT::ValueType SrcVT = Op.getValueType(); 03291 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT); 03292 SelectionDAG &DAG = SDL.DAG; 03293 if (SrcVT == DestVT) { 03294 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 03295 } else if (SrcVT == MVT::Vector) { 03296 // Handle copies from generic vectors to registers. 03297 MVT::ValueType PTyElementVT, PTyLegalElementVT; 03298 unsigned NE = TLI.getPackedTypeBreakdown(cast<PackedType>(V->getType()), 03299 PTyElementVT, PTyLegalElementVT); 03300 03301 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT" 03302 // MVT::Vector type. 03303 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op, 03304 DAG.getConstant(NE, MVT::i32), 03305 DAG.getValueType(PTyElementVT)); 03306 03307 // Loop over all of the elements of the resultant vector, 03308 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then 03309 // copying them into output registers. 03310 std::vector<SDOperand> OutChains; 03311 SDOperand Root = SDL.getRoot(); 03312 for (unsigned i = 0; i != NE; ++i) { 03313 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT, 03314 Op, DAG.getConstant(i, TLI.getPointerTy())); 03315 if (PTyElementVT == PTyLegalElementVT) { 03316 // Elements are legal. 03317 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 03318 } else if (PTyLegalElementVT > PTyElementVT) { 03319 // Elements are promoted. 03320 if (MVT::isFloatingPoint(PTyLegalElementVT)) 03321 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt); 03322 else 03323 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt); 03324 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 03325 } else { 03326 // Elements are expanded. 03327 // The src value is expanded into multiple registers. 03328 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 03329 Elt, DAG.getConstant(0, TLI.getPointerTy())); 03330 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 03331 Elt, DAG.getConstant(1, TLI.getPointerTy())); 03332 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo)); 03333 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi)); 03334 } 03335 } 03336 return DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains); 03337 } else if (SrcVT < DestVT) { 03338 // The src value is promoted to the register. 03339 if (MVT::isFloatingPoint(SrcVT)) 03340 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op); 03341 else 03342 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op); 03343 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 03344 } else { 03345 // The src value is expanded into multiple registers. 03346 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 03347 Op, DAG.getConstant(0, TLI.getPointerTy())); 03348 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 03349 Op, DAG.getConstant(1, TLI.getPointerTy())); 03350 Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo); 03351 return DAG.getCopyToReg(Op, Reg+1, Hi); 03352 } 03353 } 03354 03355 void SelectionDAGISel:: 03356 LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL, 03357 std::vector<SDOperand> &UnorderedChains) { 03358 // If this is the entry block, emit arguments. 03359 Function &F = *BB->getParent(); 03360 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 03361 SDOperand OldRoot = SDL.DAG.getRoot(); 03362 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 03363 03364 unsigned a = 0; 03365 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 03366 AI != E; ++AI, ++a) 03367 if (!AI->use_empty()) { 03368 SDL.setValue(AI, Args[a]); 03369 03370 // If this argument is live outside of the entry block, insert a copy from 03371 // whereever we got it to the vreg that other BB's will reference it as. 03372 if (FuncInfo.ValueMap.count(AI)) { 03373 SDOperand Copy = 03374 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]); 03375 UnorderedChains.push_back(Copy); 03376 } 03377 } 03378 03379 // Finally, if the target has anything special to do, allow it to do so. 03380 // FIXME: this should insert code into the DAG! 03381 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 03382 } 03383 03384 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 03385 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 03386 FunctionLoweringInfo &FuncInfo) { 03387 SelectionDAGLowering SDL(DAG, TLI, FuncInfo); 03388 03389 std::vector<SDOperand> UnorderedChains; 03390 03391 // Lower any arguments needed in this block if this is the entry block. 03392 if (LLVMBB == &LLVMBB->getParent()->front()) 03393 LowerArguments(LLVMBB, SDL, UnorderedChains); 03394 03395 BB = FuncInfo.MBBMap[LLVMBB]; 03396 SDL.setCurrentBasicBlock(BB); 03397 03398 // Lower all of the non-terminator instructions. 03399 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 03400 I != E; ++I) 03401 SDL.visit(*I); 03402 03403 // Ensure that all instructions which are used outside of their defining 03404 // blocks are available as virtual registers. 03405 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 03406 if (!I->use_empty() && !isa<PHINode>(I)) { 03407 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 03408 if (VMI != FuncInfo.ValueMap.end()) 03409 UnorderedChains.push_back( 03410 CopyValueToVirtualRegister(SDL, I, VMI->second)); 03411 } 03412 03413 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 03414 // ensure constants are generated when needed. Remember the virtual registers 03415 // that need to be added to the Machine PHI nodes as input. We cannot just 03416 // directly add them, because expansion might result in multiple MBB's for one 03417 // BB. As such, the start of the BB might correspond to a different MBB than 03418 // the end. 03419 // 03420 03421 // Emit constants only once even if used by multiple PHI nodes. 03422 std::map<Constant*, unsigned> ConstantsOut; 03423 03424 // Check successor nodes PHI nodes that expect a constant to be available from 03425 // this block. 03426 TerminatorInst *TI = LLVMBB->getTerminator(); 03427 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 03428 BasicBlock *SuccBB = TI->getSuccessor(succ); 03429 MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin(); 03430 PHINode *PN; 03431 03432 // At this point we know that there is a 1-1 correspondence between LLVM PHI 03433 // nodes and Machine PHI nodes, but the incoming operands have not been 03434 // emitted yet. 03435 for (BasicBlock::iterator I = SuccBB->begin(); 03436 (PN = dyn_cast<PHINode>(I)); ++I) 03437 if (!PN->use_empty()) { 03438 unsigned Reg; 03439 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 03440 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 03441 unsigned &RegOut = ConstantsOut[C]; 03442 if (RegOut == 0) { 03443 RegOut = FuncInfo.CreateRegForValue(C); 03444 UnorderedChains.push_back( 03445 CopyValueToVirtualRegister(SDL, C, RegOut)); 03446 } 03447 Reg = RegOut; 03448 } else { 03449 Reg = FuncInfo.ValueMap[PHIOp]; 03450 if (Reg == 0) { 03451 assert(isa<AllocaInst>(PHIOp) && 03452 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 03453 "Didn't codegen value into a register!??"); 03454 Reg = FuncInfo.CreateRegForValue(PHIOp); 03455 UnorderedChains.push_back( 03456 CopyValueToVirtualRegister(SDL, PHIOp, Reg)); 03457 } 03458 } 03459 03460 // Remember that this register needs to added to the machine PHI node as 03461 // the input for this MBB. 03462 MVT::ValueType VT = TLI.getValueType(PN->getType()); 03463 unsigned NumElements; 03464 if (VT != MVT::Vector) 03465 NumElements = TLI.getNumElements(VT); 03466 else { 03467 MVT::ValueType VT1,VT2; 03468 NumElements = 03469 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 03470 VT1, VT2); 03471 } 03472 for (unsigned i = 0, e = NumElements; i != e; ++i) 03473 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 03474 } 03475 } 03476 ConstantsOut.clear(); 03477 03478 // Turn all of the unordered chains into one factored node. 03479 if (!UnorderedChains.empty()) { 03480 SDOperand Root = SDL.getRoot(); 03481 if (Root.getOpcode() != ISD::EntryToken) { 03482 unsigned i = 0, e = UnorderedChains.size(); 03483 for (; i != e; ++i) { 03484 assert(UnorderedChains[i].Val->getNumOperands() > 1); 03485 if (UnorderedChains[i].Val->getOperand(0) == Root) 03486 break; // Don't add the root if we already indirectly depend on it. 03487 } 03488 03489 if (i == e) 03490 UnorderedChains.push_back(Root); 03491 } 03492 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains)); 03493 } 03494 03495 // Lower the terminator after the copies are emitted. 03496 SDL.visit(*LLVMBB->getTerminator()); 03497 03498 // Copy over any CaseBlock records that may now exist due to SwitchInst 03499 // lowering, as well as any jump table information. 03500 SwitchCases.clear(); 03501 SwitchCases = SDL.SwitchCases; 03502 JT = SDL.JT; 03503 03504 // Make sure the root of the DAG is up-to-date. 03505 DAG.setRoot(SDL.getRoot()); 03506 } 03507 03508 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { 03509 // Run the DAG combiner in pre-legalize mode. 03510 DAG.Combine(false); 03511 03512 DEBUG(std::cerr << "Lowered selection DAG:\n"); 03513 DEBUG(DAG.dump()); 03514 03515 // Second step, hack on the DAG until it only uses operations and types that 03516 // the target supports. 03517 DAG.Legalize(); 03518 03519 DEBUG(std::cerr << "Legalized selection DAG:\n"); 03520 DEBUG(DAG.dump()); 03521 03522 // Run the DAG combiner in post-legalize mode. 03523 DAG.Combine(true); 03524 03525 if (ViewISelDAGs) DAG.viewGraph(); 03526 03527 // Third, instruction select all of the operations to machine code, adding the 03528 // code to the MachineBasicBlock. 03529 InstructionSelectBasicBlock(DAG); 03530 03531 DEBUG(std::cerr << "Selected machine code:\n"); 03532 DEBUG(BB->dump()); 03533 } 03534 03535 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 03536 FunctionLoweringInfo &FuncInfo) { 03537 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 03538 { 03539 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>()); 03540 CurDAG = &DAG; 03541 03542 // First step, lower LLVM code to some DAG. This DAG may use operations and 03543 // types that are not supported by the target. 03544 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 03545 03546 // Second step, emit the lowered DAG as machine code. 03547 CodeGenAndEmitDAG(DAG); 03548 } 03549 03550 // Next, now that we know what the last MBB the LLVM BB expanded is, update 03551 // PHI nodes in successors. 03552 if (SwitchCases.empty() && JT.Reg == 0) { 03553 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 03554 MachineInstr *PHI = PHINodesToUpdate[i].first; 03555 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 03556 "This is not a machine PHI node that we are updating!"); 03557 PHI->addRegOperand(PHINodesToUpdate[i].second); 03558 PHI->addMachineBasicBlockOperand(BB); 03559 } 03560 return; 03561 } 03562 03563 // If the JumpTable record is filled in, then we need to emit a jump table. 03564 // Updating the PHI nodes is tricky in this case, since we need to determine 03565 // whether the PHI is a successor of the range check MBB or the jump table MBB 03566 if (JT.Reg) { 03567 assert(SwitchCases.empty() && "Cannot have jump table and lowered switch"); 03568 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>()); 03569 CurDAG = &SDAG; 03570 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo); 03571 MachineBasicBlock *RangeBB = BB; 03572 // Set the current basic block to the mbb we wish to insert the code into 03573 BB = JT.MBB; 03574 SDL.setCurrentBasicBlock(BB); 03575 // Emit the code 03576 SDL.visitJumpTable(JT); 03577 SDAG.setRoot(SDL.getRoot()); 03578 CodeGenAndEmitDAG(SDAG); 03579 // Update PHI Nodes 03580 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 03581 MachineInstr *PHI = PHINodesToUpdate[pi].first; 03582 MachineBasicBlock *PHIBB = PHI->getParent(); 03583 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 03584 "This is not a machine PHI node that we are updating!"); 03585 if (PHIBB == JT.Default) { 03586 PHI->addRegOperand(PHINodesToUpdate[pi].second); 03587 PHI->addMachineBasicBlockOperand(RangeBB); 03588 } 03589 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 03590 PHI->addRegOperand(PHINodesToUpdate[pi].second); 03591 PHI->addMachineBasicBlockOperand(BB); 03592 } 03593 } 03594 return; 03595 } 03596 03597 // If we generated any switch lowering information, build and codegen any 03598 // additional DAGs necessary. 03599 for(unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { 03600 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>()); 03601 CurDAG = &SDAG; 03602 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo); 03603 // Set the current basic block to the mbb we wish to insert the code into 03604 BB = SwitchCases[i].ThisBB; 03605 SDL.setCurrentBasicBlock(BB); 03606 // Emit the code 03607 SDL.visitSwitchCase(SwitchCases[i]); 03608 SDAG.setRoot(SDL.getRoot()); 03609 CodeGenAndEmitDAG(SDAG); 03610 // Iterate over the phi nodes, if there is a phi node in a successor of this 03611 // block (for instance, the default block), then add a pair of operands to 03612 // the phi node for this block, as if we were coming from the original 03613 // BB before switch expansion. 03614 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 03615 MachineInstr *PHI = PHINodesToUpdate[pi].first; 03616 MachineBasicBlock *PHIBB = PHI->getParent(); 03617 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 03618 "This is not a machine PHI node that we are updating!"); 03619 if (PHIBB == SwitchCases[i].LHSBB || PHIBB == SwitchCases[i].RHSBB) { 03620 PHI->addRegOperand(PHINodesToUpdate[pi].second); 03621 PHI->addMachineBasicBlockOperand(BB); 03622 } 03623 } 03624 } 03625 } 03626 03627 //===----------------------------------------------------------------------===// 03628 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each 03629 /// target node in the graph. 03630 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { 03631 if (ViewSchedDAGs) DAG.viewGraph(); 03632 ScheduleDAG *SL = NULL; 03633 03634 switch (ISHeuristic) { 03635 default: assert(0 && "Unrecognized scheduling heuristic"); 03636 case defaultScheduling: 03637 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) 03638 SL = createTDListDAGScheduler(DAG, BB, CreateTargetHazardRecognizer()); 03639 else { 03640 assert(TLI.getSchedulingPreference() == 03641 TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 03642 SL = createBURRListDAGScheduler(DAG, BB); 03643 } 03644 break; 03645 case noScheduling: 03646 SL = createBFS_DAGScheduler(DAG, BB); 03647 break; 03648 case simpleScheduling: 03649 SL = createSimpleDAGScheduler(false, DAG, BB); 03650 break; 03651 case simpleNoItinScheduling: 03652 SL = createSimpleDAGScheduler(true, DAG, BB); 03653 break; 03654 case listSchedulingBURR: 03655 SL = createBURRListDAGScheduler(DAG, BB); 03656 break; 03657 case listSchedulingTDRR: 03658 SL = createTDRRListDAGScheduler(DAG, BB); 03659 break; 03660 case listSchedulingTD: 03661 SL = createTDListDAGScheduler(DAG, BB, CreateTargetHazardRecognizer()); 03662 break; 03663 } 03664 BB = SL->Run(); 03665 delete SL; 03666 } 03667 03668 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 03669 return new HazardRecognizer(); 03670 } 03671 03672 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 03673 /// by tblgen. Others should not call it. 03674 void SelectionDAGISel:: 03675 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) { 03676 std::vector<SDOperand> InOps; 03677 std::swap(InOps, Ops); 03678 03679 Ops.push_back(InOps[0]); // input chain. 03680 Ops.push_back(InOps[1]); // input asm string. 03681 03682 unsigned i = 2, e = InOps.size(); 03683 if (InOps[e-1].getValueType() == MVT::Flag) 03684 --e; // Don't process a flag operand if it is here. 03685 03686 while (i != e) { 03687 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 03688 if ((Flags & 7) != 4 /*MEM*/) { 03689 // Just skip over this operand, copying the operands verbatim. 03690 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 03691 i += (Flags >> 3) + 1; 03692 } else { 03693 assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 03694 // Otherwise, this is a memory operand. Ask the target to select it. 03695 std::vector<SDOperand> SelOps; 03696 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { 03697 std::cerr << "Could not match memory address. Inline asm failure!\n"; 03698 exit(1); 03699 } 03700 03701 // Add this to the output node. 03702 Ops.push_back(DAG.getConstant(4/*MEM*/ | (SelOps.size() << 3), MVT::i32)); 03703 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 03704 i += 2; 03705 } 03706 } 03707 03708 // Add the flag input back if present. 03709 if (e != InOps.size()) 03710 Ops.push_back(InOps.back()); 03711 }