[Analysis] Remove global state from `PluginInline{Advisor,Order}Analysis`. (#114615)

The plugin analysis for `InlineAdvisor` and `InlineOrder` currently
relies on shared global state to keep track

[Analysis] Remove global state from `PluginInline{Advisor,Order}Analysis`. (#114615)

The plugin analysis for `InlineAdvisor` and `InlineOrder` currently
relies on shared global state to keep track if the analysis is
available.
This causes issues when pipelines using plugins and pipelines not using
plugins are run in the same process.
The shared global state can be easily replaced by checking in the given
instance of `ModuleAnalysisManager` if the plugin analysis has been
registered.

show more ...

[InlineOrder] fix the calculation of Cost for CostBenefitPriority (#86630)

getCost() expects that isVariable() is true.
https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Analysis/Inl

[InlineOrder] fix the calculation of Cost for CostBenefitPriority (#86630)

getCost() expects that isVariable() is true.
https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Analysis/InlineCost.h#L146

Co-authored-by: helloguo <helloguo@meta.com>

show more ...

[InlineOrder] Fix InlineOrder erase_if implementation (#78684)

The InlineOrder Heap stores a CallBase ptr and InlineHistoryID pair.
When running the `erase_if` method, InlineHistoryID is always ret

[InlineOrder] Fix InlineOrder erase_if implementation (#78684)

The InlineOrder Heap stores a CallBase ptr and InlineHistoryID pair.
When running the `erase_if` method, InlineHistoryID is always returned
with 0. Instead, we should be retrieving it from the `InlineHistoryMap`
(similar to what is done in the `pop` implementation).

This change is completely harmless because no one is using
InlineHistoryID right now as part of the `erase_if` implementation which
is currently only used in the ModuleInliner.

show more ...

[ModuleInliner] Remove an extraneous pair of std::push_heap and std::pop_heap (NFC) (#69672)

Immediately after the "while" loop in adjust, Heap.back() is
guaranteed to be the highest priority item

[ModuleInliner] Remove an extraneous pair of std::push_heap and std::pop_heap (NFC) (#69672)

Immediately after the "while" loop in adjust, Heap.back() is
guaranteed to be the highest priority item for the current values of
Priorities. std::push_back() at the end of adjust moves the highest
priority item to Heap.front(), but std::pop_heap() in pop moves it
right back to Heap.back().

This roundtrip is wasteful. This patch removes the extraneous pair of
std::push_heap and std::pop_heap. This patch cuts down about 45% of
calls to std::push_heap and std::pop_heap in InlineOrder.cpp while
building clang with FDO+ThinLTO.

Strictly speaking, removing the pair of calls may change the order in
which call sites with identical priorities are removed from the
priority queue, but we do not need to worry about that.

Since the functionality of adjust becomes more like a smart version of
pop_heap, this patch renames adjust to pop_heap_adjust.

show more ...

[ModuleInliner] Update a comment (NFC)

InlinerOrder::front was removed by:

commit d3b95ecc98d204badbffa1840be7b7a06652a0a3
Author: Kazu Hirata <kazu@google.com>
Date: Sun Sep 18 08:49:44 20

[ModuleInliner] Update a comment (NFC)

InlinerOrder::front was removed by:

commit d3b95ecc98d204badbffa1840be7b7a06652a0a3
Author: Kazu Hirata <kazu@google.com>
Date: Sun Sep 18 08:49:44 2022 -0700

This patch removes a mention of front.

show more ...

[ModuleInliner] Use SmallVector::pop_back_val (NFC)

We can use std::pop_heap first and then retrieve the top priority item
with pop_back_val, saving one line of code.

[ModuleInliner] Fix the heap maintenance (#69251)

With expensive checks enabled but without this patch, std::pop_heap
triggers an assertion failure. This is because:

updateAndCheckDecreased(H

[ModuleInliner] Fix the heap maintenance (#69251)

With expensive checks enabled but without this patch, std::pop_heap
triggers an assertion failure. This is because:

updateAndCheckDecreased(Heap.front())

updates the priority associated with Heap.front(), so Heap may no
longer be a valid heap. The libstdc++ version of std::pop_heap
requires that the entire range be a valid heap even though the core
task of std::pop_heap is just to swap the Heap.front() and
Heap.back().

This patch fixes the problem by:

- calling std::pop_heap to swap Heap.front() and Heap.back(),
- updating the priority of Heap.back(), and
- inserting Heap.back() back into the heap.

We could reduce the number of calls to updateAndCheckDecreased or the
number of elements being moved, but I think it's important to fix the
crash first.

Credit to Ivan Kosarev for identifying the problem and Liqiang Tao for
the analysis and initial version of the patch.

show more ...

Fix typo in module inliner priority flag

Change-Id: If4a830fdacf1b0e7b7634f48f648427d5ec7ea21

Reviewed By: kazu, arsenm

Differential Revision: https://reviews.llvm.org/D158013

[InlineOrder] Plugin Inline Order

Adds the ability to load a plugin to control the inline order.
This allows developing and distributing inlining heuristics
outside of tree. And together with the in

[InlineOrder] Plugin Inline Order

Adds the ability to load a plugin to control the inline order.
This allows developing and distributing inlining heuristics
outside of tree. And together with the inline advisor plugins
allows for fine grained control of the inliner.

The PluginInlineOrderAnalysis class serves as the entry point
for dynamic advisors. Plugins must register instances of this
class to provide their own InlineOrder.

Reviewed By: kazu

Differential Revision: https://reviews.llvm.org/D140637

show more ...

Revert "[InlineOrder] Plugin Inline Order"

This commit is causing a CMake error on AIX. Will recommit with
a fix.

This reverts commit e46d8a731535afcf0c5c2a2f6cf3c5d4fb69cd5b.

[InlineOrder] Plugin Inline Order

This allows developing and distributing inlining heuristics
outside of tree. And together with the inline advisor plugins
allows for fine grained control of the inl

[InlineOrder] Plugin Inline Order

This allows developing and distributing inlining heuristics
outside of tree. And together with the inline advisor plugins
allows for fine grained control of the inliner.

The PluginInlineOrderAnalysis class serves as the entry point
for dynamic advisors. Plugins must register instances of this
class to provide their own InlineOrder.

I'm checking in this patch on behalf of ibricchi
<ibricchi@student.ethz.ch>.

Differential Revision: https://reviews.llvm.org/D140637

show more ...

[Analysis] llvm::Optional => std::optional

[ModuleInliner] Add MLPriority

This patch adds MLPriority as the first step toward the ML-based
function inlining with the module inliner.

For now, MLPriority is completely identical to CostPriorit

[ModuleInliner] Add MLPriority

This patch adds MLPriority as the first step toward the ML-based
function inlining with the module inliner.

For now, MLPriority is completely identical to CostPriority.

Once this patch lands, I'm planning to:

- integrate NoInferenceModelRunner,

- memoize the priority computation so that the priority remains the
same for given values of metrics even with the noise injected during
training, and

- port/take more features into account.

Differential Revision: https://reviews.llvm.org/D139140

show more ...

[ModuleInliner] Initialize variables (NFC)

This patch initializes all class variables in InlineOrder.cpp for
safety just in case we miss them in constructors. Currently, all
these variables are pro

[ModuleInliner] Initialize variables (NFC)

This patch initializes all class variables in InlineOrder.cpp for
safety just in case we miss them in constructors. Currently, all
these variables are properly initialized in their respective
constructors.

Differential Revision: https://reviews.llvm.org/D139225

show more ...

[ModuleInliner] Add a cost-benefit-based priority

This patch teaches the module inliner a traversal order designed for
the instrumentation FDO (+ThinLTO) scenario.

The new traversal order prioritiz

[ModuleInliner] Add a cost-benefit-based priority

This patch teaches the module inliner a traversal order designed for
the instrumentation FDO (+ThinLTO) scenario.

The new traversal order prioritizes call sites in the following order:

1. Those call sites that are expected to reduce the caller size

2. Those call sites that have gone through the cost-benefit analaysis

3. The remaining call sites

With this fairly simple traversal order, a large internel benchmark
yields performance comparable to the bottom-up inliner -- both in
terms of the execution performance and .text* sizes.

Big thanks goes to Liqiang Tao for the module inliner infrastructure.

I still have hacks outside this patch to prevent excessively long
compilation or .text* size explosion. I'm trying to come up with
acceptable solutions in near future.

Differential Revision: https://reviews.llvm.org/D134376

show more ...

[ModuleInliner] Factor out common code in InlineOrder.cpp (NFC)

This patch factors out common code in InlineOrder.cpp.

Without this patch, the model is to ask classes like SizePriority and
CostPrio

[ModuleInliner] Factor out common code in InlineOrder.cpp (NFC)

This patch factors out common code in InlineOrder.cpp.

Without this patch, the model is to ask classes like SizePriority and
CostPriority to compare a pair of call sites:

bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {

while these priority classes have their own caches of priorities:

DenseMap<const CallBase *, PriorityT> Priorities;

This model results in a lot of duplicate code like hasLowerPriority
and updateAndCheckDecreased.

This patch changes the model so that priority classes just have two
methods to compute a priority for a given call site and to compare two
previously computed priorities (as opposed to call sites).

Facilities like hasLowerPriority and updateAndCheckDecreased move to
PriorityInlineOrder along with the map from call sites to their
priorities. PriorityInlineOrder becomes a template class so that it
can accommodate different priority classes.

Differential Revision: https://reviews.llvm.org/D134149

show more ...

[ModuleInliner] Capitalize a variable name (NFC)

[ModuleInliner] Remove unused using declarations (NFC)

[ModuleInliner] Move getInlineCostWrapper to an anonymous namespace (NFC)

This patch moves getInlineCostWrapper to an anonymous namespace.
While I am at it, I'm moving the function closer to the beg

[ModuleInliner] Move getInlineCostWrapper to an anonymous namespace (NFC)

This patch moves getInlineCostWrapper to an anonymous namespace.
While I am at it, I'm moving the function closer to the beginning of
the file so that I can use it elsewhere in the file without a forward
declaration.

show more ...

[ModuleInliner] Remove InlineOrder::front (NFC)

InlineOrder::front is a remnant from the era when we had a nested
"while" loops in the module inliner, with the inner one grouping the
call sites with

[ModuleInliner] Remove InlineOrder::front (NFC)

InlineOrder::front is a remnant from the era when we had a nested
"while" loops in the module inliner, with the inner one grouping the
call sites with the same caller.

Now that we have a simple "while" loop draining the priority queue, we
can just use InlineOrder::pop.

Differential Revision: https://reviews.llvm.org/D134121

show more ...

[ModuleInliner] Move UseInlinePriority to InlineOrder.cpp (NFC)

UseInlinePriority specifies the priority function. This patch
simplifies the code by moving UseInlinePriority closer to the actual
co

[ModuleInliner] Move UseInlinePriority to InlineOrder.cpp (NFC)

UseInlinePriority specifies the priority function. This patch
simplifies the code by moving UseInlinePriority closer to the actual
consumer -- the switch statement inside getInlineOrder.

Differential Revision: https://reviews.llvm.org/D134100

show more ...

[Inliner] Retire DefaultInlineOrder (NFC)

DefaultInlineOrder was largely an exercise in generalizing the
traversal order of call sites within the inliner.

Now that the module inliner is starting to

[Inliner] Retire DefaultInlineOrder (NFC)

DefaultInlineOrder was largely an exercise in generalizing the
traversal order of call sites within the inliner.

Now that the module inliner is starting to form its shape, there is no
point in sharing DefaultInlineOrder between the module inliner and the
CGSCC inliner. DefaultInlineOrder and all the other inline orders are
mutually exclusive in the following sense:

- The use of DefaultInlineOrder doesn't make sense in the module
inliner because there is no priority inherent in the order in which
call sites are added to the list of call sites -- SmallVector.

- The use of any other inline order doesn't make sense in the CGSCC
inliner because little prioritization can be done within one CGSCC.

This patch essentially reverts the addition of DefaultInlineOrder so
that the loop structure of Inliner.cpp looks like the state just
before we started working on the module inliner (circa June 2021).

At the same time, ww remove the choice of DefaultInlineOrder from
UseInlinePriority.

Differential Revision: https://reviews.llvm.org/D134080

show more ...

[ModuleInliner] Move InlinePriority and its derived classes to InlineOrder.cpp (NFC)

These classes are referred to only from getInlineOrder in
InlineOrder.cpp. This patch hides the entire class dec

[ModuleInliner] Move InlinePriority and its derived classes to InlineOrder.cpp (NFC)

These classes are referred to only from getInlineOrder in
InlineOrder.cpp. This patch hides the entire class declarations and
definitions in InlineOrder.cpp.

Differential Revision: https://reviews.llvm.org/D134056

show more ...

[llvm][ModuleInliner] Add inline cost priority for module inliner

This patch introduces the inline cost priority into the
module inliner, which uses the same computation as
InlineCost.

Reviewed By:

[llvm][ModuleInliner] Add inline cost priority for module inliner

This patch introduces the inline cost priority into the
module inliner, which uses the same computation as
InlineCost.

Reviewed By: kazu

Differential Revision: https://reviews.llvm.org/D130012

show more ...

[llvm][ModuleInliner] Add inline cost priority for module inliner

This patch introduces the inline cost priority into the
module inliner, which uses the same computation as
InlineCost.

Reviewed By:

[llvm][ModuleInliner] Add inline cost priority for module inliner

This patch introduces the inline cost priority into the
module inliner, which uses the same computation as
InlineCost.

Reviewed By: kazu

Differential Revision: https://reviews.llvm.org/D130012

show more ...