|Re: loops firstname.lastname@example.org (1992-02-25)|
|Re: loops email@example.com (1992-02-26)|
|Re: loops firstname.lastname@example.org (1992-02-26)|
|Re: loops email@example.com.Virginia.EDU (1992-02-28)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|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
} 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
A New Approach to Flow Analysis in Optimizing Compilers
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.
Return to the
Search the comp.compilers archives again.