[ValueTracking] Teach isKnownNonZero about monotonically increasing PHIs

[jmolloy]

Summary

If a PHI starts at a non-negative constant, monotonically increases (only adds of a constant are supported at the moment) and that add does not wrap, then the PHI is known never to be zero.

[jmolloy]

Hi David, Hal,

Do either of you have any comments on this?

Cheers,

James

[reames]

A couple of meta comments:

• This is duplicating logic in SCEV. I think that's okay in this case, but we don't want to take that to the extreme.
• Adding the analogous case isKnownNonNegative (aka, using it to set the sign bit in computeKnownBits) would be a really good idea. An increasing induction variable starting at zero is pretty much the ideal canonical induction variable and we should exploit that.

lib/Analysis/ValueTracking.cpp

1911

I find the Op1 vs Op0 naming confusing. Given this is inherently zero based indexing, mind either using that in the Op names or picking non-index based ones?

1916

Might be time to introduce a isNonNegative on ConstantInt? Could be another patch.

1919

Given you're starting from zero, I think you only need the NSW check. Given INT_MAX is always less than UINT_MAX, I believe the former implies the later in this case. (But we might not yet have proved it.)

[jmolloy]

Hi Philip,

Thanks very much for the review!

I've addressed your comments, and spent some time to convert the test into one that can run through InstSimplify.

Cheers,

James

[jmolloy]

Adding the analogous case isKnownNonNegative (aka, using it to set the sign bit in computeKnownBits) would be a really good idea. An increasing induction variable starting at zero is pretty much the ideal canonical induction variable and we should exploit that.

It looks like this should already be handled in computeKnownBits (ValueTracking.cpp:1277).

[reames]

LGTM

[jmolloy]

Thanks Philip, r248796

lib/Analysis/ValueTracking.cpp

if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) &&
       return true;
   }
   // (C ? X : Y) != 0 if X != 0 and Y != 0.
   else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
     if (isKnownNonZero(SI->getTrueValue(), DL, Depth, Q) &&
         isKnownNonZero(SI->getFalseValue(), DL, Depth, Q))
       return true;
   }
+  // PHI
+  else if (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 ((match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
+               match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
+              !X->isNegative())
+            return true;
+        }
+      }
+    }
+  }
 
   if (!BitWidth) return false;
   APInt KnownZero(BitWidth, 0);
   APInt KnownOne(BitWidth, 0);
   computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
   return KnownOne != 0;
 }
 

test/Analysis/ValueTracking/monotonic-phi.ll

+; RUN: opt -instsimplify -S < %s | FileCheck %s
+
+; CHECK-LABEL: @test1
+define i1 @test1(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %entry ], [ %next, %loop ]
+  %next = add nsw 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
+  ; CHECK: ret i1 false
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @test2
+define i1 @test2(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %entry ], [ %next, %loop ]
+  %next = add 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
+  ; CHECK-NOT: ret i1 false
+  ret i1 %cmp
+}
+
+; CHECK-LABEL: @test3
+define i1 @test3(i8 %p, i8* %pq, i8 %n, i8 %r) {
+entry:
+  br label %loop
+loop:
+  %A = phi i8 [ 1, %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
+  ; CHECK: ret i1 false
+  ret i1 %cmp
+}