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. Comments are very welcome! Chad
> On Dec 15, 2014, at 9:57 AM, Chad Rosier <mcrosier at codeaurora.org> wrote: > > > 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?If one case strongly dominates the others, and there are still a large number of unlikely cases, it seems like it would be a good idea to do a branch for the hot case, and then a lookup table for the cold cases. More generally, it makes intuitive sense to me that this kind of switch-peeling is naturally recursive, and we should allow the existing heuristics to fire each time we peel out cases. —Owen -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141215/e91b47c3/attachment.html>
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. Thanks, Hans
> 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.The current implementation selects the pivot in such a way that it optimizes for lookup tables. Lowering the binary tree based on branch probabilities doesn't fit well with this approach. However, I think we could start by building a Huffman tree and once we've handled the most heavily weighted nodes, we could fall back to the current logic. Make sense?> 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 take back my previous comment; I agree we should have a hybrid approach, per my comments above.> Thanks, > Hans
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>
> 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.> > 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
(this is a total side-note) On Mon, Dec 15, 2014 at 10:18 PM, Bob Wilson <bob.wilson at apple.com> wrote:> I don’t remember any static heuristics for switches.We should probably bias slightly toward a single case for switches where one dominates the value range space of the input, and that one doesn't have some other heuristic (such as we provide for an unreachable-terminated block) applied to it. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141218/ee2bab2b/attachment.html>
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>