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