Mechanism for finding spare registers in binary code

Details Mechanism for finding spare registers in binary code Mechanism for finding spare registers in binary code

1998-11-02

2001-02-20

Chaki, Kakali (Department: 2762)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000, C714S035000

Reexamination Certificate

active

06192513

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The invention relates in general to program instrumentation, and in particular to an efficient mechanism for finding spare registers for use in instrumenting programs to measure performance of binary code.
BACKGROUND OF THE INVENTION
Compilers convert a source program that is usually written in a high level language into low level object code, which typically consists of a sequence of machine instructions or assembly language. The constructs in the source program are converted into a sequence of assembly language instructions. To achieve the highest possible efficiency of operation, it is essential to know exactly how much time the program takes to execute. In order to concentrate on those parts of the program that need improvements in efficiency, the length of time that the program takes to execute, and other statistics about the program execution, at the function level, at the loop level, and at the basic block level must be determined. Specialized programs have been used to conduct measurements of the required program performance characteristics necessary to acquire such data.
One such program is the instrumentor either static or dynamic. Instrumentors conduct specific tasks within binary files such as assessing instruction types and adding program code where appropriate. If, for example, a desired point of code insertion is identified, the instrumentor will add program instructions which precede this point so as to monitor the operation of the main program at this point. The instrumentor then rewrites the binary file in a manner such that when the modified program is finally executed, both the original binary instructions and the instrumenting instructions will execute, thus producing output resulting from both the original binary program code, as well as from the instrumenting code.
A problem faced by instrumenting tools after deciding that instrumenting code is to be added to a program, is that of finding temporary storage space in which to store data. Using memory would avoid interference with the main program, but slows execution. It is therefore necessary to use registers, and as many of them as possible. The problem here lies in determining which registers can be used without interfering with operations of the main program. Four principal techniques have been used in the prior art to address this problem.
The first of these prior art techniques involves deciding upon a set of registers for use by the instrumenting program. Then, to preclude interference with the main program by the instrumenting program, the values of the selected registers are saved to memory. The instrumentor performs whatever operations are required for its purposes, employing the selected registers, and then retrieves the original values of the selected registers from memory.
One advantage of this approach is its safety. Because the data originally present in the selected registers is saved to memory and then retrieved after instrumentor operations are complete, the instrumentor does not harm the original data. A further advantage is that during instrumentation, time is saved because the instrumentor does not check the operation of the main program with regard to the selected registers, before saving their contents to memory.
The principal disadvantage of this first approach is that movement of data between the registers and memory locations is slow, and in this case, the contents of all selected registers is saved to memory regardless of whether the data in these registers is useful to the main program or not. As such, there is likely some wasteful data transfer to and from memory using this technique. This movement of useless data to and from memory from the registers is computationally expensive and is a major drawback of this first technique.
The second approach seeks to avoid the time consuming movement of register contents to and from memory by determining which registers contain data to be subsequently accessed by the main program and which do not. This involves a process of global analysis which by itself is quite time consuming. The second technique operates as follows.
At every point in the main program where the instrumentor decides to place instrumenting code, the registers available for instrumentation have to be identified. Arcs or lines are drawn between the points in the program where data in particular registers is stored and accessed. If the point in the program where the instrumentor seeks to place code is in between the points where data is stored in a register and data from this register is accessed, the register is deemed unavailable for instrumentation. Once a sufficient number of available registers is identified, the instrumentor uses these identified registers for the instrumenting code needed at that point in the program. This analysis must be performed at every point where instrumentation code is to be inserted.
The advantages of this approach are that it is safe and precise. It is also quick to run in the execution phase because the data traffic between the registers and memory mentioned in the first technique is absent here. The main disadvantage is that the register availability determinations made during the instrumenting phase are time consuming. Here, there is slow instrumentation and rapid execution which is the opposite of the situation in the first technique.
A distinguishing characteristic of the first two approaches is that they are both applicable to situations where the designer of the instrumenting program has no control over the design of the original or main program, and no provision is made in the main program to provide for the instrumentation program. The following two techniques address situations where there is some cooperation between the design of the original program and the instrumenting program.
The third technique involves cooperation between the development of the original compiler program and the instrumentor program in the form of expressly reserving certain registers for use by the instrumentor program when designing the original compiler program. Using this approach, the instrumentor program has the advantages associated with both of the first two techniques discussed above, with none of the disadvantages. Since the registers are set aside in advance, the instrumentor program is not burdened with the need to check for availability of the registers. The arrangement is such that the compiler program will not have used these registers and will therefore not have any data in them to be destroyed. Further, assuming that a sufficient number of registers has been set aside, the instrumentor program will not have to transfer data between the registers and memory, thereby obviating the need for this time consuming data transfer process.
One disadvantage associated with the third technique is that the reservation of registers for the instrumentor program reduces the number of registers available for the compiler program. The compiler program, which is written in anticipation of the need for registers by an instrumentor program, will likely have to move data between registers and memory more often than it would otherwise because of the reduced number of available registers. The compiler program is therefore likely to run more slowly. Further, many compiler programs written in anticipation of the use of instrumenting programs will never in fact be instrumented. Therefore, it is a further disadvantage that the burden imposed on the compiler program may be uncompensated by a benefit to an instrumenting program.
A fourth technique uses a looser form of cooperation between compiler and instrumentor. The compiler program is written taking full advantage of the registers provided by the processor, thus permitting optimum execution efficiency. The compiler program however, leaves information embedded in the program, at the bottom of each basic block of code for the instrumentor program to read, indicating which registers are available for use by the instrumentor program in that block. Compilers typically have to acquire su

Affiliated with

Also associated with

Rating

Mechanism for finding spare registers in binary code does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mechanism for finding spare registers in binary code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for finding spare registers in binary code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2571528