Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-09-30
2001-05-15
Courtenay, III, St. John (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06233733
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the optimization of Java class files. More particularly, the present invention relates to the generation of aspects of a data flow graph from a Java classfile optimizer that identifies the propagation of data values in blocks of bytecode and between blocks of bytecode.
2. The Prior Art
A known problem for software developers and computer users is the lack of portability of software across operating system platforms. Attempts to address this problem must include means of ensuring security as computers are linked together in ever expanding networks, such as the World Wide Web. As a response to both of these concerns, the JAVA programming language was developed at Sun Microsystems as a platform independent, object oriented computer language designed to include several layers of security protection.
Java achieves its operating system independence by being both a compiled and interpreted language. First, Java source code, which consists of Java classfiles, is compiled into a generic intermediate format called Java bytecode. Java's bytecodes consist of a sequence of single byte opcodes, each of which identify a particular operation to be carried out. Additionally, some of the opcodes have parameters. For example, opcode number
21
, iload <varnum>, takes the single-word integer value stored in the local variable, varnum, and pushes it onto a stack.
Next, the bytecodes are interpreted by a Java Virtual Machine (JVM) which translates the bytecodes into native machine code. The JVM is a stacked-based implementation of a “virtual” processor that shares many characteristics with physical microprocessors. The bytecodes executed by the JVM are essentially a machine instruction set, and as will be appreciated by those of ordinary skill in the art, are similar to the assembly language of a computing machine. Accordingly, every hardware platform or operating system may have a unique implementation of the JVM, called a Java Runtime System, to route the universal bytecode calls to the underlying native system.
When developing the JAVA bytecode instruction set, the designers sought to ensure that it was simple enough for hardware optimization and also included verification means to provide security protection and to prevent the execution errors or system crashes that can result from improperly formatted bytecode. As Java's bytecodes contain significant type information, the verification means are able to do extensive type checking when the bytecodes are first retrieved from the internet or a local disk. As a result, the interpreter of the native machine need only perform minimal type checking at run time. Unlike languages such as SmallTalk that provide protection by performing extensive runtime checks, Java executes more quickly at run time.
Although Java provides security through verification means and portability through bytecodes, Java programs lag natively compiled programs, written in languages like C/C++, in their execution time. When a user activates a Java program on a Web Page, the user must wait not only for the program to download but also to be interpreted. To improve Java's execution time, optimizations can be introduced into the processing of Java bytecodes. These optimizations can be implemented in a variety of manners including as Stand-Alone Optimizers (SAO) or as part of Just-in-Time (JIT) compilers.
A SAO transforms an input classfile containing bytecode into an output classfile containing bytecodes that more efficiently perform the same operations. A JIT transforms an input classfile containing bytecode into an executable program. Prior to the development of JITs, a JVM would step through all the bytecode instructions in a program and mechanically perform the native code calls. With a JIT compiler, however, the JVM first makes a call to the JlT which compiles the instructions into native code that is then run directly on the native operating system. The JIT compiler permits natively complied code to run faster and makes it so that the code only needs to be compiled once. Further, JIT compilers offer a stage at which the executable code can be optimized.
To either optimize or compile bytecodes involves the translation of the source bytecodes into what is known in the art as an intermediate representation (IR). The IR provides information about two essential components of a program: the control flow graph (CFG) and the data flow graph (DFG). Subsequently, the IR is transformed for compilers into object code and for optimizers into an improved version of the source code format.
The CFG breaks the code into blocks of bytecode that are always performed as an uninterrupted group and establishes the connections that link the blocks together. The DFG maps the connections between where values are produced and where they are used. This includes connections within blocks of bytecodes and also connections between blocks of bytecodes. Because Java programs frequently use stack locations as implicit variables, tracking the propagation of values is a difficult process. When extracting the data flow information to generate the DFG for the IR, the prior art approach has been to perform a complete simulation of both the stack and iterations through all possible flow paths.
In contrast to traditional compilers where end users only interact with compiled programs, the run time nature of Java creates a significant incentive to optimize the speed and efficiency of Java optimizers and JIT compilers. Accordingly, it is an object of the present invention to provide a method for generating a DFG from the source bytecodes to form an IR that optimizes the speed and efficiency of Java optimizers and JIT compilers.
These and many other objects and advantages of the present invention will become apparent to those of ordinary skill in the art from a consideration of the drawings and ensuing description of the invention.
SUMMARY OF THE INVENTION
The present invention is directed to the optimization of Java class files by improving the efficiency of generating a DFG for the IR.
According to a first aspect of the present invention, a forward scan of an uninterrupted bytecode block from a bytecode source file is performed to identify the start of each bytecode in the uninterrupted block. Next, a backwards scan is performed. For each bytecode in the block, a DFG node is created, links to all the values used by the bytecode in the block are established, and links to preceding or subsequent nodes in the file are created.
According to a second aspect of the invention, the bytecode blocks are linked in the file's order of execution and a stack state is generated for each block of code. For each join statement generated by the CFG, one path of the CFG is stepped through. Next, links are established in the DFG between locations where values are used and where the values are produced. Finally, for all blocks parallel to the blocks producing values the links for bytecodes occupying the same stack state location are duplicated.
REFERENCES:
patent: 5650948 (1997-07-01), Gafter
Aho, et al., “Code Optimization”, Mar. 1988, Compliers-Principles, Techniques, and Tools, Addison-Wesley Publishing Co., Chapter 10, pp. 585-722.
Allen, et al., “A Program Data Flow Analysis Procedure”, Mar. 1976, Communications of the ACM, vol. 19, No. 3, pp. 137-147.
Hecht, et al., “A Simple Algorithm for Global Data Flow Analysis Problems”, Dec. 1975, SIAM Journal of Computing, vol. 4, No. 4, pp. 519-532.
Kennedy, Ken, “A Global Flow Analysis Algorithm”, 1971, International Journal of Computer Math, Section A., vol. 3, pp. 5-15.
O'Connor, J.M., et al., “PicoJava-I: The Java Virtual Machine in Hardware”, Citation and Abstract Search Results View Full Page, IEEE/IEE Electronic Library, Mar./Apr. 1997, pp. 45-53.
Courtenay III St. John
Opie George
Ritchie David B.
Sun Microsystems Inc.
Thelen Reid & Preist LLP
LandOfFree
Method for generating a Java bytecode data flow graph 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 generating a Java bytecode data flow graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating a Java bytecode data flow graph will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2481773