Deprecate and remove old SelectionDAG scheduler

While looking at why some generated code for SPARC was poor, I ran into the fact that the MachineScheduler is not yet enabled by default -- it's opt in for each target. Having a bunch of deprecatedish code around was a bit confusing for newbie me.

So, I suggested on IRC that perhaps it's been long enough by now that any target that hasn't switched over probably isn't actually caring much for the performance of their target. Has the time come to start getting rid of the old SelectionDAG scheduler? I have no pressing *need* to do this, so if the answer is "no", fine. But if it's "yes", I'm willing to do my part for code cleanliness.

(Eric said on IRC that sounded probably a reasonable thing to do but I should ask Andrew first; so cc'd.)

I'd propose to do it in a few steps:

Step 1: Switch defaults, and all in-tree targets away from selectiondag schedulers and to the machine scheduler.

That is, 3 changes:

a) Change enableMachineScheduler() -> true by default, and remove target overrides.

That would change the behavior of the following in-tree targets (resulting in enabling the new scheduler, and implicitly forcing their ScheduleDAG scheduler to Sched::Source):
- ARM (only for some CPUs; others are already using it)
- (Hexagon, only with the non-default -disable-hexagon-misched; I'd remove the option)
- MSP430
- PPC (only for some CPUs; others are already using it)
- SystemZ
- XCore

As part of this, I'd fix tests that fail due to instruction re-orderings, but, I *wouldn't* try to do performance testing of any sort.

The targets from the above list that still use the old code which surprise me are ARM and PPC. However, both also usually seem to return true from enablePostRAScheduler -- maybe they really just want to avoid doing machine scheduling both pre-RA and post-RA, and the fact that it also causes the old selectiondag scheduler to get used is an unintended consequence? (And thus, would actually want enableMachineScheduler() -> false, but with Sched::Source as the selectiondag scheduler?)

b) Change enableMachineSchedDefaultSched() -> true.

Only Hexagon sets that to false currently, with a FIXME near it saying it probably shouldn't. But, that is actually irrelevant, normally, since it uses Sched::Source as its scheduler in any case -- unless an option "-enable-hexagon-sdnode-sched" is passed. I'd remove that option too.

c) Change the default for SchedPreferenceInfo in TargetLoweringBase.cpp to Sched::Source. If everyone also uses enableMachineScheduler() -> true and enableMachineSchedDefaultSched() -> true, this has no effect of course. But just to be clear what the future is, I'd suggest to change it too. :slight_smile:

After this step, out-of-tree targets could still have "enableMachineScheduler()" return false, and call "setSchedulingPreference(Sched::ILP)" (or whatever other option), if they want to keep using the old scheduler after this step, until step 3 happens.

Step 2: Wait for some time to pass, for people to notice performance regressions, or otherwise complain.

Step 3: Delete all the selectiondag scheduling code, the above 3 customization points, and whatever other hooks/apis are dead. Rejoice at the deletion of code!

Does the above sound sane (today is the first time I've actually looked at all this code, so if I've misunderstood something, do let me know!) Is it okay to execute step 1?

Hi James,

From the bird’s-eye view that looks reasonable.
Though you’ll need a replacement for the SDAG scheduler to emit the basic block.


For step 3, I was actually intending to preserve all the existing code which implements the Sched::Source selectiondag scheduler mode (so, yes, it's still technically a "selectiondag scheduler", just a really dumb one, and with no configuration knobs). I'd only propose to remove code which is needed only for the other sdag scheduler modes. I think that actually will remove the majority of the code.

I'd certainly want to avoid needing to write any new code as part of this.

Hi James,

Thanks for sorting out the current defaults for all the targets. Keeping track of which options are enabled by each target, and how that is done is the challenging part of this proposal. I think your plan makes perfect sense and anyone who cares enough about scheduling for their microarchitecture should at least be able to benchmark LLVM test suite themselves and take a look at any regressions.

The only reason that I never pushed for this is that I’m more interested in making SelectionDAG scheduler go away completely. As Quentin pointed out, we need a replacement for it first. The big win will come when MachineScheduler is the only client of the DAG builder, allowing us to greatly simplify and streamline that code.

However, I don’t see SelectionDAG scheduler going away any time in the next year and your plan would have immediate benefits
- Simpler configuration of the backend
- More standardization of the pipeline across targets
- Broader testing of the shared MI passes
- Some of the crazy heuristics in ScheduleDAGRRList could be removed making the code easier to understand.

I’m all for this. Thanks for taking it up!


This thread is of considerable interest to me. Our scheduler was originally coded for LLVM v2.9 using a sub-class of ‘ScheduleDAGInstrs’. I have been aware for some time that the use of ‘MachineSchedStrategy’ had become the preferred approach, and with LLVM v3.6 there were no longer any other supported targets that used the legacy strategy. It has been on my “to do” wish-list to rewrite this sometime, but this thread indicates that it is no longer something desirable, but something essential.

I really admire that the LLVM developer community is willing to refactor and replace older approaches to the compiler with newer and better approaches, and this is what lends great strength to the technology.

But at the moment our target has not yet been upstreamed (that decision has yet to be made) and I have not been able to track the HEAD revision either due to having a tiny team (also on my wish-list). As a result our implementation is diverging from the mainstream with legacy techniques still present. Bit by bit I am trying to “catch up” and bring our target implementation up to date with the current design.

Have you any recommendations for me for:

a. How to still use the legacy scheduler in LLVM v3.7

b. How to best approach transporting a legacy ‘ScheduleDAGInstrs’ based scheduler to the ‘MachineSchedStrategy’ based approach

I need to keep the legacy version working for the immediate future, and to give me breathing space to migrate to the preferred implementation.