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 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)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
Re: reducible loops preston@dawn.cs.rice.edu (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
follows:

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

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

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