[LLVMdev] [llvm-commits] Bottom-Up Scheduling?

[Andrew Trick]

Sergei,

I would say that each target has its own scheduling strategy that has changed considerably over time. We try to maximize code reuse across targets, but it's not easy and done ad hoc. The result is confusing code that makes it difficult to understand the strategy for any particular target.

The right thing to do is:
1) Make it as easy as possible to understand how scheduling works for each of the primary targets (x86 and ARM) independent of each other.
2) Make it easy for very similar targets to piggyback on one of those implementations, without having to worry about other targets
3) Allow dissimilar targets (e.g. VLIW) to completely bypass the scheduler used by other targets and reuse only nicely self-contained parts of the framework, such as the DAG builder and individual machine description features.

We've recently moved further from this ideal scenario in that we're now forcing targets to implement the bottom-up selection dag scheduler. This is not really so bad, because you can revert to "source order" scheduling, -pre-RA-sched=source, and you don't need to implement many target hooks. It burns compile time for no good reason, but you can probably live with it. Then you're free to implement your own MI-level scheduler.

The next step in making it easier to maintain an llvm scheduler for "interesting" targets is to build an MI-level scheduling framework and move at least one of the primary targets to this framework so it's well supported. This would separate the nasty issues of serializing the selection DAG from the challenge of microarchitecture-level scheduling, and provide a suitable place to inject your own scheduling algorithm. It's easier to implement a scheduler when starting from a valid instruction sequence  where all dependencies are resolved and no register interferences exit.

To answer your question, there's no clear way to describe the current overall scheduling strategy. For now, you'll need to ask porting questions on llvm-dev. Maybe someone who's faced a similar problem will have a good suggestion. We do want to improve that situation and we intend to do that by first providing a new scheduler framework. When we get to that point, I'll be sure that the new direction can work for you and is easy to understand. All I can say now is that the new design will allow a target to compose a preRA scheduler from an MI-level framework combined with target-specific logic for selecting the optimal instruction order. I don't see any point in imposing a generic scheduling algorithm across all targets.

-Andy

On Nov 29, 2011, at 11:20 AM, Sergei Larin wrote:

> 
> Andy, 
> 
>  Is there any good info/docs on scheduling strategy in LLVM? As I was
> complaining to you at the LLVM meeting, I end up reverse engineering/double
> guessing more than I would like to... This thread shows that I am not
> exactly alone in this... Thanks. 
> 
> Sergei Larin
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> 
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
> Behalf Of Andrew Trick
> Sent: Tuesday, November 29, 2011 11:48 AM
> To: Hal Finkel
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] [llvm-commits] Bottom-Up Scheduling?
> 
> ARM can reuse all the default scoreboard hazard recognizer logic such as
> recede cycle (naturally since its the primary client). If you can do the
> same with PPC that's great. 
> 
> Andy
> 
> On Nov 29, 2011, at 8:51 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
>>> Thanks! Since I have to change PPCHazardRecognizer for bottom-up support
>>> anyway, is there any reason not to have it derive from
>>> ScoreboardHazardRecognizer at this point? It looks like the custom
>>> bundling logic could be implemented on top of the scoreboard recognizer
>>> (that seems similar to what ARM's recognizer is doing).
>> 
>> Also, how does the ARM hazard recognizer get away with not implementing
>> RecedeCycle?
>> 
>> Thanks again,
>> Hal
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>