System and method for dynamically identifying free registers

Details System and method for dynamically identifying free registers System and method for dynamically identifying free registers

1997-08-21

2002-08-20

Maung, Zarni (Department: 2151)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C712S228000

Reexamination Certificate

active

06438740

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to computer systems and, more particularly, to identifying free registers in a computer.
BACKGROUND OF THE INVENTION
During the execution of a computer program, a register “R” is called “free” if, for all possible execution paths of a program from that particular point forward, the content of R is always written before being read. If register R is not free then it is said to be in use.
Knowing whether a register is free or in use is important for many reasons. For example, when calling subroutines, if the free registers are known, then the contents of the free registers do not have to be saved upon entry to the subroutine and restored upon return from the subroutine. This saves processing time which would otherwise be required to store and restore data to/from memory in order to ensure that the use of a register while executing the subroutine does not interfere with subsequent program execution. Thus, a determination of which registers are free at various points while executing a program is typically performed during program compiling and is an important aspect in compiler design in the context of assignment of registers.
A conventional method of locating free registers during compiling is illustrated in FIG.
1
. The first step in this method is to construct a complete flow graph. Next, for each register the edges of the graph are explored backwards, starting from each Read instruction from that register and stopping at all Write instructions to that register. At each point that is reached before a Write is reached, that particular register is marked as “in-use” or not free.
For example, in
FIG. 1
, for register R
1
the flow graph is examined from the Read
1
at
50
. Working backwards from the Read
1
at
50
, each execution path reaches a Write at
52
before a point of interest
55
is reached. Therefore, register R
1
is a free register at
55
. For register R
2
the flow graph is also examined backwards from each Read
2
statement. From the Read
2
at
54
, the search reaches point
55
before a Write is reached. Therefore, register R
2
is not a free register at
55
.
This type of search requires analysis of the entire program and sometimes even with an entire code analysis, the system cannot make complete determinations. This is because jumps and branches within the program may require the searching algorithm to make pessimistic assumptions regarding the status of a particular register. Further, this type of search for free registers requires an amount of time which makes its use impractical during program execution.
Free registers are also required in order to implement a software “patch.” A program may require a software patch to replace small portions of the original executable code with new code. The patch may be required for debugging the program, instrumentation, architecture emulation, or other reasons which are well known to those skilled in the art.
For example, in situations where an upgraded program is being run on an existing computer architecture that does not include upgraded hardware, the upgraded program may have instructions which are not executable on the older architecture. To correct this problem, a patch that emulates the upgraded hardware is inserted into the program.
When modules of a program are mapped to memory, word or page alignment of the modules may result in “free space” between aligned modules. Prior art
FIG. 2
illustrates a typical program stored in memory. The program includes four modules
205
-
220
, with free space
225
-
240
located between the modules. A patch can be inserted into the free space during linking or loading, or while the program is executing.
With reference to prior art
FIG. 3
, new source code
300
represents the patch. A compiler
310
compiles the patch and sends the compiled code to a linker
320
. The linker
320
then links the compiled patch code with original program executable code
330
so that the processor can execute the program patch. The linker
320
may also be coupled to various libraries
340
that contain previously compiled code. The details of linking the patched code with the executable code are well known by those skilled in the art and accordingly will not be further described herein.
Conventionally, when a patch is needed for a program, the contents of all required registers are saved to memory and then restored after the patch is executed. This may result in a serious performance penalty during program execution. For example, the time spent storing and restoring the contents of the registers to/from memory may slow the operation of the program to the point where the program execution is unacceptable. This is particularly true in cases where the patch is executed in a loop with many iterations.
Prior art
FIG. 4
illustrates a conventional patch executed within a program. At the step labeled
10
, the program is executing. At step
12
, a jump to the patch occurs. The program proceeds at step
14
to save the contents of required registers to memory or stack. In step
16
, the patch is executed. Upon completion of the patch execution, the program restores the registers as indicated at step
18
and jumps back to the program execution at step
20
. In other implementations, a patch can directly be inserted in the executable code.
In view of the above, a need exists for an improved technique to locate free registers within a program.
OBJECTIVES OF THE INVENTION
Accordingly, it is an object of the invention to locate free registers in an efficient manner. The free registers can then be utilized for various purposes, such as a software patch.
Another object of the invention is to execute a software patch without saving and restoring the content registers to memory.
A further object of the invention is to dynamically locate free registers while a program is executing without undue delays.
Yet another object of the invention is to reduce the number of instances of the same patch stored in memory.
Other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description. The embodiments shown and described provide illustration of the best mode contemplated for carrying out the invention. The invention is capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings are to be regarded as illustrative in nature, and not as restrictive.
SUMMARY OF THE INVENTION
To achieve the foregoing and other object and advantages, the present invention provides a technique for locating free registers within a plurality of registers. In accordance with the invention, a point of interest within an execution flow of a program, e.g., a point at which a jump to a patch will be eventually inserted, is selected. A search is performed from the point of interest to locate registers that will be written prior to being read, subsequent to, i.e., downstream of, the point of interest in the program's execution flow. The search is performed by using a flow graph constructed by analyzing the execution flow.
In accordance with other aspects of the invention, the search associated with a particular register is terminated when the particular register is determined to be in use. The identity of the located free registers may be stored for later use by, for example, a patch. The patch may then be executed by writing data in the identified free registers. Additionally, saved search results may be utilized by other searches that may overlap the saved results. Further, if desired, the flow graph may be searched for more than one free register at the same time or searched from more than one point of interest at the same time.
In further aspects of the invention, a timer may be started when the search for free registers begins, and the search can be terminated when the timer times out.
According to one embodiment of the invention, a computer system performs the steps for identifying free registers. The computer system includes a processor exec

Affiliated with

Also associated with

Rating

System and method for dynamically identifying free registers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for dynamically identifying free registers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for dynamically identifying free registers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2918065