|
 ABSTRACT
Partial redundancy elimination is a code optimization with a long history of literature and implementation. In practice, its effectiveness depends on issues of naming and code shape. This paper shows that a combination of global reassociation and global value numbering can increase the effectiveness of partial redundancy elimination. By imposing a discipline on the choice of names and the shape of expressions, we are able to expose more redundancies.
As part of the work, we introduce a new algorithm for global reassociation of expressions. It uses global information to reorder expressions, creating opportunities for other optimizations. The new algorithm generalizes earlier work that ordered FORTRAN array address expressions to improve otpimization [25].
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
|
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]
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
Gregory J. ChaJtin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. M arkstein. Register allocation via coloring. Computer Languages, 6:47-57, January 1981.
|
| |
7
|
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
[doi> 10.1145/99583.99594]
|
| |
8
|
|
| |
9
|
John Cocke and Peter W. Markstein. Measurement of program improvement algorithms. In Proceedings of Informatzon Processzng 80. North Holland Publishing Company, 1980.
|
| |
10
|
John Cocke and Jacob T. Schwartz. Programming languages and their compilers: Prehminary notes. Technical report, Courant institute of MathematicM Sciences, New York University, 1970.
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
Lawrence Feigen , David Klappholz , Robert Casazza , Xing Xue, The revival transformation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.421-434, January 16-19, 1994, Portland, Oregon, United States
[doi> 10.1145/174675.178043]
|
| |
16
|
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
Peter W. Markstein, Victoria Markstein, and F. Kenneth Zadeck. Reassociation and strength reduction. In Optimization in Compilers. ACM Press, to appear.
|
| |
21
|
|
| |
22
|
Kevin O'Brien, Bii1 Hay, Joanne Minish, Hartmann Schaffer, Bob Schloss, Arvin Shepherd, and Matthew Zaleski. Advanced compiler technology for the RISe/: System/6000 architecture. In IBM RISU System/6000 Technology. IBM Corporation, Armonk, New York, 1990.
|
| |
23
|
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]
|
| |
24
|
Vatsa S~nthanam. Register reassociation in PA-RISC, compilers. Hewlett-Packard Journal, pages 33-38, June 1992.
|
| |
25
|
Randolph G. Scarborough and H arwood G. K olsky. Improved optimization of FORTRAN object programs. IBM Journal of Research and Development, pages 660- 676, November 1980.
|
| |
26
|
|
| |
27
|
|
CITED BY 39
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Oliver Rüthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
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
|
|
|
Ali-Reza Adl-Tabatabai , Jay Bharadwaj , Michal Cierniak , Marsha Eng , Jesse Fang , Brian T. Lewis , Brian R. Murphy , James M. Stichnoth, Improving 64-Bit Java IPF Performance by Compressing Heap References, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.100, March 20-24, 2004, Palo Alto, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3