9537ce062407c022caa1a87b726101c3075e73c1
[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 & 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     
1364 bool performPredictionPropagation(Graph& graph)
1365 {
1366     return runPhase<PredictionPropagationPhase>(graph);
1367 }
1368
1369 } } // namespace JSC::DFG
1370
1371 #endif // ENABLE(DFG_JIT)
1372