Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!world!iecc!compilers-sender From: napi@jaring.ism.MY (Mohd Hanafiah Abdullah) Newsgroups: comp.compilers Subject: SUMMARY: Multiple entry to loop. Keywords: optimize Message-ID: <91-06-030@comp.compilers> Date: 19 Jun 91 03:27:17 GMT References: <91-06-006@comp.compilers> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Mohd Hanafiah Abdullah Organization: Compilers Central Lines: 68 Approved: compilers@iecc.cambridge.ma.us 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@comp.compilers> 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@comp.compilers> 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.