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