From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12731 invoked by alias); 4 Jul 2005 16:55:08 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 12711 invoked by uid 22791); 4 Jul 2005 16:55:01 -0000 Received: from smtp1.csit.fsu.edu (HELO smtp1.csit.fsu.edu) (144.174.112.31) by sourceware.org (qpsmtpd/0.30-dev) with ESMTP; Mon, 04 Jul 2005 16:55:01 +0000 Received: from dial536.acns.fsu.edu ([146.201.34.28]) by smtp1.csit.fsu.edu with asmtp (TLS-1.0:RSA_ARCFOUR_SHA:16) (Exim 4.34) id 1DpTrT-00010H-3o for gcc@gcc.gnu.org; Mon, 04 Jul 2005 12:32:01 -0400 Mime-Version: 1.0 (Apple Message framework v622) Content-Transfer-Encoding: 7bit Message-Id: <6dcfb375d92ba00972dc2da53b971200@csit.fsu.edu> Content-Type: text/plain; charset=US-ASCII; format=flowed To: gcc@gcc.gnu.org From: Robert van Engelen Subject: The origin of scalar evolutions? Date: Mon, 04 Jul 2005 16:55:00 -0000 X-CSIT-MailScanner: Found to be clean X-CSIT-MailScanner-SpamCheck: not spam, SpamAssassin (score=-2.447, required 6, AWL 0.15, BAYES_00 -2.60) X-MailScanner-From: engelen@csit.fsu.edu X-SW-Source: 2005-07/txt/msg00116.txt.bz2 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