Simplify function llvm::removeUnreachableBlocks() to avoid (re-)computation.

[rcorcs]

Summary

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.

[xbolva00]

llvm/lib/Transforms/Utils/Local.cpp

2232 ↗

(On Diff #222318)

Since Reachable is SmallPtrSet, count should be as good as find()

https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallPtrSet.h#L381

[hiraditya]

llvm/lib/Transforms/Utils/Local.cpp

2255 ↗

(On Diff #222318)

With this patch, it now seems like we are iterating on DeadBlockSet twice, is it possible to merge the two loops?

[rcorcs]

I have fused two loops. Now, for any execution path, only two loops over DeadBlockSet will be performed, instead of the previous worst-case of three loops.

[xbolva00]

llvm/lib/Transforms/Utils/Local.cpp

2232 ↗

(On Diff #222318)

Please “clang format” this patch

[rcorcs]

llvm/lib/Transforms/Utils/Local.cpp

2232 ↗

(On Diff #222318)

Indeed they have the same complexity. I prefer find() because it conveys a better idea of what is being done and its complexity, but I don't have a strong opinion about that. If you prefer, I can roll back to using count() instead.

[xbolva00]

llvm/lib/Transforms/Utils/Local.cpp

2232 ↗

(On Diff #222318)

I am fine with this (and I like find version more than count version).

[rcorcs]

This the same patch after running clang-format specifically to the llvm::removeUnreachableBlocks() function.

[fhahn]

Nice catch. This should be better overall, as instead of iterating over the whole function to delete dead blocks, we just iterate over the dead blocks. Even more work is skipped in case we have a DTU.

LGTM

llvm/lib/Transforms/Utils/Local.cpp

2231 ↗

(On Diff #222504)

In LLVM comments tend to be sentences, i.e. capitalize Skip and add a full stop.

2276 ↗

(On Diff #222504)

I think most code in LLVM tends to omit unnecessary braces for single statement blocks.

[rcorcs]

Addressed @fhahn 's comments.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

2229 ↗

(On Diff #222591)

This can now be just for (BasicBlock &BB : F) { I think, as we do not modify the BB list

[rcorcs]

Addressed @fhahn 's comment.
Indeed. That's much better.

[rcorcs]

Thanks everyone for your comments.

I don't have commit access. Unless anyone has another comment, I appreciate if one could commit this for me.

[fhahn]

I can commit it tomorrow

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

 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 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...
   if (Reachable.size() == F.size())
     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)
     MSSAU->removeBlocks(DeadBlockSet);
 
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references. Update DTU and LVI if available.
   std::vector<DominatorTree::UpdateType> Updates;
   for (auto *BB : DeadBlockSet) {
     for (BasicBlock *Successor : successors(BB)) {
       if (!DeadBlockSet.count(Successor))
         Successor->removePredecessor(BB);
       if (DTU)
         Updates.push_back({DominatorTree::Delete, BB, Successor});
     }
     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())
         BB->getInstList().pop_back();
       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);
     }
   }
 
   if (DTU) {
     DTU->applyUpdatesPermissive(Updates);
     bool Deleted = false;
     for (auto *BB : DeadBlockSet) {
       if (DTU->isBBPendingDeletion(BB))
         --NumRemoved;
       else
         Deleted = true;
       DTU->deleteBB(BB);
     }
     if (!Deleted)
       return false;
+  } else {
+    for (auto *BB : DeadBlockSet)
+      BB->eraseFromParent();
   }
+
   return true;
 }
 
 void llvm::combineMetadata(Instruction *K, const Instruction *J,
                            ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownNonDebugMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);