|
Warning: The download time has expired please click on the item to try again.
 ABSTRACT
Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far foward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type of determination). We present four algorithms in this paper, all conservitive in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant progagation. Several variants of this algorithm are considered.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
|
| |
2
|
ALLEN, F. E. A catalogue of optimizing transformations. In Design and Optimizat~on of Compilers. R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J, 1972, pp. 1-30.
|
| |
3
|
ALLEN, F.E. Interprocedural data fiow analysis. Inf. Proc. 74 (1974), 398-402.
|
| |
4
|
ALLEN, F. E., CARTER, J. L., FABRI, J., FERRANTE, J., HARRISON, W. H., LOEWNER, P. G., AND TREVmLYAN, L. H. The experimental compiling system. IBM J. Res. Dev. 24, 6 (Nov. 1980), 695-715.
|
 |
5
|
B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States
[doi> 10.1145/73560.73561]
|
| |
6
|
A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States
[doi> 10.1145/75277.75303]
|
| |
7
|
|
| |
8
|
|
| |
9
|
|
| |
10
|
BURKE, M. An interval approach toward interprocedural analysis. Tech. Rep. RC 10640 47724, IBM, July 1984.
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F.K. Efficiently computing statie single assignment form and the control dependence graph. Tech. Rep. RC 14756, IBM, revised Mar. 1991.
|
| |
17
|
|
| |
18
|
ERSHOV, A. P. On the essence of compilation. In IFIP Working Conference on Formal Description of Programming Concepts. (Aug. 1977).
|
| |
19
|
|
| |
20
|
FURTNEY, M. AND PRATT, T.W. Kernel-control tailoring of sequential programs for parallel execution. In Proceedings of the 1982 International Conference on Parallel Processing. (Aug. 1982), pp. 245-247.
|
| |
21
|
|
| |
22
|
HARRISON, W.H. Compiler analysis of the value ranges for variables. IEEE Trans. Softw. Eng. SE-3, 3 (May 1977), 243-250.
|
| |
23
|
HOLLEY, L. H. AND ROSEN, B.K. Qualified data fiow problems. IEEE Trans. Softw. Eng. SE-7, I (Jan. 1981), 60-78.
|
| |
24
|
|
| |
25
|
KAM, J. B. AND ULLMAN, J. D. Monotone data fiow analysis frameworks. Acta Inf. 7 (1977), 305-317.
|
| |
26
|
|
| |
27
|
|
| |
28
|
MUCSMCK, S. S. AND JONES, N. D, Eds. Program Flow Analysis. Prentice~Hall, Englewood Cliffs, N.J., 1981.
|
| |
29
|
|
| |
30
|
O~rENSTE~N, K. J. Data-fiow graphs as an intermediate form. Ph.D. thesis, Dept. of Computer Science, Purdue Univ., Aug. 1978.
|
| |
31
|
PRATT, T. W. Program analysis and optimization through kernel-control decomposition. Acta Inf. 9 (1978), 195-216.
|
| |
32
|
|
| |
33
|
|
| |
34
|
REIF, J. H. AND T~JAN, R.E. Symbolic program analysis in almost linear time. SIAM J. Comput. 11, I (Feb. 1982), 81-93.
|
| |
35
|
|
| |
36
|
|
| |
37
|
|
| |
38
|
B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States
[doi> 10.1145/73560.73562]
|
| |
39
|
|
| |
40
|
SsAPmo, R. M. AND SAI~T, H. The representat~on of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, Feb. 1970.
|
| |
41
|
|
| |
42
|
WEaSREIT, B. Property extraction in well-founded property sers IEEE Trans. Softw. Eng SE-l, 3 (Sept 1975), 270-285.
|
| |
43
|
|
| |
44
|
|
CITED BY 102
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Robert Kennedy , Sun Chan , Shin-Ming Liu , Raymond Lo , Peng Tu , Fred Chow, Partial redundancy elimination in SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.627-676, May 1999
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, ACM SIGPLAN Notices, v.32 n.5, p.273-286, May 1997
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, ACM SIGPLAN Notices, v.39 n.7, July 2004
|
|
|
|
|
|
|
|
|
|
|
|
John Field , G. Ramalingam , Frank Tip, Parametric program slicing, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.379-392, January 23-25, 1995, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eric Stoltz , Michael Wolfe , Michael P. Gerlek, Constant propagation: a fresh, demand-driven look, Proceedings of the 1994 ACM symposium on Applied computing, p.400-404, March 06-08, 1994, Phoenix, Arizona, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Daniel Luna , Mikael Pettersson , Konstantinos Sagonas, HiPE on AMD64, Proceedings of the 2004 ACM SIGPLAN workshop on Erlang, p.38-47, September 22-22, 2004, Snowbird, Utah, USA
|
|
|
|
|
|
Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, ACM SIGPLAN Notices, v.40 n.7, July 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steve Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Exploring the structure of the space of compilation sequences using randomized search algorithms, The Journal of Supercomputing, v.36 n.2, p.135-151, May 2006
|
|
|
Nurit Dor , Tal Lev-Ami , Shay Litvak , Mooly Sagiv , Dror Weiss, Customization change impact analysis for erp professionals via program slicing, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thomas J. Marlowe , William G. Landi , Barbara G. Ryder , Jong-Deok Choi , Michael G. Burke , Paul Carini, Pointer-induced aliasing: a clarification, ACM SIGPLAN Notices, v.28 n.9, p.67-70, Sept. 1993
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
D.
Software
D.3
PROGRAMMING LANGUAGES
D.3.4
Processors
Subjects:
Optimization
Additional Classification:
D.
Software
D.3
PROGRAMMING LANGUAGES
D.3.4
Processors
Subjects:
Compilers
I.
Computing Methodologies
I.2
ARTIFICIAL INTELLIGENCE
I.2.2
Automatic Programming
Subjects:
Program transformation
General Terms:
Algorithms,
Design,
Languages,
Performance
Keywords:
abstract interpretation,
code optimization,
constant propagation,
control flow graph,
interprocedural analysis,
procedure integration,
static single assignment form,
type determination
REVIEW
"Anne De Niel : Reviewer"
Constant propagation is a way to discover which values in a program
remain constant over all possible program executions. The purpose of
constant propagation is optimization. The authors discuss several
existing algorithms by relating them to
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf