Fix bugs in the MemorySSA walker

[george.burgess.iv]

Summary

Test case:

define void @foo(i1 %b, i8* %ext) {
  %a = alloca i8, align 1
  %sink = alloca i8, align 1
  ; 1 = MemoryDef(liveOnEntry) <<<<<<<<
  store i8 1, i8* %a, align 1
  br i1 %b, label %if.b, label %end

if.b:
  ; 2 = MemoryDef(1)
  store i8 1, i8* %sink
  br label %end

end:
  ; 3 = MemoryPhi({if.b,2},{%0,1})
  ; MemoryUse(liveOnEntry)  <<<<<<<<<<<<<
  load i8, i8* %a, align 1
  ret void
}

...This happens because because of how we recursively walk phis, and how we cache the results afterward. Both of these problems are (hopefully) fixed by this patch.

I plan to move the code around in the loop a bit (because break; as the last statement in a for is kind of dumb), but I’ve separated that from this patch because the refactor adds a fair amount of noise, and should be NFC.

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

970 ↗

(On Diff #50359)

Errr.
What?

A. In buildMemorySSA, we already detect forward-unreachable-from-entry blocks and mark all definitions as live on entry. So they should never loop anywhere in the case you are listing, because if the loop has no entry, all the defs/uses in it should be to live on entry.

So i don't see how this can happen.

However
B.
Because we already handle forward unreachable-from-entry blocks and mark all defs in them as liveonentry in buildmemoryssa, is there a good reason we shouldn't just detect reverse unreachable-from-entry blocks and do the same?

We can say that MemorySSA has no forward or reverse unreachable blocks, and make the IR sane in them. This is because we have no real IR, and so, at worst, we can do what we do now:

Mark anything in unreachable as live on entry, and remove all phis in unreachable. We could go one more, and remove all the memory accesses entirely if we wanted to.

[george.burgess.iv]

Addressed feedback

lib/Transforms/Utils/MemorySSA.cpp

970 ↗

(On Diff #50359)

A. In buildMemorySSA, we already detect forward-unreachable-from-entry blocks and mark all definitions as live on entry. So they should never loop anywhere in the case you are listing, because if the loop has no entry, all the defs/uses in it should be to live on entry.

Correct.

So i don't see how this can happen.

I was thinking that the update API might be able to get us in this situation, but after looking at it, I think I was wrong. :)

Ternary replaced with assert(FirstDef);

Because we already handle forward unreachable-from-entry blocks and mark all defs in them as liveonentry in buildmemoryssa, is there a good reason we shouldn't just detect reverse unreachable-from-entry blocks and do the same?

I can't think of one. Though, I'm also not sure I understand backwards reachability, because I can't think of a case where a reverse unreachable-from-entry block would be walked by a DFS of the domtree. Would a trivial algorithm for determining reverse reachability-from-entry for some node N not be "flip the edges of the CFG, and see if Entry is reachable from N"?

Mark anything in unreachable as live on entry, and remove all phis in unreachable. We could go one more, and remove all the memory accesses entirely if we wanted to.

Would it be fine to just not build them in the first place?

[• dberlin]

Just because this logic is getting fairly complicated, can you explain to me (either here or on a whiteboard) the failure mode that is occurring that you are solving?

It's clear the testcase gives the wrong answer. Can you describe more of "why"?

lib/Transforms/Utils/MemorySSA.cpp

911 ↗

(On Diff #50390)

why did you move this out of the for loop init?

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

930 ↗

(On Diff #50390)

I'm unclear why this makes sense. It tracks whether you've ever seen a backedge before hitting this phi.

If you see a backedge and move past that cycle, it will still trigger on the next cycle.

Honestly, this is also moving a bit far away from normal usage of the DFI iterator.
I am kinda wondering if we should not just turn this into the traditional SCC finding algorithm (treating the tuple of <thing, memorylocation> as the node we are visiting), and then we will know exactly which stuff is a cycle and which is not.

[george.burgess.iv]

It's clear the testcase gives the wrong answer. Can you describe more of "why"?

In that particular case, because we don't do anything useful with FirstDef after the phi loop :)

I guess I tried to cram too many "fixes" into one patch, and was unclear about that -- sorry.

As it stood, the patch fixed the above code sample, and made us more accurate in cases like:

define void @f(i8* noalias %p1, i8* noalias %p2) {
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, i8* %p1
  ; MemoryUse(1)
  load i8, i8* %p1
  br i1 undef, label %a, label %b

a:
  ; 2 = MemoryDef(1)
  store i8 0, i8* %p2
  br i1 undef, label %c, label %d

b:
  ; 3 = MemoryDef(1)
  store i8 1, i8* %p2
  br i1 undef, label %c, label %d

c:
  ; 6 = MemoryPhi({a,2},{b,3})
  ; 4 = MemoryDef(6)
  store i8 2, i8* %p2
  br label %e

d:
  ; 7 = MemoryPhi({a,2},{b,3})
  ; 5 = MemoryDef(7)
  store i8 3, i8* %p2
  br label %e

e:
  ; 8 = MemoryPhi({c,4},{d,5})
  ; MemoryUse(8) << Should be MemoryUse(1)
  load i8, i8* %p1
  ret void
}

...And any optimizable case where we have a non-cyclic phi structure that visits the same phi twice (the VisitedOnlyOne check gets triggered).

Though, I think there's a better way to handle that *and* cyclic phis that lets us leave the walking loop mostly untouched. So, I backed out the enhancements + make this review strictly for correctness fixes. I'll work on something to give us better accuracy and send it out separately.

If you'd like more examples, I left the tests I think we can do better on in the patch (with: ; FIXME:s in them). I'll pull them out prior to committing this, and move them to the enhancements patch.

[• dberlin]

At this point, LGT.

i think we discussed offline that as the caching gets more complex, we should either seriously rethink the caching scheme (since we know it sucks and in fact, is useless for memoryuses, relook at the BFS version to see if it makes it simpler, explore other walking algorithms (Collapse cycles into SCC's), etc.

[george.burgess.iv]

i think we discussed offline that as the caching gets more complex, we should either seriously rethink the caching scheme (since we know it sucks and in fact, is useless for memoryuses, relook at the BFS version to see if it makes it simpler, explore other walking algorithms (Collapse cycles into SCC's), etc.

SG. I'll dig up + play around with the BFS code, and see if that makes our lives easier. If that fails, we'll figure out something from there. :)

Thanks for the review.

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

for (auto DFE = df_end(StartingAccess); DFI != DFE;) {
 
     // We need to know whether it is a phi so we can track backedges.
     // Otherwise, walk all upward defs.
     if (!isa<MemoryPhi>(CurrAccess)) {
       ++DFI;
       continue;
     }
 
+#ifndef NDEBUG
+    // The loop below visits the phi's children for us. Because phis are the
+    // only things with multiple edges, skipping the children should always lead
+    // us to the end of the loop.
+    //
+    // Use a copy of DFI because skipChildren would kill our search stack, which
+    // would make caching anything on the way back impossible.
+    auto DFICopy = DFI;
+    assert(DFICopy.skipChildren() == DFE &&
+           "Skipping phi's children doesn't end the DFS?");
+#endif
+
     // 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;
-    DFI = DFI.skipChildren();
     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;
 
for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
       }
 
       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))
+      if (VisitedOnlyOne && !(FirstDef && MSSA->isLiveOnEntryDef(FirstDef))) {
         ModifyingAccess = CurrAccess;
+      } else {
+        assert(FirstDef && "Visited multiple phis, but FirstDef isn't set?");
+        ModifyingAccess = FirstDef;
+      }
+    }
+    break;
   }
 
   if (!ModifyingAccess)
     return {MSSA->getLiveOnEntryDef(), Q.StartingLoc};
 
-  const BasicBlock *OriginalBlock = Q.OriginalAccess->getBlock();
+  const BasicBlock *OriginalBlock = StartingAccess->getBlock();
   unsigned N = DFI.getPathLength();
-  MemoryAccess *FinalAccess = ModifyingAccess;
   for (; N != 0; --N) {
-    ModifyingAccess = DFI.getPath(N - 1);
-    BasicBlock *CurrBlock = ModifyingAccess->getBlock();
+    MemoryAccess *CacheAccess = DFI.getPath(N - 1);
+    BasicBlock *CurrBlock = CacheAccess->getBlock();
     if (!FollowingBackedge)
-      doCacheInsert(ModifyingAccess, FinalAccess, Q, Loc);
+      doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);
     if (DT->dominates(CurrBlock, OriginalBlock) &&
         (CurrBlock != OriginalBlock || !FollowingBackedge ||
-         MSSA->locallyDominates(ModifyingAccess, Q.OriginalAccess)))
+         MSSA->locallyDominates(CacheAccess, StartingAccess)))
       break;
   }
 
   // Cache everything else on the way back. The caller should cache
   // Q.OriginalAccess for us.
   for (; N != 0; --N) {
     MemoryAccess *CacheAccess = DFI.getPath(N - 1);
     doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);

llvm/trunk/test/Transforms/Util/MemorySSA/cyclicphi.ll

 bb77:                                             ; preds = %bb68, %bb26
 ; CHECK:  2 = MemoryPhi({bb26,3},{bb68,1})
 ; CHECK:  MemoryUse(2)
 ; CHECK-NEXT:   %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef
   br label %bb26
 }
+
+; CHECK-LABEL: define void @quux_skip
+define void @quux_skip(%struct.hoge* noalias %f, i64* noalias %g) align 2 {
+  %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
+  %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
+  %tmp25 = bitcast %struct.widget* %tmp24 to i64**
+  br label %bb26
+
+bb26:                                             ; preds = %bb77, %0
+; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; CHECK-NEXT: br i1 undef, label %bb68, label %bb77
+  br i1 undef, label %bb68, label %bb77
+
+bb68:                                             ; preds = %bb26
+; CHECK: MemoryUse(3)
+; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8
+  %tmp69 = load i64, i64* %g, align 8
+; CHECK: 1 = MemoryDef(3)
+; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8
+  store i64 %tmp69, i64* %g, align 8
+  br label %bb77
+
+bb77:                                             ; preds = %bb68, %bb26
+; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1})
+; FIXME: This should be MemoryUse(liveOnEntry)
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8
+  %tmp78 = load i64*, i64** %tmp25, align 8
+  br label %bb26
+}
+
+; CHECK-LABEL: define void @quux_dominated
+define void @quux_dominated(%struct.hoge* noalias %f, i64* noalias %g) align 2 {
+  %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
+  %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
+  %tmp25 = bitcast %struct.widget* %tmp24 to i64**
+  br label %bb26
+
+bb26:                                             ; preds = %bb77, %0
+; CHECK: 4 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; CHECK: MemoryUse(4)
+; CHECK-NEXT: load i64*, i64** %tmp25, align 8
+  load i64*, i64** %tmp25, align 8
+  br i1 undef, label %bb68, label %bb77
+
+bb68:                                             ; preds = %bb26
+; CHECK: MemoryUse(4)
+; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8
+  %tmp69 = load i64, i64* %g, align 8
+; CHECK: 1 = MemoryDef(4)
+; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8
+  store i64 %tmp69, i64* %g, align 8
+  br label %bb77
+
+bb77:                                             ; preds = %bb68, %bb26
+; CHECK: 3 = MemoryPhi({bb26,4},{bb68,1})
+; CHECK: 2 = MemoryDef(3)
+; CHECK-NEXT: store i64* null, i64** %tmp25, align 8
+  store i64* null, i64** %tmp25, align 8
+  br label %bb26
+}
+
+; CHECK-LABEL: define void @quux_nodominate
+define void @quux_nodominate(%struct.hoge* noalias %f, i64* noalias %g) align 2 {
+  %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
+  %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
+  %tmp25 = bitcast %struct.widget* %tmp24 to i64**
+  br label %bb26
+
+bb26:                                             ; preds = %bb77, %0
+; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: load i64*, i64** %tmp25, align 8
+  load i64*, i64** %tmp25, align 8
+  br i1 undef, label %bb68, label %bb77
+
+bb68:                                             ; preds = %bb26
+; CHECK: MemoryUse(3)
+; CHECK-NEXT: %tmp69 = load i64, i64* %g, align 8
+  %tmp69 = load i64, i64* %g, align 8
+; CHECK: 1 = MemoryDef(3)
+; CHECK-NEXT: store i64 %tmp69, i64* %g, align 8
+  store i64 %tmp69, i64* %g, align 8
+  br label %bb77
+
+bb77:                                             ; preds = %bb68, %bb26
+; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1})
+; CHECK-NEXT: br label %bb26
+  br label %bb26
+}

llvm/trunk/test/Transforms/Util/MemorySSA/phi-translation.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+
+; %ptr can't alias %local, so we should be able to optimize the use of %local to
+; point to the store to %local.
+; CHECK-LABEL: define void @check
+define void @check(i8* %ptr, i1 %bool) {
+entry:
+  %local = alloca i8, align 1
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %local, align 1
+  store i8 0, i8* %local, align 1
+  br i1 %bool, label %if.then, label %if.end
+
+if.then:
+  %p2 = getelementptr inbounds i8, i8* %ptr, i32 1
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 0, i8* %p2, align 1
+  store i8 0, i8* %p2, align 1
+  br label %if.end
+
+if.end:
+; CHECK: 3 = MemoryPhi({entry,1},{if.then,2})
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: load i8, i8* %local, align 1
+  load i8, i8* %local, align 1
+  ret void
+}
+
+; CHECK-LABEL: define void @check2
+define void @check2(i1 %val1, i1 %val2, i1 %val3) {
+entry:
+  %local = alloca i8, align 1
+  %local2 = alloca i8, align 1
+
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %local
+  store i8 0, i8* %local
+  br i1 %val1, label %if.then, label %phi.3
+
+if.then:
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 2, i8* %local2
+  store i8 2, i8* %local2
+  br i1 %val2, label %phi.2, label %phi.3
+
+phi.3:
+; CHECK: 6 = MemoryPhi({entry,1},{if.then,2})
+; CHECK: 3 = MemoryDef(6)
+; CHECK-NEXT: store i8 3, i8* %local2
+  store i8 3, i8* %local2
+  br i1 %val3, label %phi.2, label %phi.1
+
+phi.2:
+; CHECK: 5 = MemoryPhi({if.then,2},{phi.3,3})
+; CHECK: 4 = MemoryDef(5)
+; CHECK-NEXT: store i8 4, i8* %local2
+  store i8 4, i8* %local2
+  br label %phi.1
+
+phi.1:
+; Order matters here; phi.2 needs to come before phi.3, because that's the order
+; they're visited in.
+; CHECK: 7 = MemoryPhi({phi.2,4},{phi.3,3})
+; FIXME: This should be MemoryUse(1)
+; CHECK: MemoryUse(7)
+; CHECK-NEXT: load i8, i8* %local
+  load i8, i8* %local
+  ret void
+}
+
+; CHECK-LABEL: define void @cross_phi
+define void @cross_phi(i8* noalias %p1, i8* noalias %p2) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %p1
+  store i8 0, i8* %p1
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  br i1 undef, label %a, label %b
+
+a:
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 0, i8* %p2
+  store i8 0, i8* %p2
+  br i1 undef, label %c, label %d
+
+b:
+; CHECK: 3 = MemoryDef(1)
+; CHECK-NEXT: store i8 1, i8* %p2
+  store i8 1, i8* %p2
+  br i1 undef, label %c, label %d
+
+c:
+; CHECK: 6 = MemoryPhi({a,2},{b,3})
+; CHECK: 4 = MemoryDef(6)
+; CHECK-NEXT: store i8 2, i8* %p2
+  store i8 2, i8* %p2
+  br label %e
+
+d:
+; CHECK: 7 = MemoryPhi({a,2},{b,3})
+; CHECK: 5 = MemoryDef(7)
+; CHECK-NEXT: store i8 3, i8* %p2
+  store i8 3, i8* %p2
+  br label %e
+
+e:
+; 8 = MemoryPhi({c,4},{d,5})
+; FIXME: This should be MemoryUse(1)
+; CHECK: MemoryUse(8)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  ret void
+}
+
+; CHECK-LABEL: define void @looped
+define void @looped(i8* noalias %p1, i8* noalias %p2) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %p1
+  store i8 0, i8* %p1
+  br label %loop.1
+
+loop.1:
+; CHECK: 7 = MemoryPhi({%0,1},{loop.3,4})
+; CHECK: 2 = MemoryDef(7)
+; CHECK-NEXT: store i8 0, i8* %p2
+  store i8 0, i8* %p2
+  br i1 undef, label %loop.2, label %loop.3
+
+loop.2:
+; CHECK: 6 = MemoryPhi({loop.1,2},{loop.3,4})
+; CHECK: 3 = MemoryDef(6)
+; CHECK-NEXT: store i8 1, i8* %p2
+  store i8 1, i8* %p2
+  br label %loop.3
+
+loop.3:
+; CHECK: 5 = MemoryPhi({loop.1,2},{loop.2,3})
+; CHECK: 4 = MemoryDef(5)
+; CHECK-NEXT: store i8 2, i8* %p2
+  store i8 2, i8* %p2
+; FIXME: This should be MemoryUse(1)
+; CHECK: MemoryUse(5)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  br i1 undef, label %loop.2, label %loop.1
+}