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