[LLVMdev] [RFC] Scheduler Rework

[dag at cray.com]

Andrew Trick <atrick at apple.com> writes:

>     How hard will this be to backport to 3.1?  Has woprk on this started
>     yet?
>
> In my previous message I outlined the steps that I would take to bring up the new scheduler. I'm about to checkin the register pressure reducing
> scheduler. The next step will be plugging in the target itinerary.

Ok, but that doesn't really answer the question.  Do you have a feel for
whether this can be backported relatively easily?

> Machine scheduling occurs in the vicinity of register allocation. It uses the existing MachineInstr->SUnit mechanism.

I'm not familiar with this mechanism.  I thought that after
ISel/ScheduleDAG we no longer have SUnits.

>     ...
>     I'm glad to hear the top-down scheduler will get some attention.  We'll
>     be wanting to use that.
>
> Out of curiosity what about top-down works better for your target?

It's easier to analyze certain constructs for heuristic purposes.  For
example, I posted a while back about the problem that the current
scheduler moves calls around.  It's easier to schedule those "in the
right place" if you don't have to look back through chains to find them.

The problem with bottom-up schedulers in general is that if you need
some node to be scheduled in a certain spot, you have to make sure all
its uses are scheduled "early" (that is, late in the static schedule) so
you can even _see_ the node that might cause a problem (like a call).
You don't know you have a potential problem until you've already
scheduled a bunch of stuff in the wrong place.  With a top-down
scheduler you can see problem nodes earlier.

>     What do you mean by this last point?  We absolutely want to be able to
>     swap out different queue implementations.  There is a significant
>     compile time tradeoff to be made here.
>
> Use whatever data structure you like for your queue. I don't have
> plans to make a reusable one yet. They're not complicated.

That's fine but there have to be some hooks to plug in a different data
structure.

> I do intend to allow a target to identify arbitrary categories of
> resources, how many are available in each cycle on average, and
> indicate which resources are used by an operation. I'll initially
> piggyback on the existing functional units to avoid rewriting target
> itineraries.

Ok.

> As far as the scheduler, pieces are starting to fall into
> place. People are starting to use those pieces and contribute. This is
> a pluggable pass, so there's no reason you can't develop your own
> machine scheduler in parallel and gradually take advantage of features
> as I add them. 

That's a bit disappointing.  It sounds like a lot of throwaway work.  I
understand it's a work in progress.  I'll take a look at what's there
and see where I might be of some help.

> Please expect to do a little code copy-pasting into your target until
> the infrastructure is mature enough to expose more target
> interfaces. I'm not going to waste time redesigning APIs until we have
> working components.

Which APIs are you talking about?

> It would be very useful to have people testing new features, finding
> bugs early, and hopefully fixing those bugs. I would also like people
> to give me interesting bits of code with performance issues that can
> work as test cases. That's hard if I can't run your target.

We just use x86, so you can almost certainly run it.  But to do testing
I'll need something I can backport to 3.1.  We can't afford to develop
against buggy trunk.  We have to work off a release.

                            -Dave