clang  8.0.0svn
CFGReachabilityAnalysis.cpp
Go to the documentation of this file.
1 //===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines a flow-sensitive, (mostly) path-insensitive reachability
11 // analysis based on Clang's CFGs. Clients can query if a given basic block
12 // is reachable within the CFG.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "clang/Analysis/CFG.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/SmallVector.h"
20 
21 using namespace clang;
22 
24  const CFG &cfg)
25  : analyzed(cfg.getNumBlockIDs(), false) {}
26 
28  const CFGBlock *Dst) {
29  const unsigned DstBlockID = Dst->getBlockID();
30 
31  // If we haven't analyzed the destination node, run the analysis now
32  if (!analyzed[DstBlockID]) {
33  mapReachability(Dst);
34  analyzed[DstBlockID] = true;
35  }
36 
37  // Return the cached result
38  return reachable[DstBlockID][Src->getBlockID()];
39 }
40 
41 // Maps reachability to a common node by walking the predecessors of the
42 // destination node.
43 void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
45  llvm::BitVector visited(analyzed.size());
46 
47  ReachableSet &DstReachability = reachable[Dst->getBlockID()];
48  DstReachability.resize(analyzed.size(), false);
49 
50  // Start searching from the destination node, since we commonly will perform
51  // multiple queries relating to a destination node.
52  worklist.push_back(Dst);
53  bool firstRun = true;
54 
55  while (!worklist.empty()) {
56  const CFGBlock *block = worklist.pop_back_val();
57 
58  if (visited[block->getBlockID()])
59  continue;
60  visited[block->getBlockID()] = true;
61 
62  // Update reachability information for this node -> Dst
63  if (!firstRun) {
64  // Don't insert Dst -> Dst unless it was a predecessor of itself
65  DstReachability[block->getBlockID()] = true;
66  }
67  else
68  firstRun = false;
69 
70  // Add the predecessors to the worklist.
71  for (CFGBlock::const_pred_iterator i = block->pred_begin(),
72  e = block->pred_end(); i != e; ++i) {
73  if (*i)
74  worklist.push_back(*i);
75  }
76  }
77 }
pred_iterator pred_end()
Definition: CFG.h:734
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:720
unsigned getBlockID() const
Definition: CFG.h:856
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
#define false
Definition: stdbool.h:33
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:733
Dataflow Directional Tag Classes.