[LLVMdev] Lowering switch statements with PGO

[Sean Silva]

On Mon, Dec 15, 2014 at 1:07 PM, Hans Wennborg <hans at chromium.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.
>
> 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 don't have any data, but I suspect that the relative performance of the
two is highly situation-specific and architecture-specific.

One thing to remember is that a Huffman tree is an *optimal* solution to
the problem that it solves (it is not a heuristic); however, the problem of
switch lowering is not exactly the problem that a Huffman tree solves. So
really we are talking about "how do we model the costs?" (and later "how to
do we optimize over the solution space?") which is a tedious problem.

One place to start might be to determine how much performance a naive
Huffman-based approach leaves on the table (and also *why* it suffers in
particular situations). Maybe just a few special cases on top of a Huffman
tree would give most of the benefit, while still largely retaining the
underlying conceptual simplicity of the Huffman approach (and the model
that it is optimal for).

-- Sean Silva


>
> 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/80fe9879/attachment.html>