Method and Apparatus For Register Spill Minimization

• US 20130198495A1
• Filed: 03/01/2012
• Published: 08/01/2013
• Est. Priority Date: 01/26/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Vick, Christopher A., Wright, Gregory M.
• Granted Patent: US 8,893,104 B2
• Time in Patent Office: Days
• US Class Current: 712/226
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

The aspects enable a computing device to allocate memory space to variables during runtime compilation of a software application. A compiler may be modified to identify operations that can be performed on either a main pipe or an alternative pipe, identify chains of related operations that can be performed on either the main pipe or the alternative pipe, identify points in the execution of code at which the number of live values will exceed the number of registers, and choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of live values at identified points in the execution of code. The entire chosen chain of operations may be moved to the alternative pipe. The alternative pipe may perform the computations and return the results to the main pipe for execution.

Claims

1. A compiler method implemented within a compiler on a computing device, the method comprising:

identifying operations that may be performed on either a main pipe or an alternative pipe;

identifying chains of related operations that may be performed on either the main pipe or the alternative pipe;

identifying points of execution at which a number of simultaneous live values will exceed a number of available registers in the main pipe;

choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points of execution that compete for registers in the main pipe; and

generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe.

2. The method of claim 1, further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the main pipe from the pseudo instructions.

3. The method of claim 1, further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the alternative pipe from the pseudo instructions.

4. The method of claim 1, further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe as part of a register allocation process; and

selecting an instruction set to be generated from the pseudo instructions as part of the register allocation process.

5. The method of claim 1, further comprising computing costs of performing each chain of operations on the alternative pipe, wherein choosing a chain of operations as a candidate to be moved to the alternative pipe comprises:

identifying live values associated with candidate chains of operations; and

choosing among chains of operations associated with a live value based upon the computed costs.

6. The method of claim 1, wherein the alternative pipe is a single instruction multiple data (SIMD) unit.

7. The method of claim 1, further comprising repeating operations of choosing a chain of operations to move to the alternative pipe until the number of simultaneous live values on the main pipe no longer exceeds the number of available registers in the main pipe.

8. A computing device, comprising:

means for identifying operations that may be performed on either a main pipe or an alternative pipe;

means for identifying chains of related operations that may be performed on either the main pipe or the alternative pipe;

means for identifying points of execution at which a number of simultaneous live values will exceed a number of available registers in the main pipe;

means for choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points in of execution which compete for registers in the main pipe; and

means for generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe.

9. The computing device of claim 8, further comprising:

means for generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein means for choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points in of execution which compete for registers in the main pipe comprises means for generating instructions for the main pipe from the pseudo instructions.

10. The computing device of claim 8, further comprising:

means for generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein means for choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points in of execution which compete for registers in the main pipe comprises means for generating instructions for the alternative pipe from the pseudo instructions.

11. The computing device of claim 8, further comprising:

means for generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe as part of a register allocation process; and

means for selecting an instruction set to be generated from the pseudo instructions as part of the register allocation process.

12. The computing device of claim 8, further comprising means for computing costs of performing each chain of operations on the alternative pipe, wherein means for choosing a chain of operations as a candidate to be moved to the alternative pipe comprises:

means for identifying live values associated with candidate chains of operations; and

means for choosing among chains of operations associated with a live value based upon the computed costs.

13. The computing device of claim 8, wherein means for choosing a chain of operations as a candidate to be moved to the alternative pipe comprises means for choosing a chain of operations as a candidate to be moved to a single instruction multiple data (SIMD) unit.

14. The computing device of claim 8, further comprising means for repeating operations of choosing a chain of operations to move to the alternative pipe until the number of simultaneous live values on the main pipe no longer exceeds the number of available registers in the main pipe.

15. A computing device, comprising:

a memory; and

a processor coupled to the memory, wherein the processor is configured with processor-executable instructions to perform operations comprising;

identifying operations that may be performed on either a main pipe or an alternative pipe;

identifying chains of related operations that may be performed on either the main pipe or the alternative pipe;

identifying points of execution at which a number of simultaneous live values will exceed a number of available registers in the main pipe;

choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points of execution which compete for registers in the main pipe; and

generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe.

16. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the main pipe from the pseudo instructions.

17. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe,

wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the alternative pipe from the pseudo instructions.

18. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe as part of a register allocation process; and

selecting an instruction set to be generated from the pseudo instructions as part of the register allocation process.

19. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising computing costs of performing each chain of operations on the alternative pipe, and wherein the processor is configured with processor-executable instructions such that choosing a chain of operations as a candidate to be moved to the alternative pipe comprises:

identifying live values associated with candidate chains of operations; and

choosing among chains of operations associated with a live value based upon the computed costs.

20. The computing device of claim 15, wherein the processor is configured with processor-executable instructions such that generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the chosen chain of operations for a single instruction multiple data (SIMD) unit.

21. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising repeating operations of choosing a chain of operations to move to the alternative pipe until the number of simultaneous live values on the main pipe no longer exceeds the number of available registers in the main pipe.

22. A non-transitory computer readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform operations comprising:

identifying operations that may be performed on either a main pipe or an alternative pipe;

identifying chains of related operations that may be performed on either the main pipe or the alternative pipe;

identifying points of execution at which a number of simultaneous live values will exceed a number of available registers in the main pipe;

choosing a chain of operations as a candidate to be moved to the alternative pipe in order to reduce the number of simultaneous live values at identified points of execution which compete for registers in the main pipe; and

generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe.

23. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe, wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the main pipe from the pseudo instructions.

24. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe, wherein generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the alternative pipe from the pseudo instructions.

25. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations comprising:

generating pseudo instructions that enable later generation of instructions for execution on the main pipe or instructions for execution on the alternative pipe as part of a register allocation process; and

selecting an instruction set to be generated from the pseudo instructions as part of the register allocation process.

26. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations comprising computing costs of performing each chain of operations on the alternative pipe, and the stored processor-executable instructions are configured to cause a processor to perform operations such that choosing a chain of operations as a candidate to be moved to the alternative pipe comprises:

identifying live values associated with candidate chains of operations; and

choosing among chains of operations associated with a live value based upon the computed costs.

27. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that generating instructions for the chosen chain of operations for execution on either the main pipe or the alternative pipe comprises generating instructions for the chosen chain of operations for execution on a single instruction multiple data (SIMD) unit.

28. The non-transitory computer readable storage medium of claim 22, wherein the stored processor-executable instructions are configured to cause a processor to perform operations comprising repeating operations of choosing a chain of operations to move to the alternative pipe until the number of simultaneous live values on the main pipe no longer exceeds the number of available registers in the main pipe.