Abstract

Apparatus, methods, and computer program products are disclosed for providing optimized access to pointer or externally-tagged primitive type data-values. The invention maintains a type identifier external to the variable that contains the data-value. The invention determines the type distribution of data-values stored in the variable and optimizes access to the variable accordingly. Some of these optimizations are targeted towards called routines and the call sites for the called routines. Other optimizations are targeted towards object-oriented programming language implementations. These optimizations generate optimized versions of a class/map. Objects are linked to the optimized versions of the class/map depending on the type configuration of the data-values stored in the object. Thus, the invention optimizes access to variables in the object when the object contains commonly used type configurations.

Other References

• Lins, R.D., "A Multi-processor Shared Memory Architecture for Parallel Cyclic Reference Counting," Microprocessing and Microprogramming, vol. 35, No. 1 / 05, Sep. 1, 1992, pp. 563-569
• Agesen, O. and Holzle, U., "Type Feedback vs. Concrete Type Inference: A Comparison of Optimization Techniques for Object-Oriented Languages," OOPSLA '95 Conference Proceedings, Austin, Texas. 1-17 1995
• Aho, A.V. et al., "A Simple One-Pass Compiler," Compilers, Principles, Techniques, and Tools. Reading: Addison-Wesley Publishing Company. 23-81 1986
• Aho, A.V. et al., "Introduction to Compiling," Compilers, Principles, Techniques, and Tools. Reading: Addison-Wesley Publishing Company. 1-23 1986
• Chambers, C. et al., "An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes," Lisp and Symbolic Computation. 4: (3) 57-95 1991
• Chambers, C. and Ungar D., "Customization: Optimizing Compiler Technology for SELF, a Dynamically-Typed Object-Oriented Programming Language," PLDI. 146-160 1989
• Chambers, C. and Ungar, D., "Iterative Type Analysis and Extended Message Splitting: Optimizing Dynamically-Typed Object-Oriented Programs," Lisp and Symbolic Computation. 4: (3) 97-124 1991
• Holzle, U. and Ungar, D., "A Third-Generation SELF Implementation: Reconciling Responsiveness with Performance," OOPSLA '94 Conference Proceedings, Portland, Oregon. 1-15 1994
• Holzle, U., "Adaptive Optimization for Self: Reconciling High Performance with Exploratory Programming," a Dissertation submitted to the Stanford University Department of Computer Science. 1-164 1995
• Holzle, U., "Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback," SIGPLAN Conference on Programming Language Design and Implementation, Orlando, FL. 1-11 1994
• Ungar, D. et al., "Objcet, Message, and Performance: How they coexist in SELF," IEEE Computer. 25: (10) 1-21 1992
• Ungar, D. and Smith, R.B., "Self: The Power of Simplicity," published in Sun Microsystems Laboratories SMLI Technical Report Series 1-18 1994
• Van Der Linden, P., "Java Language Specifics, " Not Just Java. Mountain View: Sun Microsystems Press. 136-149 1997
• Wismuller, "Debugging of globally optimized programs using data flow analysis", ACM SIGPLAN, pp. 278-289, Jun. 1994
• Dean et al., "Vortex: an optimizing computer for object oriented languages", ACM OOPSLA, pp. 83-100, 1996
• Kandemir et al, "A compiler algorithm for locality in loop nests", ACM ICS, pp. 269-276, May 1997
• Bershad et al., "Avoiding conflict misses dyanmically in large direct mapped caches", ACM ASPLOS VI, pp. 158-170, Oct. 1994
• Engelen et al, "Incorporating application development information in an automatic code generating environment", ACM ICS, pp. 180-187, 1997
• Shao et al., "A type based compiler for standrad ML", ACM SIGPLAN, pp. 116-129, Feb. 1995
• Holzle & Ungar, "Reconciling Responsiveness with performance in pure object oriented languages", ACM Trans. Prog. Lang. & Syst. vol. 18, No. 4, pp. 355-400, Jul. 1996
• Ungar, David., "Annotating objects for transport to other world", OOPSLA '95 ACM, pp. 73-87, 1995
• Agesen & Ungar, "Sifting out the Gold: Delevering compact applications from an exploratory object oriented programming environment", OOPSLA, ACM, pp. 355-370, Oct. 199