Page MenuHomePhabricator

[Inline-cost] Teach cost function to account for accumulative code-size growth
AbandonedPublic

Authored by dnsampaio on Aug 14 2018, 6:57 AM.

Details

Summary

The current Inline-cost function does not take into account the accumulative code size growth of inlining calls to the same function multiple times.
If N function calls to a function are inlined, each increasing size by I, the accumulative code growth is N * I.
If the callee has local linkage, then we give it a bonus, as the function can be eliminated by the number of instruction in the function.

Diff Detail

Event Timeline

dnsampaio created this revision.Aug 14 2018, 6:57 AM
lebedev.ri added inline comments.
test/Transforms/Inline/InlineGrowthCost.ll
2–3

Can't you just use FileCheck?

dnsampaio updated this revision to Diff 160604.Aug 14 2018, 8:50 AM
dnsampaio marked an inline comment as done.

Using FileCheck in test file.

greened added inline comments.Aug 14 2018, 9:20 AM
lib/Analysis/InlineCost.cpp
1908

S - (N*X) doesn't match what the comment message says and doesn't make sense to me in this context. If N is large enough, this says the growth could become negative.

1913

This assumes all uses are inlined. That seems overly pessimistic. I'm not sure it's wise to predict what the inliner will do in the cost model. It seems like an incremental cost would be better. The inliner would then do the cost analysis for each inlining opportunity and decide on a case-by-case basis whether to inline or not. As written, this seems to have the cost model driving inline decisions (inline everything or nothing) rather than the inliner using cost information to make decisions.

dnsampaio added inline comments.Aug 14 2018, 9:43 AM
lib/Analysis/InlineCost.cpp
1908

Indeed the comment wrong. It should be (N*X). Will fix it.

The stipulated growth is N * (NumberOfInstrucions - NumberOfSimplifiedInstructions), where the last is expected, due the previous analysis. Yes, it is a pessimistic assumption, but with such a small threshold, is quite effective.

If the function has local linkage, then the expected growth might be negative, as the function will be eliminated, and the cost would actually be (N*X)-S.

1913

The cost-function analysis using -Oz are not that complex. It only considers each of the instructions (if they can be simplified if inlined), arguments passed and a constant cost for the call site. And see that it is incremental already. The additional cost decreases each time the function is inlined, that is, N reduces. The first one has the higher penalty, the last ones the higher benefit. Not counting the last one that gains huge bonus already.

dnsampaio updated this revision to Diff 160620.Aug 14 2018, 9:50 AM

Fixed comment explaining the elaborated growth cost-function.

eraman added inline comments.Aug 14 2018, 2:22 PM
lib/Analysis/InlineCost.cpp
286

Turning on ComputeFullInlineCost can lead to excessive compile time for pathological cases. It changes the cost to analyze a function F from O(1) [the constant here depends on inline threshold] to O(size of F) and will particularly be bad for Oz because the threshold is low to start with.

1913

The cost of a callee depends on the callsite so multiplying the cost for one callsite by number of uses is not very meaningful.

greened added inline comments.Aug 22 2018, 1:45 PM
lib/Analysis/InlineCost.cpp
1913

It seems weird to have the cost decrease as inlining is done. I understand that's what happens given the current formulation, but I'm not sure the current formulation is correct. The cost of a single inline operation isn't N*X but rather X. By calculating the cost as N*X the code is assuming all calls to the function are inlined.

dnsampaio abandoned this revision.Dec 28 2018, 9:31 AM