On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
> Hello.
>
> After some discussions with Honza, I've decided to convert current code in
> stmt.c that
> is responsible for switch expansion. More precisely, I would like to convert
> the code
> to expand gswitch statements on tree level. Currently the newly created pass
> is executed
> at the end of tree optimizations.
Hah, something I promissed myself (and others) to do years ago! Thanks
thanks thanks! :-)
The end of the gimple optimizations is seems late for the lowering.
Before there were gimple optimizations, switch lowering was part of
the first compiler pass (to generate RTL from the front end) *before*
all code transformation passes ("optimizations" ;-). Because the
lowering of switch statements was rewritten as a gimple lowering pass,
it now runs *after* optimizations. But to be honest, I can't think of
any optimization opportunities exposed by lowering earlier than at the
end of gimple optimizations. Years ago there was some RTL jump
threading still done after lowering of small switch statements, but I
can't find the related PRs anymore.
> My plan for future is to inspire in [1] and come up with some more
> sophisticated switch
> expansions. For that I've been working on a paper where I'll summarize
> statistics based
> on what I've collected in openSUSE distribution with specially instrumented
> GCC. If I'll be
> happy I can also fit in to schedule of this year's Cauldron with a talk.
Sayle's paper is a good starting point. Also interesting:
http://llvm.org/devmtg/2017-02-04/Efficient-clustering-of-case-statements-for-indirect-branch-prediction.pdf
About adjusting the size of jump tables to the capabilities of the CPU
branch predictor. Mixed results but something to consider.
Kannan & Proebsting, "CORRECTION TO ‘PRODUCING GOOD CODE FOR THE CASE
STATEMENT’"
About finding "clusers" of given density within the target values of
the switch statement. The clustering algorithm as presented is N^2 in
the number of case labels, but the idea is interesting and a
simplified, cheaper approach may be possible. This is already used in
LLVM, it seems.
The real challenge will be to figure out how to pick from all these
different approaches the right ones to lower a single switch
statement.
Ciao!
Steven
