[MemDep] Handle gep with zeros for invariant.group

[Prazek]

Summary

gep 0, 0 is equivalent to bitcast. LLVM canonicalizes it
to getelementptr because it make SROA can then handle it.

Simple case like

void g(A &a) {
  z(a);
  if (glob)
      a.foo();
}
void testG() {
  A a;
  g(a);
}

was not devirtualized with -fstrict-vtable-pointers because luck of
handling for gep 0 in Memory Dependence Analysis

[Prazek]

Updated documentation

[Prazek]

Fixed comment

[chandlerc]

While I think this patch is simple and a nice pragmatic improvement, I don't want to prematurely cut off discussion about whether we have the right canonicalization here. Maybe leave a FIXME about the fact that we have two representations that are used? Unsure

I suspect something like this should go in at least while instcombine is actively canonicalizing in this direction just for practical reasons.

lib/Analysis/MemoryDependenceAnalysis.cpp

354–355 ↗

(On Diff #82553)

Is the adding of const everywhere helping much? We've historically avoided it, but I have no really strong opinions...

356–359 ↗

(On Diff #82553)

I think its fine to just use [&] capture on simple factorings like this.

383–384 ↗

(On Diff #82553)

It would be nice to avoid going through the type lookup machinery twice here.

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

354–355 ↗

(On Diff #82553)

I only added 4 consts, where 2 are inside container and 2 in the loop (which could be avoided by using auto, but in that cases it seems cleaner without auto).

I prefer const in the container types because I can show this way that I am not going to modify any of these values

383–384 ↗

(On Diff #82553)

Code elegance your concern here right?
I can put it in ifs like

if (isa<BitCastInst>(U)) {
  TryInsertToQueue(U);
  continue;
}
if (auto *GEP = dyn_cast<GetElementPtr>(U)) {
  if(GEP->hasAllZeroIndices())
    TryInsertToQueue(U);
  continue;
}

I am not sure if it will be cleaner (specially because of nested if)

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

383–384 ↗

(On Diff #82553)

if (auto *GEP = dyn_cast<GetElementPtr>(U); GEP && GEP->hasAllZeroIndices()) {

TryInsertToQueue(U);
continue;

}

This is exactly why I really would love to use C++17 in LLVM :)

[JDevlieghere]

lib/Analysis/MemoryDependenceAnalysis.cpp

383–384 ↗

(On Diff #82553)

Alternatively you could switch on U->getOpcode() and use a regular cast. This way you have to check the type only once, at the expense of adding more clutter. Wouldn't do it here though.

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

383–384 ↗

(On Diff #82553)

I am pretty sure that clang is smart enough to do the exact same thing (all the functions are inline so it is not that hard)

[Prazek]

Added comments and & in lambda

[Prazek]

Addressing Chandler's comments

[Prazek]

• small fix

[Prazek]

I am not really sure who is the code owner of MemDep

[reames]

lib/Analysis/MemoryDependenceAnalysis.cpp

392 ↗

(On Diff #82609)

minor: remove brackets for single statement ifs.

test/Transforms/GVN/invariant.group.ll

323 ↗

(On Diff #82609)

you need a few more check statements here. As written, I'm not sure what this test is testing by just reading it.

Also, can you strip away any of this?

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

392 ↗

(On Diff #82609)

sure

test/Transforms/GVN/invariant.group.ll

323 ↗

(On Diff #82609)

Strip away what?

Test checks if invariant.group works also on zero geps (%2).
You are right, I need at least check of
call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a)

[Prazek]

• small fix
• address Phillip's comments

[reames]

LGTM

lib/Analysis/MemoryDependenceAnalysis.cpp

368 ↗

(On Diff #82723)

minor: walking back the def chain could be handled by a call to stripPointerCasts. This can be a following cleanup change,

[Prazek]

Thanks :)

lib/Analysis/MemoryDependenceAnalysis.cpp

368 ↗

(On Diff #82723)

do you mean firstly call stripPointerCasts on the LoadOperand so that we will only have to walk down the tree? I didn't know this function, but I was also thinking about splitting it into 2 loops to firstly get to the top.

llvm/trunk/docs/LangRef.rst

 '``invariant.group``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 The ``invariant.group`` metadata may be attached to ``load``/``store`` instructions.
 The existence of the ``invariant.group`` metadata on the instruction tells 
 the optimizer that every ``load`` and ``store`` to the same pointer operand 
 within the same invariant group can be assumed to load or store the same  
 value (but see the ``llvm.invariant.group.barrier`` intrinsic which affects 
-when two pointers are considered the same).
+when two pointers are considered the same). Pointers returned by bitcast or
+getelementptr with only zero indices are considered the same.
 
 Examples:
 
 .. code-block:: llvm
 
    @unknownPtr = external global i8
    ...
    %ptr = alloca i8

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
   }
   return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst,
                                         Limit);
 }
 
 MemDepResult
 MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
                                                             BasicBlock *BB) {
+
+  auto *InvariantGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group);
+  if (!InvariantGroupMD)
+    return MemDepResult::getUnknown();
+
   Value *LoadOperand = LI->getPointerOperand();
   // It's is not safe to walk the use list of global value, because function
   // passes aren't allowed to look outside their functions.
   if (isa<GlobalValue>(LoadOperand))
     return MemDepResult::getUnknown();
 
-  auto *InvariantGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group);
-  if (!InvariantGroupMD)
-    return MemDepResult::getUnknown();
-
-  SmallSet<Value *, 14> Seen;
   // Queue to process all pointers that are equivalent to load operand.
-  SmallVector<Value *, 8> LoadOperandsQueue;
-  LoadOperandsQueue.push_back(LoadOperand);
-  Seen.insert(LoadOperand);
+  SmallVector<const Value *, 8> LoadOperandsQueue;
+  SmallSet<const Value *, 14> SeenValues;
+  auto TryInsertToQueue = [&](Value *V) {
+    if (SeenValues.insert(V).second)
+      LoadOperandsQueue.push_back(V);
+  };
+
+  TryInsertToQueue(LoadOperand);
   while (!LoadOperandsQueue.empty()) {
-    Value *Ptr = LoadOperandsQueue.pop_back_val();
+    const Value *Ptr = LoadOperandsQueue.pop_back_val();
+    assert(Ptr);
     if (isa<GlobalValue>(Ptr))
       continue;
 
-    if (auto *BCI = dyn_cast<BitCastInst>(Ptr)) {
-      if (Seen.insert(BCI->getOperand(0)).second) {
-        LoadOperandsQueue.push_back(BCI->getOperand(0));
-      }
-    }
+    // Value comes from bitcast: Ptr = bitcast x. Insert x.
+    if (auto *BCI = dyn_cast<BitCastInst>(Ptr))
+      TryInsertToQueue(BCI->getOperand(0));
+    // Gep with zeros is equivalent to bitcast.
+    // FIXME: we are not sure if some bitcast should be canonicalized to gep 0
+    // or gep 0 to bitcast because of SROA, so there are 2 forms. When typeless
+    // pointers will be upstream then both cases will be gone (and this BFS
+    // also won't be needed).
+    if (auto *GEP = dyn_cast<GetElementPtrInst>(Ptr))
+      if (GEP->hasAllZeroIndices())
+        TryInsertToQueue(GEP->getOperand(0));
 
-    for (Use &Us : Ptr->uses()) {
+    for (const Use &Us : Ptr->uses()) {
       auto *U = dyn_cast<Instruction>(Us.getUser());
       if (!U || U == LI || !DT.dominates(U, LI))
         continue;
 
-      if (auto *BCI = dyn_cast<BitCastInst>(U)) {
-        if (Seen.insert(BCI).second) {
-          LoadOperandsQueue.push_back(BCI);
-        }
+      // Bitcast or gep with zeros are using Ptr. Add to queue to check it's
+      // users.      U = bitcast Ptr
+      if (isa<BitCastInst>(U)) {
+        TryInsertToQueue(U);
+        continue;
+      // U = getelementptr Ptr, 0, 0...
+      if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
+        if (GEP->hasAllZeroIndices()) {
+          TryInsertToQueue(U);
           continue;
         }
+
       // If we hit load/store with the same invariant.group metadata (and the
       // same pointer operand) we can assume that value pointed by pointer
       // operand didn't change.
       if ((isa<LoadInst>(U) || isa<StoreInst>(U)) && U->getParent() == BB &&
           U->getMetadata(LLVMContext::MD_invariant_group) == InvariantGroupMD)
         return MemDepResult::getDef(U);
     }
   }

llvm/trunk/test/Transforms/GVN/invariant.group.ll

; CHECK: store i8 %unknownValue, i8* %ptr, !invariant.group !0
     store i8 %unknownValue, i8* %ptr, !invariant.group !0 
 
     %newPtr2 = call i8* @llvm.invariant.group.barrier(i8* %ptr)
     %d = load i8, i8* %newPtr2, !invariant.group !0  ; Can't step through invariant.group.barrier to get value of %ptr
 ; CHECK: ret i8 %d
     ret i8 %d
 }
 
+; This test checks if invariant.group understands gep with zeros
+; CHECK-LABEL: define void @testGEP0() {
+define void @testGEP0() {
+  %a = alloca %struct.A, align 8
+  %1 = bitcast %struct.A* %a to i8*
+  %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
+  store i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %2, align 8, !invariant.group !0
+; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a)
+  call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a) ; This call may change vptr
+  %3 = load i8, i8* @unknownPtr, align 4
+  %4 = icmp eq i8 %3, 0
+  br i1 %4, label %_Z1gR1A.exit, label %5
+
+; This should be devirtualized by invariant.group
+  %6 = bitcast %struct.A* %a to void (%struct.A*)***
+  %7 = load void (%struct.A*)**, void (%struct.A*)*** %6, align 8, !invariant.group !0
+  %8 = load void (%struct.A*)*, void (%struct.A*)** %7, align 8
+; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
+  call void %8(%struct.A* nonnull %a)
+  br label %_Z1gR1A.exit
+
+_Z1gR1A.exit:                                     ; preds = %0, %5
+  ret void
+}
+
 declare void @foo(i8*)
 declare void @bar(i8)
 declare i8* @getPointer(i8*)
 declare void @_ZN1A3fooEv(%struct.A*)
 declare void @_ZN1AC1Ev(%struct.A*)
 declare i8* @llvm.invariant.group.barrier(i8*)
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1 %cmp.vtables) #0
 
 
 attributes #0 = { nounwind }
 ; CHECK: ![[OneMD]] = !{!"other ptr"}
 !0 = !{!"magic ptr"}
 !1 = !{!"other ptr"}
 !2 = !{!"vtable_of_a"}

llvm/trunk/test/Transforms/NewGVN/invariant.group.ll

; CHECK: store i8 %unknownValue, i8* %ptr, !invariant.group !0
     store i8 %unknownValue, i8* %ptr, !invariant.group !0 
 
     %newPtr2 = call i8* @llvm.invariant.group.barrier(i8* %ptr)
     %d = load i8, i8* %newPtr2, !invariant.group !0  ; Can't step through invariant.group.barrier to get value of %ptr
 ; CHECK: ret i8 %d
     ret i8 %d
 }
 
+; This test checks if invariant.group understands gep with zeros
+; CHECK-LABEL: define void @testGEP0() {
+define void @testGEP0() {
+  %a = alloca %struct.A, align 8
+  %1 = bitcast %struct.A* %a to i8*
+  %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
+  store i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %2, align 8, !invariant.group !0
+; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a)
+  call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a) ; This call may change vptr
+  %3 = load i8, i8* @unknownPtr, align 4
+  %4 = icmp eq i8 %3, 0
+  br i1 %4, label %_Z1gR1A.exit, label %5
+
+; This should be devirtualized by invariant.group
+  %6 = bitcast %struct.A* %a to void (%struct.A*)***
+  %7 = load void (%struct.A*)**, void (%struct.A*)*** %6, align 8, !invariant.group !0
+  %8 = load void (%struct.A*)*, void (%struct.A*)** %7, align 8
+; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
+  call void %8(%struct.A* nonnull %a)
+  br label %_Z1gR1A.exit
+
+_Z1gR1A.exit:                                     ; preds = %0, %5
+  ret void
+}
+
 declare void @foo(i8*)
 declare void @bar(i8)
 declare i8* @getPointer(i8*)
 declare void @_ZN1A3fooEv(%struct.A*)
 declare void @_ZN1AC1Ev(%struct.A*)
 declare i8* @llvm.invariant.group.barrier(i8*)
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1 %cmp.vtables) #0
 
 
 attributes #0 = { nounwind }
 ; CHECK: ![[OneMD]] = !{!"other ptr"}
 !0 = !{!"magic ptr"}
 !1 = !{!"other ptr"}
 !2 = !{!"vtable_of_a"}