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