Re: The origin of scalar evolutions?

[Daniel Berlin <dberlin@dberlin.org>]

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