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/DenseMap.h"
20 #include "llvm/ADT/PostOrderIterator.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include <memory>
24 #include <unordered_map>
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 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;
appendBlockModifiedPO44   void appendBlock(const BasicBlock &BB) {
45     POIndex[&BB] = LoopPO.size();
46     LoopPO.push_back(&BB);
47   }
getIndexOfModifiedPO48   unsigned getIndexOf(const BasicBlock &BB) const {
49     return POIndex.find(&BB)->second;
50   }
sizeModifiedPO51   unsigned size() const { return LoopPO.size(); }
getBlockAtModifiedPO52   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