Re: reducible loops

Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu> writes:
>If you want an example of an irreducible loop, here's the simplest example
>I can think of.


[ugly code supressed!]


>I'm fairly sure that this is irreducible, but I forget my graph theory,
>and am not sure that the proof applies to the sort of reduction we're
>talking about here.


Ok. I've drawn this out on my white board (not very helpful to you though
:-) and it does look irreducible, in the sense that there is a cycle <30,
32, 40, 41, 30> with two entry points (into 30 and into 40). I can make
it reducible by cloning a couple of statements, at 40 and 41.


Oops. There's another problem. The cycles <20, 21, 30, f, 20> and <20,
21, 30, 31, 20> have two entries, at 20 and at 30. (The previous cycle
containing 30 is nested within this one.) One possibility is to start
splitting at 30, but since 30 is a loop header, we'd have to clone the
whole loop. A better alternative looks like cloning 20 and 21.


I don't want to try and get this correct, so I'll have to leave it as an
exercise for your favorite optimizer.


Earlier I posted a small example. Here's a simpler one (the simplest?)
that's usually used in texts:


A
if (p) goto 20
        10 B
        20 C
if (q) goto 10
D


There's this little cycle with <10, 20, 10, ...> with an entrance
at 10 and at 20. We can fix this by cloning either B or C.
I'll choose B this time


A
if (!p) B
        20 C
if (!q) goto 30
B
goto 20
        30 D


Notice that the code doesn't get any smaller, so it is surely not
"reduced" in that sense. However, each loop is now simple, with a single
entrance at the header.


Reducible means that we can do various forms of interval analysis on the
control flow graph to discover a tree of nested single-entry regions
called intervals. This tree (a control tree) illustrates, in more or less
detail depending on the method, the overall structure of the code.


Some schemes simply find the loop nests. Other more sophisticated
approaches find if-the-else structures, while structures, etc.


Preston Briggs
--

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