[IndVars] Provide eliminateIVComparison with context

[mkazantsev]

Summary

We can prove more predicates when we have a context when eliminating ICmp.
As first (and very obvious) approximation we can use the ICmp instruction itself,
though in the future we are going to use a common dominator of all its users.
Need some refactoring before that.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

264

266

It's usually called CtxI

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

822

Please precommit, it's a bit noisy.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

119 ↗

(On Diff #330941)

Looks like it's a bug needs to be fixed before we can go with it.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

119 ↗

(On Diff #330941)

Funny thing that both false and true are correct here.
false is obviously correct because inc is strictly positive and i.0 is non-positive, and this is what is proved without context.
However true is also correct because this is guarded by

br i1 %cmp8243, label %for.body84, label %return

which is an impossible condition. In fact, this code is unreachable so anything is OK.

[lebedev.ri]

And that's what i was expecting to see: https://llvm-compile-time-tracker.com/compare.php?from=9575c48b8959dae3c3e39e0227435ae6ebd71443&to=c0e80b44e3c80fa9f344b14cbb8435c15f75f94e&stat=instructions
Are the checks already ordered from less costly to more costly?

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

119 ↗

(On Diff #330941)

btw this is a lead for further compile time opt that we are missing. Blocks guarded by false conditions can have any predicate proved automatically, to save some time.

[mkazantsev]

In D98697#2628661, @lebedev.ri wrote:

And that's what i was expecting to see: https://llvm-compile-time-tracker.com/compare.php?from=9575c48b8959dae3c3e39e0227435ae6ebd71443&to=c0e80b44e3c80fa9f344b14cbb8435c15f75f94e&stat=instructions
Are the checks already ordered from less costly to more costly?

That's sad. I think this is happening because, when false is trivially provable without context, we still spend a lot of time proving true via context. I'll try to find a way around it...

[reames]

For the compile time concern, one idea you could consider exploring would be to have a version of isKnownPredicateAt which returns an Optional<bool>. Such a routine could use the cheap proof techniques first (in both directions), and then resort to the more expensive ones. In this particular case, it would also simplify the caller code. Looking at a couple other callers, we seem to be missing some optimizations by not asking both.

If we pushed that down all the way to the loop guard processing, that could be a substantial compile time win. (As we'd walk the CFG once, not twice, in the case where we can't prove anything.)

[mkazantsev]

In D98697#2630151, @reames wrote:

For the compile time concern, one idea you could consider exploring would be to have a version of isKnownPredicateAt which returns an Optional<bool>. Such a routine could use the cheap proof techniques first (in both directions), and then resort to the more expensive ones. In this particular case, it would also simplify the caller code. Looking at a couple other callers, we seem to be missing some optimizations by not asking both.

If we pushed that down all the way to the loop guard processing, that could be a substantial compile time win. (As we'd walk the CFG once, not twice, in the case where we can't prove anything.)

This is a really good way to imrpove this, thank you for bringing this up. I'll consider this.

[mkazantsev]

Rebased on top of new API for predicate evaluation. Now the order of checks should be from cheap to expensive. Hope this is more CT-friendly.

[lebedev.ri]

Looks good to me.

In D98697#2634349, @mkazantsev wrote:

Rebased on top of new API for predicate evaluation. Now the order of checks should be from cheap to expensive. Hope this is more CT-friendly.

It didn't really help, still within the same ballpark +/- noise i would say:
https://llvm-compile-time-tracker.com/compare.php?from=9575c48b8959dae3c3e39e0227435ae6ebd71443&to=c0e80b44e3c80fa9f344b14cbb8435c15f75f94e&stat=instructions
vs
https://llvm-compile-time-tracker.com/compare.php?from=fb04227c7cc3c5ebb3ece90f8ec5c629920eb3af&to=71476f7052b97e7ba9f91624c7fa3d3cbd418aa6&stat=instructions

As discussed in previous SCEV changes, that is probably not a blocker here, although it is not great.

[mkazantsev]

Well, we clearly can produce better code here. Let's hope it's worth it. I'll spend some time trying to understand how we can make SCEV cheaper.

[uabelho]

I wrote
https://bugs.llvm.org/show_bug.cgi?id=52327
about a crash starting to happen with this patch.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   }
 
   // Get the SCEVs for the ICmp operands (in the specific context of the
   // current loop)
   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
   const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
   const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
 
-  // If the condition is always true or always false, replace it with
-  // a constant value.
-  if (auto Ev = SE->evaluatePredicate(Pred, S, X)) {
+  // If the condition is always true or always false in the given context,
+  // replace it with a constant value.
+  // TODO: We can sharpen the context to common dominator of all ICmp's users.
+  if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, ICmp)) {
     ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
     DeadInsts.emplace_back(ICmp);
     LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
   } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
     // fallthrough to end of function
   } else if (ICmpInst::isSigned(OriginalPred) &&
              SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
     // If we were unable to make anything above, all we can is to canonicalize

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 60392, [[TMP0]]
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[TMP1]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT2:%.*]], [[LOOP2]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
 ; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT2]]
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[P1]] unordered, align 8
-; CHECK-NEXT:    br i1 false, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
+; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i64 [[TMP4]], 60392
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP5]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
 ; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[P1]] unordered, align 8
-; CHECK-NEXT:    br i1 false, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
+; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[I9]] = add nuw nsw i32 [[LOCAL_0_]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;

llvm/test/Transforms/IndVarSimplify/checks_against_min_value.ll

 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ], [ [[START]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[IV]]
 ; CHECK-NEXT:    br i1 [[CHECK]], label [[GUARDED]], label [[FAIL:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], -2147483648
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ;
 entry:

 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[GUARDED:%.*]] ], [ [[START]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp ult i32 [[IV_NEXT]], [[IV]]
 ; CHECK-NEXT:    br i1 [[CHECK]], label [[GUARDED]], label [[FAIL:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ;
 entry:

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

leave:
   ret void
 }
 
 ; This checks that the backedge condition, (I + 1) < Length - 1 implies
 ; (I + 1) < Length
 define void @func_22(i32* %length.ptr) {
 ; CHECK-LABEL: @func_22(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp sgt i32 [[LENGTH]], 1
 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]

 ; CHECK-LABEL: @func_25(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 ; CHECK:       checked.1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp ne i32 [[IV]], 0
-; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
 ; CHECK:       checked.2:
-; CHECK-NEXT:    [[C3:%.*]] = icmp ne i32 [[IV]], 0
-; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]

 ; CHECK-LABEL: @func_26(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 ; CHECK:       checked.1:
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[IV]], 1
-; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
 ; CHECK:       checked.2:
-; CHECK-NEXT:    [[C3:%.*]] = icmp slt i32 [[IV]], 2
-; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]

llvm/test/Transforms/LoopLoadElim/pr-49141.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -indvars -loop-load-elim < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[A_01:%.*]] = phi i16 [ undef, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[INC]] = add nsw i16 [[A_01]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i16 [[INC]], 2
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 false, [[CMP]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    br i1 false, label [[FOR_COND:%.*]], label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.cond:                                         ; preds = %for.body
   %a.0 = phi i16 [ %inc, %for.body ]