Abstract
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 0(E logE) time to analyze a graph with E edges, where logx = minCillog11}. The time bound compares favorably with the 0(E log E) bound of a previously known algorithm.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 96-107 |
| Number of pages | 12 |
| Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
| DOIs | |
| State | Published - Apr 30 1973 |
| Externally published | Yes |
| Event | 5th Annual ACM Symposium on Theory of Computing, STOC 1973 - Austin, United States Duration: Apr 30 1973 → May 2 1973 |
All Science Journal Classification (ASJC) codes
- Software
Keywords
- Algorithm
- Code optimization
- Complexity
- Depth-first search
- Directed graph
- Flow analysis
- Flow graph
- Interval analysis
- Program optimization
- Reducibility
- Set union algorithm
- Tree