[Dominators] Simplify child lists and make them deterministic

[bkramer]

Summary

This fixes an extremely subtle non-determinism that can only be
triggered by an unfortunate alignment of passes. In my case:

• JumpThreading does large dominator tree updates
• CorrelatedValuePropagation preserves domtree now
• LICM codegen depends on the order of children on domtree nodes

The last part is non-deterministic if the update was stored in a set.
But it turns out that the set is completely unnecessary, updates are
deduplicated at an earlier stage so we can just use a vector, which is
both more efficient and doesn't destroy the input ordering.

I didn't manage to get the 240 MB IR file reduced enough, triggering
this bug requires a lot of jump threading, so landing this without a
test case.

[brzycki]

I always prefer deterministic execution (all other things being equal). Have you done any testing of performance impact to this change? The adding and erasing of Dominator elements may cost more with how the SmallVector type performs the operations.

Otherwise I think the patch looks good. However, @kuhar is the Dominator expert here and I'd recommend waiting for him to speak up before committing.

I didn't manage to get the 240 MB IR file reduced enough, triggering this bug requires a lot of jump threading, so landing this without a test case.

Did you try bugpoint? a 240MB IR fire is indeed huge but maybe letting it run over night can help reduce the problem space. Non-deterministic errors like these are very difficult to narrow down though.

include/llvm/Support/GenericDomTreeConstruction.h

86 ↗

(On Diff #152141)

Why did you reduce the initialization size from 4 elements down to 1?

[bkramer]

In D48392#1138246, @brzycki wrote:

I always prefer deterministic execution (all other things being equal). Have you done any testing of performance impact to this change? The adding and erasing of Dominator elements may cost more with how the SmallVector type performs the operations.

Otherwise I think the patch looks good. However, @kuhar is the Dominator expert here and I'd recommend waiting for him to speak up before committing.

I didn't manage to get the 240 MB IR file reduced enough, triggering this bug requires a lot of jump threading, so landing this without a test case.

Did you try bugpoint? a 240MB IR fire is indeed huge but maybe letting it run over night can help reduce the problem space. Non-deterministic errors like these are very difficult to narrow down though.

I didn't have success bugpointing this. It compiles really slowly and you need a lot of compiles in an interestingness function for a determinism bug. The other problem is you need to be really unlucky to get all the transforms trigger in the right order, blowing up the amount of input needed.

include/llvm/Support/GenericDomTreeConstruction.h

86 ↗

(On Diff #152141)

No good reason, I'll bump it back to 4.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

1221 ↗

(On Diff #152141)

Won't this also introduce non-determinism in the case you described?

1255 ↗

(On Diff #152141)

Related to above.

1272 ↗

(On Diff #152141)

I think this deserves a comment -- it's only obvious that the successor/predecessor is at the end once you realize updates are performed in the same order as they happened to be legalized.

[bkramer]

Address comments.

[bkramer]

include/llvm/Support/GenericDomTreeConstruction.h

1221 ↗

(On Diff #152141)

It would, but we restore a deterministic order below by sorting back to input order.

1255 ↗

(On Diff #152141)

Right, this makes the order deterministic again.

1272 ↗

(On Diff #152141)

Done.

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

struct BatchUpdateInfo {
 
     // In order to be able to walk a CFG that is out of sync with the CFG
     // DominatorTree last knew about, use the list of updates to reconstruct
     // previous CFG versions of the current CFG. For each node, we store a set
     // of its virtually added/deleted future successors and predecessors.
     // Note that these children are from the future relative to what the
     // DominatorTree knows about -- using them to gets us some snapshot of the
     // CFG from the past (relative to the state of the CFG).
-    DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors;
-    DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FuturePredecessors;
+    DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
+    DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
     // Remembers if the whole tree was recalculated at some point during the
     // current batch update.
     bool IsRecalculated = false;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
 
static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
     const size_t NumLegalized = BUI.Updates.size();
     BUI.FutureSuccessors.reserve(NumLegalized);
     BUI.FuturePredecessors.reserve(NumLegalized);
 
     // Use the legalized future updates to initialize future successors and
     // predecessors. Note that these sets will only decrease size over time, as
     // the next CFG snapshots slowly approach the actual (current) CFG.
     for (UpdateT &U : BUI.Updates) {
-      BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()});
-      BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()});
+      BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
+      BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
     }
 
     LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
     LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
                                            : reverse(BUI.Updates)) dbgs()
                << '\t' << U << "\n");
     LLVM_DEBUG(dbgs() << "\n");
 
#endif
   }
 
   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
     assert(!BUI.Updates.empty() && "No updates to apply!");
     UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
     LLVM_DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
 
     // Move to the next snapshot of the CFG by removing the reverse-applied
-    // current update.
+    // current update. Since updates are performed in the same order they are
+    // legalized it's sufficient to pop the last item here.
     auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
-    FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()});
+    assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
+           FS.back().getInt() == CurrentUpdate.getKind());
+    FS.pop_back();
     if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
 
     auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
-    FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()});
+    assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
+           FP.back().getInt() == CurrentUpdate.getKind());
+    FP.pop_back();
     if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
 
     if (CurrentUpdate.getKind() == UpdateKind::Insert)
       InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
     else
       DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
   }