[llvm-dev] Writing static analyzers to detect non-deterministic behavior?

[David Blaikie via llvm-dev]

1) I'm not sure it's do-able. I don't know of any nice way to track whether
an ordered walk of an unordered container leaks out into the final output
of the program. Only iterating over an unordered container is probably not
a sufficient hint (it'd have a high false positive rate to warn on every
instance of that) - and I don't have any great ideas about whether that
false positive rate could be sufficiently reduced with maybe some
heuristics about connecting one iteration to another container population,
and to the final program output...

2) Maybe - but I would think that'd still end up using heuristics to guess
at whether one iteration order impacts the order of another container, etc.

On Wed, Aug 8, 2018 at 7:43 PM Grang, Mandeep Singh via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> In the past, I had added the ability in LLVM to uncover 2 types of
> non-deterministic behaviors: iteration of unordered containers with
> pointer-like keys and sorting of elements with the same keys.
>
> Now, I wanted to add checkers for these (and other types of
> non-deterministic behaviors) so that they could be applied more widely.
> I also realize that not all of these may be doable at compile-time.
>
> With that in mind, I have pushed a patch which I adds a new category of
> checks for non-determinism: https://reviews.llvm.org/D50488.
>
> The first checker which I have pushed here will simply check if raw
> pointers are being sorted. In subsequent patches, I will fine tune this
> by handling more complex cases of sorting of pointer-like keys.
>
> I have another patch which checks for iteration of unordered containers
> but that may be very noisy in its current form.
>
> I would like comments/suggestions from the community on:
>
> 1. Are static analysis checks to detect non-determinism something worth
> doing/doable?
>
> 2. How about writing sanitizers to detect non-deterministic behavior?
> Would that be too costly in terms of run time and instrumentation?
>
> --Mandeep
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180809/5777d7ed/attachment.html>