The program structure tree
Richard Johnson, David Pearson, Keshav K. Pingali · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1994
In this paper, we describe the program structure tree (PST), a hierarchical representation of program structure based on single entry single exit (SESE) regions of the control flow graph. We give a linear-time algorithm for finding SESE regions and for building the PST of arbitrary control flow graphs (including irreducible ones). Next, we establish a connection between SESE regions and control dependence equivalence classes, and show how to use the algorithm to find control regions in linear time. Finally, we discuss some applications of the PST. Many control flow algorithms, such as construction of Static Single Assignment form, can be speeded up by applying the algorithms in a divide-and-conquer style to each SESE region on its own. The PST is also used to speed up data flow analysis by exploiting “sparsity”. Experimental results from the Perfect Club and SPEC89 benchmarks confirm that the PST approach finds and exploits program structure.
Cited by 191 works. doi:10.1145/178243.178258
Authors
References
- The program dependence graph and its use in optimization
- A program data flow analysis procedure
- Efficiently computing static single assignment form and the control dependence graph
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- A fast algorithm for finding dominators in a flowgraph
- Program Flow Analysis: Theory and Application
- Automatic construction of sparse data flow evaluation graphs
- The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages
- Incremental data flow analysis in a structured program editor
- Elimination algorithms for data flow analysis