From d90c9f4a3c2f727df24c404a916df84983fb48c0 Mon Sep 17 00:00:00 2001 From: Alina Sbirlea Date: Thu, 8 Mar 2018 18:03:14 +0000 Subject: 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 --- llvm/lib/Analysis/MemorySSA.cpp | 124 ++++++++++++++++++++++++++++------------ 1 file changed, 89 insertions(+), 35 deletions(-) (limited to 'llvm/lib/Analysis') diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp index 77126344c60..baa625441f1 100644 --- a/llvm/lib/Analysis/MemorySSA.cpp +++ b/llvm/lib/Analysis/MemorySSA.cpp @@ -224,13 +224,25 @@ static bool areLoadsReorderable(const LoadInst *Use, return !(SeqCstUse || MayClobberIsAcquire); } -static bool instructionClobbersQuery(MemoryDef *MD, - const MemoryLocation &UseLoc, - const Instruction *UseInst, - AliasAnalysis &AA) { +namespace { + +struct ClobberAlias { + bool IsClobber; + Optional 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 AR; if (const IntrinsicInst *II = dyn_cast(DefInst)) { // These intrinsics will show up as affecting memory, but they are just @@ -238,13 +250,14 @@ static bool instructionClobbersQuery(MemoryDef *MD, 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 @@ static bool instructionClobbersQuery(MemoryDef *MD, 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(DefInst)) if (auto *UseLoad = dyn_cast(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 @@ static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU, // 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 @@ struct UpwardsMemoryQuery { const Instruction *Inst = nullptr; // The MemoryAccess we actually got called with, used to test local domination const MemoryAccess *OriginalAccess = nullptr; + Optional AR = MayAlias; UpwardsMemoryQuery() = default; @@ -375,9 +393,15 @@ checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt, // // 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 @@ checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt, if (auto *MD = dyn_cast(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 @@ class ClobberWalker { /// 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 AR; }; /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. @@ -475,17 +501,21 @@ class ClobberWalker { for (MemoryAccess *Current : def_chain(Desc.Last)) { Desc.Last = Current; if (Current == StopAt) - return {Current, false}; - - if (auto *MD = dyn_cast(Current)) - if (MSSA.isLiveOnEntryDef(MD) || - instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) - return {MD, true}; + return {Current, false, MayAlias}; + + if (auto *MD = dyn_cast(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(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 &PausedSearches, @@ -828,6 +858,7 @@ public: MemoryAccess *Result; if (WalkResult.IsKnownClobber) { Result = WalkResult.Result; + Q.AR = WalkResult.AR; } else { OptznResult OptRes = tryOptimizePhi(cast(FirstDesc.Last), Current, Q.StartingLoc); @@ -1095,6 +1126,7 @@ private: // This is where the last walk for this memory location ended. unsigned long LastKill; bool LastKillValid; + Optional AR; }; void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &, @@ -1154,7 +1186,7 @@ void MemorySSA::OptimizeUses::optimizeUsesInBlock( } if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) { - MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true); + MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, None); continue; } @@ -1196,6 +1228,7 @@ void MemorySSA::OptimizeUses::optimizeUsesInBlock( 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 @@ void MemorySSA::OptimizeUses::optimizeUsesInBlock( // 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 @@ MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) { 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 @@ MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) { if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) { MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef(); - if (auto *MUD = dyn_cast(StartingAccess)) + if (auto *MUD = dyn_cast(StartingAccess)) { MUD->setOptimized(LiveOnEntry); + MUD->setOptimizedAccessType(None); + } return LiveOnEntry; } @@ -2051,16 +2094,27 @@ MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) { // 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(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(StartingAccess)) + + if (auto *MUD = dyn_cast(StartingAccess)) { MUD->setOptimized(Result); + if (MSSA->isLiveOnEntryDef(Result)) + MUD->setOptimizedAccessType(None); + else if (Q.AR == MustAlias) + MUD->setOptimizedAccessType(MustAlias); + } return Result; } -- cgit v1.2.3