[ValueTracking] Fix recurrence detection to check both PHI operands.

[fhahn]

Summary

Currently we fail to compute known bits for recurrences where the
first incoming value is the start value of the recurrence.

Instead of exiting the loop when the first incoming value is not
the step of the recurrence, continue to check the second incoming
value.

The original code uses a loop to handle both cases, but incorrectly
exits instead of continuing.

[lebedev.ri]

llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll

1

Please use utils/update_test_checks.py and precommit.

[fhahn]

Update test after pre-committing it.

[fhahn]

llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll

1

Done.
I am a bit torn when it come sousing update_test_checks.py here, as checking everything potentially makes the test slightly more verbose and brittle than necessary. But it is quite convenient.

[lebedev.ri]

I know nothing about this code, but the test change appears correct,
and matches what already happens in the second test case.

llvm/lib/Analysis/ValueTracking.cpp

1376

continue; // Check other incoming value

llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll

40

I think this should/can be unconditional branch to for.cond11?
It branches on the same condition that brought us here.
Does the fold still happen then?

[fhahn]

Add comment to continue.

[fhahn]

llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll

40

If this branch is unconditional, we get the ult through some other code path (I did not track it down though). My guess is that we evaluate things in a different order.

[lebedev.ri]

Still no clue about this code, but looks plausible.

llvm/lib/Analysis/ValueTracking.cpp

if (P->getNumIncomingValues() == 2) {
           Value *LL = LU->getOperand(0);
           Value *LR = LU->getOperand(1);
           // Find a recurrence.
           if (LL == I)
             L = LR;
           else if (LR == I)
             L = LL;
           else
-            break;
+            continue; // Check for recurrence with L and R flipped.
           // Ok, we have a PHI of the form L op= R. Check for low
           // zero bits.
           computeKnownBits(R, Known2, Depth + 1, Q);
 
           // We need to take the minimum number of known bits
           KnownBits Known3(Known);
           computeKnownBits(L, Known3, Depth + 1, Q);
 

llvm/test/Transforms/InstCombine/phi-known-bits-operand-order.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; Check that we can turn the icmp sle into icmp ult, regardless of the
 ; order of the incoming values of the PHI node.
 
 declare i1 @cond()
 
 define void @phi_recurrence_start_first() {
 ; CHECK-LABEL: @phi_recurrence_start_first(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    [[CELL_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[START:%.*]], [[FOR_COND26:%.*]] ]
 ; CHECK-NEXT:    [[COND_V:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND_V]], label [[IF_THEN:%.*]], label [[WHILE_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[START]] = add nuw nsw i32 [[CELL_0]], 1
 ; CHECK-NEXT:    br i1 [[COND_V]], label [[FOR_COND11:%.*]], label [[FOR_COND26]]
 ; CHECK:       for.cond11:
 ; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[START]], [[IF_THEN]] ], [ [[STEP:%.*]], [[FOR_COND11]] ]
-; CHECK-NEXT:    [[CMP13:%.*]] = icmp slt i32 [[I_1]], 100
-; CHECK-NEXT:    [[STEP]] = add nsw i32 [[I_1]], 1
+; CHECK-NEXT:    [[CMP13:%.*]] = icmp ult i32 [[I_1]], 100
+; CHECK-NEXT:    [[STEP]] = add nuw nsw i32 [[I_1]], 1
 ; CHECK-NEXT:    br i1 [[CMP13]], label [[FOR_COND11]], label [[WHILE_END]]
 ; CHECK:       for.cond26:
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %entry, %for.cond26
   %cell.0 = phi i32 [ 0, %entry ], [ %start, %for.cond26 ]
   %cond.v = call i1 @cond()
   br i1 %cond.v, label %if.then, label %while.end
 
 if.then:                                          ; preds = %while.cond
   %start = add nsw i32 %cell.0, 1
   br i1 %cond.v, label %for.cond11, label %for.cond26
 
 for.cond11:                                       ; preds = %for.cond11, %if.then
   %i.1 = phi i32 [ %start, %if.then ], [ %step, %for.cond11 ]
   %cmp13 = icmp sle i32 %i.1, 99
   %step = add nsw i32 %i.1, 1
   br i1 %cmp13, label %for.cond11, label %while.end
 
 for.cond26:                                       ; preds = %if.then