[ValueTracking] Don't let isAddOfNonZero look at adds with a PHI node as input

[craig.topper]

Summary

This is a fix for the test case in PR32314.

Basic Alias Analysis can ask if two nodes are known non-equal after looking through a phi node to find a GEP. isAddOfNonZero saw an add of a constant from the same phi and said that its output couldn't be equal. But Basic Alias Analysis was really asking about the value from the previous loop iteration.

This patch at least makes that case not happen anymore, I'm not sure if there were still other ways this can fail. As was discussed in the bug, it looks like fixing BasicAA would be difficult so this patch seemed like a possible workaround

[hfinkel]

Can we add a mode (e.g. some extra boolean parameter) to ValueTracking to enable this kind of restriction? We could then enable this mode when in BasicAA. I don't want to, in general, disable things here to work around the fact that BasicAA is doing some unsound.

[craig.topper]

I couldn't come up with a bool variable name that I liked so I just taught BasicAA not to call isKnownNonEqual if one of the inputs is a PHI. Instead we'll just compute the known bits separately. I think we should add a helper method to KnownBits to check if two KnownBits structs are known non equal which would simplify the intersection check.

[Farhana]

What is the performance implication of this change-set? Have you done any performance testing? This seems to make the alias analysis very conservative. It is now going to find two non-equal numbers equal very easily.

[craig.topper]

Only one of the benchmarks I ran this through showed any effect on the compiled code. And the one benchmark that changed got slightly faster.

[craig.topper]

Ping

[• dberlin]

In D33136#773589, @Farhana wrote:

What is the performance implication of this change-set? Have you done any performance testing? This seems to make the alias analysis very conservative. It is now going to find two non-equal numbers equal very easily.

Other than rewrite it all, what are you suggesting he do?

[• dberlin]

I'm fine with this.
If we want better performance or better aliasing, we can do the hard work of doing it right.

lib/Analysis/ValueTracking.cpp

bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
   return Known.One != 0;
 }
 
 /// Return true if V2 == V1 + X, where X is known non-zero.
 static bool isAddOfNonZero(const Value *V1, const Value *V2, const Query &Q) {
   const BinaryOperator *BO = dyn_cast<BinaryOperator>(V1);
   if (!BO || BO->getOpcode() != Instruction::Add)
     return false;
+  // If V2 is a PHINode we don't know if its safe to compare them because
+  // because V1 could be using V2 from a different loop iteration.
+  if (isa<PHINode>(V2))
+    return false;
   Value *Op = nullptr;
   if (V2 == BO->getOperand(0))
     Op = BO->getOperand(1);
   else if (V2 == BO->getOperand(1))
     Op = BO->getOperand(0);
   else
     return false;
   return isKnownNonZero(Op, 0, Q);

test/Transforms/GVN/pr32314.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -gvn < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; The load in the loop can not bypass the data from the previous loop. The store above it in the loop aliases.
+define void @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca [3 x i32], align 4
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[P_017:%.*]] = phi i32* [ undef, [[ENTRY]] ], [ [[ARRAYIDX3:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* [[A]], i64 0, i64 [[TMP0]]
+; CHECK-NEXT:    store i32 50, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[P_017]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP1]] to i32
+; CHECK-NEXT:    [[ADD1:%.*]] = add nsw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[ARRAYIDX3]] = getelementptr inbounds [3 x i32], [3 x i32]* [[A]], i64 0, i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i32 60, i32* [[ARRAYIDX3]], align 4
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], 3
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
+;
+entry:
+  %a = alloca [3 x i32], align 4
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
+  %p.017 = phi i32* [ undef, %entry ], [ %arrayidx3, %for.body ]
+  %0 = add nsw i64 %indvars.iv, -1
+  %arrayidx = getelementptr inbounds [3 x i32], [3 x i32]* %a, i64 0, i64 %0
+  store i32 50, i32* %arrayidx, align 4
+  %1 = shl i64 %indvars.iv, 1
+  %2 = load i32, i32* %p.017, align 4
+  %3 = trunc i64 %1 to i32
+  %add1 = add nsw i32 %2, %3
+  %arrayidx3 = getelementptr inbounds [3 x i32], [3 x i32]* %a, i64 0, i64 %indvars.iv
+  store i32 60, i32* %arrayidx3, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 3
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}