Re: Loop Optimizations and Gotos

baynes@ukpsshp1.serigate.philips.nl writes:


> There are two ways a compiler can view code:
>
> 1: It can flatten down the code into basic blocks (with no jumps in them) and
> work on these finding its own loops and other structures. This is typical of
> compilers for unstructured languages though it can be used on structured
> languages too. This is able to cope with almost anything, but tends to lose
> any hints that can be gained from how the programer wrote the code (eg using
> 'for' loops).


No reason why it has to lose hints.
The code pattern made by DO loops or straightforward for() loops is as
easy to spot as is the loop itself. If you write Fortran style code
in the C language, a good optimizer will generate the same code as the
Fortran one, modulo the Fortran no-alias assertion.


For historical reasons, there exist compilers that use syntax instead
of semantics to spot loops, and they lose on goto-loops. I think most
workstation-class compilers spot loops by looking at the CFG.


For historical reasons, there exist compilers that use syntax instead
of semantics to spot _array_references_, and they lose on simple
pointer-based array addressing. This is a MUCH more common problem,
and I can only think of a few folks that reverse pointer addressing
back to array references. Loss of array references kills much
dependence analysis, upon which many loop-based transforms depend (and
these transforms can have integer-factor speedups for scientic codes).


There's no general way to figure out the Fortran no-alias assertion in
C code (lots of IPA can get you part of the way there, but not all the
way). Lack of this assertion can hurt some dependence analysis, with
the results outlined above.


Summary:
    1) Loops from GOTOs will be optimized "properly" on most (not all)
          workstation compilers.
    2) Array refs as pointer derefs could be optimized properly, 'cept
          they aren't on most (not all) compilers. Cause: software inertia.
    3) You can't get the "no alias" assertion without writing Fortran
          (modulo pragma's & wild function-unswitching techniques).
          Cause: it's intractable.


Cliff
--
Cliff Click Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
--

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