LLVM 17.0.0git
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_SYNCDEPENDENCEANALYSIS_H
17#define LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
18
20#include <map>
21#include <memory>
22#include <unordered_map>
23#include <vector>
24
25namespace llvm {
26
27class BasicBlock;
28class DominatorTree;
29class Instruction;
30class LoopInfo;
31class PostDominatorTree;
32
35 // Join points of divergent disjoint paths.
37 // Divergent loop exits
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.
61public:
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.
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
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the SmallPtrSet class.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Relates points of divergent control to join points in reducible CFGs.
const ControlDivergenceDesc & getJoinBlocks(const Instruction &Term)
Computes divergent join points and loop exits caused by branch divergence in Term.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
const BasicBlock * getBlockAt(unsigned Idx) const
std::vector< const BasicBlock * > LoopPO
std::unordered_map< const BasicBlock *, unsigned > POIndex
unsigned getIndexOf(const BasicBlock &BB) const
void appendBlock(const BasicBlock &BB)
unsigned size() const