include/llvm/Analysis/SyncDependenceAnalysis.h

   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_SYNC_DEPENDENCE_ANALYSIS_H
  17 #define LLVM_ANALYSIS_SYNC_DEPENDENCE_ANALYSIS_H
  18
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/PostOrderIterator.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include <memory>
  24
  25 namespace llvm {
  26
  27 class BasicBlock;
  28 class DominatorTree;
  29 class Loop;
  30 class PostDominatorTree;
  31
  32 using ConstBlockSet = SmallPtrSet<const BasicBlock *, 4>;
  33
  34 /// \brief Relates points of divergent control to join points in
  35 /// reducible CFGs.
  36 ///
  37 /// This analysis relates points of divergent control to points of converging
  38 /// divergent control. The analysis requires all loops to be reducible.
  39 class SyncDependenceAnalysis {
  40   void visitSuccessor(const BasicBlock &succBlock, const Loop *termLoop,
  41                       const BasicBlock *defBlock);
  42
  43 public:
  44   bool inRegion(const BasicBlock &BB) const;
  45
  46   ~SyncDependenceAnalysis();
  47   SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT,
  48                          const LoopInfo &LI);
  49
  50   /// \brief Computes divergent join points and loop exits caused by branch
  51   /// divergence in \p Term.
  52   ///
  53   /// The set of blocks which are reachable by disjoint paths from \p Term.
  54   /// The set also contains loop exits if there two disjoint paths:
  55   /// one from \p Term to the loop exit and another from \p Term to the loop
  56   /// header. Those exit blocks are added to the returned set.
  57   /// If L is the parent loop of \p Term and an exit of L is in the returned
  58   /// set then L is a divergent loop.
  59   const ConstBlockSet &join_blocks(const Instruction &Term);
  60
  61   /// \brief Computes divergent join points and loop exits (in the surrounding
  62   /// loop) caused by the divergent loop exits of\p Loop.
  63   ///
  64   /// The set of blocks which are reachable by disjoint paths from the
  65   /// loop exits of \p Loop.
  66   /// This treats the loop as a single node in \p Loop's parent loop.
  67   /// The returned set has the same properties as for join_blocks(TermInst&).
  68   const ConstBlockSet &join_blocks(const Loop &Loop);
  69
  70 private:
  71   static ConstBlockSet EmptyBlockSet;
  72
  73   ReversePostOrderTraversal<const Function *> FuncRPOT;
  74   const DominatorTree &DT;
  75   const PostDominatorTree &PDT;
  76   const LoopInfo &LI;
  77
  78   std::map<const Loop *, std::unique_ptr<ConstBlockSet>> CachedLoopExitJoins;
  79   std::map<const Instruction *, std::unique_ptr<ConstBlockSet>>
  80       CachedBranchJoins;
  81 };
  82
  83 } // namespace llvm
  84
  85 #endif // LLVM_ANALYSIS_SYNC_DEPENDENCE_ANALYSIS_H