Re: loops

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 {
<A>
} 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
innermost).


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


and


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

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