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