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

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

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

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

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

930

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.

include/llvm/Transforms/Utils/MemorySSA.h

protected:
   void doCacheInsert(const MemoryAccess *, MemoryAccess *,
                      const UpwardsMemoryQuery &, const MemoryLocation &);
 
   void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &,
                      const MemoryLocation &);
 
 private:
   MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
-                                  UpwardsMemoryQuery &, bool);
+                                  UpwardsMemoryQuery &, bool, bool);
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
   bool instructionClobbersQuery(const MemoryDef *, UpwardsMemoryQuery &,
                                 const MemoryLocation &Loc) const;
   SmallDenseMap<ConstMemoryAccessPair, MemoryAccess *>
       CachedUpwardsClobberingAccess;
   DenseMap<const MemoryAccess *, MemoryAccess *> CachedUpwardsClobberingCall;
   AliasAnalysis *AA;
   DominatorTree *DT;

lib/Transforms/Utils/MemorySSA.cpp

bool CachingMemorySSAWalker::instructionClobbersQuery(
   if (ImmutableCallSite(DefMemoryInst))
     Q.VisitedCalls.insert(MD);
   ModRefInfo I = AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst));
   return I != MRI_NoModRef;
 }
 
 MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
     MemoryAccess *StartingAccess, const MemoryLocation &Loc,
-    UpwardsMemoryQuery &Q, bool FollowingBackedge) {
+    UpwardsMemoryQuery &Q, bool FollowingBackedge, bool SeenBackedge) {
   MemoryAccess *ModifyingAccess = nullptr;
 
   auto DFI = df_begin(StartingAccess);
-  for (auto DFE = df_end(StartingAccess); DFI != DFE;) {
+  // FIXME: Refactor this loop
+  for (auto DFE = df_end(StartingAccess); DFI != DFE; ++DFI) {
+    assert(!ModifyingAccess &&
+           "ModifyingAccess was set, but we're still in the loop?");
     MemoryAccess *CurrAccess = *DFI;
     if (MSSA->isLiveOnEntryDef(CurrAccess))
       return {CurrAccess, Loc};
     if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc))
       return {CacheResult, Loc};
     // If this is a MemoryDef, check whether it clobbers our current query.
     if (auto *MD = dyn_cast<MemoryDef>(CurrAccess)) {
       // If we hit the top, stop following this path.
       // While we can do lookups, we can't sanely do inserts here unless we were
       // to track everything we saw along the way, since we don't know where we
       // will stop.
       if (instructionClobbersQuery(MD, Q, Loc)) {
         ModifyingAccess = CurrAccess;
         break;
       }
     }
 
-    // We need to know whether it is a phi so we can track backedges.
-    // Otherwise, walk all upward defs.
-    if (!isa<MemoryPhi>(CurrAccess)) {
-      ++DFI;
+    // If this isn't a phi, we can continue walking all upward defs.
+    if (!isa<MemoryPhi>(CurrAccess))
       continue;
-    }
 
     // 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;
+    // If all phis end up pointing to the same place, we can skip this phi.
+    // This loop tries to detect these cases.
+    auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
+    for (; MPI != MPE; ++MPI) {
+      MemoryAccess *Clobber;
+      // There's no point in putting liveOnEntry into `Visited`, nor is there a
+      // point in trying to walk it.
+      if (MSSA->isLiveOnEntryDef(MPI->first)) {
+        Clobber = MPI->first;
+      } else {
+        // If we were able to find this in the cache, we can get away without
+        // putting this in the `Visited` map, because we'll never recurse on it.
+        Clobber = doCacheLookup(MPI->first, Q, MPI->second);
+        if (!Clobber) {
+          bool SeenBefore = !Q.Visited.insert(*MPI).second;
+          // If the cache gives us nothing, we should walk. We need to be
+          // careful if we've seen this before *and* we've seen a back-edge,
+          // because we may have a phi that cycles back to itself. For this
+          // reason, we need to answer conservatively.
+          if (SeenBefore && SeenBackedge)
+            break;
 
           bool Backedge =
               !FollowingBackedge &&
               DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock());
 
-      MemoryAccessPair CurrentPair =
-          UpwardsDFSWalk(MPI->first, MPI->second, Q, Backedge);
-      // All the phi arguments should reach the same point if we can bypass
-      // this phi. The alternative is that they hit this phi node, which
-      // means we can skip this argument.
-      if (FirstDef && CurrentPair.first != PHIPair.first &&
-          CurrentPair.first != FirstDef) {
-        ModifyingAccess = CurrAccess;
-        break;
+          Clobber = UpwardsDFSWalk(MPI->first, MPI->second, Q, Backedge,
+                                   Backedge || SeenBackedge)
+                        .first;
+        }
       }
 
+      // If we looped back to this phi, no interesting defs happen on any of the
+      // paths we took, so we can safely ignore it.
+      if (Clobber == CurrAccess)
+        continue;
+
       if (!FirstDef)
-        FirstDef = CurrentPair.first;
-      else
-        VisitedOnlyOne = false;
+        FirstDef = Clobber;
+      else if (FirstDef != Clobber)
+        break;
     }
 
-    // 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))
+#ifndef NDEBUG
+    // The above loop should examine all of the phi's children, so we can skip
+    // them. Because all nodes except Phis only have one edge, skipping the
+    // children of a phi should terminate our DFS.
+    //
+    // Don't call skipChildren directly on the iterator because doing so deletes
+    // the iterator's search stack, and we need that so we can cache everything.
+    auto DFICopy = DFI;
+    assert(DFICopy.skipChildren() == DFE);
+#endif
+
+    if (MPI != MPE) {
+      // If we didn't examine everything, we need to answer conservatively.
       ModifyingAccess = CurrAccess;
+    } else {
+      // FirstDef can only be null if all "Clobber"s pointed back to this phi,
+      // which would imply we have a loop with no entry, which shouldn't be
+      // possible.
+      assert(FirstDef);
+      ModifyingAccess = FirstDef;
+    }
+    break;
   }
 
-  if (!ModifyingAccess)
-    return {MSSA->getLiveOnEntryDef(), Q.StartingLoc};
+  if (!ModifyingAccess) {
+    // If DFI hit the end, it will have 0 path entries. Give up early.
+    assert(DFI == df_end(StartingAccess) &&
+           "Loop should set ModifyingAccess before exiting early.");
+    return {MSSA->getLiveOnEntryDef(), Loc};
+  }
 
-  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 *PathAccess = DFI.getPath(N - 1);
+    BasicBlock *CurrBlock = PathAccess->getBlock();
     if (!FollowingBackedge)
-      doCacheInsert(ModifyingAccess, FinalAccess, Q, Loc);
+      doCacheInsert(PathAccess, ModifyingAccess, Q, Loc);
     if (DT->dominates(CurrBlock, OriginalBlock) &&
         (CurrBlock != OriginalBlock || !FollowingBackedge ||
-         MSSA->locallyDominates(ModifyingAccess, Q.OriginalAccess)))
+         MSSA->locallyDominates(PathAccess, 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);
+    MemoryAccess *PathAccess = DFI.getPath(N - 1);
+    doCacheInsert(PathAccess, ModifyingAccess, Q, Loc);
   }
   assert(Q.Visited.size() < 1000 && "Visited too much");
 
   return {ModifyingAccess, Loc};
 }
 
 /// \brief Walk the use-def chains starting at \p MA and find
 /// the MemoryAccess that actually clobbers Loc.
 ///
 /// \returns our clobbering memory access
 MemoryAccess *
 CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
                                                   UpwardsMemoryQuery &Q) {
-  return UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false).first;
+  return UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false, false).first;
 }
 
 MemoryAccess *
 CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
                                                   MemoryLocation &Loc) {
   if (isa<MemoryPhi>(StartingAccess))
     return StartingAccess;
 

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})
+; NOTE: we're currently a bit too conservative here; this could point to
+; liveOnEntry.
+; CHECK: MemoryUse(3)
+; 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_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
+}

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
+}
+
+; This case is a bit more interesting, and exists specifically to test the
+; caching walker's walking algorithm.
+;
+; The phi structure is:
+;
+;   2 -> 3
+;   ^    ^
+;    \  /
+;     1
+;
+; Where each number is a phi, each arrow is a directed edge from that phi to
+; another phi, and the phi number is the order that phi gets visited in by the
+; walker.
+;
+; We want to optimize a use that uses phi 1 to use phi 3. This case is
+; interesting because it hits the case where we've already visited the phi,
+; and no phi translation has occurred. So, we need to fall back to our cache.
+;
+; 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
+
+  ; We need if.then so phi.3 starts with an actual phi.
+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})
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: load i8, i8* %local
+  load i8, i8* %local
+  ret void
+}