Abstract
Data-flow analyses usually associate information with control-flow regions. Informally, if these regions are too small, like a point between two consecutive statements, we call the analysis dense. On the other hand, if these regions include many such points, then we call it sparse. Sparse analyses have advantages over their dense versions: They tend to run faster and require less storage space. The Static Single Assignment form already lets us implement sparse versions of several static analyses, such as constant propagation. Additionally, it is possible to augment this representation to support sparse versions of many other analyses. Key to these extensions is the so-called Single Information Property. We say that a given superset of the SSA form representation bears this property for some data-flow analysis if the data-flow information associated with a variable remains invariant along the entire live range of that variable. This chapter explains which static analyses admit the single information property, and how the said property can be achieved via extensions of the SSA form. It also shows that these SSA extensions are equivalent to techniques originally conceived to support sparse data-flow analyses, such as the Static Single Information form or Sparse Evaluation Graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In an ideal world, with monotone framework and lattice of finite height.
- 2.
Actually, class inference is no longer a PVP as soon as we want to propagate the information through copies.
References
Allen, F. E. (1970). Control flow analysis. Sigplan Notices, 5(7), 1–19 (1970).
Allen, F. E., & Cocke, J. (1976). A program data flow analysis procedure. Communications of the ACM, 19(3), 137–146.
Gawlitza, T., et al. (2009). Polynomial precise interval analysis revisited. Efficient Algorithms, 1, 422–437.
George, L., & Matthias, B. (2003). Taming the IXP network processor. In International Conference on Programming Languages Design and Implementation. PLDI ’03 (pp. 26–37).
Johnson, R., Pearson, D., & Pingali, K. (1994). The program tree structure. In International Conference on Programming Languages Design and Implementation. PLDI ’94 (pp. 171–185).
Lo, R., et al. (1998). Register promotion by sparse partial redundancy elimination of loads and stores. In International Conference on Programming Languages Design and Implementation. PLDI ’98 (pp. 26–37).
Pingali, K., & Bilardi, G. (1995). APT: A data structure for optimal control dependence computation. In International Conference on Programming Languages Design and Implementation. PLDI ’95 (pp. 211–222).
Pingali, K., & Bilardi, G. (1997). Optimal control dependence computation and the roman chariots problem. In ACM Transactions on Programming Language and Systems (pp. 462–491) (1997).
Plevyak, J. B. (1996). Optimization of Object-Oriented and Concurrent Programs. PhD Thesis. University of Illinois at Urbana-Champaign.
Su, Z., & Wagner, D. (2005). A class of polynomially solvable range constraints for interval analysis without widenings. Theoretical Computeter Science, 345(1), 122–138.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Pereira, F.M.Q., Rastello, F. (2022). Static Single Information Form. In: Rastello, F., Bouchez Tichadou, F. (eds) SSA-based Compiler Design. Springer, Cham. https://doi.org/10.1007/978-3-030-80515-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-80515-9_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80514-2
Online ISBN: 978-3-030-80515-9
eBook Packages: Computer ScienceComputer Science (R0)