Method an apparatus for store-into-instruction-stream detection and maintaining branch prediction cache consistency

Claim 1

An apparatus for preventing malfunction of pipeline processing associated with a program that modifies an instruction queued for execution, said apparatus comprising: an instruction pipeline which performs overlapped processing of a plurality of executing instructions and aborts processing of selected ones Of said executing instructions; a prefetch buffer, when active said prefetch buffer holding a plurality of instructions queued for possible execution by said pipeline; an address storage holding a first address value that identifies a block of addressee including said plurality of instructions held in said prefetch buffer; a comparator having e first input coupled to receive said first address value from said address storage and a second input coupled to receive a second address value from said pipeline; and a control circuit coupled to said comparator and to said pipeline, said control circuit aborting further processing of said selected ones of said executing instructions when said program includes a store instruction and said pipeline generates said second address for said store instruction and said comparator detects that said second address value corresponds to said first address value, thereby restarting said pipeline when said program modifies an instruction in a block of instructions that includes said queued instructions.

Claim 2

An apparatus for preventing malfunction of pipeline processing associated with a program that modifies an instruction queued for execution, said apparatus comprising: an instruction pipeline which performs overlapped processing of a plurality of executing instructions and aborts processing of selected ones Of said executing instructions; a prefetch buffer, when active said prefetch buffer holding a plurality of instructions queued for possible execution by said pipeline; an address storage holding a first address value that identifies a block of addressee including said plurality of instructions held in said prefetch buffer; a comparator having e first input coupled to receive said first address value from said address storage and a second input coupled to receive a second address value from said pipeline; and a control circuit coupled to said comparator and to said pipeline, said control circuit aborting further processing of said selected ones of said executing instructions when said program includes a store instruction and said pipeline generates said second address for said store instruction and said comparator detects that said second address value corresponds to said first address value, thereby restarting said pipeline when said program modifies an instruction in a block of instructions that includes said queued instructions.

Claim 4

An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including, for each entry, an instruction address tag, instruction data, and an instruction cache entry validity bit for indicating whether an entry is valid; means for detecting when a store signal on said system bus matches an instruction address tag for an entry in said instruction cache; means for setting said instruction cache entry validity bit for an entry in said instruction cache to invalid when said means for detecting detects a store signal on said system bus which matches the instruction address tag for that entry; a randomly addressable branch prediction cache including, for each entry, a branch instruction address tag, a branch target address, branch target instruction data and a branch prediction cache entry validity bit; means for comparing an instruction address tag of an instruction cache entry to said branch prediction, cache branch target addresses; control means for writing target instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing target instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting said branch prediction cache entry validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with said instruction cache entry validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction cache.

Claim 5

An apparatus comprising: a system bus; an instruction cache, coupled to said system bus, including, for each entry, an instruction address tag, instruction data, and an instruction cache entry validity bit for indicating whether an entry is valid; means for detecting when a store signal on said system bus matches an instruction address tag for an entry in said instruction cache; means for setting said instruction cache entry validity bit for an entry in said instruction cache to invalid when said means for detecting detects a store signal on said system bus which matches the instruction address tag for that entry; a randomly addressable branch prediction cache including, for each entry, a branch instruction address tag, a branch target address, branch target instruction data and a branch prediction cache entry validity bit; means for comparing an instruction address tag of an instruction cache entry to said branch prediction, cache branch target addresses; control means for writing target instructions into said branch prediction cache only if said instructions are also written into said instruction cache and for removing target instructions from said branch prediction cache whenever said instructions are removed from said instruction cache; and means for setting said branch prediction cache entry validity bit for a branch prediction cache entry to invalid when the branch target address matches the address of an instruction cache entry with said instruction cache entry validity bit in an invalid state; such that a store-into-instruction-stream will be detected by said instruction cache and will result in the invalidation of any corresponding entries in both said instruction cache and said branch prediction cache.

Claim 9

An apparatus for preventing malfunction of pipeline processing associated with a program that modifies an instruction queued for execution, said apparatus comprising: an instruction pipeline which performs overlapped processing of a plurality of executing instructions and aborts processing of selected ones of said executing instructions; a profetch buffer, when active said profetch buffer holding a plurality of instructions queued for possible execution by said pipeline; an address storage holding a first address value that identifies a block of addresses including said plurality of instructions held in said profetch buffer; a comparator having a first input coupled to receive said first address value from said address storage and a second input coupled to receive a second address value from said pipeline; and a control circuit coupled to said comparator and to said pipeline said control circuit aborting further processing of said selected ones of said executing instructions when said program includes a store instruction and said pipeline generates said second address for said store instruction and said comparator detects that said second address value corresponds to said first address value, thereby restarting said pipeline when said program modifies an instruction in a block of instructions that includes said queued instructions; wherein said block of instructions consists of 32 bytes and said address values each consist of at least 27 bit.

Claim 10

An apparatus for preventing malfunction of pipeline processing associated with a program that modifies an instruction queued for execution, said apparatus comprising: an instruction pipeline which performs overlapped processing of a plurality of executing instructions and aborts processing of selected ones of said executing instructions; a profetch buffer, when active said profetch buffer holding a plurality of instructions queued for possible execution by said pipeline; an address storage holding a first address value that identifies a block of addresses including said plurality of instructions held in said profetch buffer; a comparator having a first input coupled to receive said first address value from said address storage and a second input coupled to receive a second address value from said pipeline; and a control circuit coupled to said comparator and to said pipeline said control circuit aborting further processing of said selected ones of said executing instructions when said program includes a store instruction and said pipeline generates said second address for said store instruction and said comparator detects that said second address value corresponds to said first address value, thereby restarting said pipeline when said program modifies an instruction in a block of instructions that includes said queued instructions; wherein said block of instructions consists of 32 bytes and said address values each consist of at least 27 bit.

Claim 13

An apparatus comprising: an instruction pipeline for overlapping execution of a plurality of sequential instructions; a pre-fetch queue for holding a plurality of instructions to be executed; means for detecting a store to an address for a given instruction in said pre-fetch queue and generating a store-into-instruction-stream signal; control means for flushing and restarting said instruction pipeline when said store-into-instruction-stream signal is detected from at least said given instruction onward; an instruction cache holding a plurality of instruction entries, each instruction entry having an instruction address tag, instruction data and an entry validity bit for indicating whether a corresponding instruction is valid; means for setting said entry validity bit to invalid when a store is detected to an address matching the instruction address tag; and a branch prediction cache holding a plurality of branch instruction addresses, wherein said branch prediction cache includes a branch validity bit for each of said branch instruction addresses, and further comprising means for setting said branch validity bit to invalid when a store is detected to an address matching the branch instruction address.

Claim 14

An apparatus comprising: an instruction pipeline for overlapping execution of a plurality of sequential instructions; a pre-fetch queue for holding a plurality of instructions to be executed; means for detecting a store to an address for a given instruction in said pre-fetch queue and generating a store-into-instruction-stream signal; control means for flushing and restarting said instruction pipeline when said store-into-instruction-stream signal is detected from at least said given instruction onward; an instruction cache holding a plurality of instruction entries, each instruction entry having an instruction address tag, instruction data and an entry validity bit for indicating whether a corresponding instruction is valid; means for setting said entry validity bit to invalid when a store is detected to an address matching the instruction address tag; and a branch prediction cache holding a plurality of branch instruction addresses, wherein said branch prediction cache includes a branch validity bit for each of said branch instruction addresses, and further comprising means for setting said branch validity bit to invalid when a store is detected to an address matching the branch instruction address.