RedCard: Redundant Check Elimination For Dynamic Race Detectors Technical Report UCSC-SOE-13-05

Precise dynamic race detectors report an error if and only if an observed program trace exhibits a data race. They must typically check for races on all memory accesses to ensure that they catch all races and generate no spurious warnings. However, a race check for a particular memory access is guaranteed to be redundant if the accessing thread has already accessed that location within the same release-free span. A release-free span is any sequence of instructions containing no lock releases or other \release-like" synchronization operations, such as notify or fork. We present a static analysis to identify redundant race checks by reason- ing about memory accesses within release-free spans. In contrast to prior whole program analyses for identifying accesses that are always race-free, our redundant check analysis is span-local and can also be made method- local without any major loss in eectiveness. RedCard, our prototype implementation for the Java language, enables dynamic race detectors to reduce the number of run-time checks by close to 40% with no loss in precision. We also present a complementary shadow proxy analysis for identify- ing when multiple memory locations can be treated as a single location by a dynamic race detector, again with no loss in precision. Combined, our analyses reduce the number of memory accesses requiring checks by roughly 50%.