Abstract
The static single-assignment (SSA) form of a program provides data flow information in a form which makes some compiler optimizations easy to perform. In this paper we present a new, simple method for converting to SSA form, which produces correct solutions for nonreducible control-flow graphs, and produces minimal solutions for reducible ones. Our timing results show that, despite its simplicity, our algorithm is competitive with more established techniques.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. V. Aho, R. Sethi, and J. D. Ullman. Code Optimization and Finite Church-Rosser Systems. In Design and Optimization of Compilers, R. Rustin, ed. Prentice Hall, 1971, pp. 89–105. 118
B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting Equality of Variables in Programs. Proceedings of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, 1988, pp. 1–11. 111
A.W. Appel. SSA is Functional Programming. ACM SIGPLAN 33, 4 (April 1998), pp. 17–20. 111, 112
A. W. Appel. Modern Compiler Implementation in Java. Cambridge, 1998. 111
M. M. Brandis and H. Mössenböck. Single-Pass Generation of Static Single-Assignment Form for Structured Languages. ACM TOPLAS 16, 6 (November 1994), pp. 1684–1698. 122
P. Briggs, T. Harvey, and T. Simpson. Static Single Assignment Construction, Version 1.0. Unpublished document, 1995. 115
J.-D. Choi, R. Cytron, and J. Ferrante. Automatic Construction of Sparse Data Flow Evaluation Graphs. ACM POPL’ 91, pp. 55–66. 122
F. Chow, S. Chan, R. Kennedy, S.-M. Liu, R. Lo, and P. Tu. A New Algorithm for Partial Redundancy Elimination based on SSA Form. ACM PLDI’ 97, pp. 273–286. 123
R. K. Cytron and J. Ferrante. Efficiently Computing φ-Nodes On-The-Fly. ACM TOPLAS 17, 3 (May 1995), pp. 487–506. 122
R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently Computing Static Single-Assignment Form and the Control Dependence Graph. ACM TOPLAS 13, 4 (October 1991), pp. 451–490. 111, 112, 119, 120, 122, 123
R. Cytron, A. Lowry, K. Zadeck. Code Motion of Control Structures in High-Level Languages. Proceedings of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, 1986, pp. 70–85. 122
M. J. Fischer. Efficiency of Equivalence Algorithms. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds. Plenum Press, 1972. 120
M. S. Hecht. Flow Analysis of Computer Programs, North-Holland, 1977. 116, 118
M. S. Hecht and J. D. Ullman. Flow Graph Reducibility. SIAM Journal of Computing 1, 2 (June 1972), pp. 188–202. 115, 118, 119
J. E. Hopcroft and J. D. Ullman. Set Merging Algorithms. SIAM Journal of Computing 2, 4 (December 1973), pp. 294–303. 120
R. Johnson, D. Pearson, and K. Pingali. The Program Structure Tree: Computing Control Regions in Linear Time. ACM PLDI’ 94, pp. 171–185. 122
D. E. Knuth. An Empirical Study of FORTRAN Programs. Software — Practice and Experience 1, 1971, pp. 105–133. 112
D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison Wesley, 1997. 120
D. B. Loveman and R. A. Faneuf. Program Optimization — Theory and Practice. Conference on Programming Languages and Compilers for Parallel and Vector Machines, 1975, pp. 97–102. 122
R. Morgan. Building an Optimizing Compiler, Digital Press, 1998. 115
S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. 111
B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global Value Numbers and Redundant Computations. Proceedings of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, 1988, pp. 12–27. 122
R. M. Shapiro and H. Saint. The Representation of Algorithms. Rome Air Development Center TR-69-313, Volume II, September 1969. 122
V. C. Sreedhar and G. R. Gao. A Linear Time Algorithm for Placing φ-Nodes. Proceedings of the Twenty-Second Annual ACM Symposium on Principles of Programming Languages, 1995, pp. 62–73. 122
R. E. Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. JACM 22, 2 (April 1975), pp. 215–225. 120
J. D. Ullman. Fast Algorithms for the Elimination of Common Subexpressions. Acta Informatica 2, 1973, pp. 191–213. 119
M. N. Wegman and F. K. Zadeck. Constant Propagation with Conditional Branches. ACM TOPLAS 13, 2 (April 1991), pp. 181–210. 111, 112
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aycock, J., Horspool, N. (2000). Simple Generation of Static Single-Assignment Form. In: Watt, D.A. (eds) Compiler Construction. CC 2000. Lecture Notes in Computer Science, vol 1781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46423-9_8
Download citation
DOI: https://doi.org/10.1007/3-540-46423-9_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67263-0
Online ISBN: 978-3-540-46423-5
eBook Packages: Springer Book Archive