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