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
22namespace clang {
23
24class CFG;
25class 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.
32class CFGReverseBlockReachabilityAnalysis {
33  typedef llvm::BitVector ReachableSet;
34  typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap;
35  ReachableSet analyzed;
36  ReachableMap reachable;
37public:
38  CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
39
40  /// Returns true if the block 'Dst' can be reached from block 'Src'.
41  bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
42
43private:
44  void mapReachability(const CFGBlock *Dst);
45};
46
47}
48
49#endif
50