Coverage Report

Created: 2020-09-19 12:23

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
Line
Count
Source
1
//===- DataflowWorklist.h ---------------------------------------*- 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
// A simple and reusable worklist for flow-sensitive analyses.
10
//
11
//===----------------------------------------------------------------------===//
12
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
13
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
14
15
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
16
#include "clang/Analysis/CFG.h"
17
#include "llvm/ADT/PriorityQueue.h"
18
19
namespace clang {
20
/// A worklist implementation where the enqueued blocks will be dequeued based
21
/// on the order defined by 'Comp'.
22
template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
23
  llvm::BitVector EnqueuedBlocks;
24
  PostOrderCFGView *POV;
25
  llvm::PriorityQueue<const CFGBlock *,
26
                      SmallVector<const CFGBlock *, QueueSize>, Comp>
27
      WorkList;
28
29
public:
30
  DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
31
25.9k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::DataflowWorklistBase(clang::CFG const&, clang::PostOrderCFGView*, clang::ReversePostOrderCompare)
Line
Count
Source
31
1.31k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::DataflowWorklistBase(clang::CFG const&, clang::PostOrderCFGView*, clang::PostOrderCFGView::BlockOrderCompare)
Line
Count
Source
31
24.6k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33
  const PostOrderCFGView *getCFGView() const { return POV; }
34
35
172k
  void enqueueBlock(const CFGBlock *Block) {
36
172k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]170k
) {
37
100k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
100k
      WorkList.push(Block);
39
100k
    }
40
172k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
10.6k
  void enqueueBlock(const CFGBlock *Block) {
36
10.6k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]10.3k
) {
37
9.58k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
9.58k
      WorkList.push(Block);
39
9.58k
    }
40
10.6k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
161k
  void enqueueBlock(const CFGBlock *Block) {
36
161k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]160k
) {
37
91.3k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
91.3k
      WorkList.push(Block);
39
91.3k
    }
40
161k
  }
41
42
126k
  const CFGBlock *dequeue() {
43
126k
    if (WorkList.empty())
44
25.9k
      return nullptr;
45
100k
    const CFGBlock *B = WorkList.top();
46
100k
    WorkList.pop();
47
100k
    EnqueuedBlocks[B->getBlockID()] = false;
48
100k
    return B;
49
100k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()
Line
Count
Source
42
10.8k
  const CFGBlock *dequeue() {
43
10.8k
    if (WorkList.empty())
44
1.31k
      return nullptr;
45
9.58k
    const CFGBlock *B = WorkList.top();
46
9.58k
    WorkList.pop();
47
9.58k
    EnqueuedBlocks[B->getBlockID()] = false;
48
9.58k
    return B;
49
9.58k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()
Line
Count
Source
42
115k
  const CFGBlock *dequeue() {
43
115k
    if (WorkList.empty())
44
24.6k
      return nullptr;
45
91.3k
    const CFGBlock *B = WorkList.top();
46
91.3k
    WorkList.pop();
47
91.3k
    EnqueuedBlocks[B->getBlockID()] = false;
48
91.3k
    return B;
49
91.3k
  }
50
};
51
52
struct ReversePostOrderCompare {
53
  PostOrderCFGView::BlockOrderCompare Cmp;
54
23.8k
  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55
23.8k
    return Cmp(rhs, lhs);
56
23.8k
  }
57
};
58
59
/// A worklist implementation for forward dataflow analysis. The enqueued
60
/// blocks will be dequeued in reverse post order. The worklist cannot contain
61
/// the same block multiple times at once.
62
struct ForwardDataflowWorklist
63
    : DataflowWorklistBase<ReversePostOrderCompare, 20> {
64
  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
65
      : DataflowWorklistBase(
66
            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
67
            ReversePostOrderCompare{
68
1.31k
                Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {}
69
70
9.74k
  void enqueueSuccessors(const CFGBlock *Block) {
71
9.74k
    for (auto B : Block->succs())
72
10.6k
      enqueueBlock(B);
73
9.74k
  }
74
};
75
76
/// A worklist implementation for backward dataflow analysis. The enqueued
77
/// block will be dequeued in post order. The worklist cannot contain the same
78
/// block multiple times at once.
79
struct BackwardDataflowWorklist
80
    : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
81
  BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
82
      : DataflowWorklistBase(
83
            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
84
24.6k
            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
85
86
90.1k
  void enqueuePredecessors(const CFGBlock *Block) {
87
90.1k
    for (auto B : Block->preds())
88
73.9k
      enqueueBlock(B);
89
90.1k
  }
90
};
91
92
} // namespace clang
93
94
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H