From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2679 invoked by alias); 11 Dec 2003 17:01:25 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 2671 invoked from network); 11 Dec 2003 17:01:24 -0000 Received: from unknown (HELO touchme.toronto.redhat.com) (216.129.200.20) by sources.redhat.com with SMTP; 11 Dec 2003 17:01:24 -0000 Received: from redhat.com (torque.toronto.redhat.com [172.16.14.46]) by touchme.toronto.redhat.com (Postfix) with ESMTP id 3D2F580018E; Thu, 11 Dec 2003 12:01:23 -0500 (EST) Message-ID: <3FD8A2EC.AA2D9B51@redhat.com> Date: Thu, 11 Dec 2003 17:02:00 -0000 From: Vladimir Makarov X-Accept-Language: en MIME-Version: 1.0 To: Mostafa Hagog Cc: gcc@gcc.gnu.org, Ayal Zaks , David Edelsohn , canqun@yahoo.com.cn Subject: Re: DDG - Implementing Swing Modulo Scheduling in GCC (cont.) References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-SW-Source: 2003-12/txt/msg00660.txt.bz2 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