RCSP and modulo scheduling

RCSP and modulo scheduling

[David Edelsohn]

	Is RCSP suppose to be a complete solution for software pipelining
or used in conjunction with modulo scheduling?  The GCC IA-64 Wish List
and GCC IA-64 Summit both seem to imply that RCSP is a fallback when
modulo scheduling cannot be applied.  Should both be implemented and work
together for a complete solution?

Thanks, David

Re: RCSP and modulo scheduling

[Vladimir Makarov]

David Edelsohn wrote:
> 
>         Is RCSP suppose to be a complete solution for software pipelining
> or used in conjunction with modulo scheduling?  The GCC IA-64 Wish List
> and GCC IA-64 Summit both seem to imply that RCSP is a fallback when
> modulo scheduling cannot be applied.  Should both be implemented and work
> together for a complete solution?

  I can not decide it alone.  I'd prefer to have only RCSP because
existing RCSP and modulo scheduling in one compiler is not reasonable
because of the code duplication.  I don't know industrial compilers
which implement several software pipelining (or insn scheduling)
methods.   It is too complicated optimization whose effect for the most
programs is negligible.

  I think about possibility to force RCSP work as modulo scheduling for
loops without if-constructions.  But I am not sure I'll be successful
(especial problem is usage of implementation of register rotation).  In
any case it will be not soon.  RCSP also works slower than modulo
scheduling.

  So may be there is a sense to use modulo scheduling for loops without
internal branches and RCSP for loops with them as a temporary solution
(although all temporary solutions aim to be permanent ones).  It would
be definitely worth to do it if we already had modulo scheduling.

Vlad

Re: RCSP and modulo scheduling

[Jim Wilson]

>         Is RCSP suppose to be a complete solution for software pipelining
> or used in conjunction with modulo scheduling?  The GCC IA-64 Wish List
> and GCC IA-64 Summit both seem to imply that RCSP is a fallback when
> modulo scheduling cannot be applied.  Should both be implemented and work
> together for a complete solution?

IA-64 has hardware register rotation which is supported by modulo scheduling
but not RCSP.

RCSP can handle loops containing if statements better than modulo scheduling.
IA-64 has relatively cheap predication support that lets us eliminate if
statements thus allowing modulo scheduling to succeed more often.

There are also a number of other issues to consider, but the main point here
is that the IA-64 architecture was designed assuming the compiler would support
modulo scheduling.  So modulo scheduling is clearly the best choice for an
IA-64 target, but is not necessarily the best choice for other targets.

As for which one is right for gcc, that issue has not been decided yet, and
may not be decided for a long time.

There was a previous thread that discussed some of the issues here.
See for instance...
        http://gcc.gnu.org/ml/gcc/2002-09/msg01263.html

Jim

Re: RCSP and modulo scheduling

[Vladimir N. Makarov]

Jim Wilson wrote:

> >         Is RCSP suppose to be a complete solution for software pipelining
> > or used in conjunction with modulo scheduling?  The GCC IA-64 Wish List
> > and GCC IA-64 Summit both seem to imply that RCSP is a fallback when
> > modulo scheduling cannot be applied.  Should both be implemented and work
> > together for a complete solution?
>
> There was a previous thread that discussed some of the issues here.
> See for instance...
>         http://gcc.gnu.org/ml/gcc/2002-09/msg01263.html
>
>

Just one addition for the message mentioned by Jim:

"  Machine independent implementation of modulo scheduling requires to
use the old or DFA pipeline description.  Unfortunately, the DFA
pipeline hazard recognizer is not good enough to support modulo
scheduling (it needs more interface functions).  But the support could
be provided."

DFA pipeline hazard recognizer could be easily used for modulo scheduling without
the additional support.

To implement modulo scheduling we need to make a union of the state after
instruction issue and the states gotten from the it by advancing the simulated
processor cycle by II * n, where II is the initiation interval and n is 1, 2, 3
and so on.  N could be constrained by a value which results in the state
designating no functional unit reservations.  Actually, we could implement the
union of states as simply a set of the states.  It could be a part of module
scheduling not the pipeline hazard recognizer interface.

It is easy although usually recognizing pipeline hazards for software pipelining
(reservation tables are usually used there) is more complicated than the same
thing for insn scheduling.

Vlad