Patent ID: 7725692

Claim:
A method for representing instruction execution path history, comprising: gathering information associated with a current instruction, the information including at least a target address, the target address being an instruction address to which control flows after the current instruction; assigning a 1-bit direction to a conditional branch if the current instruction is a conditional branch and if the conditional branch is determined to be taken; assigning a 1-bit direction if the current instruction is not a conditional branch; hashing the target address by shifting the target address to the right by a predetermined number of bits and selecting a predetermined number of low order bits to represent a hashed target address; shifting current content of a shift register having previously computed execution path history, left by one bit position and replacing rightmost bit of the shift register with the 1-bit direction, if the executing instruction is a conditional branch and the conditional branch is determined to be taken, or if the current instruction is not a conditional branch; shifting current content of the shift register left by number of bit positions equal to number of bits of the hashed target address and replacing rightmost bits with the hashed target address, if the current instruction is a conditional branch and the conditional branch is determined to be not taken; and compressing the current content of the shift register.