CFGReachabilityAnalysis.cpp source code [clang_source_code/lib/Analysis/CFGReachabilityAnalysis.cpp]

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	: analyzed(cfg.getNumBlockIDs(), false) {}
25
26	bool 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.
42	void 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

clang::CFGReverseBlockReachabilityAnalysis::isReachable

clang::CFGReverseBlockReachabilityAnalysis::mapReachability

Clang Project