[MSSA] Fix PR28880 by fixing stack popping behavior.

[• dberlin]

Summary

In the use optimizer, we need to keep track of the stack size after popping off dominating accesses, or else we may decide a lower bound is still valid when it is not due to
intervening pushes.
Fixes PR28880 (and probably a bunch of other things).

[sebpop]

LGTM.
Let's enable gvn-hoist back again once this is committed.

test/Transforms/Util/MemorySSA/pr28880.ll

54 ↗

(On Diff #67075)

You may want to remove all these attributes.

[• dberlin]

• Update to check domination of lower bound

[sebpop]

You may want to add the testcases you were speaking about that break the logic of checking the stack size.

[george.burgess.iv]

Ooh, tricky. LGTM with sebpop's comment addressed; I'm fine if the stack size test cases are committed later. Thanks for the patch!

I'll see what I can do to add EXPENSIVE_CHECKS to the use optimizer (like the ones we have in the walker). :)

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

struct MemlocStackInfo {
     // the stack changes due to pushes or pops, these versions increase.
     unsigned long StackEpoch;
     unsigned long PopEpoch;
     // This is the lower bound of places on the stack to check. It is equal to
     // the place the last stack walk ended.
     // Note: Correctness depends on this being initialized to 0, which densemap
     // does
     unsigned long LowerBound;
+    const BasicBlock *LowerBoundBlock;
     // This is where the last walk for this memory location ended.
     unsigned long LastKill;
     bool LastKillValid;
   };
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
   MemorySSA *MSSA;
void MemorySSA::OptimizeUses::optimizeUsesInBlock(
   while (!VersionStack.empty()) {
     BasicBlock *BackBlock = VersionStack.back()->getBlock();
     if (DT->dominates(BackBlock, BB))
       break;
     while (VersionStack.back()->getBlock() == BackBlock)
       VersionStack.pop_back();
     ++PopEpoch;
   }
-
   for (MemoryAccess &MA : *Accesses) {
     auto *MU = dyn_cast<MemoryUse>(&MA);
     if (!MU) {
       VersionStack.push_back(&MA);
       ++StackEpoch;
       continue;
     }
 
     if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) {
       MU->setDefiningAccess(MSSA->getLiveOnEntryDef());
       continue;
     }
 
     MemoryLocOrCall UseMLOC(MU);
     auto &LocInfo = LocStackInfo[UseMLOC];
     // If the pop epoch changed, it means we've removed stuff from top of
     // stack due to changing blocks. We may have to reset the lower bound or
     // last kill info.
     if (LocInfo.PopEpoch != PopEpoch) {
       LocInfo.PopEpoch = PopEpoch;
       LocInfo.StackEpoch = StackEpoch;
-      // If the lower bound was in the info we popped, we have to reset it.
-      if (LocInfo.LowerBound >= VersionStack.size()) {
+      // If the lower bound was in something that no longer dominates us, we
+      // have to reset it.
+      // We can't simply track stack size, because the stack may have had
+      // pushes/pops in the meantime.
+      // XXX: This is non-optimal, but only is slower cases with heavily
+      // branching dominator trees.  To get the optimal number of queries would
+      // be to make lowerbound and lastkill a per-loc stack, and pop it until
+      // the top of that stack dominates us.  This does not seem worth it ATM.
+      // A much cheaper optimization would be to always explore the deepest
+      // branch of the dominator tree first. This will guarantee this resets on
+      // the smallest set of blocks.
+      if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
+          !DT->dominates(LocInfo.LowerBoundBlock, BB)){
         // Reset the lower bound of things to check.
         // TODO: Some day we should be able to reset to last kill, rather than
         // 0.
-
         LocInfo.LowerBound = 0;
+        LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
         LocInfo.LastKillValid = false;
       }
     } else if (LocInfo.StackEpoch != StackEpoch) {
       // If all that has changed is the StackEpoch, we only have to check the
       // new things on the stack, because we've checked everything before.  In
       // this case, the lower bound of things to check remains the same.
       LocInfo.PopEpoch = PopEpoch;
       LocInfo.StackEpoch = StackEpoch;
if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
       // We were last killed now by where we got to
       LocInfo.LastKill = UpperBound;
     } else {
       // Otherwise, we checked all the new ones, and now we know we can get to
       // LastKill.
       MU->setDefiningAccess(VersionStack[LocInfo.LastKill]);
     }
     LocInfo.LowerBound = VersionStack.size() - 1;
+    LocInfo.LowerBoundBlock = BB;
   }
 }
 
 /// Optimize uses to point to their actual clobbering definitions.
 void MemorySSA::OptimizeUses::optimizeUses() {
 
   // We perform a non-recursive top-down dominator tree walk
   struct StackInfo {

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

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
+
+; This testcase is reduced from SingleSource/Benchmarks/Misc/fbench.c
+; It is testing to make sure that the MemorySSA use optimizer
+; comes up with right answers when dealing with multiple MemoryLocations
+; over different blocks. See PR28880 for more details.
+@global = external hidden unnamed_addr global double, align 8
+@global.1 = external hidden unnamed_addr global double, align 8
+
+; Function Attrs: nounwind ssp uwtable
+define hidden fastcc void @hoge() unnamed_addr #0 {
+bb:
+  br i1 undef, label %bb1, label %bb2
+
+bb1:                                              ; preds = %bb
+; These accesses should not conflict.
+; CHECK:  1 = MemoryDef(liveOnEntry)
+; 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store double undef, double* @global, align 8
+  store double undef, double* @global, align 8
+; CHECK:  MemoryUse(liveOnEntry)
+; MemoryUse(liveOnEntry)
+; CHECK-NEXT:   %tmp = load double, double* @global.1, align 8
+  %tmp = load double, double* @global.1, align 8
+  unreachable
+
+bb2:                                              ; preds = %bb
+  br label %bb3
+
+bb3:                                              ; preds = %bb2
+  br i1 undef, label %bb4, label %bb6
+
+bb4:                                              ; preds = %bb3
+; These accesses should conflict.
+; CHECK:  2 = MemoryDef(liveOnEntry)
+; 2 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store double 0.000000e+00, double* @global.1, align 8
+  store double 0.000000e+00, double* @global.1, align 8
+; CHECK:  MemoryUse(2)
+; MemoryUse(2)
+; CHECK-NEXT:   %tmp5 = load double, double* @global.1, align 8
+  %tmp5 = load double, double* @global.1, align 8
+  unreachable
+
+bb6:                                              ; preds = %bb3
+  unreachable
+}
+
+attributes #0 = { nounwind ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }
+