reducible loops

preston@cs.rice.edu (Preston Briggs)
Mon, 24 Feb 92 17:05:14 CST

          From comp.compilers
Related articles
Re: How Smart Can We Afford to be? idacrd!desj@uunet.uu.net (1992-02-24)
reducible loops preston@cs.rice.edu (1992-02-24)
Re: reducible loops rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1992-02-25)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-26)
Re: reducible loops lee@dumas.rutgers.edu (1992-02-26)
Re: reducible loops glew@pdx007.intel.com (1992-02-26)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-27)
Re: reducible loops joel@decwrl.dec.com (1992-02-28)
[2 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: preston@cs.rice.edu (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!desj@uunet.uu.net (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
>loop."


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


>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.