blob: c710c74b670f6bfe04566dae9edcccf10ed6d3b2 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- SyncDependenceAnalysis.h - Divergent Branch Dependence -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// \file
// This file defines the SyncDependenceAnalysis class, which computes for
// every divergent branch the set of phi nodes that the branch will make
// divergent.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
#define LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/LoopInfo.h"
#include <map>
#include <memory>
#include <unordered_map>
namespace llvm {
class BasicBlock;
class DominatorTree;
class PostDominatorTree;
using ConstBlockSet = SmallPtrSet<const BasicBlock *, 4>;
struct ControlDivergenceDesc {
// Join points of divergent disjoint paths.
ConstBlockSet JoinDivBlocks;
// Divergent loop exits
ConstBlockSet LoopDivBlocks;
};
struct ModifiedPO {
std::vector<const BasicBlock *> LoopPO;
std::unordered_map<const BasicBlock *, unsigned> POIndex;
void appendBlock(const BasicBlock &BB) {
POIndex[&BB] = LoopPO.size();
LoopPO.push_back(&BB);
}
unsigned getIndexOf(const BasicBlock &BB) const {
return POIndex.find(&BB)->second;
}
unsigned size() const { return LoopPO.size(); }
const BasicBlock *getBlockAt(unsigned Idx) const { return LoopPO[Idx]; }
};
/// \brief Relates points of divergent control to join points in
/// reducible CFGs.
///
/// This analysis relates points of divergent control to points of converging
/// divergent control. The analysis requires all loops to be reducible.
class SyncDependenceAnalysis {
public:
~SyncDependenceAnalysis();
SyncDependenceAnalysis(const DominatorTree &DT, const PostDominatorTree &PDT,
const LoopInfo &LI);
/// \brief Computes divergent join points and loop exits caused by branch
/// divergence in \p Term.
///
/// The set of blocks which are reachable by disjoint paths from \p Term.
/// The set also contains loop exits if there two disjoint paths:
/// one from \p Term to the loop exit and another from \p Term to the loop
/// header. Those exit blocks are added to the returned set.
/// If L is the parent loop of \p Term and an exit of L is in the returned
/// set then L is a divergent loop.
const ControlDivergenceDesc &getJoinBlocks(const Instruction &Term);
private:
static ControlDivergenceDesc EmptyDivergenceDesc;
ModifiedPO LoopPO;
const DominatorTree &DT;
const PostDominatorTree &PDT;
const LoopInfo &LI;
std::map<const Instruction *, std::unique_ptr<ControlDivergenceDesc>>
CachedControlDivDescs;
};
} // namespace llvm
#endif // LLVM_ANALYSIS_SYNCDEPENDENCEANALYSIS_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
