[LLVMdev] Lowering switch statements with PGO

[Chad Rosier]

> On Mon, Dec 15, 2014 at 9:57 AM, Chad Rosier <mcrosier at codeaurora.org>
> wrote:
>> All,
>> 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
>> a
>> 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
>> lowered
>> 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
>> a
>> purely tree structure.  Does anyone object or have opinions on this
>> matter?
>
> 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
nodes,
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.

> Thanks,
> Hans