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

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

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