Method for identifying basic blocks with conditional delay slot instructions

PRIORITY INFORMATION

0001This application is a continuation of and claims priority to U.S. patent application having an application Ser. No. 09/961,579; filed Sep. 24, 2001, now U.S. Pat. No. 6,859,874 which application is hereby incorporated by reference.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003This invention is related to the field of processors and, more particularly, to the canceling of speculative instructions in response to a branch misprediction.

00042. Description of the Related Art

0005Branch instructions present numerous challenges to processor designers. The existence of branch instructions in code, and the mechanisms that the processor includes to handle the branch instructions with high performance, are frequently large factors in determining the overall performance that a user may actually experience when using a system including the processor.

0006One mechanism frequently used to address the challenges presented by branch instructions is speculative operation. Generally, branch instructions may be predicted (e.g. taken or not taken, for conditional branches, and/or branch target address predictions, for indirect branches and returns) and speculative operation may be performed based on the prediction. Instructions may be speculatively fetched and processed up to and/or including execution prior to resolution of the predicted branch instruction. If the prediction is correct, performance of the processor may be increased due to the speculative processing of the next instructions to be executed after the branch (either those at the branch target address or the sequential instructions). However, if the prediction is incorrect, the speculative instructions must be cancelled. Canceling the speculative instructions, particularly in wide issue processors, may be complex.

0007A further difficulty introduced in some instruction set architectures (e.g. the MIPS instruction set architecture) involves the branch delay slot. The instruction in the branch delay slot is typically executed irrespective of whether the branch instruction is taken or not taken. However, for some branch instructions, the instruction in the branch delay slot is architecturally defined to be conditional based on whether the corresponding branch is taken or not taken. If the branch is taken, the instruction in the branch delay slot is executed. If the branch is not taken, the instruction in the branch delay slot is not executed. Thus, the branch delay slot instruction is treated differently for different branches, further complicating the canceling of speculative instructions. Any type of instruction may be in the branch delay slot, and thus locating the instruction and canceling or not canceling the instruction based on which branch instruction that instruction follows is complicated.

SUMMARY OF THE INVENTION

0008A processor implements a mechanism for handling instruction cancellation for mispredicted branch instructions. Particularly, a first tag (referred to herein in certain exemplary embodiments as a branch sequence number) is assigned to a branch instruction. Dependent on the type of branch instruction, a second tag is assigned to an instruction in the branch delay slot of the branch instruction. The second tag may equal the first tag if the branch delay slot is unconditional for that branch, and may equal a different tag if the branch delay slot is conditional for the branch. If the branch is mispredicted, the first tag is broadcast to pipeline stages that may have speculative instructions, and the first tag is compared to tags in the pipeline stages. If the tag in a pipeline stage matches the first tag, the instruction is not cancelled. If the tag mismatches, the instruction is cancelled. Thus, an instruction in the unconditional delay slot is not cancelled (since the second tag equals the first tag for the unconditional delay slot) and an instruction in the conditional delay slot is cancelled (since the second tag equals a different tag). The cancellation mechanism thus may not require special handling of the branch delay slot during cancellation . . . the assignment of the tag may ensure the proper cancellation or non-cancellation of the branch delay slot instruction.

0009In one embodiment, the assignment of tags for a fetch group of concurrently fetched instructions may be performed in parallel. A plurality of branch sequence numbers may be generated, and one of the plurality may be selected for each instruction responsive to the cumulative number of branch instructions preceding that instruction within the fetch group. In embodiments having the conditional delay slot, the selection may be further responsive to whether or not the instruction is in a conditional delay slot.

BRIEF DESCRIPTION OF THE DRAWINGS

The following detailed description makes reference to the accompanying drawings, which are now briefly described.

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of one embodiment of a processor.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of a portion of one embodiment of a fetch/decode/issue unit shown in <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 3</figref> is a flowchart illustrating operation of one embodiment of a control circuit shown in <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart illustrating operation of one embodiment of an instruction queue shown in <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram of one embodiment of pipelines within execution units shown in <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart illustrating operation of one embodiment of the pipelines shown in <figref idref="DRAWINGS">FIG. 5</figref>.

<figref idref="DRAWINGS">FIG. 7</figref> is an example instruction sequence with corresponding branch sequence numbers.

<figref idref="DRAWINGS">FIG. 8</figref> is a second example instruction sequence with corresponding branch sequence numbers.

<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram of one embodiment of a control circuit shown in <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 10</figref> is a logic diagram of one embodiment of a mux control circuit shown in <figref idref="DRAWINGS">FIG. 9</figref>.

<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of a carrier medium.

0022While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0000Processor Overview

0023Turning now to <figref idref="DRAWINGS">FIG. 1</figref>, a block diagram of one embodiment of a processor <b>10</b> is shown. Other embodiments are possible and contemplated. In the embodiment of <figref idref="DRAWINGS">FIG. 1</figref>, the processor <b>10</b> includes an instruction cache <b>12</b>, a fetch/decode/issue unit <b>14</b>, a branch predictors unit <b>16</b>, a branch target buffer <b>18</b>, a return stack <b>20</b>, a set of integer execution units <b>22</b>A–<b>22</b>B, a set of floating point execution units <b>24</b>A–<b>24</b>B, a set of load/store execution units <b>26</b>A–<b>26</b>B, a register file <b>28</b>, a data cache <b>30</b>, and a bus interface unit <b>32</b>. The instruction cache <b>12</b> is coupled to the bus interface unit <b>32</b>, and is coupled to receive a fetch address from, and provide corresponding instructions to, the fetch/decode/issue unit <b>14</b>. The fetch/decode/issue unit <b>14</b> is further coupled to the branch predictors <b>16</b>, the branch target buffer <b>18</b>, the return stack <b>20</b>, and the execution units <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, and <b>26</b>A–<b>26</b>B. Specifically, the fetch/decode/issue unit <b>14</b> is coupled to provide a branch address to the branch predictors <b>16</b> and the branch target buffer <b>18</b>, and to receive a prediction from the branch predictors <b>16</b> and a target address from the branch target buffer <b>18</b>. The fetch/decode/issue unit <b>14</b> is coupled to provide a link address to the return stack <b>20</b> and to receive a predicted return address from the return stack <b>20</b>. The fetch/decode/issue unit <b>14</b> is coupled to provide instructions for execution to the execution units <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, and <b>26</b>A–<b>26</b>B and to receive a corrected fetch address and corresponding branch sequence number from the integer execution unit <b>22</b>A. The execution units <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, and <b>26</b>A–<b>26</b>B are generally coupled to the register file <b>28</b> and the data cache <b>30</b>, and the data cache <b>30</b> is coupled to the bus interface unit <b>32</b>.

0024Generally speaking, the fetch/decode/issue unit <b>14</b> is configured to generate fetch addresses for the instruction cache <b>12</b> and to receive corresponding instructions therefrom. The fetch/decode/issue unit <b>14</b> uses branch prediction information to generate the fetch addresses, to allow for speculative fetching of instructions prior to execution of the corresponding branch instructions. Specifically, in the illustrated embodiment, the fetch/decode/issue unit <b>14</b> may provide a branch address of the branch instruction to be predicted to the branch predictors <b>16</b> and the branch target buffer <b>18</b>. The branch predictors <b>16</b> may be an array of branch predictors indexed by the branch address. A prediction is generated from the selected branch predictor and provided to the fetch/decode/issue unit <b>14</b> (e.g. the typical two bit counters which are incremented when the corresponding branch is taken, saturating at 11 in binary, and decremented when the corresponding branch is not taken, saturating at 00 in binary, with the most significant bit indicating taken or not taken). The fetch/decode/issue unit <b>14</b> may use the branch prediction to select the next fetch address as either the target address or the sequential address of a conditional branch instruction. While any size and configuration may be used, one implementation of the branch predictors <b>16</b> may be 4 k entries in a direct-mapped configuration. The branch target buffer <b>18</b> may be an array of branch target addresses. The target addresses may be previously generated target addresses of any type of branch, or just those of indirect branches. Again, while any configuration may be used, one implementation may provide 64 entries in the branch target buffer <b>18</b>. Still further, the return stack <b>20</b> may be used to store link addresses of branch instructions which update a link resource (“branch and link” instructions). Such branch and link instructions may be used as procedure calls, and the corresponding return which terminates the called procedure may use the stored link address to return to the next instruction after the procedure call. The fetch/decode/issue unit <b>14</b> may provide link addresses when branch instructions which update the link register are fetched for pushing on the return stack <b>20</b>, and the return stack <b>20</b> may provide the address from the top entry of the return stack <b>20</b> as a predicted return address. The predicted return address may be selected as the next fetch address if a return is detected by the fetch/decode/issue unit <b>14</b>. While any configuration may be used, one implementation may provide 8 entries in the return stack <b>20</b>.

0025The fetch/decode/issue unit <b>14</b> decodes the fetched instructions and queues them in one or more instruction queues for issue to the appropriate execution units. The instructions may be speculatively issued to the appropriate execution units, again prior to execution/resolution of the branch instructions which cause the instructions to be speculative. In some embodiments, out of order execution may be employed (e.g. instructions may be issued in a different order than the program order). In other embodiments, in order execution may be used. However, some speculative issue/execution may still occur between the time that a branch instruction is issued and its result is generated from the execution unit which executes that branch instruction (e.g. the execution unit may have more than one pipeline stage).

0026The integer execution units <b>22</b>A–<b>22</b>B are generally capable of handling integer arithmetic/logic operations, shifts, rotates, etc. At least the integer execution unit <b>22</b>A is configured to execute branch instructions, and in some embodiments both of the integer execution units <b>22</b>A–<b>22</b>B may handle branch instructions. In one implementation, only the execution unit <b>22</b>B executes integer multiply and divide instructions although both may handle such instructions in other embodiments. The floating point execution units <b>24</b>A–<b>24</b>B similarly execute the floating point instructions. The integer and floating point execution units <b>22</b>A–<b>22</b>B and <b>24</b>A–<b>24</b>B may read and write operands to and from the register file <b>28</b> in the illustrated embodiment, which may include both integer and floating point registers. The load/store units <b>26</b>A–<b>26</b>B may generate load/store addresses in response to load/store instructions and perform cache accesses to read and write memory locations through the data cache <b>30</b> (and through the bus interface unit <b>32</b>, as needed), transferring data to and from the registers in the register file <b>28</b> as well.

0027The instruction cache <b>12</b> may have any suitable configuration and size, including direct mapped, fully associative, and set associative configurations. Similarly, the data cache <b>30</b> may have any suitable configuration and size, including any of the above mentioned configurations. In one implementation, each of the instruction cache <b>12</b> and the data cache <b>30</b> may be 4 way set associative, 32 kilobyte (kb) caches including 32 byte cache lines. Both the instruction cache <b>12</b> and the data cache <b>30</b> are coupled to the bus interface unit <b>32</b> for transferring instructions and data into and out of the caches in response to misses, flushes, coherency activity on the bus, etc.

0028In one implementation, the processor <b>10</b> is designed to the MIPS instruction set architecture (including the MIPS-3D and MIPS MDMX application specific extensions). The MIPS instruction set may be used below as a specific example of certain instructions. However, other embodiments may implement the IA-32 or IA-64 instruction set architectures developed by Intel Corp., the PowerPC instruction set architecture, the Alpha instruction set architecture, the ARM instruction set architecture, or any other instruction set architecture.

0029It is noted that, while <figref idref="DRAWINGS">FIG. 1</figref> illustrates two integer execution units, two floating point execution units, and two load/store units, other embodiments may employ any number of each type of unit, and the number of one type may differ from the number of another type.

0000Conditional Branch Delay Slot Handling—Overview

0030The processor <b>10</b> may employ branch sequence numbers for handling speculative processing and the conditional branch delay slot. As used herein, the term “branch delay slot” refers to the next sequential instruction location after a particular branch instruction in program order.

0031For some types of branch instructions, the instruction in the branch delay slot is executed unconditionally. In other words, regardless of whether or not the branch instruction is taken, the instruction in the branch delay slot is executed. The next instruction to be executed after the instruction in the branch delay slot is either the instruction at the target address of the branch instruction (if the branch instruction is taken) or the instruction sequential to the branch delay slot (if the branch instruction is not taken). For other types of branch instructions, the branch delay slot may be conditional. If the branch instruction is taken, the instruction in the branch delay slot is executed (followed by the instruction at the target address of the branch instruction). If the branch instruction is not taken, the instruction in the branch delay slot is nullified (and the next instruction to be executed is the instruction sequential to the branch delay slot).

0032The processor <b>10</b> may assign a first branch sequence number to the branch instruction, and may assign a second branch sequence number to the instruction in the branch delay slot. Depending upon the type of branch instruction, the second branch sequence number may be either equal to the first branch sequence number (if the delay slot is unconditional) or a different branch sequence number (if the delay slot is conditional). If the branch instruction is mispredicted, the branch sequence number of the branch instruction may be broadcast to pipeline stages that may have speculative instructions in them. If the branch sequence number of an instruction matches that of the branch instruction, then the instruction is not cancelled and processing may continue. Thus, the unconditional delay slot instruction is not cancelled. If the branch sequence number of the instruction does not match that of the branch instruction, then the instruction is cancelled. Thus, the conditional delay slot instruction is cancelled.

0033Accordingly, the conditional/unconditional delay slot special case is handled in the assignment of branch sequence numbers. Special logic to locate the delay slot instruction and to cancel or not cancel the instruction based on the type of branch instruction may not be required. As used herein, the term “cancel”, when referring to an instruction, means ensuring that the instruction does not update architected state of the processor. Any mechanism for canceling the instruction may be used. For example, state carried with the instruction in the pipeline may be altered to indicate that no update should be performed but the instruction may continue through the pipeline and exit the pipeline like any other instruction. Alternatively, processing of the instruction in the pipeline may cease and a bubble in the pipeline may be introduced where the instruction was (or the bubble may be squashed). Any combination of mechanisms for canceling may be employed as well, as desired.

0034The same mechanism may further be used to cancel other speculative instructions. Generally, the processor <b>10</b> may assign the same branch sequence number to each instruction within a basic block terminated by a branch instruction, and may change the branch sequence number in response to the branch instruction (e.g. the branch sequence number may be incremented). The different branch sequence number mentioned above for the conditional delay slot may be the branch sequence number after it has been changed in response to the branch instruction. Subsequent instructions may be assigned the incremented branch sequence number until another branch instruction is detected, terminating another basic block. Thus, the branch sequence number of a branch instruction matches the branch sequence number of instructions within its basic block and differs from the branch sequence number of instructions in other basic blocks.

0035As used herein, the term “basic block” refers to the group of instructions which are guaranteed to execute (notwithstanding an exception) once a particular branch instruction is resolved as either taken or not taken. Thus, basic blocks are terminated by branch instructions, and a branch instruction may define the beginning of another basic block at its target address and at its sequential address (including or not including the branch delay slot, depending on the type of branch instruction).

0036In one embodiment, the processor <b>10</b> employs the MIPS instruction set architecture. In such an embodiment, the type of branch instruction which indicates a conditional delay slot is the “branch likely” type. Branch likely instructions are used as a hint to the processor <b>10</b> that the branch is likely to be taken. For example, branch instructions used to form a loop may be branch likely instructions, since they are taken on each iteration of the loop other than the last iteration of the loop. The processor <b>10</b> may, in general, predict the branch likely instructions taken. Other types of branches in the MIPS instruction set may indicate an unconditional delay slot. Other embodiments may employ different types of branches indicating the conditional or unconditional delay slot. Generally, the “type” of a branch is a classification of the branch instruction into one of at least two groups of branch instructions, where at least one of the groups indicates a conditional branch delay slot and the remaining groups indicate an unconditional delay slot. Any classification of branches may be used.

0037Turning now to <figref idref="DRAWINGS">FIG. 2</figref>, a block diagram of one embodiment of a portion of the fetch/decode/issue unit <b>14</b> is shown. Other embodiments are possible and contemplated. In the embodiment of <figref idref="DRAWINGS">FIG. 2</figref>, the portion of the fetch/decode/issue unit <b>14</b> includes a branch sequence number (BSN) control circuit <b>40</b>, a current BSN register <b>42</b>, a branch state table <b>44</b>, an instruction queue <b>46</b>, and an issue logic circuit <b>48</b>. The BSN control circuit <b>40</b> is coupled to the current BSN register <b>42</b>, the branch state table <b>44</b>, and the instruction queue <b>46</b>. Additionally, the BSN control circuit <b>40</b> is coupled to receive the BSN and a misprediction signal from the integer execution unit <b>22</b>A, instructions from the instruction cache <b>12</b>, and prediction information from the branch predictors <b>16</b>. The instruction queue <b>46</b> is further coupled to receive instructions and other information from the decode logic within the fetch/decode/issue unit <b>14</b> (not shown) and is coupled to the issue logic circuit <b>48</b>, which is also coupled to receive the BSN and the misprediction signal from the integer execution unit <b>22</b>A. The issue queue <b>46</b> is coupled to provide issued instructions and corresponding BSNs to the execution units <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, and <b>26</b>A–<b>26</b>B.

0038Generally, the BSN control circuit <b>40</b> is configured to receive instructions fetched from the instruction cache <b>12</b> and to assign BSNs to those instructions. A BSN is assigned to each instruction, and provided to the instruction queue <b>46</b> for storage. Separately, the instructions may be provided to the decode logic for decoding, and the instructions and other information generated by the decode logic may be provided to the instruction queue <b>46</b> for storage as well. The BSN control circuit <b>40</b> scans the instructions to locate branches, and assigns either the current BSN (stored in the current BSN register <b>42</b>), the current BSN+1, or the current BSN+2 (in one embodiment) to each instruction based on whether or not a branch instruction is detected and the type of branch instruction. Additional details regarding the assignment of BSNs to an instruction are provided below in the flowchart of <figref idref="DRAWINGS">FIG. 3</figref>. Furthermore, additional details regarding the parallel assignment of BSNs to multiple concurrently fetched instructions (where the current BSN may differ between the concurrently fetched instructions) are provided below in <figref idref="DRAWINGS">FIGS. 9 and 10</figref>.

0039The BSN control circuit <b>40</b> is configured to update the current BSN based on the instructions processed. In one embodiment, the BSN control circuit <b>40</b> processes a plurality of concurrently fetched instructions in parallel. The plurality of concurrently fetched instructions may include multiple branch instructions. However, if one branch instruction is predicted taken, the remaining branch instructions may be cancelled (and the target of the predicted taken branch may be fetched). Accordingly, updating the current BSN may be affected by branch predictions for the branch instructions within the plurality of concurrently fetched instructions. In one specific embodiment, four concurrently fetched instructions are processed in parallel and the branch prediction for the first instruction of the concurrently fetched instructions (if a branch instruction) is used in updating the current BSN.

0040In the illustrated embodiment, the BSN may also be used to identify an entry in the branch state table <b>44</b> assigned to a given branch instruction. Generally, the branch state table <b>44</b> may be used to store various information used in predicting the branch instruction, to allow for prediction update when the branch instruction is resolved. The BSN may include relatively few bits as compared to the information stored in an entry of the branch state table <b>44</b>, and thus the smaller BSN may be more easily transmitted with the branch instruction through the pipeline of the processor <b>10</b>. As illustrated in <figref idref="DRAWINGS">FIG. 2</figref>, the branch PC (or a portion thereof) may be stored, since that value may be used to locate information in the branch predictors <b>16</b> or the branch target buffer <b>18</b>, as well as other prediction state. History information may also be used to locate the information in the branch predictors <b>16</b> or the branch target buffer <b>18</b>, and the history information may be stored as well. Alternatively, the value actually used to index each storage may be stored. Furthermore, the information read from the branch predictors <b>16</b> or the branch target buffer <b>18</b> may be stored (e.g. the prediction counters, predicted target address, etc.). Information regarding the type of branch may also be stored. Generally, any information that may be used to update branch predictors <b>16</b>, the branch target buffer <b>18</b>, the return stack <b>20</b>, etc. in response to correct prediction or misprediction may be used. The information to be stored may be provided from any number of sources (not shown).

0041If a misprediction is detected, the integer execution unit <b>22</b>A asserts the misprediction signal and provides the corresponding BSN to the BSN control circuit <b>40</b>. The BSN control circuit <b>40</b> may read the entry of the branch state table <b>44</b> indicated by the BSN and provide the information to prediction correction logic (not shown) which may update the branch prediction information (e.g. the information stored in the branch predictors <b>16</b> and/or the branch target buffer <b>18</b>) to reflect the actual execution of the branch instruction. It is noted that the BSN and the misprediction signal from the integer execution unit <b>22</b>A may be directly connected to the branch state table <b>44</b> for reading the entry corresponding to the mispredicted branch instruction.

0042While the embodiment shown in <figref idref="DRAWINGS">FIG. 2</figref> uses the BSN as an indication of the entry in the branch state table <b>44</b> in addition to assigning it to instructions to identify instructions for cancellation when a misprediction is detected, other embodiments may not employ the branch state table <b>44</b>. In such embodiments, the BSN control circuit <b>40</b> may assign BSNs for cancellation purposes only, and may perform the BSN assignment as illustrated in <figref idref="DRAWINGS">FIG. 3</figref> below. Generally, the BSN control circuit <b>40</b> may operate on instructions at any point in the pipeline of the processor <b>10</b> which is prior to issue of the instructions for execution. In the illustrated embodiment, the BSN control circuit <b>40</b> operates during the decode stage of the pipeline, but can operate at any stage subsequent to fetch of the instructions. Particularly, in the illustrated embodiment, the BSN control circuit <b>40</b> operates prior to queuing of the instructions in the instruction queue <b>46</b>. The instruction queue <b>46</b> may be viewed as part of the pipeline of the processor <b>10</b> (in addition to the stages shown in <figref idref="DRAWINGS">FIG. 5</figref> below). As used herein, the term “pipeline” refers to a circuit arrangement in which an instruction is passed through multiple pipeline stages, each of which is assigned a portion of the processing required to perform the operations specified by that instruction. Generally, the pipeline includes fetching the instruction, decoding the instruction, issuing the instruction for execution, reading the operands of the instruction, executing the instruction, and storing the results. One or more of these operations may occur in the same pipeline stage, and any of these operations may be performed over multiple pipeline stages, as desired.

0043In addition to reporting mispredictions, the integer execution unit <b>22</b>A may report BSNs of branch instructions which are correctly predicted to free the BSN (and the branch state table <b>44</b> entry, in embodiments supporting the branch state table <b>44</b>) for subsequent branch instructions.

0044Generally, the instruction queue <b>46</b> stores instructions until they can be issued to an appropriate execution unit for execution. The instructions are stored, as well as the BSNs assigned by the BSN control circuit <b>40</b> and other information provided by the decode logic. Included in the other information may be, for example, dependency information indicating on which earlier instructions in the instruction queue <b>46</b> a particular instruction depends, what operands are used, etc. The issue logic circuit <b>48</b> may use such information to determine when an instruction is ready to be issued. In one embodiment, instructions are issued in program order but speculatively. Thus, an instruction is ready for issue if: (i) the instructions prior to that instruction in the instruction queue <b>46</b> have been issued or are being issued; and (ii) that instruction is otherwise ready for issue (its operands are available, etc.). Other embodiments may employ out of order issue, as desired. If an instruction is selected for issue, the issue logic reads the corresponding entry storing that instruction and routes the instruction, the corresponding BSN, and any other information that may be useful for execution to the execution unit <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, or <b>26</b>A–<b>26</b>B selected to execute that instruction. In one embodiment, up to four instructions may be issued per clock cycle, with at most one instruction being issued to a given execution unit <b>22</b>A–<b>22</b>B, <b>24</b>A–<b>24</b>B, and <b>26</b>A–<b>26</b>B. Other embodiments may concurrently issue more or fewer instructions. As used herein, the term “issue” refers to transmitting an instruction to an execution unit for execution.

0045The issue logic circuit <b>48</b> may also receive the BSN of a mispredicted branch instruction from the integer execution unit <b>22</b>A. In an in order embodiment, most of the instructions in the instruction queue <b>46</b> are cancelled in response to a mispredicted branch. However, the oldest instruction in the instruction queue <b>46</b> may be the instruction in the branch delay slot corresponding to the mispredicted branch instruction. Thus, the issue logic circuit <b>48</b> may compare the BSN of the mispredicted branch to the BSN of the oldest instruction in the instruction queue for possible cancellation.

0046It is noted that, while the embodiment of the BSN control circuit <b>40</b> illustrated in <figref idref="DRAWINGS">FIG. 2</figref> scans the instructions from instruction cache <b>12</b> to perform BSN assignment, other embodiments may scan other information. For example, the instruction cache <b>12</b> may store predecode data indicative of the instructions stored therein, and the predecode data may be provided for scanning. The predecode data may identify, for example, the branch instructions within a group of instruction bytes fetched from the instruction cache <b>12</b> as well as the type of branch instruction. Still further, data stored in branch prediction structures could be used to identify branches and/or branch type. In yet another alternative, signals indicating which instructions are valid, which are branch instructions, and the type of the branch instructions may be provided from the decode logic, not shown.

0047Turning next to <figref idref="DRAWINGS">FIG. 3</figref>, a flowchart is shown illustrating operation of one embodiment of the BSN control circuit <b>40</b> for assigning a BSN to an instruction. Other embodiments are possible and contemplated. While the blocks shown in <figref idref="DRAWINGS">FIG. 3</figref> are illustrated in a particular order for ease of understanding, any suitable order may be used. Furthermore, blocks may be performed in parallel in combinatorial logic circuitry within the BSN control circuit <b>40</b>. Alternatively, some blocks may be performed in different clock cycles than other blocks.

0048The BSN control circuit <b>40</b> determines if the instruction is in the branch delay slot (decision block <b>50</b>). In other words, the BSN control circuit <b>40</b> determines if the preceding instruction, in program order, is a branch instruction. If the instruction is in the branch delay slot, and the branch instruction is a branch likely (decision block <b>52</b>), the BSN control circuit <b>40</b> assigns the BSN of the instruction to be equal to the BSN of the branch instruction plus one (block <b>54</b>). If the instruction is in the branch delay slot, and the branch instruction is not a branch likely (decision block <b>52</b>), the BSN control circuit <b>40</b> assigns the BSN of the instruction to be equal to the BSN of the branch instruction (block <b>56</b>). The BSN of the branch instruction may be the current BSN, if the branch instruction and the instruction in the branch delay slot are fetched concurrently, or may be the current BSN−1, if the branch instruction is fetched during a clock cycle prior to the clock cycle in which the instruction in the branch delay slot is fetched. For the situation in which the branch instruction and the instruction in the branch delay slot are fetched on different clock cycles, the BSN control circuit <b>40</b> may retain an indication of whether or not the branch was a branch likely or may precalculate the BSN for the instruction in the delay slot (e.g. according to blocks <b>50</b>–<b>56</b>) and retain the BSN for assignment to the instruction in the branch delay slot during the next clock cycle.

0049On the other hand, if the instruction is not in the branch delay slot of a branch instruction, the BSN control circuit <b>40</b> assigns the BSN of the instruction to be equal to the current BSN (block <b>58</b>). Additionally, if the instruction is a branch instruction (decision block <b>60</b>), the BSN control circuit <b>40</b> increments the current BSN (block <b>62</b>).

0050The flowchart of <figref idref="DRAWINGS">FIG. 3</figref> illustrates the operation of the BSN control circuit <b>40</b> in response to one instruction. However, multiple instructions may be fetched concurrently. For example, in one embodiment, a fetch group of 16 bytes (4 MIPS instructions) may be implemented and thus up to four instructions may be fetched concurrently. The BSN control circuit <b>40</b> may generally perform the operation illustrated by the flowchart of <figref idref="DRAWINGS">FIG. 3</figref> in parallel for each instruction, except that the current BSN shown in block <b>62</b> may be the current BSN from the current BSN register <b>42</b> as modified in response to any preceding branch instructions within the fetch group.

0051It is noted that a particular BSN assigned to a branch instruction is not reused for another branch instruction until that branch instruction is resolved. Thus, the BSN control circuit <b>40</b> may include circuitry for detecting that all BSNs are currently assigned to in-flight instructions and for stalling instructions until a BSN becomes available.

0052Turning now to <figref idref="DRAWINGS">FIG. 4</figref>, a flowchart is shown illustrating operation of one embodiment of the issue logic circuit <b>48</b> in response to receiving a BSN for a mispredicted branch instruction. Other embodiments are possible and contemplated.

0053The issue logic circuit <b>48</b> compares the BSN of the mispredicted branch to the BSN of the oldest instruction in the instruction queue <b>46</b>. If the BSNs match (decision block <b>70</b>), then the instruction is an unconditional branch delay slot instruction and should not be cancelled. If the BSNs do not match, then the instruction is either a conditional branch delay slot instruction and thus should be cancelled (since the branch likely was predicted taken and is mispredicted) or the instruction is another instruction subsequent to the branch instruction and thus is to be cancelled (block <b>72</b>). As mentioned above, the other instructions in the instruction queue <b>46</b> may be cancelled in response to a misprediction.

0054In one embodiment, the instruction queue <b>46</b> may be implemented as a shifting structure in which instructions are shifted down as older instructions are issued. In such a structure, the oldest instruction is always in the same entry of the instruction queue <b>46</b> and the issue logic circuit <b>48</b> may include a comparator coupled to this entry and to receive the BSN from the integer execution unit <b>22</b>A to perform the comparison illustrated by decision block <b>70</b>. On the other hand, the instruction queue <b>46</b> may be a circular buffer in which the instructions are allocated entries in the instruction queue <b>46</b> and remain in those entries until issued. A pointer may indicate the oldest instruction in the instruction queue <b>46</b>, and the BSN may be read from the indicated entry for input to a comparator to perform the comparison illustrated by decision block <b>70</b>.

0055Turning next to <figref idref="DRAWINGS">FIG. 5</figref>, a block diagram of one embodiment of the execution units <b>22</b>A–<b>22</b>B, <b>24</b>A, and <b>26</b>B is shown. The execution units <b>24</b>B and <b>26</b>A may be similar to the corresponding execution units <b>24</b>A and <b>26</b>B shown in <figref idref="DRAWINGS">FIG. 5</figref>. Other embodiments are possible and contemplated. In the embodiment of <figref idref="DRAWINGS">FIG. 5</figref>, each execution unit is shown as including multiple pipeline stages (e.g. stages <b>80</b>A–<b>80</b>C in the integer execution unit <b>22</b>A). Each execution unit is coupled to receive an instruction and corresponding BSN from the fetch/decode/issue unit <b>14</b> (e.g. from the instruction queue <b>46</b> for the embodiment shown in <figref idref="DRAWINGS">FIG. 2</figref>). Each pipeline stage stores an instruction (as well as any other related information that may be generated or used within the pipeline), the BSN for the instruction, and a valid bit indicating whether or not an instruction is present in that stage. Only the BSN and the valid bit are illustrated as fields in <figref idref="DRAWINGS">FIG. 5</figref>. Each of the pipeline stages is coupled to another stage (or to provide an output, if the stage is the last stage in the pipeline). Additionally, the BSN field of the stage is coupled to a respective comparator (e.g. comparators <b>82</b>A–<b>82</b>C corresponding to stages <b>80</b>A–<b>80</b>C in the integer execution unit <b>22</b>A). The comparators <b>82</b>A–<b>82</b>C are further coupled to receive the BSN corresponding to a mispredicted branch instruction from the integer execution unit <b>22</b>A. The misprediction signal may also be received to enable the comparison. The output of each comparator is coupled to the respective valid bit of the following stage (e.g. comparator <b>82</b>A is coupled to provide an output to the valid bit of stage <b>80</b>B).

0056Generally, the pipeline stages illustrated in <figref idref="DRAWINGS">FIG. 5</figref> may be part of the pipeline of the processor <b>10</b>. Each stage may operate on a different instruction concurrently (e.g. the stage <b>80</b>A may be operating on a different integer instruction than stage <b>80</b>B, etc.). The circuitry forming each stage, which does the work assigned to the stage, is omitted for simplicity in <figref idref="DRAWINGS">FIG. 5</figref>. The number of stages in each type of unit may vary and may differ from the number of stages in the other types of units. For example, in one implementation, the integer execution units <b>22</b>A–<b>22</b>B include five pipeline stages, the floating point execution units <b>24</b>A–<b>24</b>B include eight stages, and the load/store units <b>26</b>A–<b>26</b>B include four stages.

0057When the integer execution unit <b>22</b>A detects a mispredicted branch instruction, the integer execution unit <b>22</b>A outputs the BSN of the mispredicted branch and asserts the misprediction signal. Each of the comparators at each of the pipeline stages of the execution units compares the BSN of the instruction therein to the BSN of the mispredicted branch instruction. If the BSNs match, then the instruction in that stage is in the basic block terminated by the branch and thus is not cancelled. The output of the comparator is a one, which does not clear the valid bit as the instruction moves to the next stage. To prevent validating a stage which does not store an instruction, the output of the comparator may be logically ANDed with the current state of the valid bit. If the BSNs do not match, then the instruction in that stage is in a subsequent basic block (for embodiments employing in-order issue) and thus the instruction is cancelled. The output of the comparator is a zero, which may clear the valid bit as the instruction moves to the next stage. Since the instruction is invalidated, the execution units may not update any architected state in response to the instruction (e.g. the instruction appears to be a bubble in the pipeline).

0058It is noted that, for in-order embodiments, a comparison of less than the full BSN may be used. Only enough of the BSN need be compared to accurately distinguish among the number of basic blocks which may be outstanding between issuance and writeback of results or evaluation of the branch instruction. For example, in an embodiment in which the integer execution unit <b>22</b>A outputs a misprediction indication from the fourth stage of its pipeline, up to four branch instructions (one in each of the first four stages of the integer execution unit <b>22</b>A's pipeline) may be outstanding and thus four unique BSNs may be outstanding, plus a BSN for the basic block following the most recent of the four branch instructions. The BSNs are in numerically increasing order (again due to the in-order issuance of instructions). However, other sorts of assignments may be used (e.g. gray coding) in other embodiments. Accordingly, the least significant three bits of the BSN may be used in the comparisons within the execution units and for the oldest instruction in the instruction queue <b>46</b>. However, additional BSNs may be outstanding within the instruction queue <b>46</b> at any given time, and thus it may be desirable for the BSN control circuit <b>40</b> and the instruction queue <b>46</b> to support BSNs in excess of three bits so that stalling due to a lack of available BSNs is infrequent. For example, four bits of BSN may be implemented, in one embodiment.

0059Turning now to <figref idref="DRAWINGS">FIG. 6</figref>, a flowchart is shown illustrating operation of a pipeline stage in response to a BSN corresponding to a mispredicted branch instruction is shown. Other embodiments are possible and contemplated.

0060If the BSN corresponding to the mispredicted branch instruction matches the BSN in the stage (decision block <b>90</b>), the stage continues processing of the instruction therein (block <b>92</b>). If the BSNs do not match, the instruction is cancelled (block <b>94</b>). For the embodiment of <figref idref="DRAWINGS">FIG. 5</figref>, the instruction is cancelled by resetting the valid bit corresponding to the instruction. Other embodiments may use any cancellation method, as described above.

0061It is noted that, while some embodiments of the processor <b>10</b> described above may employ in-order issue, other embodiments may employ out of order issue. In such embodiments, the BSN comparisons may be a greater-than/less-than compare rather than an equality compare. An additional most significant bit may be included in the BSNs to account for the rollover of BSN assignment, and depending on the state of the most significant bits, either a greater-than or a less-than result indicates that the instruction is subsequent to the mispredicted branch instruction and thus should be cancelled. Particularly, if the most significant bits of the branch BSN and the instruction BSN are the same, a greater-than result (the BSN of the instruction is greater than the BSN of the mispredicted branch instruction) indicates that the instruction is subsequent to the mispredicted branch instruction. If the most significant bits differ, a less-than result (the BSN of the instruction is less than the BSN of the mispredicted branch instruction) indicates that the instruction is subsequent to the mispredicted branch instruction. Additionally, the instruction queue <b>46</b> may compare the BSNs of all instructions in an out of order embodiment to determine which instructions to cancel.

0062Turning now to <figref idref="DRAWINGS">FIG. 7</figref>, a first exemplary code sequence and corresponding BSN assignment is shown. The exemplary instruction sequence includes a first basic block having instructions In<b>0</b>, In<b>1</b>, and In<b>2</b>, terminated by a branch instruction B<b>1</b> (a non-branch likely instruction). Instruction In<b>3</b> is in the branch delay slot of the branch instruction. A second basic block including instructions In<b>4</b>, In<b>5</b>, and In<b>6</b> is shown, terminated by a second branch instruction B<b>2</b> (a non-branch likely instruction). Instruction In<b>7</b> is in the branch delay slot of the second branch instruction, and the Instruction In<b>8</b> is also shown.

0063The BSN is equal to N when instruction In<b>0</b> is fetched, and thus a BSN of N is assigned to instructions In<b>0</b>, In<b>1</b>, In<b>2</b>, and the branch instruction B<b>1</b>. Additionally, since the branch instruction B<b>1</b> is not a branch likely instruction and therefore the branch delay slot is unconditional, the instruction In<b>3</b> is assigned a BSN of N. Subsequent instructions In<b>4</b>, In<b>5</b>, and In<b>6</b> and the second branch instruction B<b>2</b> are assigned the BSN of N+1 (the BSN after being incremented in response to the branch instruction B<b>1</b>). The instruction In<b>7</b>, being in an unconditional branch delay slot, is also assigned a BSN of N+1. The instruction In<b>8</b> is assigned a BSN of N+2 (the BSN after being incremented in response to the second branch instruction B<b>2</b>).

0064<figref idref="DRAWINGS">FIG. 8</figref> is a second exemplary code sequence and corresponding BSN assignment. The exemplary instruction sequence includes a first basic block having instructions In<b>0</b>, In<b>1</b>, and In<b>2</b>, terminated by a branch-likely instruction BL<b>1</b>. Instruction In<b>3</b> is in the branch delay slot of the branch-likely instruction BL<b>1</b>. A second basic block including instructions In<b>4</b>, In<b>5</b>, and In<b>6</b> is shown, terminated by a second branch-likely instruction BL<b>2</b>. Instruction In<b>7</b> is in the branch delay slot of the second branch-likely instruction BL<b>2</b>, and the Instruction In<b>8</b> is also shown.

0065The BSN is equal to N when instruction In<b>0</b> is fetched, and thus a BSN of N is assigned to instructions In<b>0</b>, In<b>1</b>, In<b>2</b>, and the branch-likely instruction BL<b>1</b>. The branch-likely instruction BL<b>1</b> indicates that the branch delay slot is conditional, and thus the instruction In<b>3</b> is assigned a BSN of N+1 (the BSN after being incremented in response to the branch-likely instruction BL<b>1</b>). Subsequent instructions In<b>4</b>, In<b>5</b>, and In<b>6</b> and the second branch-likely instruction BL<b>2</b> are assigned the BSN of N+1. The instruction In<b>7</b>, being in an conditional branch delay slot, is assigned a BSN of N+2 (the BSN after being incremented in response to the second branch-likely instruction BL<b>2</b>). The instruction In<b>8</b> is also assigned a BSN of N+2.

0000Parallel BSN Assignment

0066As mentioned above, the BSN control circuit <b>40</b> may be configured to process multiple concurrently fetched instructions in parallel. A set of concurrently fetched instructions will be referred to more succinctly herein as a “fetch group”. For example, <figref idref="DRAWINGS">FIGS. 9 and 10</figref> illustrate an example in which 4 instructions (aligned to a 4 instruction boundary, e.g. 16 bytes in the MIPS architecture) form a fetch group. Generally, the BSN control circuit <b>40</b> may maintain a current BSN (in the current BSN register <b>42</b>) which reflects the fetch groups previously processed by the BSN control circuit <b>40</b>. The BSN control circuit <b>40</b> may unconditionally generate one or more BSNs from the current BSN (e.g. by incrementing the BSN) to create a set of BSNs for assignment to the current fetch group. Based on the cumulative number of branch instructions within the fetch group and prior to a given instruction, a BSN may be selected from the set of BSNs for assignment to the given instruction. For example, if no branches are prior to the given instruction, the current BSN is selected. If one branch is prior to the given instruction, the current BSN+1 is selected. If two branches are prior to the given instruction, the current BSN+2 is selected. Since the incremented BSNs are unconditionally generated and then selected, the assignment of a BSN for the given instruction may be independent of the assignment of a BSN for other instructions in the fetch group.

0067For embodiments in which the branch delay slot is implemented (e.g. the MIPS architecture), the last instruction of the most recently processed fetch group (the “previous fetch group”) may also be included in selecting BSNs. In such embodiments, the instruction in the branch delay slot (if it is unconditional) may be part of the basic block including the corresponding branch instruction, and thus the basic block boundary (indicated by changing the BSN) is actually the branch delay slot. Accordingly, the current BSN in the current BSN register <b>42</b> may be calculated without regard to the last instruction in the previous fetch group, and the BSNs for instructions in the current fetch group may be assigned considering the last instruction in the previous fetch group in addition to the instructions in the current fetch group. Similarly, generation of the current BSN for the next fetch group may consider the last instruction in the previous fetch group and the branch instructions in the current fetch group, excluding the last instruction in the current fetch group.

0068On the other hand, if the branch delay slot is conditional, the instruction in the branch delay slot is not part of the basic block terminated by the corresponding branch instruction. In one embodiment, an initial set of BSNs may be assigned to the instructions in the current fetch group based on the number of preceding branch instructions (including the last instruction in the previous fetch group). The initial set of BSNs may be the assigned BSNs for each instruction, except for the conditional branch delay slot instruction. For the conditional branch delay slot instruction, the initial BSN assigned to the next consecutive instruction is assigned (by detecting that the instruction preceding the conditional branch delay slot instruction is of a type indicating that the delay slot is conditional, e.g. the branch likely instructions in the MIPS architecture).

0069<figref idref="DRAWINGS">FIGS. 9 and 10</figref> illustrate an embodiment of the BSN control circuit <b>40</b> for an architecture having the branch delay slot and having the instruction in the branch delay slot conditional for certain types of branch instructions (e.g. the MIPS architecture). Additionally, the embodiment shown may handle a fetch group of 4 instructions. Other embodiments are contemplated which do not include the branch delay slot, as well as embodiments in which the branch delay slot is unconditional. Other embodiments may also handle more or fewer than 4 instructions in a fetch group.

0070Turning now to <figref idref="DRAWINGS">FIG. 9</figref>, a block diagram of a portion of one embodiment of the BSN control circuit <b>40</b> and the current BSN register <b>42</b> is shown. Particularly, the portion for assigning BSNs is shown. Other embodiments are possible and contemplated. The embodiment of <figref idref="DRAWINGS">FIG. 9</figref> may be used for fetch groups of four instructions, although more or fewer instructions may be included in a fetch group in other embodiments. In the embodiment of <figref idref="DRAWINGS">FIG. 9</figref>, the BSN control circuit <b>40</b> includes a mux control circuit <b>100</b>, an adder circuit <b>102</b>, a last branch register <b>104</b>, a first set of multiplexors (muxes) <b>106</b>A–<b>106</b>D, a second set of muxes <b>108</b>A–<b>108</b>D, and a next BSN mux <b>110</b>. The mux control circuit <b>100</b> is coupled to receive instructions in a fetch group from the instruction cache <b>112</b>, a branch prediction for the first instruction in the fetch group from the branch predictors <b>16</b> (Pt[<b>0</b>] in <figref idref="DRAWINGS">FIG. 9</figref>), and to the last branch register <b>104</b>. Additionally, the mux control circuit <b>100</b> is coupled to provide selection controls to the muxes <b>110</b>, <b>106</b>B–<b>106</b>D, and <b>108</b>B–<b>108</b>D. The selection controls to muxes <b>106</b>A and <b>108</b>A are provided from the last branch register <b>104</b>. The mux <b>110</b> is coupled to the adder circuit <b>102</b> and to the current BSN register <b>42</b>. Each of the muxes <b>106</b>A–<b>106</b>D and <b>108</b>A are coupled to the current BSN register <b>42</b>, and the muxes <b>106</b>A–<b>106</b>D are further coupled to the adder circuit. Each of the muxes <b>108</b>A–<b>108</b>D are coupled to receive outputs of one or more muxes <b>106</b>A–<b>106</b>D as shown in <figref idref="DRAWINGS">FIG. 9</figref>.

0071The adder circuit <b>102</b> receives the current BSN (labeled simply BSN in <figref idref="DRAWINGS">FIG. 9</figref> and referred to below as BSN for brevity) from the current BSN register <b>42</b> and generates the BSN incremented by one (BSN+1) and the BSN incremented by two (BSN+2). The BSN is provided to each of the muxes <b>110</b>, <b>108</b>A, and <b>106</b>A–<b>106</b>D. The BSN+1 is provided to each of muxes <b>110</b> and <b>106</b>A–<b>106</b>D. The BSN+2 is provided to each of the muxes <b>110</b> and <b>106</b>C–<b>106</b>D.

0072Various signals are illustrated in <figref idref="DRAWINGS">FIG. 9</figref>, including the br[<b>3</b>:<b>0</b>], brl[<b>3</b>:<b>0</b>], and BSN[<b>3</b>:<b>0</b>] signals. Each of these signals corresponds to one of the instructions in the fetch group, with <b>0</b> referring to the first instruction in the fetch group, <b>1</b> referring to the second instruction in the fetch group, <b>2</b> referring to the third instruction in the fetch group, and <b>3</b> referring to the fourth instruction in the fetch group. The br[<b>3</b>:<b>0</b>] and brl[<b>3</b>:<b>0</b>] signals are generated by the mux control circuit <b>100</b> in response to the instructions in the fetch group. Specifically, the br[n] signal indicates whether or not instruction “n” is a branch instruction (of any type). The brl[n] signal indicates whether or not instruction “n” is a branch likely instruction. The BSN[n] signal is the BSN assigned to instruction “n”. The br[<b>3</b>] and brl[<b>3</b>] signals are provided to the last branch register <b>104</b> for storage, and are output as the last_brl and last_br signals in the next clock cycle. The last_brl and last_br signals are therefore indicative of the last instruction in the previous fetch group.

0073As mentioned above, the BSN control circuit <b>40</b> may assign an initial set of BSNs to the instructions in the fetch group based on the cumulative number of branch instructions prior to each instruction (including the last instruction in the previous fetch group and excluding the branch instruction immediately prior to that instruction). The initial assignment of BSNs comprises the input of the BSN from the current BSN register <b>42</b> to the mux <b>108</b>A (for instruction <b>0</b>), the selection of one of BSN and BSN+1 through the muxes <b>106</b>A–<b>106</b>B for instructions <b>1</b> and <b>2</b>, respectively, and the selection of one of BSN, BSN+1, or BSN+2 through the mux <b>106</b>C for instruction <b>3</b>. The initial assignment of BSNs assumes that the delay slot is unconditional. Accordingly, the initial BSN for each instruction is affected by the cumulative number of branch instructions prior to that instruction except for the instruction immediately prior to that instruction. For example, the initial BSN for instruction <b>1</b> is dependent on whether or not the last instruction from the previous fetch group is a branch, but not on whether instruction <b>0</b> is a branch instruction. If instruction <b>0</b> is a branch instruction, then instruction <b>1</b> is in the (assumed unconditional) branch delay slot, which is part of the basic block of the branch instruction and thus receives the same BSN as the branch instruction. The mux <b>106</b>D is used to select a BSN for a hypothetical instruction <b>4</b> in the fetch group. This BSN may be used for instruction <b>3</b> if instruction <b>3</b> is in a conditional branch delay slot.

0074Accordingly, the selection control for the mux <b>106</b>A is illustrated as the last_br signal from the last branch register <b>104</b>. The mux <b>106</b>A selects the BSN if the last_br signal is deasserted (indicating that the last instruction from the previous fetch group is not a branch) and selects the BSN+1 if the last_br signal is asserted (indicating that the last instruction from the previous fetch group is a branch). The selection controls for the muxes <b>106</b>B–<b>106</b>D are generated by the mux control circuit <b>100</b> (as signals sel[<b>4</b>:<b>0</b>]). Specifically, sel[<b>0</b>] is the selection control for the mux <b>106</b>B; the signals sel[<b>2</b>:<b>1</b>] are the selection controls for the mux <b>106</b>C; and the signals sel[<b>4</b>:<b>3</b>] are the selection controls for the mux <b>106</b>D. If the sel[<b>0</b>] signal is deasserted, the mux <b>106</b>B selects the BSN. If the sel[<b>0</b>] signal is asserted, the mux <b>106</b>B selects the BSN+1.

0075The muxes <b>106</b>C–<b>106</b>D each receive the BSN, the BSN+1, and the BSN+2. The muxes <b>106</b>C–<b>106</b>D may select the BSN by default (if neither of the select signals are asserted). The muxes <b>106</b>C–<b>106</b>D may select the BSN+1 if the sel[l] and sel[<b>3</b>] signals are asserted (respectively) and the sel[<b>2</b>] and sel[<b>4</b>] signals are deasserted (respectively). Finally, the muxes <b>106</b>C–<b>106</b>D may select the BSN+2 if the sel[<b>2</b>] and sel[<b>4</b>] signals are asserted, irrespective of the state of the sel[l] and sel[<b>3</b>] signals, respectively. In other words, the muxes <b>106</b>C–<b>106</b>D may be priority select muxes where sel[<b>2</b>] and sel[<b>4</b>] take priority over sel[<b>1</b>] and sel[<b>3</b>], respectively. The sel[<b>2</b>] and sel[<b>4</b>] signals are asserted if there are two branches prior to the corresponding instruction (excluding the immediately prior instruction to the corresponding instruction). The sel[<b>1</b>] and sel[<b>3</b>] signals are asserted if there is at least one branch prior to the corresponding instruction (excluding the immediately prior instruction to the corresponding instruction). Other embodiments may encode the selections of BSN, BSN+1, and BSN+2 on the select lines or may use three select lines (one for each selection), as desired.

0076The BSNs received by each of the muxes <b>106</b>A–<b>106</b>D may be based on the maximum number of branch instructions which may exist prior to the corresponding instruction. For example, in the MIPS architecture, a branch instruction may not be the instruction in the branch delay slot. Accordingly, in four instructions, at most two branch instructions may be included (where the second branch instruction is separated from the first branch instruction by the delay slot for the first branch instruction). Therefore, in the present embodiment, the BSN, BSN+1, and BSN+2 are sufficient to supply BSNs for each instruction. Embodiments which do not employ a branch delay slot may generate additional incremented BSNs for selection.

0077The logic equations for the sel[<b>5</b>:<b>0</b>] signals may be as follows (where “+” is a logical OR and “&amp;” is a logical AND):

0078<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="203pt" align="left" /><colspec colname="2" colwidth="14pt" align="center" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>sel[0] = last_br + br[0]</entry><entry>(1)</entry></row><row><entry>sel[1] = last_br + br[0] + br[1]</entry><entry>(2)</entry></row><row><entry>sel[2] = last_br &amp; br[1]</entry><entry>(3)</entry></row><row><entry>sel[3] = last_br + br[0] + br[1] + br[2]</entry><entry>(4)</entry></row><row><entry>sel[4] = (last_br &amp; br[1]) + (last_br &amp; br[2]) + (br[0] &amp; br[2])</entry><entry>(5)</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0079It is noted that the sel[<b>2</b>] and sel[<b>4</b>] signals (which indicate that there are two branches prior to the corresponding instruction when asserted) consider pairs of branches which are separated by at least one other instruction, since the at least one other instruction is the instruction in the delay slot if the first of the pair is a branch (and therefore the first of the at least one other instruction may not be a branch).

0080The muxes <b>108</b>A–<b>108</b>D receive the initial BSNs and select a final set of BSNs for the instructions in the fetch group. The muxes <b>108</b>A–<b>108</b>D account for the conditional delay slot. If a given instruction is in a conditional delay slot, the initial BSN for the next sequential instruction (which is in the next basic block and therefore is equal to the initial BSN of the given instruction plus one) is selected. For example, if instruction <b>0</b> is in a conditional delay slot, the initial BSN for instruction <b>1</b> (output from mux <b>106</b>A) is selected. If the given instruction is not in a conditional delay slot, the initial BSN assigned to the given instruction is selected. A given instruction is in the conditional delay slot if the immediately preceding branch instruction is a branch likely instruction, as indicated by an asserted last_brl or brl[<b>2</b>:<b>0</b>] signal.

0081Accordingly, the mux <b>108</b>A selects the BSN for instruction <b>0</b> (BSN[<b>0</b>]) from either the BSN (the initial BSN for instruction <b>0</b>) or the output of mux <b>106</b>A (the initial BSN for instruction <b>1</b>) responsive to the last_brl signal. Similarly, the mux <b>108</b>B selects the BSN[<b>1</b>] as either the output of the mux <b>106</b>A (the initial BSN for instruction <b>1</b>) or the output of the mux <b>106</b>B (the initial BSN for instruction <b>2</b>) responsive to the brl[<b>0</b>] signal; the mux <b>108</b>C selects the BSN[<b>2</b>] as either the output of the mux <b>106</b>B (the initial BSN for instruction <b>2</b>) or the output of the mux <b>106</b>C (the initial BSN for instruction <b>3</b>) responsive to the brl[<b>1</b>] signal; and the mux <b>108</b>D selects the BSN[<b>3</b>] either the output of the mux <b>106</b>C (the initial BSN for instruction <b>3</b>) or the output of the mux <b>106</b>D (the initial BSN for hypothetical instruction <b>4</b>) responsive to the brl[<b>2</b>] signal.

0082The next BSN mux <b>110</b> may be used to select the next BSN (to become the current BSN for the next fetch group). The next BSN may be similar to selecting the initial BSN for the hypothetical instruction <b>4</b> in the fetch group. However, the branch predictions for branches in the fetch group may also affect the generation of the next BSN. The mux control circuit <b>100</b> provides selection control signals sel_next[<b>1</b>:<b>0</b>] to select the next BSN. The next BSN mux <b>110</b> may be a priority select mux similar to the muxes <b>106</b>C–<b>106</b>D. In other words, the next BSN mux <b>110</b> may select the BSN by default, or may select the BSN+1 if the sel_next[<b>0</b>] signal is asserted and the sel_next[<b>1</b>] signal is deasserted, or may select the BSN+2 if the sel_next[<b>1</b>] signal is asserted irrespective of the state of the sel_next[<b>0</b>] signal. As mentioned above, other embodiments may encode the selections on the sel_next signals or use three signals for the three selections.

0083When a branch is predicted taken, subsequent instructions within the fetch group are discarded and the target of the branch is fetched. BSNs may be assigned to instructions with the fetch group subsequent to a predicted taken branch without considering the branch prediction, since the instructions are to be discarded anyway. However, when generating the next BSN, the branch prediction may be taken into account. In one embodiment, the branch prediction for instruction <b>0</b> is used (Pt[<b>0</b>]). The Pt[<b>0</b>] signal may be asserted if instruction <b>0</b> is a branch and is predicted taken, and may be deasserted otherwise. If instruction <b>1</b> is a predicted taken branch, instruction <b>2</b> is in the delay slot and thus is not discarded. Instruction <b>3</b> does not affect the generation of the next BSN. Accordingly, the prediction for instruction <b>1</b> is not used. For similar reasons, the prediction for instruction <b>2</b> is not used.

0084The branch prediction for instruction <b>0</b> is used to qualify the br[<b>2</b>] signal in the equations for the sel_next[<b>1</b>:<b>0</b>] signals. The br[<b>1</b>] signal is not qualified with the branch prediction for instruction <b>0</b> since, if instruction <b>0</b> is a branch instruction, instruction <b>1</b> is in the branch delay slot and is not a branch instruction (br[<b>1</b>] is deasserted). The equations for the sel_next[<b>1</b>:<b>0</b>] signals may thus be (where “+” is a logical OR, “&amp;” is a logical AND, and “!” is a logical inversion):

0085<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="196pt" align="left" /><colspec colname="2" colwidth="21pt" align="center" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>sel_next[0] = last_br + br[0] + br[1] + (br[2] &amp; !Pt[0])</entry><entry>(6)</entry></row><row><entry>sel_next[1] = (last_br &amp; br[1]) + (last_br &amp; br[2] &amp; !Pt[0]) +</entry><entry>(7)</entry></row><row><entry>(br[1] &amp; br[2] &amp; !Pt[0])</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0086It is noted that, in one embodiment, the fetch group is aligned to a 4 instruction boundary. In such an embodiment, if the fetch group is the target of a branch instruction, one or more of the initial instructions in the fetch group may not be valid (e.g. the target of the branch may be in the middle of the fetch group). For such an embodiment, the mux control circuit <b>100</b> may qualify the generation of the br[<b>3</b>:<b>0</b>] and brl[<b>3</b>:<b>0</b>] signals with the instructions being valid to ensure the br[<b>3</b>:<b>0</b>] and brl[<b>3</b>:<b>0</b>] signals are deasserted for invalid instructions.

0087It is noted that, while the above description refers to assigning tags to a fetch group, other embodiments may assign tags in parallel to any group of instructions, as desired. For example, the group may be fetched at different times, and may be concurrently decoded or concurrently dispatched. Generally, any group of instructions which is in the pipeline stage that the BSN control circuit <b>40</b> operates may be processed as described above.

0088Turning now to <figref idref="DRAWINGS">FIG. 10</figref>, a block diagram of one embodiment of the mux control circuit <b>100</b> is shown. Other embodiments are possible and contemplated. In the embodiment of <figref idref="DRAWINGS">FIG. 10</figref>, the mux control circuit <b>100</b> includes logic gates <b>120</b>, <b>122</b>, <b>124</b>, <b>126</b>, <b>128</b>, <b>130</b>, <b>132</b>, <b>134</b>, <b>136</b>, <b>138</b>, <b>140</b>, <b>142</b>, <b>144</b>, <b>146</b>, and <b>148</b> and a decoder <b>150</b>. The decoder <b>150</b> is coupled to receive the instructions and to decode the instructions to generate the brl[<b>3</b>:<b>0</b>] and br[<b>3</b>:<b>0</b>] signals. The brl[<b>3</b>:<b>0</b>] and br[<b>3</b>] signals are provided to other portions of the BSN control circuit <b>40</b> as illustrated in <figref idref="DRAWINGS">FIG. 9</figref>. The br[<b>2</b>:<b>0</b>] signals are provided to the logic gates <b>120</b>–<b>146</b> as illustrated in <figref idref="DRAWINGS">FIG. 10</figref>. Furthermore, the last_brl signal is provided to the logic gates <b>120</b>–<b>146</b> as illustrated in <figref idref="DRAWINGS">FIG. 10</figref>. The Pt[<b>0</b>] signal is provided to the inverter <b>148</b>.

0089Generally, the logic gates <b>120</b>–<b>148</b> may be an example implement of the equations 1–7 above. Specifically: (i) logic gate <b>120</b> may implement equation 1; (ii) logic gate <b>122</b> may implement equation 2; (iii) logic gate <b>124</b> may implement equation 3; (iv) logic gate <b>126</b> may implement equation 4; (v) logic gates <b>128</b>, <b>130</b>, <b>132</b>, and <b>134</b> may implement equation 5; (vi) logic gates <b>136</b>, <b>138</b>, and <b>148</b> may implement equation 6; and (vii) logic gates <b>140</b>, <b>142</b>, <b>144</b>, <b>146</b>, and <b>148</b> may implement equation 7.

0090It is noted that the logic gates <b>120</b>–<b>148</b> are merely an example, and any other logic circuit may be used. Specifically, Boolean equivalents of the circuits shown in <figref idref="DRAWINGS">FIG. 10</figref> may be used. The illustrated circuitry may receive inputs and provide outputs which are asserted high and deasserted low. The circuitry may be modified to receive inputs and/or provide outputs which are asserted low and deasserted high, as desired.

0091As mentioned above, other embodiments of the BSN control circuit <b>40</b> (and the mux control circuit <b>100</b>) may receive decoded signals instead of the instructions directly. In such embodiments, the decoder <b>150</b> may be eliminated and the decoded signals may be used. For example, the decode logic may provide the brl[<b>3</b>:<b>0</b>] and br[<b>3</b>:<b>0</b>] signals.

0092While the embodiment illustrated in <figref idref="DRAWINGS">FIGS. 9 and 10</figref> handles fetch groups of four instructions, other embodiments may handle less than four instructions or more than four instructions. Each additional instruction above four may consider prior branches (and branch-likely instructions) in a manner similar to the above illustrated embodiment. Furthermore, additional BSNs may be generated by the adder circuit <b>102</b> and selected by the muxes corresponding to the additional instructions. Still further, additional branch predictions may be used to qualify generation of the next BSN if more than four instructions are handled.

0093It is noted that embodiments which do not have a conditional delay slot may eliminate the muxes <b>108</b>A–<b>108</b>D and may use the outputs of muxes <b>106</b>A–<b>106</b>C (plus the default BSN assignment to instruction <b>0</b>) as the BSNs for the instructions. Furthermore, embodiments which do not have a delay slot may not exclude the instruction immediately preceding the given instruction when counting branches to select a BSN, and may not consider the last instruction of the previous fetch group.

0094It is noted that, while the term “branch sequence number” has been used above, generally the BSN is used as a tag in the above disclosure. As used herein, a tag is a value generated by hardware to track an instruction or group of instructions.

0095Turning next to <figref idref="DRAWINGS">FIG. 11</figref>, a block diagram of a carrier medium <b>300</b> including one or more data structures representative of the processor <b>10</b> is shown. Generally speaking, a carrier medium may include storage media such as magnetic or optical media, e.g., disk or CD-ROM, volatile or non-volatile memory media such as RAM (e.g. SDRAM, RDRAM, SRAM, etc.), ROM, etc., as well as transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as a network and/or a wireless link.

0096Generally, the data structure(s) of the processor <b>10</b> carried on carrier medium <b>300</b> may be read by a program and used, directly or indirectly, to fabricate the hardware comprising the processor <b>10</b>. For example, the data structure(s) may include one or more behavioral-level descriptions or register-transfer level (RTL) descriptions of the hardware functionality in a high level design language (HDL) such as Verilog or VHDL. The description(s) may be read by a synthesis tool which may synthesize the description(s) to produce one or more netlists comprising lists of gates from a synthesis library. The netlist(s) each comprise a set of gates which also represent the functionality of the hardware comprising the processor <b>10</b>. The netlist(s) may then be placed and routed to produce one or more data sets describing geometric shapes to be applied to masks. The masks may then be used in various semiconductor fabrication steps to produce a semiconductor circuit or circuits corresponding to the processor <b>10</b>. Alternatively, the data structure(s) on carrier medium <b>300</b> may be the netlist(s) (with or without the synthesis library) or the data set(s), as desired.

0097While carrier medium <b>300</b> carries a representation of the processor <b>10</b>, other embodiments may carry a representation of any portion of processor <b>10</b>, as desired, including any set of BSN control circuits or portions thereof, instruction queues, issue logic, branch state tables, execution units, fetch/issue/decode units, execution units, branch execution circuits, pipelines, etc.

0098Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.