From 79c45a39542b9d62811482b9cc96d7f4429f7d15 Mon Sep 17 00:00:00 2001
From: James Molloy <james.molloy@arm.com>
Date: Tue, 29 Sep 2015 14:08:45 +0000
Subject: [PATCH] [ValueTracking] Teach isKnownNonZero about monotonically
 increasing PHIs

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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248796 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ValueTracking.cpp               | 20 ++++++++++++
 test/Analysis/ValueTracking/monotonic-phi.ll | 49 ++++++++++++++++++++++++++++
 2 files changed, 69 insertions(+)
 create mode 100644 test/Analysis/ValueTracking/monotonic-phi.ll

diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 5481e722e53..285c945fc62 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -1904,6 +1904,26 @@ bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
         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);
diff --git a/test/Analysis/ValueTracking/monotonic-phi.ll b/test/Analysis/ValueTracking/monotonic-phi.ll
new file mode 100644
index 00000000000..3204bda49f0
--- /dev/null
+++ b/test/Analysis/ValueTracking/monotonic-phi.ll
@@ -0,0 +1,49 @@
+; 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
+}
-- 
2.11.0