File: | lib/Transforms/Scalar/NewGVN.cpp |
Warning: | line 190, column 7 Forming reference to null pointer |
1 | //===---- NewGVN.cpp - Global Value Numbering Pass --------------*- 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 implements the new LLVM's Global Value Numbering pass. | |||
11 | /// GVN partitions values computed by a function into congruence classes. | |||
12 | /// Values ending up in the same congruence class are guaranteed to be the same | |||
13 | /// for every execution of the program. In that respect, congruency is a | |||
14 | /// compile-time approximation of equivalence of values at runtime. | |||
15 | /// The algorithm implemented here uses a sparse formulation and it's based | |||
16 | /// on the ideas described in the paper: | |||
17 | /// "A Sparse Algorithm for Predicated Global Value Numbering" from | |||
18 | /// Karthik Gargi. | |||
19 | /// | |||
20 | /// A brief overview of the algorithm: The algorithm is essentially the same as | |||
21 | /// the standard RPO value numbering algorithm (a good reference is the paper | |||
22 | /// "SCC based value numbering" by L. Taylor Simpson) with one major difference: | |||
23 | /// The RPO algorithm proceeds, on every iteration, to process every reachable | |||
24 | /// block and every instruction in that block. This is because the standard RPO | |||
25 | /// algorithm does not track what things have the same value number, it only | |||
26 | /// tracks what the value number of a given operation is (the mapping is | |||
27 | /// operation -> value number). Thus, when a value number of an operation | |||
28 | /// changes, it must reprocess everything to ensure all uses of a value number | |||
29 | /// get updated properly. In constrast, the sparse algorithm we use *also* | |||
30 | /// tracks what operations have a given value number (IE it also tracks the | |||
31 | /// reverse mapping from value number -> operations with that value number), so | |||
32 | /// that it only needs to reprocess the instructions that are affected when | |||
33 | /// something's value number changes. The rest of the algorithm is devoted to | |||
34 | /// performing symbolic evaluation, forward propagation, and simplification of | |||
35 | /// operations based on the value numbers deduced so far. | |||
36 | /// | |||
37 | /// We also do not perform elimination by using any published algorithm. All | |||
38 | /// published algorithms are O(Instructions). Instead, we use a technique that | |||
39 | /// is O(number of operations with the same value number), enabling us to skip | |||
40 | /// trying to eliminate things that have unique value numbers. | |||
41 | //===----------------------------------------------------------------------===// | |||
42 | ||||
43 | #include "llvm/Transforms/Scalar/NewGVN.h" | |||
44 | #include "llvm/ADT/BitVector.h" | |||
45 | #include "llvm/ADT/DenseMap.h" | |||
46 | #include "llvm/ADT/DenseSet.h" | |||
47 | #include "llvm/ADT/DepthFirstIterator.h" | |||
48 | #include "llvm/ADT/Hashing.h" | |||
49 | #include "llvm/ADT/MapVector.h" | |||
50 | #include "llvm/ADT/PostOrderIterator.h" | |||
51 | #include "llvm/ADT/STLExtras.h" | |||
52 | #include "llvm/ADT/SmallPtrSet.h" | |||
53 | #include "llvm/ADT/SmallSet.h" | |||
54 | #include "llvm/ADT/SparseBitVector.h" | |||
55 | #include "llvm/ADT/Statistic.h" | |||
56 | #include "llvm/ADT/TinyPtrVector.h" | |||
57 | #include "llvm/Analysis/AliasAnalysis.h" | |||
58 | #include "llvm/Analysis/AssumptionCache.h" | |||
59 | #include "llvm/Analysis/CFG.h" | |||
60 | #include "llvm/Analysis/CFGPrinter.h" | |||
61 | #include "llvm/Analysis/ConstantFolding.h" | |||
62 | #include "llvm/Analysis/GlobalsModRef.h" | |||
63 | #include "llvm/Analysis/InstructionSimplify.h" | |||
64 | #include "llvm/Analysis/MemoryBuiltins.h" | |||
65 | #include "llvm/Analysis/MemoryLocation.h" | |||
66 | #include "llvm/Analysis/TargetLibraryInfo.h" | |||
67 | #include "llvm/IR/DataLayout.h" | |||
68 | #include "llvm/IR/Dominators.h" | |||
69 | #include "llvm/IR/GlobalVariable.h" | |||
70 | #include "llvm/IR/IRBuilder.h" | |||
71 | #include "llvm/IR/IntrinsicInst.h" | |||
72 | #include "llvm/IR/LLVMContext.h" | |||
73 | #include "llvm/IR/Metadata.h" | |||
74 | #include "llvm/IR/PatternMatch.h" | |||
75 | #include "llvm/IR/Type.h" | |||
76 | #include "llvm/Support/Allocator.h" | |||
77 | #include "llvm/Support/CommandLine.h" | |||
78 | #include "llvm/Support/Debug.h" | |||
79 | #include "llvm/Support/DebugCounter.h" | |||
80 | #include "llvm/Transforms/Scalar.h" | |||
81 | #include "llvm/Transforms/Scalar/GVNExpression.h" | |||
82 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
83 | #include "llvm/Transforms/Utils/Local.h" | |||
84 | #include "llvm/Transforms/Utils/MemorySSA.h" | |||
85 | #include "llvm/Transforms/Utils/PredicateInfo.h" | |||
86 | #include "llvm/Transforms/Utils/VNCoercion.h" | |||
87 | #include <unordered_map> | |||
88 | #include <utility> | |||
89 | #include <vector> | |||
90 | using namespace llvm; | |||
91 | using namespace PatternMatch; | |||
92 | using namespace llvm::GVNExpression; | |||
93 | using namespace llvm::VNCoercion; | |||
94 | #define DEBUG_TYPE"newgvn" "newgvn" | |||
95 | ||||
96 | STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted")static llvm::Statistic NumGVNInstrDeleted = {"newgvn", "NumGVNInstrDeleted" , "Number of instructions deleted", {0}, false}; | |||
97 | STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted")static llvm::Statistic NumGVNBlocksDeleted = {"newgvn", "NumGVNBlocksDeleted" , "Number of blocks deleted", {0}, false}; | |||
98 | STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified")static llvm::Statistic NumGVNOpsSimplified = {"newgvn", "NumGVNOpsSimplified" , "Number of Expressions simplified", {0}, false}; | |||
99 | STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same")static llvm::Statistic NumGVNPhisAllSame = {"newgvn", "NumGVNPhisAllSame" , "Number of PHIs whos arguments are all the same", {0}, false }; | |||
100 | STATISTIC(NumGVNMaxIterations,static llvm::Statistic NumGVNMaxIterations = {"newgvn", "NumGVNMaxIterations" , "Maximum Number of iterations it took to converge GVN", {0} , false} | |||
101 | "Maximum Number of iterations it took to converge GVN")static llvm::Statistic NumGVNMaxIterations = {"newgvn", "NumGVNMaxIterations" , "Maximum Number of iterations it took to converge GVN", {0} , false}; | |||
102 | STATISTIC(NumGVNLeaderChanges, "Number of leader changes")static llvm::Statistic NumGVNLeaderChanges = {"newgvn", "NumGVNLeaderChanges" , "Number of leader changes", {0}, false}; | |||
103 | STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes")static llvm::Statistic NumGVNSortedLeaderChanges = {"newgvn", "NumGVNSortedLeaderChanges", "Number of sorted leader changes" , {0}, false}; | |||
104 | STATISTIC(NumGVNAvoidedSortedLeaderChanges,static llvm::Statistic NumGVNAvoidedSortedLeaderChanges = {"newgvn" , "NumGVNAvoidedSortedLeaderChanges", "Number of avoided sorted leader changes" , {0}, false} | |||
105 | "Number of avoided sorted leader changes")static llvm::Statistic NumGVNAvoidedSortedLeaderChanges = {"newgvn" , "NumGVNAvoidedSortedLeaderChanges", "Number of avoided sorted leader changes" , {0}, false}; | |||
106 | STATISTIC(NumGVNNotMostDominatingLeader,static llvm::Statistic NumGVNNotMostDominatingLeader = {"newgvn" , "NumGVNNotMostDominatingLeader", "Number of times a member dominated it's new classes' leader" , {0}, false} | |||
107 | "Number of times a member dominated it's new classes' leader")static llvm::Statistic NumGVNNotMostDominatingLeader = {"newgvn" , "NumGVNNotMostDominatingLeader", "Number of times a member dominated it's new classes' leader" , {0}, false}; | |||
108 | STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated")static llvm::Statistic NumGVNDeadStores = {"newgvn", "NumGVNDeadStores" , "Number of redundant/dead stores eliminated", {0}, false}; | |||
109 | DEBUG_COUNTER(VNCounter, "newgvn-vn",static const unsigned VNCounter = DebugCounter::registerCounter ("newgvn-vn", "Controls which instructions are value numbered" ); | |||
110 | "Controls which instructions are value numbered")static const unsigned VNCounter = DebugCounter::registerCounter ("newgvn-vn", "Controls which instructions are value numbered" ); | |||
111 | //===----------------------------------------------------------------------===// | |||
112 | // GVN Pass | |||
113 | //===----------------------------------------------------------------------===// | |||
114 | ||||
115 | // Anchor methods. | |||
116 | namespace llvm { | |||
117 | namespace GVNExpression { | |||
118 | Expression::~Expression() = default; | |||
119 | BasicExpression::~BasicExpression() = default; | |||
120 | CallExpression::~CallExpression() = default; | |||
121 | LoadExpression::~LoadExpression() = default; | |||
122 | StoreExpression::~StoreExpression() = default; | |||
123 | AggregateValueExpression::~AggregateValueExpression() = default; | |||
124 | PHIExpression::~PHIExpression() = default; | |||
125 | } | |||
126 | } | |||
127 | ||||
128 | // Congruence classes represent the set of expressions/instructions | |||
129 | // that are all the same *during some scope in the function*. | |||
130 | // That is, because of the way we perform equality propagation, and | |||
131 | // because of memory value numbering, it is not correct to assume | |||
132 | // you can willy-nilly replace any member with any other at any | |||
133 | // point in the function. | |||
134 | // | |||
135 | // For any Value in the Member set, it is valid to replace any dominated member | |||
136 | // with that Value. | |||
137 | // | |||
138 | // Every congruence class has a leader, and the leader is used to | |||
139 | // symbolize instructions in a canonical way (IE every operand of an | |||
140 | // instruction that is a member of the same congruence class will | |||
141 | // always be replaced with leader during symbolization). | |||
142 | // To simplify symbolization, we keep the leader as a constant if class can be | |||
143 | // proved to be a constant value. | |||
144 | // Otherwise, the leader is a randomly chosen member of the value set, it does | |||
145 | // not matter which one is chosen. | |||
146 | // Each congruence class also has a defining expression, | |||
147 | // though the expression may be null. If it exists, it can be used for forward | |||
148 | // propagation and reassociation of values. | |||
149 | // | |||
150 | struct CongruenceClass { | |||
151 | using MemberSet = SmallPtrSet<Value *, 4>; | |||
152 | unsigned ID; | |||
153 | // Representative leader. | |||
154 | Value *RepLeader = nullptr; | |||
155 | // If this is represented by a store, the value. | |||
156 | Value *RepStoredValue = nullptr; | |||
157 | // If this class contains MemoryDefs, what is the represented memory state. | |||
158 | MemoryAccess *RepMemoryAccess = nullptr; | |||
159 | // Defining Expression. | |||
160 | const Expression *DefiningExpr = nullptr; | |||
161 | // Actual members of this class. | |||
162 | MemberSet Members; | |||
163 | ||||
164 | // True if this class has no members left. This is mainly used for assertion | |||
165 | // purposes, and for skipping empty classes. | |||
166 | bool Dead = false; | |||
167 | ||||
168 | // Number of stores in this congruence class. | |||
169 | // This is used so we can detect store equivalence changes properly. | |||
170 | int StoreCount = 0; | |||
171 | ||||
172 | // The most dominating leader after our current leader, because the member set | |||
173 | // is not sorted and is expensive to keep sorted all the time. | |||
174 | std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U}; | |||
175 | ||||
176 | explicit CongruenceClass(unsigned ID) : ID(ID) {} | |||
177 | CongruenceClass(unsigned ID, Value *Leader, const Expression *E) | |||
178 | : ID(ID), RepLeader(Leader), DefiningExpr(E) {} | |||
179 | }; | |||
180 | ||||
181 | // Return true if two congruence classes are equivalent to each other. This | |||
182 | // means | |||
183 | // that every field but the ID number and the dead field are equivalent. | |||
184 | bool areClassesEquivalent(const CongruenceClass *A, const CongruenceClass *B) { | |||
185 | if (A == B) | |||
186 | return true; | |||
187 | if ((A && !B) || (B && !A)) | |||
188 | return false; | |||
189 | ||||
190 | if (std::tie(A->StoreCount, A->RepLeader, A->RepStoredValue, | |||
| ||||
191 | A->RepMemoryAccess) != std::tie(B->StoreCount, B->RepLeader, | |||
192 | B->RepStoredValue, | |||
193 | B->RepMemoryAccess)) | |||
194 | return false; | |||
195 | if (A->DefiningExpr != B->DefiningExpr) | |||
196 | if (!A->DefiningExpr || !B->DefiningExpr || | |||
197 | *A->DefiningExpr != *B->DefiningExpr) | |||
198 | return false; | |||
199 | // We need some ordered set | |||
200 | std::set<Value *> AMembers(A->Members.begin(), A->Members.end()); | |||
201 | std::set<Value *> BMembers(B->Members.begin(), B->Members.end()); | |||
202 | return AMembers == BMembers; | |||
203 | } | |||
204 | ||||
205 | namespace llvm { | |||
206 | template <> struct DenseMapInfo<const Expression *> { | |||
207 | static const Expression *getEmptyKey() { | |||
208 | auto Val = static_cast<uintptr_t>(-1); | |||
209 | Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; | |||
210 | return reinterpret_cast<const Expression *>(Val); | |||
211 | } | |||
212 | static const Expression *getTombstoneKey() { | |||
213 | auto Val = static_cast<uintptr_t>(~1U); | |||
214 | Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; | |||
215 | return reinterpret_cast<const Expression *>(Val); | |||
216 | } | |||
217 | static unsigned getHashValue(const Expression *V) { | |||
218 | return static_cast<unsigned>(V->getHashValue()); | |||
219 | } | |||
220 | static bool isEqual(const Expression *LHS, const Expression *RHS) { | |||
221 | if (LHS == RHS) | |||
222 | return true; | |||
223 | if (LHS == getTombstoneKey() || RHS == getTombstoneKey() || | |||
224 | LHS == getEmptyKey() || RHS == getEmptyKey()) | |||
225 | return false; | |||
226 | return *LHS == *RHS; | |||
227 | } | |||
228 | }; | |||
229 | } // end namespace llvm | |||
230 | ||||
231 | namespace { | |||
232 | class NewGVN { | |||
233 | Function &F; | |||
234 | DominatorTree *DT; | |||
235 | AssumptionCache *AC; | |||
236 | const TargetLibraryInfo *TLI; | |||
237 | AliasAnalysis *AA; | |||
238 | MemorySSA *MSSA; | |||
239 | MemorySSAWalker *MSSAWalker; | |||
240 | const DataLayout &DL; | |||
241 | std::unique_ptr<PredicateInfo> PredInfo; | |||
242 | BumpPtrAllocator ExpressionAllocator; | |||
243 | ArrayRecycler<Value *> ArgRecycler; | |||
244 | ||||
245 | // Number of function arguments, used by ranking | |||
246 | unsigned int NumFuncArgs; | |||
247 | ||||
248 | // Congruence class info. | |||
249 | ||||
250 | // This class is called INITIAL in the paper. It is the class everything | |||
251 | // startsout in, and represents any value. Being an optimistic analysis, | |||
252 | // anything in the TOP class has the value TOP, which is indeterminate and | |||
253 | // equivalent to everything. | |||
254 | CongruenceClass *TOPClass; | |||
255 | std::vector<CongruenceClass *> CongruenceClasses; | |||
256 | unsigned NextCongruenceNum; | |||
257 | ||||
258 | // Value Mappings. | |||
259 | DenseMap<Value *, CongruenceClass *> ValueToClass; | |||
260 | DenseMap<Value *, const Expression *> ValueToExpression; | |||
261 | ||||
262 | // Mapping from predicate info we used to the instructions we used it with. | |||
263 | // In order to correctly ensure propagation, we must keep track of what | |||
264 | // comparisons we used, so that when the values of the comparisons change, we | |||
265 | // propagate the information to the places we used the comparison. | |||
266 | DenseMap<const Value *, SmallPtrSet<Instruction *, 2>> PredicateToUsers; | |||
267 | ||||
268 | // A table storing which memorydefs/phis represent a memory state provably | |||
269 | // equivalent to another memory state. | |||
270 | // We could use the congruence class machinery, but the MemoryAccess's are | |||
271 | // abstract memory states, so they can only ever be equivalent to each other, | |||
272 | // and not to constants, etc. | |||
273 | DenseMap<const MemoryAccess *, CongruenceClass *> MemoryAccessToClass; | |||
274 | ||||
275 | // Expression to class mapping. | |||
276 | using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>; | |||
277 | ExpressionClassMap ExpressionToClass; | |||
278 | ||||
279 | // Which values have changed as a result of leader changes. | |||
280 | SmallPtrSet<Value *, 8> LeaderChanges; | |||
281 | ||||
282 | // Reachability info. | |||
283 | using BlockEdge = BasicBlockEdge; | |||
284 | DenseSet<BlockEdge> ReachableEdges; | |||
285 | SmallPtrSet<const BasicBlock *, 8> ReachableBlocks; | |||
286 | ||||
287 | // This is a bitvector because, on larger functions, we may have | |||
288 | // thousands of touched instructions at once (entire blocks, | |||
289 | // instructions with hundreds of uses, etc). Even with optimization | |||
290 | // for when we mark whole blocks as touched, when this was a | |||
291 | // SmallPtrSet or DenseSet, for some functions, we spent >20% of all | |||
292 | // the time in GVN just managing this list. The bitvector, on the | |||
293 | // other hand, efficiently supports test/set/clear of both | |||
294 | // individual and ranges, as well as "find next element" This | |||
295 | // enables us to use it as a worklist with essentially 0 cost. | |||
296 | BitVector TouchedInstructions; | |||
297 | ||||
298 | DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange; | |||
299 | ||||
300 | #ifndef NDEBUG | |||
301 | // Debugging for how many times each block and instruction got processed. | |||
302 | DenseMap<const Value *, unsigned> ProcessedCount; | |||
303 | #endif | |||
304 | ||||
305 | // DFS info. | |||
306 | // This contains a mapping from Instructions to DFS numbers. | |||
307 | // The numbering starts at 1. An instruction with DFS number zero | |||
308 | // means that the instruction is dead. | |||
309 | DenseMap<const Value *, unsigned> InstrDFS; | |||
310 | ||||
311 | // This contains the mapping DFS numbers to instructions. | |||
312 | SmallVector<Value *, 32> DFSToInstr; | |||
313 | ||||
314 | // Deletion info. | |||
315 | SmallPtrSet<Instruction *, 8> InstructionsToErase; | |||
316 | ||||
317 | public: | |||
318 | NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC, | |||
319 | TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA, | |||
320 | const DataLayout &DL) | |||
321 | : F(F), DT(DT), AC(AC), TLI(TLI), AA(AA), MSSA(MSSA), DL(DL), | |||
322 | PredInfo(make_unique<PredicateInfo>(F, *DT, *AC)) {} | |||
323 | bool runGVN(); | |||
324 | ||||
325 | private: | |||
326 | // Expression handling. | |||
327 | const Expression *createExpression(Instruction *); | |||
328 | const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *); | |||
329 | PHIExpression *createPHIExpression(Instruction *); | |||
330 | const VariableExpression *createVariableExpression(Value *); | |||
331 | const ConstantExpression *createConstantExpression(Constant *); | |||
332 | const Expression *createVariableOrConstant(Value *V); | |||
333 | const UnknownExpression *createUnknownExpression(Instruction *); | |||
334 | const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *); | |||
335 | LoadExpression *createLoadExpression(Type *, Value *, LoadInst *, | |||
336 | MemoryAccess *); | |||
337 | const CallExpression *createCallExpression(CallInst *, MemoryAccess *); | |||
338 | const AggregateValueExpression *createAggregateValueExpression(Instruction *); | |||
339 | bool setBasicExpressionInfo(Instruction *, BasicExpression *); | |||
340 | ||||
341 | // Congruence class handling. | |||
342 | CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) { | |||
343 | auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E); | |||
344 | CongruenceClasses.emplace_back(result); | |||
345 | return result; | |||
346 | } | |||
347 | ||||
348 | CongruenceClass *createSingletonCongruenceClass(Value *Member) { | |||
349 | CongruenceClass *CClass = createCongruenceClass(Member, nullptr); | |||
350 | CClass->Members.insert(Member); | |||
351 | ValueToClass[Member] = CClass; | |||
352 | return CClass; | |||
353 | } | |||
354 | void initializeCongruenceClasses(Function &F); | |||
355 | ||||
356 | // Value number an Instruction or MemoryPhi. | |||
357 | void valueNumberMemoryPhi(MemoryPhi *); | |||
358 | void valueNumberInstruction(Instruction *); | |||
359 | ||||
360 | // Symbolic evaluation. | |||
361 | const Expression *checkSimplificationResults(Expression *, Instruction *, | |||
362 | Value *); | |||
363 | const Expression *performSymbolicEvaluation(Value *); | |||
364 | const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *, | |||
365 | Instruction *, MemoryAccess *); | |||
366 | const Expression *performSymbolicLoadEvaluation(Instruction *); | |||
367 | const Expression *performSymbolicStoreEvaluation(Instruction *); | |||
368 | const Expression *performSymbolicCallEvaluation(Instruction *); | |||
369 | const Expression *performSymbolicPHIEvaluation(Instruction *); | |||
370 | const Expression *performSymbolicAggrValueEvaluation(Instruction *); | |||
371 | const Expression *performSymbolicCmpEvaluation(Instruction *); | |||
372 | const Expression *performSymbolicPredicateInfoEvaluation(Instruction *); | |||
373 | ||||
374 | // Congruence finding. | |||
375 | bool someEquivalentDominates(const Instruction *, const Instruction *) const; | |||
376 | Value *lookupOperandLeader(Value *) const; | |||
377 | void performCongruenceFinding(Instruction *, const Expression *); | |||
378 | void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *, | |||
379 | CongruenceClass *); | |||
380 | bool setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To); | |||
381 | MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const; | |||
382 | bool isMemoryAccessTop(const MemoryAccess *) const; | |||
383 | // Ranking | |||
384 | unsigned int getRank(const Value *) const; | |||
385 | bool shouldSwapOperands(const Value *, const Value *) const; | |||
386 | ||||
387 | // Reachability handling. | |||
388 | void updateReachableEdge(BasicBlock *, BasicBlock *); | |||
389 | void processOutgoingEdges(TerminatorInst *, BasicBlock *); | |||
390 | Value *findConditionEquivalence(Value *) const; | |||
391 | ||||
392 | // Elimination. | |||
393 | struct ValueDFS; | |||
394 | void convertClassToDFSOrdered(const CongruenceClass::MemberSet &, | |||
395 | SmallVectorImpl<ValueDFS> &, | |||
396 | DenseMap<const Value *, unsigned int> &, | |||
397 | SmallPtrSetImpl<Instruction *> &); | |||
398 | void convertClassToLoadsAndStores(const CongruenceClass::MemberSet &, | |||
399 | SmallVectorImpl<ValueDFS> &); | |||
400 | ||||
401 | bool eliminateInstructions(Function &); | |||
402 | void replaceInstruction(Instruction *, Value *); | |||
403 | void markInstructionForDeletion(Instruction *); | |||
404 | void deleteInstructionsInBlock(BasicBlock *); | |||
405 | ||||
406 | // New instruction creation. | |||
407 | void handleNewInstruction(Instruction *){}; | |||
408 | ||||
409 | // Various instruction touch utilities | |||
410 | void markUsersTouched(Value *); | |||
411 | void markMemoryUsersTouched(MemoryAccess *); | |||
412 | void markPredicateUsersTouched(Instruction *); | |||
413 | void markLeaderChangeTouched(CongruenceClass *CC); | |||
414 | void addPredicateUsers(const PredicateBase *, Instruction *); | |||
415 | ||||
416 | // Main loop of value numbering | |||
417 | void iterateTouchedInstructions(); | |||
418 | ||||
419 | // Utilities. | |||
420 | void cleanupTables(); | |||
421 | std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned); | |||
422 | void updateProcessedCount(Value *V); | |||
423 | void verifyMemoryCongruency() const; | |||
424 | void verifyIterationSettled(Function &F); | |||
425 | bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const; | |||
426 | BasicBlock *getBlockForValue(Value *V) const; | |||
427 | void deleteExpression(const Expression *E); | |||
428 | // Debug counter info. When verifying, we have to reset the value numbering | |||
429 | // debug counter to the same state it started in to get the same results. | |||
430 | std::pair<int, int> StartingVNCounter; | |||
431 | }; | |||
432 | } // end anonymous namespace | |||
433 | ||||
434 | template <typename T> | |||
435 | static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) { | |||
436 | if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS)) | |||
437 | return false; | |||
438 | return LHS.MemoryExpression::equals(RHS); | |||
439 | } | |||
440 | ||||
441 | bool LoadExpression::equals(const Expression &Other) const { | |||
442 | return equalsLoadStoreHelper(*this, Other); | |||
443 | } | |||
444 | ||||
445 | bool StoreExpression::equals(const Expression &Other) const { | |||
446 | if (!equalsLoadStoreHelper(*this, Other)) | |||
447 | return false; | |||
448 | // Make sure that store vs store includes the value operand. | |||
449 | if (const auto *S = dyn_cast<StoreExpression>(&Other)) | |||
450 | if (getStoredValue() != S->getStoredValue()) | |||
451 | return false; | |||
452 | return true; | |||
453 | } | |||
454 | ||||
455 | #ifndef NDEBUG | |||
456 | static std::string getBlockName(const BasicBlock *B) { | |||
457 | return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr); | |||
458 | } | |||
459 | #endif | |||
460 | ||||
461 | // Get the basic block from an instruction/memory value. | |||
462 | BasicBlock *NewGVN::getBlockForValue(Value *V) const { | |||
463 | if (auto *I = dyn_cast<Instruction>(V)) | |||
464 | return I->getParent(); | |||
465 | else if (auto *MP = dyn_cast<MemoryPhi>(V)) | |||
466 | return MP->getBlock(); | |||
467 | llvm_unreachable("Should have been able to figure out a block for our value")::llvm::llvm_unreachable_internal("Should have been able to figure out a block for our value" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 467); | |||
468 | return nullptr; | |||
469 | } | |||
470 | ||||
471 | // Delete a definitely dead expression, so it can be reused by the expression | |||
472 | // allocator. Some of these are not in creation functions, so we have to accept | |||
473 | // const versions. | |||
474 | void NewGVN::deleteExpression(const Expression *E) { | |||
475 | assert(isa<BasicExpression>(E))((isa<BasicExpression>(E)) ? static_cast<void> (0 ) : __assert_fail ("isa<BasicExpression>(E)", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 475, __PRETTY_FUNCTION__)); | |||
476 | auto *BE = cast<BasicExpression>(E); | |||
477 | const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler); | |||
478 | ExpressionAllocator.Deallocate(E); | |||
479 | } | |||
480 | ||||
481 | PHIExpression *NewGVN::createPHIExpression(Instruction *I) { | |||
482 | BasicBlock *PHIBlock = I->getParent(); | |||
483 | auto *PN = cast<PHINode>(I); | |||
484 | auto *E = | |||
485 | new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock); | |||
486 | ||||
487 | E->allocateOperands(ArgRecycler, ExpressionAllocator); | |||
488 | E->setType(I->getType()); | |||
489 | E->setOpcode(I->getOpcode()); | |||
490 | ||||
491 | // Filter out unreachable phi operands. | |||
492 | auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) { | |||
493 | return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock}); | |||
494 | }); | |||
495 | ||||
496 | std::transform(Filtered.begin(), Filtered.end(), op_inserter(E), | |||
497 | [&](const Use &U) -> Value * { | |||
498 | // Don't try to transform self-defined phis. | |||
499 | if (U == PN) | |||
500 | return PN; | |||
501 | return lookupOperandLeader(U); | |||
502 | }); | |||
503 | return E; | |||
504 | } | |||
505 | ||||
506 | // Set basic expression info (Arguments, type, opcode) for Expression | |||
507 | // E from Instruction I in block B. | |||
508 | bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) { | |||
509 | bool AllConstant = true; | |||
510 | if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) | |||
511 | E->setType(GEP->getSourceElementType()); | |||
512 | else | |||
513 | E->setType(I->getType()); | |||
514 | E->setOpcode(I->getOpcode()); | |||
515 | E->allocateOperands(ArgRecycler, ExpressionAllocator); | |||
516 | ||||
517 | // Transform the operand array into an operand leader array, and keep track of | |||
518 | // whether all members are constant. | |||
519 | std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) { | |||
520 | auto Operand = lookupOperandLeader(O); | |||
521 | AllConstant &= isa<Constant>(Operand); | |||
522 | return Operand; | |||
523 | }); | |||
524 | ||||
525 | return AllConstant; | |||
526 | } | |||
527 | ||||
528 | const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T, | |||
529 | Value *Arg1, Value *Arg2) { | |||
530 | auto *E = new (ExpressionAllocator) BasicExpression(2); | |||
531 | ||||
532 | E->setType(T); | |||
533 | E->setOpcode(Opcode); | |||
534 | E->allocateOperands(ArgRecycler, ExpressionAllocator); | |||
535 | if (Instruction::isCommutative(Opcode)) { | |||
536 | // Ensure that commutative instructions that only differ by a permutation | |||
537 | // of their operands get the same value number by sorting the operand value | |||
538 | // numbers. Since all commutative instructions have two operands it is more | |||
539 | // efficient to sort by hand rather than using, say, std::sort. | |||
540 | if (shouldSwapOperands(Arg1, Arg2)) | |||
541 | std::swap(Arg1, Arg2); | |||
542 | } | |||
543 | E->op_push_back(lookupOperandLeader(Arg1)); | |||
544 | E->op_push_back(lookupOperandLeader(Arg2)); | |||
545 | ||||
546 | Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), DL, TLI, | |||
547 | DT, AC); | |||
548 | if (const Expression *SimplifiedE = checkSimplificationResults(E, nullptr, V)) | |||
549 | return SimplifiedE; | |||
550 | return E; | |||
551 | } | |||
552 | ||||
553 | // Take a Value returned by simplification of Expression E/Instruction | |||
554 | // I, and see if it resulted in a simpler expression. If so, return | |||
555 | // that expression. | |||
556 | // TODO: Once finished, this should not take an Instruction, we only | |||
557 | // use it for printing. | |||
558 | const Expression *NewGVN::checkSimplificationResults(Expression *E, | |||
559 | Instruction *I, Value *V) { | |||
560 | if (!V) | |||
561 | return nullptr; | |||
562 | if (auto *C = dyn_cast<Constant>(V)) { | |||
563 | if (I) | |||
564 | DEBUG(dbgs() << "Simplified " << *I << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " constant " << *C << "\n"; } } while (false) | |||
565 | << " constant " << *C << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " constant " << *C << "\n"; } } while (false); | |||
566 | NumGVNOpsSimplified++; | |||
567 | assert(isa<BasicExpression>(E) &&((isa<BasicExpression>(E) && "We should always have had a basic expression here" ) ? static_cast<void> (0) : __assert_fail ("isa<BasicExpression>(E) && \"We should always have had a basic expression here\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 568, __PRETTY_FUNCTION__)) | |||
568 | "We should always have had a basic expression here")((isa<BasicExpression>(E) && "We should always have had a basic expression here" ) ? static_cast<void> (0) : __assert_fail ("isa<BasicExpression>(E) && \"We should always have had a basic expression here\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 568, __PRETTY_FUNCTION__)); | |||
569 | deleteExpression(E); | |||
570 | return createConstantExpression(C); | |||
571 | } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) { | |||
572 | if (I) | |||
573 | DEBUG(dbgs() << "Simplified " << *I << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " variable " << *V << "\n"; } } while (false) | |||
574 | << " variable " << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " variable " << *V << "\n"; } } while (false); | |||
575 | deleteExpression(E); | |||
576 | return createVariableExpression(V); | |||
577 | } | |||
578 | ||||
579 | CongruenceClass *CC = ValueToClass.lookup(V); | |||
580 | if (CC && CC->DefiningExpr) { | |||
581 | if (I) | |||
582 | DEBUG(dbgs() << "Simplified " << *I << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " expression " << *V << "\n"; } } while (false) | |||
583 | << " expression " << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified " << *I << " to " << " expression " << *V << "\n"; } } while (false); | |||
584 | NumGVNOpsSimplified++; | |||
585 | deleteExpression(E); | |||
586 | return CC->DefiningExpr; | |||
587 | } | |||
588 | return nullptr; | |||
589 | } | |||
590 | ||||
591 | const Expression *NewGVN::createExpression(Instruction *I) { | |||
592 | auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands()); | |||
593 | ||||
594 | bool AllConstant = setBasicExpressionInfo(I, E); | |||
595 | ||||
596 | if (I->isCommutative()) { | |||
597 | // Ensure that commutative instructions that only differ by a permutation | |||
598 | // of their operands get the same value number by sorting the operand value | |||
599 | // numbers. Since all commutative instructions have two operands it is more | |||
600 | // efficient to sort by hand rather than using, say, std::sort. | |||
601 | assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!")((I->getNumOperands() == 2 && "Unsupported commutative instruction!" ) ? static_cast<void> (0) : __assert_fail ("I->getNumOperands() == 2 && \"Unsupported commutative instruction!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 601, __PRETTY_FUNCTION__)); | |||
602 | if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) | |||
603 | E->swapOperands(0, 1); | |||
604 | } | |||
605 | ||||
606 | // Perform simplificaiton | |||
607 | // TODO: Right now we only check to see if we get a constant result. | |||
608 | // We may get a less than constant, but still better, result for | |||
609 | // some operations. | |||
610 | // IE | |||
611 | // add 0, x -> x | |||
612 | // and x, x -> x | |||
613 | // We should handle this by simply rewriting the expression. | |||
614 | if (auto *CI = dyn_cast<CmpInst>(I)) { | |||
615 | // Sort the operand value numbers so x<y and y>x get the same value | |||
616 | // number. | |||
617 | CmpInst::Predicate Predicate = CI->getPredicate(); | |||
618 | if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) { | |||
619 | E->swapOperands(0, 1); | |||
620 | Predicate = CmpInst::getSwappedPredicate(Predicate); | |||
621 | } | |||
622 | E->setOpcode((CI->getOpcode() << 8) | Predicate); | |||
623 | // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands | |||
624 | assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&((I->getOperand(0)->getType() == I->getOperand(1)-> getType() && "Wrong types on cmp instruction") ? static_cast <void> (0) : __assert_fail ("I->getOperand(0)->getType() == I->getOperand(1)->getType() && \"Wrong types on cmp instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 625, __PRETTY_FUNCTION__)) | |||
625 | "Wrong types on cmp instruction")((I->getOperand(0)->getType() == I->getOperand(1)-> getType() && "Wrong types on cmp instruction") ? static_cast <void> (0) : __assert_fail ("I->getOperand(0)->getType() == I->getOperand(1)->getType() && \"Wrong types on cmp instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 625, __PRETTY_FUNCTION__)); | |||
626 | assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&(((E->getOperand(0)->getType() == I->getOperand(0)-> getType() && E->getOperand(1)->getType() == I-> getOperand(1)->getType())) ? static_cast<void> (0) : __assert_fail ("(E->getOperand(0)->getType() == I->getOperand(0)->getType() && E->getOperand(1)->getType() == I->getOperand(1)->getType())" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 627, __PRETTY_FUNCTION__)) | |||
627 | E->getOperand(1)->getType() == I->getOperand(1)->getType()))(((E->getOperand(0)->getType() == I->getOperand(0)-> getType() && E->getOperand(1)->getType() == I-> getOperand(1)->getType())) ? static_cast<void> (0) : __assert_fail ("(E->getOperand(0)->getType() == I->getOperand(0)->getType() && E->getOperand(1)->getType() == I->getOperand(1)->getType())" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 627, __PRETTY_FUNCTION__)); | |||
628 | Value *V = SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), | |||
629 | DL, TLI, DT, AC); | |||
630 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
631 | return SimplifiedE; | |||
632 | } else if (isa<SelectInst>(I)) { | |||
633 | if (isa<Constant>(E->getOperand(0)) || | |||
634 | E->getOperand(0) == E->getOperand(1)) { | |||
635 | assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&((E->getOperand(1)->getType() == I->getOperand(1)-> getType() && E->getOperand(2)->getType() == I-> getOperand(2)->getType()) ? static_cast<void> (0) : __assert_fail ("E->getOperand(1)->getType() == I->getOperand(1)->getType() && E->getOperand(2)->getType() == I->getOperand(2)->getType()" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 636, __PRETTY_FUNCTION__)) | |||
636 | E->getOperand(2)->getType() == I->getOperand(2)->getType())((E->getOperand(1)->getType() == I->getOperand(1)-> getType() && E->getOperand(2)->getType() == I-> getOperand(2)->getType()) ? static_cast<void> (0) : __assert_fail ("E->getOperand(1)->getType() == I->getOperand(1)->getType() && E->getOperand(2)->getType() == I->getOperand(2)->getType()" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 636, __PRETTY_FUNCTION__)); | |||
637 | Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1), | |||
638 | E->getOperand(2), DL, TLI, DT, AC); | |||
639 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
640 | return SimplifiedE; | |||
641 | } | |||
642 | } else if (I->isBinaryOp()) { | |||
643 | Value *V = SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), | |||
644 | DL, TLI, DT, AC); | |||
645 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
646 | return SimplifiedE; | |||
647 | } else if (auto *BI = dyn_cast<BitCastInst>(I)) { | |||
648 | Value *V = SimplifyInstruction(BI, DL, TLI, DT, AC); | |||
649 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
650 | return SimplifiedE; | |||
651 | } else if (isa<GetElementPtrInst>(I)) { | |||
652 | Value *V = SimplifyGEPInst(E->getType(), | |||
653 | ArrayRef<Value *>(E->op_begin(), E->op_end()), | |||
654 | DL, TLI, DT, AC); | |||
655 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
656 | return SimplifiedE; | |||
657 | } else if (AllConstant) { | |||
658 | // We don't bother trying to simplify unless all of the operands | |||
659 | // were constant. | |||
660 | // TODO: There are a lot of Simplify*'s we could call here, if we | |||
661 | // wanted to. The original motivating case for this code was a | |||
662 | // zext i1 false to i8, which we don't have an interface to | |||
663 | // simplify (IE there is no SimplifyZExt). | |||
664 | ||||
665 | SmallVector<Constant *, 8> C; | |||
666 | for (Value *Arg : E->operands()) | |||
667 | C.emplace_back(cast<Constant>(Arg)); | |||
668 | ||||
669 | if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI)) | |||
670 | if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) | |||
671 | return SimplifiedE; | |||
672 | } | |||
673 | return E; | |||
674 | } | |||
675 | ||||
676 | const AggregateValueExpression * | |||
677 | NewGVN::createAggregateValueExpression(Instruction *I) { | |||
678 | if (auto *II = dyn_cast<InsertValueInst>(I)) { | |||
679 | auto *E = new (ExpressionAllocator) | |||
680 | AggregateValueExpression(I->getNumOperands(), II->getNumIndices()); | |||
681 | setBasicExpressionInfo(I, E); | |||
682 | E->allocateIntOperands(ExpressionAllocator); | |||
683 | std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E)); | |||
684 | return E; | |||
685 | } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) { | |||
686 | auto *E = new (ExpressionAllocator) | |||
687 | AggregateValueExpression(I->getNumOperands(), EI->getNumIndices()); | |||
688 | setBasicExpressionInfo(EI, E); | |||
689 | E->allocateIntOperands(ExpressionAllocator); | |||
690 | std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E)); | |||
691 | return E; | |||
692 | } | |||
693 | llvm_unreachable("Unhandled type of aggregate value operation")::llvm::llvm_unreachable_internal("Unhandled type of aggregate value operation" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 693); | |||
694 | } | |||
695 | ||||
696 | const VariableExpression *NewGVN::createVariableExpression(Value *V) { | |||
697 | auto *E = new (ExpressionAllocator) VariableExpression(V); | |||
698 | E->setOpcode(V->getValueID()); | |||
699 | return E; | |||
700 | } | |||
701 | ||||
702 | const Expression *NewGVN::createVariableOrConstant(Value *V) { | |||
703 | if (auto *C = dyn_cast<Constant>(V)) | |||
704 | return createConstantExpression(C); | |||
705 | return createVariableExpression(V); | |||
706 | } | |||
707 | ||||
708 | const ConstantExpression *NewGVN::createConstantExpression(Constant *C) { | |||
709 | auto *E = new (ExpressionAllocator) ConstantExpression(C); | |||
710 | E->setOpcode(C->getValueID()); | |||
711 | return E; | |||
712 | } | |||
713 | ||||
714 | const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) { | |||
715 | auto *E = new (ExpressionAllocator) UnknownExpression(I); | |||
716 | E->setOpcode(I->getOpcode()); | |||
717 | return E; | |||
718 | } | |||
719 | ||||
720 | const CallExpression *NewGVN::createCallExpression(CallInst *CI, | |||
721 | MemoryAccess *HV) { | |||
722 | // FIXME: Add operand bundles for calls. | |||
723 | auto *E = | |||
724 | new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV); | |||
725 | setBasicExpressionInfo(CI, E); | |||
726 | return E; | |||
727 | } | |||
728 | ||||
729 | // Return true if some equivalent of instruction Inst dominates instruction U. | |||
730 | bool NewGVN::someEquivalentDominates(const Instruction *Inst, | |||
731 | const Instruction *U) const { | |||
732 | auto *CC = ValueToClass.lookup(Inst); | |||
733 | // This must be an instruction because we are only called from phi nodes | |||
734 | // in the case that the value it needs to check against is an instruction. | |||
735 | ||||
736 | // The most likely candiates for dominance are the leader and the next leader. | |||
737 | // The leader or nextleader will dominate in all cases where there is an | |||
738 | // equivalent that is higher up in the dom tree. | |||
739 | // We can't *only* check them, however, because the | |||
740 | // dominator tree could have an infinite number of non-dominating siblings | |||
741 | // with instructions that are in the right congruence class. | |||
742 | // A | |||
743 | // B C D E F G | |||
744 | // | | |||
745 | // H | |||
746 | // Instruction U could be in H, with equivalents in every other sibling. | |||
747 | // Depending on the rpo order picked, the leader could be the equivalent in | |||
748 | // any of these siblings. | |||
749 | if (!CC) | |||
750 | return false; | |||
751 | if (DT->dominates(cast<Instruction>(CC->RepLeader), U)) | |||
752 | return true; | |||
753 | if (CC->NextLeader.first && | |||
754 | DT->dominates(cast<Instruction>(CC->NextLeader.first), U)) | |||
755 | return true; | |||
756 | return llvm::any_of(CC->Members, [&](const Value *Member) { | |||
757 | return Member != CC->RepLeader && | |||
758 | DT->dominates(cast<Instruction>(Member), U); | |||
759 | }); | |||
760 | } | |||
761 | ||||
762 | // See if we have a congruence class and leader for this operand, and if so, | |||
763 | // return it. Otherwise, return the operand itself. | |||
764 | Value *NewGVN::lookupOperandLeader(Value *V) const { | |||
765 | CongruenceClass *CC = ValueToClass.lookup(V); | |||
766 | if (CC) { | |||
767 | // Everything in TOP is represneted by undef, as it can be any value. | |||
768 | // We do have to make sure we get the type right though, so we can't set the | |||
769 | // RepLeader to undef. | |||
770 | if (CC == TOPClass) | |||
771 | return UndefValue::get(V->getType()); | |||
772 | return CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader; | |||
773 | } | |||
774 | ||||
775 | return V; | |||
776 | } | |||
777 | ||||
778 | MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const { | |||
779 | auto *CC = MemoryAccessToClass.lookup(MA); | |||
780 | if (CC && CC->RepMemoryAccess) | |||
781 | return CC->RepMemoryAccess; | |||
782 | // FIXME: We need to audit all the places that current set a nullptr To, and | |||
783 | // fix them. There should always be *some* congruence class, even if it is | |||
784 | // singular. Right now, we don't bother setting congruence classes for | |||
785 | // anything but stores, which means we have to return the original access | |||
786 | // here. Otherwise, this should be unreachable. | |||
787 | return MA; | |||
788 | } | |||
789 | ||||
790 | // Return true if the MemoryAccess is really equivalent to everything. This is | |||
791 | // equivalent to the lattice value "TOP" in most lattices. This is the initial | |||
792 | // state of all memory accesses. | |||
793 | bool NewGVN::isMemoryAccessTop(const MemoryAccess *MA) const { | |||
794 | return MemoryAccessToClass.lookup(MA) == TOPClass; | |||
795 | } | |||
796 | ||||
797 | LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp, | |||
798 | LoadInst *LI, MemoryAccess *DA) { | |||
799 | auto *E = new (ExpressionAllocator) LoadExpression(1, LI, DA); | |||
800 | E->allocateOperands(ArgRecycler, ExpressionAllocator); | |||
801 | E->setType(LoadType); | |||
802 | ||||
803 | // Give store and loads same opcode so they value number together. | |||
804 | E->setOpcode(0); | |||
805 | E->op_push_back(lookupOperandLeader(PointerOp)); | |||
806 | if (LI) | |||
807 | E->setAlignment(LI->getAlignment()); | |||
808 | ||||
809 | // TODO: Value number heap versions. We may be able to discover | |||
810 | // things alias analysis can't on it's own (IE that a store and a | |||
811 | // load have the same value, and thus, it isn't clobbering the load). | |||
812 | return E; | |||
813 | } | |||
814 | ||||
815 | const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI, | |||
816 | MemoryAccess *DA) { | |||
817 | auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand()); | |||
818 | auto *E = new (ExpressionAllocator) | |||
819 | StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, DA); | |||
820 | E->allocateOperands(ArgRecycler, ExpressionAllocator); | |||
821 | E->setType(SI->getValueOperand()->getType()); | |||
822 | ||||
823 | // Give store and loads same opcode so they value number together. | |||
824 | E->setOpcode(0); | |||
825 | E->op_push_back(lookupOperandLeader(SI->getPointerOperand())); | |||
826 | ||||
827 | // TODO: Value number heap versions. We may be able to discover | |||
828 | // things alias analysis can't on it's own (IE that a store and a | |||
829 | // load have the same value, and thus, it isn't clobbering the load). | |||
830 | return E; | |||
831 | } | |||
832 | ||||
833 | const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) { | |||
834 | // Unlike loads, we never try to eliminate stores, so we do not check if they | |||
835 | // are simple and avoid value numbering them. | |||
836 | auto *SI = cast<StoreInst>(I); | |||
837 | MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI); | |||
838 | // Get the expression, if any, for the RHS of the MemoryDef. | |||
839 | MemoryAccess *StoreRHS = lookupMemoryAccessEquiv( | |||
840 | cast<MemoryDef>(StoreAccess)->getDefiningAccess()); | |||
841 | // If we are defined by ourselves, use the live on entry def. | |||
842 | if (StoreRHS == StoreAccess) | |||
843 | StoreRHS = MSSA->getLiveOnEntryDef(); | |||
844 | ||||
845 | if (SI->isSimple()) { | |||
846 | // See if we are defined by a previous store expression, it already has a | |||
847 | // value, and it's the same value as our current store. FIXME: Right now, we | |||
848 | // only do this for simple stores, we should expand to cover memcpys, etc. | |||
849 | const Expression *OldStore = createStoreExpression(SI, StoreRHS); | |||
850 | CongruenceClass *CC = ExpressionToClass.lookup(OldStore); | |||
851 | // Basically, check if the congruence class the store is in is defined by a | |||
852 | // store that isn't us, and has the same value. MemorySSA takes care of | |||
853 | // ensuring the store has the same memory state as us already. | |||
854 | // The RepStoredValue gets nulled if all the stores disappear in a class, so | |||
855 | // we don't need to check if the class contains a store besides us. | |||
856 | if (CC && CC->RepStoredValue == lookupOperandLeader(SI->getValueOperand())) | |||
857 | return OldStore; | |||
858 | deleteExpression(OldStore); | |||
859 | // Also check if our value operand is defined by a load of the same memory | |||
860 | // location, and the memory state is the same as it was then | |||
861 | // (otherwise, it could have been overwritten later. See test32 in | |||
862 | // transforms/DeadStoreElimination/simple.ll) | |||
863 | if (LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand())) { | |||
864 | if ((lookupOperandLeader(LI->getPointerOperand()) == | |||
865 | lookupOperandLeader(SI->getPointerOperand())) && | |||
866 | (lookupMemoryAccessEquiv( | |||
867 | MSSA->getMemoryAccess(LI)->getDefiningAccess()) == StoreRHS)) | |||
868 | return createVariableExpression(LI); | |||
869 | } | |||
870 | } | |||
871 | return createStoreExpression(SI, StoreAccess); | |||
872 | } | |||
873 | ||||
874 | // See if we can extract the value of a loaded pointer from a load, a store, or | |||
875 | // a memory instruction. | |||
876 | const Expression * | |||
877 | NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr, | |||
878 | LoadInst *LI, Instruction *DepInst, | |||
879 | MemoryAccess *DefiningAccess) { | |||
880 | assert((!LI || LI->isSimple()) && "Not a simple load")(((!LI || LI->isSimple()) && "Not a simple load") ? static_cast<void> (0) : __assert_fail ("(!LI || LI->isSimple()) && \"Not a simple load\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 880, __PRETTY_FUNCTION__)); | |||
881 | if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) { | |||
882 | // Can't forward from non-atomic to atomic without violating memory model. | |||
883 | // Also don't need to coerce if they are the same type, we will just | |||
884 | // propogate.. | |||
885 | if (LI->isAtomic() > DepSI->isAtomic() || | |||
886 | LoadType == DepSI->getValueOperand()->getType()) | |||
887 | return nullptr; | |||
888 | int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL); | |||
889 | if (Offset >= 0) { | |||
890 | if (auto *C = dyn_cast<Constant>( | |||
891 | lookupOperandLeader(DepSI->getValueOperand()))) { | |||
892 | DEBUG(dbgs() << "Coercing load from store " << *DepSI << " to constant "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from store " << *DepSI << " to constant " << *C << "\n"; } } while (false) | |||
893 | << *C << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from store " << *DepSI << " to constant " << *C << "\n"; } } while (false); | |||
894 | return createConstantExpression( | |||
895 | getConstantStoreValueForLoad(C, Offset, LoadType, DL)); | |||
896 | } | |||
897 | } | |||
898 | ||||
899 | } else if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { | |||
900 | // Can't forward from non-atomic to atomic without violating memory model. | |||
901 | if (LI->isAtomic() > DepLI->isAtomic()) | |||
902 | return nullptr; | |||
903 | int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL); | |||
904 | if (Offset >= 0) { | |||
905 | // We can coerce a constant load into a load | |||
906 | if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI))) | |||
907 | if (auto *PossibleConstant = | |||
908 | getConstantLoadValueForLoad(C, Offset, LoadType, DL)) { | |||
909 | DEBUG(dbgs() << "Coercing load from load " << *LI << " to constant "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from load " << *LI << " to constant " << *PossibleConstant << "\n"; } } while (false) | |||
910 | << *PossibleConstant << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from load " << *LI << " to constant " << *PossibleConstant << "\n"; } } while (false); | |||
911 | return createConstantExpression(PossibleConstant); | |||
912 | } | |||
913 | } | |||
914 | ||||
915 | } else if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) { | |||
916 | int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL); | |||
917 | if (Offset >= 0) { | |||
918 | if (auto *PossibleConstant = | |||
919 | getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) { | |||
920 | DEBUG(dbgs() << "Coercing load from meminst " << *DepMIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from meminst " << *DepMI << " to constant " << *PossibleConstant << "\n"; } } while (false) | |||
921 | << " to constant " << *PossibleConstant << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Coercing load from meminst " << *DepMI << " to constant " << *PossibleConstant << "\n"; } } while (false); | |||
922 | return createConstantExpression(PossibleConstant); | |||
923 | } | |||
924 | } | |||
925 | } | |||
926 | ||||
927 | // All of the below are only true if the loaded pointer is produced | |||
928 | // by the dependent instruction. | |||
929 | if (LoadPtr != lookupOperandLeader(DepInst) && | |||
930 | !AA->isMustAlias(LoadPtr, DepInst)) | |||
931 | return nullptr; | |||
932 | // If this load really doesn't depend on anything, then we must be loading an | |||
933 | // undef value. This can happen when loading for a fresh allocation with no | |||
934 | // intervening stores, for example. Note that this is only true in the case | |||
935 | // that the result of the allocation is pointer equal to the load ptr. | |||
936 | if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI)) { | |||
937 | return createConstantExpression(UndefValue::get(LoadType)); | |||
938 | } | |||
939 | // If this load occurs either right after a lifetime begin, | |||
940 | // then the loaded value is undefined. | |||
941 | else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) { | |||
942 | if (II->getIntrinsicID() == Intrinsic::lifetime_start) | |||
943 | return createConstantExpression(UndefValue::get(LoadType)); | |||
944 | } | |||
945 | // If this load follows a calloc (which zero initializes memory), | |||
946 | // then the loaded value is zero | |||
947 | else if (isCallocLikeFn(DepInst, TLI)) { | |||
948 | return createConstantExpression(Constant::getNullValue(LoadType)); | |||
949 | } | |||
950 | ||||
951 | return nullptr; | |||
952 | } | |||
953 | ||||
954 | const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) { | |||
955 | auto *LI = cast<LoadInst>(I); | |||
956 | ||||
957 | // We can eliminate in favor of non-simple loads, but we won't be able to | |||
958 | // eliminate the loads themselves. | |||
959 | if (!LI->isSimple()) | |||
960 | return nullptr; | |||
961 | ||||
962 | Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand()); | |||
963 | // Load of undef is undef. | |||
964 | if (isa<UndefValue>(LoadAddressLeader)) | |||
965 | return createConstantExpression(UndefValue::get(LI->getType())); | |||
966 | ||||
967 | MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I); | |||
968 | ||||
969 | if (!MSSA->isLiveOnEntryDef(DefiningAccess)) { | |||
970 | if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) { | |||
971 | Instruction *DefiningInst = MD->getMemoryInst(); | |||
972 | // If the defining instruction is not reachable, replace with undef. | |||
973 | if (!ReachableBlocks.count(DefiningInst->getParent())) | |||
974 | return createConstantExpression(UndefValue::get(LI->getType())); | |||
975 | // This will handle stores and memory insts. We only do if it the | |||
976 | // defining access has a different type, or it is a pointer produced by | |||
977 | // certain memory operations that cause the memory to have a fixed value | |||
978 | // (IE things like calloc). | |||
979 | const Expression *CoercionResult = performSymbolicLoadCoercion( | |||
980 | LI->getType(), LoadAddressLeader, LI, DefiningInst, DefiningAccess); | |||
981 | if (CoercionResult) | |||
982 | return CoercionResult; | |||
983 | } | |||
984 | } | |||
985 | ||||
986 | const Expression *E = | |||
987 | createLoadExpression(LI->getType(), LoadAddressLeader, LI, | |||
988 | lookupMemoryAccessEquiv(DefiningAccess)); | |||
989 | return E; | |||
990 | } | |||
991 | ||||
992 | const Expression * | |||
993 | NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) { | |||
994 | auto *PI = PredInfo->getPredicateInfoFor(I); | |||
995 | if (!PI) | |||
996 | return nullptr; | |||
997 | ||||
998 | DEBUG(dbgs() << "Found predicate info from instruction !\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found predicate info from instruction !\n" ; } } while (false); | |||
999 | ||||
1000 | auto *PWC = dyn_cast<PredicateWithCondition>(PI); | |||
1001 | if (!PWC) | |||
1002 | return nullptr; | |||
1003 | ||||
1004 | auto *CopyOf = I->getOperand(0); | |||
1005 | auto *Cond = PWC->Condition; | |||
1006 | ||||
1007 | // If this a copy of the condition, it must be either true or false depending | |||
1008 | // on the predicate info type and edge | |||
1009 | if (CopyOf == Cond) { | |||
1010 | // We should not need to add predicate users because the predicate info is | |||
1011 | // already a use of this operand. | |||
1012 | if (isa<PredicateAssume>(PI)) | |||
1013 | return createConstantExpression(ConstantInt::getTrue(Cond->getType())); | |||
1014 | if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) { | |||
1015 | if (PBranch->TrueEdge) | |||
1016 | return createConstantExpression(ConstantInt::getTrue(Cond->getType())); | |||
1017 | return createConstantExpression(ConstantInt::getFalse(Cond->getType())); | |||
1018 | } | |||
1019 | if (auto *PSwitch = dyn_cast<PredicateSwitch>(PI)) | |||
1020 | return createConstantExpression(cast<Constant>(PSwitch->CaseValue)); | |||
1021 | } | |||
1022 | ||||
1023 | // Not a copy of the condition, so see what the predicates tell us about this | |||
1024 | // value. First, though, we check to make sure the value is actually a copy | |||
1025 | // of one of the condition operands. It's possible, in certain cases, for it | |||
1026 | // to be a copy of a predicateinfo copy. In particular, if two branch | |||
1027 | // operations use the same condition, and one branch dominates the other, we | |||
1028 | // will end up with a copy of a copy. This is currently a small deficiency in | |||
1029 | // predicateinfo. What will end up happening here is that we will value | |||
1030 | // number both copies the same anyway. | |||
1031 | ||||
1032 | // Everything below relies on the condition being a comparison. | |||
1033 | auto *Cmp = dyn_cast<CmpInst>(Cond); | |||
1034 | if (!Cmp) | |||
1035 | return nullptr; | |||
1036 | ||||
1037 | if (CopyOf != Cmp->getOperand(0) && CopyOf != Cmp->getOperand(1)) { | |||
1038 | DEBUG(dbgs() << "Copy is not of any condition operands!")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Copy is not of any condition operands!" ; } } while (false); | |||
1039 | return nullptr; | |||
1040 | } | |||
1041 | Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0)); | |||
1042 | Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1)); | |||
1043 | bool SwappedOps = false; | |||
1044 | // Sort the ops | |||
1045 | if (shouldSwapOperands(FirstOp, SecondOp)) { | |||
1046 | std::swap(FirstOp, SecondOp); | |||
1047 | SwappedOps = true; | |||
1048 | } | |||
1049 | CmpInst::Predicate Predicate = | |||
1050 | SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate(); | |||
1051 | ||||
1052 | if (isa<PredicateAssume>(PI)) { | |||
1053 | // If the comparison is true when the operands are equal, then we know the | |||
1054 | // operands are equal, because assumes must always be true. | |||
1055 | if (CmpInst::isTrueWhenEqual(Predicate)) { | |||
1056 | addPredicateUsers(PI, I); | |||
1057 | return createVariableOrConstant(FirstOp); | |||
1058 | } | |||
1059 | } | |||
1060 | if (const auto *PBranch = dyn_cast<PredicateBranch>(PI)) { | |||
1061 | // If we are *not* a copy of the comparison, we may equal to the other | |||
1062 | // operand when the predicate implies something about equality of | |||
1063 | // operations. In particular, if the comparison is true/false when the | |||
1064 | // operands are equal, and we are on the right edge, we know this operation | |||
1065 | // is equal to something. | |||
1066 | if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) || | |||
1067 | (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) { | |||
1068 | addPredicateUsers(PI, I); | |||
1069 | return createVariableOrConstant(FirstOp); | |||
1070 | } | |||
1071 | // Handle the special case of floating point. | |||
1072 | if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) || | |||
1073 | (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && | |||
1074 | isa<ConstantFP>(FirstOp) && !cast<ConstantFP>(FirstOp)->isZero()) { | |||
1075 | addPredicateUsers(PI, I); | |||
1076 | return createConstantExpression(cast<Constant>(FirstOp)); | |||
1077 | } | |||
1078 | } | |||
1079 | return nullptr; | |||
1080 | } | |||
1081 | ||||
1082 | // Evaluate read only and pure calls, and create an expression result. | |||
1083 | const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) { | |||
1084 | auto *CI = cast<CallInst>(I); | |||
1085 | if (auto *II = dyn_cast<IntrinsicInst>(I)) { | |||
1086 | // Instrinsics with the returned attribute are copies of arguments. | |||
1087 | if (auto *ReturnedValue = II->getReturnedArgOperand()) { | |||
1088 | if (II->getIntrinsicID() == Intrinsic::ssa_copy) | |||
1089 | if (const auto *Result = performSymbolicPredicateInfoEvaluation(I)) | |||
1090 | return Result; | |||
1091 | return createVariableOrConstant(ReturnedValue); | |||
1092 | } | |||
1093 | } | |||
1094 | if (AA->doesNotAccessMemory(CI)) { | |||
1095 | return createCallExpression(CI, nullptr); | |||
1096 | } else if (AA->onlyReadsMemory(CI)) { | |||
1097 | MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI); | |||
1098 | return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess)); | |||
1099 | } | |||
1100 | return nullptr; | |||
1101 | } | |||
1102 | ||||
1103 | // Update the memory access equivalence table to say that From is equal to To, | |||
1104 | // and return true if this is different from what already existed in the table. | |||
1105 | // FIXME: We need to audit all the places that current set a nullptr To, and fix | |||
1106 | // them. There should always be *some* congruence class, even if it is singular. | |||
1107 | bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To) { | |||
1108 | DEBUG(dbgs() << "Setting " << *From)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Setting " << *From; } } while (false); | |||
1109 | if (To) { | |||
1110 | DEBUG(dbgs() << " equivalent to congruence class ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << " equivalent to congruence class " ; } } while (false); | |||
1111 | DEBUG(dbgs() << To->ID << " with current memory access leader ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << To->ID << " with current memory access leader " ; } } while (false); | |||
1112 | DEBUG(dbgs() << *To->RepMemoryAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << *To->RepMemoryAccess; } } while (false); | |||
1113 | } else { | |||
1114 | DEBUG(dbgs() << " equivalent to itself")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << " equivalent to itself"; } } while (false); | |||
1115 | } | |||
1116 | DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "\n"; } } while (false); | |||
1117 | ||||
1118 | auto LookupResult = MemoryAccessToClass.find(From); | |||
1119 | bool Changed = false; | |||
1120 | // If it's already in the table, see if the value changed. | |||
1121 | if (LookupResult != MemoryAccessToClass.end()) { | |||
1122 | if (To && LookupResult->second != To) { | |||
1123 | // It wasn't equivalent before, and now it is. | |||
1124 | LookupResult->second = To; | |||
1125 | Changed = true; | |||
1126 | } else if (!To) { | |||
1127 | // It used to be equivalent to something, and now it's not. | |||
1128 | MemoryAccessToClass.erase(LookupResult); | |||
1129 | Changed = true; | |||
1130 | } | |||
1131 | } else { | |||
1132 | assert(!To &&((!To && "Memory equivalence should never change from nothing to something" ) ? static_cast<void> (0) : __assert_fail ("!To && \"Memory equivalence should never change from nothing to something\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1133, __PRETTY_FUNCTION__)) | |||
1133 | "Memory equivalence should never change from nothing to something")((!To && "Memory equivalence should never change from nothing to something" ) ? static_cast<void> (0) : __assert_fail ("!To && \"Memory equivalence should never change from nothing to something\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1133, __PRETTY_FUNCTION__)); | |||
1134 | } | |||
1135 | ||||
1136 | return Changed; | |||
1137 | } | |||
1138 | ||||
1139 | // Evaluate PHI nodes symbolically, and create an expression result. | |||
1140 | const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) { | |||
1141 | auto *E = cast<PHIExpression>(createPHIExpression(I)); | |||
1142 | // We match the semantics of SimplifyPhiNode from InstructionSimplify here. | |||
1143 | ||||
1144 | // See if all arguaments are the same. | |||
1145 | // We track if any were undef because they need special handling. | |||
1146 | bool HasUndef = false; | |||
1147 | auto Filtered = make_filter_range(E->operands(), [&](const Value *Arg) { | |||
1148 | if (Arg == I) | |||
1149 | return false; | |||
1150 | if (isa<UndefValue>(Arg)) { | |||
1151 | HasUndef = true; | |||
1152 | return false; | |||
1153 | } | |||
1154 | return true; | |||
1155 | }); | |||
1156 | // If we are left with no operands, it's undef | |||
1157 | if (Filtered.begin() == Filtered.end()) { | |||
1158 | DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified PHI node " << *I << " to undef" << "\n"; } } while (false) | |||
1159 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified PHI node " << *I << " to undef" << "\n"; } } while (false); | |||
1160 | deleteExpression(E); | |||
1161 | return createConstantExpression(UndefValue::get(I->getType())); | |||
1162 | } | |||
1163 | Value *AllSameValue = *(Filtered.begin()); | |||
1164 | ++Filtered.begin(); | |||
1165 | // Can't use std::equal here, sadly, because filter.begin moves. | |||
1166 | if (llvm::all_of(Filtered, [AllSameValue](const Value *V) { | |||
1167 | return V == AllSameValue; | |||
1168 | })) { | |||
1169 | // In LLVM's non-standard representation of phi nodes, it's possible to have | |||
1170 | // phi nodes with cycles (IE dependent on other phis that are .... dependent | |||
1171 | // on the original phi node), especially in weird CFG's where some arguments | |||
1172 | // are unreachable, or uninitialized along certain paths. This can cause | |||
1173 | // infinite loops during evaluation. We work around this by not trying to | |||
1174 | // really evaluate them independently, but instead using a variable | |||
1175 | // expression to say if one is equivalent to the other. | |||
1176 | // We also special case undef, so that if we have an undef, we can't use the | |||
1177 | // common value unless it dominates the phi block. | |||
1178 | if (HasUndef) { | |||
1179 | // Only have to check for instructions | |||
1180 | if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue)) | |||
1181 | if (!someEquivalentDominates(AllSameInst, I)) | |||
1182 | return E; | |||
1183 | } | |||
1184 | ||||
1185 | NumGVNPhisAllSame++; | |||
1186 | DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValuedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue << "\n"; } } while (false) | |||
1187 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue << "\n"; } } while (false); | |||
1188 | deleteExpression(E); | |||
1189 | return createVariableOrConstant(AllSameValue); | |||
1190 | } | |||
1191 | return E; | |||
1192 | } | |||
1193 | ||||
1194 | const Expression *NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) { | |||
1195 | if (auto *EI = dyn_cast<ExtractValueInst>(I)) { | |||
1196 | auto *II = dyn_cast<IntrinsicInst>(EI->getAggregateOperand()); | |||
1197 | if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) { | |||
1198 | unsigned Opcode = 0; | |||
1199 | // EI might be an extract from one of our recognised intrinsics. If it | |||
1200 | // is we'll synthesize a semantically equivalent expression instead on | |||
1201 | // an extract value expression. | |||
1202 | switch (II->getIntrinsicID()) { | |||
1203 | case Intrinsic::sadd_with_overflow: | |||
1204 | case Intrinsic::uadd_with_overflow: | |||
1205 | Opcode = Instruction::Add; | |||
1206 | break; | |||
1207 | case Intrinsic::ssub_with_overflow: | |||
1208 | case Intrinsic::usub_with_overflow: | |||
1209 | Opcode = Instruction::Sub; | |||
1210 | break; | |||
1211 | case Intrinsic::smul_with_overflow: | |||
1212 | case Intrinsic::umul_with_overflow: | |||
1213 | Opcode = Instruction::Mul; | |||
1214 | break; | |||
1215 | default: | |||
1216 | break; | |||
1217 | } | |||
1218 | ||||
1219 | if (Opcode != 0) { | |||
1220 | // Intrinsic recognized. Grab its args to finish building the | |||
1221 | // expression. | |||
1222 | assert(II->getNumArgOperands() == 2 &&((II->getNumArgOperands() == 2 && "Expect two args for recognised intrinsics." ) ? static_cast<void> (0) : __assert_fail ("II->getNumArgOperands() == 2 && \"Expect two args for recognised intrinsics.\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1223, __PRETTY_FUNCTION__)) | |||
1223 | "Expect two args for recognised intrinsics.")((II->getNumArgOperands() == 2 && "Expect two args for recognised intrinsics." ) ? static_cast<void> (0) : __assert_fail ("II->getNumArgOperands() == 2 && \"Expect two args for recognised intrinsics.\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1223, __PRETTY_FUNCTION__)); | |||
1224 | return createBinaryExpression( | |||
1225 | Opcode, EI->getType(), II->getArgOperand(0), II->getArgOperand(1)); | |||
1226 | } | |||
1227 | } | |||
1228 | } | |||
1229 | ||||
1230 | return createAggregateValueExpression(I); | |||
1231 | } | |||
1232 | const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) { | |||
1233 | auto *CI = dyn_cast<CmpInst>(I); | |||
1234 | // See if our operands are equal to those of a previous predicate, and if so, | |||
1235 | // if it implies true or false. | |||
1236 | auto Op0 = lookupOperandLeader(CI->getOperand(0)); | |||
1237 | auto Op1 = lookupOperandLeader(CI->getOperand(1)); | |||
1238 | auto OurPredicate = CI->getPredicate(); | |||
1239 | if (shouldSwapOperands(Op0, Op1)) { | |||
1240 | std::swap(Op0, Op1); | |||
1241 | OurPredicate = CI->getSwappedPredicate(); | |||
1242 | } | |||
1243 | ||||
1244 | // Avoid processing the same info twice | |||
1245 | const PredicateBase *LastPredInfo = nullptr; | |||
1246 | // See if we know something about the comparison itself, like it is the target | |||
1247 | // of an assume. | |||
1248 | auto *CmpPI = PredInfo->getPredicateInfoFor(I); | |||
1249 | if (dyn_cast_or_null<PredicateAssume>(CmpPI)) | |||
1250 | return createConstantExpression(ConstantInt::getTrue(CI->getType())); | |||
1251 | ||||
1252 | if (Op0 == Op1) { | |||
1253 | // This condition does not depend on predicates, no need to add users | |||
1254 | if (CI->isTrueWhenEqual()) | |||
1255 | return createConstantExpression(ConstantInt::getTrue(CI->getType())); | |||
1256 | else if (CI->isFalseWhenEqual()) | |||
1257 | return createConstantExpression(ConstantInt::getFalse(CI->getType())); | |||
1258 | } | |||
1259 | ||||
1260 | // NOTE: Because we are comparing both operands here and below, and using | |||
1261 | // previous comparisons, we rely on fact that predicateinfo knows to mark | |||
1262 | // comparisons that use renamed operands as users of the earlier comparisons. | |||
1263 | // It is *not* enough to just mark predicateinfo renamed operands as users of | |||
1264 | // the earlier comparisons, because the *other* operand may have changed in a | |||
1265 | // previous iteration. | |||
1266 | // Example: | |||
1267 | // icmp slt %a, %b | |||
1268 | // %b.0 = ssa.copy(%b) | |||
1269 | // false branch: | |||
1270 | // icmp slt %c, %b.0 | |||
1271 | ||||
1272 | // %c and %a may start out equal, and thus, the code below will say the second | |||
1273 | // %icmp is false. c may become equal to something else, and in that case the | |||
1274 | // %second icmp *must* be reexamined, but would not if only the renamed | |||
1275 | // %operands are considered users of the icmp. | |||
1276 | ||||
1277 | // *Currently* we only check one level of comparisons back, and only mark one | |||
1278 | // level back as touched when changes appen . If you modify this code to look | |||
1279 | // back farther through comparisons, you *must* mark the appropriate | |||
1280 | // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if | |||
1281 | // we know something just from the operands themselves | |||
1282 | ||||
1283 | // See if our operands have predicate info, so that we may be able to derive | |||
1284 | // something from a previous comparison. | |||
1285 | for (const auto &Op : CI->operands()) { | |||
1286 | auto *PI = PredInfo->getPredicateInfoFor(Op); | |||
1287 | if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) { | |||
1288 | if (PI == LastPredInfo) | |||
1289 | continue; | |||
1290 | LastPredInfo = PI; | |||
1291 | ||||
1292 | // TODO: Along the false edge, we may know more things too, like icmp of | |||
1293 | // same operands is false. | |||
1294 | // TODO: We only handle actual comparison conditions below, not and/or. | |||
1295 | auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition); | |||
1296 | if (!BranchCond) | |||
1297 | continue; | |||
1298 | auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0)); | |||
1299 | auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1)); | |||
1300 | auto BranchPredicate = BranchCond->getPredicate(); | |||
1301 | if (shouldSwapOperands(BranchOp0, BranchOp1)) { | |||
1302 | std::swap(BranchOp0, BranchOp1); | |||
1303 | BranchPredicate = BranchCond->getSwappedPredicate(); | |||
1304 | } | |||
1305 | if (BranchOp0 == Op0 && BranchOp1 == Op1) { | |||
1306 | if (PBranch->TrueEdge) { | |||
1307 | // If we know the previous predicate is true and we are in the true | |||
1308 | // edge then we may be implied true or false. | |||
1309 | if (CmpInst::isImpliedTrueByMatchingCmp(OurPredicate, | |||
1310 | BranchPredicate)) { | |||
1311 | addPredicateUsers(PI, I); | |||
1312 | return createConstantExpression( | |||
1313 | ConstantInt::getTrue(CI->getType())); | |||
1314 | } | |||
1315 | ||||
1316 | if (CmpInst::isImpliedFalseByMatchingCmp(OurPredicate, | |||
1317 | BranchPredicate)) { | |||
1318 | addPredicateUsers(PI, I); | |||
1319 | return createConstantExpression( | |||
1320 | ConstantInt::getFalse(CI->getType())); | |||
1321 | } | |||
1322 | ||||
1323 | } else { | |||
1324 | // Just handle the ne and eq cases, where if we have the same | |||
1325 | // operands, we may know something. | |||
1326 | if (BranchPredicate == OurPredicate) { | |||
1327 | addPredicateUsers(PI, I); | |||
1328 | // Same predicate, same ops,we know it was false, so this is false. | |||
1329 | return createConstantExpression( | |||
1330 | ConstantInt::getFalse(CI->getType())); | |||
1331 | } else if (BranchPredicate == | |||
1332 | CmpInst::getInversePredicate(OurPredicate)) { | |||
1333 | addPredicateUsers(PI, I); | |||
1334 | // Inverse predicate, we know the other was false, so this is true. | |||
1335 | // FIXME: Double check this | |||
1336 | return createConstantExpression( | |||
1337 | ConstantInt::getTrue(CI->getType())); | |||
1338 | } | |||
1339 | } | |||
1340 | } | |||
1341 | } | |||
1342 | } | |||
1343 | // Create expression will take care of simplifyCmpInst | |||
1344 | return createExpression(I); | |||
1345 | } | |||
1346 | ||||
1347 | // Substitute and symbolize the value before value numbering. | |||
1348 | const Expression *NewGVN::performSymbolicEvaluation(Value *V) { | |||
1349 | const Expression *E = nullptr; | |||
1350 | if (auto *C = dyn_cast<Constant>(V)) | |||
1351 | E = createConstantExpression(C); | |||
1352 | else if (isa<Argument>(V) || isa<GlobalVariable>(V)) { | |||
1353 | E = createVariableExpression(V); | |||
1354 | } else { | |||
1355 | // TODO: memory intrinsics. | |||
1356 | // TODO: Some day, we should do the forward propagation and reassociation | |||
1357 | // parts of the algorithm. | |||
1358 | auto *I = cast<Instruction>(V); | |||
1359 | switch (I->getOpcode()) { | |||
1360 | case Instruction::ExtractValue: | |||
1361 | case Instruction::InsertValue: | |||
1362 | E = performSymbolicAggrValueEvaluation(I); | |||
1363 | break; | |||
1364 | case Instruction::PHI: | |||
1365 | E = performSymbolicPHIEvaluation(I); | |||
1366 | break; | |||
1367 | case Instruction::Call: | |||
1368 | E = performSymbolicCallEvaluation(I); | |||
1369 | break; | |||
1370 | case Instruction::Store: | |||
1371 | E = performSymbolicStoreEvaluation(I); | |||
1372 | break; | |||
1373 | case Instruction::Load: | |||
1374 | E = performSymbolicLoadEvaluation(I); | |||
1375 | break; | |||
1376 | case Instruction::BitCast: { | |||
1377 | E = createExpression(I); | |||
1378 | } break; | |||
1379 | case Instruction::ICmp: | |||
1380 | case Instruction::FCmp: { | |||
1381 | E = performSymbolicCmpEvaluation(I); | |||
1382 | } break; | |||
1383 | case Instruction::Add: | |||
1384 | case Instruction::FAdd: | |||
1385 | case Instruction::Sub: | |||
1386 | case Instruction::FSub: | |||
1387 | case Instruction::Mul: | |||
1388 | case Instruction::FMul: | |||
1389 | case Instruction::UDiv: | |||
1390 | case Instruction::SDiv: | |||
1391 | case Instruction::FDiv: | |||
1392 | case Instruction::URem: | |||
1393 | case Instruction::SRem: | |||
1394 | case Instruction::FRem: | |||
1395 | case Instruction::Shl: | |||
1396 | case Instruction::LShr: | |||
1397 | case Instruction::AShr: | |||
1398 | case Instruction::And: | |||
1399 | case Instruction::Or: | |||
1400 | case Instruction::Xor: | |||
1401 | case Instruction::Trunc: | |||
1402 | case Instruction::ZExt: | |||
1403 | case Instruction::SExt: | |||
1404 | case Instruction::FPToUI: | |||
1405 | case Instruction::FPToSI: | |||
1406 | case Instruction::UIToFP: | |||
1407 | case Instruction::SIToFP: | |||
1408 | case Instruction::FPTrunc: | |||
1409 | case Instruction::FPExt: | |||
1410 | case Instruction::PtrToInt: | |||
1411 | case Instruction::IntToPtr: | |||
1412 | case Instruction::Select: | |||
1413 | case Instruction::ExtractElement: | |||
1414 | case Instruction::InsertElement: | |||
1415 | case Instruction::ShuffleVector: | |||
1416 | case Instruction::GetElementPtr: | |||
1417 | E = createExpression(I); | |||
1418 | break; | |||
1419 | default: | |||
1420 | return nullptr; | |||
1421 | } | |||
1422 | } | |||
1423 | return E; | |||
1424 | } | |||
1425 | ||||
1426 | void NewGVN::markUsersTouched(Value *V) { | |||
1427 | // Now mark the users as touched. | |||
1428 | for (auto *User : V->users()) { | |||
1429 | assert(isa<Instruction>(User) && "Use of value not within an instruction?")((isa<Instruction>(User) && "Use of value not within an instruction?" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(User) && \"Use of value not within an instruction?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1429, __PRETTY_FUNCTION__)); | |||
1430 | TouchedInstructions.set(InstrDFS.lookup(User)); | |||
1431 | } | |||
1432 | } | |||
1433 | ||||
1434 | void NewGVN::markMemoryUsersTouched(MemoryAccess *MA) { | |||
1435 | for (auto U : MA->users()) { | |||
1436 | if (auto *MUD = dyn_cast<MemoryUseOrDef>(U)) | |||
1437 | TouchedInstructions.set(InstrDFS.lookup(MUD->getMemoryInst())); | |||
1438 | else | |||
1439 | TouchedInstructions.set(InstrDFS.lookup(U)); | |||
1440 | } | |||
1441 | } | |||
1442 | ||||
1443 | // Add I to the set of users of a given predicate. | |||
1444 | void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) { | |||
1445 | if (auto *PBranch = dyn_cast<PredicateBranch>(PB)) | |||
1446 | PredicateToUsers[PBranch->Condition].insert(I); | |||
1447 | else if (auto *PAssume = dyn_cast<PredicateBranch>(PB)) | |||
1448 | PredicateToUsers[PAssume->Condition].insert(I); | |||
1449 | } | |||
1450 | ||||
1451 | // Touch all the predicates that depend on this instruction. | |||
1452 | void NewGVN::markPredicateUsersTouched(Instruction *I) { | |||
1453 | const auto Result = PredicateToUsers.find(I); | |||
1454 | if (Result != PredicateToUsers.end()) { | |||
1455 | for (auto *User : Result->second) | |||
1456 | TouchedInstructions.set(InstrDFS.lookup(User)); | |||
1457 | PredicateToUsers.erase(Result); | |||
1458 | } | |||
1459 | } | |||
1460 | ||||
1461 | // Touch the instructions that need to be updated after a congruence class has a | |||
1462 | // leader change, and mark changed values. | |||
1463 | void NewGVN::markLeaderChangeTouched(CongruenceClass *CC) { | |||
1464 | for (auto M : CC->Members) { | |||
1465 | if (auto *I = dyn_cast<Instruction>(M)) | |||
1466 | TouchedInstructions.set(InstrDFS.lookup(I)); | |||
1467 | LeaderChanges.insert(M); | |||
1468 | } | |||
1469 | } | |||
1470 | ||||
1471 | // Move a value, currently in OldClass, to be part of NewClass | |||
1472 | // Update OldClass for the move (including changing leaders, etc) | |||
1473 | void NewGVN::moveValueToNewCongruenceClass(Instruction *I, | |||
1474 | CongruenceClass *OldClass, | |||
1475 | CongruenceClass *NewClass) { | |||
1476 | DEBUG(dbgs() << "New congruence class for " << I << " is " << NewClass->IDdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "New congruence class for " << I << " is " << NewClass->ID << "\n"; } } while (false) | |||
1477 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "New congruence class for " << I << " is " << NewClass->ID << "\n"; } } while (false); | |||
1478 | ||||
1479 | if (I == OldClass->NextLeader.first) | |||
1480 | OldClass->NextLeader = {nullptr, ~0U}; | |||
1481 | ||||
1482 | // It's possible, though unlikely, for us to discover equivalences such | |||
1483 | // that the current leader does not dominate the old one. | |||
1484 | // This statistic tracks how often this happens. | |||
1485 | // We assert on phi nodes when this happens, currently, for debugging, because | |||
1486 | // we want to make sure we name phi node cycles properly. | |||
1487 | if (isa<Instruction>(NewClass->RepLeader) && NewClass->RepLeader && | |||
1488 | I != NewClass->RepLeader) { | |||
1489 | auto *IBB = I->getParent(); | |||
1490 | auto *NCBB = cast<Instruction>(NewClass->RepLeader)->getParent(); | |||
1491 | bool Dominated = IBB == NCBB && | |||
1492 | InstrDFS.lookup(I) < InstrDFS.lookup(NewClass->RepLeader); | |||
1493 | Dominated = Dominated || DT->properlyDominates(IBB, NCBB); | |||
1494 | if (Dominated) { | |||
1495 | ++NumGVNNotMostDominatingLeader; | |||
1496 | assert(((!isa<PHINode>(I) && "New class for instruction should not be dominated by instruction" ) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(I) && \"New class for instruction should not be dominated by instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1498, __PRETTY_FUNCTION__)) | |||
1497 | !isa<PHINode>(I) &&((!isa<PHINode>(I) && "New class for instruction should not be dominated by instruction" ) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(I) && \"New class for instruction should not be dominated by instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1498, __PRETTY_FUNCTION__)) | |||
1498 | "New class for instruction should not be dominated by instruction")((!isa<PHINode>(I) && "New class for instruction should not be dominated by instruction" ) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(I) && \"New class for instruction should not be dominated by instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1498, __PRETTY_FUNCTION__)); | |||
1499 | } | |||
1500 | } | |||
1501 | ||||
1502 | if (NewClass->RepLeader != I) { | |||
1503 | auto DFSNum = InstrDFS.lookup(I); | |||
1504 | if (DFSNum < NewClass->NextLeader.second) | |||
1505 | NewClass->NextLeader = {I, DFSNum}; | |||
1506 | } | |||
1507 | ||||
1508 | OldClass->Members.erase(I); | |||
1509 | NewClass->Members.insert(I); | |||
1510 | MemoryAccess *StoreAccess = nullptr; | |||
1511 | if (auto *SI = dyn_cast<StoreInst>(I)) { | |||
1512 | StoreAccess = MSSA->getMemoryAccess(SI); | |||
1513 | --OldClass->StoreCount; | |||
1514 | assert(OldClass->StoreCount >= 0)((OldClass->StoreCount >= 0) ? static_cast<void> ( 0) : __assert_fail ("OldClass->StoreCount >= 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1514, __PRETTY_FUNCTION__)); | |||
1515 | ++NewClass->StoreCount; | |||
1516 | assert(NewClass->StoreCount > 0)((NewClass->StoreCount > 0) ? static_cast<void> ( 0) : __assert_fail ("NewClass->StoreCount > 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1516, __PRETTY_FUNCTION__)); | |||
1517 | if (!NewClass->RepMemoryAccess) { | |||
1518 | // If we don't have a representative memory access, it better be the only | |||
1519 | // store in there. | |||
1520 | assert(NewClass->StoreCount == 1)((NewClass->StoreCount == 1) ? static_cast<void> (0) : __assert_fail ("NewClass->StoreCount == 1", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1520, __PRETTY_FUNCTION__)); | |||
1521 | NewClass->RepMemoryAccess = StoreAccess; | |||
1522 | } | |||
1523 | setMemoryAccessEquivTo(StoreAccess, NewClass); | |||
1524 | } | |||
1525 | ||||
1526 | ValueToClass[I] = NewClass; | |||
1527 | // See if we destroyed the class or need to swap leaders. | |||
1528 | if (OldClass->Members.empty() && OldClass != TOPClass) { | |||
1529 | if (OldClass->DefiningExpr) { | |||
1530 | OldClass->Dead = true; | |||
1531 | DEBUG(dbgs() << "Erasing expression " << OldClass->DefiningExprdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Erasing expression " << OldClass ->DefiningExpr << " from table\n"; } } while (false) | |||
1532 | << " from table\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Erasing expression " << OldClass ->DefiningExpr << " from table\n"; } } while (false); | |||
1533 | ExpressionToClass.erase(OldClass->DefiningExpr); | |||
1534 | } | |||
1535 | } else if (OldClass->RepLeader == I) { | |||
1536 | // When the leader changes, the value numbering of | |||
1537 | // everything may change due to symbolization changes, so we need to | |||
1538 | // reprocess. | |||
1539 | DEBUG(dbgs() << "Leader change!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Leader change!\n"; } } while ( false); | |||
1540 | ++NumGVNLeaderChanges; | |||
1541 | // Destroy the stored value if there are no more stores to represent it. | |||
1542 | if (OldClass->StoreCount == 0) { | |||
1543 | if (OldClass->RepStoredValue != nullptr) | |||
1544 | OldClass->RepStoredValue = nullptr; | |||
1545 | if (OldClass->RepMemoryAccess != nullptr) | |||
1546 | OldClass->RepMemoryAccess = nullptr; | |||
1547 | } | |||
1548 | ||||
1549 | // If we destroy the old access leader, we have to effectively destroy the | |||
1550 | // congruence class. When it comes to scalars, anything with the same value | |||
1551 | // is as good as any other. That means that one leader is as good as | |||
1552 | // another, and as long as you have some leader for the value, you are | |||
1553 | // good.. When it comes to *memory states*, only one particular thing really | |||
1554 | // represents the definition of a given memory state. Once it goes away, we | |||
1555 | // need to re-evaluate which pieces of memory are really still | |||
1556 | // equivalent. The best way to do this is to re-value number things. The | |||
1557 | // only way to really make that happen is to destroy the rest of the class. | |||
1558 | // In order to effectively destroy the class, we reset ExpressionToClass for | |||
1559 | // each by using the ValueToExpression mapping. The members later get | |||
1560 | // marked as touched due to the leader change. We will create new | |||
1561 | // congruence classes, and the pieces that are still equivalent will end | |||
1562 | // back together in a new class. If this becomes too expensive, it is | |||
1563 | // possible to use a versioning scheme for the congruence classes to avoid | |||
1564 | // the expressions finding this old class. | |||
1565 | if (OldClass->StoreCount > 0 && OldClass->RepMemoryAccess == StoreAccess) { | |||
1566 | DEBUG(dbgs() << "Kicking everything out of class " << OldClass->IDdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Kicking everything out of class " << OldClass->ID << " because memory access leader changed" ; } } while (false) | |||
1567 | << " because memory access leader changed")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Kicking everything out of class " << OldClass->ID << " because memory access leader changed" ; } } while (false); | |||
1568 | for (auto Member : OldClass->Members) | |||
1569 | ExpressionToClass.erase(ValueToExpression.lookup(Member)); | |||
1570 | } | |||
1571 | ||||
1572 | // We don't need to sort members if there is only 1, and we don't care about | |||
1573 | // sorting the TOP class because everything either gets out of it or is | |||
1574 | // unreachable. | |||
1575 | if (OldClass->Members.size() == 1 || OldClass == TOPClass) { | |||
1576 | OldClass->RepLeader = *(OldClass->Members.begin()); | |||
1577 | } else if (OldClass->NextLeader.first) { | |||
1578 | ++NumGVNAvoidedSortedLeaderChanges; | |||
1579 | OldClass->RepLeader = OldClass->NextLeader.first; | |||
1580 | OldClass->NextLeader = {nullptr, ~0U}; | |||
1581 | } else { | |||
1582 | ++NumGVNSortedLeaderChanges; | |||
1583 | // TODO: If this ends up to slow, we can maintain a dual structure for | |||
1584 | // member testing/insertion, or keep things mostly sorted, and sort only | |||
1585 | // here, or .... | |||
1586 | std::pair<Value *, unsigned> MinDFS = {nullptr, ~0U}; | |||
1587 | for (const auto X : OldClass->Members) { | |||
1588 | auto DFSNum = InstrDFS.lookup(X); | |||
1589 | if (DFSNum < MinDFS.second) | |||
1590 | MinDFS = {X, DFSNum}; | |||
1591 | } | |||
1592 | OldClass->RepLeader = MinDFS.first; | |||
1593 | } | |||
1594 | markLeaderChangeTouched(OldClass); | |||
1595 | } | |||
1596 | } | |||
1597 | ||||
1598 | // Perform congruence finding on a given value numbering expression. | |||
1599 | void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) { | |||
1600 | ValueToExpression[I] = E; | |||
1601 | // This is guaranteed to return something, since it will at least find | |||
1602 | // TOP. | |||
1603 | ||||
1604 | CongruenceClass *IClass = ValueToClass[I]; | |||
1605 | assert(IClass && "Should have found a IClass")((IClass && "Should have found a IClass") ? static_cast <void> (0) : __assert_fail ("IClass && \"Should have found a IClass\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1605, __PRETTY_FUNCTION__)); | |||
1606 | // Dead classes should have been eliminated from the mapping. | |||
1607 | assert(!IClass->Dead && "Found a dead class")((!IClass->Dead && "Found a dead class") ? static_cast <void> (0) : __assert_fail ("!IClass->Dead && \"Found a dead class\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1607, __PRETTY_FUNCTION__)); | |||
1608 | ||||
1609 | CongruenceClass *EClass; | |||
1610 | if (const auto *VE = dyn_cast<VariableExpression>(E)) { | |||
1611 | EClass = ValueToClass[VE->getVariableValue()]; | |||
1612 | } else { | |||
1613 | auto lookupResult = ExpressionToClass.insert({E, nullptr}); | |||
1614 | ||||
1615 | // If it's not in the value table, create a new congruence class. | |||
1616 | if (lookupResult.second) { | |||
1617 | CongruenceClass *NewClass = createCongruenceClass(nullptr, E); | |||
1618 | auto place = lookupResult.first; | |||
1619 | place->second = NewClass; | |||
1620 | ||||
1621 | // Constants and variables should always be made the leader. | |||
1622 | if (const auto *CE = dyn_cast<ConstantExpression>(E)) { | |||
1623 | NewClass->RepLeader = CE->getConstantValue(); | |||
1624 | } else if (const auto *SE = dyn_cast<StoreExpression>(E)) { | |||
1625 | StoreInst *SI = SE->getStoreInst(); | |||
1626 | NewClass->RepLeader = SI; | |||
1627 | NewClass->RepStoredValue = lookupOperandLeader(SI->getValueOperand()); | |||
1628 | // The RepMemoryAccess field will be filled in properly by the | |||
1629 | // moveValueToNewCongruenceClass call. | |||
1630 | } else { | |||
1631 | NewClass->RepLeader = I; | |||
1632 | } | |||
1633 | assert(!isa<VariableExpression>(E) &&((!isa<VariableExpression>(E) && "VariableExpression should have been handled already" ) ? static_cast<void> (0) : __assert_fail ("!isa<VariableExpression>(E) && \"VariableExpression should have been handled already\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1634, __PRETTY_FUNCTION__)) | |||
1634 | "VariableExpression should have been handled already")((!isa<VariableExpression>(E) && "VariableExpression should have been handled already" ) ? static_cast<void> (0) : __assert_fail ("!isa<VariableExpression>(E) && \"VariableExpression should have been handled already\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1634, __PRETTY_FUNCTION__)); | |||
1635 | ||||
1636 | EClass = NewClass; | |||
1637 | DEBUG(dbgs() << "Created new congruence class for " << *Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Created new congruence class for " << *I << " using expression " << *E << " at " << NewClass->ID << " and leader " << *(NewClass->RepLeader); } } while (false) | |||
1638 | << " using expression " << *E << " at " << NewClass->IDdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Created new congruence class for " << *I << " using expression " << *E << " at " << NewClass->ID << " and leader " << *(NewClass->RepLeader); } } while (false) | |||
1639 | << " and leader " << *(NewClass->RepLeader))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Created new congruence class for " << *I << " using expression " << *E << " at " << NewClass->ID << " and leader " << *(NewClass->RepLeader); } } while (false); | |||
1640 | if (NewClass->RepStoredValue) | |||
1641 | DEBUG(dbgs() << " and stored value " << *(NewClass->RepStoredValue))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << " and stored value " << * (NewClass->RepStoredValue); } } while (false); | |||
1642 | DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "\n"; } } while (false); | |||
1643 | DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Hash value was " << E-> getHashValue() << "\n"; } } while (false); | |||
1644 | } else { | |||
1645 | EClass = lookupResult.first->second; | |||
1646 | if (isa<ConstantExpression>(E)) | |||
1647 | assert(isa<Constant>(EClass->RepLeader) &&((isa<Constant>(EClass->RepLeader) && "Any class with a constant expression should have a " "constant leader") ? static_cast<void> (0) : __assert_fail ("isa<Constant>(EClass->RepLeader) && \"Any class with a constant expression should have a \" \"constant leader\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1649, __PRETTY_FUNCTION__)) | |||
1648 | "Any class with a constant expression should have a "((isa<Constant>(EClass->RepLeader) && "Any class with a constant expression should have a " "constant leader") ? static_cast<void> (0) : __assert_fail ("isa<Constant>(EClass->RepLeader) && \"Any class with a constant expression should have a \" \"constant leader\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1649, __PRETTY_FUNCTION__)) | |||
1649 | "constant leader")((isa<Constant>(EClass->RepLeader) && "Any class with a constant expression should have a " "constant leader") ? static_cast<void> (0) : __assert_fail ("isa<Constant>(EClass->RepLeader) && \"Any class with a constant expression should have a \" \"constant leader\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1649, __PRETTY_FUNCTION__)); | |||
1650 | ||||
1651 | assert(EClass && "Somehow don't have an eclass")((EClass && "Somehow don't have an eclass") ? static_cast <void> (0) : __assert_fail ("EClass && \"Somehow don't have an eclass\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1651, __PRETTY_FUNCTION__)); | |||
1652 | ||||
1653 | assert(!EClass->Dead && "We accidentally looked up a dead class")((!EClass->Dead && "We accidentally looked up a dead class" ) ? static_cast<void> (0) : __assert_fail ("!EClass->Dead && \"We accidentally looked up a dead class\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1653, __PRETTY_FUNCTION__)); | |||
1654 | } | |||
1655 | } | |||
1656 | bool ClassChanged = IClass != EClass; | |||
1657 | bool LeaderChanged = LeaderChanges.erase(I); | |||
1658 | if (ClassChanged || LeaderChanged) { | |||
1659 | DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << Edo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found class " << EClass-> ID << " for expression " << E << "\n"; } } while (false) | |||
1660 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found class " << EClass-> ID << " for expression " << E << "\n"; } } while (false); | |||
1661 | ||||
1662 | if (ClassChanged) | |||
1663 | moveValueToNewCongruenceClass(I, IClass, EClass); | |||
1664 | markUsersTouched(I); | |||
1665 | if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) | |||
1666 | markMemoryUsersTouched(MA); | |||
1667 | if (auto *CI = dyn_cast<CmpInst>(I)) | |||
1668 | markPredicateUsersTouched(CI); | |||
1669 | } | |||
1670 | } | |||
1671 | ||||
1672 | // Process the fact that Edge (from, to) is reachable, including marking | |||
1673 | // any newly reachable blocks and instructions for processing. | |||
1674 | void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { | |||
1675 | // Check if the Edge was reachable before. | |||
1676 | if (ReachableEdges.insert({From, To}).second) { | |||
1677 | // If this block wasn't reachable before, all instructions are touched. | |||
1678 | if (ReachableBlocks.insert(To).second) { | |||
1679 | DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Block " << getBlockName( To) << " marked reachable\n"; } } while (false); | |||
1680 | const auto &InstRange = BlockInstRange.lookup(To); | |||
1681 | TouchedInstructions.set(InstRange.first, InstRange.second); | |||
1682 | } else { | |||
1683 | DEBUG(dbgs() << "Block " << getBlockName(To)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Block " << getBlockName( To) << " was reachable, but new edge {" << getBlockName (From) << "," << getBlockName(To) << "} to it found\n" ; } } while (false) | |||
1684 | << " was reachable, but new edge {" << getBlockName(From)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Block " << getBlockName( To) << " was reachable, but new edge {" << getBlockName (From) << "," << getBlockName(To) << "} to it found\n" ; } } while (false) | |||
1685 | << "," << getBlockName(To) << "} to it found\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Block " << getBlockName( To) << " was reachable, but new edge {" << getBlockName (From) << "," << getBlockName(To) << "} to it found\n" ; } } while (false); | |||
1686 | ||||
1687 | // We've made an edge reachable to an existing block, which may | |||
1688 | // impact predicates. Otherwise, only mark the phi nodes as touched, as | |||
1689 | // they are the only thing that depend on new edges. Anything using their | |||
1690 | // values will get propagated to if necessary. | |||
1691 | if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To)) | |||
1692 | TouchedInstructions.set(InstrDFS.lookup(MemPhi)); | |||
1693 | ||||
1694 | auto BI = To->begin(); | |||
1695 | while (isa<PHINode>(BI)) { | |||
1696 | TouchedInstructions.set(InstrDFS.lookup(&*BI)); | |||
1697 | ++BI; | |||
1698 | } | |||
1699 | } | |||
1700 | } | |||
1701 | } | |||
1702 | ||||
1703 | // Given a predicate condition (from a switch, cmp, or whatever) and a block, | |||
1704 | // see if we know some constant value for it already. | |||
1705 | Value *NewGVN::findConditionEquivalence(Value *Cond) const { | |||
1706 | auto Result = lookupOperandLeader(Cond); | |||
1707 | if (isa<Constant>(Result)) | |||
1708 | return Result; | |||
1709 | return nullptr; | |||
1710 | } | |||
1711 | ||||
1712 | // Process the outgoing edges of a block for reachability. | |||
1713 | void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) { | |||
1714 | // Evaluate reachability of terminator instruction. | |||
1715 | BranchInst *BR; | |||
1716 | if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) { | |||
1717 | Value *Cond = BR->getCondition(); | |||
1718 | Value *CondEvaluated = findConditionEquivalence(Cond); | |||
1719 | if (!CondEvaluated) { | |||
1720 | if (auto *I = dyn_cast<Instruction>(Cond)) { | |||
1721 | const Expression *E = createExpression(I); | |||
1722 | if (const auto *CE = dyn_cast<ConstantExpression>(E)) { | |||
1723 | CondEvaluated = CE->getConstantValue(); | |||
1724 | } | |||
1725 | } else if (isa<ConstantInt>(Cond)) { | |||
1726 | CondEvaluated = Cond; | |||
1727 | } | |||
1728 | } | |||
1729 | ConstantInt *CI; | |||
1730 | BasicBlock *TrueSucc = BR->getSuccessor(0); | |||
1731 | BasicBlock *FalseSucc = BR->getSuccessor(1); | |||
1732 | if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) { | |||
1733 | if (CI->isOne()) { | |||
1734 | DEBUG(dbgs() << "Condition for Terminator " << *TIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Condition for Terminator " << *TI << " evaluated to true\n"; } } while (false) | |||
1735 | << " evaluated to true\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Condition for Terminator " << *TI << " evaluated to true\n"; } } while (false); | |||
1736 | updateReachableEdge(B, TrueSucc); | |||
1737 | } else if (CI->isZero()) { | |||
1738 | DEBUG(dbgs() << "Condition for Terminator " << *TIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Condition for Terminator " << *TI << " evaluated to false\n"; } } while (false) | |||
1739 | << " evaluated to false\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Condition for Terminator " << *TI << " evaluated to false\n"; } } while (false); | |||
1740 | updateReachableEdge(B, FalseSucc); | |||
1741 | } | |||
1742 | } else { | |||
1743 | updateReachableEdge(B, TrueSucc); | |||
1744 | updateReachableEdge(B, FalseSucc); | |||
1745 | } | |||
1746 | } else if (auto *SI = dyn_cast<SwitchInst>(TI)) { | |||
1747 | // For switches, propagate the case values into the case | |||
1748 | // destinations. | |||
1749 | ||||
1750 | // Remember how many outgoing edges there are to every successor. | |||
1751 | SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges; | |||
1752 | ||||
1753 | Value *SwitchCond = SI->getCondition(); | |||
1754 | Value *CondEvaluated = findConditionEquivalence(SwitchCond); | |||
1755 | // See if we were able to turn this switch statement into a constant. | |||
1756 | if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) { | |||
1757 | auto *CondVal = cast<ConstantInt>(CondEvaluated); | |||
1758 | // We should be able to get case value for this. | |||
1759 | auto CaseVal = SI->findCaseValue(CondVal); | |||
1760 | if (CaseVal.getCaseSuccessor() == SI->getDefaultDest()) { | |||
1761 | // We proved the value is outside of the range of the case. | |||
1762 | // We can't do anything other than mark the default dest as reachable, | |||
1763 | // and go home. | |||
1764 | updateReachableEdge(B, SI->getDefaultDest()); | |||
1765 | return; | |||
1766 | } | |||
1767 | // Now get where it goes and mark it reachable. | |||
1768 | BasicBlock *TargetBlock = CaseVal.getCaseSuccessor(); | |||
1769 | updateReachableEdge(B, TargetBlock); | |||
1770 | } else { | |||
1771 | for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { | |||
1772 | BasicBlock *TargetBlock = SI->getSuccessor(i); | |||
1773 | ++SwitchEdges[TargetBlock]; | |||
1774 | updateReachableEdge(B, TargetBlock); | |||
1775 | } | |||
1776 | } | |||
1777 | } else { | |||
1778 | // Otherwise this is either unconditional, or a type we have no | |||
1779 | // idea about. Just mark successors as reachable. | |||
1780 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { | |||
1781 | BasicBlock *TargetBlock = TI->getSuccessor(i); | |||
1782 | updateReachableEdge(B, TargetBlock); | |||
1783 | } | |||
1784 | ||||
1785 | // This also may be a memory defining terminator, in which case, set it | |||
1786 | // equivalent to nothing. | |||
1787 | if (MemoryAccess *MA = MSSA->getMemoryAccess(TI)) | |||
1788 | setMemoryAccessEquivTo(MA, nullptr); | |||
1789 | } | |||
1790 | } | |||
1791 | ||||
1792 | // The algorithm initially places the values of the routine in the TOP | |||
1793 | // congruence class. The leader of TOP is the undetermined value `undef`. | |||
1794 | // When the algorithm has finished, values still in TOP are unreachable. | |||
1795 | void NewGVN::initializeCongruenceClasses(Function &F) { | |||
1796 | // FIXME now i can't remember why this is 2 | |||
1797 | NextCongruenceNum = 2; | |||
1798 | // Initialize all other instructions to be in TOP class. | |||
1799 | CongruenceClass::MemberSet InitialValues; | |||
1800 | TOPClass = createCongruenceClass(nullptr, nullptr); | |||
1801 | TOPClass->RepMemoryAccess = MSSA->getLiveOnEntryDef(); | |||
1802 | for (auto &B : F) { | |||
1803 | if (auto *MP = MSSA->getMemoryAccess(&B)) | |||
1804 | MemoryAccessToClass[MP] = TOPClass; | |||
1805 | ||||
1806 | for (auto &I : B) { | |||
1807 | // Don't insert void terminators into the class. We don't value number | |||
1808 | // them, and they just end up sitting in TOP. | |||
1809 | if (isa<TerminatorInst>(I) && I.getType()->isVoidTy()) | |||
1810 | continue; | |||
1811 | InitialValues.insert(&I); | |||
1812 | ValueToClass[&I] = TOPClass; | |||
1813 | ||||
1814 | // All memory accesses are equivalent to live on entry to start. They must | |||
1815 | // be initialized to something so that initial changes are noticed. For | |||
1816 | // the maximal answer, we initialize them all to be the same as | |||
1817 | // liveOnEntry. Note that to save time, we only initialize the | |||
1818 | // MemoryDef's for stores and all MemoryPhis to be equal. Right now, no | |||
1819 | // other expression can generate a memory equivalence. If we start | |||
1820 | // handling memcpy/etc, we can expand this. | |||
1821 | if (isa<StoreInst>(&I)) { | |||
1822 | MemoryAccessToClass[MSSA->getMemoryAccess(&I)] = TOPClass; | |||
1823 | ++TOPClass->StoreCount; | |||
1824 | assert(TOPClass->StoreCount > 0)((TOPClass->StoreCount > 0) ? static_cast<void> ( 0) : __assert_fail ("TOPClass->StoreCount > 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1824, __PRETTY_FUNCTION__)); | |||
1825 | } | |||
1826 | } | |||
1827 | } | |||
1828 | TOPClass->Members.swap(InitialValues); | |||
1829 | ||||
1830 | // Initialize arguments to be in their own unique congruence classes | |||
1831 | for (auto &FA : F.args()) | |||
1832 | createSingletonCongruenceClass(&FA); | |||
1833 | } | |||
1834 | ||||
1835 | void NewGVN::cleanupTables() { | |||
1836 | for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) { | |||
1837 | DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->ID << " has "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Congruence class " << CongruenceClasses [i]->ID << " has " << CongruenceClasses[i]-> Members.size() << " members\n"; } } while (false) | |||
1838 | << CongruenceClasses[i]->Members.size() << " members\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Congruence class " << CongruenceClasses [i]->ID << " has " << CongruenceClasses[i]-> Members.size() << " members\n"; } } while (false); | |||
1839 | // Make sure we delete the congruence class (probably worth switching to | |||
1840 | // a unique_ptr at some point. | |||
1841 | delete CongruenceClasses[i]; | |||
1842 | CongruenceClasses[i] = nullptr; | |||
1843 | } | |||
1844 | ||||
1845 | ValueToClass.clear(); | |||
1846 | ArgRecycler.clear(ExpressionAllocator); | |||
1847 | ExpressionAllocator.Reset(); | |||
1848 | CongruenceClasses.clear(); | |||
1849 | ExpressionToClass.clear(); | |||
1850 | ValueToExpression.clear(); | |||
1851 | ReachableBlocks.clear(); | |||
1852 | ReachableEdges.clear(); | |||
1853 | #ifndef NDEBUG | |||
1854 | ProcessedCount.clear(); | |||
1855 | #endif | |||
1856 | InstrDFS.clear(); | |||
1857 | InstructionsToErase.clear(); | |||
1858 | DFSToInstr.clear(); | |||
1859 | BlockInstRange.clear(); | |||
1860 | TouchedInstructions.clear(); | |||
1861 | MemoryAccessToClass.clear(); | |||
1862 | PredicateToUsers.clear(); | |||
1863 | } | |||
1864 | ||||
1865 | std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B, | |||
1866 | unsigned Start) { | |||
1867 | unsigned End = Start; | |||
1868 | if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) { | |||
1869 | InstrDFS[MemPhi] = End++; | |||
1870 | DFSToInstr.emplace_back(MemPhi); | |||
1871 | } | |||
1872 | ||||
1873 | for (auto &I : *B) { | |||
1874 | // There's no need to call isInstructionTriviallyDead more than once on | |||
1875 | // an instruction. Therefore, once we know that an instruction is dead | |||
1876 | // we change its DFS number so that it doesn't get value numbered. | |||
1877 | if (isInstructionTriviallyDead(&I, TLI)) { | |||
1878 | InstrDFS[&I] = 0; | |||
1879 | DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Skipping trivially dead instruction " << I << "\n"; } } while (false); | |||
1880 | markInstructionForDeletion(&I); | |||
1881 | continue; | |||
1882 | } | |||
1883 | ||||
1884 | InstrDFS[&I] = End++; | |||
1885 | DFSToInstr.emplace_back(&I); | |||
1886 | } | |||
1887 | ||||
1888 | // All of the range functions taken half-open ranges (open on the end side). | |||
1889 | // So we do not subtract one from count, because at this point it is one | |||
1890 | // greater than the last instruction. | |||
1891 | return std::make_pair(Start, End); | |||
1892 | } | |||
1893 | ||||
1894 | void NewGVN::updateProcessedCount(Value *V) { | |||
1895 | #ifndef NDEBUG | |||
1896 | if (ProcessedCount.count(V) == 0) { | |||
1897 | ProcessedCount.insert({V, 1}); | |||
1898 | } else { | |||
1899 | ++ProcessedCount[V]; | |||
1900 | assert(ProcessedCount[V] < 100 &&((ProcessedCount[V] < 100 && "Seem to have processed the same Value a lot" ) ? static_cast<void> (0) : __assert_fail ("ProcessedCount[V] < 100 && \"Seem to have processed the same Value a lot\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1901, __PRETTY_FUNCTION__)) | |||
1901 | "Seem to have processed the same Value a lot")((ProcessedCount[V] < 100 && "Seem to have processed the same Value a lot" ) ? static_cast<void> (0) : __assert_fail ("ProcessedCount[V] < 100 && \"Seem to have processed the same Value a lot\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 1901, __PRETTY_FUNCTION__)); | |||
1902 | } | |||
1903 | #endif | |||
1904 | } | |||
1905 | // Evaluate MemoryPhi nodes symbolically, just like PHI nodes | |||
1906 | void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) { | |||
1907 | // If all the arguments are the same, the MemoryPhi has the same value as the | |||
1908 | // argument. | |||
1909 | // Filter out unreachable blocks and self phis from our operands. | |||
1910 | const BasicBlock *PHIBlock = MP->getBlock(); | |||
1911 | auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) { | |||
1912 | return lookupMemoryAccessEquiv(cast<MemoryAccess>(U)) != MP && | |||
1913 | !isMemoryAccessTop(cast<MemoryAccess>(U)) && | |||
1914 | ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock}); | |||
1915 | }); | |||
1916 | // If all that is left is nothing, our memoryphi is undef. We keep it as | |||
1917 | // InitialClass. Note: The only case this should happen is if we have at | |||
1918 | // least one self-argument. | |||
1919 | if (Filtered.begin() == Filtered.end()) { | |||
1920 | if (setMemoryAccessEquivTo(MP, TOPClass)) | |||
1921 | markMemoryUsersTouched(MP); | |||
1922 | return; | |||
1923 | } | |||
1924 | ||||
1925 | // Transform the remaining operands into operand leaders. | |||
1926 | // FIXME: mapped_iterator should have a range version. | |||
1927 | auto LookupFunc = [&](const Use &U) { | |||
1928 | return lookupMemoryAccessEquiv(cast<MemoryAccess>(U)); | |||
1929 | }; | |||
1930 | auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc); | |||
1931 | auto MappedEnd = map_iterator(Filtered.end(), LookupFunc); | |||
1932 | ||||
1933 | // and now check if all the elements are equal. | |||
1934 | // Sadly, we can't use std::equals since these are random access iterators. | |||
1935 | MemoryAccess *AllSameValue = *MappedBegin; | |||
1936 | ++MappedBegin; | |||
1937 | bool AllEqual = std::all_of( | |||
1938 | MappedBegin, MappedEnd, | |||
1939 | [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; }); | |||
1940 | ||||
1941 | if (AllEqual) | |||
1942 | DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n"; } } while (false); | |||
1943 | else | |||
1944 | DEBUG(dbgs() << "Memory Phi value numbered to itself\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Memory Phi value numbered to itself\n" ; } } while (false); | |||
1945 | ||||
1946 | if (setMemoryAccessEquivTo( | |||
1947 | MP, AllEqual ? MemoryAccessToClass.lookup(AllSameValue) : nullptr)) | |||
1948 | markMemoryUsersTouched(MP); | |||
1949 | } | |||
1950 | ||||
1951 | // Value number a single instruction, symbolically evaluating, performing | |||
1952 | // congruence finding, and updating mappings. | |||
1953 | void NewGVN::valueNumberInstruction(Instruction *I) { | |||
1954 | DEBUG(dbgs() << "Processing instruction " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Processing instruction " << *I << "\n"; } } while (false); | |||
1955 | if (!I->isTerminator()) { | |||
1956 | const Expression *Symbolized = nullptr; | |||
1957 | if (DebugCounter::shouldExecute(VNCounter)) { | |||
1958 | Symbolized = performSymbolicEvaluation(I); | |||
1959 | } else { | |||
1960 | // Mark the instruction as unused so we don't value number it again. | |||
1961 | InstrDFS[I] = 0; | |||
1962 | } | |||
1963 | // If we couldn't come up with a symbolic expression, use the unknown | |||
1964 | // expression | |||
1965 | if (Symbolized == nullptr) | |||
1966 | Symbolized = createUnknownExpression(I); | |||
1967 | performCongruenceFinding(I, Symbolized); | |||
1968 | } else { | |||
1969 | // Handle terminators that return values. All of them produce values we | |||
1970 | // don't currently understand. We don't place non-value producing | |||
1971 | // terminators in a class. | |||
1972 | if (!I->getType()->isVoidTy()) { | |||
1973 | auto *Symbolized = createUnknownExpression(I); | |||
1974 | performCongruenceFinding(I, Symbolized); | |||
1975 | } | |||
1976 | processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent()); | |||
1977 | } | |||
1978 | } | |||
1979 | ||||
1980 | // Check if there is a path, using single or equal argument phi nodes, from | |||
1981 | // First to Second. | |||
1982 | bool NewGVN::singleReachablePHIPath(const MemoryAccess *First, | |||
1983 | const MemoryAccess *Second) const { | |||
1984 | if (First == Second) | |||
1985 | return true; | |||
1986 | if (MSSA->isLiveOnEntryDef(First)) | |||
1987 | return false; | |||
1988 | const auto *EndDef = First; | |||
1989 | for (auto *ChainDef : optimized_def_chain(First)) { | |||
1990 | if (ChainDef == Second) | |||
1991 | return true; | |||
1992 | if (MSSA->isLiveOnEntryDef(ChainDef)) | |||
1993 | return false; | |||
1994 | EndDef = ChainDef; | |||
1995 | } | |||
1996 | auto *MP = cast<MemoryPhi>(EndDef); | |||
1997 | auto ReachableOperandPred = [&](const Use &U) { | |||
1998 | return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()}); | |||
1999 | }; | |||
2000 | auto FilteredPhiArgs = | |||
2001 | make_filter_range(MP->operands(), ReachableOperandPred); | |||
2002 | SmallVector<const Value *, 32> OperandList; | |||
2003 | std::copy(FilteredPhiArgs.begin(), FilteredPhiArgs.end(), | |||
2004 | std::back_inserter(OperandList)); | |||
2005 | bool Okay = OperandList.size() == 1; | |||
2006 | if (!Okay) | |||
2007 | Okay = | |||
2008 | std::equal(OperandList.begin(), OperandList.end(), OperandList.begin()); | |||
2009 | if (Okay) | |||
2010 | return singleReachablePHIPath(cast<MemoryAccess>(OperandList[0]), Second); | |||
2011 | return false; | |||
2012 | } | |||
2013 | ||||
2014 | // Verify the that the memory equivalence table makes sense relative to the | |||
2015 | // congruence classes. Note that this checking is not perfect, and is currently | |||
2016 | // subject to very rare false negatives. It is only useful for | |||
2017 | // testing/debugging. | |||
2018 | void NewGVN::verifyMemoryCongruency() const { | |||
2019 | #ifndef NDEBUG | |||
2020 | // Anything equivalent in the memory access table should be in the same | |||
2021 | // congruence class. | |||
2022 | ||||
2023 | // Filter out the unreachable and trivially dead entries, because they may | |||
2024 | // never have been updated if the instructions were not processed. | |||
2025 | auto ReachableAccessPred = | |||
2026 | [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) { | |||
2027 | bool Result = ReachableBlocks.count(Pair.first->getBlock()); | |||
2028 | if (!Result) | |||
2029 | return false; | |||
2030 | if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first)) | |||
2031 | return !isInstructionTriviallyDead(MemDef->getMemoryInst()); | |||
2032 | return true; | |||
2033 | }; | |||
2034 | ||||
2035 | auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred); | |||
2036 | for (auto KV : Filtered) { | |||
2037 | // Unreachable instructions may not have changed because we never process | |||
2038 | // them. | |||
2039 | if (!ReachableBlocks.count(KV.first->getBlock())) | |||
2040 | continue; | |||
2041 | if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) { | |||
2042 | auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->RepMemoryAccess); | |||
2043 | if (FirstMUD && SecondMUD) | |||
2044 | assert((singleReachablePHIPath(FirstMUD, SecondMUD) ||(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)) | |||
2045 | ValueToClass.lookup(FirstMUD->getMemoryInst()) ==(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)) | |||
2046 | ValueToClass.lookup(SecondMUD->getMemoryInst())) &&(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)) | |||
2047 | "The instructions for these memory operations should have "(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)) | |||
2048 | "been in the same congruence class or reachable through"(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)) | |||
2049 | "a single argument phi")(((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass .lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup( SecondMUD->getMemoryInst())) && "The instructions for these memory operations should have " "been in the same congruence class or reachable through" "a single argument phi" ) ? static_cast<void> (0) : __assert_fail ("(singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == ValueToClass.lookup(SecondMUD->getMemoryInst())) && \"The instructions for these memory operations should have \" \"been in the same congruence class or reachable through\" \"a single argument phi\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2049, __PRETTY_FUNCTION__)); | |||
2050 | } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) { | |||
2051 | ||||
2052 | // We can only sanely verify that MemoryDefs in the operand list all have | |||
2053 | // the same class. | |||
2054 | auto ReachableOperandPred = [&](const Use &U) { | |||
2055 | return ReachableEdges.count( | |||
2056 | {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) && | |||
2057 | isa<MemoryDef>(U); | |||
2058 | ||||
2059 | }; | |||
2060 | // All arguments should in the same class, ignoring unreachable arguments | |||
2061 | auto FilteredPhiArgs = | |||
2062 | make_filter_range(FirstMP->operands(), ReachableOperandPred); | |||
2063 | SmallVector<const CongruenceClass *, 16> PhiOpClasses; | |||
2064 | std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(), | |||
2065 | std::back_inserter(PhiOpClasses), [&](const Use &U) { | |||
2066 | const MemoryDef *MD = cast<MemoryDef>(U); | |||
2067 | return ValueToClass.lookup(MD->getMemoryInst()); | |||
2068 | }); | |||
2069 | assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),((std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses .begin()) && "All MemoryPhi arguments should be in the same class" ) ? static_cast<void> (0) : __assert_fail ("std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses.begin()) && \"All MemoryPhi arguments should be in the same class\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2071, __PRETTY_FUNCTION__)) | |||
2070 | PhiOpClasses.begin()) &&((std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses .begin()) && "All MemoryPhi arguments should be in the same class" ) ? static_cast<void> (0) : __assert_fail ("std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses.begin()) && \"All MemoryPhi arguments should be in the same class\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2071, __PRETTY_FUNCTION__)) | |||
2071 | "All MemoryPhi arguments should be in the same class")((std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses .begin()) && "All MemoryPhi arguments should be in the same class" ) ? static_cast<void> (0) : __assert_fail ("std::equal(PhiOpClasses.begin(), PhiOpClasses.end(), PhiOpClasses.begin()) && \"All MemoryPhi arguments should be in the same class\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2071, __PRETTY_FUNCTION__)); | |||
2072 | } | |||
2073 | } | |||
2074 | #endif | |||
2075 | } | |||
2076 | ||||
2077 | // Verify that the sparse propagation we did actually found the maximal fixpoint | |||
2078 | // We do this by storing the value to class mapping, touching all instructions, | |||
2079 | // and redoing the iteration to see if anything changed. | |||
2080 | void NewGVN::verifyIterationSettled(Function &F) { | |||
2081 | #ifndef NDEBUG | |||
2082 | if (DebugCounter::isCounterSet(VNCounter)) | |||
| ||||
2083 | DebugCounter::setCounterValue(VNCounter, StartingVNCounter); | |||
2084 | ||||
2085 | // Note that we have to store the actual classes, as we may change existing | |||
2086 | // classes during iteration. This is because our memory iteration propagation | |||
2087 | // is not perfect, and so may waste a little work. But it should generate | |||
2088 | // exactly the same congruence classes we have now, with different IDs. | |||
2089 | std::map<const Value *, CongruenceClass> BeforeIteration; | |||
2090 | ||||
2091 | for (auto &KV : ValueToClass) { | |||
2092 | if (auto *I = dyn_cast<Instruction>(KV.first)) | |||
2093 | // Skip unused/dead instructions. | |||
2094 | if (InstrDFS.lookup(I) == 0) | |||
2095 | continue; | |||
2096 | BeforeIteration.insert({KV.first, *KV.second}); | |||
2097 | } | |||
2098 | ||||
2099 | TouchedInstructions.set(); | |||
2100 | TouchedInstructions.reset(0); | |||
2101 | iterateTouchedInstructions(); | |||
2102 | DenseSet<std::pair<const CongruenceClass *, const CongruenceClass *>> | |||
2103 | EqualClasses; | |||
2104 | for (const auto &KV : ValueToClass) { | |||
2105 | if (auto *I = dyn_cast<Instruction>(KV.first)) | |||
2106 | // Skip unused/dead instructions. | |||
2107 | if (InstrDFS.lookup(I) == 0) | |||
2108 | continue; | |||
2109 | // We could sink these uses, but i think this adds a bit of clarity here as | |||
2110 | // to what we are comparing. | |||
2111 | auto *BeforeCC = &BeforeIteration.find(KV.first)->second; | |||
2112 | auto *AfterCC = KV.second; | |||
2113 | // Note that the classes can't change at this point, so we memoize the set | |||
2114 | // that are equal. | |||
2115 | if (!EqualClasses.count({BeforeCC, AfterCC})) { | |||
2116 | assert(areClassesEquivalent(BeforeCC, AfterCC) &&((areClassesEquivalent(BeforeCC, AfterCC) && "Value number changed after main loop completed!" ) ? static_cast<void> (0) : __assert_fail ("areClassesEquivalent(BeforeCC, AfterCC) && \"Value number changed after main loop completed!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2117, __PRETTY_FUNCTION__)) | |||
2117 | "Value number changed after main loop completed!")((areClassesEquivalent(BeforeCC, AfterCC) && "Value number changed after main loop completed!" ) ? static_cast<void> (0) : __assert_fail ("areClassesEquivalent(BeforeCC, AfterCC) && \"Value number changed after main loop completed!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2117, __PRETTY_FUNCTION__)); | |||
2118 | EqualClasses.insert({BeforeCC, AfterCC}); | |||
2119 | } | |||
2120 | } | |||
2121 | #endif | |||
2122 | } | |||
2123 | ||||
2124 | // This is the main value numbering loop, it iterates over the initial touched | |||
2125 | // instruction set, propagating value numbers, marking things touched, etc, | |||
2126 | // until the set of touched instructions is completely empty. | |||
2127 | void NewGVN::iterateTouchedInstructions() { | |||
2128 | unsigned int Iterations = 0; | |||
2129 | // Figure out where touchedinstructions starts | |||
2130 | int FirstInstr = TouchedInstructions.find_first(); | |||
2131 | // Nothing set, nothing to iterate, just return. | |||
2132 | if (FirstInstr == -1) | |||
2133 | return; | |||
2134 | BasicBlock *LastBlock = getBlockForValue(DFSToInstr[FirstInstr]); | |||
2135 | while (TouchedInstructions.any()) { | |||
2136 | ++Iterations; | |||
2137 | // Walk through all the instructions in all the blocks in RPO. | |||
2138 | // TODO: As we hit a new block, we should push and pop equalities into a | |||
2139 | // table lookupOperandLeader can use, to catch things PredicateInfo | |||
2140 | // might miss, like edge-only equivalences. | |||
2141 | for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1; | |||
2142 | InstrNum = TouchedInstructions.find_next(InstrNum)) { | |||
2143 | ||||
2144 | // This instruction was found to be dead. We don't bother looking | |||
2145 | // at it again. | |||
2146 | if (InstrNum == 0) { | |||
2147 | TouchedInstructions.reset(InstrNum); | |||
2148 | continue; | |||
2149 | } | |||
2150 | ||||
2151 | Value *V = DFSToInstr[InstrNum]; | |||
2152 | BasicBlock *CurrBlock = getBlockForValue(V); | |||
2153 | ||||
2154 | // If we hit a new block, do reachability processing. | |||
2155 | if (CurrBlock != LastBlock) { | |||
2156 | LastBlock = CurrBlock; | |||
2157 | bool BlockReachable = ReachableBlocks.count(CurrBlock); | |||
2158 | const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock); | |||
2159 | ||||
2160 | // If it's not reachable, erase any touched instructions and move on. | |||
2161 | if (!BlockReachable) { | |||
2162 | TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second); | |||
2163 | DEBUG(dbgs() << "Skipping instructions in block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Skipping instructions in block " << getBlockName(CurrBlock) << " because it is unreachable\n" ; } } while (false) | |||
2164 | << getBlockName(CurrBlock)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Skipping instructions in block " << getBlockName(CurrBlock) << " because it is unreachable\n" ; } } while (false) | |||
2165 | << " because it is unreachable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Skipping instructions in block " << getBlockName(CurrBlock) << " because it is unreachable\n" ; } } while (false); | |||
2166 | continue; | |||
2167 | } | |||
2168 | updateProcessedCount(CurrBlock); | |||
2169 | } | |||
2170 | ||||
2171 | if (auto *MP = dyn_cast<MemoryPhi>(V)) { | |||
2172 | DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Processing MemoryPhi " << *MP << "\n"; } } while (false); | |||
2173 | valueNumberMemoryPhi(MP); | |||
2174 | } else if (auto *I = dyn_cast<Instruction>(V)) { | |||
2175 | valueNumberInstruction(I); | |||
2176 | } else { | |||
2177 | llvm_unreachable("Should have been a MemoryPhi or Instruction")::llvm::llvm_unreachable_internal("Should have been a MemoryPhi or Instruction" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2177); | |||
2178 | } | |||
2179 | updateProcessedCount(V); | |||
2180 | // Reset after processing (because we may mark ourselves as touched when | |||
2181 | // we propagate equalities). | |||
2182 | TouchedInstructions.reset(InstrNum); | |||
2183 | } | |||
2184 | } | |||
2185 | NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations); | |||
2186 | } | |||
2187 | ||||
2188 | // This is the main transformation entry point. | |||
2189 | bool NewGVN::runGVN() { | |||
2190 | if (DebugCounter::isCounterSet(VNCounter)) | |||
2191 | StartingVNCounter = DebugCounter::getCounterValue(VNCounter); | |||
2192 | bool Changed = false; | |||
2193 | NumFuncArgs = F.arg_size(); | |||
2194 | MSSAWalker = MSSA->getWalker(); | |||
2195 | ||||
2196 | // Count number of instructions for sizing of hash tables, and come | |||
2197 | // up with a global dfs numbering for instructions. | |||
2198 | unsigned ICount = 1; | |||
2199 | // Add an empty instruction to account for the fact that we start at 1 | |||
2200 | DFSToInstr.emplace_back(nullptr); | |||
2201 | // Note: We want ideal RPO traversal of the blocks, which is not quite the | |||
2202 | // same as dominator tree order, particularly with regard whether backedges | |||
2203 | // get visited first or second, given a block with multiple successors. | |||
2204 | // If we visit in the wrong order, we will end up performing N times as many | |||
2205 | // iterations. | |||
2206 | // The dominator tree does guarantee that, for a given dom tree node, it's | |||
2207 | // parent must occur before it in the RPO ordering. Thus, we only need to sort | |||
2208 | // the siblings. | |||
2209 | DenseMap<const DomTreeNode *, unsigned> RPOOrdering; | |||
2210 | ReversePostOrderTraversal<Function *> RPOT(&F); | |||
2211 | unsigned Counter = 0; | |||
2212 | for (auto &B : RPOT) { | |||
2213 | auto *Node = DT->getNode(B); | |||
2214 | assert(Node && "RPO and Dominator tree should have same reachability")((Node && "RPO and Dominator tree should have same reachability" ) ? static_cast<void> (0) : __assert_fail ("Node && \"RPO and Dominator tree should have same reachability\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2214, __PRETTY_FUNCTION__)); | |||
2215 | RPOOrdering[Node] = ++Counter; | |||
2216 | } | |||
2217 | // Sort dominator tree children arrays into RPO. | |||
2218 | for (auto &B : RPOT) { | |||
2219 | auto *Node = DT->getNode(B); | |||
2220 | if (Node->getChildren().size() > 1) | |||
2221 | std::sort(Node->begin(), Node->end(), | |||
2222 | [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) { | |||
2223 | return RPOOrdering[A] < RPOOrdering[B]; | |||
2224 | }); | |||
2225 | } | |||
2226 | ||||
2227 | // Now a standard depth first ordering of the domtree is equivalent to RPO. | |||
2228 | auto DFI = df_begin(DT->getRootNode()); | |||
2229 | for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) { | |||
2230 | BasicBlock *B = DFI->getBlock(); | |||
2231 | const auto &BlockRange = assignDFSNumbers(B, ICount); | |||
2232 | BlockInstRange.insert({B, BlockRange}); | |||
2233 | ICount += BlockRange.second - BlockRange.first; | |||
2234 | } | |||
2235 | ||||
2236 | // Handle forward unreachable blocks and figure out which blocks | |||
2237 | // have single preds. | |||
2238 | for (auto &B : F) { | |||
2239 | // Assign numbers to unreachable blocks. | |||
2240 | if (!DFI.nodeVisited(DT->getNode(&B))) { | |||
2241 | const auto &BlockRange = assignDFSNumbers(&B, ICount); | |||
2242 | BlockInstRange.insert({&B, BlockRange}); | |||
2243 | ICount += BlockRange.second - BlockRange.first; | |||
2244 | } | |||
2245 | } | |||
2246 | ||||
2247 | TouchedInstructions.resize(ICount); | |||
2248 | // Ensure we don't end up resizing the expressionToClass map, as | |||
2249 | // that can be quite expensive. At most, we have one expression per | |||
2250 | // instruction. | |||
2251 | ExpressionToClass.reserve(ICount); | |||
2252 | ||||
2253 | // Initialize the touched instructions to include the entry block. | |||
2254 | const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock()); | |||
2255 | TouchedInstructions.set(InstRange.first, InstRange.second); | |||
2256 | ReachableBlocks.insert(&F.getEntryBlock()); | |||
2257 | ||||
2258 | initializeCongruenceClasses(F); | |||
2259 | iterateTouchedInstructions(); | |||
2260 | verifyMemoryCongruency(); | |||
2261 | verifyIterationSettled(F); | |||
2262 | ||||
2263 | Changed |= eliminateInstructions(F); | |||
2264 | ||||
2265 | // Delete all instructions marked for deletion. | |||
2266 | for (Instruction *ToErase : InstructionsToErase) { | |||
2267 | if (!ToErase->use_empty()) | |||
2268 | ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType())); | |||
2269 | ||||
2270 | ToErase->eraseFromParent(); | |||
2271 | } | |||
2272 | ||||
2273 | // Delete all unreachable blocks. | |||
2274 | auto UnreachableBlockPred = [&](const BasicBlock &BB) { | |||
2275 | return !ReachableBlocks.count(&BB); | |||
2276 | }; | |||
2277 | ||||
2278 | for (auto &BB : make_filter_range(F, UnreachableBlockPred)) { | |||
2279 | DEBUG(dbgs() << "We believe block " << getBlockName(&BB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "We believe block " << getBlockName (&BB) << " is unreachable\n"; } } while (false) | |||
2280 | << " is unreachable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "We believe block " << getBlockName (&BB) << " is unreachable\n"; } } while (false); | |||
2281 | deleteInstructionsInBlock(&BB); | |||
2282 | Changed = true; | |||
2283 | } | |||
2284 | ||||
2285 | cleanupTables(); | |||
2286 | return Changed; | |||
2287 | } | |||
2288 | ||||
2289 | // Return true if V is a value that will always be available (IE can | |||
2290 | // be placed anywhere) in the function. We don't do globals here | |||
2291 | // because they are often worse to put in place. | |||
2292 | // TODO: Separate cost from availability | |||
2293 | static bool alwaysAvailable(Value *V) { | |||
2294 | return isa<Constant>(V) || isa<Argument>(V); | |||
2295 | } | |||
2296 | ||||
2297 | struct NewGVN::ValueDFS { | |||
2298 | int DFSIn = 0; | |||
2299 | int DFSOut = 0; | |||
2300 | int LocalNum = 0; | |||
2301 | // Only one of Def and U will be set. | |||
2302 | // The bool in the Def tells us whether the Def is the stored value of a | |||
2303 | // store. | |||
2304 | PointerIntPair<Value *, 1, bool> Def; | |||
2305 | Use *U = nullptr; | |||
2306 | bool operator<(const ValueDFS &Other) const { | |||
2307 | // It's not enough that any given field be less than - we have sets | |||
2308 | // of fields that need to be evaluated together to give a proper ordering. | |||
2309 | // For example, if you have; | |||
2310 | // DFS (1, 3) | |||
2311 | // Val 0 | |||
2312 | // DFS (1, 2) | |||
2313 | // Val 50 | |||
2314 | // We want the second to be less than the first, but if we just go field | |||
2315 | // by field, we will get to Val 0 < Val 50 and say the first is less than | |||
2316 | // the second. We only want it to be less than if the DFS orders are equal. | |||
2317 | // | |||
2318 | // Each LLVM instruction only produces one value, and thus the lowest-level | |||
2319 | // differentiator that really matters for the stack (and what we use as as a | |||
2320 | // replacement) is the local dfs number. | |||
2321 | // Everything else in the structure is instruction level, and only affects | |||
2322 | // the order in which we will replace operands of a given instruction. | |||
2323 | // | |||
2324 | // For a given instruction (IE things with equal dfsin, dfsout, localnum), | |||
2325 | // the order of replacement of uses does not matter. | |||
2326 | // IE given, | |||
2327 | // a = 5 | |||
2328 | // b = a + a | |||
2329 | // When you hit b, you will have two valuedfs with the same dfsin, out, and | |||
2330 | // localnum. | |||
2331 | // The .val will be the same as well. | |||
2332 | // The .u's will be different. | |||
2333 | // You will replace both, and it does not matter what order you replace them | |||
2334 | // in (IE whether you replace operand 2, then operand 1, or operand 1, then | |||
2335 | // operand 2). | |||
2336 | // Similarly for the case of same dfsin, dfsout, localnum, but different | |||
2337 | // .val's | |||
2338 | // a = 5 | |||
2339 | // b = 6 | |||
2340 | // c = a + b | |||
2341 | // in c, we will a valuedfs for a, and one for b,with everything the same | |||
2342 | // but .val and .u. | |||
2343 | // It does not matter what order we replace these operands in. | |||
2344 | // You will always end up with the same IR, and this is guaranteed. | |||
2345 | return std::tie(DFSIn, DFSOut, LocalNum, Def, U) < | |||
2346 | std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def, | |||
2347 | Other.U); | |||
2348 | } | |||
2349 | }; | |||
2350 | ||||
2351 | // This function converts the set of members for a congruence class from values, | |||
2352 | // to sets of defs and uses with associated DFS info. The total number of | |||
2353 | // reachable uses for each value is stored in UseCount, and instructions that | |||
2354 | // seem | |||
2355 | // dead (have no non-dead uses) are stored in ProbablyDead. | |||
2356 | void NewGVN::convertClassToDFSOrdered( | |||
2357 | const CongruenceClass::MemberSet &Dense, | |||
2358 | SmallVectorImpl<ValueDFS> &DFSOrderedSet, | |||
2359 | DenseMap<const Value *, unsigned int> &UseCounts, | |||
2360 | SmallPtrSetImpl<Instruction *> &ProbablyDead) { | |||
2361 | for (auto D : Dense) { | |||
2362 | // First add the value. | |||
2363 | BasicBlock *BB = getBlockForValue(D); | |||
2364 | // Constants are handled prior to ever calling this function, so | |||
2365 | // we should only be left with instructions as members. | |||
2366 | assert(BB && "Should have figured out a basic block for value")((BB && "Should have figured out a basic block for value" ) ? static_cast<void> (0) : __assert_fail ("BB && \"Should have figured out a basic block for value\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2366, __PRETTY_FUNCTION__)); | |||
2367 | ValueDFS VDDef; | |||
2368 | DomTreeNode *DomNode = DT->getNode(BB); | |||
2369 | VDDef.DFSIn = DomNode->getDFSNumIn(); | |||
2370 | VDDef.DFSOut = DomNode->getDFSNumOut(); | |||
2371 | // If it's a store, use the leader of the value operand, if it's always | |||
2372 | // available, or the value operand. TODO: We could do dominance checks to | |||
2373 | // find a dominating leader, but not worth it ATM. | |||
2374 | if (auto *SI = dyn_cast<StoreInst>(D)) { | |||
2375 | auto Leader = lookupOperandLeader(SI->getValueOperand()); | |||
2376 | if (alwaysAvailable(Leader)) { | |||
2377 | VDDef.Def.setPointer(Leader); | |||
2378 | } else { | |||
2379 | VDDef.Def.setPointer(SI->getValueOperand()); | |||
2380 | VDDef.Def.setInt(true); | |||
2381 | } | |||
2382 | } else { | |||
2383 | VDDef.Def.setPointer(D); | |||
2384 | } | |||
2385 | assert(isa<Instruction>(D) &&((isa<Instruction>(D) && "The dense set member should always be an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(D) && \"The dense set member should always be an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2386, __PRETTY_FUNCTION__)) | |||
2386 | "The dense set member should always be an instruction")((isa<Instruction>(D) && "The dense set member should always be an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(D) && \"The dense set member should always be an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2386, __PRETTY_FUNCTION__)); | |||
2387 | VDDef.LocalNum = InstrDFS.lookup(D); | |||
2388 | DFSOrderedSet.emplace_back(VDDef); | |||
2389 | Instruction *Def = cast<Instruction>(D); | |||
2390 | unsigned int UseCount = 0; | |||
2391 | // Now add the uses. | |||
2392 | for (auto &U : Def->uses()) { | |||
2393 | if (auto *I = dyn_cast<Instruction>(U.getUser())) { | |||
2394 | // Don't try to replace into dead uses | |||
2395 | if (InstructionsToErase.count(I)) | |||
2396 | continue; | |||
2397 | ValueDFS VDUse; | |||
2398 | // Put the phi node uses in the incoming block. | |||
2399 | BasicBlock *IBlock; | |||
2400 | if (auto *P = dyn_cast<PHINode>(I)) { | |||
2401 | IBlock = P->getIncomingBlock(U); | |||
2402 | // Make phi node users appear last in the incoming block | |||
2403 | // they are from. | |||
2404 | VDUse.LocalNum = InstrDFS.size() + 1; | |||
2405 | } else { | |||
2406 | IBlock = I->getParent(); | |||
2407 | VDUse.LocalNum = InstrDFS.lookup(I); | |||
2408 | } | |||
2409 | ||||
2410 | // Skip uses in unreachable blocks, as we're going | |||
2411 | // to delete them. | |||
2412 | if (ReachableBlocks.count(IBlock) == 0) | |||
2413 | continue; | |||
2414 | ||||
2415 | DomTreeNode *DomNode = DT->getNode(IBlock); | |||
2416 | VDUse.DFSIn = DomNode->getDFSNumIn(); | |||
2417 | VDUse.DFSOut = DomNode->getDFSNumOut(); | |||
2418 | VDUse.U = &U; | |||
2419 | ++UseCount; | |||
2420 | DFSOrderedSet.emplace_back(VDUse); | |||
2421 | } | |||
2422 | } | |||
2423 | ||||
2424 | // If there are no uses, it's probably dead (but it may have side-effects, | |||
2425 | // so not definitely dead. Otherwise, store the number of uses so we can | |||
2426 | // track if it becomes dead later). | |||
2427 | if (UseCount == 0) | |||
2428 | ProbablyDead.insert(Def); | |||
2429 | else | |||
2430 | UseCounts[Def] = UseCount; | |||
2431 | } | |||
2432 | } | |||
2433 | ||||
2434 | // This function converts the set of members for a congruence class from values, | |||
2435 | // to the set of defs for loads and stores, with associated DFS info. | |||
2436 | void NewGVN::convertClassToLoadsAndStores( | |||
2437 | const CongruenceClass::MemberSet &Dense, | |||
2438 | SmallVectorImpl<ValueDFS> &LoadsAndStores) { | |||
2439 | for (auto D : Dense) { | |||
2440 | if (!isa<LoadInst>(D) && !isa<StoreInst>(D)) | |||
2441 | continue; | |||
2442 | ||||
2443 | BasicBlock *BB = getBlockForValue(D); | |||
2444 | ValueDFS VD; | |||
2445 | DomTreeNode *DomNode = DT->getNode(BB); | |||
2446 | VD.DFSIn = DomNode->getDFSNumIn(); | |||
2447 | VD.DFSOut = DomNode->getDFSNumOut(); | |||
2448 | VD.Def.setPointer(D); | |||
2449 | ||||
2450 | // If it's an instruction, use the real local dfs number. | |||
2451 | if (auto *I = dyn_cast<Instruction>(D)) | |||
2452 | VD.LocalNum = InstrDFS.lookup(I); | |||
2453 | else | |||
2454 | llvm_unreachable("Should have been an instruction")::llvm::llvm_unreachable_internal("Should have been an instruction" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2454); | |||
2455 | ||||
2456 | LoadsAndStores.emplace_back(VD); | |||
2457 | } | |||
2458 | } | |||
2459 | ||||
2460 | static void patchReplacementInstruction(Instruction *I, Value *Repl) { | |||
2461 | auto *ReplInst = dyn_cast<Instruction>(Repl); | |||
2462 | if (!ReplInst) | |||
2463 | return; | |||
2464 | ||||
2465 | // Patch the replacement so that it is not more restrictive than the value | |||
2466 | // being replaced. | |||
2467 | // Note that if 'I' is a load being replaced by some operation, | |||
2468 | // for example, by an arithmetic operation, then andIRFlags() | |||
2469 | // would just erase all math flags from the original arithmetic | |||
2470 | // operation, which is clearly not wanted and not needed. | |||
2471 | if (!isa<LoadInst>(I)) | |||
2472 | ReplInst->andIRFlags(I); | |||
2473 | ||||
2474 | // FIXME: If both the original and replacement value are part of the | |||
2475 | // same control-flow region (meaning that the execution of one | |||
2476 | // guarantees the execution of the other), then we can combine the | |||
2477 | // noalias scopes here and do better than the general conservative | |||
2478 | // answer used in combineMetadata(). | |||
2479 | ||||
2480 | // In general, GVN unifies expressions over different control-flow | |||
2481 | // regions, and so we need a conservative combination of the noalias | |||
2482 | // scopes. | |||
2483 | static const unsigned KnownIDs[] = { | |||
2484 | LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, | |||
2485 | LLVMContext::MD_noalias, LLVMContext::MD_range, | |||
2486 | LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, | |||
2487 | LLVMContext::MD_invariant_group}; | |||
2488 | combineMetadata(ReplInst, I, KnownIDs); | |||
2489 | } | |||
2490 | ||||
2491 | static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { | |||
2492 | patchReplacementInstruction(I, Repl); | |||
2493 | I->replaceAllUsesWith(Repl); | |||
2494 | } | |||
2495 | ||||
2496 | void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) { | |||
2497 | DEBUG(dbgs() << " BasicBlock Dead:" << *BB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << " BasicBlock Dead:" << * BB; } } while (false); | |||
2498 | ++NumGVNBlocksDeleted; | |||
2499 | ||||
2500 | // Delete the instructions backwards, as it has a reduced likelihood of having | |||
2501 | // to update as many def-use and use-def chains. Start after the terminator. | |||
2502 | auto StartPoint = BB->rbegin(); | |||
2503 | ++StartPoint; | |||
2504 | // Note that we explicitly recalculate BB->rend() on each iteration, | |||
2505 | // as it may change when we remove the first instruction. | |||
2506 | for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) { | |||
2507 | Instruction &Inst = *I++; | |||
2508 | if (!Inst.use_empty()) | |||
2509 | Inst.replaceAllUsesWith(UndefValue::get(Inst.getType())); | |||
2510 | if (isa<LandingPadInst>(Inst)) | |||
2511 | continue; | |||
2512 | ||||
2513 | Inst.eraseFromParent(); | |||
2514 | ++NumGVNInstrDeleted; | |||
2515 | } | |||
2516 | // Now insert something that simplifycfg will turn into an unreachable. | |||
2517 | Type *Int8Ty = Type::getInt8Ty(BB->getContext()); | |||
2518 | new StoreInst(UndefValue::get(Int8Ty), | |||
2519 | Constant::getNullValue(Int8Ty->getPointerTo()), | |||
2520 | BB->getTerminator()); | |||
2521 | } | |||
2522 | ||||
2523 | void NewGVN::markInstructionForDeletion(Instruction *I) { | |||
2524 | DEBUG(dbgs() << "Marking " << *I << " for deletion\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Marking " << *I << " for deletion\n"; } } while (false); | |||
2525 | InstructionsToErase.insert(I); | |||
2526 | } | |||
2527 | ||||
2528 | void NewGVN::replaceInstruction(Instruction *I, Value *V) { | |||
2529 | ||||
2530 | DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Replacing " << *I << " with " << *V << "\n"; } } while (false); | |||
2531 | patchAndReplaceAllUsesWith(I, V); | |||
2532 | // We save the actual erasing to avoid invalidating memory | |||
2533 | // dependencies until we are done with everything. | |||
2534 | markInstructionForDeletion(I); | |||
2535 | } | |||
2536 | ||||
2537 | namespace { | |||
2538 | ||||
2539 | // This is a stack that contains both the value and dfs info of where | |||
2540 | // that value is valid. | |||
2541 | class ValueDFSStack { | |||
2542 | public: | |||
2543 | Value *back() const { return ValueStack.back(); } | |||
2544 | std::pair<int, int> dfs_back() const { return DFSStack.back(); } | |||
2545 | ||||
2546 | void push_back(Value *V, int DFSIn, int DFSOut) { | |||
2547 | ValueStack.emplace_back(V); | |||
2548 | DFSStack.emplace_back(DFSIn, DFSOut); | |||
2549 | } | |||
2550 | bool empty() const { return DFSStack.empty(); } | |||
2551 | bool isInScope(int DFSIn, int DFSOut) const { | |||
2552 | if (empty()) | |||
2553 | return false; | |||
2554 | return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second; | |||
2555 | } | |||
2556 | ||||
2557 | void popUntilDFSScope(int DFSIn, int DFSOut) { | |||
2558 | ||||
2559 | // These two should always be in sync at this point. | |||
2560 | assert(ValueStack.size() == DFSStack.size() &&((ValueStack.size() == DFSStack.size() && "Mismatch between ValueStack and DFSStack" ) ? static_cast<void> (0) : __assert_fail ("ValueStack.size() == DFSStack.size() && \"Mismatch between ValueStack and DFSStack\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2561, __PRETTY_FUNCTION__)) | |||
2561 | "Mismatch between ValueStack and DFSStack")((ValueStack.size() == DFSStack.size() && "Mismatch between ValueStack and DFSStack" ) ? static_cast<void> (0) : __assert_fail ("ValueStack.size() == DFSStack.size() && \"Mismatch between ValueStack and DFSStack\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2561, __PRETTY_FUNCTION__)); | |||
2562 | while ( | |||
2563 | !DFSStack.empty() && | |||
2564 | !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) { | |||
2565 | DFSStack.pop_back(); | |||
2566 | ValueStack.pop_back(); | |||
2567 | } | |||
2568 | } | |||
2569 | ||||
2570 | private: | |||
2571 | SmallVector<Value *, 8> ValueStack; | |||
2572 | SmallVector<std::pair<int, int>, 8> DFSStack; | |||
2573 | }; | |||
2574 | } | |||
2575 | ||||
2576 | bool NewGVN::eliminateInstructions(Function &F) { | |||
2577 | // This is a non-standard eliminator. The normal way to eliminate is | |||
2578 | // to walk the dominator tree in order, keeping track of available | |||
2579 | // values, and eliminating them. However, this is mildly | |||
2580 | // pointless. It requires doing lookups on every instruction, | |||
2581 | // regardless of whether we will ever eliminate it. For | |||
2582 | // instructions part of most singleton congruence classes, we know we | |||
2583 | // will never eliminate them. | |||
2584 | ||||
2585 | // Instead, this eliminator looks at the congruence classes directly, sorts | |||
2586 | // them into a DFS ordering of the dominator tree, and then we just | |||
2587 | // perform elimination straight on the sets by walking the congruence | |||
2588 | // class member uses in order, and eliminate the ones dominated by the | |||
2589 | // last member. This is worst case O(E log E) where E = number of | |||
2590 | // instructions in a single congruence class. In theory, this is all | |||
2591 | // instructions. In practice, it is much faster, as most instructions are | |||
2592 | // either in singleton congruence classes or can't possibly be eliminated | |||
2593 | // anyway (if there are no overlapping DFS ranges in class). | |||
2594 | // When we find something not dominated, it becomes the new leader | |||
2595 | // for elimination purposes. | |||
2596 | // TODO: If we wanted to be faster, We could remove any members with no | |||
2597 | // overlapping ranges while sorting, as we will never eliminate anything | |||
2598 | // with those members, as they don't dominate anything else in our set. | |||
2599 | ||||
2600 | bool AnythingReplaced = false; | |||
2601 | ||||
2602 | // Since we are going to walk the domtree anyway, and we can't guarantee the | |||
2603 | // DFS numbers are updated, we compute some ourselves. | |||
2604 | DT->updateDFSNumbers(); | |||
2605 | ||||
2606 | for (auto &B : F) { | |||
2607 | if (!ReachableBlocks.count(&B)) { | |||
2608 | for (const auto S : successors(&B)) { | |||
2609 | for (auto II = S->begin(); isa<PHINode>(II); ++II) { | |||
2610 | auto &Phi = cast<PHINode>(*II); | |||
2611 | DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Replacing incoming value of " << *II << " for block " << getBlockName(&B) << " with undef due to it being unreachable\n"; } } while (false ) | |||
2612 | << getBlockName(&B)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Replacing incoming value of " << *II << " for block " << getBlockName(&B) << " with undef due to it being unreachable\n"; } } while (false ) | |||
2613 | << " with undef due to it being unreachable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Replacing incoming value of " << *II << " for block " << getBlockName(&B) << " with undef due to it being unreachable\n"; } } while (false ); | |||
2614 | for (auto &Operand : Phi.incoming_values()) | |||
2615 | if (Phi.getIncomingBlock(Operand) == &B) | |||
2616 | Operand.set(UndefValue::get(Phi.getType())); | |||
2617 | } | |||
2618 | } | |||
2619 | } | |||
2620 | } | |||
2621 | ||||
2622 | // Map to store the use counts | |||
2623 | DenseMap<const Value *, unsigned int> UseCounts; | |||
2624 | for (CongruenceClass *CC : reverse(CongruenceClasses)) { | |||
2625 | // Track the equivalent store info so we can decide whether to try | |||
2626 | // dead store elimination. | |||
2627 | SmallVector<ValueDFS, 8> PossibleDeadStores; | |||
2628 | SmallPtrSet<Instruction *, 8> ProbablyDead; | |||
2629 | if (CC->Dead) | |||
2630 | continue; | |||
2631 | // Everything still in the TOP class is unreachable or dead. | |||
2632 | if (CC == TOPClass) { | |||
2633 | #ifndef NDEBUG | |||
2634 | for (auto M : CC->Members) | |||
2635 | assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||(((!ReachableBlocks.count(cast<Instruction>(M)->getParent ()) || InstructionsToErase.count(cast<Instruction>(M))) && "Everything in TOP should be unreachable or dead at this " "point") ? static_cast<void> (0) : __assert_fail ("(!ReachableBlocks.count(cast<Instruction>(M)->getParent()) || InstructionsToErase.count(cast<Instruction>(M))) && \"Everything in TOP should be unreachable or dead at this \" \"point\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2638, __PRETTY_FUNCTION__)) | |||
2636 | InstructionsToErase.count(cast<Instruction>(M))) &&(((!ReachableBlocks.count(cast<Instruction>(M)->getParent ()) || InstructionsToErase.count(cast<Instruction>(M))) && "Everything in TOP should be unreachable or dead at this " "point") ? static_cast<void> (0) : __assert_fail ("(!ReachableBlocks.count(cast<Instruction>(M)->getParent()) || InstructionsToErase.count(cast<Instruction>(M))) && \"Everything in TOP should be unreachable or dead at this \" \"point\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2638, __PRETTY_FUNCTION__)) | |||
2637 | "Everything in TOP should be unreachable or dead at this "(((!ReachableBlocks.count(cast<Instruction>(M)->getParent ()) || InstructionsToErase.count(cast<Instruction>(M))) && "Everything in TOP should be unreachable or dead at this " "point") ? static_cast<void> (0) : __assert_fail ("(!ReachableBlocks.count(cast<Instruction>(M)->getParent()) || InstructionsToErase.count(cast<Instruction>(M))) && \"Everything in TOP should be unreachable or dead at this \" \"point\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2638, __PRETTY_FUNCTION__)) | |||
2638 | "point")(((!ReachableBlocks.count(cast<Instruction>(M)->getParent ()) || InstructionsToErase.count(cast<Instruction>(M))) && "Everything in TOP should be unreachable or dead at this " "point") ? static_cast<void> (0) : __assert_fail ("(!ReachableBlocks.count(cast<Instruction>(M)->getParent()) || InstructionsToErase.count(cast<Instruction>(M))) && \"Everything in TOP should be unreachable or dead at this \" \"point\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2638, __PRETTY_FUNCTION__)); | |||
2639 | #endif | |||
2640 | continue; | |||
2641 | } | |||
2642 | ||||
2643 | assert(CC->RepLeader && "We should have had a leader")((CC->RepLeader && "We should have had a leader") ? static_cast<void> (0) : __assert_fail ("CC->RepLeader && \"We should have had a leader\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2643, __PRETTY_FUNCTION__)); | |||
2644 | ||||
2645 | // If this is a leader that is always available, and it's a | |||
2646 | // constant or has no equivalences, just replace everything with | |||
2647 | // it. We then update the congruence class with whatever members | |||
2648 | // are left. | |||
2649 | Value *Leader = CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader; | |||
2650 | if (alwaysAvailable(Leader)) { | |||
2651 | SmallPtrSet<Value *, 4> MembersLeft; | |||
2652 | for (auto M : CC->Members) { | |||
2653 | Value *Member = M; | |||
2654 | // Void things have no uses we can replace. | |||
2655 | if (Member == Leader || Member->getType()->isVoidTy()) { | |||
2656 | MembersLeft.insert(Member); | |||
2657 | continue; | |||
2658 | } | |||
2659 | DEBUG(dbgs() << "Found replacement " << *(Leader) << " for " << *Memberdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found replacement " << * (Leader) << " for " << *Member << "\n"; } } while (false) | |||
2660 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found replacement " << * (Leader) << " for " << *Member << "\n"; } } while (false); | |||
2661 | // Due to equality propagation, these may not always be | |||
2662 | // instructions, they may be real values. We don't really | |||
2663 | // care about trying to replace the non-instructions. | |||
2664 | if (auto *I = dyn_cast<Instruction>(Member)) { | |||
2665 | assert(Leader != I && "About to accidentally remove our leader")((Leader != I && "About to accidentally remove our leader" ) ? static_cast<void> (0) : __assert_fail ("Leader != I && \"About to accidentally remove our leader\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2665, __PRETTY_FUNCTION__)); | |||
2666 | replaceInstruction(I, Leader); | |||
2667 | AnythingReplaced = true; | |||
2668 | continue; | |||
2669 | } else { | |||
2670 | MembersLeft.insert(I); | |||
2671 | } | |||
2672 | } | |||
2673 | CC->Members.swap(MembersLeft); | |||
2674 | } else { | |||
2675 | DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Eliminating in congruence class " << CC->ID << "\n"; } } while (false); | |||
2676 | // If this is a singleton, we can skip it. | |||
2677 | if (CC->Members.size() != 1) { | |||
2678 | ||||
2679 | // This is a stack because equality replacement/etc may place | |||
2680 | // constants in the middle of the member list, and we want to use | |||
2681 | // those constant values in preference to the current leader, over | |||
2682 | // the scope of those constants. | |||
2683 | ValueDFSStack EliminationStack; | |||
2684 | ||||
2685 | // Convert the members to DFS ordered sets and then merge them. | |||
2686 | SmallVector<ValueDFS, 8> DFSOrderedSet; | |||
2687 | convertClassToDFSOrdered(CC->Members, DFSOrderedSet, UseCounts, | |||
2688 | ProbablyDead); | |||
2689 | ||||
2690 | // Sort the whole thing. | |||
2691 | std::sort(DFSOrderedSet.begin(), DFSOrderedSet.end()); | |||
2692 | for (auto &VD : DFSOrderedSet) { | |||
2693 | int MemberDFSIn = VD.DFSIn; | |||
2694 | int MemberDFSOut = VD.DFSOut; | |||
2695 | Value *Def = VD.Def.getPointer(); | |||
2696 | bool FromStore = VD.Def.getInt(); | |||
2697 | Use *U = VD.U; | |||
2698 | // We ignore void things because we can't get a value from them. | |||
2699 | if (Def && Def->getType()->isVoidTy()) | |||
2700 | continue; | |||
2701 | ||||
2702 | if (EliminationStack.empty()) { | |||
2703 | DEBUG(dbgs() << "Elimination Stack is empty\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Elimination Stack is empty\n"; } } while (false); | |||
2704 | } else { | |||
2705 | DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Elimination Stack Top DFS numbers are (" << EliminationStack.dfs_back().first << "," << EliminationStack.dfs_back().second << ")\n"; } } while (false) | |||
2706 | << EliminationStack.dfs_back().first << ","do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Elimination Stack Top DFS numbers are (" << EliminationStack.dfs_back().first << "," << EliminationStack.dfs_back().second << ")\n"; } } while (false) | |||
2707 | << EliminationStack.dfs_back().second << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Elimination Stack Top DFS numbers are (" << EliminationStack.dfs_back().first << "," << EliminationStack.dfs_back().second << ")\n"; } } while (false); | |||
2708 | } | |||
2709 | ||||
2710 | DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Current DFS numbers are (" << MemberDFSIn << "," << MemberDFSOut << ")\n" ; } } while (false) | |||
2711 | << MemberDFSOut << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Current DFS numbers are (" << MemberDFSIn << "," << MemberDFSOut << ")\n" ; } } while (false); | |||
2712 | // First, we see if we are out of scope or empty. If so, | |||
2713 | // and there equivalences, we try to replace the top of | |||
2714 | // stack with equivalences (if it's on the stack, it must | |||
2715 | // not have been eliminated yet). | |||
2716 | // Then we synchronize to our current scope, by | |||
2717 | // popping until we are back within a DFS scope that | |||
2718 | // dominates the current member. | |||
2719 | // Then, what happens depends on a few factors | |||
2720 | // If the stack is now empty, we need to push | |||
2721 | // If we have a constant or a local equivalence we want to | |||
2722 | // start using, we also push. | |||
2723 | // Otherwise, we walk along, processing members who are | |||
2724 | // dominated by this scope, and eliminate them. | |||
2725 | bool ShouldPush = Def && EliminationStack.empty(); | |||
2726 | bool OutOfScope = | |||
2727 | !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut); | |||
2728 | ||||
2729 | if (OutOfScope || ShouldPush) { | |||
2730 | // Sync to our current scope. | |||
2731 | EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); | |||
2732 | bool ShouldPush = Def && EliminationStack.empty(); | |||
2733 | if (ShouldPush) { | |||
2734 | EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut); | |||
2735 | } | |||
2736 | } | |||
2737 | ||||
2738 | // Skip the Def's, we only want to eliminate on their uses. But mark | |||
2739 | // dominated defs as dead. | |||
2740 | if (Def) { | |||
2741 | // For anything in this case, what and how we value number | |||
2742 | // guarantees that any side-effets that would have occurred (ie | |||
2743 | // throwing, etc) can be proven to either still occur (because it's | |||
2744 | // dominated by something that has the same side-effects), or never | |||
2745 | // occur. Otherwise, we would not have been able to prove it value | |||
2746 | // equivalent to something else. For these things, we can just mark | |||
2747 | // it all dead. Note that this is different from the "ProbablyDead" | |||
2748 | // set, which may not be dominated by anything, and thus, are only | |||
2749 | // easy to prove dead if they are also side-effect free. Note that | |||
2750 | // because stores are put in terms of the stored value, we skip | |||
2751 | // stored values here. If the stored value is really dead, it will | |||
2752 | // still be marked for deletion when we process it in its own class. | |||
2753 | if (!EliminationStack.empty() && Def != EliminationStack.back() && | |||
2754 | isa<Instruction>(Def) && !FromStore) | |||
2755 | markInstructionForDeletion(cast<Instruction>(Def)); | |||
2756 | continue; | |||
2757 | } | |||
2758 | // At this point, we know it is a Use we are trying to possibly | |||
2759 | // replace. | |||
2760 | ||||
2761 | assert(isa<Instruction>(U->get()) &&((isa<Instruction>(U->get()) && "Current def should have been an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(U->get()) && \"Current def should have been an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2762, __PRETTY_FUNCTION__)) | |||
2762 | "Current def should have been an instruction")((isa<Instruction>(U->get()) && "Current def should have been an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(U->get()) && \"Current def should have been an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2762, __PRETTY_FUNCTION__)); | |||
2763 | assert(isa<Instruction>(U->getUser()) &&((isa<Instruction>(U->getUser()) && "Current user should have been an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(U->getUser()) && \"Current user should have been an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2764, __PRETTY_FUNCTION__)) | |||
2764 | "Current user should have been an instruction")((isa<Instruction>(U->getUser()) && "Current user should have been an instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<Instruction>(U->getUser()) && \"Current user should have been an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2764, __PRETTY_FUNCTION__)); | |||
2765 | ||||
2766 | // If the thing we are replacing into is already marked to be dead, | |||
2767 | // this use is dead. Note that this is true regardless of whether | |||
2768 | // we have anything dominating the use or not. We do this here | |||
2769 | // because we are already walking all the uses anyway. | |||
2770 | Instruction *InstUse = cast<Instruction>(U->getUser()); | |||
2771 | if (InstructionsToErase.count(InstUse)) { | |||
2772 | auto &UseCount = UseCounts[U->get()]; | |||
2773 | if (--UseCount == 0) { | |||
2774 | ProbablyDead.insert(cast<Instruction>(U->get())); | |||
2775 | } | |||
2776 | } | |||
2777 | ||||
2778 | // If we get to this point, and the stack is empty we must have a use | |||
2779 | // with nothing we can use to eliminate this use, so just skip it. | |||
2780 | if (EliminationStack.empty()) | |||
2781 | continue; | |||
2782 | ||||
2783 | Value *DominatingLeader = EliminationStack.back(); | |||
2784 | ||||
2785 | // Don't replace our existing users with ourselves. | |||
2786 | if (U->get() == DominatingLeader) | |||
2787 | continue; | |||
2788 | DEBUG(dbgs() << "Found replacement " << *DominatingLeader << " for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found replacement " << * DominatingLeader << " for " << *U->get() << " in " << *(U->getUser()) << "\n"; } } while ( false) | |||
2789 | << *U->get() << " in " << *(U->getUser()) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Found replacement " << * DominatingLeader << " for " << *U->get() << " in " << *(U->getUser()) << "\n"; } } while ( false); | |||
2790 | ||||
2791 | // If we replaced something in an instruction, handle the patching of | |||
2792 | // metadata. Skip this if we are replacing predicateinfo with its | |||
2793 | // original operand, as we already know we can just drop it. | |||
2794 | auto *ReplacedInst = cast<Instruction>(U->get()); | |||
2795 | auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst); | |||
2796 | if (!PI || DominatingLeader != PI->OriginalOp) | |||
2797 | patchReplacementInstruction(ReplacedInst, DominatingLeader); | |||
2798 | U->set(DominatingLeader); | |||
2799 | // This is now a use of the dominating leader, which means if the | |||
2800 | // dominating leader was dead, it's now live! | |||
2801 | auto &LeaderUseCount = UseCounts[DominatingLeader]; | |||
2802 | // It's about to be alive again. | |||
2803 | if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader)) | |||
2804 | ProbablyDead.erase(cast<Instruction>(DominatingLeader)); | |||
2805 | ++LeaderUseCount; | |||
2806 | AnythingReplaced = true; | |||
2807 | } | |||
2808 | } | |||
2809 | } | |||
2810 | ||||
2811 | // At this point, anything still in the ProbablyDead set is actually dead if | |||
2812 | // would be trivially dead. | |||
2813 | for (auto *I : ProbablyDead) | |||
2814 | if (wouldInstructionBeTriviallyDead(I)) | |||
2815 | markInstructionForDeletion(I); | |||
2816 | ||||
2817 | // Cleanup the congruence class. | |||
2818 | SmallPtrSet<Value *, 4> MembersLeft; | |||
2819 | for (Value *Member : CC->Members) { | |||
2820 | if (Member->getType()->isVoidTy()) { | |||
2821 | MembersLeft.insert(Member); | |||
2822 | continue; | |||
2823 | } | |||
2824 | ||||
2825 | MembersLeft.insert(Member); | |||
2826 | } | |||
2827 | CC->Members.swap(MembersLeft); | |||
2828 | ||||
2829 | // If we have possible dead stores to look at, try to eliminate them. | |||
2830 | if (CC->StoreCount > 0) { | |||
2831 | convertClassToLoadsAndStores(CC->Members, PossibleDeadStores); | |||
2832 | std::sort(PossibleDeadStores.begin(), PossibleDeadStores.end()); | |||
2833 | ValueDFSStack EliminationStack; | |||
2834 | for (auto &VD : PossibleDeadStores) { | |||
2835 | int MemberDFSIn = VD.DFSIn; | |||
2836 | int MemberDFSOut = VD.DFSOut; | |||
2837 | Instruction *Member = cast<Instruction>(VD.Def.getPointer()); | |||
2838 | if (EliminationStack.empty() || | |||
2839 | !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) { | |||
2840 | // Sync to our current scope. | |||
2841 | EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); | |||
2842 | if (EliminationStack.empty()) { | |||
2843 | EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut); | |||
2844 | continue; | |||
2845 | } | |||
2846 | } | |||
2847 | // We already did load elimination, so nothing to do here. | |||
2848 | if (isa<LoadInst>(Member)) | |||
2849 | continue; | |||
2850 | assert(!EliminationStack.empty())((!EliminationStack.empty()) ? static_cast<void> (0) : __assert_fail ("!EliminationStack.empty()", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2850, __PRETTY_FUNCTION__)); | |||
2851 | Instruction *Leader = cast<Instruction>(EliminationStack.back()); | |||
2852 | (void)Leader; | |||
2853 | assert(DT->dominates(Leader->getParent(), Member->getParent()))((DT->dominates(Leader->getParent(), Member->getParent ())) ? static_cast<void> (0) : __assert_fail ("DT->dominates(Leader->getParent(), Member->getParent())" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299582/lib/Transforms/Scalar/NewGVN.cpp" , 2853, __PRETTY_FUNCTION__)); | |||
2854 | // Member is dominater by Leader, and thus dead | |||
2855 | DEBUG(dbgs() << "Marking dead store " << *Memberdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Marking dead store " << * Member << " that is dominated by " << *Leader << "\n"; } } while (false) | |||
2856 | << " that is dominated by " << *Leader << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("newgvn")) { dbgs() << "Marking dead store " << * Member << " that is dominated by " << *Leader << "\n"; } } while (false); | |||
2857 | markInstructionForDeletion(Member); | |||
2858 | CC->Members.erase(Member); | |||
2859 | ++NumGVNDeadStores; | |||
2860 | } | |||
2861 | } | |||
2862 | } | |||
2863 | ||||
2864 | return AnythingReplaced; | |||
2865 | } | |||
2866 | ||||
2867 | // This function provides global ranking of operations so that we can place them | |||
2868 | // in a canonical order. Note that rank alone is not necessarily enough for a | |||
2869 | // complete ordering, as constants all have the same rank. However, generally, | |||
2870 | // we will simplify an operation with all constants so that it doesn't matter | |||
2871 | // what order they appear in. | |||
2872 | unsigned int NewGVN::getRank(const Value *V) const { | |||
2873 | // Prefer undef to anything else | |||
2874 | if (isa<UndefValue>(V)) | |||
2875 | return 0; | |||
2876 | if (isa<Constant>(V)) | |||
2877 | return 1; | |||
2878 | else if (auto *A = dyn_cast<Argument>(V)) | |||
2879 | return 2 + A->getArgNo(); | |||
2880 | ||||
2881 | // Need to shift the instruction DFS by number of arguments + 3 to account for | |||
2882 | // the constant and argument ranking above. | |||
2883 | unsigned Result = InstrDFS.lookup(V); | |||
2884 | if (Result > 0) | |||
2885 | return 3 + NumFuncArgs + Result; | |||
2886 | // Unreachable or something else, just return a really large number. | |||
2887 | return ~0; | |||
2888 | } | |||
2889 | ||||
2890 | // This is a function that says whether two commutative operations should | |||
2891 | // have their order swapped when canonicalizing. | |||
2892 | bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const { | |||
2893 | // Because we only care about a total ordering, and don't rewrite expressions | |||
2894 | // in this order, we order by rank, which will give a strict weak ordering to | |||
2895 | // everything but constants, and then we order by pointer address. | |||
2896 | return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B); | |||
2897 | } | |||
2898 | ||||
2899 | class NewGVNLegacyPass : public FunctionPass { | |||
2900 | public: | |||
2901 | static char ID; // Pass identification, replacement for typeid. | |||
2902 | NewGVNLegacyPass() : FunctionPass(ID) { | |||
2903 | initializeNewGVNLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
2904 | } | |||
2905 | bool runOnFunction(Function &F) override; | |||
2906 | ||||
2907 | private: | |||
2908 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
2909 | AU.addRequired<AssumptionCacheTracker>(); | |||
2910 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
2911 | AU.addRequired<TargetLibraryInfoWrapperPass>(); | |||
2912 | AU.addRequired<MemorySSAWrapperPass>(); | |||
2913 | AU.addRequired<AAResultsWrapperPass>(); | |||
2914 | AU.addPreserved<DominatorTreeWrapperPass>(); | |||
2915 | AU.addPreserved<GlobalsAAWrapperPass>(); | |||
2916 | } | |||
2917 | }; | |||
2918 | ||||
2919 | bool NewGVNLegacyPass::runOnFunction(Function &F) { | |||
2920 | if (skipFunction(F)) | |||
2921 | return false; | |||
2922 | return NewGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), | |||
2923 | &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F), | |||
2924 | &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), | |||
2925 | &getAnalysis<AAResultsWrapperPass>().getAAResults(), | |||
2926 | &getAnalysis<MemorySSAWrapperPass>().getMSSA(), | |||
2927 | F.getParent()->getDataLayout()) | |||
2928 | .runGVN(); | |||
2929 | } | |||
2930 | ||||
2931 | INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering",static void *initializeNewGVNLegacyPassPassOnce(PassRegistry & Registry) { | |||
2932 | false, false)static void *initializeNewGVNLegacyPassPassOnce(PassRegistry & Registry) { | |||
2933 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
2934 | INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry); | |||
2935 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
2936 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry); | |||
2937 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry); | |||
2938 | INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry); | |||
2939 | INITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false,PassInfo *PI = new PassInfo( "Global Value Numbering", "newgvn" , &NewGVNLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <NewGVNLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeNewGVNLegacyPassPassFlag ; void llvm::initializeNewGVNLegacyPassPass(PassRegistry & Registry) { llvm::call_once(InitializeNewGVNLegacyPassPassFlag , initializeNewGVNLegacyPassPassOnce, std::ref(Registry)); } | |||
2940 | false)PassInfo *PI = new PassInfo( "Global Value Numbering", "newgvn" , &NewGVNLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <NewGVNLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeNewGVNLegacyPassPassFlag ; void llvm::initializeNewGVNLegacyPassPass(PassRegistry & Registry) { llvm::call_once(InitializeNewGVNLegacyPassPassFlag , initializeNewGVNLegacyPassPassOnce, std::ref(Registry)); } | |||
2941 | ||||
2942 | char NewGVNLegacyPass::ID = 0; | |||
2943 | ||||
2944 | // createGVNPass - The public interface to this file. | |||
2945 | FunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); } | |||
2946 | ||||
2947 | PreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) { | |||
2948 | // Apparently the order in which we get these results matter for | |||
2949 | // the old GVN (see Chandler's comment in GVN.cpp). I'll keep | |||
2950 | // the same order here, just in case. | |||
2951 | auto &AC = AM.getResult<AssumptionAnalysis>(F); | |||
2952 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); | |||
2953 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); | |||
2954 | auto &AA = AM.getResult<AAManager>(F); | |||
2955 | auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA(); | |||
2956 | bool Changed = | |||
2957 | NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout()) | |||
2958 | .runGVN(); | |||
2959 | if (!Changed) | |||
2960 | return PreservedAnalyses::all(); | |||
2961 | PreservedAnalyses PA; | |||
2962 | PA.preserve<DominatorTreeAnalysis>(); | |||
2963 | PA.preserve<GlobalsAA>(); | |||
2964 | return PA; | |||
2965 | } |