From stoltz@cse.ogi.edu Fri Jan 14 12:28:07 EST 1994
Article: 6141 of comp.compilers
Xref: lisp-pmax1.slisp.cs.cmu.edu comp.compilers:6141
Newsgroups: comp.compilers
Path: honeydew.srv.cs.cmu.edu!rochester!udel!news.intercon.com!howland.reston.ans.net!cs.utexas.edu!uunet!world!iecc!compilers-sender
From: stoltz@cse.ogi.edu (Eric Stoltz)
Subject: Re: loops in irreducible graph?
Message-ID: <94-01-053@comp.compilers>
Keywords: optimize, analysis
Sender: compilers-sender@chico.iecc.com
Organization: Center for Research on Parallel Computations
References: <94-01-042@comp.compilers>
Date: Fri, 14 Jan 1994 01:33:00 GMT
Approved: compilers@chico.iecc.com
Lines: 61

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
-- 
Send compilers articles to compilers@iecc.com or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request@iecc.com.