142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==// 242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// 342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// The LLVM Compiler Infrastructure 442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// 542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// This file is distributed under the University of Illinois Open Source 642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// License. See LICENSE.TXT for details. 742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// 842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek//===----------------------------------------------------------------------===// 942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// 1042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// This file defines a flow-sensitive, (mostly) path-insensitive reachability 1142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// analysis based on Clang's CFGs. Clients can query if a given basic block 1242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// is reachable within the CFG. 1342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// 1442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek//===----------------------------------------------------------------------===// 1542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 1642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#ifndef CLANG_ANALYSIS_CFG_REACHABILITY 1742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#define CLANG_ANALYSIS_CFG_REACHABILITY 1842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 1942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#include "llvm/ADT/BitVector.h" 2042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#include "llvm/ADT/DenseMap.h" 2142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 2242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremeneknamespace clang { 2342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 2442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenekclass CFG; 2542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenekclass CFGBlock; 2642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 2742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// A class that performs reachability queries for CFGBlocks. Several internal 2842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// checks in this checker require reachability information. The requests all 2942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// tend to have a common destination, so we lazily do a predecessor search 3042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// from the destination node and cache the results to prevent work 3142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// duplication. 32af13d5b25b360e698cc1cf1055ad7d14e008e505Ted Kremenekclass CFGReverseBlockReachabilityAnalysis { 3342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek typedef llvm::BitVector ReachableSet; 3442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap; 3542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek ReachableSet analyzed; 3642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek ReachableMap reachable; 3742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenekpublic: 38af13d5b25b360e698cc1cf1055ad7d14e008e505Ted Kremenek CFGReverseBlockReachabilityAnalysis(const CFG &cfg); 3942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek /// Returns true if the block 'Dst' can be reached from block 'Src'. 4142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek bool isReachable(const CFGBlock *Src, const CFGBlock *Dst); 4242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenekprivate: 4442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek void mapReachability(const CFGBlock *Dst); 4542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek}; 4642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek} 4842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#endif 50