Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / NaturalLoops.h
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
30 namespace WTF {
31
32 template<typename Graph>
33 class NaturalLoops;
34
35 template<typename Graph>
36 class NaturalLoop {
37 public:
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     
93 private:
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
110 template<typename Graph>
111 class NaturalLoops {
112 public:
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     
350 private:
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
362 using WTF::NaturalLoop;
363 using WTF::NaturalLoops;