SelectionDAGBuilder.h revision 68e6beeccc0b9ac2e8d3687a8a5b7d4b172edca1
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 28namespace llvm { 29 30class AliasAnalysis; 31class AllocaInst; 32class BasicBlock; 33class BitCastInst; 34class BranchInst; 35class CallInst; 36class DbgValueInst; 37class ExtractElementInst; 38class ExtractValueInst; 39class FCmpInst; 40class FPExtInst; 41class FPToSIInst; 42class FPToUIInst; 43class FPTruncInst; 44class Function; 45class FunctionLoweringInfo; 46class GetElementPtrInst; 47class GCFunctionInfo; 48class ICmpInst; 49class IntToPtrInst; 50class IndirectBrInst; 51class InvokeInst; 52class InsertElementInst; 53class InsertValueInst; 54class Instruction; 55class LoadInst; 56class MachineBasicBlock; 57class MachineInstr; 58class MachineRegisterInfo; 59class MDNode; 60class PHINode; 61class PtrToIntInst; 62class ReturnInst; 63class SDISelAsmOperandInfo; 64class SDDbgValue; 65class SExtInst; 66class SelectInst; 67class ShuffleVectorInst; 68class SIToFPInst; 69class StoreInst; 70class SwitchInst; 71class TargetData; 72class TargetLowering; 73class TruncInst; 74class UIToFPInst; 75class UnreachableInst; 76class UnwindInst; 77class VAArgInst; 78class ZExtInst; 79 80//===----------------------------------------------------------------------===// 81/// SelectionDAGBuilder - This is the common target-independent lowering 82/// implementation that is parameterized by a TargetLowering object. 83/// 84class 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: 100 DanglingDebugInfo() : DI(0), dl(DebugLoc()), SDNodeOrder(0) { } 101 DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) : 102 DI(di), dl(DL), SDNodeOrder(SDNO) { } 103 const DbgValueInst* getDI() { return DI; } 104 DebugLoc getdl() { return dl; } 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 112public: 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; 118private: 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 138 Case() : Low(0), High(0), BB(0) { } 139 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 140 Low(low), High(high), BB(bb) { } 141 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 153 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 { 165 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 { 185 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 { 194 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 { 205 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 { 223 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): 240 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 { 250 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 { 260 BitTestBlock(APInt F, APInt R, const Value* SV, 261 unsigned Rg, EVT RgVT, bool E, 262 MachineBasicBlock* P, MachineBasicBlock* D, 263 const BitTestInfo& C): 264 First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), 265 Parent(P), Default(D), Cases(C) { } 266 APInt First; 267 APInt Range; 268 const Value *SValue; 269 unsigned Reg; 270 EVT RegVT; 271 bool Emitted; 272 MachineBasicBlock *Parent; 273 MachineBasicBlock *Default; 274 BitTestInfo Cases; 275 }; 276 277public: 278 // TLI - This is information that describes the available target features we 279 // need for lowering. This indicates when operations are unavailable, 280 // implemented with a libcall, etc. 281 const TargetMachine &TM; 282 const TargetLowering &TLI; 283 SelectionDAG &DAG; 284 const TargetData *TD; 285 AliasAnalysis *AA; 286 287 /// SwitchCases - Vector of CaseBlock structures used to communicate 288 /// SwitchInst code generation information. 289 std::vector<CaseBlock> SwitchCases; 290 /// JTCases - Vector of JumpTable structures used to communicate 291 /// SwitchInst code generation information. 292 std::vector<JumpTableBlock> JTCases; 293 /// BitTestCases - Vector of BitTestBlock structures used to communicate 294 /// SwitchInst code generation information. 295 std::vector<BitTestBlock> BitTestCases; 296 297 // Emit PHI-node-operand constants only once even if used by multiple 298 // PHI nodes. 299 DenseMap<const Constant *, unsigned> ConstantsOut; 300 301 /// FuncInfo - Information about the function as a whole. 302 /// 303 FunctionLoweringInfo &FuncInfo; 304 305 /// OptLevel - What optimization level we're generating code for. 306 /// 307 CodeGenOpt::Level OptLevel; 308 309 /// GFI - Garbage collection metadata for the function. 310 GCFunctionInfo *GFI; 311 312 /// HasTailCall - This is set to true if a call in the current 313 /// block has been translated as a tail call. In this case, 314 /// no subsequent DAG nodes should be created. 315 /// 316 bool HasTailCall; 317 318 LLVMContext *Context; 319 320 SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, 321 CodeGenOpt::Level ol) 322 : SDNodeOrder(0), TM(dag.getTarget()), TLI(dag.getTargetLoweringInfo()), 323 DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 324 HasTailCall(false), Context(dag.getContext()) { 325 } 326 327 void init(GCFunctionInfo *gfi, AliasAnalysis &aa); 328 329 /// clear - Clear out the current SelectionDAG and the associated 330 /// state and prepare this SelectionDAGBuilder object to be used 331 /// for a new block. This doesn't clear out information about 332 /// additional blocks that are needed to complete switch lowering 333 /// or PHI node updating; that information is cleared out as it is 334 /// consumed. 335 void clear(); 336 337 /// getRoot - Return the current virtual root of the Selection DAG, 338 /// flushing any PendingLoad items. This must be done before emitting 339 /// a store or any other node that may need to be ordered after any 340 /// prior load instructions. 341 /// 342 SDValue getRoot(); 343 344 /// getControlRoot - Similar to getRoot, but instead of flushing all the 345 /// PendingLoad items, flush all the PendingExports items. It is necessary 346 /// to do this before emitting a terminator instruction. 347 /// 348 SDValue getControlRoot(); 349 350 DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 351 352 unsigned getSDNodeOrder() const { return SDNodeOrder; } 353 354 void CopyValueToVirtualRegister(const Value *V, unsigned Reg); 355 356 /// AssignOrderingToNode - Assign an ordering to the node. The order is gotten 357 /// from how the code appeared in the source. The ordering is used by the 358 /// scheduler to effectively turn off scheduling. 359 void AssignOrderingToNode(const SDNode *Node); 360 361 void visit(const Instruction &I); 362 363 void visit(unsigned Opcode, const User &I); 364 365 // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V, 366 // generate the debug data structures now that we've seen its definition. 367 void resolveDanglingDebugInfo(const Value *V, SDValue Val); 368 SDValue getValue(const Value *V); 369 SDValue getNonRegisterValue(const Value *V); 370 SDValue getValueImpl(const Value *V); 371 372 void setValue(const Value *V, SDValue NewN) { 373 SDValue &N = NodeMap[V]; 374 assert(N.getNode() == 0 && "Already set a value for this node!"); 375 N = NewN; 376 } 377 378 void setUnusedArgValue(const Value *V, SDValue NewN) { 379 SDValue &N = UnusedArgNodeMap[V]; 380 assert(N.getNode() == 0 && "Already set a value for this node!"); 381 N = NewN; 382 } 383 384 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 385 std::set<unsigned> &OutputRegs, 386 std::set<unsigned> &InputRegs); 387 388 void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, 389 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 390 MachineBasicBlock *SwitchBB, unsigned Opc); 391 void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, 392 MachineBasicBlock *FBB, 393 MachineBasicBlock *CurBB, 394 MachineBasicBlock *SwitchBB); 395 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 396 bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); 397 void CopyToExportRegsIfNeeded(const Value *V); 398 void ExportFromCurrentBlock(const Value *V); 399 void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall, 400 MachineBasicBlock *LandingPad = NULL); 401 402 /// UpdateSplitBlock - When an MBB was split during scheduling, update the 403 /// references that ned to refer to the last resulting block. 404 void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last); 405 406private: 407 // Terminator instructions. 408 void visitRet(const ReturnInst &I); 409 void visitBr(const BranchInst &I); 410 void visitSwitch(const SwitchInst &I); 411 void visitIndirectBr(const IndirectBrInst &I); 412 void visitUnreachable(const UnreachableInst &I) { /* noop */ } 413 414 // Helpers for visitSwitch 415 bool handleSmallSwitchRange(CaseRec& CR, 416 CaseRecVector& WorkList, 417 const Value* SV, 418 MachineBasicBlock* Default, 419 MachineBasicBlock *SwitchBB); 420 bool handleJTSwitchCase(CaseRec& CR, 421 CaseRecVector& WorkList, 422 const Value* SV, 423 MachineBasicBlock* Default, 424 MachineBasicBlock *SwitchBB); 425 bool handleBTSplitSwitchCase(CaseRec& CR, 426 CaseRecVector& WorkList, 427 const Value* SV, 428 MachineBasicBlock* Default, 429 MachineBasicBlock *SwitchBB); 430 bool handleBitTestsSwitchCase(CaseRec& CR, 431 CaseRecVector& WorkList, 432 const Value* SV, 433 MachineBasicBlock* Default, 434 MachineBasicBlock *SwitchBB); 435public: 436 void visitSwitchCase(CaseBlock &CB, 437 MachineBasicBlock *SwitchBB); 438 void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); 439 void visitBitTestCase(BitTestBlock &BB, 440 MachineBasicBlock* NextMBB, 441 unsigned Reg, 442 BitTestCase &B, 443 MachineBasicBlock *SwitchBB); 444 void visitJumpTable(JumpTable &JT); 445 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, 446 MachineBasicBlock *SwitchBB); 447 448private: 449 // These all get lowered before this pass. 450 void visitInvoke(const InvokeInst &I); 451 void visitUnwind(const UnwindInst &I); 452 453 void visitBinary(const User &I, unsigned OpCode); 454 void visitShift(const User &I, unsigned Opcode); 455 void visitAdd(const User &I) { visitBinary(I, ISD::ADD); } 456 void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); } 457 void visitSub(const User &I) { visitBinary(I, ISD::SUB); } 458 void visitFSub(const User &I); 459 void visitMul(const User &I) { visitBinary(I, ISD::MUL); } 460 void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); } 461 void visitURem(const User &I) { visitBinary(I, ISD::UREM); } 462 void visitSRem(const User &I) { visitBinary(I, ISD::SREM); } 463 void visitFRem(const User &I) { visitBinary(I, ISD::FREM); } 464 void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); } 465 void visitSDiv(const User &I) { visitBinary(I, ISD::SDIV); } 466 void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); } 467 void visitAnd (const User &I) { visitBinary(I, ISD::AND); } 468 void visitOr (const User &I) { visitBinary(I, ISD::OR); } 469 void visitXor (const User &I) { visitBinary(I, ISD::XOR); } 470 void visitShl (const User &I) { visitShift(I, ISD::SHL); } 471 void visitLShr(const User &I) { visitShift(I, ISD::SRL); } 472 void visitAShr(const User &I) { visitShift(I, ISD::SRA); } 473 void visitICmp(const User &I); 474 void visitFCmp(const User &I); 475 // Visit the conversion instructions 476 void visitTrunc(const User &I); 477 void visitZExt(const User &I); 478 void visitSExt(const User &I); 479 void visitFPTrunc(const User &I); 480 void visitFPExt(const User &I); 481 void visitFPToUI(const User &I); 482 void visitFPToSI(const User &I); 483 void visitUIToFP(const User &I); 484 void visitSIToFP(const User &I); 485 void visitPtrToInt(const User &I); 486 void visitIntToPtr(const User &I); 487 void visitBitCast(const User &I); 488 489 void visitExtractElement(const User &I); 490 void visitInsertElement(const User &I); 491 void visitShuffleVector(const User &I); 492 493 void visitExtractValue(const ExtractValueInst &I); 494 void visitInsertValue(const InsertValueInst &I); 495 496 void visitGetElementPtr(const User &I); 497 void visitSelect(const User &I); 498 499 void visitAlloca(const AllocaInst &I); 500 void visitLoad(const LoadInst &I); 501 void visitStore(const StoreInst &I); 502 void visitPHI(const PHINode &I); 503 void visitCall(const CallInst &I); 504 bool visitMemCmpCall(const CallInst &I); 505 506 void visitInlineAsm(ImmutableCallSite CS); 507 const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic); 508 void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic); 509 510 void visitPow(const CallInst &I); 511 void visitExp2(const CallInst &I); 512 void visitExp(const CallInst &I); 513 void visitLog(const CallInst &I); 514 void visitLog2(const CallInst &I); 515 void visitLog10(const CallInst &I); 516 517 void visitVAStart(const CallInst &I); 518 void visitVAArg(const VAArgInst &I); 519 void visitVAEnd(const CallInst &I); 520 void visitVACopy(const CallInst &I); 521 522 void visitUserOp1(const Instruction &I) { 523 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 524 } 525 void visitUserOp2(const Instruction &I) { 526 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 527 } 528 529 const char *implVisitBinaryAtomic(const CallInst& I, ISD::NodeType Op); 530 const char *implVisitAluOverflow(const CallInst &I, ISD::NodeType Op); 531 532 void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 533 534 /// EmitFuncArgumentDbgValue - If V is an function argument then create 535 /// corresponding DBG_VALUE machine instruction for it now. At the end of 536 /// instruction selection, they will be inserted to the entry BB. 537 bool EmitFuncArgumentDbgValue(const Value *V, MDNode *Variable, 538 int64_t Offset, const SDValue &N); 539}; 540 541} // end namespace llvm 542 543#endif 544