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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines a flow-sensitive, (mostly) path-insensitive reachability 10 // analysis based on Clang's CFGs. Clients can query if a given basic block 11 // 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 19 using namespace clang; 20 21 CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis( 22 const CFG &cfg) 23 : analyzed(cfg.getNumBlockIDs(), false) {} 24 25 bool 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 now 30 if (!analyzed[DstBlockID]) { 31 mapReachability(Dst); 32 analyzed[DstBlockID] = true; 33 } 34 35 // Return the cached result 36 return reachable[DstBlockID][Src->getBlockID()]; 37 } 38 39 // Maps reachability to a common node by walking the predecessors of the 40 // destination node. 41 void 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 perform 49 // 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 -> Dst 61 if (!firstRun) { 62 // Don't insert Dst -> Dst unless it was a predecessor of itself 63 DstReachability[block->getBlockID()] = true; 64 } 65 else 66 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