1263508Sdim//===-- SelectionDAGBuilder.h - Selection-DAG building --------*- C++ -*---===// 2199989Srdivacky// 3199989Srdivacky// The LLVM Compiler Infrastructure 4199989Srdivacky// 5199989Srdivacky// This file is distributed under the University of Illinois Open Source 6199989Srdivacky// License. See LICENSE.TXT for details. 7199989Srdivacky// 8199989Srdivacky//===----------------------------------------------------------------------===// 9199989Srdivacky// 10199989Srdivacky// This implements routines for translating from LLVM IR into SelectionDAG IR. 11199989Srdivacky// 12199989Srdivacky//===----------------------------------------------------------------------===// 13199989Srdivacky 14199989Srdivacky#ifndef SELECTIONDAGBUILDER_H 15199989Srdivacky#define SELECTIONDAGBUILDER_H 16199989Srdivacky 17199989Srdivacky#include "llvm/ADT/APInt.h" 18199989Srdivacky#include "llvm/ADT/DenseMap.h" 19249423Sdim#include "llvm/CodeGen/SelectionDAG.h" 20199989Srdivacky#include "llvm/CodeGen/SelectionDAGNodes.h" 21199989Srdivacky#include "llvm/CodeGen/ValueTypes.h" 22249423Sdim#include "llvm/IR/Constants.h" 23199989Srdivacky#include "llvm/Support/CallSite.h" 24199989Srdivacky#include "llvm/Support/ErrorHandling.h" 25199989Srdivacky#include <vector> 26199989Srdivacky 27199989Srdivackynamespace llvm { 28199989Srdivacky 29263508Sdimclass AddrSpaceCastInst; 30199989Srdivackyclass AliasAnalysis; 31199989Srdivackyclass AllocaInst; 32199989Srdivackyclass BasicBlock; 33199989Srdivackyclass BitCastInst; 34199989Srdivackyclass BranchInst; 35199989Srdivackyclass CallInst; 36207618Srdivackyclass DbgValueInst; 37199989Srdivackyclass ExtractElementInst; 38199989Srdivackyclass ExtractValueInst; 39199989Srdivackyclass FCmpInst; 40199989Srdivackyclass FPExtInst; 41199989Srdivackyclass FPToSIInst; 42199989Srdivackyclass FPToUIInst; 43199989Srdivackyclass FPTruncInst; 44199989Srdivackyclass Function; 45199989Srdivackyclass FunctionLoweringInfo; 46199989Srdivackyclass GetElementPtrInst; 47199989Srdivackyclass GCFunctionInfo; 48199989Srdivackyclass ICmpInst; 49199989Srdivackyclass IntToPtrInst; 50199989Srdivackyclass IndirectBrInst; 51199989Srdivackyclass InvokeInst; 52199989Srdivackyclass InsertElementInst; 53199989Srdivackyclass InsertValueInst; 54199989Srdivackyclass Instruction; 55199989Srdivackyclass LoadInst; 56199989Srdivackyclass MachineBasicBlock; 57199989Srdivackyclass MachineInstr; 58199989Srdivackyclass MachineRegisterInfo; 59207618Srdivackyclass MDNode; 60199989Srdivackyclass PHINode; 61199989Srdivackyclass PtrToIntInst; 62199989Srdivackyclass ReturnInst; 63212904Sdimclass SDDbgValue; 64199989Srdivackyclass SExtInst; 65199989Srdivackyclass SelectInst; 66199989Srdivackyclass ShuffleVectorInst; 67199989Srdivackyclass SIToFPInst; 68199989Srdivackyclass StoreInst; 69199989Srdivackyclass SwitchInst; 70243830Sdimclass DataLayout; 71234353Sdimclass TargetLibraryInfo; 72199989Srdivackyclass TargetLowering; 73199989Srdivackyclass TruncInst; 74199989Srdivackyclass UIToFPInst; 75199989Srdivackyclass UnreachableInst; 76199989Srdivackyclass VAArgInst; 77199989Srdivackyclass ZExtInst; 78199989Srdivacky 79199989Srdivacky//===----------------------------------------------------------------------===// 80199989Srdivacky/// SelectionDAGBuilder - This is the common target-independent lowering 81199989Srdivacky/// implementation that is parameterized by a TargetLowering object. 82199989Srdivacky/// 83199989Srdivackyclass SelectionDAGBuilder { 84263508Sdim /// CurInst - The current instruction being visited 85263508Sdim const Instruction *CurInst; 86199989Srdivacky 87199989Srdivacky DenseMap<const Value*, SDValue> NodeMap; 88263508Sdim 89210299Sed /// UnusedArgNodeMap - Maps argument value for unused arguments. This is used 90210299Sed /// to preserve debug information for incoming arguments. 91210299Sed DenseMap<const Value*, SDValue> UnusedArgNodeMap; 92199989Srdivacky 93212904Sdim /// DanglingDebugInfo - Helper type for DanglingDebugInfoMap. 94212904Sdim class DanglingDebugInfo { 95212904Sdim const DbgValueInst* DI; 96212904Sdim DebugLoc dl; 97212904Sdim unsigned SDNodeOrder; 98212904Sdim public: 99212904Sdim DanglingDebugInfo() : DI(0), dl(DebugLoc()), SDNodeOrder(0) { } 100212904Sdim DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) : 101212904Sdim DI(di), dl(DL), SDNodeOrder(SDNO) { } 102212904Sdim const DbgValueInst* getDI() { return DI; } 103212904Sdim DebugLoc getdl() { return dl; } 104212904Sdim unsigned getSDNodeOrder() { return SDNodeOrder; } 105212904Sdim }; 106212904Sdim 107212904Sdim /// DanglingDebugInfoMap - Keeps track of dbg_values for which we have not 108212904Sdim /// yet seen the referent. We defer handling these until we do see it. 109212904Sdim DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap; 110212904Sdim 111201360Srdivackypublic: 112199989Srdivacky /// PendingLoads - Loads are not emitted to the program immediately. We bunch 113199989Srdivacky /// them up and then emit token factor nodes when possible. This allows us to 114199989Srdivacky /// get simple disambiguation between loads without worrying about alias 115199989Srdivacky /// analysis. 116199989Srdivacky SmallVector<SDValue, 8> PendingLoads; 117201360Srdivackyprivate: 118199989Srdivacky 119199989Srdivacky /// PendingExports - CopyToReg nodes that copy values to virtual registers 120199989Srdivacky /// for export to other blocks need to be emitted before any terminator 121199989Srdivacky /// instruction, but they have no other ordering requirements. We bunch them 122199989Srdivacky /// up and the emit a single tokenfactor for them just before terminator 123199989Srdivacky /// instructions. 124199989Srdivacky SmallVector<SDValue, 8> PendingExports; 125199989Srdivacky 126201360Srdivacky /// SDNodeOrder - A unique monotonically increasing number used to order the 127201360Srdivacky /// SDNodes we create. 128201360Srdivacky unsigned SDNodeOrder; 129201360Srdivacky 130199989Srdivacky /// Case - A struct to record the Value for a switch case, and the 131199989Srdivacky /// case's target basic block. 132199989Srdivacky struct Case { 133234353Sdim const Constant *Low; 134234353Sdim const Constant *High; 135199989Srdivacky MachineBasicBlock* BB; 136226633Sdim uint32_t ExtraWeight; 137199989Srdivacky 138226633Sdim Case() : Low(0), High(0), BB(0), ExtraWeight(0) { } 139234353Sdim Case(const Constant *low, const Constant *high, MachineBasicBlock *bb, 140226633Sdim uint32_t extraweight) : Low(low), High(high), BB(bb), 141226633Sdim ExtraWeight(extraweight) { } 142226633Sdim 143199989Srdivacky APInt size() const { 144199989Srdivacky const APInt &rHigh = cast<ConstantInt>(High)->getValue(); 145199989Srdivacky const APInt &rLow = cast<ConstantInt>(Low)->getValue(); 146199989Srdivacky return (rHigh - rLow + 1ULL); 147199989Srdivacky } 148199989Srdivacky }; 149199989Srdivacky 150199989Srdivacky struct CaseBits { 151199989Srdivacky uint64_t Mask; 152199989Srdivacky MachineBasicBlock* BB; 153199989Srdivacky unsigned Bits; 154243830Sdim uint32_t ExtraWeight; 155199989Srdivacky 156243830Sdim CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits, 157243830Sdim uint32_t Weight): 158243830Sdim Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { } 159199989Srdivacky }; 160199989Srdivacky 161199989Srdivacky typedef std::vector<Case> CaseVector; 162199989Srdivacky typedef std::vector<CaseBits> CaseBitsVector; 163199989Srdivacky typedef CaseVector::iterator CaseItr; 164199989Srdivacky typedef std::pair<CaseItr, CaseItr> CaseRange; 165199989Srdivacky 166199989Srdivacky /// CaseRec - A struct with ctor used in lowering switches to a binary tree 167199989Srdivacky /// of conditional branches. 168199989Srdivacky struct CaseRec { 169207618Srdivacky CaseRec(MachineBasicBlock *bb, const Constant *lt, const Constant *ge, 170207618Srdivacky CaseRange r) : 171199989Srdivacky CaseBB(bb), LT(lt), GE(ge), Range(r) {} 172199989Srdivacky 173199989Srdivacky /// CaseBB - The MBB in which to emit the compare and branch 174199989Srdivacky MachineBasicBlock *CaseBB; 175199989Srdivacky /// LT, GE - If nonzero, we know the current case value must be less-than or 176199989Srdivacky /// greater-than-or-equal-to these Constants. 177207618Srdivacky const Constant *LT; 178207618Srdivacky const Constant *GE; 179199989Srdivacky /// Range - A pair of iterators representing the range of case values to be 180199989Srdivacky /// processed at this point in the binary search tree. 181199989Srdivacky CaseRange Range; 182199989Srdivacky }; 183199989Srdivacky 184199989Srdivacky typedef std::vector<CaseRec> CaseRecVector; 185199989Srdivacky 186263508Sdim /// The comparison function for sorting the switch case values in the vector. 187263508Sdim /// WARNING: Case ranges should be disjoint! 188263508Sdim struct CaseCmp { 189263508Sdim bool operator()(const Case &C1, const Case &C2) { 190263508Sdim assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 191263508Sdim const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 192263508Sdim const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 193263508Sdim return CI1->getValue().slt(CI2->getValue()); 194263508Sdim } 195263508Sdim }; 196263508Sdim 197199989Srdivacky struct CaseBitsCmp { 198202375Srdivacky bool operator()(const CaseBits &C1, const CaseBits &C2) { 199199989Srdivacky return C1.Bits > C2.Bits; 200199989Srdivacky } 201199989Srdivacky }; 202199989Srdivacky 203202375Srdivacky size_t Clusterify(CaseVector &Cases, const SwitchInst &SI); 204199989Srdivacky 205199989Srdivacky /// CaseBlock - This structure is used to communicate between 206199989Srdivacky /// SelectionDAGBuilder and SDISel for the code generation of additional basic 207199989Srdivacky /// blocks needed by multi-case switch statements. 208199989Srdivacky struct CaseBlock { 209207618Srdivacky CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, 210207618Srdivacky const Value *cmpmiddle, 211199989Srdivacky MachineBasicBlock *truebb, MachineBasicBlock *falsebb, 212226633Sdim MachineBasicBlock *me, 213226633Sdim uint32_t trueweight = 0, uint32_t falseweight = 0) 214199989Srdivacky : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), 215226633Sdim TrueBB(truebb), FalseBB(falsebb), ThisBB(me), 216226633Sdim TrueWeight(trueweight), FalseWeight(falseweight) { } 217226633Sdim 218199989Srdivacky // CC - the condition code to use for the case block's setcc node 219199989Srdivacky ISD::CondCode CC; 220226633Sdim 221199989Srdivacky // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. 222199989Srdivacky // Emit by default LHS op RHS. MHS is used for range comparisons: 223199989Srdivacky // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). 224207618Srdivacky const Value *CmpLHS, *CmpMHS, *CmpRHS; 225226633Sdim 226199989Srdivacky // TrueBB/FalseBB - the block to branch to if the setcc is true/false. 227199989Srdivacky MachineBasicBlock *TrueBB, *FalseBB; 228226633Sdim 229199989Srdivacky // ThisBB - the block into which to emit the code for the setcc and branches 230199989Srdivacky MachineBasicBlock *ThisBB; 231226633Sdim 232226633Sdim // TrueWeight/FalseWeight - branch weights. 233226633Sdim uint32_t TrueWeight, FalseWeight; 234199989Srdivacky }; 235226633Sdim 236199989Srdivacky struct JumpTable { 237199989Srdivacky JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, 238199989Srdivacky MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} 239263508Sdim 240199989Srdivacky /// Reg - the virtual register containing the index of the jump table entry 241199989Srdivacky //. to jump to. 242199989Srdivacky unsigned Reg; 243199989Srdivacky /// JTI - the JumpTableIndex for this jump table in the function. 244199989Srdivacky unsigned JTI; 245199989Srdivacky /// MBB - the MBB into which to emit the code for the indirect jump. 246199989Srdivacky MachineBasicBlock *MBB; 247199989Srdivacky /// Default - the MBB of the default bb, which is a successor of the range 248199989Srdivacky /// check MBB. This is when updating PHI nodes in successors. 249199989Srdivacky MachineBasicBlock *Default; 250199989Srdivacky }; 251199989Srdivacky struct JumpTableHeader { 252207618Srdivacky JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, 253199989Srdivacky bool E = false): 254199989Srdivacky First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} 255199989Srdivacky APInt First; 256199989Srdivacky APInt Last; 257207618Srdivacky const Value *SValue; 258199989Srdivacky MachineBasicBlock *HeaderBB; 259199989Srdivacky bool Emitted; 260199989Srdivacky }; 261199989Srdivacky typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock; 262199989Srdivacky 263199989Srdivacky struct BitTestCase { 264243830Sdim BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr, 265243830Sdim uint32_t Weight): 266243830Sdim Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { } 267199989Srdivacky uint64_t Mask; 268202375Srdivacky MachineBasicBlock *ThisBB; 269202375Srdivacky MachineBasicBlock *TargetBB; 270243830Sdim uint32_t ExtraWeight; 271199989Srdivacky }; 272199989Srdivacky 273199989Srdivacky typedef SmallVector<BitTestCase, 3> BitTestInfo; 274199989Srdivacky 275199989Srdivacky struct BitTestBlock { 276207618Srdivacky BitTestBlock(APInt F, APInt R, const Value* SV, 277249423Sdim unsigned Rg, MVT RgVT, bool E, 278199989Srdivacky MachineBasicBlock* P, MachineBasicBlock* D, 279199989Srdivacky const BitTestInfo& C): 280218893Sdim First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), 281199989Srdivacky Parent(P), Default(D), Cases(C) { } 282199989Srdivacky APInt First; 283199989Srdivacky APInt Range; 284207618Srdivacky const Value *SValue; 285199989Srdivacky unsigned Reg; 286249423Sdim MVT RegVT; 287199989Srdivacky bool Emitted; 288199989Srdivacky MachineBasicBlock *Parent; 289199989Srdivacky MachineBasicBlock *Default; 290199989Srdivacky BitTestInfo Cases; 291199989Srdivacky }; 292199989Srdivacky 293263508Sdim /// A class which encapsulates all of the information needed to generate a 294263508Sdim /// stack protector check and signals to isel via its state being initialized 295263508Sdim /// that a stack protector needs to be generated. 296263508Sdim /// 297263508Sdim /// *NOTE* The following is a high level documentation of SelectionDAG Stack 298263508Sdim /// Protector Generation. The reason that it is placed here is for a lack of 299263508Sdim /// other good places to stick it. 300263508Sdim /// 301263508Sdim /// High Level Overview of SelectionDAG Stack Protector Generation: 302263508Sdim /// 303263508Sdim /// Previously, generation of stack protectors was done exclusively in the 304263508Sdim /// pre-SelectionDAG Codegen LLVM IR Pass "Stack Protector". This necessitated 305263508Sdim /// splitting basic blocks at the IR level to create the success/failure basic 306263508Sdim /// blocks in the tail of the basic block in question. As a result of this, 307263508Sdim /// calls that would have qualified for the sibling call optimization were no 308263508Sdim /// longer eligible for optimization since said calls were no longer right in 309263508Sdim /// the "tail position" (i.e. the immediate predecessor of a ReturnInst 310263508Sdim /// instruction). 311263508Sdim /// 312263508Sdim /// Then it was noticed that since the sibling call optimization causes the 313263508Sdim /// callee to reuse the caller's stack, if we could delay the generation of 314263508Sdim /// the stack protector check until later in CodeGen after the sibling call 315263508Sdim /// decision was made, we get both the tail call optimization and the stack 316263508Sdim /// protector check! 317263508Sdim /// 318263508Sdim /// A few goals in solving this problem were: 319263508Sdim /// 320263508Sdim /// 1. Preserve the architecture independence of stack protector generation. 321263508Sdim /// 322263508Sdim /// 2. Preserve the normal IR level stack protector check for platforms like 323263508Sdim /// OpenBSD for which we support platform specific stack protector 324263508Sdim /// generation. 325263508Sdim /// 326263508Sdim /// The main problem that guided the present solution is that one can not 327263508Sdim /// solve this problem in an architecture independent manner at the IR level 328263508Sdim /// only. This is because: 329263508Sdim /// 330263508Sdim /// 1. The decision on whether or not to perform a sibling call on certain 331263508Sdim /// platforms (for instance i386) requires lower level information 332263508Sdim /// related to available registers that can not be known at the IR level. 333263508Sdim /// 334263508Sdim /// 2. Even if the previous point were not true, the decision on whether to 335263508Sdim /// perform a tail call is done in LowerCallTo in SelectionDAG which 336263508Sdim /// occurs after the Stack Protector Pass. As a result, one would need to 337263508Sdim /// put the relevant callinst into the stack protector check success 338263508Sdim /// basic block (where the return inst is placed) and then move it back 339263508Sdim /// later at SelectionDAG/MI time before the stack protector check if the 340263508Sdim /// tail call optimization failed. The MI level option was nixed 341263508Sdim /// immediately since it would require platform specific pattern 342263508Sdim /// matching. The SelectionDAG level option was nixed because 343263508Sdim /// SelectionDAG only processes one IR level basic block at a time 344263508Sdim /// implying one could not create a DAG Combine to move the callinst. 345263508Sdim /// 346263508Sdim /// To get around this problem a few things were realized: 347263508Sdim /// 348263508Sdim /// 1. While one can not handle multiple IR level basic blocks at the 349263508Sdim /// SelectionDAG Level, one can generate multiple machine basic blocks 350263508Sdim /// for one IR level basic block. This is how we handle bit tests and 351263508Sdim /// switches. 352263508Sdim /// 353263508Sdim /// 2. At the MI level, tail calls are represented via a special return 354263508Sdim /// MIInst called "tcreturn". Thus if we know the basic block in which we 355263508Sdim /// wish to insert the stack protector check, we get the correct behavior 356263508Sdim /// by always inserting the stack protector check right before the return 357263508Sdim /// statement. This is a "magical transformation" since no matter where 358263508Sdim /// the stack protector check intrinsic is, we always insert the stack 359263508Sdim /// protector check code at the end of the BB. 360263508Sdim /// 361263508Sdim /// Given the aforementioned constraints, the following solution was devised: 362263508Sdim /// 363263508Sdim /// 1. On platforms that do not support SelectionDAG stack protector check 364263508Sdim /// generation, allow for the normal IR level stack protector check 365263508Sdim /// generation to continue. 366263508Sdim /// 367263508Sdim /// 2. On platforms that do support SelectionDAG stack protector check 368263508Sdim /// generation: 369263508Sdim /// 370263508Sdim /// a. Use the IR level stack protector pass to decide if a stack 371263508Sdim /// protector is required/which BB we insert the stack protector check 372263508Sdim /// in by reusing the logic already therein. If we wish to generate a 373263508Sdim /// stack protector check in a basic block, we place a special IR 374263508Sdim /// intrinsic called llvm.stackprotectorcheck right before the BB's 375263508Sdim /// returninst or if there is a callinst that could potentially be 376263508Sdim /// sibling call optimized, before the call inst. 377263508Sdim /// 378263508Sdim /// b. Then when a BB with said intrinsic is processed, we codegen the BB 379263508Sdim /// normally via SelectBasicBlock. In said process, when we visit the 380263508Sdim /// stack protector check, we do not actually emit anything into the 381263508Sdim /// BB. Instead, we just initialize the stack protector descriptor 382263508Sdim /// class (which involves stashing information/creating the success 383263508Sdim /// mbbb and the failure mbb if we have not created one for this 384263508Sdim /// function yet) and export the guard variable that we are going to 385263508Sdim /// compare. 386263508Sdim /// 387263508Sdim /// c. After we finish selecting the basic block, in FinishBasicBlock if 388263508Sdim /// the StackProtectorDescriptor attached to the SelectionDAGBuilder is 389263508Sdim /// initialized, we first find a splice point in the parent basic block 390263508Sdim /// before the terminator and then splice the terminator of said basic 391263508Sdim /// block into the success basic block. Then we code-gen a new tail for 392263508Sdim /// the parent basic block consisting of the two loads, the comparison, 393263508Sdim /// and finally two branches to the success/failure basic blocks. We 394263508Sdim /// conclude by code-gening the failure basic block if we have not 395263508Sdim /// code-gened it already (all stack protector checks we generate in 396263508Sdim /// the same function, use the same failure basic block). 397263508Sdim class StackProtectorDescriptor { 398263508Sdim public: 399263508Sdim StackProtectorDescriptor() : ParentMBB(0), SuccessMBB(0), FailureMBB(0), 400263508Sdim Guard(0) { } 401263508Sdim ~StackProtectorDescriptor() { } 402263508Sdim 403263508Sdim /// Returns true if all fields of the stack protector descriptor are 404263508Sdim /// initialized implying that we should/are ready to emit a stack protector. 405263508Sdim bool shouldEmitStackProtector() const { 406263508Sdim return ParentMBB && SuccessMBB && FailureMBB && Guard; 407263508Sdim } 408263508Sdim 409263508Sdim /// Initialize the stack protector descriptor structure for a new basic 410263508Sdim /// block. 411263508Sdim void initialize(const BasicBlock *BB, 412263508Sdim MachineBasicBlock *MBB, 413263508Sdim const CallInst &StackProtCheckCall) { 414263508Sdim // Make sure we are not initialized yet. 415263508Sdim assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is " 416263508Sdim "already initialized!"); 417263508Sdim ParentMBB = MBB; 418263508Sdim SuccessMBB = AddSuccessorMBB(BB, MBB); 419263508Sdim FailureMBB = AddSuccessorMBB(BB, MBB, FailureMBB); 420263508Sdim if (!Guard) 421263508Sdim Guard = StackProtCheckCall.getArgOperand(0); 422263508Sdim } 423263508Sdim 424263508Sdim /// Reset state that changes when we handle different basic blocks. 425263508Sdim /// 426263508Sdim /// This currently includes: 427263508Sdim /// 428263508Sdim /// 1. The specific basic block we are generating a 429263508Sdim /// stack protector for (ParentMBB). 430263508Sdim /// 431263508Sdim /// 2. The successor machine basic block that will contain the tail of 432263508Sdim /// parent mbb after we create the stack protector check (SuccessMBB). This 433263508Sdim /// BB is visited only on stack protector check success. 434263508Sdim void resetPerBBState() { 435263508Sdim ParentMBB = 0; 436263508Sdim SuccessMBB = 0; 437263508Sdim } 438263508Sdim 439263508Sdim /// Reset state that only changes when we switch functions. 440263508Sdim /// 441263508Sdim /// This currently includes: 442263508Sdim /// 443263508Sdim /// 1. FailureMBB since we reuse the failure code path for all stack 444263508Sdim /// protector checks created in an individual function. 445263508Sdim /// 446263508Sdim /// 2.The guard variable since the guard variable we are checking against is 447263508Sdim /// always the same. 448263508Sdim void resetPerFunctionState() { 449263508Sdim FailureMBB = 0; 450263508Sdim Guard = 0; 451263508Sdim } 452263508Sdim 453263508Sdim MachineBasicBlock *getParentMBB() { return ParentMBB; } 454263508Sdim MachineBasicBlock *getSuccessMBB() { return SuccessMBB; } 455263508Sdim MachineBasicBlock *getFailureMBB() { return FailureMBB; } 456263508Sdim const Value *getGuard() { return Guard; } 457263508Sdim 458263508Sdim private: 459263508Sdim /// The basic block for which we are generating the stack protector. 460263508Sdim /// 461263508Sdim /// As a result of stack protector generation, we will splice the 462263508Sdim /// terminators of this basic block into the successor mbb SuccessMBB and 463263508Sdim /// replace it with a compare/branch to the successor mbbs 464263508Sdim /// SuccessMBB/FailureMBB depending on whether or not the stack protector 465263508Sdim /// was violated. 466263508Sdim MachineBasicBlock *ParentMBB; 467263508Sdim 468263508Sdim /// A basic block visited on stack protector check success that contains the 469263508Sdim /// terminators of ParentMBB. 470263508Sdim MachineBasicBlock *SuccessMBB; 471263508Sdim 472263508Sdim /// This basic block visited on stack protector check failure that will 473263508Sdim /// contain a call to __stack_chk_fail(). 474263508Sdim MachineBasicBlock *FailureMBB; 475263508Sdim 476263508Sdim /// The guard variable which we will compare against the stored value in the 477263508Sdim /// stack protector stack slot. 478263508Sdim const Value *Guard; 479263508Sdim 480263508Sdim /// Add a successor machine basic block to ParentMBB. If the successor mbb 481263508Sdim /// has not been created yet (i.e. if SuccMBB = 0), then the machine basic 482263508Sdim /// block will be created. 483263508Sdim MachineBasicBlock *AddSuccessorMBB(const BasicBlock *BB, 484263508Sdim MachineBasicBlock *ParentMBB, 485263508Sdim MachineBasicBlock *SuccMBB = 0); 486263508Sdim }; 487263508Sdim 488263508Sdimprivate: 489263508Sdim const TargetMachine &TM; 490199989Srdivackypublic: 491199989Srdivacky SelectionDAG &DAG; 492243830Sdim const DataLayout *TD; 493199989Srdivacky AliasAnalysis *AA; 494234353Sdim const TargetLibraryInfo *LibInfo; 495199989Srdivacky 496199989Srdivacky /// SwitchCases - Vector of CaseBlock structures used to communicate 497199989Srdivacky /// SwitchInst code generation information. 498199989Srdivacky std::vector<CaseBlock> SwitchCases; 499199989Srdivacky /// JTCases - Vector of JumpTable structures used to communicate 500199989Srdivacky /// SwitchInst code generation information. 501199989Srdivacky std::vector<JumpTableBlock> JTCases; 502199989Srdivacky /// BitTestCases - Vector of BitTestBlock structures used to communicate 503199989Srdivacky /// SwitchInst code generation information. 504199989Srdivacky std::vector<BitTestBlock> BitTestCases; 505263508Sdim /// A StackProtectorDescriptor structure used to communicate stack protector 506263508Sdim /// information in between SelectBasicBlock and FinishBasicBlock. 507263508Sdim StackProtectorDescriptor SPDescriptor; 508199989Srdivacky 509199989Srdivacky // Emit PHI-node-operand constants only once even if used by multiple 510199989Srdivacky // PHI nodes. 511207618Srdivacky DenseMap<const Constant *, unsigned> ConstantsOut; 512199989Srdivacky 513199989Srdivacky /// FuncInfo - Information about the function as a whole. 514199989Srdivacky /// 515199989Srdivacky FunctionLoweringInfo &FuncInfo; 516199989Srdivacky 517199989Srdivacky /// OptLevel - What optimization level we're generating code for. 518263508Sdim /// 519199989Srdivacky CodeGenOpt::Level OptLevel; 520263508Sdim 521199989Srdivacky /// GFI - Garbage collection metadata for the function. 522199989Srdivacky GCFunctionInfo *GFI; 523199989Srdivacky 524226633Sdim /// LPadToCallSiteMap - Map a landing pad to the call site indexes. 525226633Sdim DenseMap<MachineBasicBlock*, SmallVector<unsigned, 4> > LPadToCallSiteMap; 526226633Sdim 527199989Srdivacky /// HasTailCall - This is set to true if a call in the current 528199989Srdivacky /// block has been translated as a tail call. In this case, 529199989Srdivacky /// no subsequent DAG nodes should be created. 530199989Srdivacky /// 531199989Srdivacky bool HasTailCall; 532199989Srdivacky 533199989Srdivacky LLVMContext *Context; 534199989Srdivacky 535207618Srdivacky SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, 536199989Srdivacky CodeGenOpt::Level ol) 537263508Sdim : CurInst(NULL), SDNodeOrder(0), TM(dag.getTarget()), 538207618Srdivacky DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 539243830Sdim HasTailCall(false) { 540199989Srdivacky } 541199989Srdivacky 542234353Sdim void init(GCFunctionInfo *gfi, AliasAnalysis &aa, 543234353Sdim const TargetLibraryInfo *li); 544199989Srdivacky 545207618Srdivacky /// clear - Clear out the current SelectionDAG and the associated 546199989Srdivacky /// state and prepare this SelectionDAGBuilder object to be used 547199989Srdivacky /// for a new block. This doesn't clear out information about 548199989Srdivacky /// additional blocks that are needed to complete switch lowering 549199989Srdivacky /// or PHI node updating; that information is cleared out as it is 550199989Srdivacky /// consumed. 551199989Srdivacky void clear(); 552199989Srdivacky 553223017Sdim /// clearDanglingDebugInfo - Clear the dangling debug information 554239462Sdim /// map. This function is separated from the clear so that debug 555223017Sdim /// information that is dangling in a basic block can be properly 556223017Sdim /// resolved in a different basic block. This allows the 557223017Sdim /// SelectionDAG to resolve dangling debug information attached 558223017Sdim /// to PHI nodes. 559223017Sdim void clearDanglingDebugInfo(); 560223017Sdim 561199989Srdivacky /// getRoot - Return the current virtual root of the Selection DAG, 562199989Srdivacky /// flushing any PendingLoad items. This must be done before emitting 563199989Srdivacky /// a store or any other node that may need to be ordered after any 564199989Srdivacky /// prior load instructions. 565199989Srdivacky /// 566199989Srdivacky SDValue getRoot(); 567199989Srdivacky 568199989Srdivacky /// getControlRoot - Similar to getRoot, but instead of flushing all the 569199989Srdivacky /// PendingLoad items, flush all the PendingExports items. It is necessary 570199989Srdivacky /// to do this before emitting a terminator instruction. 571199989Srdivacky /// 572199989Srdivacky SDValue getControlRoot(); 573199989Srdivacky 574263508Sdim SDLoc getCurSDLoc() const { 575263508Sdim return SDLoc(CurInst, SDNodeOrder); 576263508Sdim } 577219077Sdim 578263508Sdim DebugLoc getCurDebugLoc() const { 579263508Sdim return CurInst ? CurInst->getDebugLoc() : DebugLoc(); 580263508Sdim } 581263508Sdim 582201360Srdivacky unsigned getSDNodeOrder() const { return SDNodeOrder; } 583201360Srdivacky 584207618Srdivacky void CopyValueToVirtualRegister(const Value *V, unsigned Reg); 585199989Srdivacky 586207618Srdivacky void visit(const Instruction &I); 587199989Srdivacky 588207618Srdivacky void visit(unsigned Opcode, const User &I); 589199989Srdivacky 590212904Sdim // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V, 591212904Sdim // generate the debug data structures now that we've seen its definition. 592212904Sdim void resolveDanglingDebugInfo(const Value *V, SDValue Val); 593199989Srdivacky SDValue getValue(const Value *V); 594210299Sed SDValue getNonRegisterValue(const Value *V); 595210299Sed SDValue getValueImpl(const Value *V); 596199989Srdivacky 597199989Srdivacky void setValue(const Value *V, SDValue NewN) { 598199989Srdivacky SDValue &N = NodeMap[V]; 599199989Srdivacky assert(N.getNode() == 0 && "Already set a value for this node!"); 600199989Srdivacky N = NewN; 601199989Srdivacky } 602263508Sdim 603210299Sed void setUnusedArgValue(const Value *V, SDValue NewN) { 604210299Sed SDValue &N = UnusedArgNodeMap[V]; 605210299Sed assert(N.getNode() == 0 && "Already set a value for this node!"); 606210299Sed N = NewN; 607210299Sed } 608199989Srdivacky 609207618Srdivacky void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, 610199989Srdivacky MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 611207618Srdivacky MachineBasicBlock *SwitchBB, unsigned Opc); 612207618Srdivacky void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, 613199989Srdivacky MachineBasicBlock *FBB, 614207618Srdivacky MachineBasicBlock *CurBB, 615207618Srdivacky MachineBasicBlock *SwitchBB); 616199989Srdivacky bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 617207618Srdivacky bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); 618207618Srdivacky void CopyToExportRegsIfNeeded(const Value *V); 619207618Srdivacky void ExportFromCurrentBlock(const Value *V); 620207618Srdivacky void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall, 621199989Srdivacky MachineBasicBlock *LandingPad = NULL); 622199989Srdivacky 623263508Sdim std::pair<SDValue, SDValue> LowerCallOperands(const CallInst &CI, 624263508Sdim unsigned ArgIdx, 625263508Sdim unsigned NumArgs, 626263508Sdim SDValue Callee, 627263508Sdim bool useVoidTy = false); 628263508Sdim 629218893Sdim /// UpdateSplitBlock - When an MBB was split during scheduling, update the 630218893Sdim /// references that ned to refer to the last resulting block. 631218893Sdim void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last); 632218893Sdim 633199989Srdivackyprivate: 634199989Srdivacky // Terminator instructions. 635207618Srdivacky void visitRet(const ReturnInst &I); 636207618Srdivacky void visitBr(const BranchInst &I); 637207618Srdivacky void visitSwitch(const SwitchInst &I); 638207618Srdivacky void visitIndirectBr(const IndirectBrInst &I); 639207618Srdivacky void visitUnreachable(const UnreachableInst &I) { /* noop */ } 640199989Srdivacky 641199989Srdivacky // Helpers for visitSwitch 642199989Srdivacky bool handleSmallSwitchRange(CaseRec& CR, 643199989Srdivacky CaseRecVector& WorkList, 644207618Srdivacky const Value* SV, 645207618Srdivacky MachineBasicBlock* Default, 646207618Srdivacky MachineBasicBlock *SwitchBB); 647199989Srdivacky bool handleJTSwitchCase(CaseRec& CR, 648199989Srdivacky CaseRecVector& WorkList, 649207618Srdivacky const Value* SV, 650207618Srdivacky MachineBasicBlock* Default, 651207618Srdivacky MachineBasicBlock *SwitchBB); 652199989Srdivacky bool handleBTSplitSwitchCase(CaseRec& CR, 653199989Srdivacky CaseRecVector& WorkList, 654207618Srdivacky const Value* SV, 655207618Srdivacky MachineBasicBlock* Default, 656207618Srdivacky MachineBasicBlock *SwitchBB); 657199989Srdivacky bool handleBitTestsSwitchCase(CaseRec& CR, 658199989Srdivacky CaseRecVector& WorkList, 659207618Srdivacky const Value* SV, 660207618Srdivacky MachineBasicBlock* Default, 661207618Srdivacky MachineBasicBlock *SwitchBB); 662224145Sdim 663234353Sdim uint32_t getEdgeWeight(const MachineBasicBlock *Src, 664234353Sdim const MachineBasicBlock *Dst) const; 665226633Sdim void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, 666226633Sdim uint32_t Weight = 0); 667199989Srdivackypublic: 668207618Srdivacky void visitSwitchCase(CaseBlock &CB, 669207618Srdivacky MachineBasicBlock *SwitchBB); 670263508Sdim void visitSPDescriptorParent(StackProtectorDescriptor &SPD, 671263508Sdim MachineBasicBlock *ParentBB); 672263508Sdim void visitSPDescriptorFailure(StackProtectorDescriptor &SPD); 673207618Srdivacky void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); 674218893Sdim void visitBitTestCase(BitTestBlock &BB, 675218893Sdim MachineBasicBlock* NextMBB, 676243830Sdim uint32_t BranchWeightToNext, 677199989Srdivacky unsigned Reg, 678207618Srdivacky BitTestCase &B, 679207618Srdivacky MachineBasicBlock *SwitchBB); 680199989Srdivacky void visitJumpTable(JumpTable &JT); 681207618Srdivacky void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, 682207618Srdivacky MachineBasicBlock *SwitchBB); 683263508Sdim 684199989Srdivackyprivate: 685199989Srdivacky // These all get lowered before this pass. 686207618Srdivacky void visitInvoke(const InvokeInst &I); 687226633Sdim void visitResume(const ResumeInst &I); 688199989Srdivacky 689207618Srdivacky void visitBinary(const User &I, unsigned OpCode); 690207618Srdivacky void visitShift(const User &I, unsigned Opcode); 691207618Srdivacky void visitAdd(const User &I) { visitBinary(I, ISD::ADD); } 692207618Srdivacky void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); } 693207618Srdivacky void visitSub(const User &I) { visitBinary(I, ISD::SUB); } 694207618Srdivacky void visitFSub(const User &I); 695207618Srdivacky void visitMul(const User &I) { visitBinary(I, ISD::MUL); } 696207618Srdivacky void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); } 697207618Srdivacky void visitURem(const User &I) { visitBinary(I, ISD::UREM); } 698207618Srdivacky void visitSRem(const User &I) { visitBinary(I, ISD::SREM); } 699207618Srdivacky void visitFRem(const User &I) { visitBinary(I, ISD::FREM); } 700207618Srdivacky void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); } 701224145Sdim void visitSDiv(const User &I); 702207618Srdivacky void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); } 703207618Srdivacky void visitAnd (const User &I) { visitBinary(I, ISD::AND); } 704207618Srdivacky void visitOr (const User &I) { visitBinary(I, ISD::OR); } 705207618Srdivacky void visitXor (const User &I) { visitBinary(I, ISD::XOR); } 706207618Srdivacky void visitShl (const User &I) { visitShift(I, ISD::SHL); } 707207618Srdivacky void visitLShr(const User &I) { visitShift(I, ISD::SRL); } 708207618Srdivacky void visitAShr(const User &I) { visitShift(I, ISD::SRA); } 709207618Srdivacky void visitICmp(const User &I); 710207618Srdivacky void visitFCmp(const User &I); 711199989Srdivacky // Visit the conversion instructions 712207618Srdivacky void visitTrunc(const User &I); 713207618Srdivacky void visitZExt(const User &I); 714207618Srdivacky void visitSExt(const User &I); 715207618Srdivacky void visitFPTrunc(const User &I); 716207618Srdivacky void visitFPExt(const User &I); 717207618Srdivacky void visitFPToUI(const User &I); 718207618Srdivacky void visitFPToSI(const User &I); 719207618Srdivacky void visitUIToFP(const User &I); 720207618Srdivacky void visitSIToFP(const User &I); 721207618Srdivacky void visitPtrToInt(const User &I); 722207618Srdivacky void visitIntToPtr(const User &I); 723207618Srdivacky void visitBitCast(const User &I); 724263508Sdim void visitAddrSpaceCast(const User &I); 725199989Srdivacky 726207618Srdivacky void visitExtractElement(const User &I); 727207618Srdivacky void visitInsertElement(const User &I); 728207618Srdivacky void visitShuffleVector(const User &I); 729199989Srdivacky 730207618Srdivacky void visitExtractValue(const ExtractValueInst &I); 731207618Srdivacky void visitInsertValue(const InsertValueInst &I); 732226633Sdim void visitLandingPad(const LandingPadInst &I); 733199989Srdivacky 734207618Srdivacky void visitGetElementPtr(const User &I); 735207618Srdivacky void visitSelect(const User &I); 736199989Srdivacky 737207618Srdivacky void visitAlloca(const AllocaInst &I); 738207618Srdivacky void visitLoad(const LoadInst &I); 739207618Srdivacky void visitStore(const StoreInst &I); 740226633Sdim void visitAtomicCmpXchg(const AtomicCmpXchgInst &I); 741226633Sdim void visitAtomicRMW(const AtomicRMWInst &I); 742226633Sdim void visitFence(const FenceInst &I); 743207618Srdivacky void visitPHI(const PHINode &I); 744207618Srdivacky void visitCall(const CallInst &I); 745207618Srdivacky bool visitMemCmpCall(const CallInst &I); 746263508Sdim bool visitMemChrCall(const CallInst &I); 747263508Sdim bool visitStrCpyCall(const CallInst &I, bool isStpcpy); 748263508Sdim bool visitStrCmpCall(const CallInst &I); 749263508Sdim bool visitStrLenCall(const CallInst &I); 750263508Sdim bool visitStrNLenCall(const CallInst &I); 751239462Sdim bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode); 752226633Sdim void visitAtomicLoad(const LoadInst &I); 753226633Sdim void visitAtomicStore(const StoreInst &I); 754226633Sdim 755207618Srdivacky void visitInlineAsm(ImmutableCallSite CS); 756207618Srdivacky const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic); 757207618Srdivacky void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic); 758199989Srdivacky 759207618Srdivacky void visitVAStart(const CallInst &I); 760207618Srdivacky void visitVAArg(const VAArgInst &I); 761207618Srdivacky void visitVAEnd(const CallInst &I); 762207618Srdivacky void visitVACopy(const CallInst &I); 763263508Sdim void visitStackmap(const CallInst &I); 764263508Sdim void visitPatchpoint(const CallInst &I); 765199989Srdivacky 766207618Srdivacky void visitUserOp1(const Instruction &I) { 767199989Srdivacky llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 768199989Srdivacky } 769207618Srdivacky void visitUserOp2(const Instruction &I) { 770199989Srdivacky llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 771199989Srdivacky } 772207618Srdivacky 773263508Sdim void processIntegerCallValue(const Instruction &I, 774263508Sdim SDValue Value, bool IsSigned); 775263508Sdim 776207618Srdivacky void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 777207618Srdivacky 778212904Sdim /// EmitFuncArgumentDbgValue - If V is an function argument then create 779263508Sdim /// corresponding DBG_VALUE machine instruction for it now. At the end of 780212904Sdim /// instruction selection, they will be inserted to the entry BB. 781212904Sdim bool EmitFuncArgumentDbgValue(const Value *V, MDNode *Variable, 782212904Sdim int64_t Offset, const SDValue &N); 783199989Srdivacky}; 784199989Srdivacky 785199989Srdivacky} // end namespace llvm 786199989Srdivacky 787199989Srdivacky#endif 788