clang  10.0.0svn
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 
20 using 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.
42 void 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.
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 }
pred_iterator pred_end()
Definition: CFG.h:939
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:925
unsigned getBlockID() const
Definition: CFG.h:1075
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1226
#define false
Definition: stdbool.h:17
bool isReachable(const CFGBlock *Src, const CFGBlock *Dst)
Returns true if the block 'Dst' can be reached from block 'Src'.
pred_iterator pred_begin()
Definition: CFG.h:938
Dataflow Directional Tag Classes.