[MemorySSA] Iteratively check if gep's pointer operand is a guaranteed loop invariant

[StephenFan]

Summary

On the past, we just check if gep's pointer operand is a non-instruction
operand or is a alloca instruction to decide if it is guaranteed to be
a loop invariant. If the gep's pointer operand is also a gep then it would
be considered to be a non-guaranteed loop invariant. This patch makes
MemorySSA Recursively checking if gep's pointer operand is guaranteed
to be a loop invariant.

[asbirlea]

llvm/lib/Analysis/MemorySSA.cpp

2642–2643

This recursion should not be unbounded, and preferably make it iterative.
A similar example: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ValueTracking.cpp#L4568

[StephenFan]

Replace recursion as bounded iteration.

[StephenFan]

Remove TODO.

[asbirlea]

lgtm with comments addressed.

llvm/lib/Analysis/MemorySSA.cpp

2629

The AA "look through geps" limit is 6. I don't have a strong preference on the value, I don't have any data on how frequent this will be useful..
Would be good to use a cl::opt instead of a local constant though, for easier testing.

2640

nit: Could reduce the if nesting

auto *I = dyn_cast<Instruction>(Ptr);
if (!I || isa<AllocaInst>(Ptr) || I->getParent()->isEntryBlock())
  return true;
 
if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
  if (!GEP->hasAllConstantIndices())
    return false;
  Ptr = GEP->getPointerOperand();
}

[nikic]

I'm curious where this came up in practice. Constant GEP based on constant GEP gets merged by InstCombine.

FWIW, we have a stripInBoundsConstantOffsets() method, which does nearly what we want here. I wonder whether it would make sense to add a new PointerStripKind for this? (I think some existing users of stripInBoundsConstantOffsets don't actually need the "inbounds" part and just end up using it because it's convenient.)

[StephenFan]

In D143641#4125313, @nikic wrote:

I'm curious where this came up in practice. Constant GEP based on constant GEP gets merged by InstCombine.

TBH, The test was constructed by hand. So it may not make sense in practice since as you said it always gets merged by InstCombine. But that reminds me if it makes sense to also check whether the index operands are invariant?

FWIW, we have a stripInBoundsConstantOffsets() method, which does nearly what we want here. I wonder whether it would make sense to add a new PointerStripKind for this? (I think some existing users of stripInBoundsConstantOffsets don't actually need the "inbounds" part and just end up using it because it's convenient.)

I think it makes sense. If I use the stripInBoundsConstantOffsets() here, I will not care about the inbounds flag.

[StephenFan]

https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L1283 may also be a potential user if a new PointerStripKind added.

llvm/lib/Analysis/MemorySSA.cpp

void MemoryDef::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryDef *>(Self);
 }
 
 void MemoryUse::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryUse *>(Self);
 }
 
 bool upward_defs_iterator::IsGuaranteedLoopInvariant(const Value *Ptr) const {
-  auto IsGuaranteedLoopInvariantBase = [](const Value *Ptr) {
-    Ptr = Ptr->stripPointerCasts();
-    if (!isa<Instruction>(Ptr))
-      return true;
-    return isa<AllocaInst>(Ptr);
-  };
-
+  // TODO: Increase limit?
+  const unsigned MaxGEPToLookup = 2;
+  for (unsigned I = 0; I < MaxGEPToLookup; I++) {
     Ptr = Ptr->stripPointerCasts();
     if (auto *I = dyn_cast<Instruction>(Ptr)) {
-    if (I->getParent()->isEntryBlock())
+      if (isa<AllocaInst>(Ptr) || I->getParent()->isEntryBlock())
         return true;
-  }
       if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
-    return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
-           GEP->hasAllConstantIndices();
+        if (!GEP->hasAllConstantIndices())
+          return false;
+        Ptr = GEP->getPointerOperand();
       }
-  return IsGuaranteedLoopInvariantBase(Ptr);
+    } else
+      return true;
+  }
+  return false;
 }

llvm/test/Analysis/MemorySSA/loop-invariant.ll

 ; RUN: opt -passes='print<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
 
-; TODO: The load's MemoryUse can be defined by liveOnEntry. Since
+; The load's MemoryUse can be defined by liveOnEntry. Since
 ; %p2 is a loop invariant and the MemoryLoc of load instr and store inst in
 ; loop block are NoAlias
 ;
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(liveOnEntry)
 ; CHECK: %val = load i32, ptr %p2
 define void @gep(ptr %ptr) {
 entry:
   %p1 = getelementptr i32, ptr %ptr, i32 1
   br label %tmp
 
 tmp:
   %p2 = getelementptr i32, ptr %p1, i32 1
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %tmp ], [ %x.inc, %loop ]
   %val = load i32, ptr %p2
   %p3 = getelementptr i32, ptr %p2, i32 1
   store volatile i32 0, ptr %p3
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
-; CHECK: MemoryUse(2)
+; CHECK: %x = phi i32 [ 0, %tmp ], [ %x.inc, %loop ]
+; CHECK-NEXT: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: %val = load i32, ptr %p2
 define void @load_entry_block(ptr %ptr, ptr %addr) {
 entry:
   %p1 = load ptr, ptr %ptr
   br label %tmp
 
 tmp:
   %p2 = getelementptr i32, ptr %p1, i32 1