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