Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-01-05
2004-04-20
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000, C717S152000, C712S233000, C712S237000, C714S035000
Reexamination Certificate
active
06725335
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to runtime linking and unlinking, and more particularly to a system and method for unlinking a branch linking code fragments in a caching dynamic translator during runtime.
BACKGROUND OF THE INVENTION
Caching dynamic translators use a code cache to store native optimized translations of frequently executed code fragments, which reduces emulation overhead and improves performance. When a branch instruction is reached in a fragment in the code cache, processing exits from the code cache. In instances where the branch instruction branches to another fragment in the code cache, there is a context switch from processing in the code cache to outside the code cache and back into the cache. These context switches in and out of the code cache are expensive.
To avoid these expensive context switches, it is possible to link or “backpatch” branches that exit the cache only to jump right back into another code fragment that is already in the cache. Linking minimizes the expensive context switches necessary for implementing the cache exits and entries. Linking fragments in the code cache also results in some problems.
The contents of the code cache typically change with the working set of the application program. It is therefore desirable to be able to remove older fragments as newer ones enter the code cache. Any fragment being removed from the code cache, which has been previously linked to another fragment in the code cache, needs to be unlinked. Branch unlinking adds to the overhead of dynamic translation. If unlinking is too expensive to be feasible at runtime, the system has to compensate for the inability to quickly remove fragments by enlarging the size of the code cache, which becomes undesirable after a certain point.
SUMMARY OF THE INVENTION
Briefly, in a dynamic translator in which code fragments are stored in a cache, a method for linking and unlinking a first code fragment stored and a second code fragment in the cache comprises associating a memory area with a branch in a first code fragment that branches outside of the cache, and storing at least one instruction in the memory area that is executed when the branch is taken and control is to transfer to code outside of the cache. If it is determined that the branch can be set to branch to a location in a second code fragment stored in the cache, information is stored in the associated memory area from which the branch can be reconstructed in response to the determination, and the branch is changed so that it branches to the second code fragment stored in the code cache, thereby linking the first and second code fragments.
In another aspect of the present invention, if it is determined that the branch from the first code fragment to the second code fragment should be unlinked, the branch is reconstructed to its state before linking based on the information stored in the associated memory area.
In yet another aspect of the present invention, a method for linking and unlinking code fragments stored in a code cache comprises associating a memory area with a branch in a first code fragment that branches outside the cache. If it is determined that the branch can be set to branch to a location in a second code fragment stored in the cache, branch reconstruction information is stored in the memory area associated with the branch, and the branch instruction is updated to branch to the determined location in the second code fragment, thereby linking the first code fragment to the second code fragment.
REFERENCES:
patent: 5815720 (1998-09-01), Buzbee
patent: 5949995 (1999-09-01), Freeman
patent: 6185669 (2001-02-01), Hsu et al.
patent: 6205545 (2001-03-01), Shah et al.
patent: 6237065 (2001-05-01), Banerjia et al.
patent: 6295644 (2001-09-01), Hsu et al.
patent: 6330691 (2001-12-01), Buzbee et al.
patent: 6453411 (2002-09-01), Hsu et al.
Bob Cmelik, et al.: “Shade: A Fast Instruction-Set Simulator for Execution Profiling”; SIGMETRICS 94-5/94; pp 128-137.
Thomas Ball, et al.; “Branch Prediction for Free”; ACM-SIGPLAN-PLDI-6/93; pp 300-313.
Thomas Ball, et al.; “Efficient Path Profiling”; 1072-4451/96 IEEE; pp 46-57.
Bala Vasanth
Banerjia Sanjeev
Duesterwald Evelyn
LandOfFree
Method and system for fast unlinking of a linked branch in a... 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 system for fast unlinking of a linked branch in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for fast unlinking of a linked branch in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195700