/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h
Line | Count | Source |
1 | | //===- PostOrderCFGView.h - Post order view of CFG blocks -------*- 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 | | // This file implements post order view of the blocks in a CFG. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |
14 | | #define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |
15 | | |
16 | | #include "clang/Analysis/AnalysisDeclContext.h" |
17 | | #include "clang/Analysis/CFG.h" |
18 | | #include "clang/Basic/LLVM.h" |
19 | | #include "llvm/ADT/BitVector.h" |
20 | | #include "llvm/ADT/DenseMap.h" |
21 | | #include "llvm/ADT/None.h" |
22 | | #include "llvm/ADT/PostOrderIterator.h" |
23 | | #include <utility> |
24 | | #include <vector> |
25 | | |
26 | | namespace clang { |
27 | | |
28 | | class PostOrderCFGView : public ManagedAnalysis { |
29 | | virtual void anchor(); |
30 | | |
31 | | public: |
32 | | /// Implements a set of CFGBlocks using a BitVector. |
33 | | /// |
34 | | /// This class contains a minimal interface, primarily dictated by the SetType |
35 | | /// template parameter of the llvm::po_iterator template, as used with |
36 | | /// external storage. We also use this set to keep track of which CFGBlocks we |
37 | | /// visit during the analysis. |
38 | | class CFGBlockSet { |
39 | | llvm::BitVector VisitedBlockIDs; |
40 | | |
41 | | public: |
42 | | // po_iterator requires this iterator, but the only interface needed is the |
43 | | // value_type type. |
44 | | struct iterator { using value_type = const CFGBlock *; }; |
45 | | |
46 | | CFGBlockSet() = default; |
47 | 35.6k | CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} |
48 | | |
49 | | /// Set the bit associated with a particular CFGBlock. |
50 | | /// This is the important method for the SetType template parameter. |
51 | 144k | std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) { |
52 | | // Note that insert() is called by po_iterator, which doesn't check to |
53 | | // make sure that Block is non-null. Moreover, the CFGBlock iterator will |
54 | | // occasionally hand out null pointers for pruned edges, so we catch those |
55 | | // here. |
56 | 144k | if (!Block) |
57 | 1.05k | return std::make_pair(None, false); // if an edge is trivially false. |
58 | 143k | if (VisitedBlockIDs.test(Block->getBlockID())) |
59 | 10.9k | return std::make_pair(None, false); |
60 | 132k | VisitedBlockIDs.set(Block->getBlockID()); |
61 | 132k | return std::make_pair(None, true); |
62 | 143k | } |
63 | | |
64 | | /// Check if the bit for a CFGBlock has been already set. |
65 | | /// This method is for tracking visited blocks in the main threadsafety |
66 | | /// loop. Block must not be null. |
67 | 26.6k | bool alreadySet(const CFGBlock *Block) { |
68 | 26.6k | return VisitedBlockIDs.test(Block->getBlockID()); |
69 | 26.6k | } |
70 | | }; |
71 | | |
72 | | private: |
73 | | using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>; |
74 | | std::vector<const CFGBlock *> Blocks; |
75 | | |
76 | | using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>; |
77 | | BlockOrderTy BlockOrder; |
78 | | |
79 | | public: |
80 | | friend struct BlockOrderCompare; |
81 | | |
82 | | using iterator = std::vector<const CFGBlock *>::reverse_iterator; |
83 | | using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator; |
84 | | |
85 | | PostOrderCFGView(const CFG *cfg); |
86 | | |
87 | 191 | iterator begin() { return Blocks.rbegin(); } |
88 | 191 | iterator end() { return Blocks.rend(); } |
89 | | |
90 | 9.05k | const_iterator begin() const { return Blocks.rbegin(); } |
91 | 8.50k | const_iterator end() const { return Blocks.rend(); } |
92 | | |
93 | 2.13k | bool empty() const { return begin() == end(); } |
94 | | |
95 | | struct BlockOrderCompare { |
96 | | const PostOrderCFGView &POV; |
97 | | |
98 | | public: |
99 | 29.0k | BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} |
100 | | |
101 | | bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; |
102 | | }; |
103 | | |
104 | 29.0k | BlockOrderCompare getComparator() const { |
105 | 29.0k | return BlockOrderCompare(*this); |
106 | 29.0k | } |
107 | | |
108 | | // Used by AnalyisContext to construct this object. |
109 | | static const void *getTag(); |
110 | | |
111 | | static std::unique_ptr<PostOrderCFGView> |
112 | | create(AnalysisDeclContext &analysisContext); |
113 | | }; |
114 | | |
115 | | } // namespace clang |
116 | | |
117 | | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |