Optimizing TSan Instrumentation with Static Analysis

[Alexey Paznikov]

Hi everyone,

We are exploring ways to reduce the overhead associated with TSan instrumentation and are particularly interested in the potential of static analysis. Our preliminary experiments, where we manually disabled instrumentation in verified thread-safe hot functions, showed a promising 10% performance improvement.

We are now planning to develop static analysis algorithms that can automatically identify code regions suitable for exclusion from TSan instrumentation without compromising the accuracy of data race detection.

Before we delve deeper, we'd greatly appreciate any insights and experience regarding using static analysis to optimize TSan instrumentation.

Specifically, we are interested in:

• Existing research or implementations: Are you aware of any research or tools that have explored this approach?
• Promising static analysis techniques: Are there specific techniques or tools that you believe would be most effective for identifying thread-safe code regions for instrumentation exclusion?
• Limitations of current TSan analysis:  Are there any insights into the limitations of the existing static analysis within TSan, particularly regarding its ability to identify code suitable for exclusion?

Any information or pointers you could share would be extremely valuable. We believe that a collaborative effort can lead to significant advancements in reducing TSan's overhead while maintaining its effectiveness.

As a starting point, we are considering leveraging an enhanced Escape Analysis (Capture Tracking) as a potential replacement for the simpler Capture Tracking (llvm/lib/Analysis/CaptureTracking.cpp) currently used by TSan.  We believe this could lead to more precise identification of thread-local data and further reduce unnecessary instrumentation.

Thanks in advance for your help!

Best regards,
Alexey Paznikov 

[Dmitry Vyukov]

Hi Alexey,

Overall any optimizations that don't introduce new false negatives
would be very useful and benefit all existing users.

There was some research on this, but at this point I don't remember
any concrete references (can't do better than you searching papers for
right keywords).

Things besides better escape analysis that come to mind:

Better duplicate check elimination. Currently the pass only removes
very simple duplicates (within the same basic block with no
intervening calls in between). It may be possible to extend this
analysis inter-basic-block based on pre/post-dominance.

It may also be possible to eliminate duplicates across calls if the
calls don't include any synchronization operations (that's what we
really care about).

Even tricker analysis may tolerate some synchronization operations in
between. Namely, for only acquire/release operations we leave only the
check before/after the operation.

We also discussed combining several checks into one, e.g. instead of 2
close 1-byte checks we do 1 2-byte check. However, for tsan
specifically it's more tricky than asan/msan b/c tsan wants checks to
not cross aligned 8-byte granules, so the combined check must be
within an aligned 8-byte region. And another problem with this is
report quality -- the report may contain wrong line number/access size
if we do it. This is pretty nasty, and that's the reason we didn't do
it.

The pass also ignores accesses to global const data, vptr, etc. Maybe
there are some other opportunities here: either identifying more
non-racing locations, or identifying existing types better, e.g. for
pointers returned from functions (say, a function always returns a
pointer to const global).

[Alexey Paznikov]

Hi Dmitry,

Thank you so much for your detailed and insightful response! Your suggestions are extremely valuable and have given us several new avenues to explore.

We particularly appreciate your ideas regarding optimization beyond escape analysis. We find them highly compelling and will likely prioritize them once we make progress with our initial static analysis approach.

Thanks again for your time and valuable input. We will keep you updated on our progress and will definitely reach out if we have any further questions.

Tue, 24  Sept  2024 г. в 17:08:32 UTC+8, dvy...@google.com: