[ValueTracking] Handle increasing mul recurrence in isKnownNonZero()

[jaykang10]

Summary

Detect a recurrence that monotonically increases with mul.

[nikic]

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

[jaykang10]

In D99069#2641038, @nikic wrote:

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

Ah! Thanks for letting me know. I did not know that. Let me try.

[jaykang10]

Use matchSimpleRecurrence

[jaykang10]

In D99069#2641050, @jaykang10 wrote:

In D99069#2641038, @nikic wrote:

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

Ah! Thanks for letting me know. I did not know that. Let me try.

@nikic I have updated the patch with matchSimpleRecurrence. Please check it.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2452–2453

I think the matchSimpleRecurrence() check should be higher, e.g. PN->getNumIncomingValues() == 2 is already part of it.

2453

I'd rename R/L to Start and Step.

2460

Why does this exclude C = 1? {1,*,2}<nuw> is still non-zero. The one value is important for inequality, but here we're checking for non-zero.

2463

Again, this isOne() check looks unnecessary to me.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll

91

Why is this or needed?

109

Why does this return false? Isn't this supposed to be a negative test case, due to lack of nuw/nsw?

[jaykang10]

llvm/lib/Analysis/ValueTracking.cpp

2452–2453

Yep, you are right. I will move it up.

2453

Yep, I will rename them.

2460

You are right!!! We are checking non-zero. I will update it.

2463

Yep, I will update it.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll

91

We do not need it. I will remove it.

109

Yep, it is negative test case due to lack of nuw/nsw. It could be better to check CHECK: ret i1 %cmp. I will update it.

[jaykang10]

Following comments of @nikic, updated code.

[nikic]

This looks good to me, but I think needs a couple more tests:

• Positive test for nuw instead of nsw.
• Negative test for zero start value.
• Negative test for negative multiply. (We can't really test zero multiply, as it will get folded away.)
• Negative test for negative start value -- alternatively, you can slightly extend this patch and split the start value check between add and mul: Add requires strictly positive start, but for mul non-zero is sufficient, I believe.

llvm/lib/Analysis/ValueTracking.cpp

2454

Style suggestion: I would write this using m_APInt matchers, which allows you to avoid some of the nesting:

Value *Start, *Step;
const APInt *StartC, *StepC;
if (Q.IIQ.UseInstrInfo && matchSimpleRecurrence(PN, BO, Start, Step) &&
    match(Start, m_APInt(StartC)) && match(Step, m_APInt(StepC)) &&
    StartC->isStrictlyPositive()) {
  ...
}

llvm/test/Analysis/ValueTracking/monotonic-phi.ll

109

Ah, I guess I misread a CHECK-NOT as CHECK here? I've regenerated the check lines for this test in https://github.com/llvm/llvm-project/commit/b7aae9fab14540ad3b4ccda8a5f3a7284f404e63, so you can generate the expected output using llvm/utils/update_test_checks.py.

[jaykang10]

In D99069#2642605, @nikic wrote:

This looks good to me, but I think needs a couple more tests:

• Positive test for nuw instead of nsw.
• Negative test for zero start value.
• Negative test for negative multiply. (We can't really test zero multiply, as it will get folded away.)
• Negative test for negative start value -- alternatively, you can slightly extend this patch and split the start value check between add and mul: Add requires strictly positive start, but for mul non-zero is sufficient, I believe.

Yep, let me add more tests.

[jaykang10]

llvm/lib/Analysis/ValueTracking.cpp

2454

Yep, it looks better. I will update it.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll

109

Yep, I will use the script after adding tests.

[jaykang10]

Added more tests

[nikic]

LGTM

[jaykang10]

In D99069#2645965, @nikic wrote:

LGTM

Thanks @nikic If possible, can you also review https://reviews.llvm.org/D98422 please? I think it could also be ready to merge.

llvm/lib/Analysis/ValueTracking.cpp

bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth,
   else if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
     if (isKnownNonZero(SI->getTrueValue(), DemandedElts, Depth, Q) &&
         isKnownNonZero(SI->getFalseValue(), DemandedElts, Depth, Q))
       return true;
   }
   // PHI
   else if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     // Try and detect a recurrence that monotonically increases from a
     // starting value, as these are common as induction variables.
-    if (PN->getNumIncomingValues() == 2) {
-      Value *Start = PN->getIncomingValue(0);
-      Value *Induction = PN->getIncomingValue(1);
-      if (isa<ConstantInt>(Induction) && !isa<ConstantInt>(Start))
-        std::swap(Start, Induction);
-      if (ConstantInt *C = dyn_cast<ConstantInt>(Start)) {
-        if (!C->isZero() && !C->isNegative()) {
-          ConstantInt *X;
-          if (Q.IIQ.UseInstrInfo &&
-              (match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
-               match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
-              !X->isNegative())
-            return true;
-        }
-      }
-    }
+    BinaryOperator *BO = nullptr;
+    Value *Start = nullptr, *Step = nullptr;
+    const APInt *StartC, *StepC;
+    if (Q.IIQ.UseInstrInfo && matchSimpleRecurrence(PN, BO, Start, Step) &&
+        match(Start, m_APInt(StartC)) && match(Step, m_APInt(StepC))) {
+      if (BO->getOpcode() == Instruction::Add &&
+          (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+          StartC->isStrictlyPositive() && !StepC->isNegative())
+        return true;
+      if (BO->getOpcode() == Instruction::Mul &&
+          (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+          !StartC->isNullValue() && StepC->isStrictlyPositive())
     // Check if all incoming values are non-zero using recursion.
     Query RecQ = Q;
     unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
     return llvm::all_of(PN->operands(), [&](const Use &U) {
       if (U.get() == PN)
         return true;
       RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
       return isKnownNonZero(U.get(), DemandedElts, NewDepth, RecQ);

llvm/test/Analysis/ValueTracking/monotonic-phi.ll

loop:
   %next = add nuw i8 %A, 1
   %cmp1 = icmp eq i8 %A, %n
   br i1 %cmp1, label %exit, label %loop
 exit:
   %add = or i8 %A, %r
   %cmp = icmp eq i8 %add, 0
   ret i1 %cmp
 }
+
+define i1 @test4(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = add nuw i8 [[A]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[A]], [[R:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[ADD]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 0, %entry ], [ %next, %loop ]
+  %next = add nuw i8 %A, 1
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %add = or i8 %A, %r
+  %cmp = icmp eq i8 %add, 0
+  ret i1 %cmp
+}
+
+define i1 @test5(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ -2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = add nuw i8 [[A]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[A]], [[R:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[ADD]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ -2, %entry ], [ %next, %loop ]
+  %next = add nuw i8 %A, 1
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %add = or i8 %A, %r
+  %cmp = icmp eq i8 %add, 0
+  ret i1 %cmp
+}
+
+define i1 @test6(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul nsw i8 [[A]], 2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul nsw i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}
+
+define i1 @test7(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul i8 [[A]], 2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}
+
+define i1 @test8(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul nuw i8 [[A]], 2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul nuw i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}
+
+define i1 @test9(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul nuw i8 [[A]], 2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 0, %entry ], [ %next, %loop ]
+  %next = mul nuw i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}
+
+define i1 @test10(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul nuw i8 [[A]], -2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
+  %next = mul nuw i8 %A, -2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}
+
+define i1 @test11(i8 %p, i8* %pq, i8 %n, i8 %r) {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[A:%.*]] = phi i8 [ -2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[NEXT]] = mul nuw i8 [[A]], 2
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ -2, %entry ], [ %next, %loop ]
+  %next = mul nuw i8 %A, 2
+  %cmp1 = icmp eq i8 %A, %n
+  br i1 %cmp1, label %exit, label %loop
+exit:
+  %cmp = icmp eq i8 %A, 0
+  ret i1 %cmp
+}