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