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