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