b7edc060f436293aca4988833ea94620c572ca0d
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGConstantFoldingPhase.cpp
1 /*
2  * Copyright (C) 2012-2015 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 GetByIdDirect:
494             case GetByIdDirectFlush:
495             case GetById:
496             case GetByIdFlush: {
497                 Edge childEdge = node->child1();
498                 Node* child = childEdge.node();
499                 unsigned identifierNumber = node->identifierNumber();
500                 
501                 AbstractValue baseValue = m_state.forNode(child);
502
503                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
504                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
505
506                 if (!baseValue.m_structure.isFinite()
507                     || (node->child1().useKind() == UntypedUse || (baseValue.m_type & ~SpecCell)))
508                     break;
509                 
510                 GetByIdStatus status = GetByIdStatus::computeFor(
511                     baseValue.m_structure.toStructureSet(), m_graph.identifiers()[identifierNumber]);
512                 if (!status.isSimple())
513                     break;
514                 
515                 for (unsigned i = status.numVariants(); i--;) {
516                     if (!status[i].conditionSet().isEmpty()) {
517                         // FIXME: We could handle prototype cases.
518                         // https://bugs.webkit.org/show_bug.cgi?id=110386
519                         break;
520                     }
521                 }
522                 
523                 if (status.numVariants() == 1) {
524                     emitGetByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
525                     changed = true;
526                     break;
527                 }
528                 
529                 if (!isFTL(m_graph.m_plan.mode))
530                     break;
531                 
532                 MultiGetByOffsetData* data = m_graph.m_multiGetByOffsetData.add();
533                 for (const GetByIdVariant& variant : status.variants()) {
534                     data->cases.append(
535                         MultiGetByOffsetCase(
536                             *m_graph.addStructureSet(variant.structureSet()),
537                             GetByOffsetMethod::load(variant.offset())));
538                 }
539                 data->identifierNumber = identifierNumber;
540                 node->convertToMultiGetByOffset(data);
541                 changed = true;
542                 break;
543             }
544                 
545             case PutById:
546             case PutByIdDirect:
547             case PutByIdFlush: {
548                 NodeOrigin origin = node->origin;
549                 Edge childEdge = node->child1();
550                 Node* child = childEdge.node();
551                 unsigned identifierNumber = node->identifierNumber();
552                 
553                 ASSERT(childEdge.useKind() == CellUse);
554                 
555                 AbstractValue baseValue = m_state.forNode(child);
556                 AbstractValue valueValue = m_state.forNode(node->child2());
557
558                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
559                 alreadyHandled = true; // Don't allow the default constant folder to do things to this.
560
561                 if (!baseValue.m_structure.isFinite())
562                     break;
563                 
564                 PutByIdStatus status = PutByIdStatus::computeFor(
565                     m_graph.globalObjectFor(origin.semantic),
566                     baseValue.m_structure.toStructureSet(),
567                     m_graph.identifiers()[identifierNumber],
568                     node->op() == PutByIdDirect);
569                 
570                 if (!status.isSimple())
571                     break;
572
573                 ASSERT(status.numVariants());
574                 
575                 if (status.numVariants() > 1 && !isFTL(m_graph.m_plan.mode))
576                     break;
577                 
578                 changed = true;
579
580                 bool allGood = true;
581                 for (const PutByIdVariant& variant : status.variants()) {
582                     if (!allGood)
583                         break;
584                     for (const ObjectPropertyCondition& condition : variant.conditionSet()) {
585                         if (m_graph.watchCondition(condition))
586                             continue;
587
588                         Structure* structure = condition.object()->structure();
589                         if (!condition.structureEnsuresValidity(structure)) {
590                             allGood = false;
591                             break;
592                         }
593
594                         m_insertionSet.insertNode(
595                             indexInBlock, SpecNone, CheckStructure, node->origin,
596                             OpInfo(m_graph.addStructureSet(structure)),
597                             m_insertionSet.insertConstantForUse(
598                                 indexInBlock, node->origin, condition.object(), KnownCellUse));
599                     }
600                 }
601
602                 if (!allGood)
603                     break;
604                 
605                 if (status.numVariants() == 1) {
606                     emitPutByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
607                     break;
608                 }
609                 
610                 ASSERT(isFTL(m_graph.m_plan.mode));
611
612                 MultiPutByOffsetData* data = m_graph.m_multiPutByOffsetData.add();
613                 data->variants = status.variants();
614                 data->identifierNumber = identifierNumber;
615                 node->convertToMultiPutByOffset(data);
616                 break;
617             }
618
619             case InByVal: {
620                 AbstractValue& property = m_state.forNode(node->child2());
621                 if (JSValue constant = property.value()) {
622                     if (constant.isString()) {
623                         JSString* string = asString(constant);
624                         const StringImpl* impl = string->tryGetValueImpl();
625                         if (impl && impl->isAtomic()) {
626                             unsigned identifierNumber = m_graph.identifiers().ensure(const_cast<UniquedStringImpl*>(static_cast<const UniquedStringImpl*>(impl)));
627                             node->convertToInById(identifierNumber);
628                             changed = true;
629                             break;
630                         }
631                     }
632                 }
633                 break;
634             }
635
636             case ToPrimitive: {
637                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString | SpecSymbol | SpecBigInt))
638                     break;
639                 
640                 node->convertToIdentity();
641                 changed = true;
642                 break;
643             }
644
645             case ToThis: {
646                 ToThisResult result = isToThisAnIdentity(m_graph.m_vm, m_graph.executableFor(node->origin.semantic)->isStrictMode(), m_state.forNode(node->child1()));
647                 if (result == ToThisResult::Identity) {
648                     node->convertToIdentity();
649                     changed = true;
650                     break;
651                 }
652                 if (result == ToThisResult::GlobalThis) {
653                     node->convertToGetGlobalThis();
654                     changed = true;
655                     break;
656                 }
657                 break;
658             }
659
660             case CreateThis: {
661                 if (JSValue base = m_state.forNode(node->child1()).m_value) {
662                     if (auto* function = jsDynamicCast<JSFunction*>(m_graph.m_vm, base)) {
663                         if (FunctionRareData* rareData = function->rareData()) {
664                             if (rareData->allocationProfileWatchpointSet().isStillValid()) {
665                                 Structure* structure = rareData->objectAllocationStructure();
666                                 JSObject* prototype = rareData->objectAllocationPrototype();
667                                 if (structure
668                                     && (structure->hasMonoProto() || prototype)
669                                     && rareData->allocationProfileWatchpointSet().isStillValid()) {
670
671                                     m_graph.freeze(rareData);
672                                     m_graph.watchpoints().addLazily(rareData->allocationProfileWatchpointSet());
673                                     node->convertToNewObject(m_graph.registerStructure(structure));
674
675                                     if (structure->hasPolyProto()) {
676                                         StorageAccessData* data = m_graph.m_storageAccessData.add();
677                                         data->offset = knownPolyProtoOffset;
678                                         data->identifierNumber = m_graph.identifiers().ensure(m_graph.m_vm.propertyNames->builtinNames().polyProtoName().impl());
679                                         InferredType::Descriptor inferredType = InferredType::Top;
680                                         data->inferredType = inferredType;
681                                         m_graph.registerInferredType(inferredType);
682
683                                         NodeOrigin origin = node->origin.withInvalidExit();
684                                         Node* prototypeNode = m_insertionSet.insertConstant(
685                                             indexInBlock + 1, origin, m_graph.freeze(prototype));
686
687                                         ASSERT(isInlineOffset(knownPolyProtoOffset));
688                                         m_insertionSet.insertNode(
689                                             indexInBlock + 1, SpecNone, PutByOffset, origin, OpInfo(data),
690                                             Edge(node, KnownCellUse), Edge(node, KnownCellUse), Edge(prototypeNode, UntypedUse));
691                                     }
692                                     changed = true;
693                                     break;
694
695                                 }
696                             }
697                         }
698                     }
699                 }
700                 break;
701             }
702
703             case ToNumber: {
704                 if (m_state.forNode(node->child1()).m_type & ~SpecBytecodeNumber)
705                     break;
706
707                 node->convertToIdentity();
708                 changed = true;
709                 break;
710             }
711
712             case NormalizeMapKey: {
713                 SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only);
714                 if (m_state.forNode(node->child1()).m_type & typeMaybeNormalized)
715                     break;
716
717                 node->convertToIdentity();
718                 changed = true;
719                 break;
720             }
721
722             case ParseInt: {
723                 AbstractValue& value = m_state.forNode(node->child1());
724                 if (!value.m_type || (value.m_type & ~SpecInt32Only))
725                     break;
726
727                 JSValue radix;
728                 if (!node->child2())
729                     radix = jsNumber(0);
730                 else
731                     radix = m_state.forNode(node->child2()).m_value;
732
733                 if (!radix.isNumber())
734                     break;
735
736                 if (radix.asNumber() == 0 || radix.asNumber() == 10) {
737                     node->child2() = Edge();
738                     node->convertToIdentity();
739                     changed = true;
740                 }
741
742                 break;
743             }
744
745             case NumberToStringWithRadix: {
746                 JSValue radixValue = m_state.forNode(node->child2()).m_value;
747                 if (radixValue && radixValue.isInt32()) {
748                     int32_t radix = radixValue.asInt32();
749                     if (2 <= radix && radix <= 36) {
750                         if (radix == 10) {
751                             node->setOpAndDefaultFlags(ToString);
752                             node->clearFlags(NodeMustGenerate);
753                             node->child2() = Edge();
754                         } else
755                             node->convertToNumberToStringWithValidRadixConstant(radix);
756                         changed = true;
757                         break;
758                     }
759                 }
760                 break;
761             }
762
763             case Check: {
764                 alreadyHandled = true;
765                 m_interpreter.execute(indexInBlock);
766                 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
767                     Edge edge = node->children.child(i);
768                     if (!edge)
769                         break;
770                     if (edge.isProved() || edge.willNotHaveCheck()) {
771                         node->children.removeEdge(i--);
772                         changed = true;
773                     }
774                 }
775                 break;
776             }
777
778             case CheckVarargs: {
779                 alreadyHandled = true;
780                 m_interpreter.execute(indexInBlock);
781                 unsigned targetIndex = 0;
782                 for (unsigned i = 0; i < node->numChildren(); ++i) {
783                     Edge& edge = m_graph.varArgChild(node, i);
784                     if (!edge)
785                         continue;
786                     if (edge.isProved() || edge.willNotHaveCheck()) {
787                         edge = Edge();
788                         changed = true;
789                         continue;
790                     }
791                     Edge& dst = m_graph.varArgChild(node, targetIndex++);
792                     std::swap(dst, edge);
793                 }
794                 node->children.setNumChildren(targetIndex);
795                 break;
796             }
797
798             case MakeRope: {
799                 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
800                     Edge& edge = node->children.child(i);
801                     if (!edge)
802                         break;
803                     JSValue childConstant = m_state.forNode(edge).value();
804                     if (!childConstant)
805                         continue;
806                     if (!childConstant.isString())
807                         continue;
808                     if (asString(childConstant)->length())
809                         continue;
810
811                     // Don't allow the MakeRope to have zero children.
812                     if (!i && !node->child2())
813                         break;
814
815                     node->children.removeEdge(i--);
816                     changed = true;
817                 }
818
819                 if (!node->child2()) {
820                     ASSERT(!node->child3());
821                     node->convertToIdentity();
822                     changed = true;
823                 }
824                 break;
825             }
826
827             case CheckTypeInfoFlags: {
828                 const AbstractValue& abstractValue = m_state.forNode(node->child1());
829                 unsigned bits = node->typeInfoOperand();
830                 ASSERT(bits);
831                 if (bits == ImplementsDefaultHasInstance) {
832                     if (abstractValue.m_type == SpecFunctionWithDefaultHasInstance) {
833                         changed = true;
834                         node->remove(m_graph);
835                         break;
836                     }
837                 }
838
839                 if (JSValue value = abstractValue.value()) {
840                     if (value.isCell()) {
841                         // This works because if we see a cell here, we know it's fully constructed
842                         // and we can read its inline type info flags. These flags don't change over the
843                         // object's lifetime.
844                         if ((value.asCell()->inlineTypeFlags() & bits) == bits) {
845                             changed = true;
846                             node->remove(m_graph);
847                             break;
848                         }
849                     }
850                 }
851
852                 if (abstractValue.m_structure.isFinite()) {
853                     bool ok = true;
854                     abstractValue.m_structure.forEach([&] (RegisteredStructure structure) {
855                         ok &= (structure->typeInfo().inlineTypeFlags() & bits) == bits;
856                     });
857                     if (ok) {
858                         changed = true;
859                         node->remove(m_graph);
860                         break;
861                     }
862                 }
863
864                 break;
865             }
866                 
867             case PhantomNewObject:
868             case PhantomNewFunction:
869             case PhantomNewGeneratorFunction:
870             case PhantomNewAsyncGeneratorFunction:
871             case PhantomNewAsyncFunction:
872             case PhantomCreateActivation:
873             case PhantomDirectArguments:
874             case PhantomClonedArguments:
875             case PhantomCreateRest:
876             case PhantomSpread:
877             case PhantomNewArrayWithSpread:
878             case PhantomNewArrayBuffer:
879             case PhantomNewRegexp:
880             case BottomValue:
881                 alreadyHandled = true;
882                 break;
883
884             default:
885                 break;
886             }
887             
888             if (eliminated) {
889                 changed = true;
890                 continue;
891             }
892                 
893             if (alreadyHandled)
894                 continue;
895             
896             m_interpreter.execute(indexInBlock);
897             if (!m_state.isValid()) {
898                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
899                 // example:
900                 //
901                 //     c: JSConstant(4.2)
902                 //     x: ValueToInt32(Check:Int32:@const)
903                 //
904                 // It would be correct for an analysis to assume that execution cannot
905                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
906                 // the CFA may report that it found a constant even though it also reported
907                 // that everything has been invalidated. This will only happen in a couple of
908                 // the constant folding cases; most of them are also separately defensive
909                 // about such things.
910                 break;
911             }
912             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant() || !node->result())
913                 continue;
914             
915             // Interesting fact: this freezing that we do right here may turn an fragile value into
916             // a weak value. See DFGValueStrength.h.
917             FrozenValue* value = m_graph.freeze(m_state.forNode(node).value());
918             if (!*value)
919                 continue;
920             
921             if (node->op() == GetLocal) {
922                 // Need to preserve bytecode liveness in ThreadedCPS form. This wouldn't be necessary
923                 // if it wasn't for https://bugs.webkit.org/show_bug.cgi?id=144086.
924                 m_insertionSet.insertNode(
925                     indexInBlock, SpecNone, PhantomLocal, node->origin,
926                     OpInfo(node->variableAccessData()));
927                 m_graph.dethread();
928             } else
929                 m_insertionSet.insertCheck(m_graph, indexInBlock, node);
930             m_graph.convertToConstant(node, value);
931             
932             changed = true;
933         }
934         m_state.reset();
935         m_insertionSet.execute(block);
936         
937         return changed;
938     }
939     
940     void emitGetByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const MultiGetByOffsetCase& getCase, unsigned identifierNumber)
941     {
942         // When we get to here we have already emitted all of the requisite checks for everything.
943         // So, we just need to emit what the method object tells us to emit.
944         
945         addBaseCheck(indexInBlock, node, baseValue, getCase.set());
946
947         GetByOffsetMethod method = getCase.method();
948         
949         switch (method.kind()) {
950         case GetByOffsetMethod::Invalid:
951             RELEASE_ASSERT_NOT_REACHED();
952             return;
953             
954         case GetByOffsetMethod::Constant:
955             m_graph.convertToConstant(node, method.constant());
956             return;
957             
958         case GetByOffsetMethod::Load:
959             emitGetByOffset(indexInBlock, node, node->child1(), identifierNumber, method.offset());
960             return;
961             
962         case GetByOffsetMethod::LoadFromPrototype: {
963             Node* child = m_insertionSet.insertConstant(
964                 indexInBlock, node->origin, method.prototype());
965             emitGetByOffset(
966                 indexInBlock, node, Edge(child, KnownCellUse), identifierNumber, method.offset());
967             return;
968         } }
969         
970         RELEASE_ASSERT_NOT_REACHED();
971     }
972     
973     void emitGetByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const GetByIdVariant& variant, unsigned identifierNumber)
974     {
975         Edge childEdge = node->child1();
976
977         addBaseCheck(indexInBlock, node, baseValue, variant.structureSet());
978         
979         // We aren't set up to handle prototype stuff.
980         DFG_ASSERT(m_graph, node, variant.conditionSet().isEmpty());
981
982         if (JSValue value = m_graph.tryGetConstantProperty(baseValue.m_value, *m_graph.addStructureSet(variant.structureSet()), variant.offset())) {
983             m_graph.convertToConstant(node, m_graph.freeze(value));
984             return;
985         }
986         
987         emitGetByOffset(indexInBlock, node, childEdge, identifierNumber, variant.offset());
988     }
989     
990     void emitGetByOffset(
991         unsigned indexInBlock, Node* node, Edge childEdge, unsigned identifierNumber,
992         PropertyOffset offset, const InferredType::Descriptor& inferredType = InferredType::Top)
993     {
994         childEdge.setUseKind(KnownCellUse);
995         
996         Edge propertyStorage;
997         
998         if (isInlineOffset(offset))
999             propertyStorage = childEdge;
1000         else {
1001             propertyStorage = Edge(m_insertionSet.insertNode(
1002                 indexInBlock, SpecNone, GetButterfly, node->origin, childEdge));
1003         }
1004         
1005         StorageAccessData& data = *m_graph.m_storageAccessData.add();
1006         data.offset = offset;
1007         data.identifierNumber = identifierNumber;
1008         data.inferredType = inferredType;
1009         
1010         node->convertToGetByOffset(data, propertyStorage, childEdge);
1011     }
1012
1013     void emitPutByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const PutByIdVariant& variant, unsigned identifierNumber)
1014     {
1015         NodeOrigin origin = node->origin;
1016         Edge childEdge = node->child1();
1017
1018         addBaseCheck(indexInBlock, node, baseValue, variant.oldStructure());
1019         insertInferredTypeCheck(
1020             m_insertionSet, indexInBlock, origin, node->child2().node(), variant.requiredType());
1021
1022         node->child1().setUseKind(KnownCellUse);
1023         childEdge.setUseKind(KnownCellUse);
1024
1025         Transition* transition = 0;
1026         if (variant.kind() == PutByIdVariant::Transition) {
1027             transition = m_graph.m_transitions.add(
1028                 m_graph.registerStructure(variant.oldStructureForTransition()), m_graph.registerStructure(variant.newStructure()));
1029         }
1030
1031         Edge propertyStorage;
1032
1033         DFG_ASSERT(m_graph, node, origin.exitOK);
1034         bool canExit = true;
1035         bool didAllocateStorage = false;
1036
1037         if (isInlineOffset(variant.offset()))
1038             propertyStorage = childEdge;
1039         else if (!variant.reallocatesStorage()) {
1040             propertyStorage = Edge(m_insertionSet.insertNode(
1041                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
1042         } else if (!variant.oldStructureForTransition()->outOfLineCapacity()) {
1043             ASSERT(variant.newStructure()->outOfLineCapacity());
1044             ASSERT(!isInlineOffset(variant.offset()));
1045             Node* allocatePropertyStorage = m_insertionSet.insertNode(
1046                 indexInBlock, SpecNone, AllocatePropertyStorage,
1047                 origin, OpInfo(transition), childEdge);
1048             propertyStorage = Edge(allocatePropertyStorage);
1049             didAllocateStorage = true;
1050         } else {
1051             ASSERT(variant.oldStructureForTransition()->outOfLineCapacity());
1052             ASSERT(variant.newStructure()->outOfLineCapacity() > variant.oldStructureForTransition()->outOfLineCapacity());
1053             ASSERT(!isInlineOffset(variant.offset()));
1054
1055             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
1056                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
1057                 OpInfo(transition), childEdge,
1058                 Edge(m_insertionSet.insertNode(
1059                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
1060             propertyStorage = Edge(reallocatePropertyStorage);
1061             didAllocateStorage = true;
1062         }
1063
1064         StorageAccessData& data = *m_graph.m_storageAccessData.add();
1065         data.offset = variant.offset();
1066         data.identifierNumber = identifierNumber;
1067         
1068         node->convertToPutByOffset(data, propertyStorage, childEdge);
1069         node->origin.exitOK = canExit;
1070
1071         if (variant.kind() == PutByIdVariant::Transition) {
1072             if (didAllocateStorage) {
1073                 m_insertionSet.insertNode(
1074                     indexInBlock + 1, SpecNone, NukeStructureAndSetButterfly,
1075                     origin.withInvalidExit(), childEdge, propertyStorage);
1076             }
1077             
1078             // FIXME: PutStructure goes last until we fix either
1079             // https://bugs.webkit.org/show_bug.cgi?id=142921 or
1080             // https://bugs.webkit.org/show_bug.cgi?id=142924.
1081             m_insertionSet.insertNode(
1082                 indexInBlock + 1, SpecNone, PutStructure, origin.withInvalidExit(), OpInfo(transition),
1083                 childEdge);
1084         }
1085     }
1086     
1087     void addBaseCheck(
1088         unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const StructureSet& set)
1089     {
1090         addBaseCheck(indexInBlock, node, baseValue, *m_graph.addStructureSet(set));
1091     }
1092
1093     void addBaseCheck(
1094         unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const RegisteredStructureSet& set)
1095     {
1096         if (!baseValue.m_structure.isSubsetOf(set)) {
1097             // Arises when we prune MultiGetByOffset. We could have a
1098             // MultiGetByOffset with a single variant that checks for structure S,
1099             // and the input has structures S and T, for example.
1100             ASSERT(node->child1());
1101             m_insertionSet.insertNode(
1102                 indexInBlock, SpecNone, CheckStructure, node->origin,
1103                 OpInfo(m_graph.addStructureSet(set.toStructureSet())), node->child1());
1104             return;
1105         }
1106         
1107         if (baseValue.m_type & ~SpecCell)
1108             m_insertionSet.insertCheck(indexInBlock, node->origin, node->child1());
1109     }
1110     
1111     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell, Structure* structure)
1112     {
1113         {
1114             StructureRegistrationResult result;
1115             m_graph.registerStructure(cell->structure(), result);
1116             if (result == StructureRegisteredAndWatched)
1117                 return;
1118         }
1119         
1120         m_graph.registerStructure(structure);
1121
1122         Node* weakConstant = m_insertionSet.insertNode(
1123             indexInBlock, speculationFromValue(cell), JSConstant, origin,
1124             OpInfo(m_graph.freeze(cell)));
1125         
1126         m_insertionSet.insertNode(
1127             indexInBlock, SpecNone, CheckStructure, origin,
1128             OpInfo(m_graph.addStructureSet(structure)), Edge(weakConstant, CellUse));
1129     }
1130     
1131     void fixUpsilons(BasicBlock* block)
1132     {
1133         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
1134             Node* node = block->at(nodeIndex);
1135             if (node->op() != Upsilon)
1136                 continue;
1137             switch (node->phi()->op()) {
1138             case Phi:
1139                 break;
1140             case JSConstant:
1141             case DoubleConstant:
1142             case Int52Constant:
1143                 node->remove(m_graph);
1144                 break;
1145             default:
1146                 DFG_CRASH(m_graph, node, "Bad Upsilon phi() pointer");
1147                 break;
1148             }
1149         }
1150     }
1151     
1152     InPlaceAbstractState m_state;
1153     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
1154     InsertionSet m_insertionSet;
1155 };
1156
1157 bool performConstantFolding(Graph& graph)
1158 {
1159     return runPhase<ConstantFoldingPhase>(graph);
1160 }
1161
1162 } } // namespace JSC::DFG
1163
1164 #endif // ENABLE(DFG_JIT)
1165
1166