Constant propagation with conditional branches

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant propagation with conditional branches

Full text

Pdf (1.03 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages table of contents

New Orleans, Louisiana, United States

Pages: 291 - 299

Year of Publication: 1985

ISBN:0-89791-147-4

Authors

Mark N. Wegman	IBM T. J. Watson Research Center, Yorktown Heights, New York
Frank Kenneth Zadeck	IBM T. J. Watson Research Center, Yorktown Heights, New York

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 35, Citation Count: 44

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/318593.318659 What is a DOI?

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	[ACFF80] Allen, F. E., Carter, J. L., Fabri, J., Ferrante, J., Harrison, W. H., Loewner, P. G., Trevillyan, L. H., The Experimental Compiling System. IBM Journal of Research and Development, Nov. 1980, vol. 24. no. 6, page 695-715.
	2	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	3	[AlCo72] Alien, F. E., Cocke. J., A catalogue of optimizing transformations. Design and Optimization of Compilers, Rustin, R. (Ed.). Printice-Hall, Englewood Cliffs, N. J., July 1972. This was also published as IBM Research Report No. RC3548.
	4	Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
	5	J. Eugene Ball, Predicting the effects of optimization on a procedure body, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.214-220, August 06-10, 1979, Denver, Colorado, United States
	6	[Ersh77] Ershov. A. P., On the essence of compilation. IFIP Working Conference on Formal Description of Programming Concepts, Aug. 1977.
	7	[FeOt82] Ferrante, J., Ottenstein, K. J., A program form based on data dependency in predicate regions., Nov 1982. no. RC-9685.
	8	[FuPr82] Furtney, M., Pratt, T. W., Kernal-control tailoring of sequential programs for parallel execution. Proceedings of the 1982 International Conference on Parallel Processing, Aug. 1982, page 245-247.
	9	Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
	10	[Harr77] Harrison, W. H., Compiler analysis of the value ranges for variables. IEEE Transactions on Software Engineertng, May 1977, vol. SE-3, no. 3, page 243-250.
	11	John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
	12	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
	13	[Prat78] Pratt, T. W., Program analysis and optimization through kernal-control decomposition. Acta Informatica Processing, 1978, vol. 9, page 195-216.
	14	John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
	15	[ReLe82] Reif, J. H., Lewis, H. R., Symbolic evaluation and the global value graph. published by Harvard University, Aiken Computation Laboratory, 1982, no. TR-37-82.
	16	[ReTa81] Reif, J. H., Tarjan. R. E., Symbolic program analysis in almost linear time. SIAM Journal of Computing, Feb. 1981, vol. 11. no. 1, page 81-93.
	17	Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
	18	Aaron Melvin Tenenbaum, Type determination for very high level languages., New York University, New York, NY, 1974
	19	[Wegb75] Wegbreit, B., Property extraction in well-founded property sets. IEEE Transactions on Software Engineering, Sept. 1975, volume se-l, number 3, page 270-285.
	20	Mark N. Wegman, General and efficient methods for global code improvement, University of California, Berkeley, 1981
	21	Mark Wegman, Summarizing graphs by regular expressions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.203-216, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567088]
	22	Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

CITED BY 44

	Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States
	Jonathan M. Asuru, Optimization of array subscript range checks, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.109-118, June 1992
	Michael Burke , Ron Cytron , Jeanne Ferrante , Wilson Hsieh , Vivek Sarkar , David Shields, Automatic discovery of parallelism: a tool and an experiment (extended abstract), ACM SIGPLAN Notices, v.23 n.9, p.77-84, Sept. 1988
	Karthik Gargi, A sparse algorithm for predicated global value numbering, ACM SIGPLAN Notices, v.37 n.5, May 2002
	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991
	Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, ACM SIGPLAN Notices, v.25 n.6, p.337-351, Jun. 1990
	Richard Johnson , Keshav Pingali, Dependence-based program analysis, ACM SIGPLAN Notices, v.28 n.6, p.78-89, June 1993
	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
	Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-Mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGPLAN Notices, v.35 n.11, p.222-233, Nov. 2000
	Zhiyuan Li , Pen-Chung Yew, Efficient interprocedural analysis for program parallelization and restructuring, ACM SIGPLAN Notices, v.23 n.9, p.85-99, Sept. 1988
	Dhruva R. Chakrabarti , Prithviraj Banerjee, Global optimization techniques for automatic parallelization of hybrid applications, Proceedings of the 15th international conference on Supercomputing, p.166-180, June 2001, Sorrento, Italy
	Rajiv Gupta, A fresh look at optimizing array bound checking, ACM SIGPLAN Notices, v.25 n.6, p.272-282, Jun. 1990
	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States
	Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States
	Christine Eisenbeis , Jean-Claude Sogno, A general algorithm for data dependence analysis, Proceedings of the 6th international conference on Supercomputing, p.292-302, July 19-24, 1992, Washington, D. C., United States
	Harold Johnson, Data flow analysis for `intractable' system software, ACM SIGPLAN Notices, v.21 n.7, p.109-117, July 1986
	Edward Wang , Paul N. Hilfinger, Analysis of recursive types in Lisp-like languages, ACM SIGPLAN Lisp Pointers, v.V n.1, p.216-225, Jan. 1992
	Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986
	Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, ACM SIGPLAN Notices, v.37 n.1, p.270-282, Jan. 2002
	Vugranam C. Sreedhar , Guang R. Gao, A linear time algorithm for placing &phgr;-nodes, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 23-25, 1995, San Francisco, California, United States
	Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States
	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991
	Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida
	Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
	R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States
	Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993
	Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States
	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.39 n.4, April 2004
	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Jong-Deok Choi , R. Cytron , J. Ferrante, On the Efficient Engineering of Ambitious Program Analysis, IEEE Transactions on Software Engineering, v.20 n.2, p.105-114, February 1994
	Daniel A. Connors , Hillery C. Hunter , Ben-Chung Cheng , Wen-mei W. Hwu, Hardware support for dynamic activation of compiler-directed computation reuse, ACM SIGOPS Operating Systems Review, v.34 n.5, p.222-233, Dec. 2000
	Keshav Pingali , Micah Beck , Richard Johnson , Mayan Moudgill , Paul Stodghill, Dependence flow graphs: an algebraic approach to program dependencies, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-78, January 21-23, 1991, Orlando, Florida, United States
	Fabrice Le Fessant , Luc Maranget, Optimizing pattern matching, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Chih-Ping Chu , Doris L. Carver, Parallelizing Subroutines in Sequential Programs, IEEE Software, v.11 n.1, p.77-85, January 1994
	Gaetano Borriello , Andrew R. Cherenson , Peter B. Danzig , Michael N. Nelson, RISCs vs. CISCs for Prolog: a case study, ACM SIGARCH Computer Architecture News, v.15 n.5, p.136-145, Oct. 1987
	Michael G. Burke , Ron K. Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Xipen Shen , Yaoqing Gao , Chen Ding , Roch Archambault, Lightweight reference affinity analysis, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	Dhruva R. Chakrabarti , Prithviraj Banerjee, Static Single Assignment Form for Message-Passing Programs, International Journal of Parallel Programming, v.29 n.2, p.139-184, April 2001
	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986
	R. Allen , S. Johnson, Compiling C for vectorization, parallelization, and inline expansion, ACM SIGPLAN Notices, v.23 n.7, p.241-249, July 1988
	Alexander Sakharov, Propagation of constants and assertions, ACM SIGPLAN Notices, v.29 n.5, p.3-6, May 1994
	Vugranam C. Sreedhar , Guang R. Gao , Yong-fong Lee, Incremental computation of dominator trees, ACM SIGPLAN Notices, v.30 n.3, p.1-12, March 1993
	Cindy Rubio-González , Haryadi S. Gunawi , Ben Liblit , Remzi H. Arpaci-Dusseau , Andrea C. Arpaci-Dusseau, Error propagation analysis for file systems, ACM SIGPLAN Notices, v.44 n.6, June 2009