[DFG] CheckTypeInfoFlags should say `eliminated` if it is removed in constant folding...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGConstantFoldingPhase.cpp
1 /*
2  * Copyright (C) 2012-2018 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 "DFGConstantFoldingPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "BuiltinNames.h"
32 #include "DFGAbstractInterpreterInlines.h"
33 #include "DFGArgumentsUtilities.h"
34 #include "DFGBasicBlockInlines.h"
35 #include "DFGGraph.h"
36 #include "DFGInPlaceAbstractState.h"
37 #include "DFGInferredTypeCheck.h"
38 #include "DFGInsertionSet.h"
39 #include "DFGPhase.h"
40 #include "GetByIdStatus.h"
41 #include "JSCInlines.h"
42 #include "PutByIdStatus.h"
43
44 namespace JSC { namespace DFG {
45
46 class ConstantFoldingPhase : public Phase {
47 public:
48     ConstantFoldingPhase(Graph& graph)
49         : Phase(graph, "constant folding")
50         , m_state(graph)
51         , m_interpreter(graph, m_state)
52         , m_insertionSet(graph)
53     {
54     }
55     
56     bool run()
57     {
58         bool changed = false;
59
60         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
61             if (block->cfaFoundConstants)
62                 changed |= foldConstants(block);
63         }
64         
65         if (changed && m_graph.m_form == SSA) {
66             // It's now possible that we have Upsilons pointed at JSConstants. Fix that.
67             for (BasicBlock* block : m_graph.blocksInNaturalOrder())
68                 fixUpsilons(block);
69         }
70
71         if (m_graph.m_form == SSA) {
72             // It's now possible to simplify basic blocks by placing an Unreachable terminator right
73             // after anything that invalidates AI.
74             bool didClipBlock = false;
75             Vector<Node*> nodesToDelete;
76             for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
77                 m_state.beginBasicBlock(block);
78                 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
79                     if (block->at(nodeIndex)->isTerminal()) {
80                         // It's possible that we have something after the terminal. It could be a
81                         // no-op Check node, for example. We don't want the logic below to turn that
82                         // node into Unreachable, since then we'd have two terminators.
83                         break;
84                     }
85                     if (!m_state.isValid()) {
86                         NodeOrigin origin = block->at(nodeIndex)->origin;
87                         for (unsigned killIndex = nodeIndex; killIndex < block->size(); ++killIndex)
88                             nodesToDelete.append(block->at(killIndex));
89                         block->resize(nodeIndex);
90                         block->appendNode(m_graph, SpecNone, Unreachable, origin);
91                         didClipBlock = true;
92                         break;
93                     }
94                     m_interpreter.execute(nodeIndex);
95                 }
96                 m_state.reset();
97             }
98
99             if (didClipBlock) {
100                 changed = true;
101
102                 m_graph.invalidateNodeLiveness();
103
104                 for (Node* node : nodesToDelete)
105                     m_graph.deleteNode(node);
106
107                 m_graph.invalidateCFG();
108                 m_graph.resetReachability();
109                 m_graph.killUnreachableBlocks();
110             }
111         }
112          
113         return changed;
114     }
115
116 private:
117     bool foldConstants(BasicBlock* block)
118     {
119         bool changed = false;
120         m_state.beginBasicBlock(block);
121         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
122             if (!m_state.isValid())
123                 break;
124             
125             Node* node = block->at(indexInBlock);
126
127             bool alreadyHandled = false;
128             bool eliminated = false;
129                     
130             switch (node->op()) {
131             case BooleanToNumber: {
132                 if (node->child1().useKind() == UntypedUse
133                     && !m_interpreter.needsTypeCheck(node->child1(), SpecBoolean))
134                     node->child1().setUseKind(BooleanUse);
135                 break;
136             }
137
138             case CompareEq: {
139                 // FIXME: We should add back the broken folding phase here for comparisions where we prove at least one side has type SpecOther.
140                 // See: https://bugs.webkit.org/show_bug.cgi?id=174844
141                 break;
142             }
143
144             case CompareStrictEq:
145             case SameValue: {
146                 if (node->isBinaryUseKind(UntypedUse)) {
147                     JSValue child1Constant = m_state.forNode(node->child1().node()).value();
148                     JSValue child2Constant = m_state.forNode(node->child2().node()).value();
149
150                     // FIXME: Revisit this condition when introducing BigInt to JSC.
151                     auto isNonStringOrBigIntCellConstant = [] (JSValue value) {
152                         return value && value.isCell() && !value.isString() && !value.isBigInt();
153                     };
154
155                     if (isNonStringOrBigIntCellConstant(child1Constant)) {
156                         node->convertToCompareEqPtr(m_graph.freezeStrong(child1Constant.asCell()), node->child2());
157                         changed = true;
158                     } else if (isNonStringOrBigIntCellConstant(child2Constant)) {
159                         node->convertToCompareEqPtr(m_graph.freezeStrong(child2Constant.asCell()), node->child1());
160                         changed = true;
161                     }
162                 }
163                 break;
164             }
165
166             case CheckStructureOrEmpty: {
167                 const AbstractValue& value = m_state.forNode(node->child1());
168                 if (value.m_type & SpecEmpty)
169                     break;
170                 node->convertCheckStructureOrEmptyToCheckStructure();
171                 changed = true;
172                 FALLTHROUGH;
173             }
174             case CheckStructure:
175             case ArrayifyToStructure: {
176                 AbstractValue& value = m_state.forNode(node->child1());
177                 RegisteredStructureSet set;
178                 if (node->op() == ArrayifyToStructure)
179                     set = node->structure();
180                 else {
181                     set = node->structureSet();
182                     if ((SpecCellCheck & SpecEmpty) && node->child1().useKind() == CellUse && m_state.forNode(node->child1()).m_type & SpecEmpty) {
183                         m_insertionSet.insertNode(
184                             indexInBlock, SpecNone, AssertNotEmpty, node->origin, Edge(node->child1().node(), UntypedUse));
185                     }
186                 }
187                 if (value.m_structure.isSubsetOf(set)) {
188                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
189                     node->remove(m_graph);
190                     eliminated = true;
191                     break;
192                 }
193                 break;
194             }
195
196             case CheckSubClass: {
197                 JSValue constant = m_state.forNode(node->child1()).value();
198                 if (constant) {
199                     if (constant.isCell() && constant.asCell()->inherits(m_graph.m_vm, node->classInfo())) {
200                         m_interpreter.execute(indexInBlock);
201                         node->remove(m_graph);
202                         eliminated = true;
203                         break;
204                     }
205                 }
206
207                 AbstractValue& value = m_state.forNode(node->child1());
208
209                 if (value.m_structure.isSubClassOf(node->classInfo())) {
210                     m_interpreter.execute(indexInBlock);
211                     node->remove(m_graph);
212                     eliminated = true;
213                     break;
214                 }
215                 break;
216             }
217                 
218             case GetIndexedPropertyStorage: {
219                 JSArrayBufferView* view = m_graph.tryGetFoldableView(
220                     m_state.forNode(node->child1()).m_value, node->arrayMode());
221                 if (!view)
222                     break;
223                 
224                 if (view->mode() == FastTypedArray) {
225                     // FIXME: It would be awesome to be able to fold the property storage for
226                     // these GC-allocated typed arrays. For now it doesn't matter because the
227                     // most common use-cases for constant typed arrays involve large arrays with
228                     // aliased buffer views.
229                     // https://bugs.webkit.org/show_bug.cgi?id=125425
230                     break;
231                 }
232                 
233                 m_interpreter.execute(indexInBlock);
234                 eliminated = true;
235                 
236                 m_insertionSet.insertCheck(indexInBlock, node->origin, node->children);
237                 node->convertToConstantStoragePointer(view->vector());
238                 break;
239             }
240                 
241             case CheckStructureImmediate: {
242                 AbstractValue& value = m_state.forNode(node->child1());
243                 const RegisteredStructureSet& set = node->structureSet();
244                 
245                 if (value.value()) {
246                     if (Structure* structure = jsDynamicCast<Structure*>(m_graph.m_vm, value.value())) {
247                         if (set.contains(m_graph.registerStructure(structure))) {
248                             m_interpreter.execute(indexInBlock);
249                             node->remove(m_graph);
250                             eliminated = true;
251                             break;
252                         }
253                     }
254                 }
255                 
256                 if (PhiChildren* phiChildren = m_interpreter.phiChildren()) {
257                     bool allGood = true;
258                     phiChildren->forAllTransitiveIncomingValues(
259                         node,
260                         [&] (Node* incoming) {
261                             if (Structure* structure = incoming->dynamicCastConstant<Structure*>(m_graph.m_vm)) {
262                                 if (set.contains(m_graph.registerStructure(structure)))
263                                     return;
264                             }
265                             allGood = false;
266                         });
267                     if (allGood) {
268                         m_interpreter.execute(indexInBlock);
269                         node->remove(m_graph);
270                         eliminated = true;
271                         break;
272                     }
273                 }
274                 break;
275             }
276                 
277             case CheckArray:
278             case Arrayify: {
279                 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
280                     break;
281                 node->remove(m_graph);
282                 eliminated = true;
283                 break;
284             }
285                 
286             case PutStructure: {
287                 if (m_state.forNode(node->child1()).m_structure.onlyStructure() != node->transition()->next)
288                     break;
289                 
290                 node->remove(m_graph);
291                 eliminated = true;
292                 break;
293             }
294                 
295             case CheckCell: {
296                 if (m_state.forNode(node->child1()).value() != node->cellOperand()->value())
297                     break;
298                 node->remove(m_graph);
299                 eliminated = true;
300                 break;
301             }
302
303             case AssertNotEmpty:
304             case CheckNotEmpty: {
305                 if (m_state.forNode(node->child1()).m_type & SpecEmpty)
306                     break;
307                 node->remove(m_graph);
308                 eliminated = true;
309                 break;
310             }
311
312             case CheckStringIdent: {
313                 UniquedStringImpl* uid = node->uidOperand();
314                 const UniquedStringImpl* constantUid = nullptr;
315
316                 JSValue childConstant = m_state.forNode(node->child1()).value();
317                 if (childConstant) {
318                     if (childConstant.isString()) {
319                         if (const auto* impl = asString(childConstant)->tryGetValueImpl()) {
320                             // Edge filtering requires that a value here should be StringIdent.
321                             // However, a constant value propagated in DFG is not filtered.
322                             // So here, we check the propagated value is actually an atomic string.
323                             // And if it's not, we just ignore.
324                             if (impl->isAtomic())
325                                 constantUid = static_cast<const UniquedStringImpl*>(impl);
326                         }
327                     }
328                 }
329
330                 if (constantUid == uid) {
331                     node->remove(m_graph);
332                     eliminated = true;
333                 }
334                 break;
335             }
336
337             case CheckInBounds: {
338                 JSValue left = m_state.forNode(node->child1()).value();
339                 JSValue right = m_state.forNode(node->child2()).value();
340                 if (left && right && left.isInt32() && right.isInt32()
341                     && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
342                     node->remove(m_graph);
343                     eliminated = true;
344                     break;
345                 }
346                 
347                 break;
348             }
349                 
350             case GetMyArgumentByVal:
351             case GetMyArgumentByValOutOfBounds: {
352                 JSValue indexValue = m_state.forNode(node->child2()).value();
353                 if (!indexValue || !indexValue.isUInt32())
354                     break;
355
356                 Checked<unsigned, RecordOverflow> checkedIndex = indexValue.asUInt32();
357                 checkedIndex += node->numberOfArgumentsToSkip();
358                 if (checkedIndex.hasOverflowed())
359                     break;
360                 
361                 unsigned index = checkedIndex.unsafeGet();
362                 Node* arguments = node->child1().node();
363                 InlineCallFrame* inlineCallFrame = arguments->origin.semantic.inlineCallFrame;
364                 
365                 // Don't try to do anything if the index is known to be outside our static bounds. Note
366                 // that our static bounds are usually strictly larger than the dynamic bounds. The
367                 // exception is something like this, assuming foo() is not inlined:
368                 //
369                 // function foo() { return arguments[5]; }
370                 //
371                 // Here the static bound on number of arguments is 0, and we're accessing index 5. We
372                 // will not strength-reduce this to GetStack because GetStack is otherwise assumed by the
373                 // compiler to access those variables that are statically accounted for; for example if
374                 // we emitted a GetStack on arg6 we would have out-of-bounds access crashes anywhere that
375                 // uses an Operands<> map. There is not much cost to continuing to use a
376                 // GetMyArgumentByVal in such statically-out-of-bounds accesses; we just lose CFA unless
377                 // GCSE removes the access entirely.
378                 if (inlineCallFrame) {
379                     if (index >= inlineCallFrame->argumentCountIncludingThis - 1)
380                         break;
381                 } else {
382                     if (index >= m_state.numberOfArguments() - 1)
383                         break;
384                 }
385                 
386                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
387                 
388                 StackAccessData* data;
389                 if (inlineCallFrame) {
390                     data = m_graph.m_stackAccessData.add(
391                         VirtualRegister(
392                             inlineCallFrame->stackOffset +
393                             CallFrame::argumentOffset(index)),
394                         FlushedJSValue);
395                 } else {
396                     data = m_graph.m_stackAccessData.add(
397                         virtualRegisterForArgument(index + 1), FlushedJSValue);
398                 }
399                 
400                 if (inlineCallFrame && !inlineCallFrame->isVarargs() && index < inlineCallFrame->argumentCountIncludingThis - 1) {
401                     node->convertToGetStack(data);
402                     eliminated = true;
403                     break;
404                 }
405                 
406                 if (node->op() == GetMyArgumentByValOutOfBounds)
407                     break;
408                 
409                 Node* length = emitCodeToGetArgumentsArrayLength(
410                     m_insertionSet, arguments, indexInBlock, node->origin);
411                 m_insertionSet.insertNode(
412                     indexInBlock, SpecNone, CheckInBounds, node->origin,
413                     node->child2(), Edge(length, Int32Use));
414                 node->convertToGetStack(data);
415                 eliminated = true;
416                 break;
417             }
418                 
419             case MultiGetByOffset: {
420                 Edge baseEdge = node->child1();
421                 Node* base = baseEdge.node();
422                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
423
424                 // First prune the variants, then check if the MultiGetByOffset can be
425                 // strength-reduced to a GetByOffset.
426                 
427                 AbstractValue baseValue = m_state.forNode(base);
428                 
429                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
430                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
431                 
432                 for (unsigned i = 0; i < data.cases.size(); ++i) {
433                     MultiGetByOffsetCase& getCase = data.cases[i];
434                     getCase.set().filter(baseValue);
435                     if (getCase.set().isEmpty()) {
436                         data.cases[i--] = data.cases.last();
437                         data.cases.removeLast();
438                         changed = true;
439                     }
440                 }
441                 
442                 if (data.cases.size() != 1)
443                     break;
444                 
445                 emitGetByOffset(indexInBlock, node, baseValue, data.cases[0], data.identifierNumber);
446                 changed = true;
447                 break;
448             }
449                 
450             case MultiPutByOffset: {
451                 Edge baseEdge = node->child1();
452                 Node* base = baseEdge.node();
453                 MultiPutByOffsetData& data = node->multiPutByOffsetData();
454                 
455                 AbstractValue baseValue = m_state.forNode(base);
456
457                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
458                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
459                 
460
461                 for (unsigned i = 0; i < data.variants.size(); ++i) {
462                     PutByIdVariant& variant = data.variants[i];
463                     variant.oldStructure().genericFilter([&] (Structure* structure) -> bool {
464                         return baseValue.contains(m_graph.registerStructure(structure));
465                     });
466                     
467                     if (variant.oldStructure().isEmpty()) {
468                         data.variants[i--] = data.variants.last();
469                         data.variants.removeLast();
470                         changed = true;
471                         continue;
472                     }
473                     
474                     if (variant.kind() == PutByIdVariant::Transition
475                         && variant.oldStructure().onlyStructure() == variant.newStructure()) {
476                         variant = PutByIdVariant::replace(
477                             variant.oldStructure(),
478                             variant.offset(),
479                             variant.requiredType());
480                         changed = true;
481                     }
482                 }
483
484                 if (data.variants.size() != 1)
485                     break;
486                 
487                 emitPutByOffset(
488                     indexInBlock, node, baseValue, data.variants[0], data.identifierNumber);
489                 changed = true;
490                 break;
491             }
492                 
493             case MatchStructure: {
494                 Edge baseEdge = node->child1();
495                 Node* base = baseEdge.node();
496                 MatchStructureData& data = node->matchStructureData();
497                 
498                 AbstractValue baseValue = m_state.forNode(base);
499
500                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
501                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
502                 
503                 BooleanLattice result = BooleanLattice::Bottom;
504                 for (unsigned i = 0; i < data.variants.size(); ++i) {
505                     if (!baseValue.contains(data.variants[i].structure)) {
506                         data.variants[i--] = data.variants.last();
507                         data.variants.removeLast();
508                         changed = true;
509                         continue;
510                     }
511                     result = leastUpperBoundOfBooleanLattices(
512                         result,
513                         data.variants[i].result ? BooleanLattice::True : BooleanLattice::False);
514                 }
515                 
516                 if (result == BooleanLattice::False || result == BooleanLattice::True) {
517                     RegisteredStructureSet structureSet;
518                     for (MatchStructureVariant& variant : data.variants)
519                         structureSet.add(variant.structure);
520                     addBaseCheck(indexInBlock, node, baseValue, structureSet);
521                     m_graph.convertToConstant(
522                         node, m_graph.freeze(jsBoolean(result == BooleanLattice::True)));
523                     changed = true;
524                 }
525                 break;
526             }
527         
528             case GetByIdDirect:
529             case GetByIdDirectFlush:
530             case GetById:
531             case GetByIdFlush: {
532                 Edge childEdge = node->child1();
533                 Node* child = childEdge.node();
534                 unsigned identifierNumber = node->identifierNumber();
535                 
536                 AbstractValue baseValue = m_state.forNode(child);
537
538                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
539                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
540
541                 if (!baseValue.m_structure.isFinite()
542                     || (node->child1().useKind() == UntypedUse || (baseValue.m_type & ~SpecCell)))
543                     break;
544                 
545                 GetByIdStatus status = GetByIdStatus::computeFor(
546                     baseValue.m_structure.toStructureSet(), m_graph.identifiers()[identifierNumber]);
547                 if (!status.isSimple())
548                     break;
549                 
550                 for (unsigned i = status.numVariants(); i--;) {
551                     if (!status[i].conditionSet().isEmpty()) {
552                         // FIXME: We could handle prototype cases.
553                         // https://bugs.webkit.org/show_bug.cgi?id=110386
554                         break;
555                     }
556                 }
557                 
558                 if (status.numVariants() == 1) {
559                     emitGetByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
560                     changed = true;
561                     break;
562                 }
563                 
564                 if (!isFTL(m_graph.m_plan.mode))
565                     break;
566                 
567                 MultiGetByOffsetData* data = m_graph.m_multiGetByOffsetData.add();
568                 for (const GetByIdVariant& variant : status.variants()) {
569                     data->cases.append(
570                         MultiGetByOffsetCase(
571                             *m_graph.addStructureSet(variant.structureSet()),
572                             GetByOffsetMethod::load(variant.offset())));
573                 }
574                 data->identifierNumber = identifierNumber;
575                 node->convertToMultiGetByOffset(data);
576                 changed = true;
577                 break;
578             }
579                 
580             case PutById:
581             case PutByIdDirect:
582             case PutByIdFlush: {
583                 NodeOrigin origin = node->origin;
584                 Edge childEdge = node->child1();
585                 Node* child = childEdge.node();
586                 unsigned identifierNumber = node->identifierNumber();
587                 
588                 ASSERT(childEdge.useKind() == CellUse);
589                 
590                 AbstractValue baseValue = m_state.forNode(child);
591                 AbstractValue valueValue = m_state.forNode(node->child2());
592
593                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
594                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
595
596                 if (!baseValue.m_structure.isFinite())
597                     break;
598                 
599                 PutByIdStatus status = PutByIdStatus::computeFor(
600                     m_graph.globalObjectFor(origin.semantic),
601                     baseValue.m_structure.toStructureSet(),
602                     m_graph.identifiers()[identifierNumber],
603                     node->op() == PutByIdDirect);
604                 
605                 if (!status.isSimple())
606                     break;
607
608                 ASSERT(status.numVariants());
609                 
610                 if (status.numVariants() > 1 && !isFTL(m_graph.m_plan.mode))
611                     break;
612                 
613                 changed = true;
614
615                 bool allGood = true;
616                 for (const PutByIdVariant& variant : status.variants()) {
617                     if (!allGood)
618                         break;
619                     for (const ObjectPropertyCondition& condition : variant.conditionSet()) {
620                         if (m_graph.watchCondition(condition))
621                             continue;
622
623                         Structure* structure = condition.object()->structure();
624                         if (!condition.structureEnsuresValidity(structure)) {
625                             allGood = false;
626                             break;
627                         }
628
629                         m_insertionSet.insertNode(
630                             indexInBlock, SpecNone, CheckStructure, node->origin,
631                             OpInfo(m_graph.addStructureSet(structure)),
632                             m_insertionSet.insertConstantForUse(
633                                 indexInBlock, node->origin, condition.object(), KnownCellUse));
634                     }
635                 }
636
637                 if (!allGood)
638                     break;
639                 
640                 if (status.numVariants() == 1) {
641                     emitPutByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
642                     break;
643                 }
644                 
645                 ASSERT(isFTL(m_graph.m_plan.mode));
646
647                 MultiPutByOffsetData* data = m_graph.m_multiPutByOffsetData.add();
648                 data->variants = status.variants();
649                 data->identifierNumber = identifierNumber;
650                 node->convertToMultiPutByOffset(data);
651                 break;
652             }
653
654             case InByVal: {
655                 AbstractValue& property = m_state.forNode(node->child2());
656                 if (JSValue constant = property.value()) {
657                     if (constant.isString()) {
658                         JSString* string = asString(constant);
659                         const StringImpl* impl = string->tryGetValueImpl();
660                         if (impl && impl->isAtomic()) {
661                             unsigned identifierNumber = m_graph.identifiers().ensure(const_cast<UniquedStringImpl*>(static_cast<const UniquedStringImpl*>(impl)));
662                             node->convertToInById(identifierNumber);
663                             changed = true;
664                             break;
665                         }
666                     }
667                 }
668                 break;
669             }
670
671             case ToPrimitive: {
672                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString | SpecSymbol | SpecBigInt))
673                     break;
674                 
675                 node->convertToIdentity();
676                 changed = true;
677                 break;
678             }
679
680             case ToThis: {
681                 ToThisResult result = isToThisAnIdentity(m_graph.m_vm, m_graph.executableFor(node->origin.semantic)->isStrictMode(), m_state.forNode(node->child1()));
682                 if (result == ToThisResult::Identity) {
683                     node->convertToIdentity();
684                     changed = true;
685                     break;
686                 }
687                 if (result == ToThisResult::GlobalThis) {
688                     node->convertToGetGlobalThis();
689                     changed = true;
690                     break;
691                 }
692                 break;
693             }
694
695             case CreateThis: {
696                 if (JSValue base = m_state.forNode(node->child1()).m_value) {
697                     if (auto* function = jsDynamicCast<JSFunction*>(m_graph.m_vm, base)) {
698                         if (FunctionRareData* rareData = function->rareData()) {
699                             if (rareData->allocationProfileWatchpointSet().isStillValid()) {
700                                 Structure* structure = rareData->objectAllocationStructure();
701                                 JSObject* prototype = rareData->objectAllocationPrototype();
702                                 if (structure
703                                     && (structure->hasMonoProto() || prototype)
704                                     && rareData->allocationProfileWatchpointSet().isStillValid()) {
705
706                                     m_graph.freeze(rareData);
707                                     m_graph.watchpoints().addLazily(rareData->allocationProfileWatchpointSet());
708                                     node->convertToNewObject(m_graph.registerStructure(structure));
709
710                                     if (structure->hasPolyProto()) {
711                                         StorageAccessData* data = m_graph.m_storageAccessData.add();
712                                         data->offset = knownPolyProtoOffset;
713                                         data->identifierNumber = m_graph.identifiers().ensure(m_graph.m_vm.propertyNames->builtinNames().polyProtoName().impl());
714                                         InferredType::Descriptor inferredType = InferredType::Top;
715                                         data->inferredType = inferredType;
716                                         m_graph.registerInferredType(inferredType);
717
718                                         NodeOrigin origin = node->origin.withInvalidExit();
719                                         Node* prototypeNode = m_insertionSet.insertConstant(
720                                             indexInBlock + 1, origin, m_graph.freeze(prototype));
721
722                                         ASSERT(isInlineOffset(knownPolyProtoOffset));
723                                         m_insertionSet.insertNode(
724                                             indexInBlock + 1, SpecNone, PutByOffset, origin, OpInfo(data),
725                                             Edge(node, KnownCellUse), Edge(node, KnownCellUse), Edge(prototypeNode, UntypedUse));
726                                     }
727                                     changed = true;
728                                     break;
729
730                                 }
731                             }
732                         }
733                     }
734                 }
735                 break;
736             }
737
738             case ToNumber: {
739                 if (m_state.forNode(node->child1()).m_type & ~SpecBytecodeNumber)
740                     break;
741
742                 node->convertToIdentity();
743                 changed = true;
744                 break;
745             }
746
747             case NormalizeMapKey: {
748                 SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only);
749                 if (m_state.forNode(node->child1()).m_type & typeMaybeNormalized)
750                     break;
751
752                 node->convertToIdentity();
753                 changed = true;
754                 break;
755             }
756
757             case ParseInt: {
758                 AbstractValue& value = m_state.forNode(node->child1());
759                 if (!value.m_type || (value.m_type & ~SpecInt32Only))
760                     break;
761
762                 JSValue radix;
763                 if (!node->child2())
764                     radix = jsNumber(0);
765                 else
766                     radix = m_state.forNode(node->child2()).m_value;
767
768                 if (!radix.isNumber())
769                     break;
770
771                 if (radix.asNumber() == 0 || radix.asNumber() == 10) {
772                     node->child2() = Edge();
773                     node->convertToIdentity();
774                     changed = true;
775                 }
776
777                 break;
778             }
779
780             case NumberToStringWithRadix: {
781                 JSValue radixValue = m_state.forNode(node->child2()).m_value;
782                 if (radixValue && radixValue.isInt32()) {
783                     int32_t radix = radixValue.asInt32();
784                     if (2 <= radix && radix <= 36) {
785                         if (radix == 10) {
786                             node->setOpAndDefaultFlags(ToString);
787                             node->clearFlags(NodeMustGenerate);
788                             node->child2() = Edge();
789                         } else
790                             node->convertToNumberToStringWithValidRadixConstant(radix);
791                         changed = true;
792                         break;
793                     }
794                 }
795                 break;
796             }
797
798             case Check: {
799                 alreadyHandled = true;
800                 m_interpreter.execute(indexInBlock);
801                 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
802                     Edge edge = node->children.child(i);
803                     if (!edge)
804                         break;
805                     if (edge.isProved() || edge.willNotHaveCheck()) {
806                         node->children.removeEdge(i--);
807                         changed = true;
808                     }
809                 }
810                 break;
811             }
812
813             case CheckVarargs: {
814                 alreadyHandled = true;
815                 m_interpreter.execute(indexInBlock);
816                 unsigned targetIndex = 0;
817                 for (unsigned i = 0; i < node->numChildren(); ++i) {
818                     Edge& edge = m_graph.varArgChild(node, i);
819                     if (!edge)
820                         continue;
821                     if (edge.isProved() || edge.willNotHaveCheck()) {
822                         edge = Edge();
823                         changed = true;
824                         continue;
825                     }
826                     Edge& dst = m_graph.varArgChild(node, targetIndex++);
827                     std::swap(dst, edge);
828                 }
829                 node->children.setNumChildren(targetIndex);
830                 break;
831             }
832
833             case MakeRope: {
834                 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
835                     Edge& edge = node->children.child(i);
836                     if (!edge)
837                         break;
838                     JSValue childConstant = m_state.forNode(edge).value();
839                     if (!childConstant)
840                         continue;
841                     if (!childConstant.isString())
842                         continue;
843                     if (asString(childConstant)->length())
844                         continue;
845
846                     // Don't allow the MakeRope to have zero children.
847                     if (!i && !node->child2())
848                         break;
849
850                     node->children.removeEdge(i--);
851                     changed = true;
852                 }
853
854                 if (!node->child2()) {
855                     ASSERT(!node->child3());
856                     node->convertToIdentity();
857                     changed = true;
858                 }
859                 break;
860             }
861
862             case CheckTypeInfoFlags: {
863                 const AbstractValue& abstractValue = m_state.forNode(node->child1());
864                 unsigned bits = node->typeInfoOperand();
865                 ASSERT(bits);
866                 if (bits == ImplementsDefaultHasInstance) {
867                     if (abstractValue.m_type == SpecFunctionWithDefaultHasInstance) {
868                         eliminated = true;
869                         node->remove(m_graph);
870                         break;
871                     }
872                 }
873
874                 if (JSValue value = abstractValue.value()) {
875                     if (value.isCell()) {
876                         // This works because if we see a cell here, we know it's fully constructed
877                         // and we can read its inline type info flags. These flags don't change over the
878                         // object's lifetime.
879                         if ((value.asCell()->inlineTypeFlags() & bits) == bits) {
880                             eliminated = true;
881                             node->remove(m_graph);
882                             break;
883                         }
884                     }
885                 }
886
887                 if (abstractValue.m_structure.isFinite()) {
888                     bool ok = true;
889                     abstractValue.m_structure.forEach([&] (RegisteredStructure structure) {
890                         ok &= (structure->typeInfo().inlineTypeFlags() & bits) == bits;
891                     });
892                     if (ok) {
893                         eliminated = true;
894                         node->remove(m_graph);
895                         break;
896                     }
897                 }
898
899                 break;
900             }
901                 
902             case PhantomNewObject:
903             case PhantomNewFunction:
904             case PhantomNewGeneratorFunction:
905             case PhantomNewAsyncGeneratorFunction:
906             case PhantomNewAsyncFunction:
907             case PhantomCreateActivation:
908             case PhantomDirectArguments:
909             case PhantomClonedArguments:
910             case PhantomCreateRest:
911             case PhantomSpread:
912             case PhantomNewArrayWithSpread:
913             case PhantomNewArrayBuffer:
914             case PhantomNewRegexp:
915             case BottomValue:
916                 alreadyHandled = true;
917                 break;
918
919             default:
920                 break;
921             }
922             
923             if (eliminated) {
924                 changed = true;
925                 continue;
926             }
927                 
928             if (alreadyHandled)
929                 continue;
930             
931             m_interpreter.execute(indexInBlock);
932             if (!m_state.isValid()) {
933                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
934                 // example:
935                 //
936                 //     c: JSConstant(4.2)
937                 //     x: ValueToInt32(Check:Int32:@const)
938                 //
939                 // It would be correct for an analysis to assume that execution cannot
940                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
941                 // the CFA may report that it found a constant even though it also reported
942                 // that everything has been invalidated. This will only happen in a couple of
943                 // the constant folding cases; most of them are also separately defensive
944                 // about such things.
945                 break;
946             }
947             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant() || !node->result())
948                 continue;
949             
950             // Interesting fact: this freezing that we do right here may turn an fragile value into
951             // a weak value. See DFGValueStrength.h.
952             FrozenValue* value = m_graph.freeze(m_state.forNode(node).value());
953             if (!*value)
954                 continue;
955             
956             if (node->op() == GetLocal) {
957                 // Need to preserve bytecode liveness in ThreadedCPS form. This wouldn't be necessary
958                 // if it wasn't for https://bugs.webkit.org/show_bug.cgi?id=144086.
959                 m_insertionSet.insertNode(
960                     indexInBlock, SpecNone, PhantomLocal, node->origin,
961                     OpInfo(node->variableAccessData()));
962                 m_graph.dethread();
963             } else
964                 m_insertionSet.insertCheck(m_graph, indexInBlock, node);
965             m_graph.convertToConstant(node, value);
966             
967             changed = true;
968         }
969         m_state.reset();
970         m_insertionSet.execute(block);
971         
972         return changed;
973     }
974     
975     void emitGetByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const MultiGetByOffsetCase& getCase, unsigned identifierNumber)
976     {
977         // When we get to here we have already emitted all of the requisite checks for everything.
978         // So, we just need to emit what the method object tells us to emit.
979         
980         addBaseCheck(indexInBlock, node, baseValue, getCase.set());
981
982         GetByOffsetMethod method = getCase.method();
983         
984         switch (method.kind()) {
985         case GetByOffsetMethod::Invalid:
986             RELEASE_ASSERT_NOT_REACHED();
987             return;
988             
989         case GetByOffsetMethod::Constant:
990             m_graph.convertToConstant(node, method.constant());
991             return;
992             
993         case GetByOffsetMethod::Load:
994             emitGetByOffset(indexInBlock, node, node->child1(), identifierNumber, method.offset());
995             return;
996             
997         case GetByOffsetMethod::LoadFromPrototype: {
998             Node* child = m_insertionSet.insertConstant(
999                 indexInBlock, node->origin, method.prototype());
1000             emitGetByOffset(
1001                 indexInBlock, node, Edge(child, KnownCellUse), identifierNumber, method.offset());
1002             return;
1003         } }
1004         
1005         RELEASE_ASSERT_NOT_REACHED();
1006     }
1007     
1008     void emitGetByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const GetByIdVariant& variant, unsigned identifierNumber)
1009     {
1010         Edge childEdge = node->child1();
1011
1012         addBaseCheck(indexInBlock, node, baseValue, variant.structureSet());
1013         
1014         // We aren't set up to handle prototype stuff.
1015         DFG_ASSERT(m_graph, node, variant.conditionSet().isEmpty());
1016
1017         if (JSValue value = m_graph.tryGetConstantProperty(baseValue.m_value, *m_graph.addStructureSet(variant.structureSet()), variant.offset())) {
1018             m_graph.convertToConstant(node, m_graph.freeze(value));
1019             return;
1020         }
1021         
1022         emitGetByOffset(indexInBlock, node, childEdge, identifierNumber, variant.offset());
1023     }
1024     
1025     void emitGetByOffset(
1026         unsigned indexInBlock, Node* node, Edge childEdge, unsigned identifierNumber,
1027         PropertyOffset offset, const InferredType::Descriptor& inferredType = InferredType::Top)
1028     {
1029         childEdge.setUseKind(KnownCellUse);
1030         
1031         Edge propertyStorage;
1032         
1033         if (isInlineOffset(offset))
1034             propertyStorage = childEdge;
1035         else {
1036             propertyStorage = Edge(m_insertionSet.insertNode(
1037                 indexInBlock, SpecNone, GetButterfly, node->origin, childEdge));
1038         }
1039         
1040         StorageAccessData& data = *m_graph.m_storageAccessData.add();
1041         data.offset = offset;
1042         data.identifierNumber = identifierNumber;
1043         data.inferredType = inferredType;
1044         
1045         node->convertToGetByOffset(data, propertyStorage, childEdge);
1046     }
1047
1048     void emitPutByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const PutByIdVariant& variant, unsigned identifierNumber)
1049     {
1050         NodeOrigin origin = node->origin;
1051         Edge childEdge = node->child1();
1052
1053         addBaseCheck(indexInBlock, node, baseValue, variant.oldStructure());
1054         insertInferredTypeCheck(
1055             m_insertionSet, indexInBlock, origin, node->child2().node(), variant.requiredType());
1056
1057         node->child1().setUseKind(KnownCellUse);
1058         childEdge.setUseKind(KnownCellUse);
1059
1060         Transition* transition = 0;
1061         if (variant.kind() == PutByIdVariant::Transition) {
1062             transition = m_graph.m_transitions.add(
1063                 m_graph.registerStructure(variant.oldStructureForTransition()), m_graph.registerStructure(variant.newStructure()));
1064         }
1065
1066         Edge propertyStorage;
1067
1068         DFG_ASSERT(m_graph, node, origin.exitOK);
1069         bool canExit = true;
1070         bool didAllocateStorage = false;
1071
1072         if (isInlineOffset(variant.offset()))
1073             propertyStorage = childEdge;
1074         else if (!variant.reallocatesStorage()) {
1075             propertyStorage = Edge(m_insertionSet.insertNode(
1076                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
1077         } else if (!variant.oldStructureForTransition()->outOfLineCapacity()) {
1078             ASSERT(variant.newStructure()->outOfLineCapacity());
1079             ASSERT(!isInlineOffset(variant.offset()));
1080             Node* allocatePropertyStorage = m_insertionSet.insertNode(
1081                 indexInBlock, SpecNone, AllocatePropertyStorage,
1082                 origin, OpInfo(transition), childEdge);
1083             propertyStorage = Edge(allocatePropertyStorage);
1084             didAllocateStorage = true;
1085         } else {
1086             ASSERT(variant.oldStructureForTransition()->outOfLineCapacity());
1087             ASSERT(variant.newStructure()->outOfLineCapacity() > variant.oldStructureForTransition()->outOfLineCapacity());
1088             ASSERT(!isInlineOffset(variant.offset()));
1089
1090             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
1091                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
1092                 OpInfo(transition), childEdge,
1093                 Edge(m_insertionSet.insertNode(
1094                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
1095             propertyStorage = Edge(reallocatePropertyStorage);
1096             didAllocateStorage = true;
1097         }
1098
1099         StorageAccessData& data = *m_graph.m_storageAccessData.add();
1100         data.offset = variant.offset();
1101         data.identifierNumber = identifierNumber;
1102         
1103         node->convertToPutByOffset(data, propertyStorage, childEdge);
1104         node->origin.exitOK = canExit;
1105
1106         if (variant.kind() == PutByIdVariant::Transition) {
1107             if (didAllocateStorage) {
1108                 m_insertionSet.insertNode(
1109                     indexInBlock + 1, SpecNone, NukeStructureAndSetButterfly,
1110                     origin.withInvalidExit(), childEdge, propertyStorage);
1111             }
1112             
1113             // FIXME: PutStructure goes last until we fix either
1114             // https://bugs.webkit.org/show_bug.cgi?id=142921 or
1115             // https://bugs.webkit.org/show_bug.cgi?id=142924.
1116             m_insertionSet.insertNode(
1117                 indexInBlock + 1, SpecNone, PutStructure, origin.withInvalidExit(), OpInfo(transition),
1118                 childEdge);
1119         }
1120     }
1121     
1122     void addBaseCheck(
1123         unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const StructureSet& set)
1124     {
1125         addBaseCheck(indexInBlock, node, baseValue, *m_graph.addStructureSet(set));
1126     }
1127
1128     void addBaseCheck(
1129         unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const RegisteredStructureSet& set)
1130     {
1131         if (!baseValue.m_structure.isSubsetOf(set)) {
1132             // Arises when we prune MultiGetByOffset. We could have a
1133             // MultiGetByOffset with a single variant that checks for structure S,
1134             // and the input has structures S and T, for example.
1135             ASSERT(node->child1());
1136             m_insertionSet.insertNode(
1137                 indexInBlock, SpecNone, CheckStructure, node->origin,
1138                 OpInfo(m_graph.addStructureSet(set.toStructureSet())), node->child1());
1139             return;
1140         }
1141         
1142         if (baseValue.m_type & ~SpecCell)
1143             m_insertionSet.insertCheck(indexInBlock, node->origin, node->child1());
1144     }
1145     
1146     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell, Structure* structure)
1147     {
1148         {
1149             StructureRegistrationResult result;
1150             m_graph.registerStructure(cell->structure(), result);
1151             if (result == StructureRegisteredAndWatched)
1152                 return;
1153         }
1154         
1155         m_graph.registerStructure(structure);
1156
1157         Node* weakConstant = m_insertionSet.insertNode(
1158             indexInBlock, speculationFromValue(cell), JSConstant, origin,
1159             OpInfo(m_graph.freeze(cell)));
1160         
1161         m_insertionSet.insertNode(
1162             indexInBlock, SpecNone, CheckStructure, origin,
1163             OpInfo(m_graph.addStructureSet(structure)), Edge(weakConstant, CellUse));
1164     }
1165     
1166     void fixUpsilons(BasicBlock* block)
1167     {
1168         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
1169             Node* node = block->at(nodeIndex);
1170             if (node->op() != Upsilon)
1171                 continue;
1172             switch (node->phi()->op()) {
1173             case Phi:
1174                 break;
1175             case JSConstant:
1176             case DoubleConstant:
1177             case Int52Constant:
1178                 node->remove(m_graph);
1179                 break;
1180             default:
1181                 DFG_CRASH(m_graph, node, "Bad Upsilon phi() pointer");
1182                 break;
1183             }
1184         }
1185     }
1186     
1187     InPlaceAbstractState m_state;
1188     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
1189     InsertionSet m_insertionSet;
1190 };
1191
1192 bool performConstantFolding(Graph& graph)
1193 {
1194     return runPhase<ConstantFoldingPhase>(graph);
1195 }
1196
1197 } } // namespace JSC::DFG
1198
1199 #endif // ENABLE(DFG_JIT)
1200
1201