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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:
AddressRanges.h:18
llvm::M68kBeads::Term
@ Term
Definition:
M68kBaseInfo.h:90
llvm::ControlDivergenceDesc::LoopDivBlocks
ConstBlockSet LoopDivBlocks
Definition:
SyncDependenceAnalysis.h:38
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition:
Dominators.h:166
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::BasicBlock
LLVM Basic Block Representation.
Definition:
BasicBlock.h:55
llvm::ModifiedPO::size
unsigned size() const
Definition:
SyncDependenceAnalysis.h:51
llvm::ModifiedPO::LoopPO
std::vector< const BasicBlock * > LoopPO
Definition:
SyncDependenceAnalysis.h:42
llvm::ControlDivergenceDesc::JoinDivBlocks
ConstBlockSet JoinDivBlocks
Definition:
SyncDependenceAnalysis.h:36
llvm::ModifiedPO::getIndexOf
unsigned getIndexOf(const BasicBlock &BB) const
Definition:
SyncDependenceAnalysis.h:48
llvm::Instruction
Definition:
Instruction.h:41
llvm::SyncDependenceAnalysis::~SyncDependenceAnalysis
~SyncDependenceAnalysis()
SmallPtrSet.h
llvm::SyncDependenceAnalysis::SyncDependenceAnalysis
SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI)
Definition:
SyncDependenceAnalysis.cpp:250
llvm::ModifiedPO::POIndex
std::unordered_map< const BasicBlock *, unsigned > POIndex
Definition:
SyncDependenceAnalysis.h:43
llvm::ModifiedPO::appendBlock
void appendBlock(const BasicBlock &BB)
Definition:
SyncDependenceAnalysis.h:44
llvm::ModifiedPO
Definition:
SyncDependenceAnalysis.h:41
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition:
ISDOpcodes.h:71
llvm::LoopInfo
Definition:
LoopInfo.h:1108
llvm::ControlDivergenceDesc
Definition:
SyncDependenceAnalysis.h:34
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition:
PostDominators.h:28
llvm::SyncDependenceAnalysis
Relates points of divergent control to join points in reducible CFGs.
Definition:
SyncDependenceAnalysis.h:60
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::ModifiedPO::getBlockAt
const BasicBlock * getBlockAt(unsigned Idx) const
Definition:
SyncDependenceAnalysis.h:52
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition:
README.txt:39
Generated on Sat Jan 28 2023 08:40:44 for LLVM by
1.8.17