Abstract:
A fixed number of variable-length instructions are stored in each line of an instruction cache. The variable-length instructions are aligned along predetermined boundaries. Since the length of each instruction in the line, and hence the span of memory the instructions occupy, is not known, the address of the next following instruction is calculated and stored with the cache line. Ascertaining the instruction boundaries, aligning the instructions, and calculating the next fetch address are performed in a predecoder prior to placing the instructions in the cache.

Description:
BACKGROUND  
       [0001]     The present invention relates generally to the field of processors and in particular to a processor having an instruction cache storing a fixed number of variable length instructions.  
         [0002]     Microprocessors perform computational tasks in a wide variety of applications, including portable electronic devices. In many cases, maximizing processor performance is a major design goal, to permit additional functions and features to be implemented in portable electronic devices and other applications. Additionally, power consumption is of particular concern in portable electronic devices, which have limited battery capacity. Hence, processor designs that increase performance and reduce power consumption are desirable.  
         [0003]     Most modern processors employ one or more instruction execution pipelines, wherein the execution of many multi-step sequential instructions is overlapped to improve overall processor performance. Capitalizing on the spatial and temporal locality properties of most programs, recently executed instructions are stored in a cache—a high-speed, usually on-chip memory—for ready access by the execution pipeline.  
         [0004]     Many processor Instruction Set Architectures (ISA) include variable length instructions. That is, the instruction op codes read from memory do not all occupy the same amount of space. This may result from the inclusion of operands with arithmetic or logical instructions, the amalgamation of multiple operations into a Very Long Instruction Word (VLIW), or other architectural features. One disadvantage to variable length instructions is that, upon fetching instructions from an instruction cache, the processor must ascertain the boundaries of each instruction, a computational task that consumes power and reduces performance.  
         [0005]     One approach known in the art to improving instruction cache access in the presence of variable length instructions is to “pre-decode” the instructions prior to storing them in the cache, and additionally store some instruction boundary information in the cache line along with the instructions. This reduces, but does not eliminate, the additional computational burden of ascertaining instruction boundaries that is placed on the decode task.  
         [0006]     Also, by packing instructions into the cache in the same compact form that they are read from memory, instructions are occasionally misaligned, with part of an instruction being stored at the end of one cache line and the remainder stored at the beginning of a successive cache line. Fetching this instruction requires two cache accesses, further reducing performance and increasing power consumption, particularly as the two accesses are required each time the instruction executes.  
         [0007]      FIG. 1  depicts a representative diagram of two lines  100 ,  140  of a prior art instruction cache storing variable length instructions (I 1 -I 9 ). In this representative example, each cache line comprises sixteen bytes, and a 32-bit word size is assumed. Most instructions are a word width, or four bytes. Some instructions are of half-word width, comprising two bytes. A first cache line  100  and associated tag field  120  contain instructions I 1  through I 4 , and half of instruction I 5 . A second cache line  140 , with associated tag field  160 , contains the second half of instruction I 5 , and instructions I 6  through I 9 . The instruction lengths and their address are summarized in the following table:  
                                 TABLE 1                           Variable Length Instructions in Prior Art Cache            Instruction   Size   Address   Alignment               I1   word   0x1A0   aligned on word boundary       I2   word   0x1A4   aligned on word boundary       I3   halfword   0x1A8   aligned on word boundary       I4   word   0x1AA   misaligned across word boundaries       I5   word   0x1AE   misaligned across cache lines       I6   word   0x1B2   misaligned across word boundaries       I7   word   0x1B6   misaligned across word boundaries       I8   halfword   0x1BA   not aligned on word boundary       I9   word   0x1BC   aligned on word boundary                    
         [0008]     To read these instructions from the cache lines  100 ,  140 , the processor must expend additional computational effort—at the cost of power consumption and delay—to determine the instruction boundaries. While this task may be assisted by pre-decoding the instructions and storing boundary information in or associated with the cache lines  100 ,  140 , the additional computation is not obviated. Additionally, a fetch of instruction I 5  will require two cache accesses. This dual access to fetch a misaligned instruction from the cache causes additional power consumption and processor delay.  
       SUMMARY  
       [0009]     A fixed number of variable-length instructions are stored in each line of an instruction cache. The variable-length instructions are aligned along predetermined boundaries. Since the length of each instruction in the line, and hence the span of memory the instructions occupy, is not known, the address of the next following instruction is calculated and stored with the cache line. Ascertaining the instruction boundaries, aligning the instructions, and calculating the next fetch address are performed in a predecoder prior to placing the instructions in the cache.  
         [0010]     In one embodiment, a method of cache management in a processor having variable instruction length comprises storing a fixed number of instructions per cache line.  
         [0011]     In another embodiment, a processor includes an instruction execution pipeline operative to execute instructions of variable length and an instruction cache operative to store a fixed number of the variable length instructions per cache line. The processor additionally includes a predecoder operative to align the variable length instructions along predetermined boundaries prior to writing the instructions into a cache line. 
     
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0012]      FIG. 1  is a diagram of a prior art instruction cache storing variable length instructions.  
         [0013]      FIG. 2  is a functional block diagram of a processor.  
         [0014]      FIG. 3  is a diagram of an instruction cache storing a fixed number of variable length instructions, aligned along predetermined boundaries. 
     
    
     DETAILED DESCRIPTION  
       [0015]      FIG. 2  depicts a functional block diagram of a representative processor  10 , employing both a pipelined architecture and a hierarchical memory structure. The processor  10  executes instructions in an instruction execution pipeline  12  according to control logic  14 . The pipeline includes various registers or latches  16 , organized in pipe stages, and one or more Arithmetic Logic Units (ALU)  18 . A General Purpose Register (GPR) file  20  provides registers comprising the top of the memory hierarchy.  
         [0016]     The pipeline fetches instructions from an Instruction Cache (I-cache)  22 , with memory addressing and permissions managed by an Instruction-side Translation Lookaside Buffer (ITLB)  24 . A pre-decoder  21  inspects instructions fetched from memory prior to storing them in the I-cache  22 . As discussed below, the pre-decoder  21  ascertains instruction boundaries, aligns the instructions, and calculates a next fetch address, which is store in the I-cache  22  with the instructions.  
         [0017]     Data is accessed from a Data Cache  26 , with memory addressing and permissions managed by a main Translation Lookaside Buffer (TLB)  28 . In various embodiments, the ITLB  24  may comprise a copy of part of the TLB  28 . Alternatively, the ITLB  24  and TLB  28  may be integrated. Similarly, in various embodiments of the processor  10 , the I-cache  22  and D-cache  26  may be integrated, or unified. Misses in the I-cache  22  and/or the D-cache  26  cause an access to main (off-chip) memory  32 , under the control of a memory interface  30 .  
         [0018]     The processor  10  may include an Input/Output (I/O) interface  34 , controlling access to various peripheral devices  36 . Those of skill in the art will recognize that numerous variations of the processor  10  are possible. For example, the processor  10  may include a second-level (L 2 ) cache for either or both the I and D caches  22 ,  26 . In addition, one or more of the functional blocks depicted in the processor  10  may be omitted from a particular embodiment.  
         [0019]     According to one or more embodiments disclosed herein, the processor  10  stores a fixed number of variable length instructions in each cache line. The instructions are preferably aligned along predetermined boundaries, such as for example word boundaries. This alleviates the decode pipe stage from the necessity of calculating instruction boundaries, allowing higher speed operation and thus improving processor performance. Storing instructions this way in the I-cache  22  also reduces power consumption by performing instruction length detection and alignment operation once. As I-cache  22  hit rates are commonly in the high 90%, considerable power savings may be realized by eliminating the need to ascertain instruction boundaries every time an instruction is executed from the I-cache  22 .  
         [0020]     The pre-decoder  21  comprises logic interposed in the path between main memory  32  and the I-cache  22 . The pre-decoder  21  logic inspects the data retrieved from memory, and ascertains the number and length of instructions. The pre-decoder aligns the instructions along predetermined, e.g., word, boundaries, prior to passing the aligned instructions to the cache to be stored in a cache line.  
         [0021]      FIG. 3  depicts two representative lines  200 ,  260  of the I-cache  22 , each containing a fixed number of the variable length instructions from  FIG. 1  (in this example, four instructions are stored in each cache line  200 ,  260 ). The cache lines  200 ,  260  are 16 bytes. Word boundaries are indicated by dashed lines; halfword boundaries are indicated by dotted lines. The instructions are aligned along word boundaries (i.e., each instruction starts at a word address). When an instruction is fetched from the I-cache  22  by the pipeline  12 , the decode pipe stage may simply multiplex the relevant word from the cache line  200 ,  260  and immediately begin decoding the op code. In the case of half-word instructions (e.g., I 3  and I 8 ), one half-word of space in the cache line  200 ,  260 , respectively, is unused, as indicated in  FIG. 3  by shading.  
         [0022]     Note that, as compared to the prior art cache depicted in  FIG. 1 , the cache  22  of  FIG. 3  stores only eight instructions in two cache lines, rather than nine. The word space corresponding to the length of I 9 —the halfwords at offsets 0×0A and 0×1E—is not utilized. This decrease in the efficiency of storing instructions in the cache  22  is the price of the simplicity, improved processor power, and lower power consumption of the cache utilization depicted in  FIG. 3 .  
         [0023]     Additionally, by allocating a fixed number of variable length instructions to a cache line  200 ,  260 , and aligning the instructions along predetermined boundaries, no instruction is stored misaligned across cache lines, such as I 5  in  FIG. 1 . Thus, the performance penalty and excess power consumption caused by two cache  22  accesses to retrieve a single instruction are completely obviated.  
         [0024]     Because a fixed number of variable length instructions is stored, rather than a variable number of instructions having a known total length (the length of the cache line), the address of the next sequential instruction cannot be ascertained by simply incrementing the tag  220  of one cache line  200  by the memory size of the cache line  200 . Accordingly, in one embodiment, a next fetch address is calculated by the pre-decoder  21  when the instructions are aligned (prior to storing them in the I-cache  22 ), and the next fetch address is stored in a field  240  along with the cache line  200 .  
         [0025]     As an alternative to calculating and storing a next fetch address, according to one embodiment an offset from the tag  220  may be calculated, and stored in along with the cache line  200 , such as in an offset field  240 . The next fetch address may then be easily calculated by adding the offset to the tag address. This embodiment incurs the processing delay and power consumption of performing this addition each time a successive address fetch crosses a cache line. In other embodiments, other information may be stored to assist in the calculation of the next fetch address. For example, a set of bits equal to the fixed number of instructions in a cache line  240  may be stored, with e.g. a one indicating a fullword length instruction and a zero indicating a halfword length instruction stored in the corresponding instruction “slot.” The addresses of the instructions in memory, and hence the address of the next sequential instruction, may then be calculated from this information. Those of skill in the art will readily recognize that additional next address calculation aids may be devised and stored to calculate the next instruction fetch address.  
         [0026]     While various embodiments have been explicated herein with respect to a representative ISA including word and halfword instruction lengths, the present invention is not limited to these embodiments. In general, any variable length instructions may be advantageously stored in an instruction cache  22  in a fixed number, aligned along predetermined boundaries. Additionally, a different size cache line  240 ,  300  than that depicted herein may be utilized in the practice of various embodiments.  
         [0027]     Although embodiments of the present invention have been described herein with respect to particular features, aspects and embodiments thereof, it will be apparent that numerous variations, modifications, and other embodiments are possible within the broad scope of the present invention, and accordingly, all variations, modifications and embodiments are to be regarded as being within the scope of the invention. The present embodiments are therefore to be construed in all aspects as illustrative and not restrictive and all changes coming within the meaning and equivalency range of the appended claims are intended to be embraced therein.