1. A computer implemented method for predicting critical sections, the method comprising: updating a critical section estimator based on historical analysis of atomic/store instruction pairs during runtime, the atomic/store instruction referring to a memory location, the memory location of the atomic/store instruction used to obtain a value within the memory location, wherein the updating is based on a match entry found in a first table for a memory address corresponding to the memory location and the value in the memory location of the atomic/store instruction and wherein the critical section estimator is indicative of the atomic/store instruction pairs defining start of a critical section; and performing lock elision when said critical section estimator indicates said atomic/store instruction pairs define a critical section, wherein said estimator comprises a second table having a plurality of entries each corresponding to potential critical sections, each entry including a confidence value that, when above a selected threshold, indicates corresponding atomic/store instruction pairs define said critical section and said critical section estimator tracks atomics not likely to start a critical section and the performing lock elision is executed when said critical section estimator does not indicate a current atomic instruction that does not begin a critical section.