<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 15, 2014 at 2:26 PM, Chad Rosier <span dir="ltr"><<a href="mailto:mcrosier@codeaurora.org" target="_blank">mcrosier@codeaurora.org</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">> On Mon, Dec 15, 2014 at 9:57 AM, Chad Rosier <<a href="mailto:mcrosier@codeaurora.org">mcrosier@codeaurora.org</a>><br>
> wrote:<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<br>
>> a<br>
>> more complete solution), so I'd like to put a patch together.<br>
><br>
> I think this sounds really cool!<br>
><br>
>> That being<br>
>> said, I have a few questions.<br>
>><br>
>> The current switch lowering code sorts based on case values and is<br>
>> 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<br>
>> a<br>
>> purely tree structure.  Does anyone object or have opinions on this<br>
>> matter?<br>
><br>
> Spontaneously I would have thought the Huffman tree would just replace<br>
> the binary trees, i.e. we'd use the branch probabilities to build the<br>
> tree differently.<br>
<br>
</span>The current implementation selects the pivot in such a way that it optimizes<br>
for lookup tables.</blockquote><div><br></div><div>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.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">  Lowering the binary tree based on branch probabilities<br>
doesn't fit well with this approach.  However, I think we could start by<br>
building a Huffman tree and once we've handled the most heavily weighted<br>
nodes,<br>
we could fall back to the current logic.  Make sense?<br>
<span class=""><br>
> For how many hot cases is a Huffman tree faster than a jump table? I<br>
> suspect we'll still want to build jump tables when we can.<br>
<br>
</span>I take back my previous comment; I agree we should have a hybrid approach,<br>
per my comments above.<br>
<div class="HOEnZb"><div class="h5"><br>
> Thanks,<br>
> Hans<br>
<br>
<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>