diff options
author | Max Kazantsev <max.kazantsev@azul.com> | 2018-10-16 05:26:21 +0000 |
---|---|---|
committer | Max Kazantsev <max.kazantsev@azul.com> | 2018-10-16 05:26:21 +0000 |
commit | f2cb5da6a45f63427c0d1e6a3f0deca57c44429e (patch) | |
tree | 8652263a7900ed14ed18bbbe287846073d2aaafd /test/Analysis | |
parent | 341f13c81dcaa21a6beab540e71e0bc15c526e66 (diff) |
[SCEV] Limit AddRec "simplifications" to avoid combinatorial explosions
SCEV's transform that turns `{A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>` into
a single AddRec of size `2n+1` with complex combinatorial coefficients can easily
trigger exponential growth of the SCEV (in case if nothing gets folded and simplified).
We tried to restrain this transform using the option `scalar-evolution-max-add-rec-size`,
but its default value seems to be insufficiently small: the test attached to this patch
with default value of this option `16` has a SCEV of >3M symbols (when printed out).
This patch reduces the simplification limit. It is not a cure to combinatorial
explosions, but at least it reduces this corner case to something more or less
reasonable.
Differential Revision: https://reviews.llvm.org/D53282
Reviewed By: sanjoy
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@344584 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'test/Analysis')
-rw-r--r-- | test/Analysis/ScalarEvolution/binomial-explision.ll | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/test/Analysis/ScalarEvolution/binomial-explision.ll b/test/Analysis/ScalarEvolution/binomial-explision.ll new file mode 100644 index 00000000000..82d0beda6b5 --- /dev/null +++ b/test/Analysis/ScalarEvolution/binomial-explision.ll @@ -0,0 +1,47 @@ +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1" + +; Check that we don't have unreasonably huge SCEVs and in particular only a +; reasonable amount of AddRecs in the notation of %tmp19. If we "simplify" SCEVs +; too aggressively, we may end up with huge nested expressions. +define void @test(i32 %x, i64 %y, i1 %cond) { + +; CHECK: %tmp19 = mul i32 %tmp17, %tmp18 +; CHECK: (((( +; CHECK-NOT: ((((( +; CHECK: %tmp20 = add i32 %tmp19, %x + +bb: + br label %bb1 + +bb1: ; preds = %bb3, %bb + %tmp = phi i64 [ %y, %bb ], [ %tmp22, %bb3 ] + %tmp2 = phi i32 [ %x, %bb ], [ %tmp4, %bb3 ] + br label %bb5 + +bb3: ; preds = %bb5 + %tmp4 = add i32 %tmp2, %x + br label %bb1 + +bb5: ; preds = %bb5, %bb1 + %tmp6 = phi i32 [ %tmp23, %bb5 ], [ %tmp2, %bb1 ] + %tmp7 = sub i32 -119, %tmp6 + %tmp8 = mul i32 %tmp7, %x + %tmp9 = sub i32 -120, %tmp6 + %tmp10 = mul i32 %tmp8, %tmp9 + %tmp11 = mul i32 %x, %tmp10 + %tmp12 = sub i32 -121, %tmp6 + %tmp13 = mul i32 %tmp10, %tmp12 + %tmp14 = mul i32 %tmp11, %tmp13 + %tmp15 = sub i32 -122, %tmp6 + %tmp16 = mul i32 %tmp13, %tmp15 + %tmp17 = mul i32 %tmp14, %tmp16 + %tmp18 = mul i32 %tmp16, %x + %tmp19 = mul i32 %tmp17, %tmp18 + %tmp20 = add i32 %tmp19, %x + %tmp21 = sext i32 %tmp20 to i64 + %tmp22 = add i64 %y, %tmp21 + %tmp23 = add i32 %tmp6, 7 + br i1 %cond, label %bb5, label %bb3 +} |