Method and system for identifying locations to move portions of the computer program

• US 6,415,433 B1
• Filed: 12/23/1998
• Issued: 07/02/2002
• 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: Koblenz, Brian D., Callahan, Charles David II
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/221,031
• Time in Patent Office: 1,287 Days
• Field of Search: 717/9, 717/7, 717/8, 717/4, 712/241, 707/527
• US Class Current: 717/160
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method system for optimizing a computer program. In one embodiment, the system identifies depths of blocks of a computer program and identifies the availability of expressions of the computer program. The system then modifies the computer program when he identified availability of the expression and the identified depth of a block indicate that the expression can be moved to the block. The depth of the block may represent the number of dominator blocks of that block. The availability of the expression may represent the depth of a block to which the expression may be moved. In one embodiment, when the identified availability of the expression is less than the identified depth of the block, the expression can be moved to the block.

Claims

1. A method in a computer system for optimizing a computer program, the method comprising:

identifying a depth of a block of the computer program;

identifying an availability of an expression of the computer program; and

modifying the computer program when the identified availability of the expression and the identified depth of the block indicate that the expression can be moved to the block.

2. The method of claim 1 wherein the depth of the block represents a number of dominator blocks of the block.

3. The method of claim 1 wherein the depth of the block represents a level of the block within a dominator tree representation of the computer program.

4. The method of claim 1 wherein the availability of the expression represents the depth of a block to which the expression may be moved.

5. The method of claim 4 wherein the expression may need to be re-written when moved.

6. The method of claim 1 including identifying a depth of the expression of the computer program, the depth of the expression indicating a block to which the expression can be moved without modification.

7. The method of claim 1 wherein the block dominates the expression.

8. The method of claim 1 wherein the identifying of the availability of the expression includes setting the availability of the expression to a maximum of depths of operands of the expression.

9. The method of claim 1 wherein the identifying of the availability of the expression includes when an operation of the expression is a load from memory, setting the availability of the expression to a maximum of depths of operands of the expression and an availability of a reaching definition of the expression.

10. The method of claim 9 wherein the reaching definition is a merge of a scalar loaded by the expression.

11. The method of claim 9 wherein the reaching definition is a store of a value and a value number of the reaching definition is the same as a value number of the expression.

12. The method of claim 1 wherein the identifying of the availability of the expression includes when an operation of the expression is a load from memory, setting the availability of the expression to a maximum of depths of operands of the expression and a depth of a parent block that contains a reaching definition of the expression.

13. The method of claim 12 wherein the reaching definition is neither a merge of a scalar loaded by the expression nor a store of a value such that a value number of the reaching definition is the same as a value number of the expression.

14. The method of claim 1 wherein the identifying of the availability of the expression includes when an operation of the expression is a store into memory, setting the availability of the expression to a depth of a parent block that contains the expression.

15. The method of claim 1 wherein the identifying of the availability of the expression includes when an operation of the expression is a merge of a scalar, setting the availability of the expression to a minimum of the availabilities of reaching definitions of the expression for reaching definitions whose value number is the same as a value number for the expression and a parent block that contains the reaching definition precedes a parent block that contains the expression.

16. The method of claim 1 wherein the identifying of the availability of the expression is performed while visiting blocks of the computer program during a forward traversal of a control flow graph representation of the computer program.

17. The method of claim 1 including identifying a depth of the expression and when the identified depth of the expression and the identified depth of the block indicate that the expression can be moved to the block, moving the expression to the block.

18. The method of claim 17 wherein the moving of the expression includes when the depth of the expression is not greater than the depth of the block, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

19. The method of claim 17 wherein the moving of the expression includes when the depth of the expression is greater than the depth of the block, moving inputs to the expression, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

20. The method of claim 19 wherein when the expression is not a memory reference moving to the block each operand of the expression whose depth is greater than the depth of the block.

21. The method of claim 19 wherein when the expression is a memory reference and a reaching definition of the expression is either a merge of a scalar loaded by the expression or a store of a value such that a value number of the reaching definition is the same as a value number of the expression, substituting a reaching definition for a current reaching definition of the expression.

22. The method of claim 21 wherein the substituting of the reaching definition includes selecting as a substitute reaching definition the first reaching definition in a chain of reaching definitions whose depth is less than or equal to the depth of the block or whose operation is not a merge.

23. The method of claim 22 including when the operation of the substitute reaching definition is not a merge, setting the reaching definition to be a store of an expression whose value number is the same as that of the expression, moving inputs of that store expression to the parent block that contains the substitute reaching definition, and replacing the expression with a load of a variable store by the reaching definition.

24. The method of claim 17 wherein the depth of the expression and the depth of the block indicate that the expression can be moved to the block when the depth of the expression is less than or equal to the depth of the block and the block dominates the expression.

25. The method of claim 17 wherein the identifying of the depth of the expression includes setting the depth of the expression to a maximum of depths of operands of the expression.

26. The method of claim 17 wherein the identifying of the depth of the expression includes when an operation of the expression is a load from memory, setting the depth of the expression to a maximum of depths of operands of the expression and depth of a reaching definition of the expression.

27. The method of claim 17 wherein the identifying of the depth of the expression includes when an operation of the expression is a store into memory, setting the depth of the expression to a depth of a parent block that contains the expression.

28. The method of claim 17 wherein the identifying of the depth of the expression is performed while visiting blocks of the computer program during a forward traversal of a control flow graph representation of the computer program.

29. A method in a computer system for optimizing a computer program, the method comprising:

identifying a depth of a block of the computer program;

identifying an availability of an expression of the computer program; and

modifying the computer program when the identified availability of the expression and the identified depth of the block indicate that the expression can be moved to the block wherein the identified availability of the expression and the identified depth of the block indicate that the expression can be moved to the block when the identified availability of the expression is less than or equal to the identified depth of the block.

40. The computer system of claim 29 wherein the reaching definition is a merge of a scalar loaded by the expression.

30. A method in a computer system for determining availability of expressions of a computer program, the method comprising:

for blocks visited during a forward traversal of a control flow graph representation of the computer program,

for expressions of the block,

setting the availability of expression to the latest availability of its operands, and

when the operation of the expression is a load from memory, setting the availability of the expression based on a reaching definition of the load.

31. The method of claim 30 including storing the set availability of each expression along with a representation of the computer program.

32. The method of claim 30 wherein the setting of the availability of the expression based on the reaching definition includes setting the availability of the expression to the availability of the reaching definition when the reaching definition is a store of the result of an expression with the same value as the value of the expression.

33. The method of claim 30 wherein the setting of the availability of the expression based on the reaching definition includes setting the availability of the expression to the availability of the reaching definition when the reaching definition is a merge of a scalar loaded by the expression.

34. The method of claim 30 wherein the setting of the availability of the expression based on the reaching definition includes setting the availability of the expression to the later of the availability of all the operands of the expression and of the block of the reaching expression.

35. The method of claim 30 including when the operation of the expression represents a merge of a scalar, setting the availability of the expression to the earlier of the availability of all the operands of the expression and of the earliest availability of the reaching definitions that store the same value as the result of the expression.

36. The method of claim 30 wherein a representation of the expression can be moved to a block whose dominator depth is after the availability.

37. A method in a computer system for identifying a direct dominator of a block of a computer program, the method comprising:

identifying the closest dominator of the block such that the block is contained in the innermost region containing that dominator; and

setting the direct dominator to the identified closest dominator.

38. A method in a computer system for identifying a direct dominator of a block of a computer program, the method comprising:

identifying the closest dominator of the block such that the block is contained in the innermost region containing that dominator by

selecting the closest dominator of the block;

selecting the least common region that contains the region that contains the block and the region that contains the selected dominator of the block; and

while the selected least common region is not the same as the innermost region of the selected dominator of the block,

selecting the next closest dominator of the block; and

selecting the least common region that contains the previously selected least common region and the region that contains the selected dominator of the block; and

setting the direct dominator to the identified closest dominator.

39. A computer system for identifying the availability of an expression in a computer program, the availability of the expression indicating a location within the computer program to which the expression can be moved with rewriting the expression, comprising:

a component for setting the availability of the expression to a maximum of depths of operands of the expression;

a component for, when an operation of the expression is a load from memory, setting the availability of the expression to a maximum of depths of operands of the expression and an availability of a reaching definition of the expression; and

a component for, when an operation of the expression is a store into memory, setting the availability of the expression to a depth of a parent block that contains the expression.

41. The computer system of claim 39 wherein the reaching definition is a store of a value and a value number of the reaching definition is the same as a value number of the expression.

42. The computer system of claim 39 wherein the reaching definition is neither a merge of a scalar loaded by the expression nor a store of a value such that a value number of the reaching definition is the same as a value number of the expression.

43. The computer system of claim 39 including a component for, when an operation of the expression is a merge of a scalar, setting the availability of the expression to a minimum of the availabilities of reaching definitions of the expression for reaching definitions whose value number is the same as a value number for the expression and a parent block that contains the reaching definition precedes a parent block that contains the expression.

44. The computer system of claim 39 wherein the identifying of the availability of the expression is performed while visiting blocks of the computer program during a forward traversal of a control flow graph representation of the computer program.

45. A computer-readable medium containing instructions for controlling a computer system to modify a computer program, by a method comprising:

identifying a depth of a block of the computer program;

identifying an availability of an expression of the computer program; and

when the identified availability of the expression and the identified depth of the block indicate that the expression can be moved to the block, moving a rewritten version of the expression to the block.

46. The computer-readable medium of claim 45 wherein the availability of the expression and the depth of the block indicate that the rewritten version of the expression can be moved to the block when the availability of the expression is less than or equal to the depth of the block and the block dominates the expression.

47. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression includes setting the availability of the expression to a maximum of depths of operands of the expression.

48. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression includes when an operation of the expression is a load from memory, setting the availability of the expression to a maximum of depths of operands of the expression and an availability of a reaching definition of the expression.

49. The computer-readable medium of claim 48 wherein the reaching definition is a merge of a scalar loaded by the expression.

50. The computer-readable medium of claim 48 wherein the reaching definition is a store of a value and a value number of the reaching definition is the same as a value number of the expression.

51. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression includes when an operation of the expression is a load from memory, setting the availability of the expression to a maximum of depths of operands of the expression and a depth of a parent block that contains a reaching definition of the expression.

52. The computer-readable medium of claim 51 wherein the reaching definition is neither a merge of a scalar loaded by the expression nor a store of a value such that a value number of the reaching definition is the same as a value number of the expression.

53. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression includes when an operation of the expression is a store into memory, setting the availability of the expression to a depth of a parent block that contains the expression.

54. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression includes when an operation of the expression is a merge of a scalar, setting the availability of the expression to a minimum of the availabilities of reaching definitions of the expression for reaching definitions whose value number is the same as a value number for the expression and a parent block that contains the reaching definition precedes a parent block that contains the expression.

55. The computer-readable medium of claim 45 wherein the identifying of the availability of the expression is performed while visiting blocks of the computer program during a forward traversal of a control flow graph representation of the computer program.

56. The computer-readable medium of claim 45 including identifying a depth of the expression and when the identified depth of the expression and the identified depth of the block indicate that the expression can be moved to the block, moving the expression to the block.

57. The computer-readable medium of claim 56 wherein the moving of the expression includes when the depth of the expression is not greater than the depth of the block, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

58. The computer-readable medium of claim 56 wherein the moving of the expression includes when the depth of the expression is greater than the depth of the block, moving inputs to the expression, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

59. The computer-readable medium of claim 58 wherein when the expression is not a memory reference moving to the block each operand of the expression whose depth is greater than the depth of the block.

60. The computer-readable medium of claim 58 wherein when the expression is a memory reference and a reaching definition of the expression is either a merge of a scalar loaded by the expression or a store of a value such that a value number of the reaching definition is the same as a value number of the expression, substituting a reaching definition for a current reaching definition of the expression.

61. The computer-readable medium of claim 60 wherein the substituting of the reaching definition includes selecting as a substitute reaching definition the first reaching definition in a chain of reaching definitions whose depth is less than or equal to the depth of the block or whose operation is not a merge.

62. The computer-readable medium of claim 61 including when the operation of the substitute reaching definition is not a merge, setting the reaching definition to be a store of an expression whose value number is the same as that of the expression, moving inputs of that store expression to the parent block that contains the substitute reaching definition, and replacing the expression with a load of a variable store by the reaching definition.

63. The computer-readable medium of claim 56 wherein the depth of the expression and the depth of the block indicate that the expression can be moved to the block when the depth of the expression is less than or equal to the depth of the block and the block dominates the expression.

64. The computer-readable medium of claim 56 wherein the identifying of the depth of the expression includes setting the depth of the expression to a maximum of depths of operands of the expression.

65. The computer-readable medium of claim 56 wherein the identifying of the depth of the expression includes when an operation of the expression is a load from memory, setting the depth of the expression to a maximum of depths of operands of the expression and depth of a reaching definition of the expression.

66. The computer-readable medium of claim 56 wherein the identifying of the depth of the expression includes when an operation of the expression is a store into memory, setting the depth of the expression to a depth of a parent block that contains the expression.

67. A method in a computer system for modifying a computer program, the method comprising:

identifying a depth of a block of the computer program;

identifying a depth of an expression of the computer program; and

when the identified depth of the expression is less than or equal to the depth of the block, moving the expression to the block.

68. The method of claim 67 wherein the block dominates the expression.

69. The method of claim 67 wherein the identifying of the depth of the expression includes setting the depth of the expression to a maximum of depths of operands of the expression.

70. The method of claim 67 wherein the moving of the expression includes when the depth of the expression is not greater than the depth of the block, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

71. The method of claim 67 wherein the moving of the expression includes when the depth of the expression is greater than the depth of the block, moving inputs to the expression, creating a new variable to store a value of the expression, replacing a reference to the expression in a parent block that contains the expression with a reference to the created variable, moving the expression and operands of the expression to the block, and adding to the block a store of the value of the expression into the new variable.

72. The method of claim 71 wherein when the expression is not a memory reference moving to the block each operand of the expression whose depth is greater than the depth of the block.

73. The method of claim 71 wherein when the expression is a memory reference and a reaching definition of the expression is either a merge of a scalar loaded by the expression or a store of a value such that a value number of the reaching definition is the same as a value number of the expression, substituting a reaching definition for a current reaching definition of the expression.

74. The method of claim 71 wherein the substituting of the reaching definition includes selecting as a substitute reaching definition the first reaching definition in a chain of reaching definitions whose depth is less than or equal to the depth of the block or whose operation is not a merge.

75. The method of claim 74 including when the operation of the substitute reaching definition is not a merge, setting the reaching definition to be a store of an expression whose value number is the same as that of the expression, moving inputs of that store expression to the parent block that contains the substitute reaching definition, and replacing the expression with a load of a variable store by the reaching definition.

76. The method of claim 67 wherein the depth of the expression and the depth of the block indicate that the expression can be moved to the block when the depth of the expression is less than or equal to the depth of the block and the block dominates the expression.

77. The method of claim 67 wherein the identifying of the depth of the expression includes setting the depth of the expression to a maximum of depths of operands of the expression.

78. The method of claim 67 wherein the identifying of the depth of the expression includes when an operation of the expression is a load from memory, setting the depth of the expression to a maximum of depths of operands of the expression and depth of a reaching definition of the expression.

79. The method of claim 67 wherein the identifying of the depth of the expression includes when an operation of the expression is a store into memory, setting the depth of the expression to a depth of a parent block that contains the expression.

80. The method of claim 67 wherein the identifying of the depth of the expression is performed while visiting blocks of the computer program during a forward traversal of a control flow graph representation of the computer program.