This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Prevent non-deterministic use lists
ClosedPublic

Authored by pbarrio on Nov 9 2016, 6:38 AM.

Details

Summary

Unfolding selects was previously done with the help of a vector
of pointers that was then sorted to be able to remove duplicates.
As this sorting depends on the memory addresses, it was
non-deterministic. A SetVector is used now so that duplicates are
removed without the need of sorting first.

Event Timeline

pbarrio updated this revision to Diff 77342.Nov 9 2016, 6:38 AM
pbarrio retitled this revision from to [JumpThreading] Prevent non-deterministic use lists.
pbarrio updated this object.
pbarrio added a reviewer: efriedma.
pbarrio added a subscriber: llvm-commits.

Hi @efriedma ,

Could you have a look at this fix as per your comments in D26391?

I couldn't think of a way to add a robust test to check for determinism. Please feel free to suggest if you find a reasonable way to add testing to this.

Many thanks,
Pablo

efriedma edited edge metadata.Nov 9 2016, 12:55 PM

Yes, it's kind of hard to write a good unit-test for determinism, precisely because it isn't deterministic. Maybe you could try something with opt -preserve-ll-uselistorder. If you can't come up with something that makes sense, don't worry about it.

lib/Transforms/Scalar/JumpThreading.cpp
2048

Looking at this a bit closer, there's another way you could write this: you can check whether the use is the condition of a select. Something like:

for (Use& U : I.uses()) {
  auto *SI = dyn_cast<SelectInst>(U.getUser());
  if (SI && U.getOperandNo() == 0)
    Selects.push_back(SI);
}

That naturally avoids duplicates, and is probably a bit closer to your original intent.

I have investigated the -preserve-ll-uselistorder option. It sets option "ShouldPreserveUseListOrder" to true in the module printer. According to the documentation:

"If ShouldPreserveUseListOrder, then include uselistorder directives so that use-lists can be recreated when reading the assembly. "

This will make sure that the order is the same across different calls to opt or across different tools, and I *think* it is now enabled by default. I could call opt twice with jump threading and compare the resulting testlists, but this is a fragile test as it may pass even when there is a bug. Something like this would be a very generic test:

; RUN: opt < %s -jump-threading > %t1
; RUN: opt < %s -jump-threading > %t2
; RUN: diff %t1 %t2

But I don't think it adds much value, so I haven't updated the patch.

lib/Transforms/Scalar/JumpThreading.cpp
2048

That was the first approach I tried, but it will unfold selects in cases where it is not necessary. I only want to unfold when there are two or more selects that use the same condition, so I need to check the condition's users instead of the select's uses.

efriedma added inline comments.Nov 10 2016, 10:10 AM
lib/Transforms/Scalar/JumpThreading.cpp
2048

I'm not following your response... "I.uses()" and "I.users()" are basically the same thing, except that "I.uses()" also gives you operand numbers.

Sorry, forget what I said. I didn't get what you were trying to do at first (I've never used the "uses"). I will do the change, as this makes more clear that the operand we are interested in is the condition (i.e. operand 0).

lib/Transforms/Scalar/JumpThreading.cpp
2048

Sorry, forget what I said. I didn't get what you were trying to do at first (I've never used the "uses"). I will do the change tomorrow, as this makes more clear that the operand we are interested in is the condition (i.e. operand 0).

pbarrio updated this revision to Diff 77610.Nov 11 2016, 6:07 AM
pbarrio edited edge metadata.

Traverse use list instead of user list to naturally avoid duplicates. Commit message modified accordingly.

efriedma accepted this revision.Nov 11 2016, 10:36 AM
efriedma edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Nov 11 2016, 10:36 AM
This revision was automatically updated to reflect the committed changes.