[LLVMdev] Lowering switch statements with PGO

[Sean Silva]

On Mon, Dec 15, 2014 at 2:26 PM, Chad Rosier <mcrosier at codeaurora.org>
wrote:
>
> > 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.


This seems like a potential point of friction: for lookup tables (and other
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.

-- 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
> 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
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141215/965cd8a2/attachment.html>