Page MenuHomePhabricator

[SCEV][NFC] Introduces expression sizes estimation
ClosedPublic

Authored by mkazantsev on Jul 28 2017, 5:04 AM.

Details

Summary

This patch introduces the field ExpressionSize in SCEV. This field is calculated only once on SCEV creation,
and it represents the complexity of this SCEV from arithmetical point of view (not from the point of the number
of actual different SCEV nodes that are used in the expression). Roughly saying, it is the number of operands
and operations symbols when we print this SCEV.

A formal definition is following: if SCEV X has operands Op1, Op2, ..., OpN, then

Size(X) = 1 + Size(Op1) + Size(Op2) + ... + Size(OpN)

here N can also be zero if X is a constant or SCEVUnknown.

Expression size may be used as a universal way to limit SCEV transformations for huge SCEVs. Currently,
we have a bunch of options that represents various limits (such as recursion depth limit) that may not
make any sense from the point of view of a LLVM users who is not familiar with SCEV internals, and all
these different options pursue one goal. A more general rule that may potentially allow us to get rid of
this redundancy in options is "do not make transformations with SCEVs of huge size". It can apply to all
SCEV traversals and transformations that may need to visit a SCEV node more than once, hence they are
prone to combinatorial explosions.

This patch only introduces SCEV sizes calculation as NFC, its utilization will be introduced in follow-up patches.

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev created this revision.Jul 28 2017, 5:04 AM
sanjoy edited edge metadata.Jul 28 2017, 5:09 PM

I'm worried about the peak memory usage impact of this change. Can you try to do a clang bootstrap and count the maximum number of SCEV objects alive at any one given time? That information would also be generally useful.

sanjoy requested changes to this revision.Aug 2 2017, 10:40 AM

Requesting changes as per previous comments.

This revision now requires changes to proceed.Aug 2 2017, 10:40 AM

Seems that I've missed the comment here.

I will do some experiments with estimation of number of SCEVs. The tricky thing is that this work is done to reduce this number, for example the follow-up change https://reviews.llvm.org/D35990 does it. But you're right that it would be nice to have such a statistics.

I've done clang bootstrap with this patch and gathered SCEV statistics: maximum number of SCEVs alive simultaneously is 209373; assuming sizeof(unsigned)==4 it's ~0.8MiB overhead.

mkazantsev requested review of this revision.Oct 19 2017, 4:54 AM
mkazantsev edited edge metadata.

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

mkazantsev abandoned this revision.Feb 26 2018, 2:55 AM

Rebase & reclaim to fix PR40292.

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

include/llvm/Analysis/ScalarEvolutionExpressions.h
419 ↗(On Diff #181724)

Like SCEVConstant this should probably be 1 as well? Same for SCEVCouldNotCompute? They're both leaf nodes.

If it needs to be 0 then please add a comment why.

reames requested changes to this revision.Jan 16 2019, 11:25 AM

Detailed code review comments below.

FTR, I talked to Sanjoy offline. I double checked w/him because I'm not familiar enough w/SCEVs design to be confident in judging the approach itself. He okayed the general direction, so I'm going to drive the review from a code style/implementation perspective. Once done, I'll approve the patch.

include/llvm/Analysis/ScalarEvolution.h
82 ↗(On Diff #181724)

Field alignment nit pick: If you keep it as a full 32 bit field, move it above the two 16 bit fields. With the current layout, you end up as:
128 bit FastId
16 bit SCEVType
16 bit alignment padding
your 32 bit field
16 bit SubclassData
tail padding

i.e. you're burning 32 bits of alignment padding.

88 ↗(On Diff #181724)

Does this need to be a full unsigned? From the threshold used in https://reviews.llvm.org/D35990, it looks like we could get away w/an uint16_t if we used saturating addition.

Note: I'm not requiring this change. I'm throwing out an idea for consideration on how to reduce memory usage at the cost of slightly higher computation cost. I'm leaving it to the patch author to decide which approach is better.

122 ↗(On Diff #181724)

nitpick: call the arg ExprSize or something

153 ↗(On Diff #181724)

I'd just inline the body here.

include/llvm/Analysis/ScalarEvolutionExpressions.h
419 ↗(On Diff #181724)

I agree w/Sanjoy here.

This revision now requires changes to proceed.Jan 16 2019, 11:25 AM
mkazantsev marked 7 inline comments as done.Jan 18 2019, 1:51 AM
mkazantsev added inline comments.
include/llvm/Analysis/ScalarEvolution.h
88 ↗(On Diff #181724)

Saturating adds are OK as long as our threshold fits in 16 bits.

include/llvm/Analysis/ScalarEvolutionExpressions.h
419 ↗(On Diff #181724)

There's no such reason, it was supposed to be 1. Thanks!

mkazantsev marked 2 inline comments as done.

Addressed comments, added a unit test to make sure that the computation works as intended.

reames accepted this revision.Jan 18 2019, 11:04 AM

LGTM w/one required change before commit and one optional encouraged one.

include/llvm/Analysis/ScalarEvolutionExpressions.h
143 ↗(On Diff #182477)

Stylistically, I'd recommend using a single helper function w/an arrayref argument. It can replace all of the helpers you've got here. This is an optional change, can be made before or after initial submit.

lib/Analysis/ScalarEvolution.cpp
396 ↗(On Diff #182477)

You missed a 0 -> 1

mkazantsev marked an inline comment as done.Jan 20 2019, 8:41 PM
mkazantsev added inline comments.
lib/Analysis/ScalarEvolution.cpp
396 ↗(On Diff #182477)

It's okay here, because SCEVCouldNotCompute can never be a part of another expression. It is only used to signal that SCEV was unable to construct a SCEV.

mkazantsev marked an inline comment as done.Jan 20 2019, 9:37 PM

Replaced all utility functions with one.

mkazantsev marked an inline comment as done.Jan 20 2019, 9:41 PM
mkazantsev added inline comments.
lib/Analysis/ScalarEvolution.cpp
396 ↗(On Diff #182477)

SCEVCouldNotCompute is not a real expression, so let's leave it 0.

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

We were estimating max amount of SCEVs that exist at the same time during a bootstrap compilation, and then multiplied by field size of 32 bits (now it's 16 bits). So yes, it's basically a small fraction of this memory.

This revision was not accepted when it landed; it landed in state Needs Review.Jan 20 2019, 10:20 PM
This revision was automatically updated to reflect the committed changes.

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

We were estimating max amount of SCEVs that exist at the same time during a bootstrap compilation

I meant the maximum amount of memory consumed by clang (in a release without asserts build).