Page MenuHomePhabricator

[PM] Fix a bug where through CGSCC iteration we can get infinite-inlining across multiple runs of the inliner by keeping a tiny history of internal-to-SCC inlining decisions.

Authored by chandlerc on Aug 1 2017, 2:02 PM.



This is still a bit gross, but I don't yet have any fundamentally better
ideas and numerous people are blocked on this to use new PM and ThinLTO

The core of the idea is to detect when we are about to do an inline that
has a chance of re-splitting an SCC which we have split before with
a similar inlining step. That is a critical component in the inlining
forming a cycle and so far detects all of the various cyclic patterns
I can come up with as well as the original real-world test case (which
comes from a ThinLTO build of libunwind).

I've added some tests that I think really demonstrate what is going on
here. They are essentially state machines that march the inliner through
various steps of a cycle and check that we stop when the cycle is closed
and that we actually did do inlining to form that cycle.

A lot of thanks go to Eric Christopher and Sanjoy Das for the help
understanding this issue and improving the test cases.

The biggest "yuck" here is the layering issue -- the CGSCC pass manager
is providing somewhat magical state to the inliner for it to use to make
itself converge. This isn't great, but I don't honestly have a lot of
better ideas yet and at least seems nicely isolated.

I have tested this patch, and it doesn't block *any* inlining on the
entire LLVM test suite and SPEC, so it seems sufficiently narrowly
targeted to the issue at hand.

Diff Detail


Event Timeline

chandlerc created this revision.Aug 1 2017, 2:02 PM
davide accepted this revision.Aug 1 2017, 2:22 PM
davide added a subscriber: davide.

This is pretty nasty but I can't think of a better way of handling this more surgically.
I hope you can revisit this at some point in the future.

This revision is now accepted and ready to land.Aug 1 2017, 2:22 PM
sanjoy accepted this revision.Aug 1 2017, 6:39 PM
sanjoy added inline comments.
983 ↗(On Diff #109215)

"infinite refinement" can be a bit confusing since it is easy to think refinement is monotonic (in particular, I would not classify SCC splits as refinement). How about "infinite SCC splits and merges"?

chandlerc marked an inline comment as done.Aug 1 2017, 7:01 PM

Thanks all, landing.

Sanjoy has come up with a creative test case that even this doesn't handle so we'll definitely need to revisit it. But I don't think any actualy optimization pipeline today can hit that test case so its more about resolving the underlying theoretical issues here.

This revision was automatically updated to reflect the committed changes.