System and method for assisting exact Garbage collection by segregating the contents of a stack into sub stacks

• US 5,903,899 A
• Filed: 04/23/1997
• Issued: 05/11/1999
• Est. Priority Date: 04/23/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Steele, Guy L. Jr.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/842,063
• Time in Patent Office: 748 Days
• Field of Search: 707/206, 707/200, 711/200, 711/115, 711/5, 711/201
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

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

1. In a computer system having a processor and a memory, a method for discriminating whether a datum useful in execution of program instructions by the processor is one of a plurality of operand types, the method comprising the steps of:

A. defining a first area in the memory as a first program data stack capable of accommodating a datum of a first operand type, the first program data stack having a first stack base address and a first stack limit address which define the extent of the first program data stack;

B. defining a second area in the memory as a second program data stack capable of accommodating datum of a second operand type, the second program data stack having a second stack base address and a second stack limit address which define the extent of the second program data stack;

C. storing data of the first operand type within the first program data stack, and defining a first stack pointer which identifies the current top of the first data stack, the first data stack pointer having an address value equal to the second stack limit; and

D. storing data of the second operand type within the second program data stack, and defining a second program stack pointer which identifies the current top of the second data stack, the second stack pointer having an address value equal to the first stack limit.

2. The method of claim 1, wherein the first program stack base and the second program stack base define a linear, contiguous region of the memory.

3. The method of claim 1, wherein data operands of the first type are references.

4. The method of claim 1, wherein operands of the second data type are primitive values.

5. A method for discriminating between first and second operand data types in a program stack, the first and second operand data types being useful in execution of a program instruction, the method comprising the steps of:

A. identifying indiscriminate program instructions in a sequence of instructions, which indiscriminate program instructions operate with both the first and the second operand data types;

B. replacing each indiscriminate program instruction with at least one discriminate program instruction, which discriminate program instruction operates with one of the first and the second operand data types;

C. storing operand data associated with a discriminating instruction that operates with the first operand data type in a first program data stack; and

D. storing operand data associated with a discriminating instruction that operates with the second operand data type in a second program data stack.

6. The method of claim 5, wherein step B comprises the step of:

B.1 mapping an indiscriminate program instruction identifier to a replacement discriminate program instruction identifier by using a look-up table.

7. The method of claim 5, wherein step B comprises the step of:

B.2 mapping an indiscriminate program instruction identifier to a replacement discriminate program instruction identifier during instruction verification.

8. A computer system comprising:

a processor;

a memory coupled to the processor;

program stack logic, operatively coupled to the processor and the memory and configured to store a first type of operand datum in a first plurality of stack entries, and to store a second type of operand datum in a second plurality of stack entries;

the first plurality of stack entries forming a first program substack defined by a first substack base address, a first substack limit address, and a first substack pointer address;

the second plurality of stack entries forming a second program substack defined by a second substack base address, a second substack limit address, and a second substack pointer address; and

wherein the first substack pointer address and the second substack limit address are the same address.

9. The computer system of claim 8, wherein the second substack pointer address and the first substack limit address are the same address.

10. A computer program product for use with a computer system having a processor and a memory coupled to the processor, the computer system configured to store operand datum in a plurality of stack entries and to manipulate the stack entries during program instruction execution, the computer program product comprising a computer usable medium having program code embodied in the medium for enabling discrimination of stack entries as one of a plurality of predefined operand types, the program code comprising:

program code configured to define a first data stack to accommodate operand datum of a first predefined operand type, the first data stack having a first stack base address, first stack limit address, and a first stack pointer defining the current top of the first stack;

program code configured to define a second data stack to accommodate operand datum of a second predefined operand type, the second data stack having a second stack base address, second stack limit address, and a second stack pointer defining the current top of the second stack; and

the first stack limit address being the same address as the second stack pointer address.

11. The computer program product of claim 10 wherein the second stack limit address is the same as the first stack pointer address.

12. The computer program product of claim 10 further comprising program code configured to store operand datum of the first type in the first data stack;

and

program code configured to store operand datum of the second operand type in the second data stack.

13. The computer program product of claim 10, further comprising:

program code, responsive to an indiscriminate program instruction which accommodates operand data of more than one predefined type, configured to convert the indiscriminate program instruction into discriminate instructions which manipulate operand data of a single type.

14. The computer program product of claim 10, wherein operand data of the first type are references.

15. The computer program product of claim 10, wherein operand data of the second type are primitive values.

16. A method for allocating memory slots for a program data stack, the program data stack useful for accommodating a plurality of operand data types during execution of a program instruction, the method comprising the steps of:

A. determining from a sequence of program instructions, a first number representing program data stack entries required to accommodate datum of a first operand data type;

B. determining from a sequence of program instructions, a second number representing program data stack entries required to accommodate datum of a second operand data type; and

C. allocating a total number of slots for the program data stack equal to a sum of the first number and the second number.

17. The method of claim 16 further comprising the step of:

D. analyzing each instruction in the instruction sequence to determine the operand data types with which the instruction is compatible.

18. The method of claim 16, further comprising the step of:

E. storing datum of the first operand data type in a first plurality of contiguous slots in the program data stack.

19. The method of claim 16, further comprising the step of:

F. storing datum of the second operand data type in a second plurality of contiguous slots in the program data stack.

20. The method of claim 16, wherein step C comprises the steps of:

C.1 allocating on a first substack a number of slots equal to the first number; and

C.2 allocating on a second substack a number of slots equal to the second number.

21. A method for garbage collection for use in a computer system having a processor and a memory and a program including a plurality of instructions in the memory, the method comprising the steps of:

A. identifying indiscriminate program instructions in a sequence of instructions, which indiscriminate program instructions operate with both primitive data type and reference type operands;

B. replacing each indiscriminate program instruction with at least one discriminate program instruction, which discriminate program instruction operates with one of primitive data or reference type operands;

C. storing operand data associated with a discriminating instruction that operates with the primitive data type operands in a first program data stack;

D. storing operand data associated with a discriminating instruction that operates with the reference type operands in a second program data stack; and

E. using the reference type operands in the second program data stack to locate unused memory locations so that the unused memory locations can be reclaimed.

22. The method of claim 21, wherein the first program stack base and the second program stack base define a linear, contiguous region of the memory.