LLVM 20.0.0git
GVN.h
Go to the documentation of this file.
1//===- GVN.h - Eliminate redundant values and loads -------------*- 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/// \file
9/// This file provides the interface for LLVM's Global Value Numbering pass
10/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
11/// PRE and dead load elimination.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
16#define LLVM_TRANSFORMS_SCALAR_GVN_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/SetVector.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/InstrTypes.h"
24#include "llvm/IR/PassManager.h"
25#include "llvm/IR/ValueHandle.h"
28#include <cstdint>
29#include <optional>
30#include <utility>
31#include <vector>
32
33namespace llvm {
34
35class AAResults;
36class AssumeInst;
37class AssumptionCache;
38class BasicBlock;
39class BranchInst;
40class CallInst;
41class ExtractValueInst;
42class Function;
43class FunctionPass;
44class GetElementPtrInst;
45class ImplicitControlFlowTracking;
46class LoadInst;
47class LoopInfo;
48class MemDepResult;
49class MemoryDependenceResults;
50class MemorySSA;
51class MemorySSAUpdater;
52class NonLocalDepResult;
53class OptimizationRemarkEmitter;
54class PHINode;
55class TargetLibraryInfo;
56class Value;
57/// A private "module" namespace for types and utilities used by GVN. These
58/// are implementation details and should not be used by clients.
60
61struct AvailableValue;
63class GVNLegacyPass;
64
65} // end namespace gvn
66
67/// A set of parameters to control various transforms performed by GVN pass.
68// Each of the optional boolean parameters can be set to:
69/// true - enabling the transformation.
70/// false - disabling the transformation.
71/// None - relying on a global default.
72/// Intended use is to create a default object, modify parameters with
73/// additional setters and then pass it to GVN.
74struct GVNOptions {
75 std::optional<bool> AllowPRE;
76 std::optional<bool> AllowLoadPRE;
77 std::optional<bool> AllowLoadInLoopPRE;
78 std::optional<bool> AllowLoadPRESplitBackedge;
79 std::optional<bool> AllowMemDep;
80 std::optional<bool> AllowMemorySSA;
81
82 GVNOptions() = default;
83
84 /// Enables or disables PRE in GVN.
85 GVNOptions &setPRE(bool PRE) {
86 AllowPRE = PRE;
87 return *this;
88 }
89
90 /// Enables or disables PRE of loads in GVN.
91 GVNOptions &setLoadPRE(bool LoadPRE) {
92 AllowLoadPRE = LoadPRE;
93 return *this;
94 }
95
96 GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
97 AllowLoadInLoopPRE = LoadInLoopPRE;
98 return *this;
99 }
100
101 /// Enables or disables PRE of loads in GVN.
102 GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
103 AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
104 return *this;
105 }
106
107 /// Enables or disables use of MemDepAnalysis.
108 GVNOptions &setMemDep(bool MemDep) {
109 AllowMemDep = MemDep;
110 return *this;
111 }
112
113 /// Enables or disables use of MemorySSA.
114 GVNOptions &setMemorySSA(bool MemSSA) {
115 AllowMemorySSA = MemSSA;
116 return *this;
117 }
118};
119
120/// The core GVN pass object.
121///
122/// FIXME: We should have a good summary of the GVN algorithm implemented by
123/// this particular pass here.
124class GVNPass : public PassInfoMixin<GVNPass> {
125 GVNOptions Options;
126
127public:
128 struct Expression;
129
131
132 /// Run the pass over the function.
133 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
134
135 void printPipeline(raw_ostream &OS,
136 function_ref<StringRef(StringRef)> MapClassName2PassName);
137
138 /// This removes the specified instruction from
139 /// our various maps and marks it for deletion.
141 VN.erase(I);
142 InstrsToErase.push_back(I);
143 }
144
145 DominatorTree &getDominatorTree() const { return *DT; }
147 MemoryDependenceResults &getMemDep() const { return *MD; }
148
149 bool isPREEnabled() const;
150 bool isLoadPREEnabled() const;
151 bool isLoadInLoopPREEnabled() const;
153 bool isMemDepEnabled() const;
154 bool isMemorySSAEnabled() const;
155
156 /// This class holds the mapping between values and value numbers. It is used
157 /// as an efficient mechanism to determine the expression-wise equivalence of
158 /// two values.
160 DenseMap<Value *, uint32_t> valueNumbering;
161 DenseMap<Expression, uint32_t> expressionNumbering;
162
163 // Expressions is the vector of Expression. ExprIdx is the mapping from
164 // value number to the index of Expression in Expressions. We use it
165 // instead of a DenseMap because filling such mapping is faster than
166 // filling a DenseMap and the compile time is a little better.
167 uint32_t nextExprNumber = 0;
168
169 std::vector<Expression> Expressions;
170 std::vector<uint32_t> ExprIdx;
171
172 // Value number to PHINode mapping. Used for phi-translate in scalarpre.
174
175 // Cache for phi-translate in scalarpre.
176 using PhiTranslateMap =
178 PhiTranslateMap PhiTranslateTable;
179
180 AAResults *AA = nullptr;
181 MemoryDependenceResults *MD = nullptr;
182 DominatorTree *DT = nullptr;
183
184 uint32_t nextValueNumber = 1;
185
186 Expression createExpr(Instruction *I);
187 Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
188 Value *LHS, Value *RHS);
189 Expression createExtractvalueExpr(ExtractValueInst *EI);
190 Expression createGEPExpr(GetElementPtrInst *GEP);
191 uint32_t lookupOrAddCall(CallInst *C);
192 uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
193 uint32_t Num, GVNPass &Gvn);
194 bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
195 const BasicBlock *PhiBlock, GVNPass &Gvn);
196 std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
197 bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
198
199 public:
205
207 uint32_t lookup(Value *V, bool Verify = true) const;
208 uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
209 Value *LHS, Value *RHS);
210 uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
211 uint32_t Num, GVNPass &Gvn);
212 void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
213 bool exists(Value *V) const;
214 void add(Value *V, uint32_t num);
215 void clear();
216 void erase(Value *v);
217 void setAliasAnalysis(AAResults *A) { AA = A; }
218 AAResults *getAliasAnalysis() const { return AA; }
220 void setDomTree(DominatorTree *D) { DT = D; }
221 uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
222 void verifyRemoved(const Value *) const;
223 };
224
225private:
226 friend class gvn::GVNLegacyPass;
227 friend struct DenseMapInfo<Expression>;
228
229 MemoryDependenceResults *MD = nullptr;
230 DominatorTree *DT = nullptr;
231 const TargetLibraryInfo *TLI = nullptr;
232 AssumptionCache *AC = nullptr;
233 SetVector<BasicBlock *> DeadBlocks;
234 OptimizationRemarkEmitter *ORE = nullptr;
235 ImplicitControlFlowTracking *ICF = nullptr;
236 LoopInfo *LI = nullptr;
237 MemorySSAUpdater *MSSAU = nullptr;
238
239 ValueTable VN;
240
241 /// A mapping from value numbers to lists of Value*'s that
242 /// have that value number. Use findLeader to query it.
243 class LeaderMap {
244 public:
248 };
249
250 private:
251 struct LeaderListNode {
252 LeaderTableEntry Entry;
253 LeaderListNode *Next;
254 };
256 BumpPtrAllocator TableAllocator;
257
258 public:
260 const LeaderListNode *Current;
261
262 public:
263 using iterator_category = std::forward_iterator_tag;
265 using difference_type = std::ptrdiff_t;
268
269 leader_iterator(const LeaderListNode *C) : Current(C) {}
271 assert(Current && "Dereferenced end of leader list!");
272 Current = Current->Next;
273 return *this;
274 }
275 bool operator==(const leader_iterator &Other) const {
276 return Current == Other.Current;
277 }
278 bool operator!=(const leader_iterator &Other) const {
279 return Current != Other.Current;
280 }
281 reference operator*() const { return Current->Entry; }
282 };
283
285 auto I = NumToLeaders.find(N);
286 if (I == NumToLeaders.end()) {
287 return iterator_range(leader_iterator(nullptr),
288 leader_iterator(nullptr));
289 }
290
291 return iterator_range(leader_iterator(&I->second),
292 leader_iterator(nullptr));
293 }
294
295 void insert(uint32_t N, Value *V, const BasicBlock *BB);
296 void erase(uint32_t N, Instruction *I, const BasicBlock *BB);
297 void verifyRemoved(const Value *Inst) const;
298 void clear() {
299 NumToLeaders.clear();
300 TableAllocator.Reset();
301 }
302 };
303 LeaderMap LeaderTable;
304
305 // Block-local map of equivalent values to their leader, does not
306 // propagate to any successors. Entries added mid-block are applied
307 // to the remaining instructions in the block.
308 SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
309 SmallVector<Instruction *, 8> InstrsToErase;
310
311 // Map the block to reversed postorder traversal number. It is used to
312 // find back edge easily.
313 DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
314
315 // This is set 'true' initially and also when new blocks have been added to
316 // the function being analyzed. This boolean is used to control the updating
317 // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
318 bool InvalidBlockRPONumbers = true;
319
320 using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
321 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
322 using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
323
324 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
325 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
326 MemoryDependenceResults *RunMD, LoopInfo &LI,
327 OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
328
329 // List of critical edges to be split between iterations.
330 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
331
332 // Helper functions of redundant load elimination
333 bool processLoad(LoadInst *L);
334 bool processNonLocalLoad(LoadInst *L);
335 bool processAssumeIntrinsic(AssumeInst *II);
336
337 /// Given a local dependency (Def or Clobber) determine if a value is
338 /// available for the load.
339 std::optional<gvn::AvailableValue>
340 AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);
341
342 /// Given a list of non-local dependencies, determine if a value is
343 /// available for the load in each specified block. If it is, add it to
344 /// ValuesPerBlock. If not, add it to UnavailableBlocks.
345 void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
346 AvailValInBlkVect &ValuesPerBlock,
347 UnavailBlkVect &UnavailableBlocks);
348
349 /// Given a critical edge from Pred to LoadBB, find a load instruction
350 /// which is identical to Load from another successor of Pred.
351 LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
352 LoadInst *Load);
353
354 bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
355 UnavailBlkVect &UnavailableBlocks);
356
357 /// Try to replace a load which executes on each loop iteraiton with Phi
358 /// translation of load in preheader and load(s) in conditionally executed
359 /// paths.
360 bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
361 UnavailBlkVect &UnavailableBlocks);
362
363 /// Eliminates partially redundant \p Load, replacing it with \p
364 /// AvailableLoads (connected by Phis if needed).
365 void eliminatePartiallyRedundantLoad(
366 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
367 MapVector<BasicBlock *, Value *> &AvailableLoads,
368 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
369
370 // Other helper routines
371 bool processInstruction(Instruction *I);
372 bool processBlock(BasicBlock *BB);
373 void dump(DenseMap<uint32_t, Value *> &d) const;
374 bool iterateOnFunction(Function &F);
375 bool performPRE(Function &F);
376 bool performScalarPRE(Instruction *I);
377 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
378 BasicBlock *Curr, unsigned int ValNo);
379 Value *findLeader(const BasicBlock *BB, uint32_t num);
380 void cleanupGlobalSets();
381 void removeInstruction(Instruction *I);
382 void verifyRemoved(const Instruction *I) const;
383 bool splitCriticalEdges();
384 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
385 bool replaceOperandsForInBlockEquality(Instruction *I) const;
386 bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
387 bool DominatesByEdge);
388 bool processFoldableCondBr(BranchInst *BI);
389 void addDeadBlock(BasicBlock *BB);
390 void assignValNumForDeadCode();
391 void assignBlockRPONumber(Function &F);
392};
393
394/// Create a legacy GVN pass.
395FunctionPass *createGVNPass();
396
397/// A simple and fast domtree-based GVN pass to hoist common expressions
398/// from sibling branches.
399struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
400 /// Run the pass over the function.
402};
403
404/// Uses an "inverted" value numbering to decide the similarity of
405/// expressions and sinks similar expressions into successors.
406struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
407 /// Run the pass over the function.
409};
410
411} // end namespace llvm
412
413#endif // LLVM_TRANSFORMS_SCALAR_GVN_H
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_LIBRARY_VISIBILITY_NAMESPACE
Definition: Compiler.h:139
This file defines the DenseMap class.
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1960
Hexagon Common GEP
This header defines various interfaces for pass management in LLVM.
static LVOptions Options
Definition: LVOptions.cpp:25
#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.
uint64_t IntrinsicInst * II
ppc ctr loops PowerPC CTR Loops Verify
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
Value * RHS
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:673
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:156
iterator end()
Definition: DenseMap.h:84
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This instruction extracts a struct member or array element value from an aggregate value.
std::forward_iterator_tag iterator_category
Definition: GVN.h:263
bool operator==(const leader_iterator &Other) const
Definition: GVN.h:275
bool operator!=(const leader_iterator &Other) const
Definition: GVN.h:278
leader_iterator(const LeaderListNode *C)
Definition: GVN.h:269
leader_iterator & operator++()
Definition: GVN.h:270
This class holds the mapping between values and value numbers.
Definition: GVN.h:159
ValueTable(ValueTable &&Arg)
uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
Definition: GVN.cpp:702
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:221
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
Definition: GVN.cpp:610
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:689
ValueTable & operator=(const ValueTable &Arg)
void setAliasAnalysis(AAResults *A)
Definition: GVN.h:217
void clear()
Remove all entries from the ValueTable.
Definition: GVN.cpp:710
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:604
ValueTable(const ValueTable &Arg)
AAResults * getAliasAnalysis() const
Definition: GVN.h:218
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
Definition: GVN.cpp:2246
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:219
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:722
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
Definition: GVN.cpp:473
void setDomTree(DominatorTree *D)
Definition: GVN.h:220
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
Definition: GVN.cpp:2349
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:732
The core GVN pass object.
Definition: GVN.h:124
bool isPREEnabled() const
Definition: GVN.cpp:804
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:829
AAResults * getAliasAnalysis() const
Definition: GVN.h:146
bool isLoadPREEnabled() const
Definition: GVN.cpp:808
GVNPass(GVNOptions Options={})
Definition: GVN.h:130
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: GVN.cpp:861
bool isMemorySSAEnabled() const
Definition: GVN.cpp:825
DominatorTree & getDominatorTree() const
Definition: GVN.h:145
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:812
bool isLoadPRESplitBackedgeEnabled() const
Definition: GVN.cpp:816
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:140
bool isMemDepEnabled() const
Definition: GVN.cpp:821
MemoryDependenceResults & getMemDep() const
Definition: GVN.h:147
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:933
This class allows to keep track on instructions with implicit control flow.
Provides a lazy, caching interface for making common memory aliasing information queries,...
The optimization diagnostic interface.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
A vector that has set insertion semantics.
Definition: SetVector.h:57
void push_back(const T &Elt)
Definition: SmallVector.h:413
Provides information about what library functions are available for the current target.
LLVM Value Representation.
Definition: Value.h:74
A range adaptor for a pair of iterators.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:546
@ Other
Any other memory.
FunctionPass * createGVNPass()
Create a legacy GVN pass.
Definition: GVN.cpp:3374
#define N
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:52
A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.
Definition: GVN.h:399
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1203
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:74
GVNOptions & setLoadPRE(bool LoadPRE)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:91
std::optional< bool > AllowLoadPRESplitBackedge
Definition: GVN.h:78
GVNOptions & setPRE(bool PRE)
Enables or disables PRE in GVN.
Definition: GVN.h:85
GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)
Definition: GVN.h:96
std::optional< bool > AllowPRE
Definition: GVN.h:75
std::optional< bool > AllowLoadInLoopPRE
Definition: GVN.h:77
std::optional< bool > AllowMemDep
Definition: GVN.h:79
GVNOptions & setMemDep(bool MemDep)
Enables or disables use of MemDepAnalysis.
Definition: GVN.h:108
std::optional< bool > AllowLoadPRE
Definition: GVN.h:76
GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)
Enables or disables PRE of loads in GVN.
Definition: GVN.h:102
std::optional< bool > AllowMemorySSA
Definition: GVN.h:80
GVNOptions()=default
GVNOptions & setMemorySSA(bool MemSSA)
Enables or disables use of MemorySSA.
Definition: GVN.h:114
Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...
Definition: GVN.h:406
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNSink.cpp:935
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
Definition: GVN.cpp:295
Represents a particular available value that we know how to materialize.
Definition: GVN.cpp:198