# US 6,295,640 B1 · Method and apparatus for distinguishing reference values from non-reference values in a runtime environment

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,295,640 B1
- Document ID: US6295640B1
- Status: Granted
- Kind: B1
- Application number: 09/075,455
- Filed: 1998-05-08
- Granted: 2001-09-25
- Earliest claimed: 1998-05-08
- Assignees: Apple Computer, Inc.
- Inventors: Erik L. Eidt
- Web page: https://patentgrep.com/patent/US6295640B1

## CPC

- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- Y10S 707/99953: Recoverability
- Y10S 707/99957: Garbage collection
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method and apparatus for distinguishing reference values from non-reference values in a runtime environment is described. A set of volatile registers and a set of non-volatile registers are statically determined. The set of volatile registers is partitioned into reference and non-reference register partitions statically. The set of non-volatile registers is partitioned into reference and non-reference partitions dynamically.

## Claims

### Claim 1

A method of distinguishing reference values from non-reference values in a runtime environment comprising:
statically determining a set of volatile registers and a set of non-volatile registers;
statically determining a partition of the set of volatile registers into reference and non-reference partitions; and
dynamically determining a partition of the set of non-volatile registers into reference and non-reference partitions.

### Claim 2 (depends on 1)

The method of claim 1, wherein dynamically determining a partition is performed for each subroutine.

### Claim 3 (depends on 1)

The method of claim 1, wherein one or more reference registers store a pointer either directly or indirectly to an object in memory.

### Claim 4

A machine-readable medium having stored thereon data representing a sequence of instructions, the sequence of instructions which, when executed by a processor cause the processor to:
statically determine a set of volatile registers and a set of non-volatile registers;
statically determine a partition of the set of volatile registers into reference and non-reference partitions, and
dynamically determine a partition of the set of non-volatile registers into reference and non-reference partitions.

### Claim 5 (depends on 4)

The machine-readable medium of claim 4, wherein dynamically determining a partition is performed for each subroutine.

### Claim 6

A computer system comprising:
means for statically determining a set of volatile registers and a set of non-volatile registers;
means for statically determining a partition of the set of volatile registers into reference and non-reference partitions; and
means for dynamically determining a partition of the set of non-volatile registers into reference and non-reference partitions.

### Claim 7 (depends on 6)

The computer system of claim 6, wherein the means for dynamically determining a partition of volatile registers determines partitioning on a routine by routine basis.

### Claim 8 (depends on 6)

The computer system of claim 6, wherein the dynamic partition is indicated by a mask having a bit associated with each non-volatile register.

### Claim 9

A computer system comprising:
a bus;
a processor coupled to the bus, the processor having a set of registers, wherein the set of registers is partitioned into volatile and non-volatile registers, and further wherein the volatile registers are further partitioned into reference and non-reference registers; and
memory coupled to the bus, the memory storing a plurality of objects;
wherein the non-volatile registers are dynamically partitioned at compile time into reference and non-reference registers based on data flow analysis of the objects in memory.

### Claim 10 (depends on 9)

The computer system of claim 9, wherein the non-volatile registers are dynamically partitioned into reference and non-reference registers for each object in memory based on data flow analysis of the particular object in memory.

### Claim 11 (depends on 10)

The computer system of claim 10, wherein the objects are received as a series of byte codes.

### Claim 12

A method of collecting garbage in a computer system comprising:
a) Reading a register mask for a particular subroutine to determine a set of reference values stored on a stack;
b) determining whether the reference values stored on the stack correspond to a live object in memory;
c) counting back links stored on the stack to determine whether one or more of the subroutine calls have been completed; and
d) restarting initialization of reference values if the number of back links stored on the stack is an odd number.

### Claim 13 (depends on 12)

The method of claim 12, wherein a) and b) are repeated for each of a plurality of subroutines placing values on the stack.

### Claim 14 (depends on 12)

The method of claim 12, wherein the register mask is determined dynamically at compile time based on data flow analysis of a corresponding subroutine.

### Claim 15 (depends on 12)

The method of claim 12, wherein a top value on the stack is used to determine whether processing of a corresponding stack frame has been completed.

### Claim 16

A method of calling a subroutine in a computer system comprising:
a) storing contents of a set of non-volatile registers on a stack;
b) storing a first back link indicating a stack location preceding the set of non-volatile registers; and
c) designating a set of stack locations for storing a first predetermined number of reference values and a second predetermined number of non-reference values.

### Claim 17 (depends on 16)

The method of claim 16 further comprising storing a back link on the stack that points to the first back link.

### Claim 18 (depends on 16)

The method of claim 16, wherein the first back link includes a mask value that indicates a partitioning of the non-volatile registers indicating reference values and non reference values.

### Claim 19 (depends on 16)

The method of claim 16, wherein an interrupt occurring during any of a), b) and c) causes any of a), b) and c) that have been performed to be reversed and performed again after the interrupt has been serviced.

### Claim 20 (depends on 16)

The method of claim 16, wherein an interrupt occurring during any of a), b) and c) is serviced after the storing of the second back link.

### Claim 21

A computer-readable medium having stored thereon data representing a sequence of instructions, the sequence of instructions which, when executed by a processor, cause the processor to:
a) store contents of a set of non-volatile registers on a stack;
b) store a first back link indicating a stack location preceding the set of non-volatile registers; and
c) designate a set of stack locations for storing a first predetermined number of reference values and a second predetermined number of non-reference values.

### Claim 22 (depends on 21)

The computer-readable medium of claim 21, wherein the first back link includes a mask value that indicates a partitioning of the non-volatile registers indicating reference values and non reference values.

### Claim 23 (depends on 21)

The computer-readable medium of claim 21 further comprising storing a back link on the stack that points to the first back link.

### Claim 24 (depends on 21)

The computer-readable medium of claim 21, wherein an interrupt occurring during any of a), b) and c) causes any of a), b) and c) that has been performed to be reversed and performed after the interrupt has been serviced.

### Claim 25 (depends on 21)

The computer-readable medium of claim 21, wherein an interrupt occurring during any of a), b) and c) is serviced after the storing of the second back link.

### Claim 26

A computer data signal embodied received via a data communications medium comprising sequences of instructions that, when executed, cause one or more electronic systems to:
statically determine a set of volatile registers and a set of non-volatile registers;
statically determine a partition of the set of volatile registers into reference and non-reference partitions; and
dynamically determine a partition of the set of non-volatile registers into reference and non-reference partitions.

### Claim 27 (depends on 26)

The computer data signal embodied in the data communications medium of claim 26 further wherein dynamically determining a partition is performed for each subroutine.

### Claim 28

A computer data signal embodied received via a data communications medium comprising sequences of instructions that, when executed, cause one or more electronic systems to:
a) store contents of a set of non-volatile registers on a stack:
b) store a first back link indicating a stack location preceding the set of non-volatile registers; and;
c) designate a set of stack locations for storing a first predetermined number of reference values and a second predetermined number of non-reference values.

### Claim 29 (depends on 28)

The computer data signal embodied in the data communications medium of claim 28, wherein the first back link includes a mask value that indicates a partitioning of the non-volatile registers indicating reference values and non-reference values.

### Claim 30 (depends on 28)

The computer data signal embodied in the data communications medium of claim 28 further comprising sequences of instructions that, when executed, cause the one or more electronic devices to store a back link on the stack that points to the first back link.

### Claim 31 (depends on 28)

The computer data signal embodied in the data communications medium of claim 28, wherein an interrupt occurring during any of a), b) and c) causes any of a), b) and c) that has been performed to be reversed and performed after the interrupt has been serviced.

### Claim 32 (depends on 28)

The computer data signal embodied in the data communications medium of claim 28, wherein an interrupt occurring during any of a), b) and c) is serviced after the storing of the second back link.
