This is an archive of the discontinued LLVM Phabricator instance.

[PredicateInfo] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet
ClosedPublic

Authored by mgrang on May 16 2017, 5:31 PM.

Details

Summary

Sort OpsToRename before iterating to make iteration order deterministic.

Thanks to Daniel Berlin for the sorting logic.

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang created this revision.May 16 2017, 5:31 PM
mgrang updated this revision to Diff 99229.May 16 2017, 5:33 PM

Added more context for the patch.

mgrang retitled this revision from Fix non-determinism in codegen uncovered due to reverse iteration of SmallPtrSet in PredicateInfo to [PredicateInfo ] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet.May 16 2017, 5:34 PM
davide added a subscriber: davide.May 16 2017, 5:55 PM

Where did you encounter this?

mgrang added a comment.EditedMay 16 2017, 6:10 PM

Where did you encounter this?

@davide The following two unit tests fail if run with -reverse-iterate :

test/Transforms/Util/PredicateInfo/condprop.ll
test/Transforms/Util/PredicateInfo/testandor.ll

The cause of the failure is the difference in codegen due to iteration of OpsToRename:

void PredicateInfo::renameUses(SmallSetVector<Value *, 8> &OpsToRename) {
  ValueDFS_Compare Compare(OBBMap);
  // Compute liveness, and rename in O(uses) per Op.
  for (auto *Op : OpsToRename) {
davide accepted this revision.May 16 2017, 6:11 PM
This revision is now accepted and ready to land.May 16 2017, 6:11 PM
dberlin edited edge metadata.EditedMay 16 2017, 6:16 PM

Actually, please don't land this.
This actually significantly slows down predicateinfo on large files.
The generated differences don't actually matter, either.

If you want to make a SmallPtrSetVector, i'd be more willing to do this, otherwise, i'll just convert the relevant parts.

(FWIW, i think running around the compiler and converting things from SmallPtrSet to to setvector is generally going to be a bad plan, and i'd be pretty opposed. We use SmallPtrSet because it's small and fast. SetVector is neither of these things. SmallSetVector is not *that much* better. )

dberlin requested changes to this revision.May 16 2017, 6:17 PM
This revision now requires changes to proceed.May 16 2017, 6:17 PM

uh, I'm very confused at this point, I thought this was resulting in non-deterministic output?

Nevermind, we always remove the copy so that shouldn't matter.

As we did in NewGVN I think it's important to add a comment explaining why this doesn't matter, so, @mgrang, you might want to do that instead.

(and in this case, the only place that needs any ordering is in renameUses, where we can just sort the input set of ops into a deterministic order, which we do for the uses anyway)

https://reviews.llvm.org/differential/diff/99233/?revisionID=33265
has a diff that touches one routine, and makes this deterministic.
It could use refactoring (it can share most code with the ValueDFS_Compare), but if you really want to make this deterministic, that's how to do it.

Thanks @davide and @dberlin for your comments.

Just wanted to confirm I understand this: In order to reuse the comparison function from ValueDFS_Compare in our case, we would have to move the localComesBefore function (or parts of it) out of ValueDFS_Compare so that both OBBMap and OpsToRename can use it as a comparator? ValueDFS_Compare constructor accepts BBs, so unless we first convert OpsToRename into ValueDFS (by calling our version of convertUsesToDFSOrdered) we cannot directly use it for sorting OpsToRename.
Or would it be simpler to just keep the comparator inline as you do in your code?

Also is it OK to add -reverse-iterate to the two unit tests as I have done in my patch (so that we catch any future non-determinism arising out of this piece of code)?

mgrang updated this revision to Diff 99624.May 19 2017, 2:04 PM
mgrang edited edge metadata.
mgrang retitled this revision from [PredicateInfo ] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet to [PredicateInfo] Fix non-determinism in codegen uncovered by reverse iterating SmallPtrSet.
mgrang edited the summary of this revision. (Show Details)
mgrang set the repository for this revision to rL LLVM.
sanjoy added a subscriber: sanjoy.May 21 2017, 10:05 PM

Ping for reviews please. (I know it's not been a week since I posted this patch, but it would be great if we could get this patch reviewed for an upcoming internal toolchain release).

Thanks!

RKSimon added inline comments.May 26 2017, 8:21 AM
lib/Transforms/Utils/PredicateInfo.cpp
552 ↗(On Diff #99624)

A few descriptive comments in this lambda would be useful.

mgrang updated this revision to Diff 100803.May 30 2017, 5:18 PM

Added comments for the comparator.

RKSimon edited edge metadata.Jun 1 2017, 1:34 AM

Added comments for the comparator.

Thanks no more comments from me.

@dberlin @davide anything to add?

Sorry, this was marked as accepted because davide accepted the last version.
This looks fine for now, i'll fix it up when D33380 goes in

dberlin accepted this revision.Jun 1 2017, 8:47 AM
This revision is now accepted and ready to land.Jun 1 2017, 8:47 AM
This revision was automatically updated to reflect the committed changes.