ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
An algorithm for reduction of operator strength
Full text PdfPdf (608 KB)
Source
Communications of the ACM archive
Volume 20 ,  Issue 11  (November 1977) table of contents
Pages: 850 - 856  
Year of Publication: 1977
ISSN:0001-0782
Authors
John Cocke  IBM Thomas J. Watson Research Center, Yorktown Heights, NY
Ken Kennedy  Rice Univ., Houston, TX
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 31,   Citation Count: 25
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/359863.359888
What is a DOI?

ABSTRACT

A simple algorithm which uses an indexed temporary table to perform reduction of operator strength in strongly connected regions is presented. Several extensions, including linear function test replacement, are discussed. These algorithms should fit well into an integrated package of local optimization algorithms.


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
Allen, F.E. Program Optimization. Annual Review of Automatic Programming, Vol. 5, Pergamon Press, New York, 1969.
 
2
John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
 
3
Kennedy, K. A global flow analysis algorithm. Int. J. Comptr. Math., Sect. A, 3 (Dec. 1971), 5-15.
 
4
Hecht, M.S., and Ullman, J.D. Flow graph reducibility. SlAM J. Compmg. 1, 2 (June 1972), 188-202.
5
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]
 
6
Ullman, J. D. Fast algorithms for the elimination of common subexpressions. Acta lnformatica 2 (1973), 191-213.
7
C. P. Earnest , K. G. Balke , J. Anderson, Analysis of Graphs by Ordering of Nodes, Journal of the ACM (JACM), v.19 n.1, p.23-42, Jan. 1972  [doi>10.1145/321679.321683]
8
Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
 
9
Kennedy, K. Variable subsumption with constant folding. SETL York, Feb. 1974.
 
10
Kennedy, K. Use-definition chains with applications. Tech. Rep. 476-093-9, Dept. Math. Sci., Rice U., Houston, Tex., April 1975.
 
11
Kennedy, K. Safety of code motion. Int. J. Comptr. Math., Sect. A, 3 (1972), 117-130.
 
12
Coeke, J., and Kennedy, K. Profitability computations on program flow graphs. Tech. Rep. 476-093-3, Dept. Math. Sci., Rice U., Houston, Tex., May 1974.

CITED BY  25
Karl J. Ottenstein, A Simplified Framework for Reduction in Strength, IEEE Transactions on Software Engineering, v.15 n.1, p.86-92, January 1989
Michael Wolfe, Beyond induction variables, ACM SIGPLAN Notices, v.27 n.7, p.162-174, July 1992
Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998
Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas
A. Rudmik , E. S. Lee, Compiler design for efficient code generation and program optimization, ACM SIGPLAN Notices, v.14 n.8, p.127-138, August 1979
S. Jain , C. Thompson, An efficient approach to data flow analysis in a multiple pass global optimizer, ACM SIGPLAN Notices, v.23 n.7, p.154-163, July 1988
Robert J. Sheraga , John L. Gieser, Automatic microcode generation for horizontally microprogrammed processors, ACM SIGMICRO Newsletter, v.12 n.4, p.154-168, Dec. 1981
Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, 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
Yanhong A. Liu , Tim Teitelbaum, Caching intermediate results for program improvement, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-201, June 21-23, 1995, La Jolla, California, United States
Micha Sharir, Some Observations Concerning Formal Differentiation of Set Theoretic Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.196-225, April 1982
Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996
Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987
Robert Paige, Future directions in program transformations, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
Jeanne Ferrante , Karl J. Ottenstein, A program form based on data dependency in predicate regions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.217-236, January 24-26, 1983, Austin, Texas
Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982
Yanhong A. Liu , Scott D. Stoller, Eliminating dead code on recursive data, Science of Computer Programming, v.47 n.2-3, p.221-242, May 2003
Mark S. Johnson , Terrence C. Miller, Effectiveness of a machine-level, global optimizer, ACM SIGPLAN Notices, v.21 n.7, p.99-108, July 1986
Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
J. A. N. Lee, Biographies, IEEE Annals of the History of Computing, v.24 n.4, p.53-55, October 2002
Yanhong A. Liu , Scott D. Stoller , Michael Gorbovitski , Tom Rothamel , Yanni Ellen Liu, Incrementalization across object abstraction, ACM SIGPLAN Notices, v.40 n.10, October 2005
Gautam , S. Rajopadhye, Simplifying reductions, ACM SIGPLAN Notices, v.41 n.1, p.30-41, January 2006
Yanhong A. Liu , Scott D. Stoller , Ning Li , Tom Rothamel, Optimizing aggregate array computations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.91-125, January 2005
Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998

INDEX TERMS

Keywords:
compilers, operator strength reduction, optimization of compiled code, program analysis, strongly connected region, test replacement

Collaborative Colleagues:
John Cocke: colleagues
Ken Kennedy: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player