METHOD AND APPARATUS FOR MANAGING VARIABLE ASSIGNMENTS IN A PROGRAM

• US 20090125893A1
• Filed: 11/13/2007
• Published: 05/14/2009
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wong, Ning Thomas, Copeland, Reid T., Sundaresan, Vijay, Stoodley, Mark Graham
• Granted Patent: US 8,555,266 B2
• Time in Patent Office: Days
• US Class Current: 717/151
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

The illustrative embodiments described herein provide a computer-implemented method, apparatus, and computer program product for managing variable assignments in a program. The process identifies a set of variable assignments that is live on a portion of paths to form a set of identified variable assignments. Each of the set of identified variable assignments assign a value to at least one variable of a set of variables. The process determines a set of program points at which the set of identified variable assignments is live on all paths. The process also moves the set of identified variable assignments to the set of program points in response to determining that the set of identified variable assignments is movable to the set of program points.

Claims

1. A computer-implemented method for managing variable assignments in a program, comprising

identifying a set of variable assignments that is live on a portion of paths to form a set of identified variable assignments, wherein each of the set of identified variable assignments assigns a value to at least one variable of a set of variables,

determining a set of program points at which the set of identified variable assignments is closer to a set of locations in the program at which the at least one variable is used, and

responsive to determining that the set of identified variable assignments is movable to the set of program points, moving the set of identified variable assignments to the set of program points.

2. The computer-implemented method of claim 1, wherein the set of identified variable assignments is live on all paths at the set of program points.

3. The computer-implemented method of claim 2, wherein the set of identified variable assignments is live on all paths at the set of program points if each path from the set of program points uses the set of variables.

4. The computer-implemented method of claim 1, wherein the set of variable assignments are located at a set of particular program points, and wherein the identifying step comprises:

determining that fewer than all paths from the set of particular program points uses the set of variables.

5. The computer-implemented method of claim 1, wherein the identifying step comprises:

identifying a first set of variable assignments that is live to form a first identification;

identifying a second set of variable assignments that is live on all paths to form a second identification; and

identifying the set of variable assignments that is live on the portion of the paths to form the set of identified variable assignments using the first identification and the second identification.

6. The computer-implemented method of claim 1, wherein the identifying step comprises:

determining whether each variable assignment in the program is live on the portion of the paths to form a determination, wherein the determination occurs for each variable assignment in an order that is reverse from an order of execution of the program.

7. The computer-implemented method of claim 1, wherein the identifying step comprises:

determining whether each program block in the program includes one or more variable assignments that are live on the portion of the paths to form a determination, wherein the determination occurs for each program block in an order that is reverse from an order of execution of the program.

8. The computer-implemented method of claim 1, wherein the identifying comprises:

storing each of the set of identified variable assignments in a candidate list that stores potentially movable variable assignments.

9. The computer-implemented method of claim 1, wherein determining the set of program points at which the set of identified variable assignments is closer to the set of locations in the program at which the at least one variable is used comprises:

determining a program point in the set of program points for each identified variable assignment in the set of identified variable assignments to form a determination, wherein the determination occurs for each identified variable assignment in an order that is reverse from an order of execution of the program.

10. The computer-implemented method of claim 1, wherein determining the set of program points at which the set of identified variable assignments is closer to the set of locations in the program at which the at least one variable is used comprises:

determining a program point in the set of program points for each identified variable assignment in a set of program blocks to form a determination for each identified variable assignment, wherein the determination for each identified variable assignment in the set of program blocks occurs for each program block in an order that is reverse from an order of execution of the program.

11. The computer-implemented method of claim 1, wherein determining the set of program points at which the set of identified variable assignments is closer to the set of locations in the program at which the at least one variable is used comprises:

determining a first program point in the set of program points for a first identified variable assignment in the set of identified variable assignments before determining a second program point in the set of program points for a second identified variable assignment in the set of identified variable assignments, wherein the first identified variable assignment occurs later in the program than the second identified variable assignment.

12. The computer-implemented method of claim 1, wherein determining that the set of identified variable assignments is movable to the set of program points comprises:

determining that no loop function occurs between the set of identified variable assignments and the set of program points.

13. The computer-implemented method of claim 1, wherein determining that the set of identified variable assignments is movable to the set of program points comprises:

determining that a number of incoming edges matches a number of edges on which the set of identified variable assignments is live on the portion of the paths.

14. The computer-implemented method of claim 1, wherein the set of variable assignments comprises a first variable assignment and a second variable assignment, wherein the first variable assignment and the second variable assignment include a particular variable, wherein the first variable assignment assigns a first value to the particular variable, and wherein determining that the set of identified variable assignments is movable to the set of program points comprises:

determining that the second variable assignment at a program point in the set of program points does not overwrite the first value of the particular variable.

15. The computer-implemented method of claim 1, wherein the set of variables is a set of local variables.

16. A computer program product comprising:

a computer-usable medium having computer-usable program code for managing variable assignments in a program, the computer program product comprising;

computer-usable program code for identifying a set of variable assignments that is live on a portion of paths to form a set of identified variable assignments, wherein each of the set of identified variable assignments assigns a value to at least one variable of a set of variables,

computer-usable program code for determining a set of program points at which the set of identified variable assignments is closer to a set of locations in the program at which the at least one variable is used, and

computer-usable program code, responsive to determining that the set of identified variable assignments is movable to the set of program points, for moving the set of identified variable assignments to the set of program points.

17. The computer program product of claim 16, wherein the set of identified variable assignments is live on all paths at the set of program points.

18. The computer program product of claim 16, wherein the set of variable assignments are located at a set of particular program points, and wherein the computer-usable program code for identifying the set of variable assignments that is live on the portion of the paths to form the set of identified variable assignments comprises:

computer-usable program code for determining that fewer than all paths from the set of particular program points uses the set of variables.

19. A data processing system comprising:

a bus system;

a memory connected to the bus system, wherein the memory includes a set of instructions; and

a processing unit connected to the bus system, wherein the processing unit executes the set of instructions to identify a set of variable assignments that is live on a portion of paths to form a set of identified variable assignments, wherein each of the set of identified variable assignments assigns a value to at least one variable of a set of variables;

determine a set of program points at which the set of identified variable assignments is closer to a set of locations in a program at which the at least one variable is used; and

move the set of identified variable assignments to the set of program points in response to determining that the set of identified variable assignments is movable to the set of program points.

20. The data processing system of claim 19, wherein the set of variable assignments are located at a set of particular program points, and wherein in executing the set of instructions to identify the set of variable assignments that is live on the portion of the paths to form the set of identified variable assignments, the processing unit further executes the set of instructions to determine that fewer than all paths from the set of particular program points uses the set of variables.