61140f554b88658892445211c83ceac05a46f925
[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 ArithMod: {
340             PredictedType left = m_graph[node.child1()].prediction();
341             PredictedType right = m_graph[node.child2()].prediction();
342             
343             if (left && right) {
344                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
345                     changed |= mergePrediction(PredictInt32);
346                 else
347                     changed |= mergePrediction(PredictDouble);
348             }
349             break;
350         }
351             
352         case UInt32ToNumber: {
353             if (nodeCanSpeculateInteger(node.arithNodeFlags()))
354                 changed |= setPrediction(PredictInt32);
355             else
356                 changed |= setPrediction(PredictNumber);
357             break;
358         }
359
360         case ValueToNumber: {
361             PredictedType prediction = m_graph[node.child1()].prediction();
362             
363             if (prediction) {
364                 if (!(prediction & PredictDouble) && nodeCanSpeculateInteger(node.arithNodeFlags()))
365                     changed |= mergePrediction(PredictInt32);
366                 else
367                     changed |= mergePrediction(PredictNumber);
368             }
369             
370             break;
371         }
372
373         case ValueAdd: {
374             PredictedType left = m_graph[node.child1()].prediction();
375             PredictedType right = m_graph[node.child2()].prediction();
376             
377             if (left && right) {
378                 if (isNumberPrediction(left) && isNumberPrediction(right)) {
379                     if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
380                         changed |= mergePrediction(PredictInt32);
381                     else
382                         changed |= mergePrediction(PredictDouble);
383                 } else if (!(left & PredictNumber) || !(right & PredictNumber)) {
384                     // left or right is definitely something other than a number.
385                     changed |= mergePrediction(PredictString);
386                 } else
387                     changed |= mergePrediction(PredictString | PredictInt32 | PredictDouble);
388             }
389             break;
390         }
391             
392         case ArithAdd:
393         case ArithSub:
394         case ArithMul:
395         case ArithMin:
396         case ArithMax:
397         case ArithDiv: {
398             PredictedType left = m_graph[node.child1()].prediction();
399             PredictedType right = m_graph[node.child2()].prediction();
400             
401             if (left && right) {
402                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
403                     changed |= mergePrediction(PredictInt32);
404                 else
405                     changed |= mergePrediction(PredictDouble);
406             }
407             break;
408         }
409             
410         case ArithSqrt: {
411             changed |= setPrediction(PredictDouble);
412             break;
413         }
414             
415         case ArithAbs: {
416             PredictedType child = m_graph[node.child1()].prediction();
417             if (child) {
418                 if (nodeCanSpeculateInteger(node.arithNodeFlags()))
419                     changed |= mergePrediction(child);
420                 else
421                     changed |= setPrediction(PredictDouble);
422             }
423             break;
424         }
425             
426         case LogicalNot:
427         case CompareLess:
428         case CompareLessEq:
429         case CompareGreater:
430         case CompareGreaterEq:
431         case CompareEq:
432         case CompareStrictEq:
433         case InstanceOf: {
434             changed |= setPrediction(PredictBoolean);
435             break;
436         }
437             
438         case GetById:
439         case GetMethod:
440         case GetByVal: {
441             if (node.getHeapPrediction())
442                 changed |= mergePrediction(node.getHeapPrediction());
443             break;
444         }
445             
446         case GetPropertyStorage: {
447             changed |= setPrediction(PredictOther);
448             break;
449         }
450             
451         case GetByOffset: {
452             if (node.getHeapPrediction())
453                 changed |= mergePrediction(node.getHeapPrediction());
454             break;
455         }
456             
457         case CheckMethod: {
458             changed |= setPrediction(m_graph.getMethodCheckPrediction(node));
459             break;
460         }
461
462         case Call:
463         case Construct: {
464             if (node.getHeapPrediction())
465                 changed |= mergePrediction(node.getHeapPrediction());
466             break;
467         }
468             
469         case ConvertThis: {
470             PredictedType prediction = m_graph[node.child1()].prediction();
471             if (prediction) {
472                 if (prediction & ~PredictObjectMask) {
473                     prediction &= PredictObjectMask;
474                     prediction = mergePredictions(prediction, PredictObjectUnknown);
475                 }
476                 changed |= mergePrediction(prediction);
477             }
478             break;
479         }
480             
481         case GetGlobalVar: {
482             PredictedType prediction = m_graph.getGlobalVarPrediction(node.varNumber());
483             if (prediction)
484                 changed |= mergePrediction(prediction);
485             break;
486         }
487             
488         case PutGlobalVar: {
489             changed |= m_graph.predictGlobalVar(node.varNumber(), m_graph[node.child1()].prediction());
490             break;
491         }
492             
493         case GetScopedVar:
494         case Resolve:
495         case ResolveBase:
496         case ResolveBaseStrictPut:
497         case ResolveGlobal: {
498             PredictedType prediction = node.getHeapPrediction();
499             if (prediction)
500                 changed |= mergePrediction(prediction);
501             break;
502         }
503             
504         case GetScopeChain: {
505             changed |= setPrediction(PredictCellOther);
506             break;
507         }
508             
509         case GetCallee: {
510             changed |= setPrediction(PredictObjectOther);
511             break;
512         }
513             
514         case CreateThis:
515         case NewObject: {
516             changed |= setPrediction(PredictFinalObject);
517             break;
518         }
519             
520         case NewArray:
521         case NewArrayBuffer: {
522             changed |= setPrediction(PredictArray);
523             break;
524         }
525             
526         case NewRegexp: {
527             changed |= setPrediction(PredictObjectOther);
528             break;
529         }
530             
531         case StrCat: {
532             changed |= setPrediction(PredictString);
533             break;
534         }
535             
536         case ToPrimitive: {
537             PredictedType child = m_graph[node.child1()].prediction();
538             if (child) {
539                 if (isObjectPrediction(child)) {
540                     // I'd love to fold this case into the case below, but I can't, because
541                     // removing PredictObjectMask from something that only has an object
542                     // prediction and nothing else means we have an ill-formed PredictedType
543                     // (strong predict-none). This should be killed once we remove all traces
544                     // of static (aka weak) predictions.
545                     changed |= mergePrediction(PredictString);
546                 } else if (child & PredictObjectMask) {
547                     // Objects get turned into strings. So if the input has hints of objectness,
548                     // the output will have hinsts of stringiness.
549                     changed |= mergePrediction(mergePredictions(child & ~PredictObjectMask, PredictString));
550                 } else
551                     changed |= mergePrediction(child);
552             }
553             break;
554         }
555             
556         case ValueToDouble:
557         case GetArrayLength:
558         case GetStringLength: {
559             // This node should never be visible at this stage of compilation. It is
560             // inserted by fixup(), which follows this phase.
561             ASSERT_NOT_REACHED();
562             break;
563         }
564         
565 #ifndef NDEBUG
566         // These get ignored because they don't return anything.
567         case PutScopedVar:
568         case DFG::Jump:
569         case Branch:
570         case Breakpoint:
571         case Return:
572         case CheckHasInstance:
573         case Phi:
574         case Throw:
575         case ThrowReferenceError:
576         case ForceOSRExit:
577         case SetArgument:
578         case PutByVal:
579         case PutByValAlias:
580         case PutById:
581         case PutByIdDirect:
582         case CheckStructure:
583         case PutStructure:
584         case PutByOffset:
585             break;
586             
587         // This gets ignored because it doesn't do anything.
588         case Phantom:
589             break;
590 #else
591         default:
592             break;
593 #endif
594         }
595
596 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
597         printf("%s ", predictionToString(m_graph[m_compileIndex].prediction()));
598 #endif
599         
600         m_changed |= changed;
601     }
602     
603     void propagatePredictionsForward()
604     {
605 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
606         printf("Propagating predictions forward [%u]\n", ++m_count);
607 #endif
608         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
609             propagateNodePredictions(m_graph[m_compileIndex]);
610     }
611     
612     void propagatePredictionsBackward()
613     {
614 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
615         printf("Propagating predictions backward [%u]\n", ++m_count);
616 #endif
617         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
618             propagateNodePredictions(m_graph[m_compileIndex]);
619     }
620     
621     void toDouble(NodeIndex nodeIndex)
622     {
623         if (m_graph[nodeIndex].op == ValueToNumber) {
624 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
625             printf("  @%u -> ValueToDouble", nodeIndex);
626 #endif
627             m_graph[nodeIndex].op = ValueToDouble;
628         }
629     }
630     
631     void fixupNode(Node& node)
632     {
633         if (!node.shouldGenerate())
634             return;
635         
636         NodeType op = node.op;
637
638 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
639         printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
640 #endif
641         
642         switch (op) {
643         case ValueAdd: {
644             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
645                 toDouble(node.child1());
646                 toDouble(node.child2());
647                 break;
648             }
649             
650             PredictedType left = m_graph[node.child1()].prediction();
651             PredictedType right = m_graph[node.child2()].prediction();
652             
653             if (left && right && isNumberPrediction(left) && isNumberPrediction(right)) {
654                 if (left & PredictDouble)
655                     toDouble(node.child2());
656                 if (right & PredictDouble)
657                     toDouble(node.child1());
658             }
659             break;
660         }
661             
662         case ArithAdd:
663         case ArithSub:
664         case ArithMul:
665         case ArithMin:
666         case ArithMax:
667         case ArithMod:
668         case ArithDiv: {
669             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
670                 toDouble(node.child1());
671                 toDouble(node.child2());
672                 break;
673             }
674             
675             PredictedType left = m_graph[node.child1()].prediction();
676             PredictedType right = m_graph[node.child2()].prediction();
677             
678             if (left && right) {
679                 if (left & PredictDouble)
680                     toDouble(node.child2());
681                 if (right & PredictDouble)
682                     toDouble(node.child1());
683             }
684             break;
685         }
686             
687         case ArithAbs: {
688             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
689                 toDouble(node.child1());
690                 break;
691             }
692             
693             PredictedType prediction = m_graph[node.child1()].prediction();
694             if (prediction & PredictDouble)
695                 toDouble(node.child1());
696             break;
697         }
698             
699         case ArithSqrt: {
700             toDouble(node.child1());
701             break;
702         }
703             
704         case GetById: {
705             bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
706             bool isString = isStringPrediction(m_graph[node.child1()].prediction());
707             if (!isArray && !isString)
708                 break;
709             if (!isInt32Prediction(m_graph[m_compileIndex].prediction()))
710                 break;
711             if (m_codeBlock->identifier(node.identifierNumber()) != m_globalData.propertyNames->length)
712                 break;
713             
714 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
715             printf("  @%u -> %s", nodeIndex, isArray ? "GetArrayLength" : "GetStringLength");
716 #endif
717             node.op = isArray ? GetArrayLength : GetStringLength;
718             break;
719         }
720             
721         default:
722             break;
723         }
724
725 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
726         printf("\n");
727 #endif
728     }
729     
730     void fixup()
731     {
732 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
733         printf("Performing Fixup\n");
734 #endif
735         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
736             fixupNode(m_graph[m_compileIndex]);
737     }
738     
739     NodeIndex canonicalize(NodeIndex nodeIndex)
740     {
741         if (nodeIndex == NoNode)
742             return NoNode;
743         
744         if (m_graph[nodeIndex].op == ValueToNumber)
745             nodeIndex = m_graph[nodeIndex].child1();
746         
747         if (m_graph[nodeIndex].op == ValueToInt32)
748             nodeIndex = m_graph[nodeIndex].child1();
749         
750         return nodeIndex;
751     }
752     
753     // Computes where the search for a candidate for CSE should start. Don't call
754     // this directly; call startIndex() instead as it does logging in debug mode.
755     NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
756     {
757         const unsigned limit = 300;
758         
759         NodeIndex start = m_start;
760         if (m_compileIndex - start > limit)
761             start = m_compileIndex - limit;
762         
763         ASSERT(start >= m_start);
764         
765         NodeIndex child = canonicalize(child1);
766         if (child == NoNode)
767             return start;
768         
769         if (start < child)
770             start = child;
771         
772         child = canonicalize(child2);
773         if (child == NoNode)
774             return start;
775         
776         if (start < child)
777             start = child;
778         
779         child = canonicalize(child3);
780         if (child == NoNode)
781             return start;
782         
783         if (start < child)
784             start = child;
785         
786         return start;
787     }
788     
789     NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
790     {
791         NodeIndex result = computeStartIndexForChildren(child1, child2, child3);
792 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
793         printf("  lookback %u: ", result);
794 #endif
795         return result;
796     }
797     
798     NodeIndex startIndex()
799     {
800         Node& node = m_graph[m_compileIndex];
801         return startIndexForChildren(node.child1(), node.child2(), node.child3());
802     }
803     
804     NodeIndex endIndexForPureCSE()
805     {
806         NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask];
807         if (result == NoNode)
808             result = 0;
809         else
810             result++;
811         ASSERT(result <= m_compileIndex);
812 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
813         printf("  limit %u: ", result);
814 #endif
815         return result;
816     }
817     
818     NodeIndex pureCSE(Node& node)
819     {
820         NodeIndex child1 = canonicalize(node.child1());
821         NodeIndex child2 = canonicalize(node.child2());
822         NodeIndex child3 = canonicalize(node.child3());
823         
824         NodeIndex start = startIndex();
825         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
826             Node& otherNode = m_graph[index];
827             if (node.op != otherNode.op)
828                 continue;
829             
830             if (node.arithNodeFlagsForCompare() != otherNode.arithNodeFlagsForCompare())
831                 continue;
832             
833             NodeIndex otherChild = canonicalize(otherNode.child1());
834             if (otherChild == NoNode)
835                 return index;
836             if (otherChild != child1)
837                 continue;
838             
839             otherChild = canonicalize(otherNode.child2());
840             if (otherChild == NoNode)
841                 return index;
842             if (otherChild != child2)
843                 continue;
844             
845             otherChild = canonicalize(otherNode.child3());
846             if (otherChild == NoNode)
847                 return index;
848             if (otherChild != child3)
849                 continue;
850             
851             return index;
852         }
853         return NoNode;
854     }
855     
856     bool isPredictedNumerical(Node& node)
857     {
858         PredictedType left = m_graph[node.child1()].prediction();
859         PredictedType right = m_graph[node.child2()].prediction();
860         return isNumberPrediction(left) && isNumberPrediction(right);
861     }
862     
863     bool logicalNotIsPure(Node& node)
864     {
865         PredictedType prediction = m_graph[node.child1()].prediction();
866         return isBooleanPrediction(prediction) || !prediction;
867     }
868     
869     bool clobbersWorld(NodeIndex nodeIndex)
870     {
871         Node& node = m_graph[nodeIndex];
872         if (node.op & NodeClobbersWorld)
873             return true;
874         if (!(node.op & NodeMightClobber))
875             return false;
876         switch (node.op) {
877         case ValueAdd:
878         case CompareLess:
879         case CompareLessEq:
880         case CompareGreater:
881         case CompareGreaterEq:
882         case CompareEq:
883             return !isPredictedNumerical(node);
884         case LogicalNot:
885             return !logicalNotIsPure(node);
886         default:
887             ASSERT_NOT_REACHED();
888             return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
889         }
890     }
891     
892     NodeIndex impureCSE(Node& node)
893     {
894         NodeIndex child1 = canonicalize(node.child1());
895         NodeIndex child2 = canonicalize(node.child2());
896         NodeIndex child3 = canonicalize(node.child3());
897         
898         NodeIndex start = startIndex();
899         for (NodeIndex index = m_compileIndex; index-- > start;) {
900             Node& otherNode = m_graph[index];
901             if (node.op == otherNode.op
902                 && node.arithNodeFlagsForCompare() == otherNode.arithNodeFlagsForCompare()) {
903                 NodeIndex otherChild = canonicalize(otherNode.child1());
904                 if (otherChild == NoNode)
905                     return index;
906                 if (otherChild == child1) {
907                     otherChild = canonicalize(otherNode.child2());
908                     if (otherChild == NoNode)
909                         return index;
910                     if (otherChild == child2) {
911                         otherChild = canonicalize(otherNode.child3());
912                         if (otherChild == NoNode)
913                             return index;
914                         if (otherChild == child3)
915                             return index;
916                     }
917                 }
918             }
919             if (clobbersWorld(index))
920                 break;
921         }
922         return NoNode;
923     }
924     
925     NodeIndex globalVarLoadElimination(unsigned varNumber)
926     {
927         NodeIndex start = startIndexForChildren();
928         for (NodeIndex index = m_compileIndex; index-- > start;) {
929             Node& node = m_graph[index];
930             switch (node.op) {
931             case GetGlobalVar:
932                 if (node.varNumber() == varNumber)
933                     return index;
934                 break;
935             case PutGlobalVar:
936                 if (node.varNumber() == varNumber)
937                     return node.child1();
938                 break;
939             default:
940                 break;
941             }
942             if (clobbersWorld(index))
943                 break;
944         }
945         return NoNode;
946     }
947     
948     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
949     {
950         NodeIndex start = startIndexForChildren(child1, child2);
951         for (NodeIndex index = m_compileIndex; index-- > start;) {
952             Node& node = m_graph[index];
953             switch (node.op) {
954             case GetByVal:
955                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
956                     return index;
957                 break;
958             case PutByVal:
959                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
960                     return node.child3();
961                 break;
962             case PutStructure:
963             case PutByOffset:
964                 // GetByVal currently always speculates that it's accessing an
965                 // array with an integer index, which means that it's impossible
966                 // for a structure change or a put to property storage to affect
967                 // the GetByVal.
968                 break;
969             default:
970                 if (clobbersWorld(index))
971                     return NoNode;
972                 break;
973             }
974         }
975         return NoNode;
976     }
977     
978     NodeIndex getMethodLoadElimination(const MethodCheckData& methodCheckData, unsigned identifierNumber, NodeIndex child1)
979     {
980         NodeIndex start = startIndexForChildren(child1);
981         for (NodeIndex index = m_compileIndex; index-- > start;) {
982             Node& node = m_graph[index];
983             switch (node.op) {
984             case CheckMethod:
985                 if (node.child1() == child1
986                     && node.identifierNumber() == identifierNumber
987                     && m_graph.m_methodCheckData[node.methodCheckDataIndex()] == methodCheckData)
988                     return index;
989                 break;
990                 
991             case PutByOffset:
992                 // If a put was optimized to by-offset then it's not changing the structure
993                 break;
994                 
995             case PutByVal:
996             case PutByValAlias:
997                 // PutByVal currently always speculates that it's accessing an array with an
998                 // integer index, which means that it's impossible for it to cause a structure
999                 // change.
1000                 break;
1001                 
1002             default:
1003                 if (clobbersWorld(index))
1004                     return NoNode;
1005                 break;
1006             }
1007         }
1008         return NoNode;
1009     }
1010     
1011     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
1012     {
1013         NodeIndex start = startIndexForChildren(child1);
1014         for (NodeIndex index = m_compileIndex; index-- > start;) {
1015             Node& node = m_graph[index];
1016             switch (node.op) {
1017             case CheckStructure:
1018                 if (node.child1() == child1
1019                     && structureSet.isSupersetOf(node.structureSet()))
1020                     return true;
1021                 break;
1022                 
1023             case PutStructure:
1024                 if (node.child1() == child1
1025                     && structureSet.contains(node.structureTransitionData().newStructure))
1026                     return true;
1027                 if (structureSet.contains(node.structureTransitionData().previousStructure))
1028                     return false;
1029                 break;
1030                 
1031             case PutByOffset:
1032                 // Setting a property cannot change the structure.
1033                 break;
1034                 
1035             case PutByVal:
1036             case PutByValAlias:
1037                 // PutByVal currently always speculates that it's accessing an array with an
1038                 // integer index, which means that it's impossible for it to cause a structure
1039                 // change.
1040                 break;
1041                 
1042             default:
1043                 if (clobbersWorld(index))
1044                     return false;
1045                 break;
1046             }
1047         }
1048         return false;
1049     }
1050     
1051     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
1052     {
1053         NodeIndex start = startIndexForChildren(child1);
1054         for (NodeIndex index = m_compileIndex; index-- > start;) {
1055             Node& node = m_graph[index];
1056             switch (node.op) {
1057             case GetByOffset:
1058                 if (node.child1() == child1
1059                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
1060                     return index;
1061                 break;
1062                 
1063             case PutByOffset:
1064                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
1065                     if (node.child2() == child1)
1066                         return node.child3();
1067                     return NoNode;
1068                 }
1069                 break;
1070                 
1071             case PutStructure:
1072                 // Changing the structure cannot change the outcome of a property get.
1073                 break;
1074                 
1075             case PutByVal:
1076             case PutByValAlias:
1077                 // PutByVal currently always speculates that it's accessing an array with an
1078                 // integer index, which means that it's impossible for it to cause a structure
1079                 // change.
1080                 break;
1081                 
1082             default:
1083                 if (clobbersWorld(index))
1084                     return NoNode;
1085                 break;
1086             }
1087         }
1088         return NoNode;
1089     }
1090     
1091     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
1092     {
1093         NodeIndex start = startIndexForChildren(child1);
1094         for (NodeIndex index = m_compileIndex; index-- > start;) {
1095             Node& node = m_graph[index];
1096             switch (node.op) {
1097             case GetPropertyStorage:
1098                 if (node.child1() == child1)
1099                     return index;
1100                 break;
1101                 
1102             case PutByOffset:
1103             case PutStructure:
1104                 // Changing the structure or putting to the storage cannot
1105                 // change the property storage pointer.
1106                 break;
1107                 
1108             case PutByVal:
1109             case PutByValAlias:
1110                 // PutByVal currently always speculates that it's accessing an array with an
1111                 // integer index, which means that it's impossible for it to cause a structure
1112                 // change.
1113                 break;
1114                 
1115             default:
1116                 if (clobbersWorld(index))
1117                     return NoNode;
1118                 break;
1119             }
1120         }
1121         return NoNode;
1122     }
1123     
1124     NodeIndex getScopeChainLoadElimination(unsigned depth)
1125     {
1126         NodeIndex start = startIndexForChildren();
1127         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
1128             Node& node = m_graph[index];
1129             if (node.op == GetScopeChain
1130                 && node.scopeChainDepth() == depth)
1131                 return index;
1132         }
1133         return NoNode;
1134     }
1135     
1136     void performSubstitution(NodeIndex& child)
1137     {
1138         // Check if this operand is actually unused.
1139         if (child == NoNode)
1140             return;
1141         
1142         // Check if there is any replacement.
1143         NodeIndex replacement = m_replacements[child];
1144         if (replacement == NoNode)
1145             return;
1146         
1147         child = replacement;
1148         
1149         // There is definitely a replacement. Assert that the replacement does not
1150         // have a replacement.
1151         ASSERT(m_replacements[child] == NoNode);
1152         
1153         m_graph[child].ref();
1154     }
1155     
1156     void setReplacement(NodeIndex replacement)
1157     {
1158         if (replacement == NoNode)
1159             return;
1160         
1161         // Be safe. Don't try to perform replacements if the predictions don't
1162         // agree.
1163         if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
1164             return;
1165         
1166 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1167         printf("   Replacing @%u -> @%u", m_compileIndex, replacement);
1168 #endif
1169         
1170         Node& node = m_graph[m_compileIndex];
1171         node.op = Phantom;
1172         node.setRefCount(1);
1173         
1174         // At this point we will eliminate all references to this node.
1175         m_replacements[m_compileIndex] = replacement;
1176     }
1177     
1178     void eliminate()
1179     {
1180 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1181         printf("   Eliminating @%u", m_compileIndex);
1182 #endif
1183         
1184         Node& node = m_graph[m_compileIndex];
1185         ASSERT(node.refCount() == 1);
1186         ASSERT(node.mustGenerate());
1187         node.op = Phantom;
1188     }
1189     
1190     void performNodeCSE(Node& node)
1191     {
1192         if (node.op & NodeHasVarArgs) {
1193             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1194                 performSubstitution(m_graph.m_varArgChildren[childIdx]);
1195         } else {
1196             performSubstitution(node.children.fixed.child1);
1197             performSubstitution(node.children.fixed.child2);
1198             performSubstitution(node.children.fixed.child3);
1199         }
1200         
1201         if (!node.shouldGenerate())
1202             return;
1203         
1204 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1205         printf("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op), m_compileIndex);
1206 #endif
1207         
1208         // NOTE: there are some nodes that we deliberately don't CSE even though we
1209         // probably could, like StrCat and ToPrimitive. That's because there is no
1210         // evidence that doing CSE on these nodes would result in a performance
1211         // progression. Hence considering these nodes in CSE would just mean that this
1212         // code does more work with no win. Of course, we may want to reconsider this,
1213         // since StrCat is trivially CSE-able. It's not trivially doable for
1214         // ToPrimitive, but we could change that with some speculations if we really
1215         // needed to.
1216         
1217         switch (node.op) {
1218         
1219         // Handle the pure nodes. These nodes never have any side-effects.
1220         case BitAnd:
1221         case BitOr:
1222         case BitXor:
1223         case BitRShift:
1224         case BitLShift:
1225         case BitURShift:
1226         case ArithAdd:
1227         case ArithSub:
1228         case ArithMul:
1229         case ArithMod:
1230         case ArithDiv:
1231         case ArithAbs:
1232         case ArithMin:
1233         case ArithMax:
1234         case ArithSqrt:
1235         case GetCallee:
1236         case GetStringLength:
1237             setReplacement(pureCSE(node));
1238             break;
1239             
1240         case GetArrayLength:
1241             setReplacement(impureCSE(node));
1242             break;
1243             
1244         case GetScopeChain:
1245             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
1246             break;
1247
1248         // Handle nodes that are conditionally pure: these are pure, and can
1249         // be CSE'd, so long as the prediction is the one we want.
1250         case ValueAdd:
1251         case CompareLess:
1252         case CompareLessEq:
1253         case CompareGreater:
1254         case CompareGreaterEq:
1255         case CompareEq: {
1256             if (isPredictedNumerical(node)) {
1257                 NodeIndex replacementIndex = pureCSE(node);
1258                 if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
1259                     setReplacement(replacementIndex);
1260             }
1261             break;
1262         }
1263             
1264         case LogicalNot: {
1265             if (logicalNotIsPure(node)) {
1266                 NodeIndex replacementIndex = pureCSE(node);
1267                 if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex]))
1268                     setReplacement(replacementIndex);
1269             }
1270             break;
1271         }
1272             
1273         // Finally handle heap accesses. These are not quite pure, but we can still
1274         // optimize them provided that some subtle conditions are met.
1275         case GetGlobalVar:
1276             setReplacement(globalVarLoadElimination(node.varNumber()));
1277             break;
1278             
1279         case GetByVal:
1280             setReplacement(getByValLoadElimination(node.child1(), node.child2()));
1281             break;
1282             
1283         case PutByVal:
1284             if (getByValLoadElimination(node.child1(), node.child2()) != NoNode)
1285                 node.op = PutByValAlias;
1286             break;
1287             
1288         case CheckMethod:
1289             setReplacement(getMethodLoadElimination(m_graph.m_methodCheckData[node.methodCheckDataIndex()], node.identifierNumber(), node.child1()));
1290             break;
1291             
1292         case CheckStructure:
1293             if (checkStructureLoadElimination(node.structureSet(), node.child1()))
1294                 eliminate();
1295             break;
1296             
1297         case GetPropertyStorage:
1298             setReplacement(getPropertyStorageLoadElimination(node.child1()));
1299             break;
1300             
1301         case GetByOffset:
1302             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1()));
1303             break;
1304             
1305         default:
1306             // do nothing.
1307             break;
1308         }
1309         
1310         m_lastSeen[node.op & NodeIdMask] = m_compileIndex;
1311 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1312         printf("\n");
1313 #endif
1314     }
1315     
1316     void performBlockCSE(BasicBlock& block)
1317     {
1318         m_start = block.begin;
1319         NodeIndex end = block.end;
1320         for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex)
1321             performNodeCSE(m_graph[m_compileIndex]);
1322     }
1323     
1324     void localCSE()
1325     {
1326 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1327         printf("Performing local CSE:");
1328 #endif
1329         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
1330             performBlockCSE(*m_graph.m_blocks[block]);
1331     }
1332     
1333     void allocateVirtualRegisters()
1334     {
1335         ScoreBoard scoreBoard(m_graph, m_graph.m_preservedVars);
1336         unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
1337         for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
1338             Node& node = m_graph[i];
1339         
1340             if (!node.shouldGenerate())
1341                 continue;
1342         
1343             // GetLocal nodes are effectively phi nodes in the graph, referencing
1344             // results from prior blocks.
1345             if (node.op != GetLocal) {
1346                 // First, call use on all of the current node's children, then
1347                 // allocate a VirtualRegister for this node. We do so in this
1348                 // order so that if a child is on its last use, and a
1349                 // VirtualRegister is freed, then it may be reused for node.
1350                 if (node.op & NodeHasVarArgs) {
1351                     for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1352                         scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
1353                 } else {
1354                     scoreBoard.use(node.child1());
1355                     scoreBoard.use(node.child2());
1356                     scoreBoard.use(node.child3());
1357                 }
1358             }
1359
1360             if (!node.hasResult())
1361                 continue;
1362
1363             node.setVirtualRegister(scoreBoard.allocate());
1364             // 'mustGenerate' nodes have their useCount artificially elevated,
1365             // call use now to account for this.
1366             if (node.mustGenerate())
1367                 scoreBoard.use(i);
1368         }
1369
1370         // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
1371         // for the function (and checked for on entry). Since we perform a new and
1372         // different allocation of temporaries, more registers may now be required.
1373         unsigned calleeRegisters = scoreBoard.allocatedCount() + m_graph.m_preservedVars + m_graph.m_parameterSlots;
1374         if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
1375             m_codeBlock->m_numCalleeRegisters = calleeRegisters;
1376     }
1377     
1378     Graph& m_graph;
1379     JSGlobalData& m_globalData;
1380     CodeBlock* m_codeBlock;
1381     CodeBlock* m_profiledBlock;
1382     
1383     NodeIndex m_start;
1384     NodeIndex m_compileIndex;
1385     
1386 #if ENABLE(DFG_DEBUG_PROPAGATION_VERBOSE)
1387     unsigned m_count;
1388 #endif
1389     
1390     bool m_changed;
1391
1392     Vector<NodeIndex, 16> m_replacements;
1393     FixedArray<NodeIndex, LastNodeId> m_lastSeen;
1394 };
1395
1396 void propagate(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
1397 {
1398     ASSERT(codeBlock);
1399     CodeBlock* profiledBlock = codeBlock->alternative();
1400     ASSERT(profiledBlock);
1401     
1402     Propagator propagator(graph, *globalData, codeBlock, profiledBlock);
1403     propagator.fixpoint();
1404     
1405 }
1406
1407 } } // namespace JSC::DFG
1408
1409 #endif // ENABLE(DFG_JIT)
1410