Method and system for target register allocation

Details Method and system for target register allocation Method and system for target register allocation

1998-12-23

2001-11-20

Chaki, Kakali (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000, C717S152000, C717S152000, C717S152000, C717S152000, C717S152000

Reexamination Certificate

active

06321379

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to target register allocation and, more specifically, to allocating and locating target registers for a computer program.
BACKGROUND OF THE INVENTION
Computers provide branch operations or instructions to control the flow of execution of a computer program. These branch operations can either be unconditional or conditional branches. An unconditional branch (e.g., a “goto” statement) indicates that the flow of control is to transfer to the location designated by the branch, rather than to the next location after the branch. A conditional branch (e.g., an “if” statement) indicates that the flow of control is to transfer to the location designated by the branch only if the condition specified in the branch is satisfied. If the condition is not satisfied, then the flow of control continues at the location after the branch. Some computers provide branch operations in which the transfer location for the branch (“target”) is stored in a specified target register. For example, a computer may provide several target registers that can be specified by a branch operation as containing the address of the target. Prior to executing a branch, the target register specified by that branch needs to be loaded with the address of the target of the branch. This loading of the target register is referred to as “defining the target register.”
A compiler may generate code that uses the branch operations to affect function invocation. When the compiler encounters a function invocation, the compiler generates code to load a “call” target register with the address of the function, code to load a “return” target register with the return address to which the function is to return, and code to branch to the address indicated in the call target register. The compiler uses the same target register every time as the return target register. In this way, functions that are separately compiled can be invoked and know where the return address is stored. In addition, compilers may generate code, assuming that certain target registers are to be preserved by the calls to functions. If a called function uses such a target register, then the called function needs to save the value of target register when invoked and restore the saved value of the target register before returning from the call. These target registers are referred to as “callee save registers.” Each function could have its own set of registers as callee save registers. However, in general, a compiler may by convention assume that the set of callee save registers is the same for all functions.
A compiler may also use branch operations to implement “switch statements” and “indirect calls” of a programming language. When generating code for a switch statement, the compiler generates code to calculate at runtime the target within the switch statement. Once that target is calculated, the address of the target can then be loaded into the target register that is specified in the branch operation. When generating code for an indirect call, the compiler may generate code to load the target register with a variable that contains the address of the function to be called.
Computer programs can have very complex flow of control. Their flow of control is often represented by a control flow graph (“CFG”) that indicates the paths of execution between the “basic blocks” of the computer program. A “basic block” is generally considered to be a series of one or more instructions having one and only one entrance instruction (i.e., where control enters the block), and one and only one exit instruction (i.e., where control exits the block). A “control flow graph” is a well-known structure for representing the flow of execution between basic blocks of a program. A control flow graph is a directed graph in which each node of the graph represents a basic block. A control flow graph has a directed edge from a block B
1
to a block B
2
if block B
2
can immediately follow block B
1
in some path of execution. In other words, a control flow graph has a directed edge from block B
1
to block B
2
(1) if the last instruction of block B
1
includes a conditional or unconditional branch to the first instruction of block B
2
, or (2) if block B
2
immediately follows block B
1
in the order of the program and block B
1
does not end in an instruction that includes an unconditional branch.
Because computer programs have complex flows of control, the selection of which target registers to assign to which branch operations can have a significant impact on the efficiency of such programs. For example, if the compiler generates code that specifies the same target register for each branch operation, then the compiler needs to generate code to re-load that target register before each branch operation. Such re-loading can seriously impact the efficiency of the program. It would be desirable to have a system that would allocate target registers to a computer program in a way that tended to improve the overall efficiency of the computer program.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide a computer-based method and system for allocating target registers to branch operations and for determining the location of target definitions for the branch operations within a computer program. The target register allocation system of the present invention allocates a target register to be specified by each branch operation. The target register is to contain the address of the target that is loaded by the target definition. The target register allocation system determines a location in the computer program for a target definition such that whenever the branch operation is executed, the allocated target register contains the address of the target of the branch. The target allocation system may determine the location to be in a dominator block of the branch operation. The target allocation system may also determine the location of a target definition so that the address of the target that is loaded by the target definition can be used by multiple branch operations. The target allocation system may also determine the location of the target definition based on execution frequency of locations. The target allocation system may, when a branch operation is in a loop, determine the location of the target definition is to be outside the loop. The target allocation system may, when the program is a function, give preference to a non-callee save register in allocating a target register. The target allocation system may give preference to a callee save register of a function whose invocation is located in between the determined location and the location of the branch operation on a path of execution when allocating a target register. Conflicting preferences may be resolved based on execution frequencies.


REFERENCES:
patent: 4819234 (1989-04-01), Huber
patent: 4872167 (1989-10-01), Maezawa et al.
patent: 5168554 (1992-12-01), Luke
patent: 5504932 (1996-04-01), Vassiliadis et al.
patent: 5533192 (1996-07-01), Hawley et al.
patent: 5557761 (1996-09-01), Chan
patent: 5594864 (1997-01-01), Trauben
patent: 5632032 (1997-05-01), Ault et al.
patent: 5712996 (1998-01-01), Schepers
patent: 5754855 (1998-05-01), Miller et al.
patent: 5768591 (1998-06-01), Robinson
patent: 5774721 (1998-06-01), Robinson
patent: 5787245 (1999-07-01), You et al.
patent: 5805892 (1998-09-01), Nakajima
patent: 5812811 (1998-09-01), Dubey et al.
patent: 5867643 (1999-02-01), Sutton
patent: 5877766 (1999-03-01), Bates et al.
patent: 5887166 (1999-03-01), Mallick et al.
patent: 5901315 (1999-05-01), Edwards et al.
patent: 5903730 (1999-05-01), Asai et al.
patent: 5913925 (1999-06-01), Kahle et al.
patent: 5953530 (1999-09-01), Rishi et al.
patent: 5961639 (1999-10-01), Mallick et al.
patent: 5978902 (1999-11-01), Mann
patent: 6002872 (1999-12-01), Alexander, III et al.
patent: 6009269 (1999-12-01), Burrows et al.
patent: 6058493 (2000-05-01), Talley
patent: 6059840 (2000-05-01), Click, Jr.
patent: 6072952 (2000-06-01), Janakiraman
patent: 6094716 (2000-07-01), Witt
patent:

Affiliated with

Also associated with

Rating

Method and system for target register allocation 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 target register allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for target register allocation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2604020