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 ArithDiv:
352 case ArithMod: {
353 SpeculatedType left = node->child1()->prediction();
354 SpeculatedType right = node->child2()->prediction();
355
356 if (left && right) {
357 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
358 && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
359 if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
360 changed |= mergePrediction(SpecInt32Only);
361 else
362 changed |= mergePrediction(SpecBytecodeDouble);
363 } else if (op == ValueDiv && isBigIntSpeculation(left) && isBigIntSpeculation(right))
364 changed |= mergePrediction(SpecBigInt);
365 else {
366 changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
367 if (op == ValueDiv && (node->mayHaveBigIntResult()
368 || (left & SpecBigInt)
369 || (right & SpecBigInt)))
370 changed |= mergePrediction(SpecBigInt);
371 }
372 }
373 break;
374 }
375
376 case ArithAbs: {
377 SpeculatedType childPrediction = node->child1()->prediction();
378 if (isInt32OrBooleanSpeculation(childPrediction)
379 && node->canSpeculateInt32(m_pass))
380 changed |= mergePrediction(SpecInt32Only);
381 else
382 changed |= mergePrediction(SpecBytecodeDouble);
383 break;
384 }
385
386 case GetByVal:
387 case AtomicsAdd:
388 case AtomicsAnd:
389 case AtomicsCompareExchange:
390 case AtomicsExchange:
391 case AtomicsLoad:
392 case AtomicsOr:
393 case AtomicsStore:
394 case AtomicsSub:
395 case AtomicsXor: {
396 Edge child1 = m_graph.child(node, 0);
397 if (!child1->prediction())
398 break;
399
400 Edge child2 = m_graph.child(node, 1);
401 ArrayMode arrayMode = node->arrayMode().refine(
402 m_graph, node,
403 child1->prediction(),
404 child2->prediction(),
405 SpecNone);
406
407 switch (arrayMode.type()) {
408 case Array::Int32:
409 if (arrayMode.isOutOfBounds())
410 changed |= mergePrediction(node->getHeapPrediction() | SpecInt32Only);
411 else
412 changed |= mergePrediction(SpecInt32Only);
413 break;
414 case Array::Double:
415 if (arrayMode.isOutOfBounds())
416 changed |= mergePrediction(node->getHeapPrediction() | SpecDoubleReal);
417 else if (node->getHeapPrediction() & SpecNonIntAsDouble)
418 changed |= mergePrediction(SpecDoubleReal);
419 else
420 changed |= mergePrediction(SpecAnyIntAsDouble);
421 break;
422 case Array::Float32Array:
423 case Array::Float64Array:
424 changed |= mergePrediction(SpecFullDouble);
425 break;
426 case Array::Uint32Array:
427 if (isInt32SpeculationForArithmetic(node->getHeapPrediction()) && node->op() == GetByVal)
428 changed |= mergePrediction(SpecInt32Only);
429 else if (enableInt52())
430 changed |= mergePrediction(SpecInt52Any);
431 else
432 changed |= mergePrediction(SpecInt32Only | SpecAnyIntAsDouble);
433 break;
434 case Array::Int8Array:
435 case Array::Uint8Array:
436 case Array::Int16Array:
437 case Array::Uint16Array:
438 case Array::Int32Array:
439 changed |= mergePrediction(SpecInt32Only);
440 break;
441 default:
442 changed |= mergePrediction(node->getHeapPrediction());
443 break;
444 }
445 break;
446 }
447
448 case ToThis: {
449 // ToThis in methods for primitive types should speculate primitive types in strict mode.
450 bool isStrictMode = m_graph.isStrictModeFor(node->origin.semantic);
451 if (isStrictMode) {
452 if (node->child1()->shouldSpeculateBoolean()) {
453 changed |= mergePrediction(SpecBoolean);
454 break;
455 }
456
457 if (node->child1()->shouldSpeculateInt32()) {
458 changed |= mergePrediction(SpecInt32Only);
459 break;
460 }
461
462 if (node->child1()->shouldSpeculateInt52()) {
463 changed |= mergePrediction(SpecInt52Any);
464 break;
465 }
466
467 if (node->child1()->shouldSpeculateNumber()) {
468 changed |= mergePrediction(SpecBytecodeNumber);
469 break;
470 }
471
472 if (node->child1()->shouldSpeculateSymbol()) {
473 changed |= mergePrediction(SpecSymbol);
474 break;
475 }
476
477 if (node->child1()->shouldSpeculateBigInt()) {
478 changed |= mergePrediction(SpecBigInt);
479 break;
480 }
481
482 if (node->child1()->shouldSpeculateStringIdent()) {
483 changed |= mergePrediction(SpecStringIdent);
484 break;
485 }
486
487 if (node->child1()->shouldSpeculateString()) {
488 changed |= mergePrediction(SpecString);
489 break;
490 }
491 } else {
492 if (node->child1()->shouldSpeculateString()) {
493 changed |= mergePrediction(SpecStringObject);
494 break;
495 }
496 }
497
498 SpeculatedType prediction = node->child1()->prediction();
499 if (isStrictMode)
500 changed |= mergePrediction(node->getHeapPrediction());
501 else if (prediction) {
502 if (prediction & ~SpecObject) {
503 // Wrapper objects are created only in sloppy mode.
504 prediction &= SpecObject;
505 prediction = mergeSpeculations(prediction, SpecObjectOther);
506 }
507 changed |= mergePrediction(prediction);
508 }
509 break;
510 }
511
512 case ToPrimitive: {
513 SpeculatedType child = node->child1()->prediction();
514 if (child)
515 changed |= mergePrediction(resultOfToPrimitive(child));
516 break;
517 }
518
519 case NormalizeMapKey: {
520 SpeculatedType prediction = node->child1()->prediction();
521 if (prediction)
522 changed |= mergePrediction(prediction);
523 break;
524 }
525
526 default:
527 break;
528 }
529
530 m_changed |= changed;
531 }
532
533 void propagateForward()
534 {
535 for (Node* node : m_dependentNodes) {
536 m_currentNode = node;
537 propagate(m_currentNode);
538 }
539 }
540
541 void propagateBackward()
542 {
543 for (unsigned i = m_dependentNodes.size(); i--;) {
544 m_currentNode = m_dependentNodes[i];
545 propagate(m_currentNode);
546 }
547 }
548
549 void doDoubleVoting(Node* node, float weight)
550 {
551 // Loop pre-headers created by OSR entrypoint creation may have NaN weight to indicate
552 // that we actually don't know they weight. Assume that they execute once. This turns
553 // out to be an OK assumption since the pre-header doesn't have any meaningful code.
554 if (weight != weight)
555 weight = 1;
556
557 switch (node->op()) {
558 case ValueAdd:
559 case ValueSub:
560 case ArithAdd:
561 case ArithSub: {
562 SpeculatedType left = node->child1()->prediction();
563 SpeculatedType right = node->child2()->prediction();
564
565 DoubleBallot ballot;
566
567 if (isFullNumberSpeculation(left)
568 && isFullNumberSpeculation(right)
569 && !m_graph.addShouldSpeculateInt32(node, m_pass)
570 && !m_graph.addShouldSpeculateInt52(node))
571 ballot = VoteDouble;
572 else
573 ballot = VoteValue;
574
575 m_graph.voteNode(node->child1(), ballot, weight);
576 m_graph.voteNode(node->child2(), ballot, weight);
577 break;
578 }
579
580 case ValueMul:
581 case ArithMul: {
582 SpeculatedType left = node->child1()->prediction();
583 SpeculatedType right = node->child2()->prediction();
584
585 DoubleBallot ballot;
586
587 if (isFullNumberSpeculation(left)
588 && isFullNumberSpeculation(right)
589 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass)
590 && !m_graph.binaryArithShouldSpeculateInt52(node, m_pass))
591 ballot = VoteDouble;
592 else
593 ballot = VoteValue;
594
595 m_graph.voteNode(node->child1(), ballot, weight);
596 m_graph.voteNode(node->child2(), ballot, weight);
597 break;
598 }
599
600 case ArithMin:
601 case ArithMax:
602 case ArithMod:
603 case ValueDiv:
604 case ArithDiv: {
605 SpeculatedType left = node->child1()->prediction();
606 SpeculatedType right = node->child2()->prediction();
607
608 DoubleBallot ballot;
609
610 if (isFullNumberSpeculation(left)
611 && isFullNumberSpeculation(right)
612 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
613 ballot = VoteDouble;
614 else
615 ballot = VoteValue;
616
617 m_graph.voteNode(node->child1(), ballot, weight);
618 m_graph.voteNode(node->child2(), ballot, weight);
619 break;
620 }
621
622 case ArithAbs:
623 DoubleBallot ballot;
624 if (node->child1()->shouldSpeculateNumber()
625 && !m_graph.unaryArithShouldSpeculateInt32(node, m_pass))
626 ballot = VoteDouble;
627 else
628 ballot = VoteValue;
629
630 m_graph.voteNode(node->child1(), ballot, weight);
631 break;
632
633 case ArithSqrt:
634 case ArithUnary:
635 if (node->child1()->shouldSpeculateNumber())
636 m_graph.voteNode(node->child1(), VoteDouble, weight);
637 else
638 m_graph.voteNode(node->child1(), VoteValue, weight);
639 break;
640
641 case SetLocal: {
642 SpeculatedType prediction = node->child1()->prediction();
643 if (isDoubleSpeculation(prediction))
644 node->variableAccessData()->vote(VoteDouble, weight);
645 else if (!isFullNumberSpeculation(prediction)
646 || isInt32Speculation(prediction) || isAnyInt52Speculation(prediction))
647 node->variableAccessData()->vote(VoteValue, weight);
648 break;
649 }
650
651 case PutByValDirect:
652 case PutByVal:
653 case PutByValAlias: {
654 Edge child1 = m_graph.varArgChild(node, 0);
655 Edge child2 = m_graph.varArgChild(node, 1);
656 Edge child3 = m_graph.varArgChild(node, 2);
657 m_graph.voteNode(child1, VoteValue, weight);
658 m_graph.voteNode(child2, VoteValue, weight);
659 switch (node->arrayMode().type()) {
660 case Array::Double:
661 m_graph.voteNode(child3, VoteDouble, weight);
662 break;
663 default:
664 m_graph.voteNode(child3, VoteValue, weight);
665 break;
666 }
667 break;
668 }
669
670 case DataViewSet: {
671 DataViewData data = node->dataViewData();
672 if (data.isFloatingPoint)
673 m_graph.voteNode(m_graph.varArgChild(node, 2), VoteValue, weight);
674 break;
675 }
676
677 case MovHint:
678 // Ignore these since they have no effect on in-DFG execution.
679 break;
680
681 default:
682 m_graph.voteChildren(node, VoteValue, weight);
683 break;
684 }
685 }
686
687 void doRoundOfDoubleVoting()
688 {
689 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
690 m_graph.m_variableAccessData[i].find()->clearVotes();
691 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
692 BasicBlock* block = m_graph.block(blockIndex);
693 if (!block)
694 continue;
695 ASSERT(block->isReachable);
696 for (unsigned i = 0; i < block->size(); ++i) {
697 m_currentNode = block->at(i);
698 doDoubleVoting(m_currentNode, block->executionCount);
699 }
700 }
701 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
702 VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
703 if (!variableAccessData->isRoot())
704 continue;
705 m_changed |= variableAccessData->tallyVotesForShouldUseDoubleFormat();
706 }
707 propagateThroughArgumentPositions();
708 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
709 VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
710 if (!variableAccessData->isRoot())
711 continue;
712 m_changed |= variableAccessData->makePredictionForDoubleFormat();
713 }
714 }
715
716 void propagateThroughArgumentPositions()
717 {
718 for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
719 m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
720 }
721
722 // Sets any predictions that do not depends on other nodes.
723 void processInvariants()
724 {
725 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
726 for (Node* node : *block) {
727 m_currentNode = node;
728 processInvariantsForNode();
729 }
730 }
731 }
732
733 void processInvariantsForNode()
734 {
735 switch (m_currentNode->op()) {
736 case JSConstant: {
737 setPrediction(speculationFromValue(m_currentNode->asJSValue()));
738 break;
739 }
740 case DoubleConstant: {
741 SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
742 setPrediction(type);
743 break;
744 }
745
746 case ArithBitNot:
747 case ArithBitAnd:
748 case ArithBitOr:
749 case ArithBitXor:
750 case BitRShift:
751 case BitLShift:
752 case BitURShift:
753 case ArithIMul:
754 case ArithClz32: {
755 setPrediction(SpecInt32Only);
756 break;
757 }
758
759 case ArrayPop:
760 case ArrayPush:
761 case RegExpExec:
762 case RegExpExecNonGlobalOrSticky:
763 case RegExpTest:
764 case RegExpMatchFast:
765 case RegExpMatchFastGlobal:
766 case StringReplace:
767 case StringReplaceRegExp:
768 case GetById:
769 case GetByIdFlush:
770 case GetByIdWithThis:
771 case GetByIdDirect:
772 case GetByIdDirectFlush:
773 case TryGetById:
774 case GetByValWithThis:
775 case GetByOffset:
776 case MultiGetByOffset:
777 case GetDirectPname:
778 case Call:
779 case DirectCall:
780 case TailCallInlinedCaller:
781 case DirectTailCallInlinedCaller:
782 case Construct:
783 case DirectConstruct:
784 case CallVarargs:
785 case CallEval:
786 case TailCallVarargsInlinedCaller:
787 case ConstructVarargs:
788 case CallForwardVarargs:
789 case ConstructForwardVarargs:
790 case TailCallForwardVarargsInlinedCaller:
791 case GetGlobalVar:
792 case GetGlobalLexicalVariable:
793 case GetClosureVar:
794 case GetFromArguments:
795 case LoadKeyFromMapBucket:
796 case LoadValueFromMapBucket:
797 case ToNumber:
798 case ToObject:
799 case ValueBitAnd:
800 case ValueBitXor:
801 case ValueBitOr:
802 case ValueBitNot:
803 case CallObjectConstructor:
804 case GetArgument:
805 case CallDOMGetter:
806 case GetDynamicVar:
807 case GetPrototypeOf:
808 case ExtractValueFromWeakMapGet:
809 case DataViewGetInt:
810 case DataViewGetFloat: {
811 setPrediction(m_currentNode->getHeapPrediction());
812 break;
813 }
814
815 case WeakMapGet:
816 case ResolveScopeForHoistingFuncDeclInEval: {
817 setPrediction(SpecBytecodeTop);
818 break;
819 }
820
821 case GetGetterSetterByOffset:
822 case GetExecutable: {
823 setPrediction(SpecCellOther);
824 break;
825 }
826
827 case GetGetter:
828 case GetSetter:
829 case GetCallee:
830 case NewFunction:
831 case NewGeneratorFunction:
832 case NewAsyncGeneratorFunction:
833 case NewAsyncFunction: {
834 setPrediction(SpecFunction);
835 break;
836 }
837
838 case GetArgumentCountIncludingThis: {
839 setPrediction(SpecInt32Only);
840 break;
841 }
842
843 case SetCallee:
844 case SetArgumentCountIncludingThis:
845 break;
846
847 case MapHash:
848 setPrediction(SpecInt32Only);
849 break;
850
851 case GetMapBucket:
852 case GetMapBucketHead:
853 case GetMapBucketNext:
854 case SetAdd:
855 case MapSet:
856 setPrediction(SpecCellOther);
857 break;
858
859 case GetRestLength:
860 case ArrayIndexOf: {
861 setPrediction(SpecInt32Only);
862 break;
863 }
864
865 case GetTypedArrayByteOffset:
866 case GetArrayLength:
867 case GetVectorLength: {
868 setPrediction(SpecInt32Only);
869 break;
870 }
871
872 case StringCharCodeAt: {
873 setPrediction(SpecInt32Only);
874 break;
875 }
876
877 case StringValueOf:
878 case StringSlice:
879 case ToLowerCase:
880 setPrediction(SpecString);
881 break;
882
883 case ArithPow:
884 case ArithSqrt:
885 case ArithFRound:
886 case ArithUnary: {
887 setPrediction(SpecBytecodeDouble);
888 break;
889 }
890
891 case ArithRound:
892 case ArithFloor:
893 case ArithCeil:
894 case ArithTrunc: {
895 if (isInt32OrBooleanSpeculation(m_currentNode->getHeapPrediction())
896 && m_graph.roundShouldSpeculateInt32(m_currentNode, m_pass))
897 setPrediction(SpecInt32Only);
898 else
899 setPrediction(SpecBytecodeDouble);
900 break;
901 }
902
903 case ArithRandom: {
904 setPrediction(SpecDoubleReal);
905 break;
906 }
907 case DeleteByVal:
908 case DeleteById:
909 case LogicalNot:
910 case CompareLess:
911 case CompareLessEq:
912 case CompareGreater:
913 case CompareGreaterEq:
914 case CompareBelow:
915 case CompareBelowEq:
916 case CompareEq:
917 case CompareStrictEq:
918 case CompareEqPtr:
919 case SameValue:
920 case OverridesHasInstance:
921 case InstanceOf:
922 case InstanceOfCustom:
923 case IsEmpty:
924 case IsUndefined:
925 case IsUndefinedOrNull:
926 case IsBoolean:
927 case IsNumber:
928 case NumberIsInteger:
929 case IsObject:
930 case IsObjectOrNull:
931 case IsFunction:
932 case IsCellWithType:
933 case IsTypedArrayView:
934 case MatchStructure: {
935 setPrediction(SpecBoolean);
936 break;
937 }
938
939 case TypeOf: {
940 setPrediction(SpecStringIdent);
941 break;
942 }
943 case GetButterfly:
944 case GetIndexedPropertyStorage:
945 case AllocatePropertyStorage:
946 case ReallocatePropertyStorage: {
947 setPrediction(SpecOther);
948 break;
949 }
950
951 case CheckSubClass:
952 break;
953
954 case SkipScope:
955 case GetGlobalObject: {
956 setPrediction(SpecObjectOther);
957 break;
958 }
959
960 case GetGlobalThis:
961 setPrediction(SpecObject);
962 break;
963
964 case ResolveScope: {
965 setPrediction(SpecObjectOther);
966 break;
967 }
968
969 case ObjectCreate:
970 case CreateThis:
971 case NewObject: {
972 setPrediction(SpecFinalObject);
973 break;
974 }
975
976 case ArraySlice:
977 case NewArrayWithSpread:
978 case NewArray:
979 case NewArrayWithSize:
980 case CreateRest:
981 case NewArrayBuffer:
982 case ObjectKeys: {
983 setPrediction(SpecArray);
984 break;
985 }
986
987 case Spread:
988 setPrediction(SpecCellOther);
989 break;
990
991 case NewTypedArray: {
992 setPrediction(speculationFromTypedArrayType(m_currentNode->typedArrayType()));
993 break;
994 }
995
996 case NewRegexp: {
997 setPrediction(SpecRegExpObject);
998 break;
999 }
1000
1001 case PushWithScope:
1002 case CreateActivation: {
1003 setPrediction(SpecObjectOther);
1004 break;
1005 }
1006
1007 case StringFromCharCode: {
1008 setPrediction(SpecString);
1009 m_currentNode->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
1010 break;
1011 }
1012 case StringCharAt:
1013 case CallStringConstructor:
1014 case ToString:
1015 case NumberToStringWithRadix:
1016 case NumberToStringWithValidRadixConstant:
1017 case MakeRope:
1018 case StrCat: {
1019 setPrediction(SpecString);
1020 break;
1021 }
1022 case NewStringObject: {
1023 setPrediction(SpecStringObject);
1024 break;
1025 }
1026 case NewSymbol: {
1027 setPrediction(SpecSymbol);
1028 break;
1029 }
1030
1031 case CreateDirectArguments: {
1032 setPrediction(SpecDirectArguments);
1033 break;
1034 }
1035
1036 case CreateScopedArguments: {
1037 setPrediction(SpecScopedArguments);
1038 break;
1039 }
1040
1041 case CreateClonedArguments: {
1042 setPrediction(SpecObjectOther);
1043 break;
1044 }
1045
1046 case FiatInt52: {
1047 RELEASE_ASSERT(enableInt52());
1048 setPrediction(SpecInt52Any);
1049 break;
1050 }
1051
1052 case GetScope:
1053 setPrediction(SpecObjectOther);
1054 break;
1055
1056 case InByVal:
1057 case InById:
1058 setPrediction(SpecBoolean);
1059 break;
1060
1061 case HasOwnProperty:
1062 setPrediction(SpecBoolean);
1063 break;
1064
1065 case GetEnumerableLength: {
1066 setPrediction(SpecInt32Only);
1067 break;
1068 }
1069 case HasGenericProperty:
1070 case HasStructureProperty:
1071 case HasIndexedProperty: {
1072 setPrediction(SpecBoolean);
1073 break;
1074 }
1075 case GetPropertyEnumerator: {
1076 setPrediction(SpecCell);
1077 break;
1078 }
1079 case GetEnumeratorStructurePname: {
1080 setPrediction(SpecCell | SpecOther);
1081 break;
1082 }
1083 case GetEnumeratorGenericPname: {
1084 setPrediction(SpecCell | SpecOther);
1085 break;
1086 }
1087 case ToIndexString: {
1088 setPrediction(SpecString);
1089 break;
1090 }
1091 case ParseInt: {
1092 // We expect this node to almost always produce an int32. However,
1093 // it's possible it produces NaN or integers out of int32 range. We
1094 // rely on the heap prediction since the parseInt() call profiled
1095 // its result.
1096 setPrediction(m_currentNode->getHeapPrediction());
1097 break;
1098 }
1099
1100 case IdentityWithProfile: {
1101 setPrediction(m_currentNode->getForcedPrediction());
1102 break;
1103 }
1104
1105 case ExtractCatchLocal: {
1106 setPrediction(m_currentNode->catchLocalPrediction());
1107 break;
1108 }
1109
1110 case GetLocal:
1111 case SetLocal:
1112 case UInt32ToNumber:
1113 case ValueNegate:
1114 case ValueAdd:
1115 case ValueSub:
1116 case ValueMul:
1117 case ValueDiv:
1118 case ArithAdd:
1119 case ArithSub:
1120 case ArithNegate:
1121 case ArithMin:
1122 case ArithMax:
1123 case ArithMul:
1124 case ArithDiv:
1125 case ArithMod:
1126 case ArithAbs:
1127 case GetByVal:
1128 case ToThis:
1129 case ToPrimitive:
1130 case NormalizeMapKey:
1131 case AtomicsAdd:
1132 case AtomicsAnd:
1133 case AtomicsCompareExchange:
1134 case AtomicsExchange:
1135 case AtomicsLoad:
1136 case AtomicsOr:
1137 case AtomicsStore:
1138 case AtomicsSub:
1139 case AtomicsXor: {
1140 m_dependentNodes.append(m_currentNode);
1141 break;
1142 }
1143
1144 case AtomicsIsLockFree: {
1145 setPrediction(SpecBoolean);
1146 break;
1147 }
1148
1149 case CPUIntrinsic: {
1150 if (m_currentNode->intrinsic() == CPURdtscIntrinsic)
1151 setPrediction(SpecInt32Only);
1152 else
1153 setPrediction(SpecOther);
1154 break;
1155 }
1156
1157 case PutByValAlias:
1158 case DoubleAsInt32:
1159 case CheckArray:
1160 case CheckTypeInfoFlags:
1161 case Arrayify:
1162 case ArrayifyToStructure:
1163 case CheckTierUpInLoop:
1164 case CheckTierUpAtReturn:
1165 case CheckTierUpAndOSREnter:
1166 case CheckInBounds:
1167 case ValueToInt32:
1168 case DoubleRep:
1169 case ValueRep:
1170 case Int52Rep:
1171 case Int52Constant:
1172 case Identity:
1173 case BooleanToNumber:
1174 case PhantomNewObject:
1175 case PhantomNewFunction:
1176 case PhantomNewGeneratorFunction:
1177 case PhantomNewAsyncGeneratorFunction:
1178 case PhantomNewAsyncFunction:
1179 case PhantomCreateActivation:
1180 case PhantomDirectArguments:
1181 case PhantomCreateRest:
1182 case PhantomSpread:
1183 case PhantomNewArrayWithSpread:
1184 case PhantomNewArrayBuffer:
1185 case PhantomClonedArguments:
1186 case PhantomNewRegexp:
1187 case GetMyArgumentByVal:
1188 case GetMyArgumentByValOutOfBounds:
1189 case PutHint:
1190 case CheckStructureImmediate:
1191 case CheckStructureOrEmpty:
1192 case MaterializeNewObject:
1193 case MaterializeCreateActivation:
1194 case PutStack:
1195 case KillStack:
1196 case StoreBarrier:
1197 case FencedStoreBarrier:
1198 case GetStack:
1199 case GetRegExpObjectLastIndex:
1200 case SetRegExpObjectLastIndex:
1201 case RecordRegExpCachedResult:
1202 case LazyJSConstant:
1203 case CallDOM: {
1204 // This node should never be visible at this stage of compilation.
1205 DFG_CRASH(m_graph, m_currentNode, "Unexpected node during prediction propagation");
1206 break;
1207 }
1208
1209 case Phi:
1210 // Phis should not be visible here since we're iterating the all-but-Phi's
1211 // part of basic blocks.
1212 RELEASE_ASSERT_NOT_REACHED();
1213 break;
1214
1215 case EntrySwitch:
1216 case Upsilon:
1217 // These don't get inserted until we go into SSA.
1218 RELEASE_ASSERT_NOT_REACHED();
1219 break;
1220
1221#ifndef NDEBUG
1222 // These get ignored because they don't return anything.
1223 case PutByValDirect:
1224 case PutByValWithThis:
1225 case PutByIdWithThis:
1226 case PutByVal:
1227 case PutClosureVar:
1228 case PutToArguments:
1229 case Return:
1230 case Throw:
1231 case ThrowStaticError:
1232 case TailCall:
1233 case DirectTailCall:
1234 case TailCallVarargs:
1235 case TailCallForwardVarargs:
1236 case PutById:
1237 case PutByIdFlush:
1238 case PutByIdDirect:
1239 case PutByOffset:
1240 case MultiPutByOffset:
1241 case PutGetterById:
1242 case PutSetterById:
1243 case PutGetterSetterById:
1244 case PutGetterByVal:
1245 case PutSetterByVal:
1246 case DefineDataProperty:
1247 case DefineAccessorProperty:
1248 case DFG::Jump:
1249 case Branch:
1250 case Switch:
1251 case ProfileType:
1252 case ProfileControlFlow:
1253 case ForceOSRExit:
1254 case SetArgument:
1255 case SetFunctionName:
1256 case CheckStructure:
1257 case CheckCell:
1258 case CheckNotEmpty:
1259 case AssertNotEmpty:
1260 case CheckStringIdent:
1261 case CheckBadCell:
1262 case PutStructure:
1263 case Phantom:
1264 case Check:
1265 case CheckVarargs:
1266 case PutGlobalVariable:
1267 case CheckTraps:
1268 case LogShadowChickenPrologue:
1269 case LogShadowChickenTail:
1270 case Unreachable:
1271 case LoopHint:
1272 case NotifyWrite:
1273 case ConstantStoragePointer:
1274 case MovHint:
1275 case ZombieHint:
1276 case ExitOK:
1277 case LoadVarargs:
1278 case ForwardVarargs:
1279 case PutDynamicVar:
1280 case NukeStructureAndSetButterfly:
1281 case InitializeEntrypointArguments:
1282 case WeakSetAdd:
1283 case WeakMapSet:
1284 case FilterCallLinkStatus:
1285 case FilterGetByIdStatus:
1286 case FilterPutByIdStatus:
1287 case FilterInByIdStatus:
1288 case ClearCatchLocals:
1289 case DataViewSet:
1290 case InvalidationPoint:
1291 break;
1292
1293 // This gets ignored because it only pretends to produce a value.
1294 case BottomValue:
1295 break;
1296
1297 // This gets ignored because it already has a prediction.
1298 case ExtractOSREntryLocal:
1299 break;
1300
1301 // These gets ignored because it doesn't do anything.
1302 case CountExecution:
1303 case SuperSamplerBegin:
1304 case SuperSamplerEnd:
1305 case PhantomLocal:
1306 case Flush:
1307 break;
1308
1309 case LastNodeType:
1310 RELEASE_ASSERT_NOT_REACHED();
1311 break;
1312#else
1313 default:
1314 break;
1315#endif
1316 }
1317 }
1318
1319 SpeculatedType resultOfToPrimitive(SpeculatedType type)
1320 {
1321 if (type & SpecObject) {
1322 // We try to be optimistic here about StringObjects since it's unlikely that
1323 // someone overrides the valueOf or toString methods.
1324 if (type & SpecStringObject && m_graph.canOptimizeStringObjectAccess(m_currentNode->origin.semantic))
1325 return mergeSpeculations(type & ~SpecObject, SpecString);
1326
1327 return mergeSpeculations(type & ~SpecObject, SpecPrimitive);
1328 }
1329
1330 return type;
1331 }
1332
1333 Vector<Node*> m_dependentNodes;
1334 Node* m_currentNode;
1335 bool m_changed { false };
1336 PredictionPass m_pass { PrimaryPass }; // We use different logic for considering predictions depending on how far along we are in propagation.
1337};
1338
1339} // Anonymous namespace.
1340
1341bool performPredictionPropagation(Graph& graph)
1342{
1343 return runPhase<PredictionPropagationPhase>(graph);
1344}
1345
1346} } // namespace JSC::DFG
1347
1348#endif // ENABLE(DFG_JIT)
1349
1350