1/*
2 * Copyright (C) 2011-2017 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 "DFGPredictionPropagationPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32#include "DFGPhase.h"
33#include "JSCInlines.h"
34
35namespace JSC { namespace DFG {
36
37namespace {
38
39bool verboseFixPointLoops = false;
40
41class PredictionPropagationPhase : public Phase {
42public:
43 PredictionPropagationPhase(Graph& graph)
44 : Phase(graph, "prediction propagation")
45 {
46 }
47
48 bool run()
49 {
50 ASSERT(m_graph.m_form == ThreadedCPS);
51 ASSERT(m_graph.m_unificationState == GloballyUnified);
52
53 m_pass = PrimaryPass;
54
55 propagateThroughArgumentPositions();
56
57 processInvariants();
58
59 propagateToFixpoint();
60
61 m_pass = RareCasePass;
62 propagateToFixpoint();
63
64 m_pass = DoubleVotingPass;
65 unsigned counter = 0;
66 do {
67 if (verboseFixPointLoops)
68 ++counter;
69
70 m_changed = false;
71 doRoundOfDoubleVoting();
72 if (!m_changed)
73 break;
74 m_changed = false;
75 propagateForward();
76 } while (m_changed);
77
78 if (verboseFixPointLoops)
79 dataLog("Iterated ", counter, " times in double voting fixpoint.\n");
80
81 return true;
82 }
83
84private:
85 void propagateToFixpoint()
86 {
87 unsigned counter = 0;
88 do {
89 if (verboseFixPointLoops)
90 ++counter;
91
92 m_changed = false;
93
94 // Forward propagation is near-optimal for both topologically-sorted and
95 // DFS-sorted code.
96 propagateForward();
97 if (!m_changed)
98 break;
99
100 // Backward propagation reduces the likelihood that pathological code will
101 // cause slowness. Loops (especially nested ones) resemble backward flow.
102 // This pass captures two cases: (1) it detects if the forward fixpoint
103 // found a sound solution and (2) short-circuits backward flow.
104 m_changed = false;
105 propagateBackward();
106 } while (m_changed);
107
108 if (verboseFixPointLoops)
109 dataLog("Iterated ", counter, " times in propagateToFixpoint.\n");
110 }
111
112 bool setPrediction(SpeculatedType prediction)
113 {
114 ASSERT(m_currentNode->hasResult());
115
116 // setPrediction() is used when we know that there is no way that we can change
117 // our minds about what the prediction is going to be. There is no semantic
118 // difference between setPrediction() and mergeSpeculation() other than the
119 // increased checking to validate this property.
120 ASSERT(m_currentNode->prediction() == SpecNone || m_currentNode->prediction() == prediction);
121
122 return m_currentNode->predict(prediction);
123 }
124
125 bool mergePrediction(SpeculatedType prediction)
126 {
127 ASSERT(m_currentNode->hasResult());
128
129 return m_currentNode->predict(prediction);
130 }
131
132 SpeculatedType speculatedDoubleTypeForPrediction(SpeculatedType value)
133 {
134 SpeculatedType result = SpecDoubleReal;
135 if (value & SpecDoubleImpureNaN)
136 result |= SpecDoubleImpureNaN;
137 if (value & SpecDoublePureNaN)
138 result |= SpecDoublePureNaN;
139 if (!isFullNumberOrBooleanSpeculation(value))
140 result |= SpecDoublePureNaN;
141 return result;
142 }
143
144 SpeculatedType speculatedDoubleTypeForPredictions(SpeculatedType left, SpeculatedType right)
145 {
146 return speculatedDoubleTypeForPrediction(mergeSpeculations(left, right));
147 }
148
149 void propagate(Node* node)
150 {
151 NodeType op = node->op();
152
153 bool changed = false;
154
155 switch (op) {
156 case GetLocal: {
157 VariableAccessData* variable = node->variableAccessData();
158 SpeculatedType prediction = variable->prediction();
159 if (!variable->couldRepresentInt52() && (prediction & SpecNonInt32AsInt52))
160 prediction = (prediction | SpecAnyIntAsDouble) & ~SpecNonInt32AsInt52;
161 if (prediction)
162 changed |= mergePrediction(prediction);
163 break;
164 }
165
166 case SetLocal: {
167 VariableAccessData* variableAccessData = node->variableAccessData();
168 changed |= variableAccessData->predict(node->child1()->prediction());
169 break;
170 }
171
172 case UInt32ToNumber: {
173 if (node->canSpeculateInt32(m_pass))
174 changed |= mergePrediction(SpecInt32Only);
175 else if (enableInt52())
176 changed |= mergePrediction(SpecInt52Any);
177 else
178 changed |= mergePrediction(SpecBytecodeNumber);
179 break;
180 }
181
182 case ValueAdd: {
183 SpeculatedType left = node->child1()->prediction();
184 SpeculatedType right = node->child2()->prediction();
185
186 if (left && right) {
187 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
188 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
189 if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
190 changed |= mergePrediction(SpecInt32Only);
191 else if (m_graph.addShouldSpeculateInt52(node))
192 changed |= mergePrediction(SpecInt52Any);
193 else
194 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
195 } else if (isStringOrStringObjectSpeculation(left) || isStringOrStringObjectSpeculation(right)) {
196 // left or right is definitely something other than a number.
197 changed |= mergePrediction(SpecString);
198 } else if (isBigIntSpeculation(left) && isBigIntSpeculation(right))
199 changed |= mergePrediction(SpecBigInt);
200 else {
201 changed |= mergePrediction(SpecInt32Only);
202 if (node->mayHaveDoubleResult())
203 changed |= mergePrediction(SpecBytecodeDouble);
204 if (node->mayHaveBigIntResult())
205 changed |= mergePrediction(SpecBigInt);
206 if (node->mayHaveNonNumericResult())
207 changed |= mergePrediction(SpecString);
208 }
209 }
210 break;
211 }
212
213 case ArithAdd: {
214 SpeculatedType left = node->child1()->prediction();
215 SpeculatedType right = node->child2()->prediction();
216
217 if (left && right) {
218 if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
219 changed |= mergePrediction(SpecInt32Only);
220 else if (m_graph.addShouldSpeculateInt52(node))
221 changed |= mergePrediction(SpecInt52Any);
222 else if (isFullNumberOrBooleanSpeculation(left) && isFullNumberOrBooleanSpeculation(right))
223 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
224 else if (node->mayHaveNonIntResult() || (left & SpecBytecodeDouble) || (right & SpecBytecodeDouble))
225 changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
226 else
227 changed |= mergePrediction(SpecInt32Only);
228 }
229 break;
230 }
231
232 case ArithSub: {
233 SpeculatedType left = node->child1()->prediction();
234 SpeculatedType right = node->child2()->prediction();
235
236 if (left && right) {
237 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
238 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
239 if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
240 changed |= mergePrediction(SpecInt32Only);
241 else if (m_graph.addShouldSpeculateInt52(node))
242 changed |= mergePrediction(SpecInt52Any);
243 else
244 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
245 } else if (node->mayHaveNonIntResult() || (left & SpecBytecodeDouble) || (right & SpecBytecodeDouble))
246 changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
247 else
248 changed |= mergePrediction(SpecInt32Only);
249 }
250 break;
251 }
252
253 case ValueSub: {
254 SpeculatedType left = node->child1()->prediction();
255 SpeculatedType right = node->child2()->prediction();
256
257 if (left && right) {
258 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
259 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
260 if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
261 changed |= mergePrediction(SpecInt32Only);
262 else if (m_graph.addShouldSpeculateInt52(node))
263 changed |= mergePrediction(SpecInt52Any);
264 else
265 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
266 } else if (isBigIntSpeculation(left) && isBigIntSpeculation(right))
267 changed |= mergePrediction(SpecBigInt);
268 else {
269 changed |= mergePrediction(SpecInt32Only);
270 if (node->mayHaveDoubleResult())
271 changed |= mergePrediction(SpecBytecodeDouble);
272 if (node->mayHaveBigIntResult())
273 changed |= mergePrediction(SpecBigInt);
274 }
275 }
276
277 break;
278 }
279
280 case ValueNegate:
281 case ArithNegate: {
282 SpeculatedType prediction = node->child1()->prediction();
283 if (prediction) {
284 if (isInt32OrBooleanSpeculation(prediction) && node->canSpeculateInt32(m_pass))
285 changed |= mergePrediction(SpecInt32Only);
286 else if (m_graph.unaryArithShouldSpeculateInt52(node, m_pass))
287 changed |= mergePrediction(SpecInt52Any);
288 else if (isBytecodeNumberSpeculation(prediction))
289 changed |= mergePrediction(speculatedDoubleTypeForPrediction(node->child1()->prediction()));
290 else {
291 changed |= mergePrediction(SpecInt32Only);
292 if (node->op() == ValueNegate && node->mayHaveBigIntResult())
293 changed |= mergePrediction(SpecBigInt);
294 if (node->mayHaveDoubleResult())
295 changed |= mergePrediction(SpecBytecodeDouble);
296 }
297 }
298 break;
299 }
300 case ArithMin:
301 case ArithMax: {
302 SpeculatedType left = node->child1()->prediction();
303 SpeculatedType right = node->child2()->prediction();
304
305 if (left && right) {
306 if (Node::shouldSpeculateInt32OrBooleanForArithmetic(node->child1().node(), node->child2().node())
307 && node->canSpeculateInt32(m_pass))
308 changed |= mergePrediction(SpecInt32Only);
309 else
310 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
311 }
312 break;
313 }
314
315 case ValueMul:
316 case ArithMul: {
317 SpeculatedType left = node->child1()->prediction();
318 SpeculatedType right = node->child2()->prediction();
319
320 if (left && right) {
321 // FIXME: We're currently relying on prediction propagation and backwards propagation
322 // whenever we can, and only falling back on result flags if that fails. And the result
323 // flags logic doesn't know how to use backwards propagation. We should get rid of the
324 // prediction propagation logic and rely solely on the result type.
325 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
326 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
327 if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
328 changed |= mergePrediction(SpecInt32Only);
329 else if (m_graph.binaryArithShouldSpeculateInt52(node, m_pass))
330 changed |= mergePrediction(SpecInt52Any);
331 else
332 changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
333 } else if (op == ValueMul && isBigIntSpeculation(left) && isBigIntSpeculation(right))
334 changed |= mergePrediction(SpecBigInt);
335 else {
336 changed |= mergePrediction(SpecInt32Only);
337 if (node->mayHaveDoubleResult()
338 || (left & SpecBytecodeDouble)
339 || (right & SpecBytecodeDouble))
340 changed |= mergePrediction(SpecBytecodeDouble);
341 if ((op == ValueMul && node->mayHaveBigIntResult())
342 || (left & SpecBigInt)
343 || (right & SpecBigInt))
344 changed |= mergePrediction(SpecBigInt);
345 }
346 }
347 break;
348 }
349
350 case ValueDiv:
351 case ValueMod:
352 case ArithDiv:
353 case ArithMod: {
354 SpeculatedType left = node->child1()->prediction();
355 SpeculatedType right = node->child2()->prediction();
356
357 if (left && right) {
358 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
359 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
360 if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
361 changed |= mergePrediction(SpecInt32Only);
362 else
363 changed |= mergePrediction(SpecBytecodeDouble);
364 } else if ((op == ValueDiv || op == ValueMod) && isBigIntSpeculation(left) && isBigIntSpeculation(right))
365 changed |= mergePrediction(SpecBigInt);
366 else {
367 changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
368 if ((op == ValueDiv || op == ValueMod) && (node->mayHaveBigIntResult()
369 || (left & SpecBigInt)
370 || (right & SpecBigInt)))
371 changed |= mergePrediction(SpecBigInt);
372 }
373 }
374 break;
375 }
376
377 case ArithAbs: {
378 SpeculatedType childPrediction = node->child1()->prediction();
379 if (isInt32OrBooleanSpeculation(childPrediction)
380 && node->canSpeculateInt32(m_pass))
381 changed |= mergePrediction(SpecInt32Only);
382 else
383 changed |= mergePrediction(SpecBytecodeDouble);
384 break;
385 }
386
387 case GetByVal:
388 case AtomicsAdd:
389 case AtomicsAnd:
390 case AtomicsCompareExchange:
391 case AtomicsExchange:
392 case AtomicsLoad:
393 case AtomicsOr:
394 case AtomicsStore:
395 case AtomicsSub:
396 case AtomicsXor: {
397 Edge child1 = m_graph.child(node, 0);
398 if (!child1->prediction())
399 break;
400
401 Edge child2 = m_graph.child(node, 1);
402 ArrayMode arrayMode = node->arrayMode().refine(
403 m_graph, node,
404 child1->prediction(),
405 child2->prediction(),
406 SpecNone);
407
408 switch (arrayMode.type()) {
409 case Array::Int32:
410 if (arrayMode.isOutOfBounds())
411 changed |= mergePrediction(node->getHeapPrediction() | SpecInt32Only);
412 else
413 changed |= mergePrediction(SpecInt32Only);
414 break;
415 case Array::Double:
416 if (arrayMode.isOutOfBounds())
417 changed |= mergePrediction(node->getHeapPrediction() | SpecDoubleReal);
418 else if (node->getHeapPrediction() & SpecNonIntAsDouble)
419 changed |= mergePrediction(SpecDoubleReal);
420 else
421 changed |= mergePrediction(SpecAnyIntAsDouble);
422 break;
423 case Array::Float32Array:
424 case Array::Float64Array:
425 changed |= mergePrediction(SpecFullDouble);
426 break;
427 case Array::Uint32Array:
428 if (isInt32SpeculationForArithmetic(node->getHeapPrediction()) && node->op() == GetByVal)
429 changed |= mergePrediction(SpecInt32Only);
430 else if (enableInt52())
431 changed |= mergePrediction(SpecInt52Any);
432 else
433 changed |= mergePrediction(SpecInt32Only | SpecAnyIntAsDouble);
434 break;
435 case Array::Int8Array:
436 case Array::Uint8Array:
437 case Array::Int16Array:
438 case Array::Uint16Array:
439 case Array::Int32Array:
440 changed |= mergePrediction(SpecInt32Only);
441 break;
442 default:
443 changed |= mergePrediction(node->getHeapPrediction());
444 break;
445 }
446 break;
447 }
448
449 case ToThis: {
450 // ToThis in methods for primitive types should speculate primitive types in strict mode.
451 bool isStrictMode = m_graph.isStrictModeFor(node->origin.semantic);
452 if (isStrictMode) {
453 if (node->child1()->shouldSpeculateBoolean()) {
454 changed |= mergePrediction(SpecBoolean);
455 break;
456 }
457
458 if (node->child1()->shouldSpeculateInt32()) {
459 changed |= mergePrediction(SpecInt32Only);
460 break;
461 }
462
463 if (node->child1()->shouldSpeculateInt52()) {
464 changed |= mergePrediction(SpecInt52Any);
465 break;
466 }
467
468 if (node->child1()->shouldSpeculateNumber()) {
469 changed |= mergePrediction(SpecBytecodeNumber);
470 break;
471 }
472
473 if (node->child1()->shouldSpeculateSymbol()) {
474 changed |= mergePrediction(SpecSymbol);
475 break;
476 }
477
478 if (node->child1()->shouldSpeculateBigInt()) {
479 changed |= mergePrediction(SpecBigInt);
480 break;
481 }
482
483 if (node->child1()->shouldSpeculateStringIdent()) {
484 changed |= mergePrediction(SpecStringIdent);
485 break;
486 }
487
488 if (node->child1()->shouldSpeculateString()) {
489 changed |= mergePrediction(SpecString);
490 break;
491 }
492 } else {
493 if (node->child1()->shouldSpeculateString()) {
494 changed |= mergePrediction(SpecStringObject);
495 break;
496 }
497 }
498
499 SpeculatedType prediction = node->child1()->prediction();
500 if (isStrictMode)
501 changed |= mergePrediction(node->getHeapPrediction());
502 else if (prediction) {
503 if (prediction & ~SpecObject) {
504 // Wrapper objects are created only in sloppy mode.
505 prediction &= SpecObject;
506 prediction = mergeSpeculations(prediction, SpecObjectOther);
507 }
508 changed |= mergePrediction(prediction);
509 }
510 break;
511 }
512
513 case ToPrimitive: {
514 SpeculatedType child = node->child1()->prediction();
515 if (child)
516 changed |= mergePrediction(resultOfToPrimitive(child));
517 break;
518 }
519
520 case NormalizeMapKey: {
521 SpeculatedType prediction = node->child1()->prediction();
522 if (prediction)
523 changed |= mergePrediction(prediction);
524 break;
525 }
526
527 default:
528 break;
529 }
530
531 m_changed |= changed;
532 }
533
534 void propagateForward()
535 {
536 for (Node* node : m_dependentNodes) {
537 m_currentNode = node;
538 propagate(m_currentNode);
539 }
540 }
541
542 void propagateBackward()
543 {
544 for (unsigned i = m_dependentNodes.size(); i--;) {
545 m_currentNode = m_dependentNodes[i];
546 propagate(m_currentNode);
547 }
548 }
549
550 void doDoubleVoting(Node* node, float weight)
551 {
552 // Loop pre-headers created by OSR entrypoint creation may have NaN weight to indicate
553 // that we actually don't know they weight. Assume that they execute once. This turns
554 // out to be an OK assumption since the pre-header doesn't have any meaningful code.
555 if (weight != weight)
556 weight = 1;
557
558 switch (node->op()) {
559 case ValueAdd:
560 case ValueSub:
561 case ArithAdd:
562 case ArithSub: {
563 SpeculatedType left = node->child1()->prediction();
564 SpeculatedType right = node->child2()->prediction();
565
566 DoubleBallot ballot;
567
568 if (isFullNumberSpeculation(left)
569 && isFullNumberSpeculation(right)
570 && !m_graph.addShouldSpeculateInt32(node, m_pass)
571 && !m_graph.addShouldSpeculateInt52(node))
572 ballot = VoteDouble;
573 else
574 ballot = VoteValue;
575
576 m_graph.voteNode(node->child1(), ballot, weight);
577 m_graph.voteNode(node->child2(), ballot, weight);
578 break;
579 }
580
581 case ValueMul:
582 case ArithMul: {
583 SpeculatedType left = node->child1()->prediction();
584 SpeculatedType right = node->child2()->prediction();
585
586 DoubleBallot ballot;
587
588 if (isFullNumberSpeculation(left)
589 && isFullNumberSpeculation(right)
590 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass)
591 && !m_graph.binaryArithShouldSpeculateInt52(node, m_pass))
592 ballot = VoteDouble;
593 else
594 ballot = VoteValue;
595
596 m_graph.voteNode(node->child1(), ballot, weight);
597 m_graph.voteNode(node->child2(), ballot, weight);
598 break;
599 }
600
601 case ArithMin:
602 case ArithMax:
603 case ArithMod:
604 case ValueDiv:
605 case ValueMod:
606 case ArithDiv: {
607 SpeculatedType left = node->child1()->prediction();
608 SpeculatedType right = node->child2()->prediction();
609
610 DoubleBallot ballot;
611
612 if (isFullNumberSpeculation(left)
613 && isFullNumberSpeculation(right)
614 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
615 ballot = VoteDouble;
616 else
617 ballot = VoteValue;
618
619 m_graph.voteNode(node->child1(), ballot, weight);
620 m_graph.voteNode(node->child2(), ballot, weight);
621 break;
622 }
623
624 case ArithAbs:
625 DoubleBallot ballot;
626 if (node->child1()->shouldSpeculateNumber()
627 && !m_graph.unaryArithShouldSpeculateInt32(node, m_pass))
628 ballot = VoteDouble;
629 else
630 ballot = VoteValue;
631
632 m_graph.voteNode(node->child1(), ballot, weight);
633 break;
634
635 case ArithSqrt:
636 case ArithUnary:
637 if (node->child1()->shouldSpeculateNumber())
638 m_graph.voteNode(node->child1(), VoteDouble, weight);
639 else
640 m_graph.voteNode(node->child1(), VoteValue, weight);
641 break;
642
643 case SetLocal: {
644 SpeculatedType prediction = node->child1()->prediction();
645 if (isDoubleSpeculation(prediction))
646 node->variableAccessData()->vote(VoteDouble, weight);
647 else if (!isFullNumberSpeculation(prediction) || isInt32OrInt52Speculation(prediction))
648 node->variableAccessData()->vote(VoteValue, weight);
649 break;
650 }
651
652 case PutByValDirect:
653 case PutByVal:
654 case PutByValAlias: {
655 Edge child1 = m_graph.varArgChild(node, 0);
656 Edge child2 = m_graph.varArgChild(node, 1);
657 Edge child3 = m_graph.varArgChild(node, 2);
658 m_graph.voteNode(child1, VoteValue, weight);
659 m_graph.voteNode(child2, VoteValue, weight);
660 switch (node->arrayMode().type()) {
661 case Array::Double:
662 m_graph.voteNode(child3, VoteDouble, weight);
663 break;
664 default:
665 m_graph.voteNode(child3, VoteValue, weight);
666 break;
667 }
668 break;
669 }
670
671 case DataViewSet: {
672 DataViewData data = node->dataViewData();
673 if (data.isFloatingPoint)
674 m_graph.voteNode(m_graph.varArgChild(node, 2), VoteValue, weight);
675 break;
676 }
677
678 case MovHint:
679 // Ignore these since they have no effect on in-DFG execution.
680 break;
681
682 default:
683 m_graph.voteChildren(node, VoteValue, weight);
684 break;
685 }
686 }
687
688 void doRoundOfDoubleVoting()
689 {
690 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
691 m_graph.m_variableAccessData[i].find()->clearVotes();
692 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
693 BasicBlock* block = m_graph.block(blockIndex);
694 if (!block)
695 continue;
696 ASSERT(block->isReachable);
697 for (unsigned i = 0; i < block->size(); ++i) {
698 m_currentNode = block->at(i);
699 doDoubleVoting(m_currentNode, block->executionCount);
700 }
701 }
702 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
703 VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
704 if (!variableAccessData->isRoot())
705 continue;
706 m_changed |= variableAccessData->tallyVotesForShouldUseDoubleFormat();
707 }
708 propagateThroughArgumentPositions();
709 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
710 VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
711 if (!variableAccessData->isRoot())
712 continue;
713 m_changed |= variableAccessData->makePredictionForDoubleFormat();
714 }
715 }
716
717 void propagateThroughArgumentPositions()
718 {
719 for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
720 m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
721 }
722
723 // Sets any predictions that do not depends on other nodes.
724 void processInvariants()
725 {
726 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
727 for (Node* node : *block) {
728 m_currentNode = node;
729 processInvariantsForNode();
730 }
731 }
732 }
733
734 void processInvariantsForNode()
735 {
736 switch (m_currentNode->op()) {
737 case JSConstant: {
738 SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
739 if (type == SpecAnyIntAsDouble && enableInt52())
740 type = int52AwareSpeculationFromValue(m_currentNode->asJSValue());
741 setPrediction(type);
742 break;
743 }
744 case DoubleConstant: {
745 SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
746 setPrediction(type);
747 break;
748 }
749
750 case ArithBitNot:
751 case ArithBitAnd:
752 case ArithBitOr:
753 case ArithBitXor:
754 case BitRShift:
755 case BitLShift:
756 case BitURShift:
757 case ArithIMul:
758 case ArithClz32: {
759 setPrediction(SpecInt32Only);
760 break;
761 }
762
763 case ArrayPop:
764 case ArrayPush:
765 case RegExpExec:
766 case RegExpExecNonGlobalOrSticky:
767 case RegExpTest:
768 case RegExpMatchFast:
769 case RegExpMatchFastGlobal:
770 case StringReplace:
771 case StringReplaceRegExp:
772 case GetById:
773 case GetByIdFlush:
774 case GetByIdWithThis:
775 case GetByIdDirect:
776 case GetByIdDirectFlush:
777 case TryGetById:
778 case GetByValWithThis:
779 case GetByOffset:
780 case MultiGetByOffset:
781 case GetDirectPname:
782 case Call:
783 case DirectCall:
784 case TailCallInlinedCaller:
785 case DirectTailCallInlinedCaller:
786 case Construct:
787 case DirectConstruct:
788 case CallVarargs:
789 case CallEval:
790 case TailCallVarargsInlinedCaller:
791 case ConstructVarargs:
792 case CallForwardVarargs:
793 case ConstructForwardVarargs:
794 case TailCallForwardVarargsInlinedCaller:
795 case GetGlobalVar:
796 case GetGlobalLexicalVariable:
797 case GetClosureVar:
798 case GetFromArguments:
799 case LoadKeyFromMapBucket:
800 case LoadValueFromMapBucket:
801 case ToNumber:
802 case ToObject:
803 case ValueBitAnd:
804 case ValueBitXor:
805 case ValueBitOr:
806 case ValueBitNot:
807 case CallObjectConstructor:
808 case GetArgument:
809 case CallDOMGetter:
810 case GetDynamicVar:
811 case GetPrototypeOf:
812 case ExtractValueFromWeakMapGet:
813 case DataViewGetInt:
814 case DataViewGetFloat: {
815 setPrediction(m_currentNode->getHeapPrediction());
816 break;
817 }
818
819 case WeakMapGet:
820 case ResolveScopeForHoistingFuncDeclInEval: {
821 setPrediction(SpecBytecodeTop);
822 break;
823 }
824
825 case GetGetterSetterByOffset:
826 case GetExecutable: {
827 setPrediction(SpecCellOther);
828 break;
829 }
830
831 case GetGetter:
832 case GetSetter:
833 case GetCallee:
834 case NewFunction:
835 case NewGeneratorFunction:
836 case NewAsyncGeneratorFunction:
837 case NewAsyncFunction: {
838 setPrediction(SpecFunction);
839 break;
840 }
841
842 case GetArgumentCountIncludingThis: {
843 setPrediction(SpecInt32Only);
844 break;
845 }
846
847 case SetCallee:
848 case SetArgumentCountIncludingThis:
849 break;
850
851 case MapHash:
852 setPrediction(SpecInt32Only);
853 break;
854
855 case GetMapBucket:
856 case GetMapBucketHead:
857 case GetMapBucketNext:
858 case SetAdd:
859 case MapSet:
860 setPrediction(SpecCellOther);
861 break;
862
863 case GetRestLength:
864 case ArrayIndexOf: {
865 setPrediction(SpecInt32Only);
866 break;
867 }
868
869 case GetTypedArrayByteOffset:
870 case GetArrayLength:
871 case GetVectorLength: {
872 setPrediction(SpecInt32Only);
873 break;
874 }
875
876 case StringCharCodeAt: {
877 setPrediction(SpecInt32Only);
878 break;
879 }
880
881 case StringValueOf:
882 case StringSlice:
883 case ToLowerCase:
884 setPrediction(SpecString);
885 break;
886
887 case ArithPow:
888 case ArithSqrt:
889 case ArithFRound:
890 case ArithUnary: {
891 setPrediction(SpecBytecodeDouble);
892 break;
893 }
894
895 case ArithRound:
896 case ArithFloor:
897 case ArithCeil:
898 case ArithTrunc: {
899 if (isInt32OrBooleanSpeculation(m_currentNode->getHeapPrediction())
900 && m_graph.roundShouldSpeculateInt32(m_currentNode, m_pass))
901 setPrediction(SpecInt32Only);
902 else
903 setPrediction(SpecBytecodeDouble);
904 break;
905 }
906
907 case ArithRandom: {
908 setPrediction(SpecDoubleReal);
909 break;
910 }
911 case DeleteByVal:
912 case DeleteById:
913 case LogicalNot:
914 case CompareLess:
915 case CompareLessEq:
916 case CompareGreater:
917 case CompareGreaterEq:
918 case CompareBelow:
919 case CompareBelowEq:
920 case CompareEq:
921 case CompareStrictEq:
922 case CompareEqPtr:
923 case SameValue:
924 case OverridesHasInstance:
925 case InstanceOf:
926 case InstanceOfCustom:
927 case IsEmpty:
928 case IsUndefined:
929 case IsUndefinedOrNull:
930 case IsBoolean:
931 case IsNumber:
932 case NumberIsInteger:
933 case IsObject:
934 case IsObjectOrNull:
935 case IsFunction:
936 case IsCellWithType:
937 case IsTypedArrayView:
938 case MatchStructure: {
939 setPrediction(SpecBoolean);
940 break;
941 }
942
943 case TypeOf: {
944 setPrediction(SpecStringIdent);
945 break;
946 }
947 case GetButterfly:
948 case GetIndexedPropertyStorage:
949 case AllocatePropertyStorage:
950 case ReallocatePropertyStorage: {
951 setPrediction(SpecOther);
952 break;
953 }
954
955 case CheckSubClass:
956 break;
957
958 case SkipScope:
959 case GetGlobalObject: {
960 setPrediction(SpecObjectOther);
961 break;
962 }
963
964 case GetGlobalThis:
965 setPrediction(SpecObject);
966 break;
967
968 case ResolveScope: {
969 setPrediction(SpecObjectOther);
970 break;
971 }
972
973 case ObjectCreate:
974 case CreateThis:
975 case NewObject: {
976 setPrediction(SpecFinalObject);
977 break;
978 }
979
980 case ArraySlice:
981 case NewArrayWithSpread:
982 case NewArray:
983 case NewArrayWithSize:
984 case CreateRest:
985 case NewArrayBuffer:
986 case ObjectKeys: {
987 setPrediction(SpecArray);
988 break;
989 }
990
991 case Spread:
992 setPrediction(SpecCellOther);
993 break;
994
995 case NewTypedArray: {
996 setPrediction(speculationFromTypedArrayType(m_currentNode->typedArrayType()));
997 break;
998 }
999
1000 case NewRegexp: {
1001 setPrediction(SpecRegExpObject);
1002 break;
1003 }
1004
1005 case PushWithScope:
1006 case CreateActivation: {
1007 setPrediction(SpecObjectOther);
1008 break;
1009 }
1010
1011 case StringFromCharCode: {
1012 setPrediction(SpecString);
1013 m_currentNode->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
1014 break;
1015 }
1016 case StringCharAt:
1017 case CallStringConstructor:
1018 case ToString:
1019 case NumberToStringWithRadix:
1020 case NumberToStringWithValidRadixConstant:
1021 case MakeRope:
1022 case StrCat: {
1023 setPrediction(SpecString);
1024 break;
1025 }
1026 case NewStringObject: {
1027 setPrediction(SpecStringObject);
1028 break;
1029 }
1030 case NewSymbol: {
1031 setPrediction(SpecSymbol);
1032 break;
1033 }
1034
1035 case CreateDirectArguments: {
1036 setPrediction(SpecDirectArguments);
1037 break;
1038 }
1039
1040 case CreateScopedArguments: {
1041 setPrediction(SpecScopedArguments);
1042 break;
1043 }
1044
1045 case CreateClonedArguments: {
1046 setPrediction(SpecObjectOther);
1047 break;
1048 }
1049
1050 case FiatInt52: {
1051 RELEASE_ASSERT(enableInt52());
1052 setPrediction(SpecInt52Any);
1053 break;
1054 }
1055
1056 case GetScope:
1057 setPrediction(SpecObjectOther);
1058 break;
1059
1060 case InByVal:
1061 case InById:
1062 setPrediction(SpecBoolean);
1063 break;
1064
1065 case HasOwnProperty:
1066 setPrediction(SpecBoolean);
1067 break;
1068
1069 case GetEnumerableLength: {
1070 setPrediction(SpecInt32Only);
1071 break;
1072 }
1073 case HasGenericProperty:
1074 case HasStructureProperty:
1075 case HasIndexedProperty: {
1076 setPrediction(SpecBoolean);
1077 break;
1078 }
1079 case GetPropertyEnumerator: {
1080 setPrediction(SpecCell);
1081 break;
1082 }
1083 case GetEnumeratorStructurePname: {
1084 setPrediction(SpecCell | SpecOther);
1085 break;
1086 }
1087 case GetEnumeratorGenericPname: {
1088 setPrediction(SpecCell | SpecOther);
1089 break;
1090 }
1091 case ToIndexString: {
1092 setPrediction(SpecString);
1093 break;
1094 }
1095 case ParseInt: {
1096 // We expect this node to almost always produce an int32. However,
1097 // it's possible it produces NaN or integers out of int32 range. We
1098 // rely on the heap prediction since the parseInt() call profiled
1099 // its result.
1100 setPrediction(m_currentNode->getHeapPrediction());
1101 break;
1102 }
1103
1104 case IdentityWithProfile: {
1105 setPrediction(m_currentNode->getForcedPrediction());
1106 break;
1107 }
1108
1109 case ExtractCatchLocal: {
1110 setPrediction(m_currentNode->catchLocalPrediction());
1111 break;
1112 }
1113
1114 case GetLocal:
1115 case SetLocal:
1116 case UInt32ToNumber:
1117 case ValueNegate:
1118 case ValueAdd:
1119 case ValueSub:
1120 case ValueMul:
1121 case ValueDiv:
1122 case ValueMod:
1123 case ArithAdd:
1124 case ArithSub:
1125 case ArithNegate:
1126 case ArithMin:
1127 case ArithMax:
1128 case ArithMul:
1129 case ArithDiv:
1130 case ArithMod:
1131 case ArithAbs:
1132 case GetByVal:
1133 case ToThis:
1134 case ToPrimitive:
1135 case NormalizeMapKey:
1136 case AtomicsAdd:
1137 case AtomicsAnd:
1138 case AtomicsCompareExchange:
1139 case AtomicsExchange:
1140 case AtomicsLoad:
1141 case AtomicsOr:
1142 case AtomicsStore:
1143 case AtomicsSub:
1144 case AtomicsXor: {
1145 m_dependentNodes.append(m_currentNode);
1146 break;
1147 }
1148
1149 case AtomicsIsLockFree: {
1150 setPrediction(SpecBoolean);
1151 break;
1152 }
1153
1154 case CPUIntrinsic: {
1155 if (m_currentNode->intrinsic() == CPURdtscIntrinsic)
1156 setPrediction(SpecInt32Only);
1157 else
1158 setPrediction(SpecOther);
1159 break;
1160 }
1161
1162 case PutByValAlias:
1163 case DoubleAsInt32:
1164 case CheckArray:
1165 case CheckTypeInfoFlags:
1166 case Arrayify:
1167 case ArrayifyToStructure:
1168 case CheckTierUpInLoop:
1169 case CheckTierUpAtReturn:
1170 case CheckTierUpAndOSREnter:
1171 case CheckInBounds:
1172 case ValueToInt32:
1173 case DoubleRep:
1174 case ValueRep:
1175 case Int52Rep:
1176 case Int52Constant:
1177 case Identity:
1178 case BooleanToNumber:
1179 case PhantomNewObject:
1180 case PhantomNewFunction:
1181 case PhantomNewGeneratorFunction:
1182 case PhantomNewAsyncGeneratorFunction:
1183 case PhantomNewAsyncFunction:
1184 case PhantomCreateActivation:
1185 case PhantomDirectArguments:
1186 case PhantomCreateRest:
1187 case PhantomSpread:
1188 case PhantomNewArrayWithSpread:
1189 case PhantomNewArrayBuffer:
1190 case PhantomClonedArguments:
1191 case PhantomNewRegexp:
1192 case GetMyArgumentByVal:
1193 case GetMyArgumentByValOutOfBounds:
1194 case PutHint:
1195 case CheckStructureImmediate:
1196 case CheckStructureOrEmpty:
1197 case MaterializeNewObject:
1198 case MaterializeCreateActivation:
1199 case PutStack:
1200 case KillStack:
1201 case StoreBarrier:
1202 case FencedStoreBarrier:
1203 case GetStack:
1204 case GetRegExpObjectLastIndex:
1205 case SetRegExpObjectLastIndex:
1206 case RecordRegExpCachedResult:
1207 case LazyJSConstant:
1208 case CallDOM: {
1209 // This node should never be visible at this stage of compilation.
1210 DFG_CRASH(m_graph, m_currentNode, "Unexpected node during prediction propagation");
1211 break;
1212 }
1213
1214 case Phi:
1215 // Phis should not be visible here since we're iterating the all-but-Phi's
1216 // part of basic blocks.
1217 RELEASE_ASSERT_NOT_REACHED();
1218 break;
1219
1220 case EntrySwitch:
1221 case Upsilon:
1222 // These don't get inserted until we go into SSA.
1223 RELEASE_ASSERT_NOT_REACHED();
1224 break;
1225
1226#ifndef NDEBUG
1227 // These get ignored because they don't return anything.
1228 case PutByValDirect:
1229 case PutByValWithThis:
1230 case PutByIdWithThis:
1231 case PutByVal:
1232 case PutClosureVar:
1233 case PutToArguments:
1234 case Return:
1235 case Throw:
1236 case ThrowStaticError:
1237 case TailCall:
1238 case DirectTailCall:
1239 case TailCallVarargs:
1240 case TailCallForwardVarargs:
1241 case PutById:
1242 case PutByIdFlush:
1243 case PutByIdDirect:
1244 case PutByOffset:
1245 case MultiPutByOffset:
1246 case PutGetterById:
1247 case PutSetterById:
1248 case PutGetterSetterById:
1249 case PutGetterByVal:
1250 case PutSetterByVal:
1251 case DefineDataProperty:
1252 case DefineAccessorProperty:
1253 case DFG::Jump:
1254 case Branch:
1255 case Switch:
1256 case ProfileType:
1257 case ProfileControlFlow:
1258 case ForceOSRExit:
1259 case SetArgumentDefinitely:
1260 case SetArgumentMaybe:
1261 case SetFunctionName:
1262 case CheckStructure:
1263 case CheckCell:
1264 case CheckNotEmpty:
1265 case AssertNotEmpty:
1266 case CheckStringIdent:
1267 case CheckBadCell:
1268 case PutStructure:
1269 case Phantom:
1270 case Check:
1271 case CheckVarargs:
1272 case PutGlobalVariable:
1273 case CheckTraps:
1274 case LogShadowChickenPrologue:
1275 case LogShadowChickenTail:
1276 case Unreachable:
1277 case LoopHint:
1278 case NotifyWrite:
1279 case ConstantStoragePointer:
1280 case MovHint:
1281 case ZombieHint:
1282 case ExitOK:
1283 case LoadVarargs:
1284 case ForwardVarargs:
1285 case PutDynamicVar:
1286 case NukeStructureAndSetButterfly:
1287 case InitializeEntrypointArguments:
1288 case WeakSetAdd:
1289 case WeakMapSet:
1290 case FilterCallLinkStatus:
1291 case FilterGetByIdStatus:
1292 case FilterPutByIdStatus:
1293 case FilterInByIdStatus:
1294 case ClearCatchLocals:
1295 case DataViewSet:
1296 case InvalidationPoint:
1297 break;
1298
1299 // This gets ignored because it only pretends to produce a value.
1300 case BottomValue:
1301 break;
1302
1303 // This gets ignored because it already has a prediction.
1304 case ExtractOSREntryLocal:
1305 break;
1306
1307 // These gets ignored because it doesn't do anything.
1308 case CountExecution:
1309 case SuperSamplerBegin:
1310 case SuperSamplerEnd:
1311 case PhantomLocal:
1312 case Flush:
1313 break;
1314
1315 case LastNodeType:
1316 RELEASE_ASSERT_NOT_REACHED();
1317 break;
1318#else
1319 default:
1320 break;
1321#endif
1322 }
1323 }
1324
1325 SpeculatedType resultOfToPrimitive(SpeculatedType type)
1326 {
1327 if (type & SpecObject) {
1328 // We try to be optimistic here about StringObjects since it's unlikely that
1329 // someone overrides the valueOf or toString methods.
1330 if (type & SpecStringObject && m_graph.canOptimizeStringObjectAccess(m_currentNode->origin.semantic))
1331 return mergeSpeculations(type & ~SpecObject, SpecString);
1332
1333 return mergeSpeculations(type & ~SpecObject, SpecPrimitive);
1334 }
1335
1336 return type;
1337 }
1338
1339 Vector<Node*> m_dependentNodes;
1340 Node* m_currentNode;
1341 bool m_changed { false };
1342 PredictionPass m_pass { PrimaryPass }; // We use different logic for considering predictions depending on how far along we are in propagation.
1343};
1344
1345} // Anonymous namespace.
1346
1347bool performPredictionPropagation(Graph& graph)
1348{
1349 return runPhase<PredictionPropagationPhase>(graph);
1350}
1351
1352} } // namespace JSC::DFG
1353
1354#endif // ENABLE(DFG_JIT)
1355
1356