1219069Sdim//==- CFGReachabilityAnalysis.cpp - 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#include "llvm/ADT/SmallVector.h" 17219069Sdim#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 18219069Sdim#include "clang/Analysis/CFG.h" 19219069Sdim 20219069Sdimusing namespace clang; 21219069Sdim 22221345SdimCFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) 23219069Sdim : analyzed(cfg.getNumBlockIDs(), false) {} 24219069Sdim 25221345Sdimbool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 26219069Sdim const CFGBlock *Dst) { 27219069Sdim 28219069Sdim const unsigned DstBlockID = Dst->getBlockID(); 29219069Sdim 30219069Sdim // If we haven't analyzed the destination node, run the analysis now 31219069Sdim if (!analyzed[DstBlockID]) { 32219069Sdim mapReachability(Dst); 33219069Sdim analyzed[DstBlockID] = true; 34219069Sdim } 35219069Sdim 36219069Sdim // Return the cached result 37219069Sdim return reachable[DstBlockID][Src->getBlockID()]; 38219069Sdim} 39219069Sdim 40219069Sdim// Maps reachability to a common node by walking the predecessors of the 41219069Sdim// destination node. 42221345Sdimvoid CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { 43226633Sdim SmallVector<const CFGBlock *, 11> worklist; 44219069Sdim llvm::BitVector visited(analyzed.size()); 45219069Sdim 46219069Sdim ReachableSet &DstReachability = reachable[Dst->getBlockID()]; 47219069Sdim DstReachability.resize(analyzed.size(), false); 48219069Sdim 49219069Sdim // Start searching from the destination node, since we commonly will perform 50219069Sdim // multiple queries relating to a destination node. 51219069Sdim worklist.push_back(Dst); 52219069Sdim bool firstRun = true; 53263508Sdim 54263508Sdim while (!worklist.empty()) { 55263508Sdim const CFGBlock *block = worklist.pop_back_val(); 56263508Sdim 57219069Sdim if (visited[block->getBlockID()]) 58219069Sdim continue; 59219069Sdim visited[block->getBlockID()] = true; 60219069Sdim 61219069Sdim // Update reachability information for this node -> Dst 62219069Sdim if (!firstRun) { 63219069Sdim // Don't insert Dst -> Dst unless it was a predecessor of itself 64219069Sdim DstReachability[block->getBlockID()] = true; 65219069Sdim } 66219069Sdim else 67219069Sdim firstRun = false; 68219069Sdim 69219069Sdim // Add the predecessors to the worklist. 70219069Sdim for (CFGBlock::const_pred_iterator i = block->pred_begin(), 71219069Sdim e = block->pred_end(); i != e; ++i) { 72219069Sdim worklist.push_back(*i); 73219069Sdim } 74219069Sdim } 75219069Sdim} 76