76 lines · cpp
1//===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a flow-sensitive, (mostly) path-insensitive reachability10// analysis based on Clang's CFGs. Clients can query if a given basic block11// is reachable within the CFG.12//13//===----------------------------------------------------------------------===//14 15#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"16#include "clang/Analysis/CFG.h"17#include "llvm/ADT/BitVector.h"18 19using namespace clang;20 21CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(22 const CFG &cfg)23 : analyzed(cfg.getNumBlockIDs(), false) {}24 25bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,26 const CFGBlock *Dst) {27 const unsigned DstBlockID = Dst->getBlockID();28 29 // If we haven't analyzed the destination node, run the analysis now30 if (!analyzed[DstBlockID]) {31 mapReachability(Dst);32 analyzed[DstBlockID] = true;33 }34 35 // Return the cached result36 return reachable[DstBlockID][Src->getBlockID()];37}38 39// Maps reachability to a common node by walking the predecessors of the40// destination node.41void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {42 SmallVector<const CFGBlock *, 11> worklist;43 llvm::BitVector visited(analyzed.size());44 45 ReachableSet &DstReachability = reachable[Dst->getBlockID()];46 DstReachability.resize(analyzed.size(), false);47 48 // Start searching from the destination node, since we commonly will perform49 // multiple queries relating to a destination node.50 worklist.push_back(Dst);51 bool firstRun = true;52 53 while (!worklist.empty()) {54 const CFGBlock *block = worklist.pop_back_val();55 56 if (visited[block->getBlockID()])57 continue;58 visited[block->getBlockID()] = true;59 60 // Update reachability information for this node -> Dst61 if (!firstRun) {62 // Don't insert Dst -> Dst unless it was a predecessor of itself63 DstReachability[block->getBlockID()] = true;64 }65 else66 firstRun = false;67 68 // Add the predecessors to the worklist.69 for (CFGBlock::const_pred_iterator i = block->pred_begin(),70 e = block->pred_end(); i != e; ++i) {71 if (*i)72 worklist.push_back(*i);73 }74 }75}76