[LLVMdev] Lowering switch statements with PGO

Bob Wilson bob.wilson at apple.com
Mon Dec 15 22:18:23 PST 2014

> On 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.  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?
> Also, is there a way to determine if branch probabilities are based on
> real data or static heuristics?  I assume we'd only want to build a
> Huffman tree if we have real data.  Please correct me if I'm wrong.

That sounds like a mistake to me, and there isn’t a way to do it now regardless. If you’re getting block frequencies via heuristics, I would expect most of the cases to be weighted equally. I don’t remember any static heuristics for switches.

> Comments are very welcome!
> Chad
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

More information about the llvm-dev mailing list