Re: reducible loops (Preston Briggs)
Wed, 26 Feb 1992 04:27:26 GMT

          From comp.compilers

Related articles
reducible loops (1992-02-24)
Re: reducible loops (Raul Deluth Miller-Rockwell) (1992-02-25)
Re: reducible loops (1992-02-26)
Re: reducible loops (1992-02-26)
Re: reducible loops (1992-02-26)
Re: reducible loops (1992-02-27)
Re: reducible loops (1992-02-28)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
Re: reducible loops (1992-03-10)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-112
Date: Wed, 26 Feb 1992 04:27:26 GMT

Raul Deluth Miller-Rockwell <> 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:

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

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

if (!p) B
        20 C
if (!q) goto 30
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

Post a followup to this message

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