A method and apparatus for detecting lock instructions and lock release instruction, as well as predicting critical sections is herein described. A lock instruction is detected with detection logic, which potentially resides in decode logic. A lock instruction entry associated with the lock instruction is stored/created. Address locations and values to be written to those address location of subsequent potential lock release instruction are compared to the address loaded from by the lock instruction and the value load by the lock instruction. If the addresses and values match, it is determined that the lock release instruction matches the lock instruction. A prediction entry stores a reference to the lock instruction, such as a last instruction pointer (LIP), and an associated value to represent the lock instruction is to be elided upon subsequent detection, if it is determined that the lock release instruction matches the lock instruction.