Re: recognition and optimization of prefix computation or variants in C/C++ compilers

George Neuner <gneuner2@comcast.net>
Wed, 18 Jun 2008 15:46:34 -0400

          From comp.compilers

Related articles
recognition and optimization of prefix computation or variants in C/C+ sandyasm@gmail.com (2008-06-17)
Re: recognition and optimization of prefix computation or variants in gneuner2@comcast.net (George Neuner) (2008-06-18)
Re: recognition and optimization of prefix computation or variants in idbaxter@semdesigns.com (2008-06-21)
Re: recognition and optimization of prefix computation or variants in rcmetzger@grandecom.net (rcmetzger) (2008-06-23)
| List of all articles for this month |

From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Date: Wed, 18 Jun 2008 15:46:34 -0400
Organization: Compilers Central
References: 08-06-035
Keywords: C, optimize
Posted-Date: 21 Jun 2008 12:57:17 EDT

On Tue, 17 Jun 2008 01:34:20 -0700 (PDT), sandyasm@gmail.com wrote:


>Does the current C/C++ compilers in industry recognize idioms of the
>form of prefix computation and transform them? For instance, given
>
>for (i = 0; i < n; i++)
> for (j = 0; j < i; j++)
> result[i] = result[i] + a[j];
>
>---> transform this to
>
> result [0] = a[0];
> for (i = 1; i < n; i++)
> result[i] = result[i-1] + a[i];
>
>If so, under what class of optimizations do they do this?


Hopefully none ... that transformation is invalid - it does not
produce the same result as the original code.


There are a number of analyses and transformations that can, in
combination, perform complicated optimizations. Loop specific things
include unrolling, fusion and invariant code motion. More general
things include value propagation, strength reduction and pointer alias
analysis.




>In the general case, a similar prefix pattern can be identified and
>seen in certain search/traversal algorithms also. Do the existing
>compilers handle any of those as well?


If the pattern is expressed using a loop, it is likely that existing
C/C++ compilers can do something with it. If the pattern is expressed
using recursion, it's unlikely many C/C++ compilers will do anything
at all with it. Late model GCC versions can (sometimes) turn simple
tail recursion into a loop and then perform loop optimizations - but
the support is still quite primitive.


There has been a lot of effort spent on optimizing loops and array
indexing - historically those were very important for programmer
acceptance of early languages and they continued to be important for
significant classes of programs. In recent years, attention has
turned to optimizing access to linked data webs, but it is a very hard
problem because, unlike array elements, there may be no discernable
pattern to the addresses of dynamically allocated heap objects.


George


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.