12048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman//===-- SelectionDAGBuilder.h - Selection-DAG building --------------------===// 2f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// 3f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// The LLVM Compiler Infrastructure 4f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// 5f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// This file is distributed under the University of Illinois Open Source 6f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// License. See LICENSE.TXT for details. 7f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// 8f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman//===----------------------------------------------------------------------===// 9f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// 10f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// This implements routines for translating from LLVM IR into SelectionDAG IR. 11f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman// 12f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman//===----------------------------------------------------------------------===// 13f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 142048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman#ifndef SELECTIONDAGBUILDER_H 152048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman#define SELECTIONDAGBUILDER_H 16f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 17f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include "llvm/ADT/APInt.h" 18f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include "llvm/ADT/DenseMap.h" 19a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/CodeGen/SelectionDAG.h" 20f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include "llvm/CodeGen/SelectionDAGNodes.h" 210eb96fd94bce94df680f1fc436c1d3d1c510f937Bill Wendling#include "llvm/CodeGen/ValueTypes.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 23f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include "llvm/Support/CallSite.h" 24c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 25f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include <vector> 26f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 27f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmannamespace llvm { 28f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 29f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass AliasAnalysis; 30f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass AllocaInst; 31f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass BasicBlock; 32f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass BitCastInst; 33f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass BranchInst; 34f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass CallInst; 354cf81c47fe060fad290ea6b95388d1da7fad105aDevang Patelclass DbgValueInst; 36f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ExtractElementInst; 37f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ExtractValueInst; 38f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass FCmpInst; 39f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass FPExtInst; 40f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass FPToSIInst; 41f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass FPToUIInst; 42f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass FPTruncInst; 43f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass Function; 446277eb2bb997a5da0808a8a5a57f18fd9faaf336Dan Gohmanclass FunctionLoweringInfo; 45f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass GetElementPtrInst; 46f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass GCFunctionInfo; 47f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ICmpInst; 48f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass IntToPtrInst; 49ab21db79ef1d2530880ad11f21f0b87ffca02dd4Chris Lattnerclass IndirectBrInst; 50f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass InvokeInst; 51f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass InsertElementInst; 52f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass InsertValueInst; 53f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass Instruction; 54f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass LoadInst; 55f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass MachineBasicBlock; 56f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass MachineInstr; 57f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass MachineRegisterInfo; 582ad0fcf794924f618a7240741cc14a39be99d0f2Evan Chengclass MDNode; 59f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass PHINode; 60f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass PtrToIntInst; 61f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ReturnInst; 62bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesenclass SDDbgValue; 63f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass SExtInst; 64f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass SelectInst; 65f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ShuffleVectorInst; 66f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass SIToFPInst; 67f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass StoreInst; 68f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass SwitchInst; 693574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowclass DataLayout; 70243eb9ecbbc6775e346e94025bd255bbceac9fcaOwen Andersonclass TargetLibraryInfo; 71f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass TargetLowering; 72f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass TruncInst; 73f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass UIToFPInst; 74f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass UnreachableInst; 75f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass VAArgInst; 76f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanclass ZExtInst; 77f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 78f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman//===----------------------------------------------------------------------===// 792048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman/// SelectionDAGBuilder - This is the common target-independent lowering 80f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman/// implementation that is parameterized by a TargetLowering object. 81f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman/// 822048b85c7c2c987874b9423e682ec8e60b60574bDan Gohmanclass SelectionDAGBuilder { 8366978ee97773aa76c3f15bee2fc77e5905aaf068Dale Johannesen /// CurDebugLoc - current file + line number. Changes as we build the DAG. 8466978ee97773aa76c3f15bee2fc77e5905aaf068Dale Johannesen DebugLoc CurDebugLoc; 8566978ee97773aa76c3f15bee2fc77e5905aaf068Dale Johannesen 86f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman DenseMap<const Value*, SDValue> NodeMap; 879126c0d42a5176e5865171713fae4a62e3c69912Devang Patel 889126c0d42a5176e5865171713fae4a62e3c69912Devang Patel /// UnusedArgNodeMap - Maps argument value for unused arguments. This is used 899126c0d42a5176e5865171713fae4a62e3c69912Devang Patel /// to preserve debug information for incoming arguments. 909126c0d42a5176e5865171713fae4a62e3c69912Devang Patel DenseMap<const Value*, SDValue> UnusedArgNodeMap; 91f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 92bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen /// DanglingDebugInfo - Helper type for DanglingDebugInfoMap. 93bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen class DanglingDebugInfo { 944cf81c47fe060fad290ea6b95388d1da7fad105aDevang Patel const DbgValueInst* DI; 95bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen DebugLoc dl; 96bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen unsigned SDNodeOrder; 97bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen public: 98bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen DanglingDebugInfo() : DI(0), dl(DebugLoc()), SDNodeOrder(0) { } 994cf81c47fe060fad290ea6b95388d1da7fad105aDevang Patel DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) : 100bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen DI(di), dl(DL), SDNodeOrder(SDNO) { } 1014cf81c47fe060fad290ea6b95388d1da7fad105aDevang Patel const DbgValueInst* getDI() { return DI; } 102bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen DebugLoc getdl() { return dl; } 103bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen unsigned getSDNodeOrder() { return SDNodeOrder; } 104bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen }; 105bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen 106bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen /// DanglingDebugInfoMap - Keeps track of dbg_values for which we have not 107bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen /// yet seen the referent. We defer handling these until we do see it. 108bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap; 109bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen 1108047d9a6be9c6261c4d3f286786be856d619ed0fChris Lattnerpublic: 111f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// PendingLoads - Loads are not emitted to the program immediately. We bunch 112f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// them up and then emit token factor nodes when possible. This allows us to 113f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// get simple disambiguation between loads without worrying about alias 114f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// analysis. 115f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SmallVector<SDValue, 8> PendingLoads; 1168047d9a6be9c6261c4d3f286786be856d619ed0fChris Lattnerprivate: 117f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 118f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// PendingExports - CopyToReg nodes that copy values to virtual registers 119f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// for export to other blocks need to be emitted before any terminator 120f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// instruction, but they have no other ordering requirements. We bunch them 121f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// up and the emit a single tokenfactor for them just before terminator 122f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// instructions. 123f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SmallVector<SDValue, 8> PendingExports; 124f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 125b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling /// SDNodeOrder - A unique monotonically increasing number used to order the 126b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling /// SDNodes we create. 127b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling unsigned SDNodeOrder; 128b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling 129f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// Case - A struct to record the Value for a switch case, and the 130f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// case's target basic block. 131f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct Case { 13224473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy const Constant *Low; 13324473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy const Constant *High; 134f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock* BB; 135c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak uint32_t ExtraWeight; 136c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 137c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak Case() : Low(0), High(0), BB(0), ExtraWeight(0) { } 13824473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy Case(const Constant *low, const Constant *high, MachineBasicBlock *bb, 139c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak uint32_t extraweight) : Low(low), High(high), BB(bb), 140c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak ExtraWeight(extraweight) { } 141f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 142e880efe446f731b73558542c12a6f980b8baa765Chris Lattner APInt size() const { 143e880efe446f731b73558542c12a6f980b8baa765Chris Lattner const APInt &rHigh = cast<ConstantInt>(High)->getValue(); 144e880efe446f731b73558542c12a6f980b8baa765Chris Lattner const APInt &rLow = cast<ConstantInt>(Low)->getValue(); 145f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return (rHigh - rLow + 1ULL); 146f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 147f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 148f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 149f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct CaseBits { 150f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman uint64_t Mask; 151f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock* BB; 152f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman unsigned Bits; 1531a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t ExtraWeight; 154f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 1551a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits, 1561a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t Weight): 1571a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { } 158f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 159f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 160f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef std::vector<Case> CaseVector; 161f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef std::vector<CaseBits> CaseBitsVector; 162f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef CaseVector::iterator CaseItr; 163f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef std::pair<CaseItr, CaseItr> CaseRange; 164f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 165f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// CaseRec - A struct with ctor used in lowering switches to a binary tree 166f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// of conditional branches. 167f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct CaseRec { 16846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman CaseRec(MachineBasicBlock *bb, const Constant *lt, const Constant *ge, 16946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman CaseRange r) : 170f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseBB(bb), LT(lt), GE(ge), Range(r) {} 171f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 172f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// CaseBB - The MBB in which to emit the compare and branch 173f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *CaseBB; 174f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// LT, GE - If nonzero, we know the current case value must be less-than or 175f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// greater-than-or-equal-to these Constants. 17646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Constant *LT; 17746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Constant *GE; 178f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// Range - A pair of iterators representing the range of case values to be 179f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// processed at this point in the binary search tree. 180f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseRange Range; 181f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 182f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 183f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef std::vector<CaseRec> CaseRecVector; 184f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 185f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct CaseBitsCmp { 18653334ca5acc43500bb2744ed1a44e16442e92d0dChris Lattner bool operator()(const CaseBits &C1, const CaseBits &C2) { 187f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return C1.Bits > C2.Bits; 188f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 189f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 190f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 19153334ca5acc43500bb2744ed1a44e16442e92d0dChris Lattner size_t Clusterify(CaseVector &Cases, const SwitchInst &SI); 1922321858c8cf5583a77b1318d5275188058ab5504Anton Korobeynikov 1932048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman /// CaseBlock - This structure is used to communicate between 1942048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman /// SelectionDAGBuilder and SDISel for the code generation of additional basic 1952048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman /// blocks needed by multi-case switch statements. 196f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct CaseBlock { 19746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, 19846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value *cmpmiddle, 199f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *truebb, MachineBasicBlock *falsebb, 200c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak MachineBasicBlock *me, 201c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak uint32_t trueweight = 0, uint32_t falseweight = 0) 202f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), 203c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak TrueBB(truebb), FalseBB(falsebb), ThisBB(me), 204c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak TrueWeight(trueweight), FalseWeight(falseweight) { } 205c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 206f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // CC - the condition code to use for the case block's setcc node 207f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman ISD::CondCode CC; 208c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 209f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. 210f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // Emit by default LHS op RHS. MHS is used for range comparisons: 211f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). 21246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value *CmpLHS, *CmpMHS, *CmpRHS; 213c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 214f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // TrueBB/FalseBB - the block to branch to if the setcc is true/false. 215f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *TrueBB, *FalseBB; 216c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 217f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // ThisBB - the block into which to emit the code for the setcc and branches 218f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *ThisBB; 219c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 220c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak // TrueWeight/FalseWeight - branch weights. 221c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak uint32_t TrueWeight, FalseWeight; 222f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 223c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak 224f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct JumpTable { 225f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, 226f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} 227f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 228f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// Reg - the virtual register containing the index of the jump table entry 229f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman //. to jump to. 230f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman unsigned Reg; 231f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// JTI - the JumpTableIndex for this jump table in the function. 232f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman unsigned JTI; 233f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// MBB - the MBB into which to emit the code for the indirect jump. 234f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *MBB; 235f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// Default - the MBB of the default bb, which is a successor of the range 236f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// check MBB. This is when updating PHI nodes in successors. 237f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *Default; 238f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 239f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct JumpTableHeader { 24046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H, 241f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool E = false): 242f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} 2432321858c8cf5583a77b1318d5275188058ab5504Anton Korobeynikov APInt First; 2442321858c8cf5583a77b1318d5275188058ab5504Anton Korobeynikov APInt Last; 24546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value *SValue; 246f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *HeaderBB; 247f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool Emitted; 248f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 249f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock; 250f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 251f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct BitTestCase { 2521a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr, 2531a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t Weight): 2541a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { } 255f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman uint64_t Mask; 25653334ca5acc43500bb2744ed1a44e16442e92d0dChris Lattner MachineBasicBlock *ThisBB; 25753334ca5acc43500bb2744ed1a44e16442e92d0dChris Lattner MachineBasicBlock *TargetBB; 2581a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t ExtraWeight; 259f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 260f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 261f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman typedef SmallVector<BitTestCase, 3> BitTestInfo; 262f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 263f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman struct BitTestBlock { 26446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman BitTestBlock(APInt F, APInt R, const Value* SV, 2658963fecc86def73634dabf7545322287aa6ae9f8Patrik Hagglund unsigned Rg, MVT RgVT, bool E, 266f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock* P, MachineBasicBlock* D, 267f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman const BitTestInfo& C): 268d08e5b48bc5d9177b1d70a1980a7805420a99085Evan Cheng First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E), 269f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman Parent(P), Default(D), Cases(C) { } 2702321858c8cf5583a77b1318d5275188058ab5504Anton Korobeynikov APInt First; 2712321858c8cf5583a77b1318d5275188058ab5504Anton Korobeynikov APInt Range; 27246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value *SValue; 273f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman unsigned Reg; 2748963fecc86def73634dabf7545322287aa6ae9f8Patrik Hagglund MVT RegVT; 275f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool Emitted; 276f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *Parent; 277f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *Default; 278f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman BitTestInfo Cases; 279f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman }; 280f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 281f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanpublic: 282f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // TLI - This is information that describes the available target features we 283f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // need for lowering. This indicates when operations are unavailable, 284f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // implemented with a libcall, etc. 28555e59c186303ff02c0be7429da3b1b36c347f164Dan Gohman const TargetMachine &TM; 286d858e90f039f5fcdc2fa93035e911a5a9505cc50Dan Gohman const TargetLowering &TLI; 287f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SelectionDAG &DAG; 2883574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD; 289f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman AliasAnalysis *AA; 290243eb9ecbbc6775e346e94025bd255bbceac9fcaOwen Anderson const TargetLibraryInfo *LibInfo; 291f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 292f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// SwitchCases - Vector of CaseBlock structures used to communicate 293f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// SwitchInst code generation information. 294f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman std::vector<CaseBlock> SwitchCases; 295f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// JTCases - Vector of JumpTable structures used to communicate 296f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// SwitchInst code generation information. 297f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman std::vector<JumpTableBlock> JTCases; 298f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// BitTestCases - Vector of BitTestBlock structures used to communicate 299f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// SwitchInst code generation information. 300f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman std::vector<BitTestBlock> BitTestCases; 301fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng 302f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // Emit PHI-node-operand constants only once even if used by multiple 303f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // PHI nodes. 30446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman DenseMap<const Constant *, unsigned> ConstantsOut; 305f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 306f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// FuncInfo - Information about the function as a whole. 307f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// 308f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman FunctionLoweringInfo &FuncInfo; 309dfdacee2abd53d71a5b9a9f4d38c7973cc722663Bill Wendling 310be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling /// OptLevel - What optimization level we're generating code for. 311dfdacee2abd53d71a5b9a9f4d38c7973cc722663Bill Wendling /// 31298a366d547772010e94609e4584489b3e5ce0043Bill Wendling CodeGenOpt::Level OptLevel; 313f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 314f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// GFI - Garbage collection metadata for the function. 315f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman GCFunctionInfo *GFI; 316f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 31730e6740f2e3d518ce1cfcd484ef728ac5764a645Bill Wendling /// LPadToCallSiteMap - Map a landing pad to the call site indexes. 31830e6740f2e3d518ce1cfcd484ef728ac5764a645Bill Wendling DenseMap<MachineBasicBlock*, SmallVector<unsigned, 4> > LPadToCallSiteMap; 319a8512edb6d1c52209bad2d6b989599bc4872c913Bill Wendling 32098ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman /// HasTailCall - This is set to true if a call in the current 32198ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman /// block has been translated as a tail call. In this case, 32298ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman /// no subsequent DAG nodes should be created. 32398ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman /// 32498ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman bool HasTailCall; 32598ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman 3260a5372ed3e8cda10d724feda3c1a1c998db05ca0Owen Anderson LLVMContext *Context; 3270a5372ed3e8cda10d724feda3c1a1c998db05ca0Owen Anderson 32855e59c186303ff02c0be7429da3b1b36c347f164Dan Gohman SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, 3292048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman CodeGenOpt::Level ol) 33055e59c186303ff02c0be7429da3b1b36c347f164Dan Gohman : SDNodeOrder(0), TM(dag.getTarget()), TLI(dag.getTargetLoweringInfo()), 33155e59c186303ff02c0be7429da3b1b36c347f164Dan Gohman DAG(dag), FuncInfo(funcinfo), OptLevel(ol), 332cb1f68d7c8bea99530ba55813c2b4ddd14556286Richard Smith HasTailCall(false) { 333f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 334f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 335243eb9ecbbc6775e346e94025bd255bbceac9fcaOwen Anderson void init(GCFunctionInfo *gfi, AliasAnalysis &aa, 336243eb9ecbbc6775e346e94025bd255bbceac9fcaOwen Anderson const TargetLibraryInfo *li); 337f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 338b02b62a2719bf5cfe12cfc902ab4e85d675450a0Dan Gohman /// clear - Clear out the current SelectionDAG and the associated 3392048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman /// state and prepare this SelectionDAGBuilder object to be used 340f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// for a new block. This doesn't clear out information about 341f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// additional blocks that are needed to complete switch lowering 342f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// or PHI node updating; that information is cleared out as it is 343f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// consumed. 344f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman void clear(); 345f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 346233857537f61a8f4ab93624986676c25b2271bc7Devang Patel /// clearDanglingDebugInfo - Clear the dangling debug information 347d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer /// map. This function is separated from the clear so that debug 348233857537f61a8f4ab93624986676c25b2271bc7Devang Patel /// information that is dangling in a basic block can be properly 349233857537f61a8f4ab93624986676c25b2271bc7Devang Patel /// resolved in a different basic block. This allows the 350233857537f61a8f4ab93624986676c25b2271bc7Devang Patel /// SelectionDAG to resolve dangling debug information attached 351233857537f61a8f4ab93624986676c25b2271bc7Devang Patel /// to PHI nodes. 352233857537f61a8f4ab93624986676c25b2271bc7Devang Patel void clearDanglingDebugInfo(); 353233857537f61a8f4ab93624986676c25b2271bc7Devang Patel 354f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// getRoot - Return the current virtual root of the Selection DAG, 355f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// flushing any PendingLoad items. This must be done before emitting 356f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// a store or any other node that may need to be ordered after any 357f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// prior load instructions. 358f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// 359f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SDValue getRoot(); 360f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 361f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// getControlRoot - Similar to getRoot, but instead of flushing all the 362f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// PendingLoad items, flush all the PendingExports items. It is necessary 363f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// to do this before emitting a terminator instruction. 364f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// 365f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SDValue getControlRoot(); 366f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 36766978ee97773aa76c3f15bee2fc77e5905aaf068Dale Johannesen DebugLoc getCurDebugLoc() const { return CurDebugLoc; } 36868e6beeccc0b9ac2e8d3687a8a5b7d4b172edca1Devang Patel 3693ea3c2461932d96d3defa0a9aa93ffaf631bb19dBill Wendling unsigned getSDNodeOrder() const { return SDNodeOrder; } 3703ea3c2461932d96d3defa0a9aa93ffaf631bb19dBill Wendling 37146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void CopyValueToVirtualRegister(const Value *V, unsigned Reg); 372f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 3734533cac557cdcc13e7c990942758ec8338d9172aBill Wendling /// AssignOrderingToNode - Assign an ordering to the node. The order is gotten 3744533cac557cdcc13e7c990942758ec8338d9172aBill Wendling /// from how the code appeared in the source. The ordering is used by the 3754533cac557cdcc13e7c990942758ec8338d9172aBill Wendling /// scheduler to effectively turn off scheduling. 3764533cac557cdcc13e7c990942758ec8338d9172aBill Wendling void AssignOrderingToNode(const SDNode *Node); 3774533cac557cdcc13e7c990942758ec8338d9172aBill Wendling 37846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visit(const Instruction &I); 379f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 38046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visit(unsigned Opcode, const User &I); 381f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 382bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V, 383bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen // generate the debug data structures now that we've seen its definition. 384bdc09d9b0943a8c5cee29c4f87666eaa97e081d4Dale Johannesen void resolveDanglingDebugInfo(const Value *V, SDValue Val); 385f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SDValue getValue(const Value *V); 38628a173581c67cda78b2febd24d10edb13f760c4cDan Gohman SDValue getNonRegisterValue(const Value *V); 38728a173581c67cda78b2febd24d10edb13f760c4cDan Gohman SDValue getValueImpl(const Value *V); 388f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 389f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman void setValue(const Value *V, SDValue NewN) { 390f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SDValue &N = NodeMap[V]; 391f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman assert(N.getNode() == 0 && "Already set a value for this node!"); 392f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman N = NewN; 393f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 394f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 3959126c0d42a5176e5865171713fae4a62e3c69912Devang Patel void setUnusedArgValue(const Value *V, SDValue NewN) { 3969126c0d42a5176e5865171713fae4a62e3c69912Devang Patel SDValue &N = UnusedArgNodeMap[V]; 3979126c0d42a5176e5865171713fae4a62e3c69912Devang Patel assert(N.getNode() == 0 && "Already set a value for this node!"); 3989126c0d42a5176e5865171713fae4a62e3c69912Devang Patel N = NewN; 3999126c0d42a5176e5865171713fae4a62e3c69912Devang Patel } 400f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 40146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, 402f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 40399be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB, unsigned Opc); 40446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, 405c227734855b615f5b09060e7ea67f697de08fc7eDan Gohman MachineBasicBlock *FBB, 40699be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *CurBB, 40799be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 408f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases); 40946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); 41046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void CopyToExportRegsIfNeeded(const Value *V); 41146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void ExportFromCurrentBlock(const Value *V); 41246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall, 413f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *LandingPad = NULL); 414f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 4152622f4622c36ec9924fb908085154ffdd7174affJakob Stoklund Olesen /// UpdateSplitBlock - When an MBB was split during scheduling, update the 4162622f4622c36ec9924fb908085154ffdd7174affJakob Stoklund Olesen /// references that ned to refer to the last resulting block. 4172622f4622c36ec9924fb908085154ffdd7174affJakob Stoklund Olesen void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last); 4182622f4622c36ec9924fb908085154ffdd7174affJakob Stoklund Olesen 419f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanprivate: 420f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // Terminator instructions. 42146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitRet(const ReturnInst &I); 42246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitBr(const BranchInst &I); 42346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSwitch(const SwitchInst &I); 42446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitIndirectBr(const IndirectBrInst &I); 425a60f0e7f817f170df55371491e246b95b0d8d6b0Bill Wendling void visitUnreachable(const UnreachableInst &I) { /* noop */ } 426f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 427f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // Helpers for visitSwitch 428f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool handleSmallSwitchRange(CaseRec& CR, 429f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseRecVector& WorkList, 43046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value* SV, 43199be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock* Default, 43299be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 433f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool handleJTSwitchCase(CaseRec& CR, 434f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseRecVector& WorkList, 43546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value* SV, 43699be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock* Default, 43799be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 438f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool handleBTSplitSwitchCase(CaseRec& CR, 439f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseRecVector& WorkList, 44046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value* SV, 44199be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock* Default, 44299be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 443f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool handleBitTestsSwitchCase(CaseRec& CR, 444f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman CaseRecVector& WorkList, 44546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const Value* SV, 44699be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock* Default, 44799be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 4487cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 44925101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak uint32_t getEdgeWeight(const MachineBasicBlock *Src, 45025101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak const MachineBasicBlock *Dst) const; 451c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, 452c8f34de5d615b858319f33d4e19c24622d971416Jakub Staszak uint32_t Weight = 0); 453f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanpublic: 45499be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman void visitSwitchCase(CaseBlock &CB, 45599be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 45699be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB); 457d08e5b48bc5d9177b1d70a1980a7805420a99085Evan Cheng void visitBitTestCase(BitTestBlock &BB, 458d08e5b48bc5d9177b1d70a1980a7805420a99085Evan Cheng MachineBasicBlock* NextMBB, 4591a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t BranchWeightToNext, 460f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman unsigned Reg, 46199be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman BitTestCase &B, 46299be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 463f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman void visitJumpTable(JumpTable &JT); 46499be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, 46599be8ae3898d87373ef0c8f1159b287e28a8d81bDan Gohman MachineBasicBlock *SwitchBB); 466f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 467f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmanprivate: 468f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // These all get lowered before this pass. 46946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitInvoke(const InvokeInst &I); 470dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling void visitResume(const ResumeInst &I); 47146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 47246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitBinary(const User &I, unsigned OpCode); 47346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitShift(const User &I, unsigned Opcode); 47446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitAdd(const User &I) { visitBinary(I, ISD::ADD); } 47546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); } 47646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSub(const User &I) { visitBinary(I, ISD::SUB); } 47746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFSub(const User &I); 47846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitMul(const User &I) { visitBinary(I, ISD::MUL); } 47946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); } 48046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitURem(const User &I) { visitBinary(I, ISD::UREM); } 48146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSRem(const User &I) { visitBinary(I, ISD::SREM); } 48246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFRem(const User &I) { visitBinary(I, ISD::FREM); } 48346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); } 4849c64030445cbe6ac486b90c5f459f91e06770474Benjamin Kramer void visitSDiv(const User &I); 48546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); } 48646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitAnd (const User &I) { visitBinary(I, ISD::AND); } 48746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitOr (const User &I) { visitBinary(I, ISD::OR); } 48846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitXor (const User &I) { visitBinary(I, ISD::XOR); } 48946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitShl (const User &I) { visitShift(I, ISD::SHL); } 49046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitLShr(const User &I) { visitShift(I, ISD::SRL); } 49146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitAShr(const User &I) { visitShift(I, ISD::SRA); } 49246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitICmp(const User &I); 49346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFCmp(const User &I); 494f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman // Visit the conversion instructions 49546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitTrunc(const User &I); 49646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitZExt(const User &I); 49746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSExt(const User &I); 49846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFPTrunc(const User &I); 49946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFPExt(const User &I); 50046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFPToUI(const User &I); 50146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitFPToSI(const User &I); 50246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitUIToFP(const User &I); 50346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSIToFP(const User &I); 50446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitPtrToInt(const User &I); 50546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitIntToPtr(const User &I); 50646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitBitCast(const User &I); 50746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 50846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitExtractElement(const User &I); 50946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitInsertElement(const User &I); 51046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitShuffleVector(const User &I); 51146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 51246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitExtractValue(const ExtractValueInst &I); 51346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitInsertValue(const InsertValueInst &I); 514e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling void visitLandingPad(const LandingPadInst &I); 51546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 51646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitGetElementPtr(const User &I); 51746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitSelect(const User &I); 51846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 51946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitAlloca(const AllocaInst &I); 52046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitLoad(const LoadInst &I); 52146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitStore(const StoreInst &I); 522ff03048c1350fcc4fda1ef6d6c57252f3a950854Eli Friedman void visitAtomicCmpXchg(const AtomicCmpXchgInst &I); 523ff03048c1350fcc4fda1ef6d6c57252f3a950854Eli Friedman void visitAtomicRMW(const AtomicRMWInst &I); 52447f3513dd574535aeb40c9eb11134f0899e92269Eli Friedman void visitFence(const FenceInst &I); 525ba5be5c07bb19dcf484e3aa40cd139dd07c10407Dan Gohman void visitPHI(const PHINode &I); 52646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitCall(const CallInst &I); 52746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman bool visitMemCmpCall(const CallInst &I); 52853624a2df557b4a24f2ee98cfce1a69bf83243afBob Wilson bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode); 529327236cd6c211e54fc6288b0ac2b413901cc0611Eli Friedman void visitAtomicLoad(const LoadInst &I); 530327236cd6c211e54fc6288b0ac2b413901cc0611Eli Friedman void visitAtomicStore(const StoreInst &I); 531327236cd6c211e54fc6288b0ac2b413901cc0611Eli Friedman 53246510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitInlineAsm(ImmutableCallSite CS); 53346510a73e977273ec67747eb34cbdb43f815e451Dan Gohman const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic); 53446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic); 53546510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 53646510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitVAStart(const CallInst &I); 53746510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitVAArg(const VAArgInst &I); 53846510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitVAEnd(const CallInst &I); 53946510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitVACopy(const CallInst &I); 54046510a73e977273ec67747eb34cbdb43f815e451Dan Gohman 54146510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitUserOp1(const Instruction &I) { 542c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 543f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 54446510a73e977273ec67747eb34cbdb43f815e451Dan Gohman void visitUserOp2(const Instruction &I) { 545c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 546f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman } 547c105a2b5b7d8969e78bd4b203e980dced8a1c689Dan Gohman 548c105a2b5b7d8969e78bd4b203e980dced8a1c689Dan Gohman void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 5492ad0fcf794924f618a7240741cc14a39be99d0f2Evan Cheng 550ab43add695179614927766269df08b22c157f931Devang Patel /// EmitFuncArgumentDbgValue - If V is an function argument then create 551ab43add695179614927766269df08b22c157f931Devang Patel /// corresponding DBG_VALUE machine instruction for it now. At the end of 552ab43add695179614927766269df08b22c157f931Devang Patel /// instruction selection, they will be inserted to the entry BB. 55378a06e50b74e5390e3d77bd80d0393191820c7c2Devang Patel bool EmitFuncArgumentDbgValue(const Value *V, MDNode *Variable, 55434ca5ed79717c9a3dad2bf5823d3747aaedbc74aDevang Patel int64_t Offset, const SDValue &N); 555f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman}; 556f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 557f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman} // end namespace llvm 558f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman 559f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#endif 560