1 //===-- SelectionDAGBuilder.h - Selection-DAG building --------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This implements routines for translating from LLVM IR into SelectionDAG IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef SELECTIONDAGBUILDER_H 15 #define SELECTIONDAGBUILDER_H 16 17 #include "llvm/Constants.h" 18 #include "llvm/CodeGen/SelectionDAG.h" 19 #include "llvm/ADT/APInt.h" 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/CodeGen/SelectionDAGNodes.h" 22 #include "llvm/CodeGen/ValueTypes.h" 23 #include "llvm/Support/CallSite.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include <vector> 26 #include <set> 27 28 namespace llvm { 29 30 class AliasAnalysis; 31 class AllocaInst; 32 class BasicBlock; 33 class BitCastInst; 34 class BranchInst; 35 class CallInst; 36 class DbgValueInst; 37 class ExtractElementInst; 38 class ExtractValueInst; 39 class FCmpInst; 40 class FPExtInst; 41 class FPToSIInst; 42 class FPToUIInst; 43 class FPTruncInst; 44 class Function; 45 class FunctionLoweringInfo; 46 class GetElementPtrInst; 47 class GCFunctionInfo; 48 class ICmpInst; 49 class IntToPtrInst; 50 class IndirectBrInst; 51 class InvokeInst; 52 class InsertElementInst; 53 class InsertValueInst; 54 class Instruction; 55 class LoadInst; 56 class MachineBasicBlock; 57 class MachineInstr; 58 class MachineRegisterInfo; 59 class MDNode; 60 class PHINode; 61 class PtrToIntInst; 62 class ReturnInst; 63 class SDISelAsmOperandInfo; 64 class SDDbgValue; 65 class SExtInst; 66 class SelectInst; 67 class ShuffleVectorInst; 68 class SIToFPInst; 69 class StoreInst; 70 class SwitchInst; 71 class TargetData; 72 class TargetLowering; 73 class TruncInst; 74 class UIToFPInst; 75 class UnreachableInst; 76 class UnwindInst; 77 class VAArgInst; 78 class ZExtInst; 79 80 //===----------------------------------------------------------------------===// 81 /// SelectionDAGBuilder - This is the common target-independent lowering 82 /// implementation that is parameterized by a TargetLowering object. 83 /// 84 class SelectionDAGBuilder { 85 /// CurDebugLoc - current file + line number. Changes as we build the DAG. 86 DebugLoc CurDebugLoc; 87 88 DenseMap<const Value*, SDValue> NodeMap; 89 90 /// UnusedArgNodeMap - Maps argument value for unused arguments. This is used 91 /// to preserve debug information for incoming arguments. 92 DenseMap<const Value*, SDValue> UnusedArgNodeMap; 93 94 /// DanglingDebugInfo - Helper type for DanglingDebugInfoMap. 95 class DanglingDebugInfo { 96 const DbgValueInst* DI; 97 DebugLoc dl; 98 unsigned SDNodeOrder; 99 public: DanglingDebugInfo()100 DanglingDebugInfo() : DI(0), dl(DebugLoc()), SDNodeOrder(0) { } DanglingDebugInfo(const DbgValueInst * di,DebugLoc DL,unsigned SDNO)101 DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) : 102 DI(di), dl(DL), SDNodeOrder(SDNO) { } getDI()103 const DbgValueInst* getDI() { return DI; } getdl()104 DebugLoc getdl() { return dl; } getSDNodeOrder()105 unsigned getSDNodeOrder() { return SDNodeOrder; } 106 }; 107 108 /// DanglingDebugInfoMap - Keeps track of dbg_values for which we have not 109 /// yet seen the referent. We defer handling these until we do see it. 110 DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap; 111 112 public: 113 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 114 /// them up and then emit token factor nodes when possible. This allows us to 115 /// get simple disambiguation between loads without worrying about alias 116 /// analysis. 117 SmallVector<SDValue, 8> PendingLoads; 118 private: 119 120 /// PendingExports - CopyToReg nodes that copy values to virtual registers 121 /// for export to other blocks need to be emitted before any terminator 122 /// instruction, but they have no other ordering requirements. We bunch them 123 /// up and the emit a single tokenfactor for them just before terminator 124 /// instructions. 125 SmallVector<SDValue, 8> PendingExports; 126 127 /// SDNodeOrder - A unique monotonically increasing number used to order the 128 /// SDNodes we create. 129 unsigned SDNodeOrder; 130 131 /// Case - A struct to record the Value for a switch case, and the 132 /// case's target basic block. 133 struct Case { 134 Constant* Low; 135 Constant* High; 136 MachineBasicBlock* BB; 137 CaseCase138 Case() : Low(0), High(0), BB(0) { } CaseCase139 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 140 Low(low), High(high), BB(bb) { } sizeCase141 APInt size() const { 142 const APInt &rHigh = cast<ConstantInt>(High)->getValue(); 143 const APInt &rLow = cast<ConstantInt>(Low)->getValue(); 144 return (rHigh - rLow + 1ULL); 145 } 146 }; 147 148 struct CaseBits { 149 uint64_t Mask; 150 MachineBasicBlock* BB; 151 unsigned Bits; 152 CaseBitsCaseBits153 CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits): 154 Mask(mask), BB(bb), Bits(bits) { } 155 }; 156 157 typedef std::vector<Case> CaseVector; 158 typedef std::vector<CaseBits> CaseBitsVector; 159 typedef CaseVector::iterator CaseItr; 160 typedef std::pair<CaseItr, CaseItr> CaseRange; 161 162 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 163 /// of conditional branches. 164 struct CaseRec { CaseRecCaseRec165 CaseRec(MachineBasicBlock *bb, const Constant *lt, const Constant *ge, 166 CaseRange r) : 167 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 168 169 /// CaseBB - The MBB in which to emit the compare and branch 170 MachineBasicBlock *CaseBB; 171 /// LT, GE - If nonzero, we know the current case value must be less-than or 172 /// greater-than-or-equal-to these Constants. 173 const Constant *LT; 174 const Constant *GE; 175 /// Range - A pair of iterators representing the range of case values to be 176 /// processed at this point in the binary search tree. 177 CaseRange Range; 178 }; 179 180 typedef std::vector<CaseRec> CaseRecVector; 181 182 /// The comparison function for sorting the switch case values in the vector. 183 /// WARNING: Case ranges should be disjoint! 184 struct CaseCmp { operatorCaseCmp185 bool operator()(const Case &C1, const Case &C2) { 186 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 187 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 188 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 189 return CI1->getValue().slt(CI2->getValue()); 190 } 191 }; 192 193 struct CaseBitsCmp { operatorCaseBitsCmp194 bool operator()(const CaseBits &C1, const CaseBits &C2) { 195 return C1.Bits > C2.Bits; 196 } 197 }; 198 199 size_t Clusterify(CaseVector &Cases, const SwitchInst &SI); 200 201 /// CaseBlock - This structure is used to communicate between 202 /// SelectionDAGBuilder and SDISel for the code generation of additional basic 203 /// blocks needed by multi-case switch statements. 204 struct CaseBlock { CaseBlockCaseBlock205 CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, 206 const Value *cmpmiddle, 207 MachineBasicBlock *truebb, MachineBasicBlock *falsebb, 208 MachineBasicBlock *me) 209 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), 210 TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} 211 // CC - the condition code to use for the case block's setcc node 212 ISD::CondCode CC; 213 // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. 214 // Emit by default LHS op RHS. MHS is used for range comparisons: 215 // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). 216 const Value *CmpLHS, *CmpMHS, *CmpRHS; 217 // TrueBB/FalseBB - the block to branch to if the setcc is true/false. 218 MachineBasicBlock *TrueBB, *FalseBB; 219 // ThisBB - the block into which to emit the code for the setcc and branches 220 MachineBasicBlock *ThisBB; 221 }; 222 struct JumpTable { JumpTableJumpTable223 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, 224 MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} 225 226 /// Reg - the virtual register containing the index of the jump table entry 227 //. to jump to. 228 unsigned Reg; 229 /// JTI - the JumpTableIndex for this jump table in the function. 230 unsigned JTI; 231 /// MBB - the MBB into which to emit the code for the indirect jump. 232 MachineBasicBlock *MBB; 233 /// Default - the MBB of the default bb, which is a successor of the range 234 /// check MBB. This is when updating PHI nodes in successors. 235 MachineBasicBlock *Default; 236 }; 237 struct JumpTableHeader { 238 JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, 239 bool E = false): FirstJumpTableHeader240 First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} 241 APInt First; 242 APInt Last; 243 const Value *SValue; 244 MachineBasicBlock *HeaderBB; 245 bool Emitted; 246 }; 247 typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock; 248 249 struct BitTestCase { BitTestCaseBitTestCase250 BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr): 251 Mask(M), ThisBB(T), TargetBB(Tr) { } 252 uint64_t Mask; 253 MachineBasicBlock *ThisBB; 254 MachineBasicBlock *TargetBB; 255 }; 256 257 typedef SmallVector<BitTestCase, 3> BitTestInfo; 258 259 struct BitTestBlock { BitTestBlockBitTestBlock260 BitTestBlock(APInt F, APInt R, const Value* SV, 261 unsigned Rg, bool E, 262 MachineBasicBlock* P, MachineBasicBlock* D, 263 const BitTestInfo& C): 264 First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E), 265 Parent(P), Default(D), Cases(C) { } 266 APInt First; 267 APInt Range; 268 const Value *SValue; 269 unsigned Reg; 270 bool Emitted; 271 MachineBasicBlock *Parent; 272 MachineBasicBlock *Default; 273 BitTestInfo Cases; 274 }; 275 276 public: 277 // TLI - This is information that describes the available target features we 278 // need for lowering. This indicates when operations are unavailable, 279 // implemented with a libcall, etc. 280 const TargetMachine &TM; 281 const TargetLowering &TLI; 282 SelectionDAG &DAG; 283 const TargetData *TD; 284 AliasAnalysis *AA; 285 286 /// SwitchCases - Vector of CaseBlock structures used to communicate 287 /// SwitchInst code generation information. 288 std::vector<CaseBlock> SwitchCases; 289 /// JTCases - Vector of JumpTable structures used to communicate 290 /// SwitchInst code generation information. 291 std::vector<JumpTableBlock> JTCases; 292 /// BitTestCases - Vector of BitTestBlock structures used to communicate 293 /// SwitchInst code generation information. 294 std::vector<BitTestBlock> BitTestCases; 295 296 // Emit PHI-node-operand constants only once even if used by multiple 297 // PHI nodes. 298 DenseMap<const Constant *, unsigned> ConstantsOut; 299 300 /// FuncInfo - Information about the function as a whole. 301 /// 302 FunctionLoweringInfo &FuncInfo; 303 304 /// OptLevel - What optimization level we're generating code for. 305 /// 306 CodeGenOpt::Level OptLevel; 307 308 /// GFI - Garbage collection metadata for the function. 309 GCFunctionInfo *GFI; 310 311 /// HasTailCall - This is set to true if a call in the current 312 /// block has been translated as a tail call. In this case, 313 /// no subsequent DAG nodes should be created. 314 /// 315 bool HasTailCall; 316 317 LLVMContext *Context; 318 SelectionDAGBuilder(SelectionDAG & dag,FunctionLoweringInfo & funcinfo,CodeGenOpt::Level ol)319 SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, 320 CodeGenOpt::Level ol) 321 : SDNodeOrder(0), TM(dag.getTarget()), TLI(dag.getTargetLoweringInfo()), 322 DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 323 HasTailCall(false), Context(dag.getContext()) { 324 } 325 326 void init(GCFunctionInfo *gfi, AliasAnalysis &aa); 327 328 /// clear - Clear out the current SelectionDAG and the associated 329 /// state and prepare this SelectionDAGBuilder object to be used 330 /// for a new block. This doesn't clear out information about 331 /// additional blocks that are needed to complete switch lowering 332 /// or PHI node updating; that information is cleared out as it is 333 /// consumed. 334 void clear(); 335 336 /// getRoot - Return the current virtual root of the Selection DAG, 337 /// flushing any PendingLoad items. This must be done before emitting 338 /// a store or any other node that may need to be ordered after any 339 /// prior load instructions. 340 /// 341 SDValue getRoot(); 342 343 /// getControlRoot - Similar to getRoot, but instead of flushing all the 344 /// PendingLoad items, flush all the PendingExports items. It is necessary 345 /// to do this before emitting a terminator instruction. 346 /// 347 SDValue getControlRoot(); 348 getCurDebugLoc()349 DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 350 getSDNodeOrder()351 unsigned getSDNodeOrder() const { return SDNodeOrder; } 352 353 void CopyValueToVirtualRegister(const Value *V, unsigned Reg); 354 355 /// AssignOrderingToNode - Assign an ordering to the node. The order is gotten 356 /// from how the code appeared in the source. The ordering is used by the 357 /// scheduler to effectively turn off scheduling. 358 void AssignOrderingToNode(const SDNode *Node); 359 360 void visit(const Instruction &I); 361 362 void visit(unsigned Opcode, const User &I); 363 364 // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V, 365 // generate the debug data structures now that we've seen its definition. 366 void resolveDanglingDebugInfo(const Value *V, SDValue Val); 367 SDValue getValue(const Value *V); 368 SDValue getNonRegisterValue(const Value *V); 369 SDValue getValueImpl(const Value *V); 370 setValue(const Value * V,SDValue NewN)371 void setValue(const Value *V, SDValue NewN) { 372 SDValue &N = NodeMap[V]; 373 assert(N.getNode() == 0 && "Already set a value for this node!"); 374 N = NewN; 375 } 376 setUnusedArgValue(const Value * V,SDValue NewN)377 void setUnusedArgValue(const Value *V, SDValue NewN) { 378 SDValue &N = UnusedArgNodeMap[V]; 379 assert(N.getNode() == 0 && "Already set a value for this node!"); 380 N = NewN; 381 } 382 383 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 384 std::set<unsigned> &OutputRegs, 385 std::set<unsigned> &InputRegs); 386 387 void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, 388 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 389 MachineBasicBlock *SwitchBB, unsigned Opc); 390 void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, 391 MachineBasicBlock *FBB, 392 MachineBasicBlock *CurBB, 393 MachineBasicBlock *SwitchBB); 394 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 395 bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); 396 void CopyToExportRegsIfNeeded(const Value *V); 397 void ExportFromCurrentBlock(const Value *V); 398 void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall, 399 MachineBasicBlock *LandingPad = NULL); 400 401 private: 402 // Terminator instructions. 403 void visitRet(const ReturnInst &I); 404 void visitBr(const BranchInst &I); 405 void visitSwitch(const SwitchInst &I); 406 void visitIndirectBr(const IndirectBrInst &I); visitUnreachable(const UnreachableInst & I)407 void visitUnreachable(const UnreachableInst &I) { /* noop */ } 408 409 // Helpers for visitSwitch 410 bool handleSmallSwitchRange(CaseRec& CR, 411 CaseRecVector& WorkList, 412 const Value* SV, 413 MachineBasicBlock* Default, 414 MachineBasicBlock *SwitchBB); 415 bool handleJTSwitchCase(CaseRec& CR, 416 CaseRecVector& WorkList, 417 const Value* SV, 418 MachineBasicBlock* Default, 419 MachineBasicBlock *SwitchBB); 420 bool handleBTSplitSwitchCase(CaseRec& CR, 421 CaseRecVector& WorkList, 422 const Value* SV, 423 MachineBasicBlock* Default, 424 MachineBasicBlock *SwitchBB); 425 bool handleBitTestsSwitchCase(CaseRec& CR, 426 CaseRecVector& WorkList, 427 const Value* SV, 428 MachineBasicBlock* Default, 429 MachineBasicBlock *SwitchBB); 430 public: 431 void visitSwitchCase(CaseBlock &CB, 432 MachineBasicBlock *SwitchBB); 433 void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); 434 void visitBitTestCase(MachineBasicBlock* NextMBB, 435 unsigned Reg, 436 BitTestCase &B, 437 MachineBasicBlock *SwitchBB); 438 void visitJumpTable(JumpTable &JT); 439 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, 440 MachineBasicBlock *SwitchBB); 441 442 private: 443 // These all get lowered before this pass. 444 void visitInvoke(const InvokeInst &I); 445 void visitUnwind(const UnwindInst &I); 446 447 void visitBinary(const User &I, unsigned OpCode); 448 void visitShift(const User &I, unsigned Opcode); visitAdd(const User & I)449 void visitAdd(const User &I) { visitBinary(I, ISD::ADD); } visitFAdd(const User & I)450 void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); } visitSub(const User & I)451 void visitSub(const User &I) { visitBinary(I, ISD::SUB); } 452 void visitFSub(const User &I); visitMul(const User & I)453 void visitMul(const User &I) { visitBinary(I, ISD::MUL); } visitFMul(const User & I)454 void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); } visitURem(const User & I)455 void visitURem(const User &I) { visitBinary(I, ISD::UREM); } visitSRem(const User & I)456 void visitSRem(const User &I) { visitBinary(I, ISD::SREM); } visitFRem(const User & I)457 void visitFRem(const User &I) { visitBinary(I, ISD::FREM); } visitUDiv(const User & I)458 void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); } visitSDiv(const User & I)459 void visitSDiv(const User &I) { visitBinary(I, ISD::SDIV); } visitFDiv(const User & I)460 void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); } visitAnd(const User & I)461 void visitAnd (const User &I) { visitBinary(I, ISD::AND); } visitOr(const User & I)462 void visitOr (const User &I) { visitBinary(I, ISD::OR); } visitXor(const User & I)463 void visitXor (const User &I) { visitBinary(I, ISD::XOR); } visitShl(const User & I)464 void visitShl (const User &I) { visitShift(I, ISD::SHL); } visitLShr(const User & I)465 void visitLShr(const User &I) { visitShift(I, ISD::SRL); } visitAShr(const User & I)466 void visitAShr(const User &I) { visitShift(I, ISD::SRA); } 467 void visitICmp(const User &I); 468 void visitFCmp(const User &I); 469 // Visit the conversion instructions 470 void visitTrunc(const User &I); 471 void visitZExt(const User &I); 472 void visitSExt(const User &I); 473 void visitFPTrunc(const User &I); 474 void visitFPExt(const User &I); 475 void visitFPToUI(const User &I); 476 void visitFPToSI(const User &I); 477 void visitUIToFP(const User &I); 478 void visitSIToFP(const User &I); 479 void visitPtrToInt(const User &I); 480 void visitIntToPtr(const User &I); 481 void visitBitCast(const User &I); 482 483 void visitExtractElement(const User &I); 484 void visitInsertElement(const User &I); 485 void visitShuffleVector(const User &I); 486 487 void visitExtractValue(const ExtractValueInst &I); 488 void visitInsertValue(const InsertValueInst &I); 489 490 void visitGetElementPtr(const User &I); 491 void visitSelect(const User &I); 492 493 void visitAlloca(const AllocaInst &I); 494 void visitLoad(const LoadInst &I); 495 void visitStore(const StoreInst &I); 496 void visitPHI(const PHINode &I); 497 void visitCall(const CallInst &I); 498 bool visitMemCmpCall(const CallInst &I); 499 500 void visitInlineAsm(ImmutableCallSite CS); 501 const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic); 502 void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic); 503 504 void visitPow(const CallInst &I); 505 void visitExp2(const CallInst &I); 506 void visitExp(const CallInst &I); 507 void visitLog(const CallInst &I); 508 void visitLog2(const CallInst &I); 509 void visitLog10(const CallInst &I); 510 511 void visitVAStart(const CallInst &I); 512 void visitVAArg(const VAArgInst &I); 513 void visitVAEnd(const CallInst &I); 514 void visitVACopy(const CallInst &I); 515 visitUserOp1(const Instruction & I)516 void visitUserOp1(const Instruction &I) { 517 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 518 } visitUserOp2(const Instruction & I)519 void visitUserOp2(const Instruction &I) { 520 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 521 } 522 523 const char *implVisitBinaryAtomic(const CallInst& I, ISD::NodeType Op); 524 const char *implVisitAluOverflow(const CallInst &I, ISD::NodeType Op); 525 526 void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 527 528 /// EmitFuncArgumentDbgValue - If V is an function argument then create 529 /// corresponding DBG_VALUE machine instruction for it now. At the end of 530 /// instruction selection, they will be inserted to the entry BB. 531 bool EmitFuncArgumentDbgValue(const Value *V, MDNode *Variable, 532 int64_t Offset, const SDValue &N); 533 }; 534 535 } // end namespace llvm 536 537 #endif 538