Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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;
  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(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.
  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 std::unique_ptr<PostOrderCFGView>
  112.   create(AnalysisDeclContext &analysisContext);
  113. };
  114.  
  115. } // namespace clang
  116.  
  117. #endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
  118.