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 getIntImmCost 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/DenseMap.h" 40 #include "llvm/ADT/PointerUnion.h" 41 #include "llvm/ADT/SmallPtrSet.h" 42 #include "llvm/ADT/SmallVector.h" 43 #include "llvm/IR/PassManager.h" 44 #include <algorithm> 45 #include <vector> 46 47 namespace llvm { 48 49 class BasicBlock; 50 class BlockFrequencyInfo; 51 class Constant; 52 class ConstantInt; 53 class ConstantExpr; 54 class DominatorTree; 55 class Function; 56 class GlobalVariable; 57 class Instruction; 58 class ProfileSummaryInfo; 59 class TargetTransformInfo; 60 61 /// A private "module" namespace for types and utilities used by 62 /// ConstantHoisting. These are implementation details and should not be used by 63 /// clients. 64 namespace consthoist { 65 66 /// Keeps track of the user of a constant and the operand index where the 67 /// constant is used. 68 struct ConstantUser { 69 Instruction *Inst; 70 unsigned OpndIdx; 71 72 ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {} 73 }; 74 75 using ConstantUseListType = SmallVector<ConstantUser, 8>; 76 77 /// Keeps track of a constant candidate and its uses. 78 struct ConstantCandidate { 79 ConstantUseListType Uses; 80 // If the candidate is a ConstantExpr (currely only constant GEP expressions 81 // whose base pointers are GlobalVariables are supported), ConstInt records 82 // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 83 ConstantInt *ConstInt; 84 ConstantExpr *ConstExpr; 85 unsigned CumulativeCost = 0; 86 87 ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) : 88 ConstInt(ConstInt), ConstExpr(ConstExpr) {} 89 90 /// Add the user to the use list and update the cost. 91 void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { 92 CumulativeCost += Cost; 93 Uses.push_back(ConstantUser(Inst, Idx)); 94 } 95 }; 96 97 /// This represents a constant that has been rebased with respect to a 98 /// base constant. The difference to the base constant is recorded in Offset. 99 struct RebasedConstantInfo { 100 ConstantUseListType Uses; 101 Constant *Offset; 102 Type *Ty; 103 104 RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, 105 Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {} 106 }; 107 108 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; 109 110 /// A base constant and all its rebased constants. 111 struct ConstantInfo { 112 // If the candidate is a ConstantExpr (currely only constant GEP expressions 113 // whose base pointers are GlobalVariables are supported), ConstInt records 114 // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 115 ConstantInt *BaseInt; 116 ConstantExpr *BaseExpr; 117 RebasedConstantListType RebasedConstants; 118 }; 119 120 } // end namespace consthoist 121 122 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { 123 public: 124 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 125 126 // Glue for old PM. 127 bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, 128 BlockFrequencyInfo *BFI, BasicBlock &Entry, 129 ProfileSummaryInfo *PSI); 130 131 void cleanup() { 132 ClonedCastMap.clear(); 133 ConstIntCandVec.clear(); 134 for (auto MapEntry : ConstGEPCandMap) 135 MapEntry.second.clear(); 136 ConstGEPCandMap.clear(); 137 ConstIntInfoVec.clear(); 138 for (auto MapEntry : ConstGEPInfoMap) 139 MapEntry.second.clear(); 140 ConstGEPInfoMap.clear(); 141 } 142 143 private: 144 using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>; 145 using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>; 146 147 const TargetTransformInfo *TTI; 148 DominatorTree *DT; 149 BlockFrequencyInfo *BFI; 150 LLVMContext *Ctx; 151 const DataLayout *DL; 152 BasicBlock *Entry; 153 ProfileSummaryInfo *PSI; 154 155 /// Keeps track of constant candidates found in the function. 156 using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; 157 using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>; 158 ConstCandVecType ConstIntCandVec; 159 GVCandVecMapType ConstGEPCandMap; 160 161 /// These are the final constants we decided to hoist. 162 using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>; 163 using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>; 164 ConstInfoVecType ConstIntInfoVec; 165 GVInfoVecMapType ConstGEPInfoMap; 166 167 /// Keep track of cast instructions we already cloned. 168 SmallDenseMap<Instruction *, Instruction *> ClonedCastMap; 169 170 Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; 171 SmallPtrSet<Instruction *, 8> 172 findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const; 173 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 174 Instruction *Inst, unsigned Idx, 175 ConstantInt *ConstInt); 176 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 177 Instruction *Inst, unsigned Idx, 178 ConstantExpr *ConstExpr); 179 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 180 Instruction *Inst, unsigned Idx); 181 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 182 Instruction *Inst); 183 void collectConstantCandidates(Function &Fn); 184 void findAndMakeBaseConstant(ConstCandVecType::iterator S, 185 ConstCandVecType::iterator E, 186 SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec); 187 unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, 188 ConstCandVecType::iterator E, 189 ConstCandVecType::iterator &MaxCostItr); 190 // If BaseGV is nullptr, find base among Constant Integer candidates; 191 // otherwise find base among constant GEPs sharing BaseGV as base pointer. 192 void findBaseConstants(GlobalVariable *BaseGV); 193 void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty, 194 const consthoist::ConstantUser &ConstUser); 195 // If BaseGV is nullptr, emit Constant Integer base; otherwise emit 196 // constant GEP base. 197 bool emitBaseConstants(GlobalVariable *BaseGV); 198 void deleteDeadCastInst() const; 199 bool optimizeConstants(Function &Fn); 200 }; 201 202 } // end namespace llvm 203 204 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 205