[LLVMdev] Lowering switch statements with PGO

[Hans Wennborg]

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.

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.

Thanks,
Hans