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