Coverage Report

Created: 2020-02-25 14:32

/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
22.7k
      : 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.01k
      : 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
21.7k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33
  const PostOrderCFGView *getCFGView() const { return POV; }
34
35
154k
  void enqueueBlock(const CFGBlock *Block) {
36
154k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]153k
) {
37
89.8k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
89.8k
      WorkList.push(Block);
39
89.8k
    }
40
154k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
8.59k
  void enqueueBlock(const CFGBlock *Block) {
36
8.59k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]8.34k
) {
37
7.66k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
7.66k
      WorkList.push(Block);
39
7.66k
    }
40
8.59k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
146k
  void enqueueBlock(const CFGBlock *Block) {
36
146k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]144k
) {
37
82.1k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
82.1k
      WorkList.push(Block);
39
82.1k
    }
40
146k
  }
41
42
112k
  const CFGBlock *dequeue() {
43
112k
    if (WorkList.empty())
44
22.7k
      return nullptr;
45
89.8k
    const CFGBlock *B = WorkList.top();
46
89.8k
    WorkList.pop();
47
89.8k
    EnqueuedBlocks[B->getBlockID()] = false;
48
89.8k
    return B;
49
89.8k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()
Line
Count
Source
42
8.68k
  const CFGBlock *dequeue() {
43
8.68k
    if (WorkList.empty())
44
1.01k
      return nullptr;
45
7.66k
    const CFGBlock *B = WorkList.top();
46
7.66k
    WorkList.pop();
47
7.66k
    EnqueuedBlocks[B->getBlockID()] = false;
48
7.66k
    return B;
49
7.66k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()
Line
Count
Source
42
103k
  const CFGBlock *dequeue() {
43
103k
    if (WorkList.empty())
44
21.7k
      return nullptr;
45
82.1k
    const CFGBlock *B = WorkList.top();
46
82.1k
    WorkList.pop();
47
82.1k
    EnqueuedBlocks[B->getBlockID()] = false;
48
82.1k
    return B;
49
82.1k
  }
50
};
51
52
struct ReversePostOrderCompare {
53
  PostOrderCFGView::BlockOrderCompare Cmp;
54
18.8k
  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55
18.8k
    return Cmp(rhs, lhs);
56
18.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.01k
                Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {}
69
70
7.79k
  void enqueueSuccessors(const CFGBlock *Block) {
71
7.79k
    for (auto B : Block->succs())
72
8.58k
      enqueueBlock(B);
73
7.79k
  }
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
21.7k
            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
85
86
81.0k
  void enqueuePredecessors(const CFGBlock *Block) {
87
81.0k
    for (auto B : Block->preds())
88
67.2k
      enqueueBlock(B);
89
81.0k
  }
90
};
91
92
} // namespace clang
93
94
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H