[LLVMdev] Lowering switch statements with PGO
mcrosier at codeaurora.org
Mon Dec 15 09:57:48 PST 2014
About two months ago I posted a patch that hoisted the hottest case
statement from a switch statement during ISelLowering.
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
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.
Comments are very welcome!
More information about the llvm-dev