/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 |