Re: Loop Optimizations and Gotos

cliffc@ami.sps.mot.com (Cliff Click)
Wed, 22 Nov 1995 20:36:06 GMT

          From comp.compilers

Related articles
[6 earlier articles]
Re: Loop Optimizations and Gotos hrubin@stat.purdue.edu (1995-11-17)
Re: Loop Optimizations and Gotos j-grout@glibm9.cen.uiuc.edu (1995-11-17)
Re: Loop Optimizations and Gotos baynes@ukpsshp1.serigate.philips.nl (1995-11-20)
Re: Loop Optimizations and Gotos plong@perf.com (Paul Long) (1995-11-21)
Re: Loop Optimizations and Gotos preston@tera.com (1995-11-21)
Re: Loop Optimizations and Gotos cliffc@ami.sps.mot.com (1995-11-21)
Re: Loop Optimizations and Gotos cliffc@ami.sps.mot.com (1995-11-22)
Re: Loop Optimizations and Gotos Paul_Long@ortel.org (1995-11-23)
Re: Loop Optimizations and Gotos bill@amber.ssd.hcsc.com (1995-11-27)
Re: Loop Optimizations and Gotos dave@occl-cam.demon.co.uk (Dave Lloyd) (1995-11-27)
alias analysis (was Loop Optimizations and Gotos) bwilson@shasta.Stanford.EDU (Bob Wilson) (1995-11-28)
Re: alias analysis (was Loop Optimizations and Gotos) cliffc@ami.sps.mot.com (1995-11-29)
Interprocedural Pointer Tracking metzger@bach.convex.com (1995-11-29)
[5 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: cliffc@ami.sps.mot.com (Cliff Click)
Keywords: optimize
Organization: none
References: 95-11-076 95-11-170
Date: Wed, 22 Nov 1995 20:36:06 GMT

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
--


Post a followup to this message

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