Re: reducible loops

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

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