<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 15, 2014 at 1:07 PM, Hans Wennborg <span dir="ltr"><<a href="mailto:hans@chromium.org" target="_blank">hans@chromium.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>> 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 a<br>
> more complete solution), so I'd like to put a patch together.<br>
<br>
</span>I think this sounds really cool!<br>
<span class=""><br>
> 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>
</span>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>
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></blockquote><div><br></div><div>I don't have any data, but I suspect that the relative performance of the two is highly situation-specific and architecture-specific.</div><div><br></div><div>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.</div><div><br></div><div>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).</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">
<br>
Thanks,<br>
Hans<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>
</blockquote></div></div></div>