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

Repository
rL LLVM

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 ↗(On Diff #169678)

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.