[LLVMdev] Lowering switch statements with PGO

[Sean Silva]

On Mon, Dec 15, 2014 at 10:18 PM, Bob Wilson <bob.wilson at apple.com> wrote:
>
>
> > 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.
>

I would expect that any good algorithm for PGO lowering would be good for
non-PGO if you set all probabilities to 0. We technically aren't really
interested in probabilities, but something more like "amount of observed
occurrence" (the term "probability" implies that the union of all the
probabilities must exhaust the entire space of possibilities; obviously not
true if the every case is 0 "probability"). The input to the PGO lowering
is more generally just a set of observations or a sample of observations,
so it must make sense to have all cases with 0 "amount of observed
occurrence".

E.g. you may be looking at pc samples and looking at how often your PC
sample lands in the text of a particular case. When we do PGO lowering, we
do "have data" on that switch, even if we collect no samples in it (in the
same sense that an empty vector "contains" 0 elements). However, we could
just as easily have perhaps gotten one sample in the switch by luck. It
seems very prone to issues to have a discontinuity in our lowering strategy
(i.e. in PGO codegen, treating "no samples" as "doesn't have PGO data and
so needs a different lowering strategy") based on a continuous factor like
the statistical sense in which we might pick up samples for a particular
switch.

-- Sean Silva


>
> >
> > 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
>
>
> _______________________________________________
> 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/20141218/a205022b/attachment.html>