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