Method and apparatus for high performance branching in pipelined microsystems

A processing apparatus comprising:

• an instruction pipeline comprising a plurality of stages;
• a branch cache module to which d fetch packets are stored from d of said pipeline stages;
• and
• a branch cache control unit that causes said branch cache module to store said fetch packets from said d of said pipeline stages in response to execution of a cacheable branch instruction which triggers a cache miss, and when a cache hit occurs, causes said branch cache module to restore data relating to said d of said fetch packets to said pipeline, thereby avoiding pipeline stalls;
• whereby the number d is related to the number of execute packets stored in one or more cached fetch packets.

A processing apparatus comprising:

• an instruction pipeline comprising a plurality of stages, each stage initially containing first data;
• branch cache module that stores at least a portion of said first data from one or more of said pipeline stages;
• and
• a branch cache control unit that causes said branch cache module to store said at least portion of said first data from one or more of said pipeline stages in response to execution of a cacheable branch instruction which triggers a cache miss, and causes said branch cache module to restore second data to one or more of said pipeline stages in response to a cache hit, thereby avoiding pipeline stalls when a cache hit occurs;
• whereby said branch cache control unit receives an early indication from said instruction pipeline prior to the execution of said branch instruction.

A processing apparatus comprising:

• a processing pipeline comprising a plurality of pipeline stages to include at least a prefetch stage, a decode stage, and an execute stage;
• a branch cache clntrol unit, said branch cache control unit receiving an early indication of the presence of a branch instruction in said pipeline, said early indication being received prior to said branch instruction propagating to said execute stage;
• a dispatch unit;
• and
• a shadow dispatch unit;
• whereby said shadow dispatch unit is operative to dispatch at least one branch target instruction.

In a processor comprising a computational pipeline having a plurality of pipeline stages and a branch cache, a method of controlling said branch cache, comprising:

• providing an indication to a branch cache controller when a branch instruction is detected in a selected one of said pipeline stages;
• evaluating the branch target address of said branch instruction;
• determining whether at least one instruction residing at said branch target address has already been fetched into said computational pipeline;
• and
• selecting a number of fetch packets (d) to be transferred to or from the branch cache based at least partially on the result of the act of determining.

In a pipelined processor, a method for reducing pipeline stalls caused by branching, comprising:

• prefetching instructions into a first stage of said pipeline;
• propagating instructions into one or more subsequent stages of said pipeline;
• concurrently with processing at a specified stage in said pipeline, analyzing one or more instruction op-codes to determine whether a branch instruction is present, and if so, its branch instruction type;
• if at least one non-delayed branch instruction is detected, performing branch cache processing;
• and
• if no branch instruction is detected or if all detected branch instructions correspond to delayed branch instructions, not performing branch cache processing.

A computer processor comprising:

• an instruction pipeline comprising a plurality of stages, each stage containing pipeline data;
• a branch cache comprising a plurality of cache lines, each cache line comprising a branch tag field and cache data field;
• and
• a branch cache controller configured to:
• detect a cacheable branch instruction in one of said pipeline stages;
• receive a current branch tag from one of said pipeline stages;
• receive conditional information indicative of whether the branch shall be taken;
• attempt to match said current branch tag to a stored branch tag for a first cache line;
• if said branch is to be taken, signal a cache miss when said attempt to match fails;
• if said branch is to be taken, signal a cache hit when said attempt to match succeeds;
• in response to said cache miss, store said current branch tag, in said branch tag field of a designated cache line and store in said cache data field of said designated cache line data from one or more of said pipeline stages which stall in response to said cacheable branch instruction after said one or more pipeline stages have been filled with data starting at a branch target address;
• and
• in response to said cache hit, load said one or more pipeline stages from said cache data field to avoid a pipeline stall from said cacheable branch instruction.

In a pipelined microsystem such as a microprocessor, DSP, media processor, or microcontroller, a method to load branch instruction information into a branch cache so as to allow the branch instruction to execute subsequently with a reduced or eliminated time penalty by minimizing the amount of information to be cached, the method comprising:

• monitoring the instruction stream in a dispatch unit in a pipeline stage to detect whether a branch instruction of a selected type is present;
• when said branch instruction is detected:
• signaling to a branch cache control unit that the branch instruction is present;
• making available at least a function of branch target address to said branch cache control unit;
• comparing said function of said address of said branch instruction to a set of cache tags containing branch instruction address related information;
• when said branch instruction does not match any tag, writing a line into said branch cache so that when said branch instruction is next encountered, the tag will match and the branch target stream can proceed without delay;
• and
• when program execution makes a branch target fetch packet available to be cached, thereby allowing the target instruction stream to execute to a target prefetch buffer, performing:
• loading data from said target prefetch buffer into a position in the branch cache associated with said branch instruction;
• setting a counter to a prespecified number, d, corresponding to the number of fetch packets that need to be cached to prevent a pipeline stall in a subsequent branch cache hit associated with said branch target address;
• decrementing the counter on each subsequent cycle;
• loading subsequent fetch packets from the target instruction stream into the branch cache;
• and
• exiting the branch cache fill operation when the counter has decremented to a specified number such that the branch cache contains the appropriate number of target prefetch packets that are fetched in the first d time slots when the target instruction stream is executed.

In a pipelined microsystem such as a microprocessor, DSP, media processor, or microcontroller, a method for servicing branch cache hits so as to reduce or eliminate cycle loss due to branching, said method comprising:

• reading the target prefetch buffer out of the branch cache;
• supplying the contents of the target prefetch buffer to a multiplexer which routes the contents of the target prefetch buffer back to a dispatch unit;
• dispatching the contents of the target prefetch buffer from said dispatch unit to said pipeline in units of execute packets;
• prefetching instructions by said pipeline at full speed, irrespective of whether it takes multiple cycles to dispatch a fetch packet, until the early pipeline stages catch up to the later pipeline stages, whereby the target instruction stream proceeds at nearly full speed, and only a minimum number of fetch packets needed to support full speed execution are fetched from the branch cache.

A method to fill an instruction pipeline after a branch instruction is detected which selects a target instruction stream, the method comprising:

• reading the contents of a prefetch buffer out of a branch cache line associated with the instruction which caused the branch cache hit, said contents comprising at least one fetch packet;
• sending the contents of the prefetch buffer to a shadow dispatch unit;
• routing the output of the shadow dispatch unit to one or more decoder stages of an execution pipeline in units of execute packets;
• and
• subsequently supplying one or more fetch packets from the branch cache to allow the target instruction stream to proceed without adding extra delay cycles.

A processing apparatus comprising:

• an instruction pipeline comprising a plurality of pipeline stages to include at least a prefetch stage, a dispatch stage, a decode stage and an execute stage;
• a branch cache control unit responsive to an early indication signal and at least a function of a branch target address coupled from a pipeline stage that precedes said execute stage;
• a branch cache that stores one or more branch target fetch packets in support of said branch target address;
• a coupling from said execute stage to said branch cache control unit, said coupling being capable of carrying a signal indicative of whether a branch condition evaluated to the affirmative or the negative;
• whereby said branch cache control unit causes at least one branch target fetch packet to be preemptively read from said branch cache prior to receiving said signal from said execute stage.

A processing apparatus comprising:

• instruction pipeline means comprising a plurality of stages, each stage initially containing first data;
• means for storing at least a portion of said first data from one or more of said pipeline means stages;
• and
• control means that causes said means for storing to store said at least portion of said first data from one or more of said stages of said pipeline means in response to execution of a storable branch instruction which triggers a miss of said means for storing, and causes said control means to restore second data to one or more of said stages in response to a hit, thereby avoiding pipeline stalls when a hit of said means for storing occurs;
• whereby said control means receives an early indication from said instruction pipeline means prior to the execution of said branch instruction.

In a processor comprising a computational pipeline having a plurality of pipeline stages and a branch cache, a method of controlling said branch cache, comprising the steps of:

• monitoring a selected one of said pipeline stages for detecting when a branch instruction is present and for providing an indication to a branch cache controller when said branch instruction is detected;
• evaluating the branch target address of said branch instruction for determining whether at least one instruction residing at said branch target address has already been fetched into said computational pipeline;
• and
• selecting a number of fetch packets (d) to be transferred to or from the branch cache based at least partially on the result of the act of determining.

A computerized system, comprising:

• means for processing data, said means for processing comprising:
• instruction pipeline means comprising a plurality of stages;
• means for caching first data from one or more of said pipeline stages and providing second data to one or more of said pipeline stages;
• and
• means for controlling said means for caching that causes said means for caching to store said first data from one or more of said pipeline stages in response to execution of a cacheable branch instruction which triggers a miss of said means for caching, and causes said means for caching to provide second data to one or more of said pipeline stages in response to a hit of said means for caching, thereby avoiding pipeline stalls when such a hit occurs;
• whereby said means for controlling receives an early indication from said instruction pipeline means prior to the execution of said branch instruction.