<div dir="ltr">On Thu, Apr 25, 2013 at 6:46 AM, Krzysztof Parzyszek <span dir="ltr"><<a href="mailto:kparzysz@codeaurora.org" target="_blank">kparzysz@codeaurora.org</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On 4/24/2013 8:05 PM, Nadav Rotem wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Everything. This includes all of the custom lowering code for all of the<br>
targets, all of dagcombine, and maybe all of the patterns in the TD files.<br>
</blockquote>
<br></div>
I may have missed the discussion, but why are we trying to move away from the SelectionDAG?  Are there specific problems that we don't want to fix or live with?  If so, what are they?</blockquote><div><br></div><div style>
The non-sequential representation is interesting. It's what first got me interested in working on SelectionDAG. I find it useful to think about programs as dependence graphs, and having that be the actual representation is really cool. However, the only thing the SelectionDAG infrastructure actually does that really takes advantage of this in a meaningful way is scheduling (this is a somewhat simplified explanation). And, it turns out that one of the premises of the non-sequential approach was the idea that the scheduler would eventually be so good that the user's original schedule would be completely irrelevant. In reality, keeping the user's original schedule around has actually proved to be quite practical. SelectionDAG has since grown the ability to annotate nodes with an ordering, but it's awkward because it has to live all the way through legalization and instruction selection.</div>
<div style><br></div><div style>Also, the non-sequential representation has other downsides. Sequential representations have builtin topological orderings which are usually easy to maintain, so they're always available. SelectionDAG has to recompute topological orderings numerous times and use worklists. In comparison, the LLVM IR legalize patch I attached at the beginning of this thread doesn't need a worklist or a sort; it just walks down the instructions in each block, which is handy.</div>
<div style><br></div><div style>Another reason why people don't like SelectionDAG framework is that it's slow. It's effectively one big pass (with several subpasses), and it consistently scores among the top of the compile time profiles. At one time, I did a bunch of work to try to make it faster, though I don't think I did all the right things. I think there are still several opportunities to speed it up significantly. However, some of the problems are pretty fundamental. For example, the continuous-CSE, which automatically eliminates equivalent nodes at all times (except in special cases), is something that costs a lot, and it creates a fair amount of complexity because it has a habit of zapping nodes out from underneath people, and it isn't obviously better than just having simple discrete CSE passes.</div>
<div style><br></div><div style>Another reason is that SelectionDAG is limited to one basic block at a time. The idea of whole-function SelectionDAGs, or even just SEME SelectionDAGs, has been tossed around a lot over the years. However one of the big things stopping this idea is the slowness. One big SelectionDAG wouldn't have any big reason to be significantly faster than lots of little ones, and it could easily be a lot slower.</div>
<div style><br></div><div style>Another is SelectionDAG's relationship with the notoriously developer-hostile tablegen-based instruction-selection process. Those people may not realize that getting rid of SelectionDAG won't necessarily get rid of tablegen-generated instruction selectors, however that's another story.</div>
<div style><br></div><div style>Another is that many parts of SelectionDAG were never really designed, but rather just emerged over a long period of evolution. Things like Glue, which was a hack to work around limitations which mostly no longer exist, but which then grew to become used for a variety of things, simply because it was there. Or the calling-convention lowering code, which has remnants of about three different attempts at frameworks which each had good ideas but were ultimately insufficient in their own ways but never got fully replaced.</div>
<div style><br></div><div style>Ultimately, the SelectionDAG is unloved today is it's unloved. It really needs some stiff refactoring. And optimization. And better documentation. And better developer tools. But with all the other problems, the zeitgeist has turned against it.</div>
<div style><br></div><div style>Dan</div><div style><br></div></div></div></div>