Method for identifying partial redundancies in a new processor architecture
Patent 6029005 Issued on February 22, 2000. Estimated Expiration Date: April 1, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
The invention, in one embodiment, is a method for compiling at least a portion of a computer program. The method includes (a) inserting a phi-function for a global variable reaching a join point in the intermediate language representation subsequent to the join point without regard to the presence of ambiguity; (b) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (c) identifying a partially redundant load by determining whether any of the operands of the inserted phi-function have not been renamed.
Other References
Alfred V. Aho, Revi Sethi, and Jeffrey D. Ullman, Compilers-Principles, Techniques, and Tools, (Addison-Wesley Publishing Co. 1988), in toto
Ron Cytron, Jeanne Ferrante, Mark N. Wegman, Barry K. Rosen, and F. Kenneth Zadeck, "An Efficient Method of Computing Static Single Assignment Form" available from the Brown University Department of Computer Science as Technical Report No. CS-88-16 at techreports@cs.brown.edu or through http:/www.cs.brown.edu:80 techreports/reports/CS-91-21.html, in toto
Ron Cytron, Jeanne Ferrante, Mark N. Wegman, Barry K. Rosen, and F. Kenneth Zadeck, "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph," 13 ACM Transactions on Programming Languages and Systems (1991); also available from the Brown University Department of Computer Science as Technical Report No. CS-91-21 at techreports@cs.brown.edu or through http:/www.cs.brown.edu:80/techreports/reports/CS-91-21.html, in toto
Mark N. Wegman and F. Kenneth Zadeck, "Constant Propagation with Conditional Branches," presented at the Twelfth Annual ACM Symposium on Principles of Programming Languages, sponsored by the Special Interest Group on Automata and Computability Theory and the Special Interest Group on Programming Languages of the Association for Computing Machinery, Jan. 14-16, 1985, in New Orleans, Louisiana, available from ACM Press and from the Brown University Department of Computer Science as Technical Report No. CS-91-22 at techreports@cs.brown.edu or through http:/www.cs.brown.edu:80/techreports/reports/CS-91-22.html, in toto
Kathleen Knobe and Kenneth Zadeck, "Register Allocation Using Control Trees," available from the Brown University Department of Computer Science as Technical Report No. CS-92-13 at techreports@cs.brown.edu or through http:/www.cs.brown.edu:80/techreports/reports/CS-92-13.html, in toto
Eric Stoltz, Harini Srinivasan, James Hook, and Michael Wolfe, "Static Single Assignment Form for Explicitly Parallel Programs: Theory and Pratice," available at http:.backslash..backslash.www.cse.ogi.edu/Sparse/sparse.papers.html, in toto
Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck, "Global Value Numbers and Redundant Computations," presented at the Fifteenth Annual ACM Symposium on Principles of Programming Languages, sponsored by the Special Interest Group on Automata and Computability Theory and the Special Interest Group on Programming Languages of the Association for Computing Machinery, Jan. 13-15, 1998, in San Diego, California, available from ACM Press, in toto
Fred C. Chow and John L. Hennessy, "The Priority-Based Coloring Approach to Register Allocation," 12 ACM Transactions on Programming Languages and Systems 501 (Association for Computing Machinery 1990), in toto
Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein, "Register Allocation via Coloring," 6 Computer Languages 47 (Pergamon Press Ltd. 1981), in toto
G. J. Chaitin, "Register Allocation & Spilling via Graph Coloring," Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, presented Jun. 23-25, 1982, Boston, Massachusetts, sponsored by the Association for Computing Machinery Speical Interest Group on Programming Languages (ACM Order No. 548820), in toto
Vugranam C. Sreedhar, Efficient Program Analysis Using DJ Graphs, Ph. D. Thesis, School of Computer Science, McGill University, Quebec Canada (1995), in toto
Gagan Agrawal, Joel Saltz, and Raja Das, "Interprocedural Partial Redundancy and its Application to Distributed Memory Compilation," UMIACS and Department of Computer Science at the University of Maryland, in toto
John H. Reif and Harry R. Lewis, "Efficent Symbolic Analysis of Programs," 32 Journal of Computer and System Sciences 280 (Academic Press, Inc. 1986), in toto
Mark N. Wegman and F. kenneth Zadeck, "Constant Propgation with Conditional Branches," 13 ACM Transactions on Programming Languages 181 (1991), in toto
Gagan Agrawal and Joel Saltz, "Interproceduarl Compilation of Irregular Applications for Distributed Memory Machines," (1995), in toto
Peter Christy, "IA-64 and Merced-What and Why," 10 Microprocessor Rep. 17 (1996), in toto
Rosen et al., `Global Value Numbering and Redundant Computations`, ACM Symp. On Principles of Programming Languages,1988, pp. 12-27. Srinivasan et al., `Static Single Assignment for Explicitly Parallel Programs`, ACM 20th PoPL,1993,pp. 260-272
Bernstein et al., `Dynamic Memory Disambiguation for Array References`, MICRO 27, 1994, pp. 105-111
Aho et al., Compilers: Principles, Techniques and Tools, Addison-Wesley, 1986, pp. 432-43
April 1, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
