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