Methods and apparatus for storage and translation of an entropy encoded instruction sequence to executable form

Patent metadata

Field	Value
Publication number	US-10120692-B2
Application number	US-201113192916-A
Country	US
Kind code	B2
Filing date	Jul 28, 2011
Priority date	Jul 28, 2011
Publication date	Nov 6, 2018
Grant date	Nov 6, 2018

Abstract

A method of compressing a sequence of program instructions begins by examining a program instruction stream to identify a sequence of two or more instructions that meet a parameter. The identified sequence of two or more instructions is replaced by a selected type of layout instruction which is then compressed. A method of decompressing accesses an X-index and a Y-index together as a compressed value. The compressed value is decompressed to a selected type of layout instruction which is decoded and replaced with a sequence of two or more instructions. An apparatus for decompressing includes a storage subsystem configured for storing compressed instructions, wherein a compressed instruction comprises an X-index and a Y-index. A decompressor is configured for translating an X-index and Y-index accessed from the storage subsystem to a selected type of layout instruction which is decoded and replaced with a sequence of two or more instructions.

First claim

What is claimed is:

1. A method of compressing a sequence of program instructions, the method comprising:
identifying a sequence of instructions that includes a no operation (NOP) instruction and two function instructions, wherein each instruction of the sequence of instructions has a same number of bits;
replacing the identified sequence of instructions by a selected type of layout instruction comprised with the same number of bits as one of the two function instructions, wherein the selected type of layout instruction identifies a position of each instruction in the identified sequence of instructions; and
compressing the selected type of layout instruction to an X-index and a Y-index pair of compressed values.

2. The method of claim 1 , wherein the identified sequence of instructions includes a sequence of two or more NOP instructions.

3. The method of claim 2 , wherein the sequence of two or more NOP instructions is positioned between the two function instructions.

4. The method of claim 1 , wherein the identified sequence of instructions includes a second NOP instruction.

5. The method of claim 1 , wherein each function instruction of the two function instructions comprises an arithmetic logic unit instruction, a load instruction, a store instruction, or a control instruction.

6. The method of claim 1 , wherein the two function instructions correspond to a pair of function instructions that has been identified in an instruction stream at least a particular number of times.

7. The method of claim 1 , wherein the identified sequence of instructions includes at least four instructions.

8. The method of claim 1 , wherein the identified sequence of instructions is a very long instruction word packet of three or more instructions.

9. The method of claim 1 , wherein the identified sequence of instructions includes two non-contiguous NOP instructions that include the NOP instruction.

10. The method of claim 1 , wherein the identified sequence of instructions includes a sequence of three NOP instructions.

11. A method to decompress instructions, the method comprising:
accessing an X-index and a Y-index together as a compressed value;
decompressing the compressed value to a selected type of layout instruction comprising a defined number of bits, wherein the selected type of layout instruction identifies instructions in a packet of instructions that includes a plurality of no operation (NOP) instructions and one or more function instructions positioned between a pair of NOP instructions of the plurality of NOP instructions in the packet of instructions, wherein the selected type of layout instruction further identifies a number of occurrences of the plurality of NOP instructions and placement of each NOP instruction of the plurality of NOP instructions to an identified position in the packet of instructions; and
decoding the selected type of layout instruction to replace the selected type of layout instruction with the packet of instructions, wherein each identified instruction of the packet of instructions is comprised with a same defined number of bits.

12. The method of claim 11 , wherein the decompressing comprises:
selecting an X pattern from an X pattern memory according to the X-index;
selecting a Y pattern from a Y pattern memory according to the Y-index; and
combining the X pattern with the Y pattern according to a mix mask to create the selected type of layout instruction.

13. The method of claim 11 , wherein the selected type of layout instruction indicates three or more NOP instructions.

14. The method of claim 11 , wherein the selected type of layout instruction indicates the packet of instructions is a combination of three or more NOP instructions and the one or more function instructions.

15. The method of claim 11 , wherein the one or more function instructions include a pair of function instructions that has been identified in an instruction stream at least a particular number of times.

16. The method of claim 11 wherein the decompressing is accomplished on an instruction fetch from a memory hierarchy of a processor core.

17. An apparatus for decompressing a compressed value representing a sequence of instructions, the apparatus comprising:
a storage subsystem configured for storing compressed instructions, wherein a compressed instruction comprises an X-index and a Y-index;
a decompressor configured for translating the X-index and the Y-index to a selected type of layout instruction comprising a defined number of bits, wherein the selected type of layout instruction identifies instructions in a packet of instructions that includes a plurality of no operation (NOP) instructions and one or more function instructions positioned between a pair of NOP instructions of the plurality of NOP instructions in the packet of instructions, wherein the selected type of layout instruction further identifies a number of occurrences of the plurality of NOP instructions and placement of each NOP instruction of the plurality of NOP instructions to an identified position in the packet of instructions; and
a decoder configured for replacing the selected type of layout instruction with the packet of instructions, wherein each identified instruction of the packet of instructions is comprised with a same defined number of bits.

18. The apparatus of claim 17 , wherein the decompressor comprises:
an X pattern memory operable to store X patterns that are selected according to the X-index;
a Y pattern memory operable to store Y patterns that are selected according to the Y-index; and
a combiner configured for combining a selected X pattern with a selected Y pattern according to a mix mask to create the selected type of layout instruction.

19. The apparatus of claim 17 , wherein the plurality of NOP instructions includes three NOP instructions.

20. The apparatus of claim 17 , wherein the instructions in the packet of instructions include a combination of three NOP instructions and the one or more function instructions.

21. The apparatus of claim 17 , wherein the one or more function instructions include a pair of function instructions that has been identified in an instruction stream at least a particular number of times.

22. The apparatus of claim 17 , wherein the storage subsystem comprises:
a level 1 instruction cache operable to store the compressed instructions.

23. A method of compressing a sequence of program instructions, the method comprising:
identifying a sequence of K instructions that includes one or more no operation (NOP) instructions and two or more function instructions, wherein each instruction of the sequence of K instructions has a same number of bits B, and K is a positive integer ≥3;
replacing the identified sequence of K instructions by a selected type of layout instruction comprised with the same number of bits B, wherein the selected type of layout instruction encodes the sequence of K instructions, and wherein the selected type of layout instruction identifies a position of each instruction in the identified sequence of K instructions; and
compressing the selected type of layout instruction to an X-index and a Y-index pair of compressed values that is a compressed representation of the identified sequence of K instructions.

24. The method of claim 23 , wherein the selected type of layout instruction solely represents the sequence of K instructions.

25. An apparatus for decompressing a compre

Assignees

• Larin Sergei
• Codrescu Lucian
• Das Gupta Anshuman
• Qualcomm Inc

Inventors

• Larin Sergei
• Codrescu Lucian
• Das Gupta Anshuman

Classifications

• G06F9/30178 Primary

  of compressed or encrypted instructions · CPC title

• G06F9/3017

  Runtime instruction translation, e.g. macros · CPC title

• G06F9/30156

  Special purpose encoding of instructions, e.g. Gray coding · CPC title

• G06F9/3853 Primary

  of compound instructions · CPC title