Index: lib/Analysis/ScalarEvolutionExpander.cpp
===================================================================
--- lib/Analysis/ScalarEvolutionExpander.cpp
+++ lib/Analysis/ScalarEvolutionExpander.cpp
@@ -2074,6 +2074,8 @@
     // the user code since it can be lowered into a right shift.
     if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
       if (SC->getAPInt().isPowerOf2()) {
+        if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, Processed))
+          return true;
         const DataLayout &DL =
             L->getHeader()->getParent()->getParent()->getDataLayout();
         unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
Index: test/Transforms/IndVarSimplify/no-iv-rewrite.ll
===================================================================
--- test/Transforms/IndVarSimplify/no-iv-rewrite.ll
+++ test/Transforms/IndVarSimplify/no-iv-rewrite.ll
@@ -223,19 +223,14 @@
   %halfLim = ashr i32 %limit, 2
   br label %loop
 
-; This test originally checked that the OR instruction was cloned. Now the
-; ScalarEvolution is able to understand the loop evolution and that '%iv' at the
-; end of the loop is an even value. Thus '%val' is computed at the end of the
-; loop and the OR instruction is replaced by an ADD keeping the result
-; equivalent.
+; Test cloning an or, which is not an OverflowBinaryOperator.
 ;
 ; CHECK: sext
 ; CHECK: loop:
 ; CHECK: phi i64
 ; CHECK-NOT: sext
-; CHECK: icmp slt i64
+; CHECK: or i64
 ; CHECK: exit:
-; CHECK: add i64
 loop:
   %iv = phi i32 [ 0, %entry], [ %iv.next, %loop ]
   %t1 = sext i32 %iv to i64
Index: test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
===================================================================
--- test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
+++ test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
@@ -33,22 +33,16 @@
 define i32 @used_loop(i32 %size) minsize {
 ; CHECK-LABEL: @used_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SIZE:%.*]], 31
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[SIZE]], i32 31
-; CHECK-NEXT:    [[UMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[SIZE]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -32
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[SIZE_ADDR_0:%.*]] = phi i32 [ [[SIZE]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_COND]] ]
+; CHECK-NEXT:    [[SIZE_ADDR_0:%.*]] = phi i32 [ [[SIZE:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_COND]] ]
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[SIZE_ADDR_0]], 31
 ; CHECK-NEXT:    [[SUB]] = add i32 [[SIZE_ADDR_0]], -32
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_COND]], label [[WHILE_END:%.*]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[SIZE]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[SIZE_ADDR_0_LCSSA:%.*]] = phi i32 [ [[SIZE_ADDR_0]], [[WHILE_COND]] ]
+; CHECK-NEXT:    ret i32 [[SIZE_ADDR_0_LCSSA]]
 ;
 entry:
   br label %while.cond
@@ -69,15 +63,9 @@
 define i32 @test_signed_while(i32 %S) {
 ; CHECK-LABEL: @test_signed_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[S:%.*]], 31
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[S]], i32 31
-; CHECK-NEXT:    [[SMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[SMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -32
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[S_ADDR_0]], 31
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
 ; CHECK:       while.body:
@@ -85,8 +73,8 @@
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[S]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[S_ADDR_0_LCSSA:%.*]] = phi i32 [ [[S_ADDR_0]], [[WHILE_COND]] ]
+; CHECK-NEXT:    ret i32 [[S_ADDR_0_LCSSA]]
 ;
 entry:
   br label %while.cond
@@ -109,22 +97,16 @@
 define i32 @test_signed_do(i32 %S) {
 ; CHECK-LABEL: @test_signed_do(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 15, [[S:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -16
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -16
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[SMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], -16
 ; CHECK-NEXT:    br label [[DO_BODY:%.*]]
 ; CHECK:       do.body:
-; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[DO_BODY]] ]
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[DO_BODY]] ]
 ; CHECK-NEXT:    [[SUB]] = add nsw i32 [[S_ADDR_0]], -16
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[SUB]], 15
 ; CHECK-NEXT:    br i1 [[CMP]], label [[DO_BODY]], label [[DO_END:%.*]]
 ; CHECK:       do.end:
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[S]], -16
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], [[TMP3]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[DO_BODY]] ]
+; CHECK-NEXT:    ret i32 [[SUB_LCSSA]]
 ;
 entry:
   br label %do.body
@@ -144,15 +126,9 @@
 define i32 @test_unsigned_while(i32 %S) {
 ; CHECK-LABEL: @test_unsigned_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[S:%.*]], 15
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[S]], i32 15
-; CHECK-NEXT:    [[UMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 16
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -16
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[S_ADDR_0]], 15
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
 ; CHECK:       while.body:
@@ -160,8 +136,8 @@
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[S]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[S_ADDR_0_LCSSA:%.*]] = phi i32 [ [[S_ADDR_0]], [[WHILE_COND]] ]
+; CHECK-NEXT:    ret i32 [[S_ADDR_0_LCSSA]]
 ;
 entry:
   br label %while.cond
@@ -184,22 +160,16 @@
 define i32 @test_unsigned_do(i32 %S) {
 ; CHECK-LABEL: @test_unsigned_do(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 15, [[S:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[TMP0]], -16
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -16
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], -16
 ; CHECK-NEXT:    br label [[DO_BODY:%.*]]
 ; CHECK:       do.body:
-; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[DO_BODY]] ]
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[DO_BODY]] ]
 ; CHECK-NEXT:    [[SUB]] = add i32 [[S_ADDR_0]], -16
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[SUB]], 15
 ; CHECK-NEXT:    br i1 [[CMP]], label [[DO_BODY]], label [[DO_END:%.*]]
 ; CHECK:       do.end:
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[S]], -16
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], [[TMP3]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[DO_BODY]] ]
+; CHECK-NEXT:    ret i32 [[SUB_LCSSA]]
 ;
 entry:
   br label %do.body