<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Everyone,<br>
<br>
There is non-determinism in LLVM codegen in the following scenarios:<br>
<br>
1. Between back-to-back runs of the same LLVM toolchain<br>
2. Between Release vs Release+Asserts toolchains<br>
3. Between Linux vs Windows toolchains<br>
<br>
The main reasons for the non-determinism in codegen are:<br>
<br>
1. Iteration of unordered containers (like SmallPtrSet, DenseMap,
etc) where the iteration order is undefined<br>
2. Use of non-stable sorts (like std:sort which uses quicksort)
where the relative order of elements with the same key is undefined<br>
<br>
I wanted a way to uncover instances where iteration of unordered
containers results in different codegen.<br>
So I have written the following patch:<br>
<b><a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D26703">https://reviews.llvm.org/D26703</a></b><br>
<br>
Given a flag (-mllvm -reverse-iterate) this patch will enable
iteration of SmallPtrSet in reverse order. The idea is to compile
the same source with and without this flag and expect the code to
not change.<br>
If there is a difference in codegen then it would mean that the
codegen is sensitive to the iteration order of SmallPtrSet.<br>
<br>
I ran make check-all with and without my patch and I see the
following additional failures due to iteration of SmallPtrSet in
reverse order:<br>
<i> Clang :: Analysis/keychainAPI.m</i><i><br>
</i><i> Clang :: Analysis/malloc.c</i><i><br>
</i><i> Clang :: Rewriter/objc-modern-metadata-visibility.mm</i><i><br>
</i><i> Clang :: SemaCXX/warn-loop-analysis.cpp</i><i><br>
</i><i> LLVM ::
Transforms/LoopVectorize/consecutive-ptr-uniforms.ll</i><i><br>
</i><i> LLVM :: Transforms/SimplifyCFG/bug-25299.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/cyclicphi.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/many-dom-backedge.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/many-doms.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/phi-translation.ll</i><br>
<br>
I have posted the following patches which fix some of the above
failures by changing SmallPtrSet to SmallSetVector:<br>
<b><a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D26704">https://reviews.llvm.org/D26704</a></b><b><br>
</b><b><a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D26705">https://reviews.llvm.org/D26705</a></b><b><br>
</b><b><a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D26706">https://reviews.llvm.org/D26706</a></b><br>
<br>
Here are the next steps which I would like to do:<br>
1. Replicate this patch for other containers (like DenseMap)<br>
2. Somehow enable reverse iteration in the lit framework for all
tests so that we can uncover these issues quickly<br>
<br>
Please feel free to review my patch for reverse iteration. I would
welcome comments/suggestions for improving/extending the patch and
enabling it in lit.<br>
<br>
Thanks,<br>
Mandeep<br>
<br>
<br>
<br>
</body>
</html>