JPH06161748A - Subroutine return prediction mechanism - Google Patents

Abstract

(57) [Summary] [Object] To provide a mechanism for removing a bubble in a pipeline and giving a return address without using a complicated procedure when using a stack in a pipeline type computer. A mechanism for generating an expected subroutine return address in response to an input of a subroutine return instruction in a computer pipeline, which has a ring pointer counter and a ring buffer connected thereto. The ring pointer of the ring pointer counter is changed when either a subroutine call instruction or a return instruction enters the pipeline. The buffer position of the ring buffer is such that the value of the input is stored in the buffer position designated by the ring pointer when the subroutine call instruction enters the pipeline. The ring buffer gives a value from the buffer position pointed to by the ring pointer when the subroutine return instruction enters the computer pipeline, and this value becomes the expected subroutine return address.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for changing a control flow in a pipeline type computer, and more particularly to processing instructions related to a subroutine in a computer having a highly pipelined structure. Pertain to.

[0002]

2. Description of the Related Art The concept of making instructions pipelined in a computer is well known. The processing of a single instruction occurs in many different stages, such as fetching, decoding and executing. In pipelined computers, each of the various stages operates on various instructions simultaneously. For example, if the length of the pipeline is only three stages, then while the first instruction that has passed through the pipeline is being executed by the third stage, the second instruction that enters the pipeline is Performed in two stages, while
The third instruction entering the pipeline is executed by the first stage. The pipeline configuration is a very efficient instruction processing method as compared with the case where the processing of the second instruction is started after waiting for the single instruction to be completely processed. In the normal flow of a computer program, it is easy to see which instruction goes into the pipeline next. In most cases, the next instruction in sequence enters the pipeline, so, for example, instruction 101 enters the pipeline after instruction 100.

One exception to this normal flow of control is known as a subroutine. A subroutine is a program or set of instructions that can be called to perform the same task at different points within a program or different programs. For example, instruction 1
00 calls a subroutine that begins execution at instruction 200. The subroutine executes instructions 200-202 and then returns to the main flow at instruction 102. In addition, the same subroutine of instructions 200-202 is called from a number of different locations in the main stream and returns to various locations in the main stream.

These subroutines pose a problem for computers of significant pipeline structure (those with multiple stages in the pipeline). The instruction that calls the subroutine contains enough information to determine which is the next instruction to enter the pipeline (ie, the first instruction in the called subroutine),
The return instruction in the subroutine does not include such information. In fact, the return instruction must go through all stages of the pipeline before the return address is known from the return instruction. If the computer is delayed until the return instruction passes through the pipeline until it enters another instruction, a bubble with no instruction occurs after the return instruction, degrading the performance of the computer.

To avoid these bubbles, a mechanism known as the stack was used. Basically, the stack stores the return address when the subroutine is called, and when the subroutine is completed and control is returned to the main flow by the return instruction, this return address is searched in the stack and Sent to the pipeline. Therefore, the pipeline can return control to the main flow by putting the appropriate instructions into the pipeline. Bubbles in the pipeline are eliminated by holding a stack of return addresses and using these return addresses to search for the next instruction when returning from the subroutine.

[0006]

The problem with the stack mechanism is that the size of the stack is limited and the procedure for handling stack overruns and underruns when multiple subroutines are called is complicated. That is. In other words, if the stack contains 12 locations, only 12 subroutines can be called at a time without resorting to the complicated procedure for stack overruns.

Therefore, there is a demand for a mechanism that gives a return address, eliminates bubbles in the pipeline, and does not require the complicated procedure required when using the stack.

[0008]

[Means for Solving the Problems] This and another request are
It is satisfied by the present invention to provide a ring buffer that mimics the characteristics of the stack mechanism to predict the subroutine return address. This ring buffer stores the expected return address each time the subroutine is called (ie, each time it enters the pipeline) in one of its ring buffer locations. When a subroutine return instruction enters the pipeline, the expected return address is sent from the ring buffer to the pipeline so that the appropriate instructions from the main stream can enter the pipeline. in this way,
Bubbles in the pipeline are removed.

The ring buffer used in the present invention is of limited size and has, for example, eight positions for storing eight different return addresses.
If more than eight subroutines are called without a return, the earliest stored return address in ring buffer form is overwritten with the more recent return address stored in that ring buffer. Eventually, the expected return address in the ring buffer is incorrect when the subroutine associated with the overwritten return address completes processing through the pipeline, and control flow is changed to main flow. Becomes The actual return address of the return instruction is known at the end of the pipeline when the return instruction has completely traversed the pipeline. This actual return address is then compared to the expected return address in the ring buffer. If this comparison indicates that the expected return address is incorrect, the pipeline is flushed and the instruction is restarted with the actual return address.

For well-functioning programs, the return address is correctly predicted over 90% of the time.

[0011]

1 is a block diagram showing the control flow of a computer program. Instructions 100-107 are instructions that make up the main flow of instructions 10. Command 200
The second stream at -202 constitutes subroutine 12.
In the example of FIG. 1, the subroutine 12 has two instructions 1
Called from one of 01 and 104. When the subroutine 12 is called from, for example, the instruction 101, the computer executes the instructions 200 and 201, and the instruction 202 returns to the main flow 10. Execution of main flow 10 is instruction 1
It will be resumed at 02. However, subroutine 12
, Is called from instruction 104, subroutine 12 directs the instruction flow to the main flow 10 at instruction 105.
Must be returned to.

As is apparent from the above description of the flow, the main flow 10 is the subroutine 1 in one of two places.
You can return from 2. In larger programs, the return to the main flow can occur at any number of locations. When executing instructions in a pipelined computer, many operations are performed in successive stages of the pipeline. Computer pipeline configurations are well known and involve operating simultaneously on separate instructions in separate stages of the pipeline. For example, if there are five stages in the pipeline, different instructions are executed concurrently in each of these five stages, with each stage performing different operations on individual instructions.
Pipelining instructions is a way to process instructions much more efficiently than waiting for each instruction to complete before starting to process the next instruction.

A pipeline constructed in accordance with the present invention is shown in FIG. 2 and is designated by the reference numeral 20. The pipeline 20 has a program counter buffer 21, which buffers the program count or "PC" in the instruction cache 22. A large number of instructions are stored in the instruction cache 22 at any time. Instruction cache 2
When 2 receives the PC from the program counter buffer 21, the coded instruction is transferred to the instruction fetch decoder 24.
Sent to. As the name implies, the decoder 24 decodes the instruction from the instruction cache 22 designated by the program counter buffer 21. According to the pipeline technique, the decoder 24 decodes the first instruction of the pipeline while the second instruction is searched in the instruction cache 22.

Decoded instructions are sent from decoder 24 to instruction buffer 26, which merely buffers the decoded instructions. Following the instruction buffer 26 is an issue logic circuit 28 which performs a scheduling type function. The other stages in the pipeline are shown at reference numeral 30, but this could be any number of stages. The final stage of the pipeline 20 is the execution stage 32, which executes instructions. Since pipeline 20 of FIG. 2 has six stages, up to six instructions can be processed simultaneously.

Usually, after one instruction, for example, the instruction 100, is called from the instruction cache 22, the next instruction is called from the cache 22 and becomes the next instruction, for example, the instruction 101 in order. In the case of a calling instruction, such as instruction 101, the decoded instruction itself provides the PC for the next instruction to be executed. In this case, the next instruction to be executed after the calling instruction is the first instruction of the subroutine, for example instruction 200. in this way,
A full instruction is held in pipeline 20 by using either the next instruction in turn (PC + 1) or the instruction pointed to by the decoded call instruction. Pipeline 20 is not used efficiently if there are bubbles (no instructions) in one or more stages in the pipeline. Such bubbles can potentially occur on subroutine return instructions, such as instruction 202, as described below.

Pipeline 20 by a subroutine return instruction
The reason why the bubble occurs is that the actual location (actual return address) of returning to the main flow is unknown until the subroutine return instruction is executed in the execution stage 32. If no further measures are taken, the address of the next instruction is not known and stages 22-30 are empty after the subroutine return instruction. As mentioned earlier,
This bubble indicates that the usage efficiency of the pipeline 20 is low.

In order to prevent bubbles in the pipeline 20, there must be a mechanism for predicting what the next instruction to process after the pipeline 20 return instruction.
Some computer architectures can use a stack that stores each return address each time the subroutine is called. This stack stores these return addresses in a last in, first out manner so that when the next return instruction is decoded in the pipeline, the last return address stored in the stack is the first return generated from the stack. It becomes an address.
However, in some computer architectures the stack cannot be used.

The present invention performs the basic functions of the stack without actually using the stack device.
(The present invention is useful for architectures without stacks, but also for architectures that use stacks.) Rather, as shown in FIG.
Is used. This ring buffer 34 holds a relatively small number of expected return addresses. The expected return address held in the ring buffer 34 is used to fetch the next instruction from the instruction cache 22 when the instruction fetch decoder 24 decodes the return address, as described in detail below. . The pipeline 20 then continues to operate based on the next instruction without forming a bubble on itself. If the expected return address is finally found to be incorrect, the instruction sequence is aborted and execution continues with the correct instruction sequence.

The ring buffer 34 is, for example, a buffer having a depth of 8 and stores an expected return address at each position. As described above, the instruction cache 22 receives the program count (PC) from the program counter buffer 21 and searches for an instruction. This PC is also sent to adder 38, which adds the value 1 to PC.
This value PC + 1 is sent to the ring buffer 34 and the multiplexer 36. During a normal instruction sequence without a subroutine or branch, one instruction is followed by another instruction in sequence, PC = PC + 1. If the program count for the first instruction is PC, then the program count for the next instruction will be PC + 1 and the third instruction will be PC + 2. In another embodiment, the increment value is different than 1, eg, the address of the instruction following instruction 300 is 304 and then 308.
Becomes In this case, the value of PC changes by 4, so P
C = PC + 4.

The multiplexer 36 also receives inputs from the instruction fetch decoder 24. One input is the called subroutine address (CSA) contained in the calling instruction, which is received from the instruction cache 22 and decoded by the decoder 24. The subroutine address called above is
It is selected from the multiplexer 36 as the PC for the instruction cache 22 when the decoded instruction is a call instruction. When the instruction decoded by the instruction fetch decoder 24 is a return instruction and not a call instruction, the ring buffer 34 is passed through the RP counter 40.
Is sent to. The RP counter 40 includes a ring pointer (RP) that indexes the ring buffer 34. Ring buffer 34 sends to multiplexer 36 the expected return address (PRA) pointed to by RP. Under the control of the signal from the instruction fetch decoder 24, the multiplexer 36 operates in the instruction cache 2
Select PRA as the PC for 2. The operation of the ring buffer 34 will be described below.

The three inputs of the multiplexer 36 for selecting the PC have been described above. The first of these is PC + 1, which is selected by the multiplexer when the instruction decoded by instruction fetch decoder 24 is neither a call nor a return instruction. The second input to the multiplexer 36 is the called subroutine address (CSA) contained in the decoded input, which is the instruction fetch decoder 2
4 sent to the multiplexer 36. C
The SA is used when the decoder 24 decodes the calling instruction. The third input to multiplexer 36, described above, is the expected return address (PRA) sent by ring buffer 34 to multiplexer 36 when the return instruction was decoded by decoder 24. The operation of the ring buffer 34 will be described below.

As described above, the ring buffer 34 is
It has a limited number of buffer locations to store expected return addresses. The buffer position of the ring buffer 34 is indexed by the ring pointer (RP) held in the RP counter 40. The operation of the RP counter is simple. When the RP counter 40 receives a signal from the decoder 24 indicating that the decoded instruction is a call instruction, the RP counter 40 is incremented by 1 and points to the next higher buffer position. Expressed as an expression, RP = RP + 1 when the subroutine is called. When the instruction decoded by the decoder 24 is a return instruction, RP is decreased by 1. This gives the equation RP = RP-1 for the subroutine return instruction.

The value put in the position in the ring buffer 34 designated by the RP when decoding the subroutine calling instruction is the PC after the address of the calling instruction is loaded in the position of the ring buffer 34 designated by the RP. Is the next address value of. This value PC + 1
Becomes PRA. The PRA is sent by the ring buffer 34 to the multiplexer 36 when the subroutine return instruction is decoded by the decoder 24. Loading PC + 1 into the location indicated by RP and returning PRA from it is done based on the ring buffer control signal generated by decoder 24.

An operation example of the ring buffer 34 will be described below. The first instruction to enter pipeline 20 is instruction 100. This is instruction cache 2 using PC = 100
2 is searched. The instruction is decoded in the decoder 24, which is neither a subroutine call nor a return, so the control signal from the decoder 24 selects the next PC to be PC + 1. In this case, the value of PC + 1 is 1.
01, so instruction 101 is sent from instruction cache 22 to decoder 24.

Instruction 101 is a subroutine call (see FIG.
(See reference), and the decoder 24 sends a signal to the RP counter 40. The RP of the RP counter 40 is increased from RP = 3 to RP = 4, for example, and points to a new buffer position RP (4) in the ring buffer 34. The value of PC + 1, in this case 101 + 1 = 102, is stored in ring buffer 34 at ring buffer location RP (4).

When the decoder 24 decodes the call instruction 101, it sends a control signal to the multiplexer 36 and also calls the called subroutine address (CSA).
As the next PC. Since the CSA is included in the decoded subroutine call instruction 101, it can be sent to the multiplexer 36 by the decoder 24.

Subroutine 12 is executed such that instruction 200 is retrieved from instruction cache 22 and decoded. Since the instruction 200 is neither a call instruction nor a return instruction, the instruction 201 is fetched from the instruction cache 22 (PC = PC + 1 = 201). Similarly, instruction 201 is followed by instruction 202 in the pipeline. However, the instruction 202 is a subroutine return instruction.

The subroutine return instruction 202 is the decoder 2
When decoded by 4, the potentially next instruction is either instruction 102 or 105. Using the ring buffer 34 (see FIG. 1), the correct return address can usually be provided. When decoding the return instruction, the decoder 24 sends a signal to the RP counter 40. The PRA designated by the RP included in the RP counter 40 is sent to the multiplexer 36. In this example, P associated with instruction 102 stored in RP (4)
RA is sent to multiplexer 36. Decoder 24 sends a control signal to multiplexer 36 to cause it to select PRA as the next PC. Therefore, using the PRA sent, the instruction 102 is sent from the instruction cache 22 and decoded by the decoder 24. Also, the RP in the RP counter 40 is decremented and newly points to RP (3).

The operation of the pipeline 20 when the PRA is correct has been described above. However, in some situations the PRA is incorrect. For example, this may occur if the subroutine causes a return of the main stream 10 to another location rather than the instruction immediately following the calling instruction. The PRA is wrong until the return instruction is completely executed through the pipeline 20. It is at that point that the actual return address for the return instruction is known. In the meantime, a number of instructions following the return instruction are input and placed in various stages of pipeline 20. It must be ensured that the pipeline 20 takes corrective measures as the actual return address is different from the expected return address.

The actual return address (ARA) is sent to the compare unit 42 from the end of the pipeline. At the same time the comparison unit 42 receives the ARA, it also receives the PRA. The PRA is sent to the comparison unit 42 via a series of delay latches 44. PRA and ARA are compared. If the comparisons do not match, the mismatch comparison signal is the decoder 2
4 and issue logic 28. By this mismatch comparison signal, all the instructions that have entered the pipeline 20 after the return instruction are flushed from the pipeline 20.
Multiplexer 36 receives the ARA on its fourth input, so the PC sent to instruction cache 22 becomes this ARA after a mismatch comparison is confirmed. The pipeline 20 then processes a new series of instructions beginning with the instruction at the actual return address (ARA).

Ring buffer 34 has only a limited number of buffer positions. As a result, a wrong return address may be given by the ring buffer 34. For example, the ring buffer 34 has eight positions R
Suppose we have P (0) -RP (7). If eight subroutines are called and no return is made, the ring buffer 34 will be full. When the ninth subroutine call is made, the first ring buffer position RP (0) is overwritten by the standard ring buffer method. PRA that was in RP (0) before that
Is essentially lost by overwriting a new PRA in this position. Thus, if nine subroutine returns have occurred, the correct subroutine return address for the first subroutine called is no longer found in RP (0). R, not
The new value of PRA stored in P (0) is generated as PRA. What is wrong with this PRA is
And ARA are finally determined. When this comparison mismatch is confirmed, the appropriate corrective measures described above are taken.

During the execution of a program by a pipelined computer, an event may occur in which the pipeline must abort all instructions in all its stages. This is also referred to as "flushing" the pipeline. At this time, all the work being executed in the pipeline 20 is eliminated. These excluded instructions are called "Shadow". Typically, the front end of the pipeline begins executing instructions at some error handling address.

For purposes of explanation, the event of flushing the pipeline is called a "trap". Examples of these traps are
Mispredicted branches, virtual memory page defects, resource busy, and hardware parity errors. In order to improve the performance of the subroutine return prediction mechanism, the ring buffer 34 stores the instruction causing the trap in the pipeline 2
It needs to be backed up to the point where the buffer was when it passed through the 0 ring buffer stage.
Ring buffer 3 until no trap is found
Keeping a copy of each change that occurs for 4 is an overly costly way.

In the embodiment of FIG. 3, this problem is solved by providing another ring pointer, the "confirmation ring pointer" or CRP, held in the CRP counter 45. CRP changes similarly to RP, ie it is increased when a subroutine call instruction is seen and decreased when a subroutine return instruction is seen. The difference is that the CRP counter 45 monitors the instructions that reach the final stage of the pipeline 20. Changes are made to the CRP based on the instructions in the last stage. When the trap occurs, the RP of the RP counter 40 is set to the CRP value of the CRP counter 45.

This causes the RP to maintain the correct synchronization when a new instruction begins executing after the trap. A certain subroutine call instruction may occur in the shadow of the trap in which the input of the ring buffer 34 is written,
Subsequent expectations of the subroutine return instruction will be incorrect. However, RP is in sync and as soon as RP passes the wrong input, ring buffer 34 is in good condition again.

The present invention is not limited to the above-described embodiments, but can be applied to pipelines of various sizes having ring buffers of various sizes.

[Brief description of drawings]

FIG. 1 is a block diagram of a program having a main flow and a subroutine.

FIG. 2 is a block diagram of a pipeline using an embodiment of the present invention.

FIG. 3 is a block diagram of a pipeline using another embodiment of the present invention.

[Explanation of symbols]

 10 ... Main flow of instruction, 12 ... Subroutine, 100-107, 200-202 ... Instruction, 20 ... Pipeline, 21 ... Program counter buffer, 22 ... Instruction cache, 24 ... Instruction fetch decoder, 26 ... Instruction buffer, 28 ... Issuing logic circuit, 32 ... Execution stage, 34 ... Ring buffer, 36 ... Multiplexer, 40 ... RP counter.

Claims (7)

[Claims] 1. A structure for generating an expected subroutine return address in response to an input of a subroutine return instruction in a computer pipeline, wherein a subroutine call instruction is incremented as it enters the computer pipeline and the subroutine return instruction is A ring pointer counter containing a ring pointer that is decremented upon entering the computer pipeline; and a ring buffer connected to the ring pointer counter and having a buffer location and an input and an output. The buffer stores the value at the input when the subroutine call instruction enters the computer pipeline into the buffer location pointed to by the ring pointer, and when the subroutine return instruction enters the computer pipeline. Gives the value of the output from the indicated buffer position pointer, the value of the output is structure, which is a subroutine return address to be expected above. 2. A comparison unit connected to the ring buffer for comparing the actual return address generated by the computer pipeline in response to processing the return instruction with the expected return address for the return instruction. 2. The structure of claim 1, wherein the unit has an output that provides a compare mismatch signal when the actual return address is not the same as the expected return address. 3. An instruction cache storing coded instructions having an input for receiving a program count indexing the coded instructions and an output provided with the indexed coded instructions. And an instruction fetch decoder that has an input connected to the output of the instruction cache and decodes a coded instruction, and the coded instruction is a subroutine call address when the coded instruction is a subroutine call instruction. And a multiplexer control signal, a ring pointer counter control signal, and an instruction fetch decoder having as output the decoded instruction. The instruction fetch decoder is connected to an execution stage and is decoded. Instructions are executed and input to the above instruction cache A gram counter is connected, the counter having an output for providing a program count to the input of the instruction cache and an input, and further having a plurality of inputs and a control input connected to the multiplexer control signal output of the instruction fetch decoder. , A multiplexer having an output connected to the input of the program counter, the adder having its input connected to the output of the program counter and the output of the adder being the program count plus one. Connected to one of the multiplexer inputs provided with an equal value, and further provided with a ring pointer counter, the input of which is connected to the instruction fetch decoder to receive a ring pointer counter control signal,
The ring pointer counter includes a ring pointer pointing to a buffer position in response to a ring pointer counter control signal, the ring pointer being incremented when the instruction fetch decoder decodes a subroutine call instruction and the instruction fetch decoder A ring buffer is provided which is reduced when decoding a subroutine return instruction and which further has an input connected to the output of the adder, a plurality of buffer locations and an output connected to one of the multiplexer inputs. This ring buffer stores the above value in the buffer position designated by the ring pointer when the subroutine call instruction is decoded, and is designated by the ring pointer when the subroutine return instruction is decoded. Supplied from Ffa position the value in the ring buffer output, a computer pipeline, wherein the value of the ring buffer output is a subroutine return address to be expected. 4. A comparison unit connected to the ring buffer, wherein the actual return address generated by the computer pipeline in response to processing the return instruction is the expected return address for that return address. 4. The pipeline according to claim 3, further comprising a comparing unit for comparing, the output of the unit being provided with a compare mismatch signal when the actual return address is not the same as the expected return address. 5. Further comprising means for processing the correct sequence of instructions starting with the instruction pointed to by the actual return address when the comparison mismatch signal indicates a mismatch between the expected return address and the actual return address. The pipeline according to claim 4, characterized in that 6. A confirmation ring pointer counter connected to the execution stage and the ring pointer counter, wherein the confirmation ring pointer contained in the counter is incremented when the execution stage receives a subroutine call instruction and the execution stage is 4. The pipeline of claim 3, wherein the ring pointer counter is provided with a confirmation ring pointer which is decremented upon receipt of a subroutine return instruction and which further replaces the ring pointer when a trap occurs. . 7. A method for predicting a subroutine return address in a pipeline computer, comprising: 1 in response to a call instruction, at the address of the call instruction.
Store a value equal to the sum of the values in one of a plurality of buffer positions in the ring buffer, indicate the buffer position containing the most recently stored value, and respond the return instruction with the above instruction for the most recently stored value. And the output is an expected subroutine return address, and then indicates the buffer location containing the most recently stored value.