1. An apparatus comprising: detection logic configured to detect a potential lock instruction and a potential subsequent lock release instruction, wherein the potential lock instruction is to include a read modify write (RMW) instruction; N storage elements to be logically viewed as a stack, wherein N elements are capable of storing N LIEs associated with N potential lock instructions to support N levels of nested critical sections, wherein N is an integer greater than 1; a storage element of the N storage elements configured to hold a lock instruction entry (LIE) associated with the potential lock instruction in response to the detection logic detecting the potential lock instruction, the lock instruction entry to include a reference to a lock address associated with the lock instruction, a store value associated with the lock instruction, a found corresponding lock release instruction flag configured to be updated to a found value in response to the match logic determining the potential subsequent lock release instruction corresponds to the potential lock instruction, and a late lock acquire flag to be updated to a late lock acquire value in response to the match logic determining the potential subsequent lock release instruction does not correspond to the potential lock instruction and a late lock acquire event occurring; match logic coupled to the detection logic and the storage element, the match logic configured to determine if the potential subsequent lock release instruction corresponds to the potential lock instruction based on a comparison of at least the reference to the lock address to be included in the lock instruction entry and a reference to a lock release address associated with the potential subsequent lock release instruction; and prediction logic coupled to the match logic, the prediction logic configured to store a prediction entry to represent the potential lock instruction is to be elided in response to subsequently detecting the potential lock instruction, if the match logic determines that the lock release instruction corresponds to the potential lock instruction.