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