[LLVMdev] Scheduler Roadmap

[Andrew Trick]

On May 9, 2012, at 8:34 AM, dag at cray.com wrote:

> Andrew Trick <atrick at apple.com> writes:
> 
>>> When I asked about enhancing scheduler heuristics a month or so ago, I
>>> got a response about a MachineInstr scheduler and that that was the way
>>> of the LLVM future.  Is that so?  Is the ScheduleDAG going away?
>> 
>> You sent a lengthy RFC on Apr 20 that demonstrated you aren't
>> following developments on trunk. That's perfectly fine, but if you
>> want to use the new scheduler before it is mature, you'll need to
>> follow trunk.
> 
> Ok, but that doesn't answer the question.  Is SchedulerDAG going away?
> If so, what's the timeframe for that?  3.2?

SchedulerDAG is used for both SD scheduling and MI scheduling. It's not going away.

SD scheduling is not going away in 3.2--it will be the first release with MI scheduling on by default.

If all goes well, I expect SD scheduling to be removed by 3.3. That has not been discussed.

Consider this the preliminary announcement. I'll post another announcement as soon as we have something that's more broadly interesting. In the current state it's only interesting for someone just beginning to write their own custom scheduler.

Here's a more complete list of the implementation steps, but the real effort will be spent in performance analysis required before flipping the switch. Don't expect it to be an adequate replacement out-of-box for your benchmarks before 3.2.

- Target pass configuration: DONE
- MachineScheduler pass framework: DONE
- MI Scheduling DAG: DONE
- AliasAnalysis aware DAG option: In review (Sergei)
- Bidirectional list scheduling: DONE
- LiveInterval Update: WIP (simple instruction reordering is supported)
- Target-independent precise modeling of register pressure: DONE
- Register pressure reduction scheduler: WIP
- Support for existing HazardChecker plugin
- New target description feature: buffered resources
- Modeling min latency, expected latency, and resources constraints
- Heuristics that balance interlocks, regpressure, latency and buffered resources

For targets where scheduling is critical, I encourage developers who stay in sync with trunk to write their own target-specific scheduler based on the pieces that are already available. Hexagon developers are doing this now. The LLVM toolkit for scheduling is all there--not perfect, but ready for developers.

- Pluggable MachineScheduler pass
- Scheduling DAG
- LiveInterval Update
- RegisterPressure tracking
- InstructionItinerary and HazardChecker (to be extended)

If you would simply like improved X86 scheduling without rolling your own, then providing feedback and test cases is useful so we can incorporate improvements into the standard scheduler while it's being developed.

>> Feel free to use the patch and send your thanks to Hal. It doesn't
>> serve any purpose to mainline a partial solution only to replace it
>> before it can ever be enabled by default, which would require a major
>> performance investigation and introduces a huge risk (AliasAnalysis in
>> CodeGen has not be well tested).
> 
> Er, but as I understand it the MachineInstr scheduler will also use
> alias analysis.

AliasAnalysis is important. We want it fully supported and enabled by default, but that requires effort beyond simply enabling it. Today, that effort is in the MI scheduler.

>> The last thing we want to do is duplicate what's already planned
> to happen.


The information I provided above is the best I can do, and as early as I could provide this level of detail. If you follow trunk, you can see the direction things are heading, but until recently I would not have been able to tell you "plans" in the form of dates or release goals.

-Andy