Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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/SmallPtrSet.h" |
||
| 20 | #include <map> |
||
| 21 | #include <memory> |
||
| 22 | #include <unordered_map> |
||
| 23 | #include <vector> |
||
| 24 | |||
| 25 | namespace llvm { |
||
| 26 | |||
| 27 | class BasicBlock; |
||
| 28 | class DominatorTree; |
||
| 29 | class Instruction; |
||
| 30 | class LoopInfo; |
||
| 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; |
||
| 44 | void appendBlock(const BasicBlock &BB) { |
||
| 45 | POIndex[&BB] = LoopPO.size(); |
||
| 46 | LoopPO.push_back(&BB); |
||
| 47 | } |
||
| 48 | unsigned getIndexOf(const BasicBlock &BB) const { |
||
| 49 | return POIndex.find(&BB)->second; |
||
| 50 | } |
||
| 51 | unsigned size() const { return LoopPO.size(); } |
||
| 52 | 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 |