Coverage Report

Created: 2019-02-21 13:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h
Line
Count
Source
1
//===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===//
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 implements post order view of the blocks in a CFG.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
14
#define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
15
16
#include "clang/Analysis/AnalysisDeclContext.h"
17
#include "clang/Analysis/CFG.h"
18
#include "clang/Basic/LLVM.h"
19
#include "llvm/ADT/BitVector.h"
20
#include "llvm/ADT/DenseMap.h"
21
#include "llvm/ADT/None.h"
22
#include "llvm/ADT/PostOrderIterator.h"
23
#include <utility>
24
#include <vector>
25
26
namespace clang {
27
28
class PostOrderCFGView : public ManagedAnalysis {
29
  virtual void anchor();
30
31
public:
32
  /// Implements a set of CFGBlocks using a BitVector.
33
  ///
34
  /// This class contains a minimal interface, primarily dictated by the SetType
35
  /// template parameter of the llvm::po_iterator template, as used with
36
  /// external storage. We also use this set to keep track of which CFGBlocks we
37
  /// visit during the analysis.
38
  class CFGBlockSet {
39
    llvm::BitVector VisitedBlockIDs;
40
41
  public:
42
    // po_iterator requires this iterator, but the only interface needed is the
43
    // value_type type.
44
    struct iterator { using value_type = const CFGBlock *; };
45
46
    CFGBlockSet() = default;
47
110k
    CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
48
49
    /// Set the bit associated with a particular CFGBlock.
50
    /// This is the important method for the SetType template parameter.
51
1.14M
    std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) {
52
1.14M
      // Note that insert() is called by po_iterator, which doesn't check to
53
1.14M
      // make sure that Block is non-null.  Moreover, the CFGBlock iterator will
54
1.14M
      // occasionally hand out null pointers for pruned edges, so we catch those
55
1.14M
      // here.
56
1.14M
      if (!Block)
57
76.6k
        return std::make_pair(None, false); // if an edge is trivially false.
58
1.07M
      if (VisitedBlockIDs.test(Block->getBlockID()))
59
222k
        return std::make_pair(None, false);
60
847k
      VisitedBlockIDs.set(Block->getBlockID());
61
847k
      return std::make_pair(None, true);
62
847k
    }
63
64
    /// Check if the bit for a CFGBlock has been already set.
65
    /// This method is for tracking visited blocks in the main threadsafety
66
    /// loop. Block must not be null.
67
24.1k
    bool alreadySet(const CFGBlock *Block) {
68
24.1k
      return VisitedBlockIDs.test(Block->getBlockID());
69
24.1k
    }
70
  };
71
72
private:
73
  using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>;
74
  std::vector<const CFGBlock *> Blocks;
75
76
  using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
77
  BlockOrderTy BlockOrder;
78
79
public:
80
  friend struct BlockOrderCompare;
81
82
  using iterator = std::vector<const CFGBlock *>::reverse_iterator;
83
  using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
84
85
  PostOrderCFGView(const CFG *cfg);
86
87
86.3k
  iterator begin() { return Blocks.rbegin(); }
88
86.3k
  iterator end() { return Blocks.rend(); }
89
90
8.59k
  const_iterator begin() const { return Blocks.rbegin(); }
91
8.05k
  const_iterator end() const { return Blocks.rend(); }
92
93
2.02k
  bool empty() const { return begin() == end(); }
94
95
  struct BlockOrderCompare {
96
    const PostOrderCFGView &POV;
97
98
  public:
99
18.1k
    BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
100
101
    bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
102
  };
103
104
18.1k
  BlockOrderCompare getComparator() const {
105
18.1k
    return BlockOrderCompare(*this);
106
18.1k
  }
107
108
  // Used by AnalyisContext to construct this object.
109
  static const void *getTag();
110
111
  static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
112
};
113
114
} // namespace clang
115
116
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H