WO1999004335A2

WO1999004335A2 - A method and a processor adapted for the handling of conditional jumps

Info

Publication number: WO1999004335A2
Application number: PCT/SE1998/001334
Authority: WO
Inventors: Carl Tobias Roos; Lars-Erik LUNDSTRÖM
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 1997-07-21
Filing date: 1998-07-07
Publication date: 1999-01-28
Anticipated expiration: 2000-01-21
Also published as: EP0998701A2; AU8365298A; BR9810768A; JP2001510916A; CN1271434A; SE510295C2; WO1999004335A3; SE9702762L; KR20010022065A; SE9702762D0

Abstract

The present invention relates to a method of handling conditional jump instructions in a computer processor (1). Space is allocated in a so-called instruction buffer (3) for respective instructions read into the processor. These spaces are given an order which corresponds to the order in which the instructions were read-in sequentially. The last position in the instruction buffer constitutes a read-out position (4). The processor (1) is adapted to predict the fulfilment of a conditional jump instruction when such a jump instruction is read-in, whereafter instructions can be read into and processed by the processor in accordance with this prediction. A wrong prediction will result in following instructions read into the processor and partially processed thereby being removed from the processor (1) so as to provide space for the read-in of correct instructions, in accordance with fulfilment of the condition.

Description

TITLE OF THE INVENTION :

A METHOD FOR HANDLING CONDITIONAL JUMP INSTRUCTIONS IN A DATA PROCESSOR

FIELD OF INVENTION

The present invention relates to the handling of specific instructions, so-called conditional jumps, in a data processor.

A conditional jump instruction is comprised of one instruction from several instructions read sequentially into a processor, where fulfilment of the condition determines whether or not the instructions that immediately follow the conditioned jump instruction shall be read into the processor or whether a jump in the instruction sequence shall be made. Such a jump will mean that subsequent instructions shall be read-in from some other place in the sequence, in accordance with the conditional jump instruction.

Respective instructions read into the processor are allocated space in a so-called instruction buffer, these spaces being given an order which corresponds to the sequential order of the instructions. At least a last position in the instruction buffer is a read-out position.

The instructions read into the processor can be processed by the processor and the processing result stored in respective spaces belonging to respective instructions in the instruction buffer, from where it can be finally read from the read-out position in the sequential order.

When a conditional jump instruction is read into the proces- sor, the processor is able to predict the fulfilment of the condition, whereafter instructions can be read into and processed by the processor in accordance with this prediction, immediately after the conditional jump instruction has been read in. A wrong prediction will result in the removal from the processor of subsequently read-in and partially processed instructions, so as to prepare a place for the read-in of correct instructions in accordance with fulfilment of the condition.

BACKGROUND OF THE INVENTION

So that the present standpoint of techniques and the present invention will be more readily understood, some of the terms and expressions used in the following description will now be defined.

When reading-in an instruction, processing of the instruction and the read-out of the processed result takes place in different steps. When reading the instruction into a processor, possible processing of the instruction is prepared. An instruction will normally include two operands and an operation that shall be applied to these operands.

The preparation of the instruction includes, among other things, a so-called "Fetch-step". This step includes fetching the operand values, since the actual instruction will often, but not always, merely contain an address to a position in a memory where the value of the operand is found.

The time taken to carry out a Fetch-step may vary with different instructions, depending on from where the different operand values shall be taken. This means that a first instruction that has been read-in before a second instruction will be processed after the said second instruction, due to the operand values of the second instruction being accessed more quickly than the operand values of the first instruction. Thus, the result obtained with the second instruction may be stored in the instruction buffer before the result obtained with the first instruction.

An instruction is processed in a part of the processor designated an arithmetical logical unit, ALU.

Since the ALU need not process the instructions in a sequential order, the ALU waiting times can be reduced, when the instruction Fetch-step takes a long time to complete.

When the fulfilment of a conditional jump instruction is wrongly predicted, the wrongly read instructions are removed from the processor. This is referred to here as "flushing" of the processor.

The general method of predicting the fulfilment of a condition as described above is found described in Patent Publication EP-A2 0 706 121, for instance.

Many different ways of reducing the deleterious effect of a wrong prediction of the fulfilment of a conditional jump instruction are known to the art.

Prior publication US-A 5,381,532 describes a processor that uses an alternative input buffer, a branch buffer (B). When reading-in a conditional jump instruction, the instructions are read in accordance with the prediction for fulfilment of the condition sequentially after the conditional jump instruction, and those instructions that shall be fetched if the prediction is wrong are read and stored in the branch buffer.

Should it be necessary to flush the processor, the correct instructions will have already been read into the branch buffer and are thus immediately available to the processor. This reduces the time loss caused by a wrong prediction and subsequent flushing of the processor.

Publications US-A 5,127,091, US-A 5,539,911, US-A 5,237,664 and US-A 4,742,451 illustrate and describe other solutions that are based on the use of a parallel buffer for the read-in of branch instructions.

It is also known to refine the algorithm that calculates the probability of the fulfilment of a condition for a conditional jump instruction, and thereby reduce the number of wrong predictions. The publication "A Tour of the Pentium (R) Pro Processor Microarchitecture" : Intel Corporation, describes a processor where only one processor input port is used and as- sumes that the predicted fulfilment of a condition is correct.

This provides very rapid and effective handling of correct predictions, but results in total flushing of the content of the processor in the event of a wrong prediction, without the correct instructions lying in readiness in an alternative buffer.

It should also be mentioned that a more accurate prediction requires a higher capacity with respect to the statistical evaluation of the fulfilment of the conditions than that required by a less accurate prediction.

It is also known to precede a conditional jump instruction with a condition-testing instruction. This instruction will ideally be positioned so far in front of the actual jump instruction as to enable the test instruction to be executed and its result received before the actual jump instruction enters the input port of the processor.

Thus, when the conditional jump instruction is read into the processor, the result regarding fulfilment of the condition will already be known because of the earlier execution of the condition-testing instruction, and correct instructions can be read-in immediately after the conditional jump instruction.

No instructions whose results can affect the condition for the conditional jump instruction may lie between the condition- testing instruction and the conditional jump instruction. Whether or not the condition-testing instruction may be placed at a sufficient distance in front of the conditional jump instruction will thus depend on whether instructions that can affect fulfilment of the condition lie close to or immediately precede the actual jump instruction.

This restriction, or limitation, results in difficulties with respect to software development, and may sometimes result in time delays caused by the insertion of empty instructions between a condition-testing instruction and an associated conditional jump instruction.

Publications GB-A 2 293 672 and EP-A2 0 509 245 both describe a computer or computer-architecture that is based fundamentally on the computer including a separate processor for processing conditional jump instructions separately from and in parallel with other instructions.

It should also be mentioned that the instructions handled in a processor can be divided up into two types of instructions, to-wit processor-external instructions and processor-internal instructions .

For instance, instructions in assembler code can be designated processor-external instructions, whereas those instructions that are obtained after the conversion of assembler code into micro-code can be designated processor-internal instructions.

In such contexts, it is also known that a processor-external instruction will normally form a series of processor-internal instructions upon conversion. It is also known that even when a processor-external instruction does not include a conditional jump instruction, such an instruction may, nevertheless, result in a processor-internal conditional jump instruction upon conversion from a processor- external code to a processor-internal code.

It is also known to use a so called sequence number generator which is adapted to generate a sequence number for each instruction read into the instruction buffer.

SUMMARY OF THE INVENTION

TECHNICAL PROBLEMS

When considering the earlier standpoint of techniques as described above and when taking a starting point from a processor that utilises predictions of the fulfilment of the condition for a conditional jump instruction for reading subsequent instructions into the processor, where respective instructions read into the processor are allocated spaces in a so-called instruction buffer, where said spaces are given an order that corresponds to the sequential order, and where at least the last position in the instruction buffer constitutes a read-out position from which the results obtained by processing respec- tive instructions can be read-out in the sequential order, and where a wrong prediction will result in the removal of subsequently read-in and partially processed instructions from the processor in order to provide place for correct instructions according to the fulfilment of the condition to be read-in, it will be seen that a technical problem is one of realising how the time losses caused by eventual flushing of the processor can be reduced in relation to known techniques.

Another technical problem is one of realising how a Fetch-step can be performed more quickly than with known techniques and the use of the processor improved, in the event of flushing the processor. Another technical problem is one of realising how this can be achieved without using condition-testing instructions that precede the conditional jump instruction, or a separate processor for processing conditional jump instructions.

Another technical problem is one of knowing how the truth or correctness of a prediction can be evaluated before the result obtained when processing the conditional jump instruction has reached the read-out position.

Another technical problem is one of realising how flushing of the processor can be effected in a correct manner in the event of a wrong prediction, when the result from processing the conditional jump instruction has still not reached the read- out position.

It will also be seen that a technical problem resides in realising how correct instructions shall be fetched in the event of a wrong prediction, and how this shall be adapted to dif- ferent processor architectures.

Yet another technical problem is one of realising how processor hardware shall be adapted to enable the truth of a prediction concerning the fulfilment of a condition to be evaluated before the result obtained when processing the conditional jump instruction has reached the read-out position and thereafter carry out correct flushing of the processor in the event of a wrong prediction.

Another technical problem is one of realising how a method or processor according to the present invention can be adapted so as to also make a processor more effective when handling processor-internal conditional jump instructions.

SOLUTION

With the intention of solving one or more of the aforesaid technical problems, the present invention takes as its starting point a method of handling specific instructions, so- called conditional jump instructions, in a data processor, wherein respective read-in instructions are allocated spaces in a so-called instructions buffer, and wherein said spaces are allocated an order or sequence that corresponds to the sequential order in which respective instructions are read into the processor.

At least the last position in the instructions buffer consti- tutes a read-out position from the buffer. The instructions are processed in the processor and the result is storable in respective spaces belonging to the instruction in the instructions buffer, and can be read-out from the read-out position in said sequential order.

The processor is adapted to predict the fulfilment of a conditional jump instruction read into the processor, whereafter instructions can be read into and processed by the processor in accordance with this prediction directly after reading-in the conditional jump instruction.

A wrong prediction results in removal from the processor of subsequent instructions read into and partially processed by said processor, so as to prepare room for reading into the processor correct instructions in accordance with fulfilment of the condition.

With a starting point from such a method, it is proposed in accordance with the present invention that the result obtained when processing the conditional jump instruction, and therewith knowledge of the fulfilment of an associated condition, is made available for evaluation before the space in the instruction buffer belonging to the conditional jump instruction has reached the read-out position.

It is also proposed in accordance with the invention that the removal of instructions from the processor solely concerns instructions that are read-in sequentially after the conditional jump instruction, regardless of the position of these instructions in the instruction processing sequence, when the prediction concerning the fulfilment of the condition is wrong.

With the intention of enabling the time gain obtained by early disclosure of whether a prediction as to whether a conditional jump instruction is correct or not to be improved, it is proposed in accordance with the invention that collection of the correct instructions is commenced immediately when it is known that the prediction concerning fulfilment of the condition is wrong.

The present invention also relates to a method based on the processing of a processor-internal instruction as described above with respect to conditional jump instructions, in other words that the result obtained when checking the fulfilment of a prediction concerning a processor-internal conditional jump instruction is made available and is taken into account immediately it is clear, even though the space in the instruction buffer belonging to the processor-internal conditional jump instruction has still not reached a read-out position in the instruction buffer.

The present invention also takes as its starting point a processor that includes:

- a read-in unit which is intended to read instructions into the processor from a memory containing mutually sequential instructions of which some are so-called conditional jump instructions, wherein fulfilment of the condition decides whether or not those instructions that follow sequentially immediately after the conditional jump instruction shall be read into the processor or whether a jump in the instruction sequence shall be made, this jump meaning that following instructions shall be read-in from some other place in the sequence in accordance with the conditional jump instruction; - an instruction buffer in which space can be allocated for respective instruction read into the processor, these spaces being allocated an order or sequence corresponded by the sequential order, wherein at least the last position in the instruction buffer constitutes a read-out position from said buffer;

- a processing unit which is constructed to process instructions read into the processor, wherein the result obtained can be stored in the instruction buffer in the space belonging to a respective instruction;

- a check unit which is constructed to check whether or not the read-out position includes a processing result;

- a read-out unit which is constructed to read the result from the read-out position;

- a prediction unit which is constructed to predict the fulfil- ment of a conditional jump instruction when the instruction is read into the processor, wherein the read-in unit is constructed to read instructions into the processor in accordance with said prediction immediately after reading-in the conditional jump instruc ion;

an evaluating unit which is constructed to evaluate whether or not the condition for the conditional jump instruction has been fulfilled in accordance with the prediction delivered by the prediction unit; and

- an instruction removal unit which is constructed to remove from the processor those instructions which have been read into and partially processed in the processor after the conditional jump instruction if the prediction concerning the conditional jump instruction is found to be wrong.

With a starting point from such a processor, it is particularly proposed in accordance with the invention that the proces- sor will include a result indicating unit that is adapted to indicate when the result obtained by processing a conditional jump instruction is stored in the position for the conditional jump instruction in the instructions buffer.

It is also proposed that the evaluating unit is adapted to fetch the result obtained when processing the conditional jump instruction, when this result is available in accordance with the result indicating unit, therewith enabling it to be ascer- tained whether or not the condition concerning the conditional jump instruction has been fulfilled or not in accordance with the prediction delivered by the prediction unit.

It is also proposed in accordance with the invention that the instruction removal unit will be adapted to remove from the processor solely those instructions that have been read sequentially into the processor after the conditional jump instruction, irrespective of where these instructions are found in the instruction processing operation, in response to a signal from the evaluating unit that shows the prediction of the fulfilment of the condition to be wrong.

An inventive processor is also adapted to commence reading correct instructions into the processor immediately after the evaluating unit has delivered its result with respect to the correctness of a prediction when said prediction has been found to be wrong.

With a starting point from a processor that includes a conver- sion unit which is adapted to convert processor-external instructions to processor-internal instructions, it is also proposed in accordance with the present invention that the aforesaid units are also adapted to process both a processor-internal conditional jump instruction and a processor-external conditional jump instruction and to evaluate the result of such processing, in accordance with the above. With a starting point from a processor that includes a sequence number generator which is adapted to generate a sequence number and to give each instructions read into the instruction buffer a sequence number, it is also proposed in accordance with the present invention that the instruction removal unit will be adapted to remove from the processor solely those instructions that have been given sequence numbers that are generated after the sequence number given to the conditional jump instruction, irrespective of where these instructions are found in the instruction processing operation, in response to a signal from the evaluating unit that shows the prediction of the fulfilment of the condition to be wrong.

ADVANTAGES

Those advantages primarily afforded by a method according to the invention and a processor adapted to operate in accordance with the method reside in the fact that the time loss that flushing in accordance with known techniques causes can be reduced. Furthermore, the Fetch-step can be made faster and the capacity of the arithmetical logical unit or units can be released for processing any waiting instructions that shall not be flushed. In the event of wrong predictions, correct instructions can be read into the processor in an earlier stage than that permitted by known techniques. These factors together enable the capacity of the processor to be utilised to a much greater extent than was earlier possible.

The principle is simple and is not bound to specific processor architectures, which enables it to be readily implemented in different processor architectures.

The main characteristic features of an inventive method are set forth in the characterising clause of Claim 1, while the main characteristic features of an inventive processor are set orth in the characterising clause of the following Claim 5.

BRIEF DESCRIPTION OF THE DRAWING

A method according to the present invention and a processor that operates in accordance with the method will now be de- scribed by way of example with reference to the accompanying drawing, in which

Figure 1 is a schematic and highly simplified illustration of a processor.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Instructions in a program code can be divided mainly into two types, flow changing instructions and non-flow changing in- structions.

A non-flow changing instruction, which is the most common occurring instruction, is an instruction referring to read, write and arithmetical operations. These operations normally include two operands, an instruction as to which operation shall be applied to the operands, and a destination address for the result of the operation.

Flow changing instructions change the flow of instructions and cause a jump in the program code. The most common type of flow changing instruction is the so-called conditional jump or conditional jump instructions.

These latter instructions also include two operands and an instruction as to which operation shall be applied thereto. This operation is, as a rule, a comparison between the operands, where the jump condition consists in similarity or dissimilarity between the operands. In the case of conditional jump instructions, no destination address is necessary, since the result from the operation is used locally in the processor to decide whether a jump shall be made in the flow or not. However, there is nothing to prevent a destination address being used.

The instructions are read into a processor sequentially, and several instructions can be found in different processing stages in the processor at one and the same time. By way of example, Figure 1 shows a processor 1 in which eight instructions can be processed "simultaneously". The instructions are read from a program memory 2 and are allocated a space in a so-called instructions buffer 3 which functions as a First In First Out (FIFO) buffer that has eight positions 31, 32, ..., 38 in the illustrated case.

The results obtained with respective operations are read out from the instructions buffer 3 and written-out to an intended destinations address when the instruction concerned is present in a so-called read-out position 4 in the instruction buffer, which in the illustrated case is the last position in said buffer 3. However, processing or execution of the operation may have been carried out when the instruction was present in an earlier position in the instructions buffer.

The manner in which a processor operates will now be described in more detail, so that the present invention may be more readily understood.

In the illustrated example, a processor 1 has a double input port, i.e. two different input ports, that is to say a first input port 111 and a second input port 112, and associated first and second buffers 113 and 114 respectively, through which the instructions can be collected. A processor-internal selector 12 decides from which input port the instructions shall be fetched. When a conditional jump instruction 21 enters the processor, for instance through the first input port 111, and when this condition has very likely been fulfilled, if it can be predicted, the instructions 22 are read-in immediately in accordance with the jump through the second input port 112, where the associated buffer 114 is filled with subsequent instructions. The instructions 23 positioned after the conditional jump 21 continue to be read-in through the first input port 111 and stored in the first buffer 113.

The processor-internal selector 12 collects instructions from the second buffer 114 in accordance with the prediction. In the event of a wrong prediction, the correct instructions wait in the first buffer 113 and can be read into the processor after the instructions wrongly read into the processor have been flushed out.

It is conceivable for a processor to use only one single input port. In this case, in the event of a prediction of the out- come from a conditional jump instruction, the instructions are then read into the single input port in accordance with the prediction, meaning that when a prediction is wrong it will take longer to read-in the correct instructions than when using two input ports, since these correct instructions have not been read-in and are not waiting in an alternative input port.

The prediction of the fulfilment of a condition may be based on different algorithms, such as static or dynamic predic- tions, for instance.

A static prediction is a choice where it is always assumed that the condition is fulfilled or not fulfilled.

A prediction can also be based on dynamic processing to show how this condition has earlier been fulfilled. The statistical outcome of the fulfilment of different conditions is then saved in a list and the list is updated each time a conditi- onal jump instruction is executed and is a basis for predictions as to whether or not these conditions are fulfilled. This is a dynamic prediction.

In the case of the earlier mentioned method, if the condition according to the prediction is fulfilled, correct instructions placed immediately after the jump instruction are read into the instructions buffer in accordance with the jump, whereby these correct instructions can be executed and be prepared to deliver their results to their respective destination addresses immediately after the conditional jump instruction has reached the read-out position 4 in the instruction buffer 3 and there left the result from the operation that determined whether or not the jump condition has been fulfilled.

The present invention is not dependent on the use of one or more input ports, nor yet on the type of algorithm used to predict fulfilment of the condition.

Regardless of processor or type of algorithm used, the instructions being processed in the instructions buffer shall not be executed in the case of a wrong prediction. Consequently, these instructions shall be flushed away so as to enable correct instructions to be read into the instructions buffer for processing.

Processing of an instruction in a processor includes several different steps.

A first step is to convert the code that represents the input instruction to a processor-internal code. This conversion takes place in a conversion unit, in the illustrated case a so-called Assembler to micro code Translator Unit (ATU) 5, which converts instructions in assemblers to instructions in machine language, whereafter the converted code is placed in the instruction buffer 3. The ATU 5 also includes the processor-internal selector 12 and controls the selector.

The space in the instructions buffer includes diverse fields, of which a part is shown in position 31 in the buffer 3. These fields include a field of operand A (OPA) 31A, a field for operand B ( OPB ) 31B, a field for the operation (ALSO) 31C and a field with the destination address for the result (DEST) 31D.

A second step is a so-called Fetch step, in which necessary operands are fetched from different memories Ml, M2 when these operands are not available in the instruction itself. This can take different lengths of time to perform, depending on the memory from which an operand shall be fetched. Some memories may be processor-internal memories Ml and others may be memories that are positioned outside the processor M2, i.e. processor-external memories.

Subsequent to having fetched the operands, the next steps can be taken. These steps include execution of the instruction, wherewith the operands 31A, 31B and the instruction 31C are sent to an ALU 6 in which the instruction is executed and a result delivered to a result field 31E.

The next step is carried out when the position of the instruction in the instructions buffer has reached the read-out position 4, provided that the result from the ALU 6 is ready and has been delivered to the result field 31E. This step is a so- called Commit or Write Back, in which the result is written to the address given by the content of the destination address field 31D.

The steps need not necessarily be executed sequentially, but can be carried out as soon as the Fetch-step of the instruction has been completed. This means that certain instructions can be ready for Commit even though instructions that lie se- quentially earlier in the instructions buffer have still not completed their respective Fetch steps .

Flushing of the processor in the event of a wrong prediction takes time to achieve and also impairs processor capacity. When the processor used has two input ports, there is obtained a certain safeguard that enables the preparation of those instructions that shall be read into the processor after the processor has been flushed in the event of a wrong prediction.

Although this safeguard means that the correct instructions are in a state of readiness in the first buffer 113, the operation necessitated by flushing the entire process contents, i.e. the entire contents of the instruction buffer 3 where many instructions may already have been executed and prepared for Commit, is both a large and expensive operation in these contexts .

When the processor used has only a single input port, the time losses caused by flushing the processor in the event of a wrong prediction is still greater.

The invention is based on the concept of early jump reporting that enables the result 31E obtained when executing a conditi- onal jump instruction can be used before the conditional jump instruction has reached the read-out position 4 in the instruction buffer 3. The earlier this result is known, the less harmful effect of a flushing process, therewith enabling correct instructions to be fetched in the event of a wrong prediction regarding the fulfilment of the condition.

The result obtained with the execution of a conditional jump instruction will be available in the processor as soon as execution of said jump instruction is completed. In earlier known techniques, the result of this execution is not used until the conditional jump instruction has reached the Commit position, i.e. the read-out position 4. The invention is thus based on the concept of using the result obtained when executing a conditional jump instruction immediately the result becomes available.

This is achieved by adapting the ATU 5 to monitor the processing of a conditional jump instruction in the processor and to use the result obtained to establish the truth of the prediction regarding fulfilment of the condition, as soon as said instruction has been processed or executed.

When the prediction is a correct prediction, processing is allowed to continue. In the event of a wrong prediction, all instructions that lie after the conditional jump instruction in the read-in sequence are flushed from the processor. This means that not all instructions in the processor will be flushed therefrom, since it is possible, and even probable, that there still remains in the processor instructions that were sequentially before the conditional jump instruction and therewith not affected by the jump but with which the fetch process for instance has still not been completed.

Thus, flushing will concern solely certain instructions and not all of the instructions present in the processor. These instructions may have been processed to different extents in the processor. Regardless of where the instructions are found in this processing operation, all following instructions are flushed out and the capacity released for the execution of instructions that have still not reached the execution stage and that shall not be flushed from the processor.

A processor adapted to operate in accordance with the afore- described method will now be described in more detail.

In simple terms, a known processor will include:

- a read-in unit, here designated input port 111 with associated buffer 113, intended to read instructions into the pro- cessor from a memory 2, with said instructions being mutually sequential;

- an instruction buffer 3 in which a space 31, 32, ..., 38 can be allocated to respective instructions read into the processor, where at least the last position in the buffer 3 constitutes a buffer read-out position 4;

- a processing unit, here designated ALU 6, which is adapted to process instructions read into the processor, whereafter the processing result can be stored in the space 313 allocated respective instructions in the buffer 3;

- a check unit 13 which is adapted to check whether or not a processing result is found in the read-out position;

- a read-out unit 14 which is adapted to read the result from the read-out position 4;

- a prediction unit 15 which is adapted to predict fulfilment of a conditional jump instruction when said instruction is read into the processor;

- an evaluating unit 16 which is adapted to evaluate whether the condition for the conditional jump instruction is fulfilled in accordance with the prediction delivered by the prediction unit; and

- an instruction removal unit 17 which is adapted to remove from the processor those instructions that were read into the processor and partially processed therein after the prediction concerning the conditional jump instruction has been found to be wrong.

With a starting point from a processor of this kind, the present invention particularly proposes that the processor will also include a result indicating unit 18 that is adapted to indicate when the result obtained by processing a conditi- onal jump instruction is stored in the position for the conditional jump instruction in the instructions buffer.

It is also proposed that the evaluating unit 16 is adapted to fetch the result 31E obtained when processing the conditional jump instruction when this is available according to the result indicating unit 18, thereby enabling it to be ascertained whether or not the condition for the conditional jump instruction has been fulfilled or not in accordance with the prediction given by the prediction unit 15. The result can thus be fetched regardless of whether the conditional jump instruction is positioned in the read-out position 4 in the buffer 3 or not.

It is also proposed in accordance with the present invention that the instruction removal unit 17 is adapted to remove from the processor solely those instructions that were read-in sequentially after the conditional jump instruction, regardless of where these instructions are found in the instruction processing chain, upon receipt of a signal from the evaluating unit 16 indicating that the prediction of the fulfilment of the condition was wrong.

Reference has been made in the aforegoing to conditional jump instructions that are read-in from a program memory 2. When such an instruction is converted to a micro-code in the conversion unit 5, such a processor will probably convert such processor-external instructions to a plurality of processor- internal instructions in micro-code.

There are also examples of processor-external instructions that do not include a conditional jump but where their correspondence in processor-internal code includes a conditional jump instruction. For instance, a processor-external instruc- tion that lacks conditional jump instructions and translated to a micro-code may result in a processor-internal loop that includes a conditional jump instruction, where the condition means that the loop shall be broken in fulfilling a given condition.

Thus, the present invention also relates to a method of hand- ling processor-internal conditional jump instructions in a data processor where the conditional jump instructions need not necessarily derive from a processor-external conditional jump instruction.

Fulfilment of the condition decides whether or not those instructions that follow sequentially immediately after said conditional jump instruction shall be processed by the processor or whether a jump in the sequence of processor-internal instructions shall be made.

Such a jump means that subsequent processor-internal instructions shall be read into the processor from some other place in the sequence, or from subsequent converted processor-external instructions according to the conditional jump instruc- tion.

A wrong prediction of the fulfilment of the condition results in following processor-internal instructions that have been read into and partially processed in the processor being flus- hed away so as to prepare room for correct processor-internal instructions with which the condition has been fulfilled to be read into the processor.

In this case, not all instructions in the processor are re- moved, since the processor will still contain processor-external instructions that have not yet been converted to processor-internal instructions and which are not affected by the processor-internal conditional jump instruction.

When a processor-internal conditional jump instruction is found, the following processor-external instruction is not read into the ATU 5 for conversion. This means that when instructions are removed because of a wrong prediction with regard to the fulfilment of a condition, only processor- internal instructions are removed and the next processor- external instruction can be read into the ATU 5 for conversion.

It is proposed in accordance with the invention that the result obtained when processing a conditional jump instruction, and therewith knowledge concerning the fulfilment of the condition, is made available for evaluation immediately proces- sing is completed, even though this takes place before the space in the instructions buffer belonging to the conditional jump instruction has reached the read-out position 4.

It is also proposed in accordance with the present invention that in the event of a wrong prediction concerning the fulfilment of the condition, removal of the instructions from the processor will only affect those processor-internal instructions that were read-in sequentially after the conditional jump instruction, regardless of where these instructions are found in the instruction processing operation.

A processor that is designed to also take into account processor-internal conditional jump instructions shall, similarly to the earlier described processor, include a result indicating unit 18 which is adapted to indicate when the result from processing a conditional jump instruction is stored in the instructions buffer.

The processor will also include an evaluating unit 16 which is adapted to fetch the result obtained when processing the processor-internal conditional jump instruction, when the result indicating unit 18 indicates that this result is available.

The evaluating unit 16 is then able to ascertain whether or not the condition for the processor-internal conditional jump instruction has been fulfilled in accordance with the prediction given by a prediction unit 15. It is also proposed in accordance with the invention that the processor includes an instruction removal unit 17 which is adapted to remove from the processor those processor-internal instructions that are read-in sequentially after the processor-internal conditional jump instruction, regardless of where these instructions are found in the instruction processing operation, upon receipt of a signal from the evaluating unit 16 to the effect that the prediction of the fulfilment of the condition was wrong.

It is known that a processor may include a sequence number generator 19 which is adapted to generate sequence numbers (SN) and to give each instructions read into the instruction buffer 3 a sequence number. The space in the instruction buffer includes a field 31F which is intended to store the sequence number of the instruction.

The SN is sent together with the OPA, OPB and ALSO to the ALU 6 for processing so that the result of the processing in the ALU can be related to the right position within the instruction buffer 3.

It is proposed in accordance with the present invention that the sequence number is used in the flushing process in order to determine what instructions that have been read into the instruction buffer before the conditional jump instruction and what instructions that have been read into the instruction buffer after the conditional jump instruction.

It is thus proposed that the instruction removal unit 17 is adapted to remove from the processor 1 solely those instructions that have been given sequence numbers that are generated after the sequence number given to the conditional jump instruction, irrespective of where these instructions are found in the instruction processing operation, in response to a signal from the evaluating unit 16 that shows the prediction of the fulfilment of the condition to be wrong. The use of a sequence number according to the aforedescribed can be implemented both in processors that are adapted to take into their account only processor external-instructions or both processor-internal and processor-external instructions.

It will be understood that the invention is not restricted to the aforedescribed exemplifying embodiment thereof and that modifications can be made within the concept of the invention as illustrated in the following Claims.

Claims

1. A method of handling specific instructions, so-called conditional jump instructions, in a data processor, where said conditional jump instruction constitutes one of several instructions read sequentially into said processor, where fulfilment of the condition decides whether those instructions that follow sequentially immediately after said conditional jump instruction shall be read into said processor or whether a jump shall be made in said sequence of instructions, meaning that following instructions shall be read in from some other place in said sequence in accordance with said conditional jump instruction, wherein respective instructions read into the processor are allocated space in a so-called instruction buffer, wherein said spaces in said buffer are given an order that corresponds to said sequential order, wherein at least the last position in said instruction buffer constitutes a read-out position from said buffer, whereafter said instructions can be processed by said processor, and whereafter the result obtained by processing said instructions can be stored in respective spaces belonging to said instructions in said instruction buffer, and read from said read-out position in said sequential order, wherein when a conditional jump instruction is read into the processor, the processor predicts the fulfilment of said condition, whereafter instructions can be read into and processed by said processor in accordance with said prediction immediately after reading-in said conditional jump instruction, and wherein a wrong prediction results in the removal of subsequent instructions read into and partially processed by the processor, so as to prepare place for correct instructions according to the fulfilment of the condition, c h a r a c t e r i s e d in that the result obtained by processing said conditional jump instruction, and therewith the knowledge of the fulfilment of said condition, is made available for evaluation immediately said processing is completed, even when this takes place before the space allocated to said conditional jump instruction in said instruction buffer has reached said read-out position.

2. A method according to Claim 1, c h a r a c t e r i s e d in that in the event of a wrong prediction of the fulfilment of said condition, only those instructions that have been read-in sequentially after said conditional jump instruction are removed from the processor, regardless of where these instructions are found in the instruction processing operation.

3. A method according to Claims 1 and 2, in which instructions are read into the processor through one single input port, c h a r a c t e r i s e d in that reading of correct instructions into the processor is commenced immediately it is known that a wrong prediction of the fulfilment of a condition belonging to a conditional jump instruction has been made available, and that these correct instructions are read into the processor through said single input port.

4. A method according to Claims 1 and 2, in which instructions are read into the processor through one of two input ports with associated buffers and belonging to a double input port, and in which instructions according to a prediction of the fulfilment of a conditional jump instruction are read into said processor through a first input port belonging to said double input port and instructions according to a second possible result with respect to the fulfilment of said conditional jump instruction are read into said processor through a second input port belonging to said double input port, wherein instructions read into the processor are stored in respective buffers, c h a r a c t e r i s e d in that reading of said correct instructions into the processor commences immediately it becomes known that the prediction of the fulfilment of a condition belonging to a conditional jump instruction was wrong; and in that said correct instructions are read from the buffer belonging to said second input port.

5. A processor which includes a read unit that is intended to read instructions into the processor from a memory in which instructions are stored in a mutually sequential order, of which instructions some are so-called conditional jump instructions, wherein fulfilment of the condition decides whether the instructions that follow sequentially immediately after said conditional jump instruction shall be read into the processor or whether a jump shall be made in said instruction sequence, said jump meaning that following instructions shall be read into the processor from some other place in said sequence in accordance with said conditional jump instruction, wherein the processor also includes an instruction buffer in which space can be allocated to respective instructions read into said processor, wherein the spaces are given an order that corresponds to said sequential order of instructions, wherein at least the last position in said instruction buffer constitutes a read-out position from said instruction buffer, and further includes a processing unit which is adapted to process said instructions, whereafter the result obtained by said processing can be stored in a respective space belonging to said instruction in said instruction buffer, a check unit which is adapted to check whether said read-out position includes a processing result, a read-out unit which is adapted to read said result from said read-out position, a prediction unit which is adapted to predict fulfilment of a conditional jump instruction read into the processor, wherein said read unit is adapted to read instructions into said processor in accordance with said prediction immediately after said conditional jump instruction is read into said processor, an evaluating unit which is adapted to ascertain whether or not the conditional jump instruction has been fulfilled in accordance with the prediction given by the prediction unit, and an instruction removal unit which is adapted to remove from the processor those instructions that were read into the processor and partially processed therein after said conditional jump instruction when said prediction is found to be wrong, c h a r a c t e r i s e d in that the processor includes a result indicating unit which is adapted to indicate when the result obtained by processing a conditional jump instruction is stored in the position for said conditional jump instruction in said instruction buffer; and in that said evaluating unit is adapted to fetch the result obtained when processing said conditional jump instruction when the result indicating unit indicates that this result is available, wherein said evaluating unit is able to ascertain whether or not the condition for said conditional jump instruction has been fulfilled in accordance with the prediction given by said prediction unit.

6. A processor according to Claim 5, c h a r a c t e r i s e d in that said instruction removal unit is adapted to remove from said processor those instructions that were read sequentially into the processor after said conditional jump instruction, regardless of where these instructions are placed in the instruction processing chain, when receiving from said evaluating unit a signal that indicates that said prediction of the fulfilment of said condition was wrong.

7. A processor according to Claims 5 and 6 , which includes one single input port through which instructions are read into said processor, c h a r a c t e r i s e d in that the processor is adapted to commence reading correct instructions into the processor immediately upon receiving from the evaluating unit a signal that indicates that the prediction of the fulfilment of said condition was wrong; and that these correct instructions are read into the processor through said one single input port.

8. A processor according to Claims 5 and 6, which includes a double input port, comprising a first and a second input port and associated buffers, wherein the processor is adapted to read-in instructions through one of said two input ports, wherein said processor is also adapted to read-in instructions according to a predicted fulfilment of a conditional jump in- struction through said first input port belonging to said double input port when reading-in such a conditional jump instruction, and instructions according to a second possible result concerning the fulfilment of said conditional jump instruction through said second input port of said double input port, and wherein respective buffers are adapted to store the read instructions, c h a r a c t e r i s e d in that said processor is adapted to commence reading-in said correct instructions immediately upon receiving from said evaluating unit a signal that shows said prediction of the fulfilment of said condition to be wrong; and in that this reading-in of said correct instructions takes place from the buffer belonging to said second input port.

9. A processor according to Claim 5 and 6, which includes a sequence number generator, c h a r a c t e r i s e d in that said instruction removal unit is adapted to remove from said processor solely those instructions that have been given sequence numbers that are generated after the sequence number given to said conditional jump instruction, irrespective of where these instructions are found in the instruction processing operation, in response to a signal from said evaluating unit that shows said prediction of the fulfilment of said condition to be wrong.

10. A method of handling specific instructions, so-called conditional jump instructions, in a data processor, wherein the processor includes a conversion unit which converts instructi- ons read into said processor on a processor-external code to a processor-internal code, wherein a processor-external instruction read into said processor may result in a sequence of different processor-internal instructions, of which some may consist of said conditional jump instructions, wherein fulfilment of the condition decides whether those instructions that follow sequentially immediately after said conditional jump instruction shall be processed by said processor or whether a jump shall be made in said sequence of processor-internal instructions, meaning that subsequent processor-internal in- structions shall be read-in from some other place in said sequence or from subsequent converted processor-external instructions according to said conditional jump instruction, wherein space is allocated to respective processor-internal instructions in a so-called instruction buffer, wherein said spaces in said instruction buffer are given an order that corresponds to said sequential order, wherein at least the last position in said instruction buffer constitutes a read- out position from said instruction buffer, whereafter said instructions can be processed by said processor and the processing result stored in a respective space belonging to said instruction in said instruction buffer and can, finally, be read from said read-out position in said sequential order, wherein said processor predicts fulfilment of the condition of a jump instruction when reading-in such a conditional jump instruction, whereafter instructions are processed by said processor in an order according to said prediction immediately after reading-in said conditional jump instruction, wherein a wrong prediction results in the removal from said processor of subsequently read-in and partially processed processor-internal instructions, so as to prepare room for reading-in correct processor-internal instructions according to the fulfilment of said condition, c h a r a c t e r i s e d in that the result obtained by processing said conditional jump instruction, and therewith the knowledge of the fulfilment of said condition, is made available for evaluation immediately said processing is completed, even when this takes place before the space allocated to said conditional jump instruc- tion in said instruction buffer has reached said read-out position.

11. A method according to Claim 10, c h a r a c t e r i s e d in that in the event of a wrong prediction of the fulfilment of said condition, the removal of instructions from the processor solely concerns processor-internal instructions that are read-in sequentially after said conditional jump instruction, regardless of where these instructions are found in the instruction processing operation.

12. A processor which includes a conversion unit that is adapted to convert instructions that are read into the processor on a processor-external code to a processor-internal code, wherein a processor-external instruction read into the processor may result in a sequence of different processor-internal instructions of which some may consist of conditional jump instructions, wherein fulfilment of the condition decides whether those instructions that sequentially follow immedi- . ately after said conditional jump instruction shall be processed by said processor or whether a jump shall be made in said sequence of processor-internal instructions, which means that subsequent processor-internal instructions shall be read-in from some other place in said sequence or from following converted processor-external instructions, according to said conditional jump instruction, wherein the processor also includes an instruction buffer in which space is allocated to respective instructions read into the processor, said spaces being given an order which corresponds to the aforesaid sequential order, wherein at least the last position in said instruction buffer constitutes a read-out position from said buffer, wherein said processor also includes a processing unit which is adapted to process instructions, whereafter the processing result can be stored in respective spaces belonging to said instructions in said instruction buffer, a check unit which is adapted to check whether said read-out position includes a processing result, a read-out unit which is adapted to read the result in said read-out position, a prediction unit which is adapted to predict the fulfilment of the condition of a processor-internal conditional jump instruction, wherein said processing unit is adapted to process instructions in accordance with said prediction immediately after reading-in said conditional jump instruction, an evaluating unit which is adapted to ascertain whether the condition for said conditional jump instruction is fulfilled in accordance with said prediction given by the prediction unit, and an instruction removal unit which is adapted to remove from the processor those processor-internal instructions that had been read into and partially processed by said processor and read into said instruction buffer after said conditional jump instruction when said prediction is found to be wrong, c h a r a c t e r i s e d in that said processor includes a result indicating unit which is adapted to indicate when the result obtained by processing a conditional jump instruction is stored in the position allocated to said conditional jump instruction in said instruction buffer; in that the evaluating unit is adapted to fetch the result obtained when processing said conditional jump instruction when the result indicating unit indicates that this result is available, thereby enabling it to be established whether the condition for said processor- internal conditional jump instruction has been fulfilled or not in accordance with the prediction given by said prediction unit.

13. A processor according to Claim 12, c h a r a c t e r i s e d in that said instruction removal unit is adapted to remove from said processor those processor-internal instructions that are read-in sequentially after said conditional jump instruction, regardless of where these instructions are found in the instruction processing operation, upon receiving from said evaluating unit a signal that indicates that said prediction of the fulfilment of said condition was wrong.

14. A processor according to Claim 12, which includes a sequence number generator, c h a r a c t e r i s e d in that said instruction removal unit is adapted to remove from said processor solely those processor-internal instructions that have been given sequence numbers that are generated after the sequence number given to said conditional jump instruction, irrespective of where these instructions are found in the instruction processing operation, in response to a signal from said evaluating unit that shows said prediction of the fulfilment of said condition to be wrong.