[JumpThreading] Prevent non-deterministic use lists

[pbarrio]

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.

[pbarrio]

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]

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.

[pbarrio]

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]

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.

[pbarrio]

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]

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

[efriedma]

LGTM.

lib/Transforms/Scalar/JumpThreading.cpp

 // This file implements the Jump Threading pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
for (auto &I : *BB) {
     if ((PN = dyn_cast<PHINode>(&I)) && (SI = getSelectFedByPhi(PN))) {
       expandSelect(SI);
       Changed = true;
       continue;
     }
 
     if (I.getType()->isIntegerTy(1)) {
 
-      SmallVector<SelectInst *, 4> Selects;
+      SmallSetVector<SelectInst *, 4> Selects;
 
       // Look for scalar booleans used in selects as conditions. If there are
       // several selects that use the same boolean, they are candidates for jump
       // threading and therefore we should unfold them.
       for (Value *U : I.users())
         if (auto *SI = dyn_cast<SelectInst>(U))
-          Selects.push_back(SI);
+          Selects.insert(SI);
       if (Selects.size() <= 1)
         continue;
 
-      // Remove duplicates
-      std::sort(Selects.begin(), Selects.end());
-      auto NewEnd = std::unique(Selects.begin(), Selects.end());
-
       Changed = true;
-      for (auto SI = Selects.begin(); SI != NewEnd; ++SI)
-        expandSelect(*SI);
+      for (auto SI : Selects)
+        expandSelect(SI);
     }
   }
 
   return Changed;
 }