Fri, 14 Jan 1994 01:33:00 GMT

Related articles |
---|

loops in irreducible graph? sreedhar@sally.cs.mcgill.ca (1994-01-12) |

Re: loops in irreducible graph? cliffc@rice.edu (1994-01-13) |

Re: loops in irreducible graph? stoltz@cse.ogi.edu (1994-01-14) |

Newsgroups: | comp.compilers |

From: | stoltz@cse.ogi.edu (Eric Stoltz) |

Keywords: | optimize, analysis |

Organization: | Center for Research on Parallel Computations |

References: | 94-01-042 |

Date: | Fri, 14 Jan 1994 01:33:00 GMT |

V.C SREEDHAR writes:

*> There are many ways to identify loops/nested loops (sometimes also called*

*> as natural loops) for reducible flowgraph. Can someone point to me how to*

*> identify loops in irreducible graph? or rather loops/nested-loops that*

*> are not reducible (in the usual sense of definition[1]). The notion of*

*> loops is little tricky for multiple entry loops.*

In our research compiler, natural loops are identified in non-reducible

graphs the same way as they are in reducible graphs: a back-edge in the

control flow graph is identified in which the head dominates the tail.

Loops with multiple entry points (and hence not defined as a loop in the

natural loop sense) are what causes the graph to be irreducible. The

dragon book says that irreducible loops occur so rarely one really needn't

be concerned. They obviously haven't parsed much of the scientific

Fortran codes which we target, such as Spice. Our motto is that if it

works on Spice, it works on anything.

Thus, one would like to identify which CFG's are irreducible. Since our

analysis on the intermediate form uses a topological sort of the basic

block nodes (forward control flow arcs only, ignoring the loop backedges

-- giving rise to a dag) for several advanced techniques, we identify

irreducible graphs during this phase. Note that a topological sort is not

possible for an irreducible graph in this context, since one can never

identify what edges are to be backedges. For example, consider nodes

A,B,C,D such that A -> B, A -> C, B -> C, C -> B, C -> D. This is

essentially the canonical example of an irreducible graph. Neither the

edge B -> C nor C -> B can be a loop backedge, since the tail does not

dominate the head.

In the following algorithm (a simple post_order dfs which will build a

stack of nodes in reverse topological order) a graph is identified as

irreducible if a cycle is found such that there are multiple entries.

test_dom(a,b) returns TRUE if a dominates b

push( v ) pushes v onto a reverse topologically-sorted stack

Invoke: top_sort( entry node )

top_sort( node v ) {

mark_visited( v );

Visit all successors s of v {

if( mark_visited( s ) && !pushed( s ) && !test_dom( s, v ) ) {

Irreducible_Graph = TRUE;

Exit -- no need to continue now!

}

if( !mark_visited( s ) )

top_sort( s );

}

push( v );

*}*

Our example graph from above will identify the multiple entry loop {B,C}

when top_sort is called on B (or C) as a successor of C (or B).

Eric

stoltz@cse.ogi.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.