Re: Loop Optimizations and Gotos

hrubin@stat.purdue.edu (Herman Rubin) writes:


> Dave Lloyd <dave@occl-cam.demon.co.uk> wrote:
> >It's simple - don't use goto. Many compilers have extra levels of
> >optimisation that only kick in when a control construct can be
> >clearly recognised that are not feasible in general for gotos.


As reported by myself and others, this is wrong. Most compilers will
pick up the loop structure from goto's, and don't care a whit about
syntatic loops.




> There are many things which can be done by gotos which eliminate
> gross inefficiencies which cannot be done by the current structure.


This is completely unrelated to the previous topic.




> How can one avoid many unnecessary steps when there are numerous logical
> exits from a block?


Did you mean "numerous logical _entries_ into some blob of code"?
Optimizing compiler writers use "block" to mean "basic block", which by
it's very definition has only 1 exit (and 1 entry).




> One case of this is entrance to a state machine; this and the progress
> within that program does not require that the state be known other than
> by location in the code, and the state variable and the associated switch
> statements are not needed. Can a compiler eliminate these? Can an
> optimizing compiler remove these?


Yes, compilers can remove these. Most don't bother since this kind of code
is both rare and often not a bottleneck (lex not withstanding :-).
Instead, memory hierarchy optimizations, dependence analysis, loop
transformations, register allocators and the old stand-bys: constant
propagation and dead code elimination keep us busy.


To do this "state-machine as a state-variable + switch" optimizaton
requires a little block cloning, the kind VLIW compilers think about doing.
Note that fat superscalar designs require much the same compilation
technology, so someday you might get your wish in the box on your desk.




> Not by any means I can think of with "structured" programming.


As mentioned above, most optimizing compilers don't give a darned about
"structured programming".




> When discussing an optimizing compiler, efficiency is the target.
> Do we need to eliminate optimizations made by the human?


As always, this is full of misconceptions:
1) Compilers don't strive to remove "human optimizations"; the term has
      no meaning to a compiler.
2) Most humans are notoriously bad at the low-level optimizations that
      compilers are good at; sometimes "human optimizations" slow the code
      down.
3) Humans are good at replacing one algorithm with another, where the
      replacment algorithm has different asymptotic behavior. This is
      where real "human optimizations" occur.
4) The original author was making machine-generated code, hardly a "human
      optimization".




> I suggest then that the fault is in the compiler writers.


Again, I suggest YOU become a compiler writer. Compiler writers have their
plates full already; rushing out and flattening state machines into goto's
is really low on the priority list. If you want this optimization, go
write a compiler that does it.


Cliff
--
Cliff Click Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
[This is the usual post-Herman impasse, so I declare this thread closed. -John]
--

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