Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-09-30
2001-01-30
Chaki, Kakali (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06182284
ABSTRACT:
TECHNICAL FIELD
The present invention relates to computer software compiler programs that translate source-language programs into equivalent compiled programs comprising assembly-language or machine instructions and, in particular, to a method and system for translating optimized, intermediate-level, static-single-assignment-form computer code that includes phi instructions into optimized, intermediate-level computer code without phi instructions.
BACKGROUND OF THE INVENTION
Compilers are programs that translate computer programs written in source languages, such as FORTRAN, Pascal, C, and C++, into equivalent compiled programs consisting of assembly-language instructions or machine-code instructions. Compilers generally perform this translation in a series of distinct steps or phases. Initial phases perform lexical analysis, syntactic analysis, and semantic analysis, generating an intermediate-level translation that includes intermediate-code instructions. Later phases perform various optimizations to produce the final assembly-language or machine-code program. In certain optimization phases, a particular form of intermediate-level code, called static-single-assignment (“SSA”) form code, facilitates and simplifies certain types of optimizations. In SSA-form code, each variable, or virtual register, is defined only once. At points in the SSA-form code where branches coalesce, phi instructions (“100 -instructions”) are inserted to abstractly coalesce the definitions of a set of virtual registers from various incoming branches. A &phgr;-instruction formally assigns an additional virtual register to the value of the corresponding virtual register defined in the particular program branch that is taken, during execution of the program, to arrive at the point where the various branches coalesce. In a later phase, the SSA-form intermediate-level code is transformed back to a non-SSA-form intermediate-level code by removing the &phgr;-instructions and substituting, throughout the intermediate-level code, a single virtual register for the set of virtual registers coalesced by each &phgr;-instruction. However, the transition from SSA-form intermediate-level code back to non-SSA-form intermediate-level code may be complicated as a result of intervening optimizations, including code motion and copy elimination. Because of these intervening optimizations, certain types of interferences between sets of variables coalesced by different &phgr;-instructions may be produced. These interferences need to be detected and removed prior to the transition from SSA-form intermediate-level code back to non-SSA-form intermediate-level code.
Various algorithms have been proposed for detecting and removing interferences between the variables coalesced by &phgr;-instructions of optimized SSA-form intermediate-level code. In particular, techniques for identifying and removing &phgr;-instruction interferences are described in the following two references: (1) P. Briggs, T. Harvey, and Taylor Simpson,
Static single assignment construction,
Version 1.0, Technical Report, Rice University, July 1995; and (2) R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck,
Efficiently computing status single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems,
13(4):451-490, October 1991. A detailed discussion of the theory and implementation of compilers can be found in a number of textbooks, including:
Compilers: Principals, Techniques, and Tools,
Aho, Sethi, and Ullman, Addison-Wesley Publishing Company, 1988; and
Advanced Compiler Design
&
Implementation,
Muchnick, Morgan Kaufmann Publishers, 1997. However, the currently-available algorithms are deficient in various aspects. They employ control flow graph representations and interference graphs, but do so by identifying and including algorithms for a number of different structural properties of the control flow graphs and interference graphs. This “special casing” approach suffers the disadvantage that, because there are potentially infinitely many different structural properties of control flow graphs and interference graphs that might require special-case algorithms, a “special case” approach cannot be proven to be correct for all control flow graphs and interference graphs that might arise in SSA-form intermediate-level code. Another disadvantage of currently-available algorithms is that they need to consider intermediate-level code instructions and traverse the control flow and interference graphs in certain predefined orders. This ordering requirement greatly complicates the algorithms. Finally, the currently-available algorithms remove &phgr;-instruction interferences by introducing copy instructions, but end up inserting more copy instructions into the intermediate-level code than are strictly required to remove the &phgr;-instruction interferences. These unnecessary copy instructions increase both the time required for execution and the size of the final assembly-language or machine-code program produced by the compiler.
A need has therefore been recognized in the area of compiler optimization for an improved method for eliminating &phgr;-instruction interferences and for eliminating redundant copy instructions from SSA-form intermediate-level code. This improved method should provide a uniform framework that does not require any “special casing” approaches. The improved method should not impose any requirements either for traversing control flow graphs and interference graphs or for considering &phgr;-instructions within the intermediate-level SSA-form code in particular orders. The improved method should not insert large numbers of redundant and unnecessary copy instructions into the SSA-form intermediate-level code to remove the interferences between &phgr;-instructions.
SUMMARY OF THE INVENTION
The present invention provides a uniform framework for eliminating interferences between variables used in &phgr;-instructions in SSA-form intermediate-level code and a uniform framework for eliminating redundant copy instructions from SSA-form intermediate-level code. Phi congruence classes interrelate variables used in multiple &phgr;-instructions. An interference graph indicates pairs of variables that are both live at some point in the SSA-form intermediate-level code. The present invention detects interferences between the variables used in &phgr;-instructions by constructing phi congruence classes and by analyzing the phi congruence classes, together with an interference graph and sets of variables that are live at the beginning and end of basic blocks within the SSA-form intermediate-level code. The detected &phgr;-instruction interferences are eliminated by inserting copy instructions into basic blocks that precede and include &phgr;-instructions. Redundant copy instructions can be removed from the SSA-form intermediate-level code by considering the interference graph and by comparing the members of the phi congruence classes associated with the variables used in the copy instructions. The method of the present invention does not impose any order requirements on considering &phgr;-instructions or traversing control flow graphs, and does not require consideration of special structural forms of the control flow graphs, thus avoiding using a “special casing” approach to eliminating &phgr;-instruction interferences and redundant copies, and inserts fewer copy instructions than are inserted by currently-available algorithms.
REFERENCES:
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
patent: 5790867 (1998-08-01), Schmidt et al.
patent: 5901317 (1999-05-01), Goebel
patent: 5937195 (1999-08-01), Ju et al.
patent: 5978588 (1999-11-01), Wallace
patent: 5991540 (1999-11-01), Radigan
patent: 6016398 (2000-01-01), Radigan
patent: 6026241 (2000-02-01), Chow et al.
Aho et al., “Compilers: Principles, Techniques and Tools”, Addison-Wesley, 1988, pp. 1.
Rosen et al., “Global value number and redundant computations”, ACM Symp. on POPL, 1988, pp. 12-27.
Gillies David Mitford
Ju Dz-ching
Santhanam Vatsa
Sreedhar Vugranam C.
Chaki Kakali
Hewlett--Packard Company
LandOfFree
Method and system for eliminating phi instruction resource... 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 and system for eliminating phi instruction resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for eliminating phi instruction resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476602