[MemDep] NFC walk invariant.group graph only down

[Prazek]

Summary

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

[reames]

lib/Analysis/MemoryDependenceAnalysis.cpp

363–364

Don't you need to check this before the loop? (i.e. why did this become an assert rather than a test?)

378

Wasn't this comment in the other change you landed?

[Prazek]

BTW I think I also don't need SeenOperands set now because there is no way I could insert the same operand twice

lib/Analysis/MemoryDependenceAnalysis.cpp

363–364

Good catch. There is check for GlobalValue on beginning of the function, but it check for pointerOperand.
So if I will check pointer after stripping, then this will be valid. I will write test for that.

378

I just moved it from line 372

[Prazek]

• fixes

[Prazek]

ping

[davide]

lib/Analysis/MemoryDependenceAnalysis.cpp

360

Any reason why did you change the initial size of the SmallVector?

test/Transforms/GVN/invariant.group.ll

372–393

ideally the checks should be auto-generated (many people, me included forget to do so)

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

360

I deleted SmallSet of 14 elements, so I thought I can be more lavish here :)

test/Transforms/GVN/invariant.group.ll

372–393

Excuse me, but I don't understand your comment. Is there anything wrong with my patch, or is it just comment about the perfect world?

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

360

8 would be probably still enough, I never did any measurements, so if you would like, I can change it back to 8

[davide]

lib/Analysis/MemoryDependenceAnalysis.cpp

360

I think we can leave it as is. In case the malloc traffic hints we should choose a larger value, fair enough, but I wouldn't change without backing data/real justification :)

test/Transforms/GVN/invariant.group.ll

372–393

You may want to run utils/update_test_checks.py on this to autogenerate checks.

[Prazek]

• fixes

[davide]

LGTM, please wait if somebody has remaining comments.

[Prazek]

test/Transforms/GVN/invariant.group.ll

372–393

I still don't understand what this script is doing. I runned it, and it only reformatted test (reduced indentation), but non of the check comments have been changed

[Prazek]

Philip, do you want to check it last time?

lib/Analysis/MemoryDependenceAnalysis.cpp

 MemDepResult
 MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
                                                             BasicBlock *BB) {
 
   auto *InvariantGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group);
   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());
       if (!U || U == LI || !DT.dominates(U, LI))
         continue;
 
       // 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;
         }
 
       // 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)

test/Transforms/GVN/invariant.group.ll

 ; 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
 }
 
+; 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
 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"}

test/Transforms/NewGVN/invariant.group.ll

 ; 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
 }
 
+; 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
 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"}