/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/CFGReachabilityAnalysis.cpp
Line | Count | Source |
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 | 10.9k | : analyzed(cfg.getNumBlockIDs(), false) {} |
25 | | |
26 | | bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, |
27 | 14.6k | const CFGBlock *Dst) { |
28 | 14.6k | const unsigned DstBlockID = Dst->getBlockID(); |
29 | | |
30 | | // If we haven't analyzed the destination node, run the analysis now |
31 | 14.6k | if (!analyzed[DstBlockID]) { |
32 | 11.1k | mapReachability(Dst); |
33 | 11.1k | analyzed[DstBlockID] = true; |
34 | 11.1k | } |
35 | | |
36 | | // Return the cached result |
37 | 14.6k | return reachable[DstBlockID][Src->getBlockID()]; |
38 | 14.6k | } |
39 | | |
40 | | // Maps reachability to a common node by walking the predecessors of the |
41 | | // destination node. |
42 | 11.1k | void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { |
43 | 11.1k | SmallVector<const CFGBlock *, 11> worklist; |
44 | 11.1k | llvm::BitVector visited(analyzed.size()); |
45 | | |
46 | 11.1k | ReachableSet &DstReachability = reachable[Dst->getBlockID()]; |
47 | 11.1k | 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 | 11.1k | worklist.push_back(Dst); |
52 | 11.1k | bool firstRun = true; |
53 | | |
54 | 94.4k | while (!worklist.empty()) { |
55 | 83.3k | const CFGBlock *block = worklist.pop_back_val(); |
56 | | |
57 | 83.3k | if (visited[block->getBlockID()]) |
58 | 10.6k | continue; |
59 | 72.6k | visited[block->getBlockID()] = true; |
60 | | |
61 | | // Update reachability information for this node -> Dst |
62 | 72.6k | if (!firstRun) { |
63 | | // Don't insert Dst -> Dst unless it was a predecessor of itself |
64 | 61.5k | DstReachability[block->getBlockID()] = true; |
65 | 61.5k | } |
66 | 11.1k | else |
67 | 11.1k | firstRun = false; |
68 | | |
69 | | // Add the predecessors to the worklist. |
70 | 72.6k | for (CFGBlock::const_pred_iterator i = block->pred_begin(), |
71 | 148k | e = block->pred_end(); i != e; ++i75.4k ) { |
72 | 75.4k | if (*i) |
73 | 72.1k | worklist.push_back(*i); |
74 | 75.4k | } |
75 | 72.6k | } |
76 | 11.1k | } |