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

[Andrew Trick]

On Nov 30, 2011, at 9:11 AM, Sergei Larin wrote:

>> 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.
> [Larin, Sergei] 
>  I am not 100% sure about this statement, but as I get closer to
> re-implementing my scheduler I might grasp a better picture.

One thing that would be nice to have ASAP is a SelectionDAG serialization pass that satisfies dependencies and physical register interferences, while preserving IR instruction whenever possible. This should be totally separate from from the SelectionDAG scheduler. It should not work on SUnits.

I realize this is quite disjoint from the work needed to port a new target. I'm just pointing out that it would be a welcome feature.

If we had that pass, I could tell you that it would be fairly straightforward to reenable the top-down SD scheduler. At this point, since you'd rather scheduler MI's anyway, you may choose to focus on that strategy instead.

>> 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.
> 
> 
> [Larin, Sergei] 
>  Agree, and my whole point is that it needs to be done with preceding
> public discussion, and not de-facto with code drops.

It will be an incremental process. I'm not going to design a complete scheduling framework for all microarchitectures "on paper" before making any changes. Design decisions will be deferred as late as they can be without holding up progress. You'll know when they're being made and have the opportunity to influence them. In fact, any new design will be strongly influenced by the scheduler work that you and others have done recently.

I think you're reacting to the recent dropping of preRA top-down scheduling without public discussion. As you know it was not part of a planned strategy, and not a desirable outcome for anyone. The fact is that we couldn't wait to fix an existing design flaw in DAG serialization. The bottom-up scheduler has the ability to overcome this problem, but implementing a fix that doesn't require running the bottom-up scheduler requires significant work. The right thing to do is to implement SD serialization pass I mentioned above. That solution would be preferable to everyone, but someone needs make the investment.

Of course, anyone is welcome to fix the existing top-down scheduler as well. It requires implementing the inverse of the bottom-up scheduler's physical register tracking, see LiveRegDefs, plus some really hairy logic for resolving interferences that the SelectionDAG builder has created. 

FWIW, we're not going to run into this issue with the MI scheduling framework that I'm referring to because no part of it will be imposed on any targets.

>> 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
> 
> [Larin, Sergei] 
> Any clue on time frame?

2012 :)

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111130/10e6f6ff/attachment.html>