[MemDep] NFC walk invariant.group graph only down

Summary:
By using stripPointerCasts we can get to the root
value and then walk down the bitcast graph

Reviewers: reames

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D28181

llvm-svn: 291405

3 files changed, 120 insertions, 26 deletions

diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
index 2746361ab4b..e7415e62319 100644
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -344,38 +344,24 @@ MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
   if (!InvariantGroupMD)
     return MemDepResult::getUnknown();
 
-  Value *LoadOperand = LI->getPointerOperand();
+  // Take the ptr operand after all casts and geps 0. This way we can search
+  // cast graph down only.
+  Value *LoadOperand = LI->getPointerOperand()->stripPointerCasts();
+
   // It's is not safe to walk the use list of global value, because function
   // passes aren't allowed to look outside their functions.
+  // FIXME: this could be fixed by filtering instructions from outside
+  // of current function.
   if (isa<GlobalValue>(LoadOperand))
     return MemDepResult::getUnknown();
 
   // Queue to process all pointers that are equivalent to load operand.
   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);
+  LoadOperandsQueue.push_back(LoadOperand);
   while (!LoadOperandsQueue.empty()) {
     const Value *Ptr = LoadOperandsQueue.pop_back_val();
-    assert(Ptr);
-    if (isa<GlobalValue>(Ptr))
-      continue;
-
-    // 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));
+    assert(Ptr && !isa<GlobalValue>(Ptr) &&
+           "Null or GlobalValue should not be inserted");
 
     for (const Use &Us : Ptr->uses()) {
       auto *U = dyn_cast<Instruction>(Us.getUser());
@@ -385,13 +371,17 @@ MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
       // 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);
+        LoadOperandsQueue.push_back(U);
         continue;
       }
-      // U = getelementptr Ptr, 0, 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 ready then both cases will be gone
+      // (and this BFS also won't be needed).
       if (auto *GEP = dyn_cast<GetElementPtrInst>(U))
         if (GEP->hasAllZeroIndices()) {
-          TryInsertToQueue(U);
+          LoadOperandsQueue.push_back(U);
           continue;
         }
 
diff --git a/llvm/test/Transforms/GVN/invariant.group.ll b/llvm/test/Transforms/GVN/invariant.group.ll
index 026671a5bdf..d0b32d7f3dd 100644
--- a/llvm/test/Transforms/GVN/invariant.group.ll
+++ b/llvm/test/Transforms/GVN/invariant.group.ll
@@ -344,11 +344,63 @@ _Z1gR1A.exit:                                     ; preds = %0, %5
   ret void
 }
 
+; Check if no optimizations are performed with global pointers.
+; FIXME: we could do the optimizations if we would check if dependency comes
+; from the same function.
+; CHECK-LABEL: define void @testGlobal() {
+define void @testGlobal() {
+; CHECK:  %a = load i8, i8* @unknownPtr, !invariant.group !0
+   %a = load i8, i8* @unknownPtr, !invariant.group !0
+   call void @foo2(i8* @unknownPtr, i8 %a)
+; CHECK:  %1 = load i8, i8* @unknownPtr, !invariant.group !0
+   %1 = load i8, i8* @unknownPtr, !invariant.group !0
+   call void @bar(i8 %1)
+
+   %b0 = bitcast i8* @unknownPtr to i1*
+   call void @fooBit(i1* %b0, i1 1)
+; Adding regex because of canonicalization of bitcasts
+; CHECK: %2 = load i1, i1* {{.*}}, !invariant.group !0
+   %2 = load i1, i1* %b0, !invariant.group !0
+   call void @fooBit(i1* %b0, i1 %2)
+; CHECK:  %3 = load i1, i1* {{.*}}, !invariant.group !0
+   %3 = load i1, i1* %b0, !invariant.group !0
+   call void @fooBit(i1* %b0, i1 %3)
+   ret void
+}
+; And in the case it is not global
+; CHECK-LABEL: define void @testNotGlobal() {
+define void @testNotGlobal() {
+   %a = alloca i8
+   call void @foo(i8* %a)
+; CHECK:  %b = load i8, i8* %a, !invariant.group !0
+   %b = load i8, i8* %a, !invariant.group !0
+   call void @foo2(i8* %a, i8 %b)
+
+   %1 = load i8, i8* %a, !invariant.group !0
+; CHECK: call void @bar(i8 %b)
+   call void @bar(i8 %1)
+
+   %b0 = bitcast i8* %a to i1*
+   call void @fooBit(i1* %b0, i1 1)
+; CHECK: %trunc = trunc i8 %b to i1
+   %2 = load i1, i1* %b0, !invariant.group !0
+; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %trunc)
+   call void @fooBit(i1* %b0, i1 %2)
+   %3 = load i1, i1* %b0, !invariant.group !0
+; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %trunc)
+   call void @fooBit(i1* %b0, i1 %3)
+   ret void
+}
+
+
 declare void @foo(i8*)
+declare void @foo2(i8*, i8)
 declare void @bar(i8)
 declare i8* @getPointer(i8*)
 declare void @_ZN1A3fooEv(%struct.A*)
 declare void @_ZN1AC1Ev(%struct.A*)
+declare void @fooBit(i1*, i1)
+
 declare i8* @llvm.invariant.group.barrier(i8*)
 
 ; Function Attrs: nounwind
diff --git a/llvm/test/Transforms/NewGVN/invariant.group.ll b/llvm/test/Transforms/NewGVN/invariant.group.ll
index 2bddc99c8b8..80c6e05a8e2 100644
--- a/llvm/test/Transforms/NewGVN/invariant.group.ll
+++ b/llvm/test/Transforms/NewGVN/invariant.group.ll
@@ -345,11 +345,63 @@ _Z1gR1A.exit:                                     ; preds = %0, %5
   ret void
 }
 
+; Check if no optimizations are performed with global pointers.
+; FIXME: we could do the optimizations if we would check if dependency comes
+; from the same function.
+; CHECK-LABEL: define void @testGlobal() {
+define void @testGlobal() {
+; CHECK:  %a = load i8, i8* @unknownPtr, !invariant.group !0
+   %a = load i8, i8* @unknownPtr, !invariant.group !0
+   call void @foo2(i8* @unknownPtr, i8 %a)
+; CHECK:  %1 = load i8, i8* @unknownPtr, !invariant.group !0
+   %1 = load i8, i8* @unknownPtr, !invariant.group !0
+   call void @bar(i8 %1)
+
+   %b0 = bitcast i8* @unknownPtr to i1*
+   call void @fooBit(i1* %b0, i1 1)
+; Adding regex because of canonicalization of bitcasts
+; CHECK: %2 = load i1, i1* {{.*}}, !invariant.group !0
+   %2 = load i1, i1* %b0, !invariant.group !0
+   call void @fooBit(i1* %b0, i1 %2)
+; CHECK:  %3 = load i1, i1* {{.*}}, !invariant.group !0
+   %3 = load i1, i1* %b0, !invariant.group !0
+   call void @fooBit(i1* %b0, i1 %3)
+   ret void
+}
+; And in the case it is not global
+; CHECK-LABEL: define void @testNotGlobal() {
+define void @testNotGlobal() {
+   %a = alloca i8
+   call void @foo(i8* %a)
+; CHECK:  %b = load i8, i8* %a, !invariant.group !0
+   %b = load i8, i8* %a, !invariant.group !0
+   call void @foo2(i8* %a, i8 %b)
+
+   %1 = load i8, i8* %a, !invariant.group !0
+; CHECK: call void @bar(i8 %b)
+   call void @bar(i8 %1)
+
+   %b0 = bitcast i8* %a to i1*
+   call void @fooBit(i1* %b0, i1 1)
+; CHECK: %trunc = trunc i8 %b to i1
+   %2 = load i1, i1* %b0, !invariant.group !0
+; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %trunc)
+   call void @fooBit(i1* %b0, i1 %2)
+   %3 = load i1, i1* %b0, !invariant.group !0
+; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %trunc)
+   call void @fooBit(i1* %b0, i1 %3)
+   ret void
+}
+
+
 declare void @foo(i8*)
+declare void @foo2(i8*, i8)
 declare void @bar(i8)
 declare i8* @getPointer(i8*)
 declare void @_ZN1A3fooEv(%struct.A*)
 declare void @_ZN1AC1Ev(%struct.A*)
+declare void @fooBit(i1*, i1)
+
 declare i8* @llvm.invariant.group.barrier(i8*)
 
 ; Function Attrs: nounwind