Re: How Smart Can We Afford to be?

In article <1992Feb22.024751.20191@rice.edu> preston@dawn.cs.rice.edu (Preston Briggs) writes:
> ...
> if (...) then
> <statements A>
> goto 20
> endif
> <statements B>
>10 continue
> <statements C>
>20 continue
> <statements D>
>30 if (...) goto 10
>
>Obviously (to us) there is some kind of loop involving the statements
>from 10 to 30. Further, it seems intuitive that <A> and <B> are not
>part of the loop. Unfortunately, I don't know of any algorithmic
>approach that matches my intuition.


I don't understand why this is a hard problem. In the control flow of
this code fragment, there is exactly one cycle. It goes, as you say, from
10 to 30 and back to 10. Finding cycles in digraphs is certainly not a
hard graph-theoretic problem. So what is the problem?


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." For example:


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


>An alternative is called "node splitting". In the simple case above,
>the code can be restructured, giving
>...
>Note that we've merely duplicated <D>; no extra computation is required.


This still holds true in my example. Duplicating statement A inside
the first if-then, and retargeting the jump, produces the following:


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


Now the restructured code is a single, if complicated, loop. (Or
possibly a pair of nested loops, depending on your point of view.)


David desJardins
--

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