lib/Analysis/CFG.cpp

   1 //===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This family of functions performs analyses on basic blocks, and instructions
  10 // contained within basic blocks.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/CFG.h"
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/SmallSet.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/IR/Dominators.h"
  19
  20 using namespace llvm;
  21
  22 /// FindFunctionBackedges - Analyze the specified function to find all of the
  23 /// loop backedges in the function and return them.  This is a relatively cheap
  24 /// (compared to computing dominators and loop info) analysis.
  25 ///
  26 /// The output is added to Result, as pairs of <from,to> edge info.
  27 void llvm::FindFunctionBackedges(const Function &F,
  28      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
  29   const BasicBlock *BB = &F.getEntryBlock();
  30   if (succ_empty(BB))
  31     return;
  32
  33   SmallPtrSet<const BasicBlock*, 8> Visited;
  34   SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
  35   SmallPtrSet<const BasicBlock*, 8> InStack;
  36
  37   Visited.insert(BB);
  38   VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
  39   InStack.insert(BB);
  40   do {
  41     std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
  42     const BasicBlock *ParentBB = Top.first;
  43     succ_const_iterator &I = Top.second;
  44
  45     bool FoundNew = false;
  46     while (I != succ_end(ParentBB)) {
  47       BB = *I++;
  48       if (Visited.insert(BB).second) {
  49         FoundNew = true;
  50         break;
  51       }
  52       // Successor is in VisitStack, it's a back edge.
  53       if (InStack.count(BB))
  54         Result.push_back(std::make_pair(ParentBB, BB));
  55     }
  56
  57     if (FoundNew) {
  58       // Go down one level if there is a unvisited successor.
  59       InStack.insert(BB);
  60       VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
  61     } else {
  62       // Go up one level.
  63       InStack.erase(VisitStack.pop_back_val().first);
  64     }
  65   } while (!VisitStack.empty());
  66 }
  67
  68 /// GetSuccessorNumber - Search for the specified successor of basic block BB
  69 /// and return its position in the terminator instruction's list of
  70 /// successors.  It is an error to call this with a block that is not a
  71 /// successor.
  72 unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,
  73     const BasicBlock *Succ) {
  74   const Instruction *Term = BB->getTerminator();
  75 #ifndef NDEBUG
  76   unsigned e = Term->getNumSuccessors();
  77 #endif
  78   for (unsigned i = 0; ; ++i) {
  79     assert(i != e && "Didn't find edge?");
  80     if (Term->getSuccessor(i) == Succ)
  81       return i;
  82   }
  83 }
  84
  85 /// isCriticalEdge - Return true if the specified edge is a critical edge.
  86 /// Critical edges are edges from a block with multiple successors to a block
  87 /// with multiple predecessors.
  88 bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,
  89                           bool AllowIdenticalEdges) {
  90   assert(TI->isTerminator() && "Must be a terminator to have successors!");
  91   assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
  92   if (TI->getNumSuccessors() == 1) return false;
  93
  94   const BasicBlock *Dest = TI->getSuccessor(SuccNum);
  95   const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
  96
  97   // If there is more than one predecessor, this is a critical edge...
  98   assert(I != E && "No preds, but we have an edge to the block?");
  99   const BasicBlock *FirstPred = *I;
 100   ++I;        // Skip one edge due to the incoming arc from TI.
 101   if (!AllowIdenticalEdges)
 102     return I != E;
 103
 104   // If AllowIdenticalEdges is true, then we allow this edge to be considered
 105   // non-critical iff all preds come from TI's block.
 106   for (; I != E; ++I)
 107     if (*I != FirstPred)
 108       return true;
 109   return false;
 110 }
 111
 112 // LoopInfo contains a mapping from basic block to the innermost loop. Find
 113 // the outermost loop in the loop nest that contains BB.
 114 static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
 115   const Loop *L = LI->getLoopFor(BB);
 116   if (L) {
 117     while (const Loop *Parent = L->getParentLoop())
 118       L = Parent;
 119   }
 120   return L;
 121 }
 122
 123 bool llvm::isPotentiallyReachableFromMany(
 124     SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
 125     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
 126     const LoopInfo *LI) {
 127   // When the stop block is unreachable, it's dominated from everywhere,
 128   // regardless of whether there's a path between the two blocks.
 129   if (DT && !DT->isReachableFromEntry(StopBB))
 130     DT = nullptr;
 131
 132   // We can't skip directly from a block that dominates the stop block if the
 133   // exclusion block is potentially in between.
 134   if (ExclusionSet && !ExclusionSet->empty())
 135     DT = nullptr;
 136
 137   // Normally any block in a loop is reachable from any other block in a loop,
 138   // however excluded blocks might partition the body of a loop to make that
 139   // untrue.
 140   SmallPtrSet<const Loop *, 8> LoopsWithHoles;
 141   if (LI && ExclusionSet) {
 142     for (auto BB : *ExclusionSet) {
 143       if (const Loop *L = getOutermostLoop(LI, BB))
 144         LoopsWithHoles.insert(L);
 145     }
 146   }
 147
 148   const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
 149
 150   // Limit the number of blocks we visit. The goal is to avoid run-away compile
 151   // times on large CFGs without hampering sensible code. Arbitrarily chosen.
 152   unsigned Limit = 32;
 153   SmallPtrSet<const BasicBlock*, 32> Visited;
 154   do {
 155     BasicBlock *BB = Worklist.pop_back_val();
 156     if (!Visited.insert(BB).second)
 157       continue;
 158     if (BB == StopBB)
 159       return true;
 160     if (ExclusionSet && ExclusionSet->count(BB))
 161       continue;
 162     if (DT && DT->dominates(BB, StopBB))
 163       return true;
 164
 165     const Loop *Outer = nullptr;
 166     if (LI) {
 167       Outer = getOutermostLoop(LI, BB);
 168       // If we're in a loop with a hole, not all blocks in the loop are
 169       // reachable from all other blocks. That implies we can't simply jump to
 170       // the loop's exit blocks, as that exit might need to pass through an
 171       // excluded block. Clear Outer so we process BB's successors.
 172       if (LoopsWithHoles.count(Outer))
 173         Outer = nullptr;
 174       if (StopLoop && Outer == StopLoop)
 175         return true;
 176     }
 177
 178     if (!--Limit) {
 179       // We haven't been able to prove it one way or the other. Conservatively
 180       // answer true -- that there is potentially a path.
 181       return true;
 182     }
 183
 184     if (Outer) {
 185       // All blocks in a single loop are reachable from all other blocks. From
 186       // any of these blocks, we can skip directly to the exits of the loop,
 187       // ignoring any other blocks inside the loop body.
 188       Outer->getExitBlocks(Worklist);
 189     } else {
 190       Worklist.append(succ_begin(BB), succ_end(BB));
 191     }
 192   } while (!Worklist.empty());
 193
 194   // We have exhausted all possible paths and are certain that 'To' can not be
 195   // reached from 'From'.
 196   return false;
 197 }
 198
 199 bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
 200                                   const DominatorTree *DT, const LoopInfo *LI) {
 201   assert(A->getParent() == B->getParent() &&
 202          "This analysis is function-local!");
 203
 204   SmallVector<BasicBlock*, 32> Worklist;
 205   Worklist.push_back(const_cast<BasicBlock*>(A));
 206
 207   return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
 208                                         nullptr, DT, LI);
 209 }
 210
 211 bool llvm::isPotentiallyReachable(
 212     const Instruction *A, const Instruction *B,
 213     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
 214     const LoopInfo *LI) {
 215   assert(A->getParent()->getParent() == B->getParent()->getParent() &&
 216          "This analysis is function-local!");
 217
 218   SmallVector<BasicBlock*, 32> Worklist;
 219
 220   if (A->getParent() == B->getParent()) {
 221     // The same block case is special because it's the only time we're looking
 222     // within a single block to see which instruction comes first. Once we
 223     // start looking at multiple blocks, the first instruction of the block is
 224     // reachable, so we only need to determine reachability between whole
 225     // blocks.
 226     BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
 227
 228     // If the block is in a loop then we can reach any instruction in the block
 229     // from any other instruction in the block by going around a backedge.
 230     if (LI && LI->getLoopFor(BB) != nullptr)
 231       return true;
 232
 233     // Linear scan, start at 'A', see whether we hit 'B' or the end first.
 234     for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); I != E;
 235          ++I) {
 236       if (&*I == B)
 237         return true;
 238     }
 239
 240     // Can't be in a loop if it's the entry block -- the entry block may not
 241     // have predecessors.
 242     if (BB == &BB->getParent()->getEntryBlock())
 243       return false;
 244
 245     // Otherwise, continue doing the normal per-BB CFG walk.
 246     Worklist.append(succ_begin(BB), succ_end(BB));
 247
 248     if (Worklist.empty()) {
 249       // We've proven that there's no path!
 250       return false;
 251     }
 252   } else {
 253     Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
 254   }
 255
 256   if (DT) {
 257     if (DT->isReachableFromEntry(A->getParent()) &&
 258         !DT->isReachableFromEntry(B->getParent()))
 259       return false;
 260     if (!ExclusionSet || ExclusionSet->empty()) {
 261       if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
 262           DT->isReachableFromEntry(B->getParent()))
 263         return true;
 264       if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
 265           DT->isReachableFromEntry(A->getParent()))
 266         return false;
 267     }
 268   }
 269
 270   return isPotentiallyReachableFromMany(
 271       Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
 272 }