|Multiple entry to loop. email@example.com.MY (Mohd Hanafiah Abdullah) (1991-06-11)|
|Re: Multiple entry to loop. firstname.lastname@example.org (1991-06-11)|
|From:||email@example.com (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Tue, 11 Jun 91 17:09:56 GMT|
Mohd Hanafiah Abdullah <firstname.lastname@example.org.MY> writes:
>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
Roughly, that's the same as checking for reducibility. To perform sych a
check over an entire subroutine, you might use Tarjan's technique
Testing Flow Graph Reducibility
R. E. Tarjan
Journal of Computer and System Sciences
Volume 9 (1974)
It's quite fast. Also gives an interval reduction (if it exists), with all
the loop headers, loop bodies, and how they nest.
Alternatively, Aho, Sethi, and Ullman, in the red dragon book, give an
algorithm for finding "natural loops". It isn't as fast, but given the
algorithms run over basic blocks (rather than all the statements), any speed
difference will probably lost in the rest of the optimizer.
Return to the
Search the comp.compilers archives again.