1. One or more computer-readable hardware storage devices storing computer-executable instructions that, when executed on one or more processors, perform acts comprising: receiving a memory trace comprising a plurality of memory access events, each of the plurality of memory access events representing the execution of a memory access instruction by a computer having a sequentially consistent memory model, wherein the plurality of memory access events are stored in a first order, the first order corresponding to an order in which the represented memory access instructions were executed; generating, for each of the plurality of memory access events, a target memory location, an issue index based on the order in which the event was executed by a processor, and a coherence index based on the number of previously executed memory access events that accessed the target memory location; determining whether the memory access instructions could, when executed on a computer having a relaxed memory model, be executed in a second order based at least in part on: computing a transitive happens-before relation that considers at least one ordering constraint that a memory model under consideration imposes on at least one memory access issued by a test program; and comparing the issue index and the coherence index of a memory access event with the issue indices and coherence indices of memory access events recorded before the memory access event, wherein the second order is different from the first order; when the memory access instructions could be executed in the second order, outputting an indication that the memory access instructions are not relaxed memory model safe; and when the memory access instructions could not be executed in an order different than the first order, outputting an indication that the memory access instructions are relaxed memory model safe.