Source: https://patents.google.com/patent/EP0689131A1/en
Timestamp: 2019-12-06 16:18:34
Document Index: 326912508

Matched Legal Cases: ['art 1', 'art 2', 'art 1', 'art 2', 'art 1', 'art 2']

EP0689131A1 - A computer system for executing branch instructions - Google Patents
A computer system for executing branch instructions Download PDF
EP0689131A1
EP0689131A1 EP95304199A EP95304199A EP0689131A1 EP 0689131 A1 EP0689131 A1 EP 0689131A1 EP 95304199 A EP95304199 A EP 95304199A EP 95304199 A EP95304199 A EP 95304199A EP 0689131 A1 EP0689131 A1 EP 0689131A1
EP95304199A
EP0689131B1 (en
1994-06-22 Priority to GB9412487 priority Critical
1994-06-22 Priority to GB9412487A priority patent/GB9412487D0/en
1995-06-16 Application filed by SGS Thomson Microelectronics Ltd filed Critical SGS Thomson Microelectronics Ltd
1995-12-27 Publication of EP0689131A1 publication Critical patent/EP0689131A1/en
2001-08-29 Publication of EP0689131B1 publication Critical patent/EP0689131B1/en
A computer system for executing branch instructions and a method of executing branch instructions are described. Two instruction fetchers respectively fetch a sequence of instructions from memory for execution and a sequence of instructions commencing from a target location identified by a set branch instruction in a sequence of instructions being executed. When an effect branch signal is generated, the target instructions are next executed, and the fetcher which was fetching the instructions for execution commences fetching of the target instructions.
Branches are well known in the art and are essential for a computer system to execute any program. Known computer systems contain a special register, the instruction pointer register, which provides an indication of the address of the next instruction to execute. This register is usually automatically incremented after an instruction executes, so that it now indicates the address of the next sequential instruction. Branch instructions are used to change this behaviour. These branch instructions specify an alternative address (the target location) for the next executable instruction. Conditional branch instructions also specify a condition which must be met for the alternative address to be used - otherwise the instruction pointer will be incremented as usual. These branch instructions thus define the end of a block of instructions.
From the previous description, it is clear that the instruction after a branch instruction is always fetched, but is only sometimes required, and that therefore a pipeline bubble is created while determining what to do. An attempt has been made to improve this by changing the semantics of branch instructions, so that the subsequent instruction is always executed and the branch determines whether the instruction executed after that one is the one sequentially after it, or the instruction at the target location. These are called delayed branches, and the instruction immediately following the branch instruction is called a branch delay slot. Figure 1 illustrates schematically this operation. The branch instruction is detected in the decode stage. The branch delay slot is Inst 1, which is always executed. If the branch is taken, then the next executed instruction will be Inst DO being the first instruction of a different block, whereas if the branch is not taken, it will be Inst 2 which is the first instruction of the next sequential block. Inst 1 must be an instruction which can always be executed, regardless of the outcome of the (conditional) branch, and it must not be an instruction which determines whether the conditional branch is to be taken. If no instruction can be found within the program which satisfies these conditions, then an instruction which has no effect (NO OP) must be inserted instead.
According to one aspect of the present invention there is provided a computer system for fetching, decoding and executing instructions comprising:
storage circuitry for holding a plurality of instructions at respective storage locations, said plurality of instructions being arranged in instruction strings, each string comprising a first instruction and a set of subsequent instructions;
instruction fetch circuitry for fetching a sequence of instructions from said storage circuitry and including an indicator for providing an indication of a next address at which a next fetch operation is to be effected;
execution circuitry for executing fetched instructions, wherein at least some of said instruction strings each includes a set branch instruction (SET) which provides an indication of a target location from which a subsequent instruction may be fetched, the subsequent instruction being from a different instruction string, and wherein said instruction fetch circuitry is operated responsive to execution of a said set branch instruction (SET) to fetch in parallel subsequent instructions from said string containing said set branch instruction and new instructions from said different instruction string commencing from said target location while said subsequent instructions continue to be executed;
a target store for holding the indication of said target location, said indication being loaded into said store on execution of said set branch instruction (SET) and being held in said store as a valid indication until execution of a subsequent set branch instruction; and
select circuitry responsive to generation of an effect branch (DO) signal indicative that further instructions to be executed are said new instructions, to cause said execution circuitry to execute said new instructions and to cause said instruction fetch circuitry to fetch again new instructions commencing from said target location.
The invention also provides a method of operating a computer to fetch decode and execute instructions which computer has storage circuitry holding a plurality of instructions at respective storage locations, said plurality of instructions being arranged in instruction strings, each string comprising a first instruction and a set of subsequent instructions the method comprising:
fetching a sequence of instructions from said storage circuitry and providing an indication of a next address at which a next fetch operation is to be effected;
decoding said instrutions;
executing each instruction in turn, wherein at least some of said instruction strings each include a set branch instruction (SET) which provides an indication of a target location from which a subsequent instruction may be fetched, the subsequent instruction being from a different instruction string;
on execution of said set branch instruction, holding the indication of said target location in a target store as a valid indication until execution of a subsequent set branch instruction, fetching in parallel subsequent instructions from the string containing said branch instruction and new instructions from said different instruction string commencing from said target location;
continuing to execute said subsequent instructions until an effect branch signal is generated which indicates that further instructions to be executed are said new instructions; and
responding to said effect branch signal by commencing execution of said new instructions and fetching again new instructions commencing from said target location.
In one embodiment said instruction fetch circuitry comprises two instruction buffers, a first buffer for holding subsequent instructions connected to said execution circuitry, and a second buffer for holding new instructions wherein the contents of said second buffer are copied into said first buffer responsive to generation of said effect branch (DO) signal.
In the described embodiment said instruction fetch circuitry includes two instruction fetchers for fetching respectively said subsequent instructions and said new instructions and wherein said select circuitry is operable to connect a selected one of said instruction fetchers to said execution circuitry.
The effect branch signal is generated when the branch point, at which the branch is to be taken, is identified. This can be done in a number of ways. For example, a further instruction can be located in the string of instructions being executed prior to the branch point in which case said further instruction will identify the branch point which will be held in a branch point register. The contents of the branch point register can then be compared with an instruction pointer register holding an indication of the address from which a next instruction would normally be fetched and when the two are equal the effect branch signal is generated. Alternative methods for identifying the branch point are also discussed herein.
To avoid the need for state indicators, the present invention provides in another aspect a computer system for fetching, decoding and executing instructions comprising:
execution circuitry for executing fetched instructions, wherein at least one of said instruction strings includes a set branch instruction (SET) which provides an indication of a target location from which a subsequent instruction may be fetched, the subsequent instruction being from a different instruction string, and an effect branch instruction different from said set branch instruction and located at the branch point after which said new instructions are to be executed and wherein said instruction fetch circuitry is operated responsive to execution of a said set branch instruction (SET) to fetch in parallel subsequent instructions from said string containing said set branch instruction and new instructions from said different instruction string commencing from said target location while said subsequent instructions continue to be executed; and
select circuitry responsive to execution of a said effect branch (DO) instruction to cause said execution circuitry to execute said new instructions if a condition determined by the effect branch instruction is satisfied.
The invention also provides in a further aspect a method of operating a computer to fetch decode and execute instructions which computer has storage circuitry holding a plurality of instructions at respective storage locations, said plurality of instructions being arranged in instruction strings, each string comprising a first instruction and a set of subsequent instructions the method comprising:
decoding said instructions;
executing each instruction in turn, wherein at least one of said instruction strings includes a set branch instruction (SET) which provides an indication of a target location from which a subsequent instruction may be fetched, the subsequent instruction being from a different instruction string;
on execution of said set branch instruction, fetching in parallel subsequent instructions from the string containing said branch instruction and new instructions from said different instruction string commencing from said target location;
continuing to execute said subsequent instructions until an effect branch instruction is executed which is located at the branch point after which new instructions are to be executed and which indicates that further instructions to be executed are said new instructions if a condition determined by the effect branch instruction is satisfied; and
responding to said effect branch signal by commencing execution of said new instructions.
Figure 1 is a schematic illustrating a known branching system;
Figure 2 is a schematic illustrating the branch system of the present invention for non-conditional branches;
Figure 3 is a schematic illustrating the branch system of the present invention for conditional branches;
Figure 4 is a simple block diagram of a pipelined processor;
Figure 5 is a circuit diagram of an instruction fetcher;
Figure 6 is a circuit diagram of a computer system for implementing branch instructions;
Figure 7 is a circuit diagram of an instruction fetcher with kernel and descriptor functions;
Figure 8 is a schematic diagram illustrating procedure calling;
Figure 9 is a sketch illustrating states for performing procedure calls;
Figure 10 is a block diagram illustrating an alternative implementation for an instruction fetch circuit;
Figure 11 is a block diagram illustrating a non predictive fetcher; and
Figure 12 is a block diagram illustrating a predictive fetcher.
Reference will first be made to Figures 2 and 3 to explain the concept underlying the branching system of the present invention. Figure 2 illustrates three blocks of instructions in memory, Block A, Block B and Block C. Each block comprises a first instruction which in each case is a set branch instruction Set B, Set C, Set D, respectively, a sequence of subsequent instructions for example Inst A1, Inst A2 ... Inst Ai-1 in Block A and a last instruction which in each case is an effect branch instruction referred to herein as D0. Assume that the sequence of instructions in Block A is being fetched decoded and executed in a pipelined computer system. On execution of the first instruction Set B, a target location for a branch is stored, in this case identifying the memory address of the first instruction Set C of Block B. However, no action is taken at this stage other than to store the target location and possibly to set up the memory containing Block B for an access, for example by moving the relevant memory addresses to a local cache. The instructions in Block A continue to be fetched, decoded and executed until the last instruction, D0, is being executed. Execution of this instruction causes an effect branch signal to be generated which causes the execution unit to address as its next instruction the target location set up by the set instruction Set B. Thus, the next instruction to be fetched from memory is the first instruction Set C of Block B. This is indicated by the dotted arrow in Figure 2.
Figure 2 illustrates the case for unconditional branches, that is branches that will inevitably be taken. Figure 3 illustrates the position for conditional branches, that is branches that may or may not be taken depending on whether or not a condition which has been evaluated is satisfied. Figure 3 illustrates the case where a third instruction is used in addition to the set branch instruction and effect branch instruction described above with reference to Figure 2. In Figure 3 this third instruction is referred to as CONFIRM, although it will become clearer in the following that it is possible to implement conditional branches using a reject instruction with the opposite semantics.
Figure 3 illustrates three sequences of instructions held in memory as Block A, Block B and Block C. Block B is shown contiguous to Block A and is arranged in memory such that if instructions are fetched from memory using sequential memory addresses then instructions will be normally fetched in the sequence of Block A followed by Block B. Block C is shown located elsewhere in memory. As in Figure 2, each block comprises a first instruction which is a set branch instruction (Set C in Block A, Set B in Block B and Set E in Block C). Block A then additionally comprises a sequence of instructions to be executed including a confirm instruction and the last instruction which is the effect branch instruction. As described above with reference to Figure 2, instructions are fetched, decoded and executed. When the first instruction of Block A is executed it is identifed as a set branch instruction with a target location identifying the memory address of the first instruction Set E in Block C. Instructions in Block A continue to be fetched, decoded and executed until the confirm instruction is reached which has a condition associated with it. If the condition is satisfied, the branch is confirmed and execution of the effect branch instruction D0 at the end of Block A will cause the branch identified by the target location to be taken as indicated by the dotted line in Figure 3. Thus, the next instruction to be fetched, decoded and executed will be the first instruction Set E of Block C. If the confirm condition is not satisfied, the branch will not be taken when the effect branch instruction is executed but instead the next instruction to be fetched, decoded and executed will be the first instruction Set D of Block B which sequentially follows Block A in memory. It will readily be appreciated that once confirm instructions has been introduced, it will be necessary even to confirm unconditional branches such as that which is illustrated by way of example in Block C, where the branch is always confirmed and is not subject to a condition.
It is assumed for the purposes of the present description that any useful computer system must be capable of implementing conditional branches in addition to unconditional branches. It will be appreciated that in order to implement branches as described above with reference to Figures 2 and 3, a target register must be provided for storing the target location indicated by the set branch instruction. Moreover, for conditional branches a state indicator must be provided to indicate whether the branch is in a confirmed state or not. A detailed explanation of circuitry capable of implementing the present invention is given later. Firstly, there follows an explanation of the various different ways in which branch instructions in accordance with the present invention may be implemented.
Some of the above referenced methods can be modified still further. For example, it will be clear that for a plurality of contiguous blocks in memory as illustrated for example in Figure 3 where the set branch instruction is the first instruction of a block and the do instruction is the last instruction of a block, there will be at each block interface a do instruction immediately followed by a set instruction. This is illustrated particularly where Block A meets Block B in Figure 3. For methods which hold an indication as to whether or not the system is in a branch state, it is possible to eliminate the do instruction at the end of a block and to rely on the set instruction at the beginning of a contiguous block. Thus, Methods A and B can be modified to eliminate a different do instruction and to interpret the set instruction as follows. If the system is in a branch state, the subsequent set instruction at the beginning of the next block is executed as though it were a do instruction to effect the branch. If the system is not in a branch state when the set instruction at the beginning of the next block is executed, the branch will not be taken and the set instruction will be executed in the normal manner to set up a branch with a target location.
There will now be described a computer system for implementing branching using a split branch instruction. Figure 4 is a simplified block diagram of a pipelined computer system. This shows a memory 41 which in this example comprises a conventional RAM. The computer system includes an address bus 39 and a data bus 43 coupled to the memory 41. It will be appreciated that read and write control signals for the memory are required but they are not illustrated in Figure 4. The memory 41 holds program comprising sequences of instructions at different addressable locations, as already described above with reference to Figures 2 and 3. The memory 41 may also hold data. The data bus 43 carries data values to and from the memory 41. The address bus 39 carries memory address values for read or write operations. The computer system comprises an instruction fetch circuit 10 which is arranged to supply addresses to memory along address line 12 and to receive instructions from memory along data line 14. A decode circuit 16 is connected to receive instructions fetched by the fetch circuit and supplied on instruction line 22 and decodes them. The decode circuit 16 supplies instructions to an execution circuit 18 which executes instructions and controls a result write circuit 20 to write results of the execution into temporary registers 11. For the purposes of the present invention, the decode circuit 16, execution circuit 18, result write circuit 20 and registers 11 are conventional and are not described further herein. They are referred to together in the following as the processor 17.
The fetch circuit 10 is arranged to fetch four bytes at a time from the memory 41 and to provide instructions along instruction line 22 to the decode circuit 16. Where the instructions are of variable length, it will be appreciated that an alignment mechanism is required within the instruction fetch circuit to deal with instructions which are not exactly four bytes long and to correctly align these instructions. Circuitry to accomplish this is described in our copending Application No. (Page White & Farrer Ref. 74893 Compressed Instruction Set). The present invention can be implemented with same length or variable length instruction sets.
The fetch circuit 10 comprises two instruction fetchers, one of which will now be described with reference to Figure 5. The data line 14a and address line 12a are connected to the corresponding lines 14 and 12 illustrated in Figure 4. The fetcher includes a fetch pointer 65 which comprises a 32 bit latch containing the next address in memory from which a 32 bit word is to be read. Whenever a value is read from memory, the fetch pointer 65 is normally increased by four bytes to a new pointer address via an increment unit 38. The fetcher is arranged to read instructions from memory on data line 14 into an instruction buffer 66 from which they are output along instruction line 22 to the processor 17. For variable length instructions, a length indicator 74 is provided which receives on line 70 an indication from the instruction buffer 66 of the length of the instruction which has been output. The length indicator 74 generates an amount signal 86 which indicates the number of bytes used by the instruction being output. A byte counter 75 holds a count of the number of bytes in the instruction buffer 66 at any one time and generates a select signal 24 which determines where in the instruction buffer 66 bytes fetched from the memory 41 are to be inserted. The instruction buffer 66 also receives a remove signal 26 which causes an instruction to be removed from the buffer. Unremoved instructions are shifted along, thereby creating space at the end of the buffer for more bytes from the memory 41. The instruction buffer 66 is also responsive to a store signal 28 which causes bytes from the memory to be stored in the buffer at the location indicated by the select signal 24. The store signal 28 is derived from a latch signal 30 which is used to indicate that data can be stored from the memory.
The fetch circuit 10 of Figure 4 includes two instruction fetchers of the type described above with reference to Figure 5. Reference will now be made to Figure 6 to describe in more detail how branch instructions control the activity of the instruction fetchers. In Figure 6, the fetchers are illustrated as Fetcher A and Fetcher B. The system includes an arbitrator unit 100 which arbitrates between Fetcher A and Fetcher B for access to the memory using the full and more signals from each fetcher to determine which requires data. The full and more signals for Fetcher A are referred to at the arbitrator as more A and full A and the full and more signals for Fetcher B are referred to at the arbitrator as more B and full B. Reference numerals relating to Fetcher A correspond to those for the instruction fetcher shown in Figure 5. These numerals are not repeated again for Fetcher B, because this has precisely the same signals and operation as fetcher A. The address outputs 12a of the Fetchers A and B are supplied through an address multiplexor 102 to the address line 12. The multiplexor is controlled by a Sel A signal on line 104 from the arbitrator 100 which gives priority to the fetcher which is currently fetching instructions for execution. It will be appreciated that one of the fetchers is used to fetch instructions in the current block (and potentially the next sequential block) and the other fetcher is used to fetch instructions commencing from the target location. Both fetchers receive instructions along data line 14 and supply their instructions on line 22a to a select multiplexor 104. The output 22 of the multiplexor 104 is connected to the processor 17 which decodes and executes instructions and writes the results to temporary registers 11. The processor 17 supplies the next signal which is fed to the instruction fetchers on line 48. The processor 17 receives a wait signal on line 106 which is derived from the more signals 92 of the fetchers. As the processor 17 executes instructions it updates an instruction pointer register 108 to point to the next instruction to be executed by supplying an output on the new IP line 110 via a pointer multiplexor 112. A latch IP signal on line 114 indicates when the instruction pointer register 108 is to be updated. The output of the instruction pointer register 108 provides the current value of the instruction pointer on a current IP line 116.
The computer system of Figure 6 also includes a target pointer register 118 for holding a target location identified by a set branch instruction and a branch pointer register 120 for holding a value identifying the point at which the branch is to be taken. The computer system also includes an active fetcher switch 122 which controls which of the fetchers A and B is supplying instructions to the processor 17. There is also a compare unit 124 connected to receive the outputs from the branch pointer register 120 and the instruction pointer register 108. A check output from the processor 17 on line 126 is fed via a gate 128 to control the pointer multiplexor 112 and the active fetcher switch 122. The gate 128 also has an input on line 130 from the compare unit 124.
The remaining gates illustrated in Figure 6 are not described herein because they are illustrated for the sake of completeness only to more clearly demonstrate the connections between the signal lines.
Operation of the computer system of Figure 6 will now be described. Assume that the processor 17 is to execute block A of Figure 3. The start address identifying the beginning of the first instruction of block A is supplied to fetcher A. The first instruction is supplied on line 22a to the multiplexor 104 which is controlled by a signal on line 134 from the active fetcher switch 122 so that instructions from fetcher A are supplied to processor 17. The first instruction is a set branch instruction Set C which is identified by the set branch execution unit 136 forming part of the processor 17. The set branch execution unit 136 generates the appropriate target location on target line 138 and a set signal on line 140. The set signal is used to activate the begin signal 42 for fetcher B so that that fetcher is initialised to commence starting to fetch instructions from the target location. The target location is also stored in the target pointer register 118. Instructions in block A continue to be supplied by fetcher A from memory to the processor 17 and executed. On execution of the confirm instruction, the condition for the confirm instruction is evaluated and the state indicator 132 is appropriately set. The condition line 145 indicates the state of the system which is selectively supplied to the stop lines 54 and the fetchers as described later. The following description assumes that the condition for the confirm state has been positive so that the system is in a branch state. After fetching decoding and execution of further instructions up to and including Inst A-1 in block A, the next instruction is an effect branch instruction. This is executed by the do instruction execution unit 142 which forms part of the processor 17. On execution of the effect branch instruction by this unit 142, the branch point is calculated (the first address of the first instruction at the beginning of the next sequential block) and is supplied to the branch pointer register 120 along line 144. The branch point is also supplied to the stop latches 50 of the fetchers. In this case, the stop signal 54 is asserted for Fetcher A via the condition line 145 and not for Fetcher B. Therefore Fetcher A latches the stop address so that it will stop fetching when that address is reached. When the branch point stored in the branch pointer register 120 matches the address of the next instruction stored in the instruction pointer register 108, the output of the compare unit 124 causes an effect branch signal to be asserted on line 146. This controls the instruction pointer multiplexor 112 to update the instruction pointer register 108 from the target pointer register 118 which, it will be recalled, holds the target location identified in the set branch instruction. Furthermore, the effect branch signal 146 is supplied to the active fetcher switch 112 which causes fetcher B to become the active fetcher commencing fetching from the target location so that the branch is taken. The output of the active fetcher switch 112 controls the instruction multiplexor 104 to switch its inputs.
The desription given above relating to the computer system of Figure 6 is for a system including a branch point register and a state indicator for holding the state of the system. As mentioned earlier, these may be omitted if a method such as method C is utilised in which the effect branch signal is a conditional signal located at the branch point. The set branch instruction sets the target location into the target pointer register 118 as described above. When the effect branch instruction is executed, the condition defined in the instruction is evaluated. If that condition is true, the effect branch signal 146 is supplied to cause fetcher B to become the active fetcher commencing fetching from the target location so that the branch is taken. The target location remains valid in the target pointer register 118 and, instead of fetcher A being controlled to stop fetching as described above, it is caused to commence fetching new instructions from the target location. This has the advantage that if a further branch should be required having a target location defined by the set instruction, the new instructions have already been fetched.
Figure 11 is a block diagram illustrating this principal. In Figure 11, reference numerals 39 and 43 denote the address bus and data bus as in preceding figures. The fetch circuitry 10 in Figure 4 is implemented by an execute instruction fetcher 402 and a target instruction fetcher 404. These are denoted fetcher E and fetcher T respectively. Like elements in each fetcher have the same reference numeral, suffixed E or T appropriately. Each fetcher comprises a fetch pointer 406 for holding an indication of the next address from which instructions are to be fetched and a start pointer 408 for holding the target location representing the first instruction in a new string of instructions. Each fetcher also has a buffer 410 for holding a queue of instructions.
Reference numeral 118 denotes as before the target pointer register which holds an indication of the target location responsive to execution of the set branch instruction. Reference numeral 412 denotes a select circuit for selecting the one of the fetchers acting as the execute Fetcher E to supply its instructions to the decode circuit 16 of Figure 4.
A sequencer 414 receives the effect branch signal 146 and has state which changes on receipt of that signal to cause the role of the fetchers to alter as described above, by controlling the select circuit 412 along line 411.
Figure 12 is a block diagram illustrating a system for implementing such an arrangement. In Figure 12, like numerals denote like parts as in Figure 11 for the execute instruction fetcher and the target instruction fetcher and the other features common between Figures 11 and 12.
The system of Figure 12 additionally includes a mispredict fetcher 403, fetcher M. This likewise has a fetch pointer register 406M for holding the address from which next instructions are to be fetched, a buffer 410M for holding a queue of instructions and a start pointer register 408M for holding the start address from which instructions are to be fetched. The select circuit 412 is arranged to select the one of the three fetchers acting as the execute fetcher E to supply instructions to the decode circuitry 16.
Figure 7 illustrates an instruction fetcher which can be used to implement kernel and descriptor branches. Like numerals in Figure 7 denote like parts in Figure 5. The fetcher of Figure 7 has the following additional circuitry. A kernel latch 200 holds the address to use for kernel calling and can only be programmed by trusted code. It receives at its latch input a store kernel signal 202 to latch the kernel address on line 204. A kernel multiplexor 206 receives the kernel address at one input thereof and the normal start address on line 40 at the other input thereof. The kernel multiplexor 206 is controlled by a branch kernel signal on line 208. The branch kernel signal is asserted at the same time as the start signal 40 would normally be asserted to initialise a branch. When the signal is asserted, the address held in the kernel latch 200 is stored into the fetch latch 65 via multiplexor 206 and a further multiplexor 208, rather than the address supplied by the start signal.
The fetcher of Figure 7 is thus able to carry out kernel branches and descriptor branches.
Another type of branch instruction is procedure calling. This requires that a suitable instruction pointer value is saved so that the procedure can return back to the piece of program from whence it came. Thus, the procedure can be called from different parts of the program. Figure 8 illustrates the flow graph for a procedure call. Figure 8 illustrates a program containing Part 1, Part 2 and Procedure. Part 1 has sequential blocks of instructions Block A, Block B between which is located a call instruction. Similarly, Part 2 has sequential blocks of instructions Block C, Block D between which is a call instruction. The procedure includes a sequence of procedure instructions PROC and a return instruction. The two pieces of code, Part 1 and Part 2 both call the Procedure and both return to their respective control flows. The call instruction can be implemented as a particular type of set or do branch instruction which not only identifies a target location (SET) or branch point (D0) but causes the return address of the first instruction of the next sequential block to be saved in a return register. Then, the return instruction can be implemented as a particular type of set instruction which effects a branch to the return address which was held in the register.
Figure 9 indicates the state register required to implement procedure calls. This includes registers 230 with a select register unit 232 controlled by a register select signal 234. On execution of a set or do branch (or call) instruction, the address of the next instruction after the call instruction to which the program is to return is stored in the registers 230 on branch line 236 responsive to the store signal 238. When the special set (or return) instruction is implemented, the branch is effected to the target location which is stored in the specified register 230.
In the above described embodiment, there are two instruction fetchers which can both function as the active fetcher depending on the state of the switch multiplexor. Figure 10 illustrate in block diagram form an alternative embodiment where the instruction fetch circuit comprises two instruction fetchers, one of which is always the active fetcher. This embodiment will now more clearly be described with reference to Figure 10. Like numerals in Figure 10 denote like parts to Figure 6, but primed. Thus, Figure 10 illustrates a pipelined processor 17' including execution circuitry with a set branch instruction execution circuit 136' and a do branch instruction execution circuit 142'. There is an instruction pointer register 108' and a target pointer register 118'. The fetch circuit includes an active fetcher and a target fetcher. The active fetcher includes a fetch pointer 65' and an instruction buffer 66'. The target fetcher similarly includes a fetch pointer 65'' and a target instruction buffer 66''.
On execution of a set branch instruction, the target pointer register 118' is initialised to instruct the fetch pointer 65'' of the target fetcher to commence fetching instructions from the target location. Meanwhile, the active fetcher is fetching instructions sequentially from memory and supplying them to the processor 17'. On execution of the effect branch instruction, a copy unit 300 acts to copy the contents of the target instruction buffer 66'' of the target fetcher to the instruction buffer 66' of the active fetcher so that the next instructions to be supplied to the processor 17' are those commencing from the target location.
Further details of implementation of the circuit of Figure 10 are not given herein because it will be apparent from the information given in relation to the circuit of Figures 5, 6 and 7 how the circuit of Figure 10 could be implemented.
A computer system for fetching, decoding and executing instructions comprising:
A computer system according to claim 1 wherein said instruction fetch circuitry comprises two instruction buffers, a first buffer for holding subsequent instructions connected to said execution circuitry, and a second buffer for holding new instructions wherein the contents of said second buffer are copied into said first buffer responsive to generation of said effect branch (DO) signal.
A computer system according to claim 1 wherein said instruction fetch circuitry includes two instruction fetchers for fetching respectively said subsequent instructions and said new instructions and wherein said select circuitry is operable to connect a selected one of said instruction fetchers to said execution circuitry.
A computer system according to claim 3 wherein said instruction fetch circuitry comprises a third instruction fetcher for fetching instructions to implement predicted conditional instructions.
A computer system according to claim 1, 2, 3 or 4 which includes a first register for holding an indication of the address from which a next instruction is to be fetched.
A computer system according to any preceding claim wherein the target store holds the address from which the first instruction of a string of new instructions is to be fetched.
A computer system according to any of claims 1 to 5 wherein the set branch instruction identifies a special register which holds the address from which the first instruction of a string of new instructions is to be fetched.
A computer system according to any of claims 1 to 5 wherein the target store holds the address of a memory location which holds the address of the first instruction of a string of new instructions is to be fetched.
A computer system according to any preceding claim which comprises decode circuitry for decoding said fetched instructions, said instruction fetch circuitry, decode circuitry and execution circuitry being arranged in a pipeline.
A computer system according to any of claims 1 to 9 wherein said at least one instruction string includes a further instruction which determines the branch point after which new instructions are to be executed, identification of said branch point causing generation of said effect branch signal to said select circuitry.
A computer system according to claim 10 wherein said further instruction is located at the branch point after which said new instructions are to be executed.
A computer system according to claim 10 wherein said further instruction is located in the string prior to the branch point after which further instructions to be executed are said new instructions, said further instruction indicating the branch point and wherein the computer system comprises a branch point register for holding said branch point.
A computer system according to claim 10, 11 or 12 wherein said further instruction is a different instruction from said set branch instruction.
A computer system according to claim 13 wherein said further instruction defines a condition and determines that further instructions to be executed are new instructions only if that condition is satisfied.
A computer system according to claim 5 wherein said set branch instruction identifies the branch point after which further instructions to be executed are new instructions, said computer system comprising a branch point register for storing said branch point and compare circuitry for generating said effect branch signal to the select circuitry when said branch point matches the address indicated by the first register.
A computer system according to any of claims 10 to 15 which comprises a return register for holding a return address being the address of the next instruction after said branch point, wherein said further instruction is effective to generate said effect branch signal and to save said return address in said return register and wherein said branch instruction identifies said return register to indicate the target location.
A method of operating a computer to fetch decode and execute instructions which computer has storage circuitry holding a plurality of instructions at respective storage locations, said plurality of instructions being arranged in instruction strings, each string comprising a first instruction and a set of subsequent instructions the method comprising:
A method according to claim 17 wherein said subsequent instructions are held in a first buffer and said new instructions are held in a second buffer and wherein said effect branch signal causes the contents of said second buffer to be copied into said first buffer.
A method according to claim 17 wherein a first instruction fetcher fetches said subsequent instructions and a second instruction fetcher fetches said new instructions, said effect branch signal selecting which of said first and second instruction fetchers supplies instructions for execution.
A method according to claim 17, 18 or 19 wherein the effect branch signal is generated responsive to execution of a further instruction which determines the branch point after which new instructions are to be executed.
A method according to claim 20 wherein said further instruction defines a condition and determines that further instructions to be executed are new instructions only if that condition is satisfied.
A method according to any of claims 17 to 21 wherein said branch instruction identifies the branch point after which further instructions to be executed are new instructions and wherein said effect branch signal is generated when said branch point matches the address from which a next instruction is to be fetched.
A method according to any of claims 17 to 22 wherein the set branch instruction identifies as the target location the address from which the first instruction of a string of new instructions is to be fetched.
A method according to any of claims 17 to 22 wherein the set branch instruction identifies a special register which holds the target location.
A method according to any of claims 17 to 22 wherein the set branch instruction identifies the address of a memory location holding the target location.
A method according to claim 20 or 21 wherein execution of said further instruction causes a return address to be saved in a return register and wherein said branch instruction identifies the return register to indicate the target location.
execution circuitry for executing fetched instructions, wherein at least one of said instruction strings includes a set branch instruction (SET) which provides an indication of a target location from which a subsequent instruction may be fetched, the subsequent instruction being from a different instruction string, and an effect branch instruction different from said set branch instruction and located at the branch point after which said new instructions are to be executed, and wherein said instruction fetch circuitry is operated responsive to execution of a said set branch instruction (SET) to fetch in parallel subsequent instructions from said string containing said set branch instruction and new instructions from said different instruction string commencing from said target location while said subsequent instructions continue to be executed; and
select circuitry responsive to execution of an effect branch (DO) instruction to cause said execution circuitry to execute said new instructions if a condition determined by the effect branch instruction is satisfied.
A computer system according to claim 27 wherein said instruction fetch circuitry comprises two instruction buffers, a first buffer for holding subsequent instructions connected to said execution circuitry, and a second buffer for holding new instructions wherein the contents of said second buffer are copied into said first buffer responsive to generation of said effect branch (DO) signal.
A computer system according to claim 27 wherein said instruction fetch circuitry includes two instruction fetchers for fetching respectively said subsequent instructions and said new instructions and wherein said select circuitry is operable to connect a selected one of said instruction fetchers to said execution circuitry.
A computer system according to claim 27, 28 or 29 which includes a first register for holding an indication of the address from which a next instruction is to be fetched.
A computer system according to claim 27, 28, 29 or 30 which comprises a target register for holding an indication of the target location identified by the set branch instruction.
A computer system according to claim 31 wherein the target register holds the address from which the first instruction of a string of new instructions is to be fetched.
A computer system according to claim 31 wherein the set branch instruction identifies a special register which holds the address from which the first instruction of a string of new instructions is to be fetched.
A computer system according to claim 31 wherein the target register holds the address of a memory location which holds the address of the first instruction of a string of new instructions is to be fetched.
A computer system according to any of claims 27 to 34 which comprises decode circuitry for decoding said fetched instructions, said instruction fetch circuitry, decode circuitry and execution circuitry being arranged in a pipeline.
A computer system according to any of claims 27 to 30 which comprises a return register for holding a return address being the address of the next instruction after said branch point, wherein said further instruction is effective to generate said effect branch signal and to save said return address in said return register and wherein said branch instruction identifies said return register to indicate the target location.
EP19950304199 1994-06-22 1995-06-16 A computer system for executing branch instructions Expired - Lifetime EP0689131B1 (en)
GB9412487 1994-06-22
GB9412487A GB9412487D0 (en) 1994-06-22 1994-06-22 A computer system for executing branch instructions
EP00102080A EP1003095B1 (en) 1994-06-22 1995-06-16 A computer system for executing branch instructions
EP00102080A Division EP1003095B1 (en) 1994-06-22 1995-06-16 A computer system for executing branch instructions
EP0689131A1 true EP0689131A1 (en) 1995-12-27
EP0689131B1 EP0689131B1 (en) 2001-08-29
ID=10757116
EP00102080A Expired - Lifetime EP1003095B1 (en) 1994-06-22 1995-06-16 A computer system for executing branch instructions
EP19950304199 Expired - Lifetime EP0689131B1 (en) 1994-06-22 1995-06-16 A computer system for executing branch instructions
US (2) US5961637A (en)
EP (2) EP1003095B1 (en)
JP (1) JP2746549B2 (en)
DE (3) DE69534148T2 (en)
GB (1) GB9412487D0 (en)
GB2321323A (en) * 1996-11-06 1998-07-22 Hyundai Electronics Ind Computer programme branch prediction
EP1235140A1 (en) * 2001-02-27 2002-08-28 STMicroelectronics S.A. Method of branch instruction management within a processor
US7007272B2 (en) 2000-10-12 2006-02-28 Stmicroelectronics Limited Compiling computer programs including branch instructions
US7155707B2 (en) 2000-10-12 2006-12-26 Stmicroelectronics Limited Compiling computer programs including branch instructions
WO2015113879A1 (en) * 2014-01-29 2015-08-06 Telefonaktiebolaget L M Ericsson (Publ) Efficient use of branch delay slots and branch prediction in pipelined computer architectures
WO2017220974A1 (en) * 2016-06-22 2017-12-28 Arm Limited Register restoring branch instruction
JP3804941B2 (en) * 2002-06-28 2006-08-02 富士通株式会社 Instruction fetch control device
DE10254653B4 (en) * 2002-11-22 2009-05-28 Infineon Technologies Ag Device for controlling the processing of data words of a data stream
JP3760999B2 (en) * 2004-06-15 2006-03-29 セイコーエプソン株式会社 Information processing apparatus, microcomputer and electronic device
US20130305017A1 (en) * 2012-05-08 2013-11-14 Alexander Rabinovitch Compiled control code parallelization by hardware treatment of data dependency
JP6374454B2 (en) * 2016-08-08 2018-08-15 株式会社Ｄｎｐハイパーテック Module encryption / decryption program
US3426330A (en) * 1966-02-14 1969-02-04 Burroughs Corp Central data processor
1994-06-22 GB GB9412487A patent/GB9412487D0/en active Pending
1995-06-16 DE DE1995634148 patent/DE69534148T2/en not_active Expired - Lifetime
1995-06-16 EP EP00102080A patent/EP1003095B1/en not_active Expired - Lifetime
1995-06-16 DE DE1995622385 patent/DE69522385D1/en not_active Expired - Lifetime
1995-06-16 EP EP19950304199 patent/EP0689131B1/en not_active Expired - Lifetime
1995-06-16 DE DE1995634148 patent/DE69534148D1/en not_active Expired - Fee Related
1995-06-21 US US08/493,103 patent/US5961637A/en not_active Expired - Lifetime
1995-06-22 JP JP7179312A patent/JP2746549B2/en not_active Expired - Fee Related
2001-04-25 US US09/842,312 patent/US7047399B2/en not_active Expired - Fee Related
"Acceleration of multimedia applications using a branch conditional to previous target instruction", IBM TECHNICAL DISCLOSURE BULLETIN, ARMONK,US, vol. 37, no. 4b, pages 285 - 288, XP013100228 *
BEEBE ET AL.: "Instruction sequencing control", IBM TECHNICAL DISCLOSURE BULLETIN., vol. 14, no. 12, NEW YORK US, pages 3599 - 3611 *
CORTADELLA AND LLABERIA: "Making branches transparent to the execution unit", INTERNATIONAL JOURNAL OF MINI AND MICROCOMPUTERS, vol. 11, no. 1, CALGARY, CALIFORNIA US, pages 13 - 17, XP000210082 *
LEE,MAHON AND MORRIS: "Pathlength reduction features in the PA-Risc architecture", COMPCON SPRING 92, 24 February 1992 (1992-02-24) - 28 February 1992 (1992-02-28), SAN FRANCISCO,US, pages 129 - 135, XP000340724, DOI: doi:10.1109/CMPCON.1992.186698 *
PLESZKUN AND FARRENS: "An instruction cache design for use with a delayed branch", PROCEEDINGS 4TH MIT CONFERENCE : ADVANCED RESEARCH IN VLSI, 7 April 1986 (1986-04-07), CAMBRIDGE, MA,US, pages 73 - 88, XP002155740 *
GB2321323B (en) * 1996-11-06 2002-01-09 Hyundai Electronics Ind Branch prediction apparatus and method thereof
EP1089170A3 (en) * 1999-10-01 2004-02-04 Hitachi, Ltd. Processor architecture and method of processing branch control instructions
FR2821450A1 (en) * 2001-02-27 2002-08-30 St Microelectronics Sa Method for management of branch instructions within a processor, especially a digital signal processor, and corresponding processor
US7370182B2 (en) 2001-02-27 2008-05-06 Stmicroelectronics Sa Method of handling branching instructions within a processor, in particular a processor for digital signal processing, and corresponding processor
DE69534148T2 (en) 2006-02-16
US7047399B2 (en) 2006-05-16
JP2746549B2 (en) 1998-05-06
EP1003095A2 (en) 2000-05-24
GB9412487D0 (en) 1994-08-10
DE69522385D1 (en) 2001-10-04
EP1003095A3 (en) 2001-02-28
US20020078330A1 (en) 2002-06-20
US5961637A (en) 1999-10-05
EP0689131B1 (en) 2001-08-29
DE69534148D1 (en) 2005-05-19
EP1003095B1 (en) 2005-04-13
JPH0844562A (en) 1996-02-16
KR100212204B1 (en) 1999-08-02 Apparatus for processing instruction in computer system
Ref document number: 69522385