Add an optional list of blocks to avoid when looking for a path in isPotentiallyReachable.

[nicholas]

Summary

Add an optional list of blocks to avoid when looking for a path in isPotentiallyReachable.

The leads to some ambiguous overloads, so update three callers.

[asbirlea]

LGTM, modulo one nit. Thank you!

llvm/lib/Analysis/CFG.cpp

168 ↗

(On Diff #193144)

Could you comment the reasoning behind this for those not familiar with this code, to make it clear why this makes sense?
e.g.: "If Outer is found, we skip straight to the exit blocks below. Set it to nullptr here, to go the slow route and process BB's successors."

llvm/trunk/include/llvm/Analysis/CFG.h

 
 /// Return true if the specified edge is a critical edge. Critical edges are
 /// edges from a block with multiple successors to a block with multiple
 /// predecessors.
 ///
 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
                     bool AllowIdenticalEdges = false);
 
-/// Determine whether instruction 'To' is reachable from 'From',
-/// returning true if uncertain.
+/// Determine whether instruction 'To' is reachable from 'From', without passing
+/// through any blocks in ExclusionSet, returning true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been executed then
 /// 'To' can not be executed. Conservatively returns true.
 ///
 /// This function is linear with respect to the number of blocks in the CFG,
 /// walking down successors from From to reach To, with a fixed threshold.
 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of
 /// an entire loop of any number of blocks to be the same as the cost of a
 /// single block. DT reduces the cost by allowing the search to terminate when
 /// we find a block that dominates the block containing 'To'. DT is most useful
 /// on branchy code but not loops, and LI is most useful on code with loops but
 /// does not help on branchy code outside loops.
-bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
-                            const DominatorTree *DT = nullptr,
-                            const LoopInfo *LI = nullptr);
+bool isPotentiallyReachable(
+    const Instruction *From, const Instruction *To,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
+    const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Determine whether block 'To' is reachable from 'From', returning
 /// true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been reached then
 /// 'To' can not be executed. Conservatively returns true.
 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
                             const DominatorTree *DT = nullptr,
                             const LoopInfo *LI = nullptr);
 
 /// Determine whether there is at least one path from a block in
 /// 'Worklist' to 'StopBB', returning true if uncertain.
 ///
 /// Determine whether there is a path from at least one block in Worklist to
 /// StopBB within a single function. Returns false only if we can prove that
 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
 /// executed. Conservatively returns true.
 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
                                     BasicBlock *StopBB,
                                     const DominatorTree *DT = nullptr,
                                     const LoopInfo *LI = nullptr);
 
+/// Determine whether there is at least one path from a block in
+/// 'Worklist' to 'StopBB' without passing through any blocks in
+/// 'ExclusionSet', returning true if uncertain.
+///
+/// Determine whether there is a path from at least one block in Worklist to
+/// StopBB within a single function without passing through any of the blocks
+/// in 'ExclusionSet'. Returns false only if we can prove that once any block
+/// in 'Worklist' has been reached then 'StopBB' can not be executed.
+/// Conservatively returns true.
+bool isPotentiallyReachableFromMany(
+    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
+    const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
+
 /// Return true if the control flow in \p RPOTraversal is irreducible.
 ///
 /// This is a generic implementation to detect CFG irreducibility based on loop
 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
 /// function is only recommended when loop info analysis is available. If loop
 /// info analysis isn't available, please, don't compute it explicitly for this

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
 
   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
     return false;
 
   // Make sure that the visited phis cannot reach the Value. This ensures that
   // the Values cannot come from different iterations of a potential cycle the
   // phi nodes could be involved in.
   for (auto *P : VisitedPhiBBs)
-    if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
+    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
       return false;
 
   return true;
 }
 
 /// Computes the symbolic difference between two de-composed GEPs.
 ///
 /// Dest and Src are the variable indices from two decomposed GetElementPtr

llvm/trunk/lib/Analysis/CFG.cpp

 //===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This family of functions performs analyses on basic blocks, and instructions
 // contained within basic blocks.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 /// FindFunctionBackedges - Analyze the specified function to find all of the
 /// loop backedges in the function and return them.  This is a relatively cheap
static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
   const Loop *L = LI->getLoopFor(BB);
   if (L) {
     while (const Loop *Parent = L->getParentLoop())
       L = Parent;
   }
   return L;
 }
 
-// True if there is a loop which contains both BB1 and BB2.
-static bool loopContainsBoth(const LoopInfo *LI,
-                             const BasicBlock *BB1, const BasicBlock *BB2) {
-  const Loop *L1 = getOutermostLoop(LI, BB1);
-  const Loop *L2 = getOutermostLoop(LI, BB2);
-  return L1 != nullptr && L1 == L2;
-}
-
 bool llvm::isPotentiallyReachableFromMany(
     SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
-    const DominatorTree *DT, const LoopInfo *LI) {
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+    const LoopInfo *LI) {
   // When the stop block is unreachable, it's dominated from everywhere,
   // regardless of whether there's a path between the two blocks.
   if (DT && !DT->isReachableFromEntry(StopBB))
     DT = nullptr;
 
+  // We can't skip directly from a block that dominates the stop block if the
+  // exclusion block is potentially in between.
+  if (ExclusionSet && !ExclusionSet->empty())
+    DT = nullptr;
+
+  // Normally any block in a loop is reachable from any other block in a loop,
+  // however excluded blocks might partition the body of a loop to make that
+  // untrue.
+  SmallPtrSet<const Loop *, 8> LoopsWithHoles;
+  if (LI && ExclusionSet) {
+    for (auto BB : *ExclusionSet) {
+      if (const Loop *L = getOutermostLoop(LI, BB))
+        LoopsWithHoles.insert(L);
+    }
+  }
+
+  const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
+
   // Limit the number of blocks we visit. The goal is to avoid run-away compile
   // times on large CFGs without hampering sensible code. Arbitrarily chosen.
   unsigned Limit = 32;
   SmallPtrSet<const BasicBlock*, 32> Visited;
   do {
     BasicBlock *BB = Worklist.pop_back_val();
     if (!Visited.insert(BB).second)
       continue;
     if (BB == StopBB)
       return true;
+    if (ExclusionSet && ExclusionSet->count(BB))
+      continue;
     if (DT && DT->dominates(BB, StopBB))
       return true;
-    if (LI && loopContainsBoth(LI, BB, StopBB))
+
+    const Loop *Outer = nullptr;
+    if (LI) {
+      Outer = getOutermostLoop(LI, BB);
+      // If we're in a loop with a hole, not all blocks in the loop are
+      // reachable from all other blocks. That implies we can't simply jump to
+      // the loop's exit blocks, as that exit might need to pass through an
+      // excluded block. Clear Outer so we process BB's successors.
+      if (LoopsWithHoles.count(Outer))
+        Outer = nullptr;
+      if (StopLoop && Outer == StopLoop)
         return true;
+    }
 
     if (!--Limit) {
       // We haven't been able to prove it one way or the other. Conservatively
       // answer true -- that there is potentially a path.
       return true;
     }
 
-    if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) {
+    if (Outer) {
       // All blocks in a single loop are reachable from all other blocks. From
       // any of these blocks, we can skip directly to the exits of the loop,
       // ignoring any other blocks inside the loop body.
       Outer->getExitBlocks(Worklist);
     } else {
       Worklist.append(succ_begin(BB), succ_end(BB));
     }
   } while (!Worklist.empty());
 
   // We have exhausted all possible paths and are certain that 'To' can not be
   // reached from 'From'.
   return false;
 }
 
 bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
                                   const DominatorTree *DT, const LoopInfo *LI) {
   assert(A->getParent() == B->getParent() &&
          "This analysis is function-local!");
 
   SmallVector<BasicBlock*, 32> Worklist;
   Worklist.push_back(const_cast<BasicBlock*>(A));
 
   return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
-                                        DT, LI);
+                                        nullptr, DT, LI);
 }
 
-bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
-                                  const DominatorTree *DT, const LoopInfo *LI) {
+bool llvm::isPotentiallyReachable(
+    const Instruction *A, const Instruction *B,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+    const LoopInfo *LI) {
   assert(A->getParent()->getParent() == B->getParent()->getParent() &&
          "This analysis is function-local!");
 
   SmallVector<BasicBlock*, 32> Worklist;
 
   if (A->getParent() == B->getParent()) {
     // The same block case is special because it's the only time we're looking
     // within a single block to see which instruction comes first. Once we
bool llvm::isPotentiallyReachable(
   } else {
     Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
   }
 
   if (DT) {
     if (DT->isReachableFromEntry(A->getParent()) !=
         DT->isReachableFromEntry(B->getParent()))
       return false;
+    if (!ExclusionSet || ExclusionSet->empty()) {
       if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
           DT->isReachableFromEntry(B->getParent()))
         return true;
       if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
           DT->isReachableFromEntry(A->getParent()))
         return false;
     }
+  }
 
   return isPotentiallyReachableFromMany(
-      Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
+      Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
 }

llvm/trunk/lib/Analysis/CaptureTracking.cpp

bool isSafeToPrune(Instruction *I) {
         //  (1) BB is an entry block or have no successors.
         //  (2) There's no path coming back through BB successors.
         if (BB == &BB->getParent()->getEntryBlock() ||
             !BB->getTerminator()->getNumSuccessors())
           return true;
 
         SmallVector<BasicBlock*, 32> Worklist;
         Worklist.append(succ_begin(BB), succ_end(BB));
-        return !isPotentiallyReachableFromMany(Worklist, BB, DT);
+        return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, DT);
       }
 
       // If the value is defined in the same basic block as use and BeforeHere,
       // there is no need to explore the use if BeforeHere dominates use.
       // Check whether there is a path from I to BeforeHere.
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
-          !isPotentiallyReachable(I, BeforeHere, DT))
+          !isPotentiallyReachable(I, BeforeHere, nullptr, DT))
         return true;
 
       return false;
     }
 
     bool shouldExplore(const Use *U) override {
       Instruction *I = cast<Instruction>(U->getUser());
 

llvm/trunk/lib/CodeGen/DwarfEHPrepare.cpp

 /// unreachable and then simplify those blocks.
 size_t DwarfEHPrepare::pruneUnreachableResumes(
     Function &Fn, SmallVectorImpl<ResumeInst *> &Resumes,
     SmallVectorImpl<LandingPadInst *> &CleanupLPads) {
   BitVector ResumeReachable(Resumes.size());
   size_t ResumeIndex = 0;
   for (auto *RI : Resumes) {
     for (auto *LP : CleanupLPads) {
-      if (isPotentiallyReachable(LP, RI, DT)) {
+      if (isPotentiallyReachable(LP, RI, nullptr, DT)) {
         ResumeReachable.set(ResumeIndex);
         break;
       }
     }
     ++ResumeIndex;
   }
 
   // If everything is reachable, there is no change.

llvm/trunk/unittests/Analysis/CFGTest.cpp

 //===- CFGTest.cpp - CFG tests --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Module.h"
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
         else if (I->getName() == "B")
           B = &*I;
       }
     }
     if (A == nullptr)
       report_fatal_error("@test must have an instruction %A");
     if (B == nullptr)
       report_fatal_error("@test must have an instruction %B");
+
+    assert(ExclusionSet.empty());
+    for (auto I = F->begin(), E = F->end(); I != E; ++I) {
+      if (I->hasName() && I->getName().startswith("excluded"))
+        ExclusionSet.insert(&*I);
+    }
   }
 
   void ExpectPath(bool ExpectedResult) {
     static char ID;
     class IsPotentiallyReachableTestPass : public FunctionPass {
      public:
-      IsPotentiallyReachableTestPass(bool ExpectedResult,
-                                     Instruction *A, Instruction *B)
-          : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
+       IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A,
+                                      Instruction *B,
+                                      SmallPtrSet<BasicBlock *, 4> ExclusionSet)
+           : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B),
+             ExclusionSet(ExclusionSet) {}
 
        static int initialize() {
-        PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
-                                    "", &ID, nullptr, true, true);
+         PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "",
+                                     &ID, nullptr, true, true);
          PassRegistry::getPassRegistry()->registerPass(*PI, false);
          initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
          initializeDominatorTreeWrapperPassPass(
              *PassRegistry::getPassRegistry());
          return 0;
       }
 
       void getAnalysisUsage(AnalysisUsage &AU) const override {
         AU.setPreservesAll();
         AU.addRequired<LoopInfoWrapperPass>();
         AU.addRequired<DominatorTreeWrapperPass>();
       }
 
       bool runOnFunction(Function &F) override {
         if (!F.hasName() || F.getName() != "test")
           return false;
 
         LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
         DominatorTree *DT =
             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-        EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr),
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI),
                   ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
         return false;
       }
       bool ExpectedResult;
       Instruction *A, *B;
+      SmallPtrSet<BasicBlock *, 4> ExclusionSet;
     };
 
     static int initialize = IsPotentiallyReachableTestPass::initialize();
     (void)initialize;
 
     IsPotentiallyReachableTestPass *P =
-        new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
+        new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet);
     legacy::PassManager PM;
     PM.add(P);
     PM.run(*M);
   }
 
   LLVMContext Context;
   std::unique_ptr<Module> M;
   Instruction *A, *B;
+  SmallPtrSet<BasicBlock *, 4> ExclusionSet;
 };
 
 }
 
 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
   ParseAssembly(
       "define void @test() {\n"
       "entry:\n"
ParseAssembly("define void @test() {\n"
                 "  %B = bitcast i8 undef to i8\n"
                 "  br label %not.reachable.2\n"
                 "not.reachable.2:\n"
                 "  %A = bitcast i8 undef to i8\n"
                 "  ret void\n"
                 "}");
   ExpectPath(false);
 }
+
+TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) {
+  ParseAssembly("define void @test() {\n"
+                "entry:\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br label %excluded\n"
+                "excluded:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) {
+  ParseAssembly("declare i1 @switch()\n"
+                "\n"
+                "define void @test() {\n"
+                "entry:\n"
+                "  %x = call i1 @switch()\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br i1 %x, label %excluded.1, label %excluded.2\n"
+                "excluded.1:\n"
+                "  br label %exit\n"
+                "excluded.2:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) {
+  ParseAssembly("declare i1 @switch()\n"
+                "\n"
+                "define void @test() {\n"
+                "entry:\n"
+                "  %x = call i1 @switch()\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br i1 %x, label %excluded, label %diamond\n"
+                "excluded:\n"
+                "  br label %exit\n"
+                "diamond:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(true);
+}