[MemorySSA] Be more conservative when traversing MemoryPhis.

[fhahn]

Summary

I think we need to be even more conservative when traversing memory
phis, to make sure we catch any loop carried dependences.

This approach updates fillInCurrentPair to use unknown sizes for
locations when we walk over a phi, unless the location is guaranteed to
be loop-invariant for any possible loop. Using an unknown size for
locations should ensure we catch all memory accesses to locations after
the given memory location, which includes loop-carried dependences.

[fhahn]

Add accidentially dropped include of User.h

[asbirlea]

I'm in favor of being conservative here and checking for only constant indexes on the geps.

llvm/include/llvm/Analysis/MemorySSA.h

1262–1270

I'm not clear that the size should be always unknown after phi translation with different ptr, but feel free to correct me.
Here's my suggestion.

if (Translator.getAddr() != Location.Ptr) {
  CurrentPair.second = CurrentPair.second.getWithNewPtr(Translator.getAddr());
  if (PerformedPhiTranslation)
            *PerformedPhiTranslation = true;
} else {
  CurrentPair.second = Location.getWithNewSize(LocationSize::unknown());
}

[fhahn]

llvm/include/llvm/Analysis/MemorySSA.h

1262–1270

Hm, I think if we translate to a different address, we still should set to an unknown size, as the translated address could itself be loop dependent and reference multiple actual locations.

But if we translate to an invariant address, it should probably be safe to use the precise address?

The invariance criteria in the patch is just a few things that matter in practice and are easy to check, but I am sure there is potential for detecting more cases there, after we established a safe baseline

[fhahn]

use precise size for translated addr.

[fhahn]

llvm/include/llvm/Analysis/MemorySSA.h

1262–1270

I tried to come up with a test case where things go wrong when we use the precise location after successfully translating the address, but failed to do so.

I adjusted the code to keep the precise location when PHI translation succeeded. I am still not entirely sure if this is completely safe, but with DSE & MemorySSA there is now a client that will most likely surface a test case, if things go wrong.

Please let me know which approach you prefer, I am fine with either.

[asbirlea]

llvm/include/llvm/Analysis/MemorySSA.h

1262–1270

My inclination here after further review of the code is to not set the size to unknown for all cases, but it's possible it's necessary.
I'd use the same loop invariant condition on the new address.

if (Translator.getAddr() != Location.Ptr) {
  CurrentPair.second = CurrentPair.second.getWithNewPtr(Translator.getAddr());

  if (Translator.getAddr() && 
      !IsGuaranteedLoopInvariant(const_cast<Value *>(Translator.getAddr()))
          CurrentPair.second = CurrentPair.second.getWithNewSize(LocationSize::unknown());

  if (PerformedPhiTranslation)
          *PerformedPhiTranslation = true;
}

(Move Translator.getAddr() to a local variable)

Also, use CurrentPair.second = CurrentPair.second.get..., not CurrentPair.second = Location.get so if the size was reset in the above condition checking loop invariance, that info is kept.

I *think* this is conservatively correct. What do you think?

[fhahn]

Apply suggested change, set size to unknown if result of phi translation is not invariant.

[fhahn]

llvm/include/llvm/Analysis/MemorySSA.h

1262–1270

I *think* this is conservatively correct. What do you think?

Thanks, I applied the suggestion. This should be conservatively correct. Once this goes in I plan on enabling DSE + MemorySSA again and see if/what the remaining failures are.

[nikic]

llvm/include/llvm/Analysis/MemorySSA.h

1251

As the comment correctly states, an unknown size guarantees that locations after the pointer are considered as clobbers. However, locations before it are not. Could there still be an issue for decrementing pointer loops here?

[fhahn]

llvm/include/llvm/Analysis/MemorySSA.h

1251

It appears that currently things work out fine with decrementing pointers because of how BasicAA deals with negative offsets. And there are also a few checks that bail out if either size is unknown. I am not familiar enough with the walking code/the basicAA logic for those cases to judge if we just get lucky. In any case, I put up 7fa8b629208c which adds the decrement version of the test added here. Without the patch, it has the same issue as the increment version.

[nikic]

llvm/include/llvm/Analysis/MemorySSA.h

1251

Thanks for adding the test case! I believe that we are indeed getting lucky right now, in that BasicAA is currently slightly over-conservative when it comes to negative offsets, and it is thus hard to reproduce any issues. When I apply D91482 over the new test, it produces an incorrect liveOnEntry use. Assuming my understanding of LocationSize::unknown() is correct, that's an issue with this MemorySSA code rather than the patch.

llvm/include/llvm/Analysis/MemorySSA.h

 #include "llvm/ADT/simple_ilist.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DerivedUser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
upward_defs_iterator &operator++() {
     if (DefIterator != OriginalAccess->defs_end())
       fillInCurrentPair();
     return *this;
   }
 
   BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
 
 private:
+  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
+  /// loop. In particular, this guarantees that it only references a single
+  /// MemoryLocation during execution of the containing function.
+  bool IsGuaranteedLoopInvariant(Value *Ptr) const {
+    auto IsGuaranteedLoopInvariantBase = [](Value *Ptr) {
+      Ptr = Ptr->stripPointerCasts();
+      if (auto *I = dyn_cast<Instruction>(Ptr)) {
+        if (isa<AllocaInst>(Ptr))
+          return true;
+        return false;
+      }
+      return true;
+    };
+
+    Ptr = Ptr->stripPointerCasts();
+    if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
+      return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
+             GEP->hasAllConstantIndices();
+    }
+    return IsGuaranteedLoopInvariantBase(Ptr);
+  }
+
   void fillInCurrentPair() {
     CurrentPair.first = *DefIterator;
+    CurrentPair.second = Location;
     if (WalkingPhi && Location.Ptr) {
+      // Mark size as unknown, if the location is not guaranteed to be
+      // loop-invariant for any possible loop in the function. Setting the size
+      // to unknown guarantees that any memory accesses that access locations
+      // after the pointer are considered as clobbers, which is important to
+      // catch loop carried dependences.
+      if (Location.Ptr &&
+          !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr)))
+        CurrentPair.second = Location.getWithNewSize(LocationSize::unknown());
       PHITransAddr Translator(
           const_cast<Value *>(Location.Ptr),
           OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
+
       if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
                                         DefIterator.getPhiArgBlock(), DT,
                                         true)) {
-        if (Translator.getAddr() != Location.Ptr) {
-          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
+        Value *TransAddr = Translator.getAddr();
+        if (TransAddr != Location.Ptr) {
+          CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
+
+          if (TransAddr &&
+              !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr)))
+            CurrentPair.second =
+                CurrentPair.second.getWithNewSize(LocationSize::unknown());
+
           if (PerformedPhiTranslation)
             *PerformedPhiTranslation = true;
-          return;
         }
-      } else {
-        CurrentPair.second = Location.getWithNewSize(LocationSize::unknown());
-        return;
       }
     }
-    CurrentPair.second = Location;
   }
 
   MemoryAccessPair CurrentPair;
   memoryaccess_def_iterator DefIterator;
   MemoryLocation Location;
   MemoryAccess *OriginalAccess = nullptr;
   DominatorTree *DT = nullptr;
   bool WalkingPhi = false;

llvm/test/Analysis/MemorySSA/phi-translation.ll

 declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
 
 define void @another_loop_clobber() {
 ; CHECK-LABEL: void @another_loop_clobber
 ; CHECK-LABEL: loop.header:
 ; CHECK-NEXT:  ; 4 = MemoryPhi({entry,1},{cond.read,3})
 
 ; CHECK-LABEL: cond.read:
-; NOLIMIT:     ; MemoryUse(liveOnEntry)
-; LIMIT:       ; MemoryUse(4)
+; CHECK:       ; MemoryUse(4)
 ; CHECK-NEXT:  %use = load i32, i32* %ptr.1, align 4
 ; CHECK-NEXT:  ; 2 = MemoryDef(4)
 ; CHECK-NEXT:  %c.2 = call i1 @cond(i32 %use)
 ; CHECK-NEXT:  %ptr.10 = getelementptr inbounds [12 x i32], [12 x i32]* %nodeStack, i32 0, i32 %inc
 ; CHECK-NEXT:  ; 3 = MemoryDef(2)
 ; CHECK-NEXT:  store i32 10, i32* %ptr.2, align 4
 
 entry: