blob: 68989f9614bfdee33efb319af35f4394b1ee7016 [file] [log] [blame]
Stephen Hines951613a2020-06-09 21:04:07 -07001//===- 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/PostOrderIterator.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Analysis/InstructionPrecedenceTracking.h"
25#include "llvm/Analysis/MemoryDependenceAnalysis.h"
26#include "llvm/IR/Dominators.h"
27#include "llvm/IR/InstrTypes.h"
28#include "llvm/IR/PassManager.h"
29#include "llvm/IR/ValueHandle.h"
30#include "llvm/Support/Allocator.h"
31#include "llvm/Support/Compiler.h"
32#include <cstdint>
33#include <utility>
34#include <vector>
35
36namespace llvm {
37
38class AssumptionCache;
39class BasicBlock;
40class BranchInst;
41class CallInst;
42class Constant;
43class ExtractValueInst;
44class Function;
45class FunctionPass;
46class IntrinsicInst;
47class LoadInst;
48class LoopInfo;
49class OptimizationRemarkEmitter;
50class PHINode;
51class TargetLibraryInfo;
52class Value;
53
54/// A private "module" namespace for types and utilities used by GVN. These
55/// are implementation details and should not be used by clients.
56namespace gvn LLVM_LIBRARY_VISIBILITY {
57
58struct AvailableValue;
59struct AvailableValueInBlock;
60class GVNLegacyPass;
61
62} // end namespace gvn
63
64/// A set of parameters to control various transforms performed by GVN pass.
65// Each of the optional boolean parameters can be set to:
66/// true - enabling the transformation.
67/// false - disabling the transformation.
68/// None - relying on a global default.
69/// Intended use is to create a default object, modify parameters with
70/// additional setters and then pass it to GVN.
71struct GVNOptions {
72 Optional<bool> AllowPRE = None;
73 Optional<bool> AllowLoadPRE = None;
74 Optional<bool> AllowLoadInLoopPRE = None;
75 Optional<bool> AllowMemDep = None;
76
77 GVNOptions() = default;
78
79 /// Enables or disables PRE in GVN.
80 GVNOptions &setPRE(bool PRE) {
81 AllowPRE = PRE;
82 return *this;
83 }
84
85 /// Enables or disables PRE of loads in GVN.
86 GVNOptions &setLoadPRE(bool LoadPRE) {
87 AllowLoadPRE = LoadPRE;
88 return *this;
89 }
90
91 GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
92 AllowLoadInLoopPRE = LoadInLoopPRE;
93 return *this;
94 }
95
96 /// Enables or disables use of MemDepAnalysis.
97 GVNOptions &setMemDep(bool MemDep) {
98 AllowMemDep = MemDep;
99 return *this;
100 }
101};
102
103/// The core GVN pass object.
104///
105/// FIXME: We should have a good summary of the GVN algorithm implemented by
106/// this particular pass here.
107class GVN : public PassInfoMixin<GVN> {
108 GVNOptions Options;
109
110public:
111 struct Expression;
112
113 GVN(GVNOptions Options = {}) : Options(Options) {}
114
115 /// Run the pass over the function.
116 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
117
118 /// This removes the specified instruction from
119 /// our various maps and marks it for deletion.
120 void markInstructionForDeletion(Instruction *I) {
121 VN.erase(I);
122 InstrsToErase.push_back(I);
123 }
124
125 DominatorTree &getDominatorTree() const { return *DT; }
126 AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
127 MemoryDependenceResults &getMemDep() const { return *MD; }
128
129 bool isPREEnabled() const;
130 bool isLoadPREEnabled() const;
131 bool isLoadInLoopPREEnabled() const;
132 bool isMemDepEnabled() const;
133
134 /// This class holds the mapping between values and value numbers. It is used
135 /// as an efficient mechanism to determine the expression-wise equivalence of
136 /// two values.
137 class ValueTable {
138 DenseMap<Value *, uint32_t> valueNumbering;
139 DenseMap<Expression, uint32_t> expressionNumbering;
140
141 // Expressions is the vector of Expression. ExprIdx is the mapping from
142 // value number to the index of Expression in Expressions. We use it
143 // instead of a DenseMap because filling such mapping is faster than
144 // filling a DenseMap and the compile time is a little better.
145 uint32_t nextExprNumber = 0;
146
147 std::vector<Expression> Expressions;
148 std::vector<uint32_t> ExprIdx;
149
150 // Value number to PHINode mapping. Used for phi-translate in scalarpre.
151 DenseMap<uint32_t, PHINode *> NumberingPhi;
152
153 // Cache for phi-translate in scalarpre.
154 using PhiTranslateMap =
155 DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
156 PhiTranslateMap PhiTranslateTable;
157
158 AliasAnalysis *AA = nullptr;
159 MemoryDependenceResults *MD = nullptr;
160 DominatorTree *DT = nullptr;
161
162 uint32_t nextValueNumber = 1;
163
164 Expression createExpr(Instruction *I);
165 Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
166 Value *LHS, Value *RHS);
167 Expression createExtractvalueExpr(ExtractValueInst *EI);
168 uint32_t lookupOrAddCall(CallInst *C);
169 uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
170 uint32_t Num, GVN &Gvn);
171 bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
172 const BasicBlock *PhiBlock, GVN &Gvn);
173 std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
174 bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
175
176 public:
177 ValueTable();
178 ValueTable(const ValueTable &Arg);
179 ValueTable(ValueTable &&Arg);
180 ~ValueTable();
181 ValueTable &operator=(const ValueTable &Arg);
182
183 uint32_t lookupOrAdd(Value *V);
184 uint32_t lookup(Value *V, bool Verify = true) const;
185 uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
186 Value *LHS, Value *RHS);
187 uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
188 uint32_t Num, GVN &Gvn);
189 void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
190 bool exists(Value *V) const;
191 void add(Value *V, uint32_t num);
192 void clear();
193 void erase(Value *v);
194 void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
195 AliasAnalysis *getAliasAnalysis() const { return AA; }
196 void setMemDep(MemoryDependenceResults *M) { MD = M; }
197 void setDomTree(DominatorTree *D) { DT = D; }
198 uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
199 void verifyRemoved(const Value *) const;
200 };
201
202private:
203 friend class gvn::GVNLegacyPass;
204 friend struct DenseMapInfo<Expression>;
205
206 MemoryDependenceResults *MD = nullptr;
207 DominatorTree *DT = nullptr;
208 const TargetLibraryInfo *TLI = nullptr;
209 AssumptionCache *AC = nullptr;
210 SetVector<BasicBlock *> DeadBlocks;
211 OptimizationRemarkEmitter *ORE = nullptr;
212 ImplicitControlFlowTracking *ICF = nullptr;
213 LoopInfo *LI = nullptr;
214
215 ValueTable VN;
216
217 /// A mapping from value numbers to lists of Value*'s that
218 /// have that value number. Use findLeader to query it.
219 struct LeaderTableEntry {
220 Value *Val;
221 const BasicBlock *BB;
222 LeaderTableEntry *Next;
223 };
224 DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
225 BumpPtrAllocator TableAllocator;
226
227 // Block-local map of equivalent values to their leader, does not
228 // propagate to any successors. Entries added mid-block are applied
229 // to the remaining instructions in the block.
230 SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
231 SmallVector<Instruction *, 8> InstrsToErase;
232
233 // Map the block to reversed postorder traversal number. It is used to
234 // find back edge easily.
235 DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
236
237 // This is set 'true' initially and also when new blocks have been added to
238 // the function being analyzed. This boolean is used to control the updating
239 // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
240 bool InvalidBlockRPONumbers = true;
241
242 using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
243 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
244 using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
245
246 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
247 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
248 MemoryDependenceResults *RunMD, LoopInfo *LI,
249 OptimizationRemarkEmitter *ORE);
250
251 /// Push a new Value to the LeaderTable onto the list for its value number.
252 void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
253 LeaderTableEntry &Curr = LeaderTable[N];
254 if (!Curr.Val) {
255 Curr.Val = V;
256 Curr.BB = BB;
257 return;
258 }
259
260 LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
261 Node->Val = V;
262 Node->BB = BB;
263 Node->Next = Curr.Next;
264 Curr.Next = Node;
265 }
266
267 /// Scan the list of values corresponding to a given
268 /// value number, and remove the given instruction if encountered.
269 void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
270 LeaderTableEntry *Prev = nullptr;
271 LeaderTableEntry *Curr = &LeaderTable[N];
272
273 while (Curr && (Curr->Val != I || Curr->BB != BB)) {
274 Prev = Curr;
275 Curr = Curr->Next;
276 }
277
278 if (!Curr)
279 return;
280
281 if (Prev) {
282 Prev->Next = Curr->Next;
283 } else {
284 if (!Curr->Next) {
285 Curr->Val = nullptr;
286 Curr->BB = nullptr;
287 } else {
288 LeaderTableEntry *Next = Curr->Next;
289 Curr->Val = Next->Val;
290 Curr->BB = Next->BB;
291 Curr->Next = Next->Next;
292 }
293 }
294 }
295
296 // List of critical edges to be split between iterations.
297 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
298
299 // Helper functions of redundant load elimination
300 bool processLoad(LoadInst *L);
301 bool processNonLocalLoad(LoadInst *L);
302 bool processAssumeIntrinsic(IntrinsicInst *II);
303
304 /// Given a local dependency (Def or Clobber) determine if a value is
305 /// available for the load. Returns true if an value is known to be
306 /// available and populates Res. Returns false otherwise.
307 bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
308 Value *Address, gvn::AvailableValue &Res);
309
310 /// Given a list of non-local dependencies, determine if a value is
311 /// available for the load in each specified block. If it is, add it to
312 /// ValuesPerBlock. If not, add it to UnavailableBlocks.
313 void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
314 AvailValInBlkVect &ValuesPerBlock,
315 UnavailBlkVect &UnavailableBlocks);
316
317 bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
318 UnavailBlkVect &UnavailableBlocks);
319
320 // Other helper routines
321 bool processInstruction(Instruction *I);
322 bool processBlock(BasicBlock *BB);
323 void dump(DenseMap<uint32_t, Value *> &d) const;
324 bool iterateOnFunction(Function &F);
325 bool performPRE(Function &F);
326 bool performScalarPRE(Instruction *I);
327 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
328 BasicBlock *Curr, unsigned int ValNo);
329 Value *findLeader(const BasicBlock *BB, uint32_t num);
330 void cleanupGlobalSets();
331 void fillImplicitControlFlowInfo(BasicBlock *BB);
332 void verifyRemoved(const Instruction *I) const;
333 bool splitCriticalEdges();
334 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
335 bool replaceOperandsForInBlockEquality(Instruction *I) const;
336 bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
337 bool DominatesByEdge);
338 bool processFoldableCondBr(BranchInst *BI);
339 void addDeadBlock(BasicBlock *BB);
340 void assignValNumForDeadCode();
341 void assignBlockRPONumber(Function &F);
342};
343
344/// Create a legacy GVN pass. This also allows parameterizing whether or not
345/// MemDep is enabled.
346FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);
347
348/// A simple and fast domtree-based GVN pass to hoist common expressions
349/// from sibling branches.
350struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
351 /// Run the pass over the function.
352 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
353};
354
355/// Uses an "inverted" value numbering to decide the similarity of
356/// expressions and sinks similar expressions into successors.
357struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
358 /// Run the pass over the function.
359 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
360};
361
362} // end namespace llvm
363
364#endif // LLVM_TRANSFORMS_SCALAR_GVN_H