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