[SCEV] Limit AddRec "simplifications" to avoid combinatorial explosions

Authored by mkazantsev on Oct 15 2018, 10:26 PM.


[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

Differential Revision: https://reviews.llvm.org/D53282
Reviewed By: sanjoy

llvm-svn: 344584