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 86