142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek//==- CFGReachabilityAnalysis.cpp - 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#include "llvm/ADT/SmallVector.h" 1742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 1842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek#include "clang/Analysis/CFG.h" 1942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 2042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenekusing namespace clang; 2142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 22af13d5b25b360e698cc1cf1055ad7d14e008e505Ted KremenekCFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) 2342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek : analyzed(cfg.getNumBlockIDs(), false) {} 2442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 25af13d5b25b360e698cc1cf1055ad7d14e008e505Ted Kremenekbool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 2642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek const CFGBlock *Dst) { 2742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 2842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek const unsigned DstBlockID = Dst->getBlockID(); 2942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 3042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // If we haven't analyzed the destination node, run the analysis now 3142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek if (!analyzed[DstBlockID]) { 3242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek mapReachability(Dst); 3342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek analyzed[DstBlockID] = true; 3442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek } 3542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 3642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // Return the cached result 3742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek return reachable[DstBlockID][Src->getBlockID()]; 3842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek} 3942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// Maps reachability to a common node by walking the predecessors of the 4142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek// destination node. 42af13d5b25b360e698cc1cf1055ad7d14e008e505Ted Kremenekvoid CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { 435f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const CFGBlock *, 11> worklist; 4442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek llvm::BitVector visited(analyzed.size()); 4542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek ReachableSet &DstReachability = reachable[Dst->getBlockID()]; 4742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek DstReachability.resize(analyzed.size(), false); 4842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 4942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // Start searching from the destination node, since we commonly will perform 5042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // multiple queries relating to a destination node. 5142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek worklist.push_back(Dst); 5242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek bool firstRun = true; 53344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm 54344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm while (!worklist.empty()) { 55344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm const CFGBlock *block = worklist.pop_back_val(); 56344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm 5742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek if (visited[block->getBlockID()]) 5842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek continue; 5942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek visited[block->getBlockID()] = true; 6042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 6142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // Update reachability information for this node -> Dst 6242461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek if (!firstRun) { 6342461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // Don't insert Dst -> Dst unless it was a predecessor of itself 6442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek DstReachability[block->getBlockID()] = true; 6542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek } 6642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek else 6742461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek firstRun = false; 6842461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek 6942461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek // Add the predecessors to the worklist. 7042461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek for (CFGBlock::const_pred_iterator i = block->pred_begin(), 7142461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek e = block->pred_end(); i != e; ++i) { 72651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (*i) 73651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines worklist.push_back(*i); 7442461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek } 7542461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek } 7642461eecee98fff3671b3c14ce10f1a9e18cc95cTed Kremenek} 77