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