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