A method is provided for executing a cacheable store. The method includes determining whether to replay a store instruction to re-acquire one or more cache lines based upon a state of the cache line(s) and an execution phase of the store instruction. The store instruction is replayed in response to determining to replay the store instruction. An apparatus is provided that includes a store queue (SQ) configurable to determine whether to replay a store instruction to re-acquire one or more cache lines based upon a state of the cache line(s) and an execution phase of the store instruction. Computer readable storage devices for adapting a fabrication facility to manufacture the apparatus are provided.