[instcombine] Collapse trivial or/and recurrences

[reames]

Summary

If we have a recurrence of the form <Start, Or, Step> or <Start, And, Step> we know that the value taken by the recurrence stabilizes on the first iteration (provided step is loop invariant). We can exploit that fact to remove the loop carried dependence in the recurrence.

The motivation is mostly consistency and demonstrating some recently added infrastructure for identifying recurrences, but as shown in the test change, we do seem to see them outside contrived examples as well.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1991

DT is required in InstCombine. You should also be able to use DT directly without going through SimplifyQuery.

[reames]

address review comment

[lebedev.ri]

This looks reasonable to me, but is this falling into the traditional pitfail of not dealing with all of the commutative variants, etc?
What happens if BinaryOperator's both operands are recurrences, and the first one isn't the one we can deal with? (DT.dominates(Step, PN))

[reames]

In D97578#2600668, @lebedev.ri wrote:

This looks reasonable to me, but is this falling into the traditional pitfail of not dealing with all of the commutative variants, etc?
What happens if BinaryOperator's both operands are recurrences, and the first one isn't the one we can deal with? (DT.dominates(Step, PN))

Honestly, I wouldn't bother to handle this case. It really seems like perfection being the enemy of the good.

[reames]

poke

[lebedev.ri]

LG, please commit and and or parts as two separate patches.

[reames]

Landed in two parts, see comments on review for links.

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// results in some odd recurrence structures.  Callers may wish to filter
   /// out recurrences where the phi is not the LHS of the returned operator.
   ///
   /// NOTE: This is intentional simple.  If you want the ability to analyze
   /// non-trivial loop conditons, see ScalarEvolution instead.
   bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
                              Value *&Start, Value *&Step);
 
+  /// Analogous to the above, but starting from the binary operator
+  inline bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
+                                    Value *&Start, Value *&Step) {
+    BinaryOperator *BO = nullptr;
+    P = dyn_cast<PHINode>(I->getOperand(0));
+    if (!P)
+      P = dyn_cast<PHINode>(I->getOperand(1));
+    return P && matchSimpleRecurrence(P, BO, Start, Step) && BO == I;
+  }
+
   /// Return true if RHS is known to be implied true by LHS.  Return false if
   /// RHS is known to be implied false by LHS.  Otherwise, return None if no
   /// implication can be made.
   /// A & B must be i1 (boolean) values or a vector of such values. Note that
   /// the truth table for implication is the same as <=u on i1 values (but not
   /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(&I, m_c_And(m_OneUse(m_AShr(
     Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
     return SelectInst::Create(NewICmpInst, X, ConstantInt::getNullValue(Ty));
   }
 
   // (~x) & y  -->  ~(x | (~y))  iff that gets rid of inversions
   if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
+  // An and recurrence w/loop invariant step is equivelent to (and start, step)
+  PHINode *PN = nullptr;
+  Value *Start = nullptr, *Step = nullptr;
+  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
+    return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
+
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::matchBSwapOrBitReverse(Instruction &I,
                                                       bool MatchBSwaps,
                                                       bool MatchBitReversals) {
   SmallVector<Instruction *, 4> Insts;
   if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
       return BinaryOperator::CreateAnd(NotNullA, NotNullB);
     }
   }
 
   // (~x) | y  -->  ~(x & (~y))  iff that gets rid of inversions
   if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
+  // An or recurrence w/loop invariant step is equivelent to (or start, step)
+  PHINode *PN = nullptr;
+  Value *Start = nullptr, *Step = nullptr;
+  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
+    return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
+
   return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);

llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll

 @e = dso_local global i32 0, align 4
 
 define dso_local i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I6:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[I24:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[D_PROMOTED9:%.*]] = load i32, i32* @d, align 4
-; CHECK-NEXT:    br label [[BB13_PREHEADER:%.*]]
-; CHECK:       bb13.preheader:
-; CHECK-NEXT:    [[I8_LCSSA10:%.*]] = phi i32 [ [[D_PROMOTED9]], [[BB:%.*]] ], [ [[I8:%.*]], [[BB19_PREHEADER:%.*]] ]
-; CHECK-NEXT:    [[I8]] = and i32 [[I8_LCSSA10]], [[I6]]
-; CHECK-NEXT:    [[I21:%.*]] = icmp eq i32 [[I8]], 0
-; CHECK-NEXT:    br i1 [[I21]], label [[BB13_PREHEADER_BB27_THREAD_SPLIT_CRIT_EDGE:%.*]], label [[BB19_PREHEADER]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[D_PROMOTED9]], [[I6]]
+; CHECK-NEXT:    [[I21:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 [[I21]], label [[BB13_PREHEADER_BB27_THREAD_SPLIT_CRIT_EDGE:%.*]], label [[BB19_PREHEADER:%.*]]
 ; CHECK:       bb19.preheader:
-; CHECK-NEXT:    [[I26:%.*]] = urem i32 [[I24]], [[I8]]
+; CHECK-NEXT:    [[I26:%.*]] = urem i32 [[I24]], [[TMP0]]
 ; CHECK-NEXT:    store i32 [[I26]], i32* @e, align 4
 ; CHECK-NEXT:    [[I30_NOT:%.*]] = icmp eq i32 [[I26]], 0
-; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB13_PREHEADER]]
+; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB1]]
 ; CHECK:       bb13.preheader.bb27.thread.split_crit_edge:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
 ; CHECK-NEXT:    store i32 0, i32* @d, align 4
 ; CHECK-NEXT:    store i32 0, i32* @c, align 4
 ; CHECK-NEXT:    br label [[BB32:%.*]]
 ; CHECK:       bb32.loopexit:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
-; CHECK-NEXT:    store i32 [[I8]], i32* @d, align 4
+; CHECK-NEXT:    store i32 [[TMP0]], i32* @d, align 4
 ; CHECK-NEXT:    br label [[BB32]]
 ; CHECK:       bb32:
 ; CHECK-NEXT:    [[C_SINK:%.*]] = phi i32* [ @c, [[BB32_LOOPEXIT]] ], [ @e, [[BB13_PREHEADER_BB27_THREAD_SPLIT_CRIT_EDGE]] ]
 ; CHECK-NEXT:    store i32 0, i32* [[C_SINK]], align 4
 ; CHECK-NEXT:    ret i32 0
 ;
 bb:
   %i = alloca i32, align 4

llvm/test/Transforms/InstCombine/recurrence.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define i64 @test_or(i64 %a) {
 ; CHECK-LABEL: @test_or(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = or i64 [[IV]], 15
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[A:%.*]], 15
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = or i64 %iv, 15
   tail call void @use(i64 %iv.next)
   br label %loop
 }
 
 
 define i64 @test_or2(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_or2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = or i64 [[IV]], [[B:%.*]]
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = or i64 %iv, %b
   tail call void @use(i64 %iv.next)
   br label %loop
 }
 
 define i64 @test_or3(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_or3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = or i64 [[IV]], [[B:%.*]]
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = or i64 %b, %iv
loop:                                             ; preds = %loop, %entry
   br label %loop
 }
 
 define i64 @test_and(i64 %a) {
 ; CHECK-LABEL: @test_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = and i64 [[IV]], 15
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[A:%.*]], 15
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = and i64 %iv, 15
   tail call void @use(i64 %iv.next)
   br label %loop
 }
 
 
 define i64 @test_and2(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_and2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = and i64 [[IV]], [[B:%.*]]
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = and i64 %iv, %b
   tail call void @use(i64 %iv.next)
   br label %loop
 }
 
 define i64 @test_and3(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_and3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = and i64 [[IV]], [[B:%.*]]
-; CHECK-NEXT:    tail call void @use(i64 [[IV_NEXT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    tail call void @use(i64 [[TMP0]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop, %entry
   %iv = phi i64 [ %a, %entry ], [ %iv.next, %loop ]
   %iv.next = and i64 %b, %iv