Abstract

A method and apparatus for improving the process of software development by a fast coalescing compiler optimizer tool that operates with one compiler pass. The present invention is a software development tool for optimization that analyzes one or more instructions, and when the instruction is a copy instruction the tool analyzes the source variable and the target variable of the copy instruction for opportunities to coalesce the source variable and the target variable. The present invention tailors its processing to advantageously enable user-level debugging when debugging is required. The present invention coalesces a target variable of a copy instruction and a source variable of the copy instruction; when the target variable of a copy instruction does not interfere with the source variable of the copy instruction, and the only use of the source variable in the program is in the copy instruction, and the source variable has one or more definitions and all the definitions in the program precede the copy instruction and are in a common basic block. The present invention coalesces a source variable of a copy instruction with a target variable of the copy instruction when the target variable has a single definition that is defined in the copy instruction, and the definition of the target variable precedes all uses in the program of the variable, and all uses of the variable are in the same basic block, and the source of the copy instruction and the target of the copy instruction do not interfere.

Other References

• Chow teaches the priority based coloring approach to register allocation in ACM Transactions on Programming Languages and Systems, vol. 12, No. 4. Oct. 1990
• Knobe et al teach Register Allocation Using Control Trees in Technical Report No. CS-92-13, Mar. 1992
• Chaitin teaches Register allocation & Spilling via Graph Coloring, in Sigplan Symposium on compiler construction, Jun. 23-25, 1982
• Agarwal et al teach Interprocedural Partial Redundancy Elimination and Its Application to Distributed Memory Compilation in their paper, 1993
• Cytron et al teach An Efficient Method of Computing Static Single Assignment Form in Technical Report No. CS-88-16, Oct., 1988
• Title: Optimistic register coalescing, author:: Jinpyo Park; Soo-Mook Moon, IEEE, published on Mar. 1998
• Joel Auslander, et al., "Fast, Effective Dynamic Compilation", Department of Computer Science and Engineering, University of Washington, PLDI' 96, pp. 1-11
• Mark Hall, "Reg. Alloc.--Graph Coloring--Copy Minimization", (visited Nov. 20, 1997) pp. 1-3
• Guhan Viswanathan and James R. Larus, "Compiler-Directed Shared-Memory Communication For Iterative Parallel Applications", (visited Nov. 20, 1997) pp. 1-18
• Preston Briggs, "Coalescing Register Allocators", (visited Nov. 20, 1997) pp. 1-2
• V. Sarkar, "Automatic Selection Of High-Order Transformations In The IBM XL FORTAN Compilers", (visited Nov. 20, 1997) pp. 1-38
• Brian Grant, et al., "Annotation-Directed Run-Time Specialization In C", Department of Computer Science and Engineering, University of Washington, PEPM'97 Proceedings, pp. 1-16
• Preston Briggs, "Register Allocation Via Graph Coloring", A Thesis Submitted In Partial Fulfillment Of The Requirements For the Degree, Rice University, Houston, Texas (Apr. 1992), pp. 1-143
• G.J. Chaitin, "The Limits Of Mathematics-Tutorial Version", IBM Research Report, RC 20190 (Sep. 18, 1995) Computer Science/Mathematics, pp. 1-141
• G.J. Chaitin, "An Invitation To Algorithmic Information Theory", (visited Nov. 21, 1997) pp. 1-18
• F.E. Allen and J. Cocke, "A Program Data Flow Analysis Procedure", IBM Thomas J. Watson Research Center, Communications of the ACM, vol. 19, No. 3, (Mar. 1976), pp. 137-14