This is an archive of the discontinued LLVM Phabricator instance.

[InlineOrder] Add TopDownInlineOrder
AbandonedPublic

Authored by IBricchi on Dec 13 2022, 6:58 AM.

Details

Reviewers
mtrofin
kazu
taolq
Summary

Adds a top down order to the ModuleInliner. A top down inlining order ensures
that all possible inlining decisions are possible (depending on what the
InliningAdvisor chooses), e.g., callsites in callees can be independently
inlined.

Diff Detail

Event Timeline

IBricchi created this revision.Dec 13 2022, 6:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 13 2022, 6:58 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
IBricchi requested review of this revision.Dec 13 2022, 6:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 13 2022, 6:58 AM
IBricchi updated this revision to Diff 482511.Dec 13 2022, 8:59 AM
IBricchi edited the summary of this revision. (Show Details)Dec 15 2022, 1:59 PM
kazu added inline comments.Dec 16 2022, 3:14 PM
llvm/lib/Analysis/InlineOrder.cpp
293 ↗(On Diff #482511)

Lowercase. we

300 ↗(On Diff #482511)

Put a period CD..

302 ↗(On Diff #482511)

Are you duplicating much of InlineOrder because you use NodeCallCount as cache and do not care about updating the priority while the priority queue is consumed? I'm wondering if there is a good way for you to take what you need without duplicating the rest.

305 ↗(On Diff #482511)

Maybe "how many places" instead of "how many times". Otherwise, we might sound like we are talking about profiling counts.

309 ↗(On Diff #482511)

Capitalize the first letter and put a period at the end. Check which call sites caller has least calls.

311 ↗(On Diff #482511)

Please rename this to LeftCount.

https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

This applies to other variables in the same function.

321 ↗(On Diff #482511)

How do you ensure the top down inlining when you have a run of single edges with NodeCallCount alone? Here, each one of B, C, D, etc is called from exactly one place, but there is a clear order in the call graph.

 A
/ \
B C
| |
D E
| |
F G
| |
H I
337 ↗(On Diff #482511)

Put a period at the end like functions..

339 ↗(On Diff #482511)

Likewise.

340–347 ↗(On Diff #482511)

How does this work? It looks like NodeCallCount keeps changing while you are pushing all call sites at the beginning of the inlining pass (see ModuleInliner.cpp:145). So, a call site inserted at the beginning of the population loop and another call site inserted toward the end of the population loop are based on totally different values of NodeCallCount even though you haven't done any inlining at all. Unless you call std::make_heap at the end of the initial population loop, I am not sure if call sites are in any particular order that makes sense.

375 ↗(On Diff #482511)

Put some comment like:

// A map from a function to the number of call sites it is statically called from.
llvm/test/Transforms/Inline/module-inliner-basic.ll
22 ↗(On Diff #482511)

Please add a new line. The message "No newline at end of file" is a bit distracting now and when somebody adds more lines to the file and examines the diff.

llvm/test/Transforms/Inline/top-down-inliner-multiple-heads.ll
33 ↗(On Diff #482511)

Likewise.

llvm/test/Transforms/Inline/top-down-inliner-recursion.ll
33 ↗(On Diff #482511)

Likewise.

llvm/test/Transforms/Inline/top-down-inliner-simple.ll
34 ↗(On Diff #482511)

Likewise.

IBricchi updated this revision to Diff 483768.Dec 17 2022, 11:20 AM
IBricchi marked 12 inline comments as done.
IBricchi added inline comments.
llvm/lib/Analysis/InlineOrder.cpp
321 ↗(On Diff #482511)

You make a good point, I forgot to decrease the call count when we pop the Caller node. This should be addressed now.

I've provided a more indepth explanation as a response to one of your later comments.

340–347 ↗(On Diff #482511)

The idea is basically that we only ever consider callers that appear the least number of times in our "NodeCallCount" however as we pop calls we also remove them from our "NodeCallCount" so in the above example.

 A
/ \
B C
| |
D E
| |
F G
| |
H I

If we decide not to inline A->B or A->C, once poped we would effectively end up counts that represent a call graph like:

B C
| |
D E
| |
F G
| |
H I

Which would then consider B->D or C->E, and so on...

If the calls do get inlined we would end up with counts for a similar call graph:

AB AC
|  |
D  E
|  |
F  G
|  |
H  I

The bulk of the call sites an the heap aren't necessarily in a particular order, only the top of the heap, but since it's only ever accessed by popping the top is the only value that really needs to be in the right place.

IBricchi added inline comments.Dec 17 2022, 11:25 AM
llvm/lib/Analysis/InlineOrder.cpp
302 ↗(On Diff #482511)

Do you mean duplication from PriorityInlineOrder?

Most of the duplication is to keep track of InlineHistory, and managing what CallBases are corrently being considered (heap). I'm not sure which parts we would be able to remove.

We could replace the Heap with a vector or set and not worry about the orider but I'm not sure if that's the kind of change you were suggesting.

IBricchi added a comment.EditedJan 16 2023, 4:15 AM

Thanks for the review @hiraditya I've come to realize this patch might not fit well with the other inline-order options. Instead I think it might make more sense to implement the functionality using custom plugins.

I opened a separate PR in this direction https://reviews.llvm.org/D140637. I would appreciate it if you could take a look at that.

IBricchi abandoned this revision.Mar 14 2023, 3:21 AM