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

Hi,

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?

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?

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

On Jun 17, 3:34 am, sandy...@gmail.com wrote:
> Hi,
>
> Does the current C/C++ compilers in industry recognize idioms of the
> form of prefix computation and transform them? ....

I doubt it. I think what you really want is a way to transform C++
code into the form that you want. Then you can decide what custom
optimizations you desire.

The DMS Software Reengineering Toolkit can be used to transform C++
source to C++ source code. You can code your transformation pretty
much as you stated it. In practice, you'll code transformations with
source patterns of interest, target patterns that are desired (both
written in C++ surface syntax) and add additional checks to verify
that certain semantic conditions are valid.

See http://www.semanticdesigns.com/Produ...pFrontEnd.html
and the link to DMS on that page. The website also has a publications
page that has papers on transforming large, complex C++ codes for
avionics software.

Ira Baxter, CTO
Semantic Designs

On Jun 17, 3:34 am, sandy...@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
> If so, under what class of optimizations do they do this?
>
> 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?

I have worked on the phase of an optimizer for Fortran/C/C++ that
recognized some prefix computations with ad hoc pattern matching.

See the Introduction to "Automatic Algorithm Recognition and
Replacement: A New Approach to Program Optimization" (Metzger and Wen,
MIT Press, 2000) for an explanation of the limitations of ad hoc
pattern matching in optimizing compilers.

Read the rest of the book for an alternative that generally doesn't
have those limitations.

Robert Metzger
Sr. Compiler Engineer
Convey Computer Corp.