Look through invertible recurrences in isKnownNonEqual

[reames]

Summary

This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle.

(Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.)

[reames]

Rebase over test updates following ashr/lshr change

[nikic]

I think you're missing an important precondition here: You need that Step1 == Step2. Otherwise you could have <0,+,2> and <1,+,1>, which have non-equal start values, but are still equal on the second iteration.

Something the implementation does account for, but doesn't appear to be tested, is if the second operand is invertible rather than the first.

llvm/test/Analysis/ValueTracking/known-non-equal.ll

998

This doesn't test what you want it to because %A/%B are unknown. You need to make them non-equal so that the nowrap flags are the *only* thing that prevents the fold.

1134

Same here.

1270

Same here.

1406

Same here.

[nikic]

In D99912#2689731, @nikic wrote:

I think you're missing an important precondition here: You need that Step1 == Step2. Otherwise you could have <0,+,2> and <1,+,1>, which have non-equal start values, but are still equal on the second iteration.

Ah no, getInvertibleOperand() would fail if the steps didn't match. I think your code is correct, it's just missing test coverage for this case.

[reames]

Rebase over requested test changes - thanks btw, good catch.

[reames]

Rebase over a couple added tests to cover cases which caused reviewer confusion. (For good cause.)

[nikic]

LGTM, thanks!

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2609

Guess there isn't really a reason why it should be the same operand on both. We could restrict to the case where it is, or else make getInvertibleOperand not return an operand index, and instead return a pair of value to which the (in)equality relation propagates.

[reames]

llvm/lib/Analysis/ValueTracking.cpp

2609

Oh, duh. Thanks for this comment, I'd been staring at the assertion failures without having this occur to me. Thanks.

I'll probably do the restrictive form first, then generalize in a separate patch.

llvm/lib/Analysis/ValueTracking.cpp

if (Op1->getOperand(1) == Op2->getOperand(1))
       return 0;
     break;
   }
   case Instruction::SExt:
   case Instruction::ZExt:
     if (Op1->getOperand(0)->getType() == Op2->getOperand(0)->getType())
       return 0;
     break;
+  case Instruction::PHI: {
+    const PHINode *PN1 = cast<PHINode>(Op1);
+    const PHINode *PN2 = cast<PHINode>(Op2);
+
+    // If PN1 and PN2 are both recurrences, can we prove the entire recurrences
+    // are a single invertible function of the start values? Note that repeated
+    // application of an invertible function is also invertible
+    BinaryOperator *BO1 = nullptr;
+    Value *Start1 = nullptr, *Step1 = nullptr;
+    BinaryOperator *BO2 = nullptr;
+    Value *Start2 = nullptr, *Step2 = nullptr;
+    if (PN1->getParent() != PN2->getParent() ||
+        !matchSimpleRecurrence(PN1, BO1, Start1, Step1) ||
+        !matchSimpleRecurrence(PN2, BO2, Start2, Step2))
+      break;
+
+    Optional<unsigned> Idx = getInvertibleOperand(cast<Operator>(BO1),
+                                                  cast<Operator>(BO2));
+    if (!Idx || *Idx != 0)
+      break;
+    assert(BO1->getOperand(*Idx) == PN1 && BO2->getOperand(*Idx) == PN2);
+
+    if (PN1->getOperand(0) == BO1) {
+      assert(PN2->getOperand(0) == BO2);
+      return 1;
+    }
+    assert(PN1->getOperand(1) == BO1 && PN2->getOperand(1) == BO2);
+    return 0;
+  }
   }
   return None;
 }
 
 /// Return true if V2 == V1 + X, where X is known non-zero.
 static bool isAddOfNonZero(const Value *V1, const Value *V2, unsigned Depth,
                            const Query &Q) {
   const BinaryOperator *BO = dyn_cast<BinaryOperator>(V1);

llvm/test/Analysis/ValueTracking/known-non-equal.ll

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [%iv.next, %loop], [0, %entry]
   %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
   %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
 ; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
loop:
   %B.iv.next = mul nuw i8 %B.iv, 2
   %cmp = icmp ne i64 %iv.next, 10
   br i1 %cmp, label %loop, label %exit
 exit:
   %res = icmp eq i8 %A.iv, %B.iv
   ret i1 %res
 }
 
 define i1 @recurrence_mul_noflags(i8 %A) {
 ; CHECK-LABEL: @recurrence_mul_noflags(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
loop:
   %B.iv.next = shl nuw i8 %B.iv, 1
   %cmp = icmp ne i64 %iv.next, 10
   br i1 %cmp, label %loop, label %exit
 exit:
   %res = icmp eq i8 %A.iv, %B.iv
   ret i1 %res
 }
 
 define i1 @recurrence_shl_noflags(i8 %A) {
 ; CHECK-LABEL: @recurrence_shl_noflags(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
loop:
   %B.iv.next = lshr exact i8 %B.iv, 1
   %cmp = icmp ne i64 %iv.next, 10
   br i1 %cmp, label %loop, label %exit
 exit:
   %res = icmp eq i8 %A.iv, %B.iv
   ret i1 %res
 }
 
 define i1 @recurrence_lshr_noflags(i8 %A) {
 ; CHECK-LABEL: @recurrence_lshr_noflags(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]

 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
 ; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %B = add i8 %A, 1
   br label %loop
 loop:
   %iv = phi i64 [0, %entry], [%iv.next, %loop]
   %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
   %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
loop:
   %B.iv.next = ashr exact i8 %B.iv, 1
   %cmp = icmp ne i64 %iv.next, 10
   br i1 %cmp, label %loop, label %exit
 exit:
   %res = icmp eq i8 %A.iv, %B.iv
   ret i1 %res
 }
 
 define i1 @recurrence_ashr_noflags(i8 %A) {
 ; CHECK-LABEL: @recurrence_ashr_noflags(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]