From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 28928 invoked by alias); 5 Jul 2005 03:36:42 -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 28863 invoked by uid 22791); 5 Jul 2005 03:36:33 -0000 Received: from h-68-164-203-246.nycmny83.covad.net (HELO dberlin.org) (68.164.203.246) by sourceware.org (qpsmtpd/0.30-dev) with ESMTP; Tue, 05 Jul 2005 03:36:33 +0000 Received: from [127.0.0.1] (HELO localhost) by dberlin.org (CommuniGate Pro SMTP 4.3.4) with ESMTP id 8193347; Mon, 04 Jul 2005 23:36:29 -0400 Subject: Re: The origin of scalar evolutions? From: Daniel Berlin To: Sebastian Pop , Robert van Engelen Cc: gcc@gcc.gnu.org In-Reply-To: <6dcfb375d92ba00972dc2da53b971200@csit.fsu.edu> References: <6dcfb375d92ba00972dc2da53b971200@csit.fsu.edu> Content-Type: text/plain Date: Tue, 05 Jul 2005 03:36:00 -0000 Message-Id: <1120534587.8157.50.camel@linux.site> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-SW-Source: 2005-07/txt/msg00129.txt.bz2 On Mon, 2005-07-04 at 12:31 -0400, Robert van Engelen wrote: > Hi, > > I am interested in the recent work in gcc 4.0 with respect to "scalar > evolutions". The students in my compiler laboratory studied the > algorithm implemented in gcc 4.0. We are considering extending this > work based on our experience [4] building a similar framework for > symbolic analysis with chains of recurrences for SUIF and Polaris > (since we introduced this approach in 2001 [1]). (I've snipped the paper references because i've read all these papers in the past, and i'm pretty sure Sebastian has as well :P) That would be great! We'd be glad to work with you to extend this and contribute the work to gcc. (We being Sebastian and I. Together we are responsible for maintenance of the chains of recurrence/scalar evolutions code and the data dependence analysis) I should note that we have significantly advanced data dependence work going on based on chrecs on the autovect-branch of gcc cvs (it's just a convenient place for the work, most of the autovectorization improvements from that code tree have already been put into 4.1) In addition, you probably want to look at the current code, as it is changing as we speak as the final "non-bugfixing" phase of gcc 4.1 closes in the next few days. Things like range analysis using the results of the analysis are also in 4.1. You can get a snapshot of the 4.1 code from ftp://gcc.gnu.org/pub/gcc/snapshots This should include the Value Range Propagation that uses the results, but won't yet include the access function information for recurrences. > > However, after reading the paper on "Fast Recognition of Scalar > Evolutions on Three-Address SSA Code", we have a couple of questions. > > 1. After reading the paper, we concluded that the scalar evolutions are > actually a restricted polynomial form of chains of recurrences by > Bachmann and Zima [6,8]. Is this true? Yes. Or rather, the scalar evolution code uses chains of recurrences as an internal representation. See tree-chrec.c " This file implements operations on chains of recurrences. Chains of recurrences are used for modeling evolution functions of scalar variables. " > Or is there an essential > difference with multi-variate chains of recurrences [7]? I don't believe so, but you'll have to ask Sebastian (who i have copied). > Does the > "scalar evolutions" name suggest something else beyond the recurrence > forms. Not really, they are evolution functions for scalar variables, represented used chains of recurrences. > Are we missing a crucial point? Dunno. I should note that that we properly give credit where it is due: " The notation used in this file is called "chains of recurrences", and has been proposed by Eugene Zima, Robert Van Engelen, and others for describing induction variables in programs. " (from tree-scalar-evolution.c) :) Sebastian devised the notation, and nobody argued with him. > > 2. What is the difference between the SSA-based algorithm described in > the paper and the G-SSA form proposed in 1995 by Tu and Padua [9]. The > G-SSA algorithms compute recurrence relations from which chains of > recurrences can be easily constructed using the construction algorithm > presented in [1]. Sebastian can cover this. > > 3. Do you compute recurrence forms for pointer variables? If so, what > is the difference compared to the method described in our 2001 paper > [2]? Yes to the first question, I don't believe anyone implemented the method discussed in your paper. One thing to note is that we have no direct array reference operation that operates on pointers at the moment. So they really are just treated as pointers, and all data dependence on pointers is very simple (mainly because we have not implemented the symbolic differencing necessary). You can see this basic work (originally from the autovectorization branch of gcc cvs) in patch at http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02057.html (and the followup patch) This work was only recently submitted to gcc 4.1, and i am about to approve it for gcc 4.1, so it should appear in the gcc 4.1 snapshots in a few weeks or so. > > 4. The "peeled" forms are described as "wrap around" forms in the paper > but do not seem to handle true wrap around variable. How do you handle > wrap around variables, i.e. those that have the form: > k = 9; > for (i=0; i < 10; i++) > { a[k] = ... > k = i; > } > Can you please explain? We used to handle true wraparounds, but don't anymore. This work can be found in a branch of the gcc source tree if you would like to look at it. It was too expensive, and didn't seem to buy us anything over what we handle now for real code. If there comes a time this isn't true, we'll probably bring it back (IE we are eminently pragmatic about this stuff. Or at least, Sebastian and I am) > > 5. Do you plan on implementing dependence testing and range analysis on > chains of recurrences as described in [3,4,5]? We have simple ZIV, SIV, and MIV dependence testing based on this work. See tree-data-ref.c in 4.0. This is used by, e.g., the linear loop transform code (in a simple way) in tree-loop-linear, and will be used in other places as well as more high level loop transforms are implemented On the autovect branch, we have improved begun work on improved data dependence testing including simple improvements to the current tests, the omega test, and even more general polyhedron dependence testing. I've submitted work to enable direct array reference operations on pointers when the user wrote them way (and in the future, i will probably implement pointer->array recovery). Range analysis using SCEV info is used in the value range propagation pass of gcc 4.1. I should note that one thing that most papers i've read on chrecs don't cover but end up very important in practice are casts between signed and unsigned, overflow behavior, etc. --Dan