[SCEV] Limit AddRec "simplifications" to avoid combinatorial explosions
authorMax Kazantsev <max.kazantsev@azul.com>
Tue, 16 Oct 2018 05:26:21 +0000 (05:26 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Tue, 16 Oct 2018 05:26:21 +0000 (05:26 +0000)
commitfdfd98ceecd17bf5d72bf4ed1a86948ad590c647
tree8e88096b377fd5a68e74f79da76d440d16e76f6f
parent28d467a809de1ac1e720d52c9296176cbe822a86
[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

llvm-svn: 344584
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/binomial-explision.ll [new file with mode: 0644]