SUMMARY: Multiple entry to loop.

The following are three responses I received as a result of my recent
posting. Thanks.


-------------------------------------------------------------------------------


Reply-To: hcx2.SSD.CSD.HARRIS.COM!bill@uunet.UUCP (Bill Leonard)


In article 91-06-006 you write:
> Is there any algorithm out there more efficient than the obvious one that
> could determine whether a WHILE loop has exactly one entry point, or
> conversely if the WHILE loop has more than one entry point due to a
> GOTO statement?


I don't know if you consider this the "obvious one" or not:


If you compute the set of DOMINATORS for each basic block (see Aho and
Ullman, Principles of Compiler Design, p. 442), then you can check to see
if the loop header block dominates the block that performs the backward
branch. If it does not, then there is another entry point to the loop.


--
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
bill@ssd.csd.harris.com


-------------------------------------------------------------------------------


Reply-To: cs.cornell.edu!ressler@uunet.UUCP (Gene Ressler)


Not sure what you mean by `the obvious one', but
ASU (the dragon book) has a good discussion of
finding the dominators of a flow graph. I
believe the basic block of the WHILE branch will
dominate the loop body subgraph if and only if there
are no branches into the loop body.


Gene


-------------------------------------------------------------------------------


Reply-To: rice.edu!preston@uunet.UUCP (Preston Briggs)


In article 91-06-006 you write:
>Is there any algorithm out there more efficient than the obvious one that
>could determine whether a WHILE loop has exactly one entry point, or
>conversely if the WHILE loop has more than one entry point due to a
>GOTO statement?


This is roughly the same as checking for flow graph reducibility.
The fast way to do this is described by Tarjan in


                Testing Flow Graph Reducibility
                R. E. Tarjan
                Journal of Computer and System Sciences
                Volume 9 (1974)
                pages 355-365


A simpler, slower scheme could be adapted from
the algorithm for finding "natural loops", described
by Aho, Sethi, and Ullman in the red dragon book.


Preston Briggs


--

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