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: [EMAIL PROTECTED], URL: http://www.cs.fsu.edu/~engelen
