32#include "llvm/Config/llvm-config.h"
63#define DEBUG_TYPE "memoryssa"
73#ifdef EXPENSIVE_CHECKS
93 MemorySSAAnnotatedWriter(
const MemorySSA *M) : MSSA(M) {}
95 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
98 OS <<
"; " << *MA <<
"\n";
104 OS <<
"; " << *MA <<
"\n";
116 MemorySSAWalkerAnnotatedWriter(
MemorySSA *M)
117 : MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
119 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
122 OS <<
"; " << *MA <<
"\n";
131 OS <<
" - clobbered by ";
151class MemoryLocOrCall {
155 MemoryLocOrCall(MemoryUseOrDef *MUD)
156 : MemoryLocOrCall(MUD->getMemoryInst()) {}
157 MemoryLocOrCall(
const MemoryUseOrDef *MUD)
158 : MemoryLocOrCall(MUD->getMemoryInst()) {}
160 MemoryLocOrCall(Instruction *Inst) {
173 explicit MemoryLocOrCall(
const MemoryLocation &Loc) : Loc(Loc) {}
175 const CallBase *getCall()
const {
180 MemoryLocation getLoc()
const {
186 if (IsCall !=
Other.IsCall)
190 return Loc ==
Other.Loc;
197 Other.Call->arg_begin());
202 const CallBase *
Call;
220 MLOC.getCall()->getCalledOperand()));
222 for (
const Value *Arg : MLOC.getCall()->args())
227 static bool isEqual(
const MemoryLocOrCall &LHS,
const MemoryLocOrCall &RHS) {
242 bool VolatileUse =
Use->isVolatile();
243 bool VolatileClobber = MayClobber->
isVolatile();
245 if (VolatileUse && VolatileClobber)
261 return !(SeqCstUse || MayClobberIsAcquire);
264template <
typename AliasAnalysisType>
269 assert(DefInst &&
"Defining instruction not actually an instruction");
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:
306template <
typename AliasAnalysisType>
308 const MemoryLocOrCall &UseMLOC,
309 AliasAnalysisType &
AA) {
327struct UpwardsMemoryQuery {
337 bool SkipSelfAccess =
false;
339 UpwardsMemoryQuery() =
default;
350template <
typename AliasAnalysisType>
355 if (
I->hasMetadata(LLVMContext::MD_invariant_load))
376[[maybe_unused]]
static void
380 bool AllowImpreciseClobber =
false) {
381 assert(MSSA.
dominates(ClobberAt, Start) &&
"Clobber doesn't dominate start?");
385 "liveOnEntry must clobber itself");
389 bool FoundClobber =
false;
392 Worklist.
push_back({Start, StartLoc,
false});
395 while (!Worklist.
empty()) {
403 if (MA == ClobberAt) {
430 "Found clobber before reaching ClobberAt!");
437 "Can only find use in def chain if Start is a use");
458 if (AllowImpreciseClobber)
464 "ClobberAt never acted as a clobber");
473 using ListIndex = unsigned;
483 std::optional<ListIndex> Previous;
484 bool MayBeCrossIteration;
486 DefPath(
const MemoryLocation &Loc, MemoryAccess *
First, MemoryAccess *
Last,
487 bool MayBeCrossIteration, std::optional<ListIndex> Previous)
489 MayBeCrossIteration(MayBeCrossIteration) {}
491 DefPath(
const MemoryLocation &Loc, MemoryAccess *Init,
492 bool MayBeCrossIteration, std::optional<ListIndex> Previous)
493 : DefPath(Loc, Init, Init, MayBeCrossIteration, Previous) {}
499 UpwardsMemoryQuery *Query;
500 unsigned *UpwardWalkLimit;
507 DenseSet<UpwardDefsElem> VisitedPhis;
510 const MemoryAccess *getWalkTarget(
const MemoryPhi *From)
const {
516 while ((Node =
Node->getIDom())) {
525 struct UpwardsWalkResult {
538 walkToPhiOrClobber(DefPath &
Desc,
const MemoryAccess *StopAt =
nullptr,
539 const MemoryAccess *SkipStopAt =
nullptr)
const {
541 assert(UpwardWalkLimit &&
"Need a valid walk limit");
542 bool LimitAlreadyReached =
false;
547 if (!*UpwardWalkLimit) {
548 *UpwardWalkLimit = 1;
549 LimitAlreadyReached =
true;
554 if (Current == StopAt || Current == SkipStopAt)
555 return {Current,
false};
561 if (!--*UpwardWalkLimit)
562 return {Current,
true};
564 BatchAACrossIterationScope
_(*AA,
Desc.MayBeCrossIteration);
570 if (LimitAlreadyReached)
571 *UpwardWalkLimit = 0;
574 "Ended at a non-clobber that's not a phi?");
575 return {
Desc.Last,
false};
578 void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
579 ListIndex PriorNode,
bool MayBeCrossIteration) {
580 auto UpwardDefsBegin =
583 for (
const UpwardDefsElem &
E : UpwardDefs) {
592 struct TerminatedPath {
593 MemoryAccess *Clobber;
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?");
615 while (!PausedSearches.
empty()) {
617 DefPath &
Node = Paths[PathIndex];
637 if (!VisitedPhis.
insert({Node.Last, Node.Loc, Node.MayBeCrossIteration})
641 const MemoryAccess *SkipStopWhere =
nullptr;
642 if (Query->SkipSelfAccess &&
Node.Loc == Query->StartingLoc) {
644 SkipStopWhere = Query->OriginalAccess;
647 UpwardsWalkResult Res = walkToPhiOrClobber(Node,
650 if (Res.IsKnownClobber) {
651 assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
655 TerminatedPath
Term{Res.Result, PathIndex};
656 if (!MSSA.
dominates(Res.Result, StopWhere))
664 if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
669 if (Res.Result != SkipStopWhere)
676 Node.MayBeCrossIteration);
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) {}
691 generic_def_path_iterator &operator++() {
692 N = curNode().Previous;
696 bool operator==(
const generic_def_path_iterator &O)
const {
697 if (
N.has_value() !=
O.N.has_value())
699 return !
N || *
N == *
O.N;
703 T &curNode()
const {
return W->Paths[*
N]; }
706 std::optional<ListIndex>
N;
709 using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
712 return make_range(def_path_iterator(
this, From), def_path_iterator());
717 TerminatedPath PrimaryClobber;
723 ListIndex defPathIndex(
const DefPath &
N)
const {
725 const DefPath *NP = &
N;
727 "Out of bounds DefPath!");
728 return NP - &Paths.
front();
744 OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
745 const MemoryLocation &Loc) {
747 "Reset the optimization state.");
753 auto PriorPathsSize = Paths.
size();
759 addSearches(Phi, PausedSearches, 0,
false);
763 auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) {
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))
771 std::iter_swap(
Last, Dom);
774 MemoryPhi *Current =
Phi;
777 "liveOnEntry wasn't treated as a clobber?");
779 const auto *
Target = getWalkTarget(Current);
782 assert(
all_of(TerminatedPaths, [&](
const TerminatedPath &
P) {
789 if (std::optional<TerminatedPath> Blocker = getBlockingAccess(
790 Target, PausedSearches, NewPaused, TerminatedPaths)) {
794 auto Iter =
find_if(def_path(Blocker->LastNode), [&](
const DefPath &
N) {
795 return defPathIndex(N) < PriorPathsSize;
797 assert(Iter != def_path_iterator());
799 DefPath &CurNode = *Iter;
800 assert(CurNode.Last == Current);
827 TerminatedPath
Result{CurNode.Last, defPathIndex(CurNode)};
834 if (NewPaused.
empty()) {
835 MoveDominatedPathToEnd(TerminatedPaths);
837 return {
Result, std::move(TerminatedPaths)};
840 MemoryAccess *DefChainEnd =
nullptr;
842 for (ListIndex Paused : NewPaused) {
843 UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
844 if (WR.IsKnownClobber)
848 DefChainEnd = WR.Result;
851 if (!TerminatedPaths.
empty()) {
855 for (
auto *MA :
def_chain(
const_cast<MemoryAccess *
>(Target)))
857 assert(DefChainEnd &&
"Failed to find dominating phi/liveOnEntry");
862 for (
const TerminatedPath &TP : TerminatedPaths) {
865 if (DT.
dominates(ChainBB, TP.Clobber->getBlock()))
872 if (!Clobbers.
empty()) {
873 MoveDominatedPathToEnd(Clobbers);
875 return {
Result, std::move(Clobbers)};
879 [&](ListIndex
I) {
return Paths[
I].Last == DefChainEnd; }));
884 PriorPathsSize = Paths.
size();
885 PausedSearches.
clear();
886 for (ListIndex
I : NewPaused)
887 addSearches(DefChainPhi, PausedSearches,
I,
888 Paths[
I].MayBeCrossIteration);
891 Current = DefChainPhi;
895 void verifyOptResult(
const OptznResult &R)
const {
897 return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
901 void resetPhiOptznState() {
907 ClobberWalker(
const MemorySSA &MSSA, DominatorTree &DT)
908 : MSSA(MSSA), DT(DT) {}
912 MemoryAccess *findClobber(BatchAAResults &BAA, MemoryAccess *Start,
913 UpwardsMemoryQuery &Q,
unsigned &UpWalkLimit) {
916 UpwardWalkLimit = &UpWalkLimit;
921 MemoryAccess *Current =
Start;
925 Current = MU->getDefiningAccess();
927 DefPath FirstDesc(Q.StartingLoc, Current, Current,
928 false, std::nullopt);
931 UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
933 if (WalkResult.IsKnownClobber) {
934 Result = WalkResult.Result;
937 Current, Q.StartingLoc);
938 verifyOptResult(OptRes);
939 resetPhiOptznState();
940 Result = OptRes.PrimaryClobber.Clobber;
943#ifdef EXPENSIVE_CHECKS
944 if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
951struct RenamePassData {
953 DomTreeNode::const_iterator ChildIt;
954 MemoryAccess *IncomingVal;
956 RenamePassData(
DomTreeNode *
D, DomTreeNode::const_iterator It,
958 : DTN(
D), ChildIt(It), IncomingVal(
M) {}
960 void swap(RenamePassData &
RHS) {
972 ClobberWalker Walker;
989 bool UseInvariantGroup =
true);
1007 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false);
1012 return Walker->getClobberingMemoryAccessBase(MA,
Loc, BAA, UWL);
1017 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
false,
false);
1022 unsigned UpwardWalkLimit =
MSSA->Opts.memssa_check_limit;
1028 unsigned UpwardWalkLimit =
MSSA->Opts.memssa_check_limit;
1034 MUD->resetOptimized();
1050 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL,
true);
1055 return Walker->getClobberingMemoryAccessBase(MA,
Loc, BAA, UWL);
1060 unsigned UpwardWalkLimit =
MSSA->Opts.memssa_check_limit;
1066 unsigned UpwardWalkLimit =
MSSA->Opts.memssa_check_limit;
1072 MUD->resetOptimized();
1079 bool RenameAllUses) {
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;
1094 (void) ReplacementDone;
1095 assert(ReplacementDone &&
"Incomplete phi during partial rename");
1097 Phi->addIncoming(IncomingVal, BB);
1105 bool RenameAllUses) {
1108 for (MemoryAccess &L : *
Accesses) {
1110 if (MUD->getDefiningAccess() ==
nullptr || RenameAllUses)
1111 MUD->setDefiningAccess(IncomingVal);
1128 bool SkipVisited,
bool RenameAllUses) {
1129 assert(Root &&
"Trying to rename accesses in an unreachable block");
1136 if (SkipVisited && AlreadyVisited)
1139 IncomingVal = renameBlock(Root->
getBlock(), IncomingVal, RenameAllUses);
1140 renameSuccessorPhis(Root->
getBlock(), IncomingVal, RenameAllUses);
1143 while (!WorkStack.
empty()) {
1145 DomTreeNode::const_iterator ChildIt = WorkStack.
back().ChildIt;
1146 IncomingVal = WorkStack.
back().IncomingVal;
1148 if (ChildIt ==
Node->end()) {
1152 ++WorkStack.
back().ChildIt;
1156 AlreadyVisited = !Visited.
insert(BB).second;
1157 if (SkipVisited && AlreadyVisited) {
1164 IncomingVal = &*BlockDefs->rbegin();
1166 IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1167 renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1176void MemorySSA::markUnreachableAsLiveOnEntry(
BasicBlock *BB) {
1177 assert(!DT->isReachableFromEntry(BB) &&
1178 "Reachable block found while handling unreachable blocks");
1185 if (!DT->isReachableFromEntry(S))
1192 Phi->addIncoming(LiveOnEntryDef.get(), BB);
1200 auto Next = std::next(AI);
1204 UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1213 BlockNumberEpoch(Func.getBlockNumberEpoch()), LiveOnEntryDef(nullptr),
1214 Walker(nullptr), SkipWalker(nullptr) {
1220 assert(AA &&
"No alias analysis?");
1232 BlockNumberEpoch(L.getHeader()->
getParent()->getBlockNumberEpoch()),
1233 LiveOnEntryDef(nullptr), Walker(nullptr), SkipWalker(nullptr) {
1239 assert(AA &&
"No alias analysis?");
1243 return *const_cast<BasicBlock *>(BB);
1254 for (
const BlockInfo &Info : PerBlock)
1260MemorySSA::BlockInfo &MemorySSA::getOrCreateBlockInfo(
const BasicBlock *BB) {
1261 unsigned N = getBlockIndex(BB);
1262 if (
N >= PerBlock.
size())
1267template <
typename ListT>
1268ListT *MemorySSA::getOrCreateList(ListPtr<ListT> &List) {
1270 List.reset(
new (UseOrDefAllocator) ListT());
1287 : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1293 struct MemlocStackInfo {
1296 unsigned long StackEpoch;
1297 unsigned long PopEpoch;
1302 unsigned long LowerBound;
1305 unsigned long LastKill;
1309 void optimizeUsesInBlock(
const BasicBlock *,
unsigned long &,
unsigned long &,
1314 CachingWalker *Walker;
1333void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1334 const BasicBlock *BB,
unsigned long &StackEpoch,
unsigned long &PopEpoch,
1347 !VersionStack.
empty() &&
1348 "Version stack should have liveOnEntry sentinel dominating everything");
1350 if (DT->dominates(BackBlock, BB))
1352 while (VersionStack.
back()->getBlock() == BackBlock)
1357 for (MemoryAccess &MA : *
Accesses) {
1365 if (MU->isOptimized())
1368 MemoryLocOrCall UseMLOC(MU);
1369 auto &LocInfo = LocStackInfo[UseMLOC];
1373 if (LocInfo.PopEpoch != PopEpoch) {
1374 LocInfo.PopEpoch = PopEpoch;
1375 LocInfo.StackEpoch = StackEpoch;
1387 if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1388 !DT->dominates(LocInfo.LowerBoundBlock, BB)) {
1392 LocInfo.LowerBound = 0;
1393 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1394 LocInfo.LastKillValid =
false;
1396 }
else if (LocInfo.StackEpoch != StackEpoch) {
1400 LocInfo.PopEpoch = PopEpoch;
1401 LocInfo.StackEpoch = StackEpoch;
1403 if (!LocInfo.LastKillValid) {
1404 LocInfo.LastKill = VersionStack.
size() - 1;
1405 LocInfo.LastKillValid =
true;
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");
1415 unsigned long UpperBound = VersionStack.
size() - 1;
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");
1425 LocInfo.LastKillValid =
false;
1428 bool FoundClobberResult =
false;
1429 unsigned UpwardWalkLimit = MSSA->Opts.memssa_check_limit;
1430 while (UpperBound > LocInfo.LowerBound) {
1436 Walker->getClobberingMemoryAccessWithoutInvariantGroup(
1437 MU, *AA, UpwardWalkLimit);
1439 while (VersionStack[UpperBound] != Result) {
1443 FoundClobberResult =
true;
1449 FoundClobberResult =
true;
1457 if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1458 MU->setDefiningAccess(VersionStack[UpperBound],
true);
1459 LocInfo.LastKill = UpperBound;
1463 MU->setDefiningAccess(VersionStack[LocInfo.LastKill],
true);
1465 LocInfo.LowerBound = VersionStack.
size() - 1;
1466 LocInfo.LowerBoundBlock = BB;
1474 VersionStack.
push_back(MSSA->getLiveOnEntryDef());
1476 unsigned long StackEpoch = 1;
1477 unsigned long PopEpoch = 1;
1479 for (
const auto *DomNode :
depth_first(DT->getRootNode()))
1480 optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1484void MemorySSA::placePHINodes(
1488 IDFs.setDefiningBlocks(DefiningBlocks);
1490 IDFs.calculate(IDFBlocks);
1493 for (
auto &BB : IDFBlocks)
1494 createMemoryPhi(BB);
1499template <
typename AccessT,
typename AllocatorT,
typename... ArgTs>
1502 char *Mem =
static_cast<char *
>(
1503 Allocator.Allocate(OpsSize +
sizeof(AccessT),
alignof(AccessT)));
1504 return ::new (Mem + OpsSize) AccessT(std::forward<ArgTs>(Args)...);
1507template <
typename IterT>
1508void MemorySSA::buildMemorySSA(BatchAAResults &BAA, IterT Blocks) {
1516 LiveOnEntryDef.reset(
1518 nullptr,
nullptr, &StartingPoint, NextID++));
1523 SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
1526 for (BasicBlock &
B : Blocks) {
1527 bool InsertIntoDef =
false;
1530 for (Instruction &
I :
B) {
1531 MemoryUseOrDef *MUD = createNewAccess(&
I, &BAA);
1539 InsertIntoDef =
true;
1541 Defs = getOrCreateList(getOrCreateBlockInfo(&
B).Defs);
1542 Defs->push_back(*MUD);
1548 placePHINodes(DefiningBlocks);
1552 SmallPtrSet<BasicBlock *, 16> Visited;
1559 U.set(LiveOnEntryDef.get());
1565 L->getExitBlocks(ExitBlocks);
1567 renamePass(DT->getNode(L->getLoopPreheader()), LiveOnEntryDef.get(),
1570 renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
1575 for (
auto &BB : Blocks)
1576 if (!Visited.
count(&BB))
1577 markUnreachableAsLiveOnEntry(&BB);
1584 return Walker.get();
1587 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1589 Walker = std::make_unique<CachingWalker>(
this, WalkerBase.get());
1590 return Walker.get();
1595 return SkipWalker.get();
1598 WalkerBase = std::make_unique<ClobberWalkerBase>(
this, DT);
1600 SkipWalker = std::make_unique<SkipSelfWalker>(
this, WalkerBase.get());
1601 return SkipWalker.get();
1611 BlockInfo &Info = getOrCreateBlockInfo(BB);
1618 getOrCreateList(Info.Defs)->push_front(*NewAccess);
1624 DefsList *Defs = getOrCreateList(Info.Defs);
1627 Defs->
insert(DI, *NewAccess);
1633 getOrCreateList(Info.Defs)->push_back(*NewAccess);
1635 BlockNumberingValid.erase(BB);
1640 BlockInfo &Info = PerBlock[getBlockIndex(BB)];
1642 bool WasEnd = InsertPt ==
Accesses->end();
1645 DefsList *Defs = getOrCreateList(Info.Defs);
1653 Defs->
insert(InsertPt->getDefsIterator(), *What);
1661 Defs->
insert(InsertPt->getDefsIterator(), *What);
1664 BlockNumberingValid.erase(BB);
1685 prepareForMoveTo(What, BB);
1693 "Can only move a Phi at the beginning of the block");
1695 ValueToMemoryAccess.erase(What->
getBlock());
1696 bool Inserted = ValueToMemoryAccess.insert({BB, What}).second;
1698 assert(Inserted &&
"Cannot move a Phi to a block that already has one");
1701 prepareForMoveTo(What, BB);
1710 ValueToMemoryAccess[BB] = Phi;
1717 bool CreationMustSucceed) {
1720 if (CreationMustSucceed)
1721 assert(NewAccess !=
nullptr &&
"Tried to create a memory access for a "
1722 "non-memory touching instruction");
1725 "A use cannot be a defining access");
1736 if (!
SI->isUnordered())
1739 if (!LI->isUnordered())
1746template <
typename AliasAnalysisType>
1747MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *
I,
1748 AliasAnalysisType *AAP,
1757 switch (
II->getIntrinsicID()) {
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:
1772 if (!
I->mayReadFromMemory() && !
I->mayWriteToMemory())
1781 bool DefCheck, UseCheck;
1786 assert((Def == DefCheck || !DefCheck) &&
1787 "Memory accesses should only be reduced");
1788 if (!Def && Use != UseCheck) {
1790 assert(!UseCheck &&
"Invalid template");
1813 MemoryUseOrDef *MUD;
1816 nullptr,
I,
I->getParent(), NextID++);
1819 nullptr,
I,
I->getParent());
1825 ValueToMemoryAccess[
I] = MUD;
1832 "Trying to remove memory access that still has uses");
1833 BlockNumbering.erase(MA);
1846 auto VMA = ValueToMemoryAccess.find(MemoryInst);
1847 if (VMA->second == MA)
1848 ValueToMemoryAccess.
erase(VMA);
1859 BlockInfo &Info = PerBlock[getBlockIndex(BB)];
1863 Info.Defs->remove(*MA);
1864 if (Info.Defs->empty())
1871 Info.Accesses->
erase(MA);
1873 Info.Accesses->remove(MA);
1875 if (Info.Accesses->empty()) {
1876 Info.Accesses.reset();
1877 BlockNumberingValid.erase(BB);
1882 MemorySSAAnnotatedWriter Writer(
this);
1886 F->
print(OS, &Writer);
1889#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1894#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
1906 assert(L &&
"must either have loop or function");
1909 return *const_cast<BasicBlock *>(BB);
1929template <
typename IterT>
1933 for (
unsigned I = 0, E = Phi->getNumIncomingValues();
I != E; ++
I) {
1934 auto *Pred = Phi->getIncomingBlock(
I);
1935 auto *IncAcc = Phi->getIncomingValue(
I);
1939 if (
auto *DTNode = DT->getNode(Pred)) {
1941 if (
auto *DefList =
getBlockDefs(DTNode->getBlock())) {
1942 auto *LastAcc = &*(--DefList->end());
1943 assert(LastAcc == IncAcc &&
1944 "Incorrect incoming access into phi.");
1949 DTNode = DTNode->getIDom();
1966template <
typename IterT>
1968 if (BlockNumberingValid.empty())
1973 if (!ValidBlocks.
count(&BB))
1976 ValidBlocks.
erase(&BB);
1984 unsigned long LastNumber = 0;
1986 auto ThisNumberIter = BlockNumbering.find(&MA);
1987 assert(ThisNumberIter != BlockNumbering.end() &&
1988 "MemoryAccess has no domination number in a valid block!");
1990 unsigned long ThisNumber = ThisNumberIter->second;
1991 assert(ThisNumber > LastNumber &&
1992 "Domination numbers should be strictly increasing!");
1994 LastNumber = ThisNumber;
1999 "All valid BasicBlocks should exist in F -- dangling pointers?");
2008template <
typename IterT>
2025 for (
const Use &U : Phi->uses()) {
2026 assert(
dominates(Phi, U) &&
"Memory PHI does not dominate it's uses");
2032 "Incomplete MemoryPhi Node");
2033 for (
unsigned I = 0, E = Phi->getNumIncomingValues();
I != E; ++
I) {
2034 verifyUseInDefs(Phi->getIncomingValue(
I), Phi);
2036 "Incoming phi block not a block predecessor");
2044 "We have memory affecting instructions "
2045 "in this block but they are not in the "
2046 "access list or defs list");
2054 for (
const Use &U : MD->
uses()) {
2056 "Memory Def does not dominate it's uses");
2070 assert(AL->size() == ActualAccesses.
size() &&
2071 "We don't have the same number of accesses in the block as on the "
2074 "Either we should have a defs list, or we should have no defs");
2076 "We don't have the same number of defs in the block as on the "
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");
2085 ActualAccesses.
clear();
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");
2105 "Null def but use not point to live on entry def");
2108 "Did not find use in def's use list");
2117void MemorySSA::renumberBlock(
const BasicBlock *
B)
const {
2119 unsigned long CurrentNumber = 0;
2121 assert(AL !=
nullptr &&
"Asking to renumber an empty block");
2122 for (
const auto &
I : *AL)
2123 BlockNumbering[&
I] = ++CurrentNumber;
2124 BlockNumberingValid.insert(
B);
2135 "Asking for local domination when accesses are in different blocks!");
2137 if (Dominatee == Dominator)
2150 if (!BlockNumberingValid.count(DominatorBlock))
2151 renumberBlock(DominatorBlock);
2153 unsigned long DominatorNum = BlockNumbering.lookup(Dominator);
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;
2163 if (Dominator == Dominatee)
2175 const Use &Dominatee)
const {
2177 BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
2179 if (UseBB != Dominator->
getBlock())
2180 return DT->dominates(Dominator->
getBlock(), UseBB);
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);
2212 if (
A &&
A->getID())
2218 OS <<
getID() <<
" = MemoryDef(";
2230 OS <<
getID() <<
" = MemoryPhi(";
2241 if (
unsigned ID = MA->
getID())
2253 if (UO && UO->
getID())
2262#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2271 MemorySSAAnnotatedWriter MSSAWriter;
2275 : F(F), MSSAWriter(&MSSA) {}
2278 MemorySSAAnnotatedWriter &
getWriter() {
return MSSAWriter; }
2286 return &(CFGInfo->
getFunction()->getEntryBlock());
2321 [](std::string &S,
unsigned &
I,
unsigned Idx) ->
void {
2322 std::string Str = S.substr(
I, Idx -
I);
2324 if (SR.
count(
" = MemoryDef(") || SR.
count(
" = MemoryPhi(") ||
2325 SR.
count(
"MemoryUse("))
2345 ?
"style=filled, fillcolor=lightpink"
2352AnalysisKey MemorySSAAnalysis::Key;
2363 FunctionAnalysisManager::Invalidator &Inv) {
2373 if (EnsureOptimizedUses)
2376 if (!DotCFGMSSA.
empty()) {
2380 OS <<
"MemorySSA for function: " <<
F.getName() <<
"\n";
2390 OS <<
"MemorySSA (walker) for function: " <<
F.getName() <<
"\n";
2391 MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2392 F.print(OS, &Writer);
2425 MSSA->verifyMemorySSA();
2444 if (
Loc.Ptr ==
nullptr)
2445 return StartingAccess;
2450 return StartingUseOrDef;
2452 I = StartingUseOrDef->getMemoryInst();
2457 return StartingUseOrDef;
2460 UpwardsMemoryQuery Q;
2461 Q.OriginalAccess = StartingAccess;
2462 Q.StartingLoc =
Loc;
2470 Walker.findClobber(BAA, StartingAccess, Q, UpwardWalkLimit);
2472 dbgs() <<
"Clobber starting at access " << *StartingAccess <<
"\n";
2474 dbgs() <<
" for instruction " << *
I <<
"\n";
2475 dbgs() <<
" is " << *Clobber <<
"\n";
2482 if (!
I.hasMetadata(LLVMContext::MD_invariant_group) ||
I.isVolatile())
2499 for (
const User *Us : PointerOperand->
users()) {
2501 if (!U || U == &
I || !DT.
dominates(U, MostDominatingInstruction))
2507 if (U->hasMetadata(LLVMContext::MD_invariant_group) &&
2509 MostDominatingInstruction = U;
2513 return MostDominatingInstruction == &
I ? nullptr : MostDominatingInstruction;
2517 MemoryAccess *MA, BatchAAResults &BAA,
unsigned &UpwardWalkLimit,
2518 bool SkipSelf,
bool UseInvariantGroup) {
2521 if (!StartingAccess)
2524 if (UseInvariantGroup) {
2526 *StartingAccess->getMemoryInst(), MSSA->
getDomTree())) {
2532 return ClobberMA->getDefiningAccess();
2537 bool IsOptimized =
false;
2542 if (StartingAccess->isOptimized()) {
2544 return StartingAccess->getOptimized();
2548 const Instruction *
I = StartingAccess->getMemoryInst();
2553 return StartingAccess;
2555 UpwardsMemoryQuery Q(
I, StartingAccess);
2559 StartingAccess->setOptimized(LiveOnEntry);
2563 MemoryAccess *OptimizedAccess;
2566 MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2571 StartingAccess->setOptimized(DefiningAccess);
2572 return DefiningAccess;
2576 Walker.findClobber(BAA, DefiningAccess, Q, UpwardWalkLimit);
2577 StartingAccess->setOptimized(OptimizedAccess);
2579 OptimizedAccess = StartingAccess->getOptimized();
2581 LLVM_DEBUG(
dbgs() <<
"Starting Memory SSA clobber for " << *
I <<
" is ");
2583 LLVM_DEBUG(
dbgs() <<
"Optimized Memory SSA clobber for " << *
I <<
" is ");
2590 Q.SkipSelfAccess =
true;
2591 Result = Walker.findClobber(BAA, OptimizedAccess, Q, UpwardWalkLimit);
2593 Result = OptimizedAccess;
2595 LLVM_DEBUG(
dbgs() <<
"Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2605 return Use->getDefiningAccess();
2612 return Use->getDefiningAccess();
2613 return StartingAccess;
2624void MemoryUse::deleteMe(DerivedUser *Self) {
2625 static_cast<MemoryUse *
>(Self)->~MemoryUse();
2628bool upward_defs_iterator::IsGuaranteedLoopInvariant(
const Value *Ptr)
const {
2629 auto IsGuaranteedLoopInvariantBase = [](
const Value *Ptr) {
2638 if (
I->getParent()->isEntryBlock())
2642 return IsGuaranteedLoopInvariantBase(
GEP->getPointerOperand()) &&
2643 GEP->hasAllConstantIndices();
2645 return IsGuaranteedLoopInvariantBase(Ptr);
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.
DXIL Forward Handle Accesses
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
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)
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[]
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...
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)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
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....
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.
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.
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.
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...
Analysis pass which computes a DominatorTree.
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.
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.
unsigned getMaxBlockNumber() const
Return a value larger than the largest block number.
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.
LLVM_ABI void dump() const
MemoryAccess(const MemoryAccess &)=delete
BasicBlock * getBlock() const
LLVM_ABI 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.
LLVM_ABI void print(raw_ostream &OS) const
MemoryAccess * getOptimized() const
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.
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
LLVM_ABI void print(raw_ostream &OS) const
An analysis that produces MemorySSA for a function.
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.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
LLVM_ABI 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 *, 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.
LLVM_ABI void dump() const
simple_ilist< MemoryAccess, ilist_tag< MSSAHelpers::DefsOnlyTag > > DefsList
LLVM_ABI void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where)
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
LLVM_ABI MemorySSAWalker * getSkipSelfWalker()
LLVM_ABI MemorySSA(Function &, AliasAnalysis *, DominatorTree *)
iplist< MemoryAccess, ilist_tag< MSSAHelpers::AllAccessTag > > AccessList
AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
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...
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
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
MemoryAccess * getLiveOnEntryDef() const
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.
LLVM_ABI 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.
LLVM_ABI void print(raw_ostream &OS) const
A Module instance is used to store all the information related to an LLVM module.
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.
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.
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 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.
std::string str() const
Get the contents as an std::string.
constexpr bool empty() const
Check if the string is empty.
size_t count(char C) const
Return the number of occurrences of C in the string.
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.
unsigned getNumOperands() const
LLVM Value Representation.
iterator_range< user_iterator > users()
unsigned getValueID() const
Return an ID for the concrete type of this object.
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.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
An opaque object representing a hash code.
typename base_list_type::iterator iterator
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.
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()
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.
@ BasicBlock
Various leaf nodes.
LocationClass< Ty > location(Ty &L)
NodeAddr< DefNode * > Def
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< NodeBase * > Node
friend class Instruction
Iterator for Instructions in a `BasicBlock.
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.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
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.
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="")
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
DomTreeNodeBase< BasicBlock > DomTreeNode
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
auto dyn_cast_or_null(const Y &Val)
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)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isAtLeastOrStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
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...
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
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.
upward_defs_iterator upward_defs_end()
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
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.
Instruction::const_succ_iterator const_succ_iterator
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
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.
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)
bool isRefSet(const ModRefInfo MRI)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
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)
DefaultDOTGraphTraits(bool simple=false)
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
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.