Page MenuHomePhabricator

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

Authored by mkazantsev on Oct 15 2018, 4:32 AM.

Details

Summary

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.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 15 2018, 4:32 AM
sanjoy accepted this revision.Oct 15 2018, 7:56 AM

lgtm

test/Analysis/ScalarEvolution/binomial-explision.ll
19

Let's remove these undefs from the test case (to make it 100% obvious that the test has nothing to do with optimizing undefs).

This revision is now accepted and ready to land.Oct 15 2018, 7:56 AM
mkazantsev marked an inline comment as done.Oct 15 2018, 9:26 PM
mkazantsev edited the summary of this revision. (Show Details)
This revision was automatically updated to reflect the committed changes.