Re: Multiple entry to loop.

preston@rutherfordia.rice.edu (Preston Briggs)
Tue, 11 Jun 91 17:09:56 GMT

          From comp.compilers
Related articles
Multiple entry to loop. napi@jaring.ism.MY (Mohd Hanafiah Abdullah) (1991-06-11)
Re: Multiple entry to loop. preston@rutherfordia.rice.edu (1991-06-11)
| List of all articles for this month |
Newsgroups: comp.compilers
From: preston@rutherfordia.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 91-06-006
Date: Tue, 11 Jun 91 17:09:56 GMT

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

Post a followup to this message

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