[MemorySSA] Change how the walker views/walks visited phis.
This patch teaches the caching MemorySSA walker a few things:
1. Not to walk Phis we've walked before. It seems that we tried to do
this before, but it didn't work so well in cases like:
define void @foo() {
%1 = alloca i8
%2 = alloca i8
br label %begin
begin:
; 3 = MemoryPhi({%0,liveOnEntry},{%end,2})
; 1 = MemoryDef(3)
store i8 0, i8* %2
br label %end
end:
; MemoryUse(?)
load i8, i8* %1
; 2 = MemoryDef(1)
store i8 0, i8* %2
br label %begin
}
Because we wouldn't put Phis in Q.Visited until we tried to visit them.
So, when trying to optimize MemoryUse(?):
- We would visit 3 above
- ...Which would make us put {%0,liveOnEntry} in Q.Visited
- ...Which would make us visit {%0,liveOnEntry}
- ...Which would make us put {%end,2} in Q.Visited
- ...Which would make us visit {%end,2}
- ...Which would make us visit 3
- ...Which would realize we've already visited everything in 3
- ...Which would make us conservatively return 3.
In the added test-case, (@looped_visitedonlyonce) this behavior would
cause us to give incorrect results. Specifically, we'd visit 4 twice
in the same query, but on the second visit, we'd skip while.cond because
it had been visited, visit if.then/if.then2, and cache "1" as the
clobbering def on the way back.
2. If we try to walk the defs of a {Phi,MemLoc} and see it has been
visited before, just hand back the Phi we're trying to optimize.
I promise this isn't as terrible as it seems. :)
We now insert {Phi,MemLoc} pairs just before walking the Phi's upward
defs. So, we check the cache for the {Phi,MemLoc} pair before checking
if we've already walked the Phi.
The {Phi,MemLoc} pair is (almost?) always guaranteed to have a cache
entry if we've already fully walked it, because we cache as we go.
So, if the {Phi,MemLoc} pair isn't in cache, either:
(a) we must be in the process of visiting it (in which case, we can't
give a better answer in a cache-as-we-go DFS walker)
(b) we visited it, but didn't cache it on the way back (...which seems
to require `ModifyingAccess` to not dominate `StartingAccess`,
so I'm 99% sure that would be an error. If it's not an error, I
haven't been able to get it to happen locally, so I suspect it's
rare.)
- - - - -
As a consequence of this change, we no longer skip upward defs of phis,
so we can kill the `VisitedOnlyOne` check. This gives us better accuracy
than we had before, at the cost of potentially doing a bit more work
when we have a loop.
llvm-svn: 264814
diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp
index f667bce..b71c194 100644
--- a/llvm/lib/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp
@@ -910,18 +910,20 @@
"Skipping phi's children doesn't end the DFS?");
#endif
+ const MemoryAccessPair PHIPair(CurrAccess, Loc);
+
+ // Don't try to optimize this phi again if we've already tried to do so.
+ if (!Q.Visited.insert(PHIPair).second) {
+ ModifyingAccess = CurrAccess;
+ break;
+ }
+
// Recurse on PHI nodes, since we need to change locations.
// TODO: Allow graphtraits on pairs, which would turn this whole function
// into a normal single depth first walk.
MemoryAccess *FirstDef = nullptr;
- const MemoryAccessPair PHIPair(CurrAccess, Loc);
- bool VisitedOnlyOne = true;
for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
MPI != MPE; ++MPI) {
- // Don't follow this path again if we've followed it once
- if (!Q.Visited.insert(*MPI).second)
- continue;
-
bool Backedge =
!FollowingBackedge &&
DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock());
@@ -939,26 +941,12 @@
if (!FirstDef)
FirstDef = CurrentPair.first;
- else
- VisitedOnlyOne = false;
}
// If we exited the loop early, go with the result it gave us.
if (!ModifyingAccess) {
- // The above loop determines if all arguments of the phi node reach the
- // same place. However we skip arguments that are cyclically dependent
- // only on the value of this phi node. This means in some cases, we may
- // only visit one argument of the phi node, and the above loop will
- // happily say that all the arguments are the same. However, in that case,
- // we still can't walk past the phi node, because that argument still
- // kills the access unless we hit the top of the function when walking
- // that argument.
- if (VisitedOnlyOne && !(FirstDef && MSSA->isLiveOnEntryDef(FirstDef))) {
- ModifyingAccess = CurrAccess;
- } else {
- assert(FirstDef && "Visited multiple phis, but FirstDef isn't set?");
- ModifyingAccess = FirstDef;
- }
+ assert(FirstDef && "Found a Phi with no upward defs?");
+ ModifyingAccess = FirstDef;
}
break;
}