commit 167b0529be766a85db3c0811607ac60f821670ff
author Florian Hahn <flo@fhahn.com> Wed Oct 02 07:37:41 2019 +0000
committer Florian Hahn <flo@fhahn.com> Wed Oct 02 07:37:41 2019 +0000
tree e703085c499920aaae4d5b00d5701a4f25202188
parent 1c57143742b1deab32ac96cfd24c6b9dc9868a21

[Local] Simplify function removeUnreachableBlocks() to avoid (re-)computation.

Two small changes in llvm::removeUnreachableBlocks() to avoid unnecessary (re-)computation.

First, replace the use of count() with find(), which has better time complexity.

Second, because we have already computed the set of dead blocks, replace the second loop over all basic blocks to a loop only over the already computed dead blocks. This simplifies the loop and avoids recomputation.

Patch by Rodrigo Caetano Rocha <rcor.cs@gmail.com>

Reviewers: efriedma, spatel, fhahn, xbolva00

Reviewed By: fhahn, xbolva00

Differential Revision: https://reviews.llvm.org/D68191

llvm-svn: 373429

llvm/lib/Transforms/Utils/Local.cpp

diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index 2285b6c..eabf4bf 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -2215,7 +2215,7 @@
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
                                    DomTreeUpdater *DTU,
                                    MemorySSAUpdater *MSSAU) {
-  SmallPtrSet<BasicBlock*, 16> Reachable;
+  SmallPtrSet<BasicBlock *, 16> Reachable;
   bool Changed = markAliveBlocks(F, Reachable, DTU);
 
   // If there are unreachable blocks in the CFG...
@@ -2223,14 +2223,14 @@
     return Changed;
 
   assert(Reachable.size() < F.size());
-  NumRemoved += F.size()-Reachable.size();
+  NumRemoved += F.size() - Reachable.size();
 
   SmallSetVector<BasicBlock *, 8> DeadBlockSet;
-  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
-    auto *BB = &*I;
-    if (Reachable.count(BB))
+  for (BasicBlock &BB : F) {
+    // Skip reachable basic blocks
+    if (Reachable.find(&BB) != Reachable.end())
       continue;
-    DeadBlockSet.insert(BB);
+    DeadBlockSet.insert(&BB);
   }
 
   if (MSSAU)
@@ -2249,13 +2249,6 @@
     if (LVI)
       LVI->eraseBlock(BB);
     BB->dropAllReferences();
-  }
-  for (Function::iterator I = ++F.begin(); I != F.end();) {
-    auto *BB = &*I;
-    if (Reachable.count(BB)) {
-      ++I;
-      continue;
-    }
     if (DTU) {
       // Remove the terminator of BB to clear the successor list of BB.
       if (BB->getTerminator())
@@ -2263,9 +2256,6 @@
       new UnreachableInst(BB->getContext(), BB);
       assert(succ_empty(BB) && "The successor list of BB isn't empty before "
                                "applying corresponding DTU updates.");
-      ++I;
-    } else {
-      I = F.getBasicBlockList().erase(I);
     }
   }
 
@@ -2281,7 +2271,11 @@
     }
     if (!Deleted)
       return false;
+  } else {
+    for (auto *BB : DeadBlockSet)
+      BB->eraseFromParent();
   }
+
   return true;
 }