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.
#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 header defines various interfaces for pass management in LLVM.
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:1097
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:81
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:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
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:1856
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)