[LLVMdev] Proposal for new Legalization framework

[Dan Gohman]

On Thu, Apr 25, 2013 at 6:46 AM, Krzysztof Parzyszek <
kparzysz at codeaurora.org> wrote:

> On 4/24/2013 8:05 PM, Nadav Rotem wrote:
>
>>
>> Everything. This includes all of the custom lowering code for all of the
>> targets, all of dagcombine, and maybe all of the patterns in the TD files.
>>
>
> 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?


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.

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.

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.

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.

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.

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.

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.

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130425/2c3ce71f/attachment.html>