This is an archive of the discontinued LLVM Phabricator instance.

[Inliner] Remove incorrect early exit during switch cost computation
ClosedPublic

Authored by tejohnson on Sep 18 2019, 9:25 AM.

Details

Summary

The CallAnalyzer::visitSwitchInst has an early exit when the estimated
lower bound of the switch cost will put the overall cost of the inline
above the threshold. However, this code is not correctly estimating the
lower bound for switches that can be transformed into bit tests, leading
to unnecessary lost inlines, and also differing behavior with
optimization remarks enabled.

First, the early exit is controlled by whether ComputeFullInlineCost is
enabled or not, and that in turn is disabled by default but enabled when
enabling -pass-remarks=missed. This by itself wouldn't lead to a
problem, except that as described below, the lower bound can be above
the real lower bound, so we can sometimes get different inline decisions
with inline remarks enabled, which is problematic.

The early exit was added in along with a new switch cost model in D31085.
The reason why this early exit was added is due to a concern one reviewer
raised about compile time for large switches:
https://reviews.llvm.org/D31085?id=94559#inline-276200

However, the code just below there calls
getEstimatedNumberOfCaseClusters, which in turn immediately calls
BasicTTIImpl getEstimatedNumberOfCaseClusters, which in the worst case
does a linear scan of the cases to get the high and low values. The
bit test handling in particular is guarded by whether the number of
cases fits into the max bit width. There is no suggestion that anyone
measured a compile time issue, it appears to be theoretical.

The problem is that the reviewer's comment about the lower bound
calculation is incorrect, specifically in the case of a switch that can
be lowered to a bit test. This isn't followed up on the comment
thread, but the author does add a FIXME to that effect above the early
exit added when they subsequently revised the patch.

As a result, we were incorrectly early exiting and not inlining
functions with switch statements that would be lowered to bit tests in
cases where we were nearing the threshold. Combined with the fact that
this early exit was skipped with opt remarks enabled, this caused
different inlining decisions to be made when -pass-remarks=missed is
enabled to debug the missing inline.

Remove the early exit for the above reasons.

I also copied over an existing AArch64 inlining test to X86, and
adjusted the threshold so that the bit test inline only occurs with the
fix in this patch.

Diff Detail

Event Timeline

tejohnson created this revision.Sep 18 2019, 9:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 18 2019, 9:25 AM

Is any compile time impact witnessed?

Is any compile time impact witnessed?

I measured overall compile time and the InlinerPass times from -ftime-report for 3 large files with and without this patch, and compared the averages of 10 runs each. There was no significant change in either metric for any of the files.

davidxl accepted this revision.Sep 20 2019, 2:12 PM

lgtm

This revision is now accepted and ready to land.Sep 20 2019, 2:12 PM
This revision was automatically updated to reflect the committed changes.