c041361732663c8fc9034174d71965b43b6799ce
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGPredictionPropagationPhase.cpp
1 /*
2  * Copyright (C) 2011, 2012, 2013 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 "Operations.h"
34
35 namespace JSC { namespace DFG {
36
37 class PredictionPropagationPhase : public Phase {
38 public:
39     PredictionPropagationPhase(Graph& graph)
40         : Phase(graph, "prediction propagation")
41     {
42     }
43     
44     bool run()
45     {
46         ASSERT(m_graph.m_form == ThreadedCPS);
47         ASSERT(m_graph.m_unificationState == GloballyUnified);
48         
49 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
50         m_count = 0;
51 #endif
52         // 1) propagate predictions
53
54         do {
55             m_changed = false;
56             
57             // Forward propagation is near-optimal for both topologically-sorted and
58             // DFS-sorted code.
59             propagateForward();
60             if (!m_changed)
61                 break;
62             
63             // Backward propagation reduces the likelihood that pathological code will
64             // cause slowness. Loops (especially nested ones) resemble backward flow.
65             // This pass captures two cases: (1) it detects if the forward fixpoint
66             // found a sound solution and (2) short-circuits backward flow.
67             m_changed = false;
68             propagateBackward();
69         } while (m_changed);
70         
71         // 2) repropagate predictions while doing double voting.
72
73         do {
74             m_changed = false;
75             doRoundOfDoubleVoting();
76             propagateForward();
77             if (!m_changed)
78                 break;
79             
80             m_changed = false;
81             doRoundOfDoubleVoting();
82             propagateBackward();
83         } while (m_changed);
84         
85         return true;
86     }
87     
88 private:
89     bool setPrediction(SpeculatedType prediction)
90     {
91         ASSERT(m_currentNode->hasResult());
92         
93         // setPrediction() is used when we know that there is no way that we can change
94         // our minds about what the prediction is going to be. There is no semantic
95         // difference between setPrediction() and mergeSpeculation() other than the
96         // increased checking to validate this property.
97         ASSERT(m_currentNode->prediction() == SpecNone || m_currentNode->prediction() == prediction);
98         
99         return m_currentNode->predict(prediction);
100     }
101     
102     bool mergePrediction(SpeculatedType prediction)
103     {
104         ASSERT(m_currentNode->hasResult());
105         
106         return m_currentNode->predict(prediction);
107     }
108     
109     SpeculatedType speculatedDoubleTypeForPrediction(SpeculatedType value)
110     {
111         if (!isNumberSpeculation(value))
112             return SpecDouble;
113         if (value & SpecDoubleNaN)
114             return SpecDouble;
115         return SpecDoubleReal;
116     }
117
118     SpeculatedType speculatedDoubleTypeForPredictions(SpeculatedType left, SpeculatedType right)
119     {
120         return speculatedDoubleTypeForPrediction(mergeSpeculations(left, right));
121     }
122
123     void propagate(Node* node)
124     {
125         NodeType op = node->op();
126
127 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
128         dataLog("   ", Graph::opName(op), " ", m_currentNode, ": ", NodeFlagsDump(node->flags()), " ");
129 #endif
130         
131         bool changed = false;
132         
133         switch (op) {
134         case JSConstant:
135         case WeakJSConstant: {
136             changed |= setPrediction(speculationFromValue(m_graph.valueOfJSConstant(node)));
137             break;
138         }
139             
140         case GetLocal: {
141             VariableAccessData* variableAccessData = node->variableAccessData();
142             SpeculatedType prediction = variableAccessData->prediction();
143             if (prediction)
144                 changed |= mergePrediction(prediction);
145             break;
146         }
147             
148         case SetLocal: {
149             VariableAccessData* variableAccessData = node->variableAccessData();
150             changed |= variableAccessData->predict(node->child1()->prediction());
151             break;
152         }
153             
154         case BitAnd:
155         case BitOr:
156         case BitXor:
157         case BitRShift:
158         case BitLShift:
159         case BitURShift: {
160             changed |= setPrediction(SpecInt32);
161             break;
162         }
163             
164         case ValueToInt32: {
165             changed |= setPrediction(SpecInt32);
166             break;
167         }
168             
169         case ArrayPop:
170         case ArrayPush:
171         case RegExpExec:
172         case RegExpTest:
173         case GetById:
174         case GetByIdFlush:
175         case GetMyArgumentByValSafe:
176         case GetByOffset:
177         case Call:
178         case Construct:
179         case GetGlobalVar:
180         case GetScopedVar:
181         case Resolve:
182         case ResolveBase:
183         case ResolveBaseStrictPut:
184         case ResolveGlobal: {
185             changed |= setPrediction(node->getHeapPrediction());
186             break;
187         }
188
189         case StringCharCodeAt: {
190             changed |= setPrediction(SpecInt32);
191             break;
192         }
193
194         case UInt32ToNumber: {
195             if (nodeCanSpeculateInteger(node->arithNodeFlags()))
196                 changed |= mergePrediction(SpecInt32);
197             else
198                 changed |= mergePrediction(SpecNumber);
199             break;
200         }
201
202         case ValueAdd: {
203             SpeculatedType left = node->child1()->prediction();
204             SpeculatedType right = node->child2()->prediction();
205             
206             if (left && right) {
207                 if (isNumberSpeculationExpectingDefined(left) && isNumberSpeculationExpectingDefined(right)) {
208                     if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
209                         changed |= mergePrediction(SpecInt32);
210                     else
211                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
212                 } else if (!(left & SpecNumber) || !(right & SpecNumber)) {
213                     // left or right is definitely something other than a number.
214                     changed |= mergePrediction(SpecString);
215                 } else
216                     changed |= mergePrediction(SpecString | SpecInt32 | SpecDouble);
217             }
218             break;
219         }
220             
221         case ArithAdd: {
222             SpeculatedType left = node->child1()->prediction();
223             SpeculatedType right = node->child2()->prediction();
224             
225             if (left && right) {
226                 if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
227                     changed |= mergePrediction(SpecInt32);
228                 else
229                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
230             }
231             break;
232         }
233             
234         case ArithSub: {
235             SpeculatedType left = node->child1()->prediction();
236             SpeculatedType right = node->child2()->prediction();
237             
238             if (left && right) {
239                 if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
240                     changed |= mergePrediction(SpecInt32);
241                 else
242                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
243             }
244             break;
245         }
246             
247         case ArithNegate:
248             if (node->child1()->prediction()) {
249                 if (m_graph.negateShouldSpeculateInteger(node))
250                     changed |= mergePrediction(SpecInt32);
251                 else
252                     changed |= mergePrediction(speculatedDoubleTypeForPrediction(node->child1()->prediction()));
253             }
254             break;
255             
256         case ArithMin:
257         case ArithMax: {
258             SpeculatedType left = node->child1()->prediction();
259             SpeculatedType right = node->child2()->prediction();
260             
261             if (left && right) {
262                 if (Node::shouldSpeculateIntegerForArithmetic(node->child1().node(), node->child2().node())
263                     && nodeCanSpeculateInteger(node->arithNodeFlags()))
264                     changed |= mergePrediction(SpecInt32);
265                 else
266                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
267             }
268             break;
269         }
270
271         case ArithMul: {
272             SpeculatedType left = node->child1()->prediction();
273             SpeculatedType right = node->child2()->prediction();
274             
275             if (left && right) {
276                 if (m_graph.mulShouldSpeculateInteger(node))
277                     changed |= mergePrediction(SpecInt32);
278                 else
279                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
280             }
281             break;
282         }
283             
284         case ArithDiv: {
285             SpeculatedType left = node->child1()->prediction();
286             SpeculatedType right = node->child2()->prediction();
287             
288             if (left && right) {
289                 if (Node::shouldSpeculateIntegerForArithmetic(node->child1().node(), node->child2().node())
290                     && nodeCanSpeculateInteger(node->arithNodeFlags()))
291                     changed |= mergePrediction(SpecInt32);
292                 else
293                     changed |= mergePrediction(SpecDouble);
294             }
295             break;
296         }
297             
298         case ArithMod: {
299             SpeculatedType left = node->child1()->prediction();
300             SpeculatedType right = node->child2()->prediction();
301             
302             if (left && right) {
303                 if (Node::shouldSpeculateIntegerForArithmetic(node->child1().node(), node->child2().node())
304                     && nodeCanSpeculateInteger(node->arithNodeFlags()))
305                     changed |= mergePrediction(SpecInt32);
306                 else
307                     changed |= mergePrediction(SpecDouble);
308             }
309             break;
310         }
311             
312         case ArithSqrt: {
313             changed |= setPrediction(SpecDouble);
314             break;
315         }
316             
317         case ArithAbs: {
318             SpeculatedType child = node->child1()->prediction();
319             if (isInt32SpeculationForArithmetic(child)
320                 && nodeCanSpeculateInteger(node->arithNodeFlags()))
321                 changed |= mergePrediction(SpecInt32);
322             else
323                 changed |= mergePrediction(speculatedDoubleTypeForPrediction(child));
324             break;
325         }
326             
327         case LogicalNot:
328         case CompareLess:
329         case CompareLessEq:
330         case CompareGreater:
331         case CompareGreaterEq:
332         case CompareEq:
333         case CompareEqConstant:
334         case CompareStrictEq:
335         case CompareStrictEqConstant:
336         case InstanceOf:
337         case IsUndefined:
338         case IsBoolean:
339         case IsNumber:
340         case IsString:
341         case IsObject:
342         case IsFunction: {
343             changed |= setPrediction(SpecBoolean);
344             break;
345         }
346
347         case TypeOf: {
348             changed |= setPrediction(SpecString);
349             break;
350         }
351
352         case GetByVal: {
353             if (node->child1()->shouldSpeculateFloat32Array()
354                 || node->child1()->shouldSpeculateFloat64Array())
355                 changed |= mergePrediction(SpecDouble);
356             else
357                 changed |= mergePrediction(node->getHeapPrediction());
358             break;
359         }
360             
361         case GetMyArgumentsLengthSafe: {
362             changed |= setPrediction(SpecInt32);
363             break;
364         }
365
366         case GetScopeRegisters:            
367         case GetButterfly: 
368         case GetIndexedPropertyStorage:
369         case AllocatePropertyStorage:
370         case ReallocatePropertyStorage: {
371             changed |= setPrediction(SpecOther);
372             break;
373         }
374
375         case ConvertThis: {
376             SpeculatedType prediction = node->child1()->prediction();
377             if (prediction) {
378                 if (prediction & ~SpecObject) {
379                     prediction &= SpecObject;
380                     prediction = mergeSpeculations(prediction, SpecObjectOther);
381                 }
382                 changed |= mergePrediction(prediction);
383             }
384             break;
385         }
386             
387         case GetMyScope:
388         case SkipTopScope:
389         case SkipScope: {
390             changed |= setPrediction(SpecCellOther);
391             break;
392         }
393             
394         case GetCallee: {
395             changed |= setPrediction(SpecFunction);
396             break;
397         }
398             
399         case CreateThis:
400         case NewObject: {
401             changed |= setPrediction(SpecFinalObject);
402             break;
403         }
404             
405         case NewArray:
406         case NewArrayWithSize:
407         case NewArrayBuffer: {
408             changed |= setPrediction(SpecArray);
409             break;
410         }
411             
412         case NewRegexp:
413         case CreateActivation: {
414             changed |= setPrediction(SpecObjectOther);
415             break;
416         }
417         
418         case StringCharAt:
419         case StrCat: {
420             changed |= setPrediction(SpecString);
421             break;
422         }
423             
424         case ToPrimitive: {
425             SpeculatedType child = node->child1()->prediction();
426             if (child) {
427                 if (isObjectSpeculation(child)) {
428                     // I'd love to fold this case into the case below, but I can't, because
429                     // removing SpecObject from something that only has an object
430                     // prediction and nothing else means we have an ill-formed SpeculatedType
431                     // (strong predict-none). This should be killed once we remove all traces
432                     // of static (aka weak) predictions.
433                     changed |= mergePrediction(SpecString);
434                 } else if (child & SpecObject) {
435                     // Objects get turned into strings. So if the input has hints of objectness,
436                     // the output will have hinsts of stringiness.
437                     changed |= mergePrediction(
438                         mergeSpeculations(child & ~SpecObject, SpecString));
439                 } else
440                     changed |= mergePrediction(child);
441             }
442             break;
443         }
444             
445         case CreateArguments: {
446             changed |= setPrediction(SpecArguments);
447             break;
448         }
449             
450         case NewFunction:
451         case NewFunctionNoCheck:
452         case NewFunctionExpression: {
453             changed |= setPrediction(SpecFunction);
454             break;
455         }
456             
457         case PutByValAlias:
458         case GetArrayLength:
459         case Int32ToDouble:
460         case ForwardInt32ToDouble:
461         case DoubleAsInt32:
462         case GetLocalUnlinked:
463         case GetMyArgumentsLength:
464         case GetMyArgumentByVal:
465         case PhantomPutStructure:
466         case PhantomArguments:
467         case CheckArray:
468         case Arrayify:
469         case ArrayifyToStructure:
470         case Identity:
471         case MovHint:
472         case MovHintAndCheck:
473         case ZombieHint: {
474             // This node should never be visible at this stage of compilation. It is
475             // inserted by fixup(), which follows this phase.
476             CRASH();
477             break;
478         }
479         
480         case Phi:
481             // Phis should not be visible here since we're iterating the all-but-Phi's
482             // part of basic blocks.
483             CRASH();
484             break;
485
486         case GetScope:
487             changed |= setPrediction(SpecCellOther);
488             break;
489
490 #ifndef NDEBUG
491         // These get ignored because they don't return anything.
492         case PutByVal:
493         case PutScopedVar:
494         case Return:
495         case Throw:
496         case PutById:
497         case PutByIdDirect:
498         case PutByOffset:
499         case SetCallee:
500         case SetMyScope:
501         case DFG::Jump:
502         case Branch:
503         case Breakpoint:
504         case CheckHasInstance:
505         case ThrowReferenceError:
506         case ForceOSRExit:
507         case SetArgument:
508         case CheckStructure:
509         case CheckExecutable:
510         case ForwardCheckStructure:
511         case StructureTransitionWatchpoint:
512         case ForwardStructureTransitionWatchpoint:
513         case CheckFunction:
514         case PutStructure:
515         case TearOffActivation:
516         case TearOffArguments:
517         case CheckArgumentsNotCreated:
518         case GlobalVarWatchpoint:
519         case GarbageValue:
520         case AllocationProfileWatchpoint:
521         case Phantom:
522         case PutGlobalVar:
523         case PutGlobalVarCheck:
524             break;
525             
526         // These gets ignored because it doesn't do anything.
527         case InlineStart:
528         case Nop:
529         case CountExecution:
530         case PhantomLocal:
531         case Flush:
532             break;
533             
534         case LastNodeType:
535             CRASH();
536             break;
537 #else
538         default:
539             break;
540 #endif
541         }
542
543 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
544         dataLog(SpeculationDump(node->prediction()), "\n");
545 #endif
546         
547         m_changed |= changed;
548     }
549         
550     void propagateForward()
551     {
552 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
553         dataLogF("Propagating predictions forward [%u]\n", ++m_count);
554 #endif
555         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
556             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
557             if (!block)
558                 continue;
559             ASSERT(block->isReachable);
560             for (unsigned i = 0; i < block->size(); ++i) {
561                 m_currentNode = block->at(i);
562                 propagate(m_currentNode);
563             }
564         }
565     }
566     
567     void propagateBackward()
568     {
569 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
570         dataLogF("Propagating predictions backward [%u]\n", ++m_count);
571 #endif
572         for (BlockIndex blockIndex = m_graph.m_blocks.size(); blockIndex--;) {
573             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
574             if (!block)
575                 continue;
576             ASSERT(block->isReachable);
577             for (unsigned i = block->size(); i--;) {
578                 m_currentNode = block->at(i);
579                 propagate(m_currentNode);
580             }
581         }
582     }
583     
584     void doDoubleVoting(Node* node)
585     {
586         switch (node->op()) {
587         case ValueAdd:
588         case ArithAdd:
589         case ArithSub: {
590             SpeculatedType left = node->child1()->prediction();
591             SpeculatedType right = node->child2()->prediction();
592                 
593             DoubleBallot ballot;
594                 
595             if (isNumberSpeculationExpectingDefined(left) && isNumberSpeculationExpectingDefined(right)
596                 && !m_graph.addShouldSpeculateInteger(node))
597                 ballot = VoteDouble;
598             else
599                 ballot = VoteValue;
600                 
601             m_graph.voteNode(node->child1(), ballot);
602             m_graph.voteNode(node->child2(), ballot);
603             break;
604         }
605                 
606         case ArithMul: {
607             SpeculatedType left = node->child1()->prediction();
608             SpeculatedType right = node->child2()->prediction();
609                 
610             DoubleBallot ballot;
611                 
612             if (isNumberSpeculation(left) && isNumberSpeculation(right)
613                 && !m_graph.mulShouldSpeculateInteger(node))
614                 ballot = VoteDouble;
615             else
616                 ballot = VoteValue;
617                 
618             m_graph.voteNode(node->child1(), ballot);
619             m_graph.voteNode(node->child2(), ballot);
620             break;
621         }
622
623         case ArithMin:
624         case ArithMax:
625         case ArithMod:
626         case ArithDiv: {
627             SpeculatedType left = node->child1()->prediction();
628             SpeculatedType right = node->child2()->prediction();
629                 
630             DoubleBallot ballot;
631                 
632             if (isNumberSpeculation(left) && isNumberSpeculation(right)
633                 && !(Node::shouldSpeculateIntegerForArithmetic(node->child1().node(), node->child2().node()) && node->canSpeculateInteger()))
634                 ballot = VoteDouble;
635             else
636                 ballot = VoteValue;
637                 
638             m_graph.voteNode(node->child1(), ballot);
639             m_graph.voteNode(node->child2(), ballot);
640             break;
641         }
642                 
643         case ArithAbs:
644             DoubleBallot ballot;
645             if (!(node->child1()->shouldSpeculateIntegerForArithmetic() && node->canSpeculateInteger()))
646                 ballot = VoteDouble;
647             else
648                 ballot = VoteValue;
649                 
650             m_graph.voteNode(node->child1(), ballot);
651             break;
652                 
653         case ArithSqrt:
654             m_graph.voteNode(node->child1(), VoteDouble);
655             break;
656                 
657         case SetLocal: {
658             SpeculatedType prediction = node->child1()->prediction();
659             if (isDoubleSpeculation(prediction))
660                 node->variableAccessData()->vote(VoteDouble);
661             else if (!isNumberSpeculation(prediction) || isInt32Speculation(prediction))
662                 node->variableAccessData()->vote(VoteValue);
663             break;
664         }
665                 
666         case PutByVal:
667         case PutByValAlias: {
668             Edge child1 = m_graph.varArgChild(node, 0);
669             Edge child2 = m_graph.varArgChild(node, 1);
670             Edge child3 = m_graph.varArgChild(node, 2);
671             m_graph.voteNode(child1, VoteValue);
672             m_graph.voteNode(child2, VoteValue);
673             switch (node->arrayMode().type()) {
674             case Array::Double:
675                 m_graph.voteNode(child3, VoteDouble);
676                 break;
677             default:
678                 m_graph.voteNode(child3, VoteValue);
679                 break;
680             }
681             break;
682         }
683             
684         default:
685             m_graph.voteChildren(node, VoteValue);
686             break;
687         }
688     }
689     
690     void doRoundOfDoubleVoting()
691     {
692 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
693         dataLogF("Voting on double uses of locals [%u]\n", m_count);
694 #endif
695         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
696             m_graph.m_variableAccessData[i].find()->clearVotes();
697         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
698             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
699             if (!block)
700                 continue;
701             ASSERT(block->isReachable);
702             for (unsigned i = 0; i < block->size(); ++i) {
703                 m_currentNode = block->at(i);
704                 doDoubleVoting(m_currentNode);
705             }
706         }
707         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
708             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
709             if (!variableAccessData->isRoot())
710                 continue;
711             m_changed |= variableAccessData->tallyVotesForShouldUseDoubleFormat();
712         }
713         for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
714             m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
715         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
716             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
717             if (!variableAccessData->isRoot())
718                 continue;
719             m_changed |= variableAccessData->makePredictionForDoubleFormat();
720         }
721     }
722     
723     Node* m_currentNode;
724     bool m_changed;
725
726 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
727     unsigned m_count;
728 #endif
729 };
730     
731 bool performPredictionPropagation(Graph& graph)
732 {
733     SamplingRegion samplingRegion("DFG Prediction Propagation Phase");
734     return runPhase<PredictionPropagationPhase>(graph);
735 }
736
737 } } // namespace JSC::DFG
738
739 #endif // ENABLE(DFG_JIT)
740