SelectionDAGBuilder.h revision 206274
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/// Also, targets can overload any lowering method. 84/// 85class SelectionDAGBuilder { 86 MachineBasicBlock *CurMBB; 87 88 /// CurDebugLoc - current file + line number. Changes as we build the DAG. 89 DebugLoc CurDebugLoc; 90 91 DenseMap<const Value*, SDValue> NodeMap; 92 93public: 94 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 95 /// them up and then emit token factor nodes when possible. This allows us to 96 /// get simple disambiguation between loads without worrying about alias 97 /// analysis. 98 SmallVector<SDValue, 8> PendingLoads; 99private: 100 101 /// PendingExports - CopyToReg nodes that copy values to virtual registers 102 /// for export to other blocks need to be emitted before any terminator 103 /// instruction, but they have no other ordering requirements. We bunch them 104 /// up and the emit a single tokenfactor for them just before terminator 105 /// instructions. 106 SmallVector<SDValue, 8> PendingExports; 107 108 /// SDNodeOrder - A unique monotonically increasing number used to order the 109 /// SDNodes we create. 110 unsigned SDNodeOrder; 111 112 /// Case - A struct to record the Value for a switch case, and the 113 /// case's target basic block. 114 struct Case { 115 Constant* Low; 116 Constant* High; 117 MachineBasicBlock* BB; 118 119 Case() : Low(0), High(0), BB(0) { } 120 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 121 Low(low), High(high), BB(bb) { } 122 APInt size() const { 123 const APInt &rHigh = cast<ConstantInt>(High)->getValue(); 124 const APInt &rLow = cast<ConstantInt>(Low)->getValue(); 125 return (rHigh - rLow + 1ULL); 126 } 127 }; 128 129 struct CaseBits { 130 uint64_t Mask; 131 MachineBasicBlock* BB; 132 unsigned Bits; 133 134 CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits): 135 Mask(mask), BB(bb), Bits(bits) { } 136 }; 137 138 typedef std::vector<Case> CaseVector; 139 typedef std::vector<CaseBits> CaseBitsVector; 140 typedef CaseVector::iterator CaseItr; 141 typedef std::pair<CaseItr, CaseItr> CaseRange; 142 143 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 144 /// of conditional branches. 145 struct CaseRec { 146 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, 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 Constant *LT; 154 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, Value *cmplhs, Value *cmprhs, Value *cmpmiddle, 186 MachineBasicBlock *truebb, MachineBasicBlock *falsebb, 187 MachineBasicBlock *me) 188 : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), 189 TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} 190 // CC - the condition code to use for the case block's setcc node 191 ISD::CondCode CC; 192 // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. 193 // Emit by default LHS op RHS. MHS is used for range comparisons: 194 // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). 195 Value *CmpLHS, *CmpMHS, *CmpRHS; 196 // TrueBB/FalseBB - the block to branch to if the setcc is true/false. 197 MachineBasicBlock *TrueBB, *FalseBB; 198 // ThisBB - the block into which to emit the code for the setcc and branches 199 MachineBasicBlock *ThisBB; 200 }; 201 struct JumpTable { 202 JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, 203 MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} 204 205 /// Reg - the virtual register containing the index of the jump table entry 206 //. to jump to. 207 unsigned Reg; 208 /// JTI - the JumpTableIndex for this jump table in the function. 209 unsigned JTI; 210 /// MBB - the MBB into which to emit the code for the indirect jump. 211 MachineBasicBlock *MBB; 212 /// Default - the MBB of the default bb, which is a successor of the range 213 /// check MBB. This is when updating PHI nodes in successors. 214 MachineBasicBlock *Default; 215 }; 216 struct JumpTableHeader { 217 JumpTableHeader(APInt F, APInt L, Value *SV, MachineBasicBlock *H, 218 bool E = false): 219 First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} 220 APInt First; 221 APInt Last; 222 Value *SValue; 223 MachineBasicBlock *HeaderBB; 224 bool Emitted; 225 }; 226 typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock; 227 228 struct BitTestCase { 229 BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr): 230 Mask(M), ThisBB(T), TargetBB(Tr) { } 231 uint64_t Mask; 232 MachineBasicBlock *ThisBB; 233 MachineBasicBlock *TargetBB; 234 }; 235 236 typedef SmallVector<BitTestCase, 3> BitTestInfo; 237 238 struct BitTestBlock { 239 BitTestBlock(APInt F, APInt R, Value* SV, 240 unsigned Rg, bool E, 241 MachineBasicBlock* P, MachineBasicBlock* D, 242 const BitTestInfo& C): 243 First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E), 244 Parent(P), Default(D), Cases(C) { } 245 APInt First; 246 APInt Range; 247 Value *SValue; 248 unsigned Reg; 249 bool Emitted; 250 MachineBasicBlock *Parent; 251 MachineBasicBlock *Default; 252 BitTestInfo Cases; 253 }; 254 255public: 256 // TLI - This is information that describes the available target features we 257 // need for lowering. This indicates when operations are unavailable, 258 // implemented with a libcall, etc. 259 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<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, TargetLowering &tli, 306 FunctionLoweringInfo &funcinfo, 307 CodeGenOpt::Level ol) 308 : SDNodeOrder(0), TLI(tli), 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 curret 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 void setCurDebugLoc(DebugLoc dl) { CurDebugLoc = dl; } 337 338 unsigned getSDNodeOrder() const { return SDNodeOrder; } 339 340 void CopyValueToVirtualRegister(Value *V, unsigned Reg); 341 342 /// AssignOrderingToNode - Assign an ordering to the node. The order is gotten 343 /// from how the code appeared in the source. The ordering is used by the 344 /// scheduler to effectively turn off scheduling. 345 void AssignOrderingToNode(const SDNode *Node); 346 347 void visit(Instruction &I); 348 349 void visit(unsigned Opcode, User &I); 350 351 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 352 353 SDValue getValue(const Value *V); 354 355 void setValue(const Value *V, SDValue NewN) { 356 SDValue &N = NodeMap[V]; 357 assert(N.getNode() == 0 && "Already set a value for this node!"); 358 N = NewN; 359 } 360 361 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 362 std::set<unsigned> &OutputRegs, 363 std::set<unsigned> &InputRegs); 364 365 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 366 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 367 unsigned Opc); 368 void EmitBranchForMergedCondition(Value *Cond, MachineBasicBlock *TBB, 369 MachineBasicBlock *FBB, 370 MachineBasicBlock *CurBB); 371 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 372 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 373 void CopyToExportRegsIfNeeded(Value *V); 374 void ExportFromCurrentBlock(Value *V); 375 void LowerCallTo(CallSite CS, SDValue Callee, bool IsTailCall, 376 MachineBasicBlock *LandingPad = NULL); 377 378private: 379 // Terminator instructions. 380 void visitRet(ReturnInst &I); 381 void visitBr(BranchInst &I); 382 void visitSwitch(SwitchInst &I); 383 void visitIndirectBr(IndirectBrInst &I); 384 void visitUnreachable(UnreachableInst &I) { /* noop */ } 385 386 // Helpers for visitSwitch 387 bool handleSmallSwitchRange(CaseRec& CR, 388 CaseRecVector& WorkList, 389 Value* SV, 390 MachineBasicBlock* Default); 391 bool handleJTSwitchCase(CaseRec& CR, 392 CaseRecVector& WorkList, 393 Value* SV, 394 MachineBasicBlock* Default); 395 bool handleBTSplitSwitchCase(CaseRec& CR, 396 CaseRecVector& WorkList, 397 Value* SV, 398 MachineBasicBlock* Default); 399 bool handleBitTestsSwitchCase(CaseRec& CR, 400 CaseRecVector& WorkList, 401 Value* SV, 402 MachineBasicBlock* Default); 403public: 404 void visitSwitchCase(CaseBlock &CB); 405 void visitBitTestHeader(BitTestBlock &B); 406 void visitBitTestCase(MachineBasicBlock* NextMBB, 407 unsigned Reg, 408 BitTestCase &B); 409 void visitJumpTable(JumpTable &JT); 410 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH); 411 412private: 413 // These all get lowered before this pass. 414 void visitInvoke(InvokeInst &I); 415 void visitUnwind(UnwindInst &I); 416 417 void visitBinary(User &I, unsigned OpCode); 418 void visitShift(User &I, unsigned Opcode); 419 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 420 void visitFAdd(User &I) { visitBinary(I, ISD::FADD); } 421 void visitSub(User &I) { visitBinary(I, ISD::SUB); } 422 void visitFSub(User &I); 423 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 424 void visitFMul(User &I) { visitBinary(I, ISD::FMUL); } 425 void visitURem(User &I) { visitBinary(I, ISD::UREM); } 426 void visitSRem(User &I) { visitBinary(I, ISD::SREM); } 427 void visitFRem(User &I) { visitBinary(I, ISD::FREM); } 428 void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); } 429 void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); } 430 void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); } 431 void visitAnd (User &I) { visitBinary(I, ISD::AND); } 432 void visitOr (User &I) { visitBinary(I, ISD::OR); } 433 void visitXor (User &I) { visitBinary(I, ISD::XOR); } 434 void visitShl (User &I) { visitShift(I, ISD::SHL); } 435 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 436 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 437 void visitICmp(User &I); 438 void visitFCmp(User &I); 439 // Visit the conversion instructions 440 void visitTrunc(User &I); 441 void visitZExt(User &I); 442 void visitSExt(User &I); 443 void visitFPTrunc(User &I); 444 void visitFPExt(User &I); 445 void visitFPToUI(User &I); 446 void visitFPToSI(User &I); 447 void visitUIToFP(User &I); 448 void visitSIToFP(User &I); 449 void visitPtrToInt(User &I); 450 void visitIntToPtr(User &I); 451 void visitBitCast(User &I); 452 453 void visitExtractElement(User &I); 454 void visitInsertElement(User &I); 455 void visitShuffleVector(User &I); 456 457 void visitExtractValue(ExtractValueInst &I); 458 void visitInsertValue(InsertValueInst &I); 459 460 void visitGetElementPtr(User &I); 461 void visitSelect(User &I); 462 463 void visitAlloca(AllocaInst &I); 464 void visitLoad(LoadInst &I); 465 void visitStore(StoreInst &I); 466 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 467 void visitCall(CallInst &I); 468 bool visitMemCmpCall(CallInst &I); 469 470 void visitInlineAsm(CallSite CS); 471 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 472 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 473 474 void visitPow(CallInst &I); 475 void visitExp2(CallInst &I); 476 void visitExp(CallInst &I); 477 void visitLog(CallInst &I); 478 void visitLog2(CallInst &I); 479 void visitLog10(CallInst &I); 480 481 void visitVAStart(CallInst &I); 482 void visitVAArg(VAArgInst &I); 483 void visitVAEnd(CallInst &I); 484 void visitVACopy(CallInst &I); 485 486 void visitUserOp1(Instruction &I) { 487 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 488 } 489 void visitUserOp2(Instruction &I) { 490 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 491 } 492 493 const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op); 494 const char *implVisitAluOverflow(CallInst &I, ISD::NodeType Op); 495}; 496 497} // end namespace llvm 498 499#endif 500