Arthur Eubanks via llvm-dev
2021-Jun-08 22:39 UTC
[llvm-dev] exponential code explosion during inlining
I may be misunderstanding, but when you say "cleanup", do you mean the function simplification pipeline (since the change that caused this was a change to the function simplification pipeline)? But that happens after inlining, and we won't revisit the SCC, unless there are some weird SCC splitting/merging things going on. On Tue, Jun 8, 2021 at 8:43 AM Joseph Tremoulet via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi, > > > > I filed a bug (PR50485 [1]) a couple weeks ago for some pathological > behavior we’ve hit in the inliner, but there hasn’t been any reply on the > bug so I figured I’d broaden the audience and ask about the issue here. > > > > The problem is partially a phase-ordering issue – we run cleanup > optimizations after inlining an SCC that reduce the size of functions in > the SCC, so a given call foo -> bar that looks unprofitable due to bar’s > size while processing the SCC containing foo and bar may suddenly look > profitable due to bar’s reduced size when later considering a copy of that > same callsite that gets created by inlining foo into some function in a > later SCC. > > > > This interacts badly with the approach that the inliner relies on local > heuristics to eventually converge (rather than limiting itself with some > global budget). I’ll copy the comment explaining that approach here: > > > > // We use a single common worklist for calls across the entire SCC. We > > // process these in-order and append new calls introduced during > inlining to > > // the end. > > // > > // Note that this particular order of processing is actually critical to > > // avoid very bad behaviors. Consider *highly connected* call graphs > where > > // each function contains a small amount of code and a couple of calls to > > // other functions. Because the LLVM inliner is fundamentally a bottom-up > > // inliner, it can handle gracefully the fact that these all appear to be > > // reasonable inlining candidates as it will flatten things until they > become > > // too big to inline, and then move on and flatten another batch. > > // > > // However, when processing call edges *within* an SCC we cannot rely on > this > > // bottom-up behavior. As a consequence, with heavily connected *SCCs* of > > // functions we can end up incrementally inlining N calls into each of > > // N functions because each incremental inlining decision looks good and > we > > // don't have a topological ordering to prevent explosions. > > // > > // To compensate for this, we don't process transitive edges made > immediate > > // by inlining until we've done one pass of inlining across the entire > SCC. > > // Large, highly connected SCCs still lead to some amount of code bloat > in > > // this model, but it is uniformly spread across all the functions in > the SCC > > // and eventually they all become too large to inline, rather than > > // incrementally maknig a single function grow in a super linear fashion. > > > > The problem in a nutshell is that “eventually they all become too large to > inline” is true while inlining is happening in their SCC, but then the > cleanup makes them small again and so the inliner goes nuts chasing all the > now-profitable paths through the highly connected SCC when considering them > as transitive inlines into a subsequent SCC. > > > > I’d love some thoughts on how we might best go about addressing this. I > could imagine trying to address it as a phase ordering issue by running > cleanup at the start of inlining an SCC – in the cases where we’ve hit this > the cleanup hasn’t actually depended on inlining to expose the > opportunities, it just happened to first get cleaned up immediately post > inlining. I could also imagine trying to address it by limiting transitive > inlines at callsites created by inlining functions from already-converged > SCCs, which we could either do wholesale (if we’re expecting them to be too > big to inline at this point, that shouldn’t be a big loss, right?) or just > by capping their depth, say, to cut off exponential explosion. > > > > > > Thanks, > > -Joseph > > > > [1] - 50485 – Exponential code explosion during inlining (llvm.org) > <https://bugs.llvm.org/show_bug.cgi?id=50485> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210608/2886d49a/attachment.html>
Joseph Tremoulet via llvm-dev
2021-Jun-09 02:41 UTC
[llvm-dev] [EXTERNAL] Re: exponential code explosion during inlining
Yes, I believe it's from the function simplification pipeline. It happens
after inlining *within* an SCC, but since it's added to the same
CFSCCPassManager as the inliner pass, it runs before the inliner pass runs on
the *next* SCC, which effectively revisits the first SCC by transitive inlines.
To be concrete:
Suppose F calls A, A calls B, B calls A.
Then A and B together belong to SCC 1.
And F is alone in SCC 2.
The order of events is:
1. CGSCCPassManager visits SCC 1
* InlinerPass visits SCC 1
i. Call from
A to B is considered for inlining, B's size is B_large, inline not performed
ii. Call from
B to A is considered for inlining, A's size is A_large, inline not performed
* FunctionSimplificationPipeline runs inside its
CGSCCToFunctionPassAdaptor inside the CGSCCPassManager
i.
FunctionSimplificationPipeline runs on A, now its size is A_small
ii.
FunctionSimplificationPipeline runs on B, now its size is B_small
1. CGSCCPassManager visits SCC 2
* InlinerPass visits SCC 2
i. Call from
F to A is considered, A's size is A_small, inlining is performed. F picks
up a call to B in the inlined copy of A.
ii. Call form
F to B (added by inline just performed) is considered, B's size is B_small,
inlining is performed, F picks up a call to A in the inlined copy of B <--
this is the step where we are effectively revisiting the call from A to B
iii. Call from F
to A (added by inline just performed) is considered, A's size is A_small,
inlining looks profitable but InlineHistory check blocks it
In the small example with just one SCC having just two nodes, the existing
InlineHistory check is sufficient to curtail the problem. But in our suites
that started failing, instead of just one such SCC, there were ~30 (i.e. A and B
each call each other but also call C and D; C and D call each other but also
call E and F; E and F each call each other but also call G and H; and so on),
which gave the inliner so many apparently-profitable call chains to inline that
it ran until OOM.
In the reduced repro attached to the bug, each SCC has six nodes, so the code
growth is unreasonable with just two or three such SCCs.
Thanks,
-Joseph
From: Arthur Eubanks <aeubanks at google.com>
Sent: Tuesday, June 8, 2021 6:40 PM
To: Joseph Tremoulet <jotrem at microsoft.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: [EXTERNAL] Re: [llvm-dev] exponential code explosion during inlining
I may be misunderstanding, but when you say "cleanup", do you mean the
function simplification pipeline (since the change that caused this was a change
to the function simplification pipeline)? But that happens after inlining, and
we won't revisit the SCC, unless there are some weird SCC splitting/merging
things going on.
On Tue, Jun 8, 2021 at 8:43 AM Joseph Tremoulet via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi,
I filed a bug (PR50485 [1]) a couple weeks ago for some pathological behavior
we've hit in the inliner, but there hasn't been any reply on the bug so
I figured I'd broaden the audience and ask about the issue here.
The problem is partially a phase-ordering issue - we run cleanup optimizations
after inlining an SCC that reduce the size of functions in the SCC, so a given
call foo -> bar that looks unprofitable due to bar's size while
processing the SCC containing foo and bar may suddenly look profitable due to
bar's reduced size when later considering a copy of that same callsite that
gets created by inlining foo into some function in a later SCC.
This interacts badly with the approach that the inliner relies on local
heuristics to eventually converge (rather than limiting itself with some global
budget). I'll copy the comment explaining that approach here:
// We use a single common worklist for calls across the entire SCC. We
// process these in-order and append new calls introduced during inlining to
// the end.
//
// Note that this particular order of processing is actually critical to
// avoid very bad behaviors. Consider *highly connected* call graphs where
// each function contains a small amount of code and a couple of calls to
// other functions. Because the LLVM inliner is fundamentally a bottom-up
// inliner, it can handle gracefully the fact that these all appear to be
// reasonable inlining candidates as it will flatten things until they become
// too big to inline, and then move on and flatten another batch.
//
// However, when processing call edges *within* an SCC we cannot rely on this
// bottom-up behavior. As a consequence, with heavily connected *SCCs* of
// functions we can end up incrementally inlining N calls into each of
// N functions because each incremental inlining decision looks good and we
// don't have a topological ordering to prevent explosions.
//
// To compensate for this, we don't process transitive edges made
immediate
// by inlining until we've done one pass of inlining across the entire
SCC.
// Large, highly connected SCCs still lead to some amount of code bloat in
// this model, but it is uniformly spread across all the functions in the SCC
// and eventually they all become too large to inline, rather than
// incrementally maknig a single function grow in a super linear fashion.
The problem in a nutshell is that "eventually they all become too large to
inline" is true while inlining is happening in their SCC, but then the
cleanup makes them small again and so the inliner goes nuts chasing all the
now-profitable paths through the highly connected SCC when considering them as
transitive inlines into a subsequent SCC.
I'd love some thoughts on how we might best go about addressing this. I
could imagine trying to address it as a phase ordering issue by running cleanup
at the start of inlining an SCC - in the cases where we've hit this the
cleanup hasn't actually depended on inlining to expose the opportunities, it
just happened to first get cleaned up immediately post inlining. I could also
imagine trying to address it by limiting transitive inlines at callsites created
by inlining functions from already-converged SCCs, which we could either do
wholesale (if we're expecting them to be too big to inline at this point,
that shouldn't be a big loss, right?) or just by capping their depth, say,
to cut off exponential explosion.
Thanks,
-Joseph
[1] - 50485 - Exponential code explosion during inlining
(llvm.org)<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fbugs.llvm.org%2Fshow_bug.cgi%3Fid%3D50485&data=04%7C01%7Cjotrem%40microsoft.com%7C9b5731388bd54a08905a08d92ace56b1%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637587888412026728%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=ordnapD5P%2BPcaPDqKKIgRfNiPbqQEOK8aYjq2uADpzA%3D&reserved=0>
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=04%7C01%7Cjotrem%40microsoft.com%7C9b5731388bd54a08905a08d92ace56b1%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637587888412026728%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C2000&sdata=5cyNhNOo1Bf3Cf8tgygi%2F318Be7oyFpRSj4%2F3UpTAhw%3D&reserved=0>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210609/a735c9f3/attachment.html>