Method and apparatus for accelerating instruction fetching for a processor

1. Technical Field

The present invention relates in general to data processing systems and in particular to a mechanism for fetching instructions within a data processing system. Still more particularly, the present invention relates to a method and apparatus for accelerating instruction fetching for a microprocessor in which both in-line and target instructions are provided in an efficient manner.

2. Description of the Related Art

A conventional processor may include an instruction fetch unit (IFU) for requesting instructions to be loaded, an instruction cache for storing instructions, an instruction buffer for temporarily storing instructions fetched from the instruction cache for execution, a number of execution units for executing sequential instructions, a branch processing unit (BPU) for executing branch instructions, a dispatch unit for dispatching sequential instructions from the instruction buffer to particular execution units, and a completion buffer for temporarily storing instructions that have finished execution, but have not been completed.

Conventional methods of fetching instructions using the above processor components are known in the art. Typically, these methods often result in cycle delays due to incorrectly fetched in-line instructions or incorrect predictions during branch processing. For example, during branch processing, if the branch that was predicted as taken is resolved as mis-predicted, a mis-predict penalty of several cycles is incurred by the processor due to the cycle time required to restore the sequential execution stream following the branch instructions (i.e., the processor has to abandon any result that the speculative instruction produced and begin executing the path that should have been taken). Another example occurs during in-line fetching, when an instruction is emulated (e.g., when a different set of code is utilized to perform the same function as the instruction) and/or an instruction fetch is temporarily halted. The IFU has to generate a return stack which takes a relatively long time to store values and read values prior to and after emulation.

Conventional instruction caches are typically large static blocks of temporarily stored instructions. The cache typically has very little functional logic and is designed solely to issue instructions out of a cache line once a corresponding line address is provided. The cache plays no part in the actual selection of instructions, branch processing, fetching branch targets, etc.

The present invention recognizes that it would be desirable and beneficial to have a system or processor architecture for effectively handling the fetching of instructions for a high-frequency, short pipeline processor. A system which also supported branch/target fetching without leading to process stalls or loss of cycles when target direction is incorrectly predicted would be a welcomed improvement. It would be further be desirable to have such a system which also permitted for fast restart of a process after instruction emulation. These and other benefits are presented in the invention described herein.

An instruction fetching system (and/or architecture) is disclosed, which may be utilized by a high-frequency short-pipeline microprocessor, for efficient fetching of both in-line and target instructions. The system contains an instruction fetching unit (IFU), having a control logic and associated components for controlling a specially designed instruction cache (I-cache). The I-cache is a sum-address cache, i.e., it receives two address inputs, which compiled by a decoder to provide the address of the line of instructions desired fetch. The I-cache is designed with an array of cache lines that can contain 32 instructions, and three buffers that each have a capacity of 32 instructions. The three buffers include a Predicted (PRED) buffer that holds the instructions which are currently being executed, a NEXT buffer that holds the instructions which are to be executed after the instructions in the PRED buffer, and an ALT buffer that holds the alternate set of instructions when a branch is predicted taken/not taken and is utilized along with the PRED buffer to permit branch target retrieval within I-cache prior to a prediction.

When a branch is encountered, instruction lines of both paths (taken/not taken) are sent to the instruction buffers and no stall occurs on the pipeline if the prediction is correct.

Address registers hold the line addresses of the instructions in each of the PRED. NEXT and ALT buffers and a 5-bit address corresponding to the specific instruction within the line to be sent to the instruction buffers. Up to four instructions are selected at a time from the instruction line in the PRED, ALT or NEXT buffer and sent to the instruction buffers. These instructions are typically selected sequentially (in-line). Use of the IFU and the I-cache provides a continuous supply of instructions to the processor pipeline without interruptions. Also, the invention supports efficient restart after a bad instruction is encountered or an instruction is emulated

The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 is a block diagram of a data processing system utilized in one embodiment of the present invention;

FIG. 2 is a block diagram of a processor utilized in a preferred embodiment of the present invention;

FIG. 3 is a block diagram of the component parts of an instruction fetching system depicting the flow of instructions and instruction addresses through the hardware and logic components of the processor in accordance with a preferred implementation of the present invention; and

FIG. 4 is a block diagram of the 64-bit PREDA instruction address according to a preferred embodiment of the invention.

With reference now to the figures and in particular with reference to FIG. 1, there is illustrated a block diagram of the basic structure of a data processing system 100 utilized in an embodiment of the invention. Data processing system 100 has at least one processor 10 which is connected to several peripheral devices, including input/output devices 114 (such as a display monitor, keyboard, and graphical pointing device) for user interface, a permanent memory device 116 (such as a hard disk) for storing the data processing system's operating system and applications, and a temporary memory device 118 (such as random access memory or RAM) that is utilized by processor 10 in execution of current program instructions. Processor 10 communicates with the peripheral devices by various means, including a bus 120 or a direct channel 122 (more than one bus may be provided utilizing a bus bridge).

Those skilled in the art will further appreciate that there are other components that might be utilized in conjunction with those shown in the block diagram of FIG. 1; for example, a display adapter connected to processor 10 might be utilized to control a video display monitor, and a memory controller may be utilized as an interface between temporary memory device 118 and processor 10 . Data processing system 100 also includes firmware 124 whose primary purpose is to seek out and load an operating system from one of the peripherals (usually permanent memory device 116 ) whenever data processing system 100 is powered. In the preferred embodiment, processor 10 of data processing system 100 is a high-frequency short-pipelined processor.

FIG. 2 is a high level block diagram of an embodiment of processor 10 , according to a preferred embodiment of the present invention. Processor 10 may be located within data processing system 100 as depicted in FIG. 1 . In the preferred embodiment, processor 10 is a single integrated circuit, high-frequency, short-pipelined processor. Accordingly, as discussed further below, processor 10 includes various execution units, registers, buffers, memories, and other functional units, which are all formed by integrated circuitry. As depicted in FIG. 2, processor 10 is coupled to system bus 120 via a bus interface unit BIU 12 within processor 10 . BIU 12 controls the transfer of information between processor 10 and other devices coupled to system bus 120 such as a main memory 116 . Processor 10 , system bus 120 , and the other devices coupled to system bus 120 together form a data processing system.

BIU 12 is connected to instruction cache 14 and data cache 16 within processor 10 . High speech caches, such as instruction cache 14 and data cache 16 , enable processor 10 to achieve relatively fast access time to a subset of instructions or data previously transferred from main memory to instruction cache 14 and data cache 16 , thus improving the speed of operation of the data processing system.

Instruction cache 14 is further coupled to instruction fetch unit 17 , which fetches instructions from instruction cache 14 during each cycle for execution by execution circuitry within processor 10 . Branch unit (BU) is connected in parallel with execution circuitry and provides a check function for validity of instructions in the pipeline.

In the depicted embodiment, the execution circuitry of processor 10 comprises multiple execution units, including fixed-point unit (FXU) 22 , load/store unit (LSU) 28 , and floating-point unit (FPU) 30 . As is well known by those skilled in the art, each of execution units FXU 22 , LSU 28 , and FPU 30 executes one or more instructions within a particular class of sequential instructions during each processor cycle. For example, FXU 22 performs fixed-point mathematical operations such as addition, subtraction, ANDing, ORing, and XORing utilizing source operands received from specified general purpose registers (GPRs) 32 . Following the execution of a fixed point instruction, FXU 22 outputs the data results of the instruction to one or more of GPRs 32 . Conversely, FPU 30 performs floating-point operations, such as floating-point multiplication and division, on source operands received from floating-point registers FPRs 36 . FPU 30 outputs data resulting from the execution of floating-point instructions to selected FPRs 36 . As its name implies, LSU 28 executes floating-point and fixed-point instructions which either load data from memory (i.e., either data cache 16 or main memory) into selected GPRs 32 or FPRs 36 or which store data from a selected GPRs 32 or FPRs 36 to memory.

Instructions are processed by each of FXU 22 , LSU 28 and FPU 30 at a sequence of pipeline stages. As is typical of high performance processors, each instruction is processed at a number of pipeline stages, for example, fetch, decode/dispatch, execute, and write.

The present invention provides a novel processor system (and/or architecture) for providing instructions to a processor pipeline. This system is designed to deliver a steady stream of instructions to the execution circuitry of the processor through the instruction buffers. The architecture supports conditional branch prediction, branch address prediction and branch mis-prediction recovery. The architecture's control scheme provides that signals entering dynamic macros do so at the beginning of the cycle. In the preferred embodiment, an IFU is designed with specialized control logic and a plurality of multiplexor-latches (MUX-latches), which interacts with a specially designed I-cache to provide the instruction fetching, address resolution, branch processing and instruction queuing functions, without a branch unit, instruction queue or other hardware components utilized in traditional instruction fetch architectures.

The preferred embodiment includes control hardware circuitry components within the IFU and a new I-cache design. These circuit components include a plurality of MUX-latches and programmable logic arrays (PLAs). The MUXes are attached to edge-triggered flip-flops which copies to the associated output every cycle. Use of PLAs enables all inputs to be made available coming out of a latch at the beginning of a cycle.

More specifically, in the preferred embodiment, the I-cache is a 64 kilobyte cache having cache lines that are 32 instructions wide. Each cache line has an identifying effective (or virtual) address. Additionally, the I-cache also contains at least three internal buffers capable of holding a cache line of 32 instructions. Other components within the I-cache include a PRED formatter and an Array formatter which control which instructions are sent to the instruction buffers.

Branch processing is automatically completed within the I-cache. The special design of the I-cache permits both the target and in-line paths to be available for late selection. A target is always fetched when a branch is detected. Additionally, as a sum-addressed I-cache, the I-cache is able to simultaneously resolve and fetch a relative branch address and reduce the latency of the instruction fetch by at least one cycle. Other features of this new architecture are described further herein with reference to the FIG. 3 .

FIG. 3 as presented combines these various components as blocks within a block diagram, which illustrates the process of instruction fetching and branch resolution, etc. The logic blocks (MUX-latches and PLAS) located at the bottom of FIG. 3, are a part of the IFU 17 control logic.

Instruction fetch requests are transmitted to the I-cache from the IFU 17 . The basic function of IFU 17 is to fetch instructions from the I-cache 14 and provide the instruction paired with the address of the instruction to the execution circuitry. IFU 17 also provides an address valid bit (within the instruction fetch address register (IFA) register) which is set (1) when the instruction corresponds to the address and is cleared (0) when it does not.

Instruction cache 14 has two latch-controlled inputs, Addr-A 329 and Addr-B 331 . The I-cache's decoder implicitly sums the operands of Addr-A 329 and Addr-B 331 to determine the address of the line to read out of the cache array 307 . Thus, I-cache 14 is also referred to as a sum-address I-cache.

At the same time, adder 323 is utilized to resolve the read address in parallel with the I-cache access by summing the operands of Addr-A 329 and Addr-B 331 . This read address is stored in the FABF register 325 .

I-cache 14 also contains a NEXT buffer 309 , an ALT buffer 311 , and a PRED buffer 313 . PRED buffer is a line buffer that contains a line full of instructions along the currently predicted path and is used to service in-line instruction sequencing. ALT buffer is a line buffer that contains a line full of instructions along the currently not predicted path (i.e., the alternate path) and is used to service branch prediction reversal and cases where in-line instruction sequencing does not keep up with the branch target processing. NEXT buffer is a line buffer that contains a line full of instructions along the currently predicted path, but is one line past the contents of the PRED buffer. NEXT buffer is used to hold the results of in-line pre-fetches and to satisfy in-line instruction sequencing when the PRED buffer is exhausted.

Finally, I-cache 14 contains two 32 input multiplexors, array formatter 315 and PRED formatter 317 , which select a particular set of 4 instructions from a line of instructions.

Each of the three line buffers has a corresponding address tag register. Thus, NextA 310 , AltA 312 , and. PredA 314 each contain the line address for the instruction in the NEXT 309 , ALT 311 , and PRED 313 buffers, respectively. The address tag register also contains an instruction index field and an instruction valid bit. FIG. 4 illustrates the fields of the PredA register 314 from the most significant bit (msb) to the least (lsb).

PRED buffer 313 is used to produce in-line instruction sequences. The output of the PRED buffer is sent through PRED formatter 317 which selects up to four of the 32 instructions to be loaded into the instruction buffers (IB 0 to IB 3 ) 319 , (hereinafter referred to as IB 319 ). PRED formatter 317 routes one of the 32 instructions into IB 0 according to the 5 bit index (which represents a line position, 0 - 31 ) located in instruction index field of PredA register 314 . The 5 bit field is provided as an input to the PRED formatter 317 and controls which instruction from the instruction line is sent to the instruction buffer 319 . Thus, IB 0 is loaded with the instruction at the position of the 5-bit index, IB 1 is loaded with the instruction one position after the index, etc. If the index is within 3 instructions of the end of the line, one or more of IB 1 through IB 3 will be empty. The instruction buffer is advanced in-line by incrementing the 5-bit index field with a 5-bit incrementer each cycle. When data from the PRED buffer 313 is latched into the IB 319 , the PredA output is latched into instruction fetch address register (IFAR) 321 .

The NEXT buffer 309 holds in-line pre-fetches until the instructions are needed to continue filling the in-line path. IFU 17 supports two different in-line pre-fetches, one during run mode and another during restart.

A run mode in-line pre-fetch is initiated when instructions are being fetched from the last quarter of the line in the PRED buffer 313 and the instruction cache array 307 is idle. IFU's control logic initiates the fetch by: (1) asserting an array activation signal, ‘use line 1 ’ (USEL 1 ), corresponding to the line of instructions in the array; (2) selecting the PredA input to Addr-A 329 , to load the line index of the PRED buffer 313 ; and (3) selecting 128 (corresponding to the value required to skip to the address of the first instruction at the next line from the address of the currently executing line) as the input to Addr-B 331 .

Thus, a read of the I-cache 14 is started at the address of the line sequentially after the line being executed. During the first cycle of the read, the array loads a line into an internal latch while an external adder (L 1 I$A+) 323 generates the read address which is latched into FABF register 325 . In the second cycle of the read, the FABF instruction index (which will be zero, corresponding to the first instruction of the next line) is applied to the array formatter 315 . The controller zeros out the 5 bit field in PREDA and adds 128 to select the first instruction on the next sequential line. I-cache 14 inputs to the NEXT buffer 309 , next formatted buffer (N 0 -N 3 ) 327 , and NextA 310 are selected so that at the end of the second cycle, NEXT buffer 309 is filled with the line of instructions and ready to be forwarded to the instruction buffers 319 and PRED buffers 313 .

When IFAR 321 is ready to-wrap around from the last instruction (instruction 31 ) of the line in the PRED buffer 313 into instruction 0 of the line in the NEXT buffer 309 , IFU's control logic sets the selects on the Mux-latches of IB 319 , IFA 321 , PRED 313 , and PredA 314 to receive data from the Mux-latches of NEXT 309 , N 0 -N 3 327 , and NextA 310 . Since the instruction in N 0 will be decoded in the next cycle, the values of N 0 -N 3 327 will be transferred into IB 0 -IB 3 319 and NextA 310 into IFA 321 . In the second cycle, because instruction 1 comes from the PRED formatter 317 , the NEXT line is loaded into the PRED buffer 313 and NextA+1 is loaded into PredA 314 . This increment is only a 5-bit increment on the instruction index field.

Thus, according to the present invention, the PRED 313 and NEXT buffers 309 allow IFU 17 to stream an in-line sequence of instructions through the IB 319 without interruption.

Branch instruction prediction and target fetching feature of the invention is now presented. In the preferred embodiment, the instructions are pre-decoded from 32 bits to 39 bits before they are loaded into I-cache 14 . One of the seven additional bits is referred to as the IS_BRANCH bit. This bit allows a PLA-based controller to react to the presence of a branch in IB 2 of IB 319 . Branch processing begins with the instruction in IB 2 . If a branch is detected in IB 2 , the sequencer's control logic automatically initiates a target fetch by asserting USEL 1 , which enables a read from the I-cache array 307 , and the branch target selection (TgtSel) 333 . TgtSel 333 is a PLA that computes select signals for the multiplexors of Addr-A 329 and Addr-B 331 . The target address is selected on Addr-A 329 and Addr-B 331 based upon a decode of the branch instruction in IB 2 . If IB 2 holds a branch relative, IB 2 _PC is selected into Addr-A 329 . Whenever none of the selects are asserted (i.e., an absolute branch, branch to register, or microcode entry), 0 is loaded into Addr-A 329 . Addr-B 331 is then loaded with a sign extended immediate (IB 2 _Imm), a microcode entry point (IB 2 _UVec), or one of several register values. These register values correspond to the types of branch targets selected and include, for example, exception return (ER/SRR 0 ), and link control (Lnk/Cnt).

If a cache miss occurs, the line buffer is marked as invalid and pre-fetch is initiated at the address stored in the FABF 325 , allowing fetch exceptions to be processed at the correct place in the instruction stream.

In the first cycle of the fetch, the target line is read from the array 307 into an internal latch, and the fetch address is summed into the FABF latch 325 . At the same time, assuming in-line operation is uninterupted, the branch instruction moves into IB 1 . During cycle two, the array formatter 315 prepares the target instruction group for direct bypassing into IB 319 . Array formatter 315 is a MUX which is provided with a 5 bit address. The five bit address corresponds to one of the 32 instructions in the target line. During the second cycle, array formatter 315 sends four instructions as input to the instruction buffer 319 . The MUX of IB 319 receives a control input which indicates wether to select the instructions received from the array formatter 315 (i.e., the target instructions) or the instructions from the PRED formatter 317 (i.e., the in-line instructions). Assuming instructions are streaming normally, the branch moves into location IB 0 after the second cycle of the target fetch.

At this point, IFU's control logic performs one of the following series of steps:

(1) predict the branch in IB 0 will be taken and

a. select output of the array formatter 315 into IB 319 so that the target instruction can be decoded in the next cycle,

b. IFA 321 latches FABF 325 ,

c. PRED buffer 313 grabs the line read from the array 317 ,

d. PredA 314 stores the value in FABF 325 with the instruction index incremented,

e. ALT buffer 311 latches the line in the PRED buffer 313 ,

f. A 0 -A 2 335 stores IB 1 -IB 3 319 , and

g. AltA 312 stores PredA 314 with the instruction index incremented; or

(2) predict the branch in IB 319 will not be taken and

a. select the output of the PRED formatter 317 into IB 319 so that in-line execution continues,

b. IFA 321 latches PredA 314 ,

c. increment the PredA instruction index,

d. ALT buffer 311 retrieves the line read from the array 307 ,

e. A 0 -A 3 335 receives the output of the array formatter 315 , and

f. AltA 312 latches FABF 325 ; or

(3) not detect a branch in IB 0 , because in-line streaming was interrupted. In this case:

a. ALT buffer 311 selects the line read from the cache array 307 ,

b. A 0 -A 3 335 receives the output of array formatter 315 ,

c. AltA 312 latches FABF 325 ,

d. Later, when a branch is detected in IB 0 that is predicted to go to the target and no target is in the second cycle of the read pipeline, the actions in case (a) above will take place with ALT 311 , A 0 -A 3 335 , and AltA 312 replacing the cache array 307 , array formatter 315 and FABF 325 as the source of the target line.

While the PRED buffer 313 holds the instructions on the predicted path, the ALT buffer 311 holds the instructions along the alternate branch path. Thus, ALT buffer 311 is used to facilitate incorrectly scheduled or predicted branch processing. If another unit in the system detects that a conditional branch direction was likely mis-predicted then IFU 17 can resume streaming from ALT buffer 311 . ALT buffer 311 , like NEXT buffer 309 does not have a formatter. It has instead registers A 0 -A 3 335 to hold previously formatted instruction groups.

As another feature of the invention, IFU 17 provides a restart mechanism. If the BU 18 detects that the IFU is providing an incorrect sequence of instructions it asserts a ‘bad instruction’ (IBAD) signal. IBAD signal causes IFU's control logic to kill instructions in the write-back stage, initiate a fetch/read from the I-cache array 307 by asserting USEL 1 , selecting fix address, RealPC, into Addr-A 329 and a value of 0 into Addr-B 331 . RealPC is an input from BU 18 , allowing BU 18 to control the start address of the new sequence. As restart proceeds, a second in-line fetch is initiated. IFU 17 initiates an in-line pre-fetch during a restart by selecting the previous cycle's line index from the FABF 325 into Addr-A 329 and a value of 128 into Addr-B 331 . Then, as the instructions corresponding to the restart address appear at the output of the array formatter 315 , the formatter output is latched into IB 319 and PRED 313 , FABF 325 is loaded into IFAR 321 , and FABF 325 with the instruction index field incremented is loaded into PredA 314 . If a second in-line fetch is started, the NEXT buffer 309 will latch the output of cache array 307 .

As another related feature, IFU 17 also facilitates microcode return address speculation through the microcode return address guess register (UretG) 337 . When the instruction in IB 0 is decoded to be branch to microcode, the IFU latches IFA+4 339 into UretG 337 . Thus, in the next cycle, the return address will be available to a microcode-return instruction in IB 2 . This greatly improves the accuracy of the branch address speculation on the microcode return.

The I-cache design of the present invention provides the fetching mechanism of the processor with a number of advanced features, which include: (1) The address is presented to the cache in the form of two operands that when summed produce the required address; (2) The cache array delivers a full 32 instruction wide line to its output in two cycles; (3) Reads and writes are fully pipelined; (4) The cache array can load a full 32 instruction wide line in two cycles; (5) There are three full 32 instruction wide line buffers; and (6) The formatters deliver up to four instructions aligned to an instruction boundary to the instruction buffer.

While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. For example, although the invention has been described with specific reference to a high-frequency processor, the invention is capable of being implemented in any processor.