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
20using namespace clang;
21
22CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(
23    const CFG &cfg)
24    : analyzed(cfg.getNumBlockIDs(), false) {}
25
26bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
27                                          const CFGBlock *Dst) {
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.
42void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
43  SmallVector<const CFGBlock *, 11> worklist;
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.pop_back_val();
56
57    if (visited[block->getBlockID()])
58      continue;
59    visited[block->getBlockID()] = true;
60
61    // Update reachability information for this node -> Dst
62    if (!firstRun) {
63      // Don't insert Dst -> Dst unless it was a predecessor of itself
64      DstReachability[block->getBlockID()] = true;
65    }
66    else
67      firstRun = false;
68
69    // Add the predecessors to the worklist.
70    for (CFGBlock::const_pred_iterator i = block->pred_begin(),
71         e = block->pred_end(); i != e; ++i) {
72      if (*i)
73        worklist.push_back(*i);
74    }
75  }
76}
77