DFG should inline Array.push and Array.pop
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGPropagator.cpp
1 /*
2  * Copyright (C) 2011 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 "DFGPropagator.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32 #include "DFGScoreBoard.h"
33 #include <wtf/FixedArray.h>
34
35 namespace JSC { namespace DFG {
36
37 class Propagator {
38 public:
39     Propagator(Graph& graph, JSGlobalData& globalData, CodeBlock* codeBlock, CodeBlock* profiledBlock)
40         : m_graph(graph)
41         , m_globalData(globalData)
42         , m_codeBlock(codeBlock)
43         , m_profiledBlock(profiledBlock)
44     {
45         // Replacements are used to implement local common subexpression elimination.
46         m_replacements.resize(m_graph.size());
47         
48         for (unsigned i = 0; i < m_graph.size(); ++i)
49             m_replacements[i] = NoNode;
50         
51         for (unsigned i = 0; i < LastNodeId; ++i)
52             m_lastSeen[i] = NoNode;
53     }
54     
55     void fixpoint()
56     {
57 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
58     m_graph.dump(m_codeBlock);
59 #endif
60
61 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
62         m_count = 0;
63 #endif
64         do {
65             m_changed = false;
66             
67             // Up here we start with a backward pass because we suspect that to be
68             // more profitable.
69             propagateArithNodeFlagsBackward();
70             if (!m_changed)
71                 break;
72             
73             m_changed = false;
74             propagateArithNodeFlagsForward();
75         } while (m_changed);
76         
77 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
78         m_count = 0;
79 #endif
80         do {
81             m_changed = false;
82             
83             // Forward propagation is near-optimal for both topologically-sorted and
84             // DFS-sorted code.
85             propagatePredictionsForward();
86             if (!m_changed)
87                 break;
88             
89             // Backward propagation reduces the likelihood that pathological code will
90             // cause slowness. Loops (especially nested ones) resemble backward flow.
91             // This pass captures two cases: (1) it detects if the forward fixpoint
92             // found a sound solution and (2) short-circuits backward flow.
93             m_changed = false;
94             propagatePredictionsBackward();
95         } while (m_changed);
96         
97         fixup();
98         
99 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
100         printf("Graph after propagation fixup:\n");
101         m_graph.dump(m_codeBlock);
102 #endif
103
104         localCSE();
105
106 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
107         printf("Graph after CSE:\n");
108         m_graph.dump(m_codeBlock);
109 #endif
110
111         allocateVirtualRegisters();
112
113 #if ENABLE(DFG_DEBUG_VERBOSE)
114         printf("Graph after propagation:\n");
115         m_graph.dump(m_codeBlock);
116 #endif
117     }
118     
119 private:
120     bool isNotNegZero(NodeIndex nodeIndex)
121     {
122         if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
123             return false;
124         double value = m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
125         return !value && 1.0 / value < 0.0;
126     }
127     
128     bool isNotZero(NodeIndex nodeIndex)
129     {
130         if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
131             return false;
132         return !!m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
133     }
134     
135     void propagateArithNodeFlags(Node& node)
136     {
137         if (!node.shouldGenerate())
138             return;
139         
140         NodeType op = node.op;
141         ArithNodeFlags flags = 0;
142         
143         if (node.hasArithNodeFlags())
144             flags = node.rawArithNodeFlags();
145         
146 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
147         printf("   %s @%u: %s ", Graph::opName(op), m_compileIndex, arithNodeFlagsAsString(flags));
148 #endif
149         
150         flags &= NodeUsedAsMask;
151         
152         bool changed = false;
153         
154         switch (op) {
155         case ValueToInt32:
156         case BitAnd:
157         case BitOr:
158         case BitXor:
159         case BitLShift:
160         case BitRShift:
161         case BitURShift: {
162             // These operations are perfectly happy with truncated integers,
163             // so we don't want to propagate anything.
164             break;
165         }
166             
167         case ValueToNumber:
168         case ValueToDouble:
169         case UInt32ToNumber: {
170             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
171             break;
172         }
173             
174         case ArithAdd:
175         case ValueAdd: {
176             if (isNotNegZero(node.child1()) || isNotNegZero(node.child2()))
177                 flags &= ~NodeNeedsNegZero;
178             
179             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
180             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
181             break;
182         }
183             
184         case ArithSub: {
185             if (isNotZero(node.child1()) || isNotZero(node.child2()))
186                 flags &= ~NodeNeedsNegZero;
187             
188             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
189             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
190             break;
191         }
192             
193         case ArithMul:
194         case ArithDiv: {
195             // As soon as a multiply happens, we can easily end up in the part
196             // of the double domain where the point at which you do truncation
197             // can change the outcome. So, ArithMul always checks for overflow
198             // no matter what, and always forces its inputs to check as well.
199             
200             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
201             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
202             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
203             break;
204         }
205             
206         case ArithMin:
207         case ArithMax: {
208             flags |= NodeUsedAsNumber;
209             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
210             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
211             break;
212         }
213             
214         case ArithAbs: {
215             flags &= ~NodeNeedsNegZero;
216             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
217             break;
218         }
219             
220         case PutByVal: {
221             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
222             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
223             changed |= m_graph[node.child3()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
224             break;
225         }
226             
227         case GetByVal: {
228             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
229             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
230             break;
231         }
232             
233         default:
234             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
235             if (op & NodeHasVarArgs) {
236                 for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
237                     changed |= m_graph[m_graph.m_varArgChildren[childIdx]].mergeArithNodeFlags(flags);
238             } else {
239                 if (node.child1() == NoNode)
240                     break;
241                 changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
242                 if (node.child2() == NoNode)
243                     break;
244                 changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
245                 if (node.child3() == NoNode)
246                     break;
247                 changed |= m_graph[node.child3()].mergeArithNodeFlags(flags);
248             }
249             break;
250         }
251
252 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
253         printf("%s\n", changed ? "CHANGED" : "");
254 #endif
255         
256         m_changed |= changed;
257     }
258     
259     void propagateArithNodeFlagsForward()
260     {
261 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
262         printf("Propagating arithmetic node flags forward [%u]\n", ++m_count);
263 #endif
264         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
265             propagateArithNodeFlags(m_graph[m_compileIndex]);
266     }
267     
268     void propagateArithNodeFlagsBackward()
269     {
270 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
271         printf("Propagating arithmetic node flags backward [%u]\n", ++m_count);
272 #endif
273         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
274             propagateArithNodeFlags(m_graph[m_compileIndex]);
275     }
276     
277     bool setPrediction(PredictedType prediction)
278     {
279         ASSERT(m_graph[m_compileIndex].hasResult());
280         
281         // setPrediction() is used when we know that there is no way that we can change
282         // our minds about what the prediction is going to be. There is no semantic
283         // difference between setPrediction() and mergePrediction() other than the
284         // increased checking to validate this property.
285         ASSERT(m_graph[m_compileIndex].prediction() == PredictNone || m_graph[m_compileIndex].prediction() == prediction);
286         
287         return m_graph[m_compileIndex].predict(prediction);
288     }
289     
290     bool mergePrediction(PredictedType prediction)
291     {
292         ASSERT(m_graph[m_compileIndex].hasResult());
293         
294         return m_graph[m_compileIndex].predict(prediction);
295     }
296     
297     void propagateNodePredictions(Node& node)
298     {
299         if (!node.shouldGenerate())
300             return;
301         
302         NodeType op = node.op;
303
304 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
305         printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
306 #endif
307         
308         bool changed = false;
309         
310         switch (op) {
311         case JSConstant: {
312             changed |= setPrediction(predictionFromValue(m_graph.valueOfJSConstant(m_codeBlock, m_compileIndex)));
313             break;
314         }
315             
316         case GetLocal: {
317             PredictedType prediction = node.variableAccessData()->prediction();
318             if (prediction)
319                 changed |= mergePrediction(prediction);
320             break;
321         }
322             
323         case SetLocal: {
324             changed |= node.variableAccessData()->predict(m_graph[node.child1()].prediction());
325             break;
326         }
327             
328         case BitAnd:
329         case BitOr:
330         case BitXor:
331         case BitRShift:
332         case BitLShift:
333         case BitURShift:
334         case ValueToInt32: {
335             changed |= setPrediction(PredictInt32);
336             break;
337         }
338             
339         case ArrayPop:
340         case ArrayPush: {
341             if (node.getHeapPrediction())
342                 changed |= mergePrediction(node.getHeapPrediction());
343             break;
344         }
345             
346         case ArithMod: {
347             PredictedType left = m_graph[node.child1()].prediction();
348             PredictedType right = m_graph[node.child2()].prediction();
349             
350             if (left && right) {
351                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
352                     changed |= mergePrediction(PredictInt32);
353                 else
354                     changed |= mergePrediction(PredictDouble);
355             }
356             break;
357         }
358             
359         case UInt32ToNumber: {
360             if (nodeCanSpeculateInteger(node.arithNodeFlags()))
361                 changed |= setPrediction(PredictInt32);
362             else
363                 changed |= setPrediction(PredictNumber);
364             break;
365         }
366
367         case ValueToNumber: {
368             PredictedType prediction = m_graph[node.child1()].prediction();
369             
370             if (prediction) {
371                 if (!(prediction & PredictDouble) && nodeCanSpeculateInteger(node.arithNodeFlags()))
372                     changed |= mergePrediction(PredictInt32);
373                 else
374                     changed |= mergePrediction(PredictNumber);
375             }
376             
377             break;
378         }
379
380         case ValueAdd: {
381             PredictedType left = m_graph[node.child1()].prediction();
382             PredictedType right = m_graph[node.child2()].prediction();
383             
384             if (left && right) {
385                 if (isNumberPrediction(left) && isNumberPrediction(right)) {
386                     if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
387                         changed |= mergePrediction(PredictInt32);
388                     else
389                         changed |= mergePrediction(PredictDouble);
390                 } else if (!(left & PredictNumber) || !(right & PredictNumber)) {
391                     // left or right is definitely something other than a number.
392                     changed |= mergePrediction(PredictString);
393                 } else
394                     changed |= mergePrediction(PredictString | PredictInt32 | PredictDouble);
395             }
396             break;
397         }
398             
399         case ArithAdd:
400         case ArithSub:
401         case ArithMul:
402         case ArithMin:
403         case ArithMax:
404         case ArithDiv: {
405             PredictedType left = m_graph[node.child1()].prediction();
406             PredictedType right = m_graph[node.child2()].prediction();
407             
408             if (left && right) {
409                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
410                     changed |= mergePrediction(PredictInt32);
411                 else
412                     changed |= mergePrediction(PredictDouble);
413             }
414             break;
415         }
416             
417         case ArithSqrt: {
418             changed |= setPrediction(PredictDouble);
419             break;
420         }
421             
422         case ArithAbs: {
423             PredictedType child = m_graph[node.child1()].prediction();
424             if (child) {
425                 if (nodeCanSpeculateInteger(node.arithNodeFlags()))
426                     changed |= mergePrediction(child);
427                 else
428                     changed |= setPrediction(PredictDouble);
429             }
430             break;
431         }
432             
433         case LogicalNot:
434         case CompareLess:
435         case CompareLessEq:
436         case CompareGreater:
437         case CompareGreaterEq:
438         case CompareEq:
439         case CompareStrictEq:
440         case InstanceOf: {
441             changed |= setPrediction(PredictBoolean);
442             break;
443         }
444             
445         case GetById:
446         case GetMethod:
447         case GetByVal: {
448             if (node.getHeapPrediction())
449                 changed |= mergePrediction(node.getHeapPrediction());
450             break;
451         }
452             
453         case GetPropertyStorage: {
454             changed |= setPrediction(PredictOther);
455             break;
456         }
457             
458         case GetByOffset: {
459             if (node.getHeapPrediction())
460                 changed |= mergePrediction(node.getHeapPrediction());
461             break;
462         }
463             
464         case CheckMethod: {
465             changed |= setPrediction(m_graph.getMethodCheckPrediction(node));
466             break;
467         }
468
469         case Call:
470         case Construct: {
471             if (node.getHeapPrediction())
472                 changed |= mergePrediction(node.getHeapPrediction());
473             break;
474         }
475             
476         case ConvertThis: {
477             PredictedType prediction = m_graph[node.child1()].prediction();
478             if (prediction) {
479                 if (prediction & ~PredictObjectMask) {
480                     prediction &= PredictObjectMask;
481                     prediction = mergePredictions(prediction, PredictObjectUnknown);
482                 }
483                 changed |= mergePrediction(prediction);
484             }
485             break;
486         }
487             
488         case GetGlobalVar: {
489             PredictedType prediction = m_graph.getGlobalVarPrediction(node.varNumber());
490             if (prediction)
491                 changed |= mergePrediction(prediction);
492             break;
493         }
494             
495         case PutGlobalVar: {
496             changed |= m_graph.predictGlobalVar(node.varNumber(), m_graph[node.child1()].prediction());
497             break;
498         }
499             
500         case GetScopedVar:
501         case Resolve:
502         case ResolveBase:
503         case ResolveBaseStrictPut:
504         case ResolveGlobal: {
505             PredictedType prediction = node.getHeapPrediction();
506             if (prediction)
507                 changed |= mergePrediction(prediction);
508             break;
509         }
510             
511         case GetScopeChain: {
512             changed |= setPrediction(PredictCellOther);
513             break;
514         }
515             
516         case GetCallee: {
517             changed |= setPrediction(PredictObjectOther);
518             break;
519         }
520             
521         case CreateThis:
522         case NewObject: {
523             changed |= setPrediction(PredictFinalObject);
524             break;
525         }
526             
527         case NewArray:
528         case NewArrayBuffer: {
529             changed |= setPrediction(PredictArray);
530             break;
531         }
532             
533         case NewRegexp: {
534             changed |= setPrediction(PredictObjectOther);
535             break;
536         }
537             
538         case StrCat: {
539             changed |= setPrediction(PredictString);
540             break;
541         }
542             
543         case ToPrimitive: {
544             PredictedType child = m_graph[node.child1()].prediction();
545             if (child) {
546                 if (isObjectPrediction(child)) {
547                     // I'd love to fold this case into the case below, but I can't, because
548                     // removing PredictObjectMask from something that only has an object
549                     // prediction and nothing else means we have an ill-formed PredictedType
550                     // (strong predict-none). This should be killed once we remove all traces
551                     // of static (aka weak) predictions.
552                     changed |= mergePrediction(PredictString);
553                 } else if (child & PredictObjectMask) {
554                     // Objects get turned into strings. So if the input has hints of objectness,
555                     // the output will have hinsts of stringiness.
556                     changed |= mergePrediction(mergePredictions(child & ~PredictObjectMask, PredictString));
557                 } else
558                     changed |= mergePrediction(child);
559             }
560             break;
561         }
562             
563         case ValueToDouble:
564         case GetArrayLength:
565         case GetStringLength: {
566             // This node should never be visible at this stage of compilation. It is
567             // inserted by fixup(), which follows this phase.
568             ASSERT_NOT_REACHED();
569             break;
570         }
571         
572 #ifndef NDEBUG
573         // These get ignored because they don't return anything.
574         case PutScopedVar:
575         case DFG::Jump:
576         case Branch:
577         case Breakpoint:
578         case Return:
579         case CheckHasInstance:
580         case Phi:
581         case Throw:
582         case ThrowReferenceError:
583         case ForceOSRExit:
584         case SetArgument:
585         case PutByVal:
586         case PutByValAlias:
587         case PutById:
588         case PutByIdDirect:
589         case CheckStructure:
590         case PutStructure:
591         case PutByOffset:
592             break;
593             
594         // This gets ignored because it doesn't do anything.
595         case Phantom:
596             break;
597 #else
598         default:
599             break;
600 #endif
601         }
602
603 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
604         printf("%s ", predictionToString(m_graph[m_compileIndex].prediction()));
605 #endif
606         
607         m_changed |= changed;
608     }
609     
610     void propagatePredictionsForward()
611     {
612 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
613         printf("Propagating predictions forward [%u]\n", ++m_count);
614 #endif
615         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
616             propagateNodePredictions(m_graph[m_compileIndex]);
617     }
618     
619     void propagatePredictionsBackward()
620     {
621 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
622         printf("Propagating predictions backward [%u]\n", ++m_count);
623 #endif
624         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
625             propagateNodePredictions(m_graph[m_compileIndex]);
626     }
627     
628     void toDouble(NodeIndex nodeIndex)
629     {
630         if (m_graph[nodeIndex].op == ValueToNumber) {
631 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
632             printf("  @%u -> ValueToDouble", nodeIndex);
633 #endif
634             m_graph[nodeIndex].op = ValueToDouble;
635         }
636     }
637     
638     void fixupNode(Node& node)
639     {
640         if (!node.shouldGenerate())
641             return;
642         
643         NodeType op = node.op;
644
645 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
646         printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
647 #endif
648         
649         switch (op) {
650         case ValueAdd: {
651             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
652                 toDouble(node.child1());
653                 toDouble(node.child2());
654                 break;
655             }
656             
657             PredictedType left = m_graph[node.child1()].prediction();
658             PredictedType right = m_graph[node.child2()].prediction();
659             
660             if (left && right && isNumberPrediction(left) && isNumberPrediction(right)) {
661                 if (left & PredictDouble)
662                     toDouble(node.child2());
663                 if (right & PredictDouble)
664                     toDouble(node.child1());
665             }
666             break;
667         }
668             
669         case ArithAdd:
670         case ArithSub:
671         case ArithMul:
672         case ArithMin:
673         case ArithMax:
674         case ArithMod:
675         case ArithDiv: {
676             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
677                 toDouble(node.child1());
678                 toDouble(node.child2());
679                 break;
680             }
681             
682             PredictedType left = m_graph[node.child1()].prediction();
683             PredictedType right = m_graph[node.child2()].prediction();
684             
685             if (left && right) {
686                 if (left & PredictDouble)
687                     toDouble(node.child2());
688                 if (right & PredictDouble)
689                     toDouble(node.child1());
690             }
691             break;
692         }
693             
694         case ArithAbs: {
695             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
696                 toDouble(node.child1());
697                 break;
698             }
699             
700             PredictedType prediction = m_graph[node.child1()].prediction();
701             if (prediction & PredictDouble)
702                 toDouble(node.child1());
703             break;
704         }
705             
706         case ArithSqrt: {
707             toDouble(node.child1());
708             break;
709         }
710             
711         case GetById: {
712             bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
713             bool isString = isStringPrediction(m_graph[node.child1()].prediction());
714             if (!isArray && !isString)
715                 break;
716             if (!isInt32Prediction(m_graph[m_compileIndex].prediction()))
717                 break;
718             if (m_codeBlock->identifier(node.identifierNumber()) != m_globalData.propertyNames->length)
719                 break;
720             
721 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
722             printf("  @%u -> %s", nodeIndex, isArray ? "GetArrayLength" : "GetStringLength");
723 #endif
724             node.op = isArray ? GetArrayLength : GetStringLength;
725             break;
726         }
727             
728         default:
729             break;
730         }
731
732 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
733         printf("\n");
734 #endif
735     }
736     
737     void fixup()
738     {
739 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
740         printf("Performing Fixup\n");
741 #endif
742         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
743             fixupNode(m_graph[m_compileIndex]);
744     }
745     
746     NodeIndex canonicalize(NodeIndex nodeIndex)
747     {
748         if (nodeIndex == NoNode)
749             return NoNode;
750         
751         if (m_graph[nodeIndex].op == ValueToNumber)
752             nodeIndex = m_graph[nodeIndex].child1();
753         
754         if (m_graph[nodeIndex].op == ValueToInt32)
755             nodeIndex = m_graph[nodeIndex].child1();
756         
757         return nodeIndex;
758     }
759     
760     // Computes where the search for a candidate for CSE should start. Don't call
761     // this directly; call startIndex() instead as it does logging in debug mode.
762     NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
763     {
764         const unsigned limit = 300;
765         
766         NodeIndex start = m_start;
767         if (m_compileIndex - start > limit)
768             start = m_compileIndex - limit;
769         
770         ASSERT(start >= m_start);
771         
772         NodeIndex child = canonicalize(child1);
773         if (child == NoNode)
774             return start;
775         
776         if (start < child)
777             start = child;
778         
779         child = canonicalize(child2);
780         if (child == NoNode)
781             return start;
782         
783         if (start < child)
784             start = child;
785         
786         child = canonicalize(child3);
787         if (child == NoNode)
788             return start;
789         
790         if (start < child)
791             start = child;
792         
793         return start;
794     }
795     
796     NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
797     {
798         NodeIndex result = computeStartIndexForChildren(child1, child2, child3);
799 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
800         printf("  lookback %u: ", result);
801 #endif
802         return result;
803     }
804     
805     NodeIndex startIndex()
806     {
807         Node& node = m_graph[m_compileIndex];
808         return startIndexForChildren(node.child1(), node.child2(), node.child3());
809     }
810     
811     NodeIndex endIndexForPureCSE()
812     {
813         NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask];
814         if (result == NoNode)
815             result = 0;
816         else
817             result++;
818         ASSERT(result <= m_compileIndex);
819 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
820         printf("  limit %u: ", result);
821 #endif
822         return result;
823     }
824     
825     NodeIndex pureCSE(Node& node)
826     {
827         NodeIndex child1 = canonicalize(node.child1());
828         NodeIndex child2 = canonicalize(node.child2());
829         NodeIndex child3 = canonicalize(node.child3());
830         
831         NodeIndex start = startIndex();
832         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
833             Node& otherNode = m_graph[index];
834             if (node.op != otherNode.op)
835                 continue;
836             
837             if (node.arithNodeFlagsForCompare() != otherNode.arithNodeFlagsForCompare())
838                 continue;
839             
840             NodeIndex otherChild = canonicalize(otherNode.child1());
841             if (otherChild == NoNode)
842                 return index;
843             if (otherChild != child1)
844                 continue;
845             
846             otherChild = canonicalize(otherNode.child2());
847             if (otherChild == NoNode)
848                 return index;
849             if (otherChild != child2)
850                 continue;
851             
852             otherChild = canonicalize(otherNode.child3());
853             if (otherChild == NoNode)
854                 return index;
855             if (otherChild != child3)
856                 continue;
857             
858             return index;
859         }
860         return NoNode;
861     }
862     
863     bool isPredictedNumerical(Node& node)
864     {
865         PredictedType left = m_graph[node.child1()].prediction();
866         PredictedType right = m_graph[node.child2()].prediction();
867         return isNumberPrediction(left) && isNumberPrediction(right);
868     }
869     
870     bool logicalNotIsPure(Node& node)
871     {
872         PredictedType prediction = m_graph[node.child1()].prediction();
873         return isBooleanPrediction(prediction) || !prediction;
874     }
875     
876     bool clobbersWorld(NodeIndex nodeIndex)
877     {
878         Node& node = m_graph[nodeIndex];
879         if (node.op & NodeClobbersWorld)
880             return true;
881         if (!(node.op & NodeMightClobber))
882             return false;
883         switch (node.op) {
884         case ValueAdd:
885         case CompareLess:
886         case CompareLessEq:
887         case CompareGreater:
888         case CompareGreaterEq:
889         case CompareEq:
890             return !isPredictedNumerical(node);
891         case LogicalNot:
892             return !logicalNotIsPure(node);
893         default:
894             ASSERT_NOT_REACHED();
895             return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
896         }
897     }
898     
899     NodeIndex impureCSE(Node& node)
900     {
901         NodeIndex child1 = canonicalize(node.child1());
902         NodeIndex child2 = canonicalize(node.child2());
903         NodeIndex child3 = canonicalize(node.child3());
904         
905         NodeIndex start = startIndex();
906         for (NodeIndex index = m_compileIndex; index-- > start;) {
907             Node& otherNode = m_graph[index];
908             if (node.op == otherNode.op
909                 && node.arithNodeFlagsForCompare() == otherNode.arithNodeFlagsForCompare()) {
910                 NodeIndex otherChild = canonicalize(otherNode.child1());
911                 if (otherChild == NoNode)
912                     return index;
913                 if (otherChild == child1) {
914                     otherChild = canonicalize(otherNode.child2());
915                     if (otherChild == NoNode)
916                         return index;
917                     if (otherChild == child2) {
918                         otherChild = canonicalize(otherNode.child3());
919                         if (otherChild == NoNode)
920                             return index;
921                         if (otherChild == child3)
922                             return index;
923                     }
924                 }
925             }
926             if (clobbersWorld(index))
927                 break;
928         }
929         return NoNode;
930     }
931     
932     NodeIndex globalVarLoadElimination(unsigned varNumber)
933     {
934         NodeIndex start = startIndexForChildren();
935         for (NodeIndex index = m_compileIndex; index-- > start;) {
936             Node& node = m_graph[index];
937             switch (node.op) {
938             case GetGlobalVar:
939                 if (node.varNumber() == varNumber)
940                     return index;
941                 break;
942             case PutGlobalVar:
943                 if (node.varNumber() == varNumber)
944                     return node.child1();
945                 break;
946             default:
947                 break;
948             }
949             if (clobbersWorld(index))
950                 break;
951         }
952         return NoNode;
953     }
954     
955     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
956     {
957         NodeIndex start = startIndexForChildren(child1, child2);
958         for (NodeIndex index = m_compileIndex; index-- > start;) {
959             Node& node = m_graph[index];
960             switch (node.op) {
961             case GetByVal:
962                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
963                     return index;
964                 break;
965             case PutByVal:
966                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
967                     return node.child3();
968                 break;
969             case PutStructure:
970             case PutByOffset:
971                 // GetByVal currently always speculates that it's accessing an
972                 // array with an integer index, which means that it's impossible
973                 // for a structure change or a put to property storage to affect
974                 // the GetByVal.
975                 break;
976             case ArrayPush:
977                 // A push cannot affect previously existing elements in the array.
978                 break;
979             default:
980                 if (clobbersWorld(index))
981                     return NoNode;
982                 break;
983             }
984         }
985         return NoNode;
986     }
987     
988     NodeIndex getMethodLoadElimination(const MethodCheckData& methodCheckData, unsigned identifierNumber, NodeIndex child1)
989     {
990         NodeIndex start = startIndexForChildren(child1);
991         for (NodeIndex index = m_compileIndex; index-- > start;) {
992             Node& node = m_graph[index];
993             switch (node.op) {
994             case CheckMethod:
995                 if (node.child1() == child1
996                     && node.identifierNumber() == identifierNumber
997                     && m_graph.m_methodCheckData[node.methodCheckDataIndex()] == methodCheckData)
998                     return index;
999                 break;
1000                 
1001             case PutByOffset:
1002                 // If a put was optimized to by-offset then it's not changing the structure
1003                 break;
1004                 
1005             case PutByVal:
1006             case PutByValAlias:
1007                 // PutByVal currently always speculates that it's accessing an array with an
1008                 // integer index, which means that it's impossible for it to cause a structure
1009                 // change.
1010                 break;
1011                 
1012             case ArrayPush:
1013             case ArrayPop:
1014                 // Pushing and popping cannot despecify a function.
1015                 break;
1016                 
1017             default:
1018                 if (clobbersWorld(index))
1019                     return NoNode;
1020                 break;
1021             }
1022         }
1023         return NoNode;
1024     }
1025     
1026     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
1027     {
1028         NodeIndex start = startIndexForChildren(child1);
1029         for (NodeIndex index = m_compileIndex; index-- > start;) {
1030             Node& node = m_graph[index];
1031             switch (node.op) {
1032             case CheckStructure:
1033                 if (node.child1() == child1
1034                     && structureSet.isSupersetOf(node.structureSet()))
1035                     return true;
1036                 break;
1037                 
1038             case PutStructure:
1039                 if (node.child1() == child1
1040                     && structureSet.contains(node.structureTransitionData().newStructure))
1041                     return true;
1042                 if (structureSet.contains(node.structureTransitionData().previousStructure))
1043                     return false;
1044                 break;
1045                 
1046             case PutByOffset:
1047                 // Setting a property cannot change the structure.
1048                 break;
1049                 
1050             case PutByVal:
1051             case PutByValAlias:
1052                 // PutByVal currently always speculates that it's accessing an array with an
1053                 // integer index, which means that it's impossible for it to cause a structure
1054                 // change.
1055                 break;
1056                 
1057             default:
1058                 if (clobbersWorld(index))
1059                     return false;
1060                 break;
1061             }
1062         }
1063         return false;
1064     }
1065     
1066     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
1067     {
1068         NodeIndex start = startIndexForChildren(child1);
1069         for (NodeIndex index = m_compileIndex; index-- > start;) {
1070             Node& node = m_graph[index];
1071             switch (node.op) {
1072             case GetByOffset:
1073                 if (node.child1() == child1
1074                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
1075                     return index;
1076                 break;
1077                 
1078             case PutByOffset:
1079                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
1080                     if (node.child2() == child1)
1081                         return node.child3();
1082                     return NoNode;
1083                 }
1084                 break;
1085                 
1086             case PutStructure:
1087                 // Changing the structure cannot change the outcome of a property get.
1088                 break;
1089                 
1090             case PutByVal:
1091             case PutByValAlias:
1092                 // PutByVal currently always speculates that it's accessing an array with an
1093                 // integer index, which means that it's impossible for it to cause a structure
1094                 // change.
1095                 break;
1096                 
1097             default:
1098                 if (clobbersWorld(index))
1099                     return NoNode;
1100                 break;
1101             }
1102         }
1103         return NoNode;
1104     }
1105     
1106     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
1107     {
1108         NodeIndex start = startIndexForChildren(child1);
1109         for (NodeIndex index = m_compileIndex; index-- > start;) {
1110             Node& node = m_graph[index];
1111             switch (node.op) {
1112             case GetPropertyStorage:
1113                 if (node.child1() == child1)
1114                     return index;
1115                 break;
1116                 
1117             case PutByOffset:
1118             case PutStructure:
1119                 // Changing the structure or putting to the storage cannot
1120                 // change the property storage pointer.
1121                 break;
1122                 
1123             case PutByVal:
1124             case PutByValAlias:
1125                 // PutByVal currently always speculates that it's accessing an array with an
1126                 // integer index, which means that it's impossible for it to cause a structure
1127                 // change.
1128                 break;
1129                 
1130             default:
1131                 if (clobbersWorld(index))
1132                     return NoNode;
1133                 break;
1134             }
1135         }
1136         return NoNode;
1137     }
1138     
1139     NodeIndex getScopeChainLoadElimination(unsigned depth)
1140     {
1141         NodeIndex start = startIndexForChildren();
1142         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
1143             Node& node = m_graph[index];
1144             if (node.op == GetScopeChain
1145                 && node.scopeChainDepth() == depth)
1146                 return index;
1147         }
1148         return NoNode;
1149     }
1150     
1151     void performSubstitution(NodeIndex& child)
1152     {
1153         // Check if this operand is actually unused.
1154         if (child == NoNode)
1155             return;
1156         
1157         // Check if there is any replacement.
1158         NodeIndex replacement = m_replacements[child];
1159         if (replacement == NoNode)
1160             return;
1161         
1162         child = replacement;
1163         
1164         // There is definitely a replacement. Assert that the replacement does not
1165         // have a replacement.
1166         ASSERT(m_replacements[child] == NoNode);
1167         
1168         m_graph[child].ref();
1169     }
1170     
1171     void setReplacement(NodeIndex replacement)
1172     {
1173         if (replacement == NoNode)
1174             return;
1175         
1176         // Be safe. Don't try to perform replacements if the predictions don't
1177         // agree.
1178         if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
1179             return;
1180         
1181 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1182         printf("   Replacing @%u -> @%u", m_compileIndex, replacement);
1183 #endif
1184         
1185         Node& node = m_graph[m_compileIndex];
1186         node.op = Phantom;
1187         node.setRefCount(1);
1188         
1189         // At this point we will eliminate all references to this node.
1190         m_replacements[m_compileIndex] = replacement;
1191     }
1192     
1193     void eliminate()
1194     {
1195 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1196         printf("   Eliminating @%u", m_compileIndex);
1197 #endif
1198         
1199         Node& node = m_graph[m_compileIndex];
1200         ASSERT(node.refCount() == 1);
1201         ASSERT(node.mustGenerate());
1202         node.op = Phantom;
1203     }
1204     
1205     void performNodeCSE(Node& node)
1206     {
1207         if (node.op & NodeHasVarArgs) {
1208             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1209                 performSubstitution(m_graph.m_varArgChildren[childIdx]);
1210         } else {
1211             performSubstitution(node.children.fixed.child1);
1212             performSubstitution(node.children.fixed.child2);
1213             performSubstitution(node.children.fixed.child3);
1214         }
1215         
1216         if (!node.shouldGenerate())
1217             return;
1218         
1219 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1220         printf("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op), m_compileIndex);
1221 #endif
1222         
1223         // NOTE: there are some nodes that we deliberately don't CSE even though we
1224         // probably could, like StrCat and ToPrimitive. That's because there is no
1225         // evidence that doing CSE on these nodes would result in a performance
1226         // progression. Hence considering these nodes in CSE would just mean that this
1227         // code does more work with no win. Of course, we may want to reconsider this,
1228         // since StrCat is trivially CSE-able. It's not trivially doable for
1229         // ToPrimitive, but we could change that with some speculations if we really
1230         // needed to.
1231         
1232         switch (node.op) {
1233         
1234         // Handle the pure nodes. These nodes never have any side-effects.
1235         case BitAnd:
1236         case BitOr:
1237         case BitXor:
1238         case BitRShift:
1239         case BitLShift:
1240         case BitURShift:
1241         case ArithAdd:
1242         case ArithSub:
1243         case ArithMul:
1244         case ArithMod:
1245         case ArithDiv:
1246         case ArithAbs:
1247         case ArithMin:
1248         case ArithMax:
1249         case ArithSqrt:
1250         case GetCallee:
1251         case GetStringLength:
1252             setReplacement(pureCSE(node));
1253             break;
1254             
1255         case GetArrayLength:
1256             setReplacement(impureCSE(node));
1257             break;
1258             
1259         case GetScopeChain:
1260             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
1261             break;
1262
1263         // Handle nodes that are conditionally pure: these are pure, and can
1264         // be CSE'd, so long as the prediction is the one we want.
1265         case ValueAdd:
1266         case CompareLess:
1267         case CompareLessEq:
1268         case CompareGreater:
1269         case CompareGreaterEq:
1270         case CompareEq: {
1271             if (isPredictedNumerical(node)) {
1272                 NodeIndex replacementIndex = pureCSE(node);
1273                 if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
1274                     setReplacement(replacementIndex);
1275             }
1276             break;
1277         }
1278             
1279         case LogicalNot: {
1280             if (logicalNotIsPure(node)) {
1281                 NodeIndex replacementIndex = pureCSE(node);
1282                 if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex]))
1283                     setReplacement(replacementIndex);
1284             }
1285             break;
1286         }
1287             
1288         // Finally handle heap accesses. These are not quite pure, but we can still
1289         // optimize them provided that some subtle conditions are met.
1290         case GetGlobalVar:
1291             setReplacement(globalVarLoadElimination(node.varNumber()));
1292             break;
1293             
1294         case GetByVal:
1295             setReplacement(getByValLoadElimination(node.child1(), node.child2()));
1296             break;
1297             
1298         case PutByVal:
1299             if (getByValLoadElimination(node.child1(), node.child2()) != NoNode)
1300                 node.op = PutByValAlias;
1301             break;
1302             
1303         case CheckMethod:
1304             setReplacement(getMethodLoadElimination(m_graph.m_methodCheckData[node.methodCheckDataIndex()], node.identifierNumber(), node.child1()));
1305             break;
1306             
1307         case CheckStructure:
1308             if (checkStructureLoadElimination(node.structureSet(), node.child1()))
1309                 eliminate();
1310             break;
1311             
1312         case GetPropertyStorage:
1313             setReplacement(getPropertyStorageLoadElimination(node.child1()));
1314             break;
1315             
1316         case GetByOffset:
1317             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1()));
1318             break;
1319             
1320         default:
1321             // do nothing.
1322             break;
1323         }
1324         
1325         m_lastSeen[node.op & NodeIdMask] = m_compileIndex;
1326 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1327         printf("\n");
1328 #endif
1329     }
1330     
1331     void performBlockCSE(BasicBlock& block)
1332     {
1333         m_start = block.begin;
1334         NodeIndex end = block.end;
1335         for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex)
1336             performNodeCSE(m_graph[m_compileIndex]);
1337     }
1338     
1339     void localCSE()
1340     {
1341 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1342         printf("Performing local CSE:");
1343 #endif
1344         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
1345             performBlockCSE(*m_graph.m_blocks[block]);
1346     }
1347     
1348     void allocateVirtualRegisters()
1349     {
1350         ScoreBoard scoreBoard(m_graph, m_graph.m_preservedVars);
1351         unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
1352         for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
1353             Node& node = m_graph[i];
1354         
1355             if (!node.shouldGenerate())
1356                 continue;
1357         
1358             // GetLocal nodes are effectively phi nodes in the graph, referencing
1359             // results from prior blocks.
1360             if (node.op != GetLocal) {
1361                 // First, call use on all of the current node's children, then
1362                 // allocate a VirtualRegister for this node. We do so in this
1363                 // order so that if a child is on its last use, and a
1364                 // VirtualRegister is freed, then it may be reused for node.
1365                 if (node.op & NodeHasVarArgs) {
1366                     for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1367                         scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
1368                 } else {
1369                     scoreBoard.use(node.child1());
1370                     scoreBoard.use(node.child2());
1371                     scoreBoard.use(node.child3());
1372                 }
1373             }
1374
1375             if (!node.hasResult())
1376                 continue;
1377
1378             node.setVirtualRegister(scoreBoard.allocate());
1379             // 'mustGenerate' nodes have their useCount artificially elevated,
1380             // call use now to account for this.
1381             if (node.mustGenerate())
1382                 scoreBoard.use(i);
1383         }
1384
1385         // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
1386         // for the function (and checked for on entry). Since we perform a new and
1387         // different allocation of temporaries, more registers may now be required.
1388         unsigned calleeRegisters = scoreBoard.allocatedCount() + m_graph.m_preservedVars + m_graph.m_parameterSlots;
1389         if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
1390             m_codeBlock->m_numCalleeRegisters = calleeRegisters;
1391     }
1392     
1393     Graph& m_graph;
1394     JSGlobalData& m_globalData;
1395     CodeBlock* m_codeBlock;
1396     CodeBlock* m_profiledBlock;
1397     
1398     NodeIndex m_start;
1399     NodeIndex m_compileIndex;
1400     
1401 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1402     unsigned m_count;
1403 #endif
1404     
1405     bool m_changed;
1406
1407     Vector<NodeIndex, 16> m_replacements;
1408     FixedArray<NodeIndex, LastNodeId> m_lastSeen;
1409 };
1410
1411 void propagate(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
1412 {
1413     ASSERT(codeBlock);
1414     CodeBlock* profiledBlock = codeBlock->alternative();
1415     ASSERT(profiledBlock);
1416     
1417     Propagator propagator(graph, *globalData, codeBlock, profiledBlock);
1418     propagator.fixpoint();
1419     
1420 }
1421
1422 } } // namespace JSC::DFG
1423
1424 #endif // ENABLE(DFG_JIT)
1425