LLVM  15.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/DenseMap.h"
40 #include "llvm/ADT/MapVector.h"
41 #include "llvm/ADT/PointerUnion.h"
42 #include "llvm/ADT/SetVector.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/IR/PassManager.h"
45 #include <algorithm>
46 #include <vector>
47 
48 namespace llvm {
49 
50 class BasicBlock;
51 class BlockFrequencyInfo;
52 class Constant;
53 class ConstantInt;
54 class ConstantExpr;
55 class DominatorTree;
56 class Function;
57 class GlobalVariable;
58 class Instruction;
59 class ProfileSummaryInfo;
60 class TargetTransformInfo;
61 
62 /// A private "module" namespace for types and utilities used by
63 /// ConstantHoisting. These are implementation details and should not be used by
64 /// clients.
65 namespace consthoist {
66 
67 /// Keeps track of the user of a constant and the operand index where the
68 /// constant is used.
69 struct ConstantUser {
71  unsigned OpndIdx;
72 
73  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
74 };
75 
77 
78 /// Keeps track of a constant candidate and its uses.
81  // If the candidate is a ConstantExpr (currely only constant GEP expressions
82  // whose base pointers are GlobalVariables are supported), ConstInt records
83  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
86  unsigned CumulativeCost = 0;
87 
90 
91  /// Add the user to the use list and update the cost.
92  void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
93  CumulativeCost += Cost;
94  Uses.push_back(ConstantUser(Inst, Idx));
95  }
96 };
97 
98 /// This represents a constant that has been rebased with respect to a
99 /// base constant. The difference to the base constant is recorded in Offset.
104 
106  Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
107 };
108 
110 
111 /// A base constant and all its rebased constants.
112 struct ConstantInfo {
113  // If the candidate is a ConstantExpr (currely only constant GEP expressions
114  // whose base pointers are GlobalVariables are supported), ConstInt records
115  // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
119 };
120 
121 } // end namespace consthoist
122 
123 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
124 public:
126 
127  // Glue for old PM.
129  BlockFrequencyInfo *BFI, BasicBlock &Entry,
130  ProfileSummaryInfo *PSI);
131 
132  void cleanup() {
133  ClonedCastMap.clear();
134  ConstIntCandVec.clear();
135  for (auto MapEntry : ConstGEPCandMap)
136  MapEntry.second.clear();
137  ConstGEPCandMap.clear();
138  ConstIntInfoVec.clear();
139  for (auto MapEntry : ConstGEPInfoMap)
140  MapEntry.second.clear();
141  ConstGEPInfoMap.clear();
142  }
143 
144 private:
145  using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
146  using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
147 
148  const TargetTransformInfo *TTI;
149  DominatorTree *DT;
150  BlockFrequencyInfo *BFI;
151  LLVMContext *Ctx;
152  const DataLayout *DL;
153  BasicBlock *Entry;
154  ProfileSummaryInfo *PSI;
155 
156  /// Keeps track of constant candidates found in the function.
157  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
158  using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>;
159  ConstCandVecType ConstIntCandVec;
160  GVCandVecMapType ConstGEPCandMap;
161 
162  /// These are the final constants we decided to hoist.
163  using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
164  using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
165  ConstInfoVecType ConstIntInfoVec;
166  GVInfoVecMapType ConstGEPInfoMap;
167 
168  /// Keep track of cast instructions we already cloned.
170 
171  Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
173  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
174  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
175  Instruction *Inst, unsigned Idx,
176  ConstantInt *ConstInt);
177  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
178  Instruction *Inst, unsigned Idx,
179  ConstantExpr *ConstExpr);
180  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
181  Instruction *Inst, unsigned Idx);
182  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
183  Instruction *Inst);
184  void collectConstantCandidates(Function &Fn);
185  void findAndMakeBaseConstant(ConstCandVecType::iterator S,
186  ConstCandVecType::iterator E,
188  unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
189  ConstCandVecType::iterator E,
190  ConstCandVecType::iterator &MaxCostItr);
191  // If BaseGV is nullptr, find base among Constant Integer candidates;
192  // otherwise find base among constant GEPs sharing BaseGV as base pointer.
193  void findBaseConstants(GlobalVariable *BaseGV);
194  void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
195  const consthoist::ConstantUser &ConstUser);
196  // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
197  // constant GEP base.
198  bool emitBaseConstants(GlobalVariable *BaseGV);
199  void deleteDeadCastInst() const;
200 };
201 
202 } // end namespace llvm
203 
204 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
llvm::consthoist::ConstantUser::ConstantUser
ConstantUser(Instruction *Inst, unsigned Idx)
Definition: ConstantHoisting.h:73
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::consthoist::ConstantCandidate
Keeps track of a constant candidate and its uses.
Definition: ConstantHoisting.h:79
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::consthoist::ConstantInfo::RebasedConstants
RebasedConstantListType RebasedConstants
Definition: ConstantHoisting.h:118
llvm::consthoist::RebasedConstantInfo::Offset
Constant * Offset
Definition: ConstantHoisting.h:102
llvm::SmallVector< ConstantUser, 8 >
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
MapVector.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::MapVector< GlobalVariable *, ConstCandVecType >
consthoist
consthoist
Definition: ConstantHoisting.cpp:136
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::ConstantHoistingPass::runImpl
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, BlockFrequencyInfo *BFI, BasicBlock &Entry, ProfileSummaryInfo *PSI)
Optimize expensive integer constants in the given function.
Definition: ConstantHoisting.cpp:951
llvm::consthoist::ConstantUser::OpndIdx
unsigned OpndIdx
Definition: ConstantHoisting.h:71
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::ConstantHoistingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ConstantHoisting.cpp:990
llvm::consthoist::ConstantCandidate::CumulativeCost
unsigned CumulativeCost
Definition: ConstantHoisting.h:86
llvm::Instruction
Definition: Instruction.h:42
llvm::consthoist::ConstantCandidate::ConstExpr
ConstantExpr * ConstExpr
Definition: ConstantHoisting.h:85
llvm::consthoist::ConstantCandidate::addUser
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost)
Add the user to the use list and update the cost.
Definition: ConstantHoisting.h:92
llvm::consthoist::ConstantInfo::BaseExpr
ConstantExpr * BaseExpr
Definition: ConstantHoisting.h:117
llvm::consthoist::ConstantUser
Keeps track of the user of a constant and the operand index where the constant is used.
Definition: ConstantHoisting.h:69
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::consthoist::ConstantInfo::BaseInt
ConstantInt * BaseInt
Definition: ConstantHoisting.h:116
llvm::consthoist::RebasedConstantInfo::RebasedConstantInfo
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, Type *Ty=nullptr)
Definition: ConstantHoisting.h:105
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::DenseMap
Definition: DenseMap.h:716
llvm::move
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:1665
llvm::ConstantHoistingPass::cleanup
void cleanup()
Definition: ConstantHoisting.h:132
PointerUnion.h
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::consthoist::ConstantCandidate::Uses
ConstantUseListType Uses
Definition: ConstantHoisting.h:80
llvm::consthoist::RebasedConstantInfo::Ty
Type * Ty
Definition: ConstantHoisting.h:103
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::consthoist::ConstantInfo
A base constant and all its rebased constants.
Definition: ConstantHoisting.h:112
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:112
llvm::consthoist::RebasedConstantInfo::Uses
ConstantUseListType Uses
Definition: ConstantHoisting.h:101
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:971
std
Definition: BitVector.h:851
llvm::consthoist::ConstantCandidate::ConstInt
ConstantInt * ConstInt
Definition: ConstantHoisting.h:84
PassManager.h
llvm::consthoist::ConstantCandidate::ConstantCandidate
ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr)
Definition: ConstantHoisting.h:88
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::consthoist::ConstantUser::Inst
Instruction * Inst
Definition: ConstantHoisting.h:70
SmallVector.h
llvm::consthoist::RebasedConstantInfo
This represents a constant that has been rebased with respect to a base constant.
Definition: ConstantHoisting.h:100
llvm::SmallVectorImpl< consthoist::ConstantInfo >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::ConstantHoistingPass
Definition: ConstantHoisting.h:123
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58