llvm/llvm/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/Analysis/LoopInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Support/CommandLine.h"

usingnamespacellvm;

// The max number of basic blocks explored during reachability analysis between
// two basic blocks. This is kept reasonably small to limit compile time when
// repeatedly used by clients of this analysis (such as captureTracking).
static cl::opt<unsigned> DefaultMaxBBsToExplore(
    "dom-tree-reachability-max-bbs-to-explore", cl::Hidden,
    cl::desc("Max number of BBs to explore for reachability analysis"),
    cl::init(32));

/// FindFunctionBackedges - Analyze the specified function to find all of the
/// loop backedges in the function and return them.  This is a relatively cheap
/// (compared to computing dominators and loop info) analysis.
///
/// The output is added to Result, as pairs of <from,to> edge info.
void llvm::FindFunctionBackedges(const Function &F,
     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) { … }

/// GetSuccessorNumber - Search for the specified successor of basic block BB
/// and return its position in the terminator instruction's list of
/// successors.  It is an error to call this with a block that is not a
/// successor.
unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,
    const BasicBlock *Succ) { … }

/// isCriticalEdge - 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 llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,
                          bool AllowIdenticalEdges) { … }

bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest,
                          bool AllowIdenticalEdges) { … }

// LoopInfo contains a mapping from basic block to the innermost loop. Find
// the outermost loop in the loop nest that contains BB.
static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) { … }

template <class StopSetT>
static bool isReachableImpl(SmallVectorImpl<BasicBlock *> &Worklist,
                            const StopSetT &StopSet,
                            const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
                            const DominatorTree *DT, const LoopInfo *LI) { … }

template <class T> class SingleEntrySet { … };

bool llvm::isPotentiallyReachableFromMany(
    SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB,
    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
    const LoopInfo *LI) { … }

bool llvm::isManyPotentiallyReachableFromMany(
    SmallVectorImpl<BasicBlock *> &Worklist,
    const SmallPtrSetImpl<const BasicBlock *> &StopSet,
    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
    const LoopInfo *LI) { … }

bool llvm::isPotentiallyReachable(
    const BasicBlock *A, const BasicBlock *B,
    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, 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) { … }