<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 15, 2014 at 10:18 PM, Bob Wilson <span dir="ltr"><<a href="mailto:bob.wilson@apple.com" target="_blank">bob.wilson@apple.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class=""><div class="h5"><br>
> On Dec 15, 2014, at 9:57 AM, Chad Rosier <<a href="mailto:mcrosier@codeaurora.org">mcrosier@codeaurora.org</a>> wrote:<br>
><br>
> All,<br>
> About two months ago I posted a patch that hoisted the hottest case<br>
> statement from a switch statement during ISelLowering.<br>
><br>
> See: <a href="http://reviews.llvm.org/D5786" target="_blank">http://reviews.llvm.org/D5786</a><br>
><br>
> Sean was rather adamant about using a Huffman tree (and I agree this is a<br>
> more complete solution), so I'd like to put a patch together.  That being<br>
> said, I have a few questions.<br>
><br>
> The current switch lowering code sorts based on case values and is lowered<br>
> with a combination of binary trees, lookup tables, bit tests and magic.<br>
> If we lower the switch based on branch probabilities, I think the most<br>
> reasonable approach would be to disable the lookup tables and stick with a<br>
> purely tree structure.  Does anyone object or have opinions on this<br>
> matter?<br>
><br>
> Also, is there a way to determine if branch probabilities are based on<br>
> real data or static heuristics?  I assume we'd only want to build a<br>
> Huffman tree if we have real data.  Please correct me if I'm wrong.<br>
<br>
</div></div>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.<br></blockquote><div><br></div><div>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".</div><div><br></div><div>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.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span class="im"><br>
><br>
> Comments are very welcome!<br>
><br>
> Chad<br>
><br>
><br>
</span><div class=""><div class="h5">> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div></div></blockquote></div></div></div>