Re: loops (Preston Briggs)
Tue, 25 Feb 1992 06:44:50 GMT

          From comp.compilers

Related articles
Re: loops (1992-02-25)
Re: loops (1992-02-26)
Re: loops (1992-02-26)
Re: loops clc5q@hemlock.cs.Virginia.EDU (1992-02-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize, bibliography
Organization: Rice University, Houston
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-110@comp.compilers>
Date: Tue, 25 Feb 1992 06:44:50 GMT

Another interesting question relating to loops... If we have two back
edges leading to a single header node, should we call it one loop or two?

A common case might look like this

do {
do {
} while ()
} while ()

My intuition says two loops here; but techniques based on Tarjan's
reducibility test (or the "natural loops" of ASU) will call this a single
loop. I characterize Tarjan's approach a based on header nodes -- 1 loop
for each header. Sharir's approach will call this two loops; basically he
finds 1 loop per back edge (using DF ordering to decide which loop is

Does it matter? Sometimes, surely; e.g., when using nesting depth to
estimate execution frequency. Otherwise, I'm not sure.

I haven't taken the time yet to figure out how other common interval
reduction techniques will interpret this sort of structure.

Relevant papers include

Testing Flow Graph Reducibility
Robert Endre Tarjan
Journal of Computer and System Sciences
Volume 9, December 1974


Structural Analysis:
A New Approach to Flow Analysis in Optimizing Compilers
Micha Sharir
Computer Languages
Volume 5, 1980

Sharir's work is fairly popular in real optimizers. I believe it's used
in the HP PA compilers and the old COMPASS compilers.

Preston Briggs

Post a followup to this message

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