Method and apparatus for preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a bufered store

Claim 2

In a computer system comprising a memory unit for storing instructions and data, a bus controller coupled to said memory unit for accessing said instructions and data, an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions, and a cache subsystem coupled to said bus controller and said execution unit for caching said data, wherein said instructions are fetched, issued, and executed in a manner with said instruction fetching and issuing potentially being speculative, an apparatus for buffering store instructions, and preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a buffered store instruction, said apparatus comprising: a) buffer means for buffering a plurality of store instructions including partial address bits of destination addresses of the buffered store instructions; b) address input means coupled to said instruction fetching and issuing unit for receiving a first plurality of partial address bits of a source address of an instruction being fetched, and outputting a second plurality of partial address bits and the first plurality of partial address bits of said source address, the second plurality of partial address bits being computed based on the first plurality of partial address bits; c) matching means coupled to said buffer means and said address input means for receiving said first and second plurality of partial address bits of said source address, concurrently matching said first and second plurality of partial address bits of said source address against said stored partial address bits of said destination addresses of said buffered store instructions, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first or second plurality of partial address bits of said source address; d) stalling means coupled to said matching means and said bus controller for generating a stall signal in response to receiving at least one match signal, to stall said bus controller, thereby preventing said instruction from being incorrectly fetched.

Claim 3

The apparatus as set forth in claim 1, wherein, each of said buffered store instructions potentially stores data into destinations spanning two cache lines of said cache subsystem, each cache line having a fixed cache line size; said address input means comprises subtraction means for computing said second plurality of partial address bits of said source address by subtracting a constant from said first plurality of partial address bits of said source address, said constant being predetermined based on said fixed cache line size.

Claim 4

The apparatus as set forth in claim 2, wherein, each of said source and destination addresses has address bits (n1:0), where n1 is an integer and greater than 0; said buffer means stores only address bits (n2:n3) of the destination address of the store destination of each buffered store instruction, where n2 is an integer and not larger than n1, and n3 is an integer and smaller than n2 but not smaller than 0; said subtraction means receives first address bits (n4:n5) of said source address of said instruction being fetched, and generates second address bits (n4:n5) of said source address by subtracting said predetermined constant from said first address bits (n4:n5), where n4 is an integer not larger than n2, and n5 is an integer smaller than n4 but not smaller than n3; said matching means receives said first and second address bits (n4:n5) of said source address, and concurrently matches said first address bits (n4:n5) and said second address bits (n4:n5) of said source address against the address bits (n4:n5) of the destination addresses of the buffered store instructions.

Claim 5

The apparatus as set forth in claim 6, wherein, address bits (n1:n6) of each of said source and destination addresses denote a memory page, and address bits (n7:0) denotes an offset into the memory page, where n6 and n7 are integers, and n1>n6>n7>0; n2 is less than n1 but greater than n6; n3 equals 0; n4 equals, n2; and n5 is less than n7 but greater than 0.

Claim 6

The apparatus as set forth in claim 4, wherein, said buffer means comprises a plurality of buffer slots for storing said buffered store instructions; and said matching means comprises a plurality of matching circuits correspondingly coupled to said buffer slots, each of said matching circuit comprising: c.1) a first comparator for receiving address bits (n4:n6) of said first address bits (n4:n5) of said source address and partial address bits (n4:n6) of the destination address of the store instruction buffered in the corresponding buffer slot as first inputs, comparing said first inputs, and outputting a first partial match signal if said first inputs match each other; c.2) a second comparator for receiving address bits (n7:n5) of said first address bits (n4:n5) of said source address and partial address bits (n7:n5) of the destination address of the store instruction buffered in the corresponding buffer slot as second inputs, comparing said second inputs, and outputting a second partial match signal if said second inputs match each other; c.3) a first AND gate coupled to said first and second comparators for receiving said first and second partial match signals, and outputting the logical AND of said first and second partial match signals as a first preliminary match signal; c.4) a third comparator for receiving address bits (n4:n6) of said second address bits (n4:n5) of said source address and partial address bits (n4:n6) of the destination address of the store instruction buffered in the corresponding buffer slot as third inputs, comparing said third inputs, and outputting a third partial match signal if said third inputs match each other; c.5) a fourth comparator for receiving address bits (n7:n5) of said second address bits (n4:n5) of said source address and partial address bits (n7:n5) of the destination address of the store instruction buffered in the corresponding buffer slot as fourth inputs, comparing said fourth inputs, and outputting a fourth partial match signal if said fourth inputs match each other; c.6) a second AND gate coupled to said third and fourth comparators for receiving said third and fourth partial match signals, and a split bit indicating whether the destination of the store instruction buffered in the corresponding buffer slot spans two cache lines, and outputting the logical AND of said third and fourth partial match signals and said split bit as a second preliminary match signal; c.7) an OR gate coupled to said first and second AND gates for receiving said first and second preliminary match signals, and outputting the logical OR of said first and second preliminary match signals as a combined preliminary match signal; c.8) a third AND gate coupled to said OR gate for receiving said combined preliminary match signal and a validity bit indicating whether the destination address of the store instruction buffered in the corresponding buffer slot is valid or not, and outputting the logical AND of said combined preliminary match signal and said validity bit as a qualified match signal; and c.9) a fourth AND gate coupled to said third AND gate for receiving said qualified match signal and a clock signal, and output the logical AND of said qualified match signal and said clock signal as one of said match signals.

Claim 7

The apparatus as set forth in claim 1, wherein, said stalling means comprises: d.1) a pre-charged bit line coupled to said matching means for generating an active low signal in response to receiving at least one match signal; d.2) an inverter coupled to said pre-charged bit line for generating an active high signal in response to said active low signal, and d.3) an AND gate coupled to said inverter and said bus controller for receiving said active high signal and a validity signal indicating whether said instruction fetch is valid or not, and generating the logical AND of said active high and validity signals as a stall signal.

Claim 8

The apparatus as set forth in claim 1, wherein, said execution unit potentially executes said issued instructions out-of-order but retires execution results in order; and said buffer means, said address input means, said matching means and said stalling means are disposed in a memory order buffer of a data cache controller of said cache subsystem.

Claim 9

In a computer system comprising a memory unit for storing instructions and data, a bus controller coupled to said memory unit for accessing said instructions and data, an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions, and a cache subsystem coupled to said bus controller and said execution unit for caching said data, wherein said instructions are fetched, issued, and executed in a manner with said instruction fetching and issuing potentially being speculative, a method for buffering store instructions, and preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a buffered store instruction, said method comprising the steps of: a) storing partial address bits of destination addresses of store destinations of a plurality of buffered store instructions; b) receiving a first plurality of partial address bits of a source address of an instruction being fetched, computing a second plurality of partial address bits of the source address based on the first plurality of partial address bits of the source address, and outputting the first and second plurality of partial address bits of said source address; c) concurrently matching said first and second plurality of partial address bits of said source address against the corresponding partial address bits of said destination addresses, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first or second plurality of partial address bits of said source address; and d) generating a stall signal in response to receiving at least one match signal, to stall said fetching of said instruction, thereby preventing said instruction from being incorrectly fetched.

Claim 10

In a computer system comprising a memory unit for storing instructions and data, a bus controller coupled to said memory unit for accessing said instructions and data, an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions, and a cache subsystem coupled to said bus controller and said execution unit for caching said data, wherein said instructions are fetched, issued, and executed in a manner with said instruction fetching and issuing potentially being speculative, a method for buffering store instructions, and preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a buffered store instruction, said method comprising the steps of: a) storing partial address bits of destination addresses of store destinations of a plurality of buffered store instructions; b) receiving a first plurality of partial address bits of a source address of an instruction being fetched, computing a second plurality of partial address bits of the source address based on the first plurality of partial address bits of the source address, and outputting the first and second plurality of partial address bits of said source address; c) concurrently matching said first and second plurality of partial address bits of said source address against the corresponding partial address bits of said destination addresses, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first or second plurality of partial address bits of said source address; and d) generating a stall signal in response to receiving at least one match signal, to stall said fetching of said instruction, thereby preventing said instruction from being incorrectly fetched.

Claim 11

The method as set forth in claim 8, wherein, each of said buffered store instructions potentially stores data into destinations spanning two cache lines of said cache subsystem, each cache line having a fixed cache line size; said step (b) comprises generating said second plurality of partial address bits of said source address by subtracting a constant from said first plurality of partial address bits of said source address, said constant being predetermined based on said fixed cache line size.

Claim 12

The method as set forth in claim 9, wherein, each of said source and destination addresses has address bits (n1:0), where n1 is an integer greater than 0; said step (a) comprises storing only address bits (n2:n3) of the destination address of the store destination of each buffered store instruction, where n2 is an integer not larger than n1, and n3 is an integer smaller than n2 but not smaller than 0, said step (b) comprises receiving first address bits (n4:n5) of said source address of said instruction being fetched, and generating second address bits (n4:n5) by subtracting said predetermined constant from said first address bits (n4:n5), where n4 is an integer not larger than n2, and n5 is an integer smaller than n4 but not smaller than n3; said step (c) comprises receiving said first address bits (n4:n5) and said second address bits (n4:n5) of said source address, and concurrently matching said first address bits (n4:n5) and said second address bits (n4:n5) of said source address against the address bits (n4:n5) of the destination addresses of the buffered store instructions.

Claim 13

The method as set forth in claim 10, wherein, address bits (n1:n6) of each of said source and destination addresses denote a memory page, and address bits (n7:0) denotes an offset into the memory page, where n6 and n7 are integers, and n1>n6>n7>0; n2 is less than n1 but greater than n6; n3 equals 0; n4 equals n2; and n5 is less than n7 but greater than 0.

Claim 14

In a computer system comprising a memory unit for storing instructions and data, a bus controller coupled to said memory unit for accessing said instructions and data, an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions, and a cache subsystem coupled to said bus controller and said execution unit for caching said data, wherein said instructions are fetched, issued, and executed in a manner with said instruction fetching and issuing potentially being speculative, an apparatus for buffering store instructions, and preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a buffered store instruction, said apparatus comprising: a) buffers for buffering a plurality of store instructions including partial address bits of destination addresses of the buffered store instructions; b) address input unit coupled to said instruction fetching and issuing unit for receiving a first plurality of partial address bits of a source address of an instruction being fetched, and outputting a second plurality of partial address bits and the first plurality of partial address bits of said source address, said second plurality of partial address bits being computed based on said first plurality of partial address bits; c) matching circuitry coupled to said buffers and said address input unit for receiving said first and second plurality of partial address bits of said source address, concurrently matching said first and second plurality of partial address bits of said source address against said stored partial address bits of said destination addresses of said buffered store instructions, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first plurality of partial address bits or said second plurality of partial address bits of said source address; d) a stall signal generator coupled to said matching circuitry and said bus controller for generating a stall signal in response to receiving at least one match signal, to stall said bus controller, thereby preventing said instruction from being incorrectly fetched.

Claim 15

In a computer system comprising a memory unit for storing instructions and data, a bus controller coupled to said memory unit for accessing said instructions and data, an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions, and a cache subsystem coupled to said bus controller and said execution unit for caching said data, wherein said instructions are fetched, issued, and executed in a manner with said instruction fetching and issuing potentially being speculative, an apparatus for buffering store instructions, and preventing incorrect fetching of an instruction of a self-modifying code sequence with dependency on a buffered store instruction, said apparatus comprising: a) buffers for buffering a plurality of store instructions including partial address bits of destination addresses of the buffered store instructions; b) address input unit coupled to said instruction fetching and issuing unit for receiving a first plurality of partial address bits of a source address of an instruction being fetched, and outputting a second plurality of partial address bits and the first plurality of partial address bits of said source address, said second plurality of partial address bits being computed based on said first plurality of partial address bits; c) matching circuitry coupled to said buffers and said address input unit for receiving said first and second plurality of partial address bits of said source address, concurrently matching said first and second plurality of partial address bits of said source address against said stored partial address bits of said destination addresses of said buffered store instructions, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first plurality of partial address bits or said second plurality of partial address bits of said source address; d) a stall signal generator coupled to said matching circuitry and said bus controller for generating a stall signal in response to receiving at least one match signal, to stall said bus controller, thereby preventing said instruction from being incorrectly fetched.

Claim 16

The apparatus as set forth in claim 12, wherein, each of said buffered store instruction potentially stores data into destinations spanning two cache lines of said cache subsystems, each cache line having a fixed cache line size; said address input unit comprises a subtractor for generating said second plurality of partial address bits of said source address by subtracting a constant from said first plurality of partial address bits of said source address, said constant being predetermined based on said fixed cache line size.

Claim 17

The apparatus as set forth in claim 13, wherein, each of said source and destination addresses has address bits (n1:0), where n1 is an integer greater than 0; each of said buffers stores only address bits (n2:n3) of the destination address of the store destination of each buffered store instruction, where n2 is an integer not larger than n1, and n3 is an integer smaller than n2 but not smaller than 0; said subtractor receives first address bits (n4:n5) of said source address of said instruction being fetched, and generates second address bits (n4:n5) by subtracting said predetermined constant from said first address bits (n4:n5), where n4 is an integer not larger than n2, and n5 is an integer smaller than n4 but not smaller than n3; said matching circuitry receives said first and second address bits (n4:n5) of said source address, and concurrently matches said first and second address bits (n4:n5) of said source address against the address bits (n4:n5) of the destination addresses of the buffered store instructions.

Claim 18

The apparatus as set forth in claim 14, wherein, address bits (n1:n6) of each of said source and destination addresses denote a memory page, and address bits (n7:0) denotes an offset into the memory page, where n6 and n7 are integers, and n1>n6>n7>0; n2 is less than n1 but greater than n6; n3 equal 0; n4 equals n2; and n5 is less than n7 but greater than 0.

Claim 19

The apparatus as set forth in claim 15, wherein, said buffers comprise a plurality of buffer slots of storing said buffered store instructions; and said matching circuitry comprises a plurality of matching circuits correspondingly coupled to said buffer slots, each of said matching circuit comprising: c.1) a first comparator for receiving first partial address bits (n4:n6) of said first address bits (n4:n5) of said source address and partial address bits (n4:n6) of the destination address of the store instruction buffered in the corresponding buffer slot as first inputs, comparing said first inputs, and outputting a first partial match signal if said first inputs match each other; c.2.) a second comparator for receiving first partial address bits (n7:n5) of said first address bits (n4:n5) of said source address and partial address bits (n7:n5) of the destination address of the store instruction buffered in the corresponding buffer slot as second inputs, comparing said second inputs, and outputting a second partial match signal if said second inputs match each other; c.3) a first AND gate coupled to said first and second comparators for receiving said first and second partial match signals, and outputting the logical AND of said first and second partial match signals as a first preliminary match signal; c.4) a third comparator for receiving second partial address bits (n4:n6) of said second address bits (n4:n5) of said source address and partial address bits (n4:n6) of the destination address of the store instruction buffered in the corresponding buffer slot as third inputs, comparing said third inputs, and outputting a third partial match signal if said third inputs match each other; c.5) a fourth comparator for receiving second partial address bits (n7:n5) of said second address bits (n4:n5) of said source address and partial address bits (n7:n5) of the destination address of the store instruction buffered in the .corresponding buffer slot as fourth inputs, comparing said fourth inputs, and outputting a fourth partial match signal if said fourth inputs match each other; c.6) a second AND gate coupled to said third and fourth comparators for receiving said third and fourth partial match signals, and a split bit indicating whether the destination of the store instruction buffered in the corresponding buffer slot spans two cache lines, and outputting the logical AND of said third and fourth partial match signals and said split bit as a second preliminary match signal; c.7) an OR gate coupled to said first and second AND gates for receiving said first and second preliminary match signals, and outputting the logical OR of said first and second preliminary match signals as a combined preliminary match signal; c.8) a third AND gate coupled to said OR gate for receiving said combined preliminary match signal and a validity bit indicating whether the destination address of the store instruction buffered in the corresponding buffer slot is valid or not, and outputting the logical AND of said combined preliminary match signal and said validity bit as a qualified match signal; and c.9) a fourth AND gate coupled to said third AND gate for receiving said qualified match signal and a clock signal, and output the logical AND of said qualified match signal and said clock signal as one of said match signals.

Claim 20

The apparatus as set forth in claim 12, wherein, said stall signal generator comprises: d.1) a pre-charged bit line coupled to said matching circuitry for generating an active low signal in response to receiving at least one match signal; d.2) an inverter coupled to said pre-charged bit line for generating an active high signal in response to said active low signal, and d.3) an AND gate coupled to said inverter and said bus controller for receiving said active high signal and a validity signal indicating whether said instruction fetch is valid or not, and generating the logical AND of said active high and validity signals as a stall signal.

Claim 21

The apparatus as set forth in claim 12, wherein, said execution unit potentially executes said issued instructions out-of-order but retires execution results in order; and said buffers, said address input unit, said matching circuitry, and said stall signal generator are disposed in a memory order buffer of a data cache controller of said cache subsystem.

Claim 22

A computer system comprising: (a) a memory unit for storing instructions and data; (b) a bus, controller coupled to said memory unit for accessing said instructions and data; (c) an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, said instruction fetching and issuing potentially being speculative, (d) an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions; (e) a cache subsystem coupled to said bus controller and said execution unit for caching said data, said cache subsystem comprising: e.1) buffers for buffering a plurality of store instructions including partial address bits of destination addresses of the buffered store instructions; e.2) address input unit coupled to said instruction fetching and issuing unit for receiving a first plurality partial address bits of a source address of an instruction being fetched, and outputting a second plurality of partial address bits and the first plurality partial address bits of said source address, the second plurality of partial address bits being computed based on said first plurality of partial address bits; e.3) matching circuitry coupled to said buffers and said address input unit for receiving said first and second plurality of partial address bits of said source address, concurrently matching said first and second plurality of partial address bits of said source address against said stored partial address bits of said destination addresses of said buffered store instructions, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first or said second plurality of partial address bits of said source address; e.4) a stall signal generator coupled to said matching circuitry and said bus controller for generating a stall signal in response to receiving at least one match signal, to stall said bus controller, thereby preventing said instruction from being incorrectly fetched.

Claim 23

A computer system comprising: (a) a memory unit for storing instructions and data; (b) a bus, controller coupled to said memory unit for accessing said instructions and data; (c) an instruction fetching and issuing unit coupled to said bus controller for fetching and issuing said instructions in order, said instruction fetching and issuing potentially being speculative, (d) an execution unit coupled to said instruction fetching and issuing unit for executing said issued instructions; (e) a cache subsystem coupled to said bus controller and said execution unit for caching said data, said cache subsystem comprising: e.1) buffers for buffering a plurality of store instructions including partial address bits of destination addresses of the buffered store instructions; e.2) address input unit coupled to said instruction fetching and issuing unit for receiving a first plurality partial address bits of a source address of an instruction being fetched, and outputting a second plurality of partial address bits and the first plurality partial address bits of said source address, the second plurality of partial address bits being computed based on said first plurality of partial address bits; e.3) matching circuitry coupled to said buffers and said address input unit for receiving said first and second plurality of partial address bits of said source address, concurrently matching said first and second plurality of partial address bits of said source address against said stored partial address bits of said destination addresses of said buffered store instructions, and generating a match signal for each buffered store instruction whose stored partial address bits of its destination address match either said first or said second plurality of partial address bits of said source address; e.4) a stall signal generator coupled to said matching circuitry and said bus controller for generating a stall signal in response to receiving at least one match signal, to stall said bus controller, thereby preventing said instruction from being incorrectly fetched.

Claim 24

The computer system as set forth in claim 19, wherein, said execution unit potentially executes said issued instructions out-of-order but retires execution results in order; and said buffers, said address input unit, said matching circuitry and said stall signal generator are disposed in a memory order buffer of a data cache controller of said cache subsystem.

Claim 25

The apparatus as set forth in claim 1, wherein, said bus controller, said instruction fetching and issuing unit, said execution unit, said cache subsystem, and said apparatus comprising buffer means, said address input means, said matching means and stalling means, are disposed on a single silicon microprocessor chip.

Claim 26

The method as set forth in claim 8, wherein, said bus controller, said instruction fetching and issuing unit, said execution unit, and said cache subsystems, are disposed on a single silicon based microprocessor chip; and said method steps (a) through (c) are practiced on said microprocessor.

Claim 27

The apparatus as set forth in claim 12, wherein, said bus controller, said instruction fetching and issuing unit, said execution unit, said cache subsystem, and said apparatus comprising buffers, said address input unit, said matching circuitry, and stalling means, are disposed on a single silicon microprocessor chip.

Claim 28

The computer system as set forth in claim 19, wherein, said bus controller, said instruction fetching and issuing unit, said execution unit, said cache subsystem, and said apparatus comprising buffers, said address input unit, said matching circuitry and stalling means, are disposed on a single silicon microprocessor chip.