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
46namespace JSC { namespace DFG {
47
48class 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
58public:
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
226private:
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
469bool performLICM(Graph& graph)
470{
471 return runPhase<LICMPhase>(graph);
472}
473
474} } // namespace JSC::DFG
475
476#endif // ENABLE(DFG_JIT)
477
478