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
43namespace JSC { namespace DFG {
44
45class ConstantFoldingPhase : public Phase {
46public:
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
115private:
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
1236bool performConstantFolding(Graph& graph)
1237{
1238 return runPhase<ConstantFoldingPhase>(graph);
1239}
1240
1241} } // namespace JSC::DFG
1242
1243#endif // ENABLE(DFG_JIT)
1244
1245
1246