Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2002-06-27
2004-01-27
Das, Chameli (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S140000, C717S116000, C717S151000, C717S153000, C717S165000, C707S793000, C711S101000, C711S129000, C711S170000, C711S173000
Reexamination Certificate
active
06684392
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to runtime environments for computer systems; more particularly, the present invention relates to an a runtime environment that distinguishes reference values from non-reference values.
BACKGROUND OF THE INVENTION
Many prior art runtime environments provide partitioning of registers into volatile registers and non-volatile registers. The partition of registers into volatile and non-volatile is typically performed once and is not subsequently changed. Volatile registers are typically used to pass parameters during subroutine calls and returns, provided the parameters fit. Parameters that do not fit in the volatile registers are passed in memory. Non-volatile registers store information that is maintained across subroutine calls. If a subroutine uses a non-volatile register, the subroutine saves the value stored in the non-volatile register and restores the value prior to returning to the calling routine.
Rigid partitioning of registers into volatile and non-volatile partitions provides predictability as to what registers are to be saved by called routines and what registers are to be saved by calling routines. However, rigid partitioning of registers does not provide information as to which registers are used for references to objects memory and which registers are used for storing values used by a routine or subroutine. For this reason, conservative garbage collection is often used in runtime environments that provide rigid partitioning of registers.
Garbage collection is the automatic recovery of memory space that is no longer required by a computation, routine or subroutine. Thus, garbage is the memory space that has been used, but is no longer required by a computation, routine or subroutine that has not yet been reclaimed by the memory manager of the runtime environment. Conservative garbage collection is based on an algorithm that overestimates the amount of live data in memory where garbage collection takes place. Conservative garbage collection is typically used where a compiler provides little support as to registers and memory locations that provide pointers to objects in memory.
Because overestimation of live data in memory (i.e., conservative garbage collection) results in sub-optimal memory management, support for non-conservative (perfect) garbage collection is desirable. A non-conservative garbage collector can take one of two forms. A non-copying collector that requires that unique references from a stack to a heap be identified so that heap objects that are in use are not accidentally collected. Alternatively, a copying collector additionally requires that non-unique references be identified so that they can be modified if the item referenced moves.
Some prior art runtime environments have provided support for garbage collection by providing tags that indicate whether a register or stack entry is a reference value or a non-reference value. However, maintaining tags increases the overhead required for memory management and in some cases reduces the number of bits available to represent data by using a most significant or least significant bit as a tag.
Prior art runtime environments have also provided support for garbage collection by providing a rigid reference
on-reference partitioning of registers. For example, the 68000 microprocessor available from Motorola, Inc. of Schaumburg, Ill. provides 16 data (non-reference) and 16 address (reference) registers. Runtime environments based on the 68000 provide 16 data and 16 address registers. Rigid reference
on-reference partitioning, however, is not based on the needs of a particular routine or subroutine, and therefore can provide sub-optimal register partitioning.
What is needed is a runtime environment that supports non-conservative garbage collection without the overhead associated with tags or tables to designate reference and non-reference values. The present invention provides such a runtime environment by providing volatile and non-volatile registers, each of which is further partitioned into reference and non-reference registers. The reference
on-reference partitioning of non-volatile registers is accomplished dynamically.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 4150430 (1979-04-01), Gusev et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4951194 (1990-08-01), Bradley et al.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5321834 (1994-06-01), Weiser et al.
patent: 5428786 (1995-06-01), Sites
patent: 5428793 (1995-06-01), Odnert et al.
patent: 5530866 (1996-06-01), Koblenz et al.
patent: 5537534 (1996-07-01), Voigt et al.
patent: 5655096 (1997-08-01), Branigin
patent: 5687368 (1997-11-01), Nilsen
patent: 5812446 (1998-09-01), Tailliet
patent: 5822787 (1998-10-01), Zucker
patent: 5842016 (1998-11-01), Toutonghi et al.
patent: 5878261 (1999-03-01), Holler et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 5903899 (1999-05-01), Steele, Jr.
patent: 5909579 (1999-06-01), Agesen et al.
patent: 5918235 (1999-06-01), Kirshenbaum et al.
patent: 5920876 (1999-07-01), Ungar et al.
patent: 5937186 (1999-08-01), Horiguchi et al.
patent: 5963982 (1999-10-01), Goldman
patent: 6047125 (2000-04-01), Agesen et al.
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6093216 (2000-07-01), Adl-Tabatabai et al.
patent: 6101580 (2000-08-01), Agesen et al.
patent: 6119206 (2000-09-01), Tatkar et al.
patent: 6256658 (2001-07-01), Mourey et al.
patent: 6292874 (2001-09-01), Barnett
patent: 6295640 (2001-09-01), Eidt
patent: 6317869 (2001-11-01), Adl-Tabatabai et al.
patent: 6317872 (2001-11-01), Gee et al.
patent: 6442751 (2002-08-01), Cocchi et al.
patent: 6446257 (2002-09-01), Pradhan et al.
patent: 6523926 (2003-02-01), Mitsuzawa et al.
Title: Performance of a Hardware-Assisted Real-Time Garbage Collector, author: Schmidt et al, ACM, 1994.*
Title: Garbage Collection for Prolog Based on WAM, author: Appleby et al, ACM, Jun. 1988.*
Title: Garbage collection in object oriented systenm author: Wilson, OOPSLA, 1991.*
Santhanam & Odnert, “Register Allocation Across Procedure and Module Boundaries,” Proceedings of the ACM SIGPLAN'90 Conf. on Programming Language Design and Implementation, 1990, pp. 28-39.
Apple Computer Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Das Chameli
LandOfFree
Method and apparatus for distinguishing reference values... 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 and apparatus for distinguishing reference values..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distinguishing reference values... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3258097