[MemorySSA] Add previous def to cache when found, even if trivial.

[asbirlea]

Summary

When inserting a new Def, MemorySSA may be have non-minimal number of Phis.
While inserting, the walk to find the previous definition may cleanup minimal Phis.
When the last definition is trivial to obtain, we do not cache it.

It is possible while getting the previous definition for a Def to get two different answers:

• one that was straight-forward to find when walking the first path (a trivial phi in this case), and
• another that follows a cleanup of the trivial phi, it determines it may need additional Phi nodes, it inserts them and returns a new phi in the same position as the former trivial one.

While the Phis added for the second path are all redundant, they are not complete (the walk is only done upwards), and they are not properly cleaned up afterwards.

A way to fix this problem is to cache the straight-forward answer we got on the first walk.
The caching is only kept for the duration of a getPreviousDef call, and for Phis we use TrackingVH, so removing the trivial phi will lead to replacing it with the next dominating phi in the cache.
Resolves PR40749.

[george.burgess.iv]

Thanks!

test/Analysis/MemorySSA/pr40749_2.ll

1 ↗

(On Diff #194958)

; REQUIRES: asserts?

[asbirlea]

Thank you for the review!

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

 }
 
 // This starts at the end of block
 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
     BasicBlock *BB,
     DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
   auto *Defs = MSSA->getWritableBlockDefs(BB);
 
-  if (Defs)
+  if (Defs) {
+    CachedPreviousDef.insert({BB, &*Defs->rbegin()});
     return &*Defs->rbegin();
+  }
 
   return getPreviousDefRecursive(BB, CachedPreviousDef);
 }
 // Recurse over a set of phi uses to eliminate the trivial ones
 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
   if (!Phi)
     return nullptr;
   TrackingVH<MemoryAccess> Res(Phi);

llvm/trunk/test/Analysis/MemorySSA/pr40749_2.ll

+; RUN: opt -S -licm -loop-unswitch -enable-mssa-loop-dependency -verify-memoryssa %s | FileCheck %s
+; REQUIRES: asserts
+target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-v128:64-a:8:16-n32:64"
+target triple = "s390x-ibm-linux"
+
+@g_92 = external dso_local local_unnamed_addr global i16, align 2
+@g_993 = external dso_local local_unnamed_addr global i32, align 4
+
+; CHECK-LABEL: @ff6
+define dso_local fastcc void @ff6(i16 %arg1) unnamed_addr #0 {
+bb:
+  %tmp6.i = icmp sgt i16 %arg1, 0
+  br label %bb10
+
+bb10:                                             ; preds = %bb81.loopexit, %bb
+  %tmp17 = load i16, i16* @g_92, align 2
+  %tmp18 = add i16 %tmp17, 1
+  store i16 %tmp18, i16* @g_92, align 2
+  br label %bb19
+
+bb19:                                             ; preds = %bb42, %bb10
+  br label %bb24.preheader
+
+bb24.preheader:                                   ; preds = %bb75, %bb19
+  store i32 0, i32* @g_993, align 4
+  br i1 %tmp6.i, label %bb24.preheader.split.us, label %bb24.preheader.split
+
+bb24.preheader.split.us:                          ; preds = %bb24.preheader
+  br label %bb61.us
+
+bb67.us.loopexit:                                 ; preds = %bb65.us
+  br label %bb75
+
+bb61.us:                                          ; preds = %bb65.us, %bb24.preheader.split.us
+  br i1 false, label %bb65.us, label %bb81.loopexit
+
+bb65.us:                                          ; preds = %bb61.us
+  br i1 false, label %bb61.us, label %bb67.us.loopexit
+
+bb24.preheader.split:                             ; preds = %bb24.preheader
+  br label %bb27
+
+bb27:                                             ; preds = %bb24.preheader.split
+  br i1 false, label %bb42, label %bb67
+
+bb42:                                             ; preds = %bb27
+  br label %bb19
+
+bb67:                                             ; preds = %bb27
+  br label %bb75
+
+bb75:                                             ; preds = %bb67, %bb67.us.loopexit
+  br i1 undef, label %bb24.preheader, label %bb84.loopexit
+
+bb81.loopexit:                                    ; preds = %bb61.us
+  br label %bb10
+
+bb84.loopexit:                                    ; preds = %bb75
+  ret void
+}
+
+attributes #0 = { "target-features"="+transactional-execution,+vector" }