DFG should be able to set watchpoints on global variables
[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     bool globalVarWatchpointElimination(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             switch (node.op()) {
226             case GlobalVarWatchpoint:
227                 if (node.registerPointer() == registerPointer)
228                     return true;
229                 break;
230             case PutGlobalVar:
231                 if (node.registerPointer() == registerPointer)
232                     return false;
233                 break;
234             default:
235                 break;
236             }
237             if (m_graph.clobbersWorld(index))
238                 break;
239         }
240         return false;
241     }
242     
243     NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
244     {
245         for (unsigned i = m_indexInBlock; i--;) {
246             NodeIndex index = m_currentBlock->at(i);
247             Node& node = m_graph[index];
248             if (!node.shouldGenerate())
249                 continue;
250             switch (node.op()) {
251             case PutGlobalVar:
252             case PutGlobalVarCheck:
253                 if (node.registerPointer() == registerPointer)
254                     return index;
255                 break;
256                 
257             case GetGlobalVar:
258                 if (node.registerPointer() == registerPointer)
259                     return NoNode;
260                 break;
261                 
262             default:
263                 break;
264             }
265             if (m_graph.clobbersWorld(index) || node.canExit())
266                 return NoNode;
267         }
268         return NoNode;
269     }
270     
271     NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
272     {
273         for (unsigned i = m_indexInBlock; i--;) {
274             NodeIndex index = m_currentBlock->at(i);
275             if (index == child1 || index == canonicalize(child2)) 
276                 break;
277
278             Node& node = m_graph[index];
279             switch (node.op()) {
280             case GetByVal:
281                 if (!m_graph.byValIsPure(node))
282                     return NoNode;
283                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
284                     return index;
285                 break;
286             case PutByVal:
287             case PutByValAlias:
288                 if (!m_graph.byValIsPure(node))
289                     return NoNode;
290                 if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
291                     return node.child3().index();
292                 // We must assume that the PutByVal will clobber the location we're getting from.
293                 // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
294                 // different type than the GetByVal, then we know that they won't clobber each other.
295                 return NoNode;
296             case PutStructure:
297             case PutByOffset:
298                 // GetByVal currently always speculates that it's accessing an
299                 // array with an integer index, which means that it's impossible
300                 // for a structure change or a put to property storage to affect
301                 // the GetByVal.
302                 break;
303             case ArrayPush:
304                 // A push cannot affect previously existing elements in the array.
305                 break;
306             default:
307                 if (m_graph.clobbersWorld(index))
308                     return NoNode;
309                 break;
310             }
311         }
312         return NoNode;
313     }
314
315     bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
316     {
317         for (unsigned i = endIndexForPureCSE(); i--;) {
318             NodeIndex index = m_currentBlock->at(i);
319             if (index == child1) 
320                 break;
321
322             Node& node = m_graph[index];
323             if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
324                 return true;
325         }
326         return false;
327     }
328
329     bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
330     {
331         for (unsigned i = m_indexInBlock; i--;) {
332             NodeIndex index = m_currentBlock->at(i);
333             if (index == child1) 
334                 break;
335
336             Node& node = m_graph[index];
337             switch (node.op()) {
338             case CheckStructure:
339                 if (node.child1() == child1
340                     && structureSet.isSupersetOf(node.structureSet()))
341                     return true;
342                 break;
343                 
344             case PutStructure:
345                 if (node.child1() == child1
346                     && structureSet.contains(node.structureTransitionData().newStructure))
347                     return true;
348                 if (structureSet.contains(node.structureTransitionData().previousStructure))
349                     return false;
350                 break;
351                 
352             case PutByOffset:
353                 // Setting a property cannot change the structure.
354                 break;
355                 
356             case PutByVal:
357             case PutByValAlias:
358                 if (m_graph.byValIsPure(node)) {
359                     // If PutByVal speculates that it's accessing an array with an
360                     // integer index, then it's impossible for it to cause a structure
361                     // change.
362                     break;
363                 }
364                 return false;
365                 
366             default:
367                 if (m_graph.clobbersWorld(index))
368                     return false;
369                 break;
370             }
371         }
372         return false;
373     }
374     
375     NodeIndex putStructureStoreElimination(NodeIndex child1)
376     {
377         for (unsigned i = m_indexInBlock; i--;) {
378             NodeIndex index = m_currentBlock->at(i);
379             if (index == child1)
380                 break;
381             Node& node = m_graph[index];
382             if (!node.shouldGenerate())
383                 break;
384             switch (node.op()) {
385             case CheckStructure:
386                 return NoNode;
387                 
388             case PhantomPutStructure:
389                 if (node.child1() == child1) // No need to retrace our steps.
390                     return NoNode;
391                 break;
392                 
393             case PutStructure:
394                 if (node.child1() == child1)
395                     return index;
396                 break;
397                 
398             // PutStructure needs to execute if we GC. Hence this needs to
399             // be careful with respect to nodes that GC.
400             case CreateArguments:
401             case TearOffArguments:
402             case NewFunctionNoCheck:
403             case NewFunction:
404             case NewFunctionExpression:
405             case CreateActivation:
406             case TearOffActivation:
407             case StrCat:
408             case ToPrimitive:
409             case NewRegexp:
410             case NewArrayBuffer:
411             case NewArray:
412             case NewObject:
413             case CreateThis:
414                 return NoNode;
415                 
416             default:
417                 break;
418             }
419             if (m_graph.clobbersWorld(index) || node.canExit())
420                 return NoNode;
421         }
422         return NoNode;
423     }
424     
425     NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
426     {
427         for (unsigned i = m_indexInBlock; i--;) {
428             NodeIndex index = m_currentBlock->at(i);
429             if (index == child1)
430                 break;
431
432             Node& node = m_graph[index];
433             switch (node.op()) {
434             case GetByOffset:
435                 if (node.child1() == child1
436                     && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
437                     return index;
438                 break;
439                 
440             case PutByOffset:
441                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
442                     if (node.child1() == child1) // Must be same property storage.
443                         return node.child3().index();
444                     return NoNode;
445                 }
446                 break;
447                 
448             case PutStructure:
449                 // Changing the structure cannot change the outcome of a property get.
450                 break;
451                 
452             case PutByVal:
453             case PutByValAlias:
454                 if (m_graph.byValIsPure(node)) {
455                     // If PutByVal speculates that it's accessing an array with an
456                     // integer index, then it's impossible for it to cause a structure
457                     // change.
458                     break;
459                 }
460                 return NoNode;
461                 
462             default:
463                 if (m_graph.clobbersWorld(index))
464                     return NoNode;
465                 break;
466             }
467         }
468         return NoNode;
469     }
470     
471     NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
472     {
473         for (unsigned i = m_indexInBlock; i--;) {
474             NodeIndex index = m_currentBlock->at(i);
475             if (index == child1)
476                 break;
477
478             Node& node = m_graph[index];
479             if (!node.shouldGenerate())
480                 continue;
481             switch (node.op()) {
482             case GetByOffset:
483                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
484                     return NoNode;
485                 break;
486                 
487             case PutByOffset:
488                 if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
489                     if (node.child1() == child1) // Must be same property storage.
490                         return index;
491                     return NoNode;
492                 }
493                 break;
494                 
495             case PutByVal:
496             case PutByValAlias:
497             case GetByVal:
498                 if (m_graph.byValIsPure(node)) {
499                     // If PutByVal speculates that it's accessing an array with an
500                     // integer index, then it's impossible for it to cause a structure
501                     // change.
502                     break;
503                 }
504                 return NoNode;
505                 
506             default:
507                 if (m_graph.clobbersWorld(index))
508                     return NoNode;
509                 break;
510             }
511             if (node.canExit())
512                 return NoNode;
513         }
514         return NoNode;
515     }
516     
517     NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
518     {
519         for (unsigned i = m_indexInBlock; i--;) {
520             NodeIndex index = m_currentBlock->at(i);
521             if (index == child1) 
522                 break;
523
524             Node& node = m_graph[index];
525             switch (node.op()) {
526             case GetPropertyStorage:
527                 if (node.child1() == child1)
528                     return index;
529                 break;
530                 
531             case PutByOffset:
532             case PutStructure:
533                 // Changing the structure or putting to the storage cannot
534                 // change the property storage pointer.
535                 break;
536                 
537             case PutByVal:
538             case PutByValAlias:
539                 if (m_graph.byValIsPure(node)) {
540                     // If PutByVal speculates that it's accessing an array with an
541                     // integer index, then it's impossible for it to cause a structure
542                     // change.
543                     break;
544                 }
545                 return NoNode;
546                 
547             default:
548                 if (m_graph.clobbersWorld(index))
549                     return NoNode;
550                 break;
551             }
552         }
553         return NoNode;
554     }
555
556     NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
557     {
558         for (unsigned i = m_indexInBlock; i--;) {
559             NodeIndex index = m_currentBlock->at(i);
560             if (index == child1) 
561                 break;
562
563             Node& node = m_graph[index];
564             switch (node.op()) {
565             case GetIndexedPropertyStorage: {
566                 SpeculatedType basePrediction = m_graph[node.child2()].prediction();
567                 bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
568                 if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
569                     return index;
570                 break;
571             }
572
573             case PutByOffset:
574             case PutStructure:
575                 // Changing the structure or putting to the storage cannot
576                 // change the property storage pointer.
577                 break;
578                 
579             case PutByValAlias:
580                 // PutByValAlias can't change the indexed storage pointer
581                 break;
582                 
583             case PutByVal:
584                 if (isFixedIndexedStorageObjectSpeculation(m_graph[node.child1()].prediction()) && m_graph.byValIsPure(node))
585                     break;
586                 return NoNode;
587
588             default:
589                 if (m_graph.clobbersWorld(index))
590                     return NoNode;
591                 break;
592             }
593         }
594         return NoNode;
595     }
596     
597     NodeIndex getScopeChainLoadElimination(unsigned depth)
598     {
599         for (unsigned i = endIndexForPureCSE(); i--;) {
600             NodeIndex index = m_currentBlock->at(i);
601             Node& node = m_graph[index];
602             if (node.op() == GetScopeChain
603                 && node.scopeChainDepth() == depth)
604                 return index;
605         }
606         return NoNode;
607     }
608     
609     NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp)
610     {
611         relevantLocalOp = NoNode;
612         
613         for (unsigned i = m_indexInBlock; i--;) {
614             NodeIndex index = m_currentBlock->at(i);
615             Node& node = m_graph[index];
616             switch (node.op()) {
617             case GetLocal:
618                 if (node.local() == local) {
619                     relevantLocalOp = index;
620                     return index;
621                 }
622                 break;
623                 
624             case GetLocalUnlinked:
625                 if (node.unlinkedLocal() == local) {
626                     relevantLocalOp = index;
627                     return index;
628                 }
629                 break;
630                 
631             case SetLocal:
632                 if (node.local() == local) {
633                     relevantLocalOp = index;
634                     return node.child1().index();
635                 }
636                 break;
637                 
638             default:
639                 if (m_graph.clobbersWorld(index))
640                     return NoNode;
641                 break;
642             }
643         }
644         return NoNode;
645     }
646     
647     struct SetLocalStoreEliminationResult {
648         SetLocalStoreEliminationResult()
649             : mayBeAccessed(false)
650             , mayExit(false)
651             , mayClobberWorld(false)
652         {
653         }
654         
655         bool mayBeAccessed;
656         bool mayExit;
657         bool mayClobberWorld;
658     };
659     SetLocalStoreEliminationResult setLocalStoreElimination(
660         VirtualRegister local, NodeIndex expectedNodeIndex)
661     {
662         SetLocalStoreEliminationResult result;
663         for (unsigned i = m_indexInBlock; i--;) {
664             NodeIndex index = m_currentBlock->at(i);
665             Node& node = m_graph[index];
666             if (!node.shouldGenerate())
667                 continue;
668             switch (node.op()) {
669             case GetLocal:
670             case Flush:
671                 if (node.local() == local)
672                     result.mayBeAccessed = true;
673                 break;
674                 
675             case GetLocalUnlinked:
676                 if (node.unlinkedLocal() == local)
677                     result.mayBeAccessed = true;
678                 break;
679                 
680             case SetLocal: {
681                 if (node.local() != local)
682                     break;
683                 if (index != expectedNodeIndex)
684                     result.mayBeAccessed = true;
685                 if (m_graph[index].refCount() > 1)
686                     result.mayBeAccessed = true;
687                 return result;
688             }
689                 
690             case GetScopeChain:
691                 if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
692                     result.mayBeAccessed = true;
693                 break;
694                 
695             case CheckArgumentsNotCreated:
696             case GetMyArgumentsLength:
697             case GetMyArgumentsLengthSafe:
698                 if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
699                     result.mayBeAccessed = true;
700                 break;
701                 
702             case GetMyArgumentByVal:
703             case GetMyArgumentByValSafe:
704                 result.mayBeAccessed = true;
705                 break;
706                 
707             case GetByVal:
708                 // If this is accessing arguments then it's potentially accessing locals.
709                 if (m_graph[node.child1()].shouldSpeculateArguments())
710                     result.mayBeAccessed = true;
711                 break;
712                 
713             case CreateArguments:
714             case TearOffActivation:
715             case TearOffArguments:
716                 // If an activation is being torn off then it means that captured variables
717                 // are live. We could be clever here and check if the local qualifies as an
718                 // argument register. But that seems like it would buy us very little since
719                 // any kind of tear offs are rare to begin with.
720                 result.mayBeAccessed = true;
721                 break;
722                 
723             default:
724                 break;
725             }
726             result.mayExit |= node.canExit();
727             result.mayClobberWorld |= m_graph.clobbersWorld(index);
728         }
729         ASSERT_NOT_REACHED();
730         // Be safe in release mode.
731         result.mayBeAccessed = true;
732         return result;
733     }
734     
735     void performSubstitution(Edge& child, bool addRef = true)
736     {
737         // Check if this operand is actually unused.
738         if (!child)
739             return;
740         
741         // Check if there is any replacement.
742         NodeIndex replacement = m_replacements[child.index()];
743         if (replacement == NoNode)
744             return;
745         
746         child.setIndex(replacement);
747         
748         // There is definitely a replacement. Assert that the replacement does not
749         // have a replacement.
750         ASSERT(m_replacements[child.index()] == NoNode);
751         
752         if (addRef)
753             m_graph[child].ref();
754     }
755     
756     enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
757     bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
758     {
759         if (replacement == NoNode)
760             return false;
761         
762         // Be safe. Don't try to perform replacements if the predictions don't
763         // agree.
764         if (predictionHandlingMode == RequireSamePrediction
765             && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
766             return false;
767         
768 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
769         dataLog("   Replacing @%u -> @%u", m_compileIndex, replacement);
770 #endif
771         
772         Node& node = m_graph[m_compileIndex];
773         node.setOpAndDefaultFlags(Phantom);
774         node.setRefCount(1);
775         
776         // At this point we will eliminate all references to this node.
777         m_replacements[m_compileIndex] = replacement;
778         
779         return true;
780     }
781     
782     void eliminate()
783     {
784 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
785         dataLog("   Eliminating @%u", m_compileIndex);
786 #endif
787         
788         Node& node = m_graph[m_compileIndex];
789         ASSERT(node.refCount() == 1);
790         ASSERT(node.mustGenerate());
791         node.setOpAndDefaultFlags(Phantom);
792     }
793     
794     void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
795     {
796         if (nodeIndex == NoNode)
797             return;
798         Node& node = m_graph[nodeIndex];
799         if (node.refCount() != 1)
800             return;
801         ASSERT(node.mustGenerate());
802         node.setOpAndDefaultFlags(phantomType);
803     }
804     
805     void performNodeCSE(Node& node)
806     {
807         bool shouldGenerate = node.shouldGenerate();
808
809         if (node.flags() & NodeHasVarArgs) {
810             for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
811                 performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
812         } else {
813             performSubstitution(node.children.child1(), shouldGenerate);
814             performSubstitution(node.children.child2(), shouldGenerate);
815             performSubstitution(node.children.child3(), shouldGenerate);
816         }
817         
818         if (!shouldGenerate)
819             return;
820         
821 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
822         dataLog("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
823 #endif
824         
825         // NOTE: there are some nodes that we deliberately don't CSE even though we
826         // probably could, like StrCat and ToPrimitive. That's because there is no
827         // evidence that doing CSE on these nodes would result in a performance
828         // progression. Hence considering these nodes in CSE would just mean that this
829         // code does more work with no win. Of course, we may want to reconsider this,
830         // since StrCat is trivially CSE-able. It's not trivially doable for
831         // ToPrimitive, but we could change that with some speculations if we really
832         // needed to.
833         
834         switch (node.op()) {
835         
836         // Handle the pure nodes. These nodes never have any side-effects.
837         case BitAnd:
838         case BitOr:
839         case BitXor:
840         case BitRShift:
841         case BitLShift:
842         case BitURShift:
843         case ArithAdd:
844         case ArithSub:
845         case ArithNegate:
846         case ArithMul:
847         case ArithMod:
848         case ArithDiv:
849         case ArithAbs:
850         case ArithMin:
851         case ArithMax:
852         case ArithSqrt:
853         case GetInt8ArrayLength:
854         case GetInt16ArrayLength:
855         case GetInt32ArrayLength:
856         case GetUint8ArrayLength:
857         case GetUint8ClampedArrayLength:
858         case GetUint16ArrayLength:
859         case GetUint32ArrayLength:
860         case GetFloat32ArrayLength:
861         case GetFloat64ArrayLength:
862         case GetCallee:
863         case GetStringLength:
864         case StringCharAt:
865         case StringCharCodeAt:
866         case Int32ToDouble:
867         case IsUndefined:
868         case IsBoolean:
869         case IsNumber:
870         case IsString:
871         case IsObject:
872         case IsFunction:
873         case DoubleAsInt32:
874         case LogicalNot:
875             setReplacement(pureCSE(node));
876             break;
877             
878         case GetLocal: {
879             VariableAccessData* variableAccessData = node.variableAccessData();
880             if (!variableAccessData->isCaptured())
881                 break;
882             NodeIndex relevantLocalOp;
883             NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp);
884             ASSERT(relevantLocalOp == NoNode
885                    || m_graph[relevantLocalOp].op() == GetLocalUnlinked
886                    || m_graph[relevantLocalOp].variableAccessData() == variableAccessData);
887             NodeIndex phiIndex = node.child1().index();
888             if (!setReplacement(possibleReplacement))
889                 break;
890             // If the GetLocal we replaced used to refer to a SetLocal, then it now
891             // should refer to the child of the SetLocal instead.
892             if (m_graph[phiIndex].op() == SetLocal) {
893                 ASSERT(node.child1().index() == phiIndex);
894                 m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
895             }
896             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
897                 variableAccessData->local());
898             if (oldTailIndex == m_compileIndex) {
899                 m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
900                     relevantLocalOp;
901                 
902                 // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
903                 // make sure that the GetLocalUnlinked is now linked.
904                 if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
905                     m_graph[relevantLocalOp].setOp(GetLocal);
906                     m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
907                     m_graph.ref(phiIndex);
908                 }
909             }
910             m_changed = true;
911             break;
912         }
913             
914         case GetLocalUnlinked: {
915             NodeIndex relevantLocalOpIgnored;
916             m_changed |= setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored));
917             break;
918         }
919             
920         case Flush: {
921             VariableAccessData* variableAccessData = node.variableAccessData();
922             VirtualRegister local = variableAccessData->local();
923             NodeIndex replacementIndex = node.child1().index();
924             Node& replacement = m_graph[replacementIndex];
925             if (replacement.op() != SetLocal)
926                 break;
927             ASSERT(replacement.variableAccessData() == variableAccessData);
928             // FIXME: We should be able to remove SetLocals that can exit; we just need
929             // to replace them with appropriate type checks.
930             if (m_fixpointState == FixpointNotConverged) {
931                 // Need to be conservative at this time; if the SetLocal has any chance of performing
932                 // any speculations then we cannot do anything.
933                 if (variableAccessData->isCaptured()) {
934                     // Captured SetLocals never speculate and hence never exit.
935                 } else {
936                     if (variableAccessData->shouldUseDoubleFormat())
937                         break;
938                     SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
939                     if (isInt32Speculation(prediction))
940                         break;
941                     if (isArraySpeculation(prediction))
942                         break;
943                     if (isBooleanSpeculation(prediction))
944                         break;
945                 }
946             } else {
947                 if (replacement.canExit())
948                     break;
949             }
950             SetLocalStoreEliminationResult result =
951                 setLocalStoreElimination(local, replacementIndex);
952             if (result.mayBeAccessed || result.mayClobberWorld)
953                 break;
954             ASSERT(replacement.op() == SetLocal);
955             ASSERT(replacement.refCount() == 1);
956             ASSERT(replacement.shouldGenerate());
957             // FIXME: Investigate using mayExit as a further optimization.
958             node.setOpAndDefaultFlags(Phantom);
959             NodeIndex dataNodeIndex = replacement.child1().index();
960             ASSERT(m_graph[dataNodeIndex].hasResult());
961             m_graph.clearAndDerefChild1(node);
962             node.children.child1() = Edge(dataNodeIndex);
963             m_graph.ref(dataNodeIndex);
964             NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
965             if (oldTailIndex == m_compileIndex)
966                 m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
967             m_changed = true;
968             break;
969         }
970             
971         case JSConstant:
972             // This is strange, but necessary. Some phases will convert nodes to constants,
973             // which may result in duplicated constants. We use CSE to clean this up.
974             setReplacement(constantCSE(node), AllowPredictionMismatch);
975             break;
976             
977         case WeakJSConstant:
978             // FIXME: have CSE for weak constants against strong constants and vice-versa.
979             setReplacement(weakConstantCSE(node));
980             break;
981             
982         case GetArrayLength:
983             setReplacement(impureCSE(node));
984             break;
985             
986         case GetScopeChain:
987             setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
988             break;
989
990         // Handle nodes that are conditionally pure: these are pure, and can
991         // be CSE'd, so long as the prediction is the one we want.
992         case ValueAdd:
993         case CompareLess:
994         case CompareLessEq:
995         case CompareGreater:
996         case CompareGreaterEq:
997         case CompareEq: {
998             if (m_graph.isPredictedNumerical(node)) {
999                 NodeIndex replacementIndex = pureCSE(node);
1000                 if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
1001                     setReplacement(replacementIndex);
1002             }
1003             break;
1004         }
1005             
1006         // Finally handle heap accesses. These are not quite pure, but we can still
1007         // optimize them provided that some subtle conditions are met.
1008         case GetGlobalVar:
1009             setReplacement(globalVarLoadElimination(node.registerPointer()));
1010             break;
1011             
1012         case GlobalVarWatchpoint:
1013             if (globalVarWatchpointElimination(node.registerPointer()))
1014                 eliminate();
1015             break;
1016             
1017         case PutGlobalVar:
1018         case PutGlobalVarCheck:
1019             if (m_fixpointState == FixpointNotConverged)
1020                 break;
1021             eliminate(globalVarStoreElimination(node.registerPointer()));
1022             break;
1023             
1024         case GetByVal:
1025             if (m_graph.byValIsPure(node))
1026                 setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
1027             break;
1028             
1029         case PutByVal:
1030             if (m_graph.byValIsPure(node)
1031                 && !m_graph[node.child1()].shouldSpeculateArguments()
1032                 && getByValLoadElimination(node.child1().index(), node.child2().index()) != NoNode)
1033                 node.setOp(PutByValAlias);
1034             break;
1035             
1036         case CheckStructure:
1037             if (checkStructureLoadElimination(node.structureSet(), node.child1().index()))
1038                 eliminate();
1039             break;
1040             
1041         case PutStructure:
1042             if (m_fixpointState == FixpointNotConverged)
1043                 break;
1044             eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
1045             break;
1046
1047         case CheckFunction:
1048             if (checkFunctionElimination(node.function(), node.child1().index()))
1049                 eliminate();
1050             break;
1051                 
1052         case GetIndexedPropertyStorage: {
1053             SpeculatedType basePrediction = m_graph[node.child2()].prediction();
1054             bool nodeHasIntegerIndexPrediction = !(!(basePrediction & SpecInt32) && basePrediction);
1055             setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), nodeHasIntegerIndexPrediction));
1056             break;
1057         }
1058
1059         case GetPropertyStorage:
1060             setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
1061             break;
1062
1063         case GetByOffset:
1064             setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1065             break;
1066             
1067         case PutByOffset:
1068             if (m_fixpointState == FixpointNotConverged)
1069                 break;
1070             eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
1071             break;
1072             
1073         default:
1074             // do nothing.
1075             break;
1076         }
1077         
1078         m_lastSeen[node.op()] = m_indexInBlock;
1079 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1080         dataLog("\n");
1081 #endif
1082     }
1083     
1084     void performBlockCSE(BasicBlock* block)
1085     {
1086         if (!block)
1087             return;
1088         if (!block->isReachable)
1089             return;
1090         
1091         m_currentBlock = block;
1092         for (unsigned i = 0; i < LastNodeType; ++i)
1093             m_lastSeen[i] = UINT_MAX;
1094
1095         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1096             m_compileIndex = block->at(m_indexInBlock);
1097             performNodeCSE(m_graph[m_compileIndex]);
1098         }
1099     }
1100     
1101     BasicBlock* m_currentBlock;
1102     NodeIndex m_compileIndex;
1103     unsigned m_indexInBlock;
1104     Vector<NodeIndex, 16> m_replacements;
1105     FixedArray<unsigned, LastNodeType> m_lastSeen;
1106     OptimizationFixpointState m_fixpointState;
1107     bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1108 };
1109
1110 bool performCSE(Graph& graph, OptimizationFixpointState fixpointState)
1111 {
1112     return runPhase<CSEPhase>(graph, fixpointState);
1113 }
1114
1115 } } // namespace JSC::DFG
1116
1117 #endif // ENABLE(DFG_JIT)
1118
1119