Patent
1997-04-01
2000-02-22
Hafiz, Tara R.
395708, 395707, G06F 945
Patent
active
060290056
ABSTRACT:
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.
REFERENCES:
patent: 4435753 (1984-03-01), Rizzi
patent: 4567574 (1986-01-01), Saade et al.
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4710872 (1987-12-01), Scarborough
patent: 4773007 (1988-09-01), Kanada et al.
patent: 4782444 (1988-11-01), Munshi et al.
patent: 4821181 (1989-04-01), Iwasawa et al.
patent: 4833606 (1989-05-01), Iwasawa et al.
patent: 4885684 (1989-12-01), Austin et al.
patent: 4965724 (1990-10-01), Utsumi et al.
patent: 5287510 (1994-02-01), Hall et al.
patent: 5768596 (1998-06-01), Chow et al.
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-433.
Chaki Kakali
Hafiz Tara R.
Intel Corporation
LandOfFree
Method for identifying partial redundancies in a new processor a does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for identifying partial redundancies in a new processor a, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for identifying partial redundancies in a new processor a will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-527762