preston@rutherfordia.rice.edu (Preston Briggs) (06/12/91)
Mohd Hanafiah Abdullah <napi@jaring.ism.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 >GOTO statement? 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) pages 355-365 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. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.