Coverage Report

Created: 2022-05-14 11:35

/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
28.4k
      : 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.8k
      : 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.59k
      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
32
33
  const PostOrderCFGView *getCFGView() const { return POV; }
34
35
252k
  void enqueueBlock(const CFGBlock *Block) {
36
252k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]251k
) {
37
175k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
175k
      WorkList.push(Block);
39
175k
    }
40
252k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
176k
  void enqueueBlock(const CFGBlock *Block) {
36
176k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]174k
) {
37
99.4k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
99.4k
      WorkList.push(Block);
39
99.4k
    }
40
176k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)
Line
Count
Source
35
76.6k
  void enqueueBlock(const CFGBlock *Block) {
36
76.6k
    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]76.6k
) {
37
75.7k
      EnqueuedBlocks[Block->getBlockID()] = true;
38
75.7k
      WorkList.push(Block);
39
75.7k
    }
40
76.6k
  }
41
42
203k
  const CFGBlock *dequeue() {
43
203k
    if (WorkList.empty())
44
28.4k
      return nullptr;
45
175k
    const CFGBlock *B = WorkList.top();
46
175k
    WorkList.pop();
47
175k
    EnqueuedBlocks[B->getBlockID()] = false;
48
175k
    return B;
49
203k
  }
clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()
Line
Count
Source
42
126k
  const CFGBlock *dequeue() {
43
126k
    if (WorkList.empty())
44
26.8k
      return nullptr;
45
99.4k
    const CFGBlock *B = WorkList.top();
46
99.4k
    WorkList.pop();
47
99.4k
    EnqueuedBlocks[B->getBlockID()] = false;
48
99.4k
    return B;
49
126k
  }
clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()
Line
Count
Source
42
77.3k
  const CFGBlock *dequeue() {
43
77.3k
    if (WorkList.empty())
44
1.59k
      return nullptr;
45
75.7k
    const CFGBlock *B = WorkList.top();
46
75.7k
    WorkList.pop();
47
75.7k
    EnqueuedBlocks[B->getBlockID()] = false;
48
75.7k
    return B;
49
77.3k
  }
50
};
51
52
struct ReversePostOrderCompare {
53
  PostOrderCFGView::BlockOrderCompare Cmp;
54
40.1k
  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
55
40.1k
    return Cmp(rhs, lhs);
56
40.1k
  }
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.59k
                             ReversePostOrderCompare{POV->getComparator()}) {}
67
68
  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
69
1.30k
      : 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.30k
      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
70
71
76.1k
  void enqueueSuccessors(const CFGBlock *Block) {
72
76.1k
    for (auto B : Block->succs())
73
76.6k
      enqueueBlock(B);
74
76.1k
  }
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.8k
            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
86
87
98.3k
  void enqueuePredecessors(const CFGBlock *Block) {
88
98.3k
    for (auto B : Block->preds())
89
80.7k
      enqueueBlock(B);
90
98.3k
  }
91
};
92
93
} // namespace clang
94
95
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H