1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| //===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines a flow-sensitive, (mostly) path-insensitive reachability
// analysis based on Clang's CFGs. Clients can query if a given basic block
// is reachable within the CFG.
//
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallVector.h"
using namespace clang;
CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(
const CFG &cfg)
: analyzed(cfg.getNumBlockIDs(), false) {}
bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
const CFGBlock *Dst) {
const unsigned DstBlockID = Dst->getBlockID();
// If we haven't analyzed the destination node, run the analysis now
if (!analyzed[DstBlockID]) {
mapReachability(Dst);
analyzed[DstBlockID] = true;
}
// Return the cached result
return reachable[DstBlockID][Src->getBlockID()];
}
// Maps reachability to a common node by walking the predecessors of the
// destination node.
void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
SmallVector<const CFGBlock *, 11> worklist;
llvm::BitVector visited(analyzed.size());
ReachableSet &DstReachability = reachable[Dst->getBlockID()];
DstReachability.resize(analyzed.size(), false);
// Start searching from the destination node, since we commonly will perform
// multiple queries relating to a destination node.
worklist.push_back(Dst);
bool firstRun = true;
while (!worklist.empty()) {
const CFGBlock *block = worklist.pop_back_val();
if (visited[block->getBlockID()])
continue;
visited[block->getBlockID()] = true;
// Update reachability information for this node -> Dst
if (!firstRun) {
// Don't insert Dst -> Dst unless it was a predecessor of itself
DstReachability[block->getBlockID()] = true;
}
else
firstRun = false;
// Add the predecessors to the worklist.
for (CFGBlock::const_pred_iterator i = block->pred_begin(),
e = block->pred_end(); i != e; ++i) {
if (*i)
worklist.push_back(*i);
}
}
}
|