contrib/llvm/tools/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h

   1 //===- CFGReachabilityAnalysis.h - Basic reachability analysis --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a flow-sensitive, (mostly) path-insensitive reachability
  11 // analysis based on Clang's CFGs.  Clients can query if a given basic block
  12 // is reachable within the CFG.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
  17 #define LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
  18
  19 #include "llvm/ADT/BitVector.h"
  20 #include "llvm/ADT/DenseMap.h"
  21
  22 namespace clang {
  23
  24 class CFG;
  25 class CFGBlock;
  26
  27 // A class that performs reachability queries for CFGBlocks. Several internal
  28 // checks in this checker require reachability information. The requests all
  29 // tend to have a common destination, so we lazily do a predecessor search
  30 // from the destination node and cache the results to prevent work
  31 // duplication.
  32 class CFGReverseBlockReachabilityAnalysis {
  33   using ReachableSet = llvm::BitVector;
  34   using ReachableMap = llvm::DenseMap<unsigned, ReachableSet>;
  35
  36   ReachableSet analyzed;
  37   ReachableMap reachable;
  38
  39 public:
  40   CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
  41
  42   /// Returns true if the block 'Dst' can be reached from block 'Src'.
  43   bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
  44
  45 private:
  46   void mapReachability(const CFGBlock *Dst);
  47 };
  48
  49 } // namespace clang
  50
  51 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H