HomePhabricator

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

Description

[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

Details

Committed
mkazantsevOct 15 2018, 10:26 PM
Reviewer
sanjoy
Differential Revision
D53282: [SCEV] Limit AddRec "simplifications" to avoid combinatorial explosions
Parents
rL344583: [mips] Group similar commands in the test case. NFC
Branches
Unknown
Tags
Unknown