[PDT] Fix splitBlock for Post Dom Trees

[dmgreen]

Summary

The previous function presumed that the PDT split
would be the split of the DT split, which isn't the
case due to the way split takes some preds from the
old block.

This uses the applyUpdates interface to add/remove
the correct edges.

[davide]

This needs a test case.

[dmgreen]

Hello, Thanks for taking a look.

I went looking for tests for splitBlock on DomTrees and was surprised not to find anything. I guess it gets tested as part of preserving trees in normal IR tests. I will see if I can add something sensible.

I'm not 100% sure yet, but making this work with the updater from d40146 might need some changes. I will try it to see what the best way to handle these split blocks might be with that interface.

[fhahn]

In D41299#959733, @dmgreen wrote:

Hello, Thanks for taking a look.

I went looking for tests for splitBlock on DomTrees and was surprised not to find anything. I guess it gets tested as part of preserving trees in normal IR tests. I will see if I can add something sensible.

PostDominators are not really used extensively, so relying on the IR tests here is not the best idea. unittests/IR/DominatorTreeTest.cpp and/or unittests/IR/DominatorTreeBatchUpdatesTest.cpp should be good places to add a unit test that fails without this patch. I assume you have a case where you discovered the failure?

I'm not 100% sure yet, but making this work with the updater from d40146 might need some changes. I will try it to see what the best way to handle these split blocks might be with that interface.

I think the reason splitBlock is there is because it's cheap to update the DomTree in this case. If we have to use the applyUpdates, it might be better to batch those changes with all other DomTree changes.

[dmgreen]

This has ended up been removed as a part of D41302. I've added everyone here to subscribers there.

include/llvm/Support/GenericDomTree.h

if (RIt != Roots.end()) {
       std::swap(*RIt, Roots.back());
       Roots.pop_back();
     }
   }
 
   /// splitBlock - BB is split and now it has one successor. Update dominator
   /// tree to reflect this change.
   void splitBlock(NodeT *NewBB) {
-    if (IsPostDominator)
-      Split<Inverse<NodeT *>>(NewBB);
-    else
+    if (!IsPostDominator)
       Split<NodeT *>(NewBB);
+    else {
+      // FIXME: Split(NewBB) only works for dominator trees. For post-dominator
+      // trees we just uses applyUpdates and so is potentially less efficient
+      // than it could be.
+      using GraphT = GraphTraits<NodeT *>;
+      assert(std::distance(GraphT::child_begin(NewBB),
+                           GraphT::child_end(NewBB)) == 1 &&
+             "NewBB should have a single successor!");
+      NodeT *OldBB = *GraphT::child_begin(NewBB);
+
+      std::vector<UpdateType> Updates;
+      SmallPtrSet<NodeT *, 4> Visited;
+      for (auto *Pred : children<Inverse<NodeT *>>(NewBB)) {
+        if (!Visited.insert(Pred).second)
+          // Make sure our updates and balanced, even if Pred is a child
+          // multiple times
+          continue;
+        Updates.emplace_back(UpdateKind::Insert, Pred, NewBB);
+        Updates.emplace_back(UpdateKind::Delete, Pred, OldBB);
+      }
+      applyUpdates(Updates);
+    }
   }
 
   /// print - Convert to human readable form
   ///
   void print(raw_ostream &O) const {
     O << "=============================--------------------------------\n";
     if (IsPostDominator)
       O << "Inorder PostDominator Tree: ";