Methods and apparatus for compiling instructions for a data processor

• US 8,166,450 B2
• Filed: 10/01/2007
• Issued: 04/24/2012
• Est. Priority Date: 12/26/2001
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Fuhler, Richard A., Pennello, Thomas J., Jalkut, Michael Lee, Warnes, Peter
• Primary Examiner(s): WANG, RONGFA PHILIP
• Application Number:
  US11/906,519
• Publication Number:
  US 20080320246A1
• Time in Patent Office: 1,667 Days
• Field of Search: 717/101, 717/140, 717/146
• US Class Current: 717/101
• CPC Class Codes: G06F 8/4434 Reducing the memory space required by the program code
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs

Abstract

Methods and apparatus optimized for compiling instructions in a data processor are disclosed. In one aspect, a method of address calculation is disclosed, comprising operating a compiler to generate at least one instruction; canonicalizing the address calculation in a plurality of different approaches: in one exemplary embodiment, the first approach comprises canonicalizing the “regular” 32-bit instruction addressing modes, and the second for the “compressed” 16-bit instruction addressing modes. In another aspect, a plurality of functions (up to and including all available functions) are called indirectly to allow addresses to be placed in a constant pool. Improved methods for instruction selection, register allocation and spilling, and instruction compression are provided. An improved SoC integrated circuit device having an optimized 32-bit/16-bit processor core implementing at least one of the foregoing improvements is also disclosed.

Claims

1. A method of register allocation for use by a pipelined digital processor having a mixed-length instruction set architecture, the method executed by the processor and comprising:

storing data in a register from a first set of registers, the first set of registers associated with a first instruction set of a first length;

evaluating, using graph theory, whether spilling of the register from the first set of registers to a second set of registers is required, the second set of registers associated with a second instruction set of a second length; and

responsive to evaluating that spilling is required, reassigning the data in the register from the first set of registers to a register from the second set of registers.

2. The method of claim 1, wherein the first instruction set of the first length comprises instructions of a 16-bit length and the second instruction set of the second length comprises instructions of a 32-bit length.

3. The method of claim 1, further comprising:

responsive to evaluating that spilling is required, coalescing instructions associated with one or more registers from the first set of registers and the second set of registers to reduce a number of instructions.

4. The method of claim 3, wherein coalescing instructions comprises:

determining a first version of a plurality of instructions associated with the first set of registers and the second set of registers, the first version determined according to the first instruction set of the first length;

determining a second version of the plurality of instructions associated with the first set of registers and the second set of registers, the second version determined according to the second instruction set of the second length;

determining for a portion of the plurality of instructions whether the first version or the second version is better in terms of size of instruction or number of instructions; and

selecting the better version of the portion of the plurality of instructions.

5. The method of claim 4, wherein determining whether the first version or the second version is better is based on size of the portion of the plurality of instructions in the first version and second version.

6. The method of claim 4, wherein determining whether the first version or the second version is better is based on a number of instructions in the first version and second version of the portion of the plurality of instructions.

7. The method of claim 1, further comprising:

assigning a different characteristic to the register that is going to be spilled; and

performing a common sub-expression elimination process.

8. The method of claim 1, further comprising:

assigning a priority to each register from the first set of registers.

9. The method of claim 1, further comprising:

assigning a specific characteristic for at least one register from the first set of registers based at least in part on at least one of;

(i) compressing a size of an instruction of the at least one register, or (ii) reducing an overall size of a compiled function.

10. The method of claim 1, further comprising:

assigning characteristics to each register from the first set of registers and the second set of registers; and

assigning a different characteristic to the register from the first set of registers that is going to be spilled.

11. A digital processor having a mixed-length instruction set architecture, the processor comprising:

a first set of registers associated with a first instruction set of a first length; and

a second set of registers associated with a second instruction set of a second length;

wherein data stored in a register from the first set of registers is reassigned to a register from the second set of registers responsive to evaluating that spilling is required.

12. The digital processor of claim 11, wherein the first instruction set of the first length comprises instructions of a 16-bit length and the second instruction set of the second length comprises instructions of a 32-bit length.

13. The digital processor of claim 11, wherein instructions associated with one or more registers from the first set of registers and the second set of registers is coalesced to reduce a number of instructions responsive to spilling.

14. The digital processor of claim 13, wherein the digital processor is configured to reduce the number of instructions by:

determining a first version of a plurality of instructions associated with the first set of registers and the second set of registers, the first version determined according to the first instruction set of the first length;

determining a second version of the plurality of instructions associated with the first set of registers and the second set of registers, the second version determined according to the second instruction set of the second length;

determining for a portion of the plurality of instructions whether the first version or the second version is better in terms of size of instruction or number of instructions; and

selecting the better version of the portion of the plurality of instructions.

15. The digital processor of claim 14, wherein determining whether the first version or the second version is better is based on size of the portion of the plurality of instructions in the first version and second version.

16. The digital processor of claim 14, wherein determining whether the first version or the second version is better is based on a number of instructions in the first version and second version of the portion of the plurality of instructions.

17. The digital processor of claim 11, wherein the digital processor is configured to:

assign a different characteristic to the register that is going to be spilled; and

perform a common sub-expression elimination process.

18. The digital processor of claim 11, wherein each register from the first set of registers is assigned a priority.

19. The digital processor of claim 11, wherein the digital processor is configured to:

assign characteristics to each register from the first set of registers and the second set of registers; and

assign a different characteristic to the register from the first set of registers that is going to be spilled.

20. The digital processor of claim 11, wherein evaluating that spilling is required comprising using graph coloring for the evaluation.