[LoopUnroll] Be more permissive to high-cost loop trip count SCEV's

[lebedev.ri]

Summary

Loop unroll's loop trip count expansion is optionally
guarded by a 'cheap expansion budget' cut-off.
Unlike the loop ind var simplification, here,
if we do unroll the loop, it's usually beneficial,
so it's generally justified to deal with a slightly
more costly loop trip counts.

Alternative to D139858.

[nikic]

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=781eabeb40b8e47e3a46b0b927784e63f0aad9ab&to=c0e5cd413681c1622e6d454bba677cf8847c3db3&stat=instructions:u ThinLTO +0.5% geomean with +2.7% tramp3d-v4

Code-size: https://llvm-compile-time-tracker.com/compare.php?from=781eabeb40b8e47e3a46b0b927784e63f0aad9ab&to=c0e5cd413681c1622e6d454bba677cf8847c3db3&stat=size-text ThinLTO +1.0% geomean with +6.7% tramp3d-v4

I checked, and using a factor of two instead of four only makes a relatively small difference (that is, the code size / compile-time impact is about the same for factor two and four).

Looks like this change has a higher impact than I would have expected. The code size increase might be worthwhile, but it's not possible to say without performance data.

It's possible that D115261 would mitigate this somewhat, by avoiding at least some of the known non-profitable unrolling.

Ultimately this (once again) comes back to our lack of a runtime unrolling cost model :/

[lebedev.ri]

ping

[mkazantsev]

If CT impact is small, fine by me.

[fhahn]

Do you have any perf data on the impact of this change?

[nikic]

In D140698#4057643, @mkazantsev wrote:

If CT impact is small, fine by me.

CT and code size impact is still large: Compile time, Code size

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

if (isa<SCEVCouldNotCompute>(TripCountSC)) {
     return false;
   }
 
   BasicBlock *PreHeader = L->getLoopPreheader();
   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   const DataLayout &DL = Header->getModule()->getDataLayout();
   SCEVExpander Expander(*SE, DL, "loop-unroll");
   if (!AllowExpensiveTripCount &&
-      Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
+      Expander.isHighCostExpansion(TripCountSC, L, 2 * SCEVCheapExpansionBudget,
                                    TTI, PreHeaderBR)) {
     LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
     return false;
   }
 
   // This constraint lets us deal with an overflowing trip count easily; see the
   // comment on ModVal below.
   if (Log2_32(Count) > BEWidth) {

llvm/test/Transforms/LoopUnroll/X86/high-cost-expansion.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=x86_64-unknown-linux-gnu -passes='loop-unroll' -unroll-runtime -S < %s 2>&1 | FileCheck %s
 
 define void @mask-high(i64 %arg, ptr dereferenceable(4) %arg1) {
 ; CHECK-LABEL: @mask-high(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = load i32, ptr [[ARG1:%.*]], align 4
 ; CHECK-NEXT:    [[I2:%.*]] = sext i32 [[I]] to i64
 ; CHECK-NEXT:    [[I3:%.*]] = and i64 [[ARG:%.*]], -16
 ; CHECK-NEXT:    [[I4:%.*]] = or i64 1, [[I3]]
 ; CHECK-NEXT:    [[I5:%.*]] = icmp sgt i64 [[I4]], [[I2]]
 ; CHECK-NEXT:    br i1 [[I5]], label [[BB10:%.*]], label [[BB6_PREHEADER:%.*]]
 ; CHECK:       bb6.preheader:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[I4]], i64 [[I2]])
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 [[SMAX]], [[I3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[SMAX]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[I3]]
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP0]], 7
+; CHECK-NEXT:    [[LCMP_MOD:%.*]] = icmp ne i64 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD]], label [[BB6_PROL_PREHEADER:%.*]], label [[BB6_PROL_LOOPEXIT:%.*]]
+; CHECK:       bb6.prol.preheader:
+; CHECK-NEXT:    br label [[BB6_PROL:%.*]]
+; CHECK:       bb6.prol:
+; CHECK-NEXT:    [[I7_PROL:%.*]] = phi i64 [ [[I8_PROL:%.*]], [[BB6_PROL]] ], [ [[I4]], [[BB6_PROL_PREHEADER]] ]
+; CHECK-NEXT:    [[PROL_ITER:%.*]] = phi i64 [ 0, [[BB6_PROL_PREHEADER]] ], [ [[PROL_ITER_NEXT:%.*]], [[BB6_PROL]] ]
+; CHECK-NEXT:    [[I8_PROL]] = add i64 [[I7_PROL]], 1
+; CHECK-NEXT:    [[I9_PROL:%.*]] = icmp slt i64 [[I7_PROL]], [[I2]]
+; CHECK-NEXT:    [[PROL_ITER_NEXT]] = add i64 [[PROL_ITER]], 1
+; CHECK-NEXT:    [[PROL_ITER_CMP:%.*]] = icmp ne i64 [[PROL_ITER_NEXT]], [[XTRAITER]]
+; CHECK-NEXT:    br i1 [[PROL_ITER_CMP]], label [[BB6_PROL]], label [[BB6_PROL_LOOPEXIT_UNR_LCSSA:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK:       bb6.prol.loopexit.unr-lcssa:
+; CHECK-NEXT:    [[I7_UNR_PH:%.*]] = phi i64 [ [[I8_PROL]], [[BB6_PROL]] ]
+; CHECK-NEXT:    br label [[BB6_PROL_LOOPEXIT]]
+; CHECK:       bb6.prol.loopexit:
+; CHECK-NEXT:    [[I7_UNR:%.*]] = phi i64 [ [[I4]], [[BB6_PREHEADER]] ], [ [[I7_UNR_PH]], [[BB6_PROL_LOOPEXIT_UNR_LCSSA]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP2]], 7
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB10_LOOPEXIT:%.*]], label [[BB6_PREHEADER_NEW:%.*]]
+; CHECK:       bb6.preheader.new:
 ; CHECK-NEXT:    br label [[BB6:%.*]]
 ; CHECK:       bb6:
-; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I8:%.*]], [[BB6]] ], [ [[I4]], [[BB6_PREHEADER]] ]
-; CHECK-NEXT:    [[I8]] = add i64 [[I7]], 1
-; CHECK-NEXT:    [[I9:%.*]] = icmp slt i64 [[I7]], [[I2]]
-; CHECK-NEXT:    br i1 [[I9]], label [[BB6]], label [[BB10_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I7_UNR]], [[BB6_PREHEADER_NEW]] ], [ [[I8_7:%.*]], [[BB6]] ]
+; CHECK-NEXT:    [[I8:%.*]] = add i64 [[I7]], 1
+; CHECK-NEXT:    [[I8_1:%.*]] = add i64 [[I8]], 1
+; CHECK-NEXT:    [[I8_2:%.*]] = add i64 [[I8_1]], 1
+; CHECK-NEXT:    [[I8_3:%.*]] = add i64 [[I8_2]], 1
+; CHECK-NEXT:    [[I8_4:%.*]] = add i64 [[I8_3]], 1
+; CHECK-NEXT:    [[I8_5:%.*]] = add i64 [[I8_4]], 1
+; CHECK-NEXT:    [[I8_6:%.*]] = add i64 [[I8_5]], 1
+; CHECK-NEXT:    [[I8_7]] = add i64 [[I8_6]], 1
+; CHECK-NEXT:    [[I9_7:%.*]] = icmp slt i64 [[I8_6]], [[I2]]
+; CHECK-NEXT:    br i1 [[I9_7]], label [[BB6]], label [[BB10_LOOPEXIT_UNR_LCSSA:%.*]]
+; CHECK:       bb10.loopexit.unr-lcssa:
+; CHECK-NEXT:    br label [[BB10_LOOPEXIT]]
 ; CHECK:       bb10.loopexit:
 ; CHECK-NEXT:    br label [[BB10]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %i = load i32, ptr %arg1, align 4
   %i2 = sext i32 %i to i64

 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = load i32, ptr [[ARG1:%.*]], align 4
 ; CHECK-NEXT:    [[I2:%.*]] = sext i32 [[I]] to i64
 ; CHECK-NEXT:    [[I3:%.*]] = and i64 [[ARG:%.*]], 16
 ; CHECK-NEXT:    [[I4:%.*]] = add i64 1, [[I3]]
 ; CHECK-NEXT:    [[I5:%.*]] = icmp sgt i64 [[I4]], [[I2]]
 ; CHECK-NEXT:    br i1 [[I5]], label [[BB10:%.*]], label [[BB6_PREHEADER:%.*]]
 ; CHECK:       bb6.preheader:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[I4]], i64 [[I2]])
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 [[SMAX]], [[I3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[SMAX]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[I3]]
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP0]], 7
+; CHECK-NEXT:    [[LCMP_MOD:%.*]] = icmp ne i64 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD]], label [[BB6_PROL_PREHEADER:%.*]], label [[BB6_PROL_LOOPEXIT:%.*]]
+; CHECK:       bb6.prol.preheader:
+; CHECK-NEXT:    br label [[BB6_PROL:%.*]]
+; CHECK:       bb6.prol:
+; CHECK-NEXT:    [[I7_PROL:%.*]] = phi i64 [ [[I8_PROL:%.*]], [[BB6_PROL]] ], [ [[I4]], [[BB6_PROL_PREHEADER]] ]
+; CHECK-NEXT:    [[PROL_ITER:%.*]] = phi i64 [ 0, [[BB6_PROL_PREHEADER]] ], [ [[PROL_ITER_NEXT:%.*]], [[BB6_PROL]] ]
+; CHECK-NEXT:    [[I8_PROL]] = add i64 [[I7_PROL]], 1
+; CHECK-NEXT:    [[I9_PROL:%.*]] = icmp slt i64 [[I7_PROL]], [[I2]]
+; CHECK-NEXT:    [[PROL_ITER_NEXT]] = add i64 [[PROL_ITER]], 1
+; CHECK-NEXT:    [[PROL_ITER_CMP:%.*]] = icmp ne i64 [[PROL_ITER_NEXT]], [[XTRAITER]]
+; CHECK-NEXT:    br i1 [[PROL_ITER_CMP]], label [[BB6_PROL]], label [[BB6_PROL_LOOPEXIT_UNR_LCSSA:%.*]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK:       bb6.prol.loopexit.unr-lcssa:
+; CHECK-NEXT:    [[I7_UNR_PH:%.*]] = phi i64 [ [[I8_PROL]], [[BB6_PROL]] ]
+; CHECK-NEXT:    br label [[BB6_PROL_LOOPEXIT]]
+; CHECK:       bb6.prol.loopexit:
+; CHECK-NEXT:    [[I7_UNR:%.*]] = phi i64 [ [[I4]], [[BB6_PREHEADER]] ], [ [[I7_UNR_PH]], [[BB6_PROL_LOOPEXIT_UNR_LCSSA]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP2]], 7
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB10_LOOPEXIT:%.*]], label [[BB6_PREHEADER_NEW:%.*]]
+; CHECK:       bb6.preheader.new:
 ; CHECK-NEXT:    br label [[BB6:%.*]]
 ; CHECK:       bb6:
-; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I8:%.*]], [[BB6]] ], [ [[I4]], [[BB6_PREHEADER]] ]
-; CHECK-NEXT:    [[I8]] = add i64 [[I7]], 1
-; CHECK-NEXT:    [[I9:%.*]] = icmp slt i64 [[I7]], [[I2]]
-; CHECK-NEXT:    br i1 [[I9]], label [[BB6]], label [[BB10_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I7_UNR]], [[BB6_PREHEADER_NEW]] ], [ [[I8_7:%.*]], [[BB6]] ]
+; CHECK-NEXT:    [[I8:%.*]] = add nuw nsw i64 [[I7]], 1
+; CHECK-NEXT:    [[I8_1:%.*]] = add nuw nsw i64 [[I8]], 1
+; CHECK-NEXT:    [[I8_2:%.*]] = add nuw nsw i64 [[I8_1]], 1
+; CHECK-NEXT:    [[I8_3:%.*]] = add nuw nsw i64 [[I8_2]], 1
+; CHECK-NEXT:    [[I8_4:%.*]] = add nuw nsw i64 [[I8_3]], 1
+; CHECK-NEXT:    [[I8_5:%.*]] = add nuw nsw i64 [[I8_4]], 1
+; CHECK-NEXT:    [[I8_6:%.*]] = add nuw nsw i64 [[I8_5]], 1
+; CHECK-NEXT:    [[I8_7]] = add nuw nsw i64 [[I8_6]], 1
+; CHECK-NEXT:    [[I9_7:%.*]] = icmp slt i64 [[I8_6]], [[I2]]
+; CHECK-NEXT:    br i1 [[I9_7]], label [[BB6]], label [[BB10_LOOPEXIT_UNR_LCSSA:%.*]]
+; CHECK:       bb10.loopexit.unr-lcssa:
+; CHECK-NEXT:    br label [[BB10_LOOPEXIT]]
 ; CHECK:       bb10.loopexit:
 ; CHECK-NEXT:    br label [[BB10]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %i = load i32, ptr %arg1, align 4
   %i2 = sext i32 %i to i64

llvm/test/Transforms/LoopUnroll/high-cost-trip-count-computation.ll

-; RUN: opt -S -unroll-runtime -passes=loop-unroll < %s | FileCheck %s
+; RUN: opt -S -unroll-runtime -passes=loop-unroll -scev-cheap-expansion-budget=1    < %s | FileCheck %s --check-prefixes=CHECK
+; RUN: opt -S -unroll-runtime -passes=loop-unroll -scev-cheap-expansion-budget=8192 < %s | FileCheck %s --check-prefixes=CHECK,CHECK-HIGH-BUDGET
+; RUN: opt -S -unroll-runtime -passes=loop-unroll                                   < %s | FileCheck %s --check-prefixes=CHECK
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
-;; Check that we don't emit expensive instructions to compute trip
+;; Check that we generally don't emit expensive instructions to compute trip
 ;; counts when unrolling loops.
 
 define i32 @test(i64 %v12, ptr %array, ptr %loc) {
 ; CHECK-LABEL: @test(
+; CHECK-HIGH-BUDGET: udiv
 ; CHECK-NOT: udiv
 entry:
   %step = load i64, ptr %loc, !range !0
   br label %loop
 
 loop:                                           ; preds = %entry, %loop
   %k.015 = phi i64 [ %v15, %loop ], [ %v12, %entry ]
   %v14 = getelementptr inbounds i8, ptr %array, i64 %k.015