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; 53219069Sdim 54219069Sdim while (!worklist.empty()) { 55219069Sdim const CFGBlock *block = worklist.back(); 56219069Sdim worklist.pop_back(); 57219069Sdim 58219069Sdim if (visited[block->getBlockID()]) 59219069Sdim continue; 60219069Sdim visited[block->getBlockID()] = true; 61219069Sdim 62219069Sdim // Update reachability information for this node -> Dst 63219069Sdim if (!firstRun) { 64219069Sdim // Don't insert Dst -> Dst unless it was a predecessor of itself 65219069Sdim DstReachability[block->getBlockID()] = true; 66219069Sdim } 67219069Sdim else 68219069Sdim firstRun = false; 69219069Sdim 70219069Sdim // Add the predecessors to the worklist. 71219069Sdim for (CFGBlock::const_pred_iterator i = block->pred_begin(), 72219069Sdim e = block->pred_end(); i != e; ++i) { 73219069Sdim worklist.push_back(*i); 74219069Sdim } 75219069Sdim } 76219069Sdim} 77