This is an archive of the discontinued LLVM Phabricator instance.

[ScalarEvolution] Apply Depth limit to getMulExpr
ClosedPublic

Authored by mkazantsev on Jun 7 2017, 5:07 AM.

Details

Summary

This is a fix for PR33292 that shows a case of extremely long compilation
of a single .c file with clang, with most time spent within SCEV.

We have a mechanism of limiting recursion depth for getAddExpr to avoid
long analysis in SCEV. However, there are calls from getAddExpr to getMulExpr
and back that do not propagate the info about depth. As result of this, a chain

getAddExpr -> ... .> getAddExpr -> getMulExpr -> getAddExpr -> ... -> getAddExpr

can be extremely long, with every segment of getAddExpr's being up to max depth long.
This leads either to long compilation or crash by stack overflow. We face this situation while
analyzing big SCEVs in the test of PR33292.

This patch applies the same limit on max expression depth for getAddExpr and getMulExpr.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 7 2017, 5:07 AM
sanjoy requested changes to this revision.Jun 9 2017, 2:48 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
2733–2737

Why not do the same thing here as you did in getAddExpr:

// Limit recursion calls depth
if (Depth > MaxArithDepth)
  return getOrCreateMulExpr(Ops, Flags);
This revision now requires changes to proceed.Jun 9 2017, 2:48 PM
mkazantsev edited edge metadata.
mkazantsev marked an inline comment as done.
sanjoy accepted this revision.Jun 14 2017, 11:04 PM

lgtm

lib/Analysis/ScalarEvolution.cpp
2630

Indent looks off?

2860

Something worth considering (no need to change in this patch) -- should we be incrementing Depth on tail calls like these where there is no real recursion?

This revision is now accepted and ready to land.Jun 14 2017, 11:04 PM
mkazantsev marked an inline comment as done.Jun 15 2017, 4:46 AM
mkazantsev added inline comments.
lib/Analysis/ScalarEvolution.cpp
2860

Not sure, may be reasonable to not do it since we always remove the number of ops here and cannot go to infinite recursion.

This revision was automatically updated to reflect the committed changes.