Method for identifying partial redundancies in existing processor architectures

• US 5,991,540 A
• Filed: 04/01/1997
• Issued: 11/23/1999
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Radigan, Jim J.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): SMITH-STEWART, DEMETRA R
• Application Number:
  US08/829,847
• Time in Patent Office: 966 Days
• Field of Search: 395/706, 395/707, 395/709, 395/705, 264/280.4, 264/280.5
• US Class Current: 717/158
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

The invention in one embodiment is a method for identifying partially redundant loads in an SSA intermediate language representation of at least a portion of a computer program. The intermediate language representation in this embodiment includes an inserted phi-function and the definitions and their uses have been renamed. The method includes identifying a partially redundant load by determining whether one of the operands in the inserted phi-function is unregisterized.

Claims

1. A method for identifying partially redundant loads in an SSA intermediate language representation of at least a portion of a computer program, the intermediate language representation having an inserted phi-function and wherein the definitions and their uses have been renamed, the method comprising identifying a partially redundant load by determining whether one of the operands in the inserted phi-function is unregisterized.

2. The method of claim 1, wherein the SSA intermediate language representation is a rank-n SSA intermediate language representation, where n is greater than 1.

3. The method of claim 1, further comprising eliminating the identified partial redundancy.

4. The method of claim 3, wherein the partial redundancy is eliminated by at least one of:

(a) inserting an artificial load immediately preceding a join point in a flow of control through the intermediate language representation along an unbalanced flow control path of an operands in the phi-function; and

(b) moving the partially redundant load to a nearest common ancestor in a dominance relationship of the operands in the phi-function.

5. The method of claim 1, further comprising at least one of the following:

(a) coloring out artificial register dependencies; and

(b) generating machine readable code.

6. A program storage device readable by a general purpose computer, the program storage device encoding statements for identifying a partially redundant load in an SSA intermediate language representation of at least a portion of a computer program, the intermediate language representation having an inserted phi-function and wherein the definitions and their uses have been renamed, the statements defining a method comprising identifying a partially redundant load by determining whether one of the operands in the inserted phi-function is unregisterized.

7. The method of claim 6, wherein the SSA intermediate language representation is a rank-n SSA intermediate language representation, where n is greater than 1.

8. The method of claim 6, further comprising eliminating the identified partial redundancy.

9. The method of claim 8, wherein the partial redundancy is eliminated by at least one of:

(a) inserting an artificial load immediately preceding a join point in a flow of control through the intermediate language representation along an unbalanced flow control path of an operands in the phi-function; and

(b) moving the partially redundant load to a nearest common ancestor in a dominance relationship of the operands in the phi-function.

10. The method of claim 6, further comprising at least one of the following:

(a) coloring out artificial register dependencies; and

(b) generating machine readable code.

11. A method for compiling at least a portion of a computer program into machine readable code, the method comprising:

(a) determining a flow of control along each execution path through an intermediate language representation of the portion of the computer program;

(b) ascertaining a dominance relationship from the flow of control;

(c) identifying an unambiguous global variable in the intermediate language representation reaching a join point;

(d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation subsequent to the join point as indicated by the dominance relationship;

(e) renaming a definition and any subsequent use of the definition in the intermediate language representation; and

(f) identifying a partially redundant load by determining whether one of the operands in the inserted phi-function is not renamed.

12. The method of claim 11, wherein the acts (b)-(e) are repeated at least once before identifying the partially redundant load.

13. The method of claim 12, wherein the acts (b)-(e) are repeated until all complex definitions and their uses have been accommodated.

14. The method of claim 11, further comprising eliminating the partial redundancy of the identified partially redundant load.

15. The method of claim 14, wherein the partial redundancy is eliminated by at least one of the following:

(a) inserting an artificial load immediately preceding a join point in the flow of control along an unbalanced flow control path of the operands the phi-function; and

(b) moving the partially redundant load to a nearest common ancestor in the dominance relationship of the operands in the phi-function.

16. The method of claim 11, wherein determining the flow of control includes at least one of the following:

(1) constructing a flow control graph; and

(2) constructing a dominator-join graph.

17. The method of claim 11, wherein ascertaining the dominance relationship includes at least one of the following:

(1) constructing a dominator tree;

(2) constructing a dominator-join graph; and

(3) calculating the iterative dominance frontier for each instruction.

18. The method of claim 11, wherein a plurality of phi functions are inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

19. The method of claim 11, wherein the act of renaming definitions includes at least one of the following:

(a) performing a depth-first ordered traversal of the intermediate language representation; and

(b) assigning temp values to each rank-0 expression.

20. The method of claim 11, wherein the instructions are partitioned into basic blocks.

21. The method of claim 11, further comprising generating machine readable code.

22. A program storage device readable by a general purpose computer, the program storage device encoding statements for compiling at least a portion of high-level source code into machine readable object code, the statements defining a method comprising:

(a) determining a flow of control along each execution path through an intermediate language representation of the portion of the computer program;

(b) ascertaining a dominance relationship from the flow of control;

(c) identifying a global variable in the intermediate language representation;

(d) inserting a phi-function having a plurality of operands for the global variable in the intermediate language representation as indicated by the dominance relationship;

(e) renaming a definition and any subsequent use of the definition in the intermediate language representation; and

(f) identifying a partially redundant load by determining whether one of the operands in the inserted phi-function is not renamed.

23. The device of claim 22, wherein the acts (b)-(e) are repeated at least once before identifying the partially redundant load.

24. The device of claim 23, wherein the acts (b)-(e) are repeated until all complex definitions and their uses have been accommodated.

25. The device of claim 22, further comprising eliminating the partial redundancy of the identified partially redundant load.

26. The device of claim 25, wherein the partial redundancy is eliminated by at least one of the following:

(a) inserting an artificial load immediately preceding a join point in the flow of control along an unbalanced flow control path of the operands the phi-function; and

(b) moving the partially redundant load to the nearest common ancestor in the dominance relationship of the operands in the phi-function.

27. The device of claim 22, wherein determining the flow of control includes at least one of the following:

(1) constructing a flow control graph; and

(2) constructing a dominator-join graph.

28. The device of claim 22, wherein ascertaining the dominance relationship includes at least one of the following:

(1) constructing a dominator tree;

(2) constructing a dominator-join graph; and

(3) calculating the iterative dominance frontier for each instruction.

29. The device of claim 22, wherein a plurality of phi-functions are inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

30. The device of claim 22, wherein the act of renaming definitions includes at least one of the following:

(a) performing a depth-first ordered traversal of the intermediate language representation;

(b) assigning temp values to each rank-0 expression; and

(c) eliminating loop invariant motion; and

(d) eliminating common subexpressions.

31. The device of claim 22, wherein a plurality of instructions comprising the portion of the computer program are partitioned into basic blocks.

32. The device of claim 22, further comprising generating machine readable code.

33. A method for compiling at least a portion of high-level source code into machine readable object code, the method comprising:

(a) determining a flow of control along each execution path through an intermediate language representation of the source code, including at least one of the following;

(1) constructing a flow control graph; and

(2) constructing a dominator-join graph;

(b) ascertaining a dominance relationship from the flow of control, including at least one of the following;

(1) constructing a dominator tree;

(2) constructing a dominator-join graph; and

(3) calculating the iterative dominance frontier for each instruction;

(c) identifying a global variable in the intermediate language representation;

(d) inserting a phi-function for the global variable in the intermediate language representation as indicated by the dominance relationship, including maintaining a linked list of inserted phi-function locations;

(e) renaming a definition and any subsequent use of the definition in the intermediate language representation, the renaming including at least one of;

(1) performing a depth-first ordered traversal of the intermediate language representation;

(2) assigning temp values to each rank-n expression;

(3) eliminating loop invariant motion; and

(4) eliminating common subexpressions;

(f) repeating acts (b)-(e) at least once to create a rank-n SSA intermediate language where n is a positive integer greater than zero;

(g) identifying a partially redundant load by determining whether an inserted phi-function contains an operand that has not been renamed; and

(h) eliminating the identified partial redundancy by doing at least one of the following;

(1) inserting an artificial load into a basic block immediately preceding a join point along an unbalanced flow control path of the operands in the phi-function; and

(2) moving the partially redundant load to a nearest common ancestor in the dominance relationship of the operands in the phi-function;

(i) coloring out artificial register dependencies; and

(j) generating machine readable code.