Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-03-16
2003-02-25
Morse, Gregory (Department: 2162)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C713S167000
Reexamination Certificate
active
06526571
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to program analysis and optimization of Java program modules.
BACKGROUND OF THE INVENTION
The running time of programs can be reduced considerably by using code and compiler optimizations, which better exploit hardware resources. For programs that contain many short procedures, as many object-oriented programs do, inter-procedural optimizations are required in order to obtain efficient code. The most relevant inter-procedural optimization is inlining, which can improve performance by reducing the overhead of calls and by increasing optimization opportunities. However, inter-procedural optimizations are limited by the virtual calls of object-oriented programs. The ability to identify the potential targets of a virtual call, frequently referred to as “call devirtualization”, is therefore crucial for such programs, and has received much attention in recent years.
The Java programming language and runtime environment challenges for devirtualization. In fact may even be impossible to identify in advance all possible targets of a virtual call in Java. New classes containing additional unanticipated targets might be loaded at any time. Sophisticated type analysis may be required in order to determine the possible targets of a virtual call completely. Being unsure what the potential targets are greatly limits the ability to perform inter-procedural optimizations. Such optimizations will need either to rely on the user to specify all classes and interfaces that may be dynamically loaded, or to repeatedly check what the actual target is and prepare default actions for unexpected targets. Otherwise, there is a risk that the optimization will become obsolete, in-which case a special mechanism is needed for undoing the optimization. Such a mechanism is described in “The Java™ HotSpot™ Virtual Machine Architecture” by David Griswold, published by Sun Microsystems, Inc., March 1998 and available as a White Paper at http://java.sun.com:81/products/hotspot/whitepaper.html.
In traditional object-oriented languages such as C++, the set of possible targets of a virtual call can be determined easily, or at least approximated conservatively. This is because all the classes that can possibly be used by the program are fixed and known at the time of compilation. A call to a given method may potentially target any overriding implementation of that method. So a simple approximation of a call's targets is the set of all overriding implementations of the called method. This set can be constructed efficiently by scanning the inheritance tree rooted at the called class. Various techniques have been developed in recent years to refine the set of possible targets of a virtual call, producing subsets of the set of all overriding implementations. It is known to use liveness analysis so as to exempt “dead method implementations” guaranteed never to be invoked during execution of the program from being potential target candidates. All such techniques rely on having all relevant classes that might be referenced at runtime, fixed and available at analysis time.
For Java programs, however, it is generally impossible to know in advance which classes will actually participate. The specific class-file is located and loaded only during runtime, when the class is referenced for the first time. Until this time, any change made to the class-files themselves or to other parameters (such as the CLASSPATH environment variable) may affect the classes that will be loaded. This dynamic behavior limits the ability to perform inter-class analysis, and in particular to determine the possible targets of virtual calls. There is another difference between Java and other object-oriented languages, with regards to the potential targets of virtual calls. In Java (unlike other languages) it is possible for a virtual call to reach an overriding implementation whose class does not implement the called interface. However, it is still possible to find all overriding implementations of a Java method by scanning the subclasses of the class or interface containing the method, occasionally examining the superclasses of such subsclasses.
Two main approaches are currently used to cope with this dynamic nature of Java and yet enable inter-class analysis and optimization. One approach is to assume that all relevant classes are supplied by the user, and revert to traditional static techniques. Such an approach was adopted by Instantiations, Inc. in their program JOVE™, (http://www.instantiations.com/jove/jovereport.htm.) which analyzes and compiles entire “sealed” Java applications.
The major drawback of this approach is that it does not apply to (dynamic) applications that may dynamically load unanticipated classes or interfaces at runtime.
The second approach is to assume that new classes may appear (at runtime), and prepare a mechanism for detecting obsolete analyses and “undoing” optimizations that were based on such analyses. It is to be noted that it is usually impossible to “undo” an optimization after the optimized code has been entered, so a default action must be provided to deal with unanticipated targets when inlining code into certain methods. Such an approach is used by Hotspot referred to above. The major drawback of this approach is the runtime overhead inflicted by this additional mechanism, and by the occasional need to detect and deal with unanticipated targets.
It would be preferable to avoid such post-compilation by ensuring that the initial optimization is self-contained and will thus not be rendered obsolete during run-time. However, this can be achieved only if specific calls can be properly identified as “sealed calls”, whose set of potential targets can be determined completely and explicitly, even prior to runtime.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method for identifying in Java packages calls whose targets are guaranteed to belong to the same package.
According to the invention there is provided a method for identifying calls in a Java sealed package whose targets are guaranteed to belong to said package, comprising the steps of:
(a) verifying that the package is sealed and signed,
(b) obtaining a class hierarchy graph for classes and interfaces of said package,
(c) obtaining access permissions of respective components in said package, and
(d) using the class hierarchy graph and access permissions in combination with a knowledge that the package is sealed and signed to determine whether all the targets of the calls are guaranteed to belong to said package.
The invention exploits the feature of Version 1.2 of the Java Development Kit (JDK 1.2) which allows packages to be sealed. This capability, which primarily serves to afford higher security, is used by the invention to identify a call as a so-called “sealed call” if it appears inside a sealed and signed Java package and it is determined that all the targets are guaranteed to belong to that package.
Identifying sealed calls and their potential targets facilitates aggressive inter-procedural (intra-package) optimizations. In particular, if a sealed call has only one potential target, it can be safely inlined. Such optimizations can take place inside a Just-In-Time (JIT) compiler, inside a standard compile-time (pre-runtime) compiler, or as a byte code transformation stage.
According to the invention, certain scenarios are identified where static analysis can be applied safely, without relying on assumptions or restrictions of the entire program, and without fear of becoming obsolete or inflicting runtime overhead. It is possible to exploit the method according to the invention in those cases where it is applicable, and to use any of the former approaches elsewhere.
REFERENCES:
patent: 5603031 (1997-02-01), White et al.
patent: 5966539 (1999-10-01), Srivastava
patent: 6038395 (2000-03-01), Chow et al.
patent: 6230314 (2001-05-01), Sweeney et al.
Wirfs-Brock, Large Java applications breaking the speed limit, http://www.instantiations.com/java1talk/sld001.htm, Jun. 1
Aizikowitz Nava
Feldman Vitaly
Zaks Ayal
Browdy and Neimark , P.L.L.C.
Morse Gregory
Nguyen-Ba Hoang-Vu Antony
LandOfFree
Method for identifying calls in java packages whose targets... 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 calls in java packages whose targets..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for identifying calls in java packages whose targets... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3117530