Combined top-down and bottom-up instruction scheduler

[Jeff Law]

On 09/08/2015 01:24 PM, Aditya K wrote:
>
>
> ----------------------------------------
>> Subject: Re: Combined top-down and bottom-up instruction scheduler
>> To: hiraditya@msn.com; gcc@gcc.gnu.org
>> CC: vmakarov@redhat.com
>> From: law@redhat.com
>> Date: Tue, 8 Sep 2015 12:51:24 -0600
>>
>> On 09/08/2015 12:39 PM, Aditya K wrote:
>>> IIUC, in the haifa-sched.c, the default scheduling algorithm seems to
>>> be top-down (before reload). Is there a way to schedule the other way
>>> (bottom up), or both ways?
>> Not that I'm aware of. Note that region scheduling allows insns to move
>> between basic blocks to help fill the bubbles that can occur at the end
>> of a block.
>>
>>>
>>> As a use case for bottom-up or some other heuristic: Currently, the
>>> first priority in the selection is given to the longest path, in some
>>> cases this may produce code with stalls at the end of the basic
>>> block. Whereas in the case of combined top-down + bottom-up
>>> scheduling we would end up having stalls in the middle of the basic
>>> block.
>> GCC's original scheduler worked bottom-up until ~1997. IBM Haifa's work
>> turned it into a top-down model and was a small, but clear improvement.
>>
>> There's certainly better things that can be done than strictly top-down
>> or bottom-up, but revamping the scheduler again hasn't been seen as a
>> major win for the most common processors GCC targets these days. Thus
>> it hasn't been a significant area of focus.
>
> Do you have pointers on places to look for if I want to explore bottom-up, or maybe a combination of the two.
>
Not immediately handy.  I'd comb through PLDI through the 1990s and 
early 2000s and possibly Morgan's compiler book.

jeff