1//===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===// 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 7//===----------------------------------------------------------------------===// 9// This file implements the MemorySSA class. 11//===----------------------------------------------------------------------===// 30#include "llvm/Config/llvm-config.h" 61#define DEBUG_TYPE "memoryssa" 76 "
memssa-check-limit", cl::Hidden, cl::init(100),
78 "will consider trying to walk past (default = 100)"));
80// Always verify MemorySSA if expensive checking is enabled. 81#ifdef EXPENSIVE_CHECKS 95/// An assembly annotator class to print Memory SSA information in 101 MemorySSAAnnotatedWriter(
constMemorySSA *M) : MSSA(M) {}
106OS <<
"; " << *MA <<
"\n";
112OS <<
"; " << *MA <<
"\n";
116/// An assembly annotator class to print Memory SSA information in 124 MemorySSAWalkerAnnotatedWriter(
MemorySSA *M)
125 : MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
130OS <<
"; " << *MA <<
"\n";
139OS <<
" - clobbered by ";
154/// Our current alias analysis API differentiates heavily between calls and 155/// non-calls, and functions called on one usually assert on the other. 156/// This class encapsulates the distinction to simplify other code that wants 157/// "Memory affecting instructions and related data" to use as a key. 158/// For example, this class is used as a densemap key in the use optimizer. 159classMemoryLocOrCall {
164 : MemoryLocOrCall(MUD->getMemoryInst()) {}
166 : MemoryLocOrCall(MUD->getMemoryInst()) {}
169if (
auto *
C = dyn_cast<CallBase>(Inst)) {
174// There is no such thing as a memorylocation for a fence inst, and it is 175// unique in that regard. 176if (!isa<FenceInst>(Inst))
194if (IsCall !=
Other.IsCall)
198return Loc ==
Other.Loc;
200if (
Call->getCalledOperand() !=
Other.Call->getCalledOperand())
203returnCall->arg_size() ==
Other.Call->arg_size() &&
204 std::equal(
Call->arg_begin(),
Call->arg_end(),
205Other.Call->arg_begin());
215}
// end anonymous namespace 236 MLOC.getCall()->getCalledOperand()));
238for (
constValue *Arg : MLOC.getCall()->args())
243staticboolisEqual(
const MemoryLocOrCall &LHS,
const MemoryLocOrCall &RHS) {
248}
// end namespace llvm 250/// This does one-way checks to see if Use could theoretically be hoisted above 251/// MayClobber. This will not check the other way around. 253/// This assumes that, for the purposes of MemorySSA, Use comes directly after 254/// MayClobber, with no potentially clobbering operations in between them. 255/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.) 258bool VolatileUse =
Use->isVolatile();
259bool VolatileClobber = MayClobber->
isVolatile();
260// Volatile operations may never be reordered with other volatile operations. 261if (VolatileUse && VolatileClobber)
263// Otherwise, volatile doesn't matter here. From the language reference: 264// 'optimizers may change the order of volatile operations relative to 265// non-volatile operations.'" 267// If a load is seq_cst, it cannot be moved above other loads. If its ordering 268// is weaker, it can be moved above other loads. We just need to be sure that 269// MayClobber isn't an acquire load, because loads can't be moved above 272// Note that this explicitly *does* allow the free reordering of monotonic (or 273// weaker) loads of the same address. 274bool SeqCstUse =
Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
276 AtomicOrdering::Acquire);
277return !(SeqCstUse || MayClobberIsAcquire);
280template <
typename AliasAnalysisType>
285assert(DefInst &&
"Defining instruction not actually an instruction");
288// These intrinsics will show up as affecting memory, but they are just 291// FIXME: We probably don't actually want MemorySSA to model these at all 292// (including creating MemoryAccesses for them): we just end up inventing 293// clobbers where they don't really exist at all. Please see D43269 for 295switch (
II->getIntrinsicID()) {
296case Intrinsic::allow_runtime_check:
297case Intrinsic::allow_ubsan_check:
298case Intrinsic::invariant_start:
299case Intrinsic::invariant_end:
300case Intrinsic::assume:
301case Intrinsic::experimental_noalias_scope_decl:
302case Intrinsic::pseudoprobe:
304case Intrinsic::dbg_declare:
305case Intrinsic::dbg_label:
306case Intrinsic::dbg_value:
313if (
auto *CB = dyn_cast_or_null<CallBase>(UseInst)) {
318if (
auto *DefLoad = dyn_cast<LoadInst>(DefInst))
319if (
auto *UseLoad = dyn_cast_or_null<LoadInst>(UseInst))
326template <
typename AliasAnalysisType>
328const MemoryLocOrCall &UseMLOC,
329 AliasAnalysisType &AA) {
330// FIXME: This is a temporary hack to allow a single instructionClobbersQuery 331// to exist while MemoryLocOrCall is pushed through places. 339// Return true when MD may alias MU, return false otherwise. 347structUpwardsMemoryQuery {
348// True if our original query started off as a call 350// The pointer location we started the query with. This will be empty if 353// This is the instruction we were querying about. 355// The MemoryAccess we actually got called with, used to test local domination 357bool SkipSelfAccess =
false;
359 UpwardsMemoryQuery() =
default;
368}
// end anonymous namespace 370template <
typename AliasAnalysisType>
373// If the memory can't be changed, then loads of the memory can't be 375if (
auto *LI = dyn_cast<LoadInst>(
I)) {
376returnI->hasMetadata(LLVMContext::MD_invariant_load) ||
382/// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing 383/// inbetween `Start` and `ClobberAt` can clobbers `Start`. 385/// This is meant to be as simple and self-contained as possible. Because it 386/// uses no cache, etc., it can be relatively expensive. 388/// \param Start The MemoryAccess that we want to walk from. 389/// \param ClobberAt A clobber for Start. 390/// \param StartLoc The MemoryLocation for Start. 391/// \param MSSA The MemorySSA instance that Start and ClobberAt belong to. 392/// \param Query The UpwardsMemoryQuery we used for our search. 393/// \param AA The AliasAnalysis we used for our search. 394/// \param AllowImpreciseClobber Always false, unless we do relaxed verify. 400bool AllowImpreciseClobber =
false) {
401assert(MSSA.
dominates(ClobberAt, Start) &&
"Clobber doesn't dominate start?");
405"liveOnEntry must clobber itself");
409bool FoundClobber =
false;
413// Walk all paths from Start to ClobberAt, while looking for clobbers. If one 414// is found, complain. 415while (!Worklist.
empty()) {
417// All we care about is that nothing from Start to ClobberAt clobbers Start. 418// We learn nothing from revisiting nodes. 423if (MA == ClobberAt) {
424if (
constauto *MD = dyn_cast<MemoryDef>(MA)) {
425// instructionClobbersQuery isn't essentially free, so don't use `|=`, 426// since it won't let us short-circuit. 428// Also, note that this can't be hoisted out of the `Worklist` loop, 429// since MD may only act as a clobber for 1 of N MemoryLocations. 439// We should never hit liveOnEntry, unless it's the clobber. 442if (
constauto *MD = dyn_cast<MemoryDef>(MA)) {
443// If Start is a Def, skip self. 448"Found clobber before reaching ClobberAt!");
452if (
constauto *MU = dyn_cast<MemoryUse>(MA)) {
455"Can only find use in def chain if Start is a use");
459assert(isa<MemoryPhi>(MA));
461// Add reachable phi predecessors 472// If the verify is done following an optimization, it's possible that 473// ClobberAt was a conservative clobbering, that we can now infer is not a 474// true clobbering access. Don't fail the verify if that's the case. 475// We do have accesses that claim they're optimized, but could be optimized 476// further. Updating all these can be expensive, so allow it for now (FIXME). 477if (AllowImpreciseClobber)
480// If ClobberAt is a MemoryPhi, we can assume something above it acted as a 481// clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point. 482assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
483"ClobberAt never acted as a clobber");
488/// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up 491 /// Save a few bytes by using unsigned instead of size_t. 494 /// Represents a span of contiguous MemoryDefs, potentially ending in a 498// Note that, because we always walk in reverse, Last will always dominate 499// First. Also note that First and Last are inclusive. 502 std::optional<ListIndex> Previous;
505 std::optional<ListIndex> Previous)
509 std::optional<ListIndex> Previous)
510 : DefPath(Loc,
Init,
Init, Previous) {}
516 UpwardsMemoryQuery *Query;
517unsigned *UpwardWalkLimit;
519// Phi optimization bookkeeping: 520// List of DefPath to process during the current phi optimization walk. 522// List of visited <Access, Location> pairs; we can skip paths already 523// visited with the same memory location. 526 /// Find the nearest def or phi that `From` can legally be optimized to. 528assert(
From->getNumOperands() &&
"Phi with no operands?");
541 /// Result of calling walkToPhiOrClobber. 542structUpwardsWalkResult {
543 /// The "Result" of the walk. Either a clobber, the last thing we walked, or 544 /// both. Include alias info when clobber found. 549 /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. 550 /// This will update Desc.Last as it walks. It will (optionally) also stop at 553 /// This does not test for whether StopAt is a clobber 557assert(!isa<MemoryUse>(
Desc.Last) &&
"Uses don't exist in my world");
558assert(UpwardWalkLimit &&
"Need a valid walk limit");
559bool LimitAlreadyReached =
false;
560// (*UpwardWalkLimit) may be 0 here, due to the loop in tryOptimizePhi. Set 561// it to 1. This will not do any alias() calls. It either returns in the 562// first iteration in the loop below, or is set back to 0 if all def chains 563// are free of MemoryDefs. 564if (!*UpwardWalkLimit) {
565 *UpwardWalkLimit = 1;
566 LimitAlreadyReached =
true;
571if (Current == StopAt || Current == SkipStopAt)
572return {Current,
false};
574if (
auto *MD = dyn_cast<MemoryDef>(Current)) {
578if (!--*UpwardWalkLimit)
579return {Current,
true};
586if (LimitAlreadyReached)
587 *UpwardWalkLimit = 0;
590"Ended at a non-clobber that's not a phi?");
591return {
Desc.Last,
false};
595 ListIndex PriorNode) {
604 /// Represents a search that terminated after finding a clobber. This clobber 605 /// may or may not be present in the path of defs from LastNode..SearchStart, 606 /// since it may have been retrieved from cache. 607structTerminatedPath {
612 /// Get an access that keeps us from optimizing to the given phi. 614 /// PausedSearches is an array of indices into the Paths array. Its incoming 615 /// value is the indices of searches that stopped at the last phi optimization 616 /// target. It's left in an unspecified state. 618 /// If this returns std::nullopt, NewPaused is a vector of searches that 619 /// terminated at StopWhere. Otherwise, NewPaused is left in an unspecified 621 std::optional<TerminatedPath>
626assert(!PausedSearches.
empty() &&
"No searches to continue?");
628// BFS vs DFS really doesn't make a difference here, so just do a DFS with 629// PausedSearches as our stack. 630while (!PausedSearches.
empty()) {
632 DefPath &
Node = Paths[PathIndex];
634// If we've already visited this path with this MemoryLocation, we don't 635// need to do so again. 637// NOTE: That we just drop these paths on the ground makes caching 638// behavior sporadic. e.g. given a diamond: 643// ...If we walk D, B, A, C, we'll only cache the result of phi 644// optimization for A, B, and D; C will be skipped because it dies here. 645// This arguably isn't the worst thing ever, since: 646// - We generally query things in a top-down order, so if we got below D 647// without needing cache entries for {C, MemLoc}, then chances are 648// that those cache entries would end up ultimately unused. 649// - We still cache things for A, so C only needs to walk up a bit. 650// If this behavior becomes problematic, we can fix without a ton of extra 652if (!VisitedPhis.
insert({Node.Last, Node.Loc}).second)
656if (Query->SkipSelfAccess &&
Node.Loc == Query->StartingLoc) {
657assert(isa<MemoryDef>(Query->OriginalAccess));
658 SkipStopWhere = Query->OriginalAccess;
661 UpwardsWalkResult Res = walkToPhiOrClobber(
Node,
663/*SkipStopAt=*/SkipStopWhere);
664if (Res.IsKnownClobber) {
665assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
667// If this wasn't a cache hit, we hit a clobber when walking. That's a 669 TerminatedPath
Term{Res.Result, PathIndex};
670if (!MSSA.
dominates(Res.Result, StopWhere))
673// Otherwise, it's a valid thing to potentially optimize to. 678if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
679// We've hit our target. Save this path off for if we want to continue 680// walking. If we are in the mode of skipping the OriginalAccess, and 681// we've reached back to the OriginalAccess, do not save path, we've 682// just looped back to self. 683if (Res.Result != SkipStopWhere)
689 addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex);
695template <
typename T,
typename Walker>
696structgeneric_def_path_iterator
698 std::forward_iterator_tag, T *> {
699 generic_def_path_iterator() =
default;
700 generic_def_path_iterator(Walker *W, ListIndex
N) :
W(
W),
N(
N) {}
704 generic_def_path_iterator &operator++() {
705N = curNode().Previous;
709booloperator==(
const generic_def_path_iterator &O)
const{
710if (
N.has_value() !=
O.N.has_value())
712return !
N || *
N == *
O.N;
716T &curNode()
const{
returnW->Paths[*
N]; }
719 std::optional<ListIndex>
N;
722usingdef_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
723usingconst_def_path_iterator =
724 generic_def_path_iterator<const DefPath, const ClobberWalker>;
727returnmake_range(def_path_iterator(
this,
From), def_path_iterator());
732 const_def_path_iterator());
736 /// The path that contains our result. 737 TerminatedPath PrimaryClobber;
738 /// The paths that we can legally cache back from, but that aren't 739 /// necessarily the result of the Phi optimization. 743 ListIndex defPathIndex(
const DefPath &
N)
const{
744// The assert looks nicer if we don't need to do &N 745const DefPath *NP = &
N;
747"Out of bounds DefPath!");
748return NP - &Paths.
front();
751 /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths 752 /// that act as legal clobbers. Note that this won't return *all* clobbers. 754 /// Phi optimization algorithm tl;dr: 755 /// - Find the earliest def/phi, A, we can optimize to 756 /// - Find if all paths from the starting memory access ultimately reach A 757 /// - If not, optimization isn't possible. 758 /// - Otherwise, walk from A to another clobber or phi, A'. 759 /// - If A' is a def, we're done. 760 /// - If A' is a phi, try to optimize it. 762 /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path 763 /// terminates when a MemoryAccess that clobbers said MemoryLocation is found. 767"Reset the optimization state.");
770// Stores how many "valid" optimization nodes we had prior to calling 771// addSearches/getBlockingAccess. Necessary for caching if we had a blocker. 772auto PriorPathsSize = Paths.
size();
778 addSearches(Phi, PausedSearches, 0);
780// Moves the TerminatedPath with the "most dominated" Clobber to the end of 784auto Dom = Paths.
begin();
785for (
autoI = std::next(Dom),
E = Paths.
end();
I !=
E; ++
I)
790 std::iter_swap(
Last, Dom);
796"liveOnEntry wasn't treated as a clobber?");
798constauto *
Target = getWalkTarget(Current);
799// If a TerminatedPath doesn't dominate Target, then it wasn't a legal 800// optimization for the prior phi. 805// FIXME: This is broken, because the Blocker may be reported to be 806// liveOnEntry, and we'll happily wait for that to disappear (read: never) 807// For the moment, this is fine, since we do nothing with blocker info. 808if (std::optional<TerminatedPath> Blocker = getBlockingAccess(
809Target, PausedSearches, NewPaused, TerminatedPaths)) {
811// Find the node we started at. We can't search based on N->Last, since 812// we may have gone around a loop with a different MemoryLocation. 813auto Iter =
find_if(def_path(Blocker->LastNode), [&](
const DefPath &
N) {
814 return defPathIndex(N) < PriorPathsSize;
816assert(Iter != def_path_iterator());
818 DefPath &CurNode = *Iter;
819assert(CurNode.Last == Current);
822// A. We can't reliably cache all of NewPaused back. Consider a case 823// where we have two paths in NewPaused; one of which can't optimize 824// above this phi, whereas the other can. If we cache the second path 825// back, we'll end up with suboptimal cache entries. We can handle 826// cases like this a bit better when we either try to find all 827// clobbers that block phi optimization, or when our cache starts 828// supporting unfinished searches. 829// B. We can't reliably cache TerminatedPaths back here without doing 830// extra checks; consider a case like: 836// Where T is our target, C is a node with a clobber on it, D is a 837// diamond (with a clobber *only* on the left or right node, N), and 838// S is our start. Say we walk to D, through the node opposite N 839// (read: ignoring the clobber), and see a cache entry in the top 840// node of D. That cache entry gets put into TerminatedPaths. We then 841// walk up to C (N is later in our worklist), find the clobber, and 842// quit. If we append TerminatedPaths to OtherClobbers, we'll cache 843// the bottom part of D to the cached clobber, ignoring the clobber 844// in N. Again, this problem goes away if we start tracking all 845// blockers for a given phi optimization. 846 TerminatedPath
Result{CurNode.Last, defPathIndex(CurNode)};
850// If there's nothing left to search, then all paths led to valid clobbers 851// that we got from our cache; pick the nearest to the start, and allow 852// the rest to be cached back. 853if (NewPaused.
empty()) {
854 MoveDominatedPathToEnd(TerminatedPaths);
856return {
Result, std::move(TerminatedPaths)};
861for (ListIndex Paused : NewPaused) {
862 UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
863if (WR.IsKnownClobber)
866// Micro-opt: If we hit the end of the chain, save it. 867 DefChainEnd = WR.Result;
870if (!TerminatedPaths.
empty()) {
871// If we couldn't find the dominating phi/liveOnEntry in the above loop, 876assert(DefChainEnd &&
"Failed to find dominating phi/liveOnEntry");
878// If any of the terminated paths don't dominate the phi we'll try to 879// optimize, we need to figure out what they are and quit. 881for (
const TerminatedPath &TP : TerminatedPaths) {
882// Because we know that DefChainEnd is as "high" as we can go, we 883// don't need local dominance checks; BB dominance is sufficient. 884if (DT.
dominates(ChainBB, TP.Clobber->getBlock()))
889// If we have clobbers in the def chain, find the one closest to Current 891if (!Clobbers.
empty()) {
892 MoveDominatedPathToEnd(Clobbers);
894return {
Result, std::move(Clobbers)};
898 [&](ListIndex
I) {
return Paths[
I].Last == DefChainEnd; }));
900// Because liveOnEntry is a clobber, this must be a phi. 901auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd);
903 PriorPathsSize = Paths.
size();
904 PausedSearches.
clear();
905for (ListIndex
I : NewPaused)
906 addSearches(DefChainPhi, PausedSearches,
I);
909 Current = DefChainPhi;
913void verifyOptResult(
const OptznResult &R)
const{
915 return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
919void resetPhiOptznState() {
926 : MSSA(MSSA), DT(DT) {}
928 /// Finds the nearest clobber for the given query, optimizing phis if 931 UpwardsMemoryQuery &Q,
unsigned &UpWalkLimit) {
934 UpwardWalkLimit = &UpWalkLimit;
935// Starting limit must be > 0. 940// This walker pretends uses don't exist. If we're handed one, silently grab 941// its def. (This has the nice side-effect of ensuring we never cache uses) 942if (
auto *MU = dyn_cast<MemoryUse>(Start))
943 Current = MU->getDefiningAccess();
945 DefPath FirstDesc(Q.StartingLoc, Current, Current, std::nullopt);
946// Fast path for the overly-common case (no crazy phi optimization 948 UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
950if (WalkResult.IsKnownClobber) {
951Result = WalkResult.Result;
953 OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
954 Current, Q.StartingLoc);
955 verifyOptResult(OptRes);
956 resetPhiOptznState();
957Result = OptRes.PrimaryClobber.Clobber;
960#ifdef EXPENSIVE_CHECKS 961if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
968structRenamePassData {
975 : DTN(
D), ChildIt(It), IncomingVal(
M) {}
984}
// end anonymous namespace 989 ClobberWalker Walker;
998// Third argument (bool), defines whether the clobber search should skip the 999// original queried access. If true, there will be a follow-up query searching 1000// for a clobber access past "self". Note that the Optimized access is not 1001// updated if a new clobber is found by this SkipSelf search. If this 1002// additional query becomes heavily used we may decide to cache the result. 1003// Walker instantiations will decide how to set the SkipSelf bool. 1006bool UseInvariantGroup =
true);
1009/// A MemorySSAWalker that does AA walks to disambiguate accesses. It no 1010/// longer does caching on its own, but the name has been retained for the 1024return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false);
1029return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1031// This method is not accessible outside of this file. 1034return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false,
false);
1050if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1051 MUD->resetOptimized();
1067return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
true);
1072return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1088if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1089 MUD->resetOptimized();
1093}
// end namespace llvm 1096bool RenameAllUses) {
1097// Pass through values to our successors 1099auto It = PerBlockAccesses.
find(S);
1100// Rename the phi nodes in our successor block 1101if (It == PerBlockAccesses.
end() || !isa<MemoryPhi>(It->second->front()))
1104auto *Phi = cast<MemoryPhi>(&Accesses->front());
1106bool ReplacementDone =
false;
1107for (
unsignedI = 0, E = Phi->getNumIncomingValues();
I != E; ++
I)
1108if (Phi->getIncomingBlock(
I) == BB) {
1109 Phi->setIncomingValue(
I, IncomingVal);
1110 ReplacementDone =
true;
1112 (void) ReplacementDone;
1113assert(ReplacementDone &&
"Incomplete phi during partial rename");
1115Phi->addIncoming(IncomingVal, BB);
1119/// Rename a single basic block into MemorySSA form. 1120/// Uses the standard SSA renaming algorithm. 1121/// \returns The new incoming value. 1123bool RenameAllUses) {
1124auto It = PerBlockAccesses.
find(BB);
1125// Skip most processing if the list is empty. 1126if (It != PerBlockAccesses.
end()) {
1130if (MUD->getDefiningAccess() ==
nullptr || RenameAllUses)
1131 MUD->setDefiningAccess(IncomingVal);
1132if (isa<MemoryDef>(&L))
1142/// This is the standard SSA renaming algorithm. 1144/// We walk the dominator tree in preorder, renaming accesses, and then filling 1145/// in phi nodes in our successors. 1148bool SkipVisited,
bool RenameAllUses) {
1149assert(Root &&
"Trying to rename accesses in an unreachable block");
1152// Skip everything if we already renamed this block and we are skipping. 1153// Note: You can't sink this into the if, because we need it to occur 1154// regardless of whether we skip blocks or not. 1156if (SkipVisited && AlreadyVisited)
1159 IncomingVal = renameBlock(Root->
getBlock(), IncomingVal, RenameAllUses);
1160 renameSuccessorPhis(Root->
getBlock(), IncomingVal, RenameAllUses);
1163while (!WorkStack.
empty()) {
1166 IncomingVal = WorkStack.
back().IncomingVal;
1168if (ChildIt ==
Node->end()) {
1172 ++WorkStack.
back().ChildIt;
1174// Note: You can't sink this into the if, because we need it to occur 1175// regardless of whether we skip blocks or not. 1176 AlreadyVisited = !Visited.
insert(BB).second;
1177if (SkipVisited && AlreadyVisited) {
1178// We already visited this during our renaming, which can happen when 1179// being asked to rename multiple blocks. Figure out the incoming val, 1180// which is the last def. 1181// Incoming value can only change if there is a block def, and in that 1182// case, it's the last block def in the list. 1184 IncomingVal = &*BlockDefs->rbegin();
1186 IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1187 renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1193/// This handles unreachable block accesses by deleting phi nodes in 1194/// unreachable blocks, and marking all other unreachable MemoryAccess's as 1195/// being uses of the live on entry definition. 1196void MemorySSA::markUnreachableAsLiveOnEntry(
BasicBlock *BB) {
1198"Reachable block found while handling unreachable blocks");
1200// Make sure phi nodes in our reachable successors end up with a 1201// LiveOnEntryDef for our incoming edge, even though our block is forward 1202// unreachable. We could just disconnect these blocks from the CFG fully, 1203// but we do not right now. 1207auto It = PerBlockAccesses.
find(S);
1208// Rename the phi nodes in our successor block 1209if (It == PerBlockAccesses.
end() || !isa<MemoryPhi>(It->second->front()))
1212auto *
Phi = cast<MemoryPhi>(&Accesses->front());
1213Phi->addIncoming(LiveOnEntryDef.get(), BB);
1216auto It = PerBlockAccesses.
find(BB);
1217if (It == PerBlockAccesses.
end())
1220auto &Accesses = It->second;
1221for (
auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1222auto Next = std::next(AI);
1223// If we have a phi, just remove it. We are going to replace all 1224// users with live on entry. 1225if (
auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
1226 UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1228 Accesses->erase(AI);
1234 : DT(DT),
F(&Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1235 SkipWalker(nullptr) {
1236// Build MemorySSA using a batch alias analysis. This reuses the internal 1237// state that AA collects during an alias()/getModRefInfo() call. This is 1238// safe because there are no CFG changes while building MemorySSA and can 1239// significantly reduce the time spent by the compiler in AA, because we will 1240// make queries about all the instructions in the Function. 1241assert(AA &&
"No alias analysis?");
1244// Intentionally leave AA to nullptr while building so we don't accidentally 1245// use non-batch AliasAnalysis. 1247// Also create the walker here. 1252 : DT(DT), L(&L), LiveOnEntryDef(nullptr), Walker(nullptr),
1253 SkipWalker(nullptr) {
1254// Build MemorySSA using a batch alias analysis. This reuses the internal 1255// state that AA collects during an alias()/getModRefInfo() call. This is 1256// safe because there are no CFG changes while building MemorySSA and can 1257// significantly reduce the time spent by the compiler in AA, because we will 1258// make queries about all the instructions in the Function. 1259assert(AA &&
"No alias analysis?");
1263 return *const_cast<BasicBlock *>(BB);
1265// Intentionally leave AA to nullptr while building so we don't accidentally 1266// use non-batch AliasAnalysis. 1268// Also create the walker here. 1273// Drop all our references 1274for (
constauto &Pair : PerBlockAccesses)
1280auto Res = PerBlockAccesses.
insert(std::make_pair(BB,
nullptr));
1283 Res.first->second = std::make_unique<AccessList>();
1284return Res.first->second.get();
1288auto Res = PerBlockDefs.
insert(std::make_pair(BB,
nullptr));
1291 Res.first->second = std::make_unique<DefsList>();
1292return Res.first->second.get();
1297/// This class is a batch walker of all MemoryUse's in the program, and points 1298/// their defining access at the thing that actually clobbers them. Because it 1299/// is a batch walker that touches everything, it does not operate like the 1300/// other walkers. This walker is basically performing a top-down SSA renaming 1301/// pass, where the version stack is used as the cache. This enables it to be 1302/// significantly more time and memory efficient than using the regular walker, 1303/// which is walking bottom-up. 1308 : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1313 /// This represents where a given memorylocation is in the stack. 1314structMemlocStackInfo {
1315// This essentially is keeping track of versions of the stack. Whenever 1316// the stack changes due to pushes or pops, these versions increase. 1317unsignedlong StackEpoch;
1318unsignedlong PopEpoch;
1319// This is the lower bound of places on the stack to check. It is equal to 1320// the place the last stack walk ended. 1321// Note: Correctness depends on this being initialized to 0, which densemap 1323unsignedlong LowerBound;
1325// This is where the last walk for this memory location ended. 1326unsignedlong LastKill;
1330void optimizeUsesInBlock(
constBasicBlock *,
unsignedlong &,
unsignedlong &,
1335 CachingWalker *Walker;
1340}
// end namespace llvm 1342/// Optimize the uses in a given block This is basically the SSA renaming 1343/// algorithm, with one caveat: We are able to use a single stack for all 1344/// MemoryUses. This is because the set of *possible* reaching MemoryDefs is 1345/// the same for every MemoryUse. The *actual* clobbering MemoryDef is just 1346/// going to be some position in that stack of possible ones. 1348/// We track the stack positions that each MemoryLocation needs 1349/// to check, and last ended at. This is because we only want to check the 1350/// things that changed since last time. The same MemoryLocation should 1351/// get clobbered by the same store (getModRefInfo does not use invariantness or 1352/// things like this, and if they start, we can modify MemoryLocOrCall to 1353/// include relevant data) 1354void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1355constBasicBlock *BB,
unsignedlong &StackEpoch,
unsignedlong &PopEpoch,
1359 /// If no accesses, nothing to do. 1361if (Accesses ==
nullptr)
1364// Pop everything that doesn't dominate the current block off the stack, 1365// increment the PopEpoch to account for this. 1368 !VersionStack.
empty() &&
1369"Version stack should have liveOnEntry sentinel dominating everything");
1373while (VersionStack.
back()->getBlock() == BackBlock)
1379auto *MU = dyn_cast<MemoryUse>(&MA);
1386if (MU->isOptimized())
1389 MemoryLocOrCall UseMLOC(MU);
1390auto &LocInfo = LocStackInfo[UseMLOC];
1391// If the pop epoch changed, it means we've removed stuff from top of 1392// stack due to changing blocks. We may have to reset the lower bound or 1394if (LocInfo.PopEpoch != PopEpoch) {
1395 LocInfo.PopEpoch = PopEpoch;
1396 LocInfo.StackEpoch = StackEpoch;
1397// If the lower bound was in something that no longer dominates us, we 1399// We can't simply track stack size, because the stack may have had 1400// pushes/pops in the meantime. 1401// XXX: This is non-optimal, but only is slower cases with heavily 1402// branching dominator trees. To get the optimal number of queries would 1403// be to make lowerbound and lastkill a per-loc stack, and pop it until 1404// the top of that stack dominates us. This does not seem worth it ATM. 1405// A much cheaper optimization would be to always explore the deepest 1406// branch of the dominator tree first. This will guarantee this resets on 1407// the smallest set of blocks. 1408if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1409 !DT->
dominates(LocInfo.LowerBoundBlock, BB)) {
1410// Reset the lower bound of things to check. 1411// TODO: Some day we should be able to reset to last kill, rather than 1413 LocInfo.LowerBound = 0;
1414 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1415 LocInfo.LastKillValid =
false;
1417 }
elseif (LocInfo.StackEpoch != StackEpoch) {
1418// If all that has changed is the StackEpoch, we only have to check the 1419// new things on the stack, because we've checked everything before. In 1420// this case, the lower bound of things to check remains the same. 1421 LocInfo.PopEpoch = PopEpoch;
1422 LocInfo.StackEpoch = StackEpoch;
1424if (!LocInfo.LastKillValid) {
1425 LocInfo.LastKill = VersionStack.
size() - 1;
1426 LocInfo.LastKillValid =
true;
1429// At this point, we should have corrected last kill and LowerBound to be 1431assert(LocInfo.LowerBound < VersionStack.
size() &&
1432"Lower bound out of range");
1433assert(LocInfo.LastKill < VersionStack.
size() &&
1434"Last kill info out of range");
1435// In any case, the new upper bound is the top of the stack. 1436unsignedlong UpperBound = VersionStack.
size() - 1;
1439LLVM_DEBUG(
dbgs() <<
"MemorySSA skipping optimization of " << *MU <<
" (" 1440 << *(MU->getMemoryInst()) <<
")" 1441 <<
" because there are " 1442 << UpperBound - LocInfo.LowerBound
1443 <<
" stores to disambiguate\n");
1444// Because we did not walk, LastKill is no longer valid, as this may 1446 LocInfo.LastKillValid =
false;
1449bool FoundClobberResult =
false;
1451while (UpperBound > LocInfo.LowerBound) {
1452if (isa<MemoryPhi>(VersionStack[UpperBound])) {
1453// For phis, use the walker, see where we ended up, go there. 1454// The invariant.group handling in MemorySSA is ad-hoc and doesn't 1455// support updates, so don't use it to optimize uses. 1458 MU, *AA, UpwardWalkLimit);
1459// We are guaranteed to find it or something is wrong. 1460while (VersionStack[UpperBound] != Result) {
1464 FoundClobberResult =
true;
1468MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
1470 FoundClobberResult =
true;
1476// At the end of this loop, UpperBound is either a clobber, or lower bound 1477// PHI walking may cause it to be < LowerBound, and in fact, < LastKill. 1478if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1479 MU->setDefiningAccess(VersionStack[UpperBound],
true);
1480 LocInfo.LastKill = UpperBound;
1482// Otherwise, we checked all the new ones, and now we know we can get to 1484 MU->setDefiningAccess(VersionStack[LocInfo.LastKill],
true);
1486 LocInfo.LowerBound = VersionStack.
size() - 1;
1487 LocInfo.LowerBoundBlock = BB;
1491/// Optimize uses to point to their actual clobbering definitions. 1497unsignedlong StackEpoch = 1;
1498unsignedlong PopEpoch = 1;
1499// We perform a non-recursive top-down dominator tree walk. 1501 optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1505void MemorySSA::placePHINodes(
1507// Determine where our MemoryPhi's should go 1509 IDFs.setDefiningBlocks(DefiningBlocks);
1511 IDFs.calculate(IDFBlocks);
1513// Now place MemoryPhi nodes. 1514for (
auto &BB : IDFBlocks)
1515 createMemoryPhi(BB);
1518template <
typename IterT>
1520// We create an access to represent "live on entry", for things like 1521// arguments or users of globals, where the memory they use is defined before 1522// the beginning of the function. We do not actually insert it into the IR. 1523// We do not define a live on exit for the immediate uses, and thus our 1524// semantics do *not* imply that something with no immediate uses can simply 1528nullptr, &StartingPoint, NextID++));
1530// We maintain lists of memory accesses per-block, trading memory for time. We 1531// could just look up the memory access for every possible instruction in the 1534// Go through each block, figure out where defs occur, and chain together all 1537bool InsertIntoDef =
false;
1546 Accesses = getOrCreateAccessList(&
B);
1547 Accesses->push_back(MUD);
1548if (isa<MemoryDef>(MUD)) {
1549 InsertIntoDef =
true;
1551 Defs = getOrCreateDefsList(&
B);
1552 Defs->push_back(*MUD);
1558 placePHINodes(DefiningBlocks);
1560// Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get 1561// filled in with all blocks. 1564// Only building MemorySSA for a single loop. placePHINodes may have 1565// inserted a MemoryPhi in the loop's preheader. As this is outside the 1566// scope of the loop, set them to LiveOnEntry. 1569U.set(LiveOnEntryDef.get());
1572// Now rename accesses in the loop. Populate Visited with the exit blocks of 1573// the loop, to limit the scope of the renaming. 1583// Mark the uses in unreachable blocks as live on entry, so that they go 1586if (!Visited.
count(&BB))
1587 markUnreachableAsLiveOnEntry(&BB);
1597 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1599 Walker = std::make_unique<CachingWalker>(
this, WalkerBase.get());
1605return SkipWalker.get();
1608 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1610 SkipWalker = std::make_unique<SkipSelfWalker>(
this, WalkerBase.get());
1611return SkipWalker.get();
1615// This is a helper function used by the creation routines. It places NewAccess 1616// into the access and defs lists for a given basic block, at the given 1621auto *Accesses = getOrCreateAccessList(BB);
1623// If it's a phi node, it goes first, otherwise, it goes after any phi 1625if (isa<MemoryPhi>(NewAccess)) {
1626 Accesses->push_front(NewAccess);
1627auto *Defs = getOrCreateDefsList(BB);
1628 Defs->push_front(*NewAccess);
1631 *Accesses, [](
constMemoryAccess &MA) {
return isa<MemoryPhi>(MA); });
1632 Accesses->insert(AI, NewAccess);
1633if (!isa<MemoryUse>(NewAccess)) {
1634auto *Defs = getOrCreateDefsList(BB);
1636 *Defs, [](
constMemoryAccess &MA) {
return isa<MemoryPhi>(MA); });
1637 Defs->insert(DI, *NewAccess);
1641 Accesses->push_back(NewAccess);
1642if (!isa<MemoryUse>(NewAccess)) {
1643auto *Defs = getOrCreateDefsList(BB);
1644 Defs->push_back(*NewAccess);
1647 BlockNumberingValid.erase(BB);
1653bool WasEnd = InsertPt == Accesses->end();
1655if (!isa<MemoryUse>(What)) {
1656auto *Defs = getOrCreateDefsList(BB);
1657// If we got asked to insert at the end, we have an easy job, just shove it 1658// at the end. If we got asked to insert before an existing def, we also get 1659// an iterator. If we got asked to insert before a use, we have to hunt for 1662 Defs->push_back(*What);
1663 }
elseif (isa<MemoryDef>(InsertPt)) {
1664 Defs->insert(InsertPt->getDefsIterator(), *What);
1666while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt))
1668// Either we found a def, or we are inserting at the end 1669if (InsertPt == Accesses->end())
1670 Defs->push_back(*What);
1672 Defs->insert(InsertPt->getDefsIterator(), *What);
1675 BlockNumberingValid.erase(BB);
1679// Keep it in the lookup tables, remove from the lists 1682// Note that moving should implicitly invalidate the optimized state of a 1683// MemoryUse (and Phis can't be optimized). However, it doesn't do so for a 1685if (
auto *MD = dyn_cast<MemoryDef>(What))
1690// Move What before Where in the IR. The end result is that What will belong to 1691// the right lists and have the right Block set, but will not otherwise be 1692// correct. It will not have the right defining access, and if it is a def, 1693// things below it will not properly be updated. 1696 prepareForMoveTo(What, BB);
1702if (isa<MemoryPhi>(What)) {
1704"Can only move a Phi at the beginning of the block");
1705// Update lookup table entry 1706 ValueToMemoryAccess.erase(What->
getBlock());
1707bool Inserted = ValueToMemoryAccess.insert({BB, What}).second;
1709assert(Inserted &&
"Cannot move a Phi to a block that already has one");
1712 prepareForMoveTo(What, BB);
1719// Phi's always are placed at the front of the block. 1721 ValueToMemoryAccess[BB] = Phi;
1728bool CreationMustSucceed) {
1729assert(!isa<PHINode>(
I) &&
"Cannot create a defined access for a PHI");
1731if (CreationMustSucceed)
1732assert(NewAccess !=
nullptr &&
"Tried to create a memory access for a " 1733"non-memory touching instruction");
1735assert((!Definition || !isa<MemoryUse>(Definition)) &&
1736"A use cannot be a defining access");
1742// Return true if the instruction has ordering constraints. 1743// Note specifically that this only considers stores and loads 1744// because others are still considered ModRef by getModRefInfo. 1746if (
auto *SI = dyn_cast<StoreInst>(
I)) {
1747if (!SI->isUnordered())
1749 }
elseif (
auto *LI = dyn_cast<LoadInst>(
I)) {
1750if (!LI->isUnordered())
1756/// Helper function to create new memory accesses 1757template <
typename AliasAnalysisType>
1759 AliasAnalysisType *AAP,
1761// The assume intrinsic has a control dependency which we model by claiming 1762// that it writes arbitrarily. Debuginfo intrinsics may be considered 1763// clobbers when we have a nonstandard AA pipeline. Ignore these fake memory 1764// dependencies here. 1765// FIXME: Replace this special casing with a more accurate modelling of 1766// assume's control dependency. 1768switch (
II->getIntrinsicID()) {
1771case Intrinsic::allow_runtime_check:
1772case Intrinsic::allow_ubsan_check:
1773case Intrinsic::assume:
1774case Intrinsic::experimental_noalias_scope_decl:
1775case Intrinsic::pseudoprobe:
1780// Using a nonstandard AA pipelines might leave us with unexpected modref 1781// results for I, so add a check to not model instructions that may not read 1782// from or write to memory. This is necessary for correctness. 1783if (!
I->mayReadFromMemory() && !
I->mayWriteToMemory())
1792bool DefCheck, UseCheck;
1795// Memory accesses should only be reduced and can not be increased since AA 1796// just might return better results as a result of some transformations. 1797assert((Def == DefCheck || !DefCheck) &&
1798"Memory accesses should only be reduced");
1799if (!Def &&
Use != UseCheck) {
1800// New Access should not have more power than template access 1801assert(!UseCheck &&
"Invalid template");
1805// Find out what affect this instruction has on memory. 1807// The isOrdered check is used to ensure that volatiles end up as defs 1808// (atomics end up as ModRef right now anyway). Until we separate the 1809// ordering chain from the memory chain, this enables people to see at least 1810// some relative ordering to volatiles. Note that getClobberingMemoryAccess 1811// will still give an answer that bypasses other volatile loads. TODO: 1812// Separate memory aliasing and ordering into two different chains so that 1813// we can precisely represent both "what memory will this read/write/is 1814// clobbered by" and "what instructions can I move this past". 1819// It's possible for an instruction to not modify memory at all. During 1820// construction, we ignore them. 1826 MUD =
newMemoryDef(
I->getContext(),
nullptr,
I,
I->getParent(), NextID++);
1828 MUD =
newMemoryUse(
I->getContext(),
nullptr,
I,
I->getParent());
1834 ValueToMemoryAccess[
I] = MUD;
1838/// Properly remove \p MA from all of MemorySSA's lookup tables. 1841"Trying to remove memory access that still has uses");
1842 BlockNumbering.erase(MA);
1843if (
auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1845// Invalidate our walker's cache if necessary 1846if (!isa<MemoryUse>(MA))
1850if (
constauto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1855auto VMA = ValueToMemoryAccess.find(MemoryInst);
1856if (VMA->second == MA)
1857 ValueToMemoryAccess.erase(VMA);
1860/// Properly remove \p MA from all of MemorySSA's lists. 1862/// Because of the way the intrusive list and use lists work, it is important to 1863/// do removal in the right order. 1864/// ShouldDelete defaults to true, and will cause the memory access to also be 1865/// deleted, not just removed. 1868// The access list owns the reference, so we erase it from the non-owning list 1870if (!isa<MemoryUse>(MA)) {
1871auto DefsIt = PerBlockDefs.
find(BB);
1872 std::unique_ptr<DefsList> &Defs = DefsIt->second;
1875 PerBlockDefs.
erase(DefsIt);
1878// The erase call here will delete it. If we don't want it deleted, we call 1880auto AccessIt = PerBlockAccesses.
find(BB);
1881 std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1883 Accesses->erase(MA);
1885 Accesses->remove(MA);
1887if (Accesses->empty()) {
1888 PerBlockAccesses.
erase(AccessIt);
1889 BlockNumberingValid.erase(BB);
1894 MemorySSAAnnotatedWriter Writer(
this);
1898F->print(
OS, &Writer);
1901#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1906#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS) 1918assert(L &&
"must either have loop or function");
1921 return *const_cast<BasicBlock *>(BB);
1929// Previously, the verification used to also verify that the clobberingAccess 1930// cached by MemorySSA is the same as the clobberingAccess found at a later 1931// query to AA. This does not hold true in general due to the current fragility 1932// of BasicAA which has arbitrary caps on the things it analyzes before giving 1933// up. As a result, transformations that are correct, will lead to BasicAA 1934// returning different Alias answers before and after that transformation. 1935// Invalidating MemorySSA is not an option, as the results in BasicAA can be so 1936// random, in the worst case we'd need to rebuild MemorySSA from scratch after 1937// every transformation, which defeats the purpose of using it. For such an 1938// example, see test4 added in D51960. 1941template <
typename IterT>
1945for (
unsignedI = 0, E = Phi->getNumIncomingValues();
I != E; ++
I) {
1946auto *Pred = Phi->getIncomingBlock(
I);
1947auto *IncAcc = Phi->getIncomingValue(
I);
1948// If Pred has no unreachable predecessors, get last def looking at 1949// IDoms. If, while walkings IDoms, any of these has an unreachable 1950// predecessor, then the incoming def can be any access. 1951if (
auto *DTNode = DT->
getNode(Pred)) {
1954auto *LastAcc = &*(--DefList->end());
1955assert(LastAcc == IncAcc &&
1956"Incorrect incoming access into phi.");
1961 DTNode = DTNode->getIDom();
1964// If Pred has unreachable predecessors, but has at least a Def, the 1965// incoming access can be the last Def in Pred, or it could have been 1966// optimized to LoE. After an update, though, the LoE may have been 1967// replaced by another access, so IncAcc may be any access. 1968// If Pred has unreachable predecessors and no Defs, incoming access 1969// should be LoE; However, after an update, it may be any access. 1976/// Verify that all of the blocks we believe to have valid domination numbers 1977/// actually have valid domination numbers. 1978template <
typename IterT>
1980if (BlockNumberingValid.empty())
1985if (!ValidBlocks.
count(&BB))
1988 ValidBlocks.
erase(&BB);
1991// It's correct to say an empty block has valid numbering. 1995// Block numbering starts at 1. 1996unsignedlong LastNumber = 0;
1998auto ThisNumberIter = BlockNumbering.find(&MA);
1999assert(ThisNumberIter != BlockNumbering.end() &&
2000"MemoryAccess has no domination number in a valid block!");
2002unsignedlong ThisNumber = ThisNumberIter->second;
2003assert(ThisNumber > LastNumber &&
2004"Domination numbers should be strictly increasing!");
2006 LastNumber = ThisNumber;
2011"All valid BasicBlocks should exist in F -- dangling pointers?");
2014/// Verify ordering: the order and existence of MemoryAccesses matches the 2015/// order and existence of memory affecting instructions. 2016/// Verify domination: each definition dominates all of its uses. 2017/// Verify def-uses: the immediate use information - walk all the memory 2018/// accesses and verifying that, for each use, it appears in the appropriate 2020template <
typename IterT>
2023// Walk all the blocks, comparing what the lookups think and what the access 2024// lists think, as well as the order in the blocks vs the order in the access 2037for (
constUse &U : Phi->uses()) {
2041// Verify def-uses for full verify. 2044"Incomplete MemoryPhi Node");
2045for (
unsignedI = 0, E = Phi->getNumIncomingValues();
I != E; ++
I) {
2046 verifyUseInDefs(Phi->getIncomingValue(
I), Phi);
2048"Incoming phi block not a block predecessor");
2055assert((!MA || (AL && (isa<MemoryUse>(MA) ||
DL))) &&
2056"We have memory affecting instructions " 2057"in this block but they are not in the " 2058"access list or defs list");
2065// Verify domination. 2066for (
constUse &U : MD->
uses()) {
2068"Memory Def does not dominate it's uses");
2072// Verify def-uses for full verify. 2077// Either we hit the assert, really have no accesses, or we have both 2078// accesses and an access list. Same with defs. 2083"We don't have the same number of accesses in the block as on the " 2086"Either we should have a defs list, or we should have no defs");
2088"We don't have the same number of defs in the block as on the " 2090auto ALI = AL->begin();
2091auto AAI = ActualAccesses.
begin();
2092while (ALI != AL->end() && AAI != ActualAccesses.
end()) {
2093assert(&*ALI == *AAI &&
"Not the same accesses in the same order");
2097 ActualAccesses.
clear();
2100auto ADI = ActualDefs.
begin();
2101while (DLI !=
DL->
end() && ADI != ActualDefs.
end()) {
2102assert(&*DLI == *ADI &&
"Not the same defs in the same order");
2111/// Verify the def-use lists in MemorySSA, by verifying that \p Use 2112/// appears in the use list of \p Def. 2114// The live on entry use may cause us to get a NULL def here 2117"Null def but use not point to live on entry def");
2120"Did not find use in def's use list");
2123/// Perform a local numbering on blocks so that instruction ordering can be 2124/// determined in constant time. 2125/// TODO: We currently just number in order. If we numbered by N, we could 2126/// allow at least N-1 sequences of insertBefore or insertAfter (and at least 2127/// log2(N) sequences of mixed before and after) without needing to invalidate 2129void MemorySSA::renumberBlock(
constBasicBlock *
B)
const{
2130// The pre-increment ensures the numbers really start at 1. 2131unsignedlong CurrentNumber = 0;
2133assert(AL !=
nullptr &&
"Asking to renumber an empty block");
2134for (
constauto &
I : *AL)
2135 BlockNumbering[&
I] = ++CurrentNumber;
2136 BlockNumberingValid.insert(
B);
2139/// Determine, for two memory accesses in the same block, 2140/// whether \p Dominator dominates \p Dominatee. 2141/// \returns True if \p Dominator dominates \p Dominatee. 2147"Asking for local domination when accesses are in different blocks!");
2148// A node dominates itself. 2149if (Dominatee == Dominator)
2152// When Dominatee is defined on function entry, it is not dominated by another 2157// When Dominator is defined on function entry, it dominates the other memory 2162if (!BlockNumberingValid.count(DominatorBlock))
2163 renumberBlock(DominatorBlock);
2165unsignedlong DominatorNum = BlockNumbering.lookup(Dominator);
2166// All numbers start with 1 2167assert(DominatorNum != 0 &&
"Block was not numbered properly");
2168unsignedlong DominateeNum = BlockNumbering.lookup(Dominatee);
2169assert(DominateeNum != 0 &&
"Block was not numbered properly");
2170return DominatorNum < DominateeNum;
2175if (Dominator == Dominatee)
2187constUse &Dominatee)
const{
2189BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
2190// The def must dominate the incoming block of the phi. 2193// If the UseBB and the DefBB are the same, compare locally. 2196// If it's not a PHI node use, the normal dominates can already handle it. 2212switch (getValueID()) {
2230OS << getID() <<
" = MemoryDef(";
2236 printID(getOptimized());
2241 ListSeparator LS(
",");
2242OS << getID() <<
" = MemoryPhi(";
2243for (
constauto &
Op : operands()) {
2265if (UO && UO->
getID())
2273// Cannot completely remove virtual function even in release mode. 2274#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2283 MemorySSAAnnotatedWriter MSSAWriter;
2287 :
F(
F), MSSAWriter(&MSSA) {}
2301// nodes_iterator/begin/end - Allow iteration over all nodes in the graph 2333 [](std::string &S,
unsigned &
I,
unsignedIdx) ->
void {
2334 std::string Str = S.substr(
I,
Idx -
I);
2336if (SR.
count(
" = MemoryDef(") || SR.
count(
" = MemoryPhi(") ||
2337 SR.
count(
"MemoryUse("))
2348 /// Display the raw branch weights from PGO. 2356returngetNodeLabel(Node, CFGInfo).find(
';') != std::string::npos
2357 ?
"style=filled, fillcolor=lightpink" 2385if (EnsureOptimizedUses)
2391OS <<
"MemorySSA for function: " <<
F.getName() <<
"\n";
2401OS <<
"MemorySSA (walker) for function: " <<
F.getName() <<
"\n";
2402 MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2403F.print(
OS, &Writer);
2430auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2431auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2447/// Walk the use-def chains starting at \p StartingAccess and find 2448/// the MemoryAccess that actually clobbers Loc. 2450/// \returns our clobbering memory access 2454assert(!isa<MemoryUse>(StartingAccess) &&
"Use cannot be defining access");
2456// If location is undefined, conservatively return starting access. 2457if (Loc.
Ptr ==
nullptr)
2458return StartingAccess;
2461if (
auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
2463return StartingUseOrDef;
2465I = StartingUseOrDef->getMemoryInst();
2467// Conservatively, fences are always clobbers, so don't perform the walk if 2469if (!isa<CallBase>(
I) &&
I->isFenceLike())
2470return StartingUseOrDef;
2473 UpwardsMemoryQuery Q;
2474 Q.OriginalAccess = StartingAccess;
2475 Q.StartingLoc = Loc;
2479// Unlike the other function, do not walk to the def of a def, because we are 2480// handed something we already believe is the clobbering access. 2481// We never set SkipSelf to true in Q in this method. 2483 Walker.findClobber(BAA, StartingAccess, Q, UpwardWalkLimit);
2485dbgs() <<
"Clobber starting at access " << *StartingAccess <<
"\n";
2487dbgs() <<
" for instruction " << *
I <<
"\n";
2488dbgs() <<
" is " << *Clobber <<
"\n";
2495if (!
I.hasMetadata(LLVMContext::MD_invariant_group) ||
I.isVolatile())
2498// We consider bitcasts and zero GEPs to be the same pointer value. Start by 2499// stripping bitcasts and zero GEPs, then we will recursively look at loads 2500// and stores through bitcasts and zero GEPs. 2503// It's not safe to walk the use list of a global value because function 2504// passes aren't allowed to look outside their functions. 2505// FIXME: this could be fixed by filtering instructions from outside of 2507if (isa<Constant>(PointerOperand))
2512for (
constUser *Us : PointerOperand->
users()) {
2513auto *U = dyn_cast<Instruction>(Us);
2514if (!U || U == &
I || !DT.
dominates(U, MostDominatingInstruction))
2517// If we hit a load/store with an invariant.group metadata and the same 2518// pointer operand, we can assume that value pointed to by the pointer 2519// operand didn't change. 2520if (U->hasMetadata(LLVMContext::MD_invariant_group) &&
2522 MostDominatingInstruction = U;
2526return MostDominatingInstruction == &
I ? nullptr : MostDominatingInstruction;
2531bool SkipSelf,
bool UseInvariantGroup) {
2532auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
2533// If this is a MemoryPhi, we can't do anything. 2537if (UseInvariantGroup) {
2539 *StartingAccess->getMemoryInst(), MSSA->
getDomTree())) {
2540assert(isa<LoadInst>(
I) || isa<StoreInst>(
I));
2544if (isa<MemoryUse>(ClobberMA))
2545return ClobberMA->getDefiningAccess();
2550bool IsOptimized =
false;
2552// If this is an already optimized use or def, return the optimized result. 2553// Note: Currently, we store the optimized def result in a separate field, 2554// since we can't use the defining access. 2555if (StartingAccess->isOptimized()) {
2556if (!SkipSelf || !isa<MemoryDef>(StartingAccess))
2557return StartingAccess->getOptimized();
2562// We can't sanely do anything with a fence, since they conservatively clobber 2563// all memory, and have no locations to get pointers from to try to 2565if (!isa<CallBase>(
I) &&
I->isFenceLike())
2566return StartingAccess;
2568 UpwardsMemoryQuery Q(
I, StartingAccess);
2572 StartingAccess->setOptimized(LiveOnEntry);
2578// Start with the thing we already think clobbers this location 2579MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2581// At this point, DefiningAccess may be the live on entry def. 2582// If it is, we will not get a better result. 2584 StartingAccess->setOptimized(DefiningAccess);
2585return DefiningAccess;
2589 Walker.findClobber(BAA, DefiningAccess, Q, UpwardWalkLimit);
2590 StartingAccess->setOptimized(OptimizedAccess);
2592 OptimizedAccess = StartingAccess->getOptimized();
2594LLVM_DEBUG(
dbgs() <<
"Starting Memory SSA clobber for " << *
I <<
" is ");
2596LLVM_DEBUG(
dbgs() <<
"Optimized Memory SSA clobber for " << *
I <<
" is ");
2600if (SkipSelf && isa<MemoryPhi>(OptimizedAccess) &&
2601 isa<MemoryDef>(StartingAccess) && UpwardWalkLimit) {
2602assert(isa<MemoryDef>(Q.OriginalAccess));
2603 Q.SkipSelfAccess =
true;
2604 Result = Walker.findClobber(BAA, OptimizedAccess, Q, UpwardWalkLimit);
2606 Result = OptimizedAccess;
2608LLVM_DEBUG(
dbgs() <<
"Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2617if (
auto *
Use = dyn_cast<MemoryUseOrDef>(MA))
2618returnUse->getDefiningAccess();
2624if (
auto *
Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
2625returnUse->getDefiningAccess();
2626return StartingAccess;
2641bool upward_defs_iterator::IsGuaranteedLoopInvariant(
constValue *
Ptr)
const{
2642auto IsGuaranteedLoopInvariantBase = [](
constValue *
Ptr) {
2643Ptr =
Ptr->stripPointerCasts();
2644if (!isa<Instruction>(
Ptr))
2646return isa<AllocaInst>(
Ptr);
2649Ptr =
Ptr->stripPointerCasts();
2650if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
2651if (
I->getParent()->isEntryBlock())
2654if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr)) {
2655return IsGuaranteedLoopInvariantBase(
GEP->getPointerOperand()) &&
2656GEP->hasAllConstantIndices();
2658return IsGuaranteedLoopInvariantBase(
Ptr);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Atomic ordering constants.
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
#define LLVM_ATTRIBUTE_UNUSED
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
This file provides utility analysis objects describing memory locations.
static bool instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc, const Instruction *UseInst, AliasAnalysisType &AA)
Memory static true cl::opt< unsigned > MaxCheckLimit("memssa-check-limit", cl::Hidden, cl::init(100), cl::desc("The maximum number of stores/phis MemorySSA" "will consider trying to walk past (default = 100)"))
static cl::opt< bool, true > VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA), cl::Hidden, cl::desc("Enable verification of MemorySSA."))
static const char LiveOnEntryStr[]
static LLVM_ATTRIBUTE_UNUSED void checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt, const MemoryLocation &StartLoc, const MemorySSA &MSSA, const UpwardsMemoryQuery &Query, BatchAAResults &AA, bool AllowImpreciseClobber=false)
Verifies that Start is clobbered by ClobberAt, and that nothing inbetween Start and ClobberAt can clo...
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 cl::opt< std::string > DotCFGMSSA("dot-cfg-mssa", cl::value_desc("file name for generated dot file"), cl::desc("file name for generated dot file"), cl::init(""))
static bool isOrdered(const Instruction *I)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS)
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
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 <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
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()
virtual void emitBasicBlockStartAnnot(const BasicBlock *, formatted_raw_ostream &)
emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...
virtual void emitInstructionAnnot(const Instruction *, formatted_raw_ostream &)
emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...
LLVM Basic Block Representation.
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.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Extension point for the Value hierarchy.
MemoryAccess * getClobberingMemoryAccess(MemoryAccess *, BatchAAResults &) override
Does the same thing as getClobberingMemoryAccess(const Instruction *I), but takes a MemoryAccess inst...
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
A wrapper class for inspecting calls to intrinsic functions.
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.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Represents a single loop in the control flow graph.
BasicBlock * getBlock() const
void print(raw_ostream &OS) const
unsigned getID() const
Used for debugging and tracking things about MemoryAccesses.
void setBlock(BasicBlock *BB)
Used by MemorySSA to change the block of a MemoryAccess when it is moved.
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
void print(raw_ostream &OS) const
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
const Value * Ptr
The address of the start of the location.
Represents phi nodes for memory accesses.
void print(raw_ostream &OS) const
An analysis that produces MemorySSA for a function.
Result run(Function &F, FunctionAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This is the generic walker interface for walkers of MemorySSA.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
MemorySSAWalker(MemorySSA *)
virtual void invalidateInfo(MemoryAccess *)
Given a memory access, invalidate anything this walker knows about that access.
Legacy analysis pass which computes MemorySSA.
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 *, const MemoryLocation &, BatchAAResults &, unsigned &)
Walk the use-def chains starting at StartingAccess and find the MemoryAccess that actually clobbers L...
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.
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where)
simple_ilist< MemoryAccess, ilist_tag< MSSAHelpers::DefsOnlyTag > > DefsList
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
MemorySSAWalker * getSkipSelfWalker()
MemorySSA(Function &, AliasAnalysis *, DominatorTree *)
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 ...
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, InsertionPlace)
MemorySSAWalker * getWalker()
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator)
MemoryUseOrDef * createDefinedAccess(Instruction *, MemoryAccess *, const MemoryUseOrDef *Template=nullptr, bool CreationMustSucceed=true)
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
DominatorTree & getDomTree() const
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
MemoryAccess * getLiveOnEntryDef() const
void removeFromLookups(MemoryAccess *)
Properly remove MA from all of MemorySSA's lookup tables.
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
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
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.
iplist< MemoryAccess, ilist_tag< MSSAHelpers::AllAccessTag > > AccessList
void print(raw_ostream &) const
Class that has the common methods + fields of memory uses/defs.
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false)
void setOptimized(MemoryAccess *)
Sets the optimized use for a MemoryDef.
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Represents read-only accesses to memory.
void print(raw_ostream &OS) const
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
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.
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 push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
size_t count(char C) const
Return the number of occurrences of C in the string.
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
void dropAllReferences()
Drop all references to operands.
LLVM Value Representation.
iterator_range< user_iterator > users()
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.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
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.
base_list_type::iterator iterator
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
A simple intrusive list implementation.
reverse_iterator rbegin()
This class provides various memory handling functions that manipulate MemoryBlock instances.
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.
@ C
The default llvm calling convention, compatible with C.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
NodeAddr< PhiNode * > Phi
NodeAddr< DefNode * > Def
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.
void initializeMemorySSAWrapperPassPass(PassRegistry &)
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_READONLY APFloat maximum(const APFloat &A, const APFloat &B)
Implements IEEE 754-2019 maximum semantics.
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...
auto pred_size(const MachineBasicBlock *BB)
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto map_range(ContainerTy &&C, FuncTy F)
iterator_range< def_chain_iterator< T > > def_chain(T MA, MemoryAccess *UpTo=nullptr)
bool isModSet(const ModRefInfo MRI)
auto find_if_not(R &&Range, UnaryPredicate P)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isAtLeastOrStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
bool isModOrRefSet(const ModRefInfo MRI)
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...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool VerifyMemorySSA
Enables verification of MemorySSA.
std::pair< MemoryAccess *, MemoryLocation > MemoryAccessPair
upward_defs_iterator upward_defs_end()
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool isRefSet(const ModRefInfo MRI)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
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)
DOTGraphTraits(bool IsSimple=false)
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
Description of the encoding of one expression Op.
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS)
static unsigned getHashValue(const MemoryLocOrCall &MLOC)
static MemoryLocOrCall getEmptyKey()
static MemoryLocOrCall getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
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)
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
