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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
| //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- 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
/// Compute iterated dominance frontiers using a linear time algorithm.
///
/// The algorithm used here is based on:
///
/// Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
/// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
/// Programming Languages
/// POPL '95. ACM, New York, NY, 62-73.
///
/// It has been modified to not explicitly use the DJ graph data structure and
/// to directly compute pruned SSA using per-variable liveness information.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_SUPPORT_GENERIC_IDF_H
#define LLVM_SUPPORT_GENERIC_IDF_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/GenericDomTree.h"
#include <queue>
namespace llvm {
namespace IDFCalculatorDetail {
/// Generic utility class used for getting the children of a basic block.
/// May be specialized if, for example, one wouldn't like to return nullpointer
/// successors.
template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
using NodeRef = typename GraphTraits<NodeTy>::NodeRef;
using ChildrenTy = SmallVector<NodeRef, 8>;
ChildrenTy get(const NodeRef &N);
};
} // end of namespace IDFCalculatorDetail
/// Determine the iterated dominance frontier, given a set of defining
/// blocks, and optionally, a set of live-in blocks.
///
/// In turn, the results can be used to place phi nodes.
///
/// This algorithm is a linear time computation of Iterated Dominance Frontiers,
/// pruned using the live-in set.
/// By default, liveness is not used to prune the IDF computation.
/// The template parameters should be of a CFG block type.
template <class NodeTy, bool IsPostDom> class IDFCalculatorBase {
public:
using OrderedNodeTy =
typename std::conditional<IsPostDom, Inverse<NodeTy *>, NodeTy *>::type;
using ChildrenGetterTy =
IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>;
IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT) : DT(DT) {}
IDFCalculatorBase(DominatorTreeBase<NodeTy, IsPostDom> &DT,
const ChildrenGetterTy &C)
: DT(DT), ChildrenGetter(C) {}
/// Give the IDF calculator the set of blocks in which the value is
/// defined. This is equivalent to the set of starting blocks it should be
/// calculating the IDF for (though later gets pruned based on liveness).
///
/// Note: This set *must* live for the entire lifetime of the IDF calculator.
void setDefiningBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
DefBlocks = &Blocks;
}
/// Give the IDF calculator the set of blocks in which the value is
/// live on entry to the block. This is used to prune the IDF calculation to
/// not include blocks where any phi insertion would be dead.
///
/// Note: This set *must* live for the entire lifetime of the IDF calculator.
void setLiveInBlocks(const SmallPtrSetImpl<NodeTy *> &Blocks) {
LiveInBlocks = &Blocks;
useLiveIn = true;
}
/// Reset the live-in block set to be empty, and tell the IDF
/// calculator to not use liveness anymore.
void resetLiveInBlocks() {
LiveInBlocks = nullptr;
useLiveIn = false;
}
/// Calculate iterated dominance frontiers
///
/// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
/// the file-level comment. It performs DF->IDF pruning using the live-in
/// set, to avoid computing the IDF for blocks where an inserted PHI node
/// would be dead.
void calculate(SmallVectorImpl<NodeTy *> &IDFBlocks);
private:
DominatorTreeBase<NodeTy, IsPostDom> &DT;
ChildrenGetterTy ChildrenGetter;
bool useLiveIn = false;
const SmallPtrSetImpl<NodeTy *> *LiveInBlocks;
const SmallPtrSetImpl<NodeTy *> *DefBlocks;
};
//===----------------------------------------------------------------------===//
// Implementation.
//===----------------------------------------------------------------------===//
namespace IDFCalculatorDetail {
template <class NodeTy, bool IsPostDom>
typename ChildrenGetterTy<NodeTy, IsPostDom>::ChildrenTy
ChildrenGetterTy<NodeTy, IsPostDom>::get(const NodeRef &N) {
using OrderedNodeTy =
typename IDFCalculatorBase<NodeTy, IsPostDom>::OrderedNodeTy;
auto Children = children<OrderedNodeTy>(N);
return {Children.begin(), Children.end()};
}
} // end of namespace IDFCalculatorDetail
template <class NodeTy, bool IsPostDom>
void IDFCalculatorBase<NodeTy, IsPostDom>::calculate(
SmallVectorImpl<NodeTy *> &PHIBlocks) {
// Use a priority queue keyed on dominator tree level so that inserted nodes
// are handled from the bottom of the dominator tree upwards. We also augment
// the level with a DFS number to ensure that the blocks are ordered in a
// deterministic way.
using DomTreeNodePair =
std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
using IDFPriorityQueue =
std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
less_second>;
IDFPriorityQueue PQ;
DT.updateDFSNumbers();
for (NodeTy *BB : *DefBlocks) {
if (DomTreeNodeBase<NodeTy> *Node = DT.getNode(BB))
PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
}
SmallVector<DomTreeNodeBase<NodeTy> *, 32> Worklist;
SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedPQ;
SmallPtrSet<DomTreeNodeBase<NodeTy> *, 32> VisitedWorklist;
while (!PQ.empty()) {
DomTreeNodePair RootPair = PQ.top();
PQ.pop();
DomTreeNodeBase<NodeTy> *Root = RootPair.first;
unsigned RootLevel = RootPair.second.first;
// Walk all dominator tree children of Root, inspecting their CFG edges with
// targets elsewhere on the dominator tree. Only targets whose level is at
// most Root's level are added to the iterated dominance frontier of the
// definition set.
Worklist.clear();
Worklist.push_back(Root);
VisitedWorklist.insert(Root);
while (!Worklist.empty()) {
DomTreeNodeBase<NodeTy> *Node = Worklist.pop_back_val();
NodeTy *BB = Node->getBlock();
// Succ is the successor in the direction we are calculating IDF, so it is
// successor for IDF, and predecessor for Reverse IDF.
auto DoWork = [&](NodeTy *Succ) {
DomTreeNodeBase<NodeTy> *SuccNode = DT.getNode(Succ);
const unsigned SuccLevel = SuccNode->getLevel();
if (SuccLevel > RootLevel)
return;
if (!VisitedPQ.insert(SuccNode).second)
return;
NodeTy *SuccBB = SuccNode->getBlock();
if (useLiveIn && !LiveInBlocks->count(SuccBB))
return;
PHIBlocks.emplace_back(SuccBB);
if (!DefBlocks->count(SuccBB))
PQ.push(std::make_pair(
SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
};
for (auto Succ : ChildrenGetter.get(BB))
DoWork(Succ);
for (auto DomChild : *Node) {
if (VisitedWorklist.insert(DomChild).second)
Worklist.push_back(DomChild);
}
}
}
}
} // end of namespace llvm
#endif
|