LLVM
17.0.0git
include
llvm
Analysis
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
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
Idx
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
Definition:
DeadArgumentElimination.cpp:347
SmallPtrSet.h
This file defines the SmallPtrSet class.
llvm::BasicBlock
LLVM Basic Block Representation.
Definition:
BasicBlock.h:56
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition:
Dominators.h:166
llvm::Instruction
Definition:
Instruction.h:42
llvm::LoopInfo
Definition:
LoopInfo.h:1108
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition:
PostDominators.h:28
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::SyncDependenceAnalysis
Relates points of divergent control to join points in reducible CFGs.
Definition:
SyncDependenceAnalysis.h:60
llvm::SyncDependenceAnalysis::~SyncDependenceAnalysis
~SyncDependenceAnalysis()
llvm::SyncDependenceAnalysis::getJoinBlocks
const ControlDivergenceDesc & getJoinBlocks(const Instruction &Term)
Computes divergent join points and loop exits caused by branch divergence in Term.
Definition:
SyncDependenceAnalysis.cpp:450
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition:
ISDOpcodes.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:
AddressRanges.h:18
llvm::ControlDivergenceDesc
Definition:
SyncDependenceAnalysis.h:34
llvm::ControlDivergenceDesc::JoinDivBlocks
ConstBlockSet JoinDivBlocks
Definition:
SyncDependenceAnalysis.h:36
llvm::ControlDivergenceDesc::LoopDivBlocks
ConstBlockSet LoopDivBlocks
Definition:
SyncDependenceAnalysis.h:38
llvm::ModifiedPO
Definition:
SyncDependenceAnalysis.h:41
llvm::ModifiedPO::getBlockAt
const BasicBlock * getBlockAt(unsigned Idx) const
Definition:
SyncDependenceAnalysis.h:52
llvm::ModifiedPO::LoopPO
std::vector< const BasicBlock * > LoopPO
Definition:
SyncDependenceAnalysis.h:42
llvm::ModifiedPO::POIndex
std::unordered_map< const BasicBlock *, unsigned > POIndex
Definition:
SyncDependenceAnalysis.h:43
llvm::ModifiedPO::getIndexOf
unsigned getIndexOf(const BasicBlock &BB) const
Definition:
SyncDependenceAnalysis.h:48
llvm::ModifiedPO::appendBlock
void appendBlock(const BasicBlock &BB)
Definition:
SyncDependenceAnalysis.h:44
llvm::ModifiedPO::size
unsigned size() const
Definition:
SyncDependenceAnalysis.h:51
Generated on Wed Feb 1 2023 00:13:20 for LLVM by
1.9.6