Ron Cytron
Jeanne Ferrante
- 1 AHo, A. V., SETm, R., AND ULLMAN, J. D. Compzlers: Princ~ples, Techniques, and Tools. Addison-Wesley, Reading, Mass, 1986. Google Scholar
- 2 ALLEN, F. E., BURKE, M., CHARLES, P., CYTRON, R., AND FERRANrE, J An overview of the PTRAN analysis system for multiprocessing. J. Parallel Distrib. Comput. 5, (Oct. 1988), 617-640. Google Scholar
- 3 ALLEN, J. R Dependence analysis for subscripted variables and ifs application fo program transformations. Ph.D. thesis, Department of Computer Science, Rice Unir., Houstom Tex., Apr. 1983. Google Scholar
- 4 ALLEN, J R , AND JOHNSON, S Compiling C for vectorizatiom parallelization and inline expansion. In Proceedings of the SIGPLAN '88 Symposium on Compiler Construction. SIGPLAN Not. (ACM)23, 7 (June 1988), 241-249 Google Scholar
- 5 ALPERN, B , WE6MAN, M. N., AND ZADECK, F.K. Detectmg equality of values m programs In Coaference Record of the 15th ACM Symposium on Principles of Programming Languages (Jan. 1988), ACM, New York, pp. 1-11. Google Scholar
- 6 BALLANCE, R. A,, MACCABE, A. B., AND OTTENSTEIN, K.J. The program dependence web: A representation supporting control-, data-, and demand driven interpretation of languages. In Proceedings of the SIGPLAN 90 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 25, 6 (June 1990), 257 271. Google Scholar
- 7 BANNING, J.B. An efficient way to find the side effects of procedure calls and the aliases of variables. In Conference Record of the 6th A CM Syrr~po6~urr~ orl Pr~nciples of Frogramrntrlg Languages (Jan. 1979) ACM, New York, pp. 29-41 Google Scholar
- 8 BARTH, J.M. An interprocedural data fiow analysis algorithm. In Conference Record of the 4th ACM Symposium on Princ~ples of Programmmg Languages (Jan. 1977) ACM, New York: pp. 119-131. Google Scholar
- 9 BURKE, M. An interval-based approach fo exhaustive and incremental interprocedural data fiow analysis. ACM Traas. Program Lang. Syst. 12, 3 (July 1990), 341-395. Google Scholar
- 10 BURKE, M., AND CYTRON, R. Interprocedural dependence analysis and parallelization. In Proceedings of the SIGPLAN 86 Symposium on Compiler Construction SIGPLAN Not (ACM) 2J, 7 (June 1986), 162 {75. Google Scholar
- 11 CARTWRIGHT, R., AND FELLEISEN, M. The semantics of program dependence. In Proceedings of the SIGPLAN 89 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 24, 7 (July 1989), 13-27. Google Scholar
- 12 CHAITIN, G. J. Register allocation and spilling via graph coloring. In Proceedings of the SIGPLAN 82 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 17, 43 (June 1982), 98-105. Google Scholar
- 13 CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. Register allocation via eoloring. Comput. Lang. 6 (1981), 47-57.Google Scholar
- 14 CHASE, D.R. Safety considerations for storage allocation optimizations. In Proceed~ngs of the SIGPLAN 88 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 23, 7 (June 1988), 1-10. Google Scholar
- 15 CHASE, D. R., WEGMAN, M. AN~ ZADECK, F. K. Analysis of pointers and structures. In Proceedings of the SIGPLAN 90 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 25, (June 1990), 296-310. Google Scholar
- 16 CHOI, J., CYTRON, R., AND FERRANTE, J. Automatic construction of sparse data fiow evaluation graphs. In Conference Record of the 18th ACM Symposium on Principles of Programming Languages (Jan. 1991). ACM, New York, pp. 55-66. Google Scholar
- 17 Csow, F. C. A portable machine-independent global optimizer--Design and measurements. Ph.D. thesis and Tech. Rep. 83-254, Computer Systems Laboratory, Stanford Univ., Stanford, Calif., Dec. 1983. Google Scholar
- 18 CHow, F. C., AND HENNESSY, J.L. The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst. 12, 4 (Oct. 1990), 501-536. Google Scholar
- 19 COOPER, K. D. Interprocedural data flow analysis in a programmmg environment. Ph.D. thesis, Dept. of Mathematical Sciences, Rice Univ., Houston, Tex., 1983. Google Scholar
- 20 CYTRON, R., AND FERRANTE, J. An improved control dependence algorithm. Tech. Rep. RC 13291, IBM Corp., Armouk, N.Y., 1987.Google Scholar
- 21 CYTRON, R., AND FERRANTE, J. What's in a name? In Proceedings ofthe 1987 International Conference on Parallel Processing (Aug. 1987), pp. 19-27.Google Scholar
- 22 CYTRON, R., LowRY, A., AND ZADECK, F.K. Code motion of control structures in high-level languages. In Conference Record of the 13th ACM Symposium on Principles of Programming Languages (Jan. 1986). ACM, New York, pp. 70-85. Google Scholar
- 23 DENNIS, J.B. First version of a data fiow procedure language. Tech. Rep. Comput. Struc. Group Memo 93 (MAC Tech. Memo 61), MIT, Cambridge, Mass., May 1975.Google Scholar
- 24 FERRANTE, J., OTTENSTEIN, K. J., AND WARREN, J.D. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (July 1987), 319-34!). Google Scholar
- 25 GIEGERICH, e. A formal framework for the derivation of machine-specific optimizers. ACM Trans. Program. Lang. Syst. 5, 3 (July 1983), 478-498. Google Scholar
- 26 HAREL, D. A linear time algorithm for finding dominators in flow g~aphs and related problems. In Proceedings of the 17th ACM Symposium on Theory of Computing (May 1985). ACM, New York, pp. 185-194. Google Scholar
- 27 HORWITZ, S., PFE~FFER, P., AND REPS, T. Dependence analysis for pointer variables. In Proceedings of the SIGPLAN 89 Symposium on Compiler Construction. SIGPLAN Not. (ACM) 24, 7 (June 1989). Google Scholar
- 28 HORWITZ, S., PRINS, J., ANa REPS, T. Integrating non-interfering versions of programs. ACM Trans. Program. Lang. Syst. 11, 3 (July 1989), 345-387. Google Scholar
- 29 JONES, N. D., AND MUCHMCK, S.S. Flow analysis and optimization of LISP-like structures. In Program Flow Analysis, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J., 1981, chap. 4, pp. 102-131.Google Scholar
- 30 KENNEDY, K. W. Global dead computation elimination. Tech. Rep. SETL Newsl. 111, Courant Institute of Mathematical Sciences, New York Univ., New York, N.Y., Aug. 1973.Google Scholar
- 31 KENNEDY, K.W. A survey of data fiow analysis techniques. In Program Flow Analysis, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J., 1981.Google Scholar
- 32 KucK, D.J. The Structure of Computers and Computations. Wiley, New York, 197'8. Google Scholar
- 33 LARUS, J.R. Restructuring symbolic programs for concurrent execution on multiprocessors. Tech. Rep. UCB/CSD 89/502, Computer Science Dept., Univ. of Cahfornia at Berkeley, Berkeley, Calif., May 1989. Google Scholar
- 34 LARUS, J R., AND HILFINGER, P. N Detecting confiicts between structure accesses In Proceedings of the ACM SIGPLAN 88 Symposium on Compiler Constructmn. SIGPLAN Not. 23, 7 (July 1988), 21-34. Google Scholar
- 35 LENGA~ER, T., AND TARJAN, R.E. A fast algorithm for finding dominators m a fiowgraph. ACM Trans. Program. Lang. Syst. 1, I (July 1979), 121-141 Google Scholar
- 36 MUCHMCK, S. S., AND JONES, N. D , EDS Program Flow Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1981Google Scholar
- 37 MYERS, E.W. A precise interprocedura} data fiow algorithm. In Conference Record of the 8th ACM Symposium on Princ~ples of Programm~ng Languages (Jan. 1981). ACM, New York, pp. 219-230. Google Scholar
- 38 O~CENSTEIN, K. J. Data-fiow graphs as an mtermediate form. Ph.D. thesis, Dept. of Computer Science, Purdue Univ., W. Lafayette, Ind., Aug. 1978. Google Scholar
- 39 POIN~ER, L. Perfect report: 1. Tech. Rep CSRD 896, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, Urbana, Ill., July 1989Google Scholar
- 40 REIF, J. H., AND LEWIS, H.R. Efficient symbolic analysis ofprograms. J. Comput. Syst. Sc~. 32, 3 (June 1986), 280-313. Google Scholar
- 41 RE~F, J. H., A~D TARJAN, R. E Symbolic program analysis in almost linear rime. SIAM J. Comput. 11, i (Feb. 1982), 81-93Google Scholar
- 42 ROSEN, B. K. Data fiow analysis for procedural languages J. ACM 26, 2 (Apr. 1979), 322-344. Google Scholar
- 43 ROSEN, B. K , WEGMAN, M. N., AND ZAnECK, F.K. Global value numbers and redundant computations. In Conference Record of the 15th ACM Symposium on Prmciples of Programming Languages, (Jan. 1988). ACM, New York, pp. 12-27. Google Scholar
- 44 RUGGmRI, C., ANn MURTAQH, T. P. Lifetime analysis of dynamically allocated objects. In Conference Record of the 15th ACM Symposium on Princ~ples of Programming Languages (Jan. 1988). ACM, New York, pp. 285-293. Google Scholar
- 45 SHAPIRO, R. M, AND SAI~T, H The representation of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, Feb. 1970.Google Scholar
- 46 SMIT~, B. T., BO~LE, J. M., DONGARRA, J. J., GA~BOW, B. S., I~EBE, Y., KLEMA, V. C., AND MOLER, C B. Matr~x Eigensystem Routines-Eispack Guide. Springer-Verlag, New York, 1976.Google Scholar
- 47 TARJAN, R.E. Finding dominators in directed graphs. SIAM J. Comput 3, i (1974), 62-89.Google Scholar
- 48 WEaSREI% B Property extraction in well-founded property sets. IEEE Trans. Softw. Eng. SE-l, 3 (Sept. 1975), 270-285.Google Scholar
- 49 WEGMAN, M. N, AND ZADECK, F. K. Constant propagation with conditional branches. In Conference Record of the 12th ACM Symposium o~ Prmczples of Programm~ng Languages (Jan.). ACM, New York, pp. 291-299. Google Scholar
- 50 WEGMA~, M. N., A~D ZADECK, F. K. Constant propagation with conditioual branches. ACM Trans. Program. Lang. OEYst. To be pubtished. Google Scholar
- 51 WOLFE, M.J. Optimizing supercompilers for supercomputers. Ph.D. thesis, Dept of Computer Science, Univ. of Illinois at Urbana~Champaign, Urbana {ll., 1982 Google Scholar
- 52 YANG, W., t~IoRwITZ, S., AND REPS, T. Detecting program components with eqmvalent behaviors. Tech Rep. 840~ Dept. of Computer Science, Univ. of Wisconsin at Madison, Madison, Apr. 1989Google Scholar
Index Terms
- Efficiently computing static single assignment form and the control dependence graph
Recommendations
On the control dependence in the program dependence graph
CSC '88: Proceedings of the 1988 ACM sixteenth annual conference on Computer scienceThe program dependence graph, PDG, is used to represent the data and control dependencies between the statements of some program. The data dependencies between the statements are fully understood and they correspond to the definition-use chain. On the ...
Using static single assignment form to improve flow-insensitive pointer analysis
A pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this ...
Algorithms for computing the static single assignment form
The Static Single Assignment (SSA) form is a program representation used in many optimizing compilers. The key step in converting a program to SSA form is called ϕ-placement. Many algorithms for ϕ-placement have been proposed in the literature, but the ...
Reviews
Benjamin Rayborn Seyfarth
The authors present strong arguments for the practicality and utility of the static single assignment (SSA) form and the control dependence graph (CDG) in optimizing compilers. They use the concept of a dominator tree to formalize the concept of dominance frontiers and use this to derive efficient algorithms for computing the SSA form and the CDG. They show that their algorithms require linear time for programs restricted to straight-line code, that is, if-then-else and while-do constructs. They also present experimental evidence that suggests that their algorithms are linear for typical programs. This paper is important, since SSA and CDG have been proposed as useful data structures for optimization without practical algorithms. It is well written and moderately long (40 pages), which is essential for describing the authors' algorithms adequately. An extensive bibliography points to excellent papers on compiler optimization techniques. Both compiler writers and theorists will find this paper useful.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments