1/*
2 * Copyright (C) 2013-2019 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 {
37 WTF_MAKE_FAST_ALLOCATED;
38public:
39 NaturalLoop()
40 : m_graph(nullptr)
41 , m_header(nullptr)
42 , m_outerLoopIndex(UINT_MAX)
43 {
44 }
45
46 NaturalLoop(Graph& graph, typename Graph::Node header, unsigned index)
47 : m_graph(&graph)
48 , m_header(header)
49 , m_outerLoopIndex(UINT_MAX)
50 , m_index(index)
51 {
52 }
53
54 Graph* graph() const { return m_graph; }
55
56 typename Graph::Node header() const { return m_header; }
57
58 unsigned size() const { return m_body.size(); }
59 typename Graph::Node at(unsigned i) const { return m_body[i]; }
60 typename Graph::Node operator[](unsigned i) const { return at(i); }
61
62 // This is the slower, but simpler, way of asking if a block belongs to
63 // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
64 // tries to be O(loop depth) rather than O(loop size). Loop depth is
65 // almost always smaller than loop size. A *lot* smaller.
66 bool contains(typename Graph::Node block) const
67 {
68 for (unsigned i = m_body.size(); i--;) {
69 if (m_body[i] == block)
70 return true;
71 }
72 ASSERT(block != header()); // Header should be contained.
73 return false;
74 }
75
76 // The index of this loop in NaturalLoops.
77 unsigned index() const { return m_index; }
78
79 bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
80
81 void dump(PrintStream& out) const
82 {
83 if (!m_graph) {
84 out.print("<null>");
85 return;
86 }
87
88 out.print("[Header: ", m_graph->dump(header()), ", Body:");
89 for (unsigned i = 0; i < m_body.size(); ++i)
90 out.print(" ", m_graph->dump(m_body[i]));
91 out.print("]");
92 }
93
94private:
95 template<typename>
96 friend class NaturalLoops;
97
98 void addBlock(typename Graph::Node block)
99 {
100 ASSERT(!m_body.contains(block)); // The NaturalLoops algorithm relies on blocks being unique in this vector.
101 m_body.append(block);
102 }
103
104 Graph* m_graph;
105 typename Graph::Node m_header;
106 Vector<typename Graph::Node, 4> m_body;
107 unsigned m_outerLoopIndex;
108 unsigned m_index;
109};
110
111template<typename Graph>
112class NaturalLoops {
113 WTF_MAKE_FAST_ALLOCATED;
114public:
115 typedef std::array<unsigned, 2> InnerMostLoopIndices;
116
117 NaturalLoops(Graph& graph, Dominators<Graph>& dominators, bool selfCheck = false)
118 : m_graph(graph)
119 , m_innerMostLoopIndices(graph.template newMap<InnerMostLoopIndices>())
120 {
121 // Implement the classic dominator-based natural loop finder. The first
122 // step is to find all control flow edges A -> B where B dominates A.
123 // Then B is a loop header and A is a backward branching block. We will
124 // then accumulate, for each loop header, multiple backward branching
125 // blocks. Then we backwards graph search from the backward branching
126 // blocks to their loop headers, which gives us all of the blocks in the
127 // loop body.
128
129 static constexpr bool verbose = false;
130
131 if (verbose) {
132 dataLog("Dominators:\n");
133 dominators.dump(WTF::dataFile());
134 }
135
136 m_loops.shrink(0);
137
138 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
139 typename Graph::Node header = graph.node(blockIndex);
140 if (!header)
141 continue;
142
143 for (unsigned i = graph.predecessors(header).size(); i--;) {
144 typename Graph::Node footer = graph.predecessors(header)[i];
145 if (!dominators.dominates(header, footer))
146 continue;
147 // At this point, we've proven 'header' is actually a loop header and
148 // that 'footer' is a loop footer.
149 bool found = false;
150 for (unsigned j = m_loops.size(); j--;) {
151 if (m_loops[j].header() == header) {
152 m_loops[j].addBlock(footer);
153 found = true;
154 break;
155 }
156 }
157 if (found)
158 continue;
159 NaturalLoop<Graph> loop(graph, header, m_loops.size());
160 loop.addBlock(footer);
161 m_loops.append(loop);
162 }
163 }
164
165 if (verbose)
166 dataLog("After bootstrap: ", *this, "\n");
167
168 FastBitVector seenBlocks;
169 Vector<typename Graph::Node, 4> blockWorklist;
170 seenBlocks.resize(graph.numNodes());
171
172 for (unsigned i = m_loops.size(); i--;) {
173 NaturalLoop<Graph>& loop = m_loops[i];
174
175 seenBlocks.clearAll();
176 ASSERT(blockWorklist.isEmpty());
177
178 if (verbose)
179 dataLog("Dealing with loop ", loop, "\n");
180
181 for (unsigned j = loop.size(); j--;) {
182 seenBlocks[graph.index(loop[j])] = true;
183 blockWorklist.append(loop[j]);
184 }
185
186 while (!blockWorklist.isEmpty()) {
187 typename Graph::Node block = blockWorklist.takeLast();
188
189 if (verbose)
190 dataLog(" Dealing with ", graph.dump(block), "\n");
191
192 if (block == loop.header())
193 continue;
194
195 for (unsigned j = graph.predecessors(block).size(); j--;) {
196 typename Graph::Node predecessor = graph.predecessors(block)[j];
197 if (seenBlocks[graph.index(predecessor)])
198 continue;
199
200 loop.addBlock(predecessor);
201 blockWorklist.append(predecessor);
202 seenBlocks[graph.index(predecessor)] = true;
203 }
204 }
205 }
206
207 // Figure out reverse mapping from blocks to loops.
208 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
209 typename Graph::Node block = graph.node(blockIndex);
210 if (!block)
211 continue;
212 for (unsigned i = std::tuple_size<InnerMostLoopIndices>::value; i--;)
213 m_innerMostLoopIndices[block][i] = UINT_MAX;
214 }
215 for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
216 NaturalLoop<Graph>& loop = m_loops[loopIndex];
217
218 for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
219 typename Graph::Node block = loop[blockIndexInLoop];
220
221 for (unsigned i = 0; i < std::tuple_size<InnerMostLoopIndices>::value; ++i) {
222 unsigned thisIndex = m_innerMostLoopIndices[block][i];
223 if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
224 insertIntoBoundedVector(
225 m_innerMostLoopIndices[block], std::tuple_size<InnerMostLoopIndices>::value,
226 loopIndex, i);
227 break;
228 }
229 }
230 }
231 }
232
233 // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
234 // this to figure out loop parenting.
235 for (unsigned i = m_loops.size(); i--;) {
236 NaturalLoop<Graph>& loop = m_loops[i];
237 RELEASE_ASSERT(m_innerMostLoopIndices[loop.header()][0] == i);
238
239 loop.m_outerLoopIndex = m_innerMostLoopIndices[loop.header()][1];
240 }
241
242 if (selfCheck) {
243 // Do some self-verification that we've done some of this correctly.
244
245 for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
246 typename Graph::Node block = graph.node(blockIndex);
247 if (!block)
248 continue;
249
250 Vector<const NaturalLoop<Graph>*> simpleLoopsOf;
251
252 for (unsigned i = m_loops.size(); i--;) {
253 if (m_loops[i].contains(block))
254 simpleLoopsOf.append(&m_loops[i]);
255 }
256
257 Vector<const NaturalLoop<Graph>*> fancyLoopsOf = loopsOf(block);
258
259 std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
260 std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
261
262 RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
263 }
264 }
265
266 if (verbose)
267 dataLog("Results: ", *this, "\n");
268 }
269
270 Graph& graph() { return m_graph; }
271
272 unsigned numLoops() const
273 {
274 return m_loops.size();
275 }
276 const NaturalLoop<Graph>& loop(unsigned i) const
277 {
278 return m_loops[i];
279 }
280
281 // Return either null if the block isn't a loop header, or the
282 // loop it belongs to.
283 const NaturalLoop<Graph>* headerOf(typename Graph::Node block) const
284 {
285 const NaturalLoop<Graph>* loop = innerMostLoopOf(block);
286 if (!loop)
287 return nullptr;
288 if (loop->header() == block)
289 return loop;
290 if (!ASSERT_DISABLED) {
291 for (; loop; loop = innerMostOuterLoop(*loop))
292 ASSERT(loop->header() != block);
293 }
294 return nullptr;
295 }
296
297 const NaturalLoop<Graph>* innerMostLoopOf(typename Graph::Node block) const
298 {
299 unsigned index = m_innerMostLoopIndices[block][0];
300 if (index == UINT_MAX)
301 return nullptr;
302 return &m_loops[index];
303 }
304
305 const NaturalLoop<Graph>* innerMostOuterLoop(const NaturalLoop<Graph>& loop) const
306 {
307 if (loop.m_outerLoopIndex == UINT_MAX)
308 return nullptr;
309 return &m_loops[loop.m_outerLoopIndex];
310 }
311
312 bool belongsTo(typename Graph::Node block, const NaturalLoop<Graph>& candidateLoop) const
313 {
314 // It's faster to do this test using the loop itself, if it's small.
315 if (candidateLoop.size() < 4)
316 return candidateLoop.contains(block);
317
318 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
319 if (loop == &candidateLoop)
320 return true;
321 }
322 return false;
323 }
324
325 unsigned loopDepth(typename Graph::Node block) const
326 {
327 unsigned depth = 0;
328 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
329 depth++;
330 return depth;
331 }
332
333 // Return all loops this belongs to. The first entry in the vector is the innermost loop. The last is the
334 // outermost loop.
335 Vector<const NaturalLoop<Graph>*> loopsOf(typename Graph::Node block) const
336 {
337 Vector<const NaturalLoop<Graph>*> result;
338 for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
339 result.append(loop);
340 return result;
341 }
342
343 void dump(PrintStream& out) const
344 {
345 out.print("NaturalLoops:{");
346 CommaPrinter comma;
347 for (unsigned i = 0; i < m_loops.size(); ++i)
348 out.print(comma, m_loops[i]);
349 out.print("}");
350 }
351
352private:
353 Graph& m_graph;
354
355 // If we ever had a scalability problem in our natural loop finder, we could
356 // use some HashMap's here. But it just feels a heck of a lot less convenient.
357 Vector<NaturalLoop<Graph>, 4> m_loops;
358
359 typename Graph::template Map<InnerMostLoopIndices> m_innerMostLoopIndices;
360};
361
362} // namespace WTF
363
364using WTF::NaturalLoop;
365using WTF::NaturalLoops;
366