[LLVMdev] Lowering switch statements with PGO
mcrosier at codeaurora.org
Tue Dec 16 07:23:22 PST 2014
> On Mon, Dec 15, 2014 at 2:26 PM, Chad Rosier <mcrosier at codeaurora.org>
>> > 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
>> >> 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
>> >> If we lower the switch based on branch probabilities, I think the
>> >> reasonable approach would be to disable the lookup tables and stick
>> >> 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
>> for lookup tables.
> This seems like a potential point of friction: for lookup tables (and
> techniques) you want to inherently keep the cases sorted by their values,
> but a Huffman tree does not care about the actual values; it only cares
> about their relative probabilities.
Exactly! I can think of lots of ways to deal with this "friction", but
none of them sit well. As you mentioned, building a Huffman tree and then
dealing with corner cases would be one approach. Another, which was
Owen's suggestion, would be to peel the hot cases and then fall-back to
the current logic.
> -- Sean Silva
>> 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
>> per my comments above.
>> > Thanks,
>> > Hans
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev