Method and system for target register allocation

Abstract

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 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 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.

Claims

What is claimed is:

1. A method in a computer system for locating target definitions for branches of a program, the method comprising:

for basic blocks of the program having a branch with a target, determining a live range of one or more basic blocks, the basic block with the branch being an ending basic block of the live range;

identifying a basic block that dominates two live ranges with ending basic blocks having a branch with the same target; and

locating a target definition for the branches of the ending basic blocks of the live ranges that are dominated by the identified basic block in the identified basic block.

2. The method of claim 1 wherein the basic blocks of a program are processed in reverse order of their position in the program.

3. The method of claim 1 wherein the identified basic block is not a preheader of a loop.

4. The method of claim 1 including selecting a target register for the target definition giving preference to callee save registers.

5. The method of claim 4 wherein the preference is given when a live range contains a function invocation.

6. The method of claim 1 wherein a live range of basic blocks has a starting basic block and a target definition for the branch of the ending basic block of the live range can be placed in the starting basic block.

7. The method of claim 1 including coalescing two live ranges into a single live range when a basic block that dominates the two live ranges with ending basic blocks having a branch with the same target are identified.

8. The method of claim 1 including when the basic blocks of the program are within a function selecting a target register for the target definition giving preference to non-callee save registers.

9. A computer system for locating target definitions for branches of a program, comprising:

a component that, for basic blocks of the program having a branch with a target, determines a live range of one or more basic blocks, the basic block with the branch being an ending basic block of the live range;

a component that identifies a basic block that dominates live ranges with ending basic blocks having a branch with the same target; and

a component that coalesces the dominated live ranges so that a target definition for the branches of the ending basic blocks of the coalesced live ranges can be located in the identified dominating basic block.

10. The computer system of claim 9 wherein the basic blocks of a program are processed in reverse order of their position in the program.

11. The computer system of claim 9 wherein the identified basic block is not a preheader of a loop.

12. The computer system of claim 9 including a component that selects a target register for the target definition giving preference to callee save registers.

13. The computer system of claim 12 wherein the preference is given when a live range contains a function invocation.

14. The computer system of claim 12 wherein the preference is given when the basic blocks of the live ranges are not within a function.

15. The computer system of claim 9 wherein a live range of basic blocks has a starting basic block and a target definition for the branch of the ending basic block of the live range can be placed in the starting basic block.

16. The computer system of claim 9 wherein one of the coalesced live ranges was itself coalesced from other live ranges.

17. The computer system of claim 9 including when the basic blocks of the program are within a function selecting a target register for the target definition giving preference to non-callee save registers.

18. A computer-readable medium containing instructions for controlling a computer system to locate target definitions for branches of a program, by a method comprising:

identifying live ranges of one or more basic blocks, each live range having a branch in an ending basic block of the live range;

identifying a basic block that dominates two live ranges with ending basic blocks having a branch with the same target; and

locating a target definition for the branches of the ending basic blocks of the live ranges that are dominated by the identified basic block in the identified basic block.

19. The computer-readable medium of claim 18 wherein the basic blocks of a program are processed in reverse order of their position in the program.

20. The computer-readable medium of claim 18 wherein the identified basic block is not a preheader of a loop.

21. The computer-readable medium of claim 18 including selecting a target register for the target definition giving preference to callee save registers.

22. The computer-readable medium of claim 21 wherein the preference is given when a live range contains a function invocation.

23. The computer-readable medium of claim 18 wherein a live range of basic blocks has a starting basic block and a target definition for the branch of the ending basic block of the live range can be placed in the starting basic block.

24. The computer-readable medium of claim 18 including coalescing two live ranges into a single live range when a basic block that dominates the two live ranges with ending basic blocks having a branch with the same target are identified.

25. The computer-readable medium of claim 18 including when the basic blocks of the program are within a function selecting a target register for the target definition giving preference to non-callee save registers.

26. A computer system for locating target definitions for branches of a program, comprising:

means for identifying a live range of one or more basic blocks, each live range having a branch;

means for identifying a basic block that dominates live ranges having a branch with the same target; and

means for coalescing the dominated live ranges so that a target definition for the branches of the coalesced live ranges can be located in the identified dominating basic block.

27. The computer system of claim 26 wherein the basic blocks of a program are processed in reverse order of their position in the program.

28. The computer system of claim 26 wherein the identified basic block is not a preheader of a loop.

29. The computer system of claim 26 including a component that selects a target register for the target definition giving preference to callee save registers.

30. The computer system of claim 29 wherein the preference is given when a live range contains a function invocation.

31. The computer system of claim 29 wherein the preference is given when the basic blocks of the live ranges are not within a function.

32. The computer system of claim 26 wherein a target definition for the branch of a live range can be placed in a starting block of the live range.

33. The computer system of claim 26 wherein one of the coalesced live ranges was itself coalesced from other live ranges.

34. The computer system of claim 26 including, when the basic blocks of the program are within a function, selecting a target register for the target definition giving preference to non-callee save registers.

Description

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 B1 to a block B2 if block B2 can immediately follow block B1 in some path of execution. In other words, a control flow graph has a directed edge from block B1 to block B2 (1) if the last instruction of block B1 includes a conditional or unconditional branch to the first instruction of block B2, or (2) if block B2 immediately follows block B1 in the order of the program and block B1 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.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates the coalescing of live blocks into a single block and the extending of that single live range to include a dominator block.

FIG. 2 illustrates the coalescing of live blocks that is delayed until a dominator block is encountered.

FIG. 3 illustrates the extending of a live range to encompass a loop.

FIG. 4 illustrates a situation in which a live range cannot be extended to encompass the loop.

FIG. 5 is a block diagram illustrating the TRA system.

FIG. 6 is a block diagram illustrating data structures used by the TRA system in one embodiment.

FIG. 7 is a flow diagram of an example routine that implements the TRA system.

FIG. 8 is a flow diagram of an example implementation of a number_operations routine.

FIG. 9 is a flow diagram of an example implementation of a process_last_block_in_loop routine.

FIG. 10 is a flow diagram of an example implementation of a process_loop_preheader routine.

FIG. 11 is a flow diagram of an example implementation of the coalesce_live_ranges routine.

FIG. 12 is a flow diagram of an example implementation of a process_calls_in_block routine.

FIG. 13 is a flow diagram of an example implementation of a adjust_target_registers_for_families routine.

FIG. 14 is a flow diagram of an example implementation of a process_callee_save_registers routine.

FIG. 15 is a flow diagram of example implementation of a start_live_range routine.

FIG. 16 is a flow diagram of an example implementation of a create_new_active_family routine.

FIG. 17 is a flow diagram of an example implementation of the update_active_family routine.

FIG. 18 is a flow diagram of an example implementation of the extend_loop_live_range routine.

FIG. 19 is a flow diagram of an example implementation of the find_new_target_register routine.

FIG. 20 is a flow diagram of an example implementation of the coalesce routine.

FIG. 21 is a flow diagram of an example implementation of the process_call routine.

FIG. 22 is a flow diagram of an example implementation of the spill_cheapest routine.

FIG. 23 is a flow diagram of an example implementation of the repack_register routine.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present invention provide a method and system for allocating target registers to a computer program. The target register allocation ("TRA") system of the present invention attempts to minimize the number of target register definitions (i.e., the loading of a target register) of the computer program, to place the target register definitions at a location early enough in the execution path that allows efficient prefetching of the target of a branch, to minimize the number of times target register definitions are executed, and to avoid the use of callee save registers of the function that is being allocated the target registers. The TRA system identifies branches that have the same target and attempts to locate a target definition so that it can be shared by both branches. If a branch is located within a loop, then the TRA system attempts to move the target definition outside the loop so that the target register is not re-loaded during each execution of the loop. When the TRA system encounters a call to a function, it tries to use the callee save registers of the called function so that the target definition of a branch that is after the call can be placed before the call. The TRA system can allocate such callee save registers knowing that their contents will not be changed by the called function.

The TRA system inputs a control flow graph with each block being ordered based on the position of the basic block in the computer program and having an execution frequency. The TRA system also inputs indications of the blocks that are the last blocks in a loop and blocks that are preheaders of loops. The TRA system processes the blocks in their reverse order, that is, starting with the last block in the computer program. When the TRA system encounters a block with a branch, it creates a "live range" for the target definition of the branch. A live range is a range of blocks that has a branch in its last block and that could still have the location of its target definition moved to a block that has not yet been encountered (i.e., earlier in the computer program). If the encountered block dominates a live range (i.e., the encountered lock is on every path of execution from the start of the computer program that includes the last block of the live range) with the same target, then the TRA system can locate the target definition for the branches of both live ranges in the encountered block. The TRA system coalesces the live ranges to create a single live range for both branches and locates the target definition for the live range in the encountered block. If, however, the newly created live range shares the same target as another live range, but the encountered block does not dominate the live range, then the TRA system cannot coalesce the live range because not all paths of execution through the other live ranges include the encountered block. Both these live ranges, however, may be dominated by blocks that have not yet been encountered. To keep track that these live ranges share the same target, the TRA system defines a "family" that contains both these live ranges. If eventually the TRA system encounters a block that dominates two live ranges in a family, the TRA system coalesces those two live ranges into a single live range and locates the target definition in the dominating block. In this way, the TRA system allows multiple branches to the same target to share the same target definition and locates the target definition early in the execution path of the branches.

FIGS. 1 and 2 illustrate the operation of the TRA system. FIG. 1 illustrates the coalescing of live blocks into a single block and the extending of that single live range to include a dominator block. As the TRA system encounters the blocks 101-105 in reverse order, the TRA system creates a live range when it encounters block 103 and another live range when it encounters block 102. Since block 102 dominates block 103 and the blocks share the same target (i.e., block 105), the TRA system coalesces the live ranges into a single live range that includes blocks 102 and 103 with the target definition for the branches located in block 102. When the TRA system encounters block 101, it notices that block 101 dominates the live range of blocks 102 and 103. Therefore, the TRA system extends the live range to include block 101 and the target definition for the branches of block 102 and 103 is located in block 101. The coalescing of live ranges allows target definitions to be shared and target definitions to be moved earlier in the execution path. The extending of a live range allows the target definition to be moved earlier in the execution path.

FIG. 2 illustrates the coalescing of live blocks that is delayed until a dominator block is encountered. The only difference between FIGS. 1 and 2 is that the second block does not dominate the third block. Thus, when the TRA system encounters block 202, it cannot coalesce the live ranges of block 202 and block 203. To keep track that these live ranges share the same target, the TRA system places these live ranges in the same family. When the TRA system encounters block 201, it notices that block 201 dominates both live ranges in the family. Therefore, the TRA system can use a single target definition that is located in block 201 for both live ranges. The TRA system coalesces the live ranges and extends the coalesced live range to include block 201.

The TRA system attempts to locate target definitions for branches occurring within a loop at the preheader block for the loop. The preheader block of a loop is a block that is immediately before a loop and dominates blocks in the loop. By locating the target definitions in the preheader, the target definitions are executed only once prior to executing the loop. The TRA system can place a target definition for a target register in the preheader when the last branch of a family of live ranges that use that target register in the loop and no other family that uses that target register has a target definition located in the loop. The TRA does so by extending the live range in the family to encompass the loop. If, however, there is such another family, then the TRA system tries to find another target register that can be used by the family to be extended. If the TRA system finds a suitable target register, then it assigns the suitable target register to the family and extends the live ranges of the family to encompass the entire loop so that the target definition can be located in the preheader block. The extending ensures that, if the TRA system eventually assigns the family to a different target register, any constraints on the assignment for the entire loop are considered.

FIG. 3 illustrates the extending of a live range to encompass a loop.

The loop comprises blocks 302-305, and block 301 is the preheader block of the loop. When the TRA system encounters block 305, it creates a live range for that block. When the TRA system encounters block 303, it creates another live range. Because the live range of block 305 has a different target register from the live range of block 303, the TRA system puts the live ranges in different families. When the TRA system encounters the preheader block 301, it extends the live range of block 303 to cover the entire loop. Since both live ranges encompass the entire loop, the TRA system can extend the live ranges to include the preheader block so that the target definitions for these live ranges can be located in the preheader block 301.

FIG. 4 illustrates a situation in which a live range cannot be extended to encompass the loop. The loop comprises blocks 402-407, and block 401 is the preheader block of the loop. The loop has three branches in blocks 403, 404, and 407 that have different targets. If the computer has only two target registers, then the live range associated with only one of the branches can include the entire loop. The target definition for the live range that encompasses the loop can be located in the preheader block 401. The other two branches need to share the other target register and have their target definitions placed in the body of the loop. When the TRA system encounters blocks 404 and blocks 407, it creates a live range for each in different families. When the TRA system encounters block 403 (and assuming the computer has only two target registers), it needs to select a target register for the live range to be created for block 403. Since both the target registers are already assigned to families, the TRA system sets one of the families to inactive, which means that the location of its target register definition is fixed at its current location. An active family of live ranges is one in which the TRA system is still attempting to find the final location of the target definition for the family. The TRA system then assigns the target register of the inactive family to the newly created live range for block 403. When the TRA system encounters the preheader block 401, it attempts to extend the family of the live range for block 403 to encompass the loop. However, since another family (i.e., that is now inactive) using the same target register has its target definition located in the loop, the attempt fails for the family of the live range of block 403. The TRA system will, however, extend the other live range that is currently active to encompass the loop and locate its target definition in the preheader block 401.

The TRA system allocates target registers for use in calling to and returning from functions. In one embodiment, any target register can be used to store the address for the function ("call register"), but only a predefined target register is used to store the return address ("return register"). The TRA system allocates two target registers when it encounters a call within a block and creates two live ranges. The TRA system also attempts to ensure that any family of live ranges that is active when a call is encountered is assigned to a callee save register of the function to be called. If any callee save register is not currently assigned to an active family, the TRA system attempts to assign that callee save register to an active family that is not using a callee save register of the function to be called. If the TRA system cannot assign a callee save register to all the active families (because not enough active families are available), then the TRA system sets those families to inactive, so that their target definition is located after the call. In this way, the TRA can extend live ranges across the call. The TRA system ensures that when a new target register is assigned to a family, that target register is a callee save register for each function called within a live range of the family. A loop may have multiple calls to functions that each have a different number of callee save registers. When the TRA system extends a live range to include a loop so that its target definition can be located in the preheader block of the loop, it ensures that the live range is assigned a target register that is a callee save register for each function that is called in the loop.

When the TRA system is allocating target registers for a function (e.g., portions of a computer program other than the main routine), it assigns target registers with a preference to non-callee save registers. If the TRA system can avoid allocating a non-callee save register to the function, then the program does not save and restore that non-callee save register. To help ensure that non-callee save registers are allocated when possible, the TRA system uses a repack algorithm when a live range is set to inactive to see if any live ranges can have their target register switch from a callee save register to a non-callee save register. In one embodiment, the TRA system assumes that the callee save registers are sequentially numbered from the lowest register number and that the higher numbered target registers are the non-callee save registers. Thus, the TRA system assigns higher numbered registers first and repacks by assigning higher numbered target registers to live ranges. If the actual callee save registers are not sequentially numbered from the lowest, then after the target allocation for the function is complete, the TRA system maps the assumed numbers of the callee save registers to the actual numbers of the callee save registers.

FIG. 5 is a block diagram illustrating the TRA system. The TRA system executes on a computer system 501 that includes a memory and a central processing unit. The computer program implementing the TRA system 505 is stored in memory of the computer system. The TRA system inputs a control flow graph ("CFG") 502 of a function that is to be allocated target registers. The CFG includes relative execution frequencies of each block in the CFG. The execution frequencies can be generated by monitoring previous executions of the function or estimated prior to executing the function. The TRA system also inputs loop definition data 503 of the loops of the CFG which identifies each block that is the last block in a loop and each block that is a preheader block of a loop. The TRA system also inputs dominator definition data 504 that identifies the immediate dominator of each block in the CFG. The TRA system generates and outputs the target definitions data 506 for the CFG, which includes each target definition along with its assigned target register location and each branch with its assigned target register.

FIG. 6 is a block diagram illustrating data structures used by the TRA system in one embodiment. The last defined ("last_def") array 601 contains an entry for each target register. Each entry points to a linked list of family data structures 602 representing families that are assigned to that target register. Each family data structure contains a list of live range data structures 603 representing the live ranges that are in that family. The family data structures are linked based on their order of creation, that is, the first family data structure represents the family most recently created. The TRA system also maintains a dominator list ("dom_list") array 604 that contains an entry for each block in the CFG. Each entry is used to keep track of live ranges that the block dominates. When the TRA system encounters a block, it extends the live ranges in the dominator list to include the encountered block. Tables 1 and 2 contain a description of the live range and family data structures. Tables 3 and 4 contain a description of other data structures, variables, and constants used by the TRA system.

                             TABLE 1
                           LIVE RANGES
        Field                  Description
        target definition ("d") target definition for this live range
        first_op               first operation in the range of
                               operations that include all
                               operations in "branches"
        last_op                last operation in the range of
                               operations that include all
                               operations in "branches"
        target                 target block for this live range; a
                               target can also be a called function,
                               a function return point, or a
                               computed location of a "switch"
                               statement
        branches               set of all branches in this live
                               range that use the target register
        family                 pointer to the family that includes
                               this live range


                         TABLE 2
                              FAMILY
    Field                Description
    next                 pointer to the next family that is assigned to
                         the same target register
    ranges               list of pointers to the live ranges within this
                         family
    target               target block for this family of live ranges
    target register ("tr") target register assigned to this family
    cost                 sum of execution frequencies of all blocks
                         which contain target definitions for the live
                         ranges in this family
    limit                target register for this family must be less
                         than or equal to this value because of the
                         callee save registers of functions called
                         within the live ranges of the family
    physical             indicates that this family can only use target
                         register tr (e.g., a live range for the return of
                         a call is bound to the return register)
    avail                indicates earliest location where the target
                         definition may be placed for computed
                         branches; computed branches include jump
                         tables and indirect calls; a target definition
                         cannot be placed before the operation that
                         sets the index for the indirect call or that
                         sets the address variable for an indirect call
    last(f)              computed value that is the largest value of a
                         last field for all live ranges in family ("f")
    first(f)             computed value that is the smallest value of
                         a last field for all live ranges in family ("f")


                         TABLE 3
                      VARIABLE DESCRIPTIONS
    Name                     Descriptions
    loc(x)                   number assigned to operation "x" based on
                             the ordering of the blocks and operations
                             within the blocks
    block_last_op (block)    number assigned to last operation in the
                             block
    dom(block)               the ordered immediate dominator of the
                             block; the ordered immediate dominator is
                             the highest numbered block (with a num-
                             ber smaller than the block) such that all
                             paths of execution from the start block
                             through the block include the dominator
    freq(b)                  execution frequency of block "b" or of the
                             block that contains operation "b"
    dom_list(block)          set of live ranges such that that the block
                             is the dominator of the blocks currently
                             containing the target definitions of the live
                             ranges
    loop_depth               current depth of a loop
    call_limit (loop_depth)  minimum callee save register of all
                             functions called in the loop at loop depth
    loop_last_op (loop_depth) last operation in the loop at that loop depth


                         TABLE 3
                      VARIABLE DESCRIPTIONS
    Name                     Descriptions
    loc(x)                   number assigned to operation "x" based on
                             the ordering of the blocks and operations
                             within the blocks
    block_last_op (block)    number assigned to last operation in the
                             block
    dom(block)               the ordered immediate dominator of the
                             block; the ordered immediate dominator is
                             the highest numbered block (with a num-
                             ber smaller than the block) such that all
                             paths of execution from the start block
                             through the block include the dominator
    freq(b)                  execution frequency of block "b" or of the
                             block that contains operation "b"
    dom_list(block)          set of live ranges such that that the block
                             is the dominator of the blocks currently
                             containing the target definitions of the live
                             ranges
    loop_depth               current depth of a loop
    call_limit (loop_depth)  minimum callee save register of all
                             functions called in the loop at loop depth
    loop_last_op (loop_depth) last operation in the loop at that loop depth

                             TABLE 5
                           PSEUDO CODE
    Pseudo Code         Frequency    Dom   Target Requirements
    B1:   S1                 1.0      N/A
          do{
    B2a:  S2                 8.0       1    call/call return
          call f;
    B2b:  S3
          while( )
    B3:   S4                 1.0       2    branch to B6
          if( )then
    B4:   S5                 0.5       3    branch to B8
          if( )goto B8;
    B5:   S6                 0.25      4
          endif
    B6:   S7                 0.75      3    branch to B8
          if( )then
    B7:   S8                 0.375     6
          endif
    B8:   S9                 1.0       3

                             TABLE 6
                           LIVE RANGES
        Name    Branches     Target     Physical?     Family
        lr1        b6          B8          no            1
        lr2        b5          B8          no            1
        lr3        b3          B6          no            2
        lr4        b2          B2a         no            3
        lr5     call ret       B2b       yes(1)          4
        lr6       call          f          no            5

                                   TABLE 7
                       ACTION OF THE ALGORITHM ASSUMING
                     NUM_CALLEE_SAVE = 2 AND MAX_LIVE = 3
    Block Action
    8     no action
    7     no action
    6     create live range lr1 and family f1
              f1.tr = 3
              active={f1}
              dom_list(3) = {lr1}
    5     no action
    4     create live range lr2 and add to existing family f1
              f1.ranges = {lr1,lr2}
              active={f1}
              dom_list(3) = {lr1,lr2}
    3     create live range lr3 and family f2
              f2.tr = 2
              active = {f1,f2}
              dom_list(2) = {lr3}
              coalesce live ranges in dom_list(3):
                  cost of b3 = 1, total cost of {lr1,lr2} is 1.25
                  so move definition of lr1 to block 3
              remove definition of lr2 and remove lr2 from f1
              lr1.branches = {b6,b4}
              dom_list(2) = {lr1,lr3}
    2     start a new loop
                  loop_depth = 1
                  loop_last(1) = end of block 2
                  call_limit(1) = MAX_LIVE
              create a live range lr4 and family f3
              f3.tr = 1
              active = {f1,f2,f3}
              dom_list(1) = { lr4 }
              no coalescing since the cost of block 2 is 8
                  dom_list(1) = {lr1,lr3,lr4}
              create a live range lr5 and family f4 for call return. The return
          address register needs to be made available. The cheapest element of
     the
          active set is removed. f1 and f2 have equal cost, assume f1 is
     removed.
                  Family f3 is moved to target 3 and
                      f3.next = f1
                  f4.tr = 1
                  f4.physical = yes
                  active = {f2,f3,f4}
                  dom_list(1) = {lr1,lr3,lr4,lr5}
              callee-save requirement is enforced
              Consider families f4,f3,f2 in that order.
                      F4 (in 1) is already in a callee. (f4.limit = 2)
                         f3 (in 3) is not and has higher cost than f2 so
                             remove f2 from the active set and move f3 to
     target
          register 2. (f3.tr=2, f3.limit=2)
                  active={f3,f4}
                  call_limit(1) = 2 /* for inner loop */
              create a live range lr6 and family f5 for the call to
                  function f.
              f5.tr = 3
              active = {f3,f4,f5}
              dom_list(1) = {lr1,lr3,lr4,lr5,lr6}
    1     a loop header: attempt to extend all active live
              ranges to include the entire loop. In cost order, consider
     families
          f5,f4,f3. There are no target registers available in the range of
          1..call_limit(1)=2 so remove family 5 from the active set. Both
     families
          3 and 4 can be extended to the entire loop. lr4.last = last(1)
     lr5.last =
          last(1)
                  loop_depth = 0
                  active = {f3,f4}
                  attempt to coalesce. only live ranges lr4 and lr5
                      are still active and both have cost greater than the
     current
          block so the definitions of these live ranges are moved into block 1.

                             TABLE 8
                          REGISTERS USED
              Pseudo Code              Target Definition
              B1:   S1
                    tr1 = B2b
                    tr2 = B2a
                    do {
              B2a:  S2
                    tr3 = f
                    call f                  tr3, tr1
              B2b:  S3
                    while( )                  tr2
              B3:   S4
                    tr3 = B8
                    tr2 = B6
                    if( ) then                tr2
              B4:   S5
                    if( ) goto B8;               tr3
              B5:   S6
                    endif
              B6:   S7
                    if( ) then                tr3
                    tr3
              B7:   S8
                    endif
              B8    S9

• Inventors
  Callahan, II, Charles David;
• Assignee
  Cray Inc. (Seattle, WA)
• Published
  Nov-20-2001
• Current US Classes:
  717/141
• Application #
  221287
• International Classes
  G06F 009/45
• Field of Search
  717/2 717/3 717/4 717/5 717/6 717/7 717/8 717/9
• Examiner
  Chaki; Kakali
• Agent
  Perkins Coie LLP
• US Patent References:
  4819234
  4872167
  5168554
  5504932
  5533192
  5557761
  5594864
  5632032
  5712996
  5754855
  5768591
  5774721
  5787245
  5805892
  5812811
  5867643
  5877766
  5887166
  5901315
  5903730
  5913925
  5953530
  5961639
  5978902
  6002872
  6009269
  6058493
  6059840
  6072952
  6094716
  6101524
  6112293
  6151701