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 25 namespace clang { 26 27 class PostOrderCFGView : public ManagedAnalysis { 28 virtual void anchor(); 29 30 public: 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; CFGBlockSet(const CFG * G)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. insert(const CFGBlock * Block)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(std::nullopt, 57 false); // if an edge is trivially false. 58 if (VisitedBlockIDs.test(Block->getBlockID())) 59 return std::make_pair(std::nullopt, false); 60 VisitedBlockIDs.set(Block->getBlockID()); 61 return std::make_pair(std::nullopt, 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. alreadySet(const CFGBlock * Block)67 bool alreadySet(const CFGBlock *Block) { 68 return VisitedBlockIDs.test(Block->getBlockID()); 69 } 70 }; 71 72 private: 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 child_beginCFGLoopBodyFirstTraits87 static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); } child_endCFGLoopBodyFirstTraits88 static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); } 89 90 using nodes_iterator = ::clang::CFG::const_iterator; 91 getEntryNodeCFGLoopBodyFirstTraits92 static NodeRef getEntryNode(const ::clang::CFG *F) { 93 return &F->getEntry(); 94 } 95 nodes_beginCFGLoopBodyFirstTraits96 static nodes_iterator nodes_begin(const ::clang::CFG *F) { 97 return F->nodes_begin(); 98 } 99 nodes_endCFGLoopBodyFirstTraits100 static nodes_iterator nodes_end(const ::clang::CFG *F) { 101 return F->nodes_end(); 102 } 103 sizeCFGLoopBodyFirstTraits104 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 113 public: 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 begin()121 iterator begin() { return Blocks.rbegin(); } end()122 iterator end() { return Blocks.rend(); } 123 begin()124 const_iterator begin() const { return Blocks.rbegin(); } end()125 const_iterator end() const { return Blocks.rend(); } 126 empty()127 bool empty() const { return begin() == end(); } 128 129 struct BlockOrderCompare { 130 const PostOrderCFGView &POV; 131 132 public: BlockOrderCompareBlockOrderCompare133 BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} 134 135 bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; 136 }; 137 getComparator()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