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 typedef llvm::BitVector ReachableSet; 34 typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap; 35 ReachableSet analyzed; 36 ReachableMap reachable; 37 public: 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 43 private: 44 void mapReachability(const CFGBlock *Dst); 45 }; 46 47 } 48 49 #endif 50