372 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This family of functions performs analyses on basic blocks, and instructions10// 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#include "llvm/IR/IntrinsicInst.h"18#include "llvm/Support/CommandLine.h"19 20using namespace llvm;21 22// The max number of basic blocks explored during reachability analysis between23// two basic blocks. This is kept reasonably small to limit compile time when24// repeatedly used by clients of this analysis (such as captureTracking).25static cl::opt<unsigned> DefaultMaxBBsToExplore(26 "dom-tree-reachability-max-bbs-to-explore", cl::Hidden,27 cl::desc("Max number of BBs to explore for reachability analysis"),28 cl::init(32));29 30/// FindFunctionBackedges - Analyze the specified function to find all of the31/// loop backedges in the function and return them. This is a relatively cheap32/// (compared to computing dominators and loop info) analysis.33///34/// The output is added to Result, as pairs of <from,to> edge info.35void llvm::FindFunctionBackedges(const Function &F,36 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {37 const BasicBlock *BB = &F.getEntryBlock();38 if (succ_empty(BB))39 return;40 41 SmallPtrSet<const BasicBlock*, 8> Visited;42 SmallVector<std::pair<const BasicBlock *, const_succ_iterator>, 8> VisitStack;43 SmallPtrSet<const BasicBlock*, 8> InStack;44 45 Visited.insert(BB);46 VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));47 InStack.insert(BB);48 do {49 std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.back();50 const BasicBlock *ParentBB = Top.first;51 const_succ_iterator &I = Top.second;52 53 bool FoundNew = false;54 while (I != succ_end(ParentBB)) {55 BB = *I++;56 if (Visited.insert(BB).second) {57 FoundNew = true;58 break;59 }60 // Successor is in VisitStack, it's a back edge.61 if (InStack.count(BB))62 Result.push_back(std::make_pair(ParentBB, BB));63 }64 65 if (FoundNew) {66 // Go down one level if there is a unvisited successor.67 InStack.insert(BB);68 VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));69 } else {70 // Go up one level.71 InStack.erase(VisitStack.pop_back_val().first);72 }73 } while (!VisitStack.empty());74}75 76/// GetSuccessorNumber - Search for the specified successor of basic block BB77/// and return its position in the terminator instruction's list of78/// successors. It is an error to call this with a block that is not a79/// successor.80unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,81 const BasicBlock *Succ) {82 const Instruction *Term = BB->getTerminator();83#ifndef NDEBUG84 unsigned e = Term->getNumSuccessors();85#endif86 for (unsigned i = 0; ; ++i) {87 assert(i != e && "Didn't find edge?");88 if (Term->getSuccessor(i) == Succ)89 return i;90 }91}92 93/// isCriticalEdge - Return true if the specified edge is a critical edge.94/// Critical edges are edges from a block with multiple successors to a block95/// with multiple predecessors.96bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,97 bool AllowIdenticalEdges) {98 assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");99 return isCriticalEdge(TI, TI->getSuccessor(SuccNum), AllowIdenticalEdges);100}101 102bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest,103 bool AllowIdenticalEdges) {104 assert(TI->isTerminator() && "Must be a terminator to have successors!");105 if (TI->getNumSuccessors() == 1) return false;106 107 assert(is_contained(predecessors(Dest), TI->getParent()) &&108 "No edge between TI's block and Dest.");109 110 const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);111 112 // If there is more than one predecessor, this is a critical edge...113 assert(I != E && "No preds, but we have an edge to the block?");114 const BasicBlock *FirstPred = *I;115 ++I; // Skip one edge due to the incoming arc from TI.116 if (!AllowIdenticalEdges)117 return I != E;118 119 // If AllowIdenticalEdges is true, then we allow this edge to be considered120 // non-critical iff all preds come from TI's block.121 for (; I != E; ++I)122 if (*I != FirstPred)123 return true;124 return false;125}126 127// LoopInfo contains a mapping from basic block to the innermost loop. Find128// the outermost loop in the loop nest that contains BB.129static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {130 const Loop *L = LI->getLoopFor(BB);131 return L ? L->getOutermostLoop() : nullptr;132}133 134template <class StopSetT>135static bool isReachableImpl(SmallVectorImpl<BasicBlock *> &Worklist,136 const StopSetT &StopSet,137 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,138 const DominatorTree *DT, const LoopInfo *LI) {139 // When a stop block is unreachable, it's dominated from everywhere,140 // regardless of whether there's a path between the two blocks.141 if (DT) {142 for (auto *BB : StopSet) {143 if (!DT->isReachableFromEntry(BB)) {144 DT = nullptr;145 break;146 }147 }148 }149 150 // We can't skip directly from a block that dominates the stop block if the151 // exclusion block is potentially in between.152 if (ExclusionSet && !ExclusionSet->empty())153 DT = nullptr;154 155 // Normally any block in a loop is reachable from any other block in a loop,156 // however excluded blocks might partition the body of a loop to make that157 // untrue.158 SmallPtrSet<const Loop *, 8> LoopsWithHoles;159 if (LI && ExclusionSet) {160 for (auto *BB : *ExclusionSet) {161 if (const Loop *L = getOutermostLoop(LI, BB))162 LoopsWithHoles.insert(L);163 }164 }165 166 SmallPtrSet<const Loop *, 2> StopLoops;167 if (LI) {168 for (auto *StopSetBB : StopSet) {169 if (const Loop *L = getOutermostLoop(LI, StopSetBB))170 StopLoops.insert(L);171 }172 }173 174 unsigned Limit = DefaultMaxBBsToExplore;175 SmallPtrSet<const BasicBlock*, 32> Visited;176 do {177 BasicBlock *BB = Worklist.pop_back_val();178 if (!Visited.insert(BB).second)179 continue;180 if (StopSet.contains(BB))181 return true;182 if (ExclusionSet && ExclusionSet->count(BB))183 continue;184 if (DT) {185 if (llvm::any_of(StopSet, [&](const BasicBlock *StopBB) {186 return DT->dominates(BB, StopBB);187 }))188 return true;189 }190 191 const Loop *Outer = nullptr;192 if (LI) {193 Outer = getOutermostLoop(LI, BB);194 // If we're in a loop with a hole, not all blocks in the loop are195 // reachable from all other blocks. That implies we can't simply jump to196 // the loop's exit blocks, as that exit might need to pass through an197 // excluded block. Clear Outer so we process BB's successors.198 if (LoopsWithHoles.count(Outer))199 Outer = nullptr;200 if (StopLoops.contains(Outer))201 return true;202 }203 204 if (!--Limit) {205 // We haven't been able to prove it one way or the other. Conservatively206 // answer true -- that there is potentially a path.207 return true;208 }209 210 if (Outer) {211 // All blocks in a single loop are reachable from all other blocks. From212 // any of these blocks, we can skip directly to the exits of the loop,213 // ignoring any other blocks inside the loop body.214 Outer->getExitBlocks(Worklist);215 } else {216 Worklist.append(succ_begin(BB), succ_end(BB));217 }218 } while (!Worklist.empty());219 220 // We have exhausted all possible paths and are certain that 'To' can not be221 // reached from 'From'.222 return false;223}224 225template <class T> class SingleEntrySet {226public:227 using const_iterator = const T *;228 229 SingleEntrySet(T Elem) : Elem(Elem) {}230 231 bool contains(T Other) const { return Elem == Other; }232 233 const_iterator begin() const { return &Elem; }234 const_iterator end() const { return &Elem + 1; }235 236private:237 T Elem;238};239 240bool llvm::isPotentiallyReachableFromMany(241 SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB,242 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,243 const LoopInfo *LI) {244 return isReachableImpl<SingleEntrySet<const BasicBlock *>>(245 Worklist, SingleEntrySet<const BasicBlock *>(StopBB), ExclusionSet, DT,246 LI);247}248 249bool llvm::isManyPotentiallyReachableFromMany(250 SmallVectorImpl<BasicBlock *> &Worklist,251 const SmallPtrSetImpl<const BasicBlock *> &StopSet,252 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,253 const LoopInfo *LI) {254 return isReachableImpl<SmallPtrSetImpl<const BasicBlock *>>(255 Worklist, StopSet, ExclusionSet, DT, LI);256}257 258bool llvm::isPotentiallyReachable(259 const BasicBlock *A, const BasicBlock *B,260 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,261 const LoopInfo *LI) {262 assert(A->getParent() == B->getParent() &&263 "This analysis is function-local!");264 265 if (DT) {266 if (DT->isReachableFromEntry(A) && !DT->isReachableFromEntry(B))267 return false;268 if (!ExclusionSet || ExclusionSet->empty()) {269 if (A->isEntryBlock() && DT->isReachableFromEntry(B))270 return true;271 if (B->isEntryBlock() && DT->isReachableFromEntry(A))272 return false;273 }274 }275 276 SmallVector<BasicBlock*, 32> Worklist;277 Worklist.push_back(const_cast<BasicBlock*>(A));278 279 return isPotentiallyReachableFromMany(Worklist, B, ExclusionSet, DT, LI);280}281 282bool llvm::isPotentiallyReachable(283 const Instruction *A, const Instruction *B,284 const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,285 const LoopInfo *LI) {286 assert(A->getParent()->getParent() == B->getParent()->getParent() &&287 "This analysis is function-local!");288 289 if (A->getParent() == B->getParent()) {290 // The same block case is special because it's the only time we're looking291 // within a single block to see which instruction comes first. Once we292 // start looking at multiple blocks, the first instruction of the block is293 // reachable, so we only need to determine reachability between whole294 // blocks.295 BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());296 297 // If the block is in a loop then we can reach any instruction in the block298 // from any other instruction in the block by going around a backedge.299 if (LI && LI->getLoopFor(BB) != nullptr)300 return true;301 302 // If A comes before B, then B is definitively reachable from A.303 if (A == B || A->comesBefore(B))304 return true;305 306 // Can't be in a loop if it's the entry block -- the entry block may not307 // have predecessors.308 if (BB->isEntryBlock())309 return false;310 311 // Otherwise, continue doing the normal per-BB CFG walk.312 SmallVector<BasicBlock*, 32> Worklist;313 Worklist.append(succ_begin(BB), succ_end(BB));314 if (Worklist.empty()) {315 // We've proven that there's no path!316 return false;317 }318 319 return isPotentiallyReachableFromMany(Worklist, B->getParent(),320 ExclusionSet, DT, LI);321 }322 323 return isPotentiallyReachable(324 A->getParent(), B->getParent(), ExclusionSet, DT, LI);325}326 327static bool instructionDoesNotReturn(const Instruction &I) {328 if (auto *CB = dyn_cast<CallBase>(&I))329 return CB->hasFnAttr(Attribute::NoReturn);330 return false;331}332 333// A basic block can only return if it terminates with a ReturnInst and does not334// contain calls to noreturn functions.335static bool basicBlockCanReturn(const BasicBlock &BB) {336 if (!isa<ReturnInst>(BB.getTerminator()))337 return false;338 return none_of(BB, instructionDoesNotReturn);339}340 341// FIXME: this doesn't handle recursion.342bool llvm::canReturn(const Function &F) {343 SmallVector<const BasicBlock *, 16> Worklist;344 SmallPtrSet<const BasicBlock *, 16> Visited;345 346 Visited.insert(&F.front());347 Worklist.push_back(&F.front());348 349 do {350 const BasicBlock *BB = Worklist.pop_back_val();351 if (basicBlockCanReturn(*BB))352 return true;353 for (const BasicBlock *Succ : successors(BB))354 if (Visited.insert(Succ).second)355 Worklist.push_back(Succ);356 } while (!Worklist.empty());357 358 return false;359}360 361bool llvm::isPresplitCoroSuspendExitEdge(const BasicBlock &Src,362 const BasicBlock &Dest) {363 assert(Src.getParent() == Dest.getParent());364 if (!Src.getParent()->isPresplitCoroutine())365 return false;366 if (auto *SW = dyn_cast<SwitchInst>(Src.getTerminator()))367 if (auto *Intr = dyn_cast<IntrinsicInst>(SW->getCondition()))368 return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&369 SW->getDefaultDest() == &Dest;370 return false;371}372