Coverage Report

Created: 2018-09-25 23:22

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