Expose must/may alias info in MemorySSA.
Summary:
Building MemorySSA gathers alias information for Defs/Uses.
Store and expose this information when optimizing uses (when building MemorySSA),
and when optimizing defs or updating uses (getClobberingMemoryAccess).
Current patch does not propagate alias information through MemoryPhis.
Reviewers: gbiv, dberlin
Subscribers: Prazek, sanjoy, llvm-commits
Differential Revision: https://reviews.llvm.org/D38569
llvm-svn: 327035
diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp
index 7712634..baa6254 100644
--- a/llvm/lib/Analysis/MemorySSA.cpp
+++ b/llvm/lib/Analysis/MemorySSA.cpp
@@ -224,13 +224,25 @@
return !(SeqCstUse || MayClobberIsAcquire);
}
-static bool instructionClobbersQuery(MemoryDef *MD,
- const MemoryLocation &UseLoc,
- const Instruction *UseInst,
- AliasAnalysis &AA) {
+namespace {
+
+struct ClobberAlias {
+ bool IsClobber;
+ Optional<AliasResult> AR;
+};
+
+} // end anonymous namespace
+
+// Return a pair of {IsClobber (bool), AR (AliasResult)}. It relies on AR being
+// ignored if IsClobber = false.
+static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
+ const MemoryLocation &UseLoc,
+ const Instruction *UseInst,
+ AliasAnalysis &AA) {
Instruction *DefInst = MD->getMemoryInst();
assert(DefInst && "Defining instruction not actually an instruction");
ImmutableCallSite UseCS(UseInst);
+ Optional<AliasResult> AR;
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
// These intrinsics will show up as affecting memory, but they are just
@@ -238,13 +250,14 @@
switch (II->getIntrinsicID()) {
case Intrinsic::lifetime_start:
if (UseCS)
- return false;
- return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
+ return {false, NoAlias};
+ AR = AA.alias(MemoryLocation(II->getArgOperand(1)), UseLoc);
+ return {AR == MustAlias, AR};
case Intrinsic::lifetime_end:
case Intrinsic::invariant_start:
case Intrinsic::invariant_end:
case Intrinsic::assume:
- return false;
+ return {false, NoAlias};
default:
break;
}
@@ -252,19 +265,23 @@
if (UseCS) {
ModRefInfo I = AA.getModRefInfo(DefInst, UseCS);
- return isModOrRefSet(I);
+ AR = isMustSet(I) ? MustAlias : MayAlias;
+ return {isModOrRefSet(I), AR};
}
if (auto *DefLoad = dyn_cast<LoadInst>(DefInst))
if (auto *UseLoad = dyn_cast<LoadInst>(UseInst))
- return !areLoadsReorderable(UseLoad, DefLoad);
+ return {!areLoadsReorderable(UseLoad, DefLoad), MayAlias};
- return isModSet(AA.getModRefInfo(DefInst, UseLoc));
+ ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
+ AR = isMustSet(I) ? MustAlias : MayAlias;
+ return {isModSet(I), AR};
}
-static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
- const MemoryLocOrCall &UseMLOC,
- AliasAnalysis &AA) {
+static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
+ const MemoryUseOrDef *MU,
+ const MemoryLocOrCall &UseMLOC,
+ AliasAnalysis &AA) {
// FIXME: This is a temporary hack to allow a single instructionClobbersQuery
// to exist while MemoryLocOrCall is pushed through places.
if (UseMLOC.IsCall)
@@ -277,7 +294,7 @@
// Return true when MD may alias MU, return false otherwise.
bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
AliasAnalysis &AA) {
- return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA);
+ return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA).IsClobber;
}
namespace {
@@ -292,6 +309,7 @@
const Instruction *Inst = nullptr;
// The MemoryAccess we actually got called with, used to test local domination
const MemoryAccess *OriginalAccess = nullptr;
+ Optional<AliasResult> AR = MayAlias;
UpwardsMemoryQuery() = default;
@@ -375,9 +393,15 @@
//
// Also, note that this can't be hoisted out of the `Worklist` loop,
// since MD may only act as a clobber for 1 of N MemoryLocations.
- FoundClobber =
- FoundClobber || MSSA.isLiveOnEntryDef(MD) ||
- instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
+ FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MD);
+ if (!FoundClobber) {
+ ClobberAlias CA =
+ instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
+ if (CA.IsClobber) {
+ FoundClobber = true;
+ // Not used: CA.AR;
+ }
+ }
}
break;
}
@@ -387,7 +411,8 @@
if (auto *MD = dyn_cast<MemoryDef>(MA)) {
(void)MD;
- assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) &&
+ assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA)
+ .IsClobber &&
"Found clobber before reaching ClobberAt!");
continue;
}
@@ -457,9 +482,10 @@
/// Result of calling walkToPhiOrClobber.
struct UpwardsWalkResult {
/// The "Result" of the walk. Either a clobber, the last thing we walked, or
- /// both.
+ /// both. Include alias info when clobber found.
MemoryAccess *Result;
bool IsKnownClobber;
+ Optional<AliasResult> AR;
};
/// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
@@ -475,17 +501,21 @@
for (MemoryAccess *Current : def_chain(Desc.Last)) {
Desc.Last = Current;
if (Current == StopAt)
- return {Current, false};
+ return {Current, false, MayAlias};
- if (auto *MD = dyn_cast<MemoryDef>(Current))
- if (MSSA.isLiveOnEntryDef(MD) ||
- instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA))
- return {MD, true};
+ if (auto *MD = dyn_cast<MemoryDef>(Current)) {
+ if (MSSA.isLiveOnEntryDef(MD))
+ return {MD, true, MustAlias};
+ ClobberAlias CA =
+ instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
+ if (CA.IsClobber)
+ return {MD, true, CA.AR};
+ }
}
assert(isa<MemoryPhi>(Desc.Last) &&
"Ended at a non-clobber that's not a phi?");
- return {Desc.Last, false};
+ return {Desc.Last, false, MayAlias};
}
void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
@@ -828,6 +858,7 @@
MemoryAccess *Result;
if (WalkResult.IsKnownClobber) {
Result = WalkResult.Result;
+ Q.AR = WalkResult.AR;
} else {
OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
Current, Q.StartingLoc);
@@ -1095,6 +1126,7 @@
// This is where the last walk for this memory location ended.
unsigned long LastKill;
bool LastKillValid;
+ Optional<AliasResult> AR;
};
void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
@@ -1154,7 +1186,7 @@
}
if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) {
- MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true);
+ MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, None);
continue;
}
@@ -1196,6 +1228,7 @@
if (!LocInfo.LastKillValid) {
LocInfo.LastKill = VersionStack.size() - 1;
LocInfo.LastKillValid = true;
+ LocInfo.AR = MayAlias;
}
// At this point, we should have corrected last kill and LowerBound to be
@@ -1239,24 +1272,32 @@
// Reset UpperBound to liveOnEntryDef's place in the stack
UpperBound = 0;
FoundClobberResult = true;
+ LocInfo.AR = MustAlias;
break;
}
- if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) {
+ ClobberAlias CA = instructionClobbersQuery(MD, MU, UseMLOC, *AA);
+ if (CA.IsClobber) {
FoundClobberResult = true;
+ LocInfo.AR = CA.AR;
break;
}
--UpperBound;
}
+
+ // Note: Phis always have AliasResult AR set to MayAlias ATM.
+
// At the end of this loop, UpperBound is either a clobber, or lower bound
// PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
- MU->setDefiningAccess(VersionStack[UpperBound], true);
// We were last killed now by where we got to
+ if (MSSA->isLiveOnEntryDef(VersionStack[UpperBound]))
+ LocInfo.AR = None;
+ MU->setDefiningAccess(VersionStack[UpperBound], true, LocInfo.AR);
LocInfo.LastKill = UpperBound;
} else {
// Otherwise, we checked all the new ones, and now we know we can get to
// LastKill.
- MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true);
+ MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true, LocInfo.AR);
}
LocInfo.LowerBound = VersionStack.size() - 1;
LocInfo.LowerBoundBlock = BB;
@@ -2026,8 +2067,8 @@
return MA;
// If this is an already optimized use or def, return the optimized result.
- // Note: Currently, we do not store the optimized def result because we'd need
- // a separate field, since we can't use it as the defining access.
+ // Note: Currently, we store the optimized def result in a separate field,
+ // since we can't use the defining access.
if (StartingAccess->isOptimized())
return StartingAccess->getOptimized();
@@ -2041,8 +2082,10 @@
if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) {
MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
- if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
+ if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
MUD->setOptimized(LiveOnEntry);
+ MUD->setOptimizedAccessType(None);
+ }
return LiveOnEntry;
}
@@ -2051,16 +2094,27 @@
// At this point, DefiningAccess may be the live on entry def.
// If it is, we will not get a better result.
- if (MSSA->isLiveOnEntryDef(DefiningAccess))
+ if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
+ if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
+ MUD->setOptimized(DefiningAccess);
+ MUD->setOptimizedAccessType(None);
+ }
return DefiningAccess;
+ }
MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
DEBUG(dbgs() << *DefiningAccess << "\n");
DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
DEBUG(dbgs() << *Result << "\n");
- if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
+
+ if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
MUD->setOptimized(Result);
+ if (MSSA->isLiveOnEntryDef(Result))
+ MUD->setOptimizedAccessType(None);
+ else if (Q.AR == MustAlias)
+ MUD->setOptimizedAccessType(MustAlias);
+ }
return Result;
}