465f472fdd21014a429592e2db75b59df7a96254
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLICMPhase.cpp
1 /*
2  * Copyright (C) 2013-2018 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 class LICMPhase : public Phase {
49     static const bool verbose = false;
50
51     using NaturalLoop = SSANaturalLoop;
52
53     struct LoopData {
54         ClobberSet writes;
55         BasicBlock* preHeader { nullptr };
56     };
57     
58 public:
59     LICMPhase(Graph& graph)
60         : Phase(graph, "LICM")
61         , m_state(graph)
62         , m_interpreter(graph, m_state)
63     {
64     }
65     
66     bool run()
67     {
68         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
69         
70         m_graph.ensureSSADominators();
71         m_graph.ensureSSANaturalLoops();
72         m_graph.ensureControlEquivalenceAnalysis();
73
74         if (verbose) {
75             dataLog("Graph before LICM:\n");
76             m_graph.dump();
77         }
78         
79         m_data.resize(m_graph.m_ssaNaturalLoops->numLoops());
80         
81         // Figure out the set of things each loop writes to, not including blocks that
82         // belong to inner loops. We fix this later.
83         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
84             BasicBlock* block = m_graph.block(blockIndex);
85             if (!block)
86                 continue;
87             
88             // Skip blocks that are proved to not execute.
89             // FIXME: This shouldn't be needed.
90             // https://bugs.webkit.org/show_bug.cgi?id=128584
91             if (!block->cfaHasVisited)
92                 continue;
93             
94             const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
95             if (!loop)
96                 continue;
97             LoopData& data = m_data[loop->index()];
98             for (auto* node : *block) {
99                 // Don't look beyond parts of the code that definitely always exit.
100                 // FIXME: This shouldn't be needed.
101                 // https://bugs.webkit.org/show_bug.cgi?id=128584
102                 if (node->op() == ForceOSRExit)
103                     break;
104
105                 addWrites(m_graph, node, data.writes);
106             }
107         }
108         
109         // For each loop:
110         // - Identify its pre-header.
111         // - Make sure its outer loops know what it clobbers.
112         for (unsigned loopIndex = m_graph.m_ssaNaturalLoops->numLoops(); loopIndex--;) {
113             const NaturalLoop& loop = m_graph.m_ssaNaturalLoops->loop(loopIndex);
114             LoopData& data = m_data[loop.index()];
115             
116             for (
117                 const NaturalLoop* outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(loop);
118                 outerLoop;
119                 outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*outerLoop))
120                 m_data[outerLoop->index()].writes.addAll(data.writes);
121             
122             BasicBlock* header = loop.header();
123             BasicBlock* preHeader = nullptr;
124             unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
125
126             // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
127             // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
128             // which cuts out the one other way of having a loop header with only one predecessor.)
129             DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1, header->predecessors.size());
130             
131             for (unsigned i = header->predecessors.size(); i--;) {
132                 BasicBlock* predecessor = header->predecessors[i];
133                 if (m_graph.m_ssaDominators->dominates(header, predecessor))
134                     continue;
135
136                 preHeader = predecessor;
137                 ++numberOfPreHeaders;
138             }
139
140             // We need to validate the pre-header. There are a bunch of things that could be wrong
141             // about it:
142             //
143             // - There might be more than one. This means that pre-header creation either did not run,
144             //   or some CFG transformation destroyed the pre-headers.
145             //
146             // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
147             //   LICM assumes that it can always hoist checks. See
148             //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
149             //   would need to check if it's OK to exit at the pre-header since if we can't then we
150             //   would have to restrict hoisting to non-exiting nodes.
151
152             if (numberOfPreHeaders != 1)
153                 continue;
154
155             // This is guaranteed because the header has multiple predecessors and critical edges are
156             // broken. Therefore the predecessors must all have one successor, which implies that they
157             // must end in a Jump.
158             DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump, preHeader->terminal()->op());
159
160             if (!preHeader->terminal()->origin.exitOK)
161                 continue;
162             
163             data.preHeader = preHeader;
164         }
165         
166         m_graph.initializeNodeOwners();
167         
168         // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
169         // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
170         // - The node doesn't write anything.
171         // - The node doesn't read anything that the loop writes.
172         // - The preHeader is valid (i.e. it passed the validation above).
173         // - The preHeader's state at tail makes the node safe to execute.
174         // - The loop's children all belong to nodes that strictly dominate the loop header.
175         // - The preHeader's state at tail is still valid. This is mostly to save compile
176         //   time and preserve some kind of sanity, if we hoist something that must exit.
177         //
178         // Also, we need to remember to:
179         // - Update the state-at-tail with the node we hoisted, so future hoist candidates
180         //   know about any type checks we hoisted.
181         //
182         // For maximum profit, we walk blocks in DFS order to ensure that we generally
183         // tend to hoist dominators before dominatees.
184         Vector<const NaturalLoop*> loopStack;
185         bool changed = false;
186         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
187             if (!block->cfaHasVisited)
188                 continue;
189
190             const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
191             if (!loop)
192                 continue;
193             
194             loopStack.shrink(0);
195             for (
196                 const NaturalLoop* current = loop;
197                 current;
198                 current = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*current))
199                 loopStack.append(current);
200             
201             // Remember: the loop stack has the inner-most loop at index 0, so if we want
202             // to bias hoisting to outer loops then we need to use a reverse loop.
203             
204             if (verbose) {
205                 dataLog(
206                     "Attempting to hoist out of block ", *block, " in loops:\n");
207                 for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
208                     dataLog(
209                         "        ", *loopStack[stackIndex], ", which writes ",
210                         m_data[loopStack[stackIndex]->index()].writes, "\n");
211                 }
212             }
213             
214             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
215                 Node*& nodeRef = block->at(nodeIndex);
216                 if (nodeRef->op() == ForceOSRExit)
217                     break;
218                 for (unsigned stackIndex = loopStack.size(); stackIndex--;)
219                     changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
220             }
221         }
222
223         return changed;
224     }
225
226 private:
227     bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
228     {
229         Node* node = nodeRef;
230         LoopData& data = m_data[loop->index()];
231
232         if (!data.preHeader) {
233             if (verbose)
234                 dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
235             return false;
236         }
237         
238         if (!data.preHeader->cfaDidFinish) {
239             if (verbose)
240                 dataLog("    Not hoisting ", node, " because CFA is invalid.\n");
241             return false;
242         }
243         
244         m_state.initializeTo(data.preHeader);
245         ASSERT(m_state.isValid());
246         NodeOrigin originalOrigin = node->origin;
247         bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
248
249         // NOTE: We could just use BackwardsDominators here directly, since we already know that the
250         // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
251         // dominance checks are O(1) and only a few integer compares.
252         bool isControlEquivalent = m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
253
254         bool addsBlindSpeculation = !isControlEquivalent;
255         NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
256         Vector<Node*, 2> hoistedNodes; // This is sorted in the program order they will appear in the basic block we're hoisting to.
257
258         auto insertHoistedNode = [&] (Node* node) {
259             data.preHeader->insertBeforeTerminal(node);
260             node->owner = data.preHeader;
261             node->origin = terminalOrigin.withSemantic(node->origin.semantic);
262             node->origin.wasHoisted |= addsBlindSpeculation;
263             hoistedNodes.append(node);
264         };
265
266         auto updateAbstractState = [&] {
267             auto invalidate = [&] (const NaturalLoop* loop) {
268                 LoopData& data = m_data[loop->index()];
269                 data.preHeader->cfaDidFinish = false;
270
271                 for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
272                     BasicBlock* block = loop->at(bodyIndex);
273                     if (block != data.preHeader)
274                         block->cfaHasVisited = false;
275                     block->cfaDidFinish = false;
276                 }
277             };
278
279             // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
280             m_state.trustEdgeProofs();
281             for (unsigned i = 0; i < hoistedNodes.size(); ++i) {
282                 if (!m_interpreter.execute(hoistedNodes[i])) {
283                     invalidate(loop);
284                     return;
285                 }
286             }
287
288             // However, when walking various inner loops below, the proof status of
289             // an edge may be trivially true, even if it's not true in the preheader
290             // we hoist to. We don't allow the below node executions to change the
291             // state of edge proofs. An example of where a proof is trivially true
292             // is if we have two loops, L1 and L2, where L2 is nested inside L1. The
293             // header for L1 dominates L2. We hoist a Check from L1's header into L1's
294             // preheader. However, inside L2's preheader, we can't trust that AI will
295             // tell us this edge is proven. It's proven in L2's preheader because L2
296             // is dominated by L1's header. However, the edge is not guaranteed to be
297             // proven inside L1's preheader.
298             m_state.dontTrustEdgeProofs();
299
300             // Modify the states at the end of the preHeader of the loop we hoisted to,
301             // and all pre-headers inside the loop. This isn't a stability bottleneck right now
302             // because most loops are small and most blocks belong to few loops.
303             for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
304                 BasicBlock* subBlock = loop->at(bodyIndex);
305                 const NaturalLoop* subLoop = m_graph.m_ssaNaturalLoops->headerOf(subBlock);
306                 if (!subLoop)
307                     continue;
308                 BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
309                 // We may not have given this loop a pre-header because either it didn't have exitOK
310                 // or the header had multiple predecessors that it did not dominate. In that case the
311                 // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
312                 if (!subPreHeader)
313                     continue;
314                 // The pre-header's tail may be unreachable, in which case we have nothing to do.
315                 if (!subPreHeader->cfaDidFinish)
316                     continue;
317                 // We handled this above.
318                 if (subPreHeader == data.preHeader)
319                     continue;
320                 m_state.initializeTo(subPreHeader);
321                 for (unsigned i = 0; i < hoistedNodes.size(); ++i) {
322                     if (!m_interpreter.execute(hoistedNodes[i])) {
323                         invalidate(subLoop);
324                         break;
325                     }
326                 }
327             }
328         };
329         
330         auto tryHoistChecks = [&] {
331             if (addsBlindSpeculation && !canSpeculateBlindly)
332                 return false;
333
334             ASSERT(hoistedNodes.isEmpty());
335
336             Vector<Edge, 3> checks;
337             m_graph.doToChildren(node, [&] (Edge edge) {
338                 if (!m_graph.m_ssaDominators->dominates(edge.node()->owner, data.preHeader))
339                     return;
340
341                 if (!edge.willHaveCheck())
342                     return;
343
344                 if ((m_state.forNode(edge).m_type & SpecEmpty) && checkMayCrashIfInputIsEmpty(edge.useKind())) {
345                     if (!canSpeculateBlindly)
346                         return;
347                     Node* checkNotEmpty = m_graph.addNode(CheckNotEmpty, originalOrigin, Edge(edge.node(), UntypedUse));
348                     insertHoistedNode(checkNotEmpty);
349                 }
350
351                 checks.append(edge);
352             });
353
354             if (checks.isEmpty())
355                 return false;
356
357             AdjacencyList children;
358             NodeType checkOp = Check;
359             if (checks.size() <= AdjacencyList::Size) {
360                 children = AdjacencyList(AdjacencyList::Fixed);
361                 for (unsigned i = 0; i < checks.size(); ++i)
362                     children.setChild(i, checks[i]);
363             } else {
364                 checkOp = CheckVarargs;
365                 unsigned firstChild = m_graph.m_varArgChildren.size();
366                 for (Edge edge : checks)
367                     m_graph.m_varArgChildren.append(edge);
368                 children = AdjacencyList(AdjacencyList::Variable, firstChild, checks.size());
369             }
370
371             Node* check = m_graph.addNode(checkOp, originalOrigin, children);
372             insertHoistedNode(check);
373             updateAbstractState();
374
375             if (verbose)
376                 dataLogLn("    Hoisted some checks from ", node, " and created a new Check ", check, ". Hoisted from ", *fromBlock, " to ", *data.preHeader);
377
378             return true;
379         };
380
381         if (!edgesDominate(m_graph, node, data.preHeader)) {
382             if (verbose) {
383                 dataLog(
384                     "    Not hoisting ", node, " because it isn't loop invariant.\n");
385             }
386             return tryHoistChecks();
387         }
388
389         if (doesWrites(m_graph, node)) {
390             if (verbose)
391                 dataLog("    Not hoisting ", node, " because it writes things.\n");
392             return tryHoistChecks();
393         }
394
395         // It's not safe to consult the AbstractState inside mayExit until we prove all edges
396         // dominate the pre-header we're hoisting to. We are more conservative above when assigning
397         // to this variable since we hadn't yet proven all edges dominate the pre-header. Above, we
398         // just assume mayExit is true. We refine that here since we can now consult the AbstractState.
399         addsBlindSpeculation = mayExit(m_graph, node, m_state) && !isControlEquivalent;
400
401         if (readsOverlap(m_graph, node, data.writes)) {
402             if (verbose) {
403                 dataLog(
404                     "    Not hoisting ", node,
405                     " because it reads things that the loop writes.\n");
406             }
407             return tryHoistChecks();
408         }
409         
410         if (addsBlindSpeculation && !canSpeculateBlindly) {
411             if (verbose) {
412                 dataLog(
413                     "    Not hoisting ", node, " because it may exit and the pre-header (",
414                     *data.preHeader, ") is not control equivalent to the node's original block (",
415                     *fromBlock, ") and hoisting had previously failed.\n");
416             }
417             return tryHoistChecks();
418         }
419         
420         if (!safeToExecute(m_state, m_graph, node)) {
421             // See if we can rescue the situation by inserting blind speculations.
422             bool ignoreEmptyChildren = true;
423             if (canSpeculateBlindly
424                 && safeToExecute(m_state, m_graph, node, ignoreEmptyChildren)) {
425                 if (verbose) {
426                     dataLog(
427                         "    Rescuing hoisting by inserting empty checks.\n");
428                 }
429                 m_graph.doToChildren(
430                     node,
431                     [&] (Edge& edge) {
432                         if (!(m_state.forNode(edge).m_type & SpecEmpty))
433                             return;
434                         
435                         Node* check = m_graph.addNode(CheckNotEmpty, originalOrigin, Edge(edge.node(), UntypedUse));
436                         insertHoistedNode(check);
437                     });
438             } else {
439                 if (verbose) {
440                     dataLog(
441                         "    Not hoisting ", node, " because it isn't safe to execute.\n");
442                 }
443                 return tryHoistChecks();
444             }
445         }
446         
447         if (verbose) {
448             dataLog(
449                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
450                 "\n");
451         }
452
453         insertHoistedNode(node);
454         updateAbstractState();
455
456         if (node->flags() & NodeHasVarArgs)
457             nodeRef = m_graph.addNode(CheckVarargs, originalOrigin, m_graph.copyVarargChildren(node));
458         else
459             nodeRef = m_graph.addNode(Check, originalOrigin, node->children);
460         
461         return true;
462     }
463     
464     AtTailAbstractState m_state;
465     AbstractInterpreter<AtTailAbstractState> m_interpreter;
466     Vector<LoopData> m_data;
467 };
468
469 bool performLICM(Graph& graph)
470 {
471     return runPhase<LICMPhase>(graph);
472 }
473
474 } } // namespace JSC::DFG
475
476 #endif // ENABLE(DFG_JIT)
477