Browse Prior Art Database

Computing Cycle Dominators

IP.com Disclosure Number: IPCOM000085382D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 70K

IBM

Related People

Chandra, AK: AUTHOR

Abstract

Given a flow chart program, there is described herein a method for constructing the control graph of the flow chart - a directed graph where each node in the graph corresponds to a statement in the flow chart, and there is an edge between two nodes corresponding to two statements of the flow chart if control can flow from the first statement to the second. Then, given a statement in the flow chart (equivalently, a node in the graph), the method determines the set of all statements in the flow chart (equivalently, nodes in the graph) that cycle-dominate the given node (a node A cycle-dominates a node B if every cycle from A to itself must pass through B). Running time of the algorithm is O(E) where E is the number of edges in the graph.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Computing Cycle Dominators

Given a flow chart program, there is described herein a method for constructing the control graph of the flow chart - a directed graph where each node in the graph corresponds to a statement in the flow chart, and there is an edge between two nodes corresponding to two statements of the flow chart if control can flow from the first statement to the second. Then, given a statement in the flow chart (equivalently, a node in the graph), the method determines the set of all statements in the flow chart (equivalently, nodes in the graph) that cycle-dominate the given node (a node A cycle-dominates a node B if every cycle from A to itself must pass through B). Running time of the algorithm is O(E) where E is the number of edges in the graph.

Fast methods for finding cycle dominators find applications in algorithms of cutting cycles in a graph [1] and finding inner loops of programs [2].

The method works as follows: First a prime cycle is found from the given node A to itself. This can be done quickly (time O(E)) for example by Tarjan's depth-first search technique [3]. If there is no such cycle, all nodes cycle- dominate A. Otherwise, only the nodes on the cycle can possibly dominate A. The cycle is stored in array ([1], ...,C[k].

The methods sets an integer variable "frontier" to a value corresponding to the first node C[frontier] in the cycle that could dominate A. It then does a depth- first search starting from A. If the node C[frontier] is reached, edges leading from this node are not used for continuing the search.

If a node is reache...