[LLVMdev] Pre-RA scheduler details

[Andrew Trick]

On Jul 24, 2013, at 12:17 PM, Chenyang Liu <ctc.liu at gmail.com> wrote:

> Hi,
> 
> I'm interested in the two pre-RA instruction schedulers used in LLVM, list-hybrid and list-ilp. I've done some digging on the internet and played around with executing some test files using the two schedules. However, I'm still uncertain of the behaviors and heuristics used in each.
> 
> For example, the XXXX_ls_rr_sort::isReady for hybrid includes a 3 cycle readydelay (seems arbitrary) whereas the ilp version readies all instructions once data dependencies are resolved.
> 
> Additionally, the ilp_ls_rr_sort::operator() just calls BURRSort at the end after applying a bunch of heuristics to the queue beforehand. Reading it is quite laborious (very few comments) and was wondering if anyone had any references to what exactly it is doing and why it is doing it in such order.
> 
> I'm focused right now on understanding the behavior of the two schedulers. If anyone could give me some direction (papers, slides) that would be greatly appreciated.


To be blunt, those heuristics are ad-hoc at best and can't be justified in any way other than running benchmarks. They were added to avoid pathologically bad scheduling in a few cases, then tuned based on this formula:

list-ilp = do the least damage overall running the test-suite on x86_64
list-hybrid = do the least damage on armv7

Those will both be retired by the MachineScheduler (MI Scheduler).

How to turn it on:
http://article.gmane.org/gmane.comp.compilers.llvm.devel/63242

Other recent messages:
http://article.gmane.org/gmane.comp.compilers.llvm.devel/63747
http://article.gmane.org/gmane.comp.compilers.llvm.devel/64145

Dev mtg BOF:
http://llvm.org/devmtg/2012-11/Larin-Trick-Scheduling.pdf

Information is scattered now between the comments, commit log, and mailing list. A design document is a good idea. I can commit to publishing one as soon as the scheduler is enabled for mainstream architectures.

The design is still evolving. The priority is supporting all targets with a great deal of flexibility and avoiding poor scheduling in strange cases. It's not really about optimal scheduling for some popular benchmarks. Optimal scheduling is very processor specific. The idea is that backend implementers can invest as little or as much effort into pluging in their own scheduling heuristics as makes sense for their project. A rich set of tools is available for them.

Thanks for your interest,

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130724/1866f9e4/attachment.html>