1/*
2 * Copyright (C) 2011, 2012, 2013, 2014 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 "DFGAbstractHeap.h"
32#include "DFGClobberize.h"
33#include "DFGEdgeUsesStructure.h"
34#include "DFGGraph.h"
35#include "DFGPhase.h"
36#include "JSCInlines.h"
37#include <array>
38#include <wtf/FastBitVector.h>
39
40namespace JSC { namespace DFG {
41
42enum CSEMode { NormalCSE, StoreElimination };
43
44template<CSEMode cseMode>
45class CSEPhase : public Phase {
46public:
47    CSEPhase(Graph& graph)
48        : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
49    {
50    }
51
52    bool run()
53    {
54        ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
55
56        m_changed = false;
57
58        m_graph.clearReplacements();
59
60        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
61            BasicBlock* block = m_graph.block(blockIndex);
62            if (!block)
63                continue;
64
65            // All Phis need to already be marked as relevant to OSR.
66            if (!ASSERT_DISABLED) {
67                for (unsigned i = 0; i < block->phis.size(); ++i)
68                    ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);
69            }
70
71            for (unsigned i = block->size(); i--;) {
72                Node* node = block->at(i);
73
74                switch (node->op()) {
75                case SetLocal:
76                case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.
77                    node->mergeFlags(NodeRelevantToOSR);
78                    break;
79                default:
80                    node->clearFlags(NodeRelevantToOSR);
81                    break;
82                }
83            }
84        }
85
86        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
87            BasicBlock* block = m_graph.block(blockIndex);
88            if (!block)
89                continue;
90
91            for (unsigned i = block->size(); i--;) {
92                Node* node = block->at(i);
93                if (!node->containsMovHint())
94                    continue;
95
96                ASSERT(node->op() != ZombieHint);
97                node->child1()->mergeFlags(NodeRelevantToOSR);
98            }
99        }
100
101        if (m_graph.m_form == SSA) {
102            Vector<BasicBlock*> depthFirst;
103            m_graph.getBlocksInDepthFirstOrder(depthFirst);
104            for (unsigned i = 0; i < depthFirst.size(); ++i)
105                performBlockCSE(depthFirst[i]);
106        } else {
107            for (unsigned blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
108                performBlockCSE(m_graph.block(blockIndex));
109        }
110
111        return m_changed;
112    }
113
114private:
115
116    unsigned endIndexForPureCSE()
117    {
118        unsigned result = m_lastSeen[m_currentNode->op()];
119        if (result == UINT_MAX)
120            result = 0;
121        else
122            result++;
123        ASSERT(result <= m_indexInBlock);
124        return result;
125    }
126
127    Node* pureCSE(Node* node)
128    {
129        Edge child1 = node->child1().sanitized();
130        Edge child2 = node->child2().sanitized();
131        Edge child3 = node->child3().sanitized();
132
133        for (unsigned i = endIndexForPureCSE(); i--;) {
134            Node* otherNode = m_currentBlock->at(i);
135            if (otherNode == child1 || otherNode == child2 || otherNode == child3)
136                break;
137
138            if (node->op() != otherNode->op())
139                continue;
140
141            Edge otherChild = otherNode->child1().sanitized();
142            if (!otherChild)
143                return otherNode;
144            if (otherChild != child1)
145                continue;
146
147            otherChild = otherNode->child2().sanitized();
148            if (!otherChild)
149                return otherNode;
150            if (otherChild != child2)
151                continue;
152
153            otherChild = otherNode->child3().sanitized();
154            if (!otherChild)
155                return otherNode;
156            if (otherChild != child3)
157                continue;
158
159            return otherNode;
160        }
161        return 0;
162    }
163
164    Node* constantCSE(Node* node)
165    {
166        for (unsigned i = endIndexForPureCSE(); i--;) {
167            Node* otherNode = m_currentBlock->at(i);
168            if (otherNode->op() != node->op())
169                continue;
170
171            if (otherNode->constantNumber() != node->constantNumber())
172                continue;
173
174            return otherNode;
175        }
176        return 0;
177    }
178
179    Node* weakConstantCSE(Node* node)
180    {
181        for (unsigned i = endIndexForPureCSE(); i--;) {
182            Node* otherNode = m_currentBlock->at(i);
183            if (otherNode->op() != WeakJSConstant)
184                continue;
185
186            if (otherNode->weakConstant() != node->weakConstant())
187                continue;
188
189            return otherNode;
190        }
191        return 0;
192    }
193
194    Node* constantStoragePointerCSE(Node* node)
195    {
196        for (unsigned i = endIndexForPureCSE(); i--;) {
197            Node* otherNode = m_currentBlock->at(i);
198            if (otherNode->op() != ConstantStoragePointer)
199                continue;
200
201            if (otherNode->storagePointer() != node->storagePointer())
202                continue;
203
204            return otherNode;
205        }
206        return 0;
207    }
208
209    Node* getCalleeLoadElimination()
210    {
211        for (unsigned i = m_indexInBlock; i--;) {
212            Node* node = m_currentBlock->at(i);
213            switch (node->op()) {
214            case GetCallee:
215                return node;
216            default:
217                break;
218            }
219        }
220        return 0;
221    }
222
223    Node* getArrayLengthElimination(Node* array)
224    {
225        for (unsigned i = m_indexInBlock; i--;) {
226            Node* node = m_currentBlock->at(i);
227            switch (node->op()) {
228            case GetArrayLength:
229                if (node->child1() == array)
230                    return node;
231                break;
232
233            case PutByValDirect:
234            case PutByVal:
235                if (!m_graph.byValIsPure(node))
236                    return 0;
237                if (node->arrayMode().mayStoreToHole())
238                    return 0;
239                break;
240
241            default:
242                if (m_graph.clobbersWorld(node))
243                    return 0;
244            }
245        }
246        return 0;
247    }
248
249    Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
250    {
251        for (unsigned i = m_indexInBlock; i--;) {
252            Node* node = m_currentBlock->at(i);
253            switch (node->op()) {
254            case GetGlobalVar:
255                if (node->registerPointer() == registerPointer)
256                    return node;
257                break;
258            case PutGlobalVar:
259                if (node->registerPointer() == registerPointer)
260                    return node->child1().node();
261                break;
262            default:
263                break;
264            }
265            if (m_graph.clobbersWorld(node))
266                break;
267        }
268        return 0;
269    }
270
271    Node* scopedVarLoadElimination(Node* registers, int varNumber)
272    {
273        for (unsigned i = m_indexInBlock; i--;) {
274            Node* node = m_currentBlock->at(i);
275            switch (node->op()) {
276            case GetClosureVar: {
277                if (node->child1() == registers && node->varNumber() == varNumber)
278                    return node;
279                break;
280            }
281            case PutClosureVar: {
282                if (node->varNumber() != varNumber)
283                    break;
284                if (node->child2() == registers)
285                    return node->child3().node();
286                return 0;
287            }
288            case SetLocal: {
289                VariableAccessData* variableAccessData = node->variableAccessData();
290                if (variableAccessData->isCaptured()
291                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
292                    return 0;
293                break;
294            }
295            default:
296                break;
297            }
298            if (m_graph.clobbersWorld(node))
299                break;
300        }
301        return 0;
302    }
303
304    bool varInjectionWatchpointElimination()
305    {
306        for (unsigned i = m_indexInBlock; i--;) {
307            Node* node = m_currentBlock->at(i);
308            if (node->op() == VarInjectionWatchpoint)
309                return true;
310            if (m_graph.clobbersWorld(node))
311                break;
312        }
313        return false;
314    }
315
316    Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
317    {
318        for (unsigned i = m_indexInBlock; i--;) {
319            Node* node = m_currentBlock->at(i);
320            switch (node->op()) {
321            case PutGlobalVar:
322                if (node->registerPointer() == registerPointer)
323                    return node;
324                break;
325
326            case GetGlobalVar:
327                if (node->registerPointer() == registerPointer)
328                    return 0;
329                break;
330
331            default:
332                break;
333            }
334            if (m_graph.clobbersWorld(node) || node->canExit())
335                return 0;
336        }
337        return 0;
338    }
339
340    Node* scopedVarStoreElimination(Node* scope, Node* registers, int varNumber)
341    {
342        for (unsigned i = m_indexInBlock; i--;) {
343            Node* node = m_currentBlock->at(i);
344            switch (node->op()) {
345            case PutClosureVar: {
346                if (node->varNumber() != varNumber)
347                    break;
348                if (node->child1() == scope && node->child2() == registers)
349                    return node;
350                return 0;
351            }
352
353            case GetClosureVar: {
354                // Let's be conservative.
355                if (node->varNumber() == varNumber)
356                    return 0;
357                break;
358            }
359
360            case GetLocal:
361            case SetLocal: {
362                VariableAccessData* variableAccessData = node->variableAccessData();
363                if (variableAccessData->isCaptured()
364                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
365                    return 0;
366                break;
367            }
368
369            default:
370                break;
371            }
372            if (m_graph.clobbersWorld(node) || node->canExit())
373                return 0;
374        }
375        return 0;
376    }
377
378    Node* getByValLoadElimination(Node* child1, Node* child2, ArrayMode arrayMode)
379    {
380        for (unsigned i = m_indexInBlock; i--;) {
381            Node* node = m_currentBlock->at(i);
382            if (node == child1 || node == child2)
383                break;
384
385            switch (node->op()) {
386            case GetByVal:
387                if (!m_graph.byValIsPure(node))
388                    return 0;
389                if (node->child1() == child1
390                    && node->child2() == child2
391                    && node->arrayMode().type() == arrayMode.type())
392                    return node;
393                break;
394
395            case PutByValDirect:
396            case PutByVal:
397            case PutByValAlias: {
398                if (!m_graph.byValIsPure(node))
399                    return 0;
400                // Typed arrays
401                if (arrayMode.typedArrayType() != NotTypedArray)
402                    return 0;
403                if (m_graph.varArgChild(node, 0) == child1
404                    && m_graph.varArgChild(node, 1) == child2
405                    && node->arrayMode().type() == arrayMode.type())
406                    return m_graph.varArgChild(node, 2).node();
407                // We must assume that the PutByVal will clobber the location we're getting from.
408                // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
409                // different type than the GetByVal, then we know that they won't clobber each other.
410                // ... except of course for typed arrays, where all typed arrays clobber all other
411                // typed arrays!  An Int32Array can alias a Float64Array for example, and so on.
412                return 0;
413            }
414            default:
415                if (m_graph.clobbersWorld(node))
416                    return 0;
417                break;
418            }
419        }
420        return 0;
421    }
422
423    bool checkFunctionElimination(JSCell* function, Node* child1)
424    {
425        for (unsigned i = endIndexForPureCSE(); i--;) {
426            Node* node = m_currentBlock->at(i);
427            if (node == child1)
428                break;
429
430            if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)
431                return true;
432        }
433        return false;
434    }
435
436    bool checkExecutableElimination(ExecutableBase* executable, Node* child1)
437    {
438        for (unsigned i = endIndexForPureCSE(); i--;) {
439            Node* node = m_currentBlock->at(i);
440            if (node == child1)
441                break;
442
443            if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)
444                return true;
445        }
446        return false;
447    }
448
449    bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
450    {
451        for (unsigned i = m_indexInBlock; i--;) {
452            Node* node = m_currentBlock->at(i);
453            if (node == child1)
454                break;
455
456            switch (node->op()) {
457            case CheckStructure:
458                if (node->child1() == child1
459                    && structureSet.isSupersetOf(node->structureSet()))
460                    return true;
461                break;
462
463            case StructureTransitionWatchpoint:
464                if (node->child1() == child1
465                    && structureSet.contains(node->structure()))
466                    return true;
467                break;
468
469            case PutStructure:
470                if (node->child1() == child1
471                    && structureSet.contains(node->structureTransitionData().newStructure))
472                    return true;
473                if (structureSet.contains(node->structureTransitionData().previousStructure))
474                    return false;
475                break;
476
477            case PutByOffset:
478                // Setting a property cannot change the structure.
479                break;
480
481            case MultiPutByOffset:
482                if (node->multiPutByOffsetData().writesStructures())
483                    return false;
484                break;
485
486            case PutByValDirect:
487            case PutByVal:
488            case PutByValAlias:
489                if (m_graph.byValIsPure(node)) {
490                    // If PutByVal speculates that it's accessing an array with an
491                    // integer index, then it's impossible for it to cause a structure
492                    // change.
493                    break;
494                }
495                return false;
496
497            case Arrayify:
498            case ArrayifyToStructure:
499                // We could check if the arrayification could affect our structures.
500                // But that seems like it would take Effort.
501                return false;
502
503            default:
504                if (m_graph.clobbersWorld(node))
505                    return false;
506                break;
507            }
508        }
509        return false;
510    }
511
512    bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
513    {
514        for (unsigned i = m_indexInBlock; i--;) {
515            Node* node = m_currentBlock->at(i);
516            if (node == child1)
517                break;
518
519            switch (node->op()) {
520            case CheckStructure:
521                if (node->child1() == child1
522                    && node->structureSet().containsOnly(structure))
523                    return true;
524                break;
525
526            case PutStructure:
527                ASSERT(node->structureTransitionData().previousStructure != structure);
528                break;
529
530            case PutByOffset:
531                // Setting a property cannot change the structure.
532                break;
533
534            case MultiPutByOffset:
535                if (node->multiPutByOffsetData().writesStructures())
536                    return false;
537                break;
538
539            case PutByValDirect:
540            case PutByVal:
541            case PutByValAlias:
542                if (m_graph.byValIsPure(node)) {
543                    // If PutByVal speculates that it's accessing an array with an
544                    // integer index, then it's impossible for it to cause a structure
545                    // change.
546                    break;
547                }
548                return false;
549
550            case StructureTransitionWatchpoint:
551                if (node->structure() == structure && node->child1() == child1)
552                    return true;
553                break;
554
555            case Arrayify:
556            case ArrayifyToStructure:
557                // We could check if the arrayification could affect our structures.
558                // But that seems like it would take Effort.
559                return false;
560
561            default:
562                if (m_graph.clobbersWorld(node))
563                    return false;
564                break;
565            }
566        }
567        return false;
568    }
569
570    Node* putStructureStoreElimination(Node* child1)
571    {
572        for (unsigned i = m_indexInBlock; i--;) {
573            Node* node = m_currentBlock->at(i);
574            if (node == child1)
575                break;
576            switch (node->op()) {
577            case CheckStructure:
578                return 0;
579
580            case PhantomPutStructure:
581                if (node->child1() == child1) // No need to retrace our steps.
582                    return 0;
583                break;
584
585            case PutStructure:
586                if (node->child1() == child1)
587                    return node;
588                break;
589
590            // PutStructure needs to execute if we GC. Hence this needs to
591            // be careful with respect to nodes that GC.
592            case CreateArguments:
593            case TearOffArguments:
594            case NewFunctionNoCheck:
595            case NewFunction:
596            case NewFunctionExpression:
597            case CreateActivation:
598            case TearOffActivation:
599            case ToPrimitive:
600            case NewRegexp:
601            case NewArrayBuffer:
602            case NewArray:
603            case NewObject:
604            case CreateThis:
605            case AllocatePropertyStorage:
606            case ReallocatePropertyStorage:
607            case TypeOf:
608            case ToString:
609            case NewStringObject:
610            case MakeRope:
611            case NewTypedArray:
612            case MultiPutByOffset:
613                return 0;
614
615            // This either exits, causes a GC (lazy string allocation), or clobbers
616            // the world. The chances of it not doing any of those things are so
617            // slim that we might as well not even try to reason about it.
618            case GetByVal:
619                return 0;
620
621            case GetIndexedPropertyStorage:
622                if (node->arrayMode().getIndexedPropertyStorageMayTriggerGC())
623                    return 0;
624                break;
625
626            default:
627                break;
628            }
629            if (m_graph.clobbersWorld(node) || node->canExit())
630                return 0;
631            if (edgesUseStructure(m_graph, node))
632                return 0;
633        }
634        return 0;
635    }
636
637    Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* base)
638    {
639        for (unsigned i = m_indexInBlock; i--;) {
640            Node* node = m_currentBlock->at(i);
641            if (node == base)
642                break;
643
644            switch (node->op()) {
645            case GetByOffset:
646                if (node->child2() == base
647                    && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
648                    return node;
649                break;
650
651            case MultiGetByOffset:
652                if (node->child1() == base
653                    && node->multiGetByOffsetData().identifierNumber == identifierNumber)
654                    return node;
655                break;
656
657            case PutByOffset:
658                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
659                    if (node->child2() == base) // Must be same property storage.
660                        return node->child3().node();
661                    return 0;
662                }
663                break;
664
665            case MultiPutByOffset:
666                if (node->multiPutByOffsetData().identifierNumber == identifierNumber) {
667                    if (node->child1() == base)
668                        return node->child2().node();
669                    return 0;
670                }
671                break;
672
673            case PutByValDirect:
674            case PutByVal:
675            case PutByValAlias:
676                if (m_graph.byValIsPure(node)) {
677                    // If PutByVal speculates that it's accessing an array with an
678                    // integer index, then it's impossible for it to cause a structure
679                    // change.
680                    break;
681                }
682                return 0;
683
684            default:
685                if (m_graph.clobbersWorld(node))
686                    return 0;
687                break;
688            }
689        }
690        return 0;
691    }
692
693    Node* putByOffsetStoreElimination(unsigned identifierNumber, Node* child1)
694    {
695        for (unsigned i = m_indexInBlock; i--;) {
696            Node* node = m_currentBlock->at(i);
697            if (node == child1)
698                break;
699
700            switch (node->op()) {
701            case GetByOffset:
702                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
703                    return 0;
704                break;
705
706            case PutByOffset:
707                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
708                    if (node->child1() == child1) // Must be same property storage.
709                        return node;
710                    return 0;
711                }
712                break;
713
714            case MultiPutByOffset:
715                if (node->multiPutByOffsetData().identifierNumber == identifierNumber)
716                    return 0;
717                break;
718
719            case PutByValDirect:
720            case PutByVal:
721            case PutByValAlias:
722            case GetByVal:
723                if (m_graph.byValIsPure(node)) {
724                    // If PutByVal speculates that it's accessing an array with an
725                    // integer index, then it's impossible for it to cause a structure
726                    // change.
727                    break;
728                }
729                return 0;
730
731            default:
732                if (m_graph.clobbersWorld(node))
733                    return 0;
734                break;
735            }
736            if (node->canExit())
737                return 0;
738        }
739        return 0;
740    }
741
742    Node* getPropertyStorageLoadElimination(Node* child1)
743    {
744        for (unsigned i = m_indexInBlock; i--;) {
745            Node* node = m_currentBlock->at(i);
746            if (node == child1)
747                break;
748
749            switch (node->op()) {
750            case GetButterfly:
751                if (node->child1() == child1)
752                    return node;
753                break;
754
755            case AllocatePropertyStorage:
756            case ReallocatePropertyStorage:
757                // If we can cheaply prove this is a change to our object's storage, we
758                // can optimize and use its result.
759                if (node->child1() == child1)
760                    return node;
761                // Otherwise, we currently can't prove that this doesn't change our object's
762                // storage, so we conservatively assume that it may change the storage
763                // pointer of any object, including ours.
764                return 0;
765
766            case PutByValDirect:
767            case PutByVal:
768            case PutByValAlias:
769                if (m_graph.byValIsPure(node)) {
770                    // If PutByVal speculates that it's accessing an array with an
771                    // integer index, then it's impossible for it to cause a structure
772                    // change.
773                    break;
774                }
775                return 0;
776
777            case Arrayify:
778            case ArrayifyToStructure:
779                // We could check if the arrayification could affect our butterfly.
780                // But that seems like it would take Effort.
781                return 0;
782
783            case MultiPutByOffset:
784                if (node->multiPutByOffsetData().reallocatesStorage())
785                    return 0;
786                break;
787
788            default:
789                if (m_graph.clobbersWorld(node))
790                    return 0;
791                break;
792            }
793        }
794        return 0;
795    }
796
797    bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
798    {
799        for (unsigned i = m_indexInBlock; i--;) {
800            Node* node = m_currentBlock->at(i);
801            if (node == child1)
802                break;
803
804            switch (node->op()) {
805            case CheckArray:
806                if (node->child1() == child1 && node->arrayMode() == arrayMode)
807                    return true;
808                break;
809
810            case Arrayify:
811            case ArrayifyToStructure:
812                // We could check if the arrayification could affect our array.
813                // But that seems like it would take Effort.
814                return false;
815
816            default:
817                if (m_graph.clobbersWorld(node))
818                    return false;
819                break;
820            }
821        }
822        return false;
823    }
824
825    Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)
826    {
827        for (unsigned i = m_indexInBlock; i--;) {
828            Node* node = m_currentBlock->at(i);
829            if (node == child1)
830                break;
831
832            switch (node->op()) {
833            case GetIndexedPropertyStorage: {
834                if (node->child1() == child1 && node->arrayMode() == arrayMode)
835                    return node;
836                break;
837            }
838
839            default:
840                if (m_graph.clobbersWorld(node))
841                    return 0;
842                break;
843            }
844        }
845        return 0;
846    }
847
848    Node* getTypedArrayByteOffsetLoadElimination(Node* child1)
849    {
850        for (unsigned i = m_indexInBlock; i--;) {
851            Node* node = m_currentBlock->at(i);
852            if (node == child1)
853                break;
854
855            switch (node->op()) {
856            case GetTypedArrayByteOffset: {
857                if (node->child1() == child1)
858                    return node;
859                break;
860            }
861
862            default:
863                if (m_graph.clobbersWorld(node))
864                    return 0;
865                break;
866            }
867        }
868        return 0;
869    }
870
871    Node* getMyScopeLoadElimination()
872    {
873        for (unsigned i = m_indexInBlock; i--;) {
874            Node* node = m_currentBlock->at(i);
875            switch (node->op()) {
876            case CreateActivation:
877                // This may cause us to return a different scope.
878                return 0;
879            case GetMyScope:
880                return node;
881            default:
882                break;
883            }
884        }
885        return 0;
886    }
887
888    Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
889    {
890        relevantLocalOp = 0;
891
892        for (unsigned i = m_indexInBlock; i--;) {
893            Node* node = m_currentBlock->at(i);
894            switch (node->op()) {
895            case GetLocal:
896                if (node->local() == local) {
897                    relevantLocalOp = node;
898                    return node;
899                }
900                break;
901
902            case GetLocalUnlinked:
903                if (node->unlinkedLocal() == local) {
904                    relevantLocalOp = node;
905                    return node;
906                }
907                break;
908
909            case SetLocal:
910                if (node->local() == local) {
911                    relevantLocalOp = node;
912                    return node->child1().node();
913                }
914                break;
915
916            case GetClosureVar:
917            case PutClosureVar:
918                if (static_cast<VirtualRegister>(node->varNumber()) == local)
919                    return 0;
920                break;
921
922            default:
923                if (careAboutClobbering && m_graph.clobbersWorld(node))
924                    return 0;
925                break;
926            }
927        }
928        return 0;
929    }
930
931    bool uncapturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
932    {
933        for (unsigned i = m_indexInBlock; i--;) {
934            Node* node = m_currentBlock->at(i);
935            switch (node->op()) {
936            case GetLocal:
937            case Flush:
938                if (node->local() == local)
939                    return false;
940                break;
941
942            case GetLocalUnlinked:
943                if (node->unlinkedLocal() == local)
944                    return false;
945                break;
946
947            case SetLocal: {
948                if (node->local() != local)
949                    break;
950                if (node != expectedNode)
951                    return false;
952                return true;
953            }
954
955            case GetClosureVar:
956            case PutClosureVar:
957                if (static_cast<VirtualRegister>(node->varNumber()) == local)
958                    return false;
959                break;
960
961            case GetMyScope:
962            case SkipTopScope:
963                if (node->origin.semantic.inlineCallFrame)
964                    break;
965                if (m_graph.uncheckedActivationRegister() == local)
966                    return false;
967                break;
968
969            case CheckArgumentsNotCreated:
970            case GetMyArgumentsLength:
971            case GetMyArgumentsLengthSafe:
972                if (m_graph.uncheckedArgumentsRegisterFor(node->origin.semantic) == local)
973                    return false;
974                break;
975
976            case GetMyArgumentByVal:
977            case GetMyArgumentByValSafe:
978                return false;
979
980            case GetByVal:
981                // If this is accessing arguments then it's potentially accessing locals.
982                if (node->arrayMode().type() == Array::Arguments)
983                    return false;
984                break;
985
986            case CreateArguments:
987            case TearOffActivation:
988            case TearOffArguments:
989                // If an activation is being torn off then it means that captured variables
990                // are live. We could be clever here and check if the local qualifies as an
991                // argument register. But that seems like it would buy us very little since
992                // any kind of tear offs are rare to begin with.
993                return false;
994
995            default:
996                break;
997            }
998            if (m_graph.clobbersWorld(node))
999                return false;
1000        }
1001        RELEASE_ASSERT_NOT_REACHED();
1002        return false;
1003    }
1004
1005    bool capturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
1006    {
1007        for (unsigned i = m_indexInBlock; i--;) {
1008            Node* node = m_currentBlock->at(i);
1009            switch (node->op()) {
1010            case GetLocal:
1011            case Flush:
1012                if (node->local() == local)
1013                    return false;
1014                break;
1015
1016            case GetLocalUnlinked:
1017                if (node->unlinkedLocal() == local)
1018                    return false;
1019                break;
1020
1021            case SetLocal: {
1022                if (node->local() != local)
1023                    break;
1024                if (node != expectedNode)
1025                    return false;
1026                return true;
1027            }
1028
1029            case Phantom:
1030            case Check:
1031            case HardPhantom:
1032            case MovHint:
1033            case JSConstant:
1034            case DoubleConstant:
1035            case Int52Constant:
1036                break;
1037
1038            default:
1039                return false;
1040            }
1041        }
1042        RELEASE_ASSERT_NOT_REACHED();
1043        return false;
1044    }
1045
1046    bool setLocalStoreElimination(VariableAccessData* variableAccessData, Node* expectedNode)
1047    {
1048        if (variableAccessData->isCaptured())
1049            return capturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
1050        return uncapturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
1051    }
1052
1053    bool invalidationPointElimination()
1054    {
1055        for (unsigned i = m_indexInBlock; i--;) {
1056            Node* node = m_currentBlock->at(i);
1057            if (node->op() == InvalidationPoint)
1058                return true;
1059            if (writesOverlap(m_graph, node, Watchpoint_fire))
1060                break;
1061        }
1062        return false;
1063    }
1064
1065    void eliminateIrrelevantPhantomChildren(Node* node)
1066    {
1067        ASSERT(node->op() == Phantom);
1068        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
1069            Edge edge = node->children.child(i);
1070            if (!edge)
1071                continue;
1072            if (edge.useKind() != UntypedUse)
1073                continue; // Keep the type check.
1074            if (edge->flags() & NodeRelevantToOSR)
1075                continue;
1076
1077            node->children.removeEdge(i--);
1078            m_changed = true;
1079        }
1080    }
1081
1082    bool setReplacement(Node* replacement)
1083    {
1084        if (!replacement)
1085            return false;
1086
1087        if (!ASSERT_DISABLED
1088            && canonicalResultRepresentation(m_currentNode->result()) != canonicalResultRepresentation(replacement->result())) {
1089            startCrashing();
1090            dataLog("CSE attempting to replace a node with a mismatched result: ", m_currentNode, " with ", replacement, "\n");
1091            dataLog("\n");
1092            m_graph.dump();
1093            RELEASE_ASSERT_NOT_REACHED();
1094        }
1095
1096        m_currentNode->convertToPhantom();
1097        eliminateIrrelevantPhantomChildren(m_currentNode);
1098
1099        // At this point we will eliminate all references to this node.
1100        m_currentNode->misc.replacement = replacement;
1101
1102        m_changed = true;
1103
1104        return true;
1105    }
1106
1107    void eliminate()
1108    {
1109        ASSERT(m_currentNode->mustGenerate());
1110        m_currentNode->convertToPhantom();
1111        eliminateIrrelevantPhantomChildren(m_currentNode);
1112
1113        m_changed = true;
1114    }
1115
1116    void eliminate(Node* node, NodeType phantomType = Phantom)
1117    {
1118        if (!node)
1119            return;
1120        ASSERT(node->mustGenerate());
1121        node->setOpAndDefaultFlags(phantomType);
1122        if (phantomType == Phantom)
1123            eliminateIrrelevantPhantomChildren(node);
1124
1125        m_changed = true;
1126    }
1127
1128    void performNodeCSE(Node* node)
1129    {
1130        if (cseMode == NormalCSE)
1131            m_graph.performSubstitution(node);
1132
1133        switch (node->op()) {
1134
1135        case Identity:
1136            if (cseMode == StoreElimination)
1137                break;
1138            setReplacement(node->child1().node());
1139            break;
1140
1141        // Handle the pure nodes. These nodes never have any side-effects.
1142        case BitAnd:
1143        case BitOr:
1144        case BitXor:
1145        case BitRShift:
1146        case BitLShift:
1147        case BitURShift:
1148        case ArithAbs:
1149        case ArithMin:
1150        case ArithMax:
1151        case ArithSqrt:
1152        case ArithFRound:
1153        case ArithSin:
1154        case ArithCos:
1155        case StringCharAt:
1156        case StringCharCodeAt:
1157        case IsUndefined:
1158        case IsBoolean:
1159        case IsNumber:
1160        case IsString:
1161        case IsObject:
1162        case IsFunction:
1163        case LogicalNot:
1164        case SkipTopScope:
1165        case SkipScope:
1166        case GetClosureRegisters:
1167        case GetScope:
1168        case TypeOf:
1169        case CompareEqConstant:
1170        case ValueToInt32:
1171        case MakeRope:
1172        case DoubleRep:
1173        case ValueRep:
1174        case Int52Rep:
1175        case BooleanToNumber:
1176            if (cseMode == StoreElimination)
1177                break;
1178            setReplacement(pureCSE(node));
1179            break;
1180
1181        case ArithAdd:
1182        case ArithSub:
1183        case ArithNegate:
1184        case ArithMul:
1185        case ArithDiv:
1186        case ArithMod:
1187        case UInt32ToNumber:
1188        case DoubleAsInt32: {
1189            if (cseMode == StoreElimination)
1190                break;
1191            Node* candidate = pureCSE(node);
1192            if (!candidate)
1193                break;
1194            if (!subsumes(candidate->arithMode(), node->arithMode())) {
1195                if (!subsumes(node->arithMode(), candidate->arithMode()))
1196                    break;
1197                candidate->setArithMode(node->arithMode());
1198            }
1199            setReplacement(candidate);
1200            break;
1201        }
1202
1203        case GetCallee:
1204            if (cseMode == StoreElimination)
1205                break;
1206            setReplacement(getCalleeLoadElimination());
1207            break;
1208
1209        case GetLocal: {
1210            if (cseMode == StoreElimination)
1211                break;
1212            VariableAccessData* variableAccessData = node->variableAccessData();
1213            if (!variableAccessData->isCaptured())
1214                break;
1215            Node* relevantLocalOp;
1216            Node* possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
1217            if (!relevantLocalOp)
1218                break;
1219            if (relevantLocalOp->op() != GetLocalUnlinked
1220                && relevantLocalOp->variableAccessData() != variableAccessData)
1221                break;
1222            Node* phi = node->child1().node();
1223            if (!setReplacement(possibleReplacement))
1224                break;
1225
1226            m_graph.dethread();
1227
1228            // If we replace a GetLocal with a GetLocalUnlinked, then turn the GetLocalUnlinked
1229            // into a GetLocal.
1230            if (relevantLocalOp->op() == GetLocalUnlinked)
1231                relevantLocalOp->convertToGetLocal(variableAccessData, phi);
1232
1233            m_changed = true;
1234            break;
1235        }
1236
1237        case GetLocalUnlinked: {
1238            if (cseMode == StoreElimination)
1239                break;
1240            Node* relevantLocalOpIgnored;
1241            setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
1242            break;
1243        }
1244
1245        case Flush: {
1246            ASSERT(m_graph.m_form != SSA);
1247            VariableAccessData* variableAccessData = node->variableAccessData();
1248            if (!node->child1()) {
1249                // FIXME: It's silly that we punt on flush-eliminating here. We don't really
1250                // need child1 to figure out what's going on.
1251                // https://bugs.webkit.org/show_bug.cgi?id=130521
1252                break;
1253            }
1254            Node* replacement = node->child1().node();
1255            if (replacement->op() != SetLocal)
1256                break;
1257            ASSERT(replacement->variableAccessData() == variableAccessData);
1258            // FIXME: We should be able to remove SetLocals that can exit; we just need
1259            // to replace them with appropriate type checks.
1260            if (cseMode == NormalCSE) {
1261                // Need to be conservative at this time; if the SetLocal has any chance of performing
1262                // any speculations then we cannot do anything.
1263                FlushFormat format = variableAccessData->flushFormat();
1264                ASSERT(format != DeadFlush);
1265                if (format != FlushedJSValue)
1266                    break;
1267            } else {
1268                if (replacement->canExit())
1269                    break;
1270            }
1271            if (!setLocalStoreElimination(variableAccessData, replacement))
1272                break;
1273            ASSERT(replacement->op() == SetLocal);
1274            node->convertToPhantom();
1275            Node* dataNode = replacement->child1().node();
1276            ASSERT(dataNode->hasResult());
1277            node->child1() = dataNode->defaultEdge();
1278            m_graph.dethread();
1279            m_changed = true;
1280            break;
1281        }
1282
1283        case JSConstant:
1284        case DoubleConstant:
1285        case Int52Constant:
1286            if (cseMode == StoreElimination)
1287                break;
1288            // This is strange, but necessary. Some phases will convert nodes to constants,
1289            // which may result in duplicated constants. We use CSE to clean this up.
1290            setReplacement(constantCSE(node));
1291            break;
1292
1293        case WeakJSConstant:
1294            if (cseMode == StoreElimination)
1295                break;
1296            // FIXME: have CSE for weak constants against strong constants and vice-versa.
1297            setReplacement(weakConstantCSE(node));
1298            break;
1299
1300        case ConstantStoragePointer:
1301            if (cseMode == StoreElimination)
1302                break;
1303            setReplacement(constantStoragePointerCSE(node));
1304            break;
1305
1306        case GetArrayLength:
1307            if (cseMode == StoreElimination)
1308                break;
1309            setReplacement(getArrayLengthElimination(node->child1().node()));
1310            break;
1311
1312        case GetMyScope:
1313            if (cseMode == StoreElimination)
1314                break;
1315            setReplacement(getMyScopeLoadElimination());
1316            break;
1317
1318        // Handle nodes that are conditionally pure: these are pure, and can
1319        // be CSE'd, so long as the prediction is the one we want.
1320        case CompareLess:
1321        case CompareLessEq:
1322        case CompareGreater:
1323        case CompareGreaterEq:
1324        case CompareEq: {
1325            if (cseMode == StoreElimination)
1326                break;
1327            if (m_graph.isPredictedNumerical(node)) {
1328                Node* replacement = pureCSE(node);
1329                if (replacement && m_graph.isPredictedNumerical(replacement))
1330                    setReplacement(replacement);
1331            }
1332            break;
1333        }
1334
1335        // Finally handle heap accesses. These are not quite pure, but we can still
1336        // optimize them provided that some subtle conditions are met.
1337        case GetGlobalVar:
1338            if (cseMode == StoreElimination)
1339                break;
1340            setReplacement(globalVarLoadElimination(node->registerPointer()));
1341            break;
1342
1343        case GetClosureVar: {
1344            if (cseMode == StoreElimination)
1345                break;
1346            setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
1347            break;
1348        }
1349
1350        case VarInjectionWatchpoint:
1351            if (cseMode == StoreElimination)
1352                break;
1353            if (varInjectionWatchpointElimination())
1354                eliminate();
1355            break;
1356
1357        case PutGlobalVar:
1358            if (cseMode == NormalCSE)
1359                break;
1360            eliminate(globalVarStoreElimination(node->registerPointer()));
1361            break;
1362
1363        case PutClosureVar: {
1364            if (cseMode == NormalCSE)
1365                break;
1366            eliminate(scopedVarStoreElimination(node->child1().node(), node->child2().node(), node->varNumber()));
1367            break;
1368        }
1369
1370        case GetByVal:
1371            if (cseMode == StoreElimination)
1372                break;
1373            if (m_graph.byValIsPure(node))
1374                setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node(), node->arrayMode()));
1375            break;
1376
1377        case PutByValDirect:
1378        case PutByVal: {
1379            if (cseMode == StoreElimination)
1380                break;
1381            Edge child1 = m_graph.varArgChild(node, 0);
1382            Edge child2 = m_graph.varArgChild(node, 1);
1383            if (node->arrayMode().canCSEStorage()) {
1384                Node* replacement = getByValLoadElimination(child1.node(), child2.node(), node->arrayMode());
1385                if (!replacement)
1386                    break;
1387                node->setOp(PutByValAlias);
1388            }
1389            break;
1390        }
1391
1392        case CheckStructure:
1393            if (cseMode == StoreElimination)
1394                break;
1395            if (checkStructureElimination(node->structureSet(), node->child1().node()))
1396                eliminate();
1397            break;
1398
1399        case StructureTransitionWatchpoint:
1400            if (cseMode == StoreElimination)
1401                break;
1402            if (structureTransitionWatchpointElimination(node->structure(), node->child1().node()))
1403                eliminate();
1404            break;
1405
1406        case PutStructure:
1407            if (cseMode == NormalCSE)
1408                break;
1409            eliminate(putStructureStoreElimination(node->child1().node()), PhantomPutStructure);
1410            break;
1411
1412        case CheckFunction:
1413            if (cseMode == StoreElimination)
1414                break;
1415            if (checkFunctionElimination(node->function(), node->child1().node()))
1416                eliminate();
1417            break;
1418
1419        case CheckExecutable:
1420            if (cseMode == StoreElimination)
1421                break;
1422            if (checkExecutableElimination(node->executable(), node->child1().node()))
1423                eliminate();
1424            break;
1425
1426        case CheckArray:
1427            if (cseMode == StoreElimination)
1428                break;
1429            if (checkArrayElimination(node->child1().node(), node->arrayMode()))
1430                eliminate();
1431            break;
1432
1433        case GetIndexedPropertyStorage: {
1434            if (cseMode == StoreElimination)
1435                break;
1436            setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
1437            break;
1438        }
1439
1440        case GetTypedArrayByteOffset: {
1441            if (cseMode == StoreElimination)
1442                break;
1443            setReplacement(getTypedArrayByteOffsetLoadElimination(node->child1().node()));
1444            break;
1445        }
1446
1447        case GetButterfly:
1448            if (cseMode == StoreElimination)
1449                break;
1450            setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
1451            break;
1452
1453        case GetByOffset:
1454            if (cseMode == StoreElimination)
1455                break;
1456            setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
1457            break;
1458
1459        case MultiGetByOffset:
1460            if (cseMode == StoreElimination)
1461                break;
1462            setReplacement(getByOffsetLoadElimination(node->multiGetByOffsetData().identifierNumber, node->child1().node()));
1463            break;
1464
1465        case PutByOffset:
1466            if (cseMode == NormalCSE)
1467                break;
1468            eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
1469            break;
1470
1471        case InvalidationPoint:
1472            if (invalidationPointElimination())
1473                eliminate();
1474            break;
1475
1476        case Phantom:
1477            // FIXME: we ought to remove Phantom's that have no children.
1478            // NB. It would be incorrect to do this for HardPhantom. In fact, the whole point
1479            // of HardPhantom is that we *don't* do this for HardPhantoms, since they signify
1480            // a more strict kind of liveness than the Phantom bytecode liveness.
1481            eliminateIrrelevantPhantomChildren(node);
1482            break;
1483
1484        default:
1485            // do nothing.
1486            break;
1487        }
1488
1489        m_lastSeen[node->op()] = m_indexInBlock;
1490    }
1491
1492    void performBlockCSE(BasicBlock* block)
1493    {
1494        if (!block)
1495            return;
1496        if (!block->isReachable)
1497            return;
1498
1499        m_currentBlock = block;
1500        for (unsigned i = 0; i < LastNodeType; ++i)
1501            m_lastSeen[i] = UINT_MAX;
1502
1503        for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
1504            m_currentNode = block->at(m_indexInBlock);
1505            performNodeCSE(m_currentNode);
1506        }
1507
1508        if (!ASSERT_DISABLED && cseMode == StoreElimination) {
1509            // Nobody should have replacements set.
1510            for (unsigned i = 0; i < block->size(); ++i)
1511                ASSERT(!block->at(i)->misc.replacement);
1512        }
1513    }
1514
1515    BasicBlock* m_currentBlock;
1516    Node* m_currentNode;
1517    unsigned m_indexInBlock;
1518    std::array<unsigned, LastNodeType> m_lastSeen;
1519    bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
1520};
1521
1522bool performCSE(Graph& graph)
1523{
1524    SamplingRegion samplingRegion("DFG CSE Phase");
1525    return runPhase<CSEPhase<NormalCSE>>(graph);
1526}
1527
1528bool performStoreElimination(Graph& graph)
1529{
1530    SamplingRegion samplingRegion("DFG Store Elimination Phase");
1531    return runPhase<CSEPhase<StoreElimination>>(graph);
1532}
1533
1534} } // namespace JSC::DFG
1535
1536#endif // ENABLE(DFG_JIT)
1537
1538
1539