The origin of scalar evolutions?

The origin of scalar evolutions?

[Robert van Engelen]

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]).

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? Or is there an essential 
difference with multi-variate chains of recurrences [7]? Does the 
"scalar evolutions" name suggest something else beyond the recurrence 
forms. Are we missing a crucial point?

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].

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]?

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?

5. Do you plan on implementing dependence testing and range analysis on 
chains of recurrences as described in [3,4,5]?

With respect to our first question, we felt that the use of a new name 
for an existing technique is confusing. For example, by calling a 
"matrix" from linear algebra a "scalar square" we do not change its 
semantics. The (algebraic) operations on matrices are still the same. 
So are the operations on scalar evolutions the same as those on chains 
of recurrences. Janson's classic "History of Art" has apt advice: "It 
has always been easier to invent new labels than to create a movement 
in art that truly deserves a new name."

References

[1]	Robert A. van Engelen, "Efficient Symbolic Analysis for Optimizing 
Compilers", in proceedings of the International Conference on Compiler 
Construction, ETAPS 2001, LNCS 2027, pages 118-132

[2]	Robert A. van Engelen and Kyle A. Gallivan, "An Efficient Algorithm 
for Pointer-to-Array Access Conversion for Compiling and Optimizing DSP 
Applications", in proceedings of the 2001 International Workshop on 
Innovative Architectures for Future Generation High-Performance 
Processors and Systems (IWIA 2001), 18-19 January 2001, Maui, Hawaii, 
pages 80-89.

[3]	Robert van Engelen, Johnnie Birch, and Kyle Gallivan, "Array Data 
Dependence Testing with the Chains of Recurrences Algebra", in the 
proceedings of the IEEE International Workshop on Innovative 
Architectures for Future Generation High-Performance Processors and 
Systems (IWIA), January 2004, pages 70-81.

[4]	Robert van Engelen, Johnnie Birch, Yixin Shou, Burt Walsh, and Kyle 
Gallivan, "A Unified Framework for Nonlinear Dependence Testing and 
Symbolic Analysis", in the proceedings of the ACM International 
Conference on Supercomputing (ICS), 2004, pages 106-115.

[5]	Johnnie Birch, Robert van Engelen, and Kyle Gallivan, "Value Range 
Analysis of Conditionally Updated Variables and Pointers", in the 
proceedings of Compilers for Parallel Computing (CPC), 2004, pages 
265-276.

[6]	O. Bachmann, P.S. Wang and E.V. Zima, "Chains of Recurrences - a 
Method to Expedite the Evaluation of Closed-Form Functions",in 
proceedings of the International Symposium on Symbolic and Algebraic 
Computing (ISSAC), 1994, pages 242-249.

[7]	O. Bachmann, "Chains of Recurrences for Functions of Two Variables 
and Their Application to Surface Plotting", in "Human Interaction for 
Symbolic Computation, 1996.

[8]	E.V. Zima, "On computational properties of chains of recurrences",
in proceedings of the 2001 International Symposium on Symbolic and 
Algebraic Computation, pages 345.

[9]	P. Tu and D. Padua, "Gated SSA-Based Demand-Driven Symbolic 
Analysis for Parallelizing Compilers", in proceedings of the ACM 
International Conference on Supercomputing (ICS), 1995, pages 414-423.

- Robert van Engelen

Robert van Engelen: Associate Professor, Computer Science Department
Florida State University, 162 J. Love Bldg., Tallahassee, FL32306-4530
Offices: 162LOV/471DSL, (850)644-9661/645-0309, Fax: (850)644-0058
Email: engelen@cs.fsu.edu, URL: http://www.cs.fsu.edu/~engelen

Re: The origin of scalar evolutions?

[Daniel Berlin]

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

Re: The origin of scalar evolutions?

[Sebastian Pop]

Robert van Engelen wrote:
> 
> 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? Or is there an essential 
> difference with multi-variate chains of recurrences [7]? Does the 
> "scalar evolutions" name suggest something else beyond the recurrence 
> forms. Are we missing a crucial point?
> 

a = {1, +, a}
b = {3, +, [1, 2]}
c = {-, +, +}
d = {abstract_value, +, abstract_value}

are not chains of recurrences.  More generally chains of recurrences
use integer or real coefficients, whereas coefficients of scalar
evolutions are over any abstract domain.

a is a mixer (exponential), b is an envelope (interval coefficients),
c is a monotonic evolution (coefficients in {+, -}).  The name of
scalar evolutions is not that far from the name "monotonic evolution"
used by Peng Wu, and it seemed appropriate to be used for the general
concept (you're free to disagree with my choice for using this name).

> With respect to our first question, we felt that the use of a new name 
> for an existing technique is confusing. For example, by calling a 
> "matrix" from linear algebra a "scalar square" we do not change its 
> semantics. The (algebraic) operations on matrices are still the same. 
> So are the operations on scalar evolutions the same as those on chains 
> of recurrences. Janson's classic "History of Art" has apt advice: "It 
> has always been easier to invent new labels than to create a movement 
> in art that truly deserves a new name."

Do you know why in natural languages we have so many synonyms?  Well,
because otherwise poets would compose very poor texts.  Poets like to
play with the phonetics of the words because they can express their
moods in the phonemes.  Restricting the number of words that point to
the same (or close) semantics would restrict the ability of writers.
Anyway, this is way off topic for this mailing list.

> 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]. 

Not the same.  You're rebuilding a higher level tree from the
gimple-ssa form, but then you use abstract domains for representing
some of the difficult evolutions.  Analyzers are like poetry: there
always will be room for something new because they are not comparable;
they just fill a missing topic.

> 
> 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]?

Daniel has already replied to this one and many other questions
(thanks Daniel).

> 
> 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?
> 

In SSA form the previous program is written:

loop_1
  c = phi (0, d)
  d = c + 1
  e = phi (9, c)
  a[e] = ...
endloop_1

so you have the following evolutions:

c = {0, +, 1}_1
d = {1, +, 1}_1
e = (9, {0, +, 1}_1)_1

e is a wrap around, whose first value when entering in the loop is 9,
followed in the next iterations by 0, 1, 2, ...

As Daniel has pointed out, this extension sleeps in the lno-branch.
We will consider this extension useful for mainline only the day when
some optimizer will show a net improvement that justifies the extra
burden of maintaining the code.  

I also have decided to restrict the polynomials to a degree less or
equal than 2 (affine evolutions) because all the other constructs are
just pure nonsense, and not used by any optimizer or other analyzer.
It's too bad that I have not restricted the analyzer earlier based on
the suggestions from Zdenek Dvorak.

Sebastian

Re: The origin of scalar evolutions?

[Robert van Engelen]

Hi Sebastian,

Thank you for your quick reply. I have a few more comments though, and 
I hope you can take a look at these.

>> 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? Or is there an essential
>> difference with multi-variate chains of recurrences [7]? Does the
>> "scalar evolutions" name suggest something else beyond the recurrence
>> forms. Are we missing a crucial point?
>>
>
> a = {1, +, a}
> b = {3, +, [1, 2]}
> c = {-, +, +}
> d = {abstract_value, +, abstract_value}
>
> are not chains of recurrences.  More generally chains of recurrences
> use integer or real coefficients, whereas coefficients of scalar
> evolutions are over any abstract domain.

I disagree. The chains of recurrences algebra is applicable to any 
semi-ring, as long as the objects adhere to the properties, based on 
the fact that chains of recurrences are strongly related to finite 
differencing, which are known to work for functions over commutative 
rings. You could use the algebra on matrices for example. There has 
been a lot of similar work on differencing techniques for various 
domains. Wouldn't it be prudent to prove you have a commutative 
(semi-)ring when dealing with abstract values? In our chains of 
recurrences approach we impose restrictions on symbolic coefficients to 
ensure the validity of the representation. For example, {i,+,1}_i is 
not valid.

> a is a mixer (exponential), b is an envelope (interval coefficients),
> c is a monotonic evolution (coefficients in {+, -}).  The name of
> scalar evolutions is not that far from the name "monotonic evolution"
> used by Peng Wu, and it seemed appropriate to be used for the general
> concept (you're free to disagree with my choice for using this name).

The fact remains that scalar evolutions are the same as chains of 
recurrences based on my statement above.

>> 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].
>
> Not the same.  You're rebuilding a higher level tree from the
> gimple-ssa form, but then you use abstract domains for representing
> some of the difficult evolutions.  Analyzers are like poetry: there
> always will be room for something new because they are not comparable;
> they just fill a missing topic.

But that is my whole point: if you have a (slightly) different code 
representation (with the same semantics), I can think of another 
(slightly) different code representation and modify an existing 
algorithm to do the same job on the new representation. The basic 
principles of the approach won't change though.

The show that there is no inherent difference in the approach, consider 
the IV problem:

k = 0
DO
   k = k + 1
   j = k
   k = j + 1

Using our algorithm published in 2001 [1,2] by analyzing the code 
bottom-up we get:

k = 0
DO
   k = k + 1     => (step 3)  k = k + 2 => {0,+,2}
   j = k         => (step 2)  k = k + 1
   k = j + 1     => (step 1)  k = j + 1

Note that we don't need to substitute the variables to obtain the CR, 
following links is sufficient. It is just more convenient to use 
replacement to visualize the algorithm.

With an SSA form, we get (again using the same algorithm):

k1 = 0
DO
   k2 = phi(k1, k4) => (step 4)  k4 = phi(0, k4) + 2 => {0,+,2}
   k3 = k2 + 1      => (step 3)  k4 = k2 + 2
   j1 = k3          => (step 2)  k4 = k3 + 1
   k4 = j1 + 1      => (step 1)  k4 = j1 + 1

This algorithm is applicable to affine, polynomial, and exponential 
series. Maybe I am losing my mind here, but I don't see the difference 
when comparing the scalar evolutions approach on SSA forms to the 
earlier CR approach.

> I also have decided to restrict the polynomials to a degree less or
> equal than 2 (affine evolutions) because all the other constructs are
> just pure nonsense, and not used by any optimizer or other analyzer.
> It's too bad that I have not restricted the analyzer earlier based on
> the suggestions from Zdenek Dvorak.

If you restrict the degree to affine, you recreate the induction 
variable representations discussed in the Red Dragon book (offset + 
stride) modulo the use of intervals, of course. But there are codes 
that use quadratic forms. It is true that auto-vectorization wouldn't 
be easy to achieve with non-affine forms thereby rendering the use of 
higher-order forms useless.

- Robert van Engelen

Robert van Engelen: Associate Professor, Computer Science Department
Florida State University, 162 J. Love Bldg., Tallahassee, FL32306-4530
Offices: 162LOV/471DSL, (850)644-9661/645-0309, Fax: (850)644-0058
Email: engelen@cs.fsu.edu, URL: http://www.cs.fsu.edu/~engelen