04bcf19b2315f5f028a32378a60fd764c467bf54
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCSEPhase.cpp
1 /*
2  * Copyright (C) 2011, 2012 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 "DFGCSEPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32 #include "DFGPhase.h"
33
34 namespace JSC { namespace DFG {
35
36 class CSEPhase : public Phase {
37 public:
38     CSEPhase(Graph& graph)
39         : Phase(graph, "common subexpression elimination")
40     {
41         // Replacements are used to implement local common subexpression elimination.
42         m_replacements.resize(m_graph.size());
43         
44         for (unsigned i = 0; i < m_graph.size(); ++i)
45             m_replacements[i] = NoNode;
46     }
47     
48     bool run()
49     {
50         m_changed = false;
51         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
52             performBlockCSE(m_graph.m_blocks[block].get());
53         return m_changed;
54     }
55     
56 private:
57     
58     NodeIndex canonicalize(NodeIndex nodeIndex)
59     {
60         if (nodeIndex == NoNode)
61             return NoNode;
62         
63         if (m_graph[nodeIndex].op() == ValueToInt32)
64             nodeIndex = m_graph[nodeIndex].child1().index();
65         
66         return nodeIndex;
67     }
68     NodeIndex canonicalize(Edge nodeUse)
69     {
70         return canonicalize(nodeUse.indexUnchecked());
71     }
72     
73     unsigned endIndexForPureCSE()
74     {
75         unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
76         if (result == UINT_MAX)
77             result = 0;
78         else
79             result++;
80         ASSERT(result <= m_indexInBlock);
81 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
82         dataLog("  limit %u: ", result);
83 #endif
84         return result;
85     }
86     
87     NodeIndex pureCSE(Node& node)
88     {
89         NodeIndex child1 = canonicalize(node.child1());
90         NodeIndex child2 = canonicalize(node.child2());
91         NodeIndex child3 = canonicalize(node.child3());
92         
93         for (unsigned i = endIndexForPureCSE(); i--;) {
94             NodeIndex index = m_currentBlock->at(i);
95             if (index == child1 || index == child2 || index == child3)
96                 break;
97
98             Node& otherNode = m_graph[index];
99             if (!otherNode.shouldGenerate())
100                 continue;
101             
102             if (node.op() != otherNode.op())
103                 continue;
104             
105             if (node.arithNodeFlags() != otherNode.arithNodeFlags())
106                 continue;
107             
108             NodeIndex otherChild = canonicalize(otherNode.child1());
109             if (otherChild == NoNode)
110                 return index;
111             if (otherChild != child1)
112                 continue;
113             
114             otherChild = canonicalize(otherNode.child2());
115             if (otherChild == NoNode)
116                 return index;
117             if (otherChild != child2)
118                 continue;
119             
120             otherChild = canonicalize(otherNode.child3());
121             if (otherChild == NoNode)
122                 return index;
123             if (otherChild != child3)
124                 continue;
125             
126             return index;
127         }
128         return NoNode;
129     }
130     
131     NodeIndex constantCSE(Node& node)
132     {
133         for (unsigned i = endIndexForPureCSE(); i--;) {
134             NodeIndex index = m_currentBlock->at(i);
135             Node& otherNode = m_graph[index];
136             if (otherNode.op() != JSConstant)
137                 continue;
138             
139             if (otherNode.constantNumber() != node.constantNumber())
140                 continue;
141             
142             return index;
143         }
144         return NoNode;
145     }
146     
147     NodeIndex weakConstantCSE(Node& node)
148     {
149         for (unsigned i = endIndexForPureCSE(); i--;) {
150             NodeIndex index = m_currentBlock->at(i);
151             Node& otherNode = m_graph[index];
152             if (otherNode.op() != WeakJSConstant)
153                 continue;
154             
155             if (otherNode.weakConstant() != node.weakConstant())
156                 continue;
157             
158             return index;
159         }
160         return NoNode;
161     }
162     
163     NodeIndex getArrayLengthElimination(NodeIndex array)
164     {
165         for (unsigned i = m_indexInBlock; i--;) {
166             NodeIndex index = m_currentBlock->at(i);
167             Node& node = m_graph[index];
168             if (!node.shouldGenerate())
169                 continue;
170             switch (node.op()) {
171             case GetArrayLength:
172                 if (node.child1() == array)
173                     return index;
174                 break;
175                 
176             case PutByVal:
177                 if (!m_graph.byValIsPure(node))
178                     return NoNode;
179                 if (node.arrayMode().mayStoreToHole())
180                     return NoNode;
181                 break;
182                 
183             default:
184                 if (m_graph.clobbersWorld(index))
185                     return NoNode;
186             }
187         }
188         return NoNode;
189     }
190     
191     NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
192     {
193         for (unsigned i = m_indexInBlock; i--;) {
194             NodeIndex index = m_currentBlock->at(i);
195             Node& node = m_graph[index];
196             if (!node.shouldGenerate())
197                 continue;
198             switch (node.op()) {
199             case GetGlobalVar:
200                 if (node.registerPointer() == registerPointer)
201                     return index;
202                 break;
203             case PutGlobalVar:
204                 if (node.registerPointer() == registerPointer)
205                     return node.child1().index();
206                 break;
207             default:
208                 break;
209             }
210             if (m_graph.clobbersWorld(index))
211                 break;
212         }
213         return NoNode;
214     }
215     
216     NodeIndex scopedVarLoadElimination(unsigned scopeChainDepth, unsigned varNumber)
217     {
218         for (unsigned i = m_indexInBlock; i--;) {
219             NodeIndex index = m_currentBlock->at(i);
220             Node& node = m_graph[index];
221             if (!node.shouldGenerate())
222                 continue;
223             switch (node.op()) {
224             case GetScopedVar: {
225                 Node& getScopeRegisters = m_graph[node.child1()];
226                 Node& getScope = m_graph[getScopeRegisters.child1()];
227                 if (getScope.scopeChainDepth() == scopeChainDepth && node.varNumber() == varNumber)
228                     return index;
229                 break;
230             } 
231             case PutScopedVar: {
232                 Node& getScope = m_graph[node.child1()];
233                 if (getScope.scopeChainDepth() == scopeChainDepth && node.varNumber() == varNumber)
234                     return node.child3().index();
235                 break;
236             }
237             default:
238                 break;
239             }
240             if (m_graph.clobbersWorld(index))
241                 break;
242         }
243         return NoNode;
244     }
245     
246     bool globalVarWatchpointElimination(WriteBarrier<Unknown>* registerPointer)
247     {
248         for (unsigned i = m_indexInBlock; i--;) {
249             NodeIndex index = m_currentBlock->at(i);
250             Node& node = m_graph[index];
251             if (!node.shouldGenerate())
252                 continue;
253             switch (node.op()) {
254             case GlobalVarWatchpoint:
255                 if (node.registerPointer() == registerPointer)
256                     return true;
257                 break;
258             case PutGlobalVar:
259                 if (node.registerPointer() == registerPointer)
260                     return false;
261                 break;
262             default:
263                 break;
264             }
265             if (m_graph.clobbersWorld(index))
266                 break;
267         }
268         return false;
269     }
270     
271     NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
272     {
273         for (unsigned i = m_indexInBlock; i--;) {
274             NodeIndex index = m_currentBlock->at(i);
275             Node& node = m_graph[index];
276             if (!node.shouldGenerate())
277                 continue;
278             switch (node.op()) {
279             case PutGlobalVar:
280             case PutGlobalVarCheck:
281                 if (node.registerPointer() == registerPointer)
282                     return index;
283                 break;
284                 
285             case GetGlobalVar:
286                 if (node.registerPointer() == registerPointer)
287                     return NoNode;
288                 break;
289                 
290             default:
291                 break;
292             }
293             if (m_graph.clobbersWorld(index) || node.canExit())
294                 return NoNode;
295         }
296         return NoNode;
297     }
298     
299     NodeIndex scopedVarStoreElimination(unsigned scopeChainDepth, unsigned varNumber)
300     {
301         for (unsigned i = m_indexInBlock; i--;) {
302             NodeIndex index = m_currentBlock->at(i);
303             Node& node = m_graph[index];
304             if (!node.shouldGenerate())
305                 continue;
306             switch (node.op()) {
307             case PutScopedVar: {
308                 Node& getScope = m_graph[node.child1()];
309                 if (getScope.scopeChainDepth() == scopeChainDepth && node.varNumber() == varNumber)
310                     return index;
311                 break;
312             }
313                 
314             case GetScopedVar: {
315                 Node& getScopeRegisters = m_graph[node.child1()];
316                 Node& getScope = m_graph[getScopeRegisters.child1()];
317                 if (getScope.scopeChainDepth() == scopeChainDepth && node.varNumber() == varNumber)
318                     return NoNode;
319                 break;
320             }
321
322             default:
323                 break;
324             }
325             if (m_graph.clobbersWorld(index) || node.canExit())
326                 return NoNode;
327         }
328         return NoNode;
329     }
330     
331     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
332     {
333         for (unsigned i = m_indexInBlock; i--;) {
334             NodeIndex index = m_currentBlock->at(i);
335             if (index == child1 || index == canonicalize(child2)) 
336                 break;
337
338             Node& node = m_graph[index];
339             if (!node.shouldGenerate())
340                 continue;
341             switch (node.op()) {
342             case GetByVal:
343                 if (!m_graph.byValIsPure(node))
344                     return NoNode;
345                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
346                     return index;
347                 break;
348             case PutByVal:
349             case PutByValAlias: {
350                 if (!m_graph.byValIsPure(node))
351                     return NoNode;
352                 if (m_graph.varArgChild(node, 0) == child1 && canonicalize(m_graph.varArgChild(node, 1)) == canonicalize(child2))
353                     return m_graph.varArgChild(node, 2).index();
354                 // We must assume that the PutByVal will clobber the location we're getting from.
355                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
356                 // different type than the GetByVal, then we know that they won't clobber each other.
357                 return NoNode;
358             }
359             case PutStructure:
360             case PutByOffset:
361                 // GetByVal currently always speculates that it's accessing an
362                 // array with an integer index, which means that it's impossible
363                 // for a structure change or a put to property storage to affect
364                 // the GetByVal.
365                 break;
366             default:
367                 if (m_graph.clobbersWorld(index))
368                     return NoNode;
369                 break;
370             }
371         }
372         return NoNode;
373     }
374
375     bool checkFunctionElimination(JSCell* function, NodeIndex child1)
376     {
377         for (unsigned i = endIndexForPureCSE(); i--;) {
378             NodeIndex index = m_currentBlock->at(i);
379             if (index == child1) 
380                 break;
381
382             Node& node = m_graph[index];
383             if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
384                 return true;
385         }
386         return false;
387     }
388
389     bool checkStructureElimination(const StructureSet& structureSet, NodeIndex child1)
390     {
391         for (unsigned i = m_indexInBlock; i--;) {
392             NodeIndex index = m_currentBlock->at(i);
393             if (index == child1) 
394                 break;
395
396             Node& node = m_graph[index];
397             if (!node.shouldGenerate())
398                 continue;
399             switch (node.op()) {
400             case CheckStructure:
401             case ForwardCheckStructure:
402                 if (node.child1() == child1
403                     && structureSet.isSupersetOf(node.structureSet()))
404                     return true;
405                 break;
406                 
407             case StructureTransitionWatchpoint:
408             case ForwardStructureTransitionWatchpoint:
409                 if (node.child1() == child1
410                     && structureSet.contains(node.structure()))
411                     return true;
412                 break;
413                 
414             case PutStructure:
415                 if (node.child1() == child1
416                     && structureSet.contains(node.structureTransitionData().newStructure))
417                     return true;
418                 if (structureSet.contains(node.structureTransitionData().previousStructure))
419                     return false;
420                 break;
421                 
422             case PutByOffset:
423                 // Setting a property cannot change the structure.
424                 break;
425                 
426             case PutByVal:
427             case PutByValAlias:
428                 if (m_graph.byValIsPure(node)) {
429                     // If PutByVal speculates that it's accessing an array with an
430                     // integer index, then it's impossible for it to cause a structure
431                     // change.
432                     break;
433                 }
434                 return false;
435                 
436             case Arrayify:
437             case ArrayifyToStructure:
438                 // We could check if the arrayification could affect our structures.
439                 // But that seems like it would take Effort.
440                 return false;
441                 
442             default:
443                 if (m_graph.clobbersWorld(index))
444                     return false;
445                 break;
446             }
447         }
448         return false;
449     }
450     
451     bool structureTransitionWatchpointElimination(Structure* structure, NodeIndex child1)
452     {
453         for (unsigned i = m_indexInBlock; i--;) {
454             NodeIndex index = m_currentBlock->at(i);
455             if (index == child1) 
456                 break;
457
458             Node& node = m_graph[index];
459             if (!node.shouldGenerate())
460                 continue;
461             switch (node.op()) {
462             case CheckStructure:
463             case ForwardCheckStructure:
464                 if (node.child1() == child1
465                     && node.structureSet().containsOnly(structure))
466                     return true;
467                 break;
468                 
469             case PutStructure:
470                 ASSERT(node.structureTransitionData().previousStructure != structure);
471                 break;
472                 
473             case PutByOffset:
474                 // Setting a property cannot change the structure.
475                 break;
476                 
477             case PutByVal:
478             case PutByValAlias:
479                 if (m_graph.byValIsPure(node)) {
480                     // If PutByVal speculates that it's accessing an array with an
481                     // integer index, then it's impossible for it to cause a structure
482                     // change.
483                     break;
484                 }
485                 return false;
486                 
487             case StructureTransitionWatchpoint:
488             case ForwardStructureTransitionWatchpoint:
489                 if (node.structure() == structure && node.child1() == child1)
490                     return true;
491                 break;
492                 
493             case Arrayify:
494             case ArrayifyToStructure:
495                 // We could check if the arrayification could affect our structures.
496                 // But that seems like it would take Effort.
497                 return false;
498                 
499             default:
500                 if (m_graph.clobbersWorld(index))
501                     return false;
502                 break;
503             }
504         }
505         return false;
506     }
507     
508     NodeIndex putStructureStoreElimination(NodeIndex child1)
509     {
510         for (unsigned i = m_indexInBlock; i--;) {
511             NodeIndex index = m_currentBlock->at(i);
512             if (index == child1)
513                 break;
514             Node& node = m_graph[index];
515             if (!node.shouldGenerate())
516                 continue;
517             switch (node.op()) {
518             case CheckStructure:
519             case ForwardCheckStructure:
520                 return NoNode;
521                 
522             case PhantomPutStructure:
523                 if (node.child1() == child1) // No need to retrace our steps.
524                     return NoNode;
525                 break;
526                 
527             case PutStructure:
528                 if (node.child1() == child1)
529                     return index;
530                 break;
531                 
532             // PutStructure needs to execute if we GC. Hence this needs to
533             // be careful with respect to nodes that GC.
534             case CreateArguments:
535             case TearOffArguments:
536             case NewFunctionNoCheck:
537             case NewFunction:
538             case NewFunctionExpression:
539             case CreateActivation:
540             case TearOffActivation:
541             case StrCat:
542             case ToPrimitive:
543             case NewRegexp:
544             case NewArrayBuffer:
545             case NewArray:
546             case NewObject:
547             case CreateThis:
548             case AllocatePropertyStorage:
549             case ReallocatePropertyStorage:
550                 return NoNode;
551                 
552             default:
553                 break;
554             }
555             if (m_graph.clobbersWorld(index) || node.canExit())
556                 return NoNode;
557         }
558         return NoNode;
559     }
560     
561     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
562     {
563         for (unsigned i = m_indexInBlock; i--;) {
564             NodeIndex index = m_currentBlock->at(i);
565             if (index == child1)
566                 break;
567
568             Node& node = m_graph[index];
569             if (!node.shouldGenerate())
570                 continue;
571             switch (node.op()) {
572             case GetByOffset:
573                 if (node.child1() == child1
574                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
575                     return index;
576                 break;
577                 
578             case PutByOffset:
579                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
580                     if (node.child1() == child1) // Must be same property storage.
581                         return node.child3().index();
582                     return NoNode;
583                 }
584                 break;
585                 
586             case PutStructure:
587                 // Changing the structure cannot change the outcome of a property get.
588                 break;
589                 
590             case PutByVal:
591             case PutByValAlias:
592                 if (m_graph.byValIsPure(node)) {
593                     // If PutByVal speculates that it's accessing an array with an
594                     // integer index, then it's impossible for it to cause a structure
595                     // change.
596                     break;
597                 }
598                 return NoNode;
599                 
600             default:
601                 if (m_graph.clobbersWorld(index))
602                     return NoNode;
603                 break;
604             }
605         }
606         return NoNode;
607     }
608     
609     NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
610     {
611         for (unsigned i = m_indexInBlock; i--;) {
612             NodeIndex index = m_currentBlock->at(i);
613             if (index == child1)
614                 break;
615
616             Node& node = m_graph[index];
617             if (!node.shouldGenerate())
618                 continue;
619             switch (node.op()) {
620             case GetByOffset:
621                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
622                     return NoNode;
623                 break;
624                 
625             case PutByOffset:
626                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
627                     if (node.child1() == child1) // Must be same property storage.
628                         return index;
629                     return NoNode;
630                 }
631                 break;
632                 
633             case PutByVal:
634             case PutByValAlias:
635             case GetByVal:
636                 if (m_graph.byValIsPure(node)) {
637                     // If PutByVal speculates that it's accessing an array with an
638                     // integer index, then it's impossible for it to cause a structure
639                     // change.
640                     break;
641                 }
642                 return NoNode;
643                 
644             default:
645                 if (m_graph.clobbersWorld(index))
646                     return NoNode;
647                 break;
648             }
649             if (node.canExit())
650                 return NoNode;
651         }
652         return NoNode;
653     }
654     
655     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
656     {
657         for (unsigned i = m_indexInBlock; i--;) {
658             NodeIndex index = m_currentBlock->at(i);
659             if (index == child1) 
660                 break;
661
662             Node& node = m_graph[index];
663             if (!node.shouldGenerate())
664                 continue;
665             switch (node.op()) {
666             case GetButterfly:
667                 if (node.child1() == child1)
668                     return index;
669                 break;
670
671             case AllocatePropertyStorage:
672             case ReallocatePropertyStorage:
673                 // If we can cheaply prove this is a change to our object's storage, we
674                 // can optimize and use its result.
675                 if (node.child1() == child1)
676                     return index;
677                 // Otherwise, we currently can't prove that this doesn't change our object's
678                 // storage, so we conservatively assume that it may change the storage
679                 // pointer of any object, including ours.
680                 return NoNode;
681                 
682             case PutByOffset:
683             case PutStructure:
684                 // Changing the structure or putting to the storage cannot
685                 // change the property storage pointer.
686                 break;
687                 
688             case PutByVal:
689             case PutByValAlias:
690                 if (m_graph.byValIsPure(node)) {
691                     // If PutByVal speculates that it's accessing an array with an
692                     // integer index, then it's impossible for it to cause a structure
693                     // change.
694                     break;
695                 }
696                 return NoNode;
697                 
698             case Arrayify:
699             case ArrayifyToStructure:
700                 // We could check if the arrayification could affect our butterfly.
701                 // But that seems like it would take Effort.
702                 return NoNode;
703                 
704             default:
705                 if (m_graph.clobbersWorld(index))
706                     return NoNode;
707                 break;
708             }
709         }
710         return NoNode;
711     }
712     
713     bool checkArrayElimination(NodeIndex child1, ArrayMode arrayMode)
714     {
715         for (unsigned i = m_indexInBlock; i--;) {
716             NodeIndex index = m_currentBlock->at(i);
717             if (index == child1) 
718                 break;
719
720             Node& node = m_graph[index];
721             if (!node.shouldGenerate())
722                 continue;
723             switch (node.op()) {
724             case PutByOffset:
725             case PutStructure:
726                 // Changing the structure or putting to the storage cannot
727                 // change the property storage pointer.
728                 break;
729                 
730             case CheckArray:
731                 if (node.child1() == child1 && node.arrayMode() == arrayMode)
732                     return true;
733                 break;
734                 
735             case Arrayify:
736             case ArrayifyToStructure:
737                 // We could check if the arrayification could affect our array.
738                 // But that seems like it would take Effort.
739                 return false;
740                 
741             default:
742                 if (m_graph.clobbersWorld(index))
743                     return false;
744                 break;
745             }
746         }
747         return false;
748     }
749
750     NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, ArrayMode arrayMode)
751     {
752         for (unsigned i = m_indexInBlock; i--;) {
753             NodeIndex index = m_currentBlock->at(i);
754             if (index == child1) 
755                 break;
756
757             Node& node = m_graph[index];
758             if (!node.shouldGenerate())
759                 continue;
760             switch (node.op()) {
761             case GetIndexedPropertyStorage: {
762                 if (node.child1() == child1 && node.arrayMode() == arrayMode)
763                     return index;
764                 break;
765             }
766
767             case PutByOffset:
768             case PutStructure:
769                 // Changing the structure or putting to the storage cannot
770                 // change the property storage pointer.
771                 break;
772                 
773             default:
774                 if (m_graph.clobbersWorld(index))
775                     return NoNode;
776                 break;
777             }
778         }
779         return NoNode;
780     }
781     
782     NodeIndex getScopeLoadElimination(unsigned depth)
783     {
784         for (unsigned i = endIndexForPureCSE(); i--;) {
785             NodeIndex index = m_currentBlock->at(i);
786             Node& node = m_graph[index];
787             if (!node.shouldGenerate())
788                 continue;
789             if (node.op() == GetScope
790                 && node.scopeChainDepth() == depth)
791                 return index;
792         }
793         return NoNode;
794     }
795
796     NodeIndex getScopeRegistersLoadElimination(unsigned depth)
797     {
798         for (unsigned i = endIndexForPureCSE(); i--;) {
799             NodeIndex index = m_currentBlock->at(i);
800             Node& node = m_graph[index];
801             if (!node.shouldGenerate())
802                 continue;
803             if (node.op() == GetScopeRegisters
804                 && m_graph[node.scope()].scopeChainDepth() == depth)
805                 return index;
806         }
807         return NoNode;
808     }
809     
810     NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp, bool careAboutClobbering)
811     {
812         relevantLocalOp = NoNode;
813         
814         for (unsigned i = m_indexInBlock; i--;) {
815             NodeIndex index = m_currentBlock->at(i);
816             Node& node = m_graph[index];
817             if (!node.shouldGenerate())
818                 continue;
819             switch (node.op()) {
820             case GetLocal:
821                 if (node.local() == local) {
822                     relevantLocalOp = index;
823                     return index;
824                 }
825                 break;
826                 
827             case GetLocalUnlinked:
828                 if (node.unlinkedLocal() == local) {
829                     relevantLocalOp = index;
830                     return index;
831                 }
832                 break;
833                 
834             case SetLocal:
835                 if (node.local() == local) {
836                     relevantLocalOp = index;
837                     return node.child1().index();
838                 }
839                 break;
840                 
841             default:
842                 if (careAboutClobbering && m_graph.clobbersWorld(index))
843                     return NoNode;
844                 break;
845             }
846         }
847         return NoNode;
848     }
849     
850     struct SetLocalStoreEliminationResult {
851         SetLocalStoreEliminationResult()
852             : mayBeAccessed(false)
853             , mayExit(false)
854             , mayClobberWorld(false)
855         {
856         }
857         
858         bool mayBeAccessed;
859         bool mayExit;
860         bool mayClobberWorld;
861     };
862     SetLocalStoreEliminationResult setLocalStoreElimination(
863         VirtualRegister local, NodeIndex expectedNodeIndex)
864     {
865         SetLocalStoreEliminationResult result;
866         for (unsigned i = m_indexInBlock; i--;) {
867             NodeIndex index = m_currentBlock->at(i);
868             Node& node = m_graph[index];
869             if (!node.shouldGenerate())
870                 continue;
871             switch (node.op()) {
872             case GetLocal:
873             case Flush:
874                 if (node.local() == local)
875                     result.mayBeAccessed = true;
876                 break;
877                 
878             case GetLocalUnlinked:
879                 if (node.unlinkedLocal() == local)
880                     result.mayBeAccessed = true;
881                 break;
882                 
883             case SetLocal: {
884                 if (node.local() != local)
885                     break;
886                 if (index != expectedNodeIndex)
887                     result.mayBeAccessed = true;
888                 if (m_graph[index].refCount() > 1)
889                     result.mayBeAccessed = true;
890                 return result;
891             }
892                 
893             case GetScope:
894             case GetScopeRegisters:
895                 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
896                     result.mayBeAccessed = true;
897                 break;
898                 
899             case CheckArgumentsNotCreated:
900             case GetMyArgumentsLength:
901             case GetMyArgumentsLengthSafe:
902                 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
903                     result.mayBeAccessed = true;
904                 break;
905                 
906             case GetMyArgumentByVal:
907             case GetMyArgumentByValSafe:
908                 result.mayBeAccessed = true;
909                 break;
910                 
911             case GetByVal:
912                 // If this is accessing arguments then it's potentially accessing locals.
913                 if (m_graph[node.child1()].shouldSpeculateArguments())
914                     result.mayBeAccessed = true;
915                 break;
916                 
917             case CreateArguments:
918             case TearOffActivation:
919             case TearOffArguments:
920                 // If an activation is being torn off then it means that captured variables
921                 // are live. We could be clever here and check if the local qualifies as an
922                 // argument register. But that seems like it would buy us very little since
923                 // any kind of tear offs are rare to begin with.
924                 result.mayBeAccessed = true;
925                 break;
926                 
927             default:
928                 break;
929             }
930             result.mayExit |= node.canExit();
931             result.mayClobberWorld |= m_graph.clobbersWorld(index);
932         }
933         ASSERT_NOT_REACHED();
934         // Be safe in release mode.
935         result.mayBeAccessed = true;
936         return result;
937     }
938     
939     void performSubstitution(Edge& child, bool addRef = true)
940     {
941         // Check if this operand is actually unused.
942         if (!child)
943             return;
944         
945         // Check if there is any replacement.
946         NodeIndex replacement = m_replacements[child.index()];
947         if (replacement == NoNode)
948             return;
949         
950         child.setIndex(replacement);
951         
952         // There is definitely a replacement. Assert that the replacement does not
953         // have a replacement.
954         ASSERT(m_replacements[child.index()] == NoNode);
955         
956         if (addRef)
957             m_graph[child].ref();
958     }
959     
960     enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
961     bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
962     {
963         if (replacement == NoNode)
964             return false;
965         
966         // Be safe. Don't try to perform replacements if the predictions don't
967         // agree.
968         if (predictionHandlingMode == RequireSamePrediction
969             && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
970             return false;
971         
972 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
973         dataLog("   Replacing @%u -> @%u", m_compileIndex, replacement);
974 #endif
975         
976         Node& node = m_graph[m_compileIndex];
977         node.setOpAndDefaultFlags(Phantom);
978         node.setRefCount(1);
979         
980         // At this point we will eliminate all references to this node.
981         m_replacements[m_compileIndex] = replacement;
982         
983         m_changed = true;
984         
985         return true;
986     }
987     
988     void eliminate()
989     {
990 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
991         dataLog("   Eliminating @%u", m_compileIndex);
992 #endif
993         
994         Node& node = m_graph[m_compileIndex];
995         ASSERT(node.refCount() == 1);
996         ASSERT(node.mustGenerate());
997         node.setOpAndDefaultFlags(Phantom);
998         
999         m_changed = true;
1000     }
1001     
1002     void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
1003     {
1004         if (nodeIndex == NoNode)
1005             return;
1006         Node& node = m_graph[nodeIndex];
1007         if (node.refCount() != 1)
1008             return;
1009         ASSERT(node.mustGenerate());
1010         node.setOpAndDefaultFlags(phantomType);
1011         
1012         m_changed = true;
1013     }
1014     
1015     void performNodeCSE(Node& node)
1016     {
1017         bool shouldGenerate = node.shouldGenerate();
1018
1019         if (node.flags() & NodeHasVarArgs) {
1020             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1021                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
1022         } else {
1023             performSubstitution(node.children.child1(), shouldGenerate);
1024             performSubstitution(node.children.child2(), shouldGenerate);
1025             performSubstitution(node.children.child3(), shouldGenerate);
1026         }
1027         
1028         if (!shouldGenerate)
1029             return;
1030         
1031 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1032         dataLog("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
1033 #endif
1034         
1035         // NOTE: there are some nodes that we deliberately don't CSE even though we
1036         // probably could, like StrCat and ToPrimitive. That's because there is no
1037         // evidence that doing CSE on these nodes would result in a performance
1038         // progression. Hence considering these nodes in CSE would just mean that this
1039         // code does more work with no win. Of course, we may want to reconsider this,
1040         // since StrCat is trivially CSE-able. It's not trivially doable for
1041         // ToPrimitive, but we could change that with some speculations if we really
1042         // needed to.
1043         
1044         switch (node.op()) {
1045         
1046         case Identity:
1047             setReplacement(node.child1().index());
1048             break;
1049             
1050         // Handle the pure nodes. These nodes never have any side-effects.
1051         case BitAnd:
1052         case BitOr:
1053         case BitXor:
1054         case BitRShift:
1055         case BitLShift:
1056         case BitURShift:
1057         case ArithAdd:
1058         case ArithSub:
1059         case ArithNegate:
1060         case ArithMul:
1061         case ArithMod:
1062         case ArithDiv:
1063         case ArithAbs:
1064         case ArithMin:
1065         case ArithMax:
1066         case ArithSqrt:
1067         case GetCallee:
1068         case StringCharAt:
1069         case StringCharCodeAt:
1070         case Int32ToDouble:
1071         case IsUndefined:
1072         case IsBoolean:
1073         case IsNumber:
1074         case IsString:
1075         case IsObject:
1076         case IsFunction:
1077         case DoubleAsInt32:
1078         case LogicalNot:
1079             setReplacement(pureCSE(node));
1080             break;
1081             
1082         case GetLocal: {
1083             VariableAccessData* variableAccessData = node.variableAccessData();
1084             if (!variableAccessData->isCaptured())
1085                 break;
1086             NodeIndex relevantLocalOp;
1087             NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
1088             if (relevantLocalOp == NoNode)
1089                 break;
1090             if (m_graph[relevantLocalOp].op() != GetLocalUnlinked
1091                 && m_graph[relevantLocalOp].variableAccessData() != variableAccessData)
1092                 break;
1093             NodeIndex phiIndex = node.child1().index();
1094             if (!setReplacement(possibleReplacement))
1095                 break;
1096             // If the GetLocal we replaced used to refer to a SetLocal, then it now
1097             // should refer to the child of the SetLocal instead.
1098             if (m_graph[phiIndex].op() == SetLocal) {
1099                 ASSERT(node.child1().index() == phiIndex);
1100                 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
1101             }
1102             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
1103                 variableAccessData->local());
1104             if (oldTailIndex == m_compileIndex) {
1105                 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
1106                     relevantLocalOp;
1107                 
1108                 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
1109                 // make sure that the GetLocalUnlinked is now linked.
1110                 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
1111                     m_graph[relevantLocalOp].setOp(GetLocal);
1112                     m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
1113                     m_graph.ref(phiIndex);
1114                 }
1115             }
1116             m_changed = true;
1117             break;
1118         }
1119             
1120         case GetLocalUnlinked: {
1121             NodeIndex relevantLocalOpIgnored;
1122             setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored, true));
1123             break;
1124         }
1125             
1126         case Flush: {
1127             VariableAccessData* variableAccessData = node.variableAccessData();
1128             VirtualRegister local = variableAccessData->local();
1129             NodeIndex replacementIndex = node.child1().index();
1130             Node& replacement = m_graph[replacementIndex];
1131             if (replacement.op() != SetLocal)
1132                 break;
1133             ASSERT(replacement.variableAccessData() == variableAccessData);
1134             // FIXME: We should be able to remove SetLocals that can exit; we just need
1135             // to replace them with appropriate type checks.
1136             if (m_graph.m_fixpointState == FixpointNotConverged) {
1137                 // Need to be conservative at this time; if the SetLocal has any chance of performing
1138                 // any speculations then we cannot do anything.
1139                 if (variableAccessData->isCaptured()) {
1140                     // Captured SetLocals never speculate and hence never exit.
1141                 } else {
1142                     if (variableAccessData->shouldUseDoubleFormat())
1143                         break;
1144                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
1145                     if (isInt32Speculation(prediction))
1146                         break;
1147                     if (isArraySpeculation(prediction))
1148                         break;
1149                     if (isBooleanSpeculation(prediction))
1150                         break;
1151                 }
1152             } else {
1153                 if (replacement.canExit())
1154                     break;
1155             }
1156             SetLocalStoreEliminationResult result =
1157                 setLocalStoreElimination(local, replacementIndex);
1158             if (result.mayBeAccessed || result.mayClobberWorld)
1159                 break;
1160             ASSERT(replacement.op() == SetLocal);
1161             ASSERT(replacement.refCount() == 1);
1162             ASSERT(replacement.shouldGenerate());
1163             // FIXME: Investigate using mayExit as a further optimization.
1164             node.setOpAndDefaultFlags(Phantom);
1165             NodeIndex dataNodeIndex = replacement.child1().index();
1166             ASSERT(m_graph[dataNodeIndex].hasResult());
1167             m_graph.clearAndDerefChild1(node);
1168             node.children.child1() = Edge(dataNodeIndex);
1169             m_graph.ref(dataNodeIndex);
1170             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
1171             if (oldTailIndex == m_compileIndex)
1172                 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
1173             m_changed = true;
1174             break;
1175         }
1176             
1177         case JSConstant:
1178             // This is strange, but necessary. Some phases will convert nodes to constants,
1179             // which may result in duplicated constants. We use CSE to clean this up.
1180             setReplacement(constantCSE(node), AllowPredictionMismatch);
1181             break;
1182             
1183         case WeakJSConstant:
1184             // FIXME: have CSE for weak constants against strong constants and vice-versa.
1185             setReplacement(weakConstantCSE(node));
1186             break;
1187             
1188         case GetArrayLength:
1189             setReplacement(getArrayLengthElimination(node.child1().index()));
1190             break;
1191
1192         case GetScope:
1193             setReplacement(getScopeLoadElimination(node.scopeChainDepth()));
1194             break;
1195
1196         case GetScopeRegisters:
1197             setReplacement(getScopeRegistersLoadElimination(m_graph[node.scope()].scopeChainDepth()));
1198             break;
1199
1200         // Handle nodes that are conditionally pure: these are pure, and can
1201         // be CSE'd, so long as the prediction is the one we want.
1202         case ValueAdd:
1203         case CompareLess:
1204         case CompareLessEq:
1205         case CompareGreater:
1206         case CompareGreaterEq:
1207         case CompareEq: {
1208             if (m_graph.isPredictedNumerical(node)) {
1209                 NodeIndex replacementIndex = pureCSE(node);
1210                 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
1211                     setReplacement(replacementIndex);
1212             }
1213             break;
1214         }
1215             
1216         // Finally handle heap accesses. These are not quite pure, but we can still
1217         // optimize them provided that some subtle conditions are met.
1218         case GetGlobalVar:
1219             setReplacement(globalVarLoadElimination(node.registerPointer()));
1220             break;
1221
1222         case GetScopedVar: {
1223             Node& getScopeRegisters = m_graph[node.child1()];
1224             Node& getScope = m_graph[getScopeRegisters.child1()];
1225             setReplacement(scopedVarLoadElimination(getScope.scopeChainDepth(), node.varNumber()));
1226             break;
1227         }
1228
1229         case GlobalVarWatchpoint:
1230             if (globalVarWatchpointElimination(node.registerPointer()))
1231                 eliminate();
1232             break;
1233             
1234         case PutGlobalVar:
1235         case PutGlobalVarCheck:
1236             if (m_graph.m_fixpointState == FixpointNotConverged)
1237                 break;
1238             eliminate(globalVarStoreElimination(node.registerPointer()));
1239             break;
1240             
1241         case PutScopedVar: {
1242             if (m_graph.m_fixpointState == FixpointNotConverged)
1243                 break;
1244             Node& getScope = m_graph[node.child1()];
1245             eliminate(scopedVarStoreElimination(getScope.scopeChainDepth(), node.varNumber()));
1246             break;
1247         }
1248
1249         case GetByVal:
1250             if (m_graph.byValIsPure(node))
1251                 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
1252             break;
1253             
1254         case PutByVal: {
1255             Edge child1 = m_graph.varArgChild(node, 0);
1256             Edge child2 = m_graph.varArgChild(node, 1);
1257             if (node.arrayMode().canCSEStorage()) {
1258                 NodeIndex nodeIndex = getByValLoadElimination(child1.index(), child2.index());
1259                 if (nodeIndex == NoNode)
1260                     break;
1261                 node.setOp(PutByValAlias);
1262             }
1263             break;
1264         }
1265             
1266         case CheckStructure:
1267         case ForwardCheckStructure:
1268             if (checkStructureElimination(node.structureSet(), node.child1().index()))
1269                 eliminate();
1270             break;
1271             
1272         case StructureTransitionWatchpoint:
1273         case ForwardStructureTransitionWatchpoint:
1274             if (structureTransitionWatchpointElimination(node.structure(), node.child1().index()))
1275                 eliminate();
1276             break;
1277             
1278         case PutStructure:
1279             if (m_graph.m_fixpointState == FixpointNotConverged)
1280                 break;
1281             eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1282             break;
1283
1284         case CheckFunction:
1285             if (checkFunctionElimination(node.function(), node.child1().index()))
1286                 eliminate();
1287             break;
1288                 
1289         case CheckArray:
1290             if (checkArrayElimination(node.child1().index(), node.arrayMode()))
1291                 eliminate();
1292             break;
1293             
1294         case GetIndexedPropertyStorage: {
1295             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), node.arrayMode()));
1296             break;
1297         }
1298
1299         case GetButterfly:
1300             setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1301             break;
1302
1303         case GetByOffset:
1304             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1305             break;
1306             
1307         case PutByOffset:
1308             if (m_graph.m_fixpointState == FixpointNotConverged)
1309                 break;
1310             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1311             break;
1312             
1313         default:
1314             // do nothing.
1315             break;
1316         }
1317         
1318         m_lastSeen[node.op()] = m_indexInBlock;
1319 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1320         dataLog("\n");
1321 #endif
1322     }
1323     
1324     void performBlockCSE(BasicBlock* block)
1325     {
1326         if (!block)
1327             return;
1328         if (!block->isReachable)
1329             return;
1330         
1331         m_currentBlock = block;
1332         for (unsigned i = 0; i < LastNodeType; ++i)
1333             m_lastSeen[i] = UINT_MAX;
1334
1335         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1336             m_compileIndex = block->at(m_indexInBlock);
1337             performNodeCSE(m_graph[m_compileIndex]);
1338         }
1339     }
1340     
1341     BasicBlock* m_currentBlock;
1342     NodeIndex m_compileIndex;
1343     unsigned m_indexInBlock;
1344     Vector<NodeIndex, 16> m_replacements;
1345     FixedArray<unsigned, LastNodeType> m_lastSeen;
1346     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1347 };
1348
1349 bool performCSE(Graph& graph)
1350 {
1351     SamplingRegion samplingRegion("DFG CSE Phase");
1352     return runPhase<CSEPhase>(graph);
1353 }
1354
1355 } } // namespace JSC::DFG
1356
1357 #endif // ENABLE(DFG_JIT)
1358
1359