How will scheduler take care of modulo scheduling?

How will scheduler take care of modulo scheduling?

[Ritu Sabharwal]

Hi,
   We have done the modulo scheduling and rotating register allocation for 
GCC C compiler for IA64. But we don't know how will gcc'c scheduler and 
register allocator take care of this modulo scheduling and register 
allocation. Do we need to modify the existing scheduler and register 
allocator or need to write our own which considers the modulo scheduling 
and rotating register allocation? If modification is to done, what are 
those modifications and if new scheduler and allocator is to be written,
what is the scheme of doing that?

regards,
Ritu Sabharwal,

Re: How will scheduler take care of modulo scheduling?

[Vladimir Makarov]

Ritu Sabharwal wrote:
> 
> Hi,
>    We have done the modulo scheduling and rotating register allocation for
> GCC C compiler for IA64. But we don't know how will gcc'c scheduler and
> register allocator take care of this modulo scheduling and register
> allocation. Do we need to modify the existing scheduler and register
> allocator or need to write our own which considers the modulo scheduling
> and rotating register allocation? If modification is to done, what are
> those modifications and if new scheduler and allocator is to be written,
> what is the scheme of doing that?
> 

  Writing insn scheduler and register allocator is a bigger work than
modulo scheduling.  So I'd not advice to write own ones especially if
you are novices for gcc.  Because they should work for all gcc
platforms.

  So the simplest approach is to modify them.  It could be done in the
same way as for RCSP (which is not in the public repository yet).  RCSP
puts notes about start and finish of each software pipelining loop.  The
insn scheduler looks at such notes and do nothing for code between the
notes.

  The same idea (it was actually Richard Henderson's idea) could be used
for register allocator.  You could transfer information about registers
used in pipelined loops through notes or in other ways, the register
allocation could not use them for the register allocation.

Vlad

Re: How will scheduler take care of modulo scheduling?

[Jim Wilson]

>   We have done the modulo scheduling and rotating register allocation for 
>GCC C compiler for IA64.

It isn't clear what you have done.  Modify an existing optimization pass?
Add a new optimization pass?  Add it where?  What exactly does this new
code do?

> Do we need to modify the existing scheduler and register 
>allocator or need to write our own which considers the modulo scheduling 
>and rotating register allocation?

We don't have enough info to answer this question.  However, it is a reasonable
assumption that all following optimization passes will perform code transforms
that destroy your modulo scheduled loops unless you do something to protect
them.  Perhaps a new RTL construct that indicates a loop that should be left
untouched because it is already scheduled and register allocated.  Or maybe
this info can go in the CFG.  This won't be very useful unless done very late
in the compiler.  Otherwise we will lose too many other optimizations.

You may still need to perform some operations like reload, and if you do need
any reloads, then that is going to mess up your modulo scheduled loop.  So
you probably need to do something to deal with this problem.

> If modification is to done, what are 
>those modifications and if new scheduler and allocator is to be written,
>what is the scheme of doing that?

I can't even hazard a guess at this.  You will probably have to figure it out
yourself.

Jim

Re: How will scheduler take care of modulo scheduling?

[Ritu Sabharwal]

Hi,
  Please give mne the details of how to modify the existing scheduler to 
incorporate the modulo scheduler. Will thus checking of loop start and 
loop end work fine? Does we nned to consider any timing  constraints for 
this?
  Modulo Scheduler is completed but please tell me the right way of 
integrating this with the insn scheduler.

Best,
Ritu.



On Tue, 10 Dec 2002, Vladimir 
Makarov wrote:

> Ritu Sabharwal wrote:
> > 
> > Hi,
> >    We have done the modulo scheduling and rotating register allocation for
> > GCC C compiler for IA64. But we don't know how will gcc'c scheduler and
> > register allocator take care of this modulo scheduling and register
> > allocation. Do we need to modify the existing scheduler and register
> > allocator or need to write our own which considers the modulo scheduling
> > and rotating register allocation? If modification is to done, what are
> > those modifications and if new scheduler and allocator is to be written,
> > what is the scheme of doing that?
> > 
> 
>   Writing insn scheduler and register allocator is a bigger work than
> modulo scheduling.  So I'd not advice to write own ones especially if
> you are novices for gcc.  Because they should work for all gcc
> platforms.
> 
>   So the simplest approach is to modify them.  It could be done in the
> same way as for RCSP (which is not in the public repository yet).  RCSP
> puts notes about start and finish of each software pipelining loop.  The
> insn scheduler looks at such notes and do nothing for code between the
> notes.
> 
>   The same idea (it was actually Richard Henderson's idea) could be used
> for register allocator.  You could transfer information about registers
> used in pipelined loops through notes or in other ways, the register
> allocation could not use them for the register allocation.
> 
> Vlad
> 

Re: How will scheduler take care of modulo scheduling?

[Vladimir Makarov]

Ritu Sabharwal wrote:
> 
> Hi,
>   Please give mne the details of how to modify the existing scheduler to
> incorporate the modulo scheduler. Will thus checking of loop start and
> loop end work fine? Does we nned to consider any timing  constraints for
> this?
>   Modulo Scheduler is completed but please tell me the right way of
> integrating this with the insn scheduler.
> 

It depends on where you are going to run modulo scheduling (on the 1st
or 2nd insn scheduling).

IMHO, the right approach is to make it on the 2nd insn scheduling
because the compiler could have more accurate information about insns
(because of the insn splitting).  On the other hand, making software
pipelining there requires to implement (partial) register renaming
because the register allocator creates new dependencies and
possibilities to get a better software pipelining are lost.

By the way RCSP and new version of haifa-scheduler (that what I read)
makes software pipelining on the 1st insn scheduling because it is easy
to do there.

So if you do it on the 1st insn scheduling, the haifa-scheduler (on the
1st phase) finds loops and uses them as regions for insn scheduler.  You
could call software pipelining instead of insn scheduler for such
region.  Please see the code in sched-rgn.c.  That is the way how RCSP
and the new haifa scheduler works.

If you do it on the 2nd insn scheduling, you could just check loop start
and loop finish and call insn scheduling only for blocks which are not
in the loops (haifa insn scheduler works only with the basic blocks not
regions on the 2nd insn scheduling).

In any case your modulo scheduling should be machine-independent code
parameterized by processor pipeline description.  Otherwise, I doubts
that the code will be accepted for gcc.

Also it is good idea to make a branch and place the code on the branch. 
Then people could look at this code and comment it.  I think it will be
not easy process if the code was written outside gcc because the
integration of a code written outside gcc is not easy process: gcc has
own style, standards, infrastructure.  For example, integration of
haifa-scheduler (donated by IBM) was not easy process and still not
finished (and on my opinion efforts for this was comparable with writing
a new scheduler from the scratch).

Vlad