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