[SCEV] Avoid compile time explosion in ScalarEvolution::isImpliedCond

[bjope]

Summary

As seen in PR51869 the ScalarEvolution::isImpliedCond function might
end up spending lots of time when doing the isKnownPredicate checks.

Calling isKnownPredicate for example result in isKnownViaInduction
being called, which might result in isLoopBackedgeGuardedByCond being
called, and then we might get one or more new calls to isImpliedCond.
Even if the scenario described here isn't an infinite loop, using
some random generated C programs as input indicates that those
isKnownPredicate checks quite often returns true. On the other hand,
the third condition that needs to be fulfilled in order to "prove
implications via truncation", i.e. the isImpliedCondBalancedTypes
check, is rarely fulfilled.
I also made some similar experiments to look at how often we would
get the same result when using isKnownViaNonRecursiveReasoning instead
of isKnownPredicate. So far I haven't seen a single case when codegen
is negatively impacted by using isKnownViaNonRecursiveReasoning. On
the other hand, it seems like we get rid of the compile time explosion
seen in PR51869 that way. Hence this patch.

[bjope]

I figure there might be some program out there for which this still will converge slowly etc, and I'm not sure exactly how to prove that this is better in general terms.

But at least this patch has a huge positive impact on compile time for the test case from PR51869 (and I haven't seen any case yet were we get a similarly huge penalty instead).

[nikic]

I think a better solution would be to replace isKnownPredicate() with isKnownViaNonRecursiveReasoning(). That's the primitive that isImpliedCond() normally uses.

[nikic]

Compile time for...
...this patch: https://llvm-compile-time-tracker.com/compare.php?from=54d868991ab79abc5c52cf38939f0a45292e7506&to=c630a0d16f0f00c4e06bdd2ea9e4fa95a3f9e16e&stat=instructions
...non-recursive reasoning: https://llvm-compile-time-tracker.com/compare.php?from=54d868991ab79abc5c52cf38939f0a45292e7506&to=b6e305314a9fd6fb2d05987ac51ea836d9e64676&stat=instructions

So it's an improvement on CTMark either way, but I think using non-recursive reasoning is the more principled choice, because it doesn't rely on isImpliedCondBalancedTypes() returning false to prevent the CT explosion.

[bjope]

I plan to update this patch into using isKnownViaNonRecursiveReasoning as suggested by @nikic

[bjope]

Now using isKnownViaNonRecursiveReasoning instead of isKnownPredicate.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

if (getTypeSizeInBits(LHS->getType()) <
     // operands fit into narrow unsigned range. If so, try to prove facts in
     // narrow types.
     if (!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)) {
+      if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_ULE, FoundLHS, MaxValue) &&
+          isKnownViaNonRecursiveReasoning(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).
+;
+; This test case used to take 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). There is a less reduced version of this test case in
+; PR51869 that takes much longer time to execute (I've not seen that one
+; terminate within reasonable time). Maybe this test case is reduced a bit too
+; much if being considered as a regression tests that would timeout without
+; the fix. It can at least be used to show compile time explosion that
+; happened when using isKnownPredicate inside ScalarEvolution::isImpliedCond.
+
+@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 }