Rules and apparatus for a loop capturing code buffer that prefetches instructions

Claim 2

Code buffer apparatus for accepting processor instructions from a code store and transferring said processor instructions to a processing element, said code buffer comprising: a random access memory containing P elements; an input address register; a program counter register; input transfer means for transferring said processor instructions from said code store to said random access memory at a location addressed by said input address register; output transfer means for transferring said processor instructions at a location addressed by said program counter register from said random access memory to said processing element; input access logic means for controlling said input transfer means to block transfer into said random access memory when said input address register addresses a location that is occupied by an unprocessed instruction or when said input address register addresses a location that is within an unprocessed instruction loop; and output access logic means for controlling said output transfer means to block transfer out of said random access memory when said program counter register does not address an unprocessed instruction or said program counter register does not address an instruction within an unprocessed instruction loop.

Claim 3

The code buffer apparatus as defined in claim 1 wherein said input access logic means comprises: loop begin stack means for storing a plurality of loop begin addresses; loop end stack means for storing a plurality of loop end stack addresses; loop present state means having a value of set or reset; means for blocking said input transfer if said input address register increments to become equal to said program counter register; and means for blocking said input transfer means if said loop present state means is set and said input address register is equal to the first of said loop begin addresses stored in said loop begin stack.

Claim 4

The code buffer apparatus as defined in claim 2 further comprising: means for detecting an inside backward branch instruction containing an address in said random access memory; means for storing said inside backward branch instruction address in said loop begin stack when said inside backward branch is detected; means for storing said input address register in said loop end stack when said inside backward branch is detected; means for coupling said loop end stack address with said loop begin stack address; and means for setting said loop present state means when said inside backward branch is detected.

Claim 5

The code buffer apparatus as defined in claim 3 further comprising means for detecting that said inside backward branch established an outer loop containing one or more inner loops and means for removing said loop begin and said loop end stack addresses for all said inner loops contained in said outer loop.

Claim 6

The code buffer apparatus as defined in claim 3 further comprising: means for detecting an address in said program counter register that points to an instruction that is after an instruction pointed to by one of said loop end stack addresses; and means responsive to said detecting means for removing said loop end stack address and said coupled loop begin stack address.

Claim 7

The code buffer apparatus as defined in claim 5 further comprising: means for detecting that said loop begin and said loop end stacks are empty; and means for resetting said loop present state means when said loop begin and said loop end stacks are empty.

Claim 8

The code buffer apparatus as defined in claim 2 further comprising means for blocking said input transfer means if said loop begin stack is full.

Claim 9

The code buffer apparatus as defined in claim 1 wherein said output access logic means comprises means for blocking said output transfer means when said program counter register points to an instruction that is not before an instruction pointed to by said input address register.

Claim 10

The code buffer apparatus as defined in claim 1 wherein said input access logic means comprises: loop begin register means for storing a loop begin address; loop end register means for storing a loop end address; loop present state means having a value of set or reset; means for blocking said input transfer means if said input address register increments to become equal to said program counter register; and means for blocking said input transfer means if said loop present state means is set and said input address register becomes equal to said loop begin address stored in said loop begin register.

Claim 11

The code buffer apparatus as defined in claim 9 further comprising: means for detecting an inside backward branch instruction containing an address in said random access memory; means for storing said inside backward branch instruction address in said loop begin register when said inside backward branch is detected; means for storing said input address register in said loop end register when said inside backward branch is detected; and means for setting said loop present state means when said inside backward branch is detected.

Claim 12

The code buffer apparatus as defined in claim 10 further comprising: means for detecting an address in said program counter register that points to an instruction that is after an instruction pointed to by one of said loop end register address; means responsive to said detecting means for indicating said loop end and said loop begin registers are empty; and means for resetting said loop present state means when said loop begin and said loop end registers are empty.

Claim 13

The code buffer apparatus as defined in claim 9 further comprising means for blocking said input transfer means if said loop begin register is full.

Claim 16

The method of claim 13 wherein step (c) further comprises the steps of: (c)(1) detecting an inside backward branch instruction containing an address in said random access memory; (c)(2) setting a loop present state means when said backward branch instruction is detected; (c)(3) storing said inside backward branch address in a loop begin stack when said backward branch is detected; (c)(4) storing said input address register in a loop end stack when said backward branch is detected; (c)(5) coupling said loop end stack address with said loop begin stack address; (c)(6) blocking said writing when said loop present state means is not set and said input address register is equal to said program counter; and (c)(7) blocking said writing when said loop present state is set and said input address register is equal to a first of said backward branch addresses stored in said loop begin stack.

Claim 17

The method of claim 14 further comprising the steps of: (c)(8) detecting that said inside backward branch established an outer loop containing one or more inner loops; (c)(9) removing said loop begin and said coupled loop end stack addresses for said inner loops contained in said outer loop.

Claim 18

The method of claim 15 further comprising the steps of: (c)(10) detecting an address in said program counter register that points to an instruction that is after an instruction that is pointed to by one of said loop end stack addresses; and (c)(11) removing said loop end stack address and said coupled loop begin address.

Claim 19

The method of claim 16 further comprising the steps of: (c)(12) detecting that said loop begin and said loop end stacks are empty; and (c)(13) resetting said loop present state means when said loop begin and said loop end stacks are empty.

Claim 20

The method of claim 1 further comprising the steps of: (c)(14) detecting that said loop begin stack is full; and (c)(15) blocking said writing when said loop begin stack is

Claim 21

The method of claim 13 wherein step g further comprises the step: (g)(1) blocking said reading when said program counter points to an instruction that is not before the instructions pointed to by said input address.

Claim 22

Code buffer apparatus for buffering processor instructions being transferred from a code store to decode logic in a processing element, said apparatus comprising: a RAM having P storage locations; an IAR having an address value; a PCR having an address value; an LB register having an address value; an LE register having an address value; a loop present state register having a value of set or reset; input transfer means for transferring said processor instructions from said code store to said RAM addressed by said IAR value; means for blocking said input transfer means when said IAR value increments to become equal to said PCR value; means for setting said loop present state register comprising first detection means for detecting an inside backward branch instruction, said instruction having a branch-to address, as said instruction is being transferred from said code store, means responsive to said first detection means for storing said IAR value in said LE register, means responsive to said first detection means for storing said branch-to address in said LB register, setting means responsive to said first detection means for setting said loop present state register; means for blocking said input transfer means when said loop present state register is set and said IAR value becomes equal to said LB register value; means for detecting an outside loop comprising second detection means for detecting an inside backward branch instruction, said instruction having a branch-to address, as said instruction is being transferred from said code store, means responsive to said second detection means for comparing said branch-to address to said LB register value and replacing said LE register value with said IAR value and replacing said LB register value with said branch-to address if said branch-to address points to an instruction that is before the instruction pointed to by said LB register value; means for resetting said loop present state register comprising third detection means for detecting a PCR value that points to an instruction that is after the instruction pointed to by said LE register value, means responsive to said third detection means for emptying said LE register and said LB register, resetting means responsive to said third detection means for resetting said loop present state register; means for blocking said input transfer means when said LB register is full; output transfer means for transferring said processor instructions at a location addressed by said PCR from said RAM to said decode logic in said processing element; means for blocking said output transfer means when said PCR points to an instruction that is not before the instruction pointed to by said IAR value.

Claim 23

Code buffer apparatus for buffering processor instructions being transferred from a code store to decode logic in a processing element, said apparatus comprising: a RAM having P storage locations; an IAR having an address value; a PCR having an address value; an LB register having an address value; an LE register having an address value; a loop present state register having a value of set or reset; input transfer means for transferring said processor instructions from said code store to said RAM addressed by said IAR value; means for blocking said input transfer means when said IAR value increments to become equal to said PCR value; means for setting said loop present state register comprising first detection means for detecting an inside backward branch instruction, said instruction having a branch-to address, as said instruction is being transferred from said code store, means responsive to said first detection means for storing said IAR value in said LE register, means responsive to said first detection means for storing said branch-to address in said LB register, setting means responsive to said first detection means for setting said loop present state register; means for blocking said input transfer means when said loop present state register is set and said IAR value becomes equal to said LB register value; means for detecting an outside loop comprising second detection means for detecting an inside backward branch instruction, said instruction having a branch-to address, as said instruction is being transferred from said code store, means responsive to said second detection means for comparing said branch-to address to said LB register value and replacing said LE register value with said IAR value and replacing said LB register value with said branch-to address if said branch-to address points to an instruction that is before the instruction pointed to by said LB register value; means for resetting said loop present state register comprising third detection means for detecting a PCR value that points to an instruction that is after the instruction pointed to by said LE register value, means responsive to said third detection means for emptying said LE register and said LB register, resetting means responsive to said third detection means for resetting said loop present state register; means for blocking said input transfer means when said LB register is full; output transfer means for transferring said processor instructions at a location addressed by said PCR from said RAM to said decode logic in said processing element; means for blocking said output transfer means when said PCR points to an instruction that is not before the instruction pointed to by said IAR value.