<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Thu, Aug 9, 2018 at 11:52 AM Grang, Mandeep Singh <<a href="mailto:mgrang@codeaurora.org">mgrang@codeaurora.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<p>Thanks for your response David.</p></div><div text="#000000" bgcolor="#FFFFFF">
<p>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</p>
</div><div text="#000000" bgcolor="#FFFFFF"><p>The idea I had in mind was to check the commutativity of each
operation inside the iteration of the unordered container. I
realize we may not be able to do this for every operation and even
if we could that would still be a heuristic and prone to false
positives. Maybe we can start with a simpler problem to tackle
instead of the iteration order. That's why in the patch I pushed I
wrote a very simple checker for std::sort with raw pointers.<br></p></div></blockquote><div>You're referring to the llvm::sort work, that randomizes the elements due to the instability of std::sort? (or some other work on std::sort and raw pointers?)<br><br>Changes like llvm::sort I don't see as "static/dynamic analysis" - but changing behavior & relying on the products own tests to validate the behavior is still correct. (unlike static or dynamic analysis which produces warnings/errors on the relevant codepaths).<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><p>
</p></div><div text="#000000" bgcolor="#FFFFFF">
<p>> 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.</p>
</div><div text="#000000" bgcolor="#FFFFFF"><p>Yes, maybe iteration order is more difficult to problem but we
should be able to detect non-deterministic sorting order of keys
with same values. The idea I had in mind is similar to what we do
in llvm::sort (which is random shuffle of the container). We
instrument the user code to sort a container twice - first is the
user's normal std::sort, the second time we random shuffle the
container and then sort again, and then check if there is a
difference in the two outputs. The run time cost would be the cost
of the shuffle + the extra sort + the cost of checking the two
containers [O(n lg n) + 2 O(n)].</p></div></blockquote><div>Though different results there doesn't necessarily represent a bug in the program - it's a question of whether that different order impacts the program behavior. Could experiment - but I'd guess that the false positive rate would be a bit high..<br><br>(that said, I'm a bit of a pessimist in general - so take my perspective with a grain of salt :) )<br><br>- Dave</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">
<p>--Mandeep<br>
</p></div><div text="#000000" bgcolor="#FFFFFF">
<br>
<div class="m_-5606010884709809547moz-cite-prefix">On 8/9/2018 11:13 AM, David Blaikie
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">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... <br>
<br>
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.</div>
<br>
<div class="gmail_quote">
<div dir="ltr">On Wed, Aug 8, 2018 at 7:43 PM Grang, Mandeep
Singh via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">In the past,
I had added the ability in LLVM to uncover 2 types of <br>
non-deterministic behaviors: iteration of unordered containers
with <br>
pointer-like keys and sorting of elements with the same keys.<br>
<br>
Now, I wanted to add checkers for these (and other types of <br>
non-deterministic behaviors) so that they could be applied
more widely. <br>
I also realize that not all of these may be doable at
compile-time.<br>
<br>
With that in mind, I have pushed a patch which I adds a new
category of <br>
checks for non-determinism: <a href="https://reviews.llvm.org/D50488" rel="noreferrer" target="_blank">https://reviews.llvm.org/D50488</a>.<br>
<br>
The first checker which I have pushed here will simply check
if raw <br>
pointers are being sorted. In subsequent patches, I will fine
tune this <br>
by handling more complex cases of sorting of pointer-like
keys.<br>
<br>
I have another patch which checks for iteration of unordered
containers <br>
but that may be very noisy in its current form.<br>
<br>
I would like comments/suggestions from the community on:<br>
<br>
1. Are static analysis checks to detect non-determinism
something worth <br>
doing/doable?<br>
<br>
2. How about writing sanitizers to detect non-deterministic
behavior? <br>
Would that be too costly in terms of run time and
instrumentation?<br>
<br>
--Mandeep<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</blockquote>
<br>
</div></blockquote></div></div>