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