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
49namespace llvm {
50
51class BasicBlock;
52class BlockFrequencyInfo;
53class Constant;
54class ConstantInt;
55class ConstantExpr;
56class DominatorTree;
57class Function;
58class GlobalVariable;
59class Instruction;
60class ProfileSummaryInfo;
61class 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.
66namespace consthoist {
67
68/// Keeps track of the user of a constant and the operand index where the
69/// constant is used.
70struct ConstantUser {
71 Instruction *Inst;
72 unsigned OpndIdx;
73
74 ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
75};
76
77using ConstantUseListType = SmallVector<ConstantUser, 8>;
78
79/// Keeps track of a constant candidate and its uses.
80struct 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.
101struct 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
110using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
111
112/// A base constant and all its rebased constants.
113struct 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
124class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
125public:
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
145private:
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

source code of llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h