From 82ee942a8c8535696c31ca336c02277c89df265d Mon Sep 17 00:00:00 2001 From: George Burgess IV Date: Wed, 30 Mar 2016 00:26:26 +0000 Subject: [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 --- llvm/lib/Transforms/Utils/MemorySSA.cpp | 32 ++++++++++---------------------- 1 file changed, 10 insertions(+), 22 deletions(-) (limited to 'llvm/lib/Transforms/Utils/MemorySSA.cpp') diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp index f667bce04e3..b71c1945a0e 100644 --- a/llvm/lib/Transforms/Utils/MemorySSA.cpp +++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp @@ -910,18 +910,20 @@ MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk( "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 @@ MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk( 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; } -- cgit v1.2.3