1 //==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #ifndef CLANG_ANALYSIS_CFG_REACHABILITY
17 #define CLANG_ANALYSIS_CFG_REACHABILITY
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DenseMap.h"
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
32 class CFGReverseBlockReachabilityAnalysis {
33 typedef llvm::BitVector ReachableSet;
34 typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap;
35 ReachableSet analyzed;
36 ReachableMap reachable;
38 CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
40 /// Returns true if the block 'Dst' can be reached from block 'Src'.
41 bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
44 void mapReachability(const CFGBlock *Dst);