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