[DomTreeUpdater] Add all insert before all delete updates to reduce compile time.

[asbirlea]

Summary

The cleanup in D62751 introduced a compile-time regression due to the way DT updates are performed.
Add all insert edges then all delete edges in DTU to match the previous compile time.
Compile time on the test provided by @mstorsjo before and after this patch on my machine:
113.046s vs 35.649s
Repro: clang -target x86_64-w64-mingw32 -c -O3 glew-preproc.c; on https://martin.st/temp/glew-preproc.c.

[mstorsjo]

I don't know this area so I can't comment on it from that perspective, but it does indeed speed up my case, to even faster than it was before the regression. On my system, it originally took 75 s to compile, 220 s after the regression, and now 62 s with this patch. So looking good in that aspect at least!

[NutshellySima]

Thanks for the patch! I believe that the modification here fulfills the precondition of calling mutation APIs of the DomTreeUpdater.
B.T.W., After seeing this patch, I recalled a not-merged patch, D54730, which has the same motivation and similar modifications.
I think "sorting updates so that insertions always happen before deletions" needs to be analyzed case-by-case, as there isn't enough evidence that the updating process will always be faster that way.

lib/Transforms/Utils/BasicBlockUtils.cpp

215 ↗

(On Diff #203442)

I would like the comment here explaining the order of updates matters the performance. :)

[asbirlea]

Add detalied comment.

[NutshellySima]

Thanks for the changes. LGTM.

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

if (isa<PHINode>(BB->front())) {
     FoldSingleEntryPHINodes(BB, MemDep);
   }
 
   // DTU update: Collect all the edges that exit BB.
   // These dominator edges will be redirected from Pred.
   std::vector<DominatorTree::UpdateType> Updates;
   if (DTU) {
     Updates.reserve(1 + (2 * succ_size(BB)));
-    Updates.push_back({DominatorTree::Delete, PredBB, BB});
-    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
-      Updates.push_back({DominatorTree::Delete, BB, *I});
+    // Add insert edges first. Experimentally, for the particular case of two
+    // blocks that can be merged, with a single successor and single predecessor
+    // respectively, it is beneficial to have all insert updates first. Deleting
+    // edges first may lead to unreachable blocks, followed by inserting edges
+    // making the blocks reachable again. Such DT updates lead to high compile
+    // times. We add inserts before deletes here to reduce compile time.
+    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
       // This successor of BB may already have PredBB as a predecessor.
       if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
         Updates.push_back({DominatorTree::Insert, PredBB, *I});
-    }
+    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
+      Updates.push_back({DominatorTree::Delete, BB, *I});
+    Updates.push_back({DominatorTree::Delete, PredBB, BB});
   }
 
   if (MSSAU)
     MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin()));
 
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();