Propagating loop carried memory dependancies to SMS

[Mostafa Hagog <MUSTAFA at il dot ibm dot com>]

There have been lately a discussion on the GCC mailing list and other
forums about the efficiency of SMS (the current implementation of software
pipelining in GCC).  One of the issues that currently limit SMS is the lack
of loop carried memory dependency information.  The long term solution for
this is to propagate alias information from tree level down to RTL level
and then through the RTL passes.  After we have the alias info we perform a
data reference analysis inside loops in RTL level and get the dependence
information.  This infrastructure is important since other optimizations
can gain from it.  However, there is another (short-term) way that we can
follow to improve the loop carried memory dependence information in SMS.
The main Idea in this approach (which was raised by Sebastian Bob several
months ago) is to propagate the loop carried memory dependancy in a form of
a maximum dependancy distance of a given loop from the trees (where we have
this information available) down to the RTL and propagate it thought the
RTL passes.  This solution can buy us a good estimation of what alias
information would give us (when available) in SMS.  However, it requires
the loop information to live across the RTL passes (currently we build the
loop information at the beginning of the pass that needs it and destroy
that information at the end of the pass).   A third approach - which is the
same as the previous one with only one difference - is to use a NOTE inside
one of the basic blocks of the loop (latch for example) and put the
information regarding the maximum memory dependence distance in that NOTE;
since notes are naturally propagated through the RTL passes there is no
need for special handling to propagate this information.  I wanted to share
these thoughts with others, because I see increasing interest in improving
SMS, and see if anyone expect problems in any of these approaches.

Mostafa.