Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp
Line
Count
Source
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
4.75k
    : analyzed(cfg.getNumBlockIDs(), false) {}
25
26
bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
27
5.92k
                                          const CFGBlock *Dst) {
28
5.92k
  const unsigned DstBlockID = Dst->getBlockID();
29
5.92k
30
5.92k
  // If we haven't analyzed the destination node, run the analysis now
31
5.92k
  if (!analyzed[DstBlockID]) {
32
4.54k
    mapReachability(Dst);
33
4.54k
    analyzed[DstBlockID] = true;
34
4.54k
  }
35
5.92k
36
5.92k
  // Return the cached result
37
5.92k
  return reachable[DstBlockID][Src->getBlockID()];
38
5.92k
}
39
40
// Maps reachability to a common node by walking the predecessors of the
41
// destination node.
42
4.54k
void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
43
4.54k
  SmallVector<const CFGBlock *, 11> worklist;
44
4.54k
  llvm::BitVector visited(analyzed.size());
45
4.54k
46
4.54k
  ReachableSet &DstReachability = reachable[Dst->getBlockID()];
47
4.54k
  DstReachability.resize(analyzed.size(), false);
48
4.54k
49
4.54k
  // Start searching from the destination node, since we commonly will perform
50
4.54k
  // multiple queries relating to a destination node.
51
4.54k
  worklist.push_back(Dst);
52
4.54k
  bool firstRun = true;
53
4.54k
54
78.2k
  while (!worklist.empty()) {
55
73.7k
    const CFGBlock *block = worklist.pop_back_val();
56
73.7k
57
73.7k
    if (visited[block->getBlockID()])
58
11.7k
      continue;
59
61.9k
    visited[block->getBlockID()] = true;
60
61.9k
61
61.9k
    // Update reachability information for this node -> Dst
62
61.9k
    if (!firstRun) {
63
57.4k
      // Don't insert Dst -> Dst unless it was a predecessor of itself
64
57.4k
      DstReachability[block->getBlockID()] = true;
65
57.4k
    }
66
4.54k
    else
67
4.54k
      firstRun = false;
68
61.9k
69
61.9k
    // Add the predecessors to the worklist.
70
61.9k
    for (CFGBlock::const_pred_iterator i = block->pred_begin(),
71
135k
         e = block->pred_end(); i != e; 
++i73.3k
) {
72
73.3k
      if (*i)
73
69.1k
        worklist.push_back(*i);
74
73.3k
    }
75
61.9k
  }
76
4.54k
}