Re: reducible loops

idacrd!desj@uunet.UU.NET (David desJardins)
Mon, 9 Mar 1992 03:25:59 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: idacrd!desj@uunet.UU.NET (David desJardins)
Keywords: optimize
Organization: IDA Center for Communications Research
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-110
Date: Mon, 9 Mar 1992 03:25:59 GMT

In article 92-02-110 Preston Briggs writes:
>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.

I think another poster said this too. But I think the problem is deeper
than that. My impression is that you can turn any code into a collection
of loops. The problem is that if you get the wrong loops your code will
really stink.

Suppose that I fill out conditions a and b and statements C and E as

j = 1
i = 1
110 continue
statement A
120 continue
statement B
if (i .lt. 100) then
i = i + 1
goto 110
statement D
if (j .lt. 100) then
j = j + 1
i = 1
goto 120

Now it is pretty clear that (AB) is the inner loop. If you optimize for
(BD) to be the inner loop, and 99% of the time it is executed exactly
once, you are going to have terrible performance.

Admittedly (AB) is not `irreducible.' But so what? The job of the
compiler is supposed to be a practical one of generating code which runs
fast rather than an academic one of identifying a particular kind of

Of course, maybe this problem is just too hard. But if your compiler
makes decisions like the one you are talking about before looking at what
the code is doing, then you have no chance to get it right.

David desJardins

Post a followup to this message

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