[Local] Refactor llvm::removeUnreachableBlocks

[bjope]

Summary

Refactored llvm::removeUnreachableBlocks, including the
markAliveBlocks helper. The part in markAliveBlocks that
examines instructions inside a basic block, and that can
change instructions to unreachable, was factored out to
a new rewriteUnreachableInstrs helper.

Also added a new boolean parameter to removeUnreachableBlocks
to be able to skip the rewriteUnreachableInstrs part.

[bjope]

I was going to use this in another patch, but it's outdated now so I'll abandon this.

include/llvm/Analysis/Utils/Local.h

 /// successor.
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
 void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
-/// Returns true if any basic block was removed.
+/// \param ExamineInstructions  If true, then reachable instructions will be
+///                             analysed and when possible instructions are
+///                             rewritten into `unreachable`. This can result
+///                             in more blocks being unreachable compared to
+///                             just following the BB successor lists.
+///
+/// \returns True if any basic block was removed (or if any instructions were
+///          rewritten due to 'ExamineInstructions')
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
-                             DeferredDominance *DDT = nullptr);
+                             DeferredDominance *DDT = nullptr,
+                             bool ExamineInstructions = true);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.

lib/Transforms/Utils/Local.cpp

BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
   // updates the CallGraph if present, because it uses a WeakTrackingVH.
   CI->replaceAllUsesWith(II);
 
   // Delete the original call
   Split->getInstList().pop_front();
   return Split;
 }
 
-static bool markAliveBlocks(Function &F,
-                            SmallPtrSetImpl<BasicBlock*> &Reachable,
+static bool rewriteUnreachableInstrs(Function &F,
+                                     BasicBlock *BB,
                                      DeferredDominance *DDT = nullptr) {
-  SmallVector<BasicBlock*, 128> Worklist;
-  BasicBlock *BB = &F.front();
-  Worklist.push_back(BB);
-  Reachable.insert(BB);
   bool Changed = false;
-  do {
-    BB = Worklist.pop_back_val();
-
-    // Do a quick scan of the basic block, turning any obviously unreachable
-    // instructions into LLVM unreachable insts.  The instruction combining pass
-    // canonicalizes unreachable insts into stores to null or undef.
-    for (Instruction &I : *BB) {
-      // Assumptions that are known to be false are equivalent to unreachable.
-      // Also, if the condition is undefined, then we make the choice most
-      // beneficial to the optimizer, and choose that to also be unreachable.
-      if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
-        if (II->getIntrinsicID() == Intrinsic::assume) {
-          if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
-            // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(II, false, false, DDT);
-            Changed = true;
-            break;
-          }
-        }
 
-        if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
-          // A call to the guard intrinsic bails out of the current compilation
-          // unit if the predicate passed to it is false.  If the predicate is a
-          // constant false, then we know the guard will bail out of the current
-          // compile unconditionally, so all code following it is dead.
-          //
-          // Note: unlike in llvm.assume, it is not "obviously profitable" for
-          // guards to treat `undef` as `false` since a guard on `undef` can
-          // still be useful for widening.
-          if (match(II->getArgOperand(0), m_Zero()))
-            if (!isa<UnreachableInst>(II->getNextNode())) {
-              changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false,
-                                  false, DDT);
-              Changed = true;
-              break;
-            }
-        }
-      }
 
-      if (auto *CI = dyn_cast<CallInst>(&I)) {
-        Value *Callee = CI->getCalledValue();
-        if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-          changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT);
-          Changed = true;
-          break;
-        }
-        if (CI->doesNotReturn()) {
-          // If we found a call to a no-return function, insert an unreachable
-          // instruction after it.  Make sure there isn't *already* one there
-          // though.
-          if (!isa<UnreachableInst>(CI->getNextNode())) {
-            // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(CI->getNextNode(), false, false, DDT);
-            Changed = true;
-          }
-          break;
-        }
-      }
 
-      // Store to undef and store to null are undefined and used to signal that
-      // they should be changed to unreachable by passes that can't modify the
-      // CFG.
-      if (auto *SI = dyn_cast<StoreInst>(&I)) {
-        // Don't touch volatile stores.
-        if (SI->isVolatile()) continue;
 
-        Value *Ptr = SI->getOperand(1);
 
-        if (isa<UndefValue>(Ptr) ||
-            (isa<ConstantPointerNull>(Ptr) &&
-             SI->getPointerAddressSpace() == 0)) {
-          changeToUnreachable(SI, true, false, DDT);
-          Changed = true;
-          break;
-        }
-      }
-    }
 
-    TerminatorInst *Terminator = BB->getTerminator();
-    if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
-      // Turn invokes that call 'nounwind' functions into ordinary calls.
-      Value *Callee = II->getCalledValue();
-      if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-        changeToUnreachable(II, true, false, DDT);
-        Changed = true;
-      } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
-        if (II->use_empty() && II->onlyReadsMemory()) {
-          // jump to the normal destination branch.
-          BasicBlock *NormalDestBB = II->getNormalDest();
-          BasicBlock *UnwindDestBB = II->getUnwindDest();
-          BranchInst::Create(NormalDestBB, II);
-          UnwindDestBB->removePredecessor(II->getParent());
-          II->eraseFromParent();
-          if (DDT)
-            DDT->deleteEdge(BB, UnwindDestBB);
-        } else
-          changeToCall(II, DDT);
-        Changed = true;
-      }
-    } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
-      // Remove catchpads which cannot be reached.
-      struct CatchPadDenseMapInfo {
-        static CatchPadInst *getEmptyKey() {
-          return DenseMapInfo<CatchPadInst *>::getEmptyKey();
-        }
 
-        static CatchPadInst *getTombstoneKey() {
-          return DenseMapInfo<CatchPadInst *>::getTombstoneKey();
-        }
 
-        static unsigned getHashValue(CatchPadInst *CatchPad) {
-          return static_cast<unsigned>(hash_combine_range(
                                          CatchPad->value_op_begin(), CatchPad->value_op_end()));
-        }
 
-        static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
-          if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
-              RHS == getEmptyKey() || RHS == getTombstoneKey())
-            return LHS == RHS;
-          return LHS->isIdenticalTo(RHS);
-        }
-      };
 
-      // Set of unique CatchPads.
-      SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
-                    CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
-          HandlerSet;
-      detail::DenseSetEmpty Empty;
-      for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
-                                             E = CatchSwitch->handler_end();
-           I != E; ++I) {
-        BasicBlock *HandlerBB = *I;
-        auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
-        if (!HandlerSet.insert({CatchPad, Empty}).second) {
-          CatchSwitch->removeHandler(I);
-          --I;
-          --E;
-          Changed = true;
-        }
-      }
-    }
 
-    Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT);
+
+  return Changed;
+}
+
+static bool markAliveBlocks(Function &F,
+                            SmallPtrSetImpl<BasicBlock*> &Reachable,
+                            bool ExamineInstructions,
+                            DeferredDominance *DDT = nullptr) {
+  SmallVector<BasicBlock*, 128> Worklist;
+  BasicBlock *BB = &F.front();
+  Worklist.push_back(BB);
+  Reachable.insert(BB);
+  bool Changed = false;
+  do {
+    BB = Worklist.pop_back_val();
+
+    if (ExamineInstructions)
+      Changed |= rewriteUnreachableInstrs(F, BB, DDT);
+
     for (BasicBlock *Successor : successors(BB))
       if (Reachable.insert(Successor).second)
         Worklist.push_back(Successor);
   } while (!Worklist.empty());
   return Changed;
 }
 
 void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) {
if (DDT)
     DDT->deleteEdge(BB, UnwindDest);
 }
 
 /// 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,
-                                   DeferredDominance *DDT) {
+                                   DeferredDominance *DDT,
+                                   bool ExamineInstructions) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
-  bool Changed = markAliveBlocks(F, Reachable, DDT);
+  bool Changed = markAliveBlocks(F, Reachable, ExamineInstructions, DDT);
 
   // 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();