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 | |
30 | namespace WTF { |
31 | |
32 | template<typename Graph> |
33 | class NaturalLoops; |
34 | |
35 | template<typename Graph> |
36 | class NaturalLoop { |
37 | WTF_MAKE_FAST_ALLOCATED; |
38 | public: |
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 , 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 () 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 | |
94 | private: |
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 ; |
106 | Vector<typename Graph::Node, 4> m_body; |
107 | unsigned m_outerLoopIndex; |
108 | unsigned m_index; |
109 | }; |
110 | |
111 | template<typename Graph> |
112 | class NaturalLoops { |
113 | WTF_MAKE_FAST_ALLOCATED; |
114 | public: |
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 = graph.node(blockIndex); |
140 | if (!header) |
141 | continue; |
142 | |
143 | for (unsigned i = graph.predecessors(header).size(); i--;) { |
144 | typename Graph::Node = 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>* (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 | |
352 | private: |
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 | |
364 | using WTF::NaturalLoop; |
365 | using WTF::NaturalLoops; |
366 | |