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