Analysis/Analyses/CFGReachabilityAnalysis.h

0001 //===- CFGReachabilityAnalysis.h - Basic reachability analysis --*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines a flow-sensitive, (mostly) path-insensitive reachability
0010 // analysis based on Clang's CFGs.  Clients can query if a given basic block
0011 // is reachable within the CFG.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
0016 #define LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
0017
0018 #include "llvm/ADT/BitVector.h"
0019 #include "llvm/ADT/DenseMap.h"
0020
0021 namespace clang {
0022
0023 class CFG;
0024 class CFGBlock;
0025
0026 // A class that performs reachability queries for CFGBlocks. Several internal
0027 // checks in this checker require reachability information. The requests all
0028 // tend to have a common destination, so we lazily do a predecessor search
0029 // from the destination node and cache the results to prevent work
0030 // duplication.
0031 class CFGReverseBlockReachabilityAnalysis {
0032   using ReachableSet = llvm::BitVector;
0033   using ReachableMap = llvm::DenseMap<unsigned, ReachableSet>;
0034
0035   ReachableSet analyzed;
0036   ReachableMap reachable;
0037
0038 public:
0039   CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
0040
0041   /// Returns true if the block 'Dst' can be reached from block 'Src'.
0042   bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
0043
0044 private:
0045   void mapReachability(const CFGBlock *Dst);
0046 };
0047
0048 } // namespace clang
0049
0050 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H