Ted Kremenek | 42461ee | 2011-02-23 01:51:59 +0000 | [diff] [blame] | 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 | |
Ted Kremenek | af13d5b | 2011-03-19 01:00:33 +0000 | [diff] [blame] | 22 | CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) |
Ted Kremenek | 42461ee | 2011-02-23 01:51:59 +0000 | [diff] [blame] | 23 | : analyzed(cfg.getNumBlockIDs(), false) {} |
| 24 | |
Ted Kremenek | af13d5b | 2011-03-19 01:00:33 +0000 | [diff] [blame] | 25 | bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, |
Ted Kremenek | 42461ee | 2011-02-23 01:51:59 +0000 | [diff] [blame] | 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. |
Ted Kremenek | af13d5b | 2011-03-19 01:00:33 +0000 | [diff] [blame] | 42 | void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { |
Chris Lattner | 5f9e272 | 2011-07-23 10:55:15 +0000 | [diff] [blame^] | 43 | SmallVector<const CFGBlock *, 11> worklist; |
Ted Kremenek | 42461ee | 2011-02-23 01:51:59 +0000 | [diff] [blame] | 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.back(); |
| 56 | worklist.pop_back(); |
| 57 | |
| 58 | if (visited[block->getBlockID()]) |
| 59 | continue; |
| 60 | visited[block->getBlockID()] = true; |
| 61 | |
| 62 | // Update reachability information for this node -> Dst |
| 63 | if (!firstRun) { |
| 64 | // Don't insert Dst -> Dst unless it was a predecessor of itself |
| 65 | DstReachability[block->getBlockID()] = true; |
| 66 | } |
| 67 | else |
| 68 | firstRun = false; |
| 69 | |
| 70 | // Add the predecessors to the worklist. |
| 71 | for (CFGBlock::const_pred_iterator i = block->pred_begin(), |
| 72 | e = block->pred_end(); i != e; ++i) { |
| 73 | worklist.push_back(*i); |
| 74 | } |
| 75 | } |
| 76 | } |