File: | lib/Transforms/Utils/MemorySSA.cpp |
Warning: | line 852, column 37 Called C++ object pointer is null |
1 | //===-- MemorySSA.cpp - Memory SSA Builder---------------------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements the MemorySSA class. | |||
11 | // | |||
12 | //===----------------------------------------------------------------===// | |||
13 | #include "llvm/Transforms/Utils/MemorySSA.h" | |||
14 | #include "llvm/ADT/DenseMap.h" | |||
15 | #include "llvm/ADT/DenseSet.h" | |||
16 | #include "llvm/ADT/DepthFirstIterator.h" | |||
17 | #include "llvm/ADT/GraphTraits.h" | |||
18 | #include "llvm/ADT/PostOrderIterator.h" | |||
19 | #include "llvm/ADT/STLExtras.h" | |||
20 | #include "llvm/ADT/SmallBitVector.h" | |||
21 | #include "llvm/ADT/SmallPtrSet.h" | |||
22 | #include "llvm/ADT/SmallSet.h" | |||
23 | #include "llvm/ADT/Statistic.h" | |||
24 | #include "llvm/Analysis/AliasAnalysis.h" | |||
25 | #include "llvm/Analysis/CFG.h" | |||
26 | #include "llvm/Analysis/GlobalsModRef.h" | |||
27 | #include "llvm/Analysis/IteratedDominanceFrontier.h" | |||
28 | #include "llvm/Analysis/MemoryLocation.h" | |||
29 | #include "llvm/Analysis/PHITransAddr.h" | |||
30 | #include "llvm/IR/AssemblyAnnotationWriter.h" | |||
31 | #include "llvm/IR/DataLayout.h" | |||
32 | #include "llvm/IR/Dominators.h" | |||
33 | #include "llvm/IR/GlobalVariable.h" | |||
34 | #include "llvm/IR/IRBuilder.h" | |||
35 | #include "llvm/IR/IntrinsicInst.h" | |||
36 | #include "llvm/IR/LLVMContext.h" | |||
37 | #include "llvm/IR/Metadata.h" | |||
38 | #include "llvm/IR/Module.h" | |||
39 | #include "llvm/IR/PatternMatch.h" | |||
40 | #include "llvm/Support/Debug.h" | |||
41 | #include "llvm/Support/FormattedStream.h" | |||
42 | #include "llvm/Transforms/Scalar.h" | |||
43 | #include <algorithm> | |||
44 | ||||
45 | #define DEBUG_TYPE"memoryssa" "memoryssa" | |||
46 | using namespace llvm; | |||
47 | STATISTIC(NumClobberCacheLookups, "Number of Memory SSA version cache lookups")static llvm::Statistic NumClobberCacheLookups = {"memoryssa", "NumClobberCacheLookups", "Number of Memory SSA version cache lookups" , {0}, false}; | |||
48 | STATISTIC(NumClobberCacheHits, "Number of Memory SSA version cache hits")static llvm::Statistic NumClobberCacheHits = {"memoryssa", "NumClobberCacheHits" , "Number of Memory SSA version cache hits", {0}, false}; | |||
49 | STATISTIC(NumClobberCacheInserts, "Number of MemorySSA version cache inserts")static llvm::Statistic NumClobberCacheInserts = {"memoryssa", "NumClobberCacheInserts", "Number of MemorySSA version cache inserts" , {0}, false}; | |||
50 | ||||
51 | INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,static void *initializeMemorySSAWrapperPassPassOnce(PassRegistry &Registry) { | |||
52 | true)static void *initializeMemorySSAWrapperPassPassOnce(PassRegistry &Registry) { | |||
53 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
54 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry); | |||
55 | INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,PassInfo *PI = new PassInfo( "Memory SSA", "memoryssa", & MemorySSAWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <MemorySSAWrapperPass>), false, true); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeMemorySSAWrapperPassPassFlag ; void llvm::initializeMemorySSAWrapperPassPass(PassRegistry & Registry) { llvm::call_once(InitializeMemorySSAWrapperPassPassFlag , initializeMemorySSAWrapperPassPassOnce, std::ref(Registry)) ; } | |||
56 | true)PassInfo *PI = new PassInfo( "Memory SSA", "memoryssa", & MemorySSAWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <MemorySSAWrapperPass>), false, true); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeMemorySSAWrapperPassPassFlag ; void llvm::initializeMemorySSAWrapperPassPass(PassRegistry & Registry) { llvm::call_once(InitializeMemorySSAWrapperPassPassFlag , initializeMemorySSAWrapperPassPassOnce, std::ref(Registry)) ; } | |||
57 | ||||
58 | INITIALIZE_PASS_BEGIN(MemorySSAPrinterLegacyPass, "print-memoryssa",static void *initializeMemorySSAPrinterLegacyPassPassOnce(PassRegistry &Registry) { | |||
59 | "Memory SSA Printer", false, false)static void *initializeMemorySSAPrinterLegacyPassPassOnce(PassRegistry &Registry) { | |||
60 | INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry); | |||
61 | INITIALIZE_PASS_END(MemorySSAPrinterLegacyPass, "print-memoryssa",PassInfo *PI = new PassInfo( "Memory SSA Printer", "print-memoryssa" , &MemorySSAPrinterLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<MemorySSAPrinterLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeMemorySSAPrinterLegacyPassPassFlag; void llvm::initializeMemorySSAPrinterLegacyPassPass(PassRegistry & Registry) { llvm::call_once(InitializeMemorySSAPrinterLegacyPassPassFlag , initializeMemorySSAPrinterLegacyPassPassOnce, std::ref(Registry )); } | |||
62 | "Memory SSA Printer", false, false)PassInfo *PI = new PassInfo( "Memory SSA Printer", "print-memoryssa" , &MemorySSAPrinterLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<MemorySSAPrinterLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeMemorySSAPrinterLegacyPassPassFlag; void llvm::initializeMemorySSAPrinterLegacyPassPass(PassRegistry & Registry) { llvm::call_once(InitializeMemorySSAPrinterLegacyPassPassFlag , initializeMemorySSAPrinterLegacyPassPassOnce, std::ref(Registry )); } | |||
63 | ||||
64 | static cl::opt<unsigned> MaxCheckLimit( | |||
65 | "memssa-check-limit", cl::Hidden, cl::init(100), | |||
66 | cl::desc("The maximum number of stores/phis MemorySSA" | |||
67 | "will consider trying to walk past (default = 100)")); | |||
68 | ||||
69 | static cl::opt<bool> | |||
70 | VerifyMemorySSA("verify-memoryssa", cl::init(false), cl::Hidden, | |||
71 | cl::desc("Verify MemorySSA in legacy printer pass.")); | |||
72 | ||||
73 | namespace llvm { | |||
74 | /// \brief An assembly annotator class to print Memory SSA information in | |||
75 | /// comments. | |||
76 | class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter { | |||
77 | friend class MemorySSA; | |||
78 | const MemorySSA *MSSA; | |||
79 | ||||
80 | public: | |||
81 | MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {} | |||
82 | ||||
83 | virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, | |||
84 | formatted_raw_ostream &OS) { | |||
85 | if (MemoryAccess *MA = MSSA->getMemoryAccess(BB)) | |||
86 | OS << "; " << *MA << "\n"; | |||
87 | } | |||
88 | ||||
89 | virtual void emitInstructionAnnot(const Instruction *I, | |||
90 | formatted_raw_ostream &OS) { | |||
91 | if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) | |||
92 | OS << "; " << *MA << "\n"; | |||
93 | } | |||
94 | }; | |||
95 | } | |||
96 | ||||
97 | namespace { | |||
98 | /// Our current alias analysis API differentiates heavily between calls and | |||
99 | /// non-calls, and functions called on one usually assert on the other. | |||
100 | /// This class encapsulates the distinction to simplify other code that wants | |||
101 | /// "Memory affecting instructions and related data" to use as a key. | |||
102 | /// For example, this class is used as a densemap key in the use optimizer. | |||
103 | class MemoryLocOrCall { | |||
104 | public: | |||
105 | MemoryLocOrCall() : IsCall(false) {} | |||
106 | MemoryLocOrCall(MemoryUseOrDef *MUD) | |||
107 | : MemoryLocOrCall(MUD->getMemoryInst()) {} | |||
108 | MemoryLocOrCall(const MemoryUseOrDef *MUD) | |||
109 | : MemoryLocOrCall(MUD->getMemoryInst()) {} | |||
110 | ||||
111 | MemoryLocOrCall(Instruction *Inst) { | |||
112 | if (ImmutableCallSite(Inst)) { | |||
113 | IsCall = true; | |||
114 | CS = ImmutableCallSite(Inst); | |||
115 | } else { | |||
116 | IsCall = false; | |||
117 | // There is no such thing as a memorylocation for a fence inst, and it is | |||
118 | // unique in that regard. | |||
119 | if (!isa<FenceInst>(Inst)) | |||
120 | Loc = MemoryLocation::get(Inst); | |||
121 | } | |||
122 | } | |||
123 | ||||
124 | explicit MemoryLocOrCall(const MemoryLocation &Loc) | |||
125 | : IsCall(false), Loc(Loc) {} | |||
126 | ||||
127 | bool IsCall; | |||
128 | ImmutableCallSite getCS() const { | |||
129 | assert(IsCall)((IsCall) ? static_cast<void> (0) : __assert_fail ("IsCall" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 129, __PRETTY_FUNCTION__)); | |||
130 | return CS; | |||
131 | } | |||
132 | MemoryLocation getLoc() const { | |||
133 | assert(!IsCall)((!IsCall) ? static_cast<void> (0) : __assert_fail ("!IsCall" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 133, __PRETTY_FUNCTION__)); | |||
134 | return Loc; | |||
135 | } | |||
136 | ||||
137 | bool operator==(const MemoryLocOrCall &Other) const { | |||
138 | if (IsCall != Other.IsCall) | |||
139 | return false; | |||
140 | ||||
141 | if (IsCall) | |||
142 | return CS.getCalledValue() == Other.CS.getCalledValue(); | |||
143 | return Loc == Other.Loc; | |||
144 | } | |||
145 | ||||
146 | private: | |||
147 | union { | |||
148 | ImmutableCallSite CS; | |||
149 | MemoryLocation Loc; | |||
150 | }; | |||
151 | }; | |||
152 | } | |||
153 | ||||
154 | namespace llvm { | |||
155 | template <> struct DenseMapInfo<MemoryLocOrCall> { | |||
156 | static inline MemoryLocOrCall getEmptyKey() { | |||
157 | return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey()); | |||
158 | } | |||
159 | static inline MemoryLocOrCall getTombstoneKey() { | |||
160 | return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getTombstoneKey()); | |||
161 | } | |||
162 | static unsigned getHashValue(const MemoryLocOrCall &MLOC) { | |||
163 | if (MLOC.IsCall) | |||
164 | return hash_combine(MLOC.IsCall, | |||
165 | DenseMapInfo<const Value *>::getHashValue( | |||
166 | MLOC.getCS().getCalledValue())); | |||
167 | return hash_combine( | |||
168 | MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc())); | |||
169 | } | |||
170 | static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) { | |||
171 | return LHS == RHS; | |||
172 | } | |||
173 | }; | |||
174 | ||||
175 | enum class Reorderability { Always, IfNoAlias, Never }; | |||
176 | ||||
177 | /// This does one-way checks to see if Use could theoretically be hoisted above | |||
178 | /// MayClobber. This will not check the other way around. | |||
179 | /// | |||
180 | /// This assumes that, for the purposes of MemorySSA, Use comes directly after | |||
181 | /// MayClobber, with no potentially clobbering operations in between them. | |||
182 | /// (Where potentially clobbering ops are memory barriers, aliased stores, etc.) | |||
183 | static Reorderability getLoadReorderability(const LoadInst *Use, | |||
184 | const LoadInst *MayClobber) { | |||
185 | bool VolatileUse = Use->isVolatile(); | |||
186 | bool VolatileClobber = MayClobber->isVolatile(); | |||
187 | // Volatile operations may never be reordered with other volatile operations. | |||
188 | if (VolatileUse && VolatileClobber) | |||
189 | return Reorderability::Never; | |||
190 | ||||
191 | // The lang ref allows reordering of volatile and non-volatile operations. | |||
192 | // Whether an aliasing nonvolatile load and volatile load can be reordered, | |||
193 | // though, is ambiguous. Because it may not be best to exploit this ambiguity, | |||
194 | // we only allow volatile/non-volatile reordering if the volatile and | |||
195 | // non-volatile operations don't alias. | |||
196 | Reorderability Result = VolatileUse || VolatileClobber | |||
197 | ? Reorderability::IfNoAlias | |||
198 | : Reorderability::Always; | |||
199 | ||||
200 | // If a load is seq_cst, it cannot be moved above other loads. If its ordering | |||
201 | // is weaker, it can be moved above other loads. We just need to be sure that | |||
202 | // MayClobber isn't an acquire load, because loads can't be moved above | |||
203 | // acquire loads. | |||
204 | // | |||
205 | // Note that this explicitly *does* allow the free reordering of monotonic (or | |||
206 | // weaker) loads of the same address. | |||
207 | bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent; | |||
208 | bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(), | |||
209 | AtomicOrdering::Acquire); | |||
210 | if (SeqCstUse || MayClobberIsAcquire) | |||
211 | return Reorderability::Never; | |||
212 | return Result; | |||
213 | } | |||
214 | ||||
215 | static bool instructionClobbersQuery(MemoryDef *MD, | |||
216 | const MemoryLocation &UseLoc, | |||
217 | const Instruction *UseInst, | |||
218 | AliasAnalysis &AA) { | |||
219 | Instruction *DefInst = MD->getMemoryInst(); | |||
220 | assert(DefInst && "Defining instruction not actually an instruction")((DefInst && "Defining instruction not actually an instruction" ) ? static_cast<void> (0) : __assert_fail ("DefInst && \"Defining instruction not actually an instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 220, __PRETTY_FUNCTION__)); | |||
221 | ||||
222 | if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) { | |||
223 | // These intrinsics will show up as affecting memory, but they are just | |||
224 | // markers. | |||
225 | switch (II->getIntrinsicID()) { | |||
226 | case Intrinsic::lifetime_start: | |||
227 | case Intrinsic::lifetime_end: | |||
228 | case Intrinsic::invariant_start: | |||
229 | case Intrinsic::invariant_end: | |||
230 | case Intrinsic::assume: | |||
231 | return false; | |||
232 | default: | |||
233 | break; | |||
234 | } | |||
235 | } | |||
236 | ||||
237 | ImmutableCallSite UseCS(UseInst); | |||
238 | if (UseCS) { | |||
239 | ModRefInfo I = AA.getModRefInfo(DefInst, UseCS); | |||
240 | return I != MRI_NoModRef; | |||
241 | } | |||
242 | ||||
243 | if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) { | |||
244 | if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) { | |||
245 | switch (getLoadReorderability(UseLoad, DefLoad)) { | |||
246 | case Reorderability::Always: | |||
247 | return false; | |||
248 | case Reorderability::Never: | |||
249 | return true; | |||
250 | case Reorderability::IfNoAlias: | |||
251 | return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad)); | |||
252 | } | |||
253 | } | |||
254 | } | |||
255 | ||||
256 | return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; | |||
257 | } | |||
258 | ||||
259 | static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU, | |||
260 | const MemoryLocOrCall &UseMLOC, | |||
261 | AliasAnalysis &AA) { | |||
262 | // FIXME: This is a temporary hack to allow a single instructionClobbersQuery | |||
263 | // to exist while MemoryLocOrCall is pushed through places. | |||
264 | if (UseMLOC.IsCall) | |||
265 | return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(), | |||
266 | AA); | |||
267 | return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(), | |||
268 | AA); | |||
269 | } | |||
270 | ||||
271 | // Return true when MD may alias MU, return false otherwise. | |||
272 | bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, | |||
273 | AliasAnalysis &AA) { | |||
274 | return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA); | |||
275 | } | |||
276 | } | |||
277 | ||||
278 | namespace { | |||
279 | struct UpwardsMemoryQuery { | |||
280 | // True if our original query started off as a call | |||
281 | bool IsCall; | |||
282 | // The pointer location we started the query with. This will be empty if | |||
283 | // IsCall is true. | |||
284 | MemoryLocation StartingLoc; | |||
285 | // This is the instruction we were querying about. | |||
286 | const Instruction *Inst; | |||
287 | // The MemoryAccess we actually got called with, used to test local domination | |||
288 | const MemoryAccess *OriginalAccess; | |||
289 | ||||
290 | UpwardsMemoryQuery() | |||
291 | : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {} | |||
292 | ||||
293 | UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access) | |||
294 | : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) { | |||
295 | if (!IsCall) | |||
296 | StartingLoc = MemoryLocation::get(Inst); | |||
297 | } | |||
298 | }; | |||
299 | ||||
300 | static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc, | |||
301 | AliasAnalysis &AA) { | |||
302 | Instruction *Inst = MD->getMemoryInst(); | |||
303 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { | |||
304 | switch (II->getIntrinsicID()) { | |||
305 | case Intrinsic::lifetime_start: | |||
306 | case Intrinsic::lifetime_end: | |||
307 | return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc); | |||
308 | default: | |||
309 | return false; | |||
310 | } | |||
311 | } | |||
312 | return false; | |||
313 | } | |||
314 | ||||
315 | static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA, | |||
316 | const Instruction *I) { | |||
317 | // If the memory can't be changed, then loads of the memory can't be | |||
318 | // clobbered. | |||
319 | // | |||
320 | // FIXME: We should handle invariant groups, as well. It's a bit harder, | |||
321 | // because we need to pay close attention to invariant group barriers. | |||
322 | return isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) || | |||
323 | AA.pointsToConstantMemory(I)); | |||
324 | } | |||
325 | ||||
326 | /// Cache for our caching MemorySSA walker. | |||
327 | class WalkerCache { | |||
328 | DenseMap<ConstMemoryAccessPair, MemoryAccess *> Accesses; | |||
329 | DenseMap<const MemoryAccess *, MemoryAccess *> Calls; | |||
330 | ||||
331 | public: | |||
332 | MemoryAccess *lookup(const MemoryAccess *MA, const MemoryLocation &Loc, | |||
333 | bool IsCall) const { | |||
334 | ++NumClobberCacheLookups; | |||
335 | MemoryAccess *R = IsCall ? Calls.lookup(MA) : Accesses.lookup({MA, Loc}); | |||
336 | if (R) | |||
337 | ++NumClobberCacheHits; | |||
338 | return R; | |||
339 | } | |||
340 | ||||
341 | bool insert(const MemoryAccess *MA, MemoryAccess *To, | |||
342 | const MemoryLocation &Loc, bool IsCall) { | |||
343 | // This is fine for Phis, since there are times where we can't optimize | |||
344 | // them. Making a def its own clobber is never correct, though. | |||
345 | assert((MA != To || isa<MemoryPhi>(MA)) &&(((MA != To || isa<MemoryPhi>(MA)) && "Something can't clobber itself!" ) ? static_cast<void> (0) : __assert_fail ("(MA != To || isa<MemoryPhi>(MA)) && \"Something can't clobber itself!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 346, __PRETTY_FUNCTION__)) | |||
346 | "Something can't clobber itself!")(((MA != To || isa<MemoryPhi>(MA)) && "Something can't clobber itself!" ) ? static_cast<void> (0) : __assert_fail ("(MA != To || isa<MemoryPhi>(MA)) && \"Something can't clobber itself!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 346, __PRETTY_FUNCTION__)); | |||
347 | ||||
348 | ++NumClobberCacheInserts; | |||
349 | bool Inserted; | |||
350 | if (IsCall) | |||
351 | Inserted = Calls.insert({MA, To}).second; | |||
352 | else | |||
353 | Inserted = Accesses.insert({{MA, Loc}, To}).second; | |||
354 | ||||
355 | return Inserted; | |||
356 | } | |||
357 | ||||
358 | bool remove(const MemoryAccess *MA, const MemoryLocation &Loc, bool IsCall) { | |||
359 | return IsCall ? Calls.erase(MA) : Accesses.erase({MA, Loc}); | |||
360 | } | |||
361 | ||||
362 | void clear() { | |||
363 | Accesses.clear(); | |||
364 | Calls.clear(); | |||
365 | } | |||
366 | ||||
367 | bool contains(const MemoryAccess *MA) const { | |||
368 | for (auto &P : Accesses) | |||
369 | if (P.first.first == MA || P.second == MA) | |||
370 | return true; | |||
371 | for (auto &P : Calls) | |||
372 | if (P.first == MA || P.second == MA) | |||
373 | return true; | |||
374 | return false; | |||
375 | } | |||
376 | }; | |||
377 | ||||
378 | /// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing | |||
379 | /// inbetween `Start` and `ClobberAt` can clobbers `Start`. | |||
380 | /// | |||
381 | /// This is meant to be as simple and self-contained as possible. Because it | |||
382 | /// uses no cache, etc., it can be relatively expensive. | |||
383 | /// | |||
384 | /// \param Start The MemoryAccess that we want to walk from. | |||
385 | /// \param ClobberAt A clobber for Start. | |||
386 | /// \param StartLoc The MemoryLocation for Start. | |||
387 | /// \param MSSA The MemorySSA isntance that Start and ClobberAt belong to. | |||
388 | /// \param Query The UpwardsMemoryQuery we used for our search. | |||
389 | /// \param AA The AliasAnalysis we used for our search. | |||
390 | static void LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) | |||
391 | checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt, | |||
392 | const MemoryLocation &StartLoc, const MemorySSA &MSSA, | |||
393 | const UpwardsMemoryQuery &Query, AliasAnalysis &AA) { | |||
394 | assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?")((MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?" ) ? static_cast<void> (0) : __assert_fail ("MSSA.dominates(ClobberAt, Start) && \"Clobber doesn't dominate start?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 394, __PRETTY_FUNCTION__)); | |||
395 | ||||
396 | if (MSSA.isLiveOnEntryDef(Start)) { | |||
397 | assert(MSSA.isLiveOnEntryDef(ClobberAt) &&((MSSA.isLiveOnEntryDef(ClobberAt) && "liveOnEntry must clobber itself" ) ? static_cast<void> (0) : __assert_fail ("MSSA.isLiveOnEntryDef(ClobberAt) && \"liveOnEntry must clobber itself\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 398, __PRETTY_FUNCTION__)) | |||
398 | "liveOnEntry must clobber itself")((MSSA.isLiveOnEntryDef(ClobberAt) && "liveOnEntry must clobber itself" ) ? static_cast<void> (0) : __assert_fail ("MSSA.isLiveOnEntryDef(ClobberAt) && \"liveOnEntry must clobber itself\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 398, __PRETTY_FUNCTION__)); | |||
399 | return; | |||
400 | } | |||
401 | ||||
402 | bool FoundClobber = false; | |||
403 | DenseSet<MemoryAccessPair> VisitedPhis; | |||
404 | SmallVector<MemoryAccessPair, 8> Worklist; | |||
405 | Worklist.emplace_back(Start, StartLoc); | |||
406 | // Walk all paths from Start to ClobberAt, while looking for clobbers. If one | |||
407 | // is found, complain. | |||
408 | while (!Worklist.empty()) { | |||
409 | MemoryAccessPair MAP = Worklist.pop_back_val(); | |||
410 | // All we care about is that nothing from Start to ClobberAt clobbers Start. | |||
411 | // We learn nothing from revisiting nodes. | |||
412 | if (!VisitedPhis.insert(MAP).second) | |||
413 | continue; | |||
414 | ||||
415 | for (MemoryAccess *MA : def_chain(MAP.first)) { | |||
416 | if (MA == ClobberAt) { | |||
417 | if (auto *MD = dyn_cast<MemoryDef>(MA)) { | |||
418 | // instructionClobbersQuery isn't essentially free, so don't use `|=`, | |||
419 | // since it won't let us short-circuit. | |||
420 | // | |||
421 | // Also, note that this can't be hoisted out of the `Worklist` loop, | |||
422 | // since MD may only act as a clobber for 1 of N MemoryLocations. | |||
423 | FoundClobber = | |||
424 | FoundClobber || MSSA.isLiveOnEntryDef(MD) || | |||
425 | instructionClobbersQuery(MD, MAP.second, Query.Inst, AA); | |||
426 | } | |||
427 | break; | |||
428 | } | |||
429 | ||||
430 | // We should never hit liveOnEntry, unless it's the clobber. | |||
431 | assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?")((!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?" ) ? static_cast<void> (0) : __assert_fail ("!MSSA.isLiveOnEntryDef(MA) && \"Hit liveOnEntry before clobber?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 431, __PRETTY_FUNCTION__)); | |||
432 | ||||
433 | if (auto *MD = dyn_cast<MemoryDef>(MA)) { | |||
434 | (void)MD; | |||
435 | assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) &&((!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && "Found clobber before reaching ClobberAt!") ? static_cast< void> (0) : __assert_fail ("!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && \"Found clobber before reaching ClobberAt!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 436, __PRETTY_FUNCTION__)) | |||
436 | "Found clobber before reaching ClobberAt!")((!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && "Found clobber before reaching ClobberAt!") ? static_cast< void> (0) : __assert_fail ("!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && \"Found clobber before reaching ClobberAt!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 436, __PRETTY_FUNCTION__)); | |||
437 | continue; | |||
438 | } | |||
439 | ||||
440 | assert(isa<MemoryPhi>(MA))((isa<MemoryPhi>(MA)) ? static_cast<void> (0) : __assert_fail ("isa<MemoryPhi>(MA)", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 440, __PRETTY_FUNCTION__)); | |||
441 | Worklist.append(upward_defs_begin({MA, MAP.second}), upward_defs_end()); | |||
442 | } | |||
443 | } | |||
444 | ||||
445 | // If ClobberAt is a MemoryPhi, we can assume something above it acted as a | |||
446 | // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point. | |||
447 | assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&(((isa<MemoryPhi>(ClobberAt) || FoundClobber) && "ClobberAt never acted as a clobber") ? static_cast<void> (0) : __assert_fail ("(isa<MemoryPhi>(ClobberAt) || FoundClobber) && \"ClobberAt never acted as a clobber\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 448, __PRETTY_FUNCTION__)) | |||
448 | "ClobberAt never acted as a clobber")(((isa<MemoryPhi>(ClobberAt) || FoundClobber) && "ClobberAt never acted as a clobber") ? static_cast<void> (0) : __assert_fail ("(isa<MemoryPhi>(ClobberAt) || FoundClobber) && \"ClobberAt never acted as a clobber\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 448, __PRETTY_FUNCTION__)); | |||
449 | } | |||
450 | ||||
451 | /// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up | |||
452 | /// in one class. | |||
453 | class ClobberWalker { | |||
454 | /// Save a few bytes by using unsigned instead of size_t. | |||
455 | using ListIndex = unsigned; | |||
456 | ||||
457 | /// Represents a span of contiguous MemoryDefs, potentially ending in a | |||
458 | /// MemoryPhi. | |||
459 | struct DefPath { | |||
460 | MemoryLocation Loc; | |||
461 | // Note that, because we always walk in reverse, Last will always dominate | |||
462 | // First. Also note that First and Last are inclusive. | |||
463 | MemoryAccess *First; | |||
464 | MemoryAccess *Last; | |||
465 | Optional<ListIndex> Previous; | |||
466 | ||||
467 | DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last, | |||
468 | Optional<ListIndex> Previous) | |||
469 | : Loc(Loc), First(First), Last(Last), Previous(Previous) {} | |||
470 | ||||
471 | DefPath(const MemoryLocation &Loc, MemoryAccess *Init, | |||
472 | Optional<ListIndex> Previous) | |||
473 | : DefPath(Loc, Init, Init, Previous) {} | |||
474 | }; | |||
475 | ||||
476 | const MemorySSA &MSSA; | |||
477 | AliasAnalysis &AA; | |||
478 | DominatorTree &DT; | |||
479 | WalkerCache &WC; | |||
480 | UpwardsMemoryQuery *Query; | |||
481 | bool UseCache; | |||
482 | ||||
483 | // Phi optimization bookkeeping | |||
484 | SmallVector<DefPath, 32> Paths; | |||
485 | DenseSet<ConstMemoryAccessPair> VisitedPhis; | |||
486 | ||||
487 | void setUseCache(bool Use) { UseCache = Use; } | |||
488 | bool shouldIgnoreCache() const { | |||
489 | // UseCache will only be false when we're debugging, or when expensive | |||
490 | // checks are enabled. In either case, we don't care deeply about speed. | |||
491 | return LLVM_UNLIKELY(!UseCache)__builtin_expect((bool)(!UseCache), false); | |||
492 | } | |||
493 | ||||
494 | void addCacheEntry(const MemoryAccess *What, MemoryAccess *To, | |||
495 | const MemoryLocation &Loc) const { | |||
496 | // EXPENSIVE_CHECKS because most of these queries are redundant. | |||
497 | #ifdef EXPENSIVE_CHECKS | |||
498 | assert(MSSA.dominates(To, What))((MSSA.dominates(To, What)) ? static_cast<void> (0) : __assert_fail ("MSSA.dominates(To, What)", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 498, __PRETTY_FUNCTION__)); | |||
499 | #endif | |||
500 | if (shouldIgnoreCache()) | |||
501 | return; | |||
502 | WC.insert(What, To, Loc, Query->IsCall); | |||
503 | } | |||
504 | ||||
505 | MemoryAccess *lookupCache(const MemoryAccess *MA, | |||
506 | const MemoryLocation &Loc) const { | |||
507 | return shouldIgnoreCache() ? nullptr : WC.lookup(MA, Loc, Query->IsCall); | |||
508 | } | |||
509 | ||||
510 | void cacheDefPath(const DefPath &DN, MemoryAccess *Target) const { | |||
511 | if (shouldIgnoreCache()) | |||
512 | return; | |||
513 | ||||
514 | for (MemoryAccess *MA : def_chain(DN.First, DN.Last)) | |||
515 | addCacheEntry(MA, Target, DN.Loc); | |||
516 | ||||
517 | // DefPaths only express the path we walked. So, DN.Last could either be a | |||
518 | // thing we want to cache, or not. | |||
519 | if (DN.Last != Target) | |||
520 | addCacheEntry(DN.Last, Target, DN.Loc); | |||
521 | } | |||
522 | ||||
523 | /// Find the nearest def or phi that `From` can legally be optimized to. | |||
524 | const MemoryAccess *getWalkTarget(const MemoryPhi *From) const { | |||
525 | assert(From->getNumOperands() && "Phi with no operands?")((From->getNumOperands() && "Phi with no operands?" ) ? static_cast<void> (0) : __assert_fail ("From->getNumOperands() && \"Phi with no operands?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 525, __PRETTY_FUNCTION__)); | |||
526 | ||||
527 | BasicBlock *BB = From->getBlock(); | |||
528 | MemoryAccess *Result = MSSA.getLiveOnEntryDef(); | |||
529 | DomTreeNode *Node = DT.getNode(BB); | |||
530 | while ((Node = Node->getIDom())) { | |||
531 | auto *Defs = MSSA.getBlockDefs(Node->getBlock()); | |||
532 | if (Defs) | |||
533 | return &*Defs->rbegin(); | |||
534 | } | |||
535 | return Result; | |||
536 | } | |||
537 | ||||
538 | /// Result of calling walkToPhiOrClobber. | |||
539 | struct UpwardsWalkResult { | |||
540 | /// The "Result" of the walk. Either a clobber, the last thing we walked, or | |||
541 | /// both. | |||
542 | MemoryAccess *Result; | |||
543 | bool IsKnownClobber; | |||
544 | bool FromCache; | |||
545 | }; | |||
546 | ||||
547 | /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. | |||
548 | /// This will update Desc.Last as it walks. It will (optionally) also stop at | |||
549 | /// StopAt. | |||
550 | /// | |||
551 | /// This does not test for whether StopAt is a clobber | |||
552 | UpwardsWalkResult | |||
553 | walkToPhiOrClobber(DefPath &Desc, | |||
554 | const MemoryAccess *StopAt = nullptr) const { | |||
555 | assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world")((!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world" ) ? static_cast<void> (0) : __assert_fail ("!isa<MemoryUse>(Desc.Last) && \"Uses don't exist in my world\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 555, __PRETTY_FUNCTION__)); | |||
556 | ||||
557 | for (MemoryAccess *Current : def_chain(Desc.Last)) { | |||
558 | Desc.Last = Current; | |||
559 | if (Current == StopAt) | |||
560 | return {Current, false, false}; | |||
561 | ||||
562 | if (auto *MD = dyn_cast<MemoryDef>(Current)) | |||
563 | if (MSSA.isLiveOnEntryDef(MD) || | |||
564 | instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) | |||
565 | return {MD, true, false}; | |||
566 | ||||
567 | // Cache checks must be done last, because if Current is a clobber, the | |||
568 | // cache will contain the clobber for Current. | |||
569 | if (MemoryAccess *MA = lookupCache(Current, Desc.Loc)) | |||
570 | return {MA, true, true}; | |||
571 | } | |||
572 | ||||
573 | assert(isa<MemoryPhi>(Desc.Last) &&((isa<MemoryPhi>(Desc.Last) && "Ended at a non-clobber that's not a phi?" ) ? static_cast<void> (0) : __assert_fail ("isa<MemoryPhi>(Desc.Last) && \"Ended at a non-clobber that's not a phi?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 574, __PRETTY_FUNCTION__)) | |||
574 | "Ended at a non-clobber that's not a phi?")((isa<MemoryPhi>(Desc.Last) && "Ended at a non-clobber that's not a phi?" ) ? static_cast<void> (0) : __assert_fail ("isa<MemoryPhi>(Desc.Last) && \"Ended at a non-clobber that's not a phi?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 574, __PRETTY_FUNCTION__)); | |||
575 | return {Desc.Last, false, false}; | |||
576 | } | |||
577 | ||||
578 | void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches, | |||
579 | ListIndex PriorNode) { | |||
580 | auto UpwardDefs = make_range(upward_defs_begin({Phi, Paths[PriorNode].Loc}), | |||
581 | upward_defs_end()); | |||
582 | for (const MemoryAccessPair &P : UpwardDefs) { | |||
583 | PausedSearches.push_back(Paths.size()); | |||
584 | Paths.emplace_back(P.second, P.first, PriorNode); | |||
585 | } | |||
586 | } | |||
587 | ||||
588 | /// Represents a search that terminated after finding a clobber. This clobber | |||
589 | /// may or may not be present in the path of defs from LastNode..SearchStart, | |||
590 | /// since it may have been retrieved from cache. | |||
591 | struct TerminatedPath { | |||
592 | MemoryAccess *Clobber; | |||
593 | ListIndex LastNode; | |||
594 | }; | |||
595 | ||||
596 | /// Get an access that keeps us from optimizing to the given phi. | |||
597 | /// | |||
598 | /// PausedSearches is an array of indices into the Paths array. Its incoming | |||
599 | /// value is the indices of searches that stopped at the last phi optimization | |||
600 | /// target. It's left in an unspecified state. | |||
601 | /// | |||
602 | /// If this returns None, NewPaused is a vector of searches that terminated | |||
603 | /// at StopWhere. Otherwise, NewPaused is left in an unspecified state. | |||
604 | Optional<TerminatedPath> | |||
605 | getBlockingAccess(const MemoryAccess *StopWhere, | |||
606 | SmallVectorImpl<ListIndex> &PausedSearches, | |||
607 | SmallVectorImpl<ListIndex> &NewPaused, | |||
608 | SmallVectorImpl<TerminatedPath> &Terminated) { | |||
609 | assert(!PausedSearches.empty() && "No searches to continue?")((!PausedSearches.empty() && "No searches to continue?" ) ? static_cast<void> (0) : __assert_fail ("!PausedSearches.empty() && \"No searches to continue?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 609, __PRETTY_FUNCTION__)); | |||
610 | ||||
611 | // BFS vs DFS really doesn't make a difference here, so just do a DFS with | |||
612 | // PausedSearches as our stack. | |||
613 | while (!PausedSearches.empty()) { | |||
614 | ListIndex PathIndex = PausedSearches.pop_back_val(); | |||
615 | DefPath &Node = Paths[PathIndex]; | |||
616 | ||||
617 | // If we've already visited this path with this MemoryLocation, we don't | |||
618 | // need to do so again. | |||
619 | // | |||
620 | // NOTE: That we just drop these paths on the ground makes caching | |||
621 | // behavior sporadic. e.g. given a diamond: | |||
622 | // A | |||
623 | // B C | |||
624 | // D | |||
625 | // | |||
626 | // ...If we walk D, B, A, C, we'll only cache the result of phi | |||
627 | // optimization for A, B, and D; C will be skipped because it dies here. | |||
628 | // This arguably isn't the worst thing ever, since: | |||
629 | // - We generally query things in a top-down order, so if we got below D | |||
630 | // without needing cache entries for {C, MemLoc}, then chances are | |||
631 | // that those cache entries would end up ultimately unused. | |||
632 | // - We still cache things for A, so C only needs to walk up a bit. | |||
633 | // If this behavior becomes problematic, we can fix without a ton of extra | |||
634 | // work. | |||
635 | if (!VisitedPhis.insert({Node.Last, Node.Loc}).second) | |||
636 | continue; | |||
637 | ||||
638 | UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere); | |||
639 | if (Res.IsKnownClobber) { | |||
640 | assert(Res.Result != StopWhere || Res.FromCache)((Res.Result != StopWhere || Res.FromCache) ? static_cast< void> (0) : __assert_fail ("Res.Result != StopWhere || Res.FromCache" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 640, __PRETTY_FUNCTION__)); | |||
641 | // If this wasn't a cache hit, we hit a clobber when walking. That's a | |||
642 | // failure. | |||
643 | TerminatedPath Term{Res.Result, PathIndex}; | |||
644 | if (!Res.FromCache || !MSSA.dominates(Res.Result, StopWhere)) | |||
645 | return Term; | |||
646 | ||||
647 | // Otherwise, it's a valid thing to potentially optimize to. | |||
648 | Terminated.push_back(Term); | |||
649 | continue; | |||
650 | } | |||
651 | ||||
652 | if (Res.Result == StopWhere) { | |||
653 | // We've hit our target. Save this path off for if we want to continue | |||
654 | // walking. | |||
655 | NewPaused.push_back(PathIndex); | |||
656 | continue; | |||
657 | } | |||
658 | ||||
659 | assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber")((!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber" ) ? static_cast<void> (0) : __assert_fail ("!MSSA.isLiveOnEntryDef(Res.Result) && \"liveOnEntry is a clobber\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 659, __PRETTY_FUNCTION__)); | |||
660 | addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex); | |||
661 | } | |||
662 | ||||
663 | return None; | |||
664 | } | |||
665 | ||||
666 | template <typename T, typename Walker> | |||
667 | struct generic_def_path_iterator | |||
668 | : public iterator_facade_base<generic_def_path_iterator<T, Walker>, | |||
669 | std::forward_iterator_tag, T *> { | |||
670 | generic_def_path_iterator() : W(nullptr), N(None) {} | |||
671 | generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {} | |||
672 | ||||
673 | T &operator*() const { return curNode(); } | |||
674 | ||||
675 | generic_def_path_iterator &operator++() { | |||
676 | N = curNode().Previous; | |||
677 | return *this; | |||
678 | } | |||
679 | ||||
680 | bool operator==(const generic_def_path_iterator &O) const { | |||
681 | if (N.hasValue() != O.N.hasValue()) | |||
682 | return false; | |||
683 | return !N.hasValue() || *N == *O.N; | |||
684 | } | |||
685 | ||||
686 | private: | |||
687 | T &curNode() const { return W->Paths[*N]; } | |||
688 | ||||
689 | Walker *W; | |||
690 | Optional<ListIndex> N; | |||
691 | }; | |||
692 | ||||
693 | using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>; | |||
694 | using const_def_path_iterator = | |||
695 | generic_def_path_iterator<const DefPath, const ClobberWalker>; | |||
696 | ||||
697 | iterator_range<def_path_iterator> def_path(ListIndex From) { | |||
698 | return make_range(def_path_iterator(this, From), def_path_iterator()); | |||
699 | } | |||
700 | ||||
701 | iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const { | |||
702 | return make_range(const_def_path_iterator(this, From), | |||
703 | const_def_path_iterator()); | |||
704 | } | |||
705 | ||||
706 | struct OptznResult { | |||
707 | /// The path that contains our result. | |||
708 | TerminatedPath PrimaryClobber; | |||
709 | /// The paths that we can legally cache back from, but that aren't | |||
710 | /// necessarily the result of the Phi optimization. | |||
711 | SmallVector<TerminatedPath, 4> OtherClobbers; | |||
712 | }; | |||
713 | ||||
714 | ListIndex defPathIndex(const DefPath &N) const { | |||
715 | // The assert looks nicer if we don't need to do &N | |||
716 | const DefPath *NP = &N; | |||
717 | assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&((!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() && "Out of bounds DefPath!" ) ? static_cast<void> (0) : __assert_fail ("!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() && \"Out of bounds DefPath!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 718, __PRETTY_FUNCTION__)) | |||
718 | "Out of bounds DefPath!")((!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() && "Out of bounds DefPath!" ) ? static_cast<void> (0) : __assert_fail ("!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() && \"Out of bounds DefPath!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 718, __PRETTY_FUNCTION__)); | |||
719 | return NP - &Paths.front(); | |||
720 | } | |||
721 | ||||
722 | /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths | |||
723 | /// that act as legal clobbers. Note that this won't return *all* clobbers. | |||
724 | /// | |||
725 | /// Phi optimization algorithm tl;dr: | |||
726 | /// - Find the earliest def/phi, A, we can optimize to | |||
727 | /// - Find if all paths from the starting memory access ultimately reach A | |||
728 | /// - If not, optimization isn't possible. | |||
729 | /// - Otherwise, walk from A to another clobber or phi, A'. | |||
730 | /// - If A' is a def, we're done. | |||
731 | /// - If A' is a phi, try to optimize it. | |||
732 | /// | |||
733 | /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path | |||
734 | /// terminates when a MemoryAccess that clobbers said MemoryLocation is found. | |||
735 | OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start, | |||
736 | const MemoryLocation &Loc) { | |||
737 | assert(Paths.empty() && VisitedPhis.empty() &&((Paths.empty() && VisitedPhis.empty() && "Reset the optimization state." ) ? static_cast<void> (0) : __assert_fail ("Paths.empty() && VisitedPhis.empty() && \"Reset the optimization state.\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 738, __PRETTY_FUNCTION__)) | |||
738 | "Reset the optimization state.")((Paths.empty() && VisitedPhis.empty() && "Reset the optimization state." ) ? static_cast<void> (0) : __assert_fail ("Paths.empty() && VisitedPhis.empty() && \"Reset the optimization state.\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 738, __PRETTY_FUNCTION__)); | |||
739 | ||||
740 | Paths.emplace_back(Loc, Start, Phi, None); | |||
741 | // Stores how many "valid" optimization nodes we had prior to calling | |||
742 | // addSearches/getBlockingAccess. Necessary for caching if we had a blocker. | |||
743 | auto PriorPathsSize = Paths.size(); | |||
744 | ||||
745 | SmallVector<ListIndex, 16> PausedSearches; | |||
746 | SmallVector<ListIndex, 8> NewPaused; | |||
747 | SmallVector<TerminatedPath, 4> TerminatedPaths; | |||
748 | ||||
749 | addSearches(Phi, PausedSearches, 0); | |||
750 | ||||
751 | // Moves the TerminatedPath with the "most dominated" Clobber to the end of | |||
752 | // Paths. | |||
753 | auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) { | |||
754 | assert(!Paths.empty() && "Need a path to move")((!Paths.empty() && "Need a path to move") ? static_cast <void> (0) : __assert_fail ("!Paths.empty() && \"Need a path to move\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 754, __PRETTY_FUNCTION__)); | |||
755 | auto Dom = Paths.begin(); | |||
756 | for (auto I = std::next(Dom), E = Paths.end(); I != E; ++I) | |||
757 | if (!MSSA.dominates(I->Clobber, Dom->Clobber)) | |||
758 | Dom = I; | |||
759 | auto Last = Paths.end() - 1; | |||
760 | if (Last != Dom) | |||
761 | std::iter_swap(Last, Dom); | |||
762 | }; | |||
763 | ||||
764 | MemoryPhi *Current = Phi; | |||
765 | while (1) { | |||
| ||||
766 | assert(!MSSA.isLiveOnEntryDef(Current) &&((!MSSA.isLiveOnEntryDef(Current) && "liveOnEntry wasn't treated as a clobber?" ) ? static_cast<void> (0) : __assert_fail ("!MSSA.isLiveOnEntryDef(Current) && \"liveOnEntry wasn't treated as a clobber?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 767, __PRETTY_FUNCTION__)) | |||
767 | "liveOnEntry wasn't treated as a clobber?")((!MSSA.isLiveOnEntryDef(Current) && "liveOnEntry wasn't treated as a clobber?" ) ? static_cast<void> (0) : __assert_fail ("!MSSA.isLiveOnEntryDef(Current) && \"liveOnEntry wasn't treated as a clobber?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 767, __PRETTY_FUNCTION__)); | |||
768 | ||||
769 | const auto *Target = getWalkTarget(Current); | |||
770 | // If a TerminatedPath doesn't dominate Target, then it wasn't a legal | |||
771 | // optimization for the prior phi. | |||
772 | assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {((all_of(TerminatedPaths, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, Target); })) ? static_cast <void> (0) : __assert_fail ("all_of(TerminatedPaths, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, Target); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 774, __PRETTY_FUNCTION__)) | |||
773 | return MSSA.dominates(P.Clobber, Target);((all_of(TerminatedPaths, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, Target); })) ? static_cast <void> (0) : __assert_fail ("all_of(TerminatedPaths, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, Target); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 774, __PRETTY_FUNCTION__)) | |||
774 | }))((all_of(TerminatedPaths, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, Target); })) ? static_cast <void> (0) : __assert_fail ("all_of(TerminatedPaths, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, Target); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 774, __PRETTY_FUNCTION__)); | |||
775 | ||||
776 | // FIXME: This is broken, because the Blocker may be reported to be | |||
777 | // liveOnEntry, and we'll happily wait for that to disappear (read: never) | |||
778 | // For the moment, this is fine, since we do nothing with blocker info. | |||
779 | if (Optional<TerminatedPath> Blocker = getBlockingAccess( | |||
780 | Target, PausedSearches, NewPaused, TerminatedPaths)) { | |||
781 | // Cache our work on the blocking node, since we know that's correct. | |||
782 | cacheDefPath(Paths[Blocker->LastNode], Blocker->Clobber); | |||
783 | ||||
784 | // Find the node we started at. We can't search based on N->Last, since | |||
785 | // we may have gone around a loop with a different MemoryLocation. | |||
786 | auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) { | |||
787 | return defPathIndex(N) < PriorPathsSize; | |||
788 | }); | |||
789 | assert(Iter != def_path_iterator())((Iter != def_path_iterator()) ? static_cast<void> (0) : __assert_fail ("Iter != def_path_iterator()", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 789, __PRETTY_FUNCTION__)); | |||
790 | ||||
791 | DefPath &CurNode = *Iter; | |||
792 | assert(CurNode.Last == Current)((CurNode.Last == Current) ? static_cast<void> (0) : __assert_fail ("CurNode.Last == Current", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 792, __PRETTY_FUNCTION__)); | |||
793 | ||||
794 | // Two things: | |||
795 | // A. We can't reliably cache all of NewPaused back. Consider a case | |||
796 | // where we have two paths in NewPaused; one of which can't optimize | |||
797 | // above this phi, whereas the other can. If we cache the second path | |||
798 | // back, we'll end up with suboptimal cache entries. We can handle | |||
799 | // cases like this a bit better when we either try to find all | |||
800 | // clobbers that block phi optimization, or when our cache starts | |||
801 | // supporting unfinished searches. | |||
802 | // B. We can't reliably cache TerminatedPaths back here without doing | |||
803 | // extra checks; consider a case like: | |||
804 | // T | |||
805 | // / \ | |||
806 | // D C | |||
807 | // \ / | |||
808 | // S | |||
809 | // Where T is our target, C is a node with a clobber on it, D is a | |||
810 | // diamond (with a clobber *only* on the left or right node, N), and | |||
811 | // S is our start. Say we walk to D, through the node opposite N | |||
812 | // (read: ignoring the clobber), and see a cache entry in the top | |||
813 | // node of D. That cache entry gets put into TerminatedPaths. We then | |||
814 | // walk up to C (N is later in our worklist), find the clobber, and | |||
815 | // quit. If we append TerminatedPaths to OtherClobbers, we'll cache | |||
816 | // the bottom part of D to the cached clobber, ignoring the clobber | |||
817 | // in N. Again, this problem goes away if we start tracking all | |||
818 | // blockers for a given phi optimization. | |||
819 | TerminatedPath Result{CurNode.Last, defPathIndex(CurNode)}; | |||
820 | return {Result, {}}; | |||
821 | } | |||
822 | ||||
823 | // If there's nothing left to search, then all paths led to valid clobbers | |||
824 | // that we got from our cache; pick the nearest to the start, and allow | |||
825 | // the rest to be cached back. | |||
826 | if (NewPaused.empty()) { | |||
827 | MoveDominatedPathToEnd(TerminatedPaths); | |||
828 | TerminatedPath Result = TerminatedPaths.pop_back_val(); | |||
829 | return {Result, std::move(TerminatedPaths)}; | |||
830 | } | |||
831 | ||||
832 | MemoryAccess *DefChainEnd = nullptr; | |||
833 | SmallVector<TerminatedPath, 4> Clobbers; | |||
834 | for (ListIndex Paused : NewPaused) { | |||
835 | UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]); | |||
836 | if (WR.IsKnownClobber) | |||
837 | Clobbers.push_back({WR.Result, Paused}); | |||
838 | else | |||
839 | // Micro-opt: If we hit the end of the chain, save it. | |||
840 | DefChainEnd = WR.Result; | |||
841 | } | |||
842 | ||||
843 | if (!TerminatedPaths.empty()) { | |||
844 | // If we couldn't find the dominating phi/liveOnEntry in the above loop, | |||
845 | // do it now. | |||
846 | if (!DefChainEnd) | |||
847 | for (auto *MA : def_chain(const_cast<MemoryAccess *>(Target))) | |||
848 | DefChainEnd = MA; | |||
849 | ||||
850 | // If any of the terminated paths don't dominate the phi we'll try to | |||
851 | // optimize, we need to figure out what they are and quit. | |||
852 | const BasicBlock *ChainBB = DefChainEnd->getBlock(); | |||
| ||||
853 | for (const TerminatedPath &TP : TerminatedPaths) { | |||
854 | // Because we know that DefChainEnd is as "high" as we can go, we | |||
855 | // don't need local dominance checks; BB dominance is sufficient. | |||
856 | if (DT.dominates(ChainBB, TP.Clobber->getBlock())) | |||
857 | Clobbers.push_back(TP); | |||
858 | } | |||
859 | } | |||
860 | ||||
861 | // If we have clobbers in the def chain, find the one closest to Current | |||
862 | // and quit. | |||
863 | if (!Clobbers.empty()) { | |||
864 | MoveDominatedPathToEnd(Clobbers); | |||
865 | TerminatedPath Result = Clobbers.pop_back_val(); | |||
866 | return {Result, std::move(Clobbers)}; | |||
867 | } | |||
868 | ||||
869 | assert(all_of(NewPaused,((all_of(NewPaused, [&](ListIndex I) { return Paths[I].Last == DefChainEnd; })) ? static_cast<void> (0) : __assert_fail ("all_of(NewPaused, [&](ListIndex I) { return Paths[I].Last == DefChainEnd; })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 870, __PRETTY_FUNCTION__)) | |||
870 | [&](ListIndex I) { return Paths[I].Last == DefChainEnd; }))((all_of(NewPaused, [&](ListIndex I) { return Paths[I].Last == DefChainEnd; })) ? static_cast<void> (0) : __assert_fail ("all_of(NewPaused, [&](ListIndex I) { return Paths[I].Last == DefChainEnd; })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 870, __PRETTY_FUNCTION__)); | |||
871 | ||||
872 | // Because liveOnEntry is a clobber, this must be a phi. | |||
873 | auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd); | |||
874 | ||||
875 | PriorPathsSize = Paths.size(); | |||
876 | PausedSearches.clear(); | |||
877 | for (ListIndex I : NewPaused) | |||
878 | addSearches(DefChainPhi, PausedSearches, I); | |||
879 | NewPaused.clear(); | |||
880 | ||||
881 | Current = DefChainPhi; | |||
882 | } | |||
883 | } | |||
884 | ||||
885 | /// Caches everything in an OptznResult. | |||
886 | void cacheOptResult(const OptznResult &R) { | |||
887 | if (R.OtherClobbers.empty()) { | |||
888 | // If we're not going to be caching OtherClobbers, don't bother with | |||
889 | // marking visited/etc. | |||
890 | for (const DefPath &N : const_def_path(R.PrimaryClobber.LastNode)) | |||
891 | cacheDefPath(N, R.PrimaryClobber.Clobber); | |||
892 | return; | |||
893 | } | |||
894 | ||||
895 | // PrimaryClobber is our answer. If we can cache anything back, we need to | |||
896 | // stop caching when we visit PrimaryClobber. | |||
897 | SmallBitVector Visited(Paths.size()); | |||
898 | for (const DefPath &N : const_def_path(R.PrimaryClobber.LastNode)) { | |||
899 | Visited[defPathIndex(N)] = true; | |||
900 | cacheDefPath(N, R.PrimaryClobber.Clobber); | |||
901 | } | |||
902 | ||||
903 | for (const TerminatedPath &P : R.OtherClobbers) { | |||
904 | for (const DefPath &N : const_def_path(P.LastNode)) { | |||
905 | ListIndex NIndex = defPathIndex(N); | |||
906 | if (Visited[NIndex]) | |||
907 | break; | |||
908 | Visited[NIndex] = true; | |||
909 | cacheDefPath(N, P.Clobber); | |||
910 | } | |||
911 | } | |||
912 | } | |||
913 | ||||
914 | void verifyOptResult(const OptznResult &R) const { | |||
915 | assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {((all_of(R.OtherClobbers, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber ); })) ? static_cast<void> (0) : __assert_fail ("all_of(R.OtherClobbers, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 917, __PRETTY_FUNCTION__)) | |||
916 | return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);((all_of(R.OtherClobbers, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber ); })) ? static_cast<void> (0) : __assert_fail ("all_of(R.OtherClobbers, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 917, __PRETTY_FUNCTION__)) | |||
917 | }))((all_of(R.OtherClobbers, [&](const TerminatedPath &P ) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber ); })) ? static_cast<void> (0) : __assert_fail ("all_of(R.OtherClobbers, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber); })" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 917, __PRETTY_FUNCTION__)); | |||
918 | } | |||
919 | ||||
920 | void resetPhiOptznState() { | |||
921 | Paths.clear(); | |||
922 | VisitedPhis.clear(); | |||
923 | } | |||
924 | ||||
925 | public: | |||
926 | ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT, | |||
927 | WalkerCache &WC) | |||
928 | : MSSA(MSSA), AA(AA), DT(DT), WC(WC), UseCache(true) {} | |||
929 | ||||
930 | void reset() {} | |||
931 | ||||
932 | /// Finds the nearest clobber for the given query, optimizing phis if | |||
933 | /// possible. | |||
934 | MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q, | |||
935 | bool UseWalkerCache = true) { | |||
936 | setUseCache(UseWalkerCache); | |||
937 | Query = &Q; | |||
938 | ||||
939 | MemoryAccess *Current = Start; | |||
940 | // This walker pretends uses don't exist. If we're handed one, silently grab | |||
941 | // its def. (This has the nice side-effect of ensuring we never cache uses) | |||
942 | if (auto *MU = dyn_cast<MemoryUse>(Start)) | |||
943 | Current = MU->getDefiningAccess(); | |||
944 | ||||
945 | DefPath FirstDesc(Q.StartingLoc, Current, Current, None); | |||
946 | // Fast path for the overly-common case (no crazy phi optimization | |||
947 | // necessary) | |||
948 | UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc); | |||
949 | MemoryAccess *Result; | |||
950 | if (WalkResult.IsKnownClobber) { | |||
951 | cacheDefPath(FirstDesc, WalkResult.Result); | |||
952 | Result = WalkResult.Result; | |||
953 | } else { | |||
954 | OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last), | |||
955 | Current, Q.StartingLoc); | |||
956 | verifyOptResult(OptRes); | |||
957 | cacheOptResult(OptRes); | |||
958 | resetPhiOptznState(); | |||
959 | Result = OptRes.PrimaryClobber.Clobber; | |||
960 | } | |||
961 | ||||
962 | #ifdef EXPENSIVE_CHECKS | |||
963 | checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA); | |||
964 | #endif | |||
965 | return Result; | |||
966 | } | |||
967 | ||||
968 | void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA)((MSSA == &this->MSSA) ? static_cast<void> (0) : __assert_fail ("MSSA == &this->MSSA", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 968, __PRETTY_FUNCTION__)); } | |||
969 | }; | |||
970 | ||||
971 | struct RenamePassData { | |||
972 | DomTreeNode *DTN; | |||
973 | DomTreeNode::const_iterator ChildIt; | |||
974 | MemoryAccess *IncomingVal; | |||
975 | ||||
976 | RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It, | |||
977 | MemoryAccess *M) | |||
978 | : DTN(D), ChildIt(It), IncomingVal(M) {} | |||
979 | void swap(RenamePassData &RHS) { | |||
980 | std::swap(DTN, RHS.DTN); | |||
981 | std::swap(ChildIt, RHS.ChildIt); | |||
982 | std::swap(IncomingVal, RHS.IncomingVal); | |||
983 | } | |||
984 | }; | |||
985 | } // anonymous namespace | |||
986 | ||||
987 | namespace llvm { | |||
988 | /// \brief A MemorySSAWalker that does AA walks and caching of lookups to | |||
989 | /// disambiguate accesses. | |||
990 | /// | |||
991 | /// FIXME: The current implementation of this can take quadratic space in rare | |||
992 | /// cases. This can be fixed, but it is something to note until it is fixed. | |||
993 | /// | |||
994 | /// In order to trigger this behavior, you need to store to N distinct locations | |||
995 | /// (that AA can prove don't alias), perform M stores to other memory | |||
996 | /// locations that AA can prove don't alias any of the initial N locations, and | |||
997 | /// then load from all of the N locations. In this case, we insert M cache | |||
998 | /// entries for each of the N loads. | |||
999 | /// | |||
1000 | /// For example: | |||
1001 | /// define i32 @foo() { | |||
1002 | /// %a = alloca i32, align 4 | |||
1003 | /// %b = alloca i32, align 4 | |||
1004 | /// store i32 0, i32* %a, align 4 | |||
1005 | /// store i32 0, i32* %b, align 4 | |||
1006 | /// | |||
1007 | /// ; Insert M stores to other memory that doesn't alias %a or %b here | |||
1008 | /// | |||
1009 | /// %c = load i32, i32* %a, align 4 ; Caches M entries in | |||
1010 | /// ; CachedUpwardsClobberingAccess for the | |||
1011 | /// ; MemoryLocation %a | |||
1012 | /// %d = load i32, i32* %b, align 4 ; Caches M entries in | |||
1013 | /// ; CachedUpwardsClobberingAccess for the | |||
1014 | /// ; MemoryLocation %b | |||
1015 | /// | |||
1016 | /// ; For completeness' sake, loading %a or %b again would not cache *another* | |||
1017 | /// ; M entries. | |||
1018 | /// %r = add i32 %c, %d | |||
1019 | /// ret i32 %r | |||
1020 | /// } | |||
1021 | class MemorySSA::CachingWalker final : public MemorySSAWalker { | |||
1022 | WalkerCache Cache; | |||
1023 | ClobberWalker Walker; | |||
1024 | bool AutoResetWalker; | |||
1025 | ||||
1026 | MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &); | |||
1027 | void verifyRemoved(MemoryAccess *); | |||
1028 | ||||
1029 | public: | |||
1030 | CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *); | |||
1031 | ~CachingWalker() override; | |||
1032 | ||||
1033 | using MemorySSAWalker::getClobberingMemoryAccess; | |||
1034 | MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override; | |||
1035 | MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, | |||
1036 | const MemoryLocation &) override; | |||
1037 | void invalidateInfo(MemoryAccess *) override; | |||
1038 | ||||
1039 | /// Whether we call resetClobberWalker() after each time we *actually* walk to | |||
1040 | /// answer a clobber query. | |||
1041 | void setAutoResetWalker(bool AutoReset) { AutoResetWalker = AutoReset; } | |||
1042 | ||||
1043 | /// Drop the walker's persistent data structures. | |||
1044 | void resetClobberWalker() { Walker.reset(); } | |||
1045 | ||||
1046 | void verify(const MemorySSA *MSSA) override { | |||
1047 | MemorySSAWalker::verify(MSSA); | |||
1048 | Walker.verify(MSSA); | |||
1049 | } | |||
1050 | }; | |||
1051 | ||||
1052 | void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal, | |||
1053 | bool RenameAllUses) { | |||
1054 | // Pass through values to our successors | |||
1055 | for (const BasicBlock *S : successors(BB)) { | |||
1056 | auto It = PerBlockAccesses.find(S); | |||
1057 | // Rename the phi nodes in our successor block | |||
1058 | if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front())) | |||
1059 | continue; | |||
1060 | AccessList *Accesses = It->second.get(); | |||
1061 | auto *Phi = cast<MemoryPhi>(&Accesses->front()); | |||
1062 | if (RenameAllUses) { | |||
1063 | int PhiIndex = Phi->getBasicBlockIndex(BB); | |||
1064 | assert(PhiIndex != -1 && "Incomplete phi during partial rename")((PhiIndex != -1 && "Incomplete phi during partial rename" ) ? static_cast<void> (0) : __assert_fail ("PhiIndex != -1 && \"Incomplete phi during partial rename\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1064, __PRETTY_FUNCTION__)); | |||
1065 | Phi->setIncomingValue(PhiIndex, IncomingVal); | |||
1066 | } else | |||
1067 | Phi->addIncoming(IncomingVal, BB); | |||
1068 | } | |||
1069 | } | |||
1070 | ||||
1071 | /// \brief Rename a single basic block into MemorySSA form. | |||
1072 | /// Uses the standard SSA renaming algorithm. | |||
1073 | /// \returns The new incoming value. | |||
1074 | MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal, | |||
1075 | bool RenameAllUses) { | |||
1076 | auto It = PerBlockAccesses.find(BB); | |||
1077 | // Skip most processing if the list is empty. | |||
1078 | if (It != PerBlockAccesses.end()) { | |||
1079 | AccessList *Accesses = It->second.get(); | |||
1080 | for (MemoryAccess &L : *Accesses) { | |||
1081 | if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&L)) { | |||
1082 | if (MUD->getDefiningAccess() == nullptr || RenameAllUses) | |||
1083 | MUD->setDefiningAccess(IncomingVal); | |||
1084 | if (isa<MemoryDef>(&L)) | |||
1085 | IncomingVal = &L; | |||
1086 | } else { | |||
1087 | IncomingVal = &L; | |||
1088 | } | |||
1089 | } | |||
1090 | } | |||
1091 | return IncomingVal; | |||
1092 | } | |||
1093 | ||||
1094 | /// \brief This is the standard SSA renaming algorithm. | |||
1095 | /// | |||
1096 | /// We walk the dominator tree in preorder, renaming accesses, and then filling | |||
1097 | /// in phi nodes in our successors. | |||
1098 | void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal, | |||
1099 | SmallPtrSetImpl<BasicBlock *> &Visited, | |||
1100 | bool SkipVisited, bool RenameAllUses) { | |||
1101 | SmallVector<RenamePassData, 32> WorkStack; | |||
1102 | // Skip everything if we already renamed this block and we are skipping. | |||
1103 | // Note: You can't sink this into the if, because we need it to occur | |||
1104 | // regardless of whether we skip blocks or not. | |||
1105 | bool AlreadyVisited = !Visited.insert(Root->getBlock()).second; | |||
1106 | if (SkipVisited && AlreadyVisited) | |||
1107 | return; | |||
1108 | ||||
1109 | IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses); | |||
1110 | renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses); | |||
1111 | WorkStack.push_back({Root, Root->begin(), IncomingVal}); | |||
1112 | ||||
1113 | while (!WorkStack.empty()) { | |||
1114 | DomTreeNode *Node = WorkStack.back().DTN; | |||
1115 | DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt; | |||
1116 | IncomingVal = WorkStack.back().IncomingVal; | |||
1117 | ||||
1118 | if (ChildIt == Node->end()) { | |||
1119 | WorkStack.pop_back(); | |||
1120 | } else { | |||
1121 | DomTreeNode *Child = *ChildIt; | |||
1122 | ++WorkStack.back().ChildIt; | |||
1123 | BasicBlock *BB = Child->getBlock(); | |||
1124 | // Note: You can't sink this into the if, because we need it to occur | |||
1125 | // regardless of whether we skip blocks or not. | |||
1126 | AlreadyVisited = !Visited.insert(BB).second; | |||
1127 | if (SkipVisited && AlreadyVisited) { | |||
1128 | // We already visited this during our renaming, which can happen when | |||
1129 | // being asked to rename multiple blocks. Figure out the incoming val, | |||
1130 | // which is the last def. | |||
1131 | // Incoming value can only change if there is a block def, and in that | |||
1132 | // case, it's the last block def in the list. | |||
1133 | if (auto *BlockDefs = getWritableBlockDefs(BB)) | |||
1134 | IncomingVal = &*BlockDefs->rbegin(); | |||
1135 | } else | |||
1136 | IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses); | |||
1137 | renameSuccessorPhis(BB, IncomingVal, RenameAllUses); | |||
1138 | WorkStack.push_back({Child, Child->begin(), IncomingVal}); | |||
1139 | } | |||
1140 | } | |||
1141 | } | |||
1142 | ||||
1143 | /// \brief Compute dominator levels, used by the phi insertion algorithm above. | |||
1144 | void MemorySSA::computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels) { | |||
1145 | for (auto DFI = df_begin(DT->getRootNode()), DFE = df_end(DT->getRootNode()); | |||
1146 | DFI != DFE; ++DFI) | |||
1147 | DomLevels[*DFI] = DFI.getPathLength() - 1; | |||
1148 | } | |||
1149 | ||||
1150 | /// \brief This handles unreachable block accesses by deleting phi nodes in | |||
1151 | /// unreachable blocks, and marking all other unreachable MemoryAccess's as | |||
1152 | /// being uses of the live on entry definition. | |||
1153 | void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) { | |||
1154 | assert(!DT->isReachableFromEntry(BB) &&((!DT->isReachableFromEntry(BB) && "Reachable block found while handling unreachable blocks" ) ? static_cast<void> (0) : __assert_fail ("!DT->isReachableFromEntry(BB) && \"Reachable block found while handling unreachable blocks\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1155, __PRETTY_FUNCTION__)) | |||
1155 | "Reachable block found while handling unreachable blocks")((!DT->isReachableFromEntry(BB) && "Reachable block found while handling unreachable blocks" ) ? static_cast<void> (0) : __assert_fail ("!DT->isReachableFromEntry(BB) && \"Reachable block found while handling unreachable blocks\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1155, __PRETTY_FUNCTION__)); | |||
1156 | ||||
1157 | // Make sure phi nodes in our reachable successors end up with a | |||
1158 | // LiveOnEntryDef for our incoming edge, even though our block is forward | |||
1159 | // unreachable. We could just disconnect these blocks from the CFG fully, | |||
1160 | // but we do not right now. | |||
1161 | for (const BasicBlock *S : successors(BB)) { | |||
1162 | if (!DT->isReachableFromEntry(S)) | |||
1163 | continue; | |||
1164 | auto It = PerBlockAccesses.find(S); | |||
1165 | // Rename the phi nodes in our successor block | |||
1166 | if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front())) | |||
1167 | continue; | |||
1168 | AccessList *Accesses = It->second.get(); | |||
1169 | auto *Phi = cast<MemoryPhi>(&Accesses->front()); | |||
1170 | Phi->addIncoming(LiveOnEntryDef.get(), BB); | |||
1171 | } | |||
1172 | ||||
1173 | auto It = PerBlockAccesses.find(BB); | |||
1174 | if (It == PerBlockAccesses.end()) | |||
1175 | return; | |||
1176 | ||||
1177 | auto &Accesses = It->second; | |||
1178 | for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) { | |||
1179 | auto Next = std::next(AI); | |||
1180 | // If we have a phi, just remove it. We are going to replace all | |||
1181 | // users with live on entry. | |||
1182 | if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI)) | |||
1183 | UseOrDef->setDefiningAccess(LiveOnEntryDef.get()); | |||
1184 | else | |||
1185 | Accesses->erase(AI); | |||
1186 | AI = Next; | |||
1187 | } | |||
1188 | } | |||
1189 | ||||
1190 | MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT) | |||
1191 | : AA(AA), DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr), | |||
1192 | NextID(INVALID_MEMORYACCESS_ID) { | |||
1193 | buildMemorySSA(); | |||
1194 | } | |||
1195 | ||||
1196 | MemorySSA::~MemorySSA() { | |||
1197 | // Drop all our references | |||
1198 | for (const auto &Pair : PerBlockAccesses) | |||
1199 | for (MemoryAccess &MA : *Pair.second) | |||
1200 | MA.dropAllReferences(); | |||
1201 | } | |||
1202 | ||||
1203 | MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) { | |||
1204 | auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr)); | |||
1205 | ||||
1206 | if (Res.second) | |||
1207 | Res.first->second = make_unique<AccessList>(); | |||
1208 | return Res.first->second.get(); | |||
1209 | } | |||
1210 | MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) { | |||
1211 | auto Res = PerBlockDefs.insert(std::make_pair(BB, nullptr)); | |||
1212 | ||||
1213 | if (Res.second) | |||
1214 | Res.first->second = make_unique<DefsList>(); | |||
1215 | return Res.first->second.get(); | |||
1216 | } | |||
1217 | ||||
1218 | /// This class is a batch walker of all MemoryUse's in the program, and points | |||
1219 | /// their defining access at the thing that actually clobbers them. Because it | |||
1220 | /// is a batch walker that touches everything, it does not operate like the | |||
1221 | /// other walkers. This walker is basically performing a top-down SSA renaming | |||
1222 | /// pass, where the version stack is used as the cache. This enables it to be | |||
1223 | /// significantly more time and memory efficient than using the regular walker, | |||
1224 | /// which is walking bottom-up. | |||
1225 | class MemorySSA::OptimizeUses { | |||
1226 | public: | |||
1227 | OptimizeUses(MemorySSA *MSSA, MemorySSAWalker *Walker, AliasAnalysis *AA, | |||
1228 | DominatorTree *DT) | |||
1229 | : MSSA(MSSA), Walker(Walker), AA(AA), DT(DT) { | |||
1230 | Walker = MSSA->getWalker(); | |||
1231 | } | |||
1232 | ||||
1233 | void optimizeUses(); | |||
1234 | ||||
1235 | private: | |||
1236 | /// This represents where a given memorylocation is in the stack. | |||
1237 | struct MemlocStackInfo { | |||
1238 | // This essentially is keeping track of versions of the stack. Whenever | |||
1239 | // the stack changes due to pushes or pops, these versions increase. | |||
1240 | unsigned long StackEpoch; | |||
1241 | unsigned long PopEpoch; | |||
1242 | // This is the lower bound of places on the stack to check. It is equal to | |||
1243 | // the place the last stack walk ended. | |||
1244 | // Note: Correctness depends on this being initialized to 0, which densemap | |||
1245 | // does | |||
1246 | unsigned long LowerBound; | |||
1247 | const BasicBlock *LowerBoundBlock; | |||
1248 | // This is where the last walk for this memory location ended. | |||
1249 | unsigned long LastKill; | |||
1250 | bool LastKillValid; | |||
1251 | }; | |||
1252 | void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &, | |||
1253 | SmallVectorImpl<MemoryAccess *> &, | |||
1254 | DenseMap<MemoryLocOrCall, MemlocStackInfo> &); | |||
1255 | MemorySSA *MSSA; | |||
1256 | MemorySSAWalker *Walker; | |||
1257 | AliasAnalysis *AA; | |||
1258 | DominatorTree *DT; | |||
1259 | }; | |||
1260 | ||||
1261 | /// Optimize the uses in a given block This is basically the SSA renaming | |||
1262 | /// algorithm, with one caveat: We are able to use a single stack for all | |||
1263 | /// MemoryUses. This is because the set of *possible* reaching MemoryDefs is | |||
1264 | /// the same for every MemoryUse. The *actual* clobbering MemoryDef is just | |||
1265 | /// going to be some position in that stack of possible ones. | |||
1266 | /// | |||
1267 | /// We track the stack positions that each MemoryLocation needs | |||
1268 | /// to check, and last ended at. This is because we only want to check the | |||
1269 | /// things that changed since last time. The same MemoryLocation should | |||
1270 | /// get clobbered by the same store (getModRefInfo does not use invariantness or | |||
1271 | /// things like this, and if they start, we can modify MemoryLocOrCall to | |||
1272 | /// include relevant data) | |||
1273 | void MemorySSA::OptimizeUses::optimizeUsesInBlock( | |||
1274 | const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch, | |||
1275 | SmallVectorImpl<MemoryAccess *> &VersionStack, | |||
1276 | DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) { | |||
1277 | ||||
1278 | /// If no accesses, nothing to do. | |||
1279 | MemorySSA::AccessList *Accesses = MSSA->getWritableBlockAccesses(BB); | |||
1280 | if (Accesses == nullptr) | |||
1281 | return; | |||
1282 | ||||
1283 | // Pop everything that doesn't dominate the current block off the stack, | |||
1284 | // increment the PopEpoch to account for this. | |||
1285 | while (true) { | |||
1286 | assert(((!VersionStack.empty() && "Version stack should have liveOnEntry sentinel dominating everything" ) ? static_cast<void> (0) : __assert_fail ("!VersionStack.empty() && \"Version stack should have liveOnEntry sentinel dominating everything\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1288, __PRETTY_FUNCTION__)) | |||
1287 | !VersionStack.empty() &&((!VersionStack.empty() && "Version stack should have liveOnEntry sentinel dominating everything" ) ? static_cast<void> (0) : __assert_fail ("!VersionStack.empty() && \"Version stack should have liveOnEntry sentinel dominating everything\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1288, __PRETTY_FUNCTION__)) | |||
1288 | "Version stack should have liveOnEntry sentinel dominating everything")((!VersionStack.empty() && "Version stack should have liveOnEntry sentinel dominating everything" ) ? static_cast<void> (0) : __assert_fail ("!VersionStack.empty() && \"Version stack should have liveOnEntry sentinel dominating everything\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1288, __PRETTY_FUNCTION__)); | |||
1289 | BasicBlock *BackBlock = VersionStack.back()->getBlock(); | |||
1290 | if (DT->dominates(BackBlock, BB)) | |||
1291 | break; | |||
1292 | while (VersionStack.back()->getBlock() == BackBlock) | |||
1293 | VersionStack.pop_back(); | |||
1294 | ++PopEpoch; | |||
1295 | } | |||
1296 | ||||
1297 | for (MemoryAccess &MA : *Accesses) { | |||
1298 | auto *MU = dyn_cast<MemoryUse>(&MA); | |||
1299 | if (!MU) { | |||
1300 | VersionStack.push_back(&MA); | |||
1301 | ++StackEpoch; | |||
1302 | continue; | |||
1303 | } | |||
1304 | ||||
1305 | if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) { | |||
1306 | MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true); | |||
1307 | continue; | |||
1308 | } | |||
1309 | ||||
1310 | MemoryLocOrCall UseMLOC(MU); | |||
1311 | auto &LocInfo = LocStackInfo[UseMLOC]; | |||
1312 | // If the pop epoch changed, it means we've removed stuff from top of | |||
1313 | // stack due to changing blocks. We may have to reset the lower bound or | |||
1314 | // last kill info. | |||
1315 | if (LocInfo.PopEpoch != PopEpoch) { | |||
1316 | LocInfo.PopEpoch = PopEpoch; | |||
1317 | LocInfo.StackEpoch = StackEpoch; | |||
1318 | // If the lower bound was in something that no longer dominates us, we | |||
1319 | // have to reset it. | |||
1320 | // We can't simply track stack size, because the stack may have had | |||
1321 | // pushes/pops in the meantime. | |||
1322 | // XXX: This is non-optimal, but only is slower cases with heavily | |||
1323 | // branching dominator trees. To get the optimal number of queries would | |||
1324 | // be to make lowerbound and lastkill a per-loc stack, and pop it until | |||
1325 | // the top of that stack dominates us. This does not seem worth it ATM. | |||
1326 | // A much cheaper optimization would be to always explore the deepest | |||
1327 | // branch of the dominator tree first. This will guarantee this resets on | |||
1328 | // the smallest set of blocks. | |||
1329 | if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB && | |||
1330 | !DT->dominates(LocInfo.LowerBoundBlock, BB)) { | |||
1331 | // Reset the lower bound of things to check. | |||
1332 | // TODO: Some day we should be able to reset to last kill, rather than | |||
1333 | // 0. | |||
1334 | LocInfo.LowerBound = 0; | |||
1335 | LocInfo.LowerBoundBlock = VersionStack[0]->getBlock(); | |||
1336 | LocInfo.LastKillValid = false; | |||
1337 | } | |||
1338 | } else if (LocInfo.StackEpoch != StackEpoch) { | |||
1339 | // If all that has changed is the StackEpoch, we only have to check the | |||
1340 | // new things on the stack, because we've checked everything before. In | |||
1341 | // this case, the lower bound of things to check remains the same. | |||
1342 | LocInfo.PopEpoch = PopEpoch; | |||
1343 | LocInfo.StackEpoch = StackEpoch; | |||
1344 | } | |||
1345 | if (!LocInfo.LastKillValid) { | |||
1346 | LocInfo.LastKill = VersionStack.size() - 1; | |||
1347 | LocInfo.LastKillValid = true; | |||
1348 | } | |||
1349 | ||||
1350 | // At this point, we should have corrected last kill and LowerBound to be | |||
1351 | // in bounds. | |||
1352 | assert(LocInfo.LowerBound < VersionStack.size() &&((LocInfo.LowerBound < VersionStack.size() && "Lower bound out of range" ) ? static_cast<void> (0) : __assert_fail ("LocInfo.LowerBound < VersionStack.size() && \"Lower bound out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1353, __PRETTY_FUNCTION__)) | |||
1353 | "Lower bound out of range")((LocInfo.LowerBound < VersionStack.size() && "Lower bound out of range" ) ? static_cast<void> (0) : __assert_fail ("LocInfo.LowerBound < VersionStack.size() && \"Lower bound out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1353, __PRETTY_FUNCTION__)); | |||
1354 | assert(LocInfo.LastKill < VersionStack.size() &&((LocInfo.LastKill < VersionStack.size() && "Last kill info out of range" ) ? static_cast<void> (0) : __assert_fail ("LocInfo.LastKill < VersionStack.size() && \"Last kill info out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1355, __PRETTY_FUNCTION__)) | |||
1355 | "Last kill info out of range")((LocInfo.LastKill < VersionStack.size() && "Last kill info out of range" ) ? static_cast<void> (0) : __assert_fail ("LocInfo.LastKill < VersionStack.size() && \"Last kill info out of range\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1355, __PRETTY_FUNCTION__)); | |||
1356 | // In any case, the new upper bound is the top of the stack. | |||
1357 | unsigned long UpperBound = VersionStack.size() - 1; | |||
1358 | ||||
1359 | if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) { | |||
1360 | DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "MemorySSA skipping optimization of " << *MU << " (" << *(MU->getMemoryInst() ) << ")" << " because there are " << UpperBound - LocInfo.LowerBound << " stores to disambiguate\n"; } } while (false) | |||
1361 | << *(MU->getMemoryInst()) << ")"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "MemorySSA skipping optimization of " << *MU << " (" << *(MU->getMemoryInst() ) << ")" << " because there are " << UpperBound - LocInfo.LowerBound << " stores to disambiguate\n"; } } while (false) | |||
1362 | << " because there are " << UpperBound - LocInfo.LowerBounddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "MemorySSA skipping optimization of " << *MU << " (" << *(MU->getMemoryInst() ) << ")" << " because there are " << UpperBound - LocInfo.LowerBound << " stores to disambiguate\n"; } } while (false) | |||
1363 | << " stores to disambiguate\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "MemorySSA skipping optimization of " << *MU << " (" << *(MU->getMemoryInst() ) << ")" << " because there are " << UpperBound - LocInfo.LowerBound << " stores to disambiguate\n"; } } while (false); | |||
1364 | // Because we did not walk, LastKill is no longer valid, as this may | |||
1365 | // have been a kill. | |||
1366 | LocInfo.LastKillValid = false; | |||
1367 | continue; | |||
1368 | } | |||
1369 | bool FoundClobberResult = false; | |||
1370 | while (UpperBound > LocInfo.LowerBound) { | |||
1371 | if (isa<MemoryPhi>(VersionStack[UpperBound])) { | |||
1372 | // For phis, use the walker, see where we ended up, go there | |||
1373 | Instruction *UseInst = MU->getMemoryInst(); | |||
1374 | MemoryAccess *Result = Walker->getClobberingMemoryAccess(UseInst); | |||
1375 | // We are guaranteed to find it or something is wrong | |||
1376 | while (VersionStack[UpperBound] != Result) { | |||
1377 | assert(UpperBound != 0)((UpperBound != 0) ? static_cast<void> (0) : __assert_fail ("UpperBound != 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1377, __PRETTY_FUNCTION__)); | |||
1378 | --UpperBound; | |||
1379 | } | |||
1380 | FoundClobberResult = true; | |||
1381 | break; | |||
1382 | } | |||
1383 | ||||
1384 | MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]); | |||
1385 | // If the lifetime of the pointer ends at this instruction, it's live on | |||
1386 | // entry. | |||
1387 | if (!UseMLOC.IsCall && lifetimeEndsAt(MD, UseMLOC.getLoc(), *AA)) { | |||
1388 | // Reset UpperBound to liveOnEntryDef's place in the stack | |||
1389 | UpperBound = 0; | |||
1390 | FoundClobberResult = true; | |||
1391 | break; | |||
1392 | } | |||
1393 | if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) { | |||
1394 | FoundClobberResult = true; | |||
1395 | break; | |||
1396 | } | |||
1397 | --UpperBound; | |||
1398 | } | |||
1399 | // At the end of this loop, UpperBound is either a clobber, or lower bound | |||
1400 | // PHI walking may cause it to be < LowerBound, and in fact, < LastKill. | |||
1401 | if (FoundClobberResult || UpperBound < LocInfo.LastKill) { | |||
1402 | MU->setDefiningAccess(VersionStack[UpperBound], true); | |||
1403 | // We were last killed now by where we got to | |||
1404 | LocInfo.LastKill = UpperBound; | |||
1405 | } else { | |||
1406 | // Otherwise, we checked all the new ones, and now we know we can get to | |||
1407 | // LastKill. | |||
1408 | MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true); | |||
1409 | } | |||
1410 | LocInfo.LowerBound = VersionStack.size() - 1; | |||
1411 | LocInfo.LowerBoundBlock = BB; | |||
1412 | } | |||
1413 | } | |||
1414 | ||||
1415 | /// Optimize uses to point to their actual clobbering definitions. | |||
1416 | void MemorySSA::OptimizeUses::optimizeUses() { | |||
1417 | SmallVector<MemoryAccess *, 16> VersionStack; | |||
1418 | DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo; | |||
1419 | VersionStack.push_back(MSSA->getLiveOnEntryDef()); | |||
1420 | ||||
1421 | unsigned long StackEpoch = 1; | |||
1422 | unsigned long PopEpoch = 1; | |||
1423 | // We perform a non-recursive top-down dominator tree walk. | |||
1424 | for (const auto *DomNode : depth_first(DT->getRootNode())) | |||
1425 | optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack, | |||
1426 | LocStackInfo); | |||
1427 | } | |||
1428 | ||||
1429 | void MemorySSA::placePHINodes( | |||
1430 | const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks, | |||
1431 | const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) { | |||
1432 | // Determine where our MemoryPhi's should go | |||
1433 | ForwardIDFCalculator IDFs(*DT); | |||
1434 | IDFs.setDefiningBlocks(DefiningBlocks); | |||
1435 | SmallVector<BasicBlock *, 32> IDFBlocks; | |||
1436 | IDFs.calculate(IDFBlocks); | |||
1437 | ||||
1438 | std::sort(IDFBlocks.begin(), IDFBlocks.end(), | |||
1439 | [&BBNumbers](const BasicBlock *A, const BasicBlock *B) { | |||
1440 | return BBNumbers.lookup(A) < BBNumbers.lookup(B); | |||
1441 | }); | |||
1442 | ||||
1443 | // Now place MemoryPhi nodes. | |||
1444 | for (auto &BB : IDFBlocks) | |||
1445 | createMemoryPhi(BB); | |||
1446 | } | |||
1447 | ||||
1448 | void MemorySSA::buildMemorySSA() { | |||
1449 | // We create an access to represent "live on entry", for things like | |||
1450 | // arguments or users of globals, where the memory they use is defined before | |||
1451 | // the beginning of the function. We do not actually insert it into the IR. | |||
1452 | // We do not define a live on exit for the immediate uses, and thus our | |||
1453 | // semantics do *not* imply that something with no immediate uses can simply | |||
1454 | // be removed. | |||
1455 | BasicBlock &StartingPoint = F.getEntryBlock(); | |||
1456 | LiveOnEntryDef = make_unique<MemoryDef>(F.getContext(), nullptr, nullptr, | |||
1457 | &StartingPoint, NextID++); | |||
1458 | DenseMap<const BasicBlock *, unsigned int> BBNumbers; | |||
1459 | unsigned NextBBNum = 0; | |||
1460 | ||||
1461 | // We maintain lists of memory accesses per-block, trading memory for time. We | |||
1462 | // could just look up the memory access for every possible instruction in the | |||
1463 | // stream. | |||
1464 | SmallPtrSet<BasicBlock *, 32> DefiningBlocks; | |||
1465 | SmallPtrSet<BasicBlock *, 32> DefUseBlocks; | |||
1466 | // Go through each block, figure out where defs occur, and chain together all | |||
1467 | // the accesses. | |||
1468 | for (BasicBlock &B : F) { | |||
1469 | BBNumbers[&B] = NextBBNum++; | |||
1470 | bool InsertIntoDef = false; | |||
1471 | AccessList *Accesses = nullptr; | |||
1472 | DefsList *Defs = nullptr; | |||
1473 | for (Instruction &I : B) { | |||
1474 | MemoryUseOrDef *MUD = createNewAccess(&I); | |||
1475 | if (!MUD) | |||
1476 | continue; | |||
1477 | ||||
1478 | if (!Accesses) | |||
1479 | Accesses = getOrCreateAccessList(&B); | |||
1480 | Accesses->push_back(MUD); | |||
1481 | if (isa<MemoryDef>(MUD)) { | |||
1482 | InsertIntoDef = true; | |||
1483 | if (!Defs) | |||
1484 | Defs = getOrCreateDefsList(&B); | |||
1485 | Defs->push_back(*MUD); | |||
1486 | } | |||
1487 | } | |||
1488 | if (InsertIntoDef) | |||
1489 | DefiningBlocks.insert(&B); | |||
1490 | if (Accesses) | |||
1491 | DefUseBlocks.insert(&B); | |||
1492 | } | |||
1493 | placePHINodes(DefiningBlocks, BBNumbers); | |||
1494 | ||||
1495 | // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get | |||
1496 | // filled in with all blocks. | |||
1497 | SmallPtrSet<BasicBlock *, 16> Visited; | |||
1498 | renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited); | |||
1499 | ||||
1500 | CachingWalker *Walker = getWalkerImpl(); | |||
1501 | ||||
1502 | // We're doing a batch of updates; don't drop useful caches between them. | |||
1503 | Walker->setAutoResetWalker(false); | |||
1504 | OptimizeUses(this, Walker, AA, DT).optimizeUses(); | |||
1505 | Walker->setAutoResetWalker(true); | |||
1506 | Walker->resetClobberWalker(); | |||
1507 | ||||
1508 | // Mark the uses in unreachable blocks as live on entry, so that they go | |||
1509 | // somewhere. | |||
1510 | for (auto &BB : F) | |||
1511 | if (!Visited.count(&BB)) | |||
1512 | markUnreachableAsLiveOnEntry(&BB); | |||
1513 | } | |||
1514 | ||||
1515 | MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); } | |||
1516 | ||||
1517 | MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() { | |||
1518 | if (Walker) | |||
1519 | return Walker.get(); | |||
1520 | ||||
1521 | Walker = make_unique<CachingWalker>(this, AA, DT); | |||
1522 | return Walker.get(); | |||
1523 | } | |||
1524 | ||||
1525 | // This is a helper function used by the creation routines. It places NewAccess | |||
1526 | // into the access and defs lists for a given basic block, at the given | |||
1527 | // insertion point. | |||
1528 | void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess, | |||
1529 | const BasicBlock *BB, | |||
1530 | InsertionPlace Point) { | |||
1531 | auto *Accesses = getOrCreateAccessList(BB); | |||
1532 | if (Point == Beginning) { | |||
1533 | // If it's a phi node, it goes first, otherwise, it goes after any phi | |||
1534 | // nodes. | |||
1535 | if (isa<MemoryPhi>(NewAccess)) { | |||
1536 | Accesses->push_front(NewAccess); | |||
1537 | auto *Defs = getOrCreateDefsList(BB); | |||
1538 | Defs->push_front(*NewAccess); | |||
1539 | } else { | |||
1540 | auto AI = find_if_not( | |||
1541 | *Accesses, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); }); | |||
1542 | Accesses->insert(AI, NewAccess); | |||
1543 | if (!isa<MemoryUse>(NewAccess)) { | |||
1544 | auto *Defs = getOrCreateDefsList(BB); | |||
1545 | auto DI = find_if_not( | |||
1546 | *Defs, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); }); | |||
1547 | Defs->insert(DI, *NewAccess); | |||
1548 | } | |||
1549 | } | |||
1550 | } else { | |||
1551 | Accesses->push_back(NewAccess); | |||
1552 | if (!isa<MemoryUse>(NewAccess)) { | |||
1553 | auto *Defs = getOrCreateDefsList(BB); | |||
1554 | Defs->push_back(*NewAccess); | |||
1555 | } | |||
1556 | } | |||
1557 | BlockNumberingValid.erase(BB); | |||
1558 | } | |||
1559 | ||||
1560 | void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB, | |||
1561 | AccessList::iterator InsertPt) { | |||
1562 | auto *Accesses = getWritableBlockAccesses(BB); | |||
1563 | bool WasEnd = InsertPt == Accesses->end(); | |||
1564 | Accesses->insert(AccessList::iterator(InsertPt), What); | |||
1565 | if (!isa<MemoryUse>(What)) { | |||
1566 | auto *Defs = getOrCreateDefsList(BB); | |||
1567 | // If we got asked to insert at the end, we have an easy job, just shove it | |||
1568 | // at the end. If we got asked to insert before an existing def, we also get | |||
1569 | // an terator. If we got asked to insert before a use, we have to hunt for | |||
1570 | // the next def. | |||
1571 | if (WasEnd) { | |||
1572 | Defs->push_back(*What); | |||
1573 | } else if (isa<MemoryDef>(InsertPt)) { | |||
1574 | Defs->insert(InsertPt->getDefsIterator(), *What); | |||
1575 | } else { | |||
1576 | while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt)) | |||
1577 | ++InsertPt; | |||
1578 | // Either we found a def, or we are inserting at the end | |||
1579 | if (InsertPt == Accesses->end()) | |||
1580 | Defs->push_back(*What); | |||
1581 | else | |||
1582 | Defs->insert(InsertPt->getDefsIterator(), *What); | |||
1583 | } | |||
1584 | } | |||
1585 | BlockNumberingValid.erase(BB); | |||
1586 | } | |||
1587 | ||||
1588 | // Move What before Where in the IR. The end result is taht What will belong to | |||
1589 | // the right lists and have the right Block set, but will not otherwise be | |||
1590 | // correct. It will not have the right defining access, and if it is a def, | |||
1591 | // things below it will not properly be updated. | |||
1592 | void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, | |||
1593 | AccessList::iterator Where) { | |||
1594 | // Keep it in the lookup tables, remove from the lists | |||
1595 | removeFromLists(What, false); | |||
1596 | What->setBlock(BB); | |||
1597 | insertIntoListsBefore(What, BB, Where); | |||
1598 | } | |||
1599 | ||||
1600 | void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, | |||
1601 | InsertionPlace Point) { | |||
1602 | removeFromLists(What, false); | |||
1603 | What->setBlock(BB); | |||
1604 | insertIntoListsForBlock(What, BB, Point); | |||
1605 | } | |||
1606 | ||||
1607 | MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { | |||
1608 | assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB")((!getMemoryAccess(BB) && "MemoryPhi already exists for this BB" ) ? static_cast<void> (0) : __assert_fail ("!getMemoryAccess(BB) && \"MemoryPhi already exists for this BB\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1608, __PRETTY_FUNCTION__)); | |||
1609 | MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++); | |||
1610 | // Phi's always are placed at the front of the block. | |||
1611 | insertIntoListsForBlock(Phi, BB, Beginning); | |||
1612 | ValueToMemoryAccess[BB] = Phi; | |||
1613 | return Phi; | |||
1614 | } | |||
1615 | ||||
1616 | MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I, | |||
1617 | MemoryAccess *Definition) { | |||
1618 | assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI")((!isa<PHINode>(I) && "Cannot create a defined access for a PHI" ) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(I) && \"Cannot create a defined access for a PHI\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1618, __PRETTY_FUNCTION__)); | |||
1619 | MemoryUseOrDef *NewAccess = createNewAccess(I); | |||
1620 | assert(((NewAccess != nullptr && "Tried to create a memory access for a non-memory touching instruction" ) ? static_cast<void> (0) : __assert_fail ("NewAccess != nullptr && \"Tried to create a memory access for a non-memory touching instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1622, __PRETTY_FUNCTION__)) | |||
1621 | NewAccess != nullptr &&((NewAccess != nullptr && "Tried to create a memory access for a non-memory touching instruction" ) ? static_cast<void> (0) : __assert_fail ("NewAccess != nullptr && \"Tried to create a memory access for a non-memory touching instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1622, __PRETTY_FUNCTION__)) | |||
1622 | "Tried to create a memory access for a non-memory touching instruction")((NewAccess != nullptr && "Tried to create a memory access for a non-memory touching instruction" ) ? static_cast<void> (0) : __assert_fail ("NewAccess != nullptr && \"Tried to create a memory access for a non-memory touching instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1622, __PRETTY_FUNCTION__)); | |||
1623 | NewAccess->setDefiningAccess(Definition); | |||
1624 | return NewAccess; | |||
1625 | } | |||
1626 | ||||
1627 | /// \brief Helper function to create new memory accesses | |||
1628 | MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) { | |||
1629 | // The assume intrinsic has a control dependency which we model by claiming | |||
1630 | // that it writes arbitrarily. Ignore that fake memory dependency here. | |||
1631 | // FIXME: Replace this special casing with a more accurate modelling of | |||
1632 | // assume's control dependency. | |||
1633 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) | |||
1634 | if (II->getIntrinsicID() == Intrinsic::assume) | |||
1635 | return nullptr; | |||
1636 | ||||
1637 | // Find out what affect this instruction has on memory. | |||
1638 | ModRefInfo ModRef = AA->getModRefInfo(I); | |||
1639 | bool Def = bool(ModRef & MRI_Mod); | |||
1640 | bool Use = bool(ModRef & MRI_Ref); | |||
1641 | ||||
1642 | // It's possible for an instruction to not modify memory at all. During | |||
1643 | // construction, we ignore them. | |||
1644 | if (!Def && !Use) | |||
1645 | return nullptr; | |||
1646 | ||||
1647 | assert((Def || Use) &&(((Def || Use) && "Trying to create a memory access with a non-memory instruction" ) ? static_cast<void> (0) : __assert_fail ("(Def || Use) && \"Trying to create a memory access with a non-memory instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1648, __PRETTY_FUNCTION__)) | |||
1648 | "Trying to create a memory access with a non-memory instruction")(((Def || Use) && "Trying to create a memory access with a non-memory instruction" ) ? static_cast<void> (0) : __assert_fail ("(Def || Use) && \"Trying to create a memory access with a non-memory instruction\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1648, __PRETTY_FUNCTION__)); | |||
1649 | ||||
1650 | MemoryUseOrDef *MUD; | |||
1651 | if (Def) | |||
1652 | MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++); | |||
1653 | else | |||
1654 | MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent()); | |||
1655 | ValueToMemoryAccess[I] = MUD; | |||
1656 | return MUD; | |||
1657 | } | |||
1658 | ||||
1659 | /// \brief Returns true if \p Replacer dominates \p Replacee . | |||
1660 | bool MemorySSA::dominatesUse(const MemoryAccess *Replacer, | |||
1661 | const MemoryAccess *Replacee) const { | |||
1662 | if (isa<MemoryUseOrDef>(Replacee)) | |||
1663 | return DT->dominates(Replacer->getBlock(), Replacee->getBlock()); | |||
1664 | const auto *MP = cast<MemoryPhi>(Replacee); | |||
1665 | // For a phi node, the use occurs in the predecessor block of the phi node. | |||
1666 | // Since we may occur multiple times in the phi node, we have to check each | |||
1667 | // operand to ensure Replacer dominates each operand where Replacee occurs. | |||
1668 | for (const Use &Arg : MP->operands()) { | |||
1669 | if (Arg.get() != Replacee && | |||
1670 | !DT->dominates(Replacer->getBlock(), MP->getIncomingBlock(Arg))) | |||
1671 | return false; | |||
1672 | } | |||
1673 | return true; | |||
1674 | } | |||
1675 | ||||
1676 | /// \brief Properly remove \p MA from all of MemorySSA's lookup tables. | |||
1677 | void MemorySSA::removeFromLookups(MemoryAccess *MA) { | |||
1678 | assert(MA->use_empty() &&((MA->use_empty() && "Trying to remove memory access that still has uses" ) ? static_cast<void> (0) : __assert_fail ("MA->use_empty() && \"Trying to remove memory access that still has uses\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1679, __PRETTY_FUNCTION__)) | |||
1679 | "Trying to remove memory access that still has uses")((MA->use_empty() && "Trying to remove memory access that still has uses" ) ? static_cast<void> (0) : __assert_fail ("MA->use_empty() && \"Trying to remove memory access that still has uses\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1679, __PRETTY_FUNCTION__)); | |||
1680 | BlockNumbering.erase(MA); | |||
1681 | if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) | |||
1682 | MUD->setDefiningAccess(nullptr); | |||
1683 | // Invalidate our walker's cache if necessary | |||
1684 | if (!isa<MemoryUse>(MA)) | |||
1685 | Walker->invalidateInfo(MA); | |||
1686 | // The call below to erase will destroy MA, so we can't change the order we | |||
1687 | // are doing things here | |||
1688 | Value *MemoryInst; | |||
1689 | if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) { | |||
1690 | MemoryInst = MUD->getMemoryInst(); | |||
1691 | } else { | |||
1692 | MemoryInst = MA->getBlock(); | |||
1693 | } | |||
1694 | auto VMA = ValueToMemoryAccess.find(MemoryInst); | |||
1695 | if (VMA->second == MA) | |||
1696 | ValueToMemoryAccess.erase(VMA); | |||
1697 | } | |||
1698 | ||||
1699 | /// \brief Properly remove \p MA from all of MemorySSA's lists. | |||
1700 | /// | |||
1701 | /// Because of the way the intrusive list and use lists work, it is important to | |||
1702 | /// do removal in the right order. | |||
1703 | /// ShouldDelete defaults to true, and will cause the memory access to also be | |||
1704 | /// deleted, not just removed. | |||
1705 | void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) { | |||
1706 | // The access list owns the reference, so we erase it from the non-owning list | |||
1707 | // first. | |||
1708 | if (!isa<MemoryUse>(MA)) { | |||
1709 | auto DefsIt = PerBlockDefs.find(MA->getBlock()); | |||
1710 | std::unique_ptr<DefsList> &Defs = DefsIt->second; | |||
1711 | Defs->remove(*MA); | |||
1712 | if (Defs->empty()) | |||
1713 | PerBlockDefs.erase(DefsIt); | |||
1714 | } | |||
1715 | ||||
1716 | // The erase call here will delete it. If we don't want it deleted, we call | |||
1717 | // remove instead. | |||
1718 | auto AccessIt = PerBlockAccesses.find(MA->getBlock()); | |||
1719 | std::unique_ptr<AccessList> &Accesses = AccessIt->second; | |||
1720 | if (ShouldDelete) | |||
1721 | Accesses->erase(MA); | |||
1722 | else | |||
1723 | Accesses->remove(MA); | |||
1724 | ||||
1725 | if (Accesses->empty()) | |||
1726 | PerBlockAccesses.erase(AccessIt); | |||
1727 | } | |||
1728 | ||||
1729 | void MemorySSA::print(raw_ostream &OS) const { | |||
1730 | MemorySSAAnnotatedWriter Writer(this); | |||
1731 | F.print(OS, &Writer); | |||
1732 | } | |||
1733 | ||||
1734 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
1735 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void MemorySSA::dump() const { print(dbgs()); } | |||
1736 | #endif | |||
1737 | ||||
1738 | void MemorySSA::verifyMemorySSA() const { | |||
1739 | verifyDefUses(F); | |||
1740 | verifyDomination(F); | |||
1741 | verifyOrdering(F); | |||
1742 | Walker->verify(this); | |||
1743 | } | |||
1744 | ||||
1745 | /// \brief Verify that the order and existence of MemoryAccesses matches the | |||
1746 | /// order and existence of memory affecting instructions. | |||
1747 | void MemorySSA::verifyOrdering(Function &F) const { | |||
1748 | // Walk all the blocks, comparing what the lookups think and what the access | |||
1749 | // lists think, as well as the order in the blocks vs the order in the access | |||
1750 | // lists. | |||
1751 | SmallVector<MemoryAccess *, 32> ActualAccesses; | |||
1752 | SmallVector<MemoryAccess *, 32> ActualDefs; | |||
1753 | for (BasicBlock &B : F) { | |||
1754 | const AccessList *AL = getBlockAccesses(&B); | |||
1755 | const auto *DL = getBlockDefs(&B); | |||
1756 | MemoryAccess *Phi = getMemoryAccess(&B); | |||
1757 | if (Phi) { | |||
1758 | ActualAccesses.push_back(Phi); | |||
1759 | ActualDefs.push_back(Phi); | |||
1760 | } | |||
1761 | ||||
1762 | for (Instruction &I : B) { | |||
1763 | MemoryAccess *MA = getMemoryAccess(&I); | |||
1764 | assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) &&(((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && "We have memory affecting instructions " "in this block but they are not in the " "access list or defs list") ? static_cast<void> (0) : __assert_fail ("(!MA || (AL && (isa<MemoryUse>(MA) || DL))) && \"We have memory affecting instructions \" \"in this block but they are not in the \" \"access list or defs list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1767, __PRETTY_FUNCTION__)) | |||
1765 | "We have memory affecting instructions "(((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && "We have memory affecting instructions " "in this block but they are not in the " "access list or defs list") ? static_cast<void> (0) : __assert_fail ("(!MA || (AL && (isa<MemoryUse>(MA) || DL))) && \"We have memory affecting instructions \" \"in this block but they are not in the \" \"access list or defs list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1767, __PRETTY_FUNCTION__)) | |||
1766 | "in this block but they are not in the "(((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && "We have memory affecting instructions " "in this block but they are not in the " "access list or defs list") ? static_cast<void> (0) : __assert_fail ("(!MA || (AL && (isa<MemoryUse>(MA) || DL))) && \"We have memory affecting instructions \" \"in this block but they are not in the \" \"access list or defs list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1767, __PRETTY_FUNCTION__)) | |||
1767 | "access list or defs list")(((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && "We have memory affecting instructions " "in this block but they are not in the " "access list or defs list") ? static_cast<void> (0) : __assert_fail ("(!MA || (AL && (isa<MemoryUse>(MA) || DL))) && \"We have memory affecting instructions \" \"in this block but they are not in the \" \"access list or defs list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1767, __PRETTY_FUNCTION__)); | |||
1768 | if (MA) { | |||
1769 | ActualAccesses.push_back(MA); | |||
1770 | if (isa<MemoryDef>(MA)) | |||
1771 | ActualDefs.push_back(MA); | |||
1772 | } | |||
1773 | } | |||
1774 | // Either we hit the assert, really have no accesses, or we have both | |||
1775 | // accesses and an access list. | |||
1776 | // Same with defs. | |||
1777 | if (!AL && !DL) | |||
1778 | continue; | |||
1779 | assert(AL->size() == ActualAccesses.size() &&((AL->size() == ActualAccesses.size() && "We don't have the same number of accesses in the block as on the " "access list") ? static_cast<void> (0) : __assert_fail ("AL->size() == ActualAccesses.size() && \"We don't have the same number of accesses in the block as on the \" \"access list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1781, __PRETTY_FUNCTION__)) | |||
1780 | "We don't have the same number of accesses in the block as on the "((AL->size() == ActualAccesses.size() && "We don't have the same number of accesses in the block as on the " "access list") ? static_cast<void> (0) : __assert_fail ("AL->size() == ActualAccesses.size() && \"We don't have the same number of accesses in the block as on the \" \"access list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1781, __PRETTY_FUNCTION__)) | |||
1781 | "access list")((AL->size() == ActualAccesses.size() && "We don't have the same number of accesses in the block as on the " "access list") ? static_cast<void> (0) : __assert_fail ("AL->size() == ActualAccesses.size() && \"We don't have the same number of accesses in the block as on the \" \"access list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1781, __PRETTY_FUNCTION__)); | |||
1782 | assert((DL || ActualDefs.size() == 0) &&(((DL || ActualDefs.size() == 0) && "Either we should have a defs list, or we should have no defs" ) ? static_cast<void> (0) : __assert_fail ("(DL || ActualDefs.size() == 0) && \"Either we should have a defs list, or we should have no defs\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1783, __PRETTY_FUNCTION__)) | |||
1783 | "Either we should have a defs list, or we should have no defs")(((DL || ActualDefs.size() == 0) && "Either we should have a defs list, or we should have no defs" ) ? static_cast<void> (0) : __assert_fail ("(DL || ActualDefs.size() == 0) && \"Either we should have a defs list, or we should have no defs\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1783, __PRETTY_FUNCTION__)); | |||
1784 | assert((!DL || DL->size() == ActualDefs.size()) &&(((!DL || DL->size() == ActualDefs.size()) && "We don't have the same number of defs in the block as on the " "def list") ? static_cast<void> (0) : __assert_fail ("(!DL || DL->size() == ActualDefs.size()) && \"We don't have the same number of defs in the block as on the \" \"def list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1786, __PRETTY_FUNCTION__)) | |||
1785 | "We don't have the same number of defs in the block as on the "(((!DL || DL->size() == ActualDefs.size()) && "We don't have the same number of defs in the block as on the " "def list") ? static_cast<void> (0) : __assert_fail ("(!DL || DL->size() == ActualDefs.size()) && \"We don't have the same number of defs in the block as on the \" \"def list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1786, __PRETTY_FUNCTION__)) | |||
1786 | "def list")(((!DL || DL->size() == ActualDefs.size()) && "We don't have the same number of defs in the block as on the " "def list") ? static_cast<void> (0) : __assert_fail ("(!DL || DL->size() == ActualDefs.size()) && \"We don't have the same number of defs in the block as on the \" \"def list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1786, __PRETTY_FUNCTION__)); | |||
1787 | auto ALI = AL->begin(); | |||
1788 | auto AAI = ActualAccesses.begin(); | |||
1789 | while (ALI != AL->end() && AAI != ActualAccesses.end()) { | |||
1790 | assert(&*ALI == *AAI && "Not the same accesses in the same order")((&*ALI == *AAI && "Not the same accesses in the same order" ) ? static_cast<void> (0) : __assert_fail ("&*ALI == *AAI && \"Not the same accesses in the same order\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1790, __PRETTY_FUNCTION__)); | |||
1791 | ++ALI; | |||
1792 | ++AAI; | |||
1793 | } | |||
1794 | ActualAccesses.clear(); | |||
1795 | if (DL) { | |||
1796 | auto DLI = DL->begin(); | |||
1797 | auto ADI = ActualDefs.begin(); | |||
1798 | while (DLI != DL->end() && ADI != ActualDefs.end()) { | |||
1799 | assert(&*DLI == *ADI && "Not the same defs in the same order")((&*DLI == *ADI && "Not the same defs in the same order" ) ? static_cast<void> (0) : __assert_fail ("&*DLI == *ADI && \"Not the same defs in the same order\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1799, __PRETTY_FUNCTION__)); | |||
1800 | ++DLI; | |||
1801 | ++ADI; | |||
1802 | } | |||
1803 | } | |||
1804 | ActualDefs.clear(); | |||
1805 | } | |||
1806 | } | |||
1807 | ||||
1808 | /// \brief Verify the domination properties of MemorySSA by checking that each | |||
1809 | /// definition dominates all of its uses. | |||
1810 | void MemorySSA::verifyDomination(Function &F) const { | |||
1811 | #ifndef NDEBUG | |||
1812 | for (BasicBlock &B : F) { | |||
1813 | // Phi nodes are attached to basic blocks | |||
1814 | if (MemoryPhi *MP = getMemoryAccess(&B)) | |||
1815 | for (const Use &U : MP->uses()) | |||
1816 | assert(dominates(MP, U) && "Memory PHI does not dominate it's uses")((dominates(MP, U) && "Memory PHI does not dominate it's uses" ) ? static_cast<void> (0) : __assert_fail ("dominates(MP, U) && \"Memory PHI does not dominate it's uses\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1816, __PRETTY_FUNCTION__)); | |||
1817 | ||||
1818 | for (Instruction &I : B) { | |||
1819 | MemoryAccess *MD = dyn_cast_or_null<MemoryDef>(getMemoryAccess(&I)); | |||
1820 | if (!MD) | |||
1821 | continue; | |||
1822 | ||||
1823 | for (const Use &U : MD->uses()) | |||
1824 | assert(dominates(MD, U) && "Memory Def does not dominate it's uses")((dominates(MD, U) && "Memory Def does not dominate it's uses" ) ? static_cast<void> (0) : __assert_fail ("dominates(MD, U) && \"Memory Def does not dominate it's uses\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1824, __PRETTY_FUNCTION__)); | |||
1825 | } | |||
1826 | } | |||
1827 | #endif | |||
1828 | } | |||
1829 | ||||
1830 | /// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use | |||
1831 | /// appears in the use list of \p Def. | |||
1832 | ||||
1833 | void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const { | |||
1834 | #ifndef NDEBUG | |||
1835 | // The live on entry use may cause us to get a NULL def here | |||
1836 | if (!Def) | |||
1837 | assert(isLiveOnEntryDef(Use) &&((isLiveOnEntryDef(Use) && "Null def but use not point to live on entry def" ) ? static_cast<void> (0) : __assert_fail ("isLiveOnEntryDef(Use) && \"Null def but use not point to live on entry def\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1838, __PRETTY_FUNCTION__)) | |||
1838 | "Null def but use not point to live on entry def")((isLiveOnEntryDef(Use) && "Null def but use not point to live on entry def" ) ? static_cast<void> (0) : __assert_fail ("isLiveOnEntryDef(Use) && \"Null def but use not point to live on entry def\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1838, __PRETTY_FUNCTION__)); | |||
1839 | else | |||
1840 | assert(is_contained(Def->users(), Use) &&((is_contained(Def->users(), Use) && "Did not find use in def's use list" ) ? static_cast<void> (0) : __assert_fail ("is_contained(Def->users(), Use) && \"Did not find use in def's use list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1841, __PRETTY_FUNCTION__)) | |||
1841 | "Did not find use in def's use list")((is_contained(Def->users(), Use) && "Did not find use in def's use list" ) ? static_cast<void> (0) : __assert_fail ("is_contained(Def->users(), Use) && \"Did not find use in def's use list\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1841, __PRETTY_FUNCTION__)); | |||
1842 | #endif | |||
1843 | } | |||
1844 | ||||
1845 | /// \brief Verify the immediate use information, by walking all the memory | |||
1846 | /// accesses and verifying that, for each use, it appears in the | |||
1847 | /// appropriate def's use list | |||
1848 | void MemorySSA::verifyDefUses(Function &F) const { | |||
1849 | for (BasicBlock &B : F) { | |||
1850 | // Phi nodes are attached to basic blocks | |||
1851 | if (MemoryPhi *Phi = getMemoryAccess(&B)) { | |||
1852 | assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance(((Phi->getNumOperands() == static_cast<unsigned>(std ::distance( pred_begin(&B), pred_end(&B))) && "Incomplete MemoryPhi Node") ? static_cast<void> (0) : __assert_fail ("Phi->getNumOperands() == static_cast<unsigned>(std::distance( pred_begin(&B), pred_end(&B))) && \"Incomplete MemoryPhi Node\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1854, __PRETTY_FUNCTION__)) | |||
1853 | pred_begin(&B), pred_end(&B))) &&((Phi->getNumOperands() == static_cast<unsigned>(std ::distance( pred_begin(&B), pred_end(&B))) && "Incomplete MemoryPhi Node") ? static_cast<void> (0) : __assert_fail ("Phi->getNumOperands() == static_cast<unsigned>(std::distance( pred_begin(&B), pred_end(&B))) && \"Incomplete MemoryPhi Node\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1854, __PRETTY_FUNCTION__)) | |||
1854 | "Incomplete MemoryPhi Node")((Phi->getNumOperands() == static_cast<unsigned>(std ::distance( pred_begin(&B), pred_end(&B))) && "Incomplete MemoryPhi Node") ? static_cast<void> (0) : __assert_fail ("Phi->getNumOperands() == static_cast<unsigned>(std::distance( pred_begin(&B), pred_end(&B))) && \"Incomplete MemoryPhi Node\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1854, __PRETTY_FUNCTION__)); | |||
1855 | for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) | |||
1856 | verifyUseInDefs(Phi->getIncomingValue(I), Phi); | |||
1857 | } | |||
1858 | ||||
1859 | for (Instruction &I : B) { | |||
1860 | if (MemoryUseOrDef *MA = getMemoryAccess(&I)) { | |||
1861 | verifyUseInDefs(MA->getDefiningAccess(), MA); | |||
1862 | } | |||
1863 | } | |||
1864 | } | |||
1865 | } | |||
1866 | ||||
1867 | MemoryUseOrDef *MemorySSA::getMemoryAccess(const Instruction *I) const { | |||
1868 | return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I)); | |||
1869 | } | |||
1870 | ||||
1871 | MemoryPhi *MemorySSA::getMemoryAccess(const BasicBlock *BB) const { | |||
1872 | return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB))); | |||
1873 | } | |||
1874 | ||||
1875 | /// Perform a local numbering on blocks so that instruction ordering can be | |||
1876 | /// determined in constant time. | |||
1877 | /// TODO: We currently just number in order. If we numbered by N, we could | |||
1878 | /// allow at least N-1 sequences of insertBefore or insertAfter (and at least | |||
1879 | /// log2(N) sequences of mixed before and after) without needing to invalidate | |||
1880 | /// the numbering. | |||
1881 | void MemorySSA::renumberBlock(const BasicBlock *B) const { | |||
1882 | // The pre-increment ensures the numbers really start at 1. | |||
1883 | unsigned long CurrentNumber = 0; | |||
1884 | const AccessList *AL = getBlockAccesses(B); | |||
1885 | assert(AL != nullptr && "Asking to renumber an empty block")((AL != nullptr && "Asking to renumber an empty block" ) ? static_cast<void> (0) : __assert_fail ("AL != nullptr && \"Asking to renumber an empty block\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1885, __PRETTY_FUNCTION__)); | |||
1886 | for (const auto &I : *AL) | |||
1887 | BlockNumbering[&I] = ++CurrentNumber; | |||
1888 | BlockNumberingValid.insert(B); | |||
1889 | } | |||
1890 | ||||
1891 | /// \brief Determine, for two memory accesses in the same block, | |||
1892 | /// whether \p Dominator dominates \p Dominatee. | |||
1893 | /// \returns True if \p Dominator dominates \p Dominatee. | |||
1894 | bool MemorySSA::locallyDominates(const MemoryAccess *Dominator, | |||
1895 | const MemoryAccess *Dominatee) const { | |||
1896 | ||||
1897 | const BasicBlock *DominatorBlock = Dominator->getBlock(); | |||
1898 | ||||
1899 | assert((DominatorBlock == Dominatee->getBlock()) &&(((DominatorBlock == Dominatee->getBlock()) && "Asking for local domination when accesses are in different blocks!" ) ? static_cast<void> (0) : __assert_fail ("(DominatorBlock == Dominatee->getBlock()) && \"Asking for local domination when accesses are in different blocks!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1900, __PRETTY_FUNCTION__)) | |||
1900 | "Asking for local domination when accesses are in different blocks!")(((DominatorBlock == Dominatee->getBlock()) && "Asking for local domination when accesses are in different blocks!" ) ? static_cast<void> (0) : __assert_fail ("(DominatorBlock == Dominatee->getBlock()) && \"Asking for local domination when accesses are in different blocks!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1900, __PRETTY_FUNCTION__)); | |||
1901 | // A node dominates itself. | |||
1902 | if (Dominatee == Dominator) | |||
1903 | return true; | |||
1904 | ||||
1905 | // When Dominatee is defined on function entry, it is not dominated by another | |||
1906 | // memory access. | |||
1907 | if (isLiveOnEntryDef(Dominatee)) | |||
1908 | return false; | |||
1909 | ||||
1910 | // When Dominator is defined on function entry, it dominates the other memory | |||
1911 | // access. | |||
1912 | if (isLiveOnEntryDef(Dominator)) | |||
1913 | return true; | |||
1914 | ||||
1915 | if (!BlockNumberingValid.count(DominatorBlock)) | |||
1916 | renumberBlock(DominatorBlock); | |||
1917 | ||||
1918 | unsigned long DominatorNum = BlockNumbering.lookup(Dominator); | |||
1919 | // All numbers start with 1 | |||
1920 | assert(DominatorNum != 0 && "Block was not numbered properly")((DominatorNum != 0 && "Block was not numbered properly" ) ? static_cast<void> (0) : __assert_fail ("DominatorNum != 0 && \"Block was not numbered properly\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1920, __PRETTY_FUNCTION__)); | |||
1921 | unsigned long DominateeNum = BlockNumbering.lookup(Dominatee); | |||
1922 | assert(DominateeNum != 0 && "Block was not numbered properly")((DominateeNum != 0 && "Block was not numbered properly" ) ? static_cast<void> (0) : __assert_fail ("DominateeNum != 0 && \"Block was not numbered properly\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 1922, __PRETTY_FUNCTION__)); | |||
1923 | return DominatorNum < DominateeNum; | |||
1924 | } | |||
1925 | ||||
1926 | bool MemorySSA::dominates(const MemoryAccess *Dominator, | |||
1927 | const MemoryAccess *Dominatee) const { | |||
1928 | if (Dominator == Dominatee) | |||
1929 | return true; | |||
1930 | ||||
1931 | if (isLiveOnEntryDef(Dominatee)) | |||
1932 | return false; | |||
1933 | ||||
1934 | if (Dominator->getBlock() != Dominatee->getBlock()) | |||
1935 | return DT->dominates(Dominator->getBlock(), Dominatee->getBlock()); | |||
1936 | return locallyDominates(Dominator, Dominatee); | |||
1937 | } | |||
1938 | ||||
1939 | bool MemorySSA::dominates(const MemoryAccess *Dominator, | |||
1940 | const Use &Dominatee) const { | |||
1941 | if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Dominatee.getUser())) { | |||
1942 | BasicBlock *UseBB = MP->getIncomingBlock(Dominatee); | |||
1943 | // The def must dominate the incoming block of the phi. | |||
1944 | if (UseBB != Dominator->getBlock()) | |||
1945 | return DT->dominates(Dominator->getBlock(), UseBB); | |||
1946 | // If the UseBB and the DefBB are the same, compare locally. | |||
1947 | return locallyDominates(Dominator, cast<MemoryAccess>(Dominatee)); | |||
1948 | } | |||
1949 | // If it's not a PHI node use, the normal dominates can already handle it. | |||
1950 | return dominates(Dominator, cast<MemoryAccess>(Dominatee.getUser())); | |||
1951 | } | |||
1952 | ||||
1953 | const static char LiveOnEntryStr[] = "liveOnEntry"; | |||
1954 | ||||
1955 | void MemoryDef::print(raw_ostream &OS) const { | |||
1956 | MemoryAccess *UO = getDefiningAccess(); | |||
1957 | ||||
1958 | OS << getID() << " = MemoryDef("; | |||
1959 | if (UO && UO->getID()) | |||
1960 | OS << UO->getID(); | |||
1961 | else | |||
1962 | OS << LiveOnEntryStr; | |||
1963 | OS << ')'; | |||
1964 | } | |||
1965 | ||||
1966 | void MemoryPhi::print(raw_ostream &OS) const { | |||
1967 | bool First = true; | |||
1968 | OS << getID() << " = MemoryPhi("; | |||
1969 | for (const auto &Op : operands()) { | |||
1970 | BasicBlock *BB = getIncomingBlock(Op); | |||
1971 | MemoryAccess *MA = cast<MemoryAccess>(Op); | |||
1972 | if (!First) | |||
1973 | OS << ','; | |||
1974 | else | |||
1975 | First = false; | |||
1976 | ||||
1977 | OS << '{'; | |||
1978 | if (BB->hasName()) | |||
1979 | OS << BB->getName(); | |||
1980 | else | |||
1981 | BB->printAsOperand(OS, false); | |||
1982 | OS << ','; | |||
1983 | if (unsigned ID = MA->getID()) | |||
1984 | OS << ID; | |||
1985 | else | |||
1986 | OS << LiveOnEntryStr; | |||
1987 | OS << '}'; | |||
1988 | } | |||
1989 | OS << ')'; | |||
1990 | } | |||
1991 | ||||
1992 | MemoryAccess::~MemoryAccess() {} | |||
1993 | ||||
1994 | void MemoryUse::print(raw_ostream &OS) const { | |||
1995 | MemoryAccess *UO = getDefiningAccess(); | |||
1996 | OS << "MemoryUse("; | |||
1997 | if (UO && UO->getID()) | |||
1998 | OS << UO->getID(); | |||
1999 | else | |||
2000 | OS << LiveOnEntryStr; | |||
2001 | OS << ')'; | |||
2002 | } | |||
2003 | ||||
2004 | void MemoryAccess::dump() const { | |||
2005 | // Cannot completely remove virtual function even in release mode. | |||
2006 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
2007 | print(dbgs()); | |||
2008 | dbgs() << "\n"; | |||
2009 | #endif | |||
2010 | } | |||
2011 | ||||
2012 | char MemorySSAPrinterLegacyPass::ID = 0; | |||
2013 | ||||
2014 | MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass() : FunctionPass(ID) { | |||
2015 | initializeMemorySSAPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
2016 | } | |||
2017 | ||||
2018 | void MemorySSAPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
2019 | AU.setPreservesAll(); | |||
2020 | AU.addRequired<MemorySSAWrapperPass>(); | |||
2021 | AU.addPreserved<MemorySSAWrapperPass>(); | |||
2022 | } | |||
2023 | ||||
2024 | bool MemorySSAPrinterLegacyPass::runOnFunction(Function &F) { | |||
2025 | auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA(); | |||
2026 | MSSA.print(dbgs()); | |||
2027 | if (VerifyMemorySSA) | |||
2028 | MSSA.verifyMemorySSA(); | |||
2029 | return false; | |||
2030 | } | |||
2031 | ||||
2032 | AnalysisKey MemorySSAAnalysis::Key; | |||
2033 | ||||
2034 | MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F, | |||
2035 | FunctionAnalysisManager &AM) { | |||
2036 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); | |||
2037 | auto &AA = AM.getResult<AAManager>(F); | |||
2038 | return MemorySSAAnalysis::Result(make_unique<MemorySSA>(F, &AA, &DT)); | |||
2039 | } | |||
2040 | ||||
2041 | PreservedAnalyses MemorySSAPrinterPass::run(Function &F, | |||
2042 | FunctionAnalysisManager &AM) { | |||
2043 | OS << "MemorySSA for function: " << F.getName() << "\n"; | |||
2044 | AM.getResult<MemorySSAAnalysis>(F).getMSSA().print(OS); | |||
2045 | ||||
2046 | return PreservedAnalyses::all(); | |||
2047 | } | |||
2048 | ||||
2049 | PreservedAnalyses MemorySSAVerifierPass::run(Function &F, | |||
2050 | FunctionAnalysisManager &AM) { | |||
2051 | AM.getResult<MemorySSAAnalysis>(F).getMSSA().verifyMemorySSA(); | |||
2052 | ||||
2053 | return PreservedAnalyses::all(); | |||
2054 | } | |||
2055 | ||||
2056 | char MemorySSAWrapperPass::ID = 0; | |||
2057 | ||||
2058 | MemorySSAWrapperPass::MemorySSAWrapperPass() : FunctionPass(ID) { | |||
2059 | initializeMemorySSAWrapperPassPass(*PassRegistry::getPassRegistry()); | |||
2060 | } | |||
2061 | ||||
2062 | void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); } | |||
2063 | ||||
2064 | void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
2065 | AU.setPreservesAll(); | |||
2066 | AU.addRequiredTransitive<DominatorTreeWrapperPass>(); | |||
2067 | AU.addRequiredTransitive<AAResultsWrapperPass>(); | |||
2068 | } | |||
2069 | ||||
2070 | bool MemorySSAWrapperPass::runOnFunction(Function &F) { | |||
2071 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
2072 | auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); | |||
2073 | MSSA.reset(new MemorySSA(F, &AA, &DT)); | |||
2074 | return false; | |||
2075 | } | |||
2076 | ||||
2077 | void MemorySSAWrapperPass::verifyAnalysis() const { MSSA->verifyMemorySSA(); } | |||
2078 | ||||
2079 | void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const { | |||
2080 | MSSA->print(OS); | |||
2081 | } | |||
2082 | ||||
2083 | MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {} | |||
2084 | ||||
2085 | MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A, | |||
2086 | DominatorTree *D) | |||
2087 | : MemorySSAWalker(M), Walker(*M, *A, *D, Cache), AutoResetWalker(true) {} | |||
2088 | ||||
2089 | MemorySSA::CachingWalker::~CachingWalker() {} | |||
2090 | ||||
2091 | void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) { | |||
2092 | // TODO: We can do much better cache invalidation with differently stored | |||
2093 | // caches. For now, for MemoryUses, we simply remove them | |||
2094 | // from the cache, and kill the entire call/non-call cache for everything | |||
2095 | // else. The problem is for phis or defs, currently we'd need to follow use | |||
2096 | // chains down and invalidate anything below us in the chain that currently | |||
2097 | // terminates at this access. | |||
2098 | ||||
2099 | // See if this is a MemoryUse, if so, just remove the cached info. MemoryUse | |||
2100 | // is by definition never a barrier, so nothing in the cache could point to | |||
2101 | // this use. In that case, we only need invalidate the info for the use | |||
2102 | // itself. | |||
2103 | ||||
2104 | if (MemoryUse *MU = dyn_cast<MemoryUse>(MA)) { | |||
2105 | UpwardsMemoryQuery Q(MU->getMemoryInst(), MU); | |||
2106 | Cache.remove(MU, Q.StartingLoc, Q.IsCall); | |||
2107 | MU->resetOptimized(); | |||
2108 | } else { | |||
2109 | // If it is not a use, the best we can do right now is destroy the cache. | |||
2110 | Cache.clear(); | |||
2111 | } | |||
2112 | ||||
2113 | #ifdef EXPENSIVE_CHECKS | |||
2114 | verifyRemoved(MA); | |||
2115 | #endif | |||
2116 | } | |||
2117 | ||||
2118 | /// \brief Walk the use-def chains starting at \p MA and find | |||
2119 | /// the MemoryAccess that actually clobbers Loc. | |||
2120 | /// | |||
2121 | /// \returns our clobbering memory access | |||
2122 | MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess( | |||
2123 | MemoryAccess *StartingAccess, UpwardsMemoryQuery &Q) { | |||
2124 | MemoryAccess *New = Walker.findClobber(StartingAccess, Q); | |||
2125 | #ifdef EXPENSIVE_CHECKS | |||
2126 | MemoryAccess *NewNoCache = | |||
2127 | Walker.findClobber(StartingAccess, Q, /*UseWalkerCache=*/false); | |||
2128 | assert(NewNoCache == New && "Cache made us hand back a different result?")((NewNoCache == New && "Cache made us hand back a different result?" ) ? static_cast<void> (0) : __assert_fail ("NewNoCache == New && \"Cache made us hand back a different result?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 2128, __PRETTY_FUNCTION__)); | |||
2129 | #endif | |||
2130 | if (AutoResetWalker) | |||
2131 | resetClobberWalker(); | |||
2132 | return New; | |||
2133 | } | |||
2134 | ||||
2135 | MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess( | |||
2136 | MemoryAccess *StartingAccess, const MemoryLocation &Loc) { | |||
2137 | if (isa<MemoryPhi>(StartingAccess)) | |||
2138 | return StartingAccess; | |||
2139 | ||||
2140 | auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess); | |||
2141 | if (MSSA->isLiveOnEntryDef(StartingUseOrDef)) | |||
2142 | return StartingUseOrDef; | |||
2143 | ||||
2144 | Instruction *I = StartingUseOrDef->getMemoryInst(); | |||
2145 | ||||
2146 | // Conservatively, fences are always clobbers, so don't perform the walk if we | |||
2147 | // hit a fence. | |||
2148 | if (!ImmutableCallSite(I) && I->isFenceLike()) | |||
2149 | return StartingUseOrDef; | |||
2150 | ||||
2151 | UpwardsMemoryQuery Q; | |||
2152 | Q.OriginalAccess = StartingUseOrDef; | |||
2153 | Q.StartingLoc = Loc; | |||
2154 | Q.Inst = I; | |||
2155 | Q.IsCall = false; | |||
2156 | ||||
2157 | if (auto *CacheResult = Cache.lookup(StartingUseOrDef, Loc, Q.IsCall)) | |||
2158 | return CacheResult; | |||
2159 | ||||
2160 | // Unlike the other function, do not walk to the def of a def, because we are | |||
2161 | // handed something we already believe is the clobbering access. | |||
2162 | MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef) | |||
2163 | ? StartingUseOrDef->getDefiningAccess() | |||
2164 | : StartingUseOrDef; | |||
2165 | ||||
2166 | MemoryAccess *Clobber = getClobberingMemoryAccess(DefiningAccess, Q); | |||
2167 | DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "Starting Memory SSA clobber for " << *I << " is "; } } while (false); | |||
2168 | DEBUG(dbgs() << *StartingUseOrDef << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << *StartingUseOrDef << "\n" ; } } while (false); | |||
2169 | DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "Final Memory SSA clobber for " << *I << " is "; } } while (false); | |||
2170 | DEBUG(dbgs() << *Clobber << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << *Clobber << "\n"; } } while (false); | |||
2171 | return Clobber; | |||
2172 | } | |||
2173 | ||||
2174 | MemoryAccess * | |||
2175 | MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) { | |||
2176 | auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA); | |||
2177 | // If this is a MemoryPhi, we can't do anything. | |||
2178 | if (!StartingAccess) | |||
2179 | return MA; | |||
2180 | ||||
2181 | // If this is an already optimized use or def, return the optimized result. | |||
2182 | // Note: Currently, we do not store the optimized def result because we'd need | |||
2183 | // a separate field, since we can't use it as the defining access. | |||
2184 | if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) | |||
2185 | if (MUD->isOptimized()) | |||
2186 | return MUD->getOptimized(); | |||
2187 | ||||
2188 | const Instruction *I = StartingAccess->getMemoryInst(); | |||
2189 | UpwardsMemoryQuery Q(I, StartingAccess); | |||
2190 | // We can't sanely do anything with a fences, they conservatively | |||
2191 | // clobber all memory, and have no locations to get pointers from to | |||
2192 | // try to disambiguate. | |||
2193 | if (!Q.IsCall && I->isFenceLike()) | |||
2194 | return StartingAccess; | |||
2195 | ||||
2196 | if (auto *CacheResult = Cache.lookup(StartingAccess, Q.StartingLoc, Q.IsCall)) | |||
2197 | return CacheResult; | |||
2198 | ||||
2199 | if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) { | |||
2200 | MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef(); | |||
2201 | Cache.insert(StartingAccess, LiveOnEntry, Q.StartingLoc, Q.IsCall); | |||
2202 | if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) | |||
2203 | MUD->setOptimized(LiveOnEntry); | |||
2204 | return LiveOnEntry; | |||
2205 | } | |||
2206 | ||||
2207 | // Start with the thing we already think clobbers this location | |||
2208 | MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess(); | |||
2209 | ||||
2210 | // At this point, DefiningAccess may be the live on entry def. | |||
2211 | // If it is, we will not get a better result. | |||
2212 | if (MSSA->isLiveOnEntryDef(DefiningAccess)) | |||
2213 | return DefiningAccess; | |||
2214 | ||||
2215 | MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q); | |||
2216 | DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "Starting Memory SSA clobber for " << *I << " is "; } } while (false); | |||
2217 | DEBUG(dbgs() << *DefiningAccess << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << *DefiningAccess << "\n" ; } } while (false); | |||
2218 | DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << "Final Memory SSA clobber for " << *I << " is "; } } while (false); | |||
2219 | DEBUG(dbgs() << *Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("memoryssa")) { dbgs() << *Result << "\n"; } } while (false); | |||
2220 | if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) | |||
2221 | MUD->setOptimized(Result); | |||
2222 | ||||
2223 | return Result; | |||
2224 | } | |||
2225 | ||||
2226 | // Verify that MA doesn't exist in any of the caches. | |||
2227 | void MemorySSA::CachingWalker::verifyRemoved(MemoryAccess *MA) { | |||
2228 | assert(!Cache.contains(MA) && "Found removed MemoryAccess in cache.")((!Cache.contains(MA) && "Found removed MemoryAccess in cache." ) ? static_cast<void> (0) : __assert_fail ("!Cache.contains(MA) && \"Found removed MemoryAccess in cache.\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn299523/lib/Transforms/Utils/MemorySSA.cpp" , 2228, __PRETTY_FUNCTION__)); | |||
2229 | } | |||
2230 | ||||
2231 | MemoryAccess * | |||
2232 | DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) { | |||
2233 | if (auto *Use = dyn_cast<MemoryUseOrDef>(MA)) | |||
2234 | return Use->getDefiningAccess(); | |||
2235 | return MA; | |||
2236 | } | |||
2237 | ||||
2238 | MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess( | |||
2239 | MemoryAccess *StartingAccess, const MemoryLocation &) { | |||
2240 | if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess)) | |||
2241 | return Use->getDefiningAccess(); | |||
2242 | return StartingAccess; | |||
2243 | } | |||
2244 | } // namespace llvm |