Disable "[SCEV] Prove implications of different type via truncation"

[bjope]

Summary

This disables the feature added in commit 5ef84688fba28b9f0f that
proved implications of different type via truncations. This due to
problems seen (and reported in PR51869) about infinite loops that
started to happen after that commit.

It was not trivial to just revert the offending commit, so I added
an option to make it possible to enable/disable the feature from the
command line instead. With the default currently being that the
feature is disabled.

Some things worth mentioning:

• test/Analysis/ScalarEvolution/srem.ll was impacted by the original patch, but nowadays we get the same result regardless of scalar-evolution-prove-implications-via-truncation.
• test/Transforms/IndVarSimplify/widen-loop-comp.ll did not exist(?) when the feature was introduced. The test case was already a bit special as it uses scalar-evolution-use-expensive-range-sharpening. Now it also use scalar-evolution-prove-implications-via-truncation, so it is not testing the default setting.
• The ProveImplicationViaNarrowing unittest test case for SCEV that was added in commit 5ef84688fba28b9f0f still passes even when disabling the feature. So this patch simply leaves that test case as is.

[nikic]

Can the test case be reduced? I don't think we want to add a 5000 line test case for this.

[bjope]

In D111066#3040144, @nikic wrote:

Can the test case be reduced? I don't think we want to add a 5000 line test case for this.

I made some attempts using bugpoint earlier (and this is actually a bit reduced compared to the original test case). A bit tricky to set it up as the fail scenario is that there should be a timeout, and then it will take lots of time to get bugpoint to actually reduce anything.
I also made some attempts adding some kind of debug printouts to detect failure by identifying some repeated patterns when calling ScalarEvolution::isImpliedCond, but never managed to get that working properly.
If I knew what the problem is it might be easier to reduce it ;-)

If anyone got some ideas on how to tackle the problem with reducing it I wouldn't mind testing those ideas.

(Maybe I should give "bugpoint + timeout" another try. But I think I need quite a long timeout setting, so it takes some time if it only attempts to remove 1 instruction every 5 minutes or so.)

[bjope]

In D111066#3040370, @bjope wrote:

In D111066#3040144, @nikic wrote:

Can the test case be reduced? I don't think we want to add a 5000 line test case for this.

I made some attempts using bugpoint earlier (and this is actually a bit reduced compared to the original test case). A bit tricky to set it up as the fail scenario is that there should be a timeout, and then it will take lots of time to get bugpoint to actually reduce anything.
I also made some attempts adding some kind of debug printouts to detect failure by identifying some repeated patterns when calling ScalarEvolution::isImpliedCond, but never managed to get that working properly.
If I knew what the problem is it might be easier to reduce it ;-)

If anyone got some ideas on how to tackle the problem with reducing it I wouldn't mind testing those ideas.

(Maybe I should give "bugpoint + timeout" another try. But I think I need quite a long timeout setting, so it takes some time if it only attempts to remove 1 instruction every 5 minutes or so.)

Was a couple of weeks ago that I tried reducing this the last time. Now I've at least managed to reduce it a bit more manually (removing some stores/calls/branches, and then running with -dce -simplifycfg, etc). I'll continue a bit more and then I'll update this patch.

[bjope]

Reduced the test case. Maybe too much, because now it terminates after around 10 minutes. The previous (>5000 lines) version of the test case is still running after 2 hours (and I do not even know if it will terminate).

[mkazantsev]

This patch is one year old. It is extremely surprising that you are trying to disable it rather than find the root cause.

I don't believe this is infinite recursion. Before all, infinite recursion should end up with stack overflow and not timeout. I can believe there is some exponential explosion happening, but in this case you need to find how exactly it happens and fix the acutal reason. The fact that this patch triggers something very slow doesn't convince me that this patch is guilty, and this test doesn't allow to figure it out easily.

Could you please check (at least, but not limited to):

• Do we end up creating some HUGE SCEVs in your test?
• Do we end up making the same implication query millions of times?
• Do we end up walking huge dom trees for execution of some queries?

Before we decide to switch something off, I want to know why exactly.

[mkazantsev]

I ran -analyze -scalar-evolution on this test and it indeed works slowly. It doesn't hang, though. It's just extremely slow work due to exponential behavior during range inference. Not obvious that it is somehow caused by trunc inference. Pretty sure it's possible to construct same test without trunc/sexts.

[bjope]

In D111066#3041655, @mkazantsev wrote:

This patch is one year old. It is extremely surprising that you are trying to disable it rather than find the root cause.

I don't believe this is infinite recursion. Before all, infinite recursion should end up with stack overflow and not timeout. I can believe there is some exponential explosion happening, but in this case you need to find how exactly it happens and fix the acutal reason. The fact that this patch triggers something very slow doesn't convince me that this patch is guilty, and this test doesn't allow to figure it out easily.

Could you please check (at least, but not limited to):

• Do we end up creating some HUGE SCEVs in your test?
• Do we end up making the same implication query millions of times?
• Do we end up walking huge dom trees for execution of some queries?

Before we decide to switch something off, I want to know why exactly.

Hi @mkazantsev,

I have tried debugging PR51869 a bit, but I don't really know this code. I've wrote a bit about it in https://bugs.llvm.org/show_bug.cgi?id=51869, and added you as susbscriber, hoping to get some feedback or reactions. But since there was no reactions I did not add much info (I thought that maybe the author of the code at least could take a quick look to see that it wasn't an obvious mistake. I for example see that there are a couple of checks related to LHS before calling sKnownPredicate(ICmpInst::ICMP_ULE, FoundLHS, MaxValue), but nothing for RHS and it is the sKnownPredicate(ICmpInst::ICMP_ULE, FoundRHS, MaxValue) call that didn't seem to return (at least not with the reproducer in the PR51869). If I remember correctly I could not see any deep recursion, but there were lots of calls to ScalarEvolution::isImpliedCond( and I suspected some kind of ping-pong effect.

We've seen timeouts in several different test cases during the last year. And bisecting points at your commit every time. However, it was quite recently we managed to reduce one of those test cases down to something smaller (~5000 lines of IR, running on a single pass, without any downstream intrinsics and without any unusual address spaces etc). I think a collegue of mine has tried to reach out for help, and we have added some comments in https://reviews.llvm.org/D89548 trying to get some reactions. This ticket was kind of another attempt to get some help/feedback. Nice to see that it got some interest. However, this ticket is about disabling the analysis that is causing bad time complexity, and perhaps we should discuss the actual problem with PR51869 in bugzilla.

Btw, since the only test case that seem to validate that we actually get some transforms given that this feature is turned on is the test case using -scalar-evolution-use-expensive-range-sharpening which is disabled by default. So we do not really have any lit tests verifying that this extra analysis is working as intended, except for that special test case. That could actually be another reason to disable this, IMHO.

Anyway, I want to switch this off because it has been causing lots of trouble and I do not know exactly why. If I knew why, then hopefully that could be fixed instead. My idea was to leave that until someone bothered about PR51869 (or until someone though it would be worth trying to enable this feature again (because right now it seem a bit broken when it comes to time complexity). I'd be happy to see a proper solution to the problem though. So the I figure the goal should be to enable -scalar-evolution-prove-implications-via-truncation again later. But I think I need some help debugging and figuring out why we start to see these timeout problems given your patch.

[fhahn]

In D111066#3041655, @mkazantsev wrote:

This patch is one year old. It is extremely surprising that you are trying to disable it rather than find the root cause.

I don't believe this is infinite recursion. Before all, infinite recursion should end up with stack overflow and not timeout. I can believe there is some exponential explosion happening, but in this case you need to find how exactly it happens and fix the acutal reason. The fact that this patch triggers something very slow doesn't convince me that this patch is guilty, and this test doesn't allow to figure it out easily.

Could you please check (at least, but not limited to):

• Do we end up creating some HUGE SCEVs in your test?
• Do we end up making the same implication query millions of times?
• Do we end up walking huge dom trees for execution of some queries?

Before we decide to switch something off, I want to know why exactly.

I added a smaller (~500 lines) reproducer that takes ~15s on my machine on main: https://bugs.llvm.org/attachment.cgi?id=25328. With D111066 it goes down to 0.2s, which I think clearly shows that . So it's not an infinite loop but a compile-time explosion with ~60% of compile-time spent in evaluatePredicateAt, ~25% in getStrengthenedNoWrapFlagsFromBinOp and ~10% in getSCEV.

It looks related to the depth of chained basic blocks. The reproducer has a lot of basic block chained together with unconditional branches. I already removed a lot of similar chains to bring down the compile-time.

[fhahn]

In D111066#3041948, @fhahn wrote:

In D111066#3041655, @mkazantsev wrote:

This patch is one year old. It is extremely surprising that you are trying to disable it rather than find the root cause.

I don't believe this is infinite recursion. Before all, infinite recursion should end up with stack overflow and not timeout. I can believe there is some exponential explosion happening, but in this case you need to find how exactly it happens and fix the acutal reason. The fact that this patch triggers something very slow doesn't convince me that this patch is guilty, and this test doesn't allow to figure it out easily.

Could you please check (at least, but not limited to):

• Do we end up creating some HUGE SCEVs in your test?
• Do we end up making the same implication query millions of times?
• Do we end up walking huge dom trees for execution of some queries?

Before we decide to switch something off, I want to know why exactly.

I added a smaller (~500 lines) reproducer that takes ~15s on my machine on main: https://bugs.llvm.org/attachment.cgi?id=25328. With D111066 it goes down to 0.2s, which I think clearly shows that . So it's not an infinite loop but a compile-time explosion with ~60% of compile-time spent in evaluatePredicateAt, ~25% in getStrengthenedNoWrapFlagsFromBinOp and ~10% in getSCEV.

Ah the recent reproducer from @bjope shows the issue with even fewer lines!

[bjope]

llvm/lib/Analysis/ScalarEvolution.cpp

10666

I tried changing the order of this if statement and the nestled if-statement. I.e. doing the isImpliedCondBalancedTypes check first, then it will converge faster. Well at least for the reproducer.

No idea if it is more common that the isKnownPredicate checks will be true more often that the isImpliedCondBalancedTypes check. One reasoning could be that it perhaps converge faster since doing the new lookup on the truncated expressions is changing the state a bit more compared to just calling isKnownPredicate on the current state. But I have no idea really. Maybe one could gather some statistics for this based on some test suite.

[bjope]

An alternative solution is presented in D112080 (using a different order for the checks involved).

[bjope]

Abandoned. Obsoleted by D111896.

llvm/lib/Analysis/ScalarEvolution.cpp

 //===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
ClassifyExpressions("scalar-evolution-classify-expressions",
     cl::desc("When printing analysis, include information on every instruction"));
 
 static cl::opt<bool> UseExpensiveRangeSharpening(
     "scalar-evolution-use-expensive-range-sharpening", cl::Hidden,
     cl::init(false),
     cl::desc("Use more powerful methods of sharpening expression ranges. May "
              "be costly in terms of compile time"));
 
+// This is currently disabled by default due to PR51869 (the analysis might end
+// up in an infinite loop).
+static cl::opt<bool> ProveImplicationsOfDifferentTypeViaTruncation(
+    "scalar-evolution-prove-implications-via-truncation", cl::Hidden,
+    cl::init(false),
+    cl::desc("If we can prove that wider type values actually fit in the "
+             "narrow type, we truncate them and prove the implication in "
+             "narrow type."));
+
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
 
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *FoundLHS, const SCEV *FoundRHS,
                                     const Instruction *CtxI) {
   // Balance the types.
   if (getTypeSizeInBits(LHS->getType()) <
       getTypeSizeInBits(FoundLHS->getType())) {
     // For unsigned and equality predicates, try to prove that both found
     // operands fit into narrow unsigned range. If so, try to prove facts in
     // narrow types.
-    if (!CmpInst::isSigned(FoundPred) && !FoundLHS->getType()->isPointerTy()) {
+    if (ProveImplicationsOfDifferentTypeViaTruncation &&
+        !CmpInst::isSigned(FoundPred) && !FoundLHS->getType()->isPointerTy()) {
       auto *NarrowType = LHS->getType();
       auto *WideType = FoundLHS->getType();
       auto BitWidth = getTypeSizeInBits(NarrowType);
       const SCEV *MaxValue = getZeroExtendExpr(
           getConstant(APInt::getMaxValue(BitWidth)), WideType);
       if (isKnownPredicate(ICmpInst::ICMP_ULE, FoundLHS, MaxValue) &&
           isKnownPredicate(ICmpInst::ICMP_ULE, FoundRHS, MaxValue)) {
         const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
         const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
         if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
                                        TruncFoundRHS, CtxI))
           return true;
       }
     }

llvm/test/Analysis/ScalarEvolution/pr51869-scalar-evolution-prove-implications-via-truncation.ll

+; RUN: opt < %s -disable-output -passes=indvars
+
+; Do not timeout (and do not crash).
+;
+; Adding; -scalar-evolution-prove-implications-via-truncation used to result
+; in this test case taking around 10 minutes to run (well, that of course
+; depends on which kind of build that is used and on which kind of server the
+; test is executed). This reduced version is hopefully enough to show that
+; there are some time complexity problems connected to that option. There is a
+; less reduced version of the test case in PR51869 that takes much longer time
+; to execute (I've not seen that one terminate, so maybe this test case is
+; reduced a bit too much).
+
+@v_228 = external dso_local global i32, align 1
+
+; Function Attrs: nounwind
+define dso_local i16 @main(i16* %0, i16* %1, i16* %2, i16* %3, i16* %4, i16* %5, i16* %6, i16* %7, i16* %8, i16* %9, i16* %10, i1 %11) #0 {
+  br i1 %11, label %27, label %13
+
+13:                                               ; preds = %12
+  %14 = load i32, i32* @v_228, align 1
+  %15 = trunc i32 %14 to i16
+  %16 = mul i16 %15, 2
+  %17 = sub i16 10, %16
+  %18 = icmp ult i16 10, %16
+  %19 = icmp ult i16 %17, 1
+  %20 = or i1 %18, %19
+  br i1 %20, label %139, label %21
+
+21:                                               ; preds = %13
+  %22 = add i16 %16, 1
+  %23 = sub i16 10, %22
+  %24 = icmp ult i16 10, %22
+  %25 = icmp ult i16 %23, 1
+  %26 = or i1 %24, %25
+  br i1 %26, label %139, label %27
+
+27:                                               ; preds = %21, %12
+  %28 = load i16, i16* %1, align 1
+  br label %29
+
+29:                                               ; preds = %29, %27
+  %30 = phi i16 [ %28, %27 ], [ %31, %29 ]
+  %31 = add i16 %30, 1
+  %32 = icmp slt i16 %31, 28
+  br i1 %32, label %29, label %33
+
+33:                                               ; preds = %29
+  %34 = load i16, i16* %2, align 1
+  br label %35
+
+35:                                               ; preds = %43, %33
+  %36 = phi i16 [ %34, %33 ], [ %44, %43 ]
+  %37 = sext i16 %36 to i32
+  %38 = mul i32 %37, 2
+  %39 = sub i32 56, %38
+  %40 = icmp ult i32 56, %38
+  %41 = icmp ult i32 %39, 2
+  %42 = or i1 %40, %41
+  br i1 %42, label %139, label %43
+
+43:                                               ; preds = %35
+  %44 = add i16 %36, 1
+  %45 = icmp slt i16 %44, 28
+  br i1 %45, label %35, label %46
+
+46:                                               ; preds = %43
+  %47 = load i16, i16* %3, align 1
+  br label %48
+
+48:                                               ; preds = %55, %46
+  %49 = phi i16 [ %47, %46 ], [ %56, %55 ]
+  %50 = mul i16 %49, 4
+  %51 = sub i16 28, %50
+  %52 = icmp ult i16 28, %50
+  %53 = icmp ult i16 %51, 4
+  %54 = or i1 %52, %53
+  br i1 %54, label %139, label %55
+
+55:                                               ; preds = %48
+  %56 = add i16 %49, 1
+  %57 = icmp slt i16 %56, 7
+  br i1 %57, label %48, label %58
+
+58:                                               ; preds = %55
+  %59 = load i16, i16* %4, align 1
+  br label %60
+
+60:                                               ; preds = %67, %58
+  %61 = phi i16 [ %59, %58 ], [ %68, %67 ]
+  %62 = sext i16 %61 to i32
+  %63 = sub i32 1, %62
+  %64 = icmp ult i32 1, %62
+  %65 = icmp ult i32 %63, 1
+  %66 = or i1 %64, %65
+  br i1 %66, label %139, label %67
+
+67:                                               ; preds = %60
+  %68 = add i16 %61, 1
+  %69 = icmp slt i16 %68, 1
+  br i1 %69, label %60, label %70
+
+70:                                               ; preds = %67
+  %71 = load i16, i16* %5, align 1
+  br label %72
+
+72:                                               ; preds = %79, %70
+  %73 = phi i16 [ %71, %70 ], [ %80, %79 ]
+  %74 = sext i16 %73 to i32
+  %75 = sub i32 1, %74
+  %76 = icmp ult i32 1, %74
+  %77 = icmp ult i32 %75, 1
+  %78 = or i1 %76, %77
+  br i1 %78, label %139, label %79
+
+79:                                               ; preds = %72
+  %80 = add i16 %73, 1
+  %81 = icmp slt i16 %80, 1
+  br i1 %81, label %72, label %82
+
+82:                                               ; preds = %79
+  %83 = load i16, i16* %6, align 1
+  br label %84
+
+84:                                               ; preds = %91, %82
+  %85 = phi i16 [ %83, %82 ], [ %92, %91 ]
+  %86 = sext i16 %85 to i32
+  %87 = sub i32 1, %86
+  %88 = icmp ult i32 1, %86
+  %89 = icmp ult i32 %87, 1
+  %90 = or i1 %88, %89
+  br i1 %90, label %139, label %91
+
+91:                                               ; preds = %84
+  %92 = add i16 %85, 1
+  %93 = icmp slt i16 %92, 1
+  br i1 %93, label %84, label %94
+
+94:                                               ; preds = %91
+  %95 = load i16, i16* %7, align 1
+  br label %96
+
+96:                                               ; preds = %103, %94
+  %97 = phi i16 [ %95, %94 ], [ %104, %103 ]
+  %98 = sext i16 %97 to i32
+  %99 = sub i32 1, %98
+  %100 = icmp ult i32 1, %98
+  %101 = icmp ult i32 %99, 1
+  %102 = or i1 %100, %101
+  br i1 %102, label %139, label %103
+
+103:                                              ; preds = %96
+  %104 = add i16 %97, 1
+  %105 = icmp slt i16 %104, 1
+  br i1 %105, label %96, label %106
+
+106:                                              ; preds = %103
+  %107 = load i16, i16* %8, align 1
+  br label %108
+
+108:                                              ; preds = %115, %106
+  %109 = phi i16 [ %107, %106 ], [ %116, %115 ]
+  %110 = mul i16 %109, 4
+  %111 = sub i16 24, %110
+  %112 = icmp ult i16 24, %110
+  %113 = icmp ult i16 %111, 4
+  %114 = or i1 %112, %113
+  br i1 %114, label %139, label %115
+
+115:                                              ; preds = %108
+  %116 = add i16 %109, 1
+  %117 = icmp slt i16 %116, 6
+  br i1 %117, label %108, label %118
+
+118:                                              ; preds = %115
+  %119 = load i16, i16* %9, align 1
+  br label %120
+
+120:                                              ; preds = %128, %118
+  %121 = phi i16 [ %119, %118 ], [ %129, %128 ]
+  %122 = sext i16 %121 to i32
+  %123 = mul i32 %122, 2
+  %124 = sub i32 4, %123
+  %125 = icmp ult i32 4, %123
+  %126 = icmp ult i32 %124, 2
+  %127 = or i1 %125, %126
+  br i1 %127, label %139, label %128
+
+128:                                              ; preds = %120
+  %129 = add i16 %121, 1
+  %130 = icmp slt i16 %129, 2
+  br i1 %130, label %120, label %131
+
+131:                                              ; preds = %128
+  %132 = load i16, i16* %10, align 1
+  br label %133
+
+133:                                              ; preds = %133, %131
+  %134 = phi i16 [ %132, %131 ], [ %135, %133 ]
+  %135 = add i16 %134, 1
+  %136 = icmp slt i16 %135, 6
+  br i1 %136, label %133, label %137
+
+137:                                              ; preds = %133
+  %138 = load i16, i16* %0, align 1
+  ret i16 %138
+
+139:                                              ; preds = %120, %108, %96, %84, %72, %60, %48, %35, %21, %13
+  call void @llvm.trap() #2
+  unreachable
+}
+
+; Function Attrs: cold noreturn nounwind
+declare void @llvm.trap() #1
+
+attributes #0 = { nounwind }
+attributes #1 = { cold noreturn nounwind }
+attributes #2 = { noreturn nounwind }

llvm/test/Transforms/IndVarSimplify/widen-loop-comp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -indvars -scalar-evolution-use-expensive-range-sharpening -S | FileCheck %s
+; RUN: opt < %s -indvars -scalar-evolution-use-expensive-range-sharpening -scalar-evolution-prove-implications-via-truncation -S | FileCheck %s
 target triple = "aarch64--linux-gnu"
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 
 ; Check the loop exit i32 compare instruction and operand are widened to i64
 ; instead of truncating IV before its use in the i32 compare instruction.