[WebAssembly] Fix a non-determinism problem in FixIrreducibleControlFlow

[kripken]

Summary

We already sorted the blocks when fixing up a set of mutual
loop entries, however, there can be multiple sets of such
mutual loop entries, and the order we encounter them
should not be random, so sort them too.

Fixes https://bugs.llvm.org/show_bug.cgi?id=44982

[sbc100]

Thanks for the quick fix!

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

72

do we need to capture everything [&] here?

[aheejin]

There seem to be multiple places that call Graph.getLoopEntries(). I guess we should sort all of them..? How about sort LoopEntries at the end of calculate() once and for all?

[kripken]

In D74999#1887675, @aheejin wrote:

There seem to be multiple places that call Graph.getLoopEntries(). I guess we should sort all of them..? How about sort LoopEntries at the end of calculate() once and for all?

We actually don't need to sort all of them - just where it matters. For example at the end of processRegion the different sets are guaranteed to be disjoint, and so we can process them in any order (see comment inside the loop). And it might be a little faster to not sort unnecessarily.

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

72

Ah, we don't good point. This code was just copied around but good idea to fix that.

[kripken]

Remove unneeded & in lambda capture.

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

 
 #define DEBUG_TYPE "wasm-fix-irreducible-control-flow"
 
 namespace {
 
 using BlockVector = SmallVector<MachineBasicBlock *, 4>;
 using BlockSet = SmallPtrSet<MachineBasicBlock *, 4>;
 
+static BlockVector getSortedEntries(const BlockSet &Entries) {
+  BlockVector SortedEntries(Entries.begin(), Entries.end());
+  llvm::sort(SortedEntries,
+             [](const MachineBasicBlock *A, const MachineBasicBlock *B) {
+               auto ANum = A->getNumber();
+               auto BNum = B->getNumber();
+               return ANum < BNum;
+             });
+  return SortedEntries;
+}
+
 // Calculates reachability in a region. Ignores branches to blocks outside of
 // the region, and ignores branches to the region entry (for the case where
 // the region is the inner part of a loop).
 class ReachabilityGraph {
 public:
   ReachabilityGraph(MachineBasicBlock *Entry, const BlockSet &Blocks)
       : Entry(Entry), Blocks(Blocks) {
 #ifndef NDEBUG

 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyFixIrreducibleControlFlow() : MachineFunctionPass(ID) {}
 };
 
 bool WebAssemblyFixIrreducibleControlFlow::processRegion(
     MachineBasicBlock *Entry, BlockSet &Blocks, MachineFunction &MF) {
   bool Changed = false;
-
   // Remove irreducibility before processing child loops, which may take
   // multiple iterations.
   while (true) {
     ReachabilityGraph Graph(Entry, Blocks);
 
     bool FoundIrreducibility = false;
 
-    for (auto *LoopEntry : Graph.getLoopEntries()) {
+    for (auto *LoopEntry : getSortedEntries(Graph.getLoopEntries())) {
       // Find mutual entries - all entries which can reach this one, and
       // are reached by it (that always includes LoopEntry itself). All mutual
       // entries must be in the same loop, so if we have more than one, then we
       // have irreducible control flow.
       //
+      // (Note that we need to sort the entries here, as otherwise the order can
+      // matter: being mutual is a symmetric relationship, and each set of
+      // mutuals will be handled properly no matter which we see first. However,
+      // there can be multiple disjoint sets of mutuals, and which we process
+      // first changes the output.)
+      //
       // Note that irreducibility may involve inner loops, e.g. imagine A
       // starts one loop, and it has B inside it which starts an inner loop.
       // If we add a branch from all the way on the outside to B, then in a
       // sense B is no longer an "inner" loop, semantically speaking. We will
       // fix that irreducibility by adding a block that dispatches to either
       // either A or B, so B will no longer be an inner loop in our output.
       // (A fancier approach might try to keep it as such.)
       //

 // ReachabilityGraph; this will be updated in the caller of this function as
 // needed.
 void WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop(
     BlockSet &Entries, BlockSet &Blocks, MachineFunction &MF,
     const ReachabilityGraph &Graph) {
   assert(Entries.size() >= 2);
 
   // Sort the entries to ensure a deterministic build.
-  BlockVector SortedEntries(Entries.begin(), Entries.end());
-  llvm::sort(SortedEntries,
-             [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
-               auto ANum = A->getNumber();
-               auto BNum = B->getNumber();
-               return ANum < BNum;
-             });
+  BlockVector SortedEntries = getSortedEntries(Entries);
 
 #ifndef NDEBUG
   for (auto Block : SortedEntries)
     assert(Block->getNumber() != -1);
   if (SortedEntries.size() > 1) {
     for (auto I = SortedEntries.begin(), E = SortedEntries.end() - 1; I != E;
          ++I) {
       auto ANum = (*I)->getNumber();