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