89ca68b9c8ba7eb2c5509a77060658afec4f16e8
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGNaturalLoops.cpp
1 /*
2  * Copyright (C) 2013 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 #include "config.h"
27 #include "DFGNaturalLoops.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32 #include "JSCInlines.h"
33 #include <wtf/CommaPrinter.h>
34
35 namespace JSC { namespace DFG {
36
37 void NaturalLoop::dump(PrintStream& out) const
38 {
39     out.print("[Header: ", *header(), ", Body:");
40     for (unsigned i = 0; i < m_body.size(); ++i)
41         out.print(" ", *m_body[i]);
42     out.print("]");
43 }
44
45 NaturalLoops::NaturalLoops(Graph& graph)
46 {
47     ASSERT(graph.m_dominators);
48
49     // Implement the classic dominator-based natural loop finder. The first
50     // step is to find all control flow edges A -> B where B dominates A.
51     // Then B is a loop header and A is a backward branching block. We will
52     // then accumulate, for each loop header, multiple backward branching
53     // blocks. Then we backwards graph search from the backward branching
54     // blocks to their loop headers, which gives us all of the blocks in the
55     // loop body.
56     
57     static const bool verbose = false;
58     
59     if (verbose) {
60         dataLog("Dominators:\n");
61         graph.m_dominators->dump(WTF::dataFile());
62     }
63     
64     m_loops.resize(0);
65     
66     for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
67         BasicBlock* block = graph.block(blockIndex);
68         if (!block)
69             continue;
70         
71         for (unsigned i = block->numSuccessors(); i--;) {
72             BasicBlock* successor = block->successor(i);
73             if (!graph.m_dominators->dominates(successor, block))
74                 continue;
75             bool found = false;
76             for (unsigned j = m_loops.size(); j--;) {
77                 if (m_loops[j].header() == successor) {
78                     m_loops[j].addBlock(block);
79                     found = true;
80                     break;
81                 }
82             }
83             if (found)
84                 continue;
85             NaturalLoop loop(successor, m_loops.size());
86             loop.addBlock(block);
87             m_loops.append(loop);
88         }
89     }
90     
91     if (verbose)
92         dataLog("After bootstrap: ", *this, "\n");
93     
94     FastBitVector seenBlocks;
95     Vector<BasicBlock*, 4> blockWorklist;
96     seenBlocks.resize(graph.numBlocks());
97     
98     for (unsigned i = m_loops.size(); i--;) {
99         NaturalLoop& loop = m_loops[i];
100         
101         seenBlocks.clearAll();
102         ASSERT(blockWorklist.isEmpty());
103         
104         if (verbose)
105             dataLog("Dealing with loop ", loop, "\n");
106         
107         for (unsigned j = loop.size(); j--;) {
108             seenBlocks.set(loop[j]->index);
109             blockWorklist.append(loop[j]);
110         }
111         
112         while (!blockWorklist.isEmpty()) {
113             BasicBlock* block = blockWorklist.takeLast();
114             
115             if (verbose)
116                 dataLog("    Dealing with ", *block, "\n");
117             
118             if (block == loop.header())
119                 continue;
120             
121             for (unsigned j = block->predecessors.size(); j--;) {
122                 BasicBlock* predecessor = block->predecessors[j];
123                 if (seenBlocks.get(predecessor->index))
124                     continue;
125                 
126                 loop.addBlock(predecessor);
127                 blockWorklist.append(predecessor);
128                 seenBlocks.set(predecessor->index);
129             }
130         }
131     }
132
133     // Figure out reverse mapping from blocks to loops.
134     for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
135         BasicBlock* block = graph.block(blockIndex);
136         if (!block)
137             continue;
138         for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
139             block->innerMostLoopIndices[i] = UINT_MAX;
140     }
141     for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
142         NaturalLoop& loop = m_loops[loopIndex];
143         
144         for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
145             BasicBlock* block = loop[blockIndexInLoop];
146             
147             for (unsigned i = 0; i < BasicBlock::numberOfInnerMostLoopIndices; ++i) {
148                 unsigned thisIndex = block->innerMostLoopIndices[i];
149                 if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
150                     insertIntoBoundedVector(
151                         block->innerMostLoopIndices, BasicBlock::numberOfInnerMostLoopIndices,
152                         loopIndex, i);
153                     break;
154                 }
155             }
156         }
157     }
158     
159     // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
160     // this to figure out loop parenting.
161     for (unsigned i = m_loops.size(); i--;) {
162         NaturalLoop& loop = m_loops[i];
163         RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
164         
165         loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
166     }
167     
168     if (validationEnabled()) {
169         // Do some self-verification that we've done some of this correctly.
170         
171         for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
172             BasicBlock* block = graph.block(blockIndex);
173             if (!block)
174                 continue;
175             
176             Vector<const NaturalLoop*> simpleLoopsOf;
177             
178             for (unsigned i = m_loops.size(); i--;) {
179                 if (m_loops[i].contains(block))
180                     simpleLoopsOf.append(&m_loops[i]);
181             }
182             
183             Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
184             
185             std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
186             std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
187             
188             RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
189         }
190     }
191     
192     if (verbose)
193         dataLog("Results: ", *this, "\n");
194 }
195
196 NaturalLoops::~NaturalLoops() { }
197
198 Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
199 {
200     Vector<const NaturalLoop*> result;
201     for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
202         result.append(loop);
203     return result;
204 }
205
206 void NaturalLoops::dump(PrintStream& out) const
207 {
208     out.print("NaturalLoops:{");
209     CommaPrinter comma;
210     for (unsigned i = 0; i < m_loops.size(); ++i)
211         out.print(comma, m_loops[i]);
212     out.print("}");
213 }
214
215 } } // namespace JSC::DFG
216
217 #endif // ENABLE(DFG_JIT)
218