LLVM  10.0.0svn
SyncDependenceAnalysis.h
Go to the documentation of this file.
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"
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 
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.
40  void visitSuccessor(const BasicBlock &succBlock, const Loop *termLoop,
41  const BasicBlock *defBlock);
42 
43 public:
44  bool inRegion(const BasicBlock &BB) const;
45 
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 
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
SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
const ConstBlockSet & join_blocks(const Instruction &Term)
Computes divergent join points and loop exits caused by branch divergence in Term.
bool inRegion(const BasicBlock &BB) const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Relates points of divergent control to join points in reducible CFGs.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509