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