[ValueTracking] Remove MaxLookup from getUnderlyingObjects

[vitalybuka]

Summary

Support long chains of instruction where getUnderlyingObject fails.
getUnderlyingObjects already traverse large set on instructions so
there is no reason to limit some sequences by MaxLookup.

getUnderlyingObject needs MaxLookup to avoid infinit loops on cycles.

getUnderlyingObjects uses Visited so it can't get into infinit loops
if it calls getUnderlyingObject with MaxLookup > 0.

So we can continiosly repeate getUnderlyingObject updating Visited and
return all underlying Values.

[vitalybuka]

typo

[lebedev.ri]

so there is no reason to limit some sequences by MaxLookup.

Except avoiding runaway compile time in some degenerate cases possibly?

[vitalybuka]

In D86669#2241103, @lebedev.ri wrote:

so there is no reason to limit some sequences by MaxLookup.

Except avoiding runaway compile time in some degenerate cases possibly?

With the current approach it's easy to make similar degenerate case with selects or phi nodes.
It was O(N) and still O(N) of number instructions.
MaxLookup makes getUnderlyingObject O(1), but it does not make getUnderlyingObjects.

[vitalybuka]

rebase

[lebedev.ri]

I think this would benefit from adding the testcase[s] for the pass that uses this utility that showcase the improvements here.

[vitalybuka]

rebase

[lebedev.ri]

Oh, so wait, we need this for correctness even?
That doesn't look good on the LAA's side.

[vitalybuka]

rebase

[fhahn]

getUnderlyingObjects already traverse large set on instructions so
there is no reason to limit some sequences by MaxLookup.

I am not sure I completely follow this reasoning. Even if it already traverses a large number of instructions, without the depth limit it will visit even more? Do you have any estimate on the impact in terms of extra work?

llvm/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll

96

Not sure if it is really incorrect, but it is certainly a bit misleading; we will create a runtime check between gepB_plus_one and gepB9, which will never succeed I think.

The result with the patch is certainly an improvement.

[vitalybuka]

In D86669#2836130, @fhahn wrote:

getUnderlyingObjects already traverse large set on instructions so
there is no reason to limit some sequences by MaxLookup.

I am not sure I completely follow this reasoning. Even if it already traverses a large number of instructions, without the depth limit it will visit even more? Do you have any estimate on the impact in terms of extra work?

On real program almost always both version will do the same work and default MaxLookup will not be reached.

However there are possible two edge-cases with large number of nodes:
a) Long chain of N values:

a = b, b = c, c = d .... = underlying_object

b) Wide graph with total N values:

a = (a, b, c ....) , a = (a1, a2, ...), b = (b1, b2, ...)...

Existing algorithm will fail on "a" but exits in constant time, it may be able discover all objects on b (if it's not too deep), and but in O(N) time.
Patched algorithm discover all objects, in O(N) in both cases.

So my point is if we accept O(N) for b) why not accept O(N) for a) and let callers avoid thinking about MaxLookup.

[tingwang]

We hit upon one test case (attached test.ll) blocked by this MaxLookup: the default value of MaxLookup is not enough to identify the underlying object, and the alias info added by AddAliasScopeMetadata() is wrong, resulting in wrong schedule decisions in machine-scheduler.

In function widget, pointer %tmp147 in below instruction is not correctly identified by getUnderlyingObjects()

%tmp148 = load i32, i32* %tmp147, align 4, !alias.scope !25, !noalias !26

The chain of pointers is below:

store [0 x %struct.ham.2]* %arg, [0 x %struct.ham.2]** %tmp, align 8
%tmp123 = load [0 x %struct.ham.2]*, [0 x %struct.ham.2]** %tmp, align 8
%tmp127 = bitcast [0 x %struct.ham.2]* %tmp123 to i8*
%tmp128 = getelementptr i8, i8* %tmp127, i64 %tmp126
%tmp136 = getelementptr inbounds i8, i8* %tmp128, i64 %tmp135
%tmp137 = bitcast i8* %tmp136 to [24 x i8]*
%tmp138 = bitcast [24 x i8]* %tmp137 to %struct.ham.2*
%tmp139 = getelementptr inbounds %struct.ham.2, %struct.ham.2* %tmp138, i32 0, i32 1
%tmp140 = bitcast [4 x %struct.spam.3]* %tmp139 to i8*
%tmp141 = getelementptr i8, i8* %tmp140, i64 -4
%tmp146 = getelementptr inbounds i8, i8* %tmp141, i64 %tmp145
%tmp147 = bitcast i8* %tmp146 to i32*

It looks like there is real program affected by this hard limit, and it produced wrong result. Can we think about this twice?

By the way, I used below command line to reproduce the issue.

opt --vector-library=MASSV -passes=default<O3> -aa-pipeline=default -mcpu=pwr9 -o test.err.bc test.ll

test.ll40 KBDownload

[efriedma]

If you're seeing a miscompile, something is probably wrong with the caller. getUnderlyingObjects() is, in general, not guaranteed to produce an identifiable object. If the caller cares, it should check; for example, GlobalsAAResult::getModRefInfoForArgument checks all_of(Objects, isIdentifiedObject).

[vitalybuka]

In D86669#3560983, @efriedma wrote:

If you're seeing a miscompile, something is probably wrong with the caller. getUnderlyingObjects() is, in general, not guaranteed to produce an identifiable object. If the caller cares, it should check; for example, GlobalsAAResult::getModRefInfoForArgument checks all_of(Objects, isIdentifiedObject).

I am not sure why do don't want to make it guaranty with a patch like this?

[efriedma]

In D86669#3561125, @vitalybuka wrote:

In D86669#3560983, @efriedma wrote:

If you're seeing a miscompile, something is probably wrong with the caller. getUnderlyingObjects() is, in general, not guaranteed to produce an identifiable object. If the caller cares, it should check; for example, GlobalsAAResult::getModRefInfoForArgument checks all_of(Objects, isIdentifiedObject).

I am not sure why do don't want to make it guaranty with a patch like this?

How could we possibly guarantee that? In general, we're going to find some opaque thing that both getUnderlyingObjects() and its caller can't understand.

I mean, I guess we could define an API that narrowly guarantees it looks though all bitcast, addrspacecast, gep, phi, and select operations. But that would be expensive in general, and it's not obvious to me it solves anything.

[vitalybuka]

In D86669#3561225, @efriedma wrote:

In D86669#3561125, @vitalybuka wrote:

In D86669#3560983, @efriedma wrote:

If you're seeing a miscompile, something is probably wrong with the caller. getUnderlyingObjects() is, in general, not guaranteed to produce an identifiable object. If the caller cares, it should check; for example, GlobalsAAResult::getModRefInfoForArgument checks all_of(Objects, isIdentifiedObject).

I am not sure why do don't want to make it guaranty with a patch like this?

How could we possibly guarantee that? In general, we're going to find some opaque thing that both getUnderlyingObjects() and its caller can't understand.

I mean, I guess we could define an API that narrowly guarantees it looks though all bitcast, addrspacecast, gep, phi, and select operations. But that would be expensive in general, and it's not obvious to me it solves anything.

Right, I totally forgot the point of the patch :)
I still think removing MaxLookup is good, and simplifies callers side.

[tingwang]

In D86669#3560983, @efriedma wrote:

If you're seeing a miscompile, something is probably wrong with the caller. getUnderlyingObjects() is, in general, not guaranteed to produce an identifiable object. If the caller cares, it should check; for example, GlobalsAAResult::getModRefInfoForArgument checks all_of(Objects, isIdentifiedObject).

Thank you for pointing out the direction. It seems the caller AddAliasScopeMetadata() is making the false assumption without additional check. I will dig a little bit into history, and maybe submit a patch to fix that.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   ///     }
   ///   }
   ///
   /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
   /// should not assume that Curr and Prev share the same underlying object thus
   /// it shouldn't look through the phi above.
   void getUnderlyingObjects(const Value *V,
                             SmallVectorImpl<const Value *> &Objects,
-                            LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
+                            LoopInfo *LI = nullptr);
 
   /// This is a wrapper around getUnderlyingObjects and adds support for basic
   /// ptrtoint+arithmetic+inttoptr sequences.
   bool getUnderlyingObjectsForCodeGen(const Value *V,
                                       SmallVectorImpl<Value *> &Objects);
 
   /// Returns unique alloca where the value comes from, or nullptr.
   /// If OffsetZero is true check that V points to the begining of the alloca.

llvm/lib/Analysis/ValueTracking.cpp

for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
 void llvm::getUnderlyingObjects(const Value *V,
                                 SmallVectorImpl<const Value *> &Objects,
-                                LoopInfo *LI, unsigned MaxLookup) {
+                                LoopInfo *LI) {
   SmallPtrSet<const Value *, 4> Visited;
   SmallVector<const Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     const Value *P = Worklist.pop_back_val();
-    P = getUnderlyingObject(P, MaxLookup);
+    P = getUnderlyingObject(P);
 
     if (!Visited.insert(P).second)
       continue;
 
+    const Value *U = P;
+    P = getUnderlyingObject(P);
+    if (U != P) {
+      // Repeat if getUnderlyingObject terminated on MaxLookup.
+      Worklist.push_back(P);
+      continue;
+    }
+
     if (auto *SI = dyn_cast<SelectInst>(P)) {
       Worklist.push_back(SI->getTrueValue());
       Worklist.push_back(SI->getFalseValue());
       continue;
     }
 
     if (auto *PN = dyn_cast<PHINode>(P)) {
       // If this PHI changes the underlying object in every iteration of the

llvm/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll

for_j.end:
   br i1 %exitcond, label %for_i.end, label %for_i.body
 
 for_i.end:
   ret void
 }
 
 ; CHECK-LABEL: function 'f_deep'
 ; CHECK: for_j.body:
-; FIXME: This is incorrect and is going to be fixed with D86669.
-; CHECK-NEXT: Memory dependences are safe with run-time checks
-; CHECK-NEXT: Dependences:
+; CHECK-NEXT: Report: unsafe dependent memory operations in loop
+; CHECK-NEXT: Dependences: 
+; CHECK-NEXT: Unknown:
+; CHECK-NEXT: %loadB = load i8, i8* %gepB9, align 1 ->
+; CHECK-NEXT: store i8 2, i8* %gepB_plus_one, align 1 
 
 define void @f_deep(i8** noalias %A, i8* noalias %B, i64 %N) {
 for_i.preheader:
   %prev_0 = load i8*, i8** %A, align 8
   br label %for_i.body
 
 for_i.body:
   %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end]

llvm/unittests/Analysis/ValueTrackingTest.cpp

define i32 @test(i32 %x.1, i32 %x.2) {
 
     // Check the depth cutoff results in a conservative result (full set) by
     // passing Depth == MaxDepth == 6.
     ConstantRange CR2 = computeConstantRange(X2, true, &AC, I, 6);
     EXPECT_TRUE(CR2.isFullSet());
   }
 }
 
+TEST_F(ValueTrackingTest, getUnderlyingObjects) {
+  auto M = parseModule(R"(
+  define i32* @test() {
+    %a = alloca i32
+    %1 = getelementptr i32, i32* %a, i32 1
+    %2 = getelementptr i32, i32* %1, i32 1
+    %3 = getelementptr i32, i32* %2, i32 1
+    %4 = getelementptr i32, i32* %3, i32 1
+    %5 = getelementptr i32, i32* %4, i32 1
+    %6 = getelementptr i32, i32* %5, i32 1
+    %7 = getelementptr i32, i32* %6, i32 1
+    %8 = getelementptr i32, i32* %7, i32 1
+    %9 = getelementptr i32, i32* %8, i32 1
+    %r = getelementptr i32, i32* %9, i32 1
+    ret i32* %r
+  })");
+  Function *F = M->getFunction("test");
+  Instruction *I = &findInstructionByName(F, "r");
+  SmallVector<const Value *, 10> Objects;
+  getUnderlyingObjects(I->getOperand(0), Objects);
+  EXPECT_EQ(1u, Objects.size());
+  EXPECT_EQ(1, isa<AllocaInst>(Objects[0]));
+}
+
+TEST_F(ValueTrackingTest, getUnderlyingObjectsCycle) {
+  auto M = parseModule(R"(
+  define void @test() {
+  entry:
+    br label %bb1
+
+  bb1:
+    %a = phi i32* [ %r, %bb1 ]
+    %0 = getelementptr i32, i32* %a, i32 1
+    %1 = getelementptr i32, i32* %0, i32 1
+    %2 = getelementptr i32, i32* %1, i32 1
+    %3 = getelementptr i32, i32* %2, i32 1
+    %4 = getelementptr i32, i32* %3, i32 1
+    %5 = getelementptr i32, i32* %4, i32 1
+    %6 = getelementptr i32, i32* %5, i32 1
+    %7 = getelementptr i32, i32* %6, i32 1
+    %8 = getelementptr i32, i32* %7, i32 1
+    %9 = getelementptr i32, i32* %8, i32 1
+    %r = getelementptr i32, i32* %9, i32 1
+    br label %bb1
+ 
+  })");
+  Function *F = M->getFunction("test");
+  Instruction *I = &findInstructionByName(F, "r");
+  SmallVector<const Value *, 10> Objects;
+  getUnderlyingObjects(I, Objects);
+  EXPECT_TRUE(Objects.empty());
+}
+
 struct FindAllocaForValueTestParams {
   const char *IR;
   bool AnyOffsetResult;
   bool ZeroOffsetResult;
 };
 
 class FindAllocaForValueTest
     : public ValueTrackingTest,