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