[Dominators] Take fast path when applying <=1 updates

[kuhar]

Summary

This patch teaches DT.applyUpdates to take the fast when applying zero or just one update and makes it not run the internal batch updater machinery.

With this patch, it should no longer make sense to have a special check in user's code that checks the update sequence size before applying them, e.g.

if (!MyUpdates.empty())
  DT.applyUpdates(MyUpdates);

or

if (MyUpdates.size() == 1)
  if (...)
    DT.insertEdge(...)
  else
    DT.deleteEdge(...)

[davide]

Does this make a difference?

[kuhar]

@davide
I haven't measured, but it definitely makes it do less work. The purpose of this patch is to stop people from writing this micro-optimization all over different passes, which just generates a lot of noise in the code.

[davide]

I'm fine with this, but please wait if Danny or Tobias have comments.

[• dberlin]

This looks right to me, since people were trying to do it anyway :)

[grosser]

Looks fine to me as well.

llvm/trunk/include/llvm/Support/GenericDomTree.h

#endif
   ///    sense to insert the same edge twice.
   ///
   /// What's more, the functions assumes that it's safe to ask every node in the
   /// CFG about its children and inverse children. This implies that deletions
   /// of CFG edges must not delete the CFG nodes before calling this function.
   ///
   /// Batch updates should be generally faster when performing longer sequences
   /// of updates than calling insertEdge/deleteEdge manually multiple times, as
-  /// they can reorder the updates and remove redundant ones internally.
+  /// it can reorder the updates and remove redundant ones internally.
+  /// The batch updater is also able to detect sequences of zero and exactly one
+  /// update -- it's optimized to do less work in these cases.
   ///
   /// Note that for postdominators it automatically takes care of applying
   /// updates on reverse edges internally (so there's no need to swap the
   /// From and To pointers when constructing DominatorTree::UpdateType).
   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
   /// with the same template parameter T.
   ///
   /// \param Updates An unordered sequence of updates to perform.

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

static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
     DT.DomTreeNodes.erase(TN->getBlock());
   }
 
   //~~
   //===--------------------- DomTree Batch Updater --------------------------===
   //~~
 
   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
+    const size_t NumUpdates = Updates.size();
+    if (NumUpdates == 0)
+      return;
+
+    // Take the fast path for a single update and avoid running the batch update
+    // machinery.
+    if (NumUpdates == 1) {
+      const auto &Update = Updates.front();
+      if (Update.getKind() == UpdateKind::Insert)
+        DT.insertEdge(Update.getFrom(), Update.getTo());
+      else
+        DT.deleteEdge(Update.getFrom(), Update.getTo());
+
+      return;
+    }
+
     BatchUpdateInfo BUI;
     LegalizeUpdates(Updates, BUI.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