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(Elt: 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 | |