1219069Sdim//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==// 2219069Sdim// 3219069Sdim// The LLVM Compiler Infrastructure 4219069Sdim// 5219069Sdim// This file is distributed under the University of Illinois Open Source 6219069Sdim// License. See LICENSE.TXT for details. 7219069Sdim// 8219069Sdim//===----------------------------------------------------------------------===// 9219069Sdim// 10219069Sdim// This file defines a flow-sensitive, (mostly) path-insensitive reachability 11219069Sdim// analysis based on Clang's CFGs. Clients can query if a given basic block 12219069Sdim// is reachable within the CFG. 13219069Sdim// 14219069Sdim//===----------------------------------------------------------------------===// 15219069Sdim 16219069Sdim#ifndef CLANG_ANALYSIS_CFG_REACHABILITY 17219069Sdim#define CLANG_ANALYSIS_CFG_REACHABILITY 18219069Sdim 19219069Sdim#include "llvm/ADT/BitVector.h" 20219069Sdim#include "llvm/ADT/DenseMap.h" 21219069Sdim 22219069Sdimnamespace clang { 23219069Sdim 24219069Sdimclass CFG; 25219069Sdimclass CFGBlock; 26219069Sdim 27219069Sdim// A class that performs reachability queries for CFGBlocks. Several internal 28219069Sdim// checks in this checker require reachability information. The requests all 29219069Sdim// tend to have a common destination, so we lazily do a predecessor search 30219069Sdim// from the destination node and cache the results to prevent work 31219069Sdim// duplication. 32221345Sdimclass CFGReverseBlockReachabilityAnalysis { 33219069Sdim typedef llvm::BitVector ReachableSet; 34219069Sdim typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap; 35219069Sdim ReachableSet analyzed; 36219069Sdim ReachableMap reachable; 37219069Sdimpublic: 38221345Sdim CFGReverseBlockReachabilityAnalysis(const CFG &cfg); 39219069Sdim 40219069Sdim /// Returns true if the block 'Dst' can be reached from block 'Src'. 41219069Sdim bool isReachable(const CFGBlock *Src, const CFGBlock *Dst); 42219069Sdim 43219069Sdimprivate: 44219069Sdim void mapReachability(const CFGBlock *Dst); 45219069Sdim}; 46219069Sdim 47219069Sdim} 48219069Sdim 49219069Sdim#endif 50