System and method for assisting exact Garbage collection by segregating the contents of a stack into sub stacks5903899Abstract In a program data stack in a computer system, every stack is implemented as two substacks, one to contain references and one to contain primitive data. In this manner, whether a piece of information on a stack is a reference or a primitive value is easily determined according to which substack it resides in. Each substack is itself a full-fledged stack data structure with a stack base, a stack pointer, and a stack limit. In the preferred embodiment, there is also a frame pointer for each substack. The normal instruction set is modified so that instructions that operate with references use the reference stack whereas instructions that operate with data use the primitive data stack. Specifically, during compilation, or loading, all instructions which can operate indiscriminately with either references or data are replaced by equivalent, but reference-specific or data-specific instructions. With this arrangement, garbage collection algorithms can locate all references stored within a stack, since the references are all in a more or less contiguous region of memory without interspersed primitive data. Claims What is claimed is: Description FIELD OF THE INVENTION
______________________________________
lload lload.sub.-- 0
lload.sub.-- 1
lload.sub.-- 2
lload.sub.-- 3
fload fload.sub.-- 0
fload.sub.-- 1
fload.sub.-- 2
fload.sub.-- 3
lload lload.sub.-- 0
lload.sub.-- 1
lload.sub.-- 2
lload.sub.-- 3
dload dload.sub.-- 0
dload.sub.-- 1
dload.sub.-- 2
dload.sub.-- 3
aload aload.sub.-- 0
aload.sub.-- 1
aload.sub.-- 2
aload.sub.-- 3
istore istore.sub.-- 0
istore.sub.-- 1
istore.sub.-- 2
istore.sub.-- 3
fstore fstore.sub.-- 0
fstore.sub.-- 1
fstore.sub.-- 2
fstore.sub.-- 3
lstore lstore.sub.-- 0
lstore.sub.-- 1
lstore.sub.-- 2
lstore.sub.-- 3
dstore dstore.sub.-- 0
dstore.sub.-- 1
dstore.sub.-- 2
dstore.sub.-- 3
astore dstore.sub.-- 0
dstore.sub.-- 1
dstore.sub.-- 2
astore.sub.-- 3
______________________________________
Those whose name begin with "a" deal with reference values and therefore use the reference frame pointer. The others deal with primitive values and therefore use the primitive frame pointer. It is not possible, in this framework, to use instructions that are indiscriminate as to whether a stack operand is a reference or primitive data. Therefore, additional instructions and two mechanisms are required, which are first summarized here and then elaborated upon below. For every instruction, whether an ordinary JVM instruction or implementation-dependent "quick" instruction, if that instruction is indiscriminate, then the instruction is replaced by new instructions which are added to the instruction set. In this manner, all instructions in the instruction set perform the relevant discriminations. The verifier is altered so that, as it traverses the code of a method (before the code for that method has ever been executed), whenever it examines any particular instance of a nominally indiscriminate instruction and determines which of its operands and results will be references, it replaces that instruction at verification time with one of several instructions that are logically equivalent but distinguish, for each stack operand or result, whether or not that operand or result is a reference. (In an alternate embodiment of the invention, a compiler might generate the necessary specialized instructions directly.) The mechanism that replaces slower instructions with quick instructions after symbolic name resolution is also modified so it chooses one of several possible quick instructions as the replacement. The choice of replacement instructions is made in such a manner to avoid losing information which would identify a particular stack operand or result as a reference. Modified Instruction Set The standard JVM instructions pop, pop2, dup, dup2, dup.sub.-- x1, dup.sub.-- x2, dup2.sub.-- x1, dup2.sub.-- x2, swap are construed always to operate on primitive values, using the primitive stack. For reasons of naming symmetry, explained below, each is given one or more additional names. Their instruction descriptions are therefore revised as follows. In every instruction description: Let v1 mean the topmost item on the primitive stack. Let v2 mean the second item from the top on the primitive stack. Let v3 mean the third item from the top on the primitive stack. Let v4 mean the fourth item from the top on the primitive stack.
______________________________________
pop = vpop
Pop v1 from the primitive stack (and discard).
pop2 = vvpop
Pop v1 from the primitive stack (and discard), then
pop v2 from the primitive stack (and discard).
dup = vdup = a.sub.-- vdup = aa.sub.-- vdup
Push a copy of v1 onto the primitive stack.
dup2 = vvdup = a.sub.-- vvdup = va.sub.-- vdup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack.
dup.sub.-- x2 = vv.sub.-- vdup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
pop v3 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v3 onto the primitive stack, then
push a copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack.
dup2.sub.-- x1 = v.sub.-- vvdup = av.sub.-- vvdup = va.sub.-- vvdup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
pop v3 from the primitive stack, then
push a copy of v2 onto the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v3 onto the primitive stack, then
push another copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack.
dup2.sub.-- x2 = vv.sub.-- vvdup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
pop v3 from the primitive stack, then
pop v4 from the primitive stack, then
push a copy of v2 onto the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v4 onto the primitive stack, then
push a copy of v3 onto the primitive stack, then
push another copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack.
swap = vvswap
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v2 onto the primitive stack.
______________________________________
Also, the instruction "nop" is given two additional names:
______________________________________
nop = avswap = vaswap
Take no action.
______________________________________
Certain of these instructions have more than one name, again for naming symmetry. To fully utilize the advantageous design of the segregated stack in accordance with the present invention, a number of new instructions are proposed as part of the invention. The behavior of the new additional instructions is as follows. In every instruction description: Let a1 mean the item that is topmost on the reference stack when the instruction begins execution. Let a2 mean the item that is second from the top on the reference stack when the instruction begins execution. Let a3 mean the item that is third from the top on the reference stack when the instruction begins execution. Let a4 mean the item that is fourth from the top on the reference stack when the instruction begins execution. Let v1 mean the item that is topmost on the primitive stack when the instruction begins execution. Let v2 mean the item is second from the top on the primitive stack when the instruction begins execution. Let v3 mean the item that is third from the top on the primitive stack when the instruction begins execution.
______________________________________
apop
Pop a1 from the reference stack (and discard).
aapop
Pop a1 from the reference stack (and discard) and
pop v1 from the primitive stack (and discard).
avpop = vapop
Pop a1 from the reference stack (and discard) and
pop v1 from the primitive stack (and discard).
adup = v.sub.-- adup = vv.sub.-- adup
Push a copy of a1 onto the reference stack.
aadup = v.sub.-- aadup = vv.sub.-- aadup
Push a copy of a2 onto the reference stack, then
push a copy of a1 onto the reference stack.
avdup = vadup
Push a copy of a1 onto the reference stack, and
push a copy of v1 onto the primitive stack.
a.sub.-- adup = av.sub.-- adup = va.sub.-- adup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack.
a.sub.-- aadup = av.sub.-- aadup = va.sub.-- aadup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
pop a3 from the reference stack, then
push a copy of a2 onto the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a3 onto the reference stack, then
push another copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack.
a.sub.-- avdup = a.sub.-- vadup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack; and
push a copy of v1 onto the primitive stack.
v.sub.-- avdup = v.sub.-- vadup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack; and
push a copy of a1 onto the reference stack.
aa.sub.-- adup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
pop a3 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a3 onto the reference stack, then
push a copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack.
aa.sub.-- aadup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
pop a3 from the reference stack, then
pop a4 from the reference stack, then
push a copy of a2 onto the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a4 onto the reference stack, then
push a copy of a3 onto the reference stack, then
push another copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack.
aa.sub.-- avdup = aa.sub.-- vadup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
pop a3 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a3 onto the reference stack, then
push a copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack; and
push a copy of v1 onto the primitive stack.
vv.sub.-- avdup = vv.sub.-- vadup
Pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
pop v3 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v3 onto the primitive stack, then
push a copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack; and
push a copy of a1 onto the reference stack.
av.sub.-- avdup = va.sub.-- avdup = av.sub.-- vadup = va.sub.-- vadup
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a2 onto the reference stack, then
push another copy of a1 onto the reference stack; and
pop v1 from the primitive stack, then
pop v2 from the primitive stack, then
push a copy of v1 onto the primitive stack, then
push a copy of v2 onto the primitive stack, then
push another copy of v1 onto the primitive stack.
aaswap
Pop a1 from the reference stack, then
pop a2 from the reference stack, then
push a copy of a1 onto the reference stack, then
push a copy of a2 onto the reference stack.
______________________________________
In the preferred embodiment whenever the verifier examines an instance of any of the pop, pop2, dup, dup2, dup.sub.-- x1, dup.sub.-- x2, dup2.sub.-- x1, dup2.sub.-- x2, or swap instructions the verifier will have determined for each item on the stack whether that item will always be a reference or always be a primitive value when that instruction is executed. The verifier then forms the name of a replacement instruction as follows: (a) For pop or pop2, use the base name "pop". For dup, dup2, dup.sub.-- x1, dup.sub.-- x2, dup2.sub.-- x1, or dup.sub.-- x2, use the base name "dup". For swap, use the base name "swap". (b) For pop or dup, prefix one letter to the base name, representing the topmost stack item. For pop2, dup.sub.-- x1, dup2, or swap, prefix two letters to the base name, representing the two topmost stack items, with the second letter of the resulting name representing the topmost stack item and the first letter of the resulting name representing the next stack item. For dup.sub.-- x2 or dup2.sub.-- x1, prefix three letters to the base name, representing the three topmost stack items, with the third letter of the resulting name representing the topmost stack item, the second letter of the resulting name representing the next stack item, and the first letter of the resulting name representing the item below that. For dup2.sub.-- x2, prefix four letters to the base name representing the four topmost stack items, with the fourth letter of the resulting name representing the topmost stack item, the third letter of the resulting name representing the next stack item, the second letter of the resulting name representing the next stack item, and the first letter of the resulting name representing the item below that. (c) For pop, pop2, dup, dup2, or swap, no further action is necessary. For dup.sub.-- x1 or dup2.sub.-- x1, insert the character ".sub.-- " between the first and second letters of the name resulting from step (b). For dup.sub.-- x2 or dup2.sub.-- x2, insert the character ".sub.-- " between the second and third letters of the name resulting from step (b). The instruction so named is then used to replace the original instruction. Note that the replacement instruction may be the same as the original instruction, under another name. The names of these instructions are chosen so that the letters "a" and "v" in the prefix form a picture of the stack to be operated upon, considering the stack in its logical, single-stack form. The letter for the topmost stack item is nearest the base name of the operation ("pop", "dup", or "swap"). If ".sub.-- " is present in the name, it separates items acted upon by the instruction from items that are skipped over. The items acted upon are adjacent to the operation name "pop", "dup", or "swap". Instruction Mapping Mechanisms Alternatively, rather than the verifier performing the process steps of constructing the instruction names as described above, replacement of names can be performed through the use of a decision table or other mechanisms for mapping an instruction name and a set of binary values to a new instruction name. A decision table in accordance with the illustrative embodiment of the invention which is capable of performing the mapping of instruction names to a new instruction is illustrated in Table 1. Utilization of a decision table as illustrated in Table 1 eliminates the need for redundant names for instructions. In Table 1, an "X" signifies a "don't care condition.
TABLE 1
______________________________________
original fourth third next top of replacement
instruction
item item to top
stack instruction
______________________________________
pop x x x a apop
pop x x x v pop
pop2 x x a a aapop
pop2 x x v a avpop
pop2 x x a v avpop
pop2 x x v v pop2
dup x x x a adup
dup x x x v dup
dup2 x x a a aadup
dup2 x x v a avdup
dup2 x x a v avdup
dup2 x x v v dup2
dup.sub.-- x1
x x a a a.sub.-- adup
dup.sub.-- x1
x x v a adup
dup.sub.-- x1
x x a v dup
dup.sub.-- x1
x x v v dup.sub.-- x1
dup.sub.-- x2
x a a a aa.sub.-- adup
dup.sub.-- x2
x v a a a.sub.-- adup
dup.sub.-- x2
x a v a a.sub.-- adup
dup.sub.-- x2
x v v a adup
dup.sub.-- x2
x a a v dup
dup.sub.-- x2
x v a v dup.sub.-- x1
dup.sub.-- x2
x a v v dup.sub.-- x1
dup.sub.-- x2
x v v v dup.sub.-- x2
dup2.sub.-- x1
x a a a a.sub.-- adup
dup2.sub.-- x1
x v a a aadup
dup2.sub.-- x1
x a v a a.sub.-- avdup
dup2.sub.-- x1
x v v a v.sub.-- avdup
dup2.sub.-- x1
x a a v a.sub.-- avdup
dup2.sub.-- x1
x v a v v.sub.-- avdup
dup2.sub.-- x1
x a v v dup2
dup2.sub.-- x1
x v v v dup2.sub.-- x1
dup2.sub.-- x2
a a a a aa.sub.-- aadup
dup2.sub.-- x2
v a a a a.sub.-- aadup
dup2.sub.-- x2
a v a a a.sub.-- aadup
dup2.sub.-- x2
v v a a aadup
dup2.sub.-- x2
a a v a aa.sub.-- avdup
dup2.sub.-- x2
v a v a av.sub.-- avdup
dup2.sub.-- x2
a v v a av.sub.-- avdup
dup2.sub.-- x2
v v v a vv.sub.-- avdup
dup2.sub.-- x2
a a a v aa.sub.-- avdup
dup2.sub.-- x2
v a a v av.sub.-- avdup
dup2.sub.-- x2
a v a v av.sub.-- avdup
dup2.sub.-- x2
v v a v vv.sub.-- avdup
dup2.sub.-- x2
a a v v dup2
dup2.sub.-- x2
v a v v dup2.sub.-- x1
dup2.sub.-- x2
a v v v dup2.sub.-- x1
dup2.sub.-- x2
v v v v dup2.sub.-- x2
swap x x a a aaswap
swap x x v a nop
swap x x a v nop
swap x x v v swap
______________________________________
In the preferred embodiment of this invention, Java bytecode instruction set opcodes may be assigned to the new instructions as follows:
______________________________________
237 apop
238 aapop
239 avpop
240 aaswap
241 adup
242 aadup
243 avdup
244 a.sub.-- adup
245 a.sub.-- aadup
246 a.sub.-- avdup
247 v.sub.-- avdup
248 aa.sub.-- adup
249 aa.sub.-- aadup
250 aa.sub.-- avdup
251 av.sub.-- avdup
252 vv.sub.-- avdup
______________________________________
(2) The semi-standard JVM quick instructions getfield.sub.-- quick getfield.sub.-- quick.sub.-- w getstatic.sub.-- quick ldc.sub.-- quick ldc.sub.-- w.sub.-- quick putfield.sub.-- quick putfield.sub.-- quick.sub.-- w putstatic.sub.-- quick are construed always to operate on primitive values, using the primitive stack. The invention contemplates these additional quick instructions, which are exactly like the corresponding existing instructions without "a" beginning their name, but operate on reference values, using the reference stack: agetfield.sub.-- quick agetfield.sub.-- quick.sub.-- w agetstatic.sub.-- quick aldc.sub.-- quick aldc.sub.-- w.sub.-- quick aputfield.sub.-- quick aputfield.sub.-- quick.sub.-- w aputstatic.sub.-- quick Whenever a slower instruction such as getfield, getstatic, ldc, ldc.sub.-- w, putfield, or putstatic is to be replaced by a quick instruction during the process of executing the slower instruction, a quick instruction whose name begins with "a" is chosen if the symbolic name resolution process determines that the datum to be transferred to or from the stack will be a reference; otherwise the usual quick instruction is chosen. The instruction agetfield.sub.-- quick is identical in its function to getfield.sub.-- quick, except in that agetfield.sub.-- quick uses the reference stack. Similar analogies are for the other seven cited quick instruction types. In the preferred embodiment of this invention, Java bytecode instruction set opcodes may be assigned to the new instructions as follows:
______________________________________
232 getfield.sub.-- reference.sub.-- quick
233 getfield.sub.-- reference.sub.-- quick.sub.-- w
234 getstatic.sub.-- reference.sub.-- quick
235 ldc.sub.-- reference.sub.-- quick
236 ldc.sub.-- reference.sub.-- w.sub.--
231 putfield.sub.-- reference.sub.-- quick
229 putfield.sub.-- reference.sub.-- quick.sub.-- w
230 putstatic.sub.-- reference.sub.-- quick
______________________________________
Space Optimization Technique An additional optimization technique is contemplated herein, which is not necessary for implementation of the invention but which improves space utilization. This technique is carried out by the verifier at the same time that the verifier is replacing pop, dup, and swap operations with more specialized versions while analyzing the code for a method. The objective of the optimization is to reduce the space needed on the stacks for local variables. The unoptimized technique simply reserves space for all the local variables of a method on both the primitive stack and the reference stack. This uses twice as much space for the local variables as would be necessary with the usual single-stack representation, but has the advantage that instructions that access local variables can be used unchanged. The optimization technique is implemented with an inventive method which first analyzes, for each local variable slot, whether the slot is ever used to hold a reference value and whether it is ever used to hold a primitive value. A local variable in the JVM may be used to hold a primitive value in some parts of the code for a method and to hold a reference value in other parts of the code for the same method. The slots are then gathered into two sets that are not necessarily disjoint, i.e. a first set of all local variable slots used for primitive values and a second set of all local variable slots used for reference values. In the illustrative embodiment, let P be the number of slots in the first set and let R be the number of slots in the second set. The slots in each set are renumbered so as to have consecutive numbers starting with zero. Specifically, for each set, for each slot S in that set, if the set contains N other slots whose original offset is less than the original offset of slot S, then slot S is renumbered to have offset N. This particular renumbering strategy advantageously allows slots that originally have consecutive offsets to be renumbered so as to have consecutive offsets in the same order. Next, once the slots are renumbered, every occurrence in the code of any of the following instructions is rewritten by the JVM verifier to refer to the new location of the stack slot, relative to the appropriate frame pointer, and according to the renumbering:
______________________________________
iload iload.sub.-- 0
iload.sub.-- 1
iload.sub.-- 2
iload.sub.-- 3
fload fload.sub.-- 0
fload.sub.-- 1
fload.sub.-- 2
fload.sub.-- 3
lload lload.sub.-- 0
lload.sub.-- 1
lload.sub.-- 2
lload.sub.-- 3
dload dload.sub.-- 0
dload.sub.-- 1
dload.sub.-- 2
dload.sub.-- 3
aload aload.sub.-- 0
aload.sub.-- 1
aload.sub.-- 2
aload.sub.-- 3
istore istore.sub.-- 0
istore.sub.-- 1
istore.sub.-- 2
istore.sub.-- 3
fstore fstore.sub.-- 0 fstore.sub.-- 1
fstore.sub.-- 2
fstore.sub.-- 3
lstore lstore.sub.-- 0
lstore.sub.-- 1
lstore.sub.-- 2
lstore.sub.-- 3
dstore dstore.sub.-- 0 dstore.sub.-- 1
dstore.sub.-- 2
dstore.sub.-- 3
astore astore.sub.-- 0 astore.sub.-- 1
astore.sub.-- 2
astore.sub.-- 3
______________________________________
is rewritten by the verifier to refer to the new location of the stack slot, relative to the appropriate frame pointer, according to the renumbering. Next, the results are annotated so that when the method is invoked, P slots are allocated for local variables on the primitive stack and R slots are allocated for local variables on the reference stack. The amount of excess memory used for local variables will then be equal to the size of the intersection of the two sets; if this intersection is empty, because no local variable slot is ever used for a reference value and also for a primitive value, then no excess memory will be allocated for that method. For the reader's benefit, a specific example of the inventive space optimization method is provided. Suppose that a method uses six local variable slots. Slots 0, 3, and 4 are each used at certain points in the code of the method to hold a reference value. Slots 1 and 2 are used together at certain points in the code of the method to hold a double-precision floating-point value. Slots 1, 3, and 5 are each used at certain points in the code of the method to hold an integer value. The verifier, as it traverses the code for the method, determines the following slot information:
______________________________________
0 1 2 3 4 5
reference reference
reference
double - floating - point
integer integer integer
______________________________________
The verifier then constructs the set of local variable slots for reference values {0, 3, 4} and the set of local variable slots for primitive values {1, 2, 3, 5}. The reference value slots are renumbered: 0.fwdarw.0 3.fwdarw.1 4.fwdarw.2 and the primitive value slots are renumbered 1.fwdarw.0 2.fwdarw.1 3.fwdarw.2 5.fwdarw.3 Note that the consecutive slots 1 and 2, used to hold a double floating point value, are renumbered to consecutive slots 0 and 1. Next, for example, an instruction sequence such as iload.sub.-- 3 istore 5 dload.sub.-- 1 aload 4 astore.sub.-- 3 would be written by the verifier, using the slot renumberings, as follows:
______________________________________
iload.sub.-- 2
3 .fwdarw.
2 in primitive renumbering
istore 3 5 .fwdarw.
3 in primitive renumbering
dload.sub.-- 0
1 .fwdarw.
0 in primitive renumbering
aload 2 4 .fwdarw.
2 in reference renumbering
astore.sub.-- 1
3 .fwdarw.
1 in reference renumbering
______________________________________
When the method is invoked, four slots are allocated for local variables on the primitive stacks and three slots are allocated for local variables on the reference stack, for a total of seven slots. This total exceeds the six slots needed in the one-stack representation by one slot, which is the size of the intersection of the two sets. If the optimization technique were not used, six slots would be allocated on each of the two substacks for a total of 12 slots. Note, a short one-byte instruction, such as iload.sub.-- 2, can always be rewritten as a short instruction, because the renumbering gives a slot a new offset that is not greater than its old offset. Also, the same offset (3, in this example) can be rewritten to different offsets depending on whether the instruction handles reference data or primitive data. FIG. 4 is a flowchart detailing an illustrative routine which computes stack sizes and sets up the program substacks in accordance with the principles of the invention. Although a single flowchart is shown, it should be understood that, depending on the implementation, some of the illustrated steps may be performed at different times. For example, instruction replacement as detailed in steps 402-406 may be performed at compilation or loading time, whereas stack allocation (steps 408-432) is generally performed during loading. The actual set-up of the stacks as set forth in steps 434-436 is performed by the operating system at the time of initial execution. The routine shown in FIG. 4 begins in step 400 and proceeds to step 402, where each instruction, or bytecode, is examined. As previously mentioned, this examination can be performed during program load by the JVM verifier function. The instructions are examined to determine whether they are reference specific, primitive data specific or indiscriminate. In step 404, a decision is made based on the examination in step 402 whether the instruction is indiscriminate. If the instruction is indiscriminate, the routine proceeds to step 406, where the indiscriminate instruction is replaced with one or more discriminate instructions as previously described. Alternatively, if, in step 404, it is determined that the instruction discriminates between reference values and primitive data, then the routine proceeds directly to step 408. In step 408, a check is made to determine whether the instruction under examination reads or writes primitive data into a destination variable. If the instruction does read or write primitive data, then the destination variable is labeled as a primitive variable in step 410. Otherwise, the routine proceeds to step 412. In step 412, a check is made to determine whether the instruction under examination reads or writes a reference into a destination variable. If the instruction does read or write a reference, then the destination variable is labeled as a reference variable in step 414. Otherwise, the routine proceeds to step 416. In step 416, a check is made to determine whether any more instructions in the program stream remain. If there are remaining instructions, the routine returns to step 402 to examine the next instruction. If no instructions remain, the routine then proceeds to renumber the variables in steps 418-420 and then alter the instructions to use the renumbered variable in steps 422-432. Finally, stack slots are allocated in steps 434 and 436. In particular, in step 418, the number of primitive variables (P) is determined from the labeled variables, and the primitive variables are renumbered as described above. Next, in step 420, the number of reference variables (R) is determined, and these are renumbered. It should be noted that it is possible for the same local variable to be labeled as a primitive variable, a reference variable or both. Subsequently, in steps 422-432, a second pass is made over the program instructions to alter the instruction to use the renumbered variable values. In particular, the instructions are re-examined in step 422. In step 424, a check is made to determine whether the instruction under examination reads or writes primitive data into a destination variable. If the instruction does read or write primitive data, then the instruction is altered to use the renumbered value of the primitive destination variable in step 426. Otherwise, the routine proceeds to step 428. In step 428, a check is made to determine whether the instruction under examination reads or writes a reference into a destination variable. If the instruction does read or write a reference, then, in step 430, the instruction is altered to use the renumbered reference variable number. Otherwise, the routine proceeds to step 432. If step 432 determines that additional instructions remain to be examined the routine proceeds back to step 422. Next, in steps 434 and 436, the first and second sub-stacks are defined using the allocations made in steps 418 and 420. More particularly, in step 434, P slots are allocated for primitive local variables are pushed onto a first substack using the first substack pointer as the stack pointer and the second substack pointer as the first stack limit as previously described. Next, in step 436, R slots for the reference local variables are pushed onto a second sub-stack with and the second sub-stack limit and points set as described above. The routine then ends in step 438. In an alternate embodiment of this work, all stack items might be capable of holding a single primitive datum, even long and double quantities. For example, all stack items would be 64 bits, and reference could be as large as 64 bits rather than 32 bits. In this case memory would be wasted when a single stack slot were used to hold a 32-bit integer or floating-point datum, or two stack slots were used to hold a long or double datum. In yet another alternate embodiment, the invention may be implemented as a computer program product for use with a computer system. In such an implementation, all the functions performed may be implemented with corresponding processor instructions. Any number of programming languages including most processor instruction sets, assembly languages and the C programming language provide facilities which allow for the manipulation of individual bits within a data word, and would be suitable for implementation of such and all software embodiment of the invention. Such implementation may comprise a series of computer instructions either fixed on a tangible medium, such as a computer readable media, e.g. diskette, CD-ROM, ROM, or fixed disk, or transmittable to a computer system, via a modem or other interface device, such as communications adapter connected to a network over a medium. Medium can be either a tangible medium, including but not limited to optical or analog communications lines, or may be implemented with wireless techniques, including but not limited to microwave, infrared or other transmission techniques. The series of computer instructions embodies all or part of the functionality previously described herein with respect to the invention. Those skilled in the art will appreciate that such computer instructions can be written in a number of programming languages for use with many computer architectures or operating systems. Further, such instructions may be stored using any memory technology, present or future, including, but not limited to, semiconductor, magnetic, optical or other memory devices, or transmitted using any communications technology, present or future, including but not limited to optical, infrared, microwave, or other transmission technologies. It is contemplated that such a computer program product may be distributed as a removable media with accompanying printed or electronic documentation, e.g., shrink wrapped software, preloaded with a computer system, e.g., on system ROM or fixed disk, or distributed from a server or electronic bulletin board over a network, e.g., the Internet or World Wide Web. Although various exemplary embodiments of the invention have been disclosed, it will be apparent to those skilled in the art that various changes and modifications can be made which will achieve some of the advantages of the invention without departing from the spirit and scope of the invention, such modifications to the inventive concept are intended to be covered by the appended claims.
|
Same subclass Same class Consider this |
||||||||||