[ValueTracking] Improve known bits detection for PHI recurrences

[jmolloy]

Summary

Proving many facts about PHIs in ValueTracking is difficult due to its context-free nature (no caching). However, it is possible to prove that a PHI is non-negative (MSB is known zero) in many real-world situations.

Often, induction variables are very simple. We already have some support for looking at trivial induction variables (simple adds for example) in order to prove low-order bits are always zero due to stride.

This patch introduces more analysis for PHIs. Specifically, if a two-entry PHI has a non-negative constant integer in one operand it will try and trace the other operand through certain instructions until it hopefully finds the PHI again.

The set of instructions that will be recursed through is deliberately small - add, mul and select. On top of this small set, we will only ever follow a linear chain (an add/mul with a non-negative constant integer as the RHS operand). Because we only ever follow a linear chain of simple instructions the search space can never expand too much which also allows us to set a non-tiny search limit.

[sanjoy]

lib/Analysis/ValueTracking.cpp

1461

Minor and subject to your discretion, but summarizing here what you've matched so far may be helpful for reading:

P = phi(NewL `op` P, R)

I'm also not sold on the name NewL -- what does "New" signify?

1472

Minor, but for multiplications I think we can actually use KnownZero2.countTrailingOnes() here (sometimes better and never worse than the min) -- do you mind adding a FIXME / TODO?

Edit: I noticed that this change doesn't really change this bit of code in a semantic way, so adding the TODO / FIXME isn't necessary.

1479

Since you're using the pattern few times here, I think it'll be cleaner if you add an m_NonNegative to PatterMatch.h and use that here and later (there already exist matchers like m_Power2 etc.).

1496

Use m_Value() (without the Dummy) since you want to ignore whatever you matched.

[mcrosier]

Feel free to add me back, if you decide to pursue this further, James.

lib/Analysis/ValueTracking.cpp

if (P->getNumIncomingValues() == 2) {
         // will have low zero bits.
         if (Opcode == Instruction::Add ||
             Opcode == Instruction::Sub ||
             Opcode == Instruction::And ||
             Opcode == Instruction::Or ||
             Opcode == Instruction::Mul) {
           Value *LL = LU->getOperand(0);
           Value *LR = LU->getOperand(1);
+          Value *NewL = nullptr;
           // Find a recurrence.
           if (LL == I)
-            L = LR;
+            NewL = LR;
           else if (LR == I)
-            L = LL;
-          else
-            break;
+            NewL = LL;
+          if (NewL) {
             // Ok, we have a PHI of the form L op= R. Check for low
             // zero bits.
             computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
 
             // We need to take the minimum number of known bits
             APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
-          computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q);
+            computeKnownBits(NewL, KnownZero3, KnownOne3, DL, Depth + 1, Q);
 
-          KnownZero = APInt::getLowBitsSet(BitWidth,
-                                           std::min(KnownZero2.countTrailingOnes(),
-                                                    KnownZero3.countTrailingOnes()));
+            KnownZero = APInt::getLowBitsSet(
+                BitWidth, std::min(KnownZero2.countTrailingOnes(),
+          }
+        }
+        // Proving non-negativity is a useful fact. If the base is non-negative,
+        // look through a single-parent chain as far as possible to try and
+        // prove that this value is always non-negative.
+        if (isa<ConstantInt>(R) && !cast<ConstantInt>(R)->isNegative()) {
+          Value *V = L;
+          unsigned Countdown = 32;
+          while (Countdown--) {
+            Value *NewV, *Dummy;
+            ConstantInt *CI;
+            if (V == I) {
+              // We made it back to the PHI node, so this PHI is non-negative.
+              KnownZero.setBit(KnownZero.getBitWidth() - 1);
+              break;
+            }
+            if ((match(V, m_NSWAdd(m_Value(NewV), m_ConstantInt(CI))) ||
+                 match(V, m_NSWMul(m_Value(NewV), m_ConstantInt(CI)))) &&
+                !CI->isNegative()) {
+              V = NewV;
+              continue;
+            }
+            if ((match(V, m_Select(m_Value(Dummy), m_ConstantInt(CI),
+                                   m_Value(NewV))) ||
+                 match(V, m_Select(m_Value(Dummy), m_Value(NewV),
+                                   m_ConstantInt(CI)))) &&
+                !CI->isNegative()) {
+              V = NewV;
+              continue;
+            }
             break;
           }
         }
+        break;
+      }
     }
 
     // Unreachable blocks may have zero-operand PHI nodes.
     if (P->getNumIncomingValues() == 0)
       break;
 
     // Otherwise take the unions of the known bit sets of the operands,
     // taking conservative care to avoid excessive recursion.

test/Analysis/ValueTracking/knownbits-phi.ll

+; RUN: opt -S -instsimplify < %s | FileCheck %s
+
+; CHECK-LABEL: @alwayspositive_loop1
+define i32 @alwayspositive_loop1(i32 %a) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = add nsw i32 %phi, 2
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop2
+define i32 @alwayspositive_loop2(i32 %a, i1 %cond) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = select i1 %cond, i32 2, i32 %phi
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop2_swapped
+define i32 @alwayspositive_loop2_swapped(i32 %a, i1 %cond) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = select i1 %cond, i32 %phi, i32 2
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}
+
+; CHECK-LABEL: @alwayspositive_loop_mul
+define i32 @alwayspositive_loop_mul(i32 %a) {
+entry:
+  br label %loop
+  
+loop:
+  %phi = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %c = mul nsw i32 %phi, 3
+  %b = icmp sgt i32 %c, 52
+  %inc = add nsw i32 %c, 1
+  br i1 %b, label %exit, label %loop
+
+exit:
+; CHECK: ret i32 0
+  %d = lshr i32 %c, 31
+  ret i32 %d
+}