DFG LICM needs to go all-in on the idea that some loops can't be LICMed
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLICMPhase.cpp
1 /*
2  * Copyright (C) 2013-2016 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 "DFGLICMPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractInterpreterInlines.h"
32 #include "DFGAtTailAbstractState.h"
33 #include "DFGBasicBlockInlines.h"
34 #include "DFGClobberSet.h"
35 #include "DFGClobberize.h"
36 #include "DFGControlEquivalenceAnalysis.h"
37 #include "DFGEdgeDominates.h"
38 #include "DFGGraph.h"
39 #include "DFGInsertionSet.h"
40 #include "DFGMayExit.h"
41 #include "DFGNaturalLoops.h"
42 #include "DFGPhase.h"
43 #include "DFGSafeToExecute.h"
44 #include "JSCInlines.h"
45
46 namespace JSC { namespace DFG {
47
48 namespace {
49
50 struct LoopData {
51     LoopData()
52         : preHeader(nullptr)
53     {
54     }
55     
56     ClobberSet writes;
57     BasicBlock* preHeader;
58 };
59
60 } // anonymous namespace
61
62 class LICMPhase : public Phase {
63     static const bool verbose = false;
64     
65 public:
66     LICMPhase(Graph& graph)
67         : Phase(graph, "LICM")
68         , m_state(graph)
69         , m_interpreter(graph, m_state)
70     {
71     }
72     
73     bool run()
74     {
75         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
76         
77         m_graph.ensureDominators();
78         m_graph.ensureNaturalLoops();
79         m_graph.ensureControlEquivalenceAnalysis();
80
81         if (verbose) {
82             dataLog("Graph before LICM:\n");
83             m_graph.dump();
84         }
85         
86         m_data.resize(m_graph.m_naturalLoops->numLoops());
87         
88         // Figure out the set of things each loop writes to, not including blocks that
89         // belong to inner loops. We fix this later.
90         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
91             BasicBlock* block = m_graph.block(blockIndex);
92             if (!block)
93                 continue;
94             
95             // Skip blocks that are proved to not execute.
96             // FIXME: This shouldn't be needed.
97             // https://bugs.webkit.org/show_bug.cgi?id=128584
98             if (!block->cfaHasVisited)
99                 continue;
100             
101             const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
102             if (!loop)
103                 continue;
104             LoopData& data = m_data[loop->index()];
105             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
106                 Node* node = block->at(nodeIndex);
107                 
108                 // Don't look beyond parts of the code that definitely always exit.
109                 // FIXME: This shouldn't be needed.
110                 // https://bugs.webkit.org/show_bug.cgi?id=128584
111                 if (node->op() == ForceOSRExit)
112                     break;
113
114                 addWrites(m_graph, node, data.writes);
115             }
116         }
117         
118         // For each loop:
119         // - Identify its pre-header.
120         // - Make sure its outer loops know what it clobbers.
121         for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
122             const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
123             LoopData& data = m_data[loop.index()];
124             
125             for (
126                 const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
127                 outerLoop;
128                 outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
129                 m_data[outerLoop->index()].writes.addAll(data.writes);
130             
131             BasicBlock* header = loop.header();
132             BasicBlock* preHeader = nullptr;
133             unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
134
135             // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
136             // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
137             // which cuts out the one other way of having a loop header with only one predecessor.)
138             DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
139             
140             for (unsigned i = header->predecessors.size(); i--;) {
141                 BasicBlock* predecessor = header->predecessors[i];
142                 if (m_graph.m_dominators->dominates(header, predecessor))
143                     continue;
144
145                 preHeader = predecessor;
146                 ++numberOfPreHeaders;
147             }
148
149             // We need to validate the pre-header. There are a bunch of things that could be wrong
150             // about it:
151             //
152             // - There might be more than one. This means that pre-header creation either did not run,
153             //   or some CFG transformation destroyed the pre-headers.
154             //
155             // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
156             //   LICM assumes that it can always hoist checks. See
157             //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
158             //   would need to check if it's OK to exit at the pre-header since if we can't then we
159             //   would have to restrict hoisting to non-exiting nodes.
160
161             if (numberOfPreHeaders != 1)
162                 continue;
163
164             // This is guaranteed because the header has multiple predecessors and critical edges are
165             // broken. Therefore the predecessors must all have one successor, which implies that they
166             // must end in a Jump.
167             DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
168
169             if (!preHeader->terminal()->origin.exitOK)
170                 continue;
171             
172             data.preHeader = preHeader;
173         }
174         
175         m_graph.initializeNodeOwners();
176         
177         // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
178         // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
179         // - The node doesn't write anything.
180         // - The node doesn't read anything that the loop writes.
181         // - The preHeader is valid (i.e. it passed the validation above).
182         // - The preHeader's state at tail makes the node safe to execute.
183         // - The loop's children all belong to nodes that strictly dominate the loop header.
184         // - The preHeader's state at tail is still valid. This is mostly to save compile
185         //   time and preserve some kind of sanity, if we hoist something that must exit.
186         //
187         // Also, we need to remember to:
188         // - Update the state-at-tail with the node we hoisted, so future hoist candidates
189         //   know about any type checks we hoisted.
190         //
191         // For maximum profit, we walk blocks in DFS order to ensure that we generally
192         // tend to hoist dominators before dominatees.
193         Vector<const NaturalLoop*> loopStack;
194         bool changed = false;
195         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
196             const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
197             if (!loop)
198                 continue;
199             
200             loopStack.resize(0);
201             for (
202                 const NaturalLoop* current = loop;
203                 current;
204                 current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
205                 loopStack.append(current);
206             
207             // Remember: the loop stack has the inner-most loop at index 0, so if we want
208             // to bias hoisting to outer loops then we need to use a reverse loop.
209             
210             if (verbose) {
211                 dataLog(
212                     "Attempting to hoist out of block ", *block, " in loops:\n");
213                 for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
214                     dataLog(
215                         "        ", *loopStack[stackIndex], ", which writes ",
216                         m_data[loopStack[stackIndex]->index()].writes, "\n");
217                 }
218             }
219             
220             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
221                 Node*& nodeRef = block->at(nodeIndex);
222                 if (doesWrites(m_graph, nodeRef)) {
223                     if (verbose)
224                         dataLog("    Not hoisting ", nodeRef, " because it writes things.\n");
225                     continue;
226                 }
227
228                 for (unsigned stackIndex = loopStack.size(); stackIndex--;)
229                     changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
230             }
231         }
232         
233         return changed;
234     }
235
236 private:
237     bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
238     {
239         Node* node = nodeRef;
240         LoopData& data = m_data[loop->index()];
241
242         if (!data.preHeader) {
243             if (verbose)
244                 dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
245             return false;
246         }
247         
248         if (!data.preHeader->cfaDidFinish) {
249             if (verbose)
250                 dataLog("    Not hoisting ", node, " because CFA is invalid.\n");
251             return false;
252         }
253         
254         if (!edgesDominate(m_graph, node, data.preHeader)) {
255             if (verbose) {
256                 dataLog(
257                     "    Not hoisting ", node, " because it isn't loop invariant.\n");
258             }
259             return false;
260         }
261         
262         // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
263         // we could still hoist just the checks.
264         // https://bugs.webkit.org/show_bug.cgi?id=144525
265         
266         if (readsOverlap(m_graph, node, data.writes)) {
267             if (verbose) {
268                 dataLog(
269                     "    Not hoisting ", node,
270                     " because it reads things that the loop writes.\n");
271             }
272             return false;
273         }
274         
275         m_state.initializeTo(data.preHeader);
276         if (!safeToExecute(m_state, m_graph, node)) {
277             if (verbose) {
278                 dataLog(
279                     "    Not hoisting ", node, " because it isn't safe to execute.\n");
280             }
281             return false;
282         }
283         
284         NodeOrigin originalOrigin = node->origin;
285
286         // NOTE: We could just use BackwardsDominators here directly, since we already know that the
287         // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
288         // dominance checks are O(1) and only a few integer compares.
289         bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
290             && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
291         
292         if (addsBlindSpeculation
293             && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
294             if (verbose) {
295                 dataLog(
296                     "    Not hoisting ", node, " because it may exit and the pre-header (",
297                     *data.preHeader, ") is not control equivalent to the node's original block (",
298                     *fromBlock, ") and hoisting had previously failed.\n");
299             }
300             return false;
301         }
302         
303         if (verbose) {
304             dataLog(
305                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
306                 "\n");
307         }
308
309         // FIXME: We should adjust the Check: flags on the edges of node. There are phases that assume
310         // that those flags are correct even if AI is stale.
311         // https://bugs.webkit.org/show_bug.cgi?id=148544
312         data.preHeader->insertBeforeTerminal(node);
313         node->owner = data.preHeader;
314         NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
315         node->origin = terminalOrigin.withSemantic(node->origin.semantic);
316         node->origin.wasHoisted |= addsBlindSpeculation;
317         
318         // Modify the states at the end of the preHeader of the loop we hoisted to,
319         // and all pre-headers inside the loop. This isn't a stability bottleneck right now
320         // because most loops are small and most blocks belong to few loops.
321         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
322             BasicBlock* subBlock = loop->at(bodyIndex);
323             const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
324             if (!subLoop)
325                 continue;
326             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
327             // We may not have given this loop a pre-header because either it didn't have exitOK
328             // or the header had multiple predecessors that it did not dominate. In that case the
329             // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
330             if (!subPreHeader)
331                 continue;
332             // The pre-header's tail may be unreachable, in which case we have nothing to do.
333             if (!subPreHeader->cfaDidFinish)
334                 continue;
335             m_state.initializeTo(subPreHeader);
336             m_interpreter.execute(node);
337         }
338         
339         // It just so happens that all of the nodes we currently know how to hoist
340         // don't have var-arg children. That may change and then we can fix this
341         // code. But for now we just assert that's the case.
342         DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
343         
344         nodeRef = m_graph.addNode(SpecNone, Check, originalOrigin, node->children);
345         
346         return true;
347     }
348     
349     AtTailAbstractState m_state;
350     AbstractInterpreter<AtTailAbstractState> m_interpreter;
351     Vector<LoopData> m_data;
352 };
353
354 bool performLICM(Graph& graph)
355 {
356     return runPhase<LICMPhase>(graph);
357 }
358
359 } } // namespace JSC::DFG
360
361 #endif // ENABLE(DFG_JIT)
362