SelectionDAGBuilder.h revision c57dcd5e708420c240dbd5423443c7fb8a59ccbd
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 MachineFunction; 60class MachineInstr; 61class MachineRegisterInfo; 62class PHINode; 63class PtrToIntInst; 64class ReturnInst; 65class SDISelAsmOperandInfo; 66class SExtInst; 67class SelectInst; 68class ShuffleVectorInst; 69class SIToFPInst; 70class StoreInst; 71class SwitchInst; 72class TargetData; 73class TargetLowering; 74class TruncInst; 75class UIToFPInst; 76class UnreachableInst; 77class UnwindInst; 78class VAArgInst; 79class ZExtInst; 80 81//===----------------------------------------------------------------------===// 82/// SelectionDAGBuilder - This is the common target-independent lowering 83/// implementation that is parameterized by a TargetLowering object. 84/// Also, targets can overload any lowering method. 85/// 86class SelectionDAGBuilder { 87 MachineBasicBlock *CurMBB; 88 89 /// CurDebugLoc - current file + line number. Changes as we build the DAG. 90 DebugLoc CurDebugLoc; 91 92 DenseMap<const Value*, SDValue> NodeMap; 93 94public: 95 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 96 /// them up and then emit token factor nodes when possible. This allows us to 97 /// get simple disambiguation between loads without worrying about alias 98 /// analysis. 99 SmallVector<SDValue, 8> PendingLoads; 100private: 101 102 /// PendingExports - CopyToReg nodes that copy values to virtual registers 103 /// for export to other blocks need to be emitted before any terminator 104 /// instruction, but they have no other ordering requirements. We bunch them 105 /// up and the emit a single tokenfactor for them just before terminator 106 /// instructions. 107 SmallVector<SDValue, 8> PendingExports; 108 109 /// SDNodeOrder - A unique monotonically increasing number used to order the 110 /// SDNodes we create. 111 unsigned SDNodeOrder; 112 113 /// Case - A struct to record the Value for a switch case, and the 114 /// case's target basic block. 115 struct Case { 116 Constant* Low; 117 Constant* High; 118 MachineBasicBlock* BB; 119 120 Case() : Low(0), High(0), BB(0) { } 121 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 122 Low(low), High(high), BB(bb) { } 123 APInt size() const { 124 const APInt &rHigh = cast<ConstantInt>(High)->getValue(); 125 const APInt &rLow = cast<ConstantInt>(Low)->getValue(); 126 return (rHigh - rLow + 1ULL); 127 } 128 }; 129 130 struct CaseBits { 131 uint64_t Mask; 132 MachineBasicBlock* BB; 133 unsigned Bits; 134 135 CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits): 136 Mask(mask), BB(bb), Bits(bits) { } 137 }; 138 139 typedef std::vector<Case> CaseVector; 140 typedef std::vector<CaseBits> CaseBitsVector; 141 typedef CaseVector::iterator CaseItr; 142 typedef std::pair<CaseItr, CaseItr> CaseRange; 143 144 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 145 /// of conditional branches. 146 struct CaseRec { 147 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 148 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 149 150 /// CaseBB - The MBB in which to emit the compare and branch 151 MachineBasicBlock *CaseBB; 152 /// LT, GE - If nonzero, we know the current case value must be less-than or 153 /// greater-than-or-equal-to these Constants. 154 Constant *LT; 155 Constant *GE; 156 /// Range - A pair of iterators representing the range of case values to be 157 /// processed at this point in the binary search tree. 158 CaseRange Range; 159 }; 160 161 typedef std::vector<CaseRec> CaseRecVector; 162 163 /// The comparison function for sorting the switch case values in the vector. 164 /// WARNING: Case ranges should be disjoint! 165 struct CaseCmp { 166 bool operator()(const Case &C1, const Case &C2) { 167 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 168 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 169 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 170 return CI1->getValue().slt(CI2->getValue()); 171 } 172 }; 173 174 struct CaseBitsCmp { 175 bool operator()(const CaseBits &C1, const CaseBits &C2) { 176 return C1.Bits > C2.Bits; 177 } 178 }; 179 180 size_t Clusterify(CaseVector &Cases, const SwitchInst &SI); 181 182 /// CaseBlock - This structure is used to communicate between 183 /// SelectionDAGBuilder and SDISel for the code generation of additional basic 184 /// blocks needed by multi-case switch statements. 185 struct CaseBlock { 186 CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, 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 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, 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 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, 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 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 TargetLowering &TLI; 261 SelectionDAG &DAG; 262 const TargetData *TD; 263 AliasAnalysis *AA; 264 265 /// SwitchCases - Vector of CaseBlock structures used to communicate 266 /// SwitchInst code generation information. 267 std::vector<CaseBlock> SwitchCases; 268 /// JTCases - Vector of JumpTable structures used to communicate 269 /// SwitchInst code generation information. 270 std::vector<JumpTableBlock> JTCases; 271 /// BitTestCases - Vector of BitTestBlock structures used to communicate 272 /// SwitchInst code generation information. 273 std::vector<BitTestBlock> BitTestCases; 274 275 /// PHINodesToUpdate - A list of phi instructions whose operand list will 276 /// be updated after processing the current basic block. 277 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 278 279 /// EdgeMapping - If an edge from CurMBB to any MBB is changed (e.g. due to 280 /// scheduler custom lowering), track the change here. 281 DenseMap<MachineBasicBlock*, MachineBasicBlock*> EdgeMapping; 282 283 // Emit PHI-node-operand constants only once even if used by multiple 284 // PHI nodes. 285 DenseMap<Constant*, unsigned> ConstantsOut; 286 287 /// FuncInfo - Information about the function as a whole. 288 /// 289 FunctionLoweringInfo &FuncInfo; 290 291 /// OptLevel - What optimization level we're generating code for. 292 /// 293 CodeGenOpt::Level OptLevel; 294 295 /// GFI - Garbage collection metadata for the function. 296 GCFunctionInfo *GFI; 297 298 /// HasTailCall - This is set to true if a call in the current 299 /// block has been translated as a tail call. In this case, 300 /// no subsequent DAG nodes should be created. 301 /// 302 bool HasTailCall; 303 304 LLVMContext *Context; 305 306 SelectionDAGBuilder(SelectionDAG &dag, TargetLowering &tli, 307 FunctionLoweringInfo &funcinfo, 308 CodeGenOpt::Level ol) 309 : CurDebugLoc(DebugLoc::getUnknownLoc()), SDNodeOrder(0), 310 TLI(tli), DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 311 HasTailCall(false), 312 Context(dag.getContext()) { 313 } 314 315 void init(GCFunctionInfo *gfi, AliasAnalysis &aa); 316 317 /// clear - Clear out the curret SelectionDAG and the associated 318 /// state and prepare this SelectionDAGBuilder object to be used 319 /// for a new block. This doesn't clear out information about 320 /// additional blocks that are needed to complete switch lowering 321 /// or PHI node updating; that information is cleared out as it is 322 /// consumed. 323 void clear(); 324 325 /// getRoot - Return the current virtual root of the Selection DAG, 326 /// flushing any PendingLoad items. This must be done before emitting 327 /// a store or any other node that may need to be ordered after any 328 /// prior load instructions. 329 /// 330 SDValue getRoot(); 331 332 /// getControlRoot - Similar to getRoot, but instead of flushing all the 333 /// PendingLoad items, flush all the PendingExports items. It is necessary 334 /// to do this before emitting a terminator instruction. 335 /// 336 SDValue getControlRoot(); 337 338 DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 339 void setCurDebugLoc(DebugLoc dl) { CurDebugLoc = dl; } 340 341 unsigned getSDNodeOrder() const { return SDNodeOrder; } 342 343 void CopyValueToVirtualRegister(Value *V, unsigned Reg); 344 345 void visit(Instruction &I); 346 347 void visit(unsigned Opcode, User &I); 348 349 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 350 351 SDValue getValue(const Value *V); 352 353 void setValue(const Value *V, SDValue NewN) { 354 SDValue &N = NodeMap[V]; 355 assert(N.getNode() == 0 && "Already set a value for this node!"); 356 N = NewN; 357 } 358 359 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 360 std::set<unsigned> &OutputRegs, 361 std::set<unsigned> &InputRegs); 362 363 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 364 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 365 unsigned Opc); 366 void EmitBranchForMergedCondition(Value *Cond, MachineBasicBlock *TBB, 367 MachineBasicBlock *FBB, 368 MachineBasicBlock *CurBB); 369 bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 370 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 371 void CopyToExportRegsIfNeeded(Value *V); 372 void ExportFromCurrentBlock(Value *V); 373 void LowerCallTo(CallSite CS, SDValue Callee, bool IsTailCall, 374 MachineBasicBlock *LandingPad = NULL); 375 376private: 377 // Terminator instructions. 378 void visitRet(ReturnInst &I); 379 void visitBr(BranchInst &I); 380 void visitSwitch(SwitchInst &I); 381 void visitIndirectBr(IndirectBrInst &I); 382 void visitUnreachable(UnreachableInst &I) { /* noop */ } 383 384 // Helpers for visitSwitch 385 bool handleSmallSwitchRange(CaseRec& CR, 386 CaseRecVector& WorkList, 387 Value* SV, 388 MachineBasicBlock* Default); 389 bool handleJTSwitchCase(CaseRec& CR, 390 CaseRecVector& WorkList, 391 Value* SV, 392 MachineBasicBlock* Default); 393 bool handleBTSplitSwitchCase(CaseRec& CR, 394 CaseRecVector& WorkList, 395 Value* SV, 396 MachineBasicBlock* Default); 397 bool handleBitTestsSwitchCase(CaseRec& CR, 398 CaseRecVector& WorkList, 399 Value* SV, 400 MachineBasicBlock* Default); 401public: 402 void visitSwitchCase(CaseBlock &CB); 403 void visitBitTestHeader(BitTestBlock &B); 404 void visitBitTestCase(MachineBasicBlock* NextMBB, 405 unsigned Reg, 406 BitTestCase &B); 407 void visitJumpTable(JumpTable &JT); 408 void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH); 409 410private: 411 // These all get lowered before this pass. 412 void visitInvoke(InvokeInst &I); 413 void visitUnwind(UnwindInst &I); 414 415 void visitBinary(User &I, unsigned OpCode); 416 void visitShift(User &I, unsigned Opcode); 417 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 418 void visitFAdd(User &I) { visitBinary(I, ISD::FADD); } 419 void visitSub(User &I) { visitBinary(I, ISD::SUB); } 420 void visitFSub(User &I); 421 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 422 void visitFMul(User &I) { visitBinary(I, ISD::FMUL); } 423 void visitURem(User &I) { visitBinary(I, ISD::UREM); } 424 void visitSRem(User &I) { visitBinary(I, ISD::SREM); } 425 void visitFRem(User &I) { visitBinary(I, ISD::FREM); } 426 void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); } 427 void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); } 428 void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); } 429 void visitAnd (User &I) { visitBinary(I, ISD::AND); } 430 void visitOr (User &I) { visitBinary(I, ISD::OR); } 431 void visitXor (User &I) { visitBinary(I, ISD::XOR); } 432 void visitShl (User &I) { visitShift(I, ISD::SHL); } 433 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 434 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 435 void visitICmp(User &I); 436 void visitFCmp(User &I); 437 // Visit the conversion instructions 438 void visitTrunc(User &I); 439 void visitZExt(User &I); 440 void visitSExt(User &I); 441 void visitFPTrunc(User &I); 442 void visitFPExt(User &I); 443 void visitFPToUI(User &I); 444 void visitFPToSI(User &I); 445 void visitUIToFP(User &I); 446 void visitSIToFP(User &I); 447 void visitPtrToInt(User &I); 448 void visitIntToPtr(User &I); 449 void visitBitCast(User &I); 450 451 void visitExtractElement(User &I); 452 void visitInsertElement(User &I); 453 void visitShuffleVector(User &I); 454 455 void visitExtractValue(ExtractValueInst &I); 456 void visitInsertValue(InsertValueInst &I); 457 458 void visitGetElementPtr(User &I); 459 void visitSelect(User &I); 460 461 void visitAlloca(AllocaInst &I); 462 void visitLoad(LoadInst &I); 463 void visitStore(StoreInst &I); 464 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 465 void visitCall(CallInst &I); 466 bool visitMemCmpCall(CallInst &I); 467 468 void visitInlineAsm(CallSite CS); 469 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 470 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 471 472 void visitPow(CallInst &I); 473 void visitExp2(CallInst &I); 474 void visitExp(CallInst &I); 475 void visitLog(CallInst &I); 476 void visitLog2(CallInst &I); 477 void visitLog10(CallInst &I); 478 479 void visitVAStart(CallInst &I); 480 void visitVAArg(VAArgInst &I); 481 void visitVAEnd(CallInst &I); 482 void visitVACopy(CallInst &I); 483 484 void visitUserOp1(Instruction &I) { 485 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 486 } 487 void visitUserOp2(Instruction &I) { 488 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 489 } 490 491 const char *implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op); 492 const char *implVisitAluOverflow(CallInst &I, ISD::NodeType Op); 493}; 494 495} // end namespace llvm 496 497#endif 498