Index: llvm/include/llvm/Analysis/ValueTracking.h
===================================================================
--- llvm/include/llvm/Analysis/ValueTracking.h
+++ llvm/include/llvm/Analysis/ValueTracking.h
@@ -764,6 +764,16 @@
   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.
Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1987,6 +1987,12 @@
   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;
 }
 
@@ -2837,6 +2843,12 @@
   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;
 }
 
Index: llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll
+++ llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll
@@ -23,17 +23,16 @@
 ; 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
@@ -41,7 +40,7 @@
 ; 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]] ]
Index: llvm/test/Transforms/InstCombine/recurrence.ll
===================================================================
--- llvm/test/Transforms/InstCombine/recurrence.ll
+++ llvm/test/Transforms/InstCombine/recurrence.ll
@@ -6,9 +6,8 @@
 ; 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:
@@ -27,9 +26,8 @@
 ; 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:
@@ -47,9 +45,8 @@
 ; 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:
@@ -89,9 +86,8 @@
 ; 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:
@@ -110,9 +106,8 @@
 ; 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:
@@ -130,9 +125,8 @@
 ; 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: