Method for identifying partial redundancies in a new processor architecture

• US 6,029,005 A
• Filed: 04/01/1997
• Issued: 02/22/2000
• 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): Hafiz, Tara R.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/829,933
• Time in Patent Office: 1,057 Days
• Field of Search: 395/705, 395/706, 395/707, 395/708, 395/709
• US Class Current: 717/158
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

The invention, in one embodiment, is a method for compiling at least a portion of a computer program. The method includes (a) inserting a phi-function for a global variable reaching a join point in the intermediate language representation subsequent to the join point without regard to the presence of ambiguity; (b) renaming a definition and any subsequent use of the definition in the intermediate language representation; and (c) identifying a partially redundant load by determining whether any of the operands of the inserted phi-function have not been renamed.

Claims

1. A method for compiling at least a portion of a computer program, the method comprising:

(a) inserting a phi-function for a global variable reaching a join point in an intermediate language representation subsequent to the join point even in the presence of ambiguity;

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

(c) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

2. The method of claim 1, wherein the acts (a)-(b) are repeated at least once before identifying the partially redundant load.

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

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

5. The method of claim 4, wherein the identified partial redundancy is eliminated by inserting:

(1) an advanced load preceding the join point along an unbalanced flow control path of the operands in the phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

6. The method of claim 1, wherein a plurality of phi-functions is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

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

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

8. The method of claim 1, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

9. The method of claim 1, further comprising generating machine readable code.

10. A program storage device encoding statements for compiling at least a portion of a computer program, the statements defining a method comprising:

(a) inserting a phi-function for a global variable reaching a join point in an intermediate language representation subsequent to the join point even in the presence of ambiguity;

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

(c) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

11. The device of claim 10, wherein the acts (a)-(b) are repeated at least once before identifying the partially redundant load.

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

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

14. The device of claim 13, wherein the identified partial redundancy is eliminated by inserting:

(1) an advanced load preceding the join point along an unbalanced flow control path of the operands in the phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

15. The device of claim 10, wherein a plurality of phi-functions is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

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

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

17. The device of claim 10, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

18. The device of claim 10, further comprising generating machine readable code.

19. A method for compiling at least a portion of a computer program, wherein a phi-function having a plurality of operands has been inserted for a global variable reaching a join point subsequent to the join point and a definition and any subsequent use thereof has been renamed, the method comprising:

(a) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand;

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

(c) inserting a load check prior to each use of the unregisterized operand subsequent to the advanced load.

20. The method of claim 19, further comprising eliminating a second identified partially redundant load by at least one of the following:

(1) inserting an artificial load preceding the 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 a dominance relationship of the operands in the one phi-function.

21. The method of claim 19, wherein a plurality of phi-nodes is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

22. The method of claim 19, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

23. The method of claim 19, further comprising generating machine readable code.

24. A program storage device encoding statements for compiling at least a portion of a computer program, wherein a phi-function having a plurality of operands has been inserted for a global variable reaching a join point subsequent to the join point and a definition and any subsequent use thereof has been renamed, the method comprising:

(a) identifying a partially redundant load by determining whether the inserted phi-function contains an unregisterized operand;

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

(c) inserting a load check prior to each use of the unregisterized operand subsequent to the advanced load.

25. The method of claim 24, further comprising eliminating a second identified partially redundant load by at least one of the following:

(1) inserting an artificial load preceding the 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 a dominance relationship of the operands in the one phi-function.

26. The method of claim 24, wherein a plurality of phi-nodes is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

27. The method of claim 24, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

28. The method of claim 24, further comprising generating machine readable code.

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

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

29. A method for compiling at least a portion of a computer program, the method comprising:

(a) determining a flow of control along an 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 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 even in the presence of ambiguity;

(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 any operands of the inserted phi-function have not been renamed.

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

33. The method of claim 32, wherein the identified partial redundancy is eliminated by inserting:

(1) an advanced load preceding a join point reached by the global variable along an unbalanced flow control path of the operands in the phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

34. The method of claim 29, 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.

35. The method of claim 29, 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 an iterative dominance frontier for each instruction.

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

37. The method of claim 29, wherein renaming the definition and any subsequent uses of the definition includes:

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

38. The method of claim 29, wherein instructions are partitioned into basic blocks.

39. The method of claim 29, further comprising generating machine readable code.

40. A program storage device encoding statements for compiling at least a portion of a computer program, the statements defining a method comprising:

(a) determining a flow of control along an 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 even in the presence of ambiguity;

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

(f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed.

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

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

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

44. The device of claim 43, wherein the partial redundancy is eliminated by inserting:

(1) an advanced load preceding a join point reached by the global variable along an unbalanced flow control path of the operands in the phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

45. The device of claim 40, 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.

46. The device of claim 40, 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 an iterative dominance frontier for each instruction.

47. The device of claim 40, wherein a plurality of phi-functions is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

48. The apparatus of claim 40, wherein renaming the definition and any subsequent uses of the definition includes:

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

49. The apparatus of claim 40, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

50. The apparatus of claim 40, further comprising generating machine readable code.

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

(a) determining a flow of control along an 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 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 only subsequent use of the definition in the intermediate language representation;

(f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed; and

(g) eliminating the partial redundancy of the identified partially redundant load by inserting;

(1) an advanced load preceding a join point along an unbalanced flow control path of the operands in the inserted phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

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

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

54. The method of claim 51, further comprising eliminating a second identified partially redundancy load by at least one of the following:

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

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

55. The method of claim 51, 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.

56. The method of claim 51, 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 an iterative dominance frontier for each instruction.

57. The method of claim 51, wherein a plurality of phi-nodes is inserted and the method further comprises maintaining a linked list of inserted phi-function locations.

58. The method of claim 51, wherein renaming the definitions and any subsequent use of the definition includes:

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

59. The method of claim 51, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

60. The method of claim 51, further comprising generating machine readable code.

61. A program storage device encoding statements for compiling at least a portion of a computer program into machine readable object code, the statements defining a method comprising:

(a) determining a flow of control along an 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 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 uses of the definition in the intermediate language representation;

(f) identifying a partially redundant load by determining whether any operands of the inserted phi-function have not been renamed; and

(g) eliminating the partial redundancy of the identified partially redundant load by inserting;

(1) an advanced load preceding the join point along an unbalanced flow control path of the operands in the inserted phi-function; and

(2) a load check prior to each use of the operand not renamed subsequent to the advanced load.

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

63. The method of claim 61, wherein a second partial redundancy from a second identified partially redundant load is eliminated by at least one of the following:

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

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

64. The method of claim 61, wherein the act of 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.

65. The method of claim 61, wherein the act of 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 an iterative dominance frontier for each instruction.

66. The method of claim 61, wherein a plurality of phi-nodes is inserted and the method further comprises includes maintaining a linked list of inserted phi-function locations.

67. The method of claim 61, wherein renaming the definition and any subsequent use of the definition includes:

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

(2) assigning temp values to each rank-0 expression encountered during the traversal.

68. The method of claim 61, wherein a plurality of instructions comprising the portion of the computer program is partitioned into basic blocks.

69. The method of claim 61, further comprising generating machine readable code.

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

(a) determining a flow of control along each execution path through an intermediate language representation, including constructing at least one of a flow control graph and a dominator-join graph;

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

(1) constructing at least one of a dominator tree and a dominator-join graph; and

(2) calculating an iterative dominance frontier for each instruction,

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

(d) inserting a phi-function for each global variable reaching a join point in the intermediate language representation as indicated by the dominance relationship even in the presence of ambiguity, including maintaining a linked list of a plurality of inserted phi-function locations;

(e) renaming a definition and subsequent uses thereof in the intermediate language representation, the renaming including;

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

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

(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 the inserted phi-function contains an unregisterized operand;

(h) eliminating the identified partial redundancy by inserting;

(1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and

(2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load; and

(i) generating machine readable code.

71. 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, including;

(1) constructing at least one of the following;

(A) a flow control graph; and

(B) a dominator-join graph;

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

(1) constructing at least one of the following;

(A) a dominator tree; and

(B) a dominator-join graph; and

(2) calculating an iterative dominance frontier for each instruction,

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

(d) inserting a phi-function for each 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 definitions in the intermediate language representation, the renaming including;

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

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

(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 partial redundancy by determining whether an inserted phi-function contains an unregisterized operand;

(h) eliminating the identified partial redundancy by inserting;

(1) an advanced load into a basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregisterized operand; and

(2) a load check immediately prior to each use of the unregisterized operand subsequent to the advanced load;

(i) eliminating a second identified partial redundancy by at least one of the following;

(1) inserting an artificial load into the basic block immediately preceding the join point along the unbalanced flow control path of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and

(2) moving the second identified partially redundant load to a nearest common ancestor in the dominance relationship of the operands in at least one phi-function containing the unregistered operand after identifying the partial redundancy; and

(j) generating machine readable code.