Page MenuHomePhabricator

[llvm] Convert iterable SmallPtrSet's to SmallSetVector's in Codegen

Authored by mgrang on Oct 21 2016, 6:48 PM.



Iteration of SmallPtrSet's are a cause of non-determinism in codegen because
the iteration order is not fixed. This results in different codegen from
run-to-run, release vs release+asserts and on linux vs windows.

The fix is to use SmallSetVector where the iteration order is deterministic.

Diff Detail

Event Timeline

mgrang updated this revision to Diff 75519.Oct 21 2016, 6:48 PM
mgrang retitled this revision from to [llvm] Convert iterable SmallPtrSet's to SmallSetVector's in Codegen.
mgrang updated this object.
mgrang set the repository for this revision to rL LLVM.
mgrang added a subscriber: llvm-commits.
vsk added a subscriber: vsk.Oct 21 2016, 9:59 PM

Thanks for working on this. I have questions about the overhead of this patch and about how to test it. First, what kind of compile-time/memory usage hit should we be willing to take to get this fixed? What happens to compile-time and peak memory consumption of the test suite after applying this patch? Is there a bot somewhere that checks for non-determinism in repeated builds of the test suite?

Thanks for the comments.

I will run LNT testsuite with and without my patch and post the results.

As for a way to check non-determinism, I guess for we can add a test which compiles the same test multiple times, although I am not sure how reliable/reproducible that will be. But I don't think there is a way to compare codegen of a release toolchain with release+asserts toolchain or linux vs windows toolchains.

rnk added a subscriber: rnk.Oct 25 2016, 12:02 PM

I don't think we should have a blanket rule banning iteration of unordered sets. Some of these do look like bugs, though. I think we should probably consider perturbing (maybe randomizing?) iteration order in NDEBUG builds to shake out these kinds of bugs.


This change makes this loop O(n^2), which is not acceptable.


There is a comment here suggesting that iteration order truly doesn't matter.

Yes, this is an attempt to preempt potential non-determinism caused due to iteration of unordered sets.

If this seems too aggressive then we can take the approach of identifying the exact causes and fixing just those.

Let me spin-off a few test runs on our internal test suite and I will come back with new fix/fixes.


mgrang abandoned this revision.Sep 7 2017, 10:57 AM

No longer needed.