Code Motion Based on Live Ranges in an Optimizing Compiler

• US 20100162220A1
• Filed: 12/23/2008
• Published: 06/24/2010
• Est. Priority Date: 12/23/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cui, Shimin, Silvera, Raul Esteban
• Granted Patent: US 8,484,630 B2
• Time in Patent Office: Days
• US Class Current: 717/155
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Optimizing program code in a static compiler by determining the live ranges of variables and determining which live ranges are candidates for moving code from the use site to the definition site of source code. Live ranges for variables in a flow graph are determined. Selected live ranges are determined as candidates in which code will be moved from a use site within the source code to a definition site within the source code. Optimization opportunities within the source code are identified based on the code motion.

Claims

1. A method of compiler optimization, the method comprising:

determining whether the identified live range is a candidate for code motion in the source code;

designating, based on a live range analysis, a variables in source code that are candidates for a renaming of the variables;

determining, based on a criteria, whether the variables of a live range are candidates for code motion in the source code;

responsive to a positive determination, modifying the code at the definition and the use site; and

optimizing the code in the compiler based on the modification.

2. The method of claim 1, wherein the live range analysis comprises performing a data flow analysis that determines definition information and use information of a plurality of variables in source code.

3. The method of claim 2, wherein the data flow analysis comprises implementing a single static assignment analysis.

4. The method of claim 3, wherein the single static assignment analysis includes automatically generating a control flow graph and a data flow graph.

5. The method of claim 1, wherein the designating comprises checking variables in the expressions in the code and determining reached uses of the variables in the live range.

6. The method of claim 1, further comprising creating a temporary variable based on a data type and data length of an expression of the reached uses in the live range.

7. The method of claim 6, wherein modifying the code comprises renaming the variables in the live range at all definition sites in the code and the use sites in the code.

8. The method of claim 1, wherein the criteria is based on determining whether a variable expression of the live range potentially exposes code folding opportunities in the code.

9. The method of claim 1, wherein the criteria is based on determining if a data type of a variable expression using the temporary variable is preferable to the original variable expression.

10. The method of claim 1, wherein optimizing the code comprises folding the code.

11. A computer program product comprising computer recordable media including instructions, which when executed by a processor, performs actions that optimizes source code in a compiler, the actions comprising:

determining whether an identified live range is a candidate for code motion in the source code;

designating, based on a live range analysis, a variables in source code that are candidates for a renaming of the variables;

determining, based on a criteria, whether the variables of a live range are candidates for code motion in the source code;

responsive to a positive determination, modifying the code at the definition and the use sites; and

optimizing the code in the compiler based on the modification.

12. The computer program product of claim 11, wherein the live range analysis comprises performing a data flow analysis that determines definition information and use information of a plurality of variables in source code.

13. The computer program product of claim 12, wherein the data flow analysis comprises implementing a single static assignment analysis.

14. The computer program product of claim 11, further comprising creating a temporary variable based on a data type and data length of an expression of the reached uses in the live range.

15. The computer program product of claim 11, wherein modifying the code comprises renaming the variables in the live range at all definition sites in the code and the use sites in the code.

16. The computer program product of claim 11, wherein the criteria is based on determining whether a variable expression of the live range potentially exposes code folding opportunities in the code.

17. A system that performs code optimization in a compiler, the system comprising:

a processor;

a memory coupled to the processor, the memory storing computer executable instructions, the instructions comprising;

computer usable code that determines whether an identified live range is a candidate for code motion in the source code;

computer usable code that designates, based on a live range analysis, variables in source code that are candidates for a renaming of the variables;

computer usable code that determines, based on a criteria, whether the variables of a live range are candidates for code motion in the source code;

computer usable code that, responsive to a positive determination, modifies the code at the definition and the use sites; and

computer usable code that optimizes the code in the compiler based on the modification.

18. The system of claim 17, further comprising computer usable code that creates a temporary variable based on a data type and data length of an expression of the reached uses in the live range.

19. The system of claim 18, further comprising computer usable code that modifies the code by renaming the variables in the live range at all definition sites in the code and the use sites in the code.

20. The system of claim 18, further comprising computer usable code that optimizes the code by folding the code.