This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Constant fold MultExpr before applying depth limit.
ClosedPublic

Authored by dantrushin on May 13 2020, 11:34 AM.

Details

Summary

Users of SCEV reasonably assume that multiplication of two constant
SCEVs will in turn be constant.
However, that is not always the case:
First, we can get here with reached depth limit, and will create
MultExpr SCEV C1 * C2 and cache it.
Then, we can get here with the same operands, but with small depth
level. But this time we will find existing MultExpr SCEV and return
it, instead of expected constant SCEV.

This patch changes getMultExpr to first try constant folding of SCEV
and then apply depth limit, just like getAddExpr does.
It might result in further get{Add|Mult}Expr calls, but they would
perform constant folding only and should not be too expensive.

Diff Detail

Event Timeline

dantrushin created this revision.May 13 2020, 11:34 AM
efriedma added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
3017

I think you need to rearrange the code a bit more: with the current version of the patch, we increase the depth before checking the current depth.

The general idea makes sense: we should perform optimizations that aren't recursive before the depth check.

dantrushin marked an inline comment as done.May 14 2020, 12:19 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
3017

Eli, could you explain?
Do you mean Depth + 1 used in calls above on constant folding path?
My reasoning was following:
If we're already at depth limit (Depth == MaxArithDepth) then we don't want to recurse into possible expensive folding.
On the other hand, constant folding will be attempted anyway, which is what we want here.

Does it makes sense?

Fix clang-format error

nikic added a subscriber: nikic.May 14 2020, 1:12 AM
mkazantsev requested changes to this revision.May 19 2020, 9:15 PM

I like the idea, however I would strongly avoid any situation where we can, even theoretically, recurse with more depth than limit.

Do you plan to make similar changes for other SCEV types (e.g. Add)?

llvm/lib/Analysis/ScalarEvolution.cpp
2971

Is this change realy necessary? Looks unrelated, please commit it separately unless there is a reason to have it here. I'm also sure that similar change can be done in Add and some other SCEVs.

2992

We can potentially recurse here with unlimited depth, which is undersiable. Can you please avoid this?

This revision now requires changes to proceed.May 19 2020, 9:15 PM
dantrushin marked 2 inline comments as done.May 19 2020, 10:48 PM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
2971

This exactly is copied from getAddExpr (the only other place where depth limits are applied)

2992

Again, the idea was that just constant folding should not take too much time even if going deep. This also allows to keep code clean and simple.
Ok, I'll change it to check for all constant ops

Only ignore depth limit for all-constant expressions

dantrushin marked 3 inline comments as done.May 19 2020, 11:28 PM

Please add a test which clearly shows the impact (e.g. running -analyze scalar-evolution on single mul instruction with zero depth).

llvm/lib/Analysis/ScalarEvolution.cpp
2940

This is too expensive. Provided that ops are sorted by type, it's enough to check the last one.

Address comments

This revision is now accepted and ready to land.May 22 2020, 3:55 AM

Please consider making same thing for add as a follow-up.

This revision was automatically updated to reflect the committed changes.