DFG should not speculate array even when predictions say that the base is not an...
[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 "DFGAbstractState.h"
32 #include "DFGGraph.h"
33 #include "DFGScoreBoard.h"
34 #include <wtf/FixedArray.h>
35
36 namespace JSC { namespace DFG {
37
38 class Propagator {
39 public:
40     Propagator(Graph& graph, JSGlobalData& globalData, CodeBlock* codeBlock, CodeBlock* profiledBlock)
41         : m_graph(graph)
42         , m_globalData(globalData)
43         , m_codeBlock(codeBlock)
44         , m_profiledBlock(profiledBlock)
45     {
46         // Replacements are used to implement local common subexpression elimination.
47         m_replacements.resize(m_graph.size());
48         
49         for (unsigned i = 0; i < m_graph.size(); ++i)
50             m_replacements[i] = NoNode;
51         
52         for (unsigned i = 0; i < LastNodeId; ++i)
53             m_lastSeen[i] = NoNode;
54     }
55     
56     void fixpoint()
57     {
58 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
59         m_graph.dump(m_codeBlock);
60 #endif
61
62         propagateArithNodeFlags();
63         propagatePredictions();
64         fixup();
65         
66 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
67         printf("Graph after propagation fixup:\n");
68         m_graph.dump(m_codeBlock);
69 #endif
70
71         localCSE();
72
73 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
74         printf("Graph after CSE:\n");
75         m_graph.dump(m_codeBlock);
76 #endif
77
78         allocateVirtualRegisters();
79
80 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
81         printf("Graph after virtual register allocation:\n");
82         m_graph.dump(m_codeBlock);
83 #endif
84
85         globalCFA();
86
87 #if DFG_ENABLE(DEBUG_VERBOSE)
88         printf("Graph after propagation:\n");
89         m_graph.dump(m_codeBlock);
90 #endif
91     }
92     
93 private:
94     bool isNotNegZero(NodeIndex nodeIndex)
95     {
96         if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
97             return false;
98         double value = m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
99         return !value && 1.0 / value < 0.0;
100     }
101     
102     bool isNotZero(NodeIndex nodeIndex)
103     {
104         if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
105             return false;
106         return !!m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
107     }
108     
109     void propagateArithNodeFlags(Node& node)
110     {
111         if (!node.shouldGenerate())
112             return;
113         
114         NodeType op = node.op;
115         ArithNodeFlags flags = 0;
116         
117         if (node.hasArithNodeFlags())
118             flags = node.rawArithNodeFlags();
119         
120 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
121         printf("   %s @%u: %s ", Graph::opName(op), m_compileIndex, arithNodeFlagsAsString(flags));
122 #endif
123         
124         flags &= NodeUsedAsMask;
125         
126         bool changed = false;
127         
128         switch (op) {
129         case ValueToInt32:
130         case BitAnd:
131         case BitOr:
132         case BitXor:
133         case BitLShift:
134         case BitRShift:
135         case BitURShift: {
136             // These operations are perfectly happy with truncated integers,
137             // so we don't want to propagate anything.
138             break;
139         }
140             
141         case ValueToNumber:
142         case ValueToDouble:
143         case UInt32ToNumber: {
144             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
145             break;
146         }
147             
148         case ArithAdd:
149         case ValueAdd: {
150             if (isNotNegZero(node.child1()) || isNotNegZero(node.child2()))
151                 flags &= ~NodeNeedsNegZero;
152             
153             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
154             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
155             break;
156         }
157             
158         case ArithSub: {
159             if (isNotZero(node.child1()) || isNotZero(node.child2()))
160                 flags &= ~NodeNeedsNegZero;
161             
162             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
163             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
164             break;
165         }
166             
167         case ArithMul:
168         case ArithDiv: {
169             // As soon as a multiply happens, we can easily end up in the part
170             // of the double domain where the point at which you do truncation
171             // can change the outcome. So, ArithMul always checks for overflow
172             // no matter what, and always forces its inputs to check as well.
173             
174             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
175             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
176             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
177             break;
178         }
179             
180         case ArithMin:
181         case ArithMax: {
182             flags |= NodeUsedAsNumber;
183             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
184             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
185             break;
186         }
187             
188         case ArithAbs: {
189             flags &= ~NodeNeedsNegZero;
190             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
191             break;
192         }
193             
194         case PutByVal: {
195             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
196             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
197             changed |= m_graph[node.child3()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
198             break;
199         }
200             
201         case GetByVal: {
202             changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
203             changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
204             break;
205         }
206             
207         default:
208             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
209             if (op & NodeHasVarArgs) {
210                 for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
211                     changed |= m_graph[m_graph.m_varArgChildren[childIdx]].mergeArithNodeFlags(flags);
212             } else {
213                 if (node.child1() == NoNode)
214                     break;
215                 changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
216                 if (node.child2() == NoNode)
217                     break;
218                 changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
219                 if (node.child3() == NoNode)
220                     break;
221                 changed |= m_graph[node.child3()].mergeArithNodeFlags(flags);
222             }
223             break;
224         }
225
226 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
227         printf("%s\n", changed ? "CHANGED" : "");
228 #endif
229         
230         m_changed |= changed;
231     }
232     
233     void propagateArithNodeFlagsForward()
234     {
235 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
236         printf("Propagating arithmetic node flags forward [%u]\n", ++m_count);
237 #endif
238         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
239             propagateArithNodeFlags(m_graph[m_compileIndex]);
240     }
241     
242     void propagateArithNodeFlagsBackward()
243     {
244 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
245         printf("Propagating arithmetic node flags backward [%u]\n", ++m_count);
246 #endif
247         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
248             propagateArithNodeFlags(m_graph[m_compileIndex]);
249     }
250     
251     void propagateArithNodeFlags()
252     {
253 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
254         m_count = 0;
255 #endif
256         do {
257             m_changed = false;
258             
259             // Up here we start with a backward pass because we suspect that to be
260             // more profitable.
261             propagateArithNodeFlagsBackward();
262             if (!m_changed)
263                 break;
264             
265             m_changed = false;
266             propagateArithNodeFlagsForward();
267         } while (m_changed);
268     }
269     
270     bool setPrediction(PredictedType prediction)
271     {
272         ASSERT(m_graph[m_compileIndex].hasResult());
273         
274         // setPrediction() is used when we know that there is no way that we can change
275         // our minds about what the prediction is going to be. There is no semantic
276         // difference between setPrediction() and mergePrediction() other than the
277         // increased checking to validate this property.
278         ASSERT(m_graph[m_compileIndex].prediction() == PredictNone || m_graph[m_compileIndex].prediction() == prediction);
279         
280         return m_graph[m_compileIndex].predict(prediction);
281     }
282     
283     bool mergePrediction(PredictedType prediction)
284     {
285         ASSERT(m_graph[m_compileIndex].hasResult());
286         
287         return m_graph[m_compileIndex].predict(prediction);
288     }
289     
290     void propagateNodePredictions(Node& node)
291     {
292         if (!node.shouldGenerate())
293             return;
294         
295         NodeType op = node.op;
296
297 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
298         printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
299 #endif
300         
301         bool changed = false;
302         
303         switch (op) {
304         case JSConstant:
305         case WeakJSConstant: {
306             changed |= setPrediction(predictionFromValue(m_graph.valueOfJSConstant(m_codeBlock, m_compileIndex)));
307             break;
308         }
309             
310         case GetLocal: {
311             PredictedType prediction = node.variableAccessData()->prediction();
312             if (prediction)
313                 changed |= mergePrediction(prediction);
314             break;
315         }
316             
317         case SetLocal: {
318             changed |= node.variableAccessData()->predict(m_graph[node.child1()].prediction());
319             break;
320         }
321             
322         case BitAnd:
323         case BitOr:
324         case BitXor:
325         case BitRShift:
326         case BitLShift:
327         case BitURShift:
328         case ValueToInt32: {
329             changed |= setPrediction(PredictInt32);
330             break;
331         }
332             
333         case ArrayPop:
334         case ArrayPush: {
335             if (node.getHeapPrediction())
336                 changed |= mergePrediction(node.getHeapPrediction());
337             break;
338         }
339
340         case StringCharCodeAt: {
341             changed |= mergePrediction(PredictInt32);
342             break;
343         }
344
345         case ArithMod: {
346             PredictedType left = m_graph[node.child1()].prediction();
347             PredictedType right = m_graph[node.child2()].prediction();
348             
349             if (left && right) {
350                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
351                     changed |= mergePrediction(PredictInt32);
352                 else
353                     changed |= mergePrediction(PredictDouble);
354             }
355             break;
356         }
357             
358         case UInt32ToNumber: {
359             if (nodeCanSpeculateInteger(node.arithNodeFlags()))
360                 changed |= setPrediction(PredictInt32);
361             else
362                 changed |= setPrediction(PredictNumber);
363             break;
364         }
365
366         case ValueToNumber: {
367             PredictedType prediction = m_graph[node.child1()].prediction();
368             
369             if (prediction) {
370                 if (!(prediction & PredictDouble) && nodeCanSpeculateInteger(node.arithNodeFlags()))
371                     changed |= mergePrediction(PredictInt32);
372                 else
373                     changed |= mergePrediction(PredictNumber);
374             }
375             
376             break;
377         }
378
379         case ValueAdd: {
380             PredictedType left = m_graph[node.child1()].prediction();
381             PredictedType right = m_graph[node.child2()].prediction();
382             
383             if (left && right) {
384                 if (isNumberPrediction(left) && isNumberPrediction(right)) {
385                     if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
386                         changed |= mergePrediction(PredictInt32);
387                     else
388                         changed |= mergePrediction(PredictDouble);
389                 } else if (!(left & PredictNumber) || !(right & PredictNumber)) {
390                     // left or right is definitely something other than a number.
391                     changed |= mergePrediction(PredictString);
392                 } else
393                     changed |= mergePrediction(PredictString | PredictInt32 | PredictDouble);
394             }
395             break;
396         }
397             
398         case ArithAdd:
399         case ArithSub:
400         case ArithMul:
401         case ArithMin:
402         case ArithMax:
403         case ArithDiv: {
404             PredictedType left = m_graph[node.child1()].prediction();
405             PredictedType right = m_graph[node.child2()].prediction();
406             
407             if (left && right) {
408                 if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
409                     changed |= mergePrediction(PredictInt32);
410                 else
411                     changed |= mergePrediction(PredictDouble);
412             }
413             break;
414         }
415             
416         case ArithSqrt: {
417             changed |= setPrediction(PredictDouble);
418             break;
419         }
420             
421         case ArithAbs: {
422             PredictedType child = m_graph[node.child1()].prediction();
423             if (child) {
424                 if (nodeCanSpeculateInteger(node.arithNodeFlags()))
425                     changed |= mergePrediction(child);
426                 else
427                     changed |= setPrediction(PredictDouble);
428             }
429             break;
430         }
431             
432         case LogicalNot:
433         case CompareLess:
434         case CompareLessEq:
435         case CompareGreater:
436         case CompareGreaterEq:
437         case CompareEq:
438         case CompareStrictEq:
439         case InstanceOf: {
440             changed |= setPrediction(PredictBoolean);
441             break;
442         }
443             
444         case GetById: {
445             if (node.getHeapPrediction())
446                 changed |= mergePrediction(node.getHeapPrediction());
447             else if (m_codeBlock->identifier(node.identifierNumber()) == m_globalData.propertyNames->length) {
448                 // If there is no prediction from value profiles, check if we might be
449                 // able to infer the type ourselves.
450                 bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
451                 bool isString = isStringPrediction(m_graph[node.child1()].prediction());
452                 bool isByteArray = m_graph[node.child1()].shouldSpeculateByteArray();
453                 bool isInt8Array = m_graph[node.child1()].shouldSpeculateInt8Array();
454                 bool isInt16Array = m_graph[node.child1()].shouldSpeculateInt16Array();
455                 bool isInt32Array = m_graph[node.child1()].shouldSpeculateInt32Array();
456                 bool isUint8Array = m_graph[node.child1()].shouldSpeculateUint8Array();
457                 bool isUint16Array = m_graph[node.child1()].shouldSpeculateUint16Array();
458                 bool isUint32Array = m_graph[node.child1()].shouldSpeculateUint32Array();
459                 bool isFloat32Array = m_graph[node.child1()].shouldSpeculateFloat32Array();
460                 bool isFloat64Array = m_graph[node.child1()].shouldSpeculateFloat64Array();
461                 if (isArray || isString || isByteArray || isInt8Array || isInt16Array || isInt32Array || isUint8Array || isUint16Array || isUint32Array || isFloat32Array || isFloat64Array)
462                     changed |= mergePrediction(PredictInt32);
463             }
464             break;
465         }
466             
467         case GetByVal: {
468             if (m_graph[node.child1()].shouldSpeculateUint32Array() || m_graph[node.child1()].shouldSpeculateFloat32Array() || m_graph[node.child1()].shouldSpeculateFloat64Array())
469                 changed |= mergePrediction(PredictDouble);
470             else if (node.getHeapPrediction())
471                 changed |= mergePrediction(node.getHeapPrediction());
472             break;
473         }
474             
475         case GetPropertyStorage: 
476         case GetIndexedPropertyStorage: {
477             changed |= setPrediction(PredictOther);
478             break;
479         }
480
481         case GetByOffset: {
482             if (node.getHeapPrediction())
483                 changed |= mergePrediction(node.getHeapPrediction());
484             break;
485         }
486             
487         case Call:
488         case Construct: {
489             if (node.getHeapPrediction())
490                 changed |= mergePrediction(node.getHeapPrediction());
491             break;
492         }
493             
494         case ConvertThis: {
495             PredictedType prediction = m_graph[node.child1()].prediction();
496             if (prediction) {
497                 if (prediction & ~PredictObjectMask) {
498                     prediction &= PredictObjectMask;
499                     prediction = mergePredictions(prediction, PredictObjectOther);
500                 }
501                 changed |= mergePrediction(prediction);
502             }
503             break;
504         }
505             
506         case GetGlobalVar: {
507             PredictedType prediction = m_graph.getGlobalVarPrediction(node.varNumber());
508             if (prediction)
509                 changed |= mergePrediction(prediction);
510             break;
511         }
512             
513         case PutGlobalVar: {
514             changed |= m_graph.predictGlobalVar(node.varNumber(), m_graph[node.child1()].prediction());
515             break;
516         }
517             
518         case GetScopedVar:
519         case Resolve:
520         case ResolveBase:
521         case ResolveBaseStrictPut:
522         case ResolveGlobal: {
523             PredictedType prediction = node.getHeapPrediction();
524             if (prediction)
525                 changed |= mergePrediction(prediction);
526             break;
527         }
528             
529         case GetScopeChain: {
530             changed |= setPrediction(PredictCellOther);
531             break;
532         }
533             
534         case GetCallee: {
535             changed |= setPrediction(PredictFunction);
536             break;
537         }
538             
539         case CreateThis:
540         case NewObject: {
541             changed |= setPrediction(PredictFinalObject);
542             break;
543         }
544             
545         case NewArray:
546         case NewArrayBuffer: {
547             changed |= setPrediction(PredictArray);
548             break;
549         }
550             
551         case NewRegexp: {
552             changed |= setPrediction(PredictObjectOther);
553             break;
554         }
555         
556         case StringCharAt:
557         case StrCat: {
558             changed |= setPrediction(PredictString);
559             break;
560         }
561             
562         case ToPrimitive: {
563             PredictedType child = m_graph[node.child1()].prediction();
564             if (child) {
565                 if (isObjectPrediction(child)) {
566                     // I'd love to fold this case into the case below, but I can't, because
567                     // removing PredictObjectMask from something that only has an object
568                     // prediction and nothing else means we have an ill-formed PredictedType
569                     // (strong predict-none). This should be killed once we remove all traces
570                     // of static (aka weak) predictions.
571                     changed |= mergePrediction(PredictString);
572                 } else if (child & PredictObjectMask) {
573                     // Objects get turned into strings. So if the input has hints of objectness,
574                     // the output will have hinsts of stringiness.
575                     changed |= mergePrediction(mergePredictions(child & ~PredictObjectMask, PredictString));
576                 } else
577                     changed |= mergePrediction(child);
578             }
579             break;
580         }
581             
582         case ValueToDouble:
583         case GetArrayLength:
584         case GetByteArrayLength:
585         case GetInt8ArrayLength:
586         case GetInt16ArrayLength:
587         case GetInt32ArrayLength:
588         case GetUint8ArrayLength:
589         case GetUint16ArrayLength:
590         case GetUint32ArrayLength:
591         case GetFloat32ArrayLength:
592         case GetFloat64ArrayLength:
593         case GetStringLength: {
594             // This node should never be visible at this stage of compilation. It is
595             // inserted by fixup(), which follows this phase.
596             ASSERT_NOT_REACHED();
597             break;
598         }
599         
600 #ifndef NDEBUG
601         // These get ignored because they don't return anything.
602         case PutScopedVar:
603         case DFG::Jump:
604         case Branch:
605         case Breakpoint:
606         case Return:
607         case CheckHasInstance:
608         case Phi:
609         case Flush:
610         case Throw:
611         case ThrowReferenceError:
612         case ForceOSRExit:
613         case SetArgument:
614         case PutByVal:
615         case PutByValAlias:
616         case PutById:
617         case PutByIdDirect:
618         case CheckStructure:
619         case CheckFunction:
620         case PutStructure:
621         case PutByOffset:
622             break;
623             
624         // These gets ignored because it doesn't do anything.
625         case Phantom:
626         case InlineStart:
627         case Nop:
628             break;
629 #else
630         default:
631             break;
632 #endif
633         }
634
635 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
636         printf("%s\n", predictionToString(m_graph[m_compileIndex].prediction()));
637 #endif
638         
639         m_changed |= changed;
640     }
641     
642     void propagatePredictionsForward()
643     {
644 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
645         printf("Propagating predictions forward [%u]\n", ++m_count);
646 #endif
647         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
648             propagateNodePredictions(m_graph[m_compileIndex]);
649     }
650     
651     void propagatePredictionsBackward()
652     {
653 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
654         printf("Propagating predictions backward [%u]\n", ++m_count);
655 #endif
656         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
657             propagateNodePredictions(m_graph[m_compileIndex]);
658     }
659     
660     void vote(NodeIndex nodeIndex, VariableAccessData::Ballot ballot)
661     {
662         switch (m_graph[nodeIndex].op) {
663         case ValueToNumber:
664         case ValueToDouble:
665         case ValueToInt32:
666         case UInt32ToNumber:
667             nodeIndex = m_graph[nodeIndex].child1();
668             break;
669         default:
670             break;
671         }
672         
673         if (m_graph[nodeIndex].op == GetLocal)
674             m_graph[nodeIndex].variableAccessData()->vote(ballot);
675     }
676     
677     void vote(Node& node, VariableAccessData::Ballot ballot)
678     {
679         if (node.op & NodeHasVarArgs) {
680             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
681                 vote(m_graph.m_varArgChildren[childIdx], ballot);
682             return;
683         }
684         
685         if (node.child1() == NoNode)
686             return;
687         vote(node.child1(), ballot);
688         if (node.child2() == NoNode)
689             return;
690         vote(node.child2(), ballot);
691         if (node.child3() == NoNode)
692             return;
693         vote(node.child3(), ballot);
694     }
695     
696     void doRoundOfDoubleVoting()
697     {
698 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
699         printf("Voting on double uses of locals [%u]\n", m_count);
700 #endif
701         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
702             m_graph.m_variableAccessData[i].find()->clearVotes();
703         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex) {
704             Node& node = m_graph[m_compileIndex];
705             switch (node.op) {
706             case ValueAdd:
707             case ArithAdd:
708             case ArithSub:
709             case ArithMul:
710             case ArithMin:
711             case ArithMax:
712             case ArithMod:
713             case ArithDiv: {
714                 PredictedType left = m_graph[node.child1()].prediction();
715                 PredictedType right = m_graph[node.child2()].prediction();
716                 
717                 VariableAccessData::Ballot ballot;
718                 
719                 if (isNumberPrediction(left) && isNumberPrediction(right) && !(Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child1()]) && node.canSpeculateInteger()))
720                     ballot = VariableAccessData::VoteDouble;
721                 else
722                     ballot = VariableAccessData::VoteValue;
723                 
724                 vote(node.child1(), ballot);
725                 vote(node.child2(), ballot);
726                 break;
727             }
728                 
729             case ArithAbs:
730                 VariableAccessData::Ballot ballot;
731                 if (!(m_graph[node.child1()].shouldSpeculateInteger() && node.canSpeculateInteger()))
732                     ballot = VariableAccessData::VoteDouble;
733                 else
734                     ballot = VariableAccessData::VoteValue;
735                 
736                 vote(node.child1(), ballot);
737                 break;
738                 
739             case ArithSqrt:
740                 vote(node.child1(), VariableAccessData::VoteDouble);
741                 break;
742                 
743             case ValueToNumber:
744             case ValueToDouble:
745                 // Don't vote.
746                 break;
747                 
748             case SetLocal: {
749                 PredictedType prediction = m_graph[node.child1()].prediction();
750                 if (isDoublePrediction(prediction))
751                     node.variableAccessData()->vote(VariableAccessData::VoteDouble);
752                 else if (!isNumberPrediction(prediction) || isInt32Prediction(prediction))
753                     node.variableAccessData()->vote(VariableAccessData::VoteValue);
754                 break;
755             }
756                 
757             default:
758                 vote(node, VariableAccessData::VoteValue);
759                 break;
760             }
761         }
762         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
763             m_changed |= m_graph.m_variableAccessData[i].find()->tallyVotesForShouldUseDoubleFormat();
764     }
765     
766     void propagatePredictions()
767     {
768 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
769         m_count = 0;
770 #endif
771         do {
772             m_changed = false;
773             
774             // Forward propagation is near-optimal for both topologically-sorted and
775             // DFS-sorted code.
776             propagatePredictionsForward();
777             doRoundOfDoubleVoting();
778             if (!m_changed)
779                 break;
780             
781             // Backward propagation reduces the likelihood that pathological code will
782             // cause slowness. Loops (especially nested ones) resemble backward flow.
783             // This pass captures two cases: (1) it detects if the forward fixpoint
784             // found a sound solution and (2) short-circuits backward flow.
785             m_changed = false;
786             propagatePredictionsBackward();
787             doRoundOfDoubleVoting();
788         } while (m_changed);
789     }
790     
791     void toDouble(NodeIndex nodeIndex)
792     {
793         if (m_graph[nodeIndex].op == ValueToNumber) {
794 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
795             printf("  @%u -> ValueToDouble", nodeIndex);
796 #endif
797             m_graph[nodeIndex].op = ValueToDouble;
798         }
799     }
800
801     void fixupNode(Node& node)
802     {
803         if (!node.shouldGenerate())
804             return;
805         
806         NodeType op = node.op;
807
808 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
809         printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
810 #endif
811         
812         switch (op) {
813         case ValueAdd: {
814             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
815                 toDouble(node.child1());
816                 toDouble(node.child2());
817                 break;
818             }
819             
820             PredictedType left = m_graph[node.child1()].prediction();
821             PredictedType right = m_graph[node.child2()].prediction();
822             
823             if (left && right
824                 && isNumberPrediction(left) && isNumberPrediction(right)
825                 && ((left & PredictDouble) || (right & PredictDouble))) {
826                 toDouble(node.child1());
827                 toDouble(node.child2());
828             }
829             break;
830         }
831             
832         case ArithAdd:
833         case ArithSub:
834         case ArithMul:
835         case ArithMin:
836         case ArithMax:
837         case ArithMod:
838         case ArithDiv: {
839             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
840                 toDouble(node.child1());
841                 toDouble(node.child2());
842                 break;
843             }
844             
845             PredictedType left = m_graph[node.child1()].prediction();
846             PredictedType right = m_graph[node.child2()].prediction();
847             
848             if (left && right
849                 && ((left & PredictDouble) || (right & PredictDouble))) {
850                 toDouble(node.child1());
851                 toDouble(node.child2());
852             }
853             break;
854         }
855             
856         case ArithAbs: {
857             if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
858                 toDouble(node.child1());
859                 break;
860             }
861             
862             PredictedType prediction = m_graph[node.child1()].prediction();
863             if (prediction & PredictDouble)
864                 toDouble(node.child1());
865             break;
866         }
867             
868         case ArithSqrt: {
869             toDouble(node.child1());
870             break;
871         }
872             
873         case GetById: {
874             if (!isInt32Prediction(m_graph[m_compileIndex].prediction()))
875                 break;
876             if (m_codeBlock->identifier(node.identifierNumber()) != m_globalData.propertyNames->length)
877                 break;
878             bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
879             bool isString = isStringPrediction(m_graph[node.child1()].prediction());
880             bool isByteArray = m_graph[node.child1()].shouldSpeculateByteArray();
881             bool isInt8Array = m_graph[node.child1()].shouldSpeculateInt8Array();
882             bool isInt16Array = m_graph[node.child1()].shouldSpeculateInt16Array();
883             bool isInt32Array = m_graph[node.child1()].shouldSpeculateInt32Array();
884             bool isUint8Array = m_graph[node.child1()].shouldSpeculateUint8Array();
885             bool isUint16Array = m_graph[node.child1()].shouldSpeculateUint16Array();
886             bool isUint32Array = m_graph[node.child1()].shouldSpeculateUint32Array();
887             bool isFloat32Array = m_graph[node.child1()].shouldSpeculateFloat32Array();
888             bool isFloat64Array = m_graph[node.child1()].shouldSpeculateFloat64Array();
889             if (!isArray && !isString && !isByteArray && !isInt8Array && !isInt16Array && !isInt32Array && !isUint8Array && !isUint16Array && !isUint32Array && !isFloat32Array && !isFloat64Array)
890                 break;
891             
892 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
893             printf("  @%u -> %s", m_compileIndex, isArray ? "GetArrayLength" : "GetStringLength");
894 #endif
895             if (isArray)
896                 node.op = GetArrayLength;
897             else if (isString)
898                 node.op = GetStringLength;
899             else if (isByteArray)
900                 node.op = GetByteArrayLength;
901             else if (isInt8Array)
902                 node.op = GetInt8ArrayLength;
903             else if (isInt16Array)
904                 node.op = GetInt16ArrayLength;
905             else if (isInt32Array)
906                 node.op = GetInt32ArrayLength;
907             else if (isUint8Array)
908                 node.op = GetUint8ArrayLength;
909             else if (isUint16Array)
910                 node.op = GetUint16ArrayLength;
911             else if (isUint32Array)
912                 node.op = GetUint32ArrayLength;
913             else if (isFloat32Array)
914                 node.op = GetFloat32ArrayLength;
915             else if (isFloat64Array)
916                 node.op = GetFloat64ArrayLength;
917             else
918                 ASSERT_NOT_REACHED();
919             node.deref(); // No longer MustGenerate
920             break;
921         }
922         case GetIndexedPropertyStorage: {
923             PredictedType basePrediction = m_graph[node.child2()].prediction();
924             if (!(basePrediction & PredictInt32) && basePrediction) {
925                 node.op = Nop;
926                 m_graph.clearAndDerefChild1(node);
927                 m_graph.clearAndDerefChild2(node);
928                 m_graph.clearAndDerefChild3(node);
929                 node.setRefCount(0);
930             }
931             break;
932         }
933         case GetByVal:
934         case StringCharAt:
935         case StringCharCodeAt: {
936             if (node.child3() != NoNode && m_graph[node.child3()].op == Nop)
937                 node.children.fixed.child3 = NoNode;
938             break;
939         }
940         default:
941             break;
942         }
943
944 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
945         printf("\n");
946 #endif
947     }
948     
949     void fixup()
950     {
951 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
952         printf("Performing Fixup\n");
953 #endif
954         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
955             fixupNode(m_graph[m_compileIndex]);
956     }
957     
958     NodeIndex canonicalize(NodeIndex nodeIndex)
959     {
960         if (nodeIndex == NoNode)
961             return NoNode;
962         
963         if (m_graph[nodeIndex].op == ValueToNumber)
964             nodeIndex = m_graph[nodeIndex].child1();
965         
966         if (m_graph[nodeIndex].op == ValueToInt32)
967             nodeIndex = m_graph[nodeIndex].child1();
968         
969         return nodeIndex;
970     }
971     
972     // Computes where the search for a candidate for CSE should start. Don't call
973     // this directly; call startIndex() instead as it does logging in debug mode.
974     NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
975     {
976         const unsigned limit = 300;
977         
978         NodeIndex start = m_start;
979         if (m_compileIndex - start > limit)
980             start = m_compileIndex - limit;
981         
982         ASSERT(start >= m_start);
983         
984         NodeIndex child = canonicalize(child1);
985         if (child == NoNode)
986             return start;
987         
988         if (start < child)
989             start = child;
990         
991         child = canonicalize(child2);
992         if (child == NoNode)
993             return start;
994         
995         if (start < child)
996             start = child;
997         
998         child = canonicalize(child3);
999         if (child == NoNode)
1000             return start;
1001         
1002         if (start < child)
1003             start = child;
1004         
1005         return start;
1006     }
1007     
1008     NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
1009     {
1010         NodeIndex result = computeStartIndexForChildren(child1, child2, child3);
1011 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1012         printf("  lookback %u: ", result);
1013 #endif
1014         return result;
1015     }
1016     
1017     NodeIndex startIndex()
1018     {
1019         Node& node = m_graph[m_compileIndex];
1020         return startIndexForChildren(node.child1(), node.child2(), node.child3());
1021     }
1022     
1023     NodeIndex endIndexForPureCSE()
1024     {
1025         NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask];
1026         if (result == NoNode)
1027             result = 0;
1028         else
1029             result++;
1030         ASSERT(result <= m_compileIndex);
1031 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1032         printf("  limit %u: ", result);
1033 #endif
1034         return result;
1035     }
1036     
1037     NodeIndex pureCSE(Node& node)
1038     {
1039         NodeIndex child1 = canonicalize(node.child1());
1040         NodeIndex child2 = canonicalize(node.child2());
1041         NodeIndex child3 = canonicalize(node.child3());
1042         
1043         NodeIndex start = startIndex();
1044         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
1045             Node& otherNode = m_graph[index];
1046             if (node.op != otherNode.op)
1047                 continue;
1048             
1049             if (node.arithNodeFlagsForCompare() != otherNode.arithNodeFlagsForCompare())
1050                 continue;
1051             
1052             NodeIndex otherChild = canonicalize(otherNode.child1());
1053             if (otherChild == NoNode)
1054                 return index;
1055             if (otherChild != child1)
1056                 continue;
1057             
1058             otherChild = canonicalize(otherNode.child2());
1059             if (otherChild == NoNode)
1060                 return index;
1061             if (otherChild != child2)
1062                 continue;
1063             
1064             otherChild = canonicalize(otherNode.child3());
1065             if (otherChild == NoNode)
1066                 return index;
1067             if (otherChild != child3)
1068                 continue;
1069             
1070             return index;
1071         }
1072         return NoNode;
1073     }
1074     
1075     bool isPredictedNumerical(Node& node)
1076     {
1077         PredictedType left = m_graph[node.child1()].prediction();
1078         PredictedType right = m_graph[node.child2()].prediction();
1079         return isNumberPrediction(left) && isNumberPrediction(right);
1080     }
1081     
1082     bool logicalNotIsPure(Node& node)
1083     {
1084         PredictedType prediction = m_graph[node.child1()].prediction();
1085         return isBooleanPrediction(prediction) || !prediction;
1086     }
1087     
1088     bool byValIsPure(Node& node)
1089     {
1090         return m_graph[node.child2()].shouldSpeculateInteger()
1091             && ((node.op == PutByVal || node.op == PutByValAlias)
1092                 ? isActionableMutableArrayPrediction(m_graph[node.child1()].prediction())
1093                 : isActionableArrayPrediction(m_graph[node.child1()].prediction()));
1094     }
1095     
1096     bool clobbersWorld(NodeIndex nodeIndex)
1097     {
1098         Node& node = m_graph[nodeIndex];
1099         if (node.op & NodeClobbersWorld)
1100             return true;
1101         if (!(node.op & NodeMightClobber))
1102             return false;
1103         switch (node.op) {
1104         case ValueAdd:
1105         case CompareLess:
1106         case CompareLessEq:
1107         case CompareGreater:
1108         case CompareGreaterEq:
1109         case CompareEq:
1110             return !isPredictedNumerical(node);
1111         case LogicalNot:
1112             return !logicalNotIsPure(node);
1113         case GetByVal:
1114             return !byValIsPure(node);
1115         default:
1116             ASSERT_NOT_REACHED();
1117             return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
1118         }
1119     }
1120     
1121     NodeIndex impureCSE(Node& node)
1122     {
1123         NodeIndex child1 = canonicalize(node.child1());
1124         NodeIndex child2 = canonicalize(node.child2());
1125         NodeIndex child3 = canonicalize(node.child3());
1126         
1127         NodeIndex start = startIndex();
1128         for (NodeIndex index = m_compileIndex; index-- > start;) {
1129             Node& otherNode = m_graph[index];
1130             if (node.op == otherNode.op
1131                 && node.arithNodeFlagsForCompare() == otherNode.arithNodeFlagsForCompare()) {
1132                 NodeIndex otherChild = canonicalize(otherNode.child1());
1133                 if (otherChild == NoNode)
1134                     return index;
1135                 if (otherChild == child1) {
1136                     otherChild = canonicalize(otherNode.child2());
1137                     if (otherChild == NoNode)
1138                         return index;
1139                     if (otherChild == child2) {
1140                         otherChild = canonicalize(otherNode.child3());
1141                         if (otherChild == NoNode)
1142                             return index;
1143                         if (otherChild == child3)
1144                             return index;
1145                     }
1146                 }
1147             }
1148             if (clobbersWorld(index))
1149                 break;
1150         }
1151         return NoNode;
1152     }
1153     
1154     NodeIndex globalVarLoadElimination(unsigned varNumber, JSGlobalObject* globalObject)
1155     {
1156         NodeIndex start = startIndexForChildren();
1157         for (NodeIndex index = m_compileIndex; index-- > start;) {
1158             Node& node = m_graph[index];
1159             switch (node.op) {
1160             case GetGlobalVar:
1161                 if (node.varNumber() == varNumber && m_codeBlock->globalObjectFor(node.codeOrigin) == globalObject)
1162                     return index;
1163                 break;
1164             case PutGlobalVar:
1165                 if (node.varNumber() == varNumber && m_codeBlock->globalObjectFor(node.codeOrigin) == globalObject)
1166                     return node.child1();
1167                 break;
1168             default:
1169                 break;
1170             }
1171             if (clobbersWorld(index))
1172                 break;
1173         }
1174         return NoNode;
1175     }
1176     
1177     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
1178     {
1179         NodeIndex start = startIndexForChildren(child1, child2);
1180         for (NodeIndex index = m_compileIndex; index-- > start;) {
1181             Node& node = m_graph[index];
1182             switch (node.op) {
1183             case GetByVal:
1184                 if (!byValIsPure(node))
1185                     return NoNode;
1186                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
1187                     return index;
1188                 break;
1189             case PutByVal:
1190             case PutByValAlias:
1191                 if (!byValIsPure(node))
1192                     return NoNode;
1193                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
1194                     return node.child3();
1195                 // We must assume that the PutByVal will clobber the location we're getting from.
1196                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
1197                 // different type than the GetByVal, then we know that they won't clobber each other.
1198                 return NoNode;
1199             case PutStructure:
1200             case PutByOffset:
1201                 // GetByVal currently always speculates that it's accessing an
1202                 // array with an integer index, which means that it's impossible
1203                 // for a structure change or a put to property storage to affect
1204                 // the GetByVal.
1205                 break;
1206             case ArrayPush:
1207                 // A push cannot affect previously existing elements in the array.
1208                 break;
1209             default:
1210                 if (clobbersWorld(index))
1211                     return NoNode;
1212                 break;
1213             }
1214         }
1215         return NoNode;
1216     }
1217
1218     bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
1219     {
1220         NodeIndex start = startIndexForChildren(child1);
1221         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
1222             Node& node = m_graph[index];
1223             if (node.op == CheckFunction && node.child1() == child1 && node.function() == function)
1224                 return true;
1225         }
1226         return false;
1227     }
1228
1229     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
1230     {
1231         NodeIndex start = startIndexForChildren(child1);
1232         for (NodeIndex index = m_compileIndex; index-- > start;) {
1233             Node& node = m_graph[index];
1234             switch (node.op) {
1235             case CheckStructure:
1236                 if (node.child1() == child1
1237                     && structureSet.isSupersetOf(node.structureSet()))
1238                     return true;
1239                 break;
1240                 
1241             case PutStructure:
1242                 if (node.child1() == child1
1243                     && structureSet.contains(node.structureTransitionData().newStructure))
1244                     return true;
1245                 if (structureSet.contains(node.structureTransitionData().previousStructure))
1246                     return false;
1247                 break;
1248                 
1249             case PutByOffset:
1250                 // Setting a property cannot change the structure.
1251                 break;
1252                 
1253             case PutByVal:
1254             case PutByValAlias:
1255                 if (byValIsPure(node)) {
1256                     // If PutByVal speculates that it's accessing an array with an
1257                     // integer index, then it's impossible for it to cause a structure
1258                     // change.
1259                     break;
1260                 }
1261                 return false;
1262                 
1263             default:
1264                 if (clobbersWorld(index))
1265                     return false;
1266                 break;
1267             }
1268         }
1269         return false;
1270     }
1271     
1272     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
1273     {
1274         NodeIndex start = startIndexForChildren(child1);
1275         for (NodeIndex index = m_compileIndex; index-- > start;) {
1276             Node& node = m_graph[index];
1277             switch (node.op) {
1278             case GetByOffset:
1279                 if (node.child1() == child1
1280                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
1281                     return index;
1282                 break;
1283                 
1284             case PutByOffset:
1285                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
1286                     if (node.child2() == child1)
1287                         return node.child3();
1288                     return NoNode;
1289                 }
1290                 break;
1291                 
1292             case PutStructure:
1293                 // Changing the structure cannot change the outcome of a property get.
1294                 break;
1295                 
1296             case PutByVal:
1297             case PutByValAlias:
1298                 if (byValIsPure(node)) {
1299                     // If PutByVal speculates that it's accessing an array with an
1300                     // integer index, then it's impossible for it to cause a structure
1301                     // change.
1302                     break;
1303                 }
1304                 return NoNode;
1305                 
1306             default:
1307                 if (clobbersWorld(index))
1308                     return NoNode;
1309                 break;
1310             }
1311         }
1312         return NoNode;
1313     }
1314     
1315     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
1316     {
1317         NodeIndex start = startIndexForChildren(child1);
1318         for (NodeIndex index = m_compileIndex; index-- > start;) {
1319             Node& node = m_graph[index];
1320             switch (node.op) {
1321             case GetPropertyStorage:
1322                 if (node.child1() == child1)
1323                     return index;
1324                 break;
1325                 
1326             case PutByOffset:
1327             case PutStructure:
1328                 // Changing the structure or putting to the storage cannot
1329                 // change the property storage pointer.
1330                 break;
1331                 
1332             case PutByVal:
1333             case PutByValAlias:
1334                 if (byValIsPure(node)) {
1335                     // If PutByVal speculates that it's accessing an array with an
1336                     // integer index, then it's impossible for it to cause a structure
1337                     // change.
1338                     break;
1339                 }
1340                 return NoNode;
1341                 
1342             default:
1343                 if (clobbersWorld(index))
1344                     return NoNode;
1345                 break;
1346             }
1347         }
1348         return NoNode;
1349     }
1350
1351     NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
1352     {
1353         NodeIndex start = startIndexForChildren(child1);
1354         for (NodeIndex index = m_compileIndex; index-- > start;) {
1355             Node& node = m_graph[index];
1356             switch (node.op) {
1357             case GetIndexedPropertyStorage: {
1358                 PredictedType basePrediction = m_graph[node.child2()].prediction();
1359                 bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
1360                 if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
1361                     return index;
1362                 break;
1363             }
1364
1365             case PutByOffset:
1366             case PutStructure:
1367                 // Changing the structure or putting to the storage cannot
1368                 // change the property storage pointer.
1369                 break;
1370                 
1371             case PutByValAlias:
1372                 // PutByValAlias can't change the indexed storage pointer
1373                 break;
1374                 
1375             case PutByVal:
1376                 if (isFixedIndexedStorageObjectPrediction(m_graph[node.child1()].prediction()) && byValIsPure(node))
1377                     break;
1378                 return NoNode;
1379
1380             default:
1381                 if (clobbersWorld(index))
1382                     return NoNode;
1383                 break;
1384             }
1385         }
1386         return NoNode;
1387     }
1388     
1389     NodeIndex getScopeChainLoadElimination(unsigned depth)
1390     {
1391         NodeIndex start = startIndexForChildren();
1392         for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
1393             Node& node = m_graph[index];
1394             if (node.op == GetScopeChain
1395                 && node.scopeChainDepth() == depth)
1396                 return index;
1397         }
1398         return NoNode;
1399     }
1400     
1401     void performSubstitution(NodeIndex& child, bool addRef = true)
1402     {
1403         // Check if this operand is actually unused.
1404         if (child == NoNode)
1405             return;
1406         
1407         // Check if there is any replacement.
1408         NodeIndex replacement = m_replacements[child];
1409         if (replacement == NoNode)
1410             return;
1411         
1412         child = replacement;
1413         
1414         // There is definitely a replacement. Assert that the replacement does not
1415         // have a replacement.
1416         ASSERT(m_replacements[child] == NoNode);
1417         
1418         if (addRef)
1419             m_graph[child].ref();
1420     }
1421     
1422     void setReplacement(NodeIndex replacement)
1423     {
1424         if (replacement == NoNode)
1425             return;
1426         
1427         // Be safe. Don't try to perform replacements if the predictions don't
1428         // agree.
1429         if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
1430             return;
1431         
1432 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1433         printf("   Replacing @%u -> @%u", m_compileIndex, replacement);
1434 #endif
1435         
1436         Node& node = m_graph[m_compileIndex];
1437         node.op = Phantom;
1438         node.setRefCount(1);
1439         
1440         // At this point we will eliminate all references to this node.
1441         m_replacements[m_compileIndex] = replacement;
1442     }
1443     
1444     void eliminate()
1445     {
1446 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1447         printf("   Eliminating @%u", m_compileIndex);
1448 #endif
1449         
1450         Node& node = m_graph[m_compileIndex];
1451         ASSERT(node.refCount() == 1);
1452         ASSERT(node.mustGenerate());
1453         node.op = Phantom;
1454     }
1455     
1456     void performNodeCSE(Node& node)
1457     {
1458         bool shouldGenerate = node.shouldGenerate();
1459
1460         if (node.op & NodeHasVarArgs) {
1461             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1462                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
1463         } else {
1464             performSubstitution(node.children.fixed.child1, shouldGenerate);
1465             performSubstitution(node.children.fixed.child2, shouldGenerate);
1466             performSubstitution(node.children.fixed.child3, shouldGenerate);
1467         }
1468         
1469         if (!shouldGenerate)
1470             return;
1471         
1472 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1473         printf("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op), m_compileIndex);
1474 #endif
1475         
1476         // NOTE: there are some nodes that we deliberately don't CSE even though we
1477         // probably could, like StrCat and ToPrimitive. That's because there is no
1478         // evidence that doing CSE on these nodes would result in a performance
1479         // progression. Hence considering these nodes in CSE would just mean that this
1480         // code does more work with no win. Of course, we may want to reconsider this,
1481         // since StrCat is trivially CSE-able. It's not trivially doable for
1482         // ToPrimitive, but we could change that with some speculations if we really
1483         // needed to.
1484         
1485         switch (node.op) {
1486         
1487         // Handle the pure nodes. These nodes never have any side-effects.
1488         case BitAnd:
1489         case BitOr:
1490         case BitXor:
1491         case BitRShift:
1492         case BitLShift:
1493         case BitURShift:
1494         case ArithAdd:
1495         case ArithSub:
1496         case ArithMul:
1497         case ArithMod:
1498         case ArithDiv:
1499         case ArithAbs:
1500         case ArithMin:
1501         case ArithMax:
1502         case ArithSqrt:
1503         case GetByteArrayLength:
1504         case GetInt8ArrayLength:
1505         case GetInt16ArrayLength:
1506         case GetInt32ArrayLength:
1507         case GetUint8ArrayLength:
1508         case GetUint16ArrayLength:
1509         case GetUint32ArrayLength:
1510         case GetFloat32ArrayLength:
1511         case GetFloat64ArrayLength:
1512         case GetCallee:
1513         case GetStringLength:
1514         case StringCharAt:
1515         case StringCharCodeAt:
1516             setReplacement(pureCSE(node));
1517             break;
1518             
1519         case GetArrayLength:
1520             setReplacement(impureCSE(node));
1521             break;
1522             
1523         case GetScopeChain:
1524             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
1525             break;
1526
1527         // Handle nodes that are conditionally pure: these are pure, and can
1528         // be CSE'd, so long as the prediction is the one we want.
1529         case ValueAdd:
1530         case CompareLess:
1531         case CompareLessEq:
1532         case CompareGreater:
1533         case CompareGreaterEq:
1534         case CompareEq: {
1535             if (isPredictedNumerical(node)) {
1536                 NodeIndex replacementIndex = pureCSE(node);
1537                 if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
1538                     setReplacement(replacementIndex);
1539             }
1540             break;
1541         }
1542             
1543         case LogicalNot: {
1544             if (logicalNotIsPure(node)) {
1545                 NodeIndex replacementIndex = pureCSE(node);
1546                 if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex]))
1547                     setReplacement(replacementIndex);
1548             }
1549             break;
1550         }
1551             
1552         // Finally handle heap accesses. These are not quite pure, but we can still
1553         // optimize them provided that some subtle conditions are met.
1554         case GetGlobalVar:
1555             setReplacement(globalVarLoadElimination(node.varNumber(), m_codeBlock->globalObjectFor(node.codeOrigin)));
1556             break;
1557             
1558         case GetByVal:
1559             if (byValIsPure(node))
1560                 setReplacement(getByValLoadElimination(node.child1(), node.child2()));
1561             break;
1562             
1563         case PutByVal:
1564             if (byValIsPure(node) && getByValLoadElimination(node.child1(), node.child2()) != NoNode)
1565                 node.op = PutByValAlias;
1566             break;
1567             
1568         case CheckStructure:
1569             if (checkStructureLoadElimination(node.structureSet(), node.child1()))
1570                 eliminate();
1571             break;
1572
1573         case CheckFunction:
1574             if (checkFunctionElimination(node.function(), node.child1()))
1575                 eliminate();
1576             break;
1577                 
1578         case GetIndexedPropertyStorage: {
1579             PredictedType basePrediction = m_graph[node.child2()].prediction();
1580             bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
1581             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1(), nodeHasIntegerIndexPrediction));
1582             break;
1583         }
1584
1585         case GetPropertyStorage:
1586             setReplacement(getPropertyStorageLoadElimination(node.child1()));
1587             break;
1588
1589         case GetByOffset:
1590             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1()));
1591             break;
1592             
1593         default:
1594             // do nothing.
1595             break;
1596         }
1597         
1598         m_lastSeen[node.op & NodeIdMask] = m_compileIndex;
1599 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1600         printf("\n");
1601 #endif
1602     }
1603     
1604     void performBlockCSE(BasicBlock& block)
1605     {
1606         m_start = block.begin;
1607         NodeIndex end = block.end;
1608         for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex)
1609             performNodeCSE(m_graph[m_compileIndex]);
1610     }
1611     
1612     void localCSE()
1613     {
1614 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1615         printf("Performing local CSE:");
1616 #endif
1617         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
1618             performBlockCSE(*m_graph.m_blocks[block]);
1619     }
1620     
1621     void allocateVirtualRegisters()
1622     {
1623 #if DFG_ENABLE(DEBUG_VERBOSE)
1624         printf("Preserved vars: ");
1625         m_graph.m_preservedVars.dump(stdout);
1626         printf("\n");
1627 #endif
1628         ScoreBoard scoreBoard(m_graph, m_graph.m_preservedVars);
1629         unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
1630         for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
1631             Node& node = m_graph[i];
1632         
1633             if (!node.shouldGenerate())
1634                 continue;
1635         
1636             // GetLocal nodes are effectively phi nodes in the graph, referencing
1637             // results from prior blocks.
1638             if (node.op != GetLocal) {
1639                 // First, call use on all of the current node's children, then
1640                 // allocate a VirtualRegister for this node. We do so in this
1641                 // order so that if a child is on its last use, and a
1642                 // VirtualRegister is freed, then it may be reused for node.
1643                 if (node.op & NodeHasVarArgs) {
1644                     for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1645                         scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
1646                 } else {
1647                     scoreBoard.use(node.child1());
1648                     scoreBoard.use(node.child2());
1649                     scoreBoard.use(node.child3());
1650                 }
1651             }
1652
1653             if (!node.hasResult())
1654                 continue;
1655
1656             node.setVirtualRegister(scoreBoard.allocate());
1657             // 'mustGenerate' nodes have their useCount artificially elevated,
1658             // call use now to account for this.
1659             if (node.mustGenerate())
1660                 scoreBoard.use(i);
1661         }
1662
1663         // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
1664         // for the function (and checked for on entry). Since we perform a new and
1665         // different allocation of temporaries, more registers may now be required.
1666         unsigned calleeRegisters = scoreBoard.highWatermark() + m_graph.m_parameterSlots;
1667         if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
1668             m_codeBlock->m_numCalleeRegisters = calleeRegisters;
1669 #if DFG_ENABLE(DEBUG_VERBOSE)
1670         printf("Num callee registers: %u\n", calleeRegisters);
1671 #endif
1672     }
1673     
1674     void performBlockCFA(AbstractState& state, BlockIndex blockIndex)
1675     {
1676         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
1677         if (!block->cfaShouldRevisit)
1678             return;
1679 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1680         printf("   Block #%u (bc#%u):\n", blockIndex, block->bytecodeBegin);
1681 #endif
1682         state.beginBasicBlock(block);
1683 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1684         printf("      head vars: ");
1685         dumpOperands(block->valuesAtHead, stdout);
1686         printf("\n");
1687 #endif
1688         for (NodeIndex nodeIndex = block->begin; nodeIndex < block->end; ++nodeIndex) {
1689             if (!m_graph[nodeIndex].shouldGenerate())
1690                 continue;
1691 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1692             printf("      %s @%u: ", Graph::opName(m_graph[nodeIndex].op), nodeIndex);
1693             state.dump(stdout);
1694             printf("\n");
1695 #endif
1696             if (!state.execute(nodeIndex))
1697                 break;
1698         }
1699 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1700         printf("      tail regs: ");
1701         state.dump(stdout);
1702         printf("\n");
1703 #endif
1704         m_changed |= state.endBasicBlock(AbstractState::MergeToSuccessors);
1705 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1706         printf("      tail vars: ");
1707         dumpOperands(block->valuesAtTail, stdout);
1708         printf("\n");
1709 #endif
1710     }
1711     
1712     void performForwardCFA(AbstractState& state)
1713     {
1714 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1715         printf("CFA [%u]\n", ++m_count);
1716 #endif
1717         
1718         for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block)
1719             performBlockCFA(state, block);
1720     }
1721     
1722     void globalCFA()
1723     {
1724 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1725         m_count = 0;
1726 #endif
1727         
1728         // This implements a pseudo-worklist-based forward CFA, except that the visit order
1729         // of blocks is the bytecode program order (which is nearly topological), and
1730         // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
1731         // is set to true. This is likely to balance the efficiency properties of both
1732         // worklist-based and forward fixpoint-based approaches. Like a worklist-based
1733         // approach, it won't visit code if it's meaningless to do so (nothing changed at
1734         // the head of the block or the predecessors have not been visited). Like a forward
1735         // fixpoint-based approach, it has a high probability of only visiting a block
1736         // after all predecessors have been visited. Only loops will cause this analysis to
1737         // revisit blocks, and the amount of revisiting is proportional to loop depth.
1738         
1739         AbstractState::initialize(m_graph);
1740         
1741         AbstractState state(m_codeBlock, m_graph);
1742         
1743         do {
1744             m_changed = false;
1745             performForwardCFA(state);
1746         } while (m_changed);
1747     }
1748     
1749     Graph& m_graph;
1750     JSGlobalData& m_globalData;
1751     CodeBlock* m_codeBlock;
1752     CodeBlock* m_profiledBlock;
1753     
1754     NodeIndex m_start;
1755     NodeIndex m_compileIndex;
1756     
1757 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1758     unsigned m_count;
1759 #endif
1760     
1761     bool m_changed;
1762
1763     Vector<NodeIndex, 16> m_replacements;
1764     FixedArray<NodeIndex, LastNodeId> m_lastSeen;
1765 };
1766
1767 void propagate(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
1768 {
1769     ASSERT(codeBlock);
1770     CodeBlock* profiledBlock = codeBlock->alternative();
1771     ASSERT(profiledBlock);
1772     
1773     Propagator propagator(graph, *globalData, codeBlock, profiledBlock);
1774     propagator.fixpoint();
1775     
1776 }
1777
1778 } } // namespace JSC::DFG
1779
1780 #endif // ENABLE(DFG_JIT)
1781