Compressing “warm” code in a dynamic binary translation environment

Selected regions of native instructions translated in a DBT environment from non-native instructions are compressed based on the independent compression of different fields of selected instructions using compression tables to reduce a length of selected fields. The regions of compressed instructions are stored and de-compressed into the native instructions during subsequent execution using de-compression tables. Specifically, for native instructions of a selected region, selected types of opcodes and/or operands may be compressed independently. The types may be selected by profiling the opcodes using benchmark programs and creating an opcode conversion table prior to compression, and scanning of the operands and creating an operand conversion table during compression of the opcodes.

BACKGROUND

Dynamic binary translation of non-native code.

A sequence of machine executable code or instructions, such as a computer program are typically written in a “language” such as an instruction set of a processor (e.g., part or all of the “machine”). A language may be all of the operations (jump, store, etc.) that a processor can or is able to perform. In other words, a single processor (embedded or otherwise) can usually only execute a given set of instructions (e.g., language). Normally, a program is developed in a higher-level language (e.g. C or C++) and then compiled to produce an executable file that will run on a target processor. If it is desired to run the program on a different processor, the higher-level language may be compiled with a different compiler to produce a different executable file for the second processor.

However, in some circumstances, the higher-level program may not be available; only the compiled program is available. In those circumstances, the compiled program, or regions of instructions thereof, may be either interpreted (the second processor emulates the original processor and calculates what the original processor would have done in response to each region of instruction) or translated (the region of instructions for the original processor are replaced with a region of instructions or instruction sequence that causes the second processor to perform the same operations that the original processor would have done). Typically, a program includes multiple “branches” or branch instructions delineating subroutines or “blocks” of instructions. A region of instructions may be one or more blocks of instructions. Thus, a region of instructions may be a sequence of one or more instructions or blocks of a program to be interpreted, translated, processed, and/or executed in succession in a dynamic binary translation (DBT) environment or by a dynamic binary translator.

For instance, in a DBT environment, a sequence of instructions or a computer program having instructions in one language (e.g., non-native instructions that can be executed or processed by a non-native machine or processor) may be “executed” or processed by a native machine or processor capable of processing another different language (e.g., such as a native processor for native instructions). Specifically, regions of instructions in the non-native language (e.g., “non-native” instructions) may be “dynamically” interpreted, and other regions may be translated into regions of instructions of the native language for processing by the native processor (e.g., such as by being compiled just-in-time during “execution” in the dynamic binary translation (DBT) environment).

Thus, compiled non-native instructions may be received in a DBT environment for processing by a processor other than the “non-native” processor for which they were compiled. Specifically, a DBT environment may exist where the non-native source code or higher-level program is not available (e.g., only the compiled non-native program is available). Also, a DBT environment may exist where a static compiler is unable to compile the non-native code into compiled native code. Next, a DBT environment may exist where, in a program or instruction sequence, regions of instructions are to be translated and regions of instructions are to be interpreted by a native processor. In this third case, a dynamic binary translator may cause some regions of non-native code instructions (e.g., instructions to control a processor capable of processing one type of code or language) to be translated to regions of native code instructions (e.g., instructions to control a different processor capable of processing a different type of code or language) and may cause other regions of instructions to be interpreted (e.g., the non-native instructions may be processed by the different processor). The goal of interpreting is to have the second processor emulate the original processor, calculate what task the original processor would have done in response to each region of instruction, and perform that task. The goal of translating is to replace the instructions the original processor is able to execute with instruction that the second processor is capable of executing.

For example, “hot regions” or hot code of a sequence of instruction may be small code regions of a program executed frequently at run time and all of the hot code may consume 90% of processor clocks (e.g., clocks of a central processing unit (CPU)) for processing the entire sequence. In a DBT environment non-native hot code regions may be “executed” by being translated into compiled native instructions “just-in-time” before execution or use by the native processor. The first time they are compiled, the non-native regions of hot instructions and the just-in-time compiled native regions of hot instructions are stored in a memory (e.g., in table or, code cache) for quick reuse to translate the non-native hot region to a native version next time that non-native region of instructions is encountered. However, this requires enough memory to store the non-native and the native regions of instructions in a memory/table for reuse. This memory requirement is tolerable because of the relatively high frequency of encountering or executing the regions of hot code and the relatively small portion or succession of the sequence that is the regions of hot code (e.g., it is more desirable to require more memory than to execute the hot code more slowly by using interpretation).

Correspondingly, “cold regions” or cold code in a sequence of instruction may be small code regions of a program executed infrequently at run time and consume few of processor clocks for processing the sequence. Thus, cold code or regions may be “executed” by being interpreted in a DBT environment. For instance, compiled non-native cold code regions can be interpreted into the functionality of native instructions during execution by the native processor. The extra time required to perform each interpretation is tolerable because of the relatively low frequency of encountering or executing the regions of cold code and the relatively large portion or succession of the sequence that is the regions of cold code (e.g., it is more desirable to require more time to interpret and less memory).

DETAILED DESCRIPTION

In a dynamic binary translation (DBT) environment, a sequence of instructions or a computer program having instructions in a non-native language (e.g., non-native instructions compiled into compiled non-native instructions) may be “translated” (e.g., dynamic binary “translation”, not to be confused with translating “hot” code as described herein, which may be part of a dynamic binary “translation” process) to be “executed” or processed by a processor for another different or native language (e.g., a “native” processor, such as an embedded micro-processor). Such dynamic binary “translating” of non-native code may include “executing” some “cold” regions (e.g., cold code) of the non-native sequence of instructions by interpretation, and “executing” other “hot” regions (e.g., hot code) of the non-native sequence of instructions by translation. The interpreted and translated regions can then be “processed” by the native processor (such as by the native processor processing or executing the native code translated from the non-native code). Translating may include translating some or all of the non-native instructions, (e.g., compiled or un-compiled), into the native instructions (e.g., compiled or un-compiled), prior to processing by the native processor. A DBT environment may include dynamic binary “translation” of a sequence of non-native instructions, and/or an environment having a dynamic binary translator.

Moreover, according to embodiments, in a DBT environment, it may be desirable to dynamic binary “translate” certain regions of compiled non-native instructions that are other than hot or cold regions of instructions. For instance, some regions of the sequence of non-native instructions may be identified as “warm” regions (e.g., warm code), translated (e.g., similar to hot code translation), compressed, and then stored. When the warm regions are subsequently encountered (e.g., invoked, issued, dynamic binary “translated”, “executed”, processed, and/or appearing), the stored compressed code can be de-compressed to form native compiled code (like translated hot code) to be “processed” by the native processor. It can be appreciated that dynamic binary “translation” of a sequence of instructions in a DBT environment may include the “execution” of cold, warm and hot code regions of the sequence of instructions.

Warm regions (e.g., regions of “warm” code) of a sequence of instructions or program may be defined as regions of code or instructions of a program (e.g., regions of compiled native x86 instructions) executed semi-frequently at run time and consume 5-30% of processor or CPU clocks. If instead of being translated, compressed, stored, decompressed, and processed, the warm code is interpreted at run time (e.g., like “cold” regions), the warm regions of code can be stored without the need to store a translation (e.g., as required by hot code). However, the slow down of program execution due to the delay required to interpret to warm regions can be 70 times leading to increase of 3.5 times execution time for the entire program (e.g., such as for an entire sequence of instructions having 5% warm code). Alternatively, if instead of being translated and compressed, the warm code is translated and stored in code cache (e.g., like “hot” regions), the warm regions of code will take up a much greater amount of the cache than the hot code.

Hence, if regions of warm code can be properly dynamic binary “translated” in a DBT environment, execution performance (e.g., speed of “execution” and amount of memory required) will be improved. Specifically, the first time a region of warm code (e.g., non-native compiled code) is encountered, it may be “executed” by being identified (e.g., as a region of warm code, but not cold or hot code), translated (e.g., “just-in-time” compiled into native instructions), compressed into a compressed region of code, and the compressed region stored in a memory (e.g., code cache). The translated version of the code may be processed by the native processor, the first time the region of warm code is encountered. When the compressed region of code is re-encountered, it can then be de-compressed into the translated version of the code and processed by the native processor.

FIG. 1shows instructions a processor is capable of processing.FIG. 1shows native instruction set105such as an instruction set a processor can process. Set105may be a sequence of machine executable code or instructions, such as a computer “language” including all of the operations a processor (e.g., a type of processor, such as a processor capable of processing x86 instructions, x86 compiled instructions, assembly language, compiled assembly language, other compiled sets of instructions, or non-compiled higher-level language).FIG. 1also shows groups of code130including code to be compressed COMP CODE134, and code not to be compressed NON-COMP CODE136. Groups of code130(e.g., COMP CODE134, and NON-COMP CODE136) may be considered groups, types, and/or subsets (e.g., seeFIGS. 7 and 8) of a set of instructions (e.g., set105). In addition,FIG. 1shows native sequence of instructions160, such as a computer program having instructions from one instruction set a native processor can process (e.g., set105) or instructions in one “language,” and types of code180for native sequence of instructions160. Types of code180correspond to groups of code130on an instruction by instruction basis.

Native instruction set105may be a set of instructions used to generate sequences of instructions, such as a computer program to be “executed” or processed in a dynamic binary translation (DBT) environment by a native processor, as described above. Native instructions may be defined as instructions (e.g., a set of instructions such as set105or a sequence of instructions generated or produced using instructions of set105(e.g., see instructions160) that one processor (e.g., a native processor) is capable of processing, although that processor may not be capable of executing another different set of instructions or language

Native Instruction set105includes fields120having field A, field B, through field X. Fields120may include only one field, only two fields, only three fields, or any number of fields, such as where the number X is any number, such as a number equal to or greater than 100. For example, field A may be a field of an instruction that causes a processor to perform an operation or function (e.g., an opcode) and field B may be a field that includes information used when the processor performs the function or operation (e.g., an operand). Note that “opcodes” as used herein may be representative of operation codes of instructions, instructions, or other functional fields of instructions as know in the art. Moreover, “operands” as used herein may be representative of one or more operands that may be associated with each opcode including a full-length address, offset address, displacement address, absolute address, or other operand as known in the art. In addition, any or all of field A through field X may be a field having a constant of an instruction, and/or a constant length in the instruction. It is also contemplated that other fields of field120may include fields as described above with respect to field A and field B. It is considered that any instruction of set105may include any, all, or some of fields120.

For example,FIG. 1shows native instructions110of set105where field A is an opcode field, field B is an operand field, and field X is another field. Specifically, instructions110includes instructions111,112,113,114,115, and116. Instruction111includes opcode 1 and operand 1; instruction112includes opcode 2 and operand 2; instruction113includes opcode 3 and operand 3 and field X3; instruction114includes opcode 4 and operand 4; instruction115includes opcode 5 but no other field; and instruction116includes opcode 6 and operand 6. Moreover, instructions110may include instructions in addition to instructions111through116.

Opcodes of instructions110may include various functions such as a “move”, a “push”, a “pop”, a “call”, a “test”, a “je”, a “jne”, a “jmp”, a “add”, a “cmp”, a “xor”, a “ret”, a “mov”, a “inc”, a “lea” (e.g., see Tables 1-3 below). Opcodes of instructions110may also include instructions to perform other logic functions, an instruction to perform other arithmetic functions, an instruction to perform other data combinations, an instruction to perform other data movement, an instruction to read or write data, an instruction to delete data, and/or various other functions as known in the art.

In addition, operands of instructions110may include various formats, various lengths, more than one operand, a full-length address, an offset address, a displacement address, an absolute address, a register operand, a push operand, a memory operand, a destination register, a long address, a long displacement, and/or other operands as known in the art. Thus, an instruction may have an opcode and one or more operands that correspond to that opcode. Moreover, opcodes and/or operands of a sequence or set of instructions can be divided, selected, identified, or assigned into groups, types, and/or subsets. For instance, certain ones of a sequence or set of instructions may be selected to be in a specific group or type of instructions (e.g., such as to be in COMP CODE134, or NON-COMP CODE136).

For example, groups of code130ofFIG. 1includes code to be compressed COMP CODE134, and code not to be compressed NON-COMP CODE136that may each be considered a group, type, selection, or subset of instructions set105. Specifically,FIG. 1shows instructions of instructions110divided into groups of code130. It is also contemplated that groups of code130may correspond to instructions of native sequence of instructions160, such as is shown by types of code180. Instructions160includes region170and region172. Region170is shown having program counter values161,162,163,164,165and166for instructions of instructions110in region170(e.g., program counter values may be used by a program counter register in a computing device to point to memory or contain an addresses of memory containing an instruction of region170). For instance,FIG. 1shows corresponding instructions190listing which ones of instructions111-116of instructions110are in region170. Corresponding instructions190lists which ones of instructions111-116correspond to instructions for program counter values161through166. Code not to be compressed NON-COMP CODE136includes instructions111,114, and116. Code to be compressed COMP CODE134includes instructions112,113, and115.

FIG. 2shows a non-native instruction set and instructions a native processor is capable of processing in a DBT environment.FIG. 2shows non-native instruction set205such as an instruction set a processor that is not the native processor capable of processing set105, can process. Set205may be a sequence of machine executable code or instructions, such as a computer “language” including all of the operations a processor (e.g., a type of processor, such as a processor capable of processing code other than x86 instructions, or x86 compiled instructions).

In addition,FIG. 2shows non-native sequence of instructions260, such as a computer program having instructions from one instruction set a non-native processor can process (e.g., set205) or instructions in one “language,” and types of regions210for regions of non-native sequence of instructions260. For instance, set205and instructions260may be a set, software program, or sequence of non-x86 instructions to be run on a non-native processor capable of executing instruction set205, but unable to be executed by a native processor capable of executing instructions of set105, without a DBT environment, a DBT, a translator, an interpreter, and/or by an embedded microprocessor.

Native instruction set205may be a set of instructions used to generate sequences of instructions (e.g., having one or more regions of hot, cold, and/or warm code), such as a computer program to be interpreted, translated, executed, and/or processed in a dynamic binary translation (DBT) environment. Moreover, set205may include instructions that are used to generate a sequence of native instructions translated via a dynamic binary translation on an embedded microprocessor from a sequence of non-native instructions. Non-native instructions may be defined as instructions (e.g., a set of instructions such as set205or a sequence of instructions generated or produced using instructions of set205) that one processor is capable of processing, but that are to be executed or processed by another processor that is capable of processing a different set or sequence of instructions.

Moreover, depending on their opcode, instructions260may be grouped or divided into regions of code, regions of instructions, or regions of an instruction sequence. For example, the regions of instructions210may be divided into multiple “blocks” by one or more branch instructions delineating (e.g., separating, defining, or dividing) subroutines or “blocks” of instructions. In other words, the instructions or code between two branches or branch instructions may be described as a “block” of instructions. In some cases, a block of instructions may and/or be defined by (such as by having the beginning or end of the block at) a branch instruction jumping to a first or beginning instruction of the block (e.g., a branch instruction branching or pointing “into” the block). References to beginning, end, and next may refer to locations or position in a sequence of instructions, such as a sequence organized according to increasing program counter values, line numbers, instruction order in a sequence, and/or location in memory of instructions of the sequence of instructions). Also, a block of instructions may include and/or be defined by a branch instruction jumping away from a final or last instruction of the block (e.g., a branch instruction branching or pointing “out of” the block). Moreover, a block of instructions may include and/or be defined by a first or beginning instruction of the block that is the next instruction, after an instruction jumped to by a branch instruction. Finally, block of instructions may include and/or be defined by a first or beginning instruction of the block that is the next instruction, after an instruction jumped away from by a branch instruction. A region of instructions may be one or more blocks of instructions. In some cases, a “region” or a “region of instructions” may be a succession or sequence of one or more instructions or blocks of a program or of an instruction sequence to be interpreted, translated, processed, and/or executed in succession in a DBT environment or by a DBT.

For instance non-native sequence of instructions260includes region290, region292, region294, region296and298. Regions of instructions260may be or become different types of regions in a DBT environment, during translation by a DBT, during “execution” by a native processor, and/or during compression, as described herein. Types of regions210include hot code, warm code, and cold code that may each be a region of instructions260. Specifically, types of regions210identifies region290as warm code, region292as cold code, region294as hot code, region296as warm code and298as cold code.

In some embodiments, instructions in hot code regions may be instructions or regions of instructions of a sequence of instructions (e.g., a computer program) that are executed frequently at run time and consume a majority of processor clocks during execution of the sequence. For example, instructions in hot code regions may consume 70%, 80%, 85%, 90%, 95%, 96% or 98% of the processor clocks when executing a sequence of instructions. Specifically, a region of non-native instructions260may be identified, selected, or determined as hot code during “execution” or translation of instructions260by a DBT or in a DBT environment, after being encountered 10, 20, 30, 40, 100, 200, 300, 400, 1000, 2000, 3000, 4000, 10000, 20000, any combination thereof, or any number therebetween of times. Corresponding, instructions of cold code regions may be instructions or regions of instructions of a sequence of instructions executed infrequently at run time and that consume few of the processor clocks when executing the sequence. Instructions in cold code regions may consume 2%, 3%, 5%, 7%, 10%, 15%, or 20% of the processor clock when executing a sequence of instructions. Specifically, a region of non-native instructions260may be identified, selected, or determined as cold code during “execution” or translation of instructions260by a DBT or in a DBT environment, if not encountered more than 1, 2, 3, 4, 10, 20, 30, 40, 100, 200, 300, 400, 1000, any combination thereof, or any number therebetween of times. Next, instructions in warm code regions for a sequence of instructions may be all or a subset of the instructions that are not included in hot code regions or cold code regions.

In some cases, warm code may be identified or selected as code or regions of code that it would take more memory than desired to process as hot code, such as by compiling just-in-time; and code that would take more time than desired if it were grouped with cold code, such as by being interpreted during execution. Instead, for warm code, a compaction or compression scheme as described herein may be used by a DBT, or in a DBT environment to more efficiently handle the warm code such as by balancing the memory necessary for the compaction scheme and the time necessary to de-compact or de-compress the compressed warm code.

Instructions in warm code regions may include instructions or regions of instructions executed semi-frequently during execution or processing of a sequence of instructions. For example, warm code regions may include instructions that consume 3%, 5%, 7%, 10%, 12%, 15%, 17%, 20%, 22%, 25%, 27%, 30%, 33%, 35%, 37%, 40%, or 50% of a processor's clocks when executing a sequence of instructions. Specifically, a region of non-native instructions260may be identified, selected, or determined as warm code during “execution” or translation of instructions260by a DBT or in a DBT environment, after being encountered 10, 20, 30, 40, 100, 200, 300, 400, any combination thereof, or any number therebetween of times. In some cases, a cold code region may become a warm code region after being encountered 5, 7, 8, 10, 15, or 20 times; and a warm or cold code region may become a hot code region after being encountered 50, 70, 80, 100, 120, 150, or 200 times. Sometimes, cold code regions may become warm code regions after being encountered 10 times, and cold or warm code regions may become hot code regions after being encountered 100 times.

Sometimes, warm code regions may be selected as the next most frequent instructions or regions encountered in one set of instructions, other than the hot code regions, according to one or more programs or sequences of instructions. In some embodiments, the length of execution time required to execute an instruction or field (e.g., an opcode) or a region of instructions or fields may or may not be a factor to determine warm code regions.

As noted, if regions of warm code can be properly identified and “executed” in a DBT environment, execution performance can be improved. Specifically, the first time a region of warm code is encountered, it may be “executed” by being identified, translated (e.g., “just-in-time” compiled into native instructions), compressed into a compressed region of code, and the compressed region stored in a memory (e.g., code cache). The translated version of the code may be processed by the native processor, the first time the region of warm code is encountered.

When the compressed region of code is re-encountered, it can then be de-compressed into the translated version of the code and processed by the native processor. One or more tables stored in a memory (e.g., other than the code cache) may be used to assign compression codes the warm code for compression (e.g., compression tables), and to decompress the compressed code back to native compiled code during de-compression (e.g., de-compression tables).

According to some embodiments, the first time the region of warm code is encountered, the compressed region stored in a memory (e.g., code cache) may be de-compressed into the translated version of the code and processed by the native processor. In other words, in these embodiments, the same process above for re-encountering the compressed region may be performed to process the code, the first time the region of warm code is encountered.

The compressed code stored in a memory allows for quick reuse of the region by the processor. However, this requires enough memory to store the compression tables, the de-compression tables, and the compressed warm code regions. In some cases all or a portion of the compression and de-compression tables are permanently stored in the native processor for reuse during execution of multiple programs or sequences in the DBT environment, while the compressed warm code regions are stored for reuse only during “execution” of one sequence of non-native instructions in the DBT environment.

This memory requirement is tolerable because of the higher frequency of encountering or “executing” the regions of warm code (e.g., as compared to cold code) and the relatively small portion or succession of the sequence that is the regions of warm code (e.g., as compared to hot code). In other words, for warm code, it is more desirable to require more memory (compression and de-compression tables, and storage of compressed translated warm code regions) than for cold code (none of the warm code memory requirements), but less than for hot code (storage of uncompressed translated hot code regions); and to “execute” faster than interpreting for cold code, but slower than translating for hot code (because unlike the uncompressed translated hot code regions, the compressed translated warm code regions must be de-compressed prior to processing when re-encountered). More information about assigning codes and compression tables, is discussed below in conjunction withFIG. 4.

InFIG. 1, native sequence of instructions160is shown having region170through region172, such as regions of instruction including one or more instructions in each region. Regions170and172may correspond to regions290and292, respectively, ofFIG. 2. Thus, region170may be warm code, to be just-in-time (JIT) compiled into native compiled code and compressed, then de-compressed for processing by a native processor in a DBT environment. Alternatively, region172may be cold code, to be interpreted by a native processor in a DBT environment.

Specifically,FIG. 1shows region170including instructions for program counter values161,162,163,164,165and166. The instruction for program counter value161includes opcode 4 and operand 4. The instruction for program counter value162includes opcode 1 and operand 1. The instruction for program counter value163includes opcode 2 and operand 2. Also, the instruction for program counter value164includes opcode 5. Next, the instruction for program counter value165includes opcode 6 and operand 6. Finally, the instruction for program counter value166includes opcode 3, operand 3, and field X3.FIG. 1also shows corresponding instructions190listing the instructions of instructions110corresponding to instructions for program counter values161through166. Thus, region170may include one or more of the instructions of set105and may include more than one of each of the instructions included in set105. Specifically, where set105is a set of x86 instructions that a native processor is able to execute, sequence of instructions160may be a software program or sequence of the x86 instructions to be run on a native processor capable of executing instruction set105. Note that although instructions for program counter values161through166include the opcodes and operands from instructions110, the particular opcodes and operands of region170may vary from those of instructions110as required by the specific functionality desired of sequence of instructions160. For instance, where operands of instructions110may be generic or representative of types of addressing, operands of instructions160may include specific addresses. Thus, instructions of region170may be identified as part of a subset or group, such as those identified or groups of code130.

More particularly, region170is a warm code region and includes code to be compressed, and code not to be compressed. For instance,FIG. 1shows types of code180indicating to which instructions for program counter values161through166are to be compressed. Code to be compressed (e.g., corresponding to COMP CODE134) includes instructions112,115, and113corresponding to instructions for program counter values163,164, and166. Alternatively, code not to be compressed (e.g., corresponding to NON-COMP CODE136) includes instructions114,111, and116corresponding to instructions for program counter values161,162and165.

According to some embodiments, code not to be compressed NON-COMP CODE136, may be translated code or may be interpreted. Specifically, while code to be compressed COMP CODE134may be compressed translated compiled code (e.g., compiled from non-native code), code not to be compressed NON-COMP CODE136may be translated compiled code (e.g., compiled from non-native code) that is not compressed (e.g., it may be similar to the same translated instruction for hot code). Thus, during execution in a DBT environment, instructions for program counter values161,162, and165may be translated compiled instructions (e.g., compiled just-in-time like hot code). On the other hand, instructions for program counter values163,164, and166may be translated compiled instructions (e.g., compiled just-in-time code like hot code) that then has one or more fields of compressed information. During processing by the native processor, instructions for program counter values161,162, and165may be processed as they are (e.g., compiled just-in-time like hot code), but instructions for program counter values163,164, and166must be de-compressed into compiled native code (e.g., into just-in-time compiled code like hot code) for processing.

Selection of code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136of groups of code130and types of code180, may include using domain specific knowledge as well as other factors. More information about analyzing instruction sets and assigning codes and instructions to groups, is discussed below in conjunction withFIG. 4.

As noted, fields of code to be compressed (e.g., instructions of a region of warm code) may be separated and coded or compressed independently, such as using separate compression processes. For example,FIG. 3shows a compression table for compressing opcodes and operands.FIG. 3also shows an altered sequence of instructions including compressed opcodes and operands.FIG. 3shows compression table300including opcode compression table302for translating opcodes of an instruction, and operand compression table304for translating or compression operands of an instruction. Table302includes opcodes220and opcode compression codes230. Similarly, table304includes operands240and operand compression codes250. Opcodes220include opcodes2,3, and5. Corresponding to opcodes220, codes230includes code232corresponding to opcodes2, code233corresponding to opcode 3, and code235corresponding to opcode 5. Similarly, operands240includes operand 2 and codes250includes code252corresponding to operand 2. Thus, a first compression process, coding, type of code, or time at which compression codes are generated may be selected for table302as compared to table304. For example, codes230of table302may be identified for an instruction set, plurality of sequence of instructions, sequence of instructions, or region of instructions prior to “executing” or translating the non-native instructions in a DBT. Codes250of table304may be determined after translation or JIT compiling of the non-native code into native code has already begun. It is also considered that codes250may be determined prior to “executing” or translating, as described above for codes230. Compression of instructions or fields during “execution” or translation in a DBT environment may be described as “dynamically” compressing instructions, or fields thereof.

Table302may be constructed prior to or during compiling of non-native instructions in a DBT environment. Constructing a table may include generating, assigning, selecting, identifying and/or creating entries (e.g., instructions, opcodes and/or operands to be compressed, such as those of COMP CODE134of groups130and/or COMP of types180) and corresponding compression codes (e.g., as described below forFIG. 4). Table302may also be constructed prior to JIT compiling, translating, “executing”, processing, and/or compressing a sequence or a region of native compiled instructions in a DBT environment. Table304may be constructed prior to or during JIT compiling, translating, “executing”, processing, and/or compression of a sequence or a region of native compiled instructions in a DBT environment. For example, the tables (e.g., instructions, opcodes, operands, and/or compression codes) may created or assigned by a programmer, a person, a user, another computer program, a computer, or a machine that is or is not part of the DBT environment, such as prior to fixing table302or table304in a medium or memory. In some cases, compression codes (e.g., tables202and/or204) may be predetermined using dynamic profiling to identify code to be compressed in warm code regions prior to JIT compiling a region (or translating a sequence) of non-native instructions. Thus, the code to be compressed may be selected and the compression codes and tables may be constructed to be used by a device, software program, or other sequence of instructions to alter a sequence of non-native code at a subsequent time by replacing fields, such as opcodes and operands, of the native code with the compression code assigned to each field. An example of a flow diagram showing a process for constructing a table to compress sequences of instructions is discussed below in conjunction withFIG. 4.

With respect toFIG. 3, selecting opcodes220and operands240may also include profiling and execution considerations as described herein (e.g., seeFIG. 4). Selecting opcodes220may include selecting a set of opcodes that appear most frequently or that consume most of the clocks in sequences of instructions (e.g., such as benchmarks). For instance, when compressing a region of warm code, instructions283,284, and286may be selected to be compressed and appended as compressed code to the JIT compiled hot code and/or cold code. In some cases, instructions283,284, and286may be 3 instructions among 16 selected instructions of a set of native instructions or opcodes (e.g., of set105) to be compressed and appended as compressed code, to the JIT compiled hot code and/or cold code. For example, 4 bit uniform code length compression codes may be used to substitute in for, compress, or replace opcodes, fields, or instructions of native JIT compiled code instructions283,284, and286. An example of compressing opcodes is given below in the section Compressing Opcodes.

Moreover, selecting operands240may include selecting operands having a full length address, a long address, or a long displacement. In addition, selecting codes250may include selecting a 4 byte uniform length code providing base relative displacement according to a base address. Also, considerations for creating table304may include creating one or more “displacement tables” to exist in table304, due to the length of the operands to use base relative displacement so all displacements are non-negative, to use multilevel displacement so that different instruction types can have separate displacement tables, to have a separate displacement table for each opcode or each sequence of instructions, and/or to set a base address to begin positioning of a program. An example of compressing operands is given below in the section Compressing Operand Long Addresses.

It is also contemplated that table302and table304may be stored together, or separately, in the same, or separate storage locations or memories, such as random access memory (RAM), read only memory (ROM), software, machine executable instructions, media, optical media, magnetic media, or other information storage devices or processes.

FIG. 3also shows an altered sequence of instructions380including compressed opcodes and operands. Altered sequence of instructions380, may be a sequence of instructions including compressed instruction regions having compressed instructions or fields thereof. Specifically, instructions380includes header262for compressed region270, and header264for region272. Regions270and272may correspond to regions170and172, respectively, ofFIG. 1, and/or regions180and182, respectively, ofFIG. 2. Thus, region270may be warm code, JIT compiled into native compiled code and compressed, that may then be de-compressed for processing by a native processor in a DBT environment. Alternatively, region272may be cold code, to be interpreted by a native processor in a DBT environment. Header262and264may be inserted at the beginning of regions270and272to indicate that those regions have been compressed. The headers can be bit sequences that do not represent any legal instruction and may be followed by a bitmap in which each bit corresponds to an instruction in the corresponding region and indicates whether the corresponding instruction is compressed. For example, header262may be followed by a bit map having a bit corresponding to instruction281indicating that that instruction is not compressed, a second bit corresponding to instruction282indicating that that instruction is not compressed, a third bit corresponding to instruction283indicating that that instruction is compressed, a fourth bit corresponding to instruction284indicating that that instruction is compressed, a fifth bit corresponding to instruction285indicating that that instruction is not compressed, and a bit corresponding to instruction286indicating that that instruction is compressed. If a code region is not compressed, then the header and bit map may be absent. Compressed region270includes instructions281,282,283,284,285, and286.

FIG. 3also shows corresponding instructions190, which identify ones of instructions110corresponding to instructions281through286. Likewise,FIG. 3shows types of code180for instructions281through286. Thus, after altering region170of sequence of instructions160to compact, encode, code, compress, create, or form compress region270of instructions380, instructions283,284and286which are code to be compressed, are compressed. As shown, instruction281includes opcode 4 and operand 4, such as non-compressed native JIT compiled code. Instruction282includes opcode 1 and operand 1, and instruction285includes opcode 6 and operand 6, such as non-compressed native JIT compiled code. Alternatively, instruction283includes code232in place of, or as a compression of opcode 2; and code252in place of or as a compression of operand 2. For example, code232may include a 4 bit uniform code length code, and code252may be a 4 byte uniform length code. Similarly, instruction284includes code235instead of, or as a compression of opcode 5. Next, instruction286includes code233in place of or as a compression of opcode 3, operand 3, and field X3. For example, instruction286represents an instance where although opcode 3 has been compressed to code233, operand 3 has not been compressed. As shown, instructions283,284and286includes codes232,252,235, and233, such as compression codes for native JIT compiled codes. Thus, region170may be compressed into compressed region270according to table300.

FIG. 4is a flow diagram showing a process for constructing a table to compress sequences of instructions.FIG. 4may be a process to construct tables such as compression table300ofFIG. 3.FIG. 4shows process400including block410where execution and/or profile data is gathered and analyzed for a native instruction set. Block410may include gathering and analyzing execution and profile data as described above. Moreover, block410may include considering whether a specific compiled native instruction or a specific native sequence of compiled instructions is to be executed by a native processor.

Next, at block420, instructions of an instruction set are assigned to groups. Block420may correspond to assigning instructions of a set of instructions a processor can process to code to be compressed and code not to be compressed groups, or groups of code130. It is also contemplated that block420may include assigning instructions to only one group, such as code to be compressed as described herein.

At block430, codes are assigned to compress fields of the code to be compressed group. For example, block430may correspond to assigning compression codes to fields of instructions, such as opcodes and operands, as described above. Next, at block440, a table to compress sequences of instructions is constructed. For example, block440may correspond to constructing one or more tables (e.g., table302) to compress one or more fields of one or more instructions or regions of instructions of one or more sequences of instructions.

Various factors may be considered when performing blocks410-440. For instance one or more tables (e.g., from block440) may require storage in a memory (e.g., other than the code cache) to assign compression codes the warm code for compression (e.g., compression tables), and to decompress the compressed code back to native compiled code during de-compression (e.g., de-compression tables). Also, the compressed version of a warm code region may require storage in memory, prior to de-compression back into compiled native instructions during “execution”.

For example, selection of code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136of groups of code130and types of code180, ofFIGS. 1 and 3may include using domain specific knowledge such as characteristics of a particular machine language or set of instructions a native processor can process (e.g., set105). Also, code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136may be selected considering various factors including data from dynamic profiling, domain specific knowledge, memory size required, execution speed required, total execution time required, frequency of appearance of an instruction or field thereof (e.g., an opcode and/or operand), size of an instruction or field, number of occurrences of an instruction including certain fields in a sequence of instructions translated in a DBT environment. Furthermore, the above factors may be considered for regions of the sequence, and/or for a number of sequences of instructions (e.g., such as a test, analysis, or benchmark analyzing or providing analysis for more than one computer program), of a native instruction set a processor can process. Moreover, such determination may include a comparative analysis with respect to the other fields and instructions of a sequence and/or set of instruction, the other types fields and instructions of a sequence and/or set of instructions, and/or other factors of a DBT environment, and may include similar considerations as known in the art. Sometimes, the code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136instructions may be selected as the most frequent instructions or regions of one or more sets of instructions, according to one or more benchmark programs, or according to many sequences of instructions analyzed. Specifically such factors for selecting opcodes220may include selecting a set of opcodes that appear most frequently or that consume most of the clocks in sequences of instructions (e.g., such as benchmarks). In some embodiments, the length of execution time required to execute an instruction or field (e.g., an opcode) or a region of instructions or fields may or may not be a factor to determine code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136.

Also, selection of code to be compressed COMP CODE134and code not to be compressed NON-COMP CODE136can take into account a balance between factors, such as the amount of memory necessary to store the compression tables (e.g., memory for compression tables to compress native JIT compiled code into compression code), and the processing time necessary to perform de-compression (e.g., time necessary using identification or decompression tables to identify and de-compress the compressed codes). Such compression may also consider factors involved (e.g., time and memory required) for translating “hot” code (e.g., via just-in-time compiling), and factors involved (e.g., time and memory required) for interpreting “cold” code. For example, factors related to “hot” code and/or “cold” code DBT translation can be dynamically profiled and analyzed to select, identify, or predetermine JIT compiled native code to be compressed of “warm” code regions of a sequence of instructions (e.g., software program) prior to JIT compiling the warm code regions. The region may then be JIT compiled into native compiled code and compressed. In particular, after JIT compiling, a “warm” code region, that region may be altered or compressed using the compression table having codes assigned to one or more fields of each instruction of the “warm” code. Alternatively, “cold” regions may be interpreted during execution, and the “hot” regions may be JIT compiled and not compressed during execution.

Once the code to be compressed is selected or identified (e.g., as group COMP CODE134ofFIG. 1), a compression code may be assigned to each of the instructions, or one or more fields thereof. In embodiments, fields of the code or instructions to be compressed may be separated and coded or compressed separately or independently, such as using separate compression processes. In some cases, the compression code may be selected to compress opcodes, instructions, fields, compiled code, or executable code more efficiently than a general purpose compressor (e.g., more efficiently than Lempel-Ziv, or Huffman coding), such as by using a uniform length code to compress opcodes, operands, and/or other fields of an instruction. Moreover, the compression code can be selected considering a static inventory of instructions of a program or sequence of instructions, or a static inventory of an instruction set a processor can process.

For instance, profiling (e.g., dynamic profiling; and/or gathering and analysis of execution data for one or more programs, test data, benchmark data, etc. which may include such data or processes, as know in the art), analysis may be used to select fields of a language (e.g., set of instructions a processor is able to process or execute) to compress, and to assign compression codes therefore. Appropriate ways to perform such profiling, analysis, selection, and/or assignment may include automated methods (e.g., such as where a computer performs profiling analysis, selection and generates the codes). It is also considered that a person may perform the profiling, analysis, selection and/or assignment, such as using a manual, machine assisted, or computer assisted process. Thus, a completely automated system (e.g., without human intervention after setup), manual system, or mixture thereof can be used to profile, analyze, select and/or assign, by considering test, benchmark, and other data for a native language of a processor before a specific non-native program including that language is compiled or compressed in a DBT environment.

In some cases, the compression code may be a uniform length code, such as a code having two bits, four bits, six bits, eight bits, 12 bits, 16 bits, 20 bits, 32 bits, or n-bits where the number of instructions selected as code to be compressed is 2(n)instructions. A sufficient number of instructions selected for code to be compressed may be 4, 6, 8, 10, 12, 14, 16, 18, 20, 32, 64, 128, 256, 512, 1024, 2048, or a combination thereof of instructions. In some cases, the number of instructions selected for code to be compressed may be 16 instructions the compression code for opcodes of the selected instructions may each be a 4 bit code, and the compression code for a subset of operands of the selected instructions may each be a 4 byte code. Instructions may have compression code to compress each opcode into a 4 bit code, and to compress each of one or more operands of some opcodes into 4 byte codes or operand address (the operand compressions may be selected while “executing” the non-native program in the DBT environment).

For instance, according to some compression techniques, a pattern of or in a region of warm code may be compressed using a pattern substitution coding format where a text or character pattern is compressed using a pattern table containing a set of distinct patterns and their corresponding function values. Each function value is a special compression indicator character (code) which represents the compressed valued of a particular argument. Appropriate coding or compression may include or have a goal of compressing each pattern to a total code length that is “minimized”. Also, at de-compression time, the code may be used as an index into an identification or de-compression table, such that the corresponding pattern (e.g., the pattern compressed), or a different pattern is retrieved.

Compression techniques or systems considered include universal loss-less data compression, speed of compression (e.g., speed to perform pattern substitution), speed of de-compression, complexity of compression (e.g., how simple the pattern is for substitution), complexity of de-compression, and compression factor for regions, instructions, or fields of instructions of code to be compressed.

For instance, in a DBT environment, compression may be based on the independent compression of different fields of code to be compressed using compression tables, each having a goal of compression of an instruction or of a field of an instruction to a total code length that is “minimized” for storage and then de-compressed using de-compression tables. Also, compression may be based on the independent compression of different fields of code to be compressed using compression tables, each having a goal of compressing one or more regions of instructions to a total code length that is “minimized” for storage and then de-compressed. Moreover, factors involved in compression may include considering the design of the instructions to be compressed (e.g., design or sequence of code, data, or digits in the fields of instructions) and/or the frequency of appearance, encounter, invoking, issue of the instructions relative to each other in benchmark programs (e.g., see Table 1 below). Specifically, for an x86 instruction or an assembly instruction (e.g., “pattern”) opcodes and operands may be compressed, coded, encoded separately, independently or via independent compression predetermined by profiling of the opcodes and operands.

Thus, opcodes and operands of regions of compiled native code (e.g. regions selected as “warm” code) may be compressed and stored so that during execution the compressed code may be de-compressed, such as using de-compression tables, into a region of native compiled code more quickly than re-translation of the region (e.g., re-JIT compiling). Moreover, storage of the compressed warm code region, such as in a memory, will take less space, size, or storage resources than it would for an uncompressed version of the warm code region (e.g., less than the JIT compiled version prior to compression). Specifically, according to embodiments, warm code may be compressed, compacted, coded, or encoded into a smaller size or smaller region so that it takes less memory (e.g., less memory than it would to store the hot code compiled just-in-time data) when stored.

FIG. 5is a block diagram of a compactor to compress and/or compact code.FIG. 5shows environment500including compiled native region of instructions170(e.g., such as a region of warm code JIT compiled from non-native code) input into compactor520and compressed region570output by compactor520to be stored in memory580. Compactor520includes memory522and processor524. For example, memory522may store a set of instructions (e.g., instructions accessed, loaded, or read from a machine readable medium) that when executed by processor524, causes compactor520to compress instructions of region170into region570, such as according toFIGS. 3,5,7, and/or otherwise as described herein. Process500may occur during compiling, JIT compiling, scanning, translating, “executing”, and/or compacting of a region of warm code instructions.

Compactor520also includes sequence scanner525, such as to scan instructions170to determine whether instructions or regions of instructions thereof may be compressed. Compactor520also includes opcode compression table526such as a table to compress opcodes like table302. Compactor520also includes operand compression table528, such as a table to compress operand like table304.

In addition, compactor520includes operand compression table generator527, such as a generator for generating table528during scanning, translating, JIT compiling, or during compacting of instructions170. Thus, instructions170may be scanned by scanner525and operands thereof may be identified (e.g., such as long addresses) to build table528. Alternatively, table526may be preexisting, such as by being generated considering an instruction set a processor can process prior to compacting instructions170with compactor520.

Compactor520also includes sequence appender532, such as an appender to append compressed opcodes and operands to a region of instructions (e.g., region170prior to compression and region570after completion of compression, as described for process700ofFIG. 7) to create compressed region570. Also, compactor520includes header/bitmap generator534, such as a generator to generate headers and bitmaps to create region570, such as a compressed region, header, and bit maps as described above with respect toFIG. 3and region270, header262, and a corresponding bit map to a compressed region. Moreover, header/bitmap generator534may insert bitmaps and headers as described below with respect to blocks785and795ofFIG. 7.

FIG. 5shows compressed region570including region1and corresponding header for region1, header1. Headers and regions of region570may be compressed regions and headers therefore as described herein. For example, header1may correspond to header262as described with respect toFIG. 3, and region1may correspond to compressed region270as described above with respect toFIG. 3. Also, region1, header1may represent a number of adjacent or un-adjacent warm code regions of a sequence of instructions.FIG. 5also shows memory580, such as a memory for storing region570.

FIG. 6is a block diagram of a decompactor to de-compress, de-compact, and/or decode.FIG. 6shows environment600including compressed region570(e.g., such as a compressed region of warm code JIT compiled from non-native code) as input to de-compactor620and native region670as output from de-compactor620, such as for execution or processing by native processor680. Native region670may represent a number of adjacent or un-adjacent JIT compiled native warm code regions of a sequence of instructions for native processor680. De-compactor620includes memory622and processor624. Memory622may store a software program or machine executable instructions (e.g., instructions accessed, loaded, or read from a machine readable medium) to be executed by processor624to de-compact or de-compress region570into region670, such as according toFIGS. 3,6,8, and/or otherwise as described herein. Thus, other than the program sorted memory622, memory622and processor624may be similar to memory522and processor524described forFIG. 5.

According to some embodiments, processor680may include de-compactor620, region570, and/or memory580. As such, region570may be de-compacted while being executed by processor680, by having compressed regions of region570de-compacted by de-compactor620when encountered prior to or during the compacted regions execution by the processor. Native processor680may be a processor capable of executing a set or sequence of instructions, such as instructions170or a set, region, or sequence of instructions from which instructions160is a sequence (e.g., a program from set105). Also, processor680may be an embedded processor, a native processor, a processor in a DBT environment, or a processor unable to execute instructions160. However, processor680may be able to process or execute native sequence670.

De-compactor620also includes header/bitmap extractor634, such as an extractor for extracting headers and bitmaps of region570, such as to extract header262and bit maps as described above with respect toFIG. 3. Moreover, header/bitmap extractor634may extract headers and bitmaps as described below with respect to blocks810and830ofFIG. 8. De-compactors620also includes sequence ranger625, such as a ranger to determine the range of a region of region570according to header information extracted by extractor634. Moreover, ranger625may determine a range of a region as described below with respect to blocks820ofFIG. 8.

Next, de-compactor620includes native opcode identifier626, such as a de-compressor, de-compactor, interpreter, identifier, or compression table to identify native code, native compiled code, or native instructions for compression codes, compressed code, compressed instructions, opcode compression codes (e.g., codes230) in compressed regions of region570. For instance, identifier626may de-compress an instruction, and/or one or more opcodes as described above for table302ofFIG. 3.

De-compactor620also includes native operand identifier628, such as to de-compact, de-compress, identify, or decode compressed operands, operand compression codes (such as codes250) of region570(such as compressed regions) to create region670. Thus, identifier628may identify compiled native operands or other instructions to allow processor680to process region670. For instance, identifier628may de-compress an instruction, and/or one or more operands as described above for table304ofFIG. 3.

De-compactor620also includes sequence appender632, such as an appender to append native opcode, native instructions, and/or native operands to a region (e.g., region570prior to de-compression and region670after completion of de-compression, as described for process800ofFIG. 8) to create region670. Thus, after de-compactor620de-compacts region570, processor680may execute or process the native code of region670. Prior to being executed or processed, de-compressed native code670can be kept in a memory or storage other than the code cache.

Compactor520, memory522, de-compactor620, and/or memory622may include a machine accessible medium containing a sequence of instructions that when executed cause a machine (e.g., when executed by processor524cause compactor520; and/or when executed by processor624cause de-compactor620) to compress region of instructions170into region570, and to de-compress region570into region670as described herein. Specifically, memory522and/or622may include instructions that cause warm code opcodes of instructions170to be compressed using table526and a portion of the operands corresponding to the compressed opcodes to be compressed using table528, such as by separating the opcodes and operands and compressing each according to a different or independent compression technique, and de-compacting region570using identifier626and/or628to create region670. Moreover, compacting operands using table528may include indexing into a table of commonly used operands for a region of instructions, sequence of instructions, or set of instructions a processor is capable of processing.

The systems and components shown inFIGS. 5 and 6may represent electronic hardware, or software components and systems. For instance, environment500, environment600, compactor520, memory522, processor524, sequence scanner525, opcode compression table526, operand compression table528, operand compression table generator527, appender532, header generator534, memory580, de-compactor620, memory622, processor624, sequence ranger625, native opcode identifier626, native operand identifier628, sequence appender632, header extractor634, and/or native processor680may include one or more computer or electronic hardware and software components. Such components may include a processor, a memory to store an application (e.g., such as a software, source code, sequence of instructions, or compiled code application) to be executed by a machine or processor to cause an environment, compactor, de-compactor or components to perform the functions described herein. Moreover, an environment, compactor, de-compactor or components may be controlled by a computer or a machine, such as according to a machine accessible medium containing instructions (e.g., software, source code, or compiled code) that when executed by the computer or machine cause the computer or machine to control an environment, compactor, de-compactor or components to perform functions described herein.

Specifically, such components may include various logic circuitry, gates, computer logic hardware, memories (e.g., such as read only memory (ROM), flash memory, random access memory (RAM), flash memory, cache memory, firmware and/or other types of memory including electronic and/or magnetic media), comparators, data buffers, gates, flip-flops, and/or registers to perform functions described herein for the environment, compactor, de-compactor or components. Moreover, the environment, compactor, de-compactor and/or components thereof described above may include or access a machine accessible medium containing a first sequence of instructions that, when executed, causes a machine to perform functions described herein corresponding to the environment, compactor, de-compactor and/or components. In addition, it is contemplated that the function of the environment, compactor, de-compactor or components described above may be performed by a machine implemented method, such as a method implemented by hardware, software, a computer, a sequence of instructions, or according to a machine accessible medium as described above. In addition, according to embodiments, environment500, environment600, compactor520, de-compactor620, memory580, and/or processor680or components thereof may be part of a DBT environment or translator.

FIG. 7is a flow diagram showing a process for compressing a region of an instruction sequence.FIG. 7shows process700, such as a process for compacting a warm code native region of instructions160(e.g., region170) into a region of region570(e.g., region1or compressed region270). Process700may include descriptions such as according toFIGS. 3,5,6, a DBT environment, a DBT translator, and/or otherwise as described herein. At block710, operands of a region of an instruction sequence are scanned. For example, block710may correspond to scanner525scanning regions of instructions160as described forFIG. 5.

At block720, an operand compression table is created to compress a subset of operands. As noted forFIG. 3, opcodes and/or operands of a sequence or set of instructions can be divided, selected, identified, or assigned into groups, types, and/or subsets. For instance, certain ones of a sequence or set of instructions may be selected to be in a specific group or type of instructions (e.g., such as to be in COMP CODE134, or NON-COMP CODE136). Block720may correspond to generator527creating table528(e.g., table304as described forFIG. 3) as described above forFIG. 5.

At block730, opcodes of the region are scanned. For example, block730may correspond to scanner525scanning opcodes of a region of instructions160to determine whether the opcodes are included in table526, as described above forFIG. 5. At block740, it is determined whether the scanned opcode is one of the subset of opcodes to be compressed. For example, block740may correspond to determining whether an opcode or an instruction is group or type of code to be compressed (e.g., see group134COMP, and type180COMP). In some cases, block740includes determining or identifying of an instruction or opcode is in table302(e.g., one of opcodes220) ofFIG. 3, or is included in table526ofFIG. 5, as described above. If an instruction or opcode is not group or type of code to be compressed (e.g., see group136NON-COMP, and type180NON-COMP), it may not be necessary compress the instruction or opcode. Instead the instruction or opcode may be left as JIT compiled native code (e.g., the instruction or opcode was not selected to be compressed during process400ofFIG. 4). If at block740, the opcode is not one of the subset, processing continues to block775. Alternatively, if at block740the opcode is one of the subset, processing continues to block750.

At block750, the opcode is compressed using an opcode compression table. Block750may correspond to compressing an opcode or instructions as described above with respect to table302ofFIG. 3, region270ofFIG. 3, and table526ofFIG. 5, as described above. For instance, block750may include identifying, substituting, or switching a compression code of an instruction or opcode for a JIT compiled native instruction or opcode (e.g., substitute one of codes230for one of opcodes220ofFIG. 3). In some cases, the opcode compression table used at block750may be the opcode compression table used at block750may be the opcode compression table constructed at block440ofFIG. 4as described above.

At block760, it is determined whether the operand corresponding to the opcode compressed in block750is a subset of operands to be compressed. Block760may correspond to determining whether the operand is of an operand group or type to be compressed (e.g., similar to determining if an opcode is selected to be in group134COMP, and type180COMP). In some cases, block760includes determining or identifying of an operand is in table304(e.g., one of operands240) ofFIG. 3, or table528ofFIG. 5, as described above. If at block760, the operand is not one of the subset, processing continues to block775. Alternatively, if at block760the operand is one of the subset, processing continues to block770.

At block770, the operand is compressed using the operand compression table. Block770may correspond to compressing according to table304ofFIG. 3or table528ofFIG. 5as described above. For instance, block770may include identifying, substituting, or switching a compression code of an operand for a JIT compiled native operand (e.g., substitute one of codes250for one of operands240ofFIG. 3). In some cases, the operand compression table used at block770may be the operand compression table created at block720.

At block775, the appropriate data (e.g., including compressed and/or non-compressed fields) is appended to the sequence of instructions (e.g., a sequence starting as region170and ending as region570after process700) and a bit map is marked appropriately. Marking a bitmap may include activating a bit (e.g., such as by setting the bit to a “high” or a “1”); or inactivating a bit (e.g., such as by setting a bit to a “low” or a “0”), where the bit activate or deactivated corresponds to the instruction or opcode compressed. For example, block775may correspond to appending an instruction that has neither opcode nor operand compressed and marking a bit map appropriately, such as where block775is reached from block740. Alternatively, block775may correspond to appending an instruction with a compressed opcode and one or more operands not compressed and marking a bit map appropriately, such as where block775is reached from block760. Also, block775may correspond to appending an instruction with an opcode compressed and one or all operands compressed and marking a bit map appropriately, such as where block775is reached from block770. At block780, it is determined whether the region of the sequence of instructions if exhausted. If the region is not exhausted, processing returns to block740. Alternatively, if the region is exhausted, processing continues to block785.

At block785, the bit map for the region is inserted at the beginning of the compressed region. At block790, the range of the compressed region is determined. Information identifying the range of the compressed region may be contained in or stored in a range field of the header for the region. At block795, the header for the region is inserted at the beginning of the compressed region. For example, at block785, a header and a region of region570may be created, such as header262and region270as described with respect toFIG. 3.

It is contemplated that if at block780the region is not exhausted, processing may return to block740instead of block730, such as in the case where at block730all opcodes of the region are scanned at once.

FIG. 8is a flow diagram showing a process for de-compressing a compressed warm code region of a compressed instruction sequence.FIG. 8shows process800such as a process for de-compacting compressed region270having header262of region570to create a region having native compiled instructions of region670. Process800may include descriptions such as according toFIGS. 3,6,8, a DBT environment, a DBT translator, and/or otherwise as described herein. At block810, the header of a compressed region of a compressed instruction sequence is extracted. Block810may correspond to extractor634extracting a header of region570as described forFIG. 6.

At block820, the range of the compressed region is determined. Block820may correspond to ranger625determining the range of a compressed region (e.g., region270) of region570according to the header of that region (e.g., header262). Block820, may include reading or interpreting the information identifying the range of the compressed region contained in or stored in a range field of the header at block790ofFIG. 7.

At block830, the bit map for the compressed region is extracted. Block830may correspond to extracting the bit map placed at the beginning of the compressed region at block785.

At block835, the compressed code in the range is scanned. Block835may correspond to scanning the opcodes in the range and/or scanning as described above for block730ofFIG. 7.

At block840, it is determined whether the next instruction of the region is compressed. Block840, may include reading or interpreting the bit map extracted at block830.

If at block880the next instruction is not compressed, processing continues to block880. Alternatively, if the next instruction is compressed, processing continues to block845.

At block845, the next byte of the instruction is extracted.

At block850, it is determined whether the information in the extracted byte is sufficient to identify the native opcode or instruction. For instance, block850may include determining if there is enough bits extracted to identify a compression code for an instruction, opcode, and/or operand. In some cases, block850includes determining or identifying of an extracted code is in table300(e.g., one of opcodes220and/or operands240) ofFIG. 3, or is included in table526ofFIG. 5, as described above. If at block850the information is not sufficient, processing returns to block845. Alternatively, if at block850the information is sufficient, processing continues to block855. At block855, the native opcode or instruction is identified. Block855may correspond to identifying or substituting compiled native opcodes or instructions for compression codes as described above with respect to identifier626ofFIG. 6. For instance, block855may include identifying, substituting, or switching a JIT compiled native instruction or opcode for a compression code of an instruction or opcode, such as according to table302(e.g., substitute one of opcodes220for one of codes230)FIG. 3, or table526ofFIG. 5, as described above.

At block860, it is determined what the types of operands, their addressing modes, and the number of bits in the compact form is for the operands of the opcode or instruction of block855. For example, block860may correspond to determining if there are operands having long addresses, what the addressing mode of those operands are, as described for extractor634, ranger625, and identifier628ofFIG. 6. At block865, the operands are extracted, such as described for identifier628ofFIG. 6.

At block870, it is determined whether the extracted operand include indices into the operand table. Block870may correspond to determining if an operand contains an indice to an address table to fetch a long address. If at block870, the operand does not include an indice, processing continues to block880. Alternatively, if at block870the operand does include an indice, processing continues to block875. At block875, a native operand is identified. Block875may correspond to identifying a native operand is described for identifier628ofFIG. 6. In addition, block875may correspond to fetching a long address from an address table for an operand. For instance, block875may include identifying, substituting, or switching a JIT compiled native operand for a compression code of an instruction or operand, such as according to table304(e.g., substitute one of operands240for one of codes250) ofFIG. 3, or table526ofFIG. 5, as described above.

At block880, data (e.g., including de-compressed fields and/or fields that were not compressed during process700) is appended to the sequence of instructions (e.g., a sequence starting as region570and ending as region670after process800), such as described with respect to appender632ofFIG. 6. For example, block880may correspond to appending an instruction that did not have a compressed opcode, operand, or field (e.g., an instruction that is not warm code to the region or sequence of instructions, such as when block880is reached from block880). In this case, was not necessary to de-compress the instruction because the instructions was JIT compiled native code (e.g., the instruction was type NON-COMPRISES, or not compressed). Alternatively, block880may correspond to appending an instruction that had a compressed field or opcode and not has compiled native instructions in place of that code, but an instruction that does not have a compressed operand (such as an instruction that has cold code for an operand) to the region or sequence of instructions. Next, block880may correspond to appending an instruction that had a compressed opcode or field (such as an instruction now having compiled native code in place of the compacted opcode) and having at least one compacted operand (e.g., such as an instruction now having at least one compiled native code operand) to the region or sequence of instructions.

At block885, unused bits are given to the compacted code. Block885may correspond to a de-compactor (e.g., de-compactor620) extracting a sufficient number of bytes from the compacted code to identify an instruction or opcode (e.g., such as an x86 instruction). In some cases, only a portion of the extracted bytes of compacted code are necessary to identity the instruction or opcode, thus, the remaining part of the extracted compacted code is “unused” code that may be returned or given back to the compacted code (e.g., such as by re-appending to the compacted code at the location where they previously were). At block890, it is determined whether the region is exhausted. If at block890, the region is not exhausted, processing returns to block840. Alternatively, if at block890, the region is exhausted, decompression of the region is complete. For example, block890may correspond to producing a native region670, such as a region including compiled native code in place of compressed warm code operands and/or opcodes. Thus, after block890, the decompressed region (e.g., region670) may be processed at block895. For instance block895may include JIT compiled native code (e.g., region670) processed by a native processor (e.g., processor680, such as described with respect toFIG. 6).

The following is an example of selecting and compressing native code for DBT to an x86 processor, according to some embodiments. In this case, the native code or language may be executable by a processor that is unable to execute or process a set of instructions that can be executed by the x86 processor without translation, interpretation, a lookup table, etc., as described above (e.g., without the DBT environment). As noted above, selection and compression of warm code may also consider factors involved (e.g., time and memory required) for translating “hot” code (e.g., via just-in-time compiling), and factors involved (e.g., time and memory required) for interpreting “cold” code. For instance, the slow speed of interpretation raises an important question, i.e. when to interpret a code region and when to compile it instead. Obviously, if a code region is to be executed only once during the entire program execution, then it makes perfect sense to interpret. However, there may exist many code regions in a program which are executed thousands of times even though their run-time is a small percentage of the entire program execution.

For example, instance Table 1 lists the size and run-time for each code module in one benchmark of x86 instructions the BiQuad00 EEMBC benchmark, EEMBC:The New Benchmark Standard for Embedded Processors, Levy, Markus (EDN Magazine) and Weiss, Alan R.: (Motorola) Embedded Systems Conference, San Jose, November 1998. Moreover, other benchmarks may be considered and/or may show similar behavior. From these benchmarks, it can be observed that there exist a large number of code regions or modules which occupy significant memory. In each benchmark, a “warm” code region can be selected or identified where a region or module spends from 5% to 30% of the total execution time.

If the warm code accounts for just 5% of total execution time, with a slow-down factor of 70, the time to interpret the warm code will be 3.5 times as long as it takes to execute the entire program or sequence of instructions. Hence, the execution time of the entire program will be 4.5 times as long as it takes to execute the entire program directly. Even a slow-down factor of 20 would double the execution time of the entire program. In this case, performance can be increased (e.g., time to process reduced) by compressing or compacting the “warm” code instead of interpreting the warm code.

For instance, the warm code region can be compressed into a smaller region based on the issue frequency (e.g., percent of total execution time, or otherwise known in the art) and the design (e.g., number, type, and length, fields in the instructions) of the instructions in a DBT environment where a high level code region is compiled into an x86 code region. If a region is determined to be warm (but not hot) according to a certain profiling study, then the warm code region is compressed into a smaller region and stored in memory. Each time the program execution proceeds to a compressed code segment, e.g. when it invokes a compressed function, the compressed code can be de-compressed before being executed.

Moreover, the de-compressed code can be kept in a memory or storage other than the code cache. In these cases, it may be assumed or expected that the de-compressed code region will not be executed soon in the future. Also, if such a code region were saved in the code cache, it may be replaced soon anyway. Even when not stored in the code cache, the compressed code takes much less time to de-compress and execute than to be interpreted.

Each x86 instruction (including both the opcode and the operands), or fields thereof (e.g., by separating the opcodes and the other fields including operands of various formats) may be viewed as a pattern. Separating the fields can be defined as a practice called “independent compression of different fields.” For x86 programs, two main sources of opportunities for compressing x86 machine code, are the opcode and the full-length addresses that appear in the operands. According to embodiments, the compression or coding of fields of the native program (e.g., the coding format) may consider the appearance frequency of each pattern such that the total code length for the fields is “minimized”.

For example, the appearance frequency of different opcodes can be ranked. Table 2 lists the top 19 opcodes and their appearance frequency (in percentages) in benchmark programs. Herein, reference to “benchmark programs” or “benchmarks” may refer to a single benchmark program or more than on benchmark program (or the execution or run data of the benchmark program(s)). For instance, numbers, percentages, or other information described for “benchmark programs” or “benchmarks” may refer to numbers, percentages, or other information combined by addition, averaging, statistical combination, or another mathematical combination of data derived or gathered from one or more benchmark programs. Of the 19 opcodes, the top 16 opcodes together account for 66% of total instruction appearances in the benchmark programs. The pattern distribution is very similar across different applications in the benchmark suite.

The “profile” shown above can be collected by text matching in the assembly code and/or the machine code. Nonetheless, instructions with different number of operands can be considered different patterns. Such instructions normally have different opcodes. Hence, the statistics can be reasonably accurate.

For instance, the benchmarks may contain over 33500 move instructions which begin with the byte “8B” and may contain 12693 move instructions which begin with the byte “89”. A large number of these may use an index register to access the memory. Thus, such instructions can be one group that four bits can be used to identify. Among these those using the esp as the index register can be treated specially and put in a “move-esp” category, because they are longer than the rest, which use an index register.

Additionally, the benchmarks contain instructions that move from register to register and begin with the byte “8B”, which can be placed in the same group with three other instructions that are register to register.

It is noted that the xor instruction is mostly used to clear a register operand, and the test instruction is mostly used to make sure a pointer is null. Each of these is a two-operand instruction, even though both operands are identical when the instructions are used for the purpose stated above. Therefore, in the compression codes for these instructions, only one register needs to be identified. Furthermore, 4 bits can be used to represent both xor and test.

Also, 4 bits can be used to represent both add3 and push2 instructions. In addition, 4 bits can be used to represent both cmp3 and lea3 instructions. The inc instruction has just a single byte, which includes the register number. So, in some cases, it cannot be shortened further and may be removed from the list.

The instruction push1 (push one operand) usually appears in a group of four at the very beginning of a called function. Four registers may be saved by these instructions as a part of the calling sequence. Correspondingly, four pop1 instructions are executed immediately before the call returns. Since it is usually the same registers that are saved and restored, those four push1 instructions can be replaced by a code and those four pop1 instructions by another. From this point of view, each 4-instruction sequence appears with a frequency of 0.09/4=0.0225.

The benchmark program may contain 14400 instructions which have both operands in the registers. Among these, over 9400 instructions can be mov, 2140 can be cmp, 1900 can be add, and 1000 can be sub. Four bits can be used to represent the group which contain all these instructions. This group (called reg-reg) can therefore account for 4.8% of all the instructions.

Based on the discussions above, a revise frequency chart (Table 3) follows:

According to Table 3, at least 4 bits can distinguish 16 patterns, and 5 bits or more can distinguished more patterns. The opcode of x86 instructions often consists of 8 bits only. Hence, one choice is to compress only the top 16 patterns (e.g., 2(n)instructions or opcodes) using 4 bits (e.g., n bits). It is also considered that the number of top patterns or opcodes chosen or selected to be compressed, is a power of two, such as 2(n)instructions where the compression code is a uniform length code of n-bits. The rest of the patterns may be left un-compressed (e.g., treated as hot or cold code).

To tell a DBT decoder whether an instruction is compressed or not, a bit-map may be used at or in the beginning of each compressed code region. Here, within each compressed code region (e.g., warm code region), compressed instructions can be distinguished from those not compressed using a single bit of the bit-map for each instruction in the compressed region to indicate whether the instruction (or the sequence of instructions) is compressed or not. Thus, in effect, x+1 bits are used to compress each instruction in the compressed region, where x is the average number of bits to encode a pattern (e.g., opcode and possibly operands), and the +1 is the indicating bit of the bit-map.

According to embodiments, a header can be inserted in the beginning of a code region that has been compressed. Such a header can be a bit sequence that does not represent any legal instruction (e.g., any instruction the processor is to process, such as an instruction including an opcode). This header can be followed by a bitmap in which each bit corresponds to an instruction in the code region. The bit indicates whether the corresponding instruction is compressed. If a code region is not compressed at all, then no such header is inserted. The dispatcher in the DBT driver can hence simply examine the first byte of a code region to determine whether de-compression should be performed.

In the following section, we present details of implementing the 4-bit coding scheme, according to some embodiments. The bit-string assigned below to each pattern may be arbitrary.

The overwhelming majority of call instructions in the benchmark may be call direct instructions. The opcode E8 is followed by a 32 bit displacement. The opcode and the displacement are compressed separately in the scheme. The displacement compression uses a displacement table such that frequently used displacements can be replaced by a shorter index in the compression code.

If the displacement is reduced to x bytes, the 40 bits of the entire call instruction are compressed into 4+8x bits.

The disp field represents a 1-byte displacement. The opcode 8B is for memory-to-reg movement, and the opcode 89 is for reg-to-memory movement. In the compression code we use a single bit d to indicate the movement direction. Thus, the compression code may be:0001 d reg disp

This takes two bytes instead of four bytes.

This category includes instructions which have both operands in the registers. According to benchmarks, among these, over 9400 instructions may be mov, 2140 may be cmp, 1900 may be add, and 1000 may be sub. An instruction format may be:

In the above, OP is the opcode (OP=2B for sub; OP=03 for add; OP=3B for cmp, and OP=8B for mov.) These instructions may be compressed into the following form:

In the above, the two bits xy selects one out of the four kinds of instructions.

The overwhelming majority of the test instructions and xor instructions in the benchmark programs are those having two identical register operands. This is used to verify whether the resister value is null.

In some cases, reg1=reg2, and 3 bits can be sued to identify the register. Thus, a compression code may be:

0011 a reg

If a=1, it is the test instruction. Otherwise, it is the xor instruction.

In some cases, a majority of jne and je instructions use 8-bit displacement. The instruction's binary format may be:

75 xx for jne and 73 xx for je

Where xx is the displacement. It is considered that such a short displacement may not be compressed. For example, the je (or jne) opcode (1) may be compressed into four bits followed by the 8-bit displacement, or (2) may be compressed only when the displacement can be fit into 4 bits. Choice (1) covers more cases, but the decoding in the DBT will be somewhat more complex since the compression code is no longer byte-aligned. Case (2) may be preferred in some embodiments.

These two kinds of push instructions push a memory operand, using the current esp or ebp as the index register, into the stack:

When esp is used as the index register, the leading bit of xx may be 0. When ebp is used as the index register, the leading bit of xx may mostly be 0. Hence, these two kinds of push instructions may be grouped together, using the leading bit to distinguish between the two.

The compressor or compactor in the DBT must be careful with verifying the leading bit. Specifically, if ebp is the index register, which the decoder should know by seeing FF75, the decoder should look at the leading bit of xx. If it is 0, it can be compressed into the format list here below. However it the leading bit of xx is 1, then it may not be compressed, in some cases.

One compression format may be:

where the bit a distinguishes between the two cases (esp vs. ebp) and yyyyyyy is the last 7 bits of xx.

According to some benchmarks, the overwhelming majority (over 90%) of the unconditional jump conditions are jump short:

EB xx

The instruction size can be reduced by 4 bits, assuming the code is compressed to 0111 followed by the displacement.

The string of 1000 represents the following sequence of instructions which may routinely appear in the beginning of a function as part of the calling sequence:

Listed alongside the assembly code is the opcode in Hexidecimal numbers. In the sub instruction, #n may be a positive integer. Normally #n is quite small although it is represented by 32 bits in the instruction. If #n can be represented by four bits, #n can be packed with 1000 to make a full byte. If #n requires more than four bits the bits “0000” can be packed with the compress opcode 1000, and an instruction of “Sub esp #n” can be inserted immediately after the Push1 pattern. Note that “Sub” may not be compressed under the current scheme.

With this pattern, either 4 or 10 bytes can be compressed into a single byte.

The string of 1001 represents the following sequence of instructions which routinely appear immediately before the “ret” instruction as part of the returning sequence.

Again, if #n can be represented by four bits, #n can be packed with 1001 to make a full byte. Otherwise, 0000 can be packed with 1001 and an instruction of “Add esp, #n” can be inserted immediately before the Pop1 pattern.

With this pattern, either 4 or 10 bytes can be compressed into a single byte.

Some benchmark programs contain about 11360 add instructions. Among these, 7430 instructions are of the form “83C(hex) 0xxx(bin) YY”, where xxx indicates a register and YY is a byte-size integer. Interestingly, 4530 among the 7430 add instructions are of the form “83 C4 YY”, which add YY to the esp register.

Two choices of encoding are explored. One is to use the code “1010” to represent the prefix “83C(hex)0(bin)”. Then append xxx to “1010”. The number YY is not compressed. In the other choice, use the code “1010” to represent “83 C4”. The first choice takes 16*7430=118880 bytes to represent those 7430 “83 Cx” add instructions. The second choice takes 12*4530+24*2900=123960 bytes. Hence, the first choice may be used with a reduction rate of 33%.

Since xxx has only three bits, we have another bit to spare. The push2 instruction is similar to add3 in the formation (The push2 instruction has the bit pattern of “6A YY”, where YY is a byte-sized integer). Hence, push2 can be merged with add3, and a bit, a, can be used to distinguish them.

The compressed representation may be:

1010 a=0 reg YY for Add3 or

This group of push instructions is in the form of:

where disp32 is a 4-byte address. This form may be represented by the compress code:

where “index” is an index to a displacement table of long addresses of operands.

The opcode C3 can be represented in the compression code by “1100”.

This set of move instructions may be in the forms of:

where the 3-bit reg selects a register, yy is a byte-size offset, disp24 a 3-byte displacement, and disp32 a 4-byte displacement.

This form may be represented by a byte “1101 a reg” which is followed by additional operands. If a=1, then it is in the form of “C74” and the byte is followed by yy and disp24. If a=0, then it is in the form of “C70” and the byte is followed by disp32.

Some benchmark programs contain about 16300 cmp instructions. Among these, 4370 are of the form “3B(hex)11 reg1 reg2(bin)”, and another 4024 are of the form “83 F(hex) 1 reg yy” where reg is a three bit register number and yy is a byte-size integer”.

The benchmark programs also contain about 10550 lea instructions. Among these, more than 5000 are of the form “8D(hex) 01 reg1 reg2(bin)”.

The compression code “1110” can be used to represent all the forms mentioned above by:

If a=1, then it is the “83F” form of the cmp instruction. The byte-size integer follows the bits “1110 1 reg1”. If a=0, then the next byte “b reg2” can be examined. If b=1, then it is the “3B” form of the cmp instruction. If b=0, then it is the “8D” form lea instruction.

Some benchmark programs contain over 33500 move instructions which begin with the byte “8B”. Within these, we have encoded the “mov-esp” and “move register to register” instructions. Among the remaining 17800 “8B” move instructions, 16600 may be of the form:

In the above, reg1 is the destination register and reg2 is the index register used in the memory load operation. YY is a byte-size integer used as the offset.

Similarly, the benchmark programs may also contain 11979 instructions which move from a register to a memory location. These may be in the form of:

Finally, some benchmark programs may contain 2390 move instructions which move immediate data to a memory location using a register as the index. These instructions can be in the form of:

In the above, reg is the index register, YY is the offset, and ZZ ZZ ZZ is a three-byte immediate data.

These instructions can be grouped together and represented in the following form:

If a=0 then the instruction is “C74” and it ends at reg1. If a=1, then additional operands can be looked for. If b=0, the instruction is “8B”. Otherwise it is “89”.

Thus, opcodes of x86 compiled warm code may be compressed according to an opcode compression table (e.g., see table302ifFIG. 3) set up using the coding above. The compressed warm code can be stored so that during execution the compressed warm code can be de-compressed, such as using an opcode identification or de-compression table to de-compress the compressed opcodes into native code (e.g., non-x86 instructions) more quickly than by translation (e.g., re-JIT compiling) or by interpretation of the warm code. Using benchmark programs, opcode compression and de-compression (e.g., identification) tables can be setup in a DBT environment (e.g., such as by storing the tables and/or software to perform the compression and de-compression) prior to compiling or even receiving native programs in the DBT environment (e.g., seeFIGS. 7 and 8).

In addition, the operands may be compressed for instructions having or not having compressed opcodes. Operands of warm code may be compressed according to an operand compression table (e.g., see table304ifFIG. 3), and stored so that during execution the compressed warm code can be de-compressed, such as using an operand identification or de-compression table to de-compress the compressed operands into native code, operand information, or addresses more quickly than translation (e.g., re-JIT compiling) or by interpretation of the warm code. Such operand compression and tables can be setup in a DBT environment (e.g., such as by storing the tables and/or software to perform the compression and de-compression) prior to or during translation (e.g., JIT compiling) and/or compression of warm regions, opcodes, and/or after receiving native programs in the DBT environment (e.g., seeFIGS. 7 and 8).

Compressing Operand Long Addresses

This section describes factors considered to select, or during compression and de-compression of, warm code operand long addresses. For instance, for de-compression of compressed warm code according to embodiments, after decoding the opcode, the DBT driver determines which operand is a long address (or a long displacement). In the compression code, the long address is represented by an index to a table (called the displacement table or the address table, such as native operand identifier628ofFIG. 6, such as to identify a native operand as described for block875ofFIG. 8).

Profiling may be used to determine whether each opcode, each function, and/or each code module should have its own displacement table (e.g., table304, and/or native operand identifier628ofFIG. 6, such as to identify a native operand as described for block875ofFIG. 8). Nonetheless, it is contemplated that at least each individual program (e.g., sequence of instructions) can have its own displacement table.

To reduce the size of the displacement table, any or all of the following measures may be taken:

1. Although x86 machine code normally uses program counter relative displacement, base-relative displacement may be used for the compression code for operands. This is because a base can be found such that all the displacements are nonnegative, making the displacements share more common bits.

2. The displacement table can have multiple levels. Whether different instruction types should have their separate displacement tables may depend on profiling studies. For benchmark programs, a single table and a single base address may be sufficient.

3. The beginning position of the program may be chosen as the base address. In the benchmarks, e.g., the base address is always 00400000(hex). Here, the first four hexadecimal digits may be appended by an x-bit displacement-table index and a y-bit offset. For simplicity of illustration, let y=8.

4. During the compression time, some optimal choices for x and y may be determined as follows:

4.1 Within a range of possible values of x, e.g. 2<x<8, an optimal choice may be obtained by considering x from the low value to the high value. The offset table can contain 2xentries. A greatest number z can be found such that all prefixes of the length z have no more than 2xvarieties. The compression benefit is thus z−x.

4.2 A value for x may be selected which gives the maximum value of z−x>0.

The DBT may compress one warm code region at a time without necessarily knowing the patterns of the rest of the program. Thus, various systems or methods may be used to dynamically determine one or more compression tables to compress and identification or displacement tables (e.g., such as tables shared by the entire program) to compress and de-compress operands as described above.

A Compression Ratio Using 4-Bit Code

This section describes a compression ratio for instructions using a 4-bit compression code for opcodes and the operand long address compression scheme described above in the Compressing Opcodes and Compressing Operand Long Addresses sections. Also, note that in some embodiments, operands are not compressed for instructions which would only have compressed operands, but are not compressed at all instead (e.g., resulting in an instruction without compressed opcode or operand). For example, operands will not be compressed for instructions in which at least one field other than an operand, such as opcode, will not be compressed. This may be because it is yet unclear how much a long addresses (or displacements) can be compressed in these cases, and since it is a rather complex matter to define the length of the opcode. Hence, in some embodiments:

For call5 instructions, the 8-bit opcode is reduced to 4 bits.

The move-esp pattern have the register esp implied. Reduce 32 bits to 16 bits.

For Jne and Je instructions, reduce 16 bits to 12 bits.

Assume all push1 and pop1 instructions are in the push sequence and the pop sequence, respectively. Without compression, each push or pop pattern takes 32 bits in the instructions. Reduce them to 4 bits.

For add3, reduce 24 bits to 16 bits. For push2 instructions reduce 16 bits to 12 bits.

For push5 and ret instructions, reduce 8 bits to 4.

For mov5 instructions, ignore the long displacement. Reduce 24 bits (or 16 bits in the case of “C70”) to 16 bits (or 8 bits in the case of “C70”).

For cmp and lea instructions, either reduce 16 bits to 12 bits, or reduce 24 bits to 16 bits.

Multiplying the estimated number of bits by the frequencies in Table 2, get the average number of bits before compression

After compression, on average

If, however, those instructions not compressed are included, and assume they are 8 bits each, then:

The compression scheme on techniques above for x86 compiled code result in an estimate saving of 39.4% during execution of a sequence of instructions, based on the profiling information collected from one set of existing x86 sequences of instructions, and if the rest of the potential operands are ignored in the savings analysis. Of course, this is an estimate and actual results will vary depending on how many there are and how much the other operands can be compressed.

Also, in the DBT environment, a translator can be allowed to generate (e.g., compile) the x86 compiled code using the 16 patterns as much as possible. In other words, the translation or compiling of non-native code to native code can be performed in such a manner that the resulting native code has an increased instance of using the 16 patterns (e.g., of instructions in type of code COMP of types180ofFIG. 3). This will increase the appearance frequency of those patterns in the DBT environment. Specifically, the increase in appearance of those patterns may be considered in selecting the instructions and/or instruction regions that will be warm code. It is also contemplated to look for other common instruction sequences, other than the 16 above, which can be replaced by a compression code as described herein.

Although descriptions above, including with respect toFIGS. 1-8, are with respect to opcodes and operands of native x86 compiled instructions, the concepts can be applied to other fields of x86 instructions, other compiled instructions, other native instructions, and/or other languages or sets of instructions. Also, the concepts described herein may be applied using other coding systems. Specifically, other uniform length codes may be used to code the opcodes, and/or operands. In some cases a uniform length code that increases in binary count for each opcode or operand encoded may be used. It is also considered that the concepts described herein may be applied to other translation environments where one or more instructions are to be translated from a language or instruction set of one processor to a different language or instructions set of a different type or processor.

In the foregoing specification, specific embodiments are described. However, various modifications and changes may be made thereto without departing from the broader spirit and scope of embodiments as set forth in the claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.