Re: Irreducible loops (summary)

The following is a summary on irreducible loops that I
recently queried on this news group.


Sreedhar
-------Summary -----




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


------------------------------------


Use a variation of Tarjan's:


    @Article{Tarj:Testing,
    Author={R. E. Tarjan}, Title={Testing Flow Graph Reducibility},
    Journal={Journal of Computer and System Sciences}, Volume={9},
    Pages={355-365}, Year=1974, location=95}


Basically, each loop can have several headers instead of just one.


My code takes in a CFG and builds loop trees out of loop nests. It
handles loops that share the same header (one block heads multiple loops)
as well as irreducible loops (one loop has multiple blocks heading it).


If there is enough desire I can post my C++ code for doing this thing.
Otherwise, I will just hand out email. Be warned: this code comes from
inside a compiler, and interacts with the compiler in crufty ways. It is
not a clean "algorithms book" implementation.


Cliff
--
cliffc@cs.rice.edu -- Massively Scalar Compiler Group, Rice University


---------------------------------


>From havlak@cs.UMD.EDU Wed Jan 12 18:33:39 1994


Here's an algorithm from my incomplete doctoral dissertation.


@phdthesis{Havlak:Dissertation,
author={Paul Havlak},
title={Interprocedural Symbolic Analysis},
year={1994},
school={Department of Computer Science, Rice University
}


The labels a-e correspond to the same points in Tarjan's algorithm:


@Article{Tarj:Testing,
                Author={R. E. Tarjan},
                Title={Testing Flow Graph Reducibility},
                Journal={Journal of Computer and System Sciences},
                Volume={9}, Pages={355--365}, Year=1974}


A node v is a loop header if cyclePreds[v] is nonempty. For each node
v the header of the closest surrounding loop (or START, if no outer
loop) is given by header[v]. If reducible[v] is false, then it does
not predominate the nodes in its loop, and the choice of v as header
of its loop is arbitrary.
/* Paul sent a one-page .ps file of his algorithm
please contact me for this .ps file
(sreedhar@binkley.cs.mcgill.ca) or contact Paul.
--Paul


---------------------------------


        I didn't give a definition of irreducible loop outside of the
algorithm. Effectively, each loop is a nested strongly-connected
region. The loops at nesting level i are those SCRs which remain if
we delete the headers of loops at nesting level (i-1).
        The header of each loop is the common ancestor of all the nodes in
a depth-first spanning tree. For reducible loops, all DFSTs will give
the same header -- if that header is not an alternate entry for an
irreducible loop.
        Different DFSTs may give different headers for irreducible loops,
and when one of these potential headers is not chosen as the header,
it may be interpreted as the header of a reducible loop nested inside
the irreducible one.
        I would be interested in hearing how our definitions differ.


--Paul


---------------------------------




One way might be to look at retreating edges in a depth-first spanning
tree of the CFG. In a reducible graph, the DFST retreating edges are
the same as the dominator back edges, which define natural loops.
In an irreducible graph, some retreating edges will not be back
edges, but must correspond to a cycle. Also, any cycle must include
a retreating edge. The nesting relationship can be found by taking
the cycle with the highest DFST root as the outer loop. The definition
of the DFST root or nesting will in general not be unique, as they are
in natural loops, since the DFST is not unique (though the dominator tree is).
But it does give a usable definition.


---------------------------------


>From rusa@research.microsoft.com Wed Jan 12 20:07:39 1994


I have written a technical report on sequentialization of program
dependence graphs for irreducible programs. As part of the work, I
generalized the notion of backedges and loop headers to what I call
loop closing edges and loop entry nodes. The generalization is valid
for all rooted graphs. The construction time is O(ne) using the
algorithm sketched in the report. I suspect that some faster
algorithm exists, but I haven't spent any time looking for one.


Even though you might not be interested in the rest of the work, I
suggest you get the report. It is much more convenient for me than
extracting the relevant section from the report. It is available by
anonymous FTP on
research.microsoft.com:pub/papers/msr-tr-93-14.ps.Z


Sincerely,


Bjarne Steensgaard
Microsoft Research




---------------------------------
>From wjs@vnet.IBM.COM Thu Jan 13 08:18:10 1994


Greetings,


This is in response to your question about finding loops in an
irreducible flow
graph. I've recently implemented code to solve this problem, so perhaps I can
help.


The method I've seen (and used) is as follows:


1. Create a depth-first ordering of the control flow graph. (See the Dragon
      book for an example algorithm; however, you are better off expressing the
      recursion within the graph, rather than the compiler's runtime stack.)


2. Visit each node in the control flow graph in decreasing order by dfo
number.
      When visiting a node, determine whether that node is a "loop header" in the
      loose sense that it is the target of a retreating edge (not a true
back edge
      in the sense that the tail of the edge is dominated by its head). A
retreating
      edge is defined as one whose tail has a larger dfo number than its head.
      Informally, call the tail of each retreating edge a "loop latch."


3. Determine the membership of the loop. This is done as follows:


            Place all loop latches in the work set;
            While the work set is not empty do
                Move one node N from the work set to the loop set;
                If N is not the header then
                    For each predecessor P of N do
                        If P's dfo number is not less than that of the header then
                            Add P to the work set;
                        Else
                            Mark the loop as irreducible;
                        End If
                    End For
                End If
            End While


      This is the same algorithm as used to find the membership of a true loop,
      except for the test on P's dfo number. If a predecessor of a loop node
      other than the header has a dfo number that is less than that of the
      purported header, then the loop has multiple entry points and thus is
      "irreducible." Flagging the loop as irreducible is important because an
      irreducible loop cannot be handled in standard ways for most optimizations.


One final note: the reason for visiting nodes in decreasing order by
dfo number
is to ensure that inner loops are discovered prior to the loops that contain
them. If you adopt the (reasonable) approach that multiple retreating
edges to
the same loop header indicate different latches for the same loop (rather than
trying to identify inner/outer loops with the same header), then the algorithm
above ensures that an inner loop is visited prior to an outer loop that
contains
it. This is very useful for building up the nesting structure of the strongly
connected regions (reducible and irreducible loops) in the control flow graph.


Well, that's probably enough to get you going. Let me know if you have any
questions! Hope this has helped a little bit.


----------------------------------------


>From wjs@vnet.IBM.COM Thu Jan 13 11:23:18 1994


Excerpts from mail: 13-Jan-94 Re: loops in irreducible gr.. V.C.
SREEDHAR@binkley.cs (3324)


> I was thinking more in terms of finding multiple loop headers.
> Different DFO numbering will give different headers??
> I will think more on your line and let you know of it...


You will find all loop headers for the irreducible region using the
algorithm I gave you, by noticing when you have a predecessor whose dfo
number lies outside the loop. The node whose predecessor has this
property is an alternate loop header; an alternate entry point for the
loop.


Thus it does not matter which dfo ordering you use. This only will
change which node is considered to be the initial loop header, and which
are the alternate loop headers. I'm sorry that I didn't make this clear
in my original note.
--

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