Re: The origin of scalar evolutions?

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

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