| //===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements post order view of the blocks in a CFG. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |
| #define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |
| |
| #include "clang/Analysis/AnalysisDeclContext.h" |
| #include "clang/Analysis/CFG.h" |
| #include "clang/Basic/LLVM.h" |
| #include "llvm/ADT/BitVector.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/None.h" |
| #include "llvm/ADT/PostOrderIterator.h" |
| #include <utility> |
| #include <vector> |
| |
| namespace clang { |
| |
| class PostOrderCFGView : public ManagedAnalysis { |
| virtual void anchor(); |
| |
| public: |
| /// Implements a set of CFGBlocks using a BitVector. |
| /// |
| /// This class contains a minimal interface, primarily dictated by the SetType |
| /// template parameter of the llvm::po_iterator template, as used with |
| /// external storage. We also use this set to keep track of which CFGBlocks we |
| /// visit during the analysis. |
| class CFGBlockSet { |
| llvm::BitVector VisitedBlockIDs; |
| |
| public: |
| // po_iterator requires this iterator, but the only interface needed is the |
| // value_type type. |
| struct iterator { using value_type = const CFGBlock *; }; |
| |
| CFGBlockSet() = default; |
| CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} |
| |
| /// Set the bit associated with a particular CFGBlock. |
| /// This is the important method for the SetType template parameter. |
| std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) { |
| // Note that insert() is called by po_iterator, which doesn't check to |
| // make sure that Block is non-null. Moreover, the CFGBlock iterator will |
| // occasionally hand out null pointers for pruned edges, so we catch those |
| // here. |
| if (!Block) |
| return std::make_pair(None, false); // if an edge is trivially false. |
| if (VisitedBlockIDs.test(Block->getBlockID())) |
| return std::make_pair(None, false); |
| VisitedBlockIDs.set(Block->getBlockID()); |
| return std::make_pair(None, true); |
| } |
| |
| /// Check if the bit for a CFGBlock has been already set. |
| /// This method is for tracking visited blocks in the main threadsafety |
| /// loop. Block must not be null. |
| bool alreadySet(const CFGBlock *Block) { |
| return VisitedBlockIDs.test(Block->getBlockID()); |
| } |
| }; |
| |
| private: |
| using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>; |
| std::vector<const CFGBlock *> Blocks; |
| |
| using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>; |
| BlockOrderTy BlockOrder; |
| |
| public: |
| friend struct BlockOrderCompare; |
| |
| using iterator = std::vector<const CFGBlock *>::reverse_iterator; |
| using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator; |
| |
| PostOrderCFGView(const CFG *cfg); |
| |
| iterator begin() { return Blocks.rbegin(); } |
| iterator end() { return Blocks.rend(); } |
| |
| const_iterator begin() const { return Blocks.rbegin(); } |
| const_iterator end() const { return Blocks.rend(); } |
| |
| bool empty() const { return begin() == end(); } |
| |
| struct BlockOrderCompare { |
| const PostOrderCFGView &POV; |
| |
| public: |
| BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} |
| |
| bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; |
| }; |
| |
| BlockOrderCompare getComparator() const { |
| return BlockOrderCompare(*this); |
| } |
| |
| // Used by AnalyisContext to construct this object. |
| static const void *getTag(); |
| |
| static std::unique_ptr<PostOrderCFGView> |
| create(AnalysisDeclContext &analysisContext); |
| }; |
| |
| } // namespace clang |
| |
| #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H |