Method for using static single assignment to color out artificial register dependencies

• US 6,016,398 A
• Filed: 04/01/1997
• Issued: 01/18/2000
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Radigan, Jim J.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/831,739
• Time in Patent Office: 1,022 Days
• Field of Search: 395/707, 395/709
• US Class Current: 717/152
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

The invention is a method of using static single assignment intermediate language to color out artificial register dependencies while compiling at least a portion of a computer program. The method comprises creating a rank-n SSA intermediate language representation of the computer program, wherein n is a positive integer greater than 1; and coloring out the artificial register dependencies.

Claims

1. A method of using static single assignment to color out artificial register dependencies while compiling at least a portion of a computer program, the method comprising:

creating a rank-n SSA intermediate language representation of the computer program, wherein n is a positive integer greater than 0, to assign a unique name to each symbolic expression;

mapping the symbolic expression into a table;

determining from the table which renamed elements from the intermediate language expression have symbolic expressions that are equivalent, by utilizing a hash function; and

coloring out an artificial register dependency based on equivalent symbolic expressions.

2. The method of claim 1, wherein creating a rank-n SSA intermediate language representation further comprises:

(a) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use; and

(b) renaming the rank-n definition and the at least one use.

3. The method of claim 2 further comprising:

(c) repeating acts (a) and (b) until all rank-n definitions that reach at least one use are renamed.

4. The method of claim 2, wherein the rank-(n-1) static single assignment intermediate language includes a plurality of statement nodes and a plurality of expression nodes.

5. The method of claim 2, wherein searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-0 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

6. The method of claim 2, wherein searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-1 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

7. The method of claim 1, wherein creating a rank-n SSA intermediate language representation further comprises:

(a) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use;

(b) renaming the rank-n definition and the at least one use, and (c) repeating acts (a) and (b) until all rank-1 definitions that reach at least one use are renamed; and

wherein;

(d) the rank-(n-1) static single assignment intermediate language includes a plurality of statement nodes and a plurality of expression nodes; and

(e) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-0 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

8. The method of claim 1, wherein the determination of whether two symbolic expressions are equivalent further includes utilizing a definition function and an equivalency function.

9. The method of claim 8, wherein the hash function retrieves a value number for any given symbolic expression.

10. The method of claim 8, wherein the definition function returns a definition number for any given expression.

11. The method of claim 8, wherein the equivalency function indicates whether any two symbolic expressions are equal.

12. A program storage device readable by a general purpose computer, the program storage device encoding statements for a method of using static single assignment to color out artificial register dependencies while compiling at least a portion of a computer program, the method comprising:

creating a rank-n SSA intermediate language representation of the computer program, wherein n is a positive integer greater than 0, to assign a unique name to each symbolic expression;

mapping the symbolic expression into a table;

determining from the table which renamed elements from the intermediate language expression have symbolic expressions that are equivalent, by utilizing a hash function; and

coloring out an artificial register dependency based on equivalent symbolic expressions.

13. The device of claim 12, wherein creating a rank-n SSA intermediate language representation further comprises:

(a) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use; and

(b) renaming the rank-n definition and the at least one use.

14. The device of claim 13, further comprising:

(c) repeating acts (a) and (b) until all rank-n definitions that reach at least one use are renamed.

15. The device of claim 13, wherein the rank-(n-1) static single assignment intermediate language includes a plurality of statement nodes and a plurality of expression nodes.

16. The device of claim 13, wherein searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-0 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

17. The device of claim 13, wherein searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-1 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

18. The device of claim 12, wherein creating a rank-n SSA intermediate language representation further comprises:

(a) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use;

(b) renaming the rank-n definition and the at least one use, and

(c) repeating acts (a) and (b) until all rank-1 definitions that reach at least one use are renamed; and

wherein;

(d) the rank-(n-1) static single assignment intermediate language includes a plurality of statement nodes and a plurality of expression nodes; and

(e) searching the rank-(n-1) static single assignment intermediate language for a rank-n definition that reaches at least one use includes searching a rank-0 static single assignment intermediate language for a rank-1 definition that reaches at least one use.

19. The device of claim 12, wherein the determination of whether two symbolic expressions are equivalent further includes utilizing a definition function and an equivalency function.

20. The device of claim 19, wherein the hash function retrieves a value number for any given symbolic expression.

21. The device of claim 19, wherein the definition function returns a definition number for any given expression.

22. The device of claim 19, wherein the equivalency function indicates whether any two symbolic expressions are equal.