Apparatus and method in a digital computer for allowing improved program branching with branch anticipation reduction of the number of branches, and reduction of branch delays

Claim 1

Apparatus in a digital computer for altering the sequence of instructions to be processed from a first instruction sequence to a second instruction sequence comprising, in combination: storaGe means for temporarily storing instructions transmitted in sequence from a storage system, said instructions including at least one branch instruction containing an operation code, and condition and address parameters, said at least one branch instruction indicating that the instruction sequence is to be altered from said first sequence to said second sequence upon the determination of a machine condition; means, coupled to said storage means and responsive to said address parameters, for determining a storage system address containing the first instruction in said second sequence; means, coupled to said storage means and responsive to said operation code and to said condition parameters, for detecting the occurrence of said machine condition; means, coupled to said storage means, for detecting an exit instruction subsequent in said sequence to said at least one branch instruction and separated therefrom by other instructions, said exit instruction indicating the point in said first sequence at which processing of said second sequence of instructions is to begin; means, responsive to said detection of the occurrence of said machine condition, for ordering instructions to be transmitted from said storage system to said storage means, beginning at said address containing said first instruction in said second sequence while said other instructions separating said at least one branch instruction from said exit instruction are being processed, such that said first instruction is processed at said point indicated by said exit instruction.

Claim 10

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence, including the steps of: decoding a branch instruction located prior to and separated from a marker instruction in said first instruction sequence, said branch instruction indicating a branch condition and said marker instruction indicating the exit point from said first sequence; resolving said branch condition as successful or unsuccessful; prefetching, in response to the successful resolution of said branch condition, at least the first instruction in said second sequence while continuing to process instructions in said first sequence; processing said marker instruction; and processing, as the next instruction processed after said marker instruction, the first instruction in said second sequence.

Claim 11

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence, including the steps of: decoding a branch instruction located prior to and separated from a marker instruction in said first instruction sequence, said branch instruction indicating a branch condition and said marker instruction indicating the exit point from said first sequence; resolving said branch condition as successful or unsuccessful; prefetching, in response to the successful resolution of said branch condition, at least the first instruction in said second sequence while continuing to process instructions in said first sequence; processing said marker instruction; and processing, as the next instruction processed after said marker instruction, the first instruction in said second sequence.

Claim 14

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: detecting a branch instruction indicating a machine condition after the occurrence of which said branching is to occur; obtaining a storage address indicative of the first instruction in said second sequence; detecting the occurrence of said indicated machine condition; prefetching said second sequence of instructions from a storage system beginning at said storage address indicative of the first instruction in said sequence; detecting, after said condition occurrence detection, a marker instruction in said first sequence which indicates that point at which the first instruction of said second sequence is to be processed; processing instructions in said first sequence to the point indicated by said marker instruction concurrently with said prefetching; and processing, beginning at said indicated point, said second sequence of instructions beginning with the first instruction of said second sequence.

Claim 15

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: detecting a branch instruction indicating a machine condition after the occurrence of which said branching is to occur; obtaining a storage address indicative of the first instruction in said second sequence; detecting the occurrence of said indicated machine condition; prefetching said second sequence of instructions from a storage system beginning at said storage address indicative of the first instruction in said sequence; detecting, after said condition occurrence detection, a marker instruction in said first sequence which indicates that point at which the first instruction of said second sequence is to be processed; processing instructions in said first sequence to the point indicated by said marker instruction concurrently with said prefetching; and processing, beginning at said indicated point, said second sequence of instructions beginning with the first instruction of said second sequence.

Claim 16

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: detecting a branch instruction previous to a marker instruction, said branch instruction indicating that a departure from said first instruction sequence to said second instruction sequence is to be made after the occurrence of a machine condition and said marker instruction indicating the point in said first sequence at which said departure is to be made; obtaining the storage address of the first instruction in said second sequence; detecting the occurrence of said machine condition; detecting said marker instruction; prefetching, in response to the detection of said machine condition and to the detection of said marker instruction, instructions from said second sequence beginning with said first instruction thereof; continuing the processing of instructions in said first sequence concurrently with said instruction prefetching; and processing said instructions fetched from said second sequence after the processing of said marker instruction of said first sequence.

Claim 17

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: detecting a branch instruction previous to a marker instruction, said branch instruction indicating that a departure from said first instruction sequence to said second instruction sequence is to be made after the occurrence of a machine condition and said marker instruction indicating the point in said first sequence at which said departure is to be made; obtaining the storage address of the first instruction in said second sequence; detecting the occurrence of said machine condition; detecting said marker instruction; prefetching, in response to the detection of said machine condition and to the detection of said marker instruction, instructions from said second sequence beginning with said first instruction thereof; continuing the processing of instructions in said first sequence concurrently with said instruction prefetching; and processing said instructions fetched from said second sequence after the processing of said marker instruction of said first sequence.

Claim 18

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: prefetching instructions from said first instruction sequence in advance of the time they are to be processed; decoding from said prefetched instructions of said first sequence a branch instruction indicating a branch will subsequently be taken to said second instruction sequence if certain indicated machine conditions are detected; obtaining the address of the beginning instruction in said second sequence; testing a plurality of possible machine conditions to detect the occurrence of said indicated machine conditions; detecting a marker instruction subsequent to said branch instruction in said first sequence, indicating the point of departure from said first sequence to said second sequence; prefetching instructions from sequential addresses beginning with said obtained address while continuing to process instructions from said first sequence; and processing instructions beginning with said prefetched instructions from said second instruction sequence after the detection of said marker instruction.

Claim 19

The method, in a digital computer, of branching from a first instruction sequence to a second instruction sequence comprising the steps of: prefetching instructions from said first instruction sequence in advance of the time they are to be processed; decoding from said prefetched instructions of said first sequence a branch instruction indicating a branch will subsequently be taken to said second instruction sequence if certain indicated machine conditions are detected; obtaining the address of the beginning instruction in said second sequence; testing a plurality of possible machine conditions to detect the occurrence of said indicated machine conditions; detecting a marker instruction subsequent to said branch instruction in said first sequence, indicating the point of departure from said first sequence to said second sequence; prefetching instructions from sequential addresses beginning with said obtained address while continuing to process instructions from said first sequence; and processing instructions beginning with said prefetched instructions from said second instruction sequence after the detection of said marker instruction.