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