Method and system for target register allocation

• US 6,321,379 B1
• Filed: 12/23/1998
• Issued: 11/20/2001
• Est. Priority Date: 12/23/1998
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Callahan, Charles David II
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Vo, Ted T.
• Application Number:
  US09/221,287
• Time in Patent Office: 1,063 Days
• Field of Search: 717/2, 717/3, 717/4, 717/5, 717/6, 717/7, 717/8, 717/9
• US Class Current: 717/141
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06Q 20/363 with the personal data of a user
• CPC Class Codes: G07F 7/0866 by active credit-cards adapted therefor G07F7/1008 takes precedence

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

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.