Re: DDG - Implementing Swing Modulo Scheduling in GCC (cont.)

[Vladimir Makarov <vmakarov at redhat dot com>]

Mostafa Hagog wrote:
> 
> Following http://gcc.gnu.org/ml/gcc/2003-09/msg00954.html:
> 
> ...
> >Infrastructure requirements for implementing SMS in GCC
> >-------------------------------------------------------
> [snip]
> >2. Building a dependance graph (for loops) with loop carried dependancies;
> >   intra-loop dependancies could be based on the standard
> >   LOG_LINKS/INSN_DEPEND structures. Loop carried dependancies
> >   calculations must be added, with their associated distances (from
> >   dependence.c?).
> >   The following functionality must be implemented:
> >   1. Identifying cycles (strongly connected components) in the
> >      dependance graph.
> >   2. Find the set of all predecessor [all successor] nodes for a given
> >      set of nodes in the dependance graph.
> >   3. Find all nodes that lie on some directed path between two strongly
> >      connected subgraphs.
> ...
> 
> Here are the interfaces and implementation of the Data Dependence Graph
> required above.
> 
> Data dependence information is collected in gcc during the scheduling
> passes, and we plan to invoke SMS as part of the first scheduling pass.
> Therefore, the dependence information collected for the scheduler can
> serve SMS. However, SMS requires additional information, some of which
> must be kept on the dependence edges. This requires a fundamental change
> in the rtl LOG_LINKS.
> 
> Our solution is to build a new and different representation of the data
> dependence information. The attached ddg.h and ddg.c files define and
> implement this representation. It is based on a general graph of nodes
> and edge structures, with basic information such as dependence distance
> and latency of edges, as well as allowing algorithm-specific information
> in the "data" union. The graph is built from the current LOG_LINKS
> dependency information (ddg.c/build_deps()), although it can be easily
> built from other representations if/when needed.
> In addition the DDG calculates loop carried dependencies,
> strongly-connected
> components and their maximum recurrence length (e.g. to compute recMII).
> We tried to make the DDG as generic as possible for potential use by other
> algorithms or optimizations.
> 
> Comments are welcome.

The first my thought as Richard's one was to use data flow analysis
framework (df.[hc]) for this.  But it is wrong.  The framework is
oriented only to register dependencies.  The insn scheduler's dependency
analysis framework is more sophisticated.  It would be good to have an
abstract framework to deal with all this stuff but it is too big work
besides writing SMS itself.  So I don't think that it is reasonable (at
least on this stage) to work on enhance/reuse the data flow analysis
framework.

So in general the data design looks ok to me of course if it is enough
for your implementation of SMS.  I've found some simplifications in data
analysis.  You are searching dependencies between iterations with only
the distance equal to 1.  It is better to use a general framework
dependence.c (now it is not a part of gcc mainline because it is not
used by any part of gcc) written by Stan Cox.  If it is hard to
understand or support this, you could implement at least the same
functionality.

Another thing is to output ddg for vcg (personally I prefer graphiz but
is distributed not under GPL therefore we does not support it).  My
experience show it will be a critical component for software pipelining
debugging.

Thanks for posting the progress of your work.  I hope that you will
create a branch for it when the work achieves some completeness.

Vlad