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