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 
CFGReverseBlockReachabilityAnalysis(const CFG & cfg)22 CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg)
23   : analyzed(cfg.getNumBlockIDs(), false) {}
24 
isReachable(const CFGBlock * Src,const CFGBlock * Dst)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.
mapReachability(const CFGBlock * Dst)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