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 #include "llvm/ADT/SmallVector.h" 19 20 using namespace clang; 21 22 CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis( 23 const CFG &cfg) 24 : analyzed(cfg.getNumBlockIDs(), false) {} 25 26 bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 27 const CFGBlock *Dst) { 28 const unsigned DstBlockID = Dst->getBlockID(); 29 30 // If we haven't analyzed the destination node, run the analysis now 31 if (!analyzed[DstBlockID]) { 32 mapReachability(Dst); 33 analyzed[DstBlockID] = true; 34 } 35 36 // Return the cached result 37 return reachable[DstBlockID][Src->getBlockID()]; 38 } 39 40 // Maps reachability to a common node by walking the predecessors of the 41 // destination node. 42 void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { 43 SmallVector<const CFGBlock *, 11> worklist; 44 llvm::BitVector visited(analyzed.size()); 45 46 ReachableSet &DstReachability = reachable[Dst->getBlockID()]; 47 DstReachability.resize(analyzed.size(), false); 48 49 // Start searching from the destination node, since we commonly will perform 50 // multiple queries relating to a destination node. 51 worklist.push_back(Dst); 52 bool firstRun = true; 53 54 while (!worklist.empty()) { 55 const CFGBlock *block = worklist.pop_back_val(); 56 57 if (visited[block->getBlockID()]) 58 continue; 59 visited[block->getBlockID()] = true; 60 61 // Update reachability information for this node -> Dst 62 if (!firstRun) { 63 // Don't insert Dst -> Dst unless it was a predecessor of itself 64 DstReachability[block->getBlockID()] = true; 65 } 66 else 67 firstRun = false; 68 69 // Add the predecessors to the worklist. 70 for (CFGBlock::const_pred_iterator i = block->pred_begin(), 71 e = block->pred_end(); i != e; ++i) { 72 if (*i) 73 worklist.push_back(*i); 74 } 75 } 76 } 77