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