1341825Sdim//===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===// 2219069Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6219069Sdim// 7219069Sdim//===----------------------------------------------------------------------===// 8219069Sdim// 9219069Sdim// This file defines a flow-sensitive, (mostly) path-insensitive reachability 10219069Sdim// analysis based on Clang's CFGs. Clients can query if a given basic block 11219069Sdim// is reachable within the CFG. 12219069Sdim// 13219069Sdim//===----------------------------------------------------------------------===// 14219069Sdim 15219069Sdim#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 16219069Sdim#include "clang/Analysis/CFG.h" 17341825Sdim#include "llvm/ADT/BitVector.h" 18341825Sdim#include "llvm/ADT/SmallVector.h" 19219069Sdim 20219069Sdimusing namespace clang; 21219069Sdim 22341825SdimCFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis( 23341825Sdim const CFG &cfg) 24341825Sdim : analyzed(cfg.getNumBlockIDs(), false) {} 25219069Sdim 26221345Sdimbool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 27219069Sdim const CFGBlock *Dst) { 28341825Sdim 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 } 35341825Sdim 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()); 45341825Sdim 46219069Sdim ReachableSet &DstReachability = reachable[Dst->getBlockID()]; 47219069Sdim DstReachability.resize(analyzed.size(), false); 48341825Sdim 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; 53261991Sdim 54261991Sdim while (!worklist.empty()) { 55261991Sdim const CFGBlock *block = worklist.pop_back_val(); 56261991Sdim 57219069Sdim if (visited[block->getBlockID()]) 58219069Sdim continue; 59219069Sdim visited[block->getBlockID()] = true; 60341825Sdim 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; 68341825Sdim 69219069Sdim // Add the predecessors to the worklist. 70341825Sdim for (CFGBlock::const_pred_iterator i = block->pred_begin(), 71219069Sdim e = block->pred_end(); i != e; ++i) { 72276479Sdim if (*i) 73276479Sdim worklist.push_back(*i); 74219069Sdim } 75219069Sdim } 76219069Sdim} 77