Re: Loop Optimizations and Gotos

jra@gensym.com (Jim Allard) writes:


      [...] With some work we can identify these
      loops by a pattern matching scheme that will get most of the commonly
      used loop idioms and then translate those as FOR or WHILE loops.


      We've had a debate here about whether this work is worth it. One
      group believes that most compilers today can identify loops from the
      flow of control through GOTO statements, and then perform loop
      optimizations. Another group (myself included) believe that while
      such sufficiently smart compilers might be imagined in practice they
      are rare in the commercial world, and that most compilers today need
      the "hint" that FOR or WHILE give them in order to trigger loop
      optimization techniques.


gcc doesn't seem to treat a low-level translation of a "for" loop
exactly as it would the equivalent "for" loop, as far as I can tell
(but I'm not yet a gcc expert). So I think that you're right as far
as gcc is concerned, and perhaps for many or most C compilers,
since C has had looping constructs throughout its history (at least
as far as it applies to earlier subsets of the language).


But the Numerix Fortran Optimizing Compiler, on which I did work for
a while, definitely did convert low-level GOTO-laden code up to the
higher loop constructs. (This compiler targeted a 128-bit-wide VLIW
architecture, the Numerix 432, 464, and 332 processors.)


In fact, what this compiler did was to first LOWER all the DO loops
to their primitive (IF/GOTO-based) equivalents, then RAISE all the
primitive stuff up to loops as much as it reasonably could. It did
this because the design of the compiler was such that it compiled
from the innermost loops outward, and was definitely willing to spend
lots of time trying different strategies for optimizing inner loops
than it did outer loops and/or straightline code.


>From what I gathered at the time, the reason to RAISE primitive stuff
to higher-level constructs in Fortran is that _lots_ of old Fortran
code exists that uses no looping constructs -- because it was written
before they existed or were considered "safe" by the code authors.


If you're not particularly concerned about old Fortran code, or some
such thing, then maybe it isn't worth it. But for your project, maybe
it is anyway, and it indeed doesn't seem to hard, especially if all
you're doing is recognizing particular patterns your code generator
actually generates, not any old weird thing somebody throws at it.


Anyway, my small amount of experience with compiler internals suggests a
50% likelihood that a given optimizing compiler will find loop constructs
where they are not explicitly used. Your mileage WILL vary. ;-)
--


James Craig Burley, Software Craftsperson burley@gnu.ai.mit.edu
--

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