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