Re: irreducible loops

johan@dutecaj.et.tudelft.nl (J.A.A.J. Janssen) writes:
>One of the problems we encountered are irreducible loops.
>Therefore I'm looking for information in this area. Our ideas for
>resolving this problem are :


>1. Solve the problem at the source language level.


I've always hated the idea of doing things at the source level.
You do it once for C, then for Fortran 77, then for C++, then for ...
The great hope of handling things like this in the optimizer is that
you won't have to repeat your work in each front end.


>2. My second question is about how to solve irreducibility on the basic
>block level. Our idea is to use Node Splitting. In our opinion this is a
>complex solution


Node splitting _is_ a complex solution and you can get exponential
code growth (and after you finished all the node splitting, the code
is so complex, your analysis won't yield too much useful information).
It also seems like a lot of programming effort for a problem that
doesn't actually arise that often.


There's a third choive you don't mention that's used by many people --
use analysis and optimization techniques that don't require reducible
flow graphs.


iterative data-flow analysis instead of interval DFA


algorithms based on static single assignment
constant propagation
dead code elimination
value numbering
peephole optimization


partial redundancy elimination


register allocation via graph coloring


If you do all these things, you'll have a fine (scalar) optimizer.
Throw in a good scheduler, and you'll be set to handle most RISC
machines (I can't speak for the MOVE architecture).


Preston Briggs
--

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