An embodiment of the present invention includes a circuit for tracking memory operations with trace-based execution. Each trace includes a sequence of operations that includes zero or more of the memory operations. The memory operations being executed form a set of active memory operations that have a predefined program order among them and corresponding ordering constraints. At least some of the active memory operations access the memory in an execution order that is different from the program order. Checkpoint entries are associated with each trace. When a memory operation attempts to update a cache line that may not be updated, the circuit attempts to upgrade the cache line. If this fails, a rollback request is generated that indicates the trace involved. The checkpoint locations associated with the indicated trace are overwritten along with those locations associated with all younger traces.