Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
1998-12-14
2002-08-27
Morse, Gregory (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S132000, C717S154000, C717S155000, C717S156000, C717S157000, C707S793000, C707S793000
Reexamination Certificate
active
06442751
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates, in general, to the tracking of variables, and more particularly, to the tracking of local variables when subroutines are called. In particular, a method and apparatus are disclosed for tracking local variable types following subroutine invocation.
BACKGROUND OF THE INVENTION
In most language implementations, a stack is used for tracking method calls and returns, and for holding the values of local variables and intermediate results. For languages that support multiple threads, a stack is created for each thread that is created. The stacks are divided into frames, with each frame pushed onto the stack when a method is invoked and popped from the stack when a method returns. Each frame, except the current frame, contains the location of the next instruction to be executed when normal control returns to that frame. For the current frame (the frame for the method that is currently being executed) the location of the current instruction being executed is kept in the frame or in a machine-dependent location (e.g. a machine-register). Each frame thus pinpoints the instruction currently being executed by the method represented by the frame (hereafter referred to as the execution point). Local variables of a method are assigned to different slots within the frame that was created when that method is executed. A more detailed description of stack frames as used in a Java™ Virtual Machine is described in “The Java™ Virtual Machine Specification”, Lindholm, Yellin, Section 3.6, 1996, herein incorporated by reference in its entirety.
The Java™ Virtual Machine (JVM) is different from other execution models in that during distinct execution portions of a method, a local variable may store values of different types. For example, during one part of the execution of a method, a local variable may hold a value of type integer (int). However, in another part of the execution of that same method, the same local variable may hold a reference (pointer) to a heap-allocated object.
During the execution of a program, it may be advantageous to track and determine precisely the types of the values stored in each of the local variables. Two exemplary applications for such type tracking are dynamic storage reclamation (garbage collection), and debugging. For dynamic storage reclamation, it is desirable to precisely determine which local variables contain references to heap-allocated objects.
For debugging, it is desirable to precisely identify the types of values stored in local variables when displaying the values stored in the local variables to the user. Given the type of data stored in a given local variable, the debugger then can display that data correctly to the user. Specifically, given a value stored in a local variable and not knowing the type of value stored in the variable, the debugger will not know whether that value is a pointer to the value or is the actual value itself. Further, even if the value is known to be a non-pointer, or primitive, value the debugger must know the specific data type to display the value properly to the user. For example, integer data, floating-point data, and character data are stored using different internal representations. Given only the value represented in internal format, the debugger must know the type of the value to translate and display that value to the user correctly. Displaying the values and types stored in local variables enables the user to define his or her debugging strategy accordingly. In the context of this application, the term “primitive” refers to any non-pointer data type, including but not limited to character, integer, long, short, float, and bit or flag.
The Java™ Virtual Machine Specification, incorporated by reference above, specifies rules to which the bytecode of a Java™ class file must conform to be considered valid. A verifier can be used before execution to ensure that a Java™ class file conforms to these rules. One Java™ rule specifies that at any given point within a method, regardless of the code path leading to that point, a local variable can only be accessed if it is known to contain a value of the type expected by the entity accessing the local variable. For example, if at a point in a method, a local variable is to be accessed as a reference, then all code paths to that point must assign a reference or a null to that variable. Likewise, if a local variable is being accessed as a float, then all code paths leading to that access must assign a float type to that local variable. This rule means that for many Java™ class files, a simple static analysis of the bytecode for each Java™ method will identify the type status for all local variables at all locations of interest within the method. The analysis is said to be “static” because it does not consider the specific control flow path taken through the method during execution.
A static analysis of the bytecode may not work if the bytecode contains JSR (jump subroutine) instructions. The JSR instructions supported by Java™ are unlike subroutine calling instructions supported by other languages in that the JSR instruction places no new frame on the stack. Thus, the JSR instruction makes no new “copies” of local variables. Instead, the subroutine targeted (hereinafter the “target subroutine” or the “JSR-subroutine”) by the JSR instruction accesses the same local variables at the same memory locations as does the calling program. Further, the JSR-subroutine can store new values in the local variable, or can alter the type of value stored in the local variable. Accordingly, depending on which particular JSR instruction called the JSR-subroutine, a given local variable could store data having different types. Other languages and the Java™ method call create a new set of local variables on a new stack frame. Thus, in such other languages type determination is a simple matter of analyzing the copy of the local variables as they exist on the stack.
In a JSR-subroutine, the determination of the type may depend on the flow of execution through the method. A JSR instruction is used to jump to a subroutine (a section of code within the method). The execution of a JSR instruction places the address of the instruction that appears immediately after the JSR instruction on the top of the stack. This is the return location for the JSR-subroutine. During the execution of the JSR-subroutine, the return location is saved in a local variable. The execution of the subroutine completes with the execution of a “ret” instruction that specifies the local variable containing the return location. Also, a JSR-subroutine can also terminate abruptly as described below.
Several different points in the bytecode can have JSR instructions that specify the same target JSR-subroutine. After execution of the subroutine, the execution continues with the instruction that follows the JSR instruction that jumped to the subroutine, as stored in the local variable. Local variables of the method are definable and accessible within the JSR-subroutine, subject to the same rules on uses of local variables as is the rest of the method.
The JVM rules allow a local variable to hold values of different types when different JSR instructions are executed that lead to the same JSR-subroutine. According to this rule, the local variable may not be accessed within the JSR-subroutine, but its existence adds to the complexity of determining precisely the types of values held in local variables for execution points within the JSR-subroutine. A simple static analysis does not consider or determine which JSR instruction was executed to jump to the JSR-subroutine, and accordingly does not track the type of value currently stored in local variables before jumping to the JSR-subroutine.
Note that a JSR-subroutine may also terminate abruptly if an exception occurs during it execution, in which case execution control is transferred to an appropriate exception handler, such as a Java™ “catch” block. This abrupt termination is mentioned only for completeness. The invention pertains to the dete
Cocchi Anthony
Shepherd Janice Cynthia
F. Chau & Associates LLP
Morse Gregory
Vo Ted T.
LandOfFree
Determination of local variable type and precision in the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determination of local variable type and precision in the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determination of local variable type and precision in the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920161