1 //==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass identifies expensive constants to hoist and coalesces them to 10 // better prepare it for SelectionDAG-based code generation. This works around 11 // the limitations of the basic-block-at-a-time approach. 12 // 13 // First it scans all instructions for integer constants and calculates its 14 // cost. If the constant can be folded into the instruction (the cost is 15 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't 16 // consider it expensive and leave it alone. This is the default behavior and 17 // the default implementation of getIntImmCostInst will always return TCC_Free. 18 // 19 // If the cost is more than TCC_BASIC, then the integer constant can't be folded 20 // into the instruction and it might be beneficial to hoist the constant. 21 // Similar constants are coalesced to reduce register pressure and 22 // materialization code. 23 // 24 // When a constant is hoisted, it is also hidden behind a bitcast to force it to 25 // be live-out of the basic block. Otherwise the constant would be just 26 // duplicated and each basic block would have its own copy in the SelectionDAG. 27 // The SelectionDAG recognizes such constants as opaque and doesn't perform 28 // certain transformations on them, which would create a new expensive constant. 29 // 30 // This optimization is only applied to integer constants in instructions and 31 // simple (this means not nested) constant cast expressions. For example: 32 // %0 = load i64* inttoptr (i64 big_constant to i64*) 33 // 34 //===----------------------------------------------------------------------===// 35 36 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 37 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 38 39 #include "llvm/ADT/ArrayRef.h" 40 #include "llvm/ADT/DenseMap.h" 41 #include "llvm/ADT/MapVector.h" 42 #include "llvm/ADT/PointerUnion.h" 43 #include "llvm/ADT/SetVector.h" 44 #include "llvm/ADT/SmallVector.h" 45 #include "llvm/IR/PassManager.h" 46 #include <algorithm> 47 #include <vector> 48 49 namespace llvm { 50 51 class BasicBlock; 52 class BlockFrequencyInfo; 53 class Constant; 54 class ConstantInt; 55 class ConstantExpr; 56 class DominatorTree; 57 class Function; 58 class GlobalVariable; 59 class Instruction; 60 class ProfileSummaryInfo; 61 class TargetTransformInfo; 62 63 /// A private "module" namespace for types and utilities used by 64 /// ConstantHoisting. These are implementation details and should not be used by 65 /// clients. 66 namespace consthoist { 67 68 /// Keeps track of the user of a constant and the operand index where the 69 /// constant is used. 70 struct ConstantUser { 71 Instruction *Inst; 72 unsigned OpndIdx; 73 74 ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {} 75 }; 76 77 using ConstantUseListType = SmallVector<ConstantUser, 8>; 78 79 /// Keeps track of a constant candidate and its uses. 80 struct ConstantCandidate { 81 ConstantUseListType Uses; 82 // If the candidate is a ConstantExpr (currely only constant GEP expressions 83 // whose base pointers are GlobalVariables are supported), ConstInt records 84 // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 85 ConstantInt *ConstInt; 86 ConstantExpr *ConstExpr; 87 unsigned CumulativeCost = 0; 88 89 ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) : 90 ConstInt(ConstInt), ConstExpr(ConstExpr) {} 91 92 /// Add the user to the use list and update the cost. 93 void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { 94 CumulativeCost += Cost; 95 Uses.push_back(ConstantUser(Inst, Idx)); 96 } 97 }; 98 99 /// This represents a constant that has been rebased with respect to a 100 /// base constant. The difference to the base constant is recorded in Offset. 101 struct RebasedConstantInfo { 102 ConstantUseListType Uses; 103 Constant *Offset; 104 Type *Ty; 105 106 RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, 107 Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {} 108 }; 109 110 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; 111 112 /// A base constant and all its rebased constants. 113 struct ConstantInfo { 114 // If the candidate is a ConstantExpr (currely only constant GEP expressions 115 // whose base pointers are GlobalVariables are supported), ConstInt records 116 // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 117 ConstantInt *BaseInt; 118 ConstantExpr *BaseExpr; 119 RebasedConstantListType RebasedConstants; 120 }; 121 122 } // end namespace consthoist 123 124 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { 125 public: 126 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 127 128 // Glue for old PM. 129 bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, 130 BlockFrequencyInfo *BFI, BasicBlock &Entry, 131 ProfileSummaryInfo *PSI); 132 133 void cleanup() { 134 ClonedCastMap.clear(); 135 ConstIntCandVec.clear(); 136 for (auto MapEntry : ConstGEPCandMap) 137 MapEntry.second.clear(); 138 ConstGEPCandMap.clear(); 139 ConstIntInfoVec.clear(); 140 for (auto MapEntry : ConstGEPInfoMap) 141 MapEntry.second.clear(); 142 ConstGEPInfoMap.clear(); 143 } 144 145 private: 146 using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>; 147 using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>; 148 149 const TargetTransformInfo *TTI; 150 DominatorTree *DT; 151 BlockFrequencyInfo *BFI; 152 LLVMContext *Ctx; 153 const DataLayout *DL; 154 BasicBlock *Entry; 155 ProfileSummaryInfo *PSI; 156 bool OptForSize; 157 158 /// Keeps track of constant candidates found in the function. 159 using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; 160 using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>; 161 ConstCandVecType ConstIntCandVec; 162 GVCandVecMapType ConstGEPCandMap; 163 164 /// These are the final constants we decided to hoist. 165 using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>; 166 using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>; 167 ConstInfoVecType ConstIntInfoVec; 168 GVInfoVecMapType ConstGEPInfoMap; 169 170 /// Keep track of cast instructions we already cloned. 171 MapVector<Instruction *, Instruction *> ClonedCastMap; 172 173 void collectMatInsertPts( 174 const consthoist::RebasedConstantListType &RebasedConstants, 175 SmallVectorImpl<Instruction *> &MatInsertPts) const; 176 Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; 177 SetVector<Instruction *> 178 findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo, 179 const ArrayRef<Instruction *> MatInsertPts) const; 180 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 181 Instruction *Inst, unsigned Idx, 182 ConstantInt *ConstInt); 183 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 184 Instruction *Inst, unsigned Idx, 185 ConstantExpr *ConstExpr); 186 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 187 Instruction *Inst, unsigned Idx); 188 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 189 Instruction *Inst); 190 void collectConstantCandidates(Function &Fn); 191 void findAndMakeBaseConstant(ConstCandVecType::iterator S, 192 ConstCandVecType::iterator E, 193 SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec); 194 unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, 195 ConstCandVecType::iterator E, 196 ConstCandVecType::iterator &MaxCostItr); 197 // If BaseGV is nullptr, find base among Constant Integer candidates; 198 // otherwise find base among constant GEPs sharing BaseGV as base pointer. 199 void findBaseConstants(GlobalVariable *BaseGV); 200 201 /// A ConstantUser grouped with the Type and Constant adjustment. The user 202 /// will be adjusted by Offset. 203 struct UserAdjustment { 204 Constant *Offset; 205 Type *Ty; 206 Instruction *MatInsertPt; 207 const consthoist::ConstantUser User; 208 UserAdjustment(Constant *O, Type *T, Instruction *I, 209 consthoist::ConstantUser U) 210 : Offset(O), Ty(T), MatInsertPt(I), User(U) {} 211 }; 212 void emitBaseConstants(Instruction *Base, UserAdjustment *Adj); 213 // If BaseGV is nullptr, emit Constant Integer base; otherwise emit 214 // constant GEP base. 215 bool emitBaseConstants(GlobalVariable *BaseGV); 216 void deleteDeadCastInst() const; 217 }; 218 219 } // end namespace llvm 220 221 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 222