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
19using namespace clang;
20
21CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(
22 const CFG &cfg)
23 : analyzed(cfg.getNumBlockIDs(), false) {}
24
25bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
26 const CFGBlock *Dst) {
27 const unsigned DstBlockID = Dst->getBlockID();
28
29 // If we haven't analyzed the destination node, run the analysis now
30 if (!analyzed[DstBlockID]) {
31 mapReachability(Dst);
32 analyzed[DstBlockID] = true;
33 }
34
35 // Return the cached result
36 return reachable[DstBlockID][Src->getBlockID()];
37}
38
39// Maps reachability to a common node by walking the predecessors of the
40// destination node.
41void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
42 SmallVector<const CFGBlock *, 11> worklist;
43 llvm::BitVector visited(analyzed.size());
44
45 ReachableSet &DstReachability = reachable[Dst->getBlockID()];
46 DstReachability.resize(N: analyzed.size(), t: false);
47
48 // Start searching from the destination node, since we commonly will perform
49 // multiple queries relating to a destination node.
50 worklist.push_back(Elt: Dst);
51 bool firstRun = true;
52
53 while (!worklist.empty()) {
54 const CFGBlock *block = worklist.pop_back_val();
55
56 if (visited[block->getBlockID()])
57 continue;
58 visited[block->getBlockID()] = true;
59
60 // Update reachability information for this node -> Dst
61 if (!firstRun) {
62 // Don't insert Dst -> Dst unless it was a predecessor of itself
63 DstReachability[block->getBlockID()] = true;
64 }
65 else
66 firstRun = false;
67
68 // Add the predecessors to the worklist.
69 for (CFGBlock::const_pred_iterator i = block->pred_begin(),
70 e = block->pred_end(); i != e; ++i) {
71 if (*i)
72 worklist.push_back(Elt: *i);
73 }
74 }
75}
76