Re: irreducible loops (Preston Briggs)
Thu, 7 Jul 1994 13:04:04 GMT

          From comp.compilers

Related articles
irreducible loops (1994-07-04)
Re: irreducible loops (1994-07-06)
Re: irreducible loops (1994-07-07)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize, analysis
Organization: Rice University, Houston
References: 94-07-030
Date: Thu, 7 Jul 1994 13:04:04 GMT (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

Post a followup to this message

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