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/PostOrderIterator.h"
22#include <utility>
23#include <vector>
24
25namespace clang {
26
27class PostOrderCFGView : public ManagedAnalysis {
28 virtual void anchor();
29
30public:
31 /// Implements a set of CFGBlocks using a BitVector.
32 class CFGBlockSet {
33 llvm::BitVector VisitedBlockIDs;
34
35 public:
36 CFGBlockSet() = default;
37 CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
38
39 /// Set the bit associated with a particular CFGBlock.
40 std::pair<std::nullopt_t, bool> insert(const CFGBlock *Block) {
41 if (VisitedBlockIDs.test(Idx: Block->getBlockID()))
42 return std::make_pair(x: std::nullopt, y: false);
43 VisitedBlockIDs.set(Block->getBlockID());
44 return std::make_pair(x: std::nullopt, y: true);
45 }
46
47 /// Check if the bit for a CFGBlock has been already set.
48 /// This method is for tracking visited blocks in the main threadsafety
49 /// loop. Block must not be null.
50 bool alreadySet(const CFGBlock *Block) {
51 return VisitedBlockIDs.test(Idx: Block->getBlockID());
52 }
53 };
54
55private:
56 std::vector<const CFGBlock *> Blocks;
57
58 using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
59 BlockOrderTy BlockOrder;
60
61public:
62 friend struct BlockOrderCompare;
63
64 using iterator = std::vector<const CFGBlock *>::reverse_iterator;
65 using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
66
67 PostOrderCFGView(const CFG *cfg);
68
69 iterator begin() { return Blocks.rbegin(); }
70 iterator end() { return Blocks.rend(); }
71
72 const_iterator begin() const { return Blocks.rbegin(); }
73 const_iterator end() const { return Blocks.rend(); }
74
75 bool empty() const { return begin() == end(); }
76
77 struct BlockOrderCompare {
78 const PostOrderCFGView &POV;
79
80 public:
81 BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
82
83 bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
84 };
85
86 BlockOrderCompare getComparator() const {
87 return BlockOrderCompare(*this);
88 }
89
90 // Used by AnalyisContext to construct this object.
91 static const void *getTag();
92
93 static std::unique_ptr<PostOrderCFGView>
94 create(AnalysisDeclContext &analysisContext);
95};
96
97} // namespace clang
98
99#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
100