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