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