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