1/*
2 * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Dominators.h>
29
30namespace WTF {
31
32template<typename Graph>
33class NaturalLoops;
34
35template<typename Graph>
36class NaturalLoop {
37public:
38 NaturalLoop()
39 : m_graph(nullptr)
40 , m_header(nullptr)
41 , m_outerLoopIndex(UINT_MAX)
42 {
43 }
44
45 NaturalLoop(Graph& graph, typename Graph::Node header, unsigned index)
46 : m_graph(&graph)
47 , m_header(header)
48 , m_outerLoopIndex(UINT_MAX)
49 , m_index(index)
50 {
51 }
52
53 Graph* graph() const { return m_graph; }
54
55 typename Graph::Node header() const { return m_header; }
56
57 unsigned size() const { return m_body.size(); }
58 typename Graph::Node at(unsigned i) const { return m_body[i]; }
59 typename Graph::Node operator[](unsigned i) const { return at(i); }
60
61 // This is the slower, but simpler, way of asking if a block belongs to
62 // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
63 // tries to be O(loop depth) rather than O(loop size). Loop depth is
64 // almost always smaller than loop size. A *lot* smaller.
65 bool contains(typename Graph::Node block) const
66 {
67 for (unsigned i = m_body.size(); i--;) {
68 if (m_body[i] == block)
69 return true;
70 }
71 ASSERT(block != header()); // Header should be contained.
72 return false;
73 }
74
75 // The index of this loop in NaturalLoops.
76 unsigned index() const { return m_index; }
77
78 bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
79
80 void dump(PrintStream& out) const
81 {
82 if (!m_graph) {
83 out.print("<null>");
84 return;
85 }
86
87 out.print("[Header: ", m_graph->dump(header()), ", Body:");
88 for (unsigned i = 0; i < m_body.size(); ++i)
89 out.print(" ", m_graph->dump(m_body[i]));
90 out.print("]");
91 }
92
93private:
94 template<typename>
95 friend class NaturalLoops;
96
97 void addBlock(typename Graph::Node block)
98 {
99 ASSERT(!m_body.contains(block)); // The NaturalLoops algorithm relies on blocks being unique in this vector.
100 m_body.append(block);
101 }
102
103 Graph* m_graph;
104 typename Graph::Node m_header;
105 Vector<typename Graph::Node, 4> m_body;
106 unsigned m_outerLoopIndex;
107 unsigned m_index;
108};
109
110template<typename Graph>
111class NaturalLoops {
112public:
113 typedef std::array<unsigned, 2> InnerMostLoopIndices;
114
115 NaturalLoops(Graph& graph, Dominators<Graph>& dominators, bool selfCheck = false)
116 : m_graph(graph)
117 , m_innerMostLoopIndices(graph.template newMap<InnerMostLoopIndices>())
118 {
119 // Implement the classic dominator-based natural loop finder. The first
120 // step is to find all control flow edges A -> B where B dominates A.
121 // Then B is a loop header and A is a backward branching block. We will
122 // then accumulate, for each loop header, multiple backward branching
123 // blocks. Then we backwards graph search from the backward branching
124 // blocks to their loop headers, which gives us all of the blocks in the
125 // loop body.
126
127 static const bool verbose = false;
128
129 if (verbose) {
130 dataLog("Dominators:\n");
131 dominators.dump(WTF::dataFile());
132 }
133
134 m_loops.shrink(0);
135
136 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
137 typename Graph::Node header = graph.node(blockIndex);
138 if (!header)
139 continue;
140
141 for (unsigned i = graph.predecessors(header).size(); i--;) {
142 typename Graph::Node footer = graph.predecessors(header)[i];
143 if (!dominators.dominates(header, footer))
144 continue;
145 // At this point, we've proven 'header' is actually a loop header and
146 // that 'footer' is a loop footer.
147 bool found = false;
148 for (unsigned j = m_loops.size(); j--;) {
149 if (m_loops[j].header() == header) {
150 m_loops[j].addBlock(footer);
151 found = true;
152 break;
153 }
154 }
155 if (found)
156 continue;
157 NaturalLoop<Graph> loop(graph, header, m_loops.size());
158 loop.addBlock(footer);
159 m_loops.append(loop);
160 }
161 }
162
163 if (verbose)
164 dataLog("After bootstrap: ", *this, "\n");
165
166 FastBitVector seenBlocks;
167 Vector<typename Graph::Node, 4> blockWorklist;
168 seenBlocks.resize(graph.numNodes());
169
170 for (unsigned i = m_loops.size(); i--;) {
171 NaturalLoop<Graph>& loop = m_loops[i];
172
173 seenBlocks.clearAll();
174 ASSERT(blockWorklist.isEmpty());
175
176 if (verbose)
177 dataLog("Dealing with loop ", loop, "\n");
178
179 for (unsigned j = loop.size(); j--;) {
180 seenBlocks[graph.index(loop[j])] = true;
181 blockWorklist.append(loop[j]);
182 }
183
184 while (!blockWorklist.isEmpty()) {
185 typename Graph::Node block = blockWorklist.takeLast();
186
187 if (verbose)
188 dataLog(" Dealing with ", graph.dump(block), "\n");
189
190 if (block == loop.header())
191 continue;
192
193 for (unsigned j = graph.predecessors(block).size(); j--;) {
194 typename Graph::Node predecessor = graph.predecessors(block)[j];
195 if (seenBlocks[graph.index(predecessor)])
196 continue;
197
198 loop.addBlock(predecessor);
199 blockWorklist.append(predecessor);
200 seenBlocks[graph.index(predecessor)] = true;
201 }
202 }
203 }
204
205 // Figure out reverse mapping from blocks to loops.
206 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
207 typename Graph::Node block = graph.node(blockIndex);
208 if (!block)
209 continue;
210 for (unsigned i = std::tuple_size<InnerMostLoopIndices>::value; i--;)
211 m_innerMostLoopIndices[block][i] = UINT_MAX;
212 }
213 for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
214 NaturalLoop<Graph>& loop = m_loops[loopIndex];
215
216 for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
217 typename Graph::Node block = loop[blockIndexInLoop];
218
219 for (unsigned i = 0; i < std::tuple_size<InnerMostLoopIndices>::value; ++i) {
220 unsigned thisIndex = m_innerMostLoopIndices[block][i];
221 if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
222 insertIntoBoundedVector(
223 m_innerMostLoopIndices[block], std::tuple_size<InnerMostLoopIndices>::value,
224 loopIndex, i);
225 break;
226 }
227 }
228 }
229 }
230
231 // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
232 // this to figure out loop parenting.
233 for (unsigned i = m_loops.size(); i--;) {
234 NaturalLoop<Graph>& loop = m_loops[i];
235 RELEASE_ASSERT(m_innerMostLoopIndices[loop.header()][0] == i);
236
237 loop.m_outerLoopIndex = m_innerMostLoopIndices[loop.header()][1];
238 }
239
240 if (selfCheck) {
241 // Do some self-verification that we've done some of this correctly.
242
243 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
244 typename Graph::Node block = graph.node(blockIndex);
245 if (!block)
246 continue;
247
248 Vector<const NaturalLoop<Graph>*> simpleLoopsOf;
249
250 for (unsigned i = m_loops.size(); i--;) {
251 if (m_loops[i].contains(block))
252 simpleLoopsOf.append(&m_loops[i]);
253 }
254
255 Vector<const NaturalLoop<Graph>*> fancyLoopsOf = loopsOf(block);
256
257 std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
258 std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
259
260 RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
261 }
262 }
263
264 if (verbose)
265 dataLog("Results: ", *this, "\n");
266 }
267
268 Graph& graph() { return m_graph; }
269
270 unsigned numLoops() const
271 {
272 return m_loops.size();
273 }
274 const NaturalLoop<Graph>& loop(unsigned i) const
275 {
276 return m_loops[i];
277 }
278
279 // Return either null if the block isn't a loop header, or the
280 // loop it belongs to.
281 const NaturalLoop<Graph>* headerOf(typename Graph::Node block) const
282 {
283 const NaturalLoop<Graph>* loop = innerMostLoopOf(block);
284 if (!loop)
285 return nullptr;
286 if (loop->header() == block)
287 return loop;
288 if (!ASSERT_DISABLED) {
289 for (; loop; loop = innerMostOuterLoop(*loop))
290 ASSERT(loop->header() != block);
291 }
292 return nullptr;
293 }
294
295 const NaturalLoop<Graph>* innerMostLoopOf(typename Graph::Node block) const
296 {
297 unsigned index = m_innerMostLoopIndices[block][0];
298 if (index == UINT_MAX)
299 return nullptr;
300 return &m_loops[index];
301 }
302
303 const NaturalLoop<Graph>* innerMostOuterLoop(const NaturalLoop<Graph>& loop) const
304 {
305 if (loop.m_outerLoopIndex == UINT_MAX)
306 return nullptr;
307 return &m_loops[loop.m_outerLoopIndex];
308 }
309
310 bool belongsTo(typename Graph::Node block, const NaturalLoop<Graph>& candidateLoop) const
311 {
312 // It's faster to do this test using the loop itself, if it's small.
313 if (candidateLoop.size() < 4)
314 return candidateLoop.contains(block);
315
316 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
317 if (loop == &candidateLoop)
318 return true;
319 }
320 return false;
321 }
322
323 unsigned loopDepth(typename Graph::Node block) const
324 {
325 unsigned depth = 0;
326 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
327 depth++;
328 return depth;
329 }
330
331 // Return all loops this belongs to. The first entry in the vector is the innermost loop. The last is the
332 // outermost loop.
333 Vector<const NaturalLoop<Graph>*> loopsOf(typename Graph::Node block) const
334 {
335 Vector<const NaturalLoop<Graph>*> result;
336 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
337 result.append(loop);
338 return result;
339 }
340
341 void dump(PrintStream& out) const
342 {
343 out.print("NaturalLoops:{");
344 CommaPrinter comma;
345 for (unsigned i = 0; i < m_loops.size(); ++i)
346 out.print(comma, m_loops[i]);
347 out.print("}");
348 }
349
350private:
351 Graph& m_graph;
352
353 // If we ever had a scalability problem in our natural loop finder, we could
354 // use some HashMap's here. But it just feels a heck of a lot less convenient.
355 Vector<NaturalLoop<Graph>, 4> m_loops;
356
357 typename Graph::template Map<InnerMostLoopIndices> m_innerMostLoopIndices;
358};
359
360} // namespace WTF
361
362using WTF::NaturalLoop;
363using WTF::NaturalLoops;
364