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