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