/
Dominance.h
146 lines (112 loc) · 4.96 KB
/
Dominance.h
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//===- Dominance.h - Dominator analysis for CFGs ----------------*- 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
//
//===----------------------------------------------------------------------===//
#ifndef MLIR_IR_DOMINANCE_H
#define MLIR_IR_DOMINANCE_H
#include "mlir/IR/RegionGraphTraits.h"
#include "llvm/Support/GenericDomTree.h"
extern template class llvm::DominatorTreeBase<mlir::Block, false>;
extern template class llvm::DominatorTreeBase<mlir::Block, true>;
namespace mlir {
using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
class Operation;
namespace detail {
template <bool IsPostDom> class DominanceInfoBase {
using base = llvm::DominatorTreeBase<Block, IsPostDom>;
public:
DominanceInfoBase(Operation *op) { recalculate(op); }
DominanceInfoBase(DominanceInfoBase &&) = default;
DominanceInfoBase &operator=(DominanceInfoBase &&) = default;
DominanceInfoBase(const DominanceInfoBase &) = delete;
DominanceInfoBase &operator=(const DominanceInfoBase &) = delete;
/// Recalculate the dominance info.
void recalculate(Operation *op);
/// Finds the nearest common dominator block for the two given blocks a
/// and b. If no common dominator can be found, this function will return
/// nullptr.
Block *findNearestCommonDominator(Block *a, Block *b) const;
/// Get the root dominance node of the given region.
DominanceInfoNode *getRootNode(Region *region) {
assert(dominanceInfos.count(region) != 0);
return dominanceInfos[region]->getRootNode();
}
/// Return the dominance node from the Region containing block A.
DominanceInfoNode *getNode(Block *a);
protected:
using super = DominanceInfoBase<IsPostDom>;
/// Return true if the specified block A properly dominates block B.
bool properlyDominates(Block *a, Block *b) const;
/// A mapping of regions to their base dominator tree.
DenseMap<Region *, std::unique_ptr<base>> dominanceInfos;
};
} // end namespace detail
/// A class for computing basic dominance information.
class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
public:
using super::super;
/// Return true if operation A properly dominates operation B.
bool properlyDominates(Operation *a, Operation *b) const;
/// Return true if operation A dominates operation B.
bool dominates(Operation *a, Operation *b) const {
return a == b || properlyDominates(a, b);
}
/// Return true if value A properly dominates operation B.
bool properlyDominates(Value a, Operation *b) const;
/// Return true if operation A dominates operation B.
bool dominates(Value a, Operation *b) const {
return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
}
/// Return true if the specified block A dominates block B.
bool dominates(Block *a, Block *b) const {
return a == b || properlyDominates(a, b);
}
/// Return true if the specified block A properly dominates block B.
bool properlyDominates(Block *a, Block *b) const {
return super::properlyDominates(a, b);
}
/// Update the internal DFS numbers for the dominance nodes.
void updateDFSNumbers();
};
/// A class for computing basic postdominance information.
class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
public:
using super::super;
/// Return true if operation A properly postdominates operation B.
bool properlyPostDominates(Operation *a, Operation *b);
/// Return true if operation A postdominates operation B.
bool postDominates(Operation *a, Operation *b) {
return a == b || properlyPostDominates(a, b);
}
/// Return true if the specified block A properly postdominates block B.
bool properlyPostDominates(Block *a, Block *b) {
return super::properlyDominates(a, b);
}
/// Return true if the specified block A postdominates block B.
bool postDominates(Block *a, Block *b) {
return a == b || properlyPostDominates(a, b);
}
};
} // end namespace mlir
namespace llvm {
/// DominatorTree GraphTraits specialization so the DominatorTree can be
/// iterated by generic graph iterators.
template <> struct GraphTraits<mlir::DominanceInfoNode *> {
using ChildIteratorType = mlir::DominanceInfoNode::iterator;
using NodeRef = mlir::DominanceInfoNode *;
static NodeRef getEntryNode(NodeRef N) { return N; }
static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
};
template <> struct GraphTraits<const mlir::DominanceInfoNode *> {
using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
using NodeRef = const mlir::DominanceInfoNode *;
static NodeRef getEntryNode(NodeRef N) { return N; }
static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
};
} // end namespace llvm
#endif