Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

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

  1. //===- SyncDependenceAnalysis.h - Divergent Branch Dependence -*- 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. // \file
  10. // This file defines the SyncDependenceAnalysis class, which computes for
  11. // every divergent branch the set of phi nodes that the branch will make
  12. // divergent.
  13. //
  14. //===----------------------------------------------------------------------===//
  15.  
  16. #ifndef LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
  17. #define LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
  18.  
  19. #include "llvm/ADT/SmallPtrSet.h"
  20. #include <map>
  21. #include <memory>
  22. #include <unordered_map>
  23. #include <vector>
  24.  
  25. namespace llvm {
  26.  
  27. class BasicBlock;
  28. class DominatorTree;
  29. class Instruction;
  30. class LoopInfo;
  31. class PostDominatorTree;
  32.  
  33. using ConstBlockSet = SmallPtrSet<const BasicBlock *, 4>;
  34. struct ControlDivergenceDesc {
  35.   // Join points of divergent disjoint paths.
  36.   ConstBlockSet JoinDivBlocks;
  37.   // Divergent loop exits
  38.   ConstBlockSet LoopDivBlocks;
  39. };
  40.  
  41. struct ModifiedPO {
  42.   std::vector<const BasicBlock *> LoopPO;
  43.   std::unordered_map<const BasicBlock *, unsigned> POIndex;
  44.   void appendBlock(const BasicBlock &BB) {
  45.     POIndex[&BB] = LoopPO.size();
  46.     LoopPO.push_back(&BB);
  47.   }
  48.   unsigned getIndexOf(const BasicBlock &BB) const {
  49.     return POIndex.find(&BB)->second;
  50.   }
  51.   unsigned size() const { return LoopPO.size(); }
  52.   const BasicBlock *getBlockAt(unsigned Idx) const { return LoopPO[Idx]; }
  53. };
  54.  
  55. /// \brief Relates points of divergent control to join points in
  56. /// reducible CFGs.
  57. ///
  58. /// This analysis relates points of divergent control to points of converging
  59. /// divergent control. The analysis requires all loops to be reducible.
  60. class SyncDependenceAnalysis {
  61. public:
  62.   ~SyncDependenceAnalysis();
  63.   SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT,
  64.                          const LoopInfo &LI);
  65.  
  66.   /// \brief Computes divergent join points and loop exits caused by branch
  67.   /// divergence in \p Term.
  68.   ///
  69.   /// The set of blocks which are reachable by disjoint paths from \p Term.
  70.   /// The set also contains loop exits if there two disjoint paths:
  71.   /// one from \p Term to the loop exit and another from \p Term to the loop
  72.   /// header. Those exit blocks are added to the returned set.
  73.   /// If L is the parent loop of \p Term and an exit of L is in the returned
  74.   /// set then L is a divergent loop.
  75.   const ControlDivergenceDesc &getJoinBlocks(const Instruction &Term);
  76.  
  77. private:
  78.   static ControlDivergenceDesc EmptyDivergenceDesc;
  79.  
  80.   ModifiedPO LoopPO;
  81.  
  82.   const DominatorTree &DT;
  83.   const PostDominatorTree &PDT;
  84.   const LoopInfo &LI;
  85.  
  86.   std::map<const Instruction *, std::unique_ptr<ControlDivergenceDesc>>
  87.       CachedControlDivDescs;
  88. };
  89.  
  90. } // namespace llvm
  91.  
  92. #endif // LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
  93.