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