JPH03212734A - Data processor - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a data processing device, and more specifically, it suppresses disturbances in pipeline processing by a branch instruction processing mechanism and makes the multi-stage pipeline processing mechanism efficient. The present invention relates to a data processing device that can be operated to exhibit high processing power.

[Conventional technology]

FIG. 6 is a schematic diagram showing a general configuration example of a pipeline processing mechanism generally employed in conventional data processing devices.

11 in the figure is the instruction fetch stage (IF stage) 12
1 is an instruction decode stage (D stage), 13 is an operand address calculation stage (A stage), 14 is an operant fetch stage (F stage), and 15 is an instruction execution stage (E stage).

[The F stage 11 fetches an instruction code from a memory (not shown) and outputs it to the D stage 12. D stage 1
2 decodes the instruction code fetched by the IP stage 11 and outputs the decoding result to the A stage 13. The A stage 13 calculates the effective address of the operand specified in the instruction code, and sends the result to the F stage 14.
Output to. The F stage 14 fetches the operand address from the memory according to the operand address input from the A stage 13 and outputs it to the E stage 15.

The E stage 15 executes the operation specified in the instruction code on the operand input from the F stage 14, and stores the operation result in the memory if necessary.

As mentioned above, in conventional data processing devices, the processing specified by each instruction by the pipeline processing mechanism is, for example, 5.
It is decomposed into parts and processed sequentially.

Each of the five processes can be operated in parallel for different instructions, and ideally, five instructions can be processed in parallel using a five-stage pipeline processing mechanism.
A data processing device can be obtained that has up to five times the processing capacity as compared to the case where pipeline processing is not adopted.

As described above, the pipeline processing method can significantly improve the processing capacity of a data processing device, and is therefore widely employed in data processing devices with high processing speeds.

However, there is no guarantee that pipeline processing always operates under ideal conditions. One of the problems in pipeline processing is the processing of branch instructions.

For example, if a branch instruction is processed in the E stage 15 by the pipeline processing mechanism configured as shown in FIG. 6, and then another branch instruction is processed in the IF stage 11, the pipeline processing will be greatly disrupted. The situation will be explained with reference to FIG. 7, which is a schematic diagram showing a branch instruction processing procedure in a conventional data processing device.

In FIG. 7, instruction 1)13 and instruction lNl2 are branch instructions. When instruction rN3 is executed, instructions IN4. Command IN
S, Instruction IN6. The instruction IN7 is canceled, and the processing of the instruction INII, which is the branch destination instruction of the instruction IN3, is newly started from the IF stage 11.

After instruction IN3 is executed at E stage 15, instruction IN
Until II is executed at E stage 15, processing time equivalent to four instructions is wasted.

Similarly, processing time for four instructions is wasted for the instruction lNl2.

This dead time occurs because the instruction to be processed after execution of the branch instruction is fetched after all pipeline processing for the branch instruction is completed.

Therefore, the greater the number of pipeline processing stages, the longer the wasted time.

In order to suppress such disturbances in pipeline processing when executing a branch instruction, the branch destination of the branch instruction is predicted at the time the instruction is fetched at the IF stage 11, and the branch instruction is executed at the E stage 15. Advance branch processing is employed in which the fetch destination of an instruction is changed to the branch destination in advance before the instruction is executed.

Such advance branch processing is referred to as pre-branch processing.

FIG. 8 shows a branch target buffer (B
TB) and a schematic diagram showing a configuration example of an instruction fetch unit.

BTB 160 is composed of multiple entries, each entry being a branch instruction address field.

It consists of a valid bit field that indicates whether the entry is valid or not, and a branch destination address field.

The address of a branch instruction is registered in the branch instruction address field. A branch destination address when each branch instruction branches is registered in the branch destination address field.

When a branch instruction causes a branch in E stage 15,
The address of the instruction and the branch destination address are registered as a pair in the branch instruction address field and the branch destination address field of the BTB 160, respectively, and the bit of the corresponding valid bit field is set to "1".

Fetching of an instruction by the 1F stage 11 is performed by setting the address of the instruction to be fetched in the counter INPC 115.

When IP stage 11 fetches an instruction, counter Q
The address of the instruction, which is the value of INPC 115, is decoded by decoder 190, and the corresponding entry in BTB 160 is designated according to the decoding result.

The value of the branch instruction address field in the designated BT 3160 is output to the comparator 191, but the comparator 191 is also given the value of the counter QINPC 115, and the two are compared by the comparator 191.

If the comparison result by the comparator 191 matches and the corresponding bit in the valid bit field is "1", a pre-branch occurs. That is, since the signal "l" indicating that the comparison result of the comparator 191 matches and the value "1" of the valid bit field are both input to the AND gate 192, the "1" output is used as the pre-branch generation signal. The instruction fetch sequence is applied to the branch destination address register 161 and the instruction fetch sequence is changed to the value of the branch destination address field in the BTB 160.

Specifically, the branch destination address register 161 is BTB1.
The output from the branch destination address field in 60 is latched, and the instruction at this address, that is, the branch destination instruction, is fetched and stored in the instruction queue 112.

When the branch destination instruction is stored in the instruction queue 112 in this manner, the input pointer P1164 is incremented accordingly. A branch instruction is stored at the position immediately before the position pointed to by the current input pointer P1164. That is, the instruction queue 112 stores a branch instruction and a branch destination instruction from the branch instruction consecutively. Therefore, it is possible to change the instruction sequence without disrupting the processing at each stage after the D stage 12.

[Problem to be solved by the invention]

As described above, by employing pre-branch processing, the efficiency of pipeline processing is generally improved by switching the instruction fetch sequence to the branch destination in advance at the instruction fetch stage.

However, if the size of the instruction field of each entry in the instruction queue 112 is less than or equal to the instruction fetch data size, for example, instructions are fetched in units of 4 bytes (32 bits), while the size of the instruction field in the instruction queue 112 is 2 bytes (32 bits). (16 bits),
There may be cases where the end of a branch instruction does not end at the boundary of the data size of instruction fetch, or the beginning of the branch destination instruction does not start from the boundary of data size of instruction fetch.

In such a case, an invalid code will be interposed between the branch instruction and the branch destination instruction within the instruction queue, making it impossible to control the instruction queue.

The present invention was made in view of these circumstances, and
An object of the present invention is to provide a data processing device capable of controlling an instruction queue even in a situation where an invalid code exists between a branch instruction and a branch destination instruction inside the instruction queue.

[Means to solve the problem]

The data processing device of the present invention includes an output pointer dedicated to when a branch occurs, and when a branch occurs, the branch destination instruction is selected based on the storage position in the instruction queue of the instruction that caused the branch and the address of the branch destination instruction. Give the storage location to the output pointer dedicated to when a branch occurs.

[Effect]

In the data processing device of the present invention, even if an invalid code exists between the branch instruction and the branch destination instruction in the instruction queue when a branch occurs, the instruction from the instruction queue is retrieved using the output pointer dedicated to the branch occurrence. The output position of the branch instruction is corrected and output from the beginning of the branch instruction, and the pre-branch is performed correctly.

[Embodiments of the invention]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described in detail below based on drawings showing embodiments thereof.

(1) "Configuration of Functional Blocks" FIG. 4 is a block diagram showing an example of the configuration of the data processing device of the present invention.

Functionally, the inside of the data processing device of the present invention can be roughly divided into an instruction fetch section 51. Instruction decoding unit 52, PC
Calculation section 53. Operand address calculation unit 54° micro ROM unit 55. Data calculation section 56. It is divided into an external bus interface section 57.

In addition, in FIG. 4, an address output circuit 58 for outputting an address to the outside of the CPU, and a data input/output circuit 59 for inputting and outputting data to and from the outside of the CPU are shown separately from other functional blocks.

(1, 1) r Instruction fetch unit The instruction fetch unit 51 includes a branch buffer, an instruction queue, and its control unit, and determines the address of the next instruction to be fetched and fetches the instruction from the branch buffer or memory outside the CPU. fetch.

It also registers instructions to the branch buffer.

Since the branch buffer is small, it acts as a selective cache. Details of the operation of the branch buffer are disclosed in Japanese Patent Application Laid-Open No. 63-56731.

The address of the next instruction to be fetched is calculated by a dedicated counter as the address of the instruction to be input to the instruction queue 112 (see FIG. 1), which will be described later.

When a branch or jump occurs, the address of a new instruction is transferred from the PC calculation unit 53 or the data calculation unit 56.

When fetching an instruction from a memory external to the CPU, the address of the instruction to be fetched is output from the address output circuit 58 to the outside of the CPU through the external bus interface section 57, so that the instruction code is fetched from the data input/output circuit 59. be done.

Then, of the bumped instruction codes, the instruction code to be decoded next is output to the instruction decoding section 52.

(1, 2) r Instruction Decode Unit” In the instruction decode unit 52, instruction codes are basically decoded in units of 16 bits (halfwords).

This block includes an FH-decoder for decoding the operation code contained in the first halfword of the instruction code; It includes an NFHW decoder that decodes the operation code included in the third halfword, and an addressing mode decoder that decodes the addressing mode.

These FH-decoder, NFH-decoder, and addressing mode decoder are collectively referred to as a first decoder.

The instruction decoding unit 52 also includes a second decoder that further decodes the output of the FHW decoder or NFH-decoder to calculate the entry address of the micro ROM, and an address calculation conflict check mechanism that checks for pipeline conflicts during operand address calculation. .

The instruction decode unit 52 converts the instruction code input from the instruction fetch unit 51 into 0 to 6 bits per 2 clocks (1 step).
Decode byte by byte. Among the decoding results, information related to the calculation in the data calculation unit 56 is stored in the micro ROM unit 5.
5, information related to the operand address total X is output to the operand address calculation unit 54, and information related to PC calculation is output to the pc calculation unit 53.

(1, 3) Micro ROM section" The micro ROM section 55 mainly stores a micro program that controls the data calculation section 56.
Includes OM, micro sequencer, micro instruction decoder, etc.

Microinstructions are successively issued from the micro ROM once every two clocks (one step). In addition to the sequence processing indicated by the microprogram, the microsequencer also handles exception 1.
Processing of interrupts and traps (these three are collectively referred to as EIT) is accepted by hardware. Also Micro R
The OM unit 55 also manages the store buffer6.
The output of the instruction decoding unit, such as the output of the decoder, is input.

The output of the micro-decoder is mainly output to the data calculation unit 56, but some information such as other preceding processing stop information due to execution of a jump instruction is also output to other blocks.

(1, 4) r Operand Address Calculation Unit The operand address calculation unit 54 is hard-wired controlled by information related to operand address calculation output from the address decoder of the instruction decoding unit 52, etc. This block performs most of the processing related to operand address calculation. The operand address calculation unit 54 also checks whether the memory access address and operand address for memory indirect addressing fall within the I/CII area mapped to memory.

The address calculation result is sent to the external bus interface section 57. The values of the general-purpose register and program counter necessary for address calculation are input from the data calculation section.

When indirect memory addressing is performed, the address output circuit 5B is connected to the CP through the external bus interface section 57.
By outputting the memory address to be referenced to the outside of the U, the indirect address value input from the data input/output unit 59 passes through the instruction decoding unit 52 as it is and is fetched.

(1, 5) rPC calculation unit J The PC calculation unit 53 receives the P output from the instruction decoding unit 52.
It is hardwired and controlled by information related to C computation and calculates the PC value of the instruction.

The data processing device of the present invention has a variable length instruction code, and the length of the instruction cannot be determined unless the instruction is decoded. Therefore, the PC calculation unit 53 creates the PC value of the next instruction by adding the instruction length output from the instruction decoding unit 52 to the PC value of the instruction being decoded.

The calculation result of the pc calculation unit 53 is output as the pc value of each instruction together with the decoding result of the instruction.

(1, 6) r Data Operation Unit The data operation unit 56 is controlled by a microprogram, and uses registers and arithmetic units to execute operations necessary to realize the function of each instruction according to the output information of the micro ROM unit 55.

When the operand to be operated on is an address or an immediate value, the data calculation unit 56 obtains the address or immediate value calculated by the operand address calculation unit 54 through the external bus ink face unit 57.

Furthermore, when the operand to be operated on is in a memory external to the CPU, the bus interface section 57 transfers the address calculated by the address calculation section 54 to the address output circuit 58.
By outputting from the data input/output circuit 59, the data calculation unit 56 obtains the operand fetched from the memory external to the CPU.

Arithmetic units include ALU, barrel shift, priority encoder or counter, and shift register. The registers and the main arithmetic unit are connected by three buses, and one microinstruction instructing one register-to-register operation is processed in two clocks (one step).

If it is necessary to access memory outside the CPU during data calculation, the address output circuit 5
By outputting the address from 8 to the outside of the CPU,
The target data is transferred to data f through the data input/output circuit 59.
The processing is performed in the R calculation section 56.

When the data calculation unit 56 reads data from a memory external to the CPU, the address of the data to be read is ^A.
The address is set in the register 76 and output from the address output circuit 58 through the external bus interface section 57, so that the data is transferred to the data input/output circuit 58.
9 through the DD lotus 108 (see FIG. 1), which will be described later, to the [l[l12 Luzisk 77 (see FIG. 1).

When the data calculation unit 56 writes data to a memory external to the CPU, the address of the data to be written is AAI.
By setting the address in the register 76 and outputting it from the address output circuit 58 through the external bus interface section 57, the DDR2 register 7, which will be described later,
8 (see FIG. 1) is output from the data input/output circuit 59 to the outside of the CPU through the DD bus 08.

When the data calculation unit 56 obtains a new instruction address by processing a jump instruction or handling an exception, it outputs this to the instruction fetch unit 11 and the PC calculation unit 13.

(1, 7) ``External Bus Interface Section'' The external bus interface section 57 controls communication on the external bus of the data processing apparatus of the present invention. All memory accesses are performed in clock synchronization, with a minimum of 2 clock cycles (1
This can be done in steps).

Access requests to the memory are generated independently from the instruction fetch unit 51, operand address calculation unit 54, and data calculation unit 56. Furthermore, an access request for performing operand prefetch is also generated.

The external hash interface unit 57 mediates these memory access requests. Furthermore, accessing data at a memory address that straddles a 32-bit (1 word) aligned boundary, which is the data bus size that connects memory and the CPU, is automatically detected as straddling a word boundary within this block. It is divided into two memory accesses.

The external bus interface unit 57 also performs conflict prevention processing when the pre-fetched operand and stored operand overlap and bypass processing from the store operand to the fetch operand.

When there is an access request from the instruction fetch unit 51,
The address to be accessed is set in the CAM register 142 (see FIG. 1), which will be described later. Address calculation section 54
If there is an access request from ■＾Register 125
The address to be accessed is sent to . When there is an access request from the data calculation unit 56, the address to be accessed is written to the AAI register 76.

When there is an access request for prefetching an operand, the address to be accessed set in the FA register 127 is output to the A^ba bus 07, so that the operand data is transferred from the memory outside the CPU to the external bus interface section 57. The 6-fetched operand data is I) S[
1 Input to ATA80. Further, the address on the AA bus 07 used for access is input to the SCAM 79.

SCAM79 and 5DATA80 are connected to each other by a match indicating line 90. Up to two pieces of aligned 4-byte data are stored in 5DATA80. SCAM79 contains an address corresponding to the data in 5DATA80.

Data is input to 5DATA 80 after being arranged, but when the data calculation unit 56 retrieves and uses the data, it retrieves any data length (within 4 bytes) from any address. Is possible.

(2) “Pipeline mechanism” The pipeline processing mechanism of the data processing device of the present invention is the fifth
It is constructed as schematically shown in the figure.

Instruction fetch stage (IP
Stage) 31. Decode stage (D stage) 32 to decode instructions. Operand address calculation stage (A stage) 33. Operand address calculation stage (A stage) for calculating addresses of operands. Operand fetch stage (F stage) 34 consisting of a part that performs micro ROM access (particularly referred to as R stage 36) and a part that performs operand brief fetch (particularly referred to as OF stage 37).
The five-stage configuration of the execution stage (E stage) 35 for executing instructions is the basis of the pipeline processing of the data processing apparatus of the present invention.

In addition to a one-stage store buffer in the E stage 35, some of the high-performance instructions pipeline the instruction execution itself, so there is actually a pipeline processing effect of five or more stages.

Each stage operates independently of the other stages, and in theory the five stages operate completely independently. Each stage can perform one process in a minimum of two clocks (l steps). Therefore, ideally, pipeline processing proceeds one after another every two clocks (l steps).

The data processing device of the present invention has some instructions that cannot be processed with just one basic pipeline process, such as memory-to-memory operations or memory indirect addressing, but the data processing device of the present invention can handle these processes. It is designed to perform pipeline processing as balanced as possible. Furthermore, in the data processing device of the present invention, for an instruction having multiple memory operands, pipeline processing is performed by decomposing the instruction into multiple pipeline processing steps (step codes) at the decoding stage based on the number of memory operands. conduct.

Regarding the disassembly method of pipeline processing, see JP-A-63
This is disclosed in detail in Japanese Patent No.-89932.

The information passed from the IF stage 31 to the D stage 32 is the instruction code 40 itself. D stage 32 to A
There are two types of information passed to the stage 33: information related to the operation specified by the instruction (referred to as D code 41) and information related to address calculation of the operand (referred to as A code 42).

The information passed from the A stage 33 to the F stage 34 is an R code 43 containing the entry address of the microprogram routine or the parameters of the microprogram.
and an F code 44 containing operand addresses, access method instruction information, and the like.

The information passed from the F stage 34 to the E stage 35 is an E code 45 containing arithmetic control information and literals, and an S code 46 containing operands or operand addresses.
There are two.

EIT detected at stages other than E stage 35 is
EIT processing is not started until the code reaches the E stage 35. This is because only the instructions being processed in the E stage 35 are in the execution stage, and the instructions being processed from the IF stage 31 to the F stage 34 have not yet reached the execution stage. Therefore, E stage 35
For EITs detected outside of the above steps, the fact that they have been detected is recorded in the step code and transmitted to the next stage.

(2,1) r pipeline processing unit” (2,1,1
) Decomposition of instructions into r-step codes The data processing device of the present invention performs pipeline processing that takes advantage of the features of the pipeline mechanism described above.

In the D stage 32, "2 hide instruction basic part + θ ~ 4 byte addressing extension part", "multi-stage indirect mode specification part addressing extension part" or instruction-specific extension part is 1
Processed as one decoding unit.

The decoding result of each time is called a step code, and from the A stage 33 onwards, this step code is used as a unit of pipeline processing. The number of step codes is unique for each instruction, and if the multi-stage indirect mode is not specified, one instruction is divided into a minimum of 1 step code and a maximum of 3 step codes. When the multi-stage indirect mode is specified, the step code increases accordingly.

(2, 1, 2) ``Program counter management'' It is possible that all the step codes existing on the pipeline of the data processing device of the present invention are for different instructions, and therefore the value of the program counter is the same as the step code. managed separately. Every step code has the program counter value of the instruction that generated the step code.

The program counter value that accompanies the step code and flows through each stage of the pipeline is referred to as the program counter (SPC). SPCs are passed between each stage of the pipeline one after another.

(2, 2) r Processing of each pipeline stage The input/output step codes of each pipeline stage are named for convenience as shown in FIG.

In addition, the step code performs processing related to the operation code, and includes a sequence that becomes the entry address of the microprogram, parameters for the E stage 35, etc.
There are two series: a series that becomes an operand for the microinstruction in the E stage 35;

(2, 2, 1) r Instruction fetch stage The instruction fetch stage (IF stage) 31 fetches instructions from the memory or branch buffer and stores them in the instruction queue 11.
2 (see FIG. 1) and outputs the instruction code to the D stage 32. Input to the instruction queue 112 is performed in units of arranged 4 hides.

Fetching an instruction from memory requires a minimum of two clocks (one step) per four aligned bytes. If the branch target buffer 160 (BTB: see FIGS. 1 and 2) hints, it can be fetched in one clock per four aligned bytes. instruction queue 1
The output unit of 12 is variable every 2 bytes, and a maximum of 6 bytes can be output during 2 clocks. Immediately after branching, it is also possible to bypass the instruction queue 112 and directly transfer the 2 bytes of the instruction basic part to the instruction decoder.

The IP stage 31 also controls the registration and clearing of instructions in the branch target buffer 160, manages the address of the instruction to which the branch target buffer is fetched, and controls the instruction queue 112.

The ErT detected at the 1F stage 31 includes a hash access exception when fetching an instruction from memory, an address translation exception due to a memory protection violation, and the like.

(2, 2, 2) r Instruction Decode Stage The instruction decode stage (D stage) 32 decodes the instruction code input from the IF stage 31.

Decoding is done by the FHW decoder of the instruction decoding section 52, NP
The first decoder, which is a combination of the H-decoder and the addressing mode decoder, is used to perform decoding once every two clocks (one step), and one decoding process consumes θ to 6 bytes of instruction code (for the RET instruction). Instruction codes are not consumed in output processing of step codes including return destination addresses, etc.). D stage 32 is A with one decoding
For the stage 33, an approximately 35-bit control code that is an A code 42 as address calculation information, a maximum of 32 bits of address modification information, and an approximately 50-bit control code that is a D code 41 as an intermediate decoding result of the operation code. and 8-bit literal information.

In the D stage 32, the PC calculation unit 53 controls each instruction.

It also performs output processing of instruction codes from the instruction queue 112.

The EIT detected in the D stage 32 includes a reserved instruction exception. In addition, various E
l↑ is encoded in the step code and A
Transfer to stage 33.

(2, 2, 3) r operand address calculation stage” operand address calculation stage (A stage) 33
The processing functions are broadly divided into two. One is a process in which the second decoder of the instruction decoding unit 52 is used to decode the operation code at a later stage, and the other is a process in which the operand address calculation unit 54 calculates an operand address.

The subsequent decoding process of the operation code is D code 4.
1 as an input, and outputs an R code 43 including register and memory write reservations, microprogram entry addresses, parameters for the microprogram, and the like. Note that register or memory write reservations are
This is to prevent incorrect address calculation from being performed due to the contents of the register or memory referenced in address calculation being rewritten by a preceding instruction on the pipeline. Register or memory write reservations are made for each instruction, not for each step code, to avoid deadlock.

For reservations for writing to registers and memory, please refer to Tokusho 6.
2-144394 in detail.

The operand address calculation process takes the A code 42 as input, performs address calculation in the operand address calculation unit 54 in accordance with the A code 42 by combining addition or memory indirect reference, and outputs the calculation result as the F code 44.

At this time, a conflict check is performed when registers and memory are successively written due to address calculation, and if a conflict is indicated because the preceding instruction has not finished writing to the register or memory, the preceding instruction is at E stage 35. Wait until the write process is finished. It is also checked whether the operand address and the memory indirect reference address fall within the I10 area mapped to memory.

BITs detected in the A stage 33 include reserved instruction exceptions, privileged instruction exceptions, bus access exceptions, address translation exceptions, and debug traps based on operand breakpoint hints during memory indirect addressing. If the D code 41 or A code 42 itself indicates that an EIT has been generated, the A stage 33 transmits the EIT to the R code 43 and F code 44 without performing address calculation processing on that code.

(2, 2, 4) r Micro ROM Access Stage The operand fetch stage (F stage) 34 is also broadly divided into two processes. One is access processing of the micro ROM, and is particularly referred to as the R stage 36. The other is operand prefetch processing, particularly referred to as OF stage 37. The R stage 36 and the Kano stage 37 do not necessarily operate at the same time, but operate independently depending on whether memory access rights can be acquired or not.

Micro ROM access processing, which is the processing of the R stage 36, includes micro ROM access and microinstruction decoding for the R code 43 to generate an E code 45, which is an execution control code used for execution in the next E stage 35. processing. When processing for one R code 43 is decomposed into two or more microprogram steps, the micro ROM is used in the E stage 35, and the next R code 43 waits for micro ROM access. R
The micro ROM access to the code 43 is performed at the time of execution of the last microinstruction in the previous E stage 35. In the data processing device of the present invention, since most basic instructions are executed in one microprogram step, the microROM for the R code 43 is actually
Accesses are often made one after another.

There is no new BIT detected in the R stage 36. If the R code 43 indicates an instruction processing re-execution type EIT, the microprogram for that ETT processing is executed, so the R stage 36 fetches the microinstruction according to the R code 43.

If R code 43 indicates an odd address jump trap, R stage 36 conveys it by E code 45. This is for a pre-branch, and in the E stage 35, if a branch does not occur in the E code 45, the pre-branch is made valid and an odd address jump trap is generated.

(2, 2, 5) r Operand Fetch Stage The operand fetch stage (OF stage) 37 performs operand prefetch processing of the above two processes performed in the F stage 34.

Operand prefetch takes the F code 44 as input, and sends the fetched operand and its address to the S code 46.
Output as . One F code 44 may straddle word boundaries, but specifies operand fetch of 4 hides or less. The F code 44 also includes a designation as to whether or not to access the operand, and when the operand address itself or the immediate value calculated in the A stage 33 is transferred to the E stage 35, operand prefetch is not performed and the F code is The contents of 44 are transferred as S code 46.

Operand to be briefetched and E stage 3
5 matches the operand for which write processing is to be performed, the operand briefetch is not performed from the memory but is performed in a bypass manner.

Further, operand prefetch is delayed for the I/C1i area, and operand fetch is performed after waiting until all preceding instruction processing is completed.

BITs detected in the leaf stage 37 include debug traps caused by hash access exceptions, address translation exceptions, and breakpoint hits for operand prefetch.

If the F code 44 indicates a BIT other than a debug trap, it is transferred to the S code 46 and no operand prefetch is performed. If the F code 44 indicates a debug trap, the EI for that F code 44 is
The same processing as in the case where T is not indicated is performed and a debug trap is transmitted to the S code 46.

(2, 2, 6) r execution stage” Execution stage (E stage) 35 has E code 45 and S
It operates with code 46 as input. This E stage 35
is a stage for executing instructions, and all processing performed in stages before the F stage 34 is preprocessing for the E stage 35. When a jump instruction is executed or BIT processing is started at E stage 35, all processing performed from IP stage 31 to F stage 34 is invalidated. The E stage 35 is controlled by a microprogram and executes instructions by executing a series of microprograms starting from the entry address of the microprogram indicated in the R code 43.

Reading of the micro ROM and execution of micro instructions are performed in a pipelined manner. Therefore, when a branch occurs in a microprogram, one microstep becomes vacant. Furthermore, the E stage 35 can perform pipeline processing for storing operands within 4 bytes and executing the next microinstruction by using the store buffer in the data calculation unit 56.

In the E stage 35, the write reservation for registers and memory made in the A stage 33 is canceled after the operand is written.

Furthermore, if a conditional branch instruction causes a branch at the E stage 35, the branch history is rewritten because the branch prediction for that conditional branch instruction was incorrect.

BITs detected at the E stage 35 include bus access exceptions, address translation exceptions, and debug traps.

Odd address jump trap, reservation function exception.

illegal operand exception, reserved stack format exception,
There are divide-by-zero traps, unconditional traps, conditional traps, delayed context traps, external interrupt delayed interrupts, reset interrupts, and system failures.

All BITs detected in the E stage 35 are subjected to BIT processing, but BITs detected between the IP stage 31 before the E stage and the F stage 34 and reflected in the R code 43 or S code 46 are not necessarily BIT processed. There is no guarantee that it will be done. It was detected between IF stage 31 and F stage 34, but the preceding instruction was detected at E stage 35.
E stage 3 due to a jump instruction being executed in
All ErTs that have not reached 5 are cancelled.

This means that the instruction that caused the EIT was never executed in the first place.

External interrupts and delayed interrupts are directly accepted by the E stage 35 at the instruction interval, and necessary processing is executed by the microprogram. Other various BIT processes are executed by microprograms.

(2, 3) r State control of each pipeline stage”
Each stage of the pipeline has an input latch and an output launch, and basically operates independently of other stages. Each stage completes the previous processing and transfers the processing result from the output lunch to the input latch of the next stage, and when all the input signals necessary for the next processing are available at the input lunch of its own stage. Start the next process.

In other words, in each stage, all input signals for the next process output from the previous stage are valid, the current processing result is transferred to the input lunch of the next stage, and when the output lunch is empty, the next process starts. Start.

All input signals must be available at the clock timing immediately before each stage starts operating. If the input signals are not ready, the stage is in a waiting state (waiting for input). When transferring from the output lunch to the input lunch of the next stage, the input latch of the next stage must be in the free state, and even if the input lunch of the next stage is not free, the pipeline stage will wait. state (waiting for output). If a necessary memory access right cannot be obtained, a wait is inserted into the memory access being processed, or other pipeline conflicts occur, the processing itself at each stage will be delayed.

(3) "Processing of Branch Instructions" Since the data processing device of the present invention employs multi-stage pipeline processing as described above, there is a large overhead when executing branch instructions. In order to reduce this overhead, pre-branch processing is performed in the IF stage 11.

The purpose of pre-branch processing is to take a branch destination instruction into the pipeline processing mechanism as early as possible by branching in advance at the IF stage 11 instead of branching at the E stage 15.

In addition, the pre-branch processing of the data processing device of the present invention can also handle variable-length branch instructions, and is more efficient than the conventional pre-branch processing that can only handle fixed-length branch instructions. The number of branch instructions increases significantly.

Not limited to the data processing apparatus of the present invention, branch instructions are executed very frequently in pig processing apparatuses, and therefore the performance improvement effect of pre-branch processing is significant.

(3,1) Type of r branch instruction In the data processing device of the present invention, an instruction that performs a pre-branch in the instruction fetch stage is called a pre-branch instruction. The pre-branch instructions include instructions that always branch, such as unconditional branch instructions.

The branch instructions included in the data processing device of the present invention are classified into four types depending on whether the branch condition is static or dynamic and whether the branch destination is static or dynamic. However, in the data processing device of the present invention, the following two types of instructions are handled as pre-branch instructions.

The first is an instruction in which both the branch condition and the branch destination are static. This type of instructions include an unconditional branch instruction (BRA) and a subroutine call instruction (BSR).

The second is an instruction in which the branch condition is dynamic and the branch destination is static. This type of instruction includes a conditional branch instruction (B
cc) and a loop control command (ACB).

(3, 2) Functional Configuration of r-Branch Instruction Processing Circuit" FIG. 1 is a block diagram showing the overall configuration of the data processing apparatus of the present invention.

In FIG. 1, an instruction fetch unit 51. Instruction decoding section 52
．． PC calculation section 53. Operand address calculation unit 54 data calculation unit 56. The configuration of the internal circuits included in each of the external lotus interface sections 57 and the address output circuits 58 . A data input/output circuit 59 and the like are shown.

The input terminals of the instruction decoder 111 and the PC adder 132 and the input side of the address adder 124 are connected to a DISP bus 100 that transfers the displacement value of the displacement value 1 branch instruction.
It is connected at

The input side of the instruction decoder 111 and the address adder 124 is the instruction code length used for step code generation,
It is also connected to a correction value bus 102 that transfers pre-decrement values and the like during stack bush mode.

The input sides of the instruction decoder 111 and the PC adder 132 are:
It is also connected to an instruction length hash 101 that transfers the instruction code length used for step code generation.

The register file 144 and the input side of the address adder 124 are connected by an A bus 103 through which address values stored in the register file 144 are transferred.

An instruction code is input to the instruction decoder 111 from an instruction queue 112 . The output section of the instruction decoder 111 includes a branch condition generation circuit 1 that selects whether to output the branch condition specification field of the conditional branch instruction to the E stage 15 as is or to invert the condition specification and output it by pre-branch processing.
14 are provided.

The output of the augend selection circuit 131 receives the value of the instruction length bus 101 and the value of the DISP hash 100 and selects and outputs one of them, and the DPC 135 holds the PC value of the instruction decoded in the D stage 12. TPC1 that holds the value or work PC value for each step code cut
Any of the 34 values is input to a PC adder 132.

The output of the pc adder 132 is the pc adder output latch 133.
After being latched, it is output to the PO bus 05.

PO lotus 105 has latch TPC134, latch DPC
It is connected to a latch APC 136 that holds the PC value of the instruction being processed in the 135°A stage 13.

The TPC 134 has a C for inputting a new instruction address when a branch or jump occurs in the E stage 15.
There is also an input path from the AB bus 04.

The output of the correction value hash 102 and the output of the DISP bus 100 are input to a displacement selection circuit 122, and either one is input to an address adder 124.

The output of the DISP bus lOO and the output of the A bus 103 are input to the base address selection circuit 123, and the negative one is input to the address adder 124.

The address adder 124 shifts the output of the displacement selection circuit 122, the output of the base address selection circuit 123, and the values input from the A hash 103, thereby increasing the values by 1, 2, 4, and 8 times. Three-value addition is performed using the three output values of the index value generation circuit 121 as input.

The output value of the address adder 124 is output to the hash 106 through the address adder output latch 125.

During memory indirect addressing, the AO bus 06
CPU from address output port 858 through A bus 07
A latch rA126 holds the address value when outputting the address value to the external device, and a latch rA126 holds the address value when outputting the address value to the outside, and the operand address when outputting the operand address value from the address output circuit 58 to the outside of the CPU through the silent bus 107 when fetching the operand in the F stage 14. It is connected to the latch FA127 that holds the value.

Latch FAI27 is a latch 5A14 that holds an operand address value for use in E stage I5 using the operand address calculated by address adder 124.
It has an output path to 1.

The latch 5A141 has an output path to the S bus 109, which is a general-purpose data bus of the data calculation unit 56.

The CA bus 04 that transfers the address of the instruction is connected to the PC adder output latch 33, the latch TPC 134, the counter QrNPC 115 that manages the address of the instruction code to be prefetched by the instruction fetch unit 51, and the AA bus 07 that transfers the address for instruction fetch. A latch CAAI42 holds the value when outputting it from the address output circuit 58 to the outside of the CPU through the S
It is connected to the EB register 143 input from the bus 109.

Latch APC 136 has an output path to A bus 103 and launch FPC 137 for holding the PC value of the instruction being processed in F stage 14.

The latch FPC 137 has an output path to the fcPc 13B that holds the PC value of the instruction being processed in the E stage 15.

The latch CPCl38 holds the value of the least significant byte of the PC value for rewriting the S bus 109 and the branch history.
It has an output path to Nochi0PCI39.

The register file 144 is composed of general-purpose registers or work registers, and has an output route to the S bus 109 and the A bus 103, and an input route from the D bus 110.

Data calculation unit 145 which is the calculation mechanism of data calculation unit 56
has an input path from S bus 109 and has an input path from D bus 110.
It has an output route to.

The BTB (branch target buffer) 160 consists of 64 entries, which will be described in detail later, and each entry contains a branch instruction address field (25 bits), a valid bit field (l bit), a branch destination address field (31 bits), and a branch target address field (31 bits). Sequence control field (2
(see Figure 2).

The valid bit field is a field that indicates whether the corresponding entry is valid or not, and the sequence control field is a field that controls the timing of switching the instruction fetch sequence when a pre-branch occurs.

A path from latch CPCl 38 to BTB 160 is provided to register the branch instruction address in BTB 160. Further, a path from the CA lotus 104 to the BTB 160 is provided in order to register the address of the instruction to be fetched when a pre-branch occurs.

The branch destination address register 161 launches the top 30 pins of the content of the branch destination address field output from the BTB 160, and outputs a value to the counter QTNPC 115 at the timing when the instruction fetch sequence is switched.

The sequence control mechanism 162 is composed of a down counter, takes in the value of the sequence control field of the BTB 160, and counts down the value each time an instruction is fetched. Then, when the count value reaches "O", the sequence control mechanism 162 outputs a control signal to switch the command sequence.

(3, 3) r Pre-branch processing method” The block diagram of FIG. 2 shows the detailed configuration of the part particularly closely related to pre-branch processing of the configuration of the data processing apparatus of the present invention shown in FIG. Shown below.

The BTB 160 consists of 64 entries, and each entry consists of a branch instruction address field (25 bits), a valid bit field (2 bits), a branch destination address field (31 bits), and a sequence control field (2 bits).

The upper 24 bits of the branch instruction address and the second 1 bit from the lowest order are registered in the branch instruction address field.

The upper 31 bits of the branch destination instruction address are registered in the branch destination address field.

The branch destination address register 161 is 30 bits,
Launch the upper 30 bits of the output of the branch destination address field of BTB15Q.

The sequence control mechanism 162 takes in the output value of the sequence control field of the BTB 160 and counts down the value each time an instruction is fetched.

Sequence system? When the count value reaches "0", the i1 mechanism 162 outputs a control signal to switch the instruction fetch sequence to the next fetch address.

A pre-branch output pointer register PBRAPO 163 latches a POO value used at the time of pre-branch, and adjusts the output pointer register PO165 of the instruction queue 112 when a pre-branch occurs.

A decoder 190 decodes the lower 6 bits of the counter QINPC 115 and selects a matching entry in the BTB 160. That is, the decoder 190 uses the BTB 160
functions as a means of searching for entries.

A comparator 191 compares the output value of the upper 24 bits of the branch instruction address field with the upper 24 bits of the counter QINPC 115, and if they match, a match signal 179 is output.
is output as one input of the two-input AND gate 192.

The other input of AND gate 192 is provided with the 1-bit output value 180 of the valid bit field. AN
If both of the re-inputs are "1", the D gate 192 outputs a pre-branch generation signal 171 ("1") to be applied to the branch destination address register 161 and the sequence control mechanism 162. That is, this AND gate 192 functions as a means for determining the validity of the valid bit field of BTB 160.

In addition, counter QINPC115, instruction queue 11
2° Instruction queue input pointer register P1164.
An instruction decoder 111 and the like are provided.

Input pointer register PK164. The output pointer register PO165 and the pre-branch output pointer register PBRAPO163 each have a 3-bit configuration, and the value of the counter QINPC115 is used as an instruction fetch address with 2-bit data "00" added to the lower side.

In addition to a field (16 bits) for inputting an instruction code, the instruction queue 112 has a field (1 bit) indicating that a pre-branch has occurred.

Each entry in the instruction queue 112 has 16 bits and consists of 8 entries.

Note that in this embodiment, it is assumed that there is no internal cache.

Hereinafter, with reference to FIGS. 1 and 2, the procedure for pre-branch processing of a branch instruction will be explained in the following four cases.

- When a pre-branch does not occur and a branch does not occur at E stage I5.

- When a branch occurs at E stage 15 without a pre-branch.

- When a pre-branch occurs and no branch occurs at E stage 15.

- When a pre-branch occurs and a branch occurs at E stage 15.

(3, 3, 1) When r pre-branch does not occur and branch does not occur at E stage” At the same time, an instruction is fetched to external memory using the value of counter QINPC115, counter old NPC11
The lower 6 bits of 5 are decoded by the decoder 190 and B
Select one entry in TB160.

Comparator 191 compares the upper 24 bits of the branch instruction address field of the selected entry with the upper 24 bits of counter QINPC115. If the comparison results do not match, prebranch does not occur. Furthermore, even if the comparison results match, if the value of the valid focus bit field of the selected entry is "0", no pre-branch occurs. If a pre-branch does not occur, the value of the counter QINPC 115 is incremented by 0.1''. That is, subsequent instructions are fetched sequentially.

The instruction data fetched from external memory is stored in the instruction queue 11.
2, and the input pointer register P1164 is “2”.
The instruction data input to the instruction queue 112 is sent to the instruction decoder 111 via the instruction bus 170 according to the output pointer register PO 165.

As a result of the instruction decoder 111 decoding the instruction, a PO increment signal 172 is output, and the PO increment signal 172 is output accordingly.
±0(166), PO+1(167), PO+2(
168) is selected and set in the output pointer register PO165.

When the instruction decoder 111 decodes an instruction, it also counts the instruction length of the instruction, outputs the information of the counting result as a PO increment signal 172, and also transmits it to the subsequent vibe line stage.

In the next A stage 13, the branch destination address is calculated. Further, the start address of the instruction is transmitted to the launch CPCI 3B used by the E stage 15 via the latch DPC 135, the latch APC 136, and the latch PPC 137.

If the pre-branch instruction decoded by the instruction decoder 111 does not branch at the E stage 15, the instruction processing sequence is not changed.

(3, 3, 2) When the r branch does not occur and a branch occurs at the E stage" A pre-branch instruction that does not pre-branch is pipelined and the processing until it reaches the E stage 15 is (3, 3, 2)
This is the same as in case 3.1).

If a pre-branch instruction that did not pre-branch branches at E stage 15, that pre-branch instruction will be transferred to BTB16.
Registered as 0.

The address of the pre-branch instruction is input from the latch CPCl 38 to the BTB 160, and the branch destination address is passed from the EB register 143 to the CA bus 04, and further incremented by ml' by the incrementer 192.
It is input to 1TB160.

The lower 6 bits of the latch CPCl 38 excluding the lowest 2 bits are decoded by the decoder 190, and the BTB 160
One entry is selected. The branch instruction address field of the selected entry contains the branch instruction address field.
The upper 24 bits and the second 1 bit from the lowest are registered.

The branch destination address field for the selected entry contains
The upper 31 bits of the output of the EB register 143 are registered. Further, the number of memory accesses required to fetch the pre-branch instruction is calculated from the address of the pre-branch instruction and its instruction length, and the value is registered as the sequence control value in the sequence control field of the selected entry. Also, the valid bit field of the selected entry is set to "B".

Registration operation of BTB 160 in E stage 15 and I
If the reference operation of the BTB 160 in the P stage 11 occurs at the same time, the registration operation takes priority.

(3, 3, 3) When an r pre-branch occurs and no branch occurs at the E stage” At the same time, an instruction is fetched from the external memory using the value of the counter ΩINPC115, and the counter old NPC11
The lower 6 bits of 5 are decoded by the decoder 190 and B
The l entry of TB 160 is selected.

The high-order 24 bits of the branch instruction address field of the selected entry and the high-order 24 bits of the counter QINPC 115 are compared by the comparator 191, and the comparison result is - and the value of the valid bit field of the selected entry is ".
1”, pre-branch occurs.

At this time, a pre-branch generation signal 177 is output to the branch destination address register 161 and the sequence control mechanism 162.

In response to the pre-branch generation signal 177, the branch destination address register 161 latches the upper 30 bits of the output from the branch destination address field of the BTB 160, and the latch 174
latches the lower one bit of the branch destination address field of BTB 160. The sequence control mechanism 162 is BTB
Launches the output (2 bits) from the sequence control field of 160.

The number of instruction fetches required to fetch the entire branch instruction is set in the sequence control field.

The value sent to the sequence control mechanism 162 is counted down by "1" each time an external memory access is completed. Then, the value in the sequence control mechanism 162 is “0”.
”, an instruction sequence switching signal 178 is output.

By outputting this instruction sequence switching signal 178, the value of the branch destination address register 161 is changed to the counter QINPC.
115 cents. Also, the upper 2 bits of the input pointer register P1164 after incrementing are the upper 2 bits of the pre-branch output pointer register PBRAPO163.
The value of latch 174 is written to the lower l bits of pre-branch output pointer register PBRAPO 163, respectively.

If the end of the branch instruction does not end at a word boundary or the beginning of the branch destination instruction does not start from a word boundary, an invalid code is inserted between the branch instruction and the branch destination instruction in the instruction queue 112. be done. The brake branch output pointer register PBRAPO 163 is used to correct this invalid code.

Instruction queue 11 when pre-branch occurs in Figure 3
2 shows the relationship between branch instructions and branch destination instructions in 2.

What is shown in FIG. 3 (al) is that the end of the branch instruction (shown with hunting) ends at a word boundary,
If the beginning of the branch destination instruction (shown with cross-hunting) does not start on a word boundary, the end of the branch instruction (shown in Figure 3) does not end on a word boundary, and the branch If the beginning of the previous instruction starts on a word boundary, what is shown in Figure 3 tc+ is that the end of the branch instruction does not end on a word boundary,
This is the case when the beginning of the branch destination instruction does not start on a word boundary.

In each case of Figure 3 fat, fbl and (C1,
There is an invalid code between the branch instruction and the branch destination instruction, and the branch output pointer register PBRAPO 163 is used to adjust this.

When a branch instruction that has generated a prebranch is taken into the instruction queue 112, by referring to the least significant bit of the branch destination address field of the BTB 160, the prebranch generation field of the entry corresponding to the first halfword is set to “ 1” cent.

The branch instruction that caused the pre-branch is sent to the instruction decoder 111
When the instruction data is sent to the instruction data, a pre-branch instruction signal 171 is sent simultaneously with the instruction data, and it is transmitted that this is the instruction that generated the pre-branch.

When the instruction decoder 111 completes decoding the instruction that generated the prebranch, a prebranch instruction decode completion signal 173 is output instead of the PO increment signal 172.

The selector 176 receives the BRIB branch instruction decoding completion signal 1.
73, the BRIB branch output pointer register P
Select the output of BRAPO163 and set it in output pointer register PO165. As a result, invalid code intervening between the branch instruction and the branch destination instruction is ignored.

The instruction decoder 111 transmits information indicating that the decoded instruction is a prebranched instruction to the subsequent pipeline stage. Further, the PC calculation unit 53 calculates the branch destination address and uses it as the pc value of the next instruction.

Further, the branch condition generating circuit 114 inverts the branch condition of the pre-branched instruction.

Furthermore, if the pre-branch prediction is incorrect, it is necessary to return the instruction sequence to the instruction following the branch instruction. Therefore, in the A stage 13, the address of the pre-branch instruction and the instruction length of the pre-branch instruction are added to calculate the address of the next instruction.

This transfers the value of the latch APC 136 to the address adder 1 through the A bus 103 and the base address selection circuit 123.
24, and the instruction length of the pre-branch instruction is sent to correction value bus 1.
02 and the displacement selection circuit 122 to the address adder 124, and the index value generation circuit 121 outputs "O".
24 and the address adder output latch 125
is set to

This address is transmitted to the launch 5A 141 through the AO bus 06 and the latch FA 127, and is used in the E stage 15.

If the prebranched prebranch instruction does not branch at E stage 15, the instruction sequence is not changed at E stage 15.

(3, 3, 4) When an r pre-branch occurs and a branch occurs at the E stage" The pre-branch instruction that causes the pre-branch is decoded by the instruction decoder 111, and the processing until reaching the E stage 15 is ( 3, 3, 3).

The fact that the pre-branch instruction that caused the pre-branch branches at E stage 15 means that the pre-branch was incorrect. Therefore, it is necessary to return the sequence to the instruction following the pre-branch instruction. Since the address of the instruction following the pre-branch instruction is set in the latch S^141, the value of the latch 5A141 is set in the EB register 143 via the t-s bus 109, and a branch is generated in the E stage 15.

In addition, after a branch occurs in E stage 15, in order to prevent a prebranch from occurring the next time the same prebranch instruction is executed, the bit field of the corresponding entry in the BT8160 is set to "0". do.

In the prebranch processing described above, BTB1
60 employs a direct mapping method, but other methods may of course be used.

Furthermore, in this embodiment, only branch instructions whose branch destination is determined statically are used as pre-branch instructions, but even for branch instructions whose branch destination is dynamic, there is a mechanism to check whether the pre-branched branch destination is appropriate. If it is provided, it can be processed as a pre-branch instruction.

〔Effect of the invention〕

As described in detail above, according to the present invention, even if an invalid code exists between the branch instruction and the branch destination instruction in the instruction queue when a branch occurs, an output exclusively for branching can be performed. Since the output from the instruction queue is corrected by the pointer and the branch destination instruction is output from the beginning, branch processing is performed correctly, and therefore the pipeline processing mechanism operates more efficiently and exhibits high data processing capacity. .

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an example of the overall configuration of a data processing device according to the present invention, FIG. 2 is a block diagram showing a more detailed configuration of a portion related to the hybrid branch processing, and FIG. 3 is a block diagram showing an example of the overall configuration of a data processing device according to the present invention. A schematic diagram showing the relationship between branch instructions and branch destination instructions in the instruction queue of a processing device, FIG. 4 is a block diagram showing the overall schematic configuration of the data processing device of the present invention, and FIG. 5 shows the data processing of the present invention. FIG. 6 is a schematic diagram showing a schematic configuration of a pipeline processing mechanism of a conventional data processing device; FIG. 7 is a schematic diagram showing a schematic configuration of a pipeline processing mechanism of a conventional data processing device; FIG. FIG. 8 is a schematic diagram showing the procedure, and FIG. 8 is a schematic diagram showing the configuration of a branch target node of a conventional data processing device. III...Decoder 112...Instruction queue 160...BTB (branch target notohasofa)
161... Branch destination address register 163... Pre-branch output pointer register PBR
APO164...Input pointer register P1165...
...Output pointer register P0166, 167, 168
... Output pointer incrementer 173 ... Pre-branch instruction decoding completion signal 176 ... Selector 190 ... Decoder (entry search means) 192 ...
・NO gate (Effectiveness judgment means) In the figures, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] (1) Consists of an instruction address register that stores the address of the instruction to be fetched, an instruction address field that stores the address of a branch instruction, and information that indicates the validity of the entry. a table including a valid entry field for storing a branch destination instruction address, and a branch destination address field for storing the address of a branch destination instruction, and searching the instruction address field of the table using the stored value of the instruction address register to find that both stored values match. Entry search means for detecting an entry; Validity determination means for determining the validity of an entry detected by the entry search means based on information in a valid entry field of the entry; and an instruction for dividing one instruction into multiple parts and storing them. and a branch instruction display field that stores information indicating that the head of the instruction of the entry determined to be valid by the validity determining means is stored in the corresponding entry. , an input pointer register that instructs which entry in the instruction queue the head of the next instruction is to be input to, an output pointer register which instructs which entry in the instruction queue the instruction is to be output from, and the output pointer an output pointer incrementer that increments the value of the register, and a next position of the output pointer based on the value of the input pointer register and the contents of the branch destination address field when the validity determining means determines that the value is valid. A branch output pointer register that calculates and holds an exponent value, and the contents of the instruction field and branch instruction display field of the instruction queue are taken in, decoded, and a predetermined signal is output when the instruction is determined to have caused a branch. a decoder to output, a value of the branch output pointer register when the predetermined signal is output from the decoder, and a value of the output pointer incrementer when the predetermined signal is not output. and a selector for inputting the output pointer to the output pointer.