1/*
2 * Copyright (C) 2012-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 "DFGTypeCheckHoistingPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlock.h"
32#include "DFGGraph.h"
33#include "DFGInsertionSet.h"
34#include "DFGPhase.h"
35#include "DFGVariableAccessDataDump.h"
36#include "JSCInlines.h"
37#include <wtf/HashMap.h>
38
39namespace JSC { namespace DFG {
40
41enum CheckBallot { VoteOther, VoteStructureCheck = 1, VoteCheckArray = 1 };
42
43struct ArrayTypeCheck;
44struct StructureTypeCheck;
45
46struct CheckData {
47 Structure* m_structure;
48 ArrayMode m_arrayMode;
49 bool m_arrayModeIsValid;
50 bool m_arrayModeHoistingOkay;
51
52 CheckData()
53 : m_structure(0)
54 , m_arrayModeIsValid(false)
55 , m_arrayModeHoistingOkay(false)
56 {
57 }
58
59 CheckData(Structure* structure)
60 : m_structure(structure)
61 , m_arrayModeIsValid(false)
62 , m_arrayModeHoistingOkay(true)
63 {
64 }
65
66 CheckData(ArrayMode arrayMode)
67 : m_structure(0)
68 , m_arrayMode(arrayMode)
69 , m_arrayModeIsValid(true)
70 , m_arrayModeHoistingOkay(true)
71 {
72 }
73
74 void disableCheckArrayHoisting()
75 {
76 m_arrayModeIsValid = false;
77 m_arrayModeHoistingOkay = false;
78 }
79};
80
81class TypeCheckHoistingPhase : public Phase {
82public:
83 TypeCheckHoistingPhase(Graph& graph)
84 : Phase(graph, "structure check hoisting")
85 {
86 }
87
88 bool run()
89 {
90 ASSERT(m_graph.m_form == ThreadedCPS);
91
92 clearVariableVotes();
93 identifyRedundantStructureChecks();
94 disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();
95
96 clearVariableVotes();
97 identifyRedundantArrayChecks();
98 disableHoistingForVariablesWithInsufficientVotes<ArrayTypeCheck>();
99
100 disableHoistingAcrossOSREntries<StructureTypeCheck>();
101 disableHoistingAcrossOSREntries<ArrayTypeCheck>();
102
103 bool changed = false;
104
105 // Place CheckStructure's at SetLocal sites.
106 InsertionSet insertionSet(m_graph);
107 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
108 BasicBlock* block = m_graph.block(blockIndex);
109 if (!block)
110 continue;
111 unsigned indexForChecks = UINT_MAX;
112 NodeOrigin originForChecks;
113 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
114 Node* node = block->at(indexInBlock);
115
116 if (node->origin.exitOK) {
117 indexForChecks = indexInBlock;
118 originForChecks = node->origin;
119 }
120
121 // Be careful not to use 'node' after appending to the graph. In those switch
122 // cases where we need to append, we first carefully extract everything we need
123 // from the node, before doing any appending.
124 switch (node->op()) {
125 case SetArgumentDefinitely: {
126 // Insert a GetLocal and a CheckStructure immediately following this
127 // SetArgumentDefinitely, if the variable was a candidate for structure hoisting.
128 // If the basic block previously only had the SetArgumentDefinitely as its
129 // variable-at-tail, then replace it with this GetLocal.
130 VariableAccessData* variable = node->variableAccessData();
131 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
132 if (iter == m_map.end())
133 break;
134 if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
135 break;
136
137 // Currently we should only be doing this hoisting for SetArguments at a CFG root.
138 ASSERT(m_graph.isRoot(block));
139
140 NodeOrigin origin = node->origin;
141 RELEASE_ASSERT(origin.exitOK);
142
143 Node* getLocal = insertionSet.insertNode(
144 indexInBlock + 1, variable->prediction(), GetLocal, origin,
145 OpInfo(variable), Edge(node));
146 if (iter->value.m_structure) {
147 auto checkOp = CheckStructure;
148 if (SpecCellCheck & SpecEmpty) {
149 VirtualRegister local = node->variableAccessData()->local();
150 auto* inlineCallFrame = node->origin.semantic.inlineCallFrame();
151 if ((local - (inlineCallFrame ? inlineCallFrame->stackOffset : 0)) == virtualRegisterForArgument(0)) {
152 // |this| can be the TDZ value. The call entrypoint won't have |this| as TDZ,
153 // but a catch or a loop OSR entry may have |this| be TDZ.
154 checkOp = CheckStructureOrEmpty;
155 }
156 }
157
158 insertionSet.insertNode(
159 indexInBlock + 1, SpecNone, checkOp, origin,
160 OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
161 Edge(getLocal, CellUse));
162 } else if (iter->value.m_arrayModeIsValid) {
163 ASSERT(iter->value.m_arrayModeHoistingOkay);
164 insertionSet.insertNode(
165 indexInBlock + 1, SpecNone, CheckArray, origin,
166 OpInfo(iter->value.m_arrayMode.asWord()),
167 Edge(getLocal, CellUse));
168 } else
169 RELEASE_ASSERT_NOT_REACHED();
170
171 if (block->variablesAtTail.operand(variable->local()) == node)
172 block->variablesAtTail.operand(variable->local()) = getLocal;
173
174 m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocal);
175
176 changed = true;
177 break;
178 }
179
180 case SetLocal: {
181 VariableAccessData* variable = node->variableAccessData();
182 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
183 if (iter == m_map.end())
184 break;
185 if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
186 break;
187
188 NodeOrigin origin = node->origin;
189 Edge child1 = node->child1();
190
191 if (iter->value.m_structure) {
192 // Note: On 64-bit platforms, cell checks allow the empty value to flow through.
193 // This means that this structure check may see the empty value as input. We need
194 // to emit a node that explicitly handles the empty value. Most of the time, CheckStructureOrEmpty
195 // will be folded to CheckStructure because AI proves that the incoming value is
196 // definitely not empty.
197 insertionSet.insertNode(
198 indexForChecks, SpecNone, (SpecCellCheck & SpecEmpty) ? CheckStructureOrEmpty : CheckStructure,
199 originForChecks.withSemantic(origin.semantic),
200 OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
201 Edge(child1.node(), CellUse));
202 } else if (iter->value.m_arrayModeIsValid) {
203 ASSERT(iter->value.m_arrayModeHoistingOkay);
204 insertionSet.insertNode(
205 indexForChecks, SpecNone, CheckArray,
206 originForChecks.withSemantic(origin.semantic),
207 OpInfo(iter->value.m_arrayMode.asWord()),
208 Edge(child1.node(), CellUse));
209 } else
210 RELEASE_ASSERT_NOT_REACHED();
211 changed = true;
212 break;
213 }
214
215 default:
216 break;
217 }
218 }
219 insertionSet.execute(block);
220 }
221
222 return changed;
223 }
224
225private:
226 void clearVariableVotes()
227 {
228 for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
229 VariableAccessData* variable = &m_graph.m_variableAccessData[i];
230 if (!variable->isRoot())
231 continue;
232 variable->clearVotes();
233 }
234 }
235
236 // Identify the set of variables that are always subject to the same structure
237 // checks. For now, only consider monomorphic structure checks (one structure).
238 void identifyRedundantStructureChecks()
239 {
240 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
241 BasicBlock* block = m_graph.block(blockIndex);
242 if (!block)
243 continue;
244 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
245 Node* node = block->at(indexInBlock);
246 switch (node->op()) {
247 case CheckStructure: {
248 Node* child = node->child1().node();
249 if (child->op() != GetLocal)
250 break;
251 VariableAccessData* variable = child->variableAccessData();
252 variable->vote(VoteStructureCheck);
253 if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
254 break;
255 noticeStructureCheck(variable, node->structureSet());
256 break;
257 }
258
259 case ArrayifyToStructure:
260 case Arrayify:
261 case GetByOffset:
262 case PutByOffset:
263 case PutStructure:
264 case AllocatePropertyStorage:
265 case ReallocatePropertyStorage:
266 case NukeStructureAndSetButterfly:
267 case GetButterfly:
268 case GetByVal:
269 case PutByValDirect:
270 case PutByVal:
271 case PutByValAlias:
272 case GetArrayLength:
273 case CheckArray:
274 case GetIndexedPropertyStorage:
275 case GetTypedArrayByteOffset:
276 case Phantom:
277 case MovHint:
278 case MultiGetByOffset:
279 case MultiPutByOffset:
280 // Don't count these uses.
281 break;
282
283 case SetLocal: {
284 // Find all uses of the source of the SetLocal. If any of them are a
285 // kind of CheckStructure, then we should notice them to ensure that
286 // we're not hoisting a check that would contravene checks that are
287 // already being performed.
288 VariableAccessData* variable = node->variableAccessData();
289 if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
290 break;
291 Node* source = node->child1().node();
292 for (auto* subNode : *block) {
293 switch (subNode->op()) {
294 case CheckStructure: {
295 if (subNode->child1() != source)
296 break;
297
298 noticeStructureCheck(variable, subNode->structureSet());
299 break;
300 }
301 default:
302 break;
303 }
304 }
305
306 m_graph.voteChildren(node, VoteOther);
307 break;
308 }
309
310 default:
311 m_graph.voteChildren(node, VoteOther);
312 break;
313 }
314 }
315 }
316 }
317
318 void identifyRedundantArrayChecks()
319 {
320 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
321 BasicBlock* block = m_graph.block(blockIndex);
322 if (!block)
323 continue;
324 for (auto* node : *block) {
325 switch (node->op()) {
326 case CheckArray: {
327 Node* child = node->child1().node();
328 if (child->op() != GetLocal)
329 break;
330 VariableAccessData* variable = child->variableAccessData();
331 variable->vote(VoteCheckArray);
332 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
333 break;
334 noticeCheckArray(variable, node->arrayMode());
335 break;
336 }
337
338 case CheckStructure:
339 case GetByOffset:
340 case PutByOffset:
341 case PutStructure:
342 case ReallocatePropertyStorage:
343 case GetButterfly:
344 case GetByVal:
345 case PutByValDirect:
346 case PutByVal:
347 case PutByValAlias:
348 case GetArrayLength:
349 case GetIndexedPropertyStorage:
350 case Phantom:
351 case MovHint:
352 case MultiGetByOffset:
353 case MultiPutByOffset:
354 // Don't count these uses.
355 break;
356
357 case AllocatePropertyStorage:
358 case ArrayifyToStructure:
359 case Arrayify: {
360 // Any Arrayify could change our indexing type, so disable
361 // all CheckArray hoisting.
362 Node* child = node->child1().node();
363 if (child->op() != GetLocal)
364 break;
365 VariableAccessData* variable = child->variableAccessData();
366 variable->vote(VoteOther);
367 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
368 break;
369 disableCheckArrayHoisting(variable);
370 break;
371 }
372
373 case SetLocal: {
374 // Find all uses of the source of the SetLocal. If any of them are a
375 // kind of CheckStructure, then we should notice them to ensure that
376 // we're not hoisting a check that would contravene checks that are
377 // already being performed.
378 VariableAccessData* variable = node->variableAccessData();
379 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
380 break;
381 Node* source = node->child1().node();
382 for (auto subNode : *block) {
383 switch (subNode->op()) {
384 case CheckStructure: {
385 if (subNode->child1() != source)
386 break;
387
388 noticeStructureCheckAccountingForArrayMode(variable, subNode->structureSet());
389 break;
390 }
391 case CheckArray: {
392 if (subNode->child1() != source)
393 break;
394 noticeCheckArray(variable, subNode->arrayMode());
395 break;
396 }
397 default:
398 break;
399 }
400 }
401
402 m_graph.voteChildren(node, VoteOther);
403 break;
404 }
405
406 default:
407 m_graph.voteChildren(node, VoteOther);
408 break;
409 }
410 }
411 }
412 }
413
414 // Disable hoisting on variables that appear to mostly be used in
415 // contexts where it doesn't make sense.
416 template <typename TypeCheck>
417 void disableHoistingForVariablesWithInsufficientVotes()
418 {
419 for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
420 VariableAccessData* variable = &m_graph.m_variableAccessData[i];
421 if (!variable->isRoot())
422 continue;
423 if (TypeCheck::hasEnoughVotesToHoist(variable))
424 continue;
425 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
426 if (iter == m_map.end())
427 continue;
428 TypeCheck::disableHoisting(iter->value);
429 }
430 }
431
432 // Disable check hoisting for variables that cross the OSR entry that
433 // we're currently taking, and where the value currently does not have the
434 // particular form we want (e.g. a contradictory ArrayMode or Struture).
435 template <typename TypeCheck>
436 void disableHoistingAcrossOSREntries()
437 {
438 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
439 BasicBlock* block = m_graph.block(blockIndex);
440 if (!block)
441 continue;
442 ASSERT(block->isReachable);
443 if (!block->isOSRTarget)
444 continue;
445 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
446 continue;
447 const Operands<Optional<JSValue>>& mustHandleValues = m_graph.m_plan.mustHandleValues();
448 for (size_t i = 0; i < mustHandleValues.size(); ++i) {
449 int operand = mustHandleValues.operandForIndex(i);
450 Node* node = block->variablesAtHead.operand(operand);
451 if (!node)
452 continue;
453 VariableAccessData* variable = node->variableAccessData();
454 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
455 if (iter == m_map.end())
456 continue;
457 if (!TypeCheck::isValidToHoist(iter->value))
458 continue;
459 Optional<JSValue> value = mustHandleValues[i];
460 if (!value || !value.value() || !value.value().isCell() || TypeCheck::isContravenedByValue(iter->value, value.value())) {
461 TypeCheck::disableHoisting(iter->value);
462 continue;
463 }
464 }
465 }
466 }
467
468 void disableCheckArrayHoisting(VariableAccessData* variable)
469 {
470 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData());
471 result.iterator->value.disableCheckArrayHoisting();
472 }
473
474 template <typename TypeCheck>
475 bool shouldConsiderForHoisting(VariableAccessData* variable)
476 {
477 if (!variable->shouldUnboxIfPossible())
478 return false;
479 if (TypeCheck::hoistingPreviouslyFailed(variable))
480 return false;
481 if (!isCellSpeculation(variable->prediction()))
482 return false;
483 return true;
484 }
485
486 void noticeStructureCheck(VariableAccessData* variable, RegisteredStructure structure)
487 {
488 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(structure.get()));
489 if (result.isNewEntry)
490 return;
491 if (result.iterator->value.m_structure == structure.get())
492 return;
493 result.iterator->value.m_structure = 0;
494 }
495
496 void noticeStructureCheck(VariableAccessData* variable, RegisteredStructureSet set)
497 {
498 if (set.size() != 1) {
499 noticeStructureCheck(variable, RegisteredStructure());
500 return;
501 }
502 noticeStructureCheck(variable, set.at(0));
503 }
504
505 void noticeCheckArray(VariableAccessData* variable, ArrayMode arrayMode)
506 {
507 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(arrayMode));
508 if (result.isNewEntry)
509 return;
510 if (!result.iterator->value.m_arrayModeHoistingOkay)
511 return;
512 if (result.iterator->value.m_arrayMode == arrayMode)
513 return;
514 if (!result.iterator->value.m_arrayModeIsValid) {
515 result.iterator->value.m_arrayMode = arrayMode;
516 result.iterator->value.m_arrayModeIsValid = true;
517 return;
518 }
519 result.iterator->value.disableCheckArrayHoisting();
520 }
521
522 void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructure structure)
523 {
524 HashMap<VariableAccessData*, CheckData>::iterator result = m_map.find(variable);
525 if (result == m_map.end())
526 return;
527 if (!result->value.m_arrayModeHoistingOkay || !result->value.m_arrayModeIsValid)
528 return;
529 if (result->value.m_arrayMode.structureWouldPassArrayModeFiltering(structure.get()))
530 return;
531 result->value.disableCheckArrayHoisting();
532 }
533
534 void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructureSet set)
535 {
536 for (unsigned i = 0; i < set.size(); i++)
537 noticeStructureCheckAccountingForArrayMode(variable, set.at(i));
538 }
539
540 HashMap<VariableAccessData*, CheckData> m_map;
541};
542
543bool performTypeCheckHoisting(Graph& graph)
544{
545 return runPhase<TypeCheckHoistingPhase>(graph);
546}
547
548struct ArrayTypeCheck {
549 static bool isValidToHoist(CheckData& checkData)
550 {
551 return checkData.m_arrayModeIsValid;
552 }
553
554 static void disableHoisting(CheckData& checkData)
555 {
556 checkData.disableCheckArrayHoisting();
557 }
558
559 static bool isContravenedByValue(CheckData& checkData, JSValue value)
560 {
561 ASSERT(value.isCell());
562 return !checkData.m_arrayMode.structureWouldPassArrayModeFiltering(value.asCell()->structure());
563 }
564
565 static bool hasEnoughVotesToHoist(VariableAccessData* variable)
566 {
567 return variable->voteRatio() >= Options::checkArrayVoteRatioForHoisting();
568 }
569
570 static bool hoistingPreviouslyFailed(VariableAccessData* variable)
571 {
572 return variable->checkArrayHoistingFailed();
573 }
574};
575
576struct StructureTypeCheck {
577 static bool isValidToHoist(CheckData& checkData)
578 {
579 return checkData.m_structure;
580 }
581
582 static void disableHoisting(CheckData& checkData)
583 {
584 checkData.m_structure = 0;
585 }
586
587 static bool isContravenedByValue(CheckData& checkData, JSValue value)
588 {
589 ASSERT(value.isCell());
590 return checkData.m_structure != value.asCell()->structure();
591 }
592
593 static bool hasEnoughVotesToHoist(VariableAccessData* variable)
594 {
595 return variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting();
596 }
597
598 static bool hoistingPreviouslyFailed(VariableAccessData* variable)
599 {
600 return variable->structureCheckHoistingFailed();
601 }
602};
603
604} } // namespace JSC::DFG
605
606#endif // ENABLE(DFG_JIT)
607
608
609