1 //==- CFGReachabilityAnalysis.cpp - Basic reachability analysis --*- C++ -*-==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines a flow-sensitive, (mostly) path-insensitive reachability 11 // analysis based on Clang's CFGs. Clients can query if a given basic block 12 // is reachable within the CFG. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/ADT/SmallVector.h" 17 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 18 #include "clang/Analysis/CFG.h" 19 20 using namespace clang; 21 22 CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) 23 : analyzed(cfg.getNumBlockIDs(), false) {} 24 25 bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, 26 const CFGBlock *Dst) { 27 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
