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/DenseMap.h" 40 #include "llvm/ADT/MapVector.h" 41 #include "llvm/ADT/PointerUnion.h" 42 #include "llvm/ADT/SetVector.h" 43 #include "llvm/ADT/SmallPtrSet.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 ConstantUserConstantUser74 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) : ConstIntConstantCandidate90 ConstInt(ConstInt), ConstExpr(ConstExpr) {} 91 92 /// Add the user to the use list and update the cost. addUserConstantCandidate93 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, UsesRebasedConstantInfo107 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 cleanup()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 157 /// Keeps track of constant candidates found in the function. 158 using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; 159 using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>; 160 ConstCandVecType ConstIntCandVec; 161 GVCandVecMapType ConstGEPCandMap; 162 163 /// These are the final constants we decided to hoist. 164 using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>; 165 using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>; 166 ConstInfoVecType ConstIntInfoVec; 167 GVInfoVecMapType ConstGEPInfoMap; 168 169 /// Keep track of cast instructions we already cloned. 170 MapVector<Instruction *, Instruction *> ClonedCastMap; 171 172 Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; 173 SetVector<Instruction *> 174 findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const; 175 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 176 Instruction *Inst, unsigned Idx, 177 ConstantInt *ConstInt); 178 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 179 Instruction *Inst, unsigned Idx, 180 ConstantExpr *ConstExpr); 181 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 182 Instruction *Inst, unsigned Idx); 183 void collectConstantCandidates(ConstCandMapType &ConstCandMap, 184 Instruction *Inst); 185 void collectConstantCandidates(Function &Fn); 186 void findAndMakeBaseConstant(ConstCandVecType::iterator S, 187 ConstCandVecType::iterator E, 188 SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec); 189 unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, 190 ConstCandVecType::iterator E, 191 ConstCandVecType::iterator &MaxCostItr); 192 // If BaseGV is nullptr, find base among Constant Integer candidates; 193 // otherwise find base among constant GEPs sharing BaseGV as base pointer. 194 void findBaseConstants(GlobalVariable *BaseGV); 195 void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty, 196 const consthoist::ConstantUser &ConstUser); 197 // If BaseGV is nullptr, emit Constant Integer base; otherwise emit 198 // constant GEP base. 199 bool emitBaseConstants(GlobalVariable *BaseGV); 200 void deleteDeadCastInst() const; 201 }; 202 203 } // end namespace llvm 204 205 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 206