Managing variable assignments in a program

• US 8,555,266 B2
• Filed: 11/13/2007
• Issued: 10/08/2013
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Copeland, Reid T., Stoodley, Mark Graham, Sundaresan, Vijay, Wong, Ning Thomas
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): Dang, Christine
• Application Number:
  US11/938,884
• Publication Number:
  US 20090125893A1
• Time in Patent Office: 2,156 Days
• Field of Search: None
• US Class Current: 717/151
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A computer-implemented method, apparatus, and computer program product to manage 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

the program containing a plurality of paths, wherein each path is a portion or sequence of programming statements that are executed during a particular execution of the program, and one or more variable assignments located at one or more corresponding program points, wherein each variable assignment assigns a value to a variable;

identifying one or more variable assignments in the program that is live on only a portion of the plurality of paths from the corresponding program point by examining each variable assignment in an order that is reverse from an order of execution of the program to form one or more identified variable assignments,

for each identified variable assignment,

determining, in an order that is reverse from an order of execution of the program, one or more program points at which the identified variable assignment would be closer to one or more locations in the program at which the variable of the identified variable assignment is used,

responsive to determining the one or more program points, determining whether the identified variable assignment is movable to the one or more program points, wherein the identified variable assignment is movable to the one or more program points if the identified variable assignment is live on all of a plurality of paths from the one or more program points, wherein the one or more identified variable assignments is live on all of the plurality of paths at the one or more program points if each of the plurality of paths from the one or more program points uses the variable of the identified variable assignment, and

responsive to determining that the identified variable assignment is movable to the one or more program points, moving the identified variable assignment to the one or more program points.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

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

12. A computer program product comprising:

a non-transitory 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 one or more variable assignments that is live only on a portion of a plurality of paths in the program by examining each variable assignment in an order that is reverse from an order of execution of the program to form one or more identified variable assignments, wherein each of the one or more identified variable assignments assigns a value to a variable, and wherein the one or more variable assignments is located at one or more corresponding program points, and each of the paths is a portion or sequence of programming statements that are executed during a particular execution of the program, and

for each identified variable assignment,

computer-usable program code for determining, in an order that is reverse from an order of execution of the program, one or more program points at which the identified variable assignment would be closer to one or more locations in the program at which the variable of the identified variable assignment is used;

computer-usable program code for responsive to determining the one or more program points, determining whether the identified variable assignment is movable to the one or more program points, wherein the identified variable assignment is movable to the one or more program points if the one or more program points is live on all of the plurality of paths at the one or more program points, wherein the identified variable assignment is live on all of the plurality of paths at the one or more program points if each of the plurality of paths from the one or more program points uses the variables of the identified variable assignment, and

computer-usable program code for responsive to determining that the identified variable assignment is movable to the one or more program points, moving the identified variable assignment to the one or more program points.

13. 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 one or more variable assignments that is live on only a portion of a plurality of paths by examining each variable assignment in an order that is reverse from an order of execution of a program to form one or more identified variable assignments, wherein each of the one or more identified variable assignments assigns a value to a variable, and wherein the one or more variable assignments is located at one or more corresponding program points, and each of the paths is a portion or sequence of programming statements that are executed during a particular execution of the program, and

for each identified variable assignment,

determines, in an order that is reverse from an order of execution of the program, one or more program points at which the identified variable assignment is closer to one or more locations in the program at which the variable of the identified variable assignment is used,

responsive to determining the set of program points, determines whether the identified variable assignment is movable to the one or more program points, wherein the identified variable assignment is movable to the one or more program points if the one or more program points is live on all of the plurality of paths at the one or more program points, wherein the identified variable assignment is live on all of the plurality of paths at the one or more program points if each of the plurality of paths from the one or more program points uses the variables of the identified variable assignment; and

moves the identified variable assignment to the one or more program points in response to determining that the identified variable assignment is movable to the one or more program points.