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 21namespace clang { 22 23class CFG; 24class 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. 31class CFGReverseBlockReachabilityAnalysis { 32 using ReachableSet = llvm::BitVector; 33 using ReachableMap = llvm::DenseMap<unsigned, ReachableSet>; 34 35 ReachableSet analyzed; 36 ReachableMap reachable; 37 38public: 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 44private: 45 void mapReachability(const CFGBlock *Dst); 46}; 47 48} // namespace clang 49 50#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H 51