LLVM API Documentation
00001 //===-- SelectionDAGBuild.h - Selection-DAG building ----------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements routines for translating from LLVM IR into SelectionDAG IR. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef SELECTIONDAGBUILD_H 00015 #define SELECTIONDAGBUILD_H 00016 00017 #include "llvm/Constants.h" 00018 #include "llvm/CodeGen/SelectionDAG.h" 00019 #include "llvm/ADT/APInt.h" 00020 #include "llvm/ADT/DenseMap.h" 00021 #ifndef NDEBUG 00022 #include "llvm/ADT/SmallSet.h" 00023 #endif 00024 #include "llvm/CodeGen/SelectionDAGNodes.h" 00025 #include "llvm/CodeGen/ValueTypes.h" 00026 #include "llvm/Support/CallSite.h" 00027 #include "llvm/Support/ErrorHandling.h" 00028 #include "llvm/Target/TargetMachine.h" 00029 #include <vector> 00030 #include <set> 00031 00032 namespace llvm { 00033 00034 class AliasAnalysis; 00035 class AllocaInst; 00036 class BasicBlock; 00037 class BitCastInst; 00038 class BranchInst; 00039 class CallInst; 00040 class ExtractElementInst; 00041 class ExtractValueInst; 00042 class FCmpInst; 00043 class FPExtInst; 00044 class FPToSIInst; 00045 class FPToUIInst; 00046 class FPTruncInst; 00047 class FreeInst; 00048 class Function; 00049 class GetElementPtrInst; 00050 class GCFunctionInfo; 00051 class ICmpInst; 00052 class IntToPtrInst; 00053 class InvokeInst; 00054 class InsertElementInst; 00055 class InsertValueInst; 00056 class Instruction; 00057 class LoadInst; 00058 class MachineBasicBlock; 00059 class MachineFunction; 00060 class MachineInstr; 00061 class MachineModuleInfo; 00062 class MachineRegisterInfo; 00063 class MallocInst; 00064 class PHINode; 00065 class PtrToIntInst; 00066 class ReturnInst; 00067 class SDISelAsmOperandInfo; 00068 class SExtInst; 00069 class SelectInst; 00070 class ShuffleVectorInst; 00071 class SIToFPInst; 00072 class StoreInst; 00073 class SwitchInst; 00074 class TargetData; 00075 class TargetLowering; 00076 class TruncInst; 00077 class UIToFPInst; 00078 class UnreachableInst; 00079 class UnwindInst; 00080 class VAArgInst; 00081 class ZExtInst; 00082 00083 //===--------------------------------------------------------------------===// 00084 /// FunctionLoweringInfo - This contains information that is global to a 00085 /// function that is used when lowering a region of the function. 00086 /// 00087 class FunctionLoweringInfo { 00088 public: 00089 TargetLowering &TLI; 00090 Function *Fn; 00091 MachineFunction *MF; 00092 MachineRegisterInfo *RegInfo; 00093 00094 explicit FunctionLoweringInfo(TargetLowering &TLI); 00095 00096 /// set - Initialize this FunctionLoweringInfo with the given Function 00097 /// and its associated MachineFunction. 00098 /// 00099 void set(Function &Fn, MachineFunction &MF, SelectionDAG &DAG, 00100 bool EnableFastISel); 00101 00102 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 00103 DenseMap<const BasicBlock*, MachineBasicBlock *> MBBMap; 00104 00105 /// ValueMap - Since we emit code for the function a basic block at a time, 00106 /// we must remember which virtual registers hold the values for 00107 /// cross-basic-block values. 00108 DenseMap<const Value*, unsigned> ValueMap; 00109 00110 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 00111 /// the entry block. This allows the allocas to be efficiently referenced 00112 /// anywhere in the function. 00113 DenseMap<const AllocaInst*, int> StaticAllocaMap; 00114 00115 #ifndef NDEBUG 00116 SmallSet<Instruction*, 8> CatchInfoLost; 00117 SmallSet<Instruction*, 8> CatchInfoFound; 00118 #endif 00119 00120 unsigned MakeReg(EVT VT); 00121 00122 /// isExportedInst - Return true if the specified value is an instruction 00123 /// exported from its block. 00124 bool isExportedInst(const Value *V) { 00125 return ValueMap.count(V); 00126 } 00127 00128 unsigned CreateRegForValue(const Value *V); 00129 00130 unsigned InitializeRegForValue(const Value *V) { 00131 unsigned &R = ValueMap[V]; 00132 assert(R == 0 && "Already initialized this value register!"); 00133 return R = CreateRegForValue(V); 00134 } 00135 00136 struct LiveOutInfo { 00137 unsigned NumSignBits; 00138 APInt KnownOne, KnownZero; 00139 LiveOutInfo() : NumSignBits(0), KnownOne(1, 0), KnownZero(1, 0) {} 00140 }; 00141 00142 /// LiveOutRegInfo - Information about live out vregs, indexed by their 00143 /// register number offset by 'FirstVirtualRegister'. 00144 std::vector<LiveOutInfo> LiveOutRegInfo; 00145 00146 /// clear - Clear out all the function-specific state. This returns this 00147 /// FunctionLoweringInfo to an empty state, ready to be used for a 00148 /// different function. 00149 void clear() { 00150 MBBMap.clear(); 00151 ValueMap.clear(); 00152 StaticAllocaMap.clear(); 00153 #ifndef NDEBUG 00154 CatchInfoLost.clear(); 00155 CatchInfoFound.clear(); 00156 #endif 00157 LiveOutRegInfo.clear(); 00158 } 00159 }; 00160 00161 //===----------------------------------------------------------------------===// 00162 /// SelectionDAGLowering - This is the common target-independent lowering 00163 /// implementation that is parameterized by a TargetLowering object. 00164 /// Also, targets can overload any lowering method. 00165 /// 00166 class SelectionDAGLowering { 00167 MachineBasicBlock *CurMBB; 00168 00169 /// CurDebugLoc - current file + line number. Changes as we build the DAG. 00170 DebugLoc CurDebugLoc; 00171 00172 DenseMap<const Value*, SDValue> NodeMap; 00173 00174 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 00175 /// them up and then emit token factor nodes when possible. This allows us to 00176 /// get simple disambiguation between loads without worrying about alias 00177 /// analysis. 00178 SmallVector<SDValue, 8> PendingLoads; 00179 00180 /// PendingExports - CopyToReg nodes that copy values to virtual registers 00181 /// for export to other blocks need to be emitted before any terminator 00182 /// instruction, but they have no other ordering requirements. We bunch them 00183 /// up and the emit a single tokenfactor for them just before terminator 00184 /// instructions. 00185 SmallVector<SDValue, 8> PendingExports; 00186 00187 /// Case - A struct to record the Value for a switch case, and the 00188 /// case's target basic block. 00189 struct Case { 00190 Constant* Low; 00191 Constant* High; 00192 MachineBasicBlock* BB; 00193 00194 Case() : Low(0), High(0), BB(0) { } 00195 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 00196 Low(low), High(high), BB(bb) { } 00197 uint64_t size() const { 00198 uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue(); 00199 uint64_t rLow = cast<ConstantInt>(Low)->getSExtValue(); 00200 return (rHigh - rLow + 1ULL); 00201 } 00202 }; 00203 00204 struct CaseBits { 00205 uint64_t Mask; 00206 MachineBasicBlock* BB; 00207 unsigned Bits; 00208 00209 CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits): 00210 Mask(mask), BB(bb), Bits(bits) { } 00211 }; 00212 00213 typedef std::vector<Case> CaseVector; 00214 typedef std::vector<CaseBits> CaseBitsVector; 00215 typedef CaseVector::iterator CaseItr; 00216 typedef std::pair<CaseItr, CaseItr> CaseRange; 00217 00218 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 00219 /// of conditional branches. 00220 struct CaseRec { 00221 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 00222 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 00223 00224 /// CaseBB - The MBB in which to emit the compare and branch 00225 MachineBasicBlock *CaseBB; 00226 /// LT, GE - If nonzero, we know the current case value must be less-than or 00227 /// greater-than-or-equal-to these Constants. 00228 Constant *LT; 00229 Constant *GE; 00230 /// Range - A pair of iterators representing the range of case values to be 00231 /// processed at this point in the binary search tree. 00232 CaseRange Range; 00233 }; 00234 00235 typedef std::vector<CaseRec> CaseRecVector; 00236 00237 /// The comparison function for sorting the switch case values in the vector. 00238 /// WARNING: Case ranges should be disjoint! 00239 struct CaseCmp { 00240 bool operator () (const Case& C1, const Case& C2) { 00241 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 00242 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 00243 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 00244 return CI1->getValue().slt(CI2->getValue()); 00245 } 00246 }; 00247 00248 struct CaseBitsCmp { 00249 bool operator () (const CaseBits& C1, const CaseBits& C2) { 00250 return C1.Bits > C2.Bits; 00251 } 00252 }; 00253 00254 size_t Clusterify(CaseVector& Cases, const SwitchInst &SI); 00255 00256 /// CaseBlock - This structure is used to communicate between SDLowering and 00257 /// SDISel for the code generation of additional basic blocks needed by multi- 00258 /// case switch statements. 00259 struct CaseBlock { 00260 CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, Value *cmpmiddle, 00261 MachineBasicBlock *truebb, MachineBasicBlock *falsebb, 00262 MachineBasicBlock *me) 00263 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), 00264 TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} 00265 // CC - the condition code to use for the case block's setcc node 00266 ISD::CondCode CC; 00267 // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. 00268 // Emit by default LHS op RHS. MHS is used for range comparisons: 00269 // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). 00270 Value *CmpLHS, *CmpMHS, *CmpRHS; 00271 // TrueBB/FalseBB - the block to branch to if the setcc is true/false. 00272 MachineBasicBlock *TrueBB, *FalseBB; 00273 // ThisBB - the block into which to emit the code for the setcc and branches 00274 MachineBasicBlock *ThisBB; 00275 }; 00276 struct JumpTable { 00277 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, 00278 MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} 00279 00280 /// Reg - the virtual register containing the index of the jump table entry 00281 //. to jump to. 00282 unsigned Reg; 00283 /// JTI - the JumpTableIndex for this jump table in the function. 00284 unsigned JTI; 00285 /// MBB - the MBB into which to emit the code for the indirect jump. 00286 MachineBasicBlock *MBB; 00287 /// Default - the MBB of the default bb, which is a successor of the range 00288 /// check MBB. This is when updating PHI nodes in successors. 00289 MachineBasicBlock *Default; 00290 }; 00291 struct JumpTableHeader { 00292 JumpTableHeader(APInt F, APInt L, Value* SV, MachineBasicBlock* H, 00293 bool E = false): 00294 First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} 00295 APInt First; 00296 APInt Last; 00297 Value *SValue; 00298 MachineBasicBlock *HeaderBB; 00299 bool Emitted; 00300 }; 00301 typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock; 00302 00303 struct BitTestCase { 00304 BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr): 00305 Mask(M), ThisBB(T), TargetBB(Tr) { } 00306 uint64_t Mask; 00307 MachineBasicBlock* ThisBB; 00308 MachineBasicBlock* TargetBB; 00309 }; 00310 00311 typedef SmallVector<BitTestCase, 3> BitTestInfo; 00312 00313 struct BitTestBlock { 00314 BitTestBlock(APInt F, APInt R, Value* SV, 00315 unsigned Rg, bool E, 00316 MachineBasicBlock* P, MachineBasicBlock* D, 00317 const BitTestInfo& C): 00318 First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E), 00319 Parent(P), Default(D), Cases(C) { } 00320 APInt First; 00321 APInt Range; 00322 Value *SValue; 00323 unsigned Reg; 00324 bool Emitted; 00325 MachineBasicBlock *Parent; 00326 MachineBasicBlock *Default; 00327 BitTestInfo Cases; 00328 }; 00329 00330 public: 00331 // TLI - This is information that describes the available target features we 00332 // need for lowering. This indicates when operations are unavailable, 00333 // implemented with a libcall, etc. 00334 TargetLowering &TLI; 00335 SelectionDAG &DAG; 00336 const TargetData *TD; 00337 AliasAnalysis *AA; 00338 00339 /// SwitchCases - Vector of CaseBlock structures used to communicate 00340 /// SwitchInst code generation information. 00341 std::vector<CaseBlock> SwitchCases; 00342 /// JTCases - Vector of JumpTable structures used to communicate 00343 /// SwitchInst code generation information. 00344 std::vector<JumpTableBlock> JTCases; 00345 /// BitTestCases - Vector of BitTestBlock structures used to communicate 00346 /// SwitchInst code generation information. 00347 std::vector<BitTestBlock> BitTestCases; 00348 00349 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 00350 00351 // Emit PHI-node-operand constants only once even if used by multiple 00352 // PHI nodes. 00353 DenseMap<Constant*, unsigned> ConstantsOut; 00354 00355 /// FuncInfo - Information about the function as a whole. 00356 /// 00357 FunctionLoweringInfo &FuncInfo; 00358 00359 /// OptLevel - What optimization level we're generating code for. 00360 /// 00361 CodeGenOpt::Level OptLevel; 00362 00363 /// GFI - Garbage collection metadata for the function. 00364 GCFunctionInfo *GFI; 00365 00366 /// HasTailCall - This is set to true if a call in the current 00367 /// block has been translated as a tail call. In this case, 00368 /// no subsequent DAG nodes should be created. 00369 /// 00370 bool HasTailCall; 00371 00372 LLVMContext *Context; 00373 00374 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 00375 FunctionLoweringInfo &funcinfo, 00376 CodeGenOpt::Level ol) 00377 : CurDebugLoc(DebugLoc::getUnknownLoc()), 00378 TLI(tli), DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 00379 HasTailCall(false), 00380 Context(dag.getContext()) { 00381 } 00382 00383 void init(GCFunctionInfo *gfi, AliasAnalysis &aa); 00384 00385 /// clear - Clear out the curret SelectionDAG and the associated 00386 /// state and prepare this SelectionDAGLowering object to be used 00387 /// for a new block. This doesn't clear out information about 00388 /// additional blocks that are needed to complete switch lowering 00389 /// or PHI node updating; that information is cleared out as it is 00390 /// consumed. 00391 void clear(); 00392 00393 /// getRoot - Return the current virtual root of the Selection DAG, 00394 /// flushing any PendingLoad items. This must be done before emitting 00395 /// a store or any other node that may need to be ordered after any 00396 /// prior load instructions. 00397 /// 00398 SDValue getRoot(); 00399 00400 /// getControlRoot - Similar to getRoot, but instead of flushing all the 00401 /// PendingLoad items, flush all the PendingExports items. It is necessary 00402 /// to do this before emitting a terminator instruction. 00403 /// 00404 SDValue getControlRoot(); 00405 00406 DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 00407 void setCurDebugLoc(DebugLoc dl) { CurDebugLoc = dl; } 00408 00409 void CopyValueToVirtualRegister(Value *V, unsigned Reg); 00410 00411 void visit(Instruction &I); 00412 00413 void visit(unsigned Opcode, User &I); 00414 00415 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 00416 00417 SDValue getValue(const Value *V); 00418 00419 void setValue(const Value *V, SDValue NewN) { 00420 SDValue &N = NodeMap[V]; 00421 assert(N.getNode() == 0 && "Already set a value for this node!"); 00422 N = NewN; 00423 } 00424 00425 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 00426 std::set<unsigned> &OutputRegs, 00427 std::set<unsigned> &InputRegs); 00428 00429 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 00430 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 00431 unsigned Opc); 00432 void EmitBranchForMergedCondition(Value *Cond, MachineBasicBlock *TBB, 00433 MachineBasicBlock *FBB, 00434 MachineBasicBlock *CurBB); 00435 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 00436 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 00437 void CopyToExportRegsIfNeeded(Value *V); 00438 void ExportFromCurrentBlock(Value *V); 00439 void LowerCallTo(CallSite CS, SDValue Callee, bool IsTailCall, 00440 MachineBasicBlock *LandingPad = NULL); 00441 00442 private: 00443 // Terminator instructions. 00444 void visitRet(ReturnInst &I); 00445 void visitBr(BranchInst &I); 00446 void visitSwitch(SwitchInst &I); 00447 void visitUnreachable(UnreachableInst &I) { /* noop */ } 00448 00449 // Helpers for visitSwitch 00450 bool handleSmallSwitchRange(CaseRec& CR, 00451 CaseRecVector& WorkList, 00452 Value* SV, 00453 MachineBasicBlock* Default); 00454 bool handleJTSwitchCase(CaseRec& CR, 00455 CaseRecVector& WorkList, 00456 Value* SV, 00457 MachineBasicBlock* Default); 00458 bool handleBTSplitSwitchCase(CaseRec& CR, 00459 CaseRecVector& WorkList, 00460 Value* SV, 00461 MachineBasicBlock* Default); 00462 bool handleBitTestsSwitchCase(CaseRec& CR, 00463 CaseRecVector& WorkList, 00464 Value* SV, 00465 MachineBasicBlock* Default); 00466 public: 00467 void visitSwitchCase(CaseBlock &CB); 00468 void visitBitTestHeader(BitTestBlock &B); 00469 void visitBitTestCase(MachineBasicBlock* NextMBB, 00470 unsigned Reg, 00471 BitTestCase &B); 00472 void visitJumpTable(JumpTable &JT); 00473 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH); 00474 00475 private: 00476 // These all get lowered before this pass. 00477 void visitInvoke(InvokeInst &I); 00478 void visitUnwind(UnwindInst &I); 00479 00480 void visitBinary(User &I, unsigned OpCode); 00481 void visitShift(User &I, unsigned Opcode); 00482 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 00483 void visitFAdd(User &I) { visitBinary(I, ISD::FADD); } 00484 void visitSub(User &I) { visitBinary(I, ISD::SUB); } 00485 void visitFSub(User &I); 00486 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 00487 void visitFMul(User &I) { visitBinary(I, ISD::FMUL); } 00488 void visitURem(User &I) { visitBinary(I, ISD::UREM); } 00489 void visitSRem(User &I) { visitBinary(I, ISD::SREM); } 00490 void visitFRem(User &I) { visitBinary(I, ISD::FREM); } 00491 void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); } 00492 void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); } 00493 void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); } 00494 void visitAnd (User &I) { visitBinary(I, ISD::AND); } 00495 void visitOr (User &I) { visitBinary(I, ISD::OR); } 00496 void visitXor (User &I) { visitBinary(I, ISD::XOR); } 00497 void visitShl (User &I) { visitShift(I, ISD::SHL); } 00498 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 00499 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 00500 void visitICmp(User &I); 00501 void visitFCmp(User &I); 00502 // Visit the conversion instructions 00503 void visitTrunc(User &I); 00504 void visitZExt(User &I); 00505 void visitSExt(User &I); 00506 void visitFPTrunc(User &I); 00507 void visitFPExt(User &I); 00508 void visitFPToUI(User &I); 00509 void visitFPToSI(User &I); 00510 void visitUIToFP(User &I); 00511 void visitSIToFP(User &I); 00512 void visitPtrToInt(User &I); 00513 void visitIntToPtr(User &I); 00514 void visitBitCast(User &I); 00515 00516 void visitExtractElement(User &I); 00517 void visitInsertElement(User &I); 00518 void visitShuffleVector(User &I); 00519 00520 void visitExtractValue(ExtractValueInst &I); 00521 void visitInsertValue(InsertValueInst &I); 00522 00523 void visitGetElementPtr(User &I); 00524 void visitSelect(User &I); 00525 00526 void visitMalloc(MallocInst &I); 00527 void visitFree(FreeInst &I); 00528 void visitAlloca(AllocaInst &I); 00529 void visitLoad(LoadInst &I); 00530 void visitStore(StoreInst &I); 00531 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 00532 void visitCall(CallInst &I); 00533 void visitInlineAsm(CallSite CS); 00534 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 00535 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 00536 00537 void visitPow(CallInst &I); 00538 void visitExp2(CallInst &I); 00539 void visitExp(CallInst &I); 00540 void visitLog(CallInst &I); 00541 void visitLog2(CallInst &I); 00542 void visitLog10(CallInst &I); 00543 00544 void visitVAStart(CallInst &I); 00545 void visitVAArg(VAArgInst &I); 00546 void visitVAEnd(CallInst &I); 00547 void visitVACopy(CallInst &I); 00548 00549 void visitUserOp1(Instruction &I) { 00550 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 00551 } 00552 void visitUserOp2(Instruction &I) { 00553 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 00554 } 00555 00556 const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op); 00557 const char *implVisitAluOverflow(CallInst &I, ISD::NodeType Op); 00558 }; 00559 00560 /// AddCatchInfo - Extract the personality and type infos from an eh.selector 00561 /// call, and add them to the specified machine basic block. 00562 void AddCatchInfo(CallInst &I, MachineModuleInfo *MMI, 00563 MachineBasicBlock *MBB); 00564 00565 } // end namespace llvm 00566 00567 #endif