[ScalarEvolution] Enhance Predicate implication from condition

[TiehuZhang]

Summary

We can prove the scenario:

FoundLHS > FoundRHS =>
LHS = (FoundLHS + Offset) > RHS = (FoundRHS + Offset)

Or

FoundLHS < FoundRHS =>
LHS = (FoundLHS + Offset) < RHS = (FoundRHS + Offset)

This patch enhance isImpliedCondBalancedTypes with the formula.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11768

This is incorrect in case of overflow. See isKnownPredicateViaNoOverflow.

[mkazantsev]

llvm/test/Transforms/HardwareLoops/ARM/simple-do.ll

151

This is miscompile, see https://alive2.llvm.org/ce/z/ESPqU_

[TiehuZhang]

llvm/lib/Analysis/ScalarEvolution.cpp

11768

This is incorrect in case of overflow. See isKnownPredicateViaNoOverflow.

llvm/test/Transforms/HardwareLoops/ARM/simple-do.ll

151

Thanks for your review! https://alive2.llvm.org/ is really a useful tool. Sometimes, it is helpful for the performance to simplify -1,+,(-1 * %max_row_length)}<nw><%for.cond1.preheader> + ({1,+,%max_row_length}<nw><%for.cond1.preheader> smax {%max_row_length,+,%max_row_length}<nw><%for.cond1.preheader> to -1 + %max_row_length . For most cases, smax is redundant, and may hurt performance. But if overflow is considered, this check is indispensable. I'll try to restrict the condition of the patch to ensure the correctness. For the scenario, do you have any suggestions?

llvm/lib/Analysis/ScalarEvolution.cpp

if (isa<SCEVConstant>(RHS)) {
       std::swap(FoundLHS, FoundRHS);
       FoundPred = ICmpInst::getSwappedPredicate(FoundPred);
     } else {
       std::swap(LHS, RHS);
       Pred = ICmpInst::getSwappedPredicate(Pred);
     }
   }
 
+  // We can handle the special case in advance, as shown:
+  // FoundLHS < FoundRHS =>
+  // LHS = (FoundLHS + Offset) < RHS = (FoundRHS + Offset)
+  // Or
+  // FoundLHS > FoundRHS =>
+  // LHS = (FoundLHS + Offset) > RHS = (FoundRHS + Offset)
+  if ((FoundPred == Pred) && (FoundLHS->getType() == LHS->getType()) &&
+      (!FoundLHS->getType()->isPointerTy() && !LHS->getType()->isPointerTy())) {
+    auto *FoundLHSOffset = getMinusSCEV(LHS, FoundLHS);
+    auto *FoundRHSOffset = getMinusSCEV(RHS, FoundRHS);
+    if (FoundLHSOffset == FoundRHSOffset)
+      return true;
+  }
+
   // Check whether the found predicate is the same as the desired predicate.
   if (FoundPred == Pred)
     return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
 
   // Check whether swapping the found predicate makes it the same as the
   // desired predicate.
   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
     // We can write the implication

llvm/test/Analysis/ScalarEvolution/add-like-or.ll

 ; CHECK-NEXT:    --> %i U: full-set S: full-set
 ; CHECK-NEXT:    %i2 = sext i32 %i to i64
 ; CHECK-NEXT:    --> (sext i32 %i to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %i3 = and i64 %arg, -16
 ; CHECK-NEXT:    --> (16 * (%arg /u 16))<nuw> U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %i4 = or i64 1, %i3
 ; CHECK-NEXT:    --> (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw> U: [1,-14) S: [-9223372036854775807,9223372036854775794)
 ; CHECK-NEXT:    %i7 = phi i64 [ %i4, %bb ], [ %i8, %bb6 ]
-; CHECK-NEXT:    --> {(1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>,+,1}<%bb6> U: full-set S: full-set Exits: ((sext i32 %i to i64) smax (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>) LoopDispositions: { %bb6: Computable }
+; CHECK-NEXT:    --> {(1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>,+,1}<%bb6> U: full-set S: full-set Exits: (sext i32 %i to i64) LoopDispositions: { %bb6: Computable }
 ; CHECK-NEXT:    %i8 = add i64 %i7, 1
-; CHECK-NEXT:    --> {(2 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>,+,1}<%bb6> U: full-set S: full-set Exits: (1 + ((sext i32 %i to i64) smax (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>))<nsw> LoopDispositions: { %bb6: Computable }
+; CHECK-NEXT:    --> {(2 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>,+,1}<%bb6> U: full-set S: full-set Exits: (1 + (sext i32 %i to i64))<nsw> LoopDispositions: { %bb6: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @mask-high
-; CHECK-NEXT:  Loop %bb6: backedge-taken count is (-1 + (-16 * (%arg /u 16)) + ((sext i32 %i to i64) smax (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>))
+; CHECK-NEXT:  Loop %bb6: backedge-taken count is (-1 + (sext i32 %i to i64) + (-16 * (%arg /u 16)))
 ; CHECK-NEXT:  Loop %bb6: constant max backedge-taken count is -9223372034707292162
-; CHECK-NEXT:  Loop %bb6: symbolic max backedge-taken count is (-1 + (-16 * (%arg /u 16)) + ((sext i32 %i to i64) smax (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>))
-; CHECK-NEXT:  Loop %bb6: Predicated backedge-taken count is (-1 + (-16 * (%arg /u 16)) + ((sext i32 %i to i64) smax (1 + (16 * (%arg /u 16))<nuw>)<nuw><nsw>))
+; CHECK-NEXT:  Loop %bb6: symbolic max backedge-taken count is (-1 + (sext i32 %i to i64) + (-16 * (%arg /u 16)))
+; CHECK-NEXT:  Loop %bb6: Predicated backedge-taken count is (-1 + (sext i32 %i to i64) + (-16 * (%arg /u 16)))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %bb6: Trip multiple is 1
 ;
 bb:
   %i = load i32, ptr %arg1, align 4
   %i2 = sext i32 %i to i64
   %i3 = and i64 %arg, -16
   %i4 = or i64 1, %i3

llvm/test/Analysis/ScalarEvolution/trip-count-implied-offset.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s "-passes=print<scalar-evolution>" -disable-output -S 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-gnu"
 
 define dso_local void @cal_sparseMV(i32 noundef %nCells, ptr nocapture noundef readonly %x, ptr nocapture noundef writeonly %b, ptr nocapture noundef readonly %values, i32 noundef %max_row_length, ptr nocapture noundef readonly %col_index) local_unnamed_addr {
 ; CHECK-LABEL: 'cal_sparseMV'
 ; CHECK:       Determining loop execution counts for: @cal_sparseMV
-; CHECK:       Loop %for.body4: backedge-taken count is ({-1,+,(-1 * %max_row_length)}<nw><%for.cond1.preheader> + ({1,+,%max_row_length}<nw><%for.cond1.preheader> smax {%max_row_length,+,%max_row_length}<nw><%for.cond1.preheader>))
+; CHECK:       Loop %for.body4: backedge-taken count is (-1 + %max_row_length)
 ; CHECK:       Loop %for.body4: constant max backedge-taken count is -1
-; CHECK:       Loop %for.body4: symbolic max backedge-taken count is ({-1,+,(-1 * %max_row_length)}<nw><%for.cond1.preheader> + ({1,+,%max_row_length}<nw><%for.cond1.preheader> smax {%max_row_length,+,%max_row_length}<nw><%for.cond1.preheader>))
-; CHECK:       Loop %for.body4: Predicated backedge-taken count is ({-1,+,(-1 * %max_row_length)}<nw><%for.cond1.preheader> + ({1,+,%max_row_length}<nw><%for.cond1.preheader> smax {%max_row_length,+,%max_row_length}<nw><%for.cond1.preheader>))
+; CHECK:       Loop %for.body4: symbolic max backedge-taken count is (-1 + %max_row_length)
+; CHECK:       Loop %for.body4: Predicated backedge-taken count is (-1 + %max_row_length)
 ;
 entry:
   %cmp28 = icmp sgt i32 %nCells, 0
   br i1 %cmp28, label %for.cond1.preheader.preheader, label %for.cond.cleanup
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader
 

llvm/test/CodeGen/Thumb2/mve-vmovlloop.ll

 ; CHECK-LABEL: vmovl_16to32:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r7, lr}
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #1
 ; CHECK-NEXT:    it lt
 ; CHECK-NEXT:    poplt {r7, pc}
 ; CHECK-NEXT:  .LBB2_1: @ %for.body.preheader
-; CHECK-NEXT:    mov r3, r2
-; CHECK-NEXT:    cmp r2, #8
-; CHECK-NEXT:    it ge
-; CHECK-NEXT:    movge r3, #8
-; CHECK-NEXT:    subs r3, r2, r3
-; CHECK-NEXT:    add.w r12, r3, #7
+; CHECK-NEXT:    sub.w r12, r2, #1
 ; CHECK-NEXT:    movs r3, #1
 ; CHECK-NEXT:    add.w r3, r3, r12, lsr #3
 ; CHECK-NEXT:    dls lr, r3
 ; CHECK-NEXT:  .LBB2_2: @ %for.body
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    vctp.16 r2
 ; CHECK-NEXT:    subs r2, #8
 ; CHECK-NEXT:    vpst

llvm/test/Transforms/HardwareLoops/ARM/simple-do.ll

 while.end:
   %res.0.lcssa = phi i32 [ 0, %entry ], [ %add, %while.end.loopexit ]
   ret i32 %res.0.lcssa
 }
 
 ; CHECK-LABEL: do_dec2
 
 ; CHECK: entry:
-; CHECK: [[ROUND:%[^ ]+]] = add i32 %n, 1
-; CHECK: [[SMIN:%[^ ]+]] = call i32 @llvm.smin.i32(i32 %n, i32 2)
-; CHECK: [[SUB:%[^ ]+]] = sub i32 [[ROUND]], [[SMIN]]
-; CHECK: [[HALVE:%[^ ]+]] = lshr i32 [[SUB]], 1
+; CHECK: [[ROUND:%[^ ]+]] = add i32 %n, -1
+; CHECK: [[HALVE:%[^ ]+]] = lshr i32 [[ROUND]], 1
 ; CHECK: [[COUNT:%[^ ]+]] = add nuw i32 [[HALVE]], 1
 
 ; CHECK: while.body.lr.ph:
 ; CHECK: [[START:%[^ ]+]] = call i32 @llvm.start.loop.iterations.i32(i32 [[COUNT]])
 ; CHECK: br label %while.body
 
 ; CHECK: [[REM:%[^ ]+]] = phi i32 [ [[START]], %while.body.lr.ph ], [ [[LOOP_DEC:%[^ ]+]], %while.body ]
 ; CHECK: [[LOOP_DEC]] = call i32 @llvm.loop.decrement.reg.i32(i32 [[REM]], i32 1)

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4
 ; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], -5
 ; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], -2147483643
 ; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 -6, [[LEN_ADD_5]]
 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 ; CHECK:       loop.preheader:
-; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LEN]], i32 0)
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[SMAX]], -5
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ -6, [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    call void @side_effect()
 ; CHECK-NEXT:    [[IV_INC]] = add nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 ; CHECK:       be:
 ; CHECK-NEXT:    call void @side_effect()
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN_ADD_5]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 ; CHECK:       leave.loopexit:
 ; CHECK-NEXT:    br label [[LEAVE]]
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %len = load i32, ptr %len.ptr

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:    [[TMP0:%.*]] = sub i64 [[I2]], [[I3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[I2]], -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