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 ///
33 /// This class contains a minimal interface, primarily dictated by the SetType
34 /// template parameter of the llvm::po_iterator template, as used with
35 /// external storage. We also use this set to keep track of which CFGBlocks we
36 /// visit during the analysis.
37 class CFGBlockSet {
38 llvm::BitVector VisitedBlockIDs;
39
40 public:
41 // po_iterator requires this iterator, but the only interface needed is the
42 // value_type type.
43 struct iterator { using value_type = const CFGBlock *; };
44
45 CFGBlockSet() = default;
46 CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
47
48 /// Set the bit associated with a particular CFGBlock.
49 /// This is the important method for the SetType template parameter.
50 std::pair<std::nullopt_t, bool> insert(const CFGBlock *Block) {
51 // Note that insert() is called by po_iterator, which doesn't check to
52 // make sure that Block is non-null. Moreover, the CFGBlock iterator will
53 // occasionally hand out null pointers for pruned edges, so we catch those
54 // here.
55 if (!Block)
56 return std::make_pair(x: std::nullopt,
57 y: false); // if an edge is trivially false.
58 if (VisitedBlockIDs.test(Idx: Block->getBlockID()))
59 return std::make_pair(x: std::nullopt, y: false);
60 VisitedBlockIDs.set(Block->getBlockID());
61 return std::make_pair(x: std::nullopt, y: 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(Idx: Block->getBlockID());
69 }
70 };
71
72private:
73 // The CFG orders the blocks of loop bodies before those of loop successors
74 // (both numerically, and in the successor order of the loop condition
75 // block). So, RPO necessarily reverses that order, placing the loop successor
76 // *before* the loop body. For many analyses, particularly those that converge
77 // to a fixpoint, this results in potentially significant extra work because
78 // loop successors will necessarily need to be reconsidered once the algorithm
79 // has reached a fixpoint on the loop body.
80 //
81 // This definition of CFG graph traits reverses the order of children, so that
82 // loop bodies will come first in an RPO.
83 struct CFGLoopBodyFirstTraits {
84 using NodeRef = const ::clang::CFGBlock *;
85 using ChildIteratorType = ::clang::CFGBlock::const_succ_reverse_iterator;
86
87 static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); }
88 static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); }
89
90 using nodes_iterator = ::clang::CFG::const_iterator;
91
92 static NodeRef getEntryNode(const ::clang::CFG *F) {
93 return &F->getEntry();
94 }
95
96 static nodes_iterator nodes_begin(const ::clang::CFG *F) {
97 return F->nodes_begin();
98 }
99
100 static nodes_iterator nodes_end(const ::clang::CFG *F) {
101 return F->nodes_end();
102 }
103
104 static unsigned size(const ::clang::CFG *F) { return F->size(); }
105 };
106 using po_iterator =
107 llvm::po_iterator<const CFG *, CFGBlockSet, true, CFGLoopBodyFirstTraits>;
108 std::vector<const CFGBlock *> Blocks;
109
110 using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
111 BlockOrderTy BlockOrder;
112
113public:
114 friend struct BlockOrderCompare;
115
116 using iterator = std::vector<const CFGBlock *>::reverse_iterator;
117 using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
118
119 PostOrderCFGView(const CFG *cfg);
120
121 iterator begin() { return Blocks.rbegin(); }
122 iterator end() { return Blocks.rend(); }
123
124 const_iterator begin() const { return Blocks.rbegin(); }
125 const_iterator end() const { return Blocks.rend(); }
126
127 bool empty() const { return begin() == end(); }
128
129 struct BlockOrderCompare {
130 const PostOrderCFGView &POV;
131
132 public:
133 BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
134
135 bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
136 };
137
138 BlockOrderCompare getComparator() const {
139 return BlockOrderCompare(*this);
140 }
141
142 // Used by AnalyisContext to construct this object.
143 static const void *getTag();
144
145 static std::unique_ptr<PostOrderCFGView>
146 create(AnalysisDeclContext &analysisContext);
147};
148
149} // namespace clang
150
151#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
152