SelectionDAGBuilder.h revision 40ba3d21580f18bc87f9a784b84b88fc21964b10
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 MachineBasicBlock *CurMBB; 86 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, Constant *lt, Constant *ge, CaseRange r) : 146 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 147 148 /// CaseBB - The MBB in which to emit the compare and branch 149 MachineBasicBlock *CaseBB; 150 /// LT, GE - If nonzero, we know the current case value must be less-than or 151 /// greater-than-or-equal-to these Constants. 152 Constant *LT; 153 Constant *GE; 154 /// Range - A pair of iterators representing the range of case values to be 155 /// processed at this point in the binary search tree. 156 CaseRange Range; 157 }; 158 159 typedef std::vector<CaseRec> CaseRecVector; 160 161 /// The comparison function for sorting the switch case values in the vector. 162 /// WARNING: Case ranges should be disjoint! 163 struct CaseCmp { 164 bool operator()(const Case &C1, const Case &C2) { 165 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 166 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 167 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 168 return CI1->getValue().slt(CI2->getValue()); 169 } 170 }; 171 172 struct CaseBitsCmp { 173 bool operator()(const CaseBits &C1, const CaseBits &C2) { 174 return C1.Bits > C2.Bits; 175 } 176 }; 177 178 size_t Clusterify(CaseVector &Cases, const SwitchInst &SI); 179 180 /// CaseBlock - This structure is used to communicate between 181 /// SelectionDAGBuilder and SDISel for the code generation of additional basic 182 /// blocks needed by multi-case switch statements. 183 struct CaseBlock { 184 CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, 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 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, 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 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, 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 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 TargetLowering &TLI; 259 SelectionDAG &DAG; 260 const TargetData *TD; 261 AliasAnalysis *AA; 262 263 /// SwitchCases - Vector of CaseBlock structures used to communicate 264 /// SwitchInst code generation information. 265 std::vector<CaseBlock> SwitchCases; 266 /// JTCases - Vector of JumpTable structures used to communicate 267 /// SwitchInst code generation information. 268 std::vector<JumpTableBlock> JTCases; 269 /// BitTestCases - Vector of BitTestBlock structures used to communicate 270 /// SwitchInst code generation information. 271 std::vector<BitTestBlock> BitTestCases; 272 273 /// PHINodesToUpdate - A list of phi instructions whose operand list will 274 /// be updated after processing the current basic block. 275 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 276 277 /// EdgeMapping - If an edge from CurMBB to any MBB is changed (e.g. due to 278 /// scheduler custom lowering), track the change here. 279 DenseMap<MachineBasicBlock*, MachineBasicBlock*> EdgeMapping; 280 281 // Emit PHI-node-operand constants only once even if used by multiple 282 // PHI nodes. 283 DenseMap<Constant*, unsigned> ConstantsOut; 284 285 /// FuncInfo - Information about the function as a whole. 286 /// 287 FunctionLoweringInfo &FuncInfo; 288 289 /// OptLevel - What optimization level we're generating code for. 290 /// 291 CodeGenOpt::Level OptLevel; 292 293 /// GFI - Garbage collection metadata for the function. 294 GCFunctionInfo *GFI; 295 296 /// HasTailCall - This is set to true if a call in the current 297 /// block has been translated as a tail call. In this case, 298 /// no subsequent DAG nodes should be created. 299 /// 300 bool HasTailCall; 301 302 LLVMContext *Context; 303 304 SelectionDAGBuilder(SelectionDAG &dag, TargetLowering &tli, 305 FunctionLoweringInfo &funcinfo, 306 CodeGenOpt::Level ol) 307 : SDNodeOrder(0), TLI(tli), DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 308 HasTailCall(false), Context(dag.getContext()) { 309 } 310 311 void init(GCFunctionInfo *gfi, AliasAnalysis &aa); 312 313 /// clear - Clear out the curret SelectionDAG and the associated 314 /// state and prepare this SelectionDAGBuilder object to be used 315 /// for a new block. This doesn't clear out information about 316 /// additional blocks that are needed to complete switch lowering 317 /// or PHI node updating; that information is cleared out as it is 318 /// consumed. 319 void clear(); 320 321 /// getRoot - Return the current virtual root of the Selection DAG, 322 /// flushing any PendingLoad items. This must be done before emitting 323 /// a store or any other node that may need to be ordered after any 324 /// prior load instructions. 325 /// 326 SDValue getRoot(); 327 328 /// getControlRoot - Similar to getRoot, but instead of flushing all the 329 /// PendingLoad items, flush all the PendingExports items. It is necessary 330 /// to do this before emitting a terminator instruction. 331 /// 332 SDValue getControlRoot(); 333 334 DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 335 void setCurDebugLoc(DebugLoc dl) { CurDebugLoc = dl; } 336 337 unsigned getSDNodeOrder() const { return SDNodeOrder; } 338 339 void CopyValueToVirtualRegister(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(Instruction &I); 347 348 void visit(unsigned Opcode, User &I); 349 350 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 351 352 SDValue getValue(const Value *V); 353 354 void setValue(const Value *V, SDValue NewN) { 355 SDValue &N = NodeMap[V]; 356 assert(N.getNode() == 0 && "Already set a value for this node!"); 357 N = NewN; 358 } 359 360 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 361 std::set<unsigned> &OutputRegs, 362 std::set<unsigned> &InputRegs); 363 364 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 365 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 366 unsigned Opc); 367 void EmitBranchForMergedCondition(Value *Cond, MachineBasicBlock *TBB, 368 MachineBasicBlock *FBB, 369 MachineBasicBlock *CurBB); 370 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 371 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 372 void CopyToExportRegsIfNeeded(Value *V); 373 void ExportFromCurrentBlock(Value *V); 374 void LowerCallTo(CallSite CS, SDValue Callee, bool IsTailCall, 375 MachineBasicBlock *LandingPad = NULL); 376 377private: 378 // Terminator instructions. 379 void visitRet(ReturnInst &I); 380 void visitBr(BranchInst &I); 381 void visitSwitch(SwitchInst &I); 382 void visitIndirectBr(IndirectBrInst &I); 383 void visitUnreachable(UnreachableInst &I) { /* noop */ } 384 385 // Helpers for visitSwitch 386 bool handleSmallSwitchRange(CaseRec& CR, 387 CaseRecVector& WorkList, 388 Value* SV, 389 MachineBasicBlock* Default); 390 bool handleJTSwitchCase(CaseRec& CR, 391 CaseRecVector& WorkList, 392 Value* SV, 393 MachineBasicBlock* Default); 394 bool handleBTSplitSwitchCase(CaseRec& CR, 395 CaseRecVector& WorkList, 396 Value* SV, 397 MachineBasicBlock* Default); 398 bool handleBitTestsSwitchCase(CaseRec& CR, 399 CaseRecVector& WorkList, 400 Value* SV, 401 MachineBasicBlock* Default); 402public: 403 void visitSwitchCase(CaseBlock &CB); 404 void visitBitTestHeader(BitTestBlock &B); 405 void visitBitTestCase(MachineBasicBlock* NextMBB, 406 unsigned Reg, 407 BitTestCase &B); 408 void visitJumpTable(JumpTable &JT); 409 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH); 410 411private: 412 // These all get lowered before this pass. 413 void visitInvoke(InvokeInst &I); 414 void visitUnwind(UnwindInst &I); 415 416 void visitBinary(User &I, unsigned OpCode); 417 void visitShift(User &I, unsigned Opcode); 418 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 419 void visitFAdd(User &I) { visitBinary(I, ISD::FADD); } 420 void visitSub(User &I) { visitBinary(I, ISD::SUB); } 421 void visitFSub(User &I); 422 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 423 void visitFMul(User &I) { visitBinary(I, ISD::FMUL); } 424 void visitURem(User &I) { visitBinary(I, ISD::UREM); } 425 void visitSRem(User &I) { visitBinary(I, ISD::SREM); } 426 void visitFRem(User &I) { visitBinary(I, ISD::FREM); } 427 void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); } 428 void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); } 429 void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); } 430 void visitAnd (User &I) { visitBinary(I, ISD::AND); } 431 void visitOr (User &I) { visitBinary(I, ISD::OR); } 432 void visitXor (User &I) { visitBinary(I, ISD::XOR); } 433 void visitShl (User &I) { visitShift(I, ISD::SHL); } 434 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 435 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 436 void visitICmp(User &I); 437 void visitFCmp(User &I); 438 // Visit the conversion instructions 439 void visitTrunc(User &I); 440 void visitZExt(User &I); 441 void visitSExt(User &I); 442 void visitFPTrunc(User &I); 443 void visitFPExt(User &I); 444 void visitFPToUI(User &I); 445 void visitFPToSI(User &I); 446 void visitUIToFP(User &I); 447 void visitSIToFP(User &I); 448 void visitPtrToInt(User &I); 449 void visitIntToPtr(User &I); 450 void visitBitCast(User &I); 451 452 void visitExtractElement(User &I); 453 void visitInsertElement(User &I); 454 void visitShuffleVector(User &I); 455 456 void visitExtractValue(ExtractValueInst &I); 457 void visitInsertValue(InsertValueInst &I); 458 459 void visitGetElementPtr(User &I); 460 void visitSelect(User &I); 461 462 void visitAlloca(AllocaInst &I); 463 void visitLoad(LoadInst &I); 464 void visitStore(StoreInst &I); 465 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 466 void visitCall(CallInst &I); 467 bool visitMemCmpCall(CallInst &I); 468 469 void visitInlineAsm(CallSite CS); 470 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 471 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 472 473 void visitPow(CallInst &I); 474 void visitExp2(CallInst &I); 475 void visitExp(CallInst &I); 476 void visitLog(CallInst &I); 477 void visitLog2(CallInst &I); 478 void visitLog10(CallInst &I); 479 480 void visitVAStart(CallInst &I); 481 void visitVAArg(VAArgInst &I); 482 void visitVAEnd(CallInst &I); 483 void visitVACopy(CallInst &I); 484 485 void visitUserOp1(Instruction &I) { 486 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 487 } 488 void visitUserOp2(Instruction &I) { 489 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 490 } 491 492 const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op); 493 const char *implVisitAluOverflow(CallInst &I, ISD::NodeType Op); 494}; 495 496} // end namespace llvm 497 498#endif 499