PostOrderCFGView.h source code [clang_source_code/include/clang/Analysis/Analyses/PostOrderCFGView.h]

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	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	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	if (!Block)
57	return std::make_pair(None, false); // if an edge is trivially false.
58	if (VisitedBlockIDs.test(Block->getBlockID()))
59	return std::make_pair(None, false);
60	VisitedBlockIDs.set(Block->getBlockID());
61	return std::make_pair(None, true);
62	}
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	bool alreadySet(const CFGBlock *Block) {
68	return VisitedBlockIDs.test(Block->getBlockID());
69	}
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	iterator begin() { return Blocks.rbegin(); }
88	iterator end() { return Blocks.rend(); }
89
90	const_iterator begin() const { return Blocks.rbegin(); }
91	const_iterator end() const { return Blocks.rend(); }
92
93	bool empty() const { return begin() == end(); }
94
95	struct BlockOrderCompare {
96	const PostOrderCFGView &POV;
97
98	public:
99	BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
100
101	bool operator()(const CFGBlock b1, const CFGBlock b2) const;
102	};
103
104	BlockOrderCompare getComparator() const {
105	return BlockOrderCompare(*this);
106	}
107
108	// Used by AnalyisContext to construct this object.
109	static const void *getTag();
110
111	static PostOrderCFGView *create(AnalysisDeclContext &analysisContext);
112	};
113
114	} // namespace clang
115
116	#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
117

clang::PostOrderCFGView::anchor

clang::PostOrderCFGView::CFGBlockSet

clang::PostOrderCFGView::CFGBlockSet::VisitedBlockIDs

clang::PostOrderCFGView::CFGBlockSet::iterator

clang::PostOrderCFGView::CFGBlockSet::insert

clang::PostOrderCFGView::CFGBlockSet::alreadySet

clang::PostOrderCFGView::Blocks

clang::PostOrderCFGView::BlockOrder

clang::PostOrderCFGView::begin

clang::PostOrderCFGView::end

clang::PostOrderCFGView::begin

clang::PostOrderCFGView::end

clang::PostOrderCFGView::empty

clang::PostOrderCFGView::BlockOrderCompare

clang::PostOrderCFGView::BlockOrderCompare::POV

clang::PostOrderCFGView::getComparator

clang::PostOrderCFGView::getTag

clang::PostOrderCFGView::create

Clang Project