1//===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the MemorySSA class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/MemorySSA.h"
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/DenseMapInfo.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/DepthFirstIterator.h"
18#include "llvm/ADT/Hashing.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/StringExtras.h"
23#include "llvm/ADT/iterator.h"
24#include "llvm/ADT/iterator_range.h"
25#include "llvm/Analysis/AliasAnalysis.h"
26#include "llvm/Analysis/CFGPrinter.h"
27#include "llvm/Analysis/IteratedDominanceFrontier.h"
28#include "llvm/Analysis/Loads.h"
29#include "llvm/Analysis/LoopInfo.h"
30#include "llvm/Analysis/MemoryLocation.h"
31#include "llvm/Config/llvm-config.h"
32#include "llvm/IR/AssemblyAnnotationWriter.h"
33#include "llvm/IR/BasicBlock.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/LLVMContext.h"
40#include "llvm/IR/Operator.h"
41#include "llvm/IR/PassManager.h"
42#include "llvm/IR/Use.h"
43#include "llvm/InitializePasses.h"
44#include "llvm/Pass.h"
45#include "llvm/Support/AtomicOrdering.h"
46#include "llvm/Support/Casting.h"
47#include "llvm/Support/CommandLine.h"
48#include "llvm/Support/Compiler.h"
49#include "llvm/Support/Debug.h"
50#include "llvm/Support/ErrorHandling.h"
51#include "llvm/Support/FormattedStream.h"
52#include "llvm/Support/GraphWriter.h"
53#include "llvm/Support/raw_ostream.h"
54#include <algorithm>
55#include <cassert>
56#include <iterator>
57#include <memory>
58#include <utility>
59
60using namespace llvm;
61
62#define DEBUG_TYPE "memoryssa"
63
64static cl::opt<std::string>
65 DotCFGMSSA("dot-cfg-mssa",
66 cl::value_desc("file name for generated dot file"),
67 cl::desc("file name for generated dot file"), cl::init(Val: ""));
68
69INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
70 true)
71INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
72INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
73INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
74 true)
75
76static cl::opt<unsigned> MaxCheckLimit(
77 "memssa-check-limit", cl::Hidden, cl::init(Val: 100),
78 cl::desc("The maximum number of stores/phis MemorySSA"
79 "will consider trying to walk past (default = 100)"));
80
81// Always verify MemorySSA if expensive checking is enabled.
82#ifdef EXPENSIVE_CHECKS
83bool llvm::VerifyMemorySSA = true;
84#else
85bool llvm::VerifyMemorySSA = false;
86#endif
87
88static cl::opt<bool, true>
89 VerifyMemorySSAX("verify-memoryssa", cl::location(L&: VerifyMemorySSA),
90 cl::Hidden, cl::desc("Enable verification of MemorySSA."));
91
92const static char LiveOnEntryStr[] = "liveOnEntry";
93
94namespace {
95
96/// An assembly annotator class to print Memory SSA information in
97/// comments.
98class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
99 const MemorySSA *MSSA;
100
101public:
102 MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
103
104 void emitBasicBlockStartAnnot(const BasicBlock *BB,
105 formatted_raw_ostream &OS) override {
106 if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
107 OS << "; " << *MA << "\n";
108 }
109
110 void emitInstructionAnnot(const Instruction *I,
111 formatted_raw_ostream &OS) override {
112 if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
113 OS << "; " << *MA << "\n";
114 }
115};
116
117/// An assembly annotator class to print Memory SSA information in
118/// comments.
119class MemorySSAWalkerAnnotatedWriter : public AssemblyAnnotationWriter {
120 MemorySSA *MSSA;
121 MemorySSAWalker *Walker;
122 BatchAAResults BAA;
123
124public:
125 MemorySSAWalkerAnnotatedWriter(MemorySSA *M)
126 : MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
127
128 void emitBasicBlockStartAnnot(const BasicBlock *BB,
129 formatted_raw_ostream &OS) override {
130 if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
131 OS << "; " << *MA << "\n";
132 }
133
134 void emitInstructionAnnot(const Instruction *I,
135 formatted_raw_ostream &OS) override {
136 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
137 MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA, AA&: BAA);
138 OS << "; " << *MA;
139 if (Clobber) {
140 OS << " - clobbered by ";
141 if (MSSA->isLiveOnEntryDef(MA: Clobber))
142 OS << LiveOnEntryStr;
143 else
144 OS << *Clobber;
145 }
146 OS << "\n";
147 }
148 }
149};
150
151} // namespace
152
153namespace {
154
155/// Our current alias analysis API differentiates heavily between calls and
156/// non-calls, and functions called on one usually assert on the other.
157/// This class encapsulates the distinction to simplify other code that wants
158/// "Memory affecting instructions and related data" to use as a key.
159/// For example, this class is used as a densemap key in the use optimizer.
160class MemoryLocOrCall {
161public:
162 bool IsCall = false;
163
164 MemoryLocOrCall(MemoryUseOrDef *MUD)
165 : MemoryLocOrCall(MUD->getMemoryInst()) {}
166 MemoryLocOrCall(const MemoryUseOrDef *MUD)
167 : MemoryLocOrCall(MUD->getMemoryInst()) {}
168
169 MemoryLocOrCall(Instruction *Inst) {
170 if (auto *C = dyn_cast<CallBase>(Val: Inst)) {
171 IsCall = true;
172 Call = C;
173 } else {
174 IsCall = false;
175 // There is no such thing as a memorylocation for a fence inst, and it is
176 // unique in that regard.
177 if (!isa<FenceInst>(Val: Inst))
178 Loc = MemoryLocation::get(Inst);
179 }
180 }
181
182 explicit MemoryLocOrCall(const MemoryLocation &Loc) : Loc(Loc) {}
183
184 const CallBase *getCall() const {
185 assert(IsCall);
186 return Call;
187 }
188
189 MemoryLocation getLoc() const {
190 assert(!IsCall);
191 return Loc;
192 }
193
194 bool operator==(const MemoryLocOrCall &Other) const {
195 if (IsCall != Other.IsCall)
196 return false;
197
198 if (!IsCall)
199 return Loc == Other.Loc;
200
201 if (Call->getCalledOperand() != Other.Call->getCalledOperand())
202 return false;
203
204 return Call->arg_size() == Other.Call->arg_size() &&
205 std::equal(first1: Call->arg_begin(), last1: Call->arg_end(),
206 first2: Other.Call->arg_begin());
207 }
208
209private:
210 union {
211 const CallBase *Call;
212 MemoryLocation Loc;
213 };
214};
215
216} // end anonymous namespace
217
218namespace llvm {
219
220template <> struct DenseMapInfo<MemoryLocOrCall> {
221 static unsigned getHashValue(const MemoryLocOrCall &MLOC) {
222 if (!MLOC.IsCall)
223 return hash_combine(
224 args: MLOC.IsCall,
225 args: DenseMapInfo<MemoryLocation>::getHashValue(Val: MLOC.getLoc()));
226
227 hash_code hash =
228 hash_combine(args: MLOC.IsCall, args: DenseMapInfo<const Value *>::getHashValue(
229 PtrVal: MLOC.getCall()->getCalledOperand()));
230
231 for (const Value *Arg : MLOC.getCall()->args())
232 hash = hash_combine(args: hash, args: DenseMapInfo<const Value *>::getHashValue(PtrVal: Arg));
233 return hash;
234 }
235
236 static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
237 return LHS == RHS;
238 }
239};
240
241} // end namespace llvm
242
243/// This does one-way checks to see if Use could theoretically be hoisted above
244/// MayClobber. This will not check the other way around.
245///
246/// This assumes that, for the purposes of MemorySSA, Use comes directly after
247/// MayClobber, with no potentially clobbering operations in between them.
248/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
249static bool areLoadsReorderable(const LoadInst *Use,
250 const LoadInst *MayClobber) {
251 bool VolatileUse = Use->isVolatile();
252 bool VolatileClobber = MayClobber->isVolatile();
253 // Volatile operations may never be reordered with other volatile operations.
254 if (VolatileUse && VolatileClobber)
255 return false;
256 // Otherwise, volatile doesn't matter here. From the language reference:
257 // 'optimizers may change the order of volatile operations relative to
258 // non-volatile operations.'"
259
260 // If a load is seq_cst, it cannot be moved above other loads. If its ordering
261 // is weaker, it can be moved above other loads. We just need to be sure that
262 // MayClobber isn't an acquire load, because loads can't be moved above
263 // acquire loads.
264 //
265 // Note that this explicitly *does* allow the free reordering of monotonic (or
266 // weaker) loads of the same address.
267 bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
268 bool MayClobberIsAcquire = isAtLeastOrStrongerThan(AO: MayClobber->getOrdering(),
269 Other: AtomicOrdering::Acquire);
270 return !(SeqCstUse || MayClobberIsAcquire);
271}
272
273template <typename AliasAnalysisType>
274static bool
275instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc,
276 const Instruction *UseInst, AliasAnalysisType &AA) {
277 Instruction *DefInst = MD->getMemoryInst();
278 assert(DefInst && "Defining instruction not actually an instruction");
279
280 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: DefInst)) {
281 // These intrinsics will show up as affecting memory, but they are just
282 // markers, mostly.
283 //
284 // FIXME: We probably don't actually want MemorySSA to model these at all
285 // (including creating MemoryAccesses for them): we just end up inventing
286 // clobbers where they don't really exist at all. Please see D43269 for
287 // context.
288 switch (II->getIntrinsicID()) {
289 case Intrinsic::allow_runtime_check:
290 case Intrinsic::allow_ubsan_check:
291 case Intrinsic::invariant_start:
292 case Intrinsic::invariant_end:
293 case Intrinsic::assume:
294 case Intrinsic::experimental_noalias_scope_decl:
295 case Intrinsic::pseudoprobe:
296 return false;
297 case Intrinsic::dbg_declare:
298 case Intrinsic::dbg_label:
299 case Intrinsic::dbg_value:
300 llvm_unreachable("debuginfo shouldn't have associated defs!");
301 default:
302 break;
303 }
304 }
305
306 if (auto *CB = dyn_cast_or_null<CallBase>(Val: UseInst)) {
307 ModRefInfo I = AA.getModRefInfo(DefInst, CB);
308 return isModSet(MRI: I);
309 }
310
311 if (auto *DefLoad = dyn_cast<LoadInst>(Val: DefInst))
312 if (auto *UseLoad = dyn_cast_or_null<LoadInst>(Val: UseInst))
313 return !areLoadsReorderable(Use: UseLoad, MayClobber: DefLoad);
314
315 ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
316 return isModSet(MRI: I);
317}
318
319template <typename AliasAnalysisType>
320static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
321 const MemoryLocOrCall &UseMLOC,
322 AliasAnalysisType &AA) {
323 // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
324 // to exist while MemoryLocOrCall is pushed through places.
325 if (UseMLOC.IsCall)
326 return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
327 AA);
328 return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
329 AA);
330}
331
332// Return true when MD may alias MU, return false otherwise.
333bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
334 AliasAnalysis &AA) {
335 return instructionClobbersQuery(MD, MU, UseMLOC: MemoryLocOrCall(MU), AA);
336}
337
338namespace {
339
340struct UpwardsMemoryQuery {
341 // True if our original query started off as a call
342 bool IsCall = false;
343 // The pointer location we started the query with. This will be empty if
344 // IsCall is true.
345 MemoryLocation StartingLoc;
346 // This is the instruction we were querying about.
347 const Instruction *Inst = nullptr;
348 // The MemoryAccess we actually got called with, used to test local domination
349 const MemoryAccess *OriginalAccess = nullptr;
350 bool SkipSelfAccess = false;
351
352 UpwardsMemoryQuery() = default;
353
354 UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
355 : IsCall(isa<CallBase>(Val: Inst)), Inst(Inst), OriginalAccess(Access) {
356 if (!IsCall)
357 StartingLoc = MemoryLocation::get(Inst);
358 }
359};
360
361} // end anonymous namespace
362
363template <typename AliasAnalysisType>
364static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
365 const Instruction *I) {
366 // If the memory can't be changed, then loads of the memory can't be
367 // clobbered.
368 if (I->hasMetadata(KindID: LLVMContext::MD_invariant_load))
369 return true;
370 if (auto *LI = dyn_cast<LoadInst>(Val: I))
371 return !isModSet(AA.getModRefInfoMask(MemoryLocation::get(LI)));
372 return false;
373}
374
375/// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
376/// inbetween `Start` and `ClobberAt` can clobbers `Start`.
377///
378/// This is meant to be as simple and self-contained as possible. Because it
379/// uses no cache, etc., it can be relatively expensive.
380///
381/// \param Start The MemoryAccess that we want to walk from.
382/// \param ClobberAt A clobber for Start.
383/// \param StartLoc The MemoryLocation for Start.
384/// \param MSSA The MemorySSA instance that Start and ClobberAt belong to.
385/// \param Query The UpwardsMemoryQuery we used for our search.
386/// \param AA The AliasAnalysis we used for our search.
387/// \param AllowImpreciseClobber Always false, unless we do relaxed verify.
388
389[[maybe_unused]] static void
390checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt,
391 const MemoryLocation &StartLoc, const MemorySSA &MSSA,
392 const UpwardsMemoryQuery &Query, BatchAAResults &AA,
393 bool AllowImpreciseClobber = false) {
394 assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
395
396 if (MSSA.isLiveOnEntryDef(MA: Start)) {
397 assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
398 "liveOnEntry must clobber itself");
399 return;
400 }
401
402 bool FoundClobber = false;
403 DenseSet<UpwardDefsElem> VisitedPhis;
404 SmallVector<UpwardDefsElem, 8> Worklist;
405 Worklist.push_back(Elt: {.MA: Start, .Loc: StartLoc, /*MayBeCrossIteration=*/false});
406 // Walk all paths from Start to ClobberAt, while looking for clobbers. If one
407 // is found, complain.
408 while (!Worklist.empty()) {
409 auto 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(V: MAP).second)
413 continue;
414
415 for (auto *MA : def_chain(MA: MAP.MA)) {
416 if (MA == ClobberAt) {
417 if (const auto *MD = dyn_cast<MemoryDef>(Val: 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 = FoundClobber || MSSA.isLiveOnEntryDef(MA: MD);
424 if (!FoundClobber) {
425 BatchAACrossIterationScope _(AA, MAP.MayBeCrossIteration);
426 if (instructionClobbersQuery(MD, UseLoc: MAP.Loc, UseInst: Query.Inst, AA))
427 FoundClobber = true;
428 }
429 }
430 break;
431 }
432
433 // We should never hit liveOnEntry, unless it's the clobber.
434 assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
435
436 if (const auto *MD = dyn_cast<MemoryDef>(Val: MA)) {
437 // If Start is a Def, skip self.
438 if (MD == Start)
439 continue;
440
441 BatchAACrossIterationScope _(AA, MAP.MayBeCrossIteration);
442 assert(!instructionClobbersQuery(MD, MAP.Loc, Query.Inst, AA) &&
443 "Found clobber before reaching ClobberAt!");
444 continue;
445 }
446
447 if (const auto *MU = dyn_cast<MemoryUse>(Val: MA)) {
448 (void)MU;
449 assert (MU == Start &&
450 "Can only find use in def chain if Start is a use");
451 continue;
452 }
453
454 assert(isa<MemoryPhi>(MA));
455
456 // Add reachable phi predecessors
457 for (auto ItB = upward_defs_begin(Pair: {.MA: MA, .Loc: MAP.Loc, .MayBeCrossIteration: MAP.MayBeCrossIteration},
458 DT&: MSSA.getDomTree()),
459 ItE = upward_defs_end();
460 ItB != ItE; ++ItB)
461 if (MSSA.getDomTree().isReachableFromEntry(A: ItB.getPhiArgBlock()))
462 Worklist.emplace_back(Args: *ItB);
463 }
464 }
465
466 // If the verify is done following an optimization, it's possible that
467 // ClobberAt was a conservative clobbering, that we can now infer is not a
468 // true clobbering access. Don't fail the verify if that's the case.
469 // We do have accesses that claim they're optimized, but could be optimized
470 // further. Updating all these can be expensive, so allow it for now (FIXME).
471 if (AllowImpreciseClobber)
472 return;
473
474 // If ClobberAt is a MemoryPhi, we can assume something above it acted as a
475 // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point.
476 assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
477 "ClobberAt never acted as a clobber");
478}
479
480namespace {
481
482/// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
483/// in one class.
484class ClobberWalker {
485 /// Save a few bytes by using unsigned instead of size_t.
486 using ListIndex = unsigned;
487
488 /// Represents a span of contiguous MemoryDefs, potentially ending in a
489 /// MemoryPhi.
490 struct DefPath {
491 MemoryLocation Loc;
492 // Note that, because we always walk in reverse, Last will always dominate
493 // First. Also note that First and Last are inclusive.
494 MemoryAccess *First;
495 MemoryAccess *Last;
496 std::optional<ListIndex> Previous;
497 bool MayBeCrossIteration;
498
499 DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
500 bool MayBeCrossIteration, std::optional<ListIndex> Previous)
501 : Loc(Loc), First(First), Last(Last), Previous(Previous),
502 MayBeCrossIteration(MayBeCrossIteration) {}
503
504 DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
505 bool MayBeCrossIteration, std::optional<ListIndex> Previous)
506 : DefPath(Loc, Init, Init, MayBeCrossIteration, Previous) {}
507 };
508
509 const MemorySSA &MSSA;
510 DominatorTree &DT;
511 BatchAAResults *AA;
512 UpwardsMemoryQuery *Query;
513 unsigned *UpwardWalkLimit;
514
515 // Phi optimization bookkeeping:
516 // List of DefPath to process during the current phi optimization walk.
517 SmallVector<DefPath, 32> Paths;
518 // List of visited <Access, Location> pairs; we can skip paths already
519 // visited with the same memory location.
520 DenseSet<UpwardDefsElem> VisitedPhis;
521
522 /// Find the nearest def or phi that `From` can legally be optimized to.
523 const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
524 assert(From->getNumOperands() && "Phi with no operands?");
525
526 BasicBlock *BB = From->getBlock();
527 MemoryAccess *Result = MSSA.getLiveOnEntryDef();
528 DomTreeNode *Node = DT.getNode(BB);
529 while ((Node = Node->getIDom())) {
530 auto *Defs = MSSA.getBlockDefs(BB: Node->getBlock());
531 if (Defs)
532 return &*Defs->rbegin();
533 }
534 return Result;
535 }
536
537 /// Result of calling walkToPhiOrClobber.
538 struct UpwardsWalkResult {
539 /// The "Result" of the walk. Either a clobber, the last thing we walked, or
540 /// both. Include alias info when clobber found.
541 MemoryAccess *Result;
542 bool IsKnownClobber;
543 };
544
545 /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
546 /// This will update Desc.Last as it walks. It will (optionally) also stop at
547 /// StopAt.
548 ///
549 /// This does not test for whether StopAt is a clobber
550 UpwardsWalkResult
551 walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
552 const MemoryAccess *SkipStopAt = nullptr) const {
553 assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
554 assert(UpwardWalkLimit && "Need a valid walk limit");
555 bool LimitAlreadyReached = false;
556 // (*UpwardWalkLimit) may be 0 here, due to the loop in tryOptimizePhi. Set
557 // it to 1. This will not do any alias() calls. It either returns in the
558 // first iteration in the loop below, or is set back to 0 if all def chains
559 // are free of MemoryDefs.
560 if (!*UpwardWalkLimit) {
561 *UpwardWalkLimit = 1;
562 LimitAlreadyReached = true;
563 }
564
565 for (MemoryAccess *Current : def_chain(MA: Desc.Last)) {
566 Desc.Last = Current;
567 if (Current == StopAt || Current == SkipStopAt)
568 return {.Result: Current, .IsKnownClobber: false};
569
570 if (auto *MD = dyn_cast<MemoryDef>(Val: Current)) {
571 if (MSSA.isLiveOnEntryDef(MA: MD))
572 return {.Result: MD, .IsKnownClobber: true};
573
574 if (!--*UpwardWalkLimit)
575 return {.Result: Current, .IsKnownClobber: true};
576
577 BatchAACrossIterationScope _(*AA, Desc.MayBeCrossIteration);
578 if (instructionClobbersQuery(MD, UseLoc: Desc.Loc, UseInst: Query->Inst, AA&: *AA))
579 return {.Result: MD, .IsKnownClobber: true};
580 }
581 }
582
583 if (LimitAlreadyReached)
584 *UpwardWalkLimit = 0;
585
586 assert(isa<MemoryPhi>(Desc.Last) &&
587 "Ended at a non-clobber that's not a phi?");
588 return {.Result: Desc.Last, .IsKnownClobber: false};
589 }
590
591 void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
592 ListIndex PriorNode, bool MayBeCrossIteration) {
593 auto UpwardDefsBegin =
594 upward_defs_begin(Pair: {.MA: Phi, .Loc: Paths[PriorNode].Loc, .MayBeCrossIteration: MayBeCrossIteration}, DT);
595 auto UpwardDefs = make_range(x: UpwardDefsBegin, y: upward_defs_end());
596 for (const UpwardDefsElem &E : UpwardDefs) {
597 PausedSearches.push_back(Elt: Paths.size());
598 Paths.emplace_back(Args: E.Loc, Args: E.MA, Args: E.MayBeCrossIteration, Args&: PriorNode);
599 }
600 }
601
602 /// Represents a search that terminated after finding a clobber. This clobber
603 /// may or may not be present in the path of defs from LastNode..SearchStart,
604 /// since it may have been retrieved from cache.
605 struct TerminatedPath {
606 MemoryAccess *Clobber;
607 ListIndex LastNode;
608 };
609
610 /// Get an access that keeps us from optimizing to the given phi.
611 ///
612 /// PausedSearches is an array of indices into the Paths array. Its incoming
613 /// value is the indices of searches that stopped at the last phi optimization
614 /// target. It's left in an unspecified state.
615 ///
616 /// If this returns std::nullopt, NewPaused is a vector of searches that
617 /// terminated at StopWhere. Otherwise, NewPaused is left in an unspecified
618 /// state.
619 std::optional<TerminatedPath>
620 getBlockingAccess(const MemoryAccess *StopWhere,
621 SmallVectorImpl<ListIndex> &PausedSearches,
622 SmallVectorImpl<ListIndex> &NewPaused,
623 SmallVectorImpl<TerminatedPath> &Terminated) {
624 assert(!PausedSearches.empty() && "No searches to continue?");
625
626 // BFS vs DFS really doesn't make a difference here, so just do a DFS with
627 // PausedSearches as our stack.
628 while (!PausedSearches.empty()) {
629 ListIndex PathIndex = PausedSearches.pop_back_val();
630 DefPath &Node = Paths[PathIndex];
631
632 // If we've already visited this path with this MemoryLocation, we don't
633 // need to do so again.
634 //
635 // NOTE: That we just drop these paths on the ground makes caching
636 // behavior sporadic. e.g. given a diamond:
637 // A
638 // B C
639 // D
640 //
641 // ...If we walk D, B, A, C, we'll only cache the result of phi
642 // optimization for A, B, and D; C will be skipped because it dies here.
643 // This arguably isn't the worst thing ever, since:
644 // - We generally query things in a top-down order, so if we got below D
645 // without needing cache entries for {C, MemLoc}, then chances are
646 // that those cache entries would end up ultimately unused.
647 // - We still cache things for A, so C only needs to walk up a bit.
648 // If this behavior becomes problematic, we can fix without a ton of extra
649 // work.
650 if (!VisitedPhis.insert(V: {.MA: Node.Last, .Loc: Node.Loc, .MayBeCrossIteration: Node.MayBeCrossIteration})
651 .second)
652 continue;
653
654 const MemoryAccess *SkipStopWhere = nullptr;
655 if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
656 assert(isa<MemoryDef>(Query->OriginalAccess));
657 SkipStopWhere = Query->OriginalAccess;
658 }
659
660 UpwardsWalkResult Res = walkToPhiOrClobber(Desc&: Node,
661 /*StopAt=*/StopWhere,
662 /*SkipStopAt=*/SkipStopWhere);
663 if (Res.IsKnownClobber) {
664 assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
665
666 // If this wasn't a cache hit, we hit a clobber when walking. That's a
667 // failure.
668 TerminatedPath Term{.Clobber: Res.Result, .LastNode: PathIndex};
669 if (!MSSA.dominates(A: Res.Result, B: StopWhere))
670 return Term;
671
672 // Otherwise, it's a valid thing to potentially optimize to.
673 Terminated.push_back(Elt: Term);
674 continue;
675 }
676
677 if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
678 // We've hit our target. Save this path off for if we want to continue
679 // walking. If we are in the mode of skipping the OriginalAccess, and
680 // we've reached back to the OriginalAccess, do not save path, we've
681 // just looped back to self.
682 if (Res.Result != SkipStopWhere)
683 NewPaused.push_back(Elt: PathIndex);
684 continue;
685 }
686
687 assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber");
688 addSearches(Phi: cast<MemoryPhi>(Val: Res.Result), PausedSearches, PriorNode: PathIndex,
689 MayBeCrossIteration: Node.MayBeCrossIteration);
690 }
691
692 return std::nullopt;
693 }
694
695 template <typename T, typename Walker>
696 struct generic_def_path_iterator
697 : public iterator_facade_base<generic_def_path_iterator<T, Walker>,
698 std::forward_iterator_tag, T *> {
699 generic_def_path_iterator() = default;
700 generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {}
701
702 T &operator*() const { return curNode(); }
703
704 generic_def_path_iterator &operator++() {
705 N = curNode().Previous;
706 return *this;
707 }
708
709 bool operator==(const generic_def_path_iterator &O) const {
710 if (N.has_value() != O.N.has_value())
711 return false;
712 return !N || *N == *O.N;
713 }
714
715 private:
716 T &curNode() const { return W->Paths[*N]; }
717
718 Walker *W = nullptr;
719 std::optional<ListIndex> N;
720 };
721
722 using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
723 using const_def_path_iterator =
724 generic_def_path_iterator<const DefPath, const ClobberWalker>;
725
726 iterator_range<def_path_iterator> def_path(ListIndex From) {
727 return make_range(x: def_path_iterator(this, From), y: def_path_iterator());
728 }
729
730 iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const {
731 return make_range(x: const_def_path_iterator(this, From),
732 y: const_def_path_iterator());
733 }
734
735 struct OptznResult {
736 /// The path that contains our result.
737 TerminatedPath PrimaryClobber;
738 /// The paths that we can legally cache back from, but that aren't
739 /// necessarily the result of the Phi optimization.
740 SmallVector<TerminatedPath, 4> OtherClobbers;
741 };
742
743 ListIndex defPathIndex(const DefPath &N) const {
744 // The assert looks nicer if we don't need to do &N
745 const DefPath *NP = &N;
746 assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&
747 "Out of bounds DefPath!");
748 return NP - &Paths.front();
749 }
750
751 /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths
752 /// that act as legal clobbers. Note that this won't return *all* clobbers.
753 ///
754 /// Phi optimization algorithm tl;dr:
755 /// - Find the earliest def/phi, A, we can optimize to
756 /// - Find if all paths from the starting memory access ultimately reach A
757 /// - If not, optimization isn't possible.
758 /// - Otherwise, walk from A to another clobber or phi, A'.
759 /// - If A' is a def, we're done.
760 /// - If A' is a phi, try to optimize it.
761 ///
762 /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
763 /// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
764 OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
765 const MemoryLocation &Loc) {
766 assert(Paths.empty() && VisitedPhis.empty() &&
767 "Reset the optimization state.");
768
769 Paths.emplace_back(Args: Loc, Args&: Start, Args&: Phi, /*MayBeCrossIteration=*/Args: false,
770 Args: std::nullopt);
771 // Stores how many "valid" optimization nodes we had prior to calling
772 // addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
773 auto PriorPathsSize = Paths.size();
774
775 SmallVector<ListIndex, 16> PausedSearches;
776 SmallVector<ListIndex, 8> NewPaused;
777 SmallVector<TerminatedPath, 4> TerminatedPaths;
778
779 addSearches(Phi, PausedSearches, PriorNode: 0, /*MayBeCrossIteration=*/false);
780
781 // Moves the TerminatedPath with the "most dominated" Clobber to the end of
782 // Paths.
783 auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) {
784 assert(!Paths.empty() && "Need a path to move");
785 auto Dom = Paths.begin();
786 for (auto I = std::next(x: Dom), E = Paths.end(); I != E; ++I)
787 if (!MSSA.dominates(A: I->Clobber, B: Dom->Clobber))
788 Dom = I;
789 auto Last = Paths.end() - 1;
790 if (Last != Dom)
791 std::iter_swap(a: Last, b: Dom);
792 };
793
794 MemoryPhi *Current = Phi;
795 while (true) {
796 assert(!MSSA.isLiveOnEntryDef(Current) &&
797 "liveOnEntry wasn't treated as a clobber?");
798
799 const auto *Target = getWalkTarget(From: Current);
800 // If a TerminatedPath doesn't dominate Target, then it wasn't a legal
801 // optimization for the prior phi.
802 assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {
803 return MSSA.dominates(P.Clobber, Target);
804 }));
805
806 // FIXME: This is broken, because the Blocker may be reported to be
807 // liveOnEntry, and we'll happily wait for that to disappear (read: never)
808 // For the moment, this is fine, since we do nothing with blocker info.
809 if (std::optional<TerminatedPath> Blocker = getBlockingAccess(
810 StopWhere: Target, PausedSearches, NewPaused, Terminated&: TerminatedPaths)) {
811
812 // Find the node we started at. We can't search based on N->Last, since
813 // we may have gone around a loop with a different MemoryLocation.
814 auto Iter = find_if(Range: def_path(From: Blocker->LastNode), P: [&](const DefPath &N) {
815 return defPathIndex(N) < PriorPathsSize;
816 });
817 assert(Iter != def_path_iterator());
818
819 DefPath &CurNode = *Iter;
820 assert(CurNode.Last == Current);
821
822 // Two things:
823 // A. We can't reliably cache all of NewPaused back. Consider a case
824 // where we have two paths in NewPaused; one of which can't optimize
825 // above this phi, whereas the other can. If we cache the second path
826 // back, we'll end up with suboptimal cache entries. We can handle
827 // cases like this a bit better when we either try to find all
828 // clobbers that block phi optimization, or when our cache starts
829 // supporting unfinished searches.
830 // B. We can't reliably cache TerminatedPaths back here without doing
831 // extra checks; consider a case like:
832 // T
833 // / \
834 // D C
835 // \ /
836 // S
837 // Where T is our target, C is a node with a clobber on it, D is a
838 // diamond (with a clobber *only* on the left or right node, N), and
839 // S is our start. Say we walk to D, through the node opposite N
840 // (read: ignoring the clobber), and see a cache entry in the top
841 // node of D. That cache entry gets put into TerminatedPaths. We then
842 // walk up to C (N is later in our worklist), find the clobber, and
843 // quit. If we append TerminatedPaths to OtherClobbers, we'll cache
844 // the bottom part of D to the cached clobber, ignoring the clobber
845 // in N. Again, this problem goes away if we start tracking all
846 // blockers for a given phi optimization.
847 TerminatedPath Result{.Clobber: CurNode.Last, .LastNode: defPathIndex(N: CurNode)};
848 return {.PrimaryClobber: Result, .OtherClobbers: {}};
849 }
850
851 // If there's nothing left to search, then all paths led to valid clobbers
852 // that we got from our cache; pick the nearest to the start, and allow
853 // the rest to be cached back.
854 if (NewPaused.empty()) {
855 MoveDominatedPathToEnd(TerminatedPaths);
856 TerminatedPath Result = TerminatedPaths.pop_back_val();
857 return {.PrimaryClobber: Result, .OtherClobbers: std::move(TerminatedPaths)};
858 }
859
860 MemoryAccess *DefChainEnd = nullptr;
861 SmallVector<TerminatedPath, 4> Clobbers;
862 for (ListIndex Paused : NewPaused) {
863 UpwardsWalkResult WR = walkToPhiOrClobber(Desc&: Paths[Paused]);
864 if (WR.IsKnownClobber)
865 Clobbers.push_back(Elt: {.Clobber: WR.Result, .LastNode: Paused});
866 else
867 // Micro-opt: If we hit the end of the chain, save it.
868 DefChainEnd = WR.Result;
869 }
870
871 if (!TerminatedPaths.empty()) {
872 // If we couldn't find the dominating phi/liveOnEntry in the above loop,
873 // do it now.
874 if (!DefChainEnd)
875 for (auto *MA : def_chain(MA: const_cast<MemoryAccess *>(Target)))
876 DefChainEnd = MA;
877 assert(DefChainEnd && "Failed to find dominating phi/liveOnEntry");
878
879 // If any of the terminated paths don't dominate the phi we'll try to
880 // optimize, we need to figure out what they are and quit.
881 const BasicBlock *ChainBB = DefChainEnd->getBlock();
882 for (const TerminatedPath &TP : TerminatedPaths) {
883 // Because we know that DefChainEnd is as "high" as we can go, we
884 // don't need local dominance checks; BB dominance is sufficient.
885 if (DT.dominates(A: ChainBB, B: TP.Clobber->getBlock()))
886 Clobbers.push_back(Elt: TP);
887 }
888 }
889
890 // If we have clobbers in the def chain, find the one closest to Current
891 // and quit.
892 if (!Clobbers.empty()) {
893 MoveDominatedPathToEnd(Clobbers);
894 TerminatedPath Result = Clobbers.pop_back_val();
895 return {.PrimaryClobber: Result, .OtherClobbers: std::move(Clobbers)};
896 }
897
898 assert(all_of(NewPaused,
899 [&](ListIndex I) { return Paths[I].Last == DefChainEnd; }));
900
901 // Because liveOnEntry is a clobber, this must be a phi.
902 auto *DefChainPhi = cast<MemoryPhi>(Val: DefChainEnd);
903
904 PriorPathsSize = Paths.size();
905 PausedSearches.clear();
906 for (ListIndex I : NewPaused)
907 addSearches(Phi: DefChainPhi, PausedSearches, PriorNode: I,
908 MayBeCrossIteration: Paths[I].MayBeCrossIteration);
909 NewPaused.clear();
910
911 Current = DefChainPhi;
912 }
913 }
914
915 void verifyOptResult(const OptznResult &R) const {
916 assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
917 return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
918 }));
919 }
920
921 void resetPhiOptznState() {
922 Paths.clear();
923 VisitedPhis.clear();
924 }
925
926public:
927 ClobberWalker(const MemorySSA &MSSA, DominatorTree &DT)
928 : MSSA(MSSA), DT(DT) {}
929
930 /// Finds the nearest clobber for the given query, optimizing phis if
931 /// possible.
932 MemoryAccess *findClobber(BatchAAResults &BAA, MemoryAccess *Start,
933 UpwardsMemoryQuery &Q, unsigned &UpWalkLimit) {
934 AA = &BAA;
935 Query = &Q;
936 UpwardWalkLimit = &UpWalkLimit;
937 // Starting limit must be > 0.
938 if (!UpWalkLimit)
939 UpWalkLimit++;
940
941 MemoryAccess *Current = Start;
942 // This walker pretends uses don't exist. If we're handed one, silently grab
943 // its def. (This has the nice side-effect of ensuring we never cache uses)
944 if (auto *MU = dyn_cast<MemoryUse>(Val: Start))
945 Current = MU->getDefiningAccess();
946
947 DefPath FirstDesc(Q.StartingLoc, Current, Current,
948 /*MayBeCrossIteration=*/false, std::nullopt);
949 // Fast path for the overly-common case (no crazy phi optimization
950 // necessary)
951 UpwardsWalkResult WalkResult = walkToPhiOrClobber(Desc&: FirstDesc);
952 MemoryAccess *Result;
953 if (WalkResult.IsKnownClobber) {
954 Result = WalkResult.Result;
955 } else {
956 OptznResult OptRes = tryOptimizePhi(Phi: cast<MemoryPhi>(Val: FirstDesc.Last),
957 Start: Current, Loc: Q.StartingLoc);
958 verifyOptResult(R: OptRes);
959 resetPhiOptznState();
960 Result = OptRes.PrimaryClobber.Clobber;
961 }
962
963#ifdef EXPENSIVE_CHECKS
964 if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
965 checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, BAA);
966#endif
967 return Result;
968 }
969};
970
971struct 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
980 void swap(RenamePassData &RHS) {
981 std::swap(a&: DTN, b&: RHS.DTN);
982 std::swap(a&: ChildIt, b&: RHS.ChildIt);
983 std::swap(a&: IncomingVal, b&: RHS.IncomingVal);
984 }
985};
986
987} // end anonymous namespace
988
989namespace llvm {
990
991class MemorySSA::ClobberWalkerBase {
992 ClobberWalker Walker;
993 MemorySSA *MSSA;
994
995public:
996 ClobberWalkerBase(MemorySSA *M, DominatorTree *D) : Walker(*M, *D), MSSA(M) {}
997
998 MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
999 const MemoryLocation &,
1000 BatchAAResults &, unsigned &);
1001 // Third argument (bool), defines whether the clobber search should skip the
1002 // original queried access. If true, there will be a follow-up query searching
1003 // for a clobber access past "self". Note that the Optimized access is not
1004 // updated if a new clobber is found by this SkipSelf search. If this
1005 // additional query becomes heavily used we may decide to cache the result.
1006 // Walker instantiations will decide how to set the SkipSelf bool.
1007 MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, BatchAAResults &,
1008 unsigned &, bool,
1009 bool UseInvariantGroup = true);
1010};
1011
1012/// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
1013/// longer does caching on its own, but the name has been retained for the
1014/// moment.
1015class MemorySSA::CachingWalker final : public MemorySSAWalker {
1016 ClobberWalkerBase *Walker;
1017
1018public:
1019 CachingWalker(MemorySSA *M, ClobberWalkerBase *W)
1020 : MemorySSAWalker(M), Walker(W) {}
1021 ~CachingWalker() override = default;
1022
1023 using MemorySSAWalker::getClobberingMemoryAccess;
1024
1025 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, BatchAAResults &BAA,
1026 unsigned &UWL) {
1027 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false);
1028 }
1029 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1030 const MemoryLocation &Loc,
1031 BatchAAResults &BAA, unsigned &UWL) {
1032 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1033 }
1034 // This method is not accessible outside of this file.
1035 MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(
1036 MemoryAccess *MA, BatchAAResults &BAA, unsigned &UWL) {
1037 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false, UseInvariantGroup: false);
1038 }
1039
1040 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1041 BatchAAResults &BAA) override {
1042 unsigned UpwardWalkLimit = MaxCheckLimit;
1043 return getClobberingMemoryAccess(MA, BAA, UWL&: UpwardWalkLimit);
1044 }
1045 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1046 const MemoryLocation &Loc,
1047 BatchAAResults &BAA) override {
1048 unsigned UpwardWalkLimit = MaxCheckLimit;
1049 return getClobberingMemoryAccess(MA, Loc, BAA, UWL&: UpwardWalkLimit);
1050 }
1051
1052 void invalidateInfo(MemoryAccess *MA) override {
1053 if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1054 MUD->resetOptimized();
1055 }
1056};
1057
1058class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
1059 ClobberWalkerBase *Walker;
1060
1061public:
1062 SkipSelfWalker(MemorySSA *M, ClobberWalkerBase *W)
1063 : MemorySSAWalker(M), Walker(W) {}
1064 ~SkipSelfWalker() override = default;
1065
1066 using MemorySSAWalker::getClobberingMemoryAccess;
1067
1068 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, BatchAAResults &BAA,
1069 unsigned &UWL) {
1070 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, true);
1071 }
1072 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1073 const MemoryLocation &Loc,
1074 BatchAAResults &BAA, unsigned &UWL) {
1075 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1076 }
1077
1078 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1079 BatchAAResults &BAA) override {
1080 unsigned UpwardWalkLimit = MaxCheckLimit;
1081 return getClobberingMemoryAccess(MA, BAA, UWL&: UpwardWalkLimit);
1082 }
1083 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1084 const MemoryLocation &Loc,
1085 BatchAAResults &BAA) override {
1086 unsigned UpwardWalkLimit = MaxCheckLimit;
1087 return getClobberingMemoryAccess(MA, Loc, BAA, UWL&: UpwardWalkLimit);
1088 }
1089
1090 void invalidateInfo(MemoryAccess *MA) override {
1091 if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1092 MUD->resetOptimized();
1093 }
1094};
1095
1096} // end namespace llvm
1097
1098void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
1099 bool RenameAllUses) {
1100 // Pass through values to our successors
1101 for (const BasicBlock *S : successors(BB)) {
1102 auto It = PerBlockAccesses.find(Val: S);
1103 // Rename the phi nodes in our successor block
1104 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(Val: It->second->front()))
1105 continue;
1106 AccessList *Accesses = It->second.get();
1107 auto *Phi = cast<MemoryPhi>(Val: &Accesses->front());
1108 if (RenameAllUses) {
1109 bool ReplacementDone = false;
1110 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
1111 if (Phi->getIncomingBlock(I) == BB) {
1112 Phi->setIncomingValue(I, V: IncomingVal);
1113 ReplacementDone = true;
1114 }
1115 (void) ReplacementDone;
1116 assert(ReplacementDone && "Incomplete phi during partial rename");
1117 } else
1118 Phi->addIncoming(V: IncomingVal, BB);
1119 }
1120}
1121
1122/// Rename a single basic block into MemorySSA form.
1123/// Uses the standard SSA renaming algorithm.
1124/// \returns The new incoming value.
1125MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal,
1126 bool RenameAllUses) {
1127 auto It = PerBlockAccesses.find(Val: BB);
1128 // Skip most processing if the list is empty.
1129 if (It != PerBlockAccesses.end()) {
1130 AccessList *Accesses = It->second.get();
1131 for (MemoryAccess &L : *Accesses) {
1132 if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(Val: &L)) {
1133 if (MUD->getDefiningAccess() == nullptr || RenameAllUses)
1134 MUD->setDefiningAccess(DMA: IncomingVal);
1135 if (isa<MemoryDef>(Val: &L))
1136 IncomingVal = &L;
1137 } else {
1138 IncomingVal = &L;
1139 }
1140 }
1141 }
1142 return IncomingVal;
1143}
1144
1145/// This is the standard SSA renaming algorithm.
1146///
1147/// We walk the dominator tree in preorder, renaming accesses, and then filling
1148/// in phi nodes in our successors.
1149void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
1150 SmallPtrSetImpl<BasicBlock *> &Visited,
1151 bool SkipVisited, bool RenameAllUses) {
1152 assert(Root && "Trying to rename accesses in an unreachable block");
1153
1154 SmallVector<RenamePassData, 32> WorkStack;
1155 // Skip everything if we already renamed this block and we are skipping.
1156 // Note: You can't sink this into the if, because we need it to occur
1157 // regardless of whether we skip blocks or not.
1158 bool AlreadyVisited = !Visited.insert(Ptr: Root->getBlock()).second;
1159 if (SkipVisited && AlreadyVisited)
1160 return;
1161
1162 IncomingVal = renameBlock(BB: Root->getBlock(), IncomingVal, RenameAllUses);
1163 renameSuccessorPhis(BB: Root->getBlock(), IncomingVal, RenameAllUses);
1164 WorkStack.push_back(Elt: {Root, Root->begin(), IncomingVal});
1165
1166 while (!WorkStack.empty()) {
1167 DomTreeNode *Node = WorkStack.back().DTN;
1168 DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
1169 IncomingVal = WorkStack.back().IncomingVal;
1170
1171 if (ChildIt == Node->end()) {
1172 WorkStack.pop_back();
1173 } else {
1174 DomTreeNode *Child = *ChildIt;
1175 ++WorkStack.back().ChildIt;
1176 BasicBlock *BB = Child->getBlock();
1177 // Note: You can't sink this into the if, because we need it to occur
1178 // regardless of whether we skip blocks or not.
1179 AlreadyVisited = !Visited.insert(Ptr: BB).second;
1180 if (SkipVisited && AlreadyVisited) {
1181 // We already visited this during our renaming, which can happen when
1182 // being asked to rename multiple blocks. Figure out the incoming val,
1183 // which is the last def.
1184 // Incoming value can only change if there is a block def, and in that
1185 // case, it's the last block def in the list.
1186 if (auto *BlockDefs = getBlockDefs(BB))
1187 IncomingVal = &*BlockDefs->rbegin();
1188 } else
1189 IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1190 renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1191 WorkStack.push_back(Elt: {Child, Child->begin(), IncomingVal});
1192 }
1193 }
1194}
1195
1196/// This handles unreachable block accesses by deleting phi nodes in
1197/// unreachable blocks, and marking all other unreachable MemoryAccess's as
1198/// being uses of the live on entry definition.
1199void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
1200 assert(!DT->isReachableFromEntry(BB) &&
1201 "Reachable block found while handling unreachable blocks");
1202
1203 // Make sure phi nodes in our reachable successors end up with a
1204 // LiveOnEntryDef for our incoming edge, even though our block is forward
1205 // unreachable. We could just disconnect these blocks from the CFG fully,
1206 // but we do not right now.
1207 for (const BasicBlock *S : successors(BB)) {
1208 if (!DT->isReachableFromEntry(A: S))
1209 continue;
1210 auto It = PerBlockAccesses.find(Val: S);
1211 // Rename the phi nodes in our successor block
1212 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(Val: It->second->front()))
1213 continue;
1214 AccessList *Accesses = It->second.get();
1215 auto *Phi = cast<MemoryPhi>(Val: &Accesses->front());
1216 Phi->addIncoming(V: LiveOnEntryDef.get(), BB);
1217 }
1218
1219 auto It = PerBlockAccesses.find(Val: BB);
1220 if (It == PerBlockAccesses.end())
1221 return;
1222
1223 auto &Accesses = It->second;
1224 for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1225 auto Next = std::next(x: AI);
1226 // If we have a phi, just remove it. We are going to replace all
1227 // users with live on entry.
1228 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(Val&: AI))
1229 UseOrDef->setDefiningAccess(DMA: LiveOnEntryDef.get());
1230 else
1231 Accesses->erase(where: AI);
1232 AI = Next;
1233 }
1234}
1235
1236MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
1237 : DT(DT), F(&Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1238 SkipWalker(nullptr) {
1239 // Build MemorySSA using a batch alias analysis. This reuses the internal
1240 // state that AA collects during an alias()/getModRefInfo() call. This is
1241 // safe because there are no CFG changes while building MemorySSA and can
1242 // significantly reduce the time spent by the compiler in AA, because we will
1243 // make queries about all the instructions in the Function.
1244 assert(AA && "No alias analysis?");
1245 BatchAAResults BatchAA(*AA);
1246 buildMemorySSA(BAA&: BatchAA, Blocks: iterator_range(F->begin(), F->end()));
1247 // Intentionally leave AA to nullptr while building so we don't accidentally
1248 // use non-batch AliasAnalysis.
1249 this->AA = AA;
1250 // Also create the walker here.
1251 getWalker();
1252}
1253
1254MemorySSA::MemorySSA(Loop &L, AliasAnalysis *AA, DominatorTree *DT)
1255 : DT(DT), L(&L), LiveOnEntryDef(nullptr), Walker(nullptr),
1256 SkipWalker(nullptr) {
1257 // Build MemorySSA using a batch alias analysis. This reuses the internal
1258 // state that AA collects during an alias()/getModRefInfo() call. This is
1259 // safe because there are no CFG changes while building MemorySSA and can
1260 // significantly reduce the time spent by the compiler in AA, because we will
1261 // make queries about all the instructions in the Function.
1262 assert(AA && "No alias analysis?");
1263 BatchAAResults BatchAA(*AA);
1264 buildMemorySSA(
1265 BAA&: BatchAA, Blocks: map_range(C: L.blocks(), F: [](const BasicBlock *BB) -> BasicBlock & {
1266 return *const_cast<BasicBlock *>(BB);
1267 }));
1268 // Intentionally leave AA to nullptr while building so we don't accidentally
1269 // use non-batch AliasAnalysis.
1270 this->AA = AA;
1271 // Also create the walker here.
1272 getWalker();
1273}
1274
1275MemorySSA::~MemorySSA() {
1276 // Drop all our references
1277 for (const auto &Pair : PerBlockAccesses)
1278 for (MemoryAccess &MA : *Pair.second)
1279 MA.dropAllReferences();
1280}
1281
1282MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) {
1283 auto Res = PerBlockAccesses.try_emplace(Key: BB);
1284
1285 if (Res.second)
1286 Res.first->second = std::make_unique<AccessList>();
1287 return Res.first->second.get();
1288}
1289
1290MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) {
1291 auto Res = PerBlockDefs.try_emplace(Key: BB);
1292
1293 if (Res.second)
1294 Res.first->second = std::make_unique<DefsList>();
1295 return Res.first->second.get();
1296}
1297
1298namespace llvm {
1299
1300/// This class is a batch walker of all MemoryUse's in the program, and points
1301/// their defining access at the thing that actually clobbers them. Because it
1302/// is a batch walker that touches everything, it does not operate like the
1303/// other walkers. This walker is basically performing a top-down SSA renaming
1304/// pass, where the version stack is used as the cache. This enables it to be
1305/// significantly more time and memory efficient than using the regular walker,
1306/// which is walking bottom-up.
1307class MemorySSA::OptimizeUses {
1308public:
1309 OptimizeUses(MemorySSA *MSSA, CachingWalker *Walker, BatchAAResults *BAA,
1310 DominatorTree *DT)
1311 : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1312
1313 void optimizeUses();
1314
1315private:
1316 /// This represents where a given memorylocation is in the stack.
1317 struct MemlocStackInfo {
1318 // This essentially is keeping track of versions of the stack. Whenever
1319 // the stack changes due to pushes or pops, these versions increase.
1320 unsigned long StackEpoch;
1321 unsigned long PopEpoch;
1322 // This is the lower bound of places on the stack to check. It is equal to
1323 // the place the last stack walk ended.
1324 // Note: Correctness depends on this being initialized to 0, which densemap
1325 // does
1326 unsigned long LowerBound;
1327 const BasicBlock *LowerBoundBlock;
1328 // This is where the last walk for this memory location ended.
1329 unsigned long LastKill;
1330 bool LastKillValid;
1331 };
1332
1333 void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
1334 SmallVectorImpl<MemoryAccess *> &,
1335 DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
1336
1337 MemorySSA *MSSA;
1338 CachingWalker *Walker;
1339 BatchAAResults *AA;
1340 DominatorTree *DT;
1341};
1342
1343} // end namespace llvm
1344
1345/// Optimize the uses in a given block This is basically the SSA renaming
1346/// algorithm, with one caveat: We are able to use a single stack for all
1347/// MemoryUses. This is because the set of *possible* reaching MemoryDefs is
1348/// the same for every MemoryUse. The *actual* clobbering MemoryDef is just
1349/// going to be some position in that stack of possible ones.
1350///
1351/// We track the stack positions that each MemoryLocation needs
1352/// to check, and last ended at. This is because we only want to check the
1353/// things that changed since last time. The same MemoryLocation should
1354/// get clobbered by the same store (getModRefInfo does not use invariantness or
1355/// things like this, and if they start, we can modify MemoryLocOrCall to
1356/// include relevant data)
1357void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1358 const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch,
1359 SmallVectorImpl<MemoryAccess *> &VersionStack,
1360 DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) {
1361
1362 /// If no accesses, nothing to do.
1363 MemorySSA::AccessList *Accesses = MSSA->getBlockAccesses(BB);
1364 if (Accesses == nullptr)
1365 return;
1366
1367 // Pop everything that doesn't dominate the current block off the stack,
1368 // increment the PopEpoch to account for this.
1369 while (true) {
1370 assert(
1371 !VersionStack.empty() &&
1372 "Version stack should have liveOnEntry sentinel dominating everything");
1373 BasicBlock *BackBlock = VersionStack.back()->getBlock();
1374 if (DT->dominates(A: BackBlock, B: BB))
1375 break;
1376 while (VersionStack.back()->getBlock() == BackBlock)
1377 VersionStack.pop_back();
1378 ++PopEpoch;
1379 }
1380
1381 for (MemoryAccess &MA : *Accesses) {
1382 auto *MU = dyn_cast<MemoryUse>(Val: &MA);
1383 if (!MU) {
1384 VersionStack.push_back(Elt: &MA);
1385 ++StackEpoch;
1386 continue;
1387 }
1388
1389 if (MU->isOptimized())
1390 continue;
1391
1392 MemoryLocOrCall UseMLOC(MU);
1393 auto &LocInfo = LocStackInfo[UseMLOC];
1394 // If the pop epoch changed, it means we've removed stuff from top of
1395 // stack due to changing blocks. We may have to reset the lower bound or
1396 // last kill info.
1397 if (LocInfo.PopEpoch != PopEpoch) {
1398 LocInfo.PopEpoch = PopEpoch;
1399 LocInfo.StackEpoch = StackEpoch;
1400 // If the lower bound was in something that no longer dominates us, we
1401 // have to reset it.
1402 // We can't simply track stack size, because the stack may have had
1403 // pushes/pops in the meantime.
1404 // XXX: This is non-optimal, but only is slower cases with heavily
1405 // branching dominator trees. To get the optimal number of queries would
1406 // be to make lowerbound and lastkill a per-loc stack, and pop it until
1407 // the top of that stack dominates us. This does not seem worth it ATM.
1408 // A much cheaper optimization would be to always explore the deepest
1409 // branch of the dominator tree first. This will guarantee this resets on
1410 // the smallest set of blocks.
1411 if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1412 !DT->dominates(A: LocInfo.LowerBoundBlock, B: BB)) {
1413 // Reset the lower bound of things to check.
1414 // TODO: Some day we should be able to reset to last kill, rather than
1415 // 0.
1416 LocInfo.LowerBound = 0;
1417 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1418 LocInfo.LastKillValid = false;
1419 }
1420 } else if (LocInfo.StackEpoch != StackEpoch) {
1421 // If all that has changed is the StackEpoch, we only have to check the
1422 // new things on the stack, because we've checked everything before. In
1423 // this case, the lower bound of things to check remains the same.
1424 LocInfo.PopEpoch = PopEpoch;
1425 LocInfo.StackEpoch = StackEpoch;
1426 }
1427 if (!LocInfo.LastKillValid) {
1428 LocInfo.LastKill = VersionStack.size() - 1;
1429 LocInfo.LastKillValid = true;
1430 }
1431
1432 // At this point, we should have corrected last kill and LowerBound to be
1433 // in bounds.
1434 assert(LocInfo.LowerBound < VersionStack.size() &&
1435 "Lower bound out of range");
1436 assert(LocInfo.LastKill < VersionStack.size() &&
1437 "Last kill info out of range");
1438 // In any case, the new upper bound is the top of the stack.
1439 unsigned long UpperBound = VersionStack.size() - 1;
1440
1441 if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
1442 LLVM_DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " ("
1443 << *(MU->getMemoryInst()) << ")"
1444 << " because there are "
1445 << UpperBound - LocInfo.LowerBound
1446 << " stores to disambiguate\n");
1447 // Because we did not walk, LastKill is no longer valid, as this may
1448 // have been a kill.
1449 LocInfo.LastKillValid = false;
1450 continue;
1451 }
1452 bool FoundClobberResult = false;
1453 unsigned UpwardWalkLimit = MaxCheckLimit;
1454 while (UpperBound > LocInfo.LowerBound) {
1455 if (isa<MemoryPhi>(Val: VersionStack[UpperBound])) {
1456 // For phis, use the walker, see where we ended up, go there.
1457 // The invariant.group handling in MemorySSA is ad-hoc and doesn't
1458 // support updates, so don't use it to optimize uses.
1459 MemoryAccess *Result =
1460 Walker->getClobberingMemoryAccessWithoutInvariantGroup(
1461 MA: MU, BAA&: *AA, UWL&: UpwardWalkLimit);
1462 // We are guaranteed to find it or something is wrong.
1463 while (VersionStack[UpperBound] != Result) {
1464 assert(UpperBound != 0);
1465 --UpperBound;
1466 }
1467 FoundClobberResult = true;
1468 break;
1469 }
1470
1471 MemoryDef *MD = cast<MemoryDef>(Val: VersionStack[UpperBound]);
1472 if (instructionClobbersQuery(MD, MU, UseMLOC, AA&: *AA)) {
1473 FoundClobberResult = true;
1474 break;
1475 }
1476 --UpperBound;
1477 }
1478
1479 // At the end of this loop, UpperBound is either a clobber, or lower bound
1480 // PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
1481 if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1482 MU->setDefiningAccess(DMA: VersionStack[UpperBound], Optimized: true);
1483 LocInfo.LastKill = UpperBound;
1484 } else {
1485 // Otherwise, we checked all the new ones, and now we know we can get to
1486 // LastKill.
1487 MU->setDefiningAccess(DMA: VersionStack[LocInfo.LastKill], Optimized: true);
1488 }
1489 LocInfo.LowerBound = VersionStack.size() - 1;
1490 LocInfo.LowerBoundBlock = BB;
1491 }
1492}
1493
1494/// Optimize uses to point to their actual clobbering definitions.
1495void MemorySSA::OptimizeUses::optimizeUses() {
1496 SmallVector<MemoryAccess *, 16> VersionStack;
1497 DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo;
1498 VersionStack.push_back(Elt: MSSA->getLiveOnEntryDef());
1499
1500 unsigned long StackEpoch = 1;
1501 unsigned long PopEpoch = 1;
1502 // We perform a non-recursive top-down dominator tree walk.
1503 for (const auto *DomNode : depth_first(G: DT->getRootNode()))
1504 optimizeUsesInBlock(BB: DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1505 LocStackInfo);
1506}
1507
1508void MemorySSA::placePHINodes(
1509 const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
1510 // Determine where our MemoryPhi's should go
1511 ForwardIDFCalculator IDFs(*DT);
1512 IDFs.setDefiningBlocks(DefiningBlocks);
1513 SmallVector<BasicBlock *, 32> IDFBlocks;
1514 IDFs.calculate(IDFBlocks);
1515
1516 // Now place MemoryPhi nodes.
1517 for (auto &BB : IDFBlocks)
1518 createMemoryPhi(BB);
1519}
1520
1521template <typename IterT>
1522void MemorySSA::buildMemorySSA(BatchAAResults &BAA, IterT Blocks) {
1523 // We create an access to represent "live on entry", for things like
1524 // arguments or users of globals, where the memory they use is defined before
1525 // the beginning of the function. We do not actually insert it into the IR.
1526 // We do not define a live on exit for the immediate uses, and thus our
1527 // semantics do *not* imply that something with no immediate uses can simply
1528 // be removed.
1529 BasicBlock &StartingPoint = *Blocks.begin();
1530 LiveOnEntryDef.reset(p: new MemoryDef(StartingPoint.getContext(), nullptr,
1531 nullptr, &StartingPoint, NextID++));
1532
1533 // We maintain lists of memory accesses per-block, trading memory for time. We
1534 // could just look up the memory access for every possible instruction in the
1535 // stream.
1536 SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
1537 // Go through each block, figure out where defs occur, and chain together all
1538 // the accesses.
1539 for (BasicBlock &B : Blocks) {
1540 bool InsertIntoDef = false;
1541 AccessList *Accesses = nullptr;
1542 DefsList *Defs = nullptr;
1543 for (Instruction &I : B) {
1544 MemoryUseOrDef *MUD = createNewAccess(I: &I, AAP: &BAA);
1545 if (!MUD)
1546 continue;
1547
1548 if (!Accesses)
1549 Accesses = getOrCreateAccessList(BB: &B);
1550 Accesses->push_back(val: MUD);
1551 if (isa<MemoryDef>(Val: MUD)) {
1552 InsertIntoDef = true;
1553 if (!Defs)
1554 Defs = getOrCreateDefsList(BB: &B);
1555 Defs->push_back(Node&: *MUD);
1556 }
1557 }
1558 if (InsertIntoDef)
1559 DefiningBlocks.insert(Ptr: &B);
1560 }
1561 placePHINodes(DefiningBlocks);
1562
1563 // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
1564 // filled in with all blocks.
1565 SmallPtrSet<BasicBlock *, 16> Visited;
1566 if (L) {
1567 // Only building MemorySSA for a single loop. placePHINodes may have
1568 // inserted a MemoryPhi in the loop's preheader. As this is outside the
1569 // scope of the loop, set them to LiveOnEntry.
1570 if (auto *P = getMemoryAccess(BB: L->getLoopPreheader())) {
1571 for (Use &U : make_early_inc_range(Range: P->uses()))
1572 U.set(LiveOnEntryDef.get());
1573 removeFromLists(P);
1574 }
1575 // Now rename accesses in the loop. Populate Visited with the exit blocks of
1576 // the loop, to limit the scope of the renaming.
1577 SmallVector<BasicBlock *> ExitBlocks;
1578 L->getExitBlocks(ExitBlocks);
1579 Visited.insert_range(R&: ExitBlocks);
1580 renamePass(Root: DT->getNode(BB: L->getLoopPreheader()), IncomingVal: LiveOnEntryDef.get(),
1581 Visited);
1582 } else {
1583 renamePass(Root: DT->getRootNode(), IncomingVal: LiveOnEntryDef.get(), Visited);
1584 }
1585
1586 // Mark the uses in unreachable blocks as live on entry, so that they go
1587 // somewhere.
1588 for (auto &BB : Blocks)
1589 if (!Visited.count(Ptr: &BB))
1590 markUnreachableAsLiveOnEntry(BB: &BB);
1591}
1592
1593MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
1594
1595MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
1596 if (Walker)
1597 return Walker.get();
1598
1599 if (!WalkerBase)
1600 WalkerBase = std::make_unique<ClobberWalkerBase>(args: this, args&: DT);
1601
1602 Walker = std::make_unique<CachingWalker>(args: this, args: WalkerBase.get());
1603 return Walker.get();
1604}
1605
1606MemorySSAWalker *MemorySSA::getSkipSelfWalker() {
1607 if (SkipWalker)
1608 return SkipWalker.get();
1609
1610 if (!WalkerBase)
1611 WalkerBase = std::make_unique<ClobberWalkerBase>(args: this, args&: DT);
1612
1613 SkipWalker = std::make_unique<SkipSelfWalker>(args: this, args: WalkerBase.get());
1614 return SkipWalker.get();
1615 }
1616
1617
1618// This is a helper function used by the creation routines. It places NewAccess
1619// into the access and defs lists for a given basic block, at the given
1620// insertion point.
1621void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess,
1622 const BasicBlock *BB,
1623 InsertionPlace Point) {
1624 auto *Accesses = getOrCreateAccessList(BB);
1625 if (Point == Beginning) {
1626 // If it's a phi node, it goes first, otherwise, it goes after any phi
1627 // nodes.
1628 if (isa<MemoryPhi>(Val: NewAccess)) {
1629 Accesses->push_front(val: NewAccess);
1630 auto *Defs = getOrCreateDefsList(BB);
1631 Defs->push_front(Node&: *NewAccess);
1632 } else {
1633 auto AI = find_if_not(
1634 Range&: *Accesses, P: [](const MemoryAccess &MA) { return isa<MemoryPhi>(Val: MA); });
1635 Accesses->insert(where: AI, New: NewAccess);
1636 if (!isa<MemoryUse>(Val: NewAccess)) {
1637 auto *Defs = getOrCreateDefsList(BB);
1638 auto DI = find_if_not(
1639 Range&: *Defs, P: [](const MemoryAccess &MA) { return isa<MemoryPhi>(Val: MA); });
1640 Defs->insert(I: DI, Node&: *NewAccess);
1641 }
1642 }
1643 } else {
1644 Accesses->push_back(val: NewAccess);
1645 if (!isa<MemoryUse>(Val: NewAccess)) {
1646 auto *Defs = getOrCreateDefsList(BB);
1647 Defs->push_back(Node&: *NewAccess);
1648 }
1649 }
1650 BlockNumberingValid.erase(Ptr: BB);
1651}
1652
1653void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB,
1654 AccessList::iterator InsertPt) {
1655 auto *Accesses = getBlockAccesses(BB);
1656 bool WasEnd = InsertPt == Accesses->end();
1657 Accesses->insert(where: AccessList::iterator(InsertPt), New: What);
1658 if (!isa<MemoryUse>(Val: What)) {
1659 auto *Defs = getOrCreateDefsList(BB);
1660 // If we got asked to insert at the end, we have an easy job, just shove it
1661 // at the end. If we got asked to insert before an existing def, we also get
1662 // an iterator. If we got asked to insert before a use, we have to hunt for
1663 // the next def.
1664 if (WasEnd) {
1665 Defs->push_back(Node&: *What);
1666 } else if (isa<MemoryDef>(Val: InsertPt)) {
1667 Defs->insert(I: InsertPt->getDefsIterator(), Node&: *What);
1668 } else {
1669 while (InsertPt != Accesses->end() && !isa<MemoryDef>(Val: InsertPt))
1670 ++InsertPt;
1671 // Either we found a def, or we are inserting at the end
1672 if (InsertPt == Accesses->end())
1673 Defs->push_back(Node&: *What);
1674 else
1675 Defs->insert(I: InsertPt->getDefsIterator(), Node&: *What);
1676 }
1677 }
1678 BlockNumberingValid.erase(Ptr: BB);
1679}
1680
1681void MemorySSA::prepareForMoveTo(MemoryAccess *What, BasicBlock *BB) {
1682 // Keep it in the lookup tables, remove from the lists
1683 removeFromLists(What, ShouldDelete: false);
1684
1685 // Note that moving should implicitly invalidate the optimized state of a
1686 // MemoryUse (and Phis can't be optimized). However, it doesn't do so for a
1687 // MemoryDef.
1688 if (auto *MD = dyn_cast<MemoryDef>(Val: What))
1689 MD->resetOptimized();
1690 What->setBlock(BB);
1691}
1692
1693// Move What before Where in the IR. The end result is that What will belong to
1694// the right lists and have the right Block set, but will not otherwise be
1695// correct. It will not have the right defining access, and if it is a def,
1696// things below it will not properly be updated.
1697void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1698 AccessList::iterator Where) {
1699 prepareForMoveTo(What, BB);
1700 insertIntoListsBefore(What, BB, InsertPt: Where);
1701}
1702
1703void MemorySSA::moveTo(MemoryAccess *What, BasicBlock *BB,
1704 InsertionPlace Point) {
1705 if (isa<MemoryPhi>(Val: What)) {
1706 assert(Point == Beginning &&
1707 "Can only move a Phi at the beginning of the block");
1708 // Update lookup table entry
1709 ValueToMemoryAccess.erase(Val: What->getBlock());
1710 bool Inserted = ValueToMemoryAccess.insert(KV: {BB, What}).second;
1711 (void)Inserted;
1712 assert(Inserted && "Cannot move a Phi to a block that already has one");
1713 }
1714
1715 prepareForMoveTo(What, BB);
1716 insertIntoListsForBlock(NewAccess: What, BB, Point);
1717}
1718
1719MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
1720 assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
1721 MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
1722 // Phi's always are placed at the front of the block.
1723 insertIntoListsForBlock(NewAccess: Phi, BB, Point: Beginning);
1724 ValueToMemoryAccess[BB] = Phi;
1725 return Phi;
1726}
1727
1728MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
1729 MemoryAccess *Definition,
1730 const MemoryUseOrDef *Template,
1731 bool CreationMustSucceed) {
1732 assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
1733 MemoryUseOrDef *NewAccess = createNewAccess(I, AAP: AA, Template);
1734 if (CreationMustSucceed)
1735 assert(NewAccess != nullptr && "Tried to create a memory access for a "
1736 "non-memory touching instruction");
1737 if (NewAccess) {
1738 assert((!Definition || !isa<MemoryUse>(Definition)) &&
1739 "A use cannot be a defining access");
1740 NewAccess->setDefiningAccess(DMA: Definition);
1741 }
1742 return NewAccess;
1743}
1744
1745// Return true if the instruction has ordering constraints.
1746// Note specifically that this only considers stores and loads
1747// because others are still considered ModRef by getModRefInfo.
1748static inline bool isOrdered(const Instruction *I) {
1749 if (auto *SI = dyn_cast<StoreInst>(Val: I)) {
1750 if (!SI->isUnordered())
1751 return true;
1752 } else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
1753 if (!LI->isUnordered())
1754 return true;
1755 }
1756 return false;
1757}
1758
1759/// Helper function to create new memory accesses
1760template <typename AliasAnalysisType>
1761MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
1762 AliasAnalysisType *AAP,
1763 const MemoryUseOrDef *Template) {
1764 // The assume intrinsic has a control dependency which we model by claiming
1765 // that it writes arbitrarily. Debuginfo intrinsics may be considered
1766 // clobbers when we have a nonstandard AA pipeline. Ignore these fake memory
1767 // dependencies here.
1768 // FIXME: Replace this special casing with a more accurate modelling of
1769 // assume's control dependency.
1770 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
1771 switch (II->getIntrinsicID()) {
1772 default:
1773 break;
1774 case Intrinsic::allow_runtime_check:
1775 case Intrinsic::allow_ubsan_check:
1776 case Intrinsic::assume:
1777 case Intrinsic::experimental_noalias_scope_decl:
1778 case Intrinsic::pseudoprobe:
1779 return nullptr;
1780 }
1781 }
1782
1783 // Using a nonstandard AA pipelines might leave us with unexpected modref
1784 // results for I, so add a check to not model instructions that may not read
1785 // from or write to memory. This is necessary for correctness.
1786 if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
1787 return nullptr;
1788
1789 bool Def, Use;
1790 if (Template) {
1791 Def = isa<MemoryDef>(Val: Template);
1792 Use = isa<MemoryUse>(Val: Template);
1793#if !defined(NDEBUG)
1794 ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1795 bool DefCheck, UseCheck;
1796 DefCheck = isModSet(ModRef) || isOrdered(I);
1797 UseCheck = isRefSet(ModRef);
1798 // Memory accesses should only be reduced and can not be increased since AA
1799 // just might return better results as a result of some transformations.
1800 assert((Def == DefCheck || !DefCheck) &&
1801 "Memory accesses should only be reduced");
1802 if (!Def && Use != UseCheck) {
1803 // New Access should not have more power than template access
1804 assert(!UseCheck && "Invalid template");
1805 }
1806#endif
1807 } else {
1808 // Find out what affect this instruction has on memory.
1809 ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1810 // The isOrdered check is used to ensure that volatiles end up as defs
1811 // (atomics end up as ModRef right now anyway). Until we separate the
1812 // ordering chain from the memory chain, this enables people to see at least
1813 // some relative ordering to volatiles. Note that getClobberingMemoryAccess
1814 // will still give an answer that bypasses other volatile loads. TODO:
1815 // Separate memory aliasing and ordering into two different chains so that
1816 // we can precisely represent both "what memory will this read/write/is
1817 // clobbered by" and "what instructions can I move this past".
1818 Def = isModSet(MRI: ModRef) || isOrdered(I);
1819 Use = isRefSet(MRI: ModRef);
1820 }
1821
1822 // It's possible for an instruction to not modify memory at all. During
1823 // construction, we ignore them.
1824 if (!Def && !Use)
1825 return nullptr;
1826
1827 MemoryUseOrDef *MUD;
1828 if (Def) {
1829 MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
1830 } else {
1831 MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
1832 if (isUseTriviallyOptimizableToLiveOnEntry(*AAP, I)) {
1833 MemoryAccess *LiveOnEntry = getLiveOnEntryDef();
1834 MUD->setOptimized(LiveOnEntry);
1835 }
1836 }
1837 ValueToMemoryAccess[I] = MUD;
1838 return MUD;
1839}
1840
1841/// Properly remove \p MA from all of MemorySSA's lookup tables.
1842void MemorySSA::removeFromLookups(MemoryAccess *MA) {
1843 assert(MA->use_empty() &&
1844 "Trying to remove memory access that still has uses");
1845 BlockNumbering.erase(Val: MA);
1846 if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1847 MUD->setDefiningAccess(DMA: nullptr);
1848 // Invalidate our walker's cache if necessary
1849 if (!isa<MemoryUse>(Val: MA))
1850 getWalker()->invalidateInfo(MA);
1851
1852 Value *MemoryInst;
1853 if (const auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1854 MemoryInst = MUD->getMemoryInst();
1855 else
1856 MemoryInst = MA->getBlock();
1857
1858 auto VMA = ValueToMemoryAccess.find(Val: MemoryInst);
1859 if (VMA->second == MA)
1860 ValueToMemoryAccess.erase(I: VMA);
1861}
1862
1863/// Properly remove \p MA from all of MemorySSA's lists.
1864///
1865/// Because of the way the intrusive list and use lists work, it is important to
1866/// do removal in the right order.
1867/// ShouldDelete defaults to true, and will cause the memory access to also be
1868/// deleted, not just removed.
1869void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
1870 BasicBlock *BB = MA->getBlock();
1871 // The access list owns the reference, so we erase it from the non-owning list
1872 // first.
1873 if (!isa<MemoryUse>(Val: MA)) {
1874 auto DefsIt = PerBlockDefs.find(Val: BB);
1875 std::unique_ptr<DefsList> &Defs = DefsIt->second;
1876 Defs->remove(N&: *MA);
1877 if (Defs->empty())
1878 PerBlockDefs.erase(I: DefsIt);
1879 }
1880
1881 // The erase call here will delete it. If we don't want it deleted, we call
1882 // remove instead.
1883 auto AccessIt = PerBlockAccesses.find(Val: BB);
1884 std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1885 if (ShouldDelete)
1886 Accesses->erase(IT: MA);
1887 else
1888 Accesses->remove(IT: MA);
1889
1890 if (Accesses->empty()) {
1891 PerBlockAccesses.erase(I: AccessIt);
1892 BlockNumberingValid.erase(Ptr: BB);
1893 }
1894}
1895
1896void MemorySSA::print(raw_ostream &OS) const {
1897 MemorySSAAnnotatedWriter Writer(this);
1898 Function *F = this->F;
1899 if (L)
1900 F = L->getHeader()->getParent();
1901 F->print(OS, AAW: &Writer);
1902}
1903
1904#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1905LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); }
1906#endif
1907
1908void MemorySSA::verifyMemorySSA(VerificationLevel VL) const {
1909#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
1910 VL = VerificationLevel::Full;
1911#endif
1912
1913#ifndef NDEBUG
1914 if (F) {
1915 auto Blocks = iterator_range(F->begin(), F->end());
1916 verifyOrderingDominationAndDefUses(Blocks, VL);
1917 verifyDominationNumbers(Blocks);
1918 if (VL == VerificationLevel::Full)
1919 verifyPrevDefInPhis(Blocks);
1920 } else {
1921 assert(L && "must either have loop or function");
1922 auto Blocks =
1923 map_range(L->blocks(), [](const BasicBlock *BB) -> BasicBlock & {
1924 return *const_cast<BasicBlock *>(BB);
1925 });
1926 verifyOrderingDominationAndDefUses(Blocks, VL);
1927 verifyDominationNumbers(Blocks);
1928 if (VL == VerificationLevel::Full)
1929 verifyPrevDefInPhis(Blocks);
1930 }
1931#endif
1932 // Previously, the verification used to also verify that the clobberingAccess
1933 // cached by MemorySSA is the same as the clobberingAccess found at a later
1934 // query to AA. This does not hold true in general due to the current fragility
1935 // of BasicAA which has arbitrary caps on the things it analyzes before giving
1936 // up. As a result, transformations that are correct, will lead to BasicAA
1937 // returning different Alias answers before and after that transformation.
1938 // Invalidating MemorySSA is not an option, as the results in BasicAA can be so
1939 // random, in the worst case we'd need to rebuild MemorySSA from scratch after
1940 // every transformation, which defeats the purpose of using it. For such an
1941 // example, see test4 added in D51960.
1942}
1943
1944template <typename IterT>
1945void MemorySSA::verifyPrevDefInPhis(IterT Blocks) const {
1946 for (const BasicBlock &BB : Blocks) {
1947 if (MemoryPhi *Phi = getMemoryAccess(BB: &BB)) {
1948 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1949 auto *Pred = Phi->getIncomingBlock(I);
1950 auto *IncAcc = Phi->getIncomingValue(I);
1951 // If Pred has no unreachable predecessors, get last def looking at
1952 // IDoms. If, while walkings IDoms, any of these has an unreachable
1953 // predecessor, then the incoming def can be any access.
1954 if (auto *DTNode = DT->getNode(BB: Pred)) {
1955 while (DTNode) {
1956 if (auto *DefList = getBlockDefs(BB: DTNode->getBlock())) {
1957 auto *LastAcc = &*(--DefList->end());
1958 assert(LastAcc == IncAcc &&
1959 "Incorrect incoming access into phi.");
1960 (void)IncAcc;
1961 (void)LastAcc;
1962 break;
1963 }
1964 DTNode = DTNode->getIDom();
1965 }
1966 } else {
1967 // If Pred has unreachable predecessors, but has at least a Def, the
1968 // incoming access can be the last Def in Pred, or it could have been
1969 // optimized to LoE. After an update, though, the LoE may have been
1970 // replaced by another access, so IncAcc may be any access.
1971 // If Pred has unreachable predecessors and no Defs, incoming access
1972 // should be LoE; However, after an update, it may be any access.
1973 }
1974 }
1975 }
1976 }
1977}
1978
1979/// Verify that all of the blocks we believe to have valid domination numbers
1980/// actually have valid domination numbers.
1981template <typename IterT>
1982void MemorySSA::verifyDominationNumbers(IterT Blocks) const {
1983 if (BlockNumberingValid.empty())
1984 return;
1985
1986 SmallPtrSet<const BasicBlock *, 16> ValidBlocks = BlockNumberingValid;
1987 for (const BasicBlock &BB : Blocks) {
1988 if (!ValidBlocks.count(Ptr: &BB))
1989 continue;
1990
1991 ValidBlocks.erase(Ptr: &BB);
1992
1993 const AccessList *Accesses = getBlockAccesses(BB: &BB);
1994 // It's correct to say an empty block has valid numbering.
1995 if (!Accesses)
1996 continue;
1997
1998 // Block numbering starts at 1.
1999 unsigned long LastNumber = 0;
2000 for (const MemoryAccess &MA : *Accesses) {
2001 auto ThisNumberIter = BlockNumbering.find(Val: &MA);
2002 assert(ThisNumberIter != BlockNumbering.end() &&
2003 "MemoryAccess has no domination number in a valid block!");
2004
2005 unsigned long ThisNumber = ThisNumberIter->second;
2006 assert(ThisNumber > LastNumber &&
2007 "Domination numbers should be strictly increasing!");
2008 (void)LastNumber;
2009 LastNumber = ThisNumber;
2010 }
2011 }
2012
2013 assert(ValidBlocks.empty() &&
2014 "All valid BasicBlocks should exist in F -- dangling pointers?");
2015}
2016
2017/// Verify ordering: the order and existence of MemoryAccesses matches the
2018/// order and existence of memory affecting instructions.
2019/// Verify domination: each definition dominates all of its uses.
2020/// Verify def-uses: the immediate use information - walk all the memory
2021/// accesses and verifying that, for each use, it appears in the appropriate
2022/// def's use list
2023template <typename IterT>
2024void MemorySSA::verifyOrderingDominationAndDefUses(IterT Blocks,
2025 VerificationLevel VL) const {
2026 // Walk all the blocks, comparing what the lookups think and what the access
2027 // lists think, as well as the order in the blocks vs the order in the access
2028 // lists.
2029 SmallVector<MemoryAccess *, 32> ActualAccesses;
2030 SmallVector<MemoryAccess *, 32> ActualDefs;
2031 for (BasicBlock &B : Blocks) {
2032 const AccessList *AL = getBlockAccesses(BB: &B);
2033 const auto *DL = getBlockDefs(BB: &B);
2034 MemoryPhi *Phi = getMemoryAccess(BB: &B);
2035 if (Phi) {
2036 // Verify ordering.
2037 ActualAccesses.push_back(Elt: Phi);
2038 ActualDefs.push_back(Elt: Phi);
2039 // Verify domination
2040 for (const Use &U : Phi->uses()) {
2041 assert(dominates(Phi, U) && "Memory PHI does not dominate it's uses");
2042 (void)U;
2043 }
2044 // Verify def-uses for full verify.
2045 if (VL == VerificationLevel::Full) {
2046 assert(Phi->getNumOperands() == pred_size(&B) &&
2047 "Incomplete MemoryPhi Node");
2048 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
2049 verifyUseInDefs(Phi->getIncomingValue(I), Phi);
2050 assert(is_contained(predecessors(&B), Phi->getIncomingBlock(I)) &&
2051 "Incoming phi block not a block predecessor");
2052 }
2053 }
2054 }
2055
2056 for (Instruction &I : B) {
2057 MemoryUseOrDef *MA = getMemoryAccess(I: &I);
2058 assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) &&
2059 "We have memory affecting instructions "
2060 "in this block but they are not in the "
2061 "access list or defs list");
2062 if (MA) {
2063 // Verify ordering.
2064 ActualAccesses.push_back(Elt: MA);
2065 if (MemoryAccess *MD = dyn_cast<MemoryDef>(Val: MA)) {
2066 // Verify ordering.
2067 ActualDefs.push_back(Elt: MA);
2068 // Verify domination.
2069 for (const Use &U : MD->uses()) {
2070 assert(dominates(MD, U) &&
2071 "Memory Def does not dominate it's uses");
2072 (void)U;
2073 }
2074 }
2075 // Verify def-uses for full verify.
2076 if (VL == VerificationLevel::Full)
2077 verifyUseInDefs(MA->getDefiningAccess(), MA);
2078 }
2079 }
2080 // Either we hit the assert, really have no accesses, or we have both
2081 // accesses and an access list. Same with defs.
2082 if (!AL && !DL)
2083 continue;
2084 // Verify ordering.
2085 assert(AL->size() == ActualAccesses.size() &&
2086 "We don't have the same number of accesses in the block as on the "
2087 "access list");
2088 assert((DL || ActualDefs.size() == 0) &&
2089 "Either we should have a defs list, or we should have no defs");
2090 assert((!DL || DL->size() == ActualDefs.size()) &&
2091 "We don't have the same number of defs in the block as on the "
2092 "def list");
2093 auto ALI = AL->begin();
2094 auto AAI = ActualAccesses.begin();
2095 while (ALI != AL->end() && AAI != ActualAccesses.end()) {
2096 assert(&*ALI == *AAI && "Not the same accesses in the same order");
2097 ++ALI;
2098 ++AAI;
2099 }
2100 ActualAccesses.clear();
2101 if (DL) {
2102 auto DLI = DL->begin();
2103 auto ADI = ActualDefs.begin();
2104 while (DLI != DL->end() && ADI != ActualDefs.end()) {
2105 assert(&*DLI == *ADI && "Not the same defs in the same order");
2106 ++DLI;
2107 ++ADI;
2108 }
2109 }
2110 ActualDefs.clear();
2111 }
2112}
2113
2114/// Verify the def-use lists in MemorySSA, by verifying that \p Use
2115/// appears in the use list of \p Def.
2116void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const {
2117 // The live on entry use may cause us to get a NULL def here
2118 if (!Def)
2119 assert(isLiveOnEntryDef(Use) &&
2120 "Null def but use not point to live on entry def");
2121 else
2122 assert(is_contained(Def->users(), Use) &&
2123 "Did not find use in def's use list");
2124}
2125
2126/// Perform a local numbering on blocks so that instruction ordering can be
2127/// determined in constant time.
2128/// TODO: We currently just number in order. If we numbered by N, we could
2129/// allow at least N-1 sequences of insertBefore or insertAfter (and at least
2130/// log2(N) sequences of mixed before and after) without needing to invalidate
2131/// the numbering.
2132void MemorySSA::renumberBlock(const BasicBlock *B) const {
2133 // The pre-increment ensures the numbers really start at 1.
2134 unsigned long CurrentNumber = 0;
2135 const AccessList *AL = getBlockAccesses(BB: B);
2136 assert(AL != nullptr && "Asking to renumber an empty block");
2137 for (const auto &I : *AL)
2138 BlockNumbering[&I] = ++CurrentNumber;
2139 BlockNumberingValid.insert(Ptr: B);
2140}
2141
2142/// Determine, for two memory accesses in the same block,
2143/// whether \p Dominator dominates \p Dominatee.
2144/// \returns True if \p Dominator dominates \p Dominatee.
2145bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
2146 const MemoryAccess *Dominatee) const {
2147 const BasicBlock *DominatorBlock = Dominator->getBlock();
2148
2149 assert((DominatorBlock == Dominatee->getBlock()) &&
2150 "Asking for local domination when accesses are in different blocks!");
2151 // A node dominates itself.
2152 if (Dominatee == Dominator)
2153 return true;
2154
2155 // When Dominatee is defined on function entry, it is not dominated by another
2156 // memory access.
2157 if (isLiveOnEntryDef(MA: Dominatee))
2158 return false;
2159
2160 // When Dominator is defined on function entry, it dominates the other memory
2161 // access.
2162 if (isLiveOnEntryDef(MA: Dominator))
2163 return true;
2164
2165 if (!BlockNumberingValid.count(Ptr: DominatorBlock))
2166 renumberBlock(B: DominatorBlock);
2167
2168 unsigned long DominatorNum = BlockNumbering.lookup(Val: Dominator);
2169 // All numbers start with 1
2170 assert(DominatorNum != 0 && "Block was not numbered properly");
2171 unsigned long DominateeNum = BlockNumbering.lookup(Val: Dominatee);
2172 assert(DominateeNum != 0 && "Block was not numbered properly");
2173 return DominatorNum < DominateeNum;
2174}
2175
2176bool MemorySSA::dominates(const MemoryAccess *Dominator,
2177 const MemoryAccess *Dominatee) const {
2178 if (Dominator == Dominatee)
2179 return true;
2180
2181 if (isLiveOnEntryDef(MA: Dominatee))
2182 return false;
2183
2184 if (Dominator->getBlock() != Dominatee->getBlock())
2185 return DT->dominates(A: Dominator->getBlock(), B: Dominatee->getBlock());
2186 return locallyDominates(Dominator, Dominatee);
2187}
2188
2189bool MemorySSA::dominates(const MemoryAccess *Dominator,
2190 const Use &Dominatee) const {
2191 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: Dominatee.getUser())) {
2192 BasicBlock *UseBB = MP->getIncomingBlock(U: Dominatee);
2193 // The def must dominate the incoming block of the phi.
2194 if (UseBB != Dominator->getBlock())
2195 return DT->dominates(A: Dominator->getBlock(), B: UseBB);
2196 // If the UseBB and the DefBB are the same, compare locally.
2197 return locallyDominates(Dominator, Dominatee: cast<MemoryAccess>(Val: Dominatee));
2198 }
2199 // If it's not a PHI node use, the normal dominates can already handle it.
2200 return dominates(Dominator, Dominatee: cast<MemoryAccess>(Val: Dominatee.getUser()));
2201}
2202
2203void MemorySSA::ensureOptimizedUses() {
2204 if (IsOptimized)
2205 return;
2206
2207 BatchAAResults BatchAA(*AA);
2208 ClobberWalkerBase WalkerBase(this, DT);
2209 CachingWalker WalkerLocal(this, &WalkerBase);
2210 OptimizeUses(this, &WalkerLocal, &BatchAA, DT).optimizeUses();
2211 IsOptimized = true;
2212}
2213
2214void MemoryAccess::print(raw_ostream &OS) const {
2215 switch (getValueID()) {
2216 case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
2217 case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);
2218 case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS);
2219 }
2220 llvm_unreachable("invalid value id");
2221}
2222
2223void MemoryDef::print(raw_ostream &OS) const {
2224 MemoryAccess *UO = getDefiningAccess();
2225
2226 auto printID = [&OS](MemoryAccess *A) {
2227 if (A && A->getID())
2228 OS << A->getID();
2229 else
2230 OS << LiveOnEntryStr;
2231 };
2232
2233 OS << getID() << " = MemoryDef(";
2234 printID(UO);
2235 OS << ")";
2236
2237 if (isOptimized()) {
2238 OS << "->";
2239 printID(getOptimized());
2240 }
2241}
2242
2243void MemoryPhi::print(raw_ostream &OS) const {
2244 ListSeparator LS(",");
2245 OS << getID() << " = MemoryPhi(";
2246 for (const auto &Op : operands()) {
2247 BasicBlock *BB = getIncomingBlock(U: Op);
2248 MemoryAccess *MA = cast<MemoryAccess>(Val: Op);
2249
2250 OS << LS << '{';
2251 if (BB->hasName())
2252 OS << BB->getName();
2253 else
2254 BB->printAsOperand(O&: OS, PrintType: false);
2255 OS << ',';
2256 if (unsigned ID = MA->getID())
2257 OS << ID;
2258 else
2259 OS << LiveOnEntryStr;
2260 OS << '}';
2261 }
2262 OS << ')';
2263}
2264
2265void MemoryUse::print(raw_ostream &OS) const {
2266 MemoryAccess *UO = getDefiningAccess();
2267 OS << "MemoryUse(";
2268 if (UO && UO->getID())
2269 OS << UO->getID();
2270 else
2271 OS << LiveOnEntryStr;
2272 OS << ')';
2273}
2274
2275void MemoryAccess::dump() const {
2276// Cannot completely remove virtual function even in release mode.
2277#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2278 print(dbgs());
2279 dbgs() << "\n";
2280#endif
2281}
2282
2283class DOTFuncMSSAInfo {
2284private:
2285 const Function &F;
2286 MemorySSAAnnotatedWriter MSSAWriter;
2287
2288public:
2289 DOTFuncMSSAInfo(const Function &F, MemorySSA &MSSA)
2290 : F(F), MSSAWriter(&MSSA) {}
2291
2292 const Function *getFunction() { return &F; }
2293 MemorySSAAnnotatedWriter &getWriter() { return MSSAWriter; }
2294};
2295
2296namespace llvm {
2297
2298template <>
2299struct GraphTraits<DOTFuncMSSAInfo *> : public GraphTraits<const BasicBlock *> {
2300 static NodeRef getEntryNode(DOTFuncMSSAInfo *CFGInfo) {
2301 return &(CFGInfo->getFunction()->getEntryBlock());
2302 }
2303
2304 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
2305 using nodes_iterator = pointer_iterator<Function::const_iterator>;
2306
2307 static nodes_iterator nodes_begin(DOTFuncMSSAInfo *CFGInfo) {
2308 return nodes_iterator(CFGInfo->getFunction()->begin());
2309 }
2310
2311 static nodes_iterator nodes_end(DOTFuncMSSAInfo *CFGInfo) {
2312 return nodes_iterator(CFGInfo->getFunction()->end());
2313 }
2314
2315 static size_t size(DOTFuncMSSAInfo *CFGInfo) {
2316 return CFGInfo->getFunction()->size();
2317 }
2318};
2319
2320template <>
2321struct DOTGraphTraits<DOTFuncMSSAInfo *> : public DefaultDOTGraphTraits {
2322
2323 DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {}
2324
2325 static std::string getGraphName(DOTFuncMSSAInfo *CFGInfo) {
2326 return "MSSA CFG for '" + CFGInfo->getFunction()->getName().str() +
2327 "' function";
2328 }
2329
2330 std::string getNodeLabel(const BasicBlock *Node, DOTFuncMSSAInfo *CFGInfo) {
2331 return DOTGraphTraits<DOTFuncInfo *>::getCompleteNodeLabel(
2332 Node, nullptr,
2333 HandleBasicBlock: [CFGInfo](raw_string_ostream &OS, const BasicBlock &BB) -> void {
2334 BB.print(OS, AAW: &CFGInfo->getWriter(), ShouldPreserveUseListOrder: true, IsForDebug: true);
2335 },
2336 HandleComment: [](std::string &S, unsigned &I, unsigned Idx) -> void {
2337 std::string Str = S.substr(pos: I, n: Idx - I);
2338 StringRef SR = Str;
2339 if (SR.count(Str: " = MemoryDef(") || SR.count(Str: " = MemoryPhi(") ||
2340 SR.count(Str: "MemoryUse("))
2341 return;
2342 DOTGraphTraits<DOTFuncInfo *>::eraseComment(OutStr&: S, I, Idx);
2343 });
2344 }
2345
2346 static std::string getEdgeSourceLabel(const BasicBlock *Node,
2347 const_succ_iterator I) {
2348 return DOTGraphTraits<DOTFuncInfo *>::getEdgeSourceLabel(Node, I);
2349 }
2350
2351 /// Display the raw branch weights from PGO.
2352 std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
2353 DOTFuncMSSAInfo *CFGInfo) {
2354 return "";
2355 }
2356
2357 std::string getNodeAttributes(const BasicBlock *Node,
2358 DOTFuncMSSAInfo *CFGInfo) {
2359 return getNodeLabel(Node, CFGInfo).find(c: ';') != std::string::npos
2360 ? "style=filled, fillcolor=lightpink"
2361 : "";
2362 }
2363};
2364
2365} // namespace llvm
2366
2367AnalysisKey MemorySSAAnalysis::Key;
2368
2369MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F,
2370 FunctionAnalysisManager &AM) {
2371 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2372 auto &AA = AM.getResult<AAManager>(IR&: F);
2373 return MemorySSAAnalysis::Result(std::make_unique<MemorySSA>(args&: F, args: &AA, args: &DT));
2374}
2375
2376bool MemorySSAAnalysis::Result::invalidate(
2377 Function &F, const PreservedAnalyses &PA,
2378 FunctionAnalysisManager::Invalidator &Inv) {
2379 auto PAC = PA.getChecker<MemorySSAAnalysis>();
2380 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2381 Inv.invalidate<AAManager>(IR&: F, PA) ||
2382 Inv.invalidate<DominatorTreeAnalysis>(IR&: F, PA);
2383}
2384
2385PreservedAnalyses MemorySSAPrinterPass::run(Function &F,
2386 FunctionAnalysisManager &AM) {
2387 auto &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
2388 if (EnsureOptimizedUses)
2389 MSSA.ensureOptimizedUses();
2390 if (DotCFGMSSA != "") {
2391 DOTFuncMSSAInfo CFGInfo(F, MSSA);
2392 WriteGraph(G: &CFGInfo, Name: "", ShortNames: false, Title: "MSSA", Filename: DotCFGMSSA);
2393 } else {
2394 OS << "MemorySSA for function: " << F.getName() << "\n";
2395 MSSA.print(OS);
2396 }
2397
2398 return PreservedAnalyses::all();
2399}
2400
2401PreservedAnalyses MemorySSAWalkerPrinterPass::run(Function &F,
2402 FunctionAnalysisManager &AM) {
2403 auto &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
2404 OS << "MemorySSA (walker) for function: " << F.getName() << "\n";
2405 MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2406 F.print(OS, AAW: &Writer);
2407
2408 return PreservedAnalyses::all();
2409}
2410
2411PreservedAnalyses MemorySSAVerifierPass::run(Function &F,
2412 FunctionAnalysisManager &AM) {
2413 AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA().verifyMemorySSA();
2414
2415 return PreservedAnalyses::all();
2416}
2417
2418char MemorySSAWrapperPass::ID = 0;
2419
2420MemorySSAWrapperPass::MemorySSAWrapperPass() : FunctionPass(ID) {}
2421
2422void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); }
2423
2424void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2425 AU.setPreservesAll();
2426 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
2427 AU.addRequiredTransitive<AAResultsWrapperPass>();
2428}
2429
2430bool MemorySSAWrapperPass::runOnFunction(Function &F) {
2431 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2432 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2433 MSSA.reset(p: new MemorySSA(F, &AA, &DT));
2434 return false;
2435}
2436
2437void MemorySSAWrapperPass::verifyAnalysis() const {
2438 if (VerifyMemorySSA)
2439 MSSA->verifyMemorySSA();
2440}
2441
2442void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const {
2443 MSSA->print(OS);
2444}
2445
2446MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
2447
2448/// Walk the use-def chains starting at \p StartingAccess and find
2449/// the MemoryAccess that actually clobbers Loc.
2450///
2451/// \returns our clobbering memory access
2452MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
2453 MemoryAccess *StartingAccess, const MemoryLocation &Loc,
2454 BatchAAResults &BAA, unsigned &UpwardWalkLimit) {
2455 assert(!isa<MemoryUse>(StartingAccess) && "Use cannot be defining access");
2456
2457 // If location is undefined, conservatively return starting access.
2458 if (Loc.Ptr == nullptr)
2459 return StartingAccess;
2460
2461 Instruction *I = nullptr;
2462 if (auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(Val: StartingAccess)) {
2463 if (MSSA->isLiveOnEntryDef(MA: StartingUseOrDef))
2464 return StartingUseOrDef;
2465
2466 I = StartingUseOrDef->getMemoryInst();
2467
2468 // Conservatively, fences are always clobbers, so don't perform the walk if
2469 // we hit a fence.
2470 if (!isa<CallBase>(Val: I) && I->isFenceLike())
2471 return StartingUseOrDef;
2472 }
2473
2474 UpwardsMemoryQuery Q;
2475 Q.OriginalAccess = StartingAccess;
2476 Q.StartingLoc = Loc;
2477 Q.Inst = nullptr;
2478 Q.IsCall = false;
2479
2480 // Unlike the other function, do not walk to the def of a def, because we are
2481 // handed something we already believe is the clobbering access.
2482 // We never set SkipSelf to true in Q in this method.
2483 MemoryAccess *Clobber =
2484 Walker.findClobber(BAA, Start: StartingAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2485 LLVM_DEBUG({
2486 dbgs() << "Clobber starting at access " << *StartingAccess << "\n";
2487 if (I)
2488 dbgs() << " for instruction " << *I << "\n";
2489 dbgs() << " is " << *Clobber << "\n";
2490 });
2491 return Clobber;
2492}
2493
2494static const Instruction *
2495getInvariantGroupClobberingInstruction(Instruction &I, DominatorTree &DT) {
2496 if (!I.hasMetadata(KindID: LLVMContext::MD_invariant_group) || I.isVolatile())
2497 return nullptr;
2498
2499 // We consider bitcasts and zero GEPs to be the same pointer value. Start by
2500 // stripping bitcasts and zero GEPs, then we will recursively look at loads
2501 // and stores through bitcasts and zero GEPs.
2502 Value *PointerOperand = getLoadStorePointerOperand(V: &I)->stripPointerCasts();
2503
2504 // It's not safe to walk the use list of a global value because function
2505 // passes aren't allowed to look outside their functions.
2506 // FIXME: this could be fixed by filtering instructions from outside of
2507 // current function.
2508 if (isa<Constant>(Val: PointerOperand))
2509 return nullptr;
2510
2511 const Instruction *MostDominatingInstruction = &I;
2512
2513 for (const User *Us : PointerOperand->users()) {
2514 auto *U = dyn_cast<Instruction>(Val: Us);
2515 if (!U || U == &I || !DT.dominates(Def: U, User: MostDominatingInstruction))
2516 continue;
2517
2518 // If we hit a load/store with an invariant.group metadata and the same
2519 // pointer operand, we can assume that value pointed to by the pointer
2520 // operand didn't change.
2521 if (U->hasMetadata(KindID: LLVMContext::MD_invariant_group) &&
2522 getLoadStorePointerOperand(V: U) == PointerOperand && !U->isVolatile()) {
2523 MostDominatingInstruction = U;
2524 }
2525 }
2526
2527 return MostDominatingInstruction == &I ? nullptr : MostDominatingInstruction;
2528}
2529
2530MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
2531 MemoryAccess *MA, BatchAAResults &BAA, unsigned &UpwardWalkLimit,
2532 bool SkipSelf, bool UseInvariantGroup) {
2533 auto *StartingAccess = dyn_cast<MemoryUseOrDef>(Val: MA);
2534 // If this is a MemoryPhi, we can't do anything.
2535 if (!StartingAccess)
2536 return MA;
2537
2538 if (UseInvariantGroup) {
2539 if (auto *I = getInvariantGroupClobberingInstruction(
2540 I&: *StartingAccess->getMemoryInst(), DT&: MSSA->getDomTree())) {
2541 assert(isa<LoadInst>(I) || isa<StoreInst>(I));
2542
2543 auto *ClobberMA = MSSA->getMemoryAccess(I);
2544 assert(ClobberMA);
2545 if (isa<MemoryUse>(Val: ClobberMA))
2546 return ClobberMA->getDefiningAccess();
2547 return ClobberMA;
2548 }
2549 }
2550
2551 bool IsOptimized = false;
2552
2553 // If this is an already optimized use or def, return the optimized result.
2554 // Note: Currently, we store the optimized def result in a separate field,
2555 // since we can't use the defining access.
2556 if (StartingAccess->isOptimized()) {
2557 if (!SkipSelf || !isa<MemoryDef>(Val: StartingAccess))
2558 return StartingAccess->getOptimized();
2559 IsOptimized = true;
2560 }
2561
2562 const Instruction *I = StartingAccess->getMemoryInst();
2563 // We can't sanely do anything with a fence, since they conservatively clobber
2564 // all memory, and have no locations to get pointers from to try to
2565 // disambiguate.
2566 if (!isa<CallBase>(Val: I) && I->isFenceLike())
2567 return StartingAccess;
2568
2569 UpwardsMemoryQuery Q(I, StartingAccess);
2570
2571 if (isUseTriviallyOptimizableToLiveOnEntry(AA&: BAA, I)) {
2572 MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
2573 StartingAccess->setOptimized(LiveOnEntry);
2574 return LiveOnEntry;
2575 }
2576
2577 MemoryAccess *OptimizedAccess;
2578 if (!IsOptimized) {
2579 // Start with the thing we already think clobbers this location
2580 MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2581
2582 // At this point, DefiningAccess may be the live on entry def.
2583 // If it is, we will not get a better result.
2584 if (MSSA->isLiveOnEntryDef(MA: DefiningAccess)) {
2585 StartingAccess->setOptimized(DefiningAccess);
2586 return DefiningAccess;
2587 }
2588
2589 OptimizedAccess =
2590 Walker.findClobber(BAA, Start: DefiningAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2591 StartingAccess->setOptimized(OptimizedAccess);
2592 } else
2593 OptimizedAccess = StartingAccess->getOptimized();
2594
2595 LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
2596 LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
2597 LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
2598 LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
2599
2600 MemoryAccess *Result;
2601 if (SkipSelf && isa<MemoryPhi>(Val: OptimizedAccess) &&
2602 isa<MemoryDef>(Val: StartingAccess) && UpwardWalkLimit) {
2603 assert(isa<MemoryDef>(Q.OriginalAccess));
2604 Q.SkipSelfAccess = true;
2605 Result = Walker.findClobber(BAA, Start: OptimizedAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2606 } else
2607 Result = OptimizedAccess;
2608
2609 LLVM_DEBUG(dbgs() << "Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2610 LLVM_DEBUG(dbgs() << "] for " << *I << " is " << *Result << "\n");
2611
2612 return Result;
2613}
2614
2615MemoryAccess *
2616DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA,
2617 BatchAAResults &) {
2618 if (auto *Use = dyn_cast<MemoryUseOrDef>(Val: MA))
2619 return Use->getDefiningAccess();
2620 return MA;
2621}
2622
2623MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
2624 MemoryAccess *StartingAccess, const MemoryLocation &, BatchAAResults &) {
2625 if (auto *Use = dyn_cast<MemoryUseOrDef>(Val: StartingAccess))
2626 return Use->getDefiningAccess();
2627 return StartingAccess;
2628}
2629
2630void MemoryPhi::deleteMe(DerivedUser *Self) {
2631 delete static_cast<MemoryPhi *>(Self);
2632}
2633
2634void MemoryDef::deleteMe(DerivedUser *Self) {
2635 delete static_cast<MemoryDef *>(Self);
2636}
2637
2638void MemoryUse::deleteMe(DerivedUser *Self) {
2639 delete static_cast<MemoryUse *>(Self);
2640}
2641
2642bool upward_defs_iterator::IsGuaranteedLoopInvariant(const Value *Ptr) const {
2643 auto IsGuaranteedLoopInvariantBase = [](const Value *Ptr) {
2644 Ptr = Ptr->stripPointerCasts();
2645 if (!isa<Instruction>(Val: Ptr))
2646 return true;
2647 return isa<AllocaInst>(Val: Ptr);
2648 };
2649
2650 Ptr = Ptr->stripPointerCasts();
2651 if (auto *I = dyn_cast<Instruction>(Val: Ptr)) {
2652 if (I->getParent()->isEntryBlock())
2653 return true;
2654 }
2655 if (auto *GEP = dyn_cast<GEPOperator>(Val: Ptr)) {
2656 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
2657 GEP->hasAllConstantIndices();
2658 }
2659 return IsGuaranteedLoopInvariantBase(Ptr);
2660}
2661