Wed, 19 Jun 91 11:27:17 U

Related articles |
---|

Multiple entry to loop. napi@jaring.ism.MY (Mohd Hanafiah Abdullah) (1991-06-11) |

SUMMARY: Multiple entry to loop. napi@jaring.ism.MY (Mohd Hanafiah Abdullah) (1991-06-19) |

Newsgroups: | comp.compilers |

From: | Mohd Hanafiah Abdullah <napi@jaring.ism.MY> |

Keywords: | optimize |

Organization: | Compilers Central |

References: | 91-06-006 |

Date: | Wed, 19 Jun 91 11:27:17 U |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.