1//==- CFGReachabilityAnalysis.cpp - Basic reachability analysis --*- C++ -*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a flow-sensitive, (mostly) path-insensitive reachability 11// analysis based on Clang's CFGs. Clients can query if a given basic block 12// is reachable within the CFG. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/ADT/SmallVector.h" 17#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 18#include "clang/Analysis/CFG.h" 19 20using namespace clang; 21 22CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) 23 : analyzed(cfg.getNumBlockIDs(), false) {} 24 25bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 26 const CFGBlock *Dst) { 27 28 const unsigned DstBlockID = Dst->getBlockID(); 29 30 // If we haven't analyzed the destination node, run the analysis now 31 if (!analyzed[DstBlockID]) { 32 mapReachability(Dst); 33 analyzed[DstBlockID] = true; 34 } 35 36 // Return the cached result 37 return reachable[DstBlockID][Src->getBlockID()]; 38} 39 40// Maps reachability to a common node by walking the predecessors of the 41// destination node. 42void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { 43 SmallVector<const CFGBlock *, 11> worklist; 44 llvm::BitVector visited(analyzed.size()); 45 46 ReachableSet &DstReachability = reachable[Dst->getBlockID()]; 47 DstReachability.resize(analyzed.size(), false); 48 49 // Start searching from the destination node, since we commonly will perform 50 // multiple queries relating to a destination node. 51 worklist.push_back(Dst); 52 bool firstRun = true; 53 54 while (!worklist.empty()) { 55 const CFGBlock *block = worklist.pop_back_val(); 56 57 if (visited[block->getBlockID()]) 58 continue; 59 visited[block->getBlockID()] = true; 60 61 // Update reachability information for this node -> Dst 62 if (!firstRun) { 63 // Don't insert Dst -> Dst unless it was a predecessor of itself 64 DstReachability[block->getBlockID()] = true; 65 } 66 else 67 firstRun = false; 68 69 // Add the predecessors to the worklist. 70 for (CFGBlock::const_pred_iterator i = block->pred_begin(), 71 e = block->pred_end(); i != e; ++i) { 72 worklist.push_back(*i); 73 } 74 } 75} 76