Browse Prior Art Database

Method for Efficient Detection of Nodes in a Multi-Entry Loop of a Flow Graph

IP.com Disclosure Number: IPCOM000105698D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 152K

Publishing Venue

IBM

Related People

Makino, S: AUTHOR

Abstract

Disclosed is a method for detecting nodes efficiently inside a multi-entry loop of a flow graph. Detecting nodes inside a loop often plays an important role in program analysis. When a flow graph has no multi-entry loops, a straightforward application of depth-first search [*] may yield an efficient solution. When it has multi-entry loops, however, an efficient solution is not trivial. Our method give an efficient method for detecting nodes in a multi-entry loop.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Method for Efficient Detection of Nodes in a Multi-Entry Loop of a Flow Graph

      Disclosed is a method for detecting nodes efficiently inside a
multi-entry loop of a flow graph.  Detecting nodes inside a loop
often plays an important role in program analysis.  When a flow graph
has no multi-entry loops, a straightforward application of
depth-first search [*]  may yield an efficient solution.  When it has
multi-entry loops, however, an efficient solution is not trivial.
Our method give an efficient method for detecting nodes in a
multi-entry loop.

      Description of Problems - Fig. 2 shows an example of a flow
graph and depth-first search.  In the figure, 's' and 't' represent
the 'start' and 'end' nodes of a flow graph, respectively.  A
depth-first search visits all the nodes of a flow graph beginning at
the start node and searching the entire graph, trying to visit nodes
far away from the start node as quickly as possible (depth first).
That is, beginning at the start node, visit a node, and if it has a
successor which is not visited yet, then visit the successor.  If a
visited node has no successor or all of its successors have already
been visited ('the node was traversed'), select the most recently
visited node which has not been traversed yet, and if the node has a
successor which has not been visited yet, then visit the successor.
In Fig. 2, the two numbers in parentheses at each node are the
pre-visit and post-visit numbers in depth-first search.

      Pre-visit numbers represent the order in which the nodes were
visited in depth-first search.  Post-vist numbers represent the order
in which the nodes were traversed.  A depth-first search classifies
each edge of a flow graph into four types, namely, 'tree', 'back',
'forward', and 'cross' edges.  In Fig. 2, these edges are represented
by the labels 'T' (Tree), 'B' (Back), 'F'(Forward), and 'C'(Cross).

      In a flow graph, each edge has origin and destination nodes
(Fig. 1) A back edge indicates that there is a loop in a flow graph.
The destination node of a back edge is called the 'head' of a loop.

The origin node of a back edge is called the 'tail' of a loop.  A
loop is formed by a set of back edges which have the same destination
node.  For example, the back edges in Fig. 2 are <g,d>  and <f,d>.
These back edges form a loop whose head is 'd' and whose tails are
'f' and 'g'.

      Nodes in a loop are defined by those nodes on every path, from
the head to the tails, that contain no back edges.  For example, in
Fig. 2, the nodes in the loop are 'd', 'e', 'f', and 'g'.  This loop
has only one entry node, 'd'.  When a loop has only one entry node
(namely, the loop head), we can easily detect nodes in a loop by
searching for edges in a backward direction, avoiding back edges from
tails to the head.  In this case, an efficient search of edges is
possible, because no nodes except for those in the loop are visited.
In Fig. 4,...