[BigInt] Add support to BigInt into ValueAdd
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGPredictionPropagationPhase.cpp
1 /*
2  * Copyright (C) 2011-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DFGPredictionPropagationPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32 #include "DFGPhase.h"
33 #include "JSCInlines.h"
34
35 namespace JSC { namespace DFG {
36
37 namespace {
38
39 bool verboseFixPointLoops = false;
40
41 class PredictionPropagationPhase : public Phase {
42 public:
43     PredictionPropagationPhase(Graph& graph)
44         : Phase(graph, "prediction propagation")
45     {
46     }
47     
48     bool run()
49     {
50         ASSERT(m_graph.m_form == ThreadedCPS);
51         ASSERT(m_graph.m_unificationState == GloballyUnified);
52
53         m_pass = PrimaryPass;
54
55         propagateThroughArgumentPositions();
56
57         processInvariants();
58
59         propagateToFixpoint();
60         
61         m_pass = RareCasePass;
62         propagateToFixpoint();
63         
64         m_pass = DoubleVotingPass;
65         unsigned counter = 0;
66         do {
67             if (verboseFixPointLoops)
68                 ++counter;
69
70             m_changed = false;
71             doRoundOfDoubleVoting();
72             if (!m_changed)
73                 break;
74             m_changed = false;
75             propagateForward();
76         } while (m_changed);
77
78         if (verboseFixPointLoops)
79             dataLog("Iterated ", counter, " times in double voting fixpoint.\n");
80         
81         return true;
82     }
83     
84 private:
85     void propagateToFixpoint()
86     {
87         unsigned counter = 0;
88         do {
89             if (verboseFixPointLoops)
90                 ++counter;
91
92             m_changed = false;
93
94             // Forward propagation is near-optimal for both topologically-sorted and
95             // DFS-sorted code.
96             propagateForward();
97             if (!m_changed)
98                 break;
99             
100             // Backward propagation reduces the likelihood that pathological code will
101             // cause slowness. Loops (especially nested ones) resemble backward flow.
102             // This pass captures two cases: (1) it detects if the forward fixpoint
103             // found a sound solution and (2) short-circuits backward flow.
104             m_changed = false;
105             propagateBackward();
106         } while (m_changed);
107
108         if (verboseFixPointLoops)
109             dataLog("Iterated ", counter, " times in propagateToFixpoint.\n");
110     }
111     
112     bool setPrediction(SpeculatedType prediction)
113     {
114         ASSERT(m_currentNode->hasResult());
115         
116         // setPrediction() is used when we know that there is no way that we can change
117         // our minds about what the prediction is going to be. There is no semantic
118         // difference between setPrediction() and mergeSpeculation() other than the
119         // increased checking to validate this property.
120         ASSERT(m_currentNode->prediction() == SpecNone || m_currentNode->prediction() == prediction);
121         
122         return m_currentNode->predict(prediction);
123     }
124     
125     bool mergePrediction(SpeculatedType prediction)
126     {
127         ASSERT(m_currentNode->hasResult());
128         
129         return m_currentNode->predict(prediction);
130     }
131     
132     SpeculatedType speculatedDoubleTypeForPrediction(SpeculatedType value)
133     {
134         SpeculatedType result = SpecDoubleReal;
135         if (value & SpecDoubleImpureNaN)
136             result |= SpecDoubleImpureNaN;
137         if (value & SpecDoublePureNaN)
138             result |= SpecDoublePureNaN;
139         if (!isFullNumberOrBooleanSpeculation(value))
140             result |= SpecDoublePureNaN;
141         return result;
142     }
143
144     SpeculatedType speculatedDoubleTypeForPredictions(SpeculatedType left, SpeculatedType right)
145     {
146         return speculatedDoubleTypeForPrediction(mergeSpeculations(left, right));
147     }
148
149     void propagate(Node* node)
150     {
151         NodeType op = node->op();
152
153         bool changed = false;
154         
155         switch (op) {
156         case GetLocal: {
157             VariableAccessData* variable = node->variableAccessData();
158             SpeculatedType prediction = variable->prediction();
159             if (!variable->couldRepresentInt52() && (prediction & SpecInt52Only))
160                 prediction = (prediction | SpecAnyIntAsDouble) & ~SpecInt52Only;
161             if (prediction)
162                 changed |= mergePrediction(prediction);
163             break;
164         }
165             
166         case SetLocal: {
167             VariableAccessData* variableAccessData = node->variableAccessData();
168             changed |= variableAccessData->predict(node->child1()->prediction());
169             break;
170         }
171
172         case UInt32ToNumber: {
173             if (node->canSpeculateInt32(m_pass))
174                 changed |= mergePrediction(SpecInt32Only);
175             else if (enableInt52())
176                 changed |= mergePrediction(SpecAnyInt);
177             else
178                 changed |= mergePrediction(SpecBytecodeNumber);
179             break;
180         }
181
182         case ValueAdd: {
183             SpeculatedType left = node->child1()->prediction();
184             SpeculatedType right = node->child2()->prediction();
185             
186             if (left && right) {
187                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
188                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
189                     if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
190                         changed |= mergePrediction(SpecInt32Only);
191                     else if (m_graph.addShouldSpeculateAnyInt(node))
192                         changed |= mergePrediction(SpecInt52Only);
193                     else
194                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
195                 } else if (isStringOrStringObjectSpeculation(left) || isStringOrStringObjectSpeculation(right)) {
196                     // left or right is definitely something other than a number.
197                     changed |= mergePrediction(SpecString);
198                 } else 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.addShouldSpeculateAnyInt(node))
221                     changed |= mergePrediction(SpecInt52Only);
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.addShouldSpeculateAnyInt(node))
242                         changed |= mergePrediction(SpecInt52Only);
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.addShouldSpeculateAnyInt(node))
263                         changed |= mergePrediction(SpecInt52Only);
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 ValueBitOr:
281         case ValueBitAnd: {
282             if (node->child1()->shouldSpeculateBigInt() && node->child2()->shouldSpeculateBigInt())
283                 changed |= mergePrediction(SpecBigInt);
284             break;
285         }
286
287         case ValueNegate:
288         case ArithNegate: {
289             SpeculatedType prediction = node->child1()->prediction();
290             if (prediction) {
291                 if (isInt32OrBooleanSpeculation(prediction) && node->canSpeculateInt32(m_pass))
292                     changed |= mergePrediction(SpecInt32Only);
293                 else if (m_graph.unaryArithShouldSpeculateAnyInt(node, m_pass))
294                     changed |= mergePrediction(SpecInt52Only);
295                 else if (isBytecodeNumberSpeculation(prediction))
296                     changed |= mergePrediction(speculatedDoubleTypeForPrediction(node->child1()->prediction()));
297                 else {
298                     changed |= mergePrediction(SpecInt32Only);
299                     if (node->op() == ValueNegate && node->mayHaveBigIntResult())
300                         changed |= mergePrediction(SpecBigInt);
301                     if (node->mayHaveDoubleResult())
302                         changed |= mergePrediction(SpecBytecodeDouble);
303                 }
304             }
305             break;
306         }
307         case ArithMin:
308         case ArithMax: {
309             SpeculatedType left = node->child1()->prediction();
310             SpeculatedType right = node->child2()->prediction();
311             
312             if (left && right) {
313                 if (Node::shouldSpeculateInt32OrBooleanForArithmetic(node->child1().node(), node->child2().node())
314                     && node->canSpeculateInt32(m_pass))
315                     changed |= mergePrediction(SpecInt32Only);
316                 else
317                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
318             }
319             break;
320         }
321
322         case ArithMul: {
323             SpeculatedType left = node->child1()->prediction();
324             SpeculatedType right = node->child2()->prediction();
325             
326             if (left && right) {
327                 // FIXME: We're currently relying on prediction propagation and backwards propagation
328                 // whenever we can, and only falling back on result flags if that fails. And the result
329                 // flags logic doesn't know how to use backwards propagation. We should get rid of the
330                 // prediction propagation logic and rely solely on the result type.
331                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
332                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
333                     if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
334                         changed |= mergePrediction(SpecInt32Only);
335                     else if (m_graph.binaryArithShouldSpeculateAnyInt(node, m_pass))
336                         changed |= mergePrediction(SpecInt52Only);
337                     else
338                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
339                 } else {
340                     if (node->mayHaveNonIntResult()
341                         || (left & SpecBytecodeDouble)
342                         || (right & SpecBytecodeDouble))
343                         changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
344                     else
345                         changed |= mergePrediction(SpecInt32Only);
346                 }
347             }
348             break;
349         }
350
351         case ArithDiv:
352         case ArithMod: {
353             SpeculatedType left = node->child1()->prediction();
354             SpeculatedType right = node->child2()->prediction();
355             
356             if (left && right) {
357                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
358                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
359                     if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
360                         changed |= mergePrediction(SpecInt32Only);
361                     else
362                         changed |= mergePrediction(SpecBytecodeDouble);
363                 } else
364                     changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
365             }
366             break;
367         }
368
369         case ArithAbs: {
370             SpeculatedType childPrediction = node->child1()->prediction();
371             if (isInt32OrBooleanSpeculation(childPrediction)
372                 && node->canSpeculateInt32(m_pass))
373                 changed |= mergePrediction(SpecInt32Only);
374             else
375                 changed |= mergePrediction(SpecBytecodeDouble);
376             break;
377         }
378
379         case GetByVal:
380         case AtomicsAdd:
381         case AtomicsAnd:
382         case AtomicsCompareExchange:
383         case AtomicsExchange:
384         case AtomicsLoad:
385         case AtomicsOr:
386         case AtomicsStore:
387         case AtomicsSub:
388         case AtomicsXor: {
389             Edge child1 = m_graph.child(node, 0);
390             if (!child1->prediction())
391                 break;
392             
393             Edge child2 = m_graph.child(node, 1);
394             ArrayMode arrayMode = node->arrayMode().refine(
395                 m_graph, node,
396                 child1->prediction(),
397                 child2->prediction(),
398                 SpecNone);
399             
400             switch (arrayMode.type()) {
401             case Array::Int32:
402                 if (arrayMode.isOutOfBounds())
403                     changed |= mergePrediction(node->getHeapPrediction() | SpecInt32Only);
404                 else
405                     changed |= mergePrediction(SpecInt32Only);
406                 break;
407             case Array::Double:
408                 if (arrayMode.isOutOfBounds())
409                     changed |= mergePrediction(node->getHeapPrediction() | SpecDoubleReal);
410                 else if (node->getHeapPrediction() & SpecNonIntAsDouble)
411                     changed |= mergePrediction(SpecDoubleReal);
412                 else
413                     changed |= mergePrediction(SpecAnyIntAsDouble);
414                 break;
415             case Array::Float32Array:
416             case Array::Float64Array:
417                 changed |= mergePrediction(SpecFullDouble);
418                 break;
419             case Array::Uint32Array:
420                 if (isInt32SpeculationForArithmetic(node->getHeapPrediction()) && node->op() == GetByVal)
421                     changed |= mergePrediction(SpecInt32Only);
422                 else if (enableInt52())
423                     changed |= mergePrediction(SpecAnyInt);
424                 else
425                     changed |= mergePrediction(SpecInt32Only | SpecAnyIntAsDouble);
426                 break;
427             case Array::Int8Array:
428             case Array::Uint8Array:
429             case Array::Int16Array:
430             case Array::Uint16Array:
431             case Array::Int32Array:
432                 changed |= mergePrediction(SpecInt32Only);
433                 break;
434             default:
435                 changed |= mergePrediction(node->getHeapPrediction());
436                 break;
437             }
438             break;
439         }
440             
441         case ToThis: {
442             // ToThis in methods for primitive types should speculate primitive types in strict mode.
443             ECMAMode ecmaMode = m_graph.executableFor(node->origin.semantic)->isStrictMode() ? StrictMode : NotStrictMode;
444             if (ecmaMode == StrictMode) {
445                 if (node->child1()->shouldSpeculateBoolean()) {
446                     changed |= mergePrediction(SpecBoolean);
447                     break;
448                 }
449
450                 if (node->child1()->shouldSpeculateInt32()) {
451                     changed |= mergePrediction(SpecInt32Only);
452                     break;
453                 }
454
455                 if (enableInt52() && node->child1()->shouldSpeculateAnyInt()) {
456                     changed |= mergePrediction(SpecAnyInt);
457                     break;
458                 }
459
460                 if (node->child1()->shouldSpeculateNumber()) {
461                     changed |= mergePrediction(SpecBytecodeNumber);
462                     break;
463                 }
464
465                 if (node->child1()->shouldSpeculateSymbol()) {
466                     changed |= mergePrediction(SpecSymbol);
467                     break;
468                 }
469                 
470                 if (node->child1()->shouldSpeculateBigInt()) {
471                     changed |= mergePrediction(SpecBigInt);
472                     break;
473                 }
474
475                 if (node->child1()->shouldSpeculateStringIdent()) {
476                     changed |= mergePrediction(SpecStringIdent);
477                     break;
478                 }
479
480                 if (node->child1()->shouldSpeculateString()) {
481                     changed |= mergePrediction(SpecString);
482                     break;
483                 }
484             } else {
485                 if (node->child1()->shouldSpeculateString()) {
486                     changed |= mergePrediction(SpecStringObject);
487                     break;
488                 }
489             }
490
491             SpeculatedType prediction = node->child1()->prediction();
492             if (ecmaMode == StrictMode)
493                 changed |= mergePrediction(node->getHeapPrediction());
494             else if (prediction) {
495                 if (prediction & ~SpecObject) {
496                     // Wrapper objects are created only in sloppy mode.
497                     prediction &= SpecObject;
498                     prediction = mergeSpeculations(prediction, SpecObjectOther);
499                 }
500                 changed |= mergePrediction(prediction);
501             }
502             break;
503         }
504             
505         case ToPrimitive: {
506             SpeculatedType child = node->child1()->prediction();
507             if (child)
508                 changed |= mergePrediction(resultOfToPrimitive(child));
509             break;
510         }
511
512         case NormalizeMapKey: {
513             SpeculatedType prediction = node->child1()->prediction();
514             if (prediction)
515                 changed |= mergePrediction(prediction);
516             break;
517         }
518
519         default:
520             break;
521         }
522
523         m_changed |= changed;
524     }
525         
526     void propagateForward()
527     {
528         for (Node* node : m_dependentNodes) {
529             m_currentNode = node;
530             propagate(m_currentNode);
531         }
532     }
533
534     void propagateBackward()
535     {
536         for (unsigned i = m_dependentNodes.size(); i--;) {
537             m_currentNode = m_dependentNodes[i];
538             propagate(m_currentNode);
539         }
540     }
541     
542     void doDoubleVoting(Node* node, float weight)
543     {
544         // Loop pre-headers created by OSR entrypoint creation may have NaN weight to indicate
545         // that we actually don't know they weight. Assume that they execute once. This turns
546         // out to be an OK assumption since the pre-header doesn't have any meaningful code.
547         if (weight != weight)
548             weight = 1;
549         
550         switch (node->op()) {
551         case ValueAdd:
552         case ValueSub:
553         case ArithAdd:
554         case ArithSub: {
555             SpeculatedType left = node->child1()->prediction();
556             SpeculatedType right = node->child2()->prediction();
557                 
558             DoubleBallot ballot;
559                 
560             if (isFullNumberSpeculation(left)
561                 && isFullNumberSpeculation(right)
562                 && !m_graph.addShouldSpeculateInt32(node, m_pass)
563                 && !m_graph.addShouldSpeculateAnyInt(node))
564                 ballot = VoteDouble;
565             else
566                 ballot = VoteValue;
567                 
568             m_graph.voteNode(node->child1(), ballot, weight);
569             m_graph.voteNode(node->child2(), ballot, weight);
570             break;
571         }
572
573         case ArithMul: {
574             SpeculatedType left = node->child1()->prediction();
575             SpeculatedType right = node->child2()->prediction();
576                 
577             DoubleBallot ballot;
578                 
579             if (isFullNumberSpeculation(left)
580                 && isFullNumberSpeculation(right)
581                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass)
582                 && !m_graph.binaryArithShouldSpeculateAnyInt(node, m_pass))
583                 ballot = VoteDouble;
584             else
585                 ballot = VoteValue;
586                 
587             m_graph.voteNode(node->child1(), ballot, weight);
588             m_graph.voteNode(node->child2(), ballot, weight);
589             break;
590         }
591
592         case ArithMin:
593         case ArithMax:
594         case ArithMod:
595         case ArithDiv: {
596             SpeculatedType left = node->child1()->prediction();
597             SpeculatedType right = node->child2()->prediction();
598                 
599             DoubleBallot ballot;
600                 
601             if (isFullNumberSpeculation(left)
602                 && isFullNumberSpeculation(right)
603                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
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 ArithAbs:
614             DoubleBallot ballot;
615             if (node->child1()->shouldSpeculateNumber()
616                 && !m_graph.unaryArithShouldSpeculateInt32(node, m_pass))
617                 ballot = VoteDouble;
618             else
619                 ballot = VoteValue;
620                 
621             m_graph.voteNode(node->child1(), ballot, weight);
622             break;
623                 
624         case ArithSqrt:
625         case ArithUnary:
626             if (node->child1()->shouldSpeculateNumber())
627                 m_graph.voteNode(node->child1(), VoteDouble, weight);
628             else
629                 m_graph.voteNode(node->child1(), VoteValue, weight);
630             break;
631                 
632         case SetLocal: {
633             SpeculatedType prediction = node->child1()->prediction();
634             if (isDoubleSpeculation(prediction))
635                 node->variableAccessData()->vote(VoteDouble, weight);
636             else if (!isFullNumberSpeculation(prediction)
637                 || isInt32Speculation(prediction) || isAnyIntSpeculation(prediction))
638                 node->variableAccessData()->vote(VoteValue, weight);
639             break;
640         }
641
642         case PutByValDirect:
643         case PutByVal:
644         case PutByValAlias: {
645             Edge child1 = m_graph.varArgChild(node, 0);
646             Edge child2 = m_graph.varArgChild(node, 1);
647             Edge child3 = m_graph.varArgChild(node, 2);
648             m_graph.voteNode(child1, VoteValue, weight);
649             m_graph.voteNode(child2, VoteValue, weight);
650             switch (node->arrayMode().type()) {
651             case Array::Double:
652                 m_graph.voteNode(child3, VoteDouble, weight);
653                 break;
654             default:
655                 m_graph.voteNode(child3, VoteValue, weight);
656                 break;
657             }
658             break;
659         }
660         
661         case DataViewSet: {
662             DataViewData data = node->dataViewData();
663             if (data.isFloatingPoint)
664                 m_graph.voteNode(m_graph.varArgChild(node, 2), VoteValue, weight);
665             break;
666         }
667
668         case MovHint:
669             // Ignore these since they have no effect on in-DFG execution.
670             break;
671             
672         default:
673             m_graph.voteChildren(node, VoteValue, weight);
674             break;
675         }
676     }
677     
678     void doRoundOfDoubleVoting()
679     {
680         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
681             m_graph.m_variableAccessData[i].find()->clearVotes();
682         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
683             BasicBlock* block = m_graph.block(blockIndex);
684             if (!block)
685                 continue;
686             ASSERT(block->isReachable);
687             for (unsigned i = 0; i < block->size(); ++i) {
688                 m_currentNode = block->at(i);
689                 doDoubleVoting(m_currentNode, block->executionCount);
690             }
691         }
692         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
693             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
694             if (!variableAccessData->isRoot())
695                 continue;
696             m_changed |= variableAccessData->tallyVotesForShouldUseDoubleFormat();
697         }
698         propagateThroughArgumentPositions();
699         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
700             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
701             if (!variableAccessData->isRoot())
702                 continue;
703             m_changed |= variableAccessData->makePredictionForDoubleFormat();
704         }
705     }
706     
707     void propagateThroughArgumentPositions()
708     {
709         for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
710             m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
711     }
712
713     // Sets any predictions that do not depends on other nodes.
714     void processInvariants()
715     {
716         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
717             for (Node* node : *block) {
718                 m_currentNode = node;
719                 processInvariantsForNode();
720             }
721         }
722     }
723
724     void processInvariantsForNode()
725     {
726         switch (m_currentNode->op()) {
727         case JSConstant: {
728             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
729             if (type == SpecAnyIntAsDouble && enableInt52())
730                 type = SpecInt52Only;
731             setPrediction(type);
732             break;
733         }
734         case DoubleConstant: {
735             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
736             setPrediction(type);
737             break;
738         }
739
740         case ArithBitAnd:
741         case ArithBitOr:
742         case BitXor:
743         case BitRShift:
744         case BitLShift:
745         case BitURShift:
746         case ArithIMul:
747         case ArithClz32: {
748             setPrediction(SpecInt32Only);
749             break;
750         }
751
752         case ArrayPop:
753         case ArrayPush:
754         case RegExpExec:
755         case RegExpExecNonGlobalOrSticky:
756         case RegExpTest:
757         case RegExpMatchFast:
758         case RegExpMatchFastGlobal:
759         case StringReplace:
760         case StringReplaceRegExp:
761         case GetById:
762         case GetByIdFlush:
763         case GetByIdWithThis:
764         case GetByIdDirect:
765         case GetByIdDirectFlush:
766         case TryGetById:
767         case GetByValWithThis:
768         case GetByOffset:
769         case MultiGetByOffset:
770         case GetDirectPname:
771         case Call:
772         case DirectCall:
773         case TailCallInlinedCaller:
774         case DirectTailCallInlinedCaller:
775         case Construct:
776         case DirectConstruct:
777         case CallVarargs:
778         case CallEval:
779         case TailCallVarargsInlinedCaller:
780         case ConstructVarargs:
781         case CallForwardVarargs:
782         case ConstructForwardVarargs:
783         case TailCallForwardVarargsInlinedCaller:
784         case GetGlobalVar:
785         case GetGlobalLexicalVariable:
786         case GetClosureVar:
787         case GetFromArguments:
788         case LoadKeyFromMapBucket:
789         case LoadValueFromMapBucket:
790         case ToNumber:
791         case ToObject:
792         case CallObjectConstructor:
793         case GetArgument:
794         case CallDOMGetter:
795         case GetDynamicVar:
796         case GetPrototypeOf:
797         case ExtractValueFromWeakMapGet: 
798         case DataViewGetInt:
799         case DataViewGetFloat: {
800             setPrediction(m_currentNode->getHeapPrediction());
801             break;
802         }
803
804         case WeakMapGet:
805         case ResolveScopeForHoistingFuncDeclInEval: {
806             setPrediction(SpecBytecodeTop);
807             break;
808         }
809             
810         case GetGetterSetterByOffset:
811         case GetExecutable: {
812             setPrediction(SpecCellOther);
813             break;
814         }
815
816         case GetGetter:
817         case GetSetter:
818         case GetCallee:
819         case NewFunction:
820         case NewGeneratorFunction:
821         case NewAsyncGeneratorFunction:
822         case NewAsyncFunction: {
823             setPrediction(SpecFunction);
824             break;
825         }
826             
827         case GetArgumentCountIncludingThis: {
828             setPrediction(SpecInt32Only);
829             break;
830         }
831
832         case SetCallee:
833         case SetArgumentCountIncludingThis:
834             break;
835
836         case MapHash:
837             setPrediction(SpecInt32Only);
838             break;
839
840         case GetMapBucket:
841         case GetMapBucketHead:
842         case GetMapBucketNext:
843         case SetAdd:
844         case MapSet:
845             setPrediction(SpecCellOther);
846             break;
847
848         case GetRestLength:
849         case ArrayIndexOf: {
850             setPrediction(SpecInt32Only);
851             break;
852         }
853
854         case GetTypedArrayByteOffset:
855         case GetArrayLength:
856         case GetVectorLength: {
857             setPrediction(SpecInt32Only);
858             break;
859         }
860
861         case StringCharCodeAt: {
862             setPrediction(SpecInt32Only);
863             break;
864         }
865
866         case StringValueOf:
867         case StringSlice:
868         case ToLowerCase:
869             setPrediction(SpecString);
870             break;
871
872         case ArithPow:
873         case ArithSqrt:
874         case ArithFRound:
875         case ArithUnary: {
876             setPrediction(SpecBytecodeDouble);
877             break;
878         }
879
880         case ArithRound:
881         case ArithFloor:
882         case ArithCeil:
883         case ArithTrunc: {
884             if (isInt32OrBooleanSpeculation(m_currentNode->getHeapPrediction())
885                 && m_graph.roundShouldSpeculateInt32(m_currentNode, m_pass))
886                 setPrediction(SpecInt32Only);
887             else
888                 setPrediction(SpecBytecodeDouble);
889             break;
890         }
891
892         case ArithRandom: {
893             setPrediction(SpecDoubleReal);
894             break;
895         }
896         case DeleteByVal:
897         case DeleteById:
898         case LogicalNot:
899         case CompareLess:
900         case CompareLessEq:
901         case CompareGreater:
902         case CompareGreaterEq:
903         case CompareBelow:
904         case CompareBelowEq:
905         case CompareEq:
906         case CompareStrictEq:
907         case CompareEqPtr:
908         case SameValue:
909         case OverridesHasInstance:
910         case InstanceOf:
911         case InstanceOfCustom:
912         case IsEmpty:
913         case IsUndefined:
914         case IsBoolean:
915         case IsNumber:
916         case NumberIsInteger:
917         case IsObject:
918         case IsObjectOrNull:
919         case IsFunction:
920         case IsCellWithType:
921         case IsTypedArrayView:
922         case MatchStructure: {
923             setPrediction(SpecBoolean);
924             break;
925         }
926
927         case TypeOf: {
928             setPrediction(SpecStringIdent);
929             break;
930         }
931         case GetButterfly:
932         case GetIndexedPropertyStorage:
933         case AllocatePropertyStorage:
934         case ReallocatePropertyStorage: {
935             setPrediction(SpecOther);
936             break;
937         }
938
939         case CheckSubClass:
940             break;
941
942         case SkipScope:
943         case GetGlobalObject: {
944             setPrediction(SpecObjectOther);
945             break;
946         }
947
948         case GetGlobalThis:
949             setPrediction(SpecObject);
950             break;
951
952         case ResolveScope: {
953             setPrediction(SpecObjectOther);
954             break;
955         }
956             
957         case ObjectCreate:
958         case CreateThis:
959         case NewObject: {
960             setPrediction(SpecFinalObject);
961             break;
962         }
963             
964         case ArraySlice:
965         case NewArrayWithSpread:
966         case NewArray:
967         case NewArrayWithSize:
968         case CreateRest:
969         case NewArrayBuffer: {
970             setPrediction(SpecArray);
971             break;
972         }
973
974         case Spread:
975             setPrediction(SpecCellOther);
976             break;
977             
978         case NewTypedArray: {
979             setPrediction(speculationFromTypedArrayType(m_currentNode->typedArrayType()));
980             break;
981         }
982             
983         case NewRegexp: {
984             setPrediction(SpecRegExpObject);
985             break;
986         }
987             
988         case PushWithScope:
989         case CreateActivation: {
990             setPrediction(SpecObjectOther);
991             break;
992         }
993         
994         case StringFromCharCode: {
995             setPrediction(SpecString);
996             m_currentNode->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
997             break;
998         }
999         case StringCharAt:
1000         case CallStringConstructor:
1001         case ToString:
1002         case NumberToStringWithRadix:
1003         case NumberToStringWithValidRadixConstant:
1004         case MakeRope:
1005         case StrCat: {
1006             setPrediction(SpecString);
1007             break;
1008         }
1009         case NewStringObject: {
1010             setPrediction(SpecStringObject);
1011             break;
1012         }
1013             
1014         case CreateDirectArguments: {
1015             setPrediction(SpecDirectArguments);
1016             break;
1017         }
1018             
1019         case CreateScopedArguments: {
1020             setPrediction(SpecScopedArguments);
1021             break;
1022         }
1023             
1024         case CreateClonedArguments: {
1025             setPrediction(SpecObjectOther);
1026             break;
1027         }
1028             
1029         case FiatInt52: {
1030             RELEASE_ASSERT(enableInt52());
1031             setPrediction(SpecAnyInt);
1032             break;
1033         }
1034
1035         case GetScope:
1036             setPrediction(SpecObjectOther);
1037             break;
1038
1039         case InByVal:
1040         case InById:
1041             setPrediction(SpecBoolean);
1042             break;
1043
1044         case HasOwnProperty:
1045             setPrediction(SpecBoolean);
1046             break;
1047
1048         case GetEnumerableLength: {
1049             setPrediction(SpecInt32Only);
1050             break;
1051         }
1052         case HasGenericProperty:
1053         case HasStructureProperty:
1054         case HasIndexedProperty: {
1055             setPrediction(SpecBoolean);
1056             break;
1057         }
1058         case GetPropertyEnumerator: {
1059             setPrediction(SpecCell);
1060             break;
1061         }
1062         case GetEnumeratorStructurePname: {
1063             setPrediction(SpecCell | SpecOther);
1064             break;
1065         }
1066         case GetEnumeratorGenericPname: {
1067             setPrediction(SpecCell | SpecOther);
1068             break;
1069         }
1070         case ToIndexString: {
1071             setPrediction(SpecString);
1072             break;
1073         }
1074         case ParseInt: {
1075             // We expect this node to almost always produce an int32. However,
1076             // it's possible it produces NaN or integers out of int32 range. We
1077             // rely on the heap prediction since the parseInt() call profiled
1078             // its result.
1079             setPrediction(m_currentNode->getHeapPrediction());
1080             break;
1081         }
1082
1083         case IdentityWithProfile: {
1084             setPrediction(m_currentNode->getForcedPrediction());
1085             break;
1086         }
1087
1088         case ExtractCatchLocal: {
1089             setPrediction(m_currentNode->catchLocalPrediction());
1090             break;
1091         }
1092
1093         case GetLocal:
1094         case SetLocal:
1095         case UInt32ToNumber:
1096         case ValueBitOr:
1097         case ValueBitAnd:
1098         case ValueNegate:
1099         case ValueAdd:
1100         case ValueSub:
1101         case ArithAdd:
1102         case ArithSub:
1103         case ArithNegate:
1104         case ArithMin:
1105         case ArithMax:
1106         case ArithMul:
1107         case ArithDiv:
1108         case ArithMod:
1109         case ArithAbs:
1110         case GetByVal:
1111         case ToThis:
1112         case ToPrimitive: 
1113         case NormalizeMapKey:
1114         case AtomicsAdd:
1115         case AtomicsAnd:
1116         case AtomicsCompareExchange:
1117         case AtomicsExchange:
1118         case AtomicsLoad:
1119         case AtomicsOr:
1120         case AtomicsStore:
1121         case AtomicsSub:
1122         case AtomicsXor: {
1123             m_dependentNodes.append(m_currentNode);
1124             break;
1125         }
1126             
1127         case AtomicsIsLockFree: {
1128             setPrediction(SpecBoolean);
1129             break;
1130         }
1131
1132         case CPUIntrinsic: {
1133             if (m_currentNode->intrinsic() == CPURdtscIntrinsic)
1134                 setPrediction(SpecInt32Only);
1135             else
1136                 setPrediction(SpecOther);
1137             break;
1138         }
1139
1140         case PutByValAlias:
1141         case DoubleAsInt32:
1142         case CheckArray:
1143         case CheckTypeInfoFlags:
1144         case Arrayify:
1145         case ArrayifyToStructure:
1146         case CheckTierUpInLoop:
1147         case CheckTierUpAtReturn:
1148         case CheckTierUpAndOSREnter:
1149         case CheckInBounds:
1150         case ValueToInt32:
1151         case DoubleRep:
1152         case ValueRep:
1153         case Int52Rep:
1154         case Int52Constant:
1155         case Identity:
1156         case BooleanToNumber:
1157         case PhantomNewObject:
1158         case PhantomNewFunction:
1159         case PhantomNewGeneratorFunction:
1160         case PhantomNewAsyncGeneratorFunction:
1161         case PhantomNewAsyncFunction:
1162         case PhantomCreateActivation:
1163         case PhantomDirectArguments:
1164         case PhantomCreateRest:
1165         case PhantomSpread:
1166         case PhantomNewArrayWithSpread:
1167         case PhantomNewArrayBuffer:
1168         case PhantomClonedArguments:
1169         case PhantomNewRegexp:
1170         case GetMyArgumentByVal:
1171         case GetMyArgumentByValOutOfBounds:
1172         case PutHint:
1173         case CheckStructureImmediate:
1174         case CheckStructureOrEmpty:
1175         case MaterializeNewObject:
1176         case MaterializeCreateActivation:
1177         case PutStack:
1178         case KillStack:
1179         case StoreBarrier:
1180         case FencedStoreBarrier:
1181         case GetStack:
1182         case GetRegExpObjectLastIndex:
1183         case SetRegExpObjectLastIndex:
1184         case RecordRegExpCachedResult:
1185         case LazyJSConstant:
1186         case CallDOM: {
1187             // This node should never be visible at this stage of compilation.
1188             DFG_CRASH(m_graph, m_currentNode, "Unexpected node during prediction propagation");
1189             break;
1190         }
1191         
1192         case Phi:
1193             // Phis should not be visible here since we're iterating the all-but-Phi's
1194             // part of basic blocks.
1195             RELEASE_ASSERT_NOT_REACHED();
1196             break;
1197             
1198         case EntrySwitch:
1199         case Upsilon:
1200             // These don't get inserted until we go into SSA.
1201             RELEASE_ASSERT_NOT_REACHED();
1202             break;
1203
1204 #ifndef NDEBUG
1205         // These get ignored because they don't return anything.
1206         case PutByValDirect:
1207         case PutByValWithThis:
1208         case PutByIdWithThis:
1209         case PutByVal:
1210         case PutClosureVar:
1211         case PutToArguments:
1212         case Return:
1213         case Throw:
1214         case ThrowStaticError:
1215         case TailCall:
1216         case DirectTailCall:
1217         case TailCallVarargs:
1218         case TailCallForwardVarargs:
1219         case PutById:
1220         case PutByIdFlush:
1221         case PutByIdDirect:
1222         case PutByOffset:
1223         case MultiPutByOffset:
1224         case PutGetterById:
1225         case PutSetterById:
1226         case PutGetterSetterById:
1227         case PutGetterByVal:
1228         case PutSetterByVal:
1229         case DefineDataProperty:
1230         case DefineAccessorProperty:
1231         case DFG::Jump:
1232         case Branch:
1233         case Switch:
1234         case ProfileType:
1235         case ProfileControlFlow:
1236         case ForceOSRExit:
1237         case SetArgument:
1238         case SetFunctionName:
1239         case CheckStructure:
1240         case CheckCell:
1241         case CheckNotEmpty:
1242         case AssertNotEmpty:
1243         case CheckStringIdent:
1244         case CheckBadCell:
1245         case PutStructure:
1246         case Phantom:
1247         case Check:
1248         case CheckVarargs:
1249         case PutGlobalVariable:
1250         case CheckTraps:
1251         case LogShadowChickenPrologue:
1252         case LogShadowChickenTail:
1253         case Unreachable:
1254         case LoopHint:
1255         case NotifyWrite:
1256         case ConstantStoragePointer:
1257         case MovHint:
1258         case ZombieHint:
1259         case ExitOK:
1260         case LoadVarargs:
1261         case ForwardVarargs:
1262         case PutDynamicVar:
1263         case NukeStructureAndSetButterfly:
1264         case InitializeEntrypointArguments:
1265         case WeakSetAdd:
1266         case WeakMapSet:
1267         case FilterCallLinkStatus:
1268         case FilterGetByIdStatus:
1269         case FilterPutByIdStatus:
1270         case FilterInByIdStatus:
1271         case ClearCatchLocals:
1272         case DataViewSet:
1273         case InvalidationPoint:
1274             break;
1275             
1276         // This gets ignored because it only pretends to produce a value.
1277         case BottomValue:
1278             break;
1279             
1280         // This gets ignored because it already has a prediction.
1281         case ExtractOSREntryLocal:
1282             break;
1283             
1284         // These gets ignored because it doesn't do anything.
1285         case CountExecution:
1286         case SuperSamplerBegin:
1287         case SuperSamplerEnd:
1288         case PhantomLocal:
1289         case Flush:
1290             break;
1291             
1292         case LastNodeType:
1293             RELEASE_ASSERT_NOT_REACHED();
1294             break;
1295 #else
1296         default:
1297             break;
1298 #endif
1299         }
1300     }
1301
1302     SpeculatedType resultOfToPrimitive(SpeculatedType type)
1303     {
1304         if (type & SpecObject) {
1305             // We try to be optimistic here about StringObjects since it's unlikely that
1306             // someone overrides the valueOf or toString methods.
1307             if (type & SpecStringObject && m_graph.canOptimizeStringObjectAccess(m_currentNode->origin.semantic))
1308                 return mergeSpeculations(type & ~SpecObject, SpecString);
1309
1310             return mergeSpeculations(type & ~SpecObject, SpecPrimitive);
1311         }
1312
1313         return type;
1314     }
1315
1316     Vector<Node*> m_dependentNodes;
1317     Node* m_currentNode;
1318     bool m_changed { false };
1319     PredictionPass m_pass { PrimaryPass }; // We use different logic for considering predictions depending on how far along we are in propagation.
1320 };
1321
1322 } // Anonymous namespace.
1323     
1324 bool performPredictionPropagation(Graph& graph)
1325 {
1326     return runPhase<PredictionPropagationPhase>(graph);
1327 }
1328
1329 } } // namespace JSC::DFG
1330
1331 #endif // ENABLE(DFG_JIT)
1332