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
26namespace llvm {
27
28class BasicBlock;
29class DominatorTree;
30class Loop;
31class PostDominatorTree;
32
33using ConstBlockSet = SmallPtrSet<const BasicBlock *, 4>;
34struct ControlDivergenceDesc {
35  // Join points of divergent disjoint paths.
36  ConstBlockSet JoinDivBlocks;
37  // Divergent loop exits
38  ConstBlockSet LoopDivBlocks;
39};
40
41struct 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.
60class SyncDependenceAnalysis {
61public:
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
77private:
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