reducible loops (Preston Briggs)
Mon, 24 Feb 92 17:05:14 CST

          From comp.compilers

Related articles
Re: How Smart Can We Afford to be? idacrd! (1992-02-24)
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)
[2 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize
Organization: Compilers Central
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-106
Date: Mon, 24 Feb 92 17:05:14 CST

idacrd! (David desJardins) writes:

>I don't understand why this is a hard problem.
> Finding cycles in digraphs is certainly not a
>hard graph-theoretic problem. So what is the problem?

Well, I've left lots of pieces of the problem out. We want to find
all the loops, including loop nests, and organize them into a little
tree that shows which is contained where.

>What I thought you were going to produce, and the only case which it seems
>to me should be hard, is code in which multiple cycles are intertwined
>with one another. In this case it may indeed be hard to find the "real

110 continue
statement A
120 continue
statement B
if (condition a) then
statement C
goto 110
statement D
if (condition b) then
statement E
goto 120

>Now there are two cycles, (ABC) and (BDE), intertwined, and optimizing
>both simultaneously seems a hard problem.

Most techniques would say this is is a loop nest with 2 loops, ABCDE and BDE.
BDE is just an inner loop, contained entirely within the larger ABCDE.

Surprised? I was.

Preston Briggs

Post a followup to this message

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