[SCEV] Ensure that isHighCostExpansion takes into account what is being divided

[dmgreen]

Summary

A SCEV is not low-cost just because you can divide it by a power of 2. We need to also
check what we are dividing to make sure it too is not a high-code expansion. This helps
to not expand the exit value of certain loops, helping not to bloat the code.

The change in no-iv-rewrite.ll is reverting to back before rL194116, and looks a lot like
the other tests in replace-loop-exit-folds.ll.

[dmgreen]

ping

This is targeted at codesize, but I ran the standard set of benchmarks and didn't see any changes that didn't look like noise.

[RKSimon]

lib/Analysis/ScalarEvolutionExpander.cpp

2073–2075

Please update the comment

[sanjoy]

The change itself looks fine to me, but I'm a bit worried about the test changes. Is it possible that the tests were checking certain the correctness for certain expressions that we no longer check because these happen to be expensive? If that's the case maybe we should add a debug flag that disregards the "is expensive expansion" check to make sure the the same code paths remain tested?

Can you also add a specific test for this change in behavior? Even if it is incidentally tested by the other tests, it would be nicer to have a dedicated test.

[dmgreen]

Is it possible that the tests were checking the correctness for certain expressions that we no longer check because these happen to be expensive?

All the tests in replace-loop-exit-folds.ll are added for this patch. It's showing the changes produced by this patch, but the left hand files are not in-tree yet (it would have been clearer if I would have mentioned that). Most of the tests are a loop like this, with S being signed or unsigned, and with a while or a do loop. They were originally out of D52508 (but that doesn't fix most of the cases).

while(S >= 32) {
    S -= 32;
    something();
};
return S;

no-iv-rewrite.ll is returning back to what it was before rL194116, so is now testing the original point of the test again. The full diff for before and after is much like the other newly added tests (i.e. now a lot smaller):

 define i64 @cloneOr(i32 %limit, i64* %base) #0 {
 entry:
   %halfLim = ashr i32 %limit, 2
   %0 = sext i32 %halfLim to i64
-  %1 = icmp sgt i32 %halfLim, 2
-  %smax = select i1 %1, i32 %halfLim, i32 2
-  %2 = add i32 %smax, -1
-  %3 = zext i32 %2 to i64
-  %4 = lshr i64 %3, 1
-  %5 = shl i64 %4, 1
   br label %loop

 loop:                                             ; preds = %loop, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
   %adr = getelementptr i64, i64* %base, i64 %indvars.iv
   %val = load i64, i64* %adr
+  %1 = or i64 %indvars.iv, 1
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
   %cmp = icmp slt i64 %indvars.iv.next, %0
   br i1 %cmp, label %loop, label %exit

 exit:                                             ; preds = %loop
   %val.lcssa = phi i64 [ %val, %loop ]
-  %6 = add i64 %5, 1
-  %result = and i64 %val.lcssa, %6
+  %t3.lcssa = phi i64 [ %1, %loop ]
+  %result = and i64 %val.lcssa, %t3.lcssa
   ret i64 %result
 }

[dmgreen]

Altered comment, and just use indvars for the tests (not instcombine/loop-delete).

[sanjoy]

Thanks for the explanation!

[dmgreen]

Thanks

lib/Analysis/ScalarEvolutionExpander.cpp

return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
                                      L, At, Processed);
   }
 
   if (!Processed.insert(S).second)
     return false;
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // If the divisor is a power of two and the SCEV type fits in a native
-    // integer, consider the division cheap irrespective of whether it occurs in
-    // the user code since it can be lowered into a right shift.
+    // integer (and the LHS not expensive), consider the division cheap
+    // irrespective of whether it occurs in 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();
         return DL.isIllegalInteger(Width);
       }
 
     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
     // HowManyLessThans produced to compute a precise expression, rather than a

test/Transforms/IndVarSimplify/no-iv-rewrite.ll

 }
 
 define i64 @cloneOr(i32 %limit, i64* %base) nounwind {
 entry:
   ; ensure that the loop can't overflow
   %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
   %adr = getelementptr i64, i64* %base, i64 %t1
   %val = load i64, i64* %adr
   %t2 = or i32 %iv, 1
   %t3 = sext i32 %t2 to i64
   %iv.next = add i32 %iv, 2

test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll

 while.end:                                        ; preds = %while.cond
   %size.lcssa = phi i32 [ %size.addr.0, %while.cond ]
   ret i32 %size.lcssa
 }
 
 define i32 @used_loop(i32 %size) minsize {
 ; CHECK-LABEL: @used_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[SIZE:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[TMP0]], -32
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -32
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[SIZE]], [[UMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP3]], 5
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 [[TMP4]], 5
 ; 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:    [[TMP6:%.*]] = sub i32 [[SIZE]], [[TMP5]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; CHECK-NEXT:    [[SIZE_LCSSA:%.*]] = phi i32 [ [[SIZE_ADDR_0]], [[WHILE_COND]] ]
+; CHECK-NEXT:    ret i32 [[SIZE_LCSSA]]
 ;
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
   %size.addr.0 = phi i32 [ %size, %entry ], [ %sub, %while.cond ]
   tail call void @call()
   %cmp = icmp ugt i32 %size.addr.0, 31
   %sub = add i32 %size.addr.0, -32
   br i1 %cmp, label %while.cond, label %while.end
 
 while.end:                                        ; preds = %while.cond
   %size.lcssa = phi i32 [ %size.addr.0, %while.cond ]
   ret i32 %size.lcssa
 }
 
 
 define i32 @test_signed_while(i32 %S) {
 ; CHECK-LABEL: @test_signed_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[S:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -32
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -32
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[S]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP3]], 5
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 [[TMP4]], 5
 ; 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:
 ; CHECK-NEXT:    [[SUB]] = add nsw i32 [[S_ADDR_0]], -32
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[S]], [[TMP5]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; 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
 
 while.cond:                                       ; preds = %while.body, %entry
   %S.addr.0 = phi i32 [ %S, %entry ], [ %sub, %while.body ]
   %cmp = icmp sgt i32 %S.addr.0, 31
   br i1 %cmp, label %while.body, label %while.end
 
 while.body:                                       ; preds = %while.cond
   %sub = add nsw i32 %S.addr.0, -32
   tail call void @call()
   br label %while.cond
 
 while.end:                                        ; preds = %while.cond
   %S.addr.0.lcssa = phi i32 [ %S.addr.0, %while.cond ]
   ret i32 %S.addr.0.lcssa
 }
 
 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 [[S]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 [[TMP2]], 4
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 [[TMP3]], 4
 ; 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:    [[TMP5:%.*]] = add i32 [[S]], -16
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[TMP5]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[DO_BODY]] ]
+; CHECK-NEXT:    ret i32 [[SUB_LCSSA]]
 ;
 entry:
   br label %do.body
 
 do.body:                                          ; preds = %do.body, %entry
   %S.addr.0 = phi i32 [ %S, %entry ], [ %sub, %do.body ]
   %sub = add nsw i32 %S.addr.0, -16
   tail call void @call()
   %cmp = icmp sgt i32 %sub, 15
   br i1 %cmp, label %do.body, label %do.end
 
 do.end:                                           ; preds = %do.body
   %sub.lcssa = phi i32 [ %sub, %do.body ]
   ret i32 %sub.lcssa
 }
 
 define i32 @test_unsigned_while(i32 %S) {
 ; CHECK-LABEL: @test_unsigned_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[S:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[TMP0]], -16
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -16
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[S]], [[UMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 16
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP3]], 4
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 [[TMP4]], 4
 ; 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:
 ; CHECK-NEXT:    [[SUB]] = add i32 [[S_ADDR_0]], -16
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[S]], [[TMP5]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; 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
 
 while.cond:                                       ; preds = %while.body, %entry
   %S.addr.0 = phi i32 [ %S, %entry ], [ %sub, %while.body ]
   %cmp = icmp ugt i32 %S.addr.0, 15
   br i1 %cmp, label %while.body, label %while.end
 
 while.body:                                       ; preds = %while.cond
   %sub = add i32 %S.addr.0, -16
   tail call void @call()
   br label %while.cond
 
 while.end:                                        ; preds = %while.cond
   %S.addr.0.lcssa = phi i32 [ %S.addr.0, %while.cond ]
   ret i32 %S.addr.0.lcssa
 }
 
 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 [[S]], [[UMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 [[TMP2]], 4
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 [[TMP3]], 4
 ; 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:    [[TMP5:%.*]] = add i32 [[S]], -16
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[TMP5]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; CHECK-NEXT:    [[SUB_LCSSA:%.*]] = phi i32 [ [[SUB]], [[DO_BODY]] ]
+; CHECK-NEXT:    ret i32 [[SUB_LCSSA]]
 ;
 entry:
   br label %do.body
 
 do.body:                                          ; preds = %do.body, %entry
   %S.addr.0 = phi i32 [ %S, %entry ], [ %sub, %do.body ]
   %sub = add i32 %S.addr.0, -16
   tail call void @call()