Coverage Report

Created: 2022-07-16 07:03

/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
29.0k
      : 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
27.2k
      : 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.76k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33
  const PostOrderCFGView *getCFGView() const { return POV; }
34
35
192k
  void enqueueBlock(const CFGBlock *Block) {
36
192k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]190k
) {
37
112k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
112k
      WorkList.push(Block);
39
112k
    }
40
192k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
180k
  void enqueueBlock(const CFGBlock *Block) {
36
180k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]178k
) {
37
101k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
101k
      WorkList.push(Block);
39
101k
    }
40
180k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
12.1k
  void enqueueBlock(const CFGBlock *Block) {
36
12.1k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]12.1k
) {
37
11.0k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
11.0k
      WorkList.push(Block);
39
11.0k
    }
40
12.1k
  }
41
42
141k
  const CFGBlock *dequeue() {
43
141k
    if (WorkList.empty())
44
29.0k
      return nullptr;
45
112k
    const CFGBlock *B = WorkList.top();
46
112k
    WorkList.pop();
47
112k
    EnqueuedBlocks[B->getBlockID()] = false;
48
112k
    return B;
49
141k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()
Line
Count
Source
42
128k
  const CFGBlock *dequeue() {
43
128k
    if (WorkList.empty())
44
27.2k
      return nullptr;
45
101k
    const CFGBlock *B = WorkList.top();
46
101k
    WorkList.pop();
47
101k
    EnqueuedBlocks[B->getBlockID()] = false;
48
101k
    return B;
49
128k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()
Line
Count
Source
42
12.8k
  const CFGBlock *dequeue() {
43
12.8k
    if (WorkList.empty())
44
1.76k
      return nullptr;
45
11.0k
    const CFGBlock *B = WorkList.top();
46
11.0k
    WorkList.pop();
47
11.0k
    EnqueuedBlocks[B->getBlockID()] = false;
48
11.0k
    return B;
49
12.8k
  }
50
};
51
52
struct ReversePostOrderCompare {
53
  PostOrderCFGView::BlockOrderCompare Cmp;
54
18.7k
  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55
18.7k
    return Cmp(rhs, lhs);
56
18.7k
  }
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, PostOrderCFGView *POV)
65
      : DataflowWorklistBase(Cfg, POV,
66
1.76k
                             ReversePostOrderCompare{POV->getComparator()}) {}
67
68
  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
69
1.37k
      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
Unexecuted instantiation: clang::ForwardDataflowWorklist::ForwardDataflowWorklist(clang::CFG const&, clang::AnalysisDeclContext&)
clang::ForwardDataflowWorklist::ForwardDataflowWorklist(clang::CFG const&, clang::AnalysisDeclContext&)
Line
Count
Source
69
1.37k
      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70
71
11.5k
  void enqueueSuccessors(const CFGBlock *Block) {
72
11.5k
    for (auto B : Block->succs())
73
12.1k
      enqueueBlock(B);
74
11.5k
  }
75
};
76
77
/// A worklist implementation for backward dataflow analysis. The enqueued
78
/// block will be dequeued in post order. The worklist cannot contain the same
79
/// block multiple times at once.
80
struct BackwardDataflowWorklist
81
    : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
82
  BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
83
      : DataflowWorklistBase(
84
            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
85
27.2k
            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
86
87
100k
  void enqueuePredecessors(const CFGBlock *Block) {
88
100k
    for (auto B : Block->preds())
89
82.8k
      enqueueBlock(B);
90
100k
  }
91
};
92
93
} // namespace clang
94
95
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H