828a31125ae493171b50a74da001f71272c352fe
[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 #include <wtf/FastBitVector.h>
34
35 namespace JSC { namespace DFG {
36
37 class CSEPhase : public Phase {
38 public:
39     CSEPhase(Graph& graph)
40         : Phase(graph, "common subexpression elimination")
41     {
42         // Replacements are used to implement local common subexpression elimination.
43         m_replacements.resize(m_graph.size());
44         
45         for (unsigned i = 0; i < m_graph.size(); ++i)
46             m_replacements[i] = NoNode;
47         
48         m_relevantToOSR.resize(m_graph.size());
49     }
50     
51     bool run()
52     {
53         m_changed = false;
54         
55         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
56             performBlockCSE(m_graph.m_blocks[block].get());
57         
58         return m_changed;
59     }
60     
61 private:
62     
63     NodeIndex canonicalize(NodeIndex nodeIndex)
64     {
65         if (nodeIndex == NoNode)
66             return NoNode;
67         
68         if (m_graph[nodeIndex].op() == ValueToInt32)
69             nodeIndex = m_graph[nodeIndex].child1().index();
70         
71         return nodeIndex;
72     }
73     NodeIndex canonicalize(Edge nodeUse)
74     {
75         return canonicalize(nodeUse.indexUnchecked());
76     }
77     
78     unsigned endIndexForPureCSE()
79     {
80         unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
81         if (result == UINT_MAX)
82             result = 0;
83         else
84             result++;
85         ASSERT(result <= m_indexInBlock);
86 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
87         dataLogF("  limit %u: ", result);
88 #endif
89         return result;
90     }
91     
92     NodeIndex pureCSE(Node& node)
93     {
94         NodeIndex child1 = canonicalize(node.child1());
95         NodeIndex child2 = canonicalize(node.child2());
96         NodeIndex child3 = canonicalize(node.child3());
97         
98         for (unsigned i = endIndexForPureCSE(); i--;) {
99             NodeIndex index = m_currentBlock->at(i);
100             if (index == child1 || index == child2 || index == child3)
101                 break;
102
103             Node& otherNode = m_graph[index];
104             if (!otherNode.shouldGenerate())
105                 continue;
106             
107             if (node.op() != otherNode.op())
108                 continue;
109             
110             if (node.arithNodeFlags() != otherNode.arithNodeFlags())
111                 continue;
112             
113             NodeIndex otherChild = canonicalize(otherNode.child1());
114             if (otherChild == NoNode)
115                 return index;
116             if (otherChild != child1)
117                 continue;
118             
119             otherChild = canonicalize(otherNode.child2());
120             if (otherChild == NoNode)
121                 return index;
122             if (otherChild != child2)
123                 continue;
124             
125             otherChild = canonicalize(otherNode.child3());
126             if (otherChild == NoNode)
127                 return index;
128             if (otherChild != child3)
129                 continue;
130             
131             return index;
132         }
133         return NoNode;
134     }
135     
136     NodeIndex constantCSE(Node& node)
137     {
138         for (unsigned i = endIndexForPureCSE(); i--;) {
139             NodeIndex index = m_currentBlock->at(i);
140             Node& otherNode = m_graph[index];
141             if (otherNode.op() != JSConstant)
142                 continue;
143             
144             if (otherNode.constantNumber() != node.constantNumber())
145                 continue;
146             
147             return index;
148         }
149         return NoNode;
150     }
151     
152     NodeIndex weakConstantCSE(Node& node)
153     {
154         for (unsigned i = endIndexForPureCSE(); i--;) {
155             NodeIndex index = m_currentBlock->at(i);
156             Node& otherNode = m_graph[index];
157             if (otherNode.op() != WeakJSConstant)
158                 continue;
159             
160             if (otherNode.weakConstant() != node.weakConstant())
161                 continue;
162             
163             return index;
164         }
165         return NoNode;
166     }
167     
168     NodeIndex getArrayLengthElimination(NodeIndex array)
169     {
170         for (unsigned i = m_indexInBlock; i--;) {
171             NodeIndex index = m_currentBlock->at(i);
172             Node& node = m_graph[index];
173             if (!node.shouldGenerate())
174                 continue;
175             switch (node.op()) {
176             case GetArrayLength:
177                 if (node.child1() == array)
178                     return index;
179                 break;
180                 
181             case PutByVal:
182                 if (!m_graph.byValIsPure(node))
183                     return NoNode;
184                 if (node.arrayMode().mayStoreToHole())
185                     return NoNode;
186                 break;
187                 
188             default:
189                 if (m_graph.clobbersWorld(index))
190                     return NoNode;
191             }
192         }
193         return NoNode;
194     }
195     
196     NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
197     {
198         for (unsigned i = m_indexInBlock; i--;) {
199             NodeIndex index = m_currentBlock->at(i);
200             Node& node = m_graph[index];
201             if (!node.shouldGenerate())
202                 continue;
203             switch (node.op()) {
204             case GetGlobalVar:
205                 if (node.registerPointer() == registerPointer)
206                     return index;
207                 break;
208             case PutGlobalVar:
209                 if (node.registerPointer() == registerPointer)
210                     return node.child1().index();
211                 break;
212             default:
213                 break;
214             }
215             if (m_graph.clobbersWorld(index))
216                 break;
217         }
218         return NoNode;
219     }
220     
221     NodeIndex scopedVarLoadElimination(NodeIndex registers, unsigned varNumber)
222     {
223         for (unsigned i = m_indexInBlock; i--;) {
224             NodeIndex index = m_currentBlock->at(i);
225             Node& node = m_graph[index];
226             if (!node.shouldGenerate())
227                 continue;
228             switch (node.op()) {
229             case GetScopedVar: {
230                 if (node.child1() == registers && node.varNumber() == varNumber)
231                     return index;
232                 break;
233             } 
234             case PutScopedVar: {
235                 if (node.child2() == registers && node.varNumber() == varNumber)
236                     return node.child3().index();
237                 break;
238             }
239             default:
240                 break;
241             }
242             if (m_graph.clobbersWorld(index))
243                 break;
244         }
245         return NoNode;
246     }
247     
248     bool globalVarWatchpointElimination(WriteBarrier<Unknown>* registerPointer)
249     {
250         for (unsigned i = m_indexInBlock; i--;) {
251             NodeIndex index = m_currentBlock->at(i);
252             Node& node = m_graph[index];
253             if (!node.shouldGenerate())
254                 continue;
255             switch (node.op()) {
256             case GlobalVarWatchpoint:
257                 if (node.registerPointer() == registerPointer)
258                     return true;
259                 break;
260             case PutGlobalVar:
261                 if (node.registerPointer() == registerPointer)
262                     return false;
263                 break;
264             default:
265                 break;
266             }
267             if (m_graph.clobbersWorld(index))
268                 break;
269         }
270         return false;
271     }
272     
273     NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
274     {
275         for (unsigned i = m_indexInBlock; i--;) {
276             NodeIndex index = m_currentBlock->at(i);
277             Node& node = m_graph[index];
278             if (!node.shouldGenerate())
279                 continue;
280             switch (node.op()) {
281             case PutGlobalVar:
282             case PutGlobalVarCheck:
283                 if (node.registerPointer() == registerPointer)
284                     return index;
285                 break;
286                 
287             case GetGlobalVar:
288                 if (node.registerPointer() == registerPointer)
289                     return NoNode;
290                 break;
291                 
292             default:
293                 break;
294             }
295             if (m_graph.clobbersWorld(index) || node.canExit())
296                 return NoNode;
297         }
298         return NoNode;
299     }
300     
301     NodeIndex scopedVarStoreElimination(NodeIndex scope, NodeIndex registers, unsigned varNumber)
302     {
303         for (unsigned i = m_indexInBlock; i--;) {
304             NodeIndex index = m_currentBlock->at(i);
305             Node& node = m_graph[index];
306             if (!node.shouldGenerate())
307                 continue;
308             switch (node.op()) {
309             case PutScopedVar: {
310                 if (node.child1() == scope && node.child2() == registers && node.varNumber() == varNumber)
311                     return index;
312                 break;
313             }
314                 
315             case GetScopedVar: {
316                 // Let's be conservative.
317                 if (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 getMyScopeLoadElimination()
783     {
784         for (unsigned i = m_indexInBlock; i--;) {
785             NodeIndex index = m_currentBlock->at(i);
786             Node& node = m_graph[index];
787             if (!node.shouldGenerate())
788                 continue;
789             switch (node.op()) {
790             case CreateActivation:
791                 // This may cause us to return a different scope.
792                 return NoNode;
793             case GetMyScope:
794                 return index;
795             default:
796                 break;
797             }
798         }
799         return NoNode;
800     }
801     
802     NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp, bool careAboutClobbering)
803     {
804         relevantLocalOp = NoNode;
805         
806         for (unsigned i = m_indexInBlock; i--;) {
807             NodeIndex index = m_currentBlock->at(i);
808             Node& node = m_graph[index];
809             if (!node.shouldGenerate())
810                 continue;
811             switch (node.op()) {
812             case GetLocal:
813                 if (node.local() == local) {
814                     relevantLocalOp = index;
815                     return index;
816                 }
817                 break;
818                 
819             case GetLocalUnlinked:
820                 if (node.unlinkedLocal() == local) {
821                     relevantLocalOp = index;
822                     return index;
823                 }
824                 break;
825                 
826             case SetLocal:
827                 if (node.local() == local) {
828                     relevantLocalOp = index;
829                     return node.child1().index();
830                 }
831                 break;
832                 
833             default:
834                 if (careAboutClobbering && m_graph.clobbersWorld(index))
835                     return NoNode;
836                 break;
837             }
838         }
839         return NoNode;
840     }
841     
842     struct SetLocalStoreEliminationResult {
843         SetLocalStoreEliminationResult()
844             : mayBeAccessed(false)
845             , mayExit(false)
846             , mayClobberWorld(false)
847         {
848         }
849         
850         bool mayBeAccessed;
851         bool mayExit;
852         bool mayClobberWorld;
853     };
854     SetLocalStoreEliminationResult setLocalStoreElimination(
855         VirtualRegister local, NodeIndex expectedNodeIndex)
856     {
857         SetLocalStoreEliminationResult result;
858         for (unsigned i = m_indexInBlock; i--;) {
859             NodeIndex index = m_currentBlock->at(i);
860             Node& node = m_graph[index];
861             if (!node.shouldGenerate())
862                 continue;
863             switch (node.op()) {
864             case GetLocal:
865             case Flush:
866                 if (node.local() == local)
867                     result.mayBeAccessed = true;
868                 break;
869                 
870             case GetLocalUnlinked:
871                 if (node.unlinkedLocal() == local)
872                     result.mayBeAccessed = true;
873                 break;
874                 
875             case SetLocal: {
876                 if (node.local() != local)
877                     break;
878                 if (index != expectedNodeIndex)
879                     result.mayBeAccessed = true;
880                 if (m_graph[index].refCount() > 1)
881                     result.mayBeAccessed = true;
882                 return result;
883             }
884                 
885             case GetMyScope:
886             case SkipTopScope:
887             case GetScopeRegisters:
888                 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
889                     result.mayBeAccessed = true;
890                 break;
891                 
892             case CheckArgumentsNotCreated:
893             case GetMyArgumentsLength:
894             case GetMyArgumentsLengthSafe:
895                 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
896                     result.mayBeAccessed = true;
897                 break;
898                 
899             case GetMyArgumentByVal:
900             case GetMyArgumentByValSafe:
901                 result.mayBeAccessed = true;
902                 break;
903                 
904             case GetByVal:
905                 // If this is accessing arguments then it's potentially accessing locals.
906                 if (m_graph[node.child1()].shouldSpeculateArguments())
907                     result.mayBeAccessed = true;
908                 break;
909                 
910             case CreateArguments:
911             case TearOffActivation:
912             case TearOffArguments:
913                 // If an activation is being torn off then it means that captured variables
914                 // are live. We could be clever here and check if the local qualifies as an
915                 // argument register. But that seems like it would buy us very little since
916                 // any kind of tear offs are rare to begin with.
917                 result.mayBeAccessed = true;
918                 break;
919                 
920             default:
921                 break;
922             }
923             result.mayExit |= node.canExit();
924             result.mayClobberWorld |= m_graph.clobbersWorld(index);
925         }
926         ASSERT_NOT_REACHED();
927         // Be safe in release mode.
928         result.mayBeAccessed = true;
929         return result;
930     }
931     
932     void performSubstitution(Edge& child, bool addRef = true)
933     {
934         // Check if this operand is actually unused.
935         if (!child)
936             return;
937         
938         // Check if there is any replacement.
939         NodeIndex replacement = m_replacements[child.index()];
940         if (replacement == NoNode)
941             return;
942         
943         child.setIndex(replacement);
944         
945         // There is definitely a replacement. Assert that the replacement does not
946         // have a replacement.
947         ASSERT(m_replacements[child.index()] == NoNode);
948         
949         if (addRef)
950             m_graph.ref(child);
951     }
952     
953     void eliminateIrrelevantPhantomChildren(Node& node)
954     {
955         ASSERT(node.op() == Phantom);
956         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
957             Edge edge = node.children.child(i);
958             if (!edge)
959                 continue;
960             if (m_relevantToOSR.get(edge.index()))
961                 continue;
962             
963 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
964             dataLog("   Eliminating edge @", m_compileIndex, " -> @", edge.index());
965 #endif
966             m_graph.deref(edge);
967             node.children.removeEdgeFromBag(i--);
968             m_changed = true;
969         }
970     }
971     
972     enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
973     bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
974     {
975         if (replacement == NoNode)
976             return false;
977         
978         // Be safe. Don't try to perform replacements if the predictions don't
979         // agree.
980         if (predictionHandlingMode == RequireSamePrediction
981             && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
982             return false;
983         
984 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
985         dataLogF("   Replacing @%u -> @%u", m_compileIndex, replacement);
986 #endif
987         
988         Node& node = m_graph[m_compileIndex];
989         node.setOpAndDefaultFlags(Phantom);
990         node.setRefCount(1);
991         eliminateIrrelevantPhantomChildren(node);
992         
993         // At this point we will eliminate all references to this node.
994         m_replacements[m_compileIndex] = replacement;
995         
996         m_changed = true;
997         
998         return true;
999     }
1000     
1001     void eliminate()
1002     {
1003 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1004         dataLogF("   Eliminating @%u", m_compileIndex);
1005 #endif
1006         
1007         Node& node = m_graph[m_compileIndex];
1008         ASSERT(node.refCount() == 1);
1009         ASSERT(node.mustGenerate());
1010         node.setOpAndDefaultFlags(Phantom);
1011         eliminateIrrelevantPhantomChildren(node);
1012         
1013         m_changed = true;
1014     }
1015     
1016     void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
1017     {
1018         if (nodeIndex == NoNode)
1019             return;
1020         Node& node = m_graph[nodeIndex];
1021         if (node.refCount() != 1)
1022             return;
1023         ASSERT(node.mustGenerate());
1024         node.setOpAndDefaultFlags(phantomType);
1025         if (phantomType == Phantom)
1026             eliminateIrrelevantPhantomChildren(node);
1027         
1028         m_changed = true;
1029     }
1030     
1031     void performNodeCSE(Node& node)
1032     {
1033         bool shouldGenerate = node.shouldGenerate();
1034
1035         if (node.flags() & NodeHasVarArgs) {
1036             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
1037                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
1038         } else {
1039             performSubstitution(node.children.child1(), shouldGenerate);
1040             performSubstitution(node.children.child2(), shouldGenerate);
1041             performSubstitution(node.children.child3(), shouldGenerate);
1042         }
1043         
1044         if (node.op() == SetLocal)
1045             m_relevantToOSR.set(node.child1().index());
1046         
1047         if (!shouldGenerate)
1048             return;
1049         
1050 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1051         dataLogF("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
1052 #endif
1053         
1054         // NOTE: there are some nodes that we deliberately don't CSE even though we
1055         // probably could, like StrCat and ToPrimitive. That's because there is no
1056         // evidence that doing CSE on these nodes would result in a performance
1057         // progression. Hence considering these nodes in CSE would just mean that this
1058         // code does more work with no win. Of course, we may want to reconsider this,
1059         // since StrCat is trivially CSE-able. It's not trivially doable for
1060         // ToPrimitive, but we could change that with some speculations if we really
1061         // needed to.
1062         
1063         switch (node.op()) {
1064         
1065         case Identity:
1066             setReplacement(node.child1().index());
1067             break;
1068             
1069         // Handle the pure nodes. These nodes never have any side-effects.
1070         case BitAnd:
1071         case BitOr:
1072         case BitXor:
1073         case BitRShift:
1074         case BitLShift:
1075         case BitURShift:
1076         case ArithAdd:
1077         case ArithSub:
1078         case ArithNegate:
1079         case ArithMul:
1080         case ArithMod:
1081         case ArithDiv:
1082         case ArithAbs:
1083         case ArithMin:
1084         case ArithMax:
1085         case ArithSqrt:
1086         case GetCallee:
1087         case StringCharAt:
1088         case StringCharCodeAt:
1089         case Int32ToDouble:
1090         case IsUndefined:
1091         case IsBoolean:
1092         case IsNumber:
1093         case IsString:
1094         case IsObject:
1095         case IsFunction:
1096         case DoubleAsInt32:
1097         case LogicalNot:
1098         case SkipTopScope:
1099         case SkipScope:
1100         case GetScopeRegisters:
1101             setReplacement(pureCSE(node));
1102             break;
1103             
1104         case GetLocal: {
1105             VariableAccessData* variableAccessData = node.variableAccessData();
1106             if (!variableAccessData->isCaptured())
1107                 break;
1108             NodeIndex relevantLocalOp;
1109             NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
1110             if (relevantLocalOp == NoNode)
1111                 break;
1112             if (m_graph[relevantLocalOp].op() != GetLocalUnlinked
1113                 && m_graph[relevantLocalOp].variableAccessData() != variableAccessData)
1114                 break;
1115             NodeIndex phiIndex = node.child1().index();
1116             if (!setReplacement(possibleReplacement))
1117                 break;
1118             // If the GetLocal we replaced used to refer to a SetLocal, then it now
1119             // should refer to the child of the SetLocal instead.
1120             if (m_graph[phiIndex].op() == SetLocal) {
1121                 ASSERT(node.child1().index() == phiIndex);
1122                 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
1123             }
1124             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
1125                 variableAccessData->local());
1126             if (oldTailIndex == m_compileIndex) {
1127                 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
1128                     relevantLocalOp;
1129                 
1130                 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
1131                 // make sure that the GetLocalUnlinked is now linked.
1132                 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
1133                     m_graph[relevantLocalOp].setOp(GetLocal);
1134                     m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
1135                     m_graph.ref(phiIndex);
1136                 }
1137             }
1138             m_changed = true;
1139             break;
1140         }
1141             
1142         case GetLocalUnlinked: {
1143             NodeIndex relevantLocalOpIgnored;
1144             setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored, true));
1145             break;
1146         }
1147             
1148         case Flush: {
1149             VariableAccessData* variableAccessData = node.variableAccessData();
1150             VirtualRegister local = variableAccessData->local();
1151             NodeIndex replacementIndex = node.child1().index();
1152             Node& replacement = m_graph[replacementIndex];
1153             if (replacement.op() != SetLocal)
1154                 break;
1155             ASSERT(replacement.variableAccessData() == variableAccessData);
1156             // FIXME: We should be able to remove SetLocals that can exit; we just need
1157             // to replace them with appropriate type checks.
1158             if (m_graph.m_fixpointState == FixpointNotConverged) {
1159                 // Need to be conservative at this time; if the SetLocal has any chance of performing
1160                 // any speculations then we cannot do anything.
1161                 if (variableAccessData->isCaptured()) {
1162                     // Captured SetLocals never speculate and hence never exit.
1163                 } else {
1164                     if (variableAccessData->shouldUseDoubleFormat())
1165                         break;
1166                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
1167                     if (isInt32Speculation(prediction))
1168                         break;
1169                     if (isArraySpeculation(prediction))
1170                         break;
1171                     if (isBooleanSpeculation(prediction))
1172                         break;
1173                 }
1174             } else {
1175                 if (replacement.canExit())
1176                     break;
1177             }
1178             SetLocalStoreEliminationResult result =
1179                 setLocalStoreElimination(local, replacementIndex);
1180             if (result.mayBeAccessed || result.mayClobberWorld)
1181                 break;
1182             ASSERT(replacement.op() == SetLocal);
1183             ASSERT(replacement.refCount() == 1);
1184             ASSERT(replacement.shouldGenerate());
1185             // FIXME: Investigate using mayExit as a further optimization.
1186             node.setOpAndDefaultFlags(Phantom);
1187             NodeIndex dataNodeIndex = replacement.child1().index();
1188             ASSERT(m_graph[dataNodeIndex].hasResult());
1189             m_graph.clearAndDerefChild1(node);
1190             node.children.child1() = Edge(dataNodeIndex);
1191             m_graph.ref(dataNodeIndex);
1192             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
1193             if (oldTailIndex == m_compileIndex)
1194                 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
1195             m_changed = true;
1196             break;
1197         }
1198             
1199         case JSConstant:
1200             // This is strange, but necessary. Some phases will convert nodes to constants,
1201             // which may result in duplicated constants. We use CSE to clean this up.
1202             setReplacement(constantCSE(node), AllowPredictionMismatch);
1203             break;
1204             
1205         case WeakJSConstant:
1206             // FIXME: have CSE for weak constants against strong constants and vice-versa.
1207             setReplacement(weakConstantCSE(node));
1208             break;
1209             
1210         case GetArrayLength:
1211             setReplacement(getArrayLengthElimination(node.child1().index()));
1212             break;
1213
1214         case GetMyScope:
1215             setReplacement(getMyScopeLoadElimination());
1216             break;
1217             
1218         // Handle nodes that are conditionally pure: these are pure, and can
1219         // be CSE'd, so long as the prediction is the one we want.
1220         case ValueAdd:
1221         case CompareLess:
1222         case CompareLessEq:
1223         case CompareGreater:
1224         case CompareGreaterEq:
1225         case CompareEq: {
1226             if (m_graph.isPredictedNumerical(node)) {
1227                 NodeIndex replacementIndex = pureCSE(node);
1228                 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
1229                     setReplacement(replacementIndex);
1230             }
1231             break;
1232         }
1233             
1234         // Finally handle heap accesses. These are not quite pure, but we can still
1235         // optimize them provided that some subtle conditions are met.
1236         case GetGlobalVar:
1237             setReplacement(globalVarLoadElimination(node.registerPointer()));
1238             break;
1239
1240         case GetScopedVar: {
1241             setReplacement(scopedVarLoadElimination(node.child1().index(), node.varNumber()));
1242             break;
1243         }
1244
1245         case GlobalVarWatchpoint:
1246             if (globalVarWatchpointElimination(node.registerPointer()))
1247                 eliminate();
1248             break;
1249             
1250         case PutGlobalVar:
1251         case PutGlobalVarCheck:
1252             if (m_graph.m_fixpointState == FixpointNotConverged)
1253                 break;
1254             eliminate(globalVarStoreElimination(node.registerPointer()));
1255             break;
1256             
1257         case PutScopedVar: {
1258             if (m_graph.m_fixpointState == FixpointNotConverged)
1259                 break;
1260             eliminate(scopedVarStoreElimination(node.child1().index(), node.child2().index(), node.varNumber()));
1261             break;
1262         }
1263
1264         case GetByVal:
1265             if (m_graph.byValIsPure(node))
1266                 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
1267             break;
1268             
1269         case PutByVal: {
1270             Edge child1 = m_graph.varArgChild(node, 0);
1271             Edge child2 = m_graph.varArgChild(node, 1);
1272             if (node.arrayMode().canCSEStorage()) {
1273                 NodeIndex nodeIndex = getByValLoadElimination(child1.index(), child2.index());
1274                 if (nodeIndex == NoNode)
1275                     break;
1276                 node.setOp(PutByValAlias);
1277             }
1278             break;
1279         }
1280             
1281         case CheckStructure:
1282         case ForwardCheckStructure:
1283             if (checkStructureElimination(node.structureSet(), node.child1().index()))
1284                 eliminate();
1285             break;
1286             
1287         case StructureTransitionWatchpoint:
1288         case ForwardStructureTransitionWatchpoint:
1289             if (structureTransitionWatchpointElimination(node.structure(), node.child1().index()))
1290                 eliminate();
1291             break;
1292             
1293         case PutStructure:
1294             if (m_graph.m_fixpointState == FixpointNotConverged)
1295                 break;
1296             eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1297             break;
1298
1299         case CheckFunction:
1300             if (checkFunctionElimination(node.function(), node.child1().index()))
1301                 eliminate();
1302             break;
1303                 
1304         case CheckArray:
1305             if (checkArrayElimination(node.child1().index(), node.arrayMode()))
1306                 eliminate();
1307             break;
1308             
1309         case GetIndexedPropertyStorage: {
1310             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), node.arrayMode()));
1311             break;
1312         }
1313
1314         case GetButterfly:
1315             setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1316             break;
1317
1318         case GetByOffset:
1319             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1320             break;
1321             
1322         case PutByOffset:
1323             if (m_graph.m_fixpointState == FixpointNotConverged)
1324                 break;
1325             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1326             break;
1327             
1328         case Phantom:
1329             // FIXME: we ought to remove Phantom's that have no children.
1330             
1331             eliminateIrrelevantPhantomChildren(node);
1332             break;
1333             
1334         default:
1335             // do nothing.
1336             break;
1337         }
1338         
1339         m_lastSeen[node.op()] = m_indexInBlock;
1340 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1341         dataLogF("\n");
1342 #endif
1343     }
1344     
1345     void performBlockCSE(BasicBlock* block)
1346     {
1347         if (!block)
1348             return;
1349         if (!block->isReachable)
1350             return;
1351         
1352         m_currentBlock = block;
1353         for (unsigned i = 0; i < LastNodeType; ++i)
1354             m_lastSeen[i] = UINT_MAX;
1355         
1356         // Make all of my Phi nodes relevant to OSR.
1357         for (unsigned i = 0; i < block->phis.size(); ++i)
1358             m_relevantToOSR.set(block->phis[i]);
1359         
1360         // Make all of my SetLocal nodes relevant to OSR.
1361         for (unsigned i = 0; i < block->size(); ++i) {
1362             NodeIndex nodeIndex = block->at(i);
1363             Node& node = m_graph[nodeIndex];
1364             switch (node.op()) {
1365             case SetLocal:
1366                 m_relevantToOSR.set(nodeIndex);
1367                 break;
1368             default:
1369                 break;
1370             }
1371         }
1372
1373         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1374             m_compileIndex = block->at(m_indexInBlock);
1375             performNodeCSE(m_graph[m_compileIndex]);
1376         }
1377     }
1378     
1379     BasicBlock* m_currentBlock;
1380     NodeIndex m_compileIndex;
1381     unsigned m_indexInBlock;
1382     Vector<NodeIndex, 16> m_replacements;
1383     FixedArray<unsigned, LastNodeType> m_lastSeen;
1384     FastBitVector m_relevantToOSR;
1385     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1386 };
1387
1388 bool performCSE(Graph& graph)
1389 {
1390     SamplingRegion samplingRegion("DFG CSE Phase");
1391     return runPhase<CSEPhase>(graph);
1392 }
1393
1394 } } // namespace JSC::DFG
1395
1396 #endif // ENABLE(DFG_JIT)
1397
1398