1 //===-- ConstantHoisting.h - Prepare code for expensive constants ---------===// 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 pass identifies expensive constants to hoist and coalesces them to 11 // better prepare it for SelectionDAG-based code generation. This works around 12 // the limitations of the basic-block-at-a-time approach. 13 // 14 // First it scans all instructions for integer constants and calculates its 15 // cost. If the constant can be folded into the instruction (the cost is 16 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't 17 // consider it expensive and leave it alone. This is the default behavior and 18 // the default implementation of getIntImmCost will always return TCC_Free. 19 // 20 // If the cost is more than TCC_BASIC, then the integer constant can't be folded 21 // into the instruction and it might be beneficial to hoist the constant. 22 // Similar constants are coalesced to reduce register pressure and 23 // materialization code. 24 // 25 // When a constant is hoisted, it is also hidden behind a bitcast to force it to 26 // be live-out of the basic block. Otherwise the constant would be just 27 // duplicated and each basic block would have its own copy in the SelectionDAG. 28 // The SelectionDAG recognizes such constants as opaque and doesn't perform 29 // certain transformations on them, which would create a new expensive constant. 30 // 31 // This optimization is only applied to integer constants in instructions and 32 // simple (this means not nested) constant cast expressions. For example: 33 // %0 = load i64* inttoptr (i64 big_constant to i64*) 34 //===----------------------------------------------------------------------===// 35 36 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 37 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 38 39 #include "llvm/Analysis/TargetTransformInfo.h" 40 #include "llvm/IR/Dominators.h" 41 #include "llvm/IR/PassManager.h" 42 43 namespace llvm { 44 45 /// A private "module" namespace for types and utilities used by 46 /// ConstantHoisting. These are implementation details and should not be used by 47 /// clients. 48 namespace consthoist { 49 /// \brief Keeps track of the user of a constant and the operand index where the 50 /// constant is used. 51 struct ConstantUser { 52 Instruction *Inst; 53 unsigned OpndIdx; 54 ConstantUserConstantUser55 ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { } 56 }; 57 58 typedef SmallVector<ConstantUser, 8> ConstantUseListType; 59 60 /// \brief Keeps track of a constant candidate and its uses. 61 struct ConstantCandidate { 62 ConstantUseListType Uses; 63 ConstantInt *ConstInt; 64 unsigned CumulativeCost; 65 ConstantCandidateConstantCandidate66 ConstantCandidate(ConstantInt *ConstInt) 67 : ConstInt(ConstInt), CumulativeCost(0) { } 68 69 /// \brief Add the user to the use list and update the cost. addUserConstantCandidate70 void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { 71 CumulativeCost += Cost; 72 Uses.push_back(ConstantUser(Inst, Idx)); 73 } 74 }; 75 76 /// \brief This represents a constant that has been rebased with respect to a 77 /// base constant. The difference to the base constant is recorded in Offset. 78 struct RebasedConstantInfo { 79 ConstantUseListType Uses; 80 Constant *Offset; 81 RebasedConstantInfoRebasedConstantInfo82 RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) 83 : Uses(std::move(Uses)), Offset(Offset) { } 84 }; 85 86 typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType; 87 88 /// \brief A base constant and all its rebased constants. 89 struct ConstantInfo { 90 ConstantInt *BaseConstant; 91 RebasedConstantListType RebasedConstants; 92 }; 93 } 94 95 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { 96 public: 97 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 98 99 // Glue for old PM. 100 bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, 101 BasicBlock &Entry); 102 releaseMemory()103 void releaseMemory() { 104 ConstantVec.clear(); 105 ClonedCastMap.clear(); 106 ConstCandVec.clear(); 107 } 108 109 private: 110 typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType; 111 typedef std::vector<consthoist::ConstantCandidate> ConstCandVecType; 112 113 const TargetTransformInfo *TTI; 114 DominatorTree *DT; 115 BasicBlock *Entry; 116 117 /// Keeps track of constant candidates found in the function. 118 ConstCandVecType ConstCandVec; 119 120 /// Keep track of cast instructions we already cloned. 121 SmallDenseMap<Instruction *, Instruction *> ClonedCastMap; 122 123 /// These are the final constants we decided to hoist. 124 SmallVector<consthoist::ConstantInfo, 8> ConstantVec; 125 126 Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; 127 Instruction *findConstantInsertionPoint( 128 const consthoist::ConstantInfo &ConstInfo) const; 129 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 130 Instruction *Inst, unsigned Idx, 131 ConstantInt *ConstInt); 132 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 133 Instruction *Inst); 134 void collectConstantCandidates(Function &Fn); 135 void findAndMakeBaseConstant(ConstCandVecType::iterator S, 136 ConstCandVecType::iterator E); 137 unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, 138 ConstCandVecType::iterator E, 139 ConstCandVecType::iterator &MaxCostItr); 140 void findBaseConstants(); 141 void emitBaseConstants(Instruction *Base, Constant *Offset, 142 const consthoist::ConstantUser &ConstUser); 143 bool emitBaseConstants(); 144 void deleteDeadCastInst() const; 145 bool optimizeConstants(Function &Fn); 146 }; 147 } 148 149 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 150