LLVM 20.0.0git
ConstantHoisting.h
Go to the documentation of this file.
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"
43#include "llvm/ADT/SetVector.h"
45#include "llvm/IR/BasicBlock.h"
46#include "llvm/IR/PassManager.h"
47#include <algorithm>
48#include <vector>
49
50namespace llvm {
51
52class BasicBlock;
53class BlockFrequencyInfo;
54class Constant;
55class ConstantInt;
56class ConstantExpr;
57class DominatorTree;
58class Function;
59class GlobalVariable;
60class Instruction;
61class ProfileSummaryInfo;
62class TargetTransformInfo;
63class 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.
68namespace consthoist {
69
70/// Keeps track of the user of a constant and the operand index where the
71/// constant is used.
74 unsigned OpndIdx;
75
77};
78
80
81/// Keeps track of a constant candidate and its 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.
89 unsigned CumulativeCost = 0;
90
93
94 /// Add the user to the use list and update the cost.
95 void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
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.
107
109 Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
110};
111
113
114/// A base constant and all its rebased constants.
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.
122};
123
124} // end namespace consthoist
125
126class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
127public:
129
130 // Glue for old PM.
132 BlockFrequencyInfo *BFI, BasicBlock &Entry,
133 ProfileSummaryInfo *PSI);
134
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
147private:
148 using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
149 using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
150
152 DominatorTree *DT;
154 LLVMContext *Ctx;
155 const DataLayout *DL;
156 BasicBlock *Entry;
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.
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,
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;
211 UserAdjustment(Constant *O, Type *T, BasicBlock::iterator I,
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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
This file defines the PointerUnion class, which is a discriminated union of pointer types.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1108
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, BlockFrequencyInfo *BFI, BasicBlock &Entry, ProfileSummaryInfo *PSI)
Optimize expensive integer constants in the given function.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This is an important base class in LLVM.
Definition: Constant.h:42
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:118
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
Analysis providing profile information.
A vector that has set insertion semantics.
Definition: SetVector.h:57
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
void push_back(const T &Elt)
Definition: SmallVector.h:413
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1873
InstructionCost Cost
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
Keeps track of a constant candidate and its uses.
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost)
Add the user to the use list and update the cost.
ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr)
A base constant and all its rebased constants.
RebasedConstantListType RebasedConstants
Keeps track of the user of a constant and the operand index where the constant is used.
ConstantUser(Instruction *Inst, unsigned Idx)
This represents a constant that has been rebased with respect to a base constant.
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, Type *Ty=nullptr)