clang 19.0.0git
CFGReachabilityAnalysis.cpp
Go to the documentation of this file.
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
16#include "clang/Analysis/CFG.h"
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/SmallVector.h"
19
20using namespace clang;
21
23 const CFG &cfg)
24 : analyzed(cfg.getNumBlockIDs(), false) {}
25
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) {
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.
71 e = block->pred_end(); i != e; ++i) {
72 if (*i)
73 worklist.push_back(*i);
74 }
75 }
76}
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
pred_iterator pred_end()
Definition: CFG.h:967
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:953
pred_iterator pred_begin()
Definition: CFG.h:966
unsigned getBlockID() const
Definition: CFG.h:1105
bool isReachable(const CFGBlock *Src, const CFGBlock *Dst)
Returns true if the block 'Dst' can be reached from block 'Src'.
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
The JSON file list parser is used to communicate input to InstallAPI.
#define false
Definition: stdbool.h:22