[LLVMdev] [RFC] Scheduler Rework

[dag at cray.com]

Andrew Trick <atrick at apple.com> writes:

> We plan to move to the MachineScheduler by 3.2. The structure is:

How hard will this be to backport to 3.1?  Has woprk on this started
yet?

> ScheduleDAG: Abstract DAG of SUnits and SDeps
>   |
>   v
> ScheduleDAGInstrs: Build the DAG from MachineInstrs, each SUnit tied to an MI
>                    Delimit the current "region" of code being scheduled.
>   |
>   v
> ScheduleDAGMI: Concrete implementation that supports both top-down and bottom-up scheduling
>                with live interval update. It divides the region into three zones:
>                Top-scheduled, bottom-scheduled, and unscheduled.

So does this happen after SDNodes are converted to MachineInstrs?  It's
not clear to me given your description of ScheduleDAGInstrs.  I assume
it uses the current SDNode->SUnit mechanism but I just want to make
sure.

> 3. New scheduling algorithms can be introduced by implementing new
>    MachineSchedStrategies.  We can add a target hook to select the
>    strategy if needed.

This sounds like what we want and yes, it should be target-selectable.

> There's still plenty of opportunity to restructure the code and add
> customization points. Keep in mind that the goal for the target
> independent code is clarity and maintainability. Code reuse across
> custom schedulers is secondary and I'm not currently thinking of
> designing a template library for custom schedulers.

The two are not contradictory but for me I care less about the specific
structure than I do about the flexibility to mix and match heuristics.
It just struck me that templates and policy classes is the natural way
to do it.

I'm glad to hear the top-down scheduler will get some attention.  We'll
be wanting to use that.

> As much as possible, the standard scheduling algorithm will be built
> from standalone utilities and data structures. The customizations that
> you describe would all be handled by providing a new
> MachineSchedStrategy. 

Makes sense to me.

> Start by composing your scheduler from the pieces that are available,
> e.g.  HazardChecker, RegisterPressure... (There's not much value
> providing a scheduling queue abstraction on top of vector or
> priority_queue).

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.

> 1. Precise register pressure tracking with back off. I'm in the
> process of checking in the pieces for this. It should be usable
> sometime in the next couple of weeks.

Great!

> 2. Division of the target-defined resources into "interlocked"
> vs. "buffered". The HazardChecker will continue to handle the
> interlocks for the resources that the hardware handles in
> order. 

So by "interlocks" you mean hardware-implemented interlocks?  So that
the scheduler will attempt to avoid them.  Not that we have a machine
like this, but what about machines with no interlocks where software is
responsible for correctness (VLIW, early MIPS, etc.)?  I suppose they
can be handled with a similar mechanism but the latter is much more
strict than the former.

> Buffered resources, which the hardware can handle out of order. These
> will be considered separately for scheduling priority. We will also
> make a distinction between minimum and expected operation latency.

Does this mean you want to model the various queues, hardware scheduling
windows, etc.?  I'm just trying to get a clearer idea of what this
means.

> 3. A register pressure reducing scheduler that considers interlocks
> and register pressure. This will prioritize register reuse above the
> pressure limits and include a very simple heuristic for avoiding high
> register pressure situations.
>
> 4. A balanced scheduler that still prioritizes interlocks and register
> pressure limits, but balances buffered resource usage with register
> pressure avoidance.
>
> 5. Improved heuristics. For example, we can precompute register
> lineages and use that information to avoid high register pressure
> situations.

This all sounds great and is exactly what we're looking for.

As I said, this is a time-critical thing for us.  Is there any way I can
help to move this along?

Thanks!

                             -Dave