Coverage Report

Created: 2022-01-22 13:19

/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
27.6k
      : 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
26.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.36k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33
  const PostOrderCFGView *getCFGView() const { return POV; }
34
35
313k
  void enqueueBlock(const CFGBlock *Block) {
36
313k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]312k
) {
37
238k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
238k
      WorkList.push(Block);
39
238k
    }
40
313k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
172k
  void enqueueBlock(const CFGBlock *Block) {
36
172k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]171k
) {
37
97.4k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
97.4k
      WorkList.push(Block);
39
97.4k
    }
40
172k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
141k
  void enqueueBlock(const CFGBlock *Block) {
36
141k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]141k
) {
37
140k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
140k
      WorkList.push(Block);
39
140k
    }
40
141k
  }
41
42
265k
  const CFGBlock *dequeue() {
43
265k
    if (WorkList.empty())
44
27.6k
      return nullptr;
45
238k
    const CFGBlock *B = WorkList.top();
46
238k
    WorkList.pop();
47
238k
    EnqueuedBlocks[B->getBlockID()] = false;
48
238k
    return B;
49
265k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()
Line
Count
Source
42
123k
  const CFGBlock *dequeue() {
43
123k
    if (WorkList.empty())
44
26.2k
      return nullptr;
45
97.4k
    const CFGBlock *B = WorkList.top();
46
97.4k
    WorkList.pop();
47
97.4k
    EnqueuedBlocks[B->getBlockID()] = false;
48
97.4k
    return B;
49
123k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()
Line
Count
Source
42
141k
  const CFGBlock *dequeue() {
43
141k
    if (WorkList.empty())
44
1.36k
      return nullptr;
45
140k
    const CFGBlock *B = WorkList.top();
46
140k
    WorkList.pop();
47
140k
    EnqueuedBlocks[B->getBlockID()] = false;
48
140k
    return B;
49
141k
  }
50
};
51
52
struct ReversePostOrderCompare {
53
  PostOrderCFGView::BlockOrderCompare Cmp;
54
72.0k
  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55
72.0k
    return Cmp(rhs, lhs);
56
72.0k
  }
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.36k
                             ReversePostOrderCompare{POV->getComparator()}) {}
67
68
  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
69
1.28k
      : 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.28k
      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70
71
140k
  void enqueueSuccessors(const CFGBlock *Block) {
72
140k
    for (auto B : Block->succs())
73
141k
      enqueueBlock(B);
74
140k
  }
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
26.2k
            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
86
87
96.3k
  void enqueuePredecessors(const CFGBlock *Block) {
88
96.3k
    for (auto B : Block->preds())
89
79.0k
      enqueueBlock(B);
90
96.3k
  }
91
};
92
93
} // namespace clang
94
95
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H