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