Testing Flow Graph Reducibility

Many problems in program optimization have been solved by applying a technique called interval analysis to the flow graph of the program. A flow graph which is susceptible to this type of analysis is called reducible . This paper describes an algorithm for testing whether a flow graph is reducible. The algorithm uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. When the algorithm is implemented on a random access computer, it requires O(E log* E) time to analyze a graph with E edges, where log* x = min{i/log i x≤1}. The time bound compares favorably with the O(E log E) bound of a previously known algorithm.

Authors

• Robert Endre Tarjan

Keywords

• Algorithm
• Code optimization
• Complexity
• Depth-first search
• Directed graph
• Flow analysis
• Flow graph
• Interval analysis
• Program optimization
• Reducibility
• Set union algorithm
• Tree