[LLVMdev] Lowering switch statements with PGO
mcrosier at codeaurora.org
Mon Dec 15 14:26:55 PST 2014
> On Mon, Dec 15, 2014 at 9:57 AM, Chad Rosier <mcrosier at codeaurora.org>
>> About two months ago I posted a patch that hoisted the hottest case
>> statement from a switch statement during ISelLowering.
>> See: http://reviews.llvm.org/D5786
>> Sean was rather adamant about using a Huffman tree (and I agree this is
>> more complete solution), so I'd like to put a patch together.
> I think this sounds really cool!
>> That being
>> said, I have a few questions.
>> The current switch lowering code sorts based on case values and is
>> with a combination of binary trees, lookup tables, bit tests and magic.
>> If we lower the switch based on branch probabilities, I think the most
>> reasonable approach would be to disable the lookup tables and stick with
>> purely tree structure. Does anyone object or have opinions on this
> Spontaneously I would have thought the Huffman tree would just replace
> the binary trees, i.e. we'd use the branch probabilities to build the
> tree differently.
The current implementation selects the pivot in such a way that it optimizes
for lookup tables. Lowering the binary tree based on branch probabilities
doesn't fit well with this approach. However, I think we could start by
building a Huffman tree and once we've handled the most heavily weighted
we could fall back to the current logic. Make sense?
> For how many hot cases is a Huffman tree faster than a jump table? I
> suspect we'll still want to build jump tables when we can.
I take back my previous comment; I agree we should have a hybrid approach,
per my comments above.
More information about the llvm-dev