f26de0125bfd5f71f2e6f4236091b24ec4cdb6cb
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCSEPhase.cpp
1 /*
2  * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DFGCSEPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGGraph.h"
32 #include "DFGPhase.h"
33
34 namespace JSC { namespace DFG {
35
36 class CSEPhase : public Phase {
37 public:
38     CSEPhase(Graph& graph, OptimizationFixpointState fixpointState)
39         : Phase(graph, "common subexpression elimination")
40         , m_fixpointState(fixpointState)
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     
49     bool run()
50     {
51         m_changed = false;
52         for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
53             performBlockCSE(m_graph.m_blocks[block].get());
54         return m_changed;
55     }
56     
57 private:
58     
59     NodeIndex canonicalize(NodeIndex nodeIndex)
60     {
61         if (nodeIndex == NoNode)
62             return NoNode;
63         
64         if (m_graph[nodeIndex].op() == ValueToInt32)
65             nodeIndex = m_graph[nodeIndex].child1().index();
66         
67         return nodeIndex;
68     }
69     NodeIndex canonicalize(Edge nodeUse)
70     {
71         return canonicalize(nodeUse.indexUnchecked());
72     }
73     
74     unsigned endIndexForPureCSE()
75     {
76         unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
77         if (result == UINT_MAX)
78             result = 0;
79         else
80             result++;
81         ASSERT(result <= m_indexInBlock);
82 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
83         dataLog("  limit %u: ", result);
84 #endif
85         return result;
86     }
87     
88     NodeIndex pureCSE(Node& node)
89     {
90         NodeIndex child1 = canonicalize(node.child1());
91         NodeIndex child2 = canonicalize(node.child2());
92         NodeIndex child3 = canonicalize(node.child3());
93         
94         for (unsigned i = endIndexForPureCSE(); i--;) {
95             NodeIndex index = m_currentBlock->at(i);
96             if (index == child1 || index == child2 || index == child3)
97                 break;
98
99             Node& otherNode = m_graph[index];
100             if (node.op() != otherNode.op())
101                 continue;
102             
103             if (node.arithNodeFlags() != otherNode.arithNodeFlags())
104                 continue;
105             
106             NodeIndex otherChild = canonicalize(otherNode.child1());
107             if (otherChild == NoNode)
108                 return index;
109             if (otherChild != child1)
110                 continue;
111             
112             otherChild = canonicalize(otherNode.child2());
113             if (otherChild == NoNode)
114                 return index;
115             if (otherChild != child2)
116                 continue;
117             
118             otherChild = canonicalize(otherNode.child3());
119             if (otherChild == NoNode)
120                 return index;
121             if (otherChild != child3)
122                 continue;
123             
124             return index;
125         }
126         return NoNode;
127     }
128     
129     NodeIndex constantCSE(Node& node)
130     {
131         for (unsigned i = endIndexForPureCSE(); i--;) {
132             NodeIndex index = m_currentBlock->at(i);
133             Node& otherNode = m_graph[index];
134             if (otherNode.op() != JSConstant)
135                 continue;
136             
137             if (otherNode.constantNumber() != node.constantNumber())
138                 continue;
139             
140             return index;
141         }
142         return NoNode;
143     }
144     
145     NodeIndex weakConstantCSE(Node& node)
146     {
147         for (unsigned i = endIndexForPureCSE(); i--;) {
148             NodeIndex index = m_currentBlock->at(i);
149             Node& otherNode = m_graph[index];
150             if (otherNode.op() != WeakJSConstant)
151                 continue;
152             
153             if (otherNode.weakConstant() != node.weakConstant())
154                 continue;
155             
156             return index;
157         }
158         return NoNode;
159     }
160     
161     NodeIndex impureCSE(Node& node)
162     {
163         NodeIndex child1 = canonicalize(node.child1());
164         NodeIndex child2 = canonicalize(node.child2());
165         NodeIndex child3 = canonicalize(node.child3());
166         
167         for (unsigned i = m_indexInBlock; i--;) {
168             NodeIndex index = m_currentBlock->at(i);
169             if (index == child1 || index == child2 || index == child3)
170                 break;
171
172             Node& otherNode = m_graph[index];
173             if (node.op() == otherNode.op()
174                 && node.arithNodeFlags() == otherNode.arithNodeFlags()) {
175                 NodeIndex otherChild = canonicalize(otherNode.child1());
176                 if (otherChild == NoNode)
177                     return index;
178                 if (otherChild == child1) {
179                     otherChild = canonicalize(otherNode.child2());
180                     if (otherChild == NoNode)
181                         return index;
182                     if (otherChild == child2) {
183                         otherChild = canonicalize(otherNode.child3());
184                         if (otherChild == NoNode)
185                             return index;
186                         if (otherChild == child3)
187                             return index;
188                     }
189                 }
190             }
191             if (m_graph.clobbersWorld(index))
192                 break;
193         }
194         return NoNode;
195     }
196     
197     NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
198     {
199         for (unsigned i = m_indexInBlock; i--;) {
200             NodeIndex index = m_currentBlock->at(i);
201             Node& node = m_graph[index];
202             switch (node.op()) {
203             case GetGlobalVar:
204                 if (node.registerPointer() == registerPointer)
205                     return index;
206                 break;
207             case PutGlobalVar:
208                 if (node.registerPointer() == registerPointer)
209                     return node.child1().index();
210                 break;
211             default:
212                 break;
213             }
214             if (m_graph.clobbersWorld(index))
215                 break;
216         }
217         return NoNode;
218     }
219     
220     NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
221     {
222         for (unsigned i = m_indexInBlock; i--;) {
223             NodeIndex index = m_currentBlock->at(i);
224             Node& node = m_graph[index];
225             if (!node.shouldGenerate())
226                 continue;
227             switch (node.op()) {
228             case PutGlobalVar:
229                 if (node.registerPointer() == registerPointer)
230                     return index;
231                 break;
232                 
233             case GetGlobalVar:
234                 if (node.registerPointer() == registerPointer)
235                     return NoNode;
236                 break;
237                 
238             default:
239                 break;
240             }
241             if (m_graph.clobbersWorld(index) || node.canExit())
242                 return NoNode;
243         }
244         return NoNode;
245     }
246     
247     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
248     {
249         for (unsigned i = m_indexInBlock; i--;) {
250             NodeIndex index = m_currentBlock->at(i);
251             if (index == child1 || index == canonicalize(child2)) 
252                 break;
253
254             Node& node = m_graph[index];
255             switch (node.op()) {
256             case GetByVal:
257                 if (!m_graph.byValIsPure(node))
258                     return NoNode;
259                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
260                     return index;
261                 break;
262             case PutByVal:
263             case PutByValAlias:
264                 if (!m_graph.byValIsPure(node))
265                     return NoNode;
266                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
267                     return node.child3().index();
268                 // We must assume that the PutByVal will clobber the location we're getting from.
269                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
270                 // different type than the GetByVal, then we know that they won't clobber each other.
271                 return NoNode;
272             case PutStructure:
273             case PutByOffset:
274                 // GetByVal currently always speculates that it's accessing an
275                 // array with an integer index, which means that it's impossible
276                 // for a structure change or a put to property storage to affect
277                 // the GetByVal.
278                 break;
279             case ArrayPush:
280                 // A push cannot affect previously existing elements in the array.
281                 break;
282             default:
283                 if (m_graph.clobbersWorld(index))
284                     return NoNode;
285                 break;
286             }
287         }
288         return NoNode;
289     }
290
291     bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
292     {
293         for (unsigned i = endIndexForPureCSE(); i--;) {
294             NodeIndex index = m_currentBlock->at(i);
295             if (index == child1) 
296                 break;
297
298             Node& node = m_graph[index];
299             if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
300                 return true;
301         }
302         return false;
303     }
304
305     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
306     {
307         for (unsigned i = m_indexInBlock; i--;) {
308             NodeIndex index = m_currentBlock->at(i);
309             if (index == child1) 
310                 break;
311
312             Node& node = m_graph[index];
313             switch (node.op()) {
314             case CheckStructure:
315                 if (node.child1() == child1
316                     && structureSet.isSupersetOf(node.structureSet()))
317                     return true;
318                 break;
319                 
320             case PutStructure:
321                 if (node.child1() == child1
322                     && structureSet.contains(node.structureTransitionData().newStructure))
323                     return true;
324                 if (structureSet.contains(node.structureTransitionData().previousStructure))
325                     return false;
326                 break;
327                 
328             case PutByOffset:
329                 // Setting a property cannot change the structure.
330                 break;
331                 
332             case PutByVal:
333             case PutByValAlias:
334                 if (m_graph.byValIsPure(node)) {
335                     // If PutByVal speculates that it's accessing an array with an
336                     // integer index, then it's impossible for it to cause a structure
337                     // change.
338                     break;
339                 }
340                 return false;
341                 
342             default:
343                 if (m_graph.clobbersWorld(index))
344                     return false;
345                 break;
346             }
347         }
348         return false;
349     }
350     
351     NodeIndex putStructureStoreElimination(NodeIndex child1)
352     {
353         for (unsigned i = m_indexInBlock; i--;) {
354             NodeIndex index = m_currentBlock->at(i);
355             if (index == child1)
356                 break;
357             Node& node = m_graph[index];
358             if (!node.shouldGenerate())
359                 break;
360             switch (node.op()) {
361             case CheckStructure:
362                 return NoNode;
363                 
364             case PhantomPutStructure:
365                 if (node.child1() == child1) // No need to retrace our steps.
366                     return NoNode;
367                 break;
368                 
369             case PutStructure:
370                 if (node.child1() == child1)
371                     return index;
372                 break;
373                 
374             // PutStructure needs to execute if we GC. Hence this needs to
375             // be careful with respect to nodes that GC.
376             case CreateArguments:
377             case TearOffArguments:
378             case NewFunctionNoCheck:
379             case NewFunction:
380             case NewFunctionExpression:
381             case CreateActivation:
382             case TearOffActivation:
383             case StrCat:
384             case ToPrimitive:
385             case NewRegexp:
386             case NewArrayBuffer:
387             case NewArray:
388             case NewObject:
389             case CreateThis:
390                 return NoNode;
391                 
392             default:
393                 break;
394             }
395             if (m_graph.clobbersWorld(index) || node.canExit())
396                 return NoNode;
397         }
398         return NoNode;
399     }
400     
401     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
402     {
403         for (unsigned i = m_indexInBlock; i--;) {
404             NodeIndex index = m_currentBlock->at(i);
405             if (index == child1)
406                 break;
407
408             Node& node = m_graph[index];
409             switch (node.op()) {
410             case GetByOffset:
411                 if (node.child1() == child1
412                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
413                     return index;
414                 break;
415                 
416             case PutByOffset:
417                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
418                     if (node.child1() == child1) // Must be same property storage.
419                         return node.child3().index();
420                     return NoNode;
421                 }
422                 break;
423                 
424             case PutStructure:
425                 // Changing the structure cannot change the outcome of a property get.
426                 break;
427                 
428             case PutByVal:
429             case PutByValAlias:
430                 if (m_graph.byValIsPure(node)) {
431                     // If PutByVal speculates that it's accessing an array with an
432                     // integer index, then it's impossible for it to cause a structure
433                     // change.
434                     break;
435                 }
436                 return NoNode;
437                 
438             default:
439                 if (m_graph.clobbersWorld(index))
440                     return NoNode;
441                 break;
442             }
443         }
444         return NoNode;
445     }
446     
447     NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
448     {
449         for (unsigned i = m_indexInBlock; i--;) {
450             NodeIndex index = m_currentBlock->at(i);
451             if (index == child1)
452                 break;
453
454             Node& node = m_graph[index];
455             if (!node.shouldGenerate())
456                 continue;
457             switch (node.op()) {
458             case GetByOffset:
459                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
460                     return NoNode;
461                 break;
462                 
463             case PutByOffset:
464                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
465                     if (node.child1() == child1) // Must be same property storage.
466                         return index;
467                     return NoNode;
468                 }
469                 break;
470                 
471             case PutByVal:
472             case PutByValAlias:
473             case GetByVal:
474                 if (m_graph.byValIsPure(node)) {
475                     // If PutByVal speculates that it's accessing an array with an
476                     // integer index, then it's impossible for it to cause a structure
477                     // change.
478                     break;
479                 }
480                 return NoNode;
481                 
482             default:
483                 if (m_graph.clobbersWorld(index))
484                     return NoNode;
485                 break;
486             }
487             if (node.canExit())
488                 return NoNode;
489         }
490         return NoNode;
491     }
492     
493     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
494     {
495         for (unsigned i = m_indexInBlock; i--;) {
496             NodeIndex index = m_currentBlock->at(i);
497             if (index == child1) 
498                 break;
499
500             Node& node = m_graph[index];
501             switch (node.op()) {
502             case GetPropertyStorage:
503                 if (node.child1() == child1)
504                     return index;
505                 break;
506                 
507             case PutByOffset:
508             case PutStructure:
509                 // Changing the structure or putting to the storage cannot
510                 // change the property storage pointer.
511                 break;
512                 
513             case PutByVal:
514             case PutByValAlias:
515                 if (m_graph.byValIsPure(node)) {
516                     // If PutByVal speculates that it's accessing an array with an
517                     // integer index, then it's impossible for it to cause a structure
518                     // change.
519                     break;
520                 }
521                 return NoNode;
522                 
523             default:
524                 if (m_graph.clobbersWorld(index))
525                     return NoNode;
526                 break;
527             }
528         }
529         return NoNode;
530     }
531
532     NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
533     {
534         for (unsigned i = m_indexInBlock; i--;) {
535             NodeIndex index = m_currentBlock->at(i);
536             if (index == child1) 
537                 break;
538
539             Node& node = m_graph[index];
540             switch (node.op()) {
541             case GetIndexedPropertyStorage: {
542                 SpeculatedType basePrediction = m_graph[node.child2()].prediction();
543                 bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
544                 if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
545                     return index;
546                 break;
547             }
548
549             case PutByOffset:
550             case PutStructure:
551                 // Changing the structure or putting to the storage cannot
552                 // change the property storage pointer.
553                 break;
554                 
555             case PutByValAlias:
556                 // PutByValAlias can't change the indexed storage pointer
557                 break;
558                 
559             case PutByVal:
560                 if (isFixedIndexedStorageObjectSpeculation(m_graph[node.child1()].prediction()) && m_graph.byValIsPure(node))
561                     break;
562                 return NoNode;
563
564             default:
565                 if (m_graph.clobbersWorld(index))
566                     return NoNode;
567                 break;
568             }
569         }
570         return NoNode;
571     }
572     
573     NodeIndex getScopeChainLoadElimination(unsigned depth)
574     {
575         for (unsigned i = endIndexForPureCSE(); i--;) {
576             NodeIndex index = m_currentBlock->at(i);
577             Node& node = m_graph[index];
578             if (node.op() == GetScopeChain
579                 && node.scopeChainDepth() == depth)
580                 return index;
581         }
582         return NoNode;
583     }
584     
585     NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp)
586     {
587         relevantLocalOp = NoNode;
588         
589         for (unsigned i = m_indexInBlock; i--;) {
590             NodeIndex index = m_currentBlock->at(i);
591             Node& node = m_graph[index];
592             switch (node.op()) {
593             case GetLocal:
594                 if (node.local() == local) {
595                     relevantLocalOp = index;
596                     return index;
597                 }
598                 break;
599                 
600             case GetLocalUnlinked:
601                 if (node.unlinkedLocal() == local) {
602                     relevantLocalOp = index;
603                     return index;
604                 }
605                 break;
606                 
607             case SetLocal:
608                 if (node.local() == local) {
609                     relevantLocalOp = index;
610                     return node.child1().index();
611                 }
612                 break;
613                 
614             default:
615                 if (m_graph.clobbersWorld(index))
616                     return NoNode;
617                 break;
618             }
619         }
620         return NoNode;
621     }
622     
623     struct SetLocalStoreEliminationResult {
624         SetLocalStoreEliminationResult()
625             : mayBeAccessed(false)
626             , mayExit(false)
627             , mayClobberWorld(false)
628         {
629         }
630         
631         bool mayBeAccessed;
632         bool mayExit;
633         bool mayClobberWorld;
634     };
635     SetLocalStoreEliminationResult setLocalStoreElimination(
636         VirtualRegister local, NodeIndex expectedNodeIndex)
637     {
638         SetLocalStoreEliminationResult result;
639         for (unsigned i = m_indexInBlock; i--;) {
640             NodeIndex index = m_currentBlock->at(i);
641             Node& node = m_graph[index];
642             if (!node.shouldGenerate())
643                 continue;
644             switch (node.op()) {
645             case GetLocal:
646             case Flush:
647                 if (node.local() == local)
648                     result.mayBeAccessed = true;
649                 break;
650                 
651             case GetLocalUnlinked:
652                 if (node.unlinkedLocal() == local)
653                     result.mayBeAccessed = true;
654                 break;
655                 
656             case SetLocal: {
657                 if (node.local() != local)
658                     break;
659                 if (index != expectedNodeIndex)
660                     result.mayBeAccessed = true;
661                 if (m_graph[index].refCount() > 1)
662                     result.mayBeAccessed = true;
663                 return result;
664             }
665                 
666             case GetScopeChain:
667                 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
668                     result.mayBeAccessed = true;
669                 break;
670                 
671             case CheckArgumentsNotCreated:
672             case GetMyArgumentsLength:
673             case GetMyArgumentsLengthSafe:
674                 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
675                     result.mayBeAccessed = true;
676                 break;
677                 
678             case GetMyArgumentByVal:
679             case GetMyArgumentByValSafe:
680                 result.mayBeAccessed = true;
681                 break;
682                 
683             case GetByVal:
684                 // If this is accessing arguments then it's potentially accessing locals.
685                 if (m_graph[node.child1()].shouldSpeculateArguments())
686                     result.mayBeAccessed = true;
687                 break;
688                 
689             case CreateArguments:
690             case TearOffActivation:
691             case TearOffArguments:
692                 // If an activation is being torn off then it means that captured variables
693                 // are live. We could be clever here and check if the local qualifies as an
694                 // argument register. But that seems like it would buy us very little since
695                 // any kind of tear offs are rare to begin with.
696                 result.mayBeAccessed = true;
697                 break;
698                 
699             default:
700                 break;
701             }
702             result.mayExit |= node.canExit();
703             result.mayClobberWorld |= m_graph.clobbersWorld(index);
704         }
705         ASSERT_NOT_REACHED();
706         // Be safe in release mode.
707         result.mayBeAccessed = true;
708         return result;
709     }
710     
711     void performSubstitution(Edge& child, bool addRef = true)
712     {
713         // Check if this operand is actually unused.
714         if (!child)
715             return;
716         
717         // Check if there is any replacement.
718         NodeIndex replacement = m_replacements[child.index()];
719         if (replacement == NoNode)
720             return;
721         
722         child.setIndex(replacement);
723         
724         // There is definitely a replacement. Assert that the replacement does not
725         // have a replacement.
726         ASSERT(m_replacements[child.index()] == NoNode);
727         
728         if (addRef)
729             m_graph[child].ref();
730     }
731     
732     enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
733     bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
734     {
735         if (replacement == NoNode)
736             return false;
737         
738         // Be safe. Don't try to perform replacements if the predictions don't
739         // agree.
740         if (predictionHandlingMode == RequireSamePrediction
741             && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
742             return false;
743         
744 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
745         dataLog("   Replacing @%u -> @%u", m_compileIndex, replacement);
746 #endif
747         
748         Node& node = m_graph[m_compileIndex];
749         node.setOpAndDefaultFlags(Phantom);
750         node.setRefCount(1);
751         
752         // At this point we will eliminate all references to this node.
753         m_replacements[m_compileIndex] = replacement;
754         
755         return true;
756     }
757     
758     void eliminate()
759     {
760 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
761         dataLog("   Eliminating @%u", m_compileIndex);
762 #endif
763         
764         Node& node = m_graph[m_compileIndex];
765         ASSERT(node.refCount() == 1);
766         ASSERT(node.mustGenerate());
767         node.setOpAndDefaultFlags(Phantom);
768     }
769     
770     void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
771     {
772         if (nodeIndex == NoNode)
773             return;
774         Node& node = m_graph[nodeIndex];
775         if (node.refCount() != 1)
776             return;
777         ASSERT(node.mustGenerate());
778         node.setOpAndDefaultFlags(phantomType);
779     }
780     
781     void performNodeCSE(Node& node)
782     {
783         bool shouldGenerate = node.shouldGenerate();
784
785         if (node.flags() & NodeHasVarArgs) {
786             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
787                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
788         } else {
789             performSubstitution(node.children.child1(), shouldGenerate);
790             performSubstitution(node.children.child2(), shouldGenerate);
791             performSubstitution(node.children.child3(), shouldGenerate);
792         }
793         
794         if (!shouldGenerate)
795             return;
796         
797 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
798         dataLog("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
799 #endif
800         
801         // NOTE: there are some nodes that we deliberately don't CSE even though we
802         // probably could, like StrCat and ToPrimitive. That's because there is no
803         // evidence that doing CSE on these nodes would result in a performance
804         // progression. Hence considering these nodes in CSE would just mean that this
805         // code does more work with no win. Of course, we may want to reconsider this,
806         // since StrCat is trivially CSE-able. It's not trivially doable for
807         // ToPrimitive, but we could change that with some speculations if we really
808         // needed to.
809         
810         switch (node.op()) {
811         
812         // Handle the pure nodes. These nodes never have any side-effects.
813         case BitAnd:
814         case BitOr:
815         case BitXor:
816         case BitRShift:
817         case BitLShift:
818         case BitURShift:
819         case ArithAdd:
820         case ArithSub:
821         case ArithNegate:
822         case ArithMul:
823         case ArithMod:
824         case ArithDiv:
825         case ArithAbs:
826         case ArithMin:
827         case ArithMax:
828         case ArithSqrt:
829         case GetInt8ArrayLength:
830         case GetInt16ArrayLength:
831         case GetInt32ArrayLength:
832         case GetUint8ArrayLength:
833         case GetUint8ClampedArrayLength:
834         case GetUint16ArrayLength:
835         case GetUint32ArrayLength:
836         case GetFloat32ArrayLength:
837         case GetFloat64ArrayLength:
838         case GetCallee:
839         case GetStringLength:
840         case StringCharAt:
841         case StringCharCodeAt:
842         case Int32ToDouble:
843         case IsUndefined:
844         case IsBoolean:
845         case IsNumber:
846         case IsString:
847         case IsObject:
848         case IsFunction:
849         case DoubleAsInt32:
850         case LogicalNot:
851             setReplacement(pureCSE(node));
852             break;
853             
854         case GetLocal: {
855             VariableAccessData* variableAccessData = node.variableAccessData();
856             if (!variableAccessData->isCaptured())
857                 break;
858             NodeIndex relevantLocalOp;
859             NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp);
860             ASSERT(relevantLocalOp == NoNode
861                    || m_graph[relevantLocalOp].op() == GetLocalUnlinked
862                    || m_graph[relevantLocalOp].variableAccessData() == variableAccessData);
863             NodeIndex phiIndex = node.child1().index();
864             if (!setReplacement(possibleReplacement))
865                 break;
866             // If the GetLocal we replaced used to refer to a SetLocal, then it now
867             // should refer to the child of the SetLocal instead.
868             if (m_graph[phiIndex].op() == SetLocal) {
869                 ASSERT(node.child1().index() == phiIndex);
870                 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
871             }
872             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
873                 variableAccessData->local());
874             if (oldTailIndex == m_compileIndex) {
875                 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
876                     relevantLocalOp;
877                 
878                 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
879                 // make sure that the GetLocalUnlinked is now linked.
880                 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
881                     m_graph[relevantLocalOp].setOp(GetLocal);
882                     m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
883                     m_graph.ref(phiIndex);
884                 }
885             }
886             m_changed = true;
887             break;
888         }
889             
890         case GetLocalUnlinked: {
891             NodeIndex relevantLocalOpIgnored;
892             m_changed |= setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored));
893             break;
894         }
895             
896         case Flush: {
897             VariableAccessData* variableAccessData = node.variableAccessData();
898             VirtualRegister local = variableAccessData->local();
899             NodeIndex replacementIndex = node.child1().index();
900             Node& replacement = m_graph[replacementIndex];
901             if (replacement.op() != SetLocal)
902                 break;
903             ASSERT(replacement.variableAccessData() == variableAccessData);
904             // FIXME: We should be able to remove SetLocals that can exit; we just need
905             // to replace them with appropriate type checks.
906             if (m_fixpointState == FixpointNotConverged) {
907                 // Need to be conservative at this time; if the SetLocal has any chance of performing
908                 // any speculations then we cannot do anything.
909                 if (variableAccessData->isCaptured()) {
910                     // Captured SetLocals never speculate and hence never exit.
911                 } else {
912                     if (variableAccessData->shouldUseDoubleFormat())
913                         break;
914                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
915                     if (isInt32Speculation(prediction))
916                         break;
917                     if (isArraySpeculation(prediction))
918                         break;
919                     if (isBooleanSpeculation(prediction))
920                         break;
921                 }
922             } else {
923                 if (replacement.canExit())
924                     break;
925             }
926             SetLocalStoreEliminationResult result =
927                 setLocalStoreElimination(local, replacementIndex);
928             if (result.mayBeAccessed || result.mayClobberWorld)
929                 break;
930             ASSERT(replacement.op() == SetLocal);
931             ASSERT(replacement.refCount() == 1);
932             ASSERT(replacement.shouldGenerate());
933             // FIXME: Investigate using mayExit as a further optimization.
934             node.setOpAndDefaultFlags(Phantom);
935             NodeIndex dataNodeIndex = replacement.child1().index();
936             ASSERT(m_graph[dataNodeIndex].hasResult());
937             m_graph.clearAndDerefChild1(node);
938             node.children.child1() = Edge(dataNodeIndex);
939             m_graph.ref(dataNodeIndex);
940             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
941             if (oldTailIndex == m_compileIndex)
942                 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
943             m_changed = true;
944             break;
945         }
946             
947         case JSConstant:
948             // This is strange, but necessary. Some phases will convert nodes to constants,
949             // which may result in duplicated constants. We use CSE to clean this up.
950             setReplacement(constantCSE(node), AllowPredictionMismatch);
951             break;
952             
953         case WeakJSConstant:
954             // FIXME: have CSE for weak constants against strong constants and vice-versa.
955             setReplacement(weakConstantCSE(node));
956             break;
957             
958         case GetArrayLength:
959             setReplacement(impureCSE(node));
960             break;
961             
962         case GetScopeChain:
963             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
964             break;
965
966         // Handle nodes that are conditionally pure: these are pure, and can
967         // be CSE'd, so long as the prediction is the one we want.
968         case ValueAdd:
969         case CompareLess:
970         case CompareLessEq:
971         case CompareGreater:
972         case CompareGreaterEq:
973         case CompareEq: {
974             if (m_graph.isPredictedNumerical(node)) {
975                 NodeIndex replacementIndex = pureCSE(node);
976                 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
977                     setReplacement(replacementIndex);
978             }
979             break;
980         }
981             
982         // Finally handle heap accesses. These are not quite pure, but we can still
983         // optimize them provided that some subtle conditions are met.
984         case GetGlobalVar:
985             setReplacement(globalVarLoadElimination(node.registerPointer()));
986             break;
987             
988         case PutGlobalVar:
989             if (m_fixpointState == FixpointNotConverged)
990                 break;
991             eliminate(globalVarStoreElimination(node.registerPointer()));
992             break;
993             
994         case GetByVal:
995             if (m_graph.byValIsPure(node))
996                 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
997             break;
998             
999         case PutByVal:
1000             if (m_graph.byValIsPure(node)
1001                 && !m_graph[node.child1()].shouldSpeculateArguments()
1002                 && getByValLoadElimination(node.child1().index(), node.child2().index()) != NoNode)
1003                 node.setOp(PutByValAlias);
1004             break;
1005             
1006         case CheckStructure:
1007             if (checkStructureLoadElimination(node.structureSet(), node.child1().index()))
1008                 eliminate();
1009             break;
1010             
1011         case PutStructure:
1012             if (m_fixpointState == FixpointNotConverged)
1013                 break;
1014             eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1015             break;
1016
1017         case CheckFunction:
1018             if (checkFunctionElimination(node.function(), node.child1().index()))
1019                 eliminate();
1020             break;
1021                 
1022         case GetIndexedPropertyStorage: {
1023             SpeculatedType basePrediction = m_graph[node.child2()].prediction();
1024             bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
1025             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), nodeHasIntegerIndexPrediction));
1026             break;
1027         }
1028
1029         case GetPropertyStorage:
1030             setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1031             break;
1032
1033         case GetByOffset:
1034             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1035             break;
1036             
1037         case PutByOffset:
1038             if (m_fixpointState == FixpointNotConverged)
1039                 break;
1040             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1041             break;
1042             
1043         default:
1044             // do nothing.
1045             break;
1046         }
1047         
1048         m_lastSeen[node.op()] = m_indexInBlock;
1049 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1050         dataLog("\n");
1051 #endif
1052     }
1053     
1054     void performBlockCSE(BasicBlock* block)
1055     {
1056         if (!block)
1057             return;
1058         if (!block->isReachable)
1059             return;
1060         
1061         m_currentBlock = block;
1062         for (unsigned i = 0; i < LastNodeType; ++i)
1063             m_lastSeen[i] = UINT_MAX;
1064
1065         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1066             m_compileIndex = block->at(m_indexInBlock);
1067             performNodeCSE(m_graph[m_compileIndex]);
1068         }
1069     }
1070     
1071     BasicBlock* m_currentBlock;
1072     NodeIndex m_compileIndex;
1073     unsigned m_indexInBlock;
1074     Vector<NodeIndex, 16> m_replacements;
1075     FixedArray<unsigned, LastNodeType> m_lastSeen;
1076     OptimizationFixpointState m_fixpointState;
1077     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1078 };
1079
1080 bool performCSE(Graph& graph, OptimizationFixpointState fixpointState)
1081 {
1082     return runPhase<CSEPhase>(graph, fixpointState);
1083 }
1084
1085 } } // namespace JSC::DFG
1086
1087 #endif // ENABLE(DFG_JIT)
1088
1089