Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-04-27
2003-12-16
Ingberg, Todd (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S151000, C717S154000, C717S156000, C717S144000
Reexamination Certificate
active
06665865
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of computers, and in particular to alias analyses useful for optimizing software.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright® 2000, Microsoft Corporation, All Rights Reserved.
BACKGROUND
As is known to those skilled in the art, JAVA™ is an object-oriented language developed by Sun Microsystems, Inc.
Java libraries include synchronization operations throughout. Synchronization operations in Java acquire and release locks associated with or belonging to Java objects. The operations of acquiring or releasing locks are typically expensive in terms of added execution time, and so single threaded libraries and multithreaded libraries are often supplied so that users can link to the single threaded libraries to avoid the synchronization operations when appropriate. There is also a storage allocation cost associated with a lock. Even when the multithreaded libraries are used, many unnecessary synchronization operations, and their associated overhead exist.
Typical approaches to find ways to remove synchronization operations that are not necessary include: 1) determining if a program is single threaded, and if so, removing all synchronization operations; 2) and escape analysis. A program can be determined to be single threaded by searching for any thread creation sites, and then declaring the program single threaded if none are found. Since, in a single threaded program, only one thread runs at a time, all synchronization operations can be removed. This approach is not without problems. Notification operations that operate through locked objects can occur in either single threaded or multi threaded programs. The semantics of Java require that a thread issuing a notification be synchronized on the object at issue. If synchronization operations have been removed, and a notification operation takes place, an exception can be thrown, possibly causing the program to crash.
A second approach is escape analysis. If an object never escapes the thread in which it is created, then it cannot be accessed by a separate thread, and any synchronization operations on the object can be removed. If an object does escape from the thread in which it is created, then there is a possibility that a separate thread may try to synchronize it. This is not to say that multiple threads can never execute the same piece of code. If multiple threads execute the same piece of code but the object does not escape, then each thread has a separate instance of the object, and lock contention is not a concern.
An object escapes from a thread when it can be transitively referenced by a global object. An escaping object is thus accessible by multiple threads, which may contend for its lock. Escape analysis is very conservative. Even if an object can be accessed by a global variable, it's possible that it is not. Also, even if an object is accessed, it may not be locked. This results in a conservative estimate, in that an assumption is made that the escaped object is synchronized elsewhere, when in fact it may not be.
Thus, an alternate method and apparatus are needed for optimizing synchronization operations from Java code.
SUMMARY OF THE INVENTION
The method and apparatus of the present invention provide a mechanism for performing an alias analysis on a program using a compact, equivalence-class-based representation that eliminates the need for fixed point operations. In one embodiment, the mechanism is used to remove unnecessary synchronization operations from statically compiled Java programs.
In general, the mechanism provides a method for determining if a thread can perform an action of interest on an object of interest. The action can be any type of action, such as a synchronization operation in a Java program. The method includes performing a thread closure analysis to determine the closure of code potentially executed by the thread, performing an alias analysis for each procedure in the closure of code to determine a polymorphic summary of each procedure, and utilizing the polymorphic summary to specialize each procedure in the closure of code. The program statements in the procedures are walked and searched for occurrences of the action of interest performed on objects represented by the same equivalence class representative as the object of interest. When these actions of interest are found, they can be optimized separately for each specialized copy of each procedure.
The polymorphic summaries include alias sets that describe the aliasing behavior of formal parameters at the procedure boundary. Alias sets include attribute fields that describe the action of interest. In one embodiment of the invention, the attribute fields include fields that describe whether the object of interest is synchronized, by what threads, and whether the object is reachable by a global value. In other embodiments, a “notified” field is included as an attribute field. The notified field allows synchronizations to be optimized out of Java programs while still allowing notification operations to perform correctly.
REFERENCES:
patent: 5488727 (1996-01-01), Agrawal et al.
patent: 6014518 (2000-01-01), Steensgaard
patent: 6041179 (2000-03-01), Bacon et al.
patent: 6173444 (2001-01-01), Archambault
patent: 6434740 (2002-08-01), Monday et al.
patent: 6463581 (2002-10-01), Bacon et al.
“Topics in Online Partial Evaluation”, Erik Ruf, Technical Report: CSL-TR-93-563, Stanford University, 1993.*
“Context-Intensive Alias Analysis Reconsidered”, Erik Ruf, Technical Report: MSR-TR-95-20, Microsoft Research, 1995.*
“Removing Unnecessary Synchronizaion in Java”, Jeff Bogda and Urs Holzle, University of California, 1999.*
“Effective Syncronization Removal for Java”, Erik Ruf, Microsoft Research, 2000.*
Steven S. Muchnick, “Advanced Compiler Design and Implementation”,Morgan Kaufmann, 1997, Chapter 8, 217-266.
Gross Kenneth A
Ingberg Todd
Woodcock & Washburn LLP
LandOfFree
Equivalence class based synchronization optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Equivalence class based synchronization optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence class based synchronization optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171338