Loop Transformation for Computer Compiler Optimization

• US 20110231830A1
• Filed: 03/16/2010
• Published: 09/22/2011
• Est. Priority Date: 03/16/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Zhang, Chihong, Udayakumaran, Sumesh
• Granted Patent: US 8,732,679 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A new computer-compiler architecture includes code analysis processes in which loops present in an intermediate instruction set are transformed into more efficient loops prior to fully executing the intermediate instruction set. The compiler architecture starts by generating the equivalent intermediate instructions for the original high level source code. For each loop in the intermediate instructions, a total cycle cost is calculated using a cycle cost table associated with the compiler. The compiler then generates intermediate code for replacement loops in which all conversion instructions are removed. The cycle costs for these new transformed loops are then compared against the total cycle cost for the original loops. If the total cycle costs exceed the new cycle costs, the compiler will replace the original loops in the intermediate instructions with the new transformed loops prior to generation of final code using the instruction set of the processor.

Claims

1. A method for compiling high level source code, said method comprising:

translating said high level source code into an intermediate instruction set;

determining a total cycle cost for a loop in said intermediate instruction set;

determining an estimated cycle cost for an equivalent transformed loop having all conversions outside the transformed loop;

comparing said total cycle cost with said estimated cycle cost; and

in response to said total cycle cost exceeding said estimated cycle cost, replacing said loop with said equivalent transformed loop.

2. The method of claim 1 wherein said determining a total cycle cost comprises:

scanning instructions in said loop to identify lower precision registers;

identifying all upward exposed use values involving said lower precision registers;

identifying all downward exposed define values involving said lower precision registers;

determining a lower bound for a loop trip count of said loop; and

calculating said total cycle cost using an instruction cost table related to said instructions.

3. The method of claim 2 further comprising in response to said total cycle cost exceeding said estimated cycle cost:

scanning instructions in said loop to identify lower precision instructions, and higher precision registers;

reserving at least one additional higher precision register for each of said identified upward exposed use values involving lower precision registers;

creating a mapping table relating said lower precision registers to said at least one additional higher precision register;

identifying conversion registers used in conversion instructions in said loop;

updating said mapping table with said conversion registers; and

deleting said conversion instructions in said loop.

4. The method of claim 3, further comprising:

replacing in said loop each lower precision register name representing said lower precision registers with a corresponding higher precision register name representing said higher precision registers from said mapping table;

replacing said lower precision instructions in the loop with an equivalent higher precision instruction;

generating a loop prologue having an upconvert instruction for each of said upward exposed use values, wherein said upconvert instruction obtains a destination higher precision register from said mapping table; and

generating a loop epilogue having a down convert instruction for said downward exposed, wherein a source higher precision register of said convert instruction is obtained from said mapping table

5. The method of claim 1 wherein said translating, said determining said total cycle cost, said determining said estimated cost, said comparing, and said replacing are performed on a single integrated circuit.

6. A computing device comprising:

a processor;

an input/output (I/O) interface coupled to said processor;

a storage memory coupled to said processor;

a compiler stored on said storage memory;

high level source code stored on said storage memory, wherein, when selected for execution, said processor executes said compiler, said executing compiler configured;

to trigger execution of a code generator associated with said compiler, said code generator executed by said processor and configured to generate an intermediate instruction set based on said high level source code;

to trigger execution of a cost analyzing module associated with said compiler, said cost analyzing module executed by said processor and configured to determine a total cycle cost for a loop in said intermediate instruction set, wherein said executing cost analyzing module is further configured to determine an estimated cycle cost for an equivalent transformed loop without conversion instructions in the transformed loop;

to compare said total cycle cost with said estimated cycle cost; and

to replace said loop with said equivalent transformed loop in response to said total cycle cost exceeding said estimated cycle cost.

7. The computing device of claim 6 wherein, in determining said total cycle cost, said executing cost analyzing module further configures said executing compiler:

to scan instructions in said loop to identify lower precision registers;

to identify all upward exposed use values in said lower precision registers to identify all downward exposed define values in said lower precision registers;

to determine a lower bound for a loop trip count of said loop; and

to calculate said total cycle cost using an instruction cost table related to said instructions.

8. The computing device of claim 7 wherein, when said total cycle cost exceeds said estimated cycle cost, said executing compiler is further configured:

to scan instructions in said loop to identify lower precision instructions, and higher precision registers;

to reserve at least one additional higher precision register for each of said identified upward exposed use values involving lower precision registers;

to create a mapping table relating said lower precision registers to said at least one additional higher precision register;

to identify conversion registers used in conversion instructions in said loop;

to update said mapping table with said conversion registers;

to delete said conversion instructions in said loop;

to replace in said loop each lower precision register name representing said lower precision registers with a corresponding higher precision register name representing said higher precision registers from said mapping table;

to replace said lower precision instructions in the loop with an equivalent higher precision instruction;

to generate code defining a loop prologue having an upconvert instruction for each of said upward exposed use values, wherein said upconvert instruction obtains a destination higher precision register from said mapping table; and

to generate code defining a loop epilogue having a down convert instruction for said downward exposed, wherein a source higher precision register of said convert instruction is obtained from said mapping table.

9. The computing device of claim 6 wherein, in translating said source code, said code generator is further configured:

to generate an intermediate instruction corresponding to at least one high level instruction contained in said source code; and

to substitute said intermediate instruction for said at least one high level instruction in said intermediate instruction set.

10. A computer-readable medium including program code tangibly stored thereon, comprising:

program code to translate source code into an intermediate instruction set;

program code to determine a total cycle cost for a loop in said intermediate instruction set;

program code to determine an estimated cycle cost for an equivalent transformed loop without looped conversions;

program code to compare said total cycle cost with said estimated cycle cost; and

program code, executable in response to said total cycle cost exceeding said estimated cycle cost, to replace said loop with said equivalent transformed loop.

11. The computer-readable medium of claim 10 wherein said program code to determine a total cycle cost comprises:

program code to scan instructions in said loop to identify lower precision instructions;

program code to identify all upward exposed use values in said lower precision registers;

program code to identify all downward exposed define values in said lower precision registers;

program code to determine a lower bound for a loop trip count of said loop; and

program code to calculate said total cycle cost using an instruction cost table related to said instructions.

12. The computer-readable medium of claim 11 further comprising in response to said total cycle cost exceeding said estimated cycle cost:

program code to reserve at least one additional higher precision register for each of said identified upward exposed use values involving lower precision registers;

program code to create a mapping table relating said lower precision registers to said at least one additional higher precision register;

program code to identify conversion registers used in conversion instructions in said loop;

program code to update said mapping table with said conversion registers;

program code to delete said conversion instructions in said loop;

program code to replace in said loop each lower precision register name representing said lower precision registers with a corresponding higher precision register name representing said higher precision registers from said mapping table;

program code to replace said lower precision instructions in the loop with an equivalent higher precision instruction;

program code to generate code defining a loop prologue having an upconvert instruction for each of said upward exposed use values, wherein said upconvert instruction obtains a destination higher precision register from said mapping table; and

program code to generate code defining a loop epilogue having a down convert instruction for said downward exposed, wherein a source higher precision register of said convert instruction is obtained from said mapping table.

13. The computer-readable medium of claim 10 wherein said program code to translate said source code comprises:

program code to generate an intermediate instruction corresponding to at least one high level instruction contained in said source code; and

program code to substitute said intermediate instruction for said at least one high level instruction in said intermediate instruction set.

14. The computer-readable medium of claim 10 wherein said program code to translate, said program code to determine said total cycle cost, said program code to determine said estimated cost, said program code to compare, and said program code to replace reside on a single integrated circuit.

15. A system for compiling high level source code, said system comprising:

means for translating said source code into an intermediate instruction set;

means for determining a total cycle cost for a loop in said intermediate instruction set;

means for determining an estimated cycle cost for an equivalent transformed loop without conversions;

means for comparing said total cycle cost with said estimated cycle cost; and

means, executable in response to said total cycle cost exceeding said estimated cycle cost, for replacing said loop with said equivalent transformed loop.

16. The system of claim 15 wherein said means for determining a total cycle cost comprises:

means for scanning instructions in said loop to identify lower precision registers;

means for identifying all upward exposed use values in said lower precision registers

means for identifying all downward exposed define values in said lower precision registers;

means for determining a lower bound for a loop trip count of said loop; and

means for calculating said total cycle cost using an instruction cost table related to said instructions.

17. The system of claim 16 further comprising in response to said total cycle cost exceeding said estimated cycle cost:

means for scanning instructions in said loop to identify lower precision instructions, and higher precision registers;

means for reserving at least one additional higher precision register for each of said identified upward exposed use values involving lower precision registers;

means for creating a mapping table relating said lower precision registers to said at least one additional higher precision register;

means for identifying conversion registers used in conversion instructions in said loop;

means for updating said mapping table with said conversion registers;

means for deleting said conversion instructions in said loop;

means for replacing in said loop each lower precision register name representing said lower precision registers with a corresponding higher precision register name representing said higher precision registers from said mapping table;

means for replacing said lower precision instructions in the loop with an equivalent higher precision instruction;

means for generating a loop prologue having an upconvert instruction for each of said upward exposed use values, wherein said upconvert instruction obtains a destination higher precision register from said mapping table; and

means for generating a loop epilogue having a down convert instruction for said downward exposed, wherein a source higher precision register of said convert instruction is obtained from said mapping table.

18. A computer compiler integrated circuit (IC) comprising:

a plurality of functional code modules, said plurality comprising;

a compilation module configured to manage compilation of high level source code into executable low level code;

a code generator;

a cost table;

a cost analyzing module;

an instruction set architecture (ISA);

wherein said plurality of functional code modules are integrated into a single IC;

a bus interface coupled to a computer bus, said computer bus enabling communication with a processor for executing said plurality of functional code modules, wherein, when executed by said processor, said compilation module configures said compiler;

to trigger execution of said code generator, said code generator executed by said processor and configured to generate an intermediate instruction set using said ISA and based on said high level source code;

to trigger execution of said cost analyzing module, said cost analyzing module is executed by said processor and configured to access said cost table and calculate a total cycle cost for a loop in said intermediate instruction set, and to calculate an estimated cycle cost for an equivalent transformed loop generated by said code generator, the equivalent loop omitting conversions;

to compare said total cycle cost with said estimated cycle cost; and

to replace said loop with said equivalent transformed loop in response to said total cycle cost exceeding said estimated cycle cost.

19. The computer compiler IC of claim 18 wherein, in determining said total cycle cost, said executing cost analyzing module further configures said executing compiler:

to scan instructions in said loop to identify lower precision registers;

to identify all upward exposed use values in said lower precision registers;

to identify all downward exposed define values in said lower precision registers;

to determine a lower bound for a loop trip count of said loop; and

to calculate said total cycle cost using an instruction cost table related to said instructions.

20. The computer compiler IC of claim 19 wherein, when said total cycle cost exceeds said estimated cycle cost, said executing compiler is further configured:

to scan instructions in said loop to identify lower precision instructions and higher precision registers;

to reserve at least one additional higher precision register for each of said identified upward exposed use values involving lower precision registers;

to create a mapping table relating said lower precision registers to said at least one additional higher precision register;

to identify conversion registers used in conversion instructions in said loop;

to update said mapping table with said conversion registers;

to delete said conversion instructions in said loop;

to replace in said loop each lower precision register name representing said lower precision registers with a corresponding higher precision register name representing said higher precision registers from said mapping table;

to replace said lower precision instructions in the loop with an equivalent higher precision instruction;

to generate code defining a loop prologue having an upconvert instruction for each of said upward exposed use values, wherein said upconvert instruction obtains a destination higher precision register from said mapping table; and

to generate code defining a loop epilogue having a down convert instruction for said downward exposed, wherein a source higher precision register of said convert instruction is obtained from said mapping table.