blob: e90cf311c85b948e681284888b66a49433b72cd9 [file] [log] [blame]
/*
* Copyright (C) 2013-2021 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
#include "DFGStrengthReductionPhase.h"
#if ENABLE(DFG_JIT)
#include "ButterflyInlines.h"
#include "DFGAbstractHeap.h"
#include "DFGClobberize.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGJITCode.h"
#include "DFGPhase.h"
#include "MathCommon.h"
#include "RegExpObject.h"
#include "StringPrototype.h"
#include <cstdlib>
#include <wtf/text/StringBuilder.h>
namespace JSC { namespace DFG {
class StrengthReductionPhase : public Phase {
static constexpr bool verbose = false;
public:
StrengthReductionPhase(Graph& graph)
: Phase(graph, "strength reduction")
, m_insertionSet(graph)
{
}
bool run()
{
ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
m_changed = false;
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
m_block = m_graph.block(blockIndex);
if (!m_block)
continue;
for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
m_node = m_block->at(m_nodeIndex);
handleNode();
}
m_insertionSet.execute(m_block);
}
return m_changed;
}
private:
void handleNode()
{
switch (m_node->op()) {
case ArithBitOr:
handleCommutativity();
if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
convertToIdentityOverChild1();
break;
}
break;
case ArithBitXor:
case ArithBitAnd:
handleCommutativity();
break;
case ArithBitLShift:
case ArithBitRShift:
case BitURShift:
if (m_node->child1().useKind() != UntypedUse && m_node->child2()->isInt32Constant() && !(m_node->child2()->asInt32() & 0x1f)) {
convertToIdentityOverChild1();
break;
}
break;
case UInt32ToNumber:
if (m_node->child1()->op() == BitURShift
&& m_node->child1()->child2()->isInt32Constant()
&& (m_node->child1()->child2()->asInt32() & 0x1f)
&& m_node->arithMode() != Arith::DoOverflow) {
m_node->convertToIdentity();
m_changed = true;
break;
}
break;
case ArithAdd:
handleCommutativity();
if (m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
convertToIdentityOverChild1();
break;
}
break;
case ValueMul:
case ValueBitOr:
case ValueBitAnd:
case ValueBitXor: {
// FIXME: we should maybe support the case where one operand is always HeapBigInt and the other is always BigInt32?
if (m_node->binaryUseKind() == AnyBigIntUse || m_node->binaryUseKind() == BigInt32Use || m_node->binaryUseKind() == HeapBigIntUse)
handleCommutativity();
break;
}
case ArithMul: {
handleCommutativity();
Edge& child2 = m_node->child2();
if (child2->isNumberConstant() && child2->asNumber() == 2) {
switch (m_node->binaryUseKind()) {
case DoubleRepUse:
// It is always valuable to get rid of a double multiplication by 2.
// We won't have half-register dependencies issues on x86 and we won't have to load the constants.
m_node->setOp(ArithAdd);
child2.setNode(m_node->child1().node());
m_changed = true;
break;
#if USE(JSVALUE64)
case Int52RepUse:
#endif
case Int32Use:
// For integers, we can only convert compatible modes.
// ArithAdd does handle do negative zero check for example.
if (m_node->arithMode() == Arith::CheckOverflow || m_node->arithMode() == Arith::Unchecked) {
m_node->setOp(ArithAdd);
child2.setNode(m_node->child1().node());
m_changed = true;
}
break;
default:
break;
}
}
break;
}
case ArithSub:
if (m_node->child2()->isInt32Constant()
&& m_node->isBinaryUseKind(Int32Use)) {
int32_t value = m_node->child2()->asInt32();
if (value != INT32_MIN) {
m_node->setOp(ArithAdd);
m_node->child2().setNode(
m_insertionSet.insertConstant(
m_nodeIndex, m_node->origin, jsNumber(-value)));
m_changed = true;
break;
}
}
break;
case ArithPow:
if (m_node->child2()->isNumberConstant()) {
double yOperandValue = m_node->child2()->asNumber();
if (yOperandValue == 1) {
convertToIdentityOverChild1();
m_changed = true;
} else if (yOperandValue == 2) {
m_node->setOp(ArithMul);
m_node->child2() = m_node->child1();
m_changed = true;
}
}
break;
case ArithMod:
// On Integers
// In: ArithMod(ArithMod(x, const1), const2)
// Out: Identity(ArithMod(x, const1))
// if const1 <= const2.
if (m_node->binaryUseKind() == Int32Use
&& m_node->child2()->isInt32Constant()
&& m_node->child1()->op() == ArithMod
&& m_node->child1()->binaryUseKind() == Int32Use
&& m_node->child1()->child2()->isInt32Constant()) {
int32_t const1 = m_node->child1()->child2()->asInt32();
int32_t const2 = m_node->child2()->asInt32();
if (const1 == INT_MIN || const2 == INT_MIN)
break; // std::abs(INT_MIN) is undefined.
if (std::abs(const1) <= std::abs(const2))
convertToIdentityOverChild1();
}
break;
case ArithDiv:
// Transform
// ArithDiv(x, constant)
// Into
// ArithMul(x, 1 / constant)
// if the operation has the same result.
if (m_node->isBinaryUseKind(DoubleRepUse)
&& m_node->child2()->isNumberConstant()) {
if (std::optional<double> reciprocal = safeReciprocalForDivByConst(m_node->child2()->asNumber())) {
Node* reciprocalNode = m_insertionSet.insertConstant(m_nodeIndex, m_node->origin, jsDoubleNumber(*reciprocal), DoubleConstant);
m_node->setOp(ArithMul);
m_node->child2() = Edge(reciprocalNode, DoubleRepUse);
m_changed = true;
break;
}
}
break;
case ValueRep:
case Int52Rep: {
// This short-circuits circuitous conversions, like ValueRep(Int52Rep(value)).
// The only speculation that we would do beyond validating that we have a type that
// can be represented a certain way is an Int32 check that would appear on Int52Rep
// nodes. For now, if we see this and the final type we want is an Int52, we use it
// as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
bool hadInt32Check = false;
if (m_node->op() == Int52Rep) {
if (m_node->child1().useKind() != Int32Use)
break;
hadInt32Check = true;
}
for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
if (canonicalResultRepresentation(node->result()) ==
canonicalResultRepresentation(m_node->result())) {
m_insertionSet.insertCheck(m_graph, m_nodeIndex, m_node);
if (hadInt32Check) {
// FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
// which would be super weird. The latter would only arise in some
// seriously circuitous conversions.
if (canonicalResultRepresentation(node->result()) != NodeResultJS)
break;
m_insertionSet.insertCheck(
m_nodeIndex, m_node->origin, Edge(node, Int32Use));
}
m_node->child1() = node->defaultEdge();
m_node->convertToIdentity();
m_changed = true;
break;
}
switch (node->op()) {
case Int52Rep:
if (node->child1().useKind() != Int32Use)
break;
hadInt32Check = true;
continue;
case ValueRep:
continue;
default:
break;
}
break;
}
break;
}
case Flush: {
ASSERT(m_graph.m_form != SSA);
if (m_graph.willCatchExceptionInMachineFrame(m_node->origin.semantic)) {
// FIXME: We should be able to relax this:
// https://bugs.webkit.org/show_bug.cgi?id=150824
break;
}
Node* setLocal = nullptr;
Operand operand = m_node->operand();
for (unsigned i = m_nodeIndex; i--;) {
Node* node = m_block->at(i);
if (node->op() == SetLocal && node->operand() == operand) {
setLocal = node;
break;
}
if (accessesOverlap(m_graph, node, AbstractHeap(Stack, operand)))
break;
}
if (!setLocal)
break;
// The Flush should become a PhantomLocal at this point. This means that we want the
// local's value during OSR, but we don't care if the value is stored to the stack. CPS
// rethreading can canonicalize PhantomLocals for us.
m_node->convertFlushToPhantomLocal();
m_graph.dethread();
m_changed = true;
break;
}
// FIXME: we should probably do this in constant folding but this currently relies on OSR exit history:
// https://bugs.webkit.org/show_bug.cgi?id=154832
case OverridesHasInstance: {
if (!m_node->child2().node()->isCellConstant())
break;
if (m_node->child2().node()->asCell() != m_graph.globalObjectFor(m_node->origin.semantic)->functionProtoHasInstanceSymbolFunction()) {
m_graph.convertToConstant(m_node, jsBoolean(true));
m_changed = true;
} else if (!m_graph.hasExitSite(m_node->origin.semantic, BadTypeInfoFlags)) {
// We optimistically assume that we will not see a function that has a custom instanceof operation as they should be rare.
m_insertionSet.insertNode(m_nodeIndex, SpecNone, CheckTypeInfoFlags, m_node->origin, OpInfo(ImplementsDefaultHasInstance), Edge(m_node->child1().node(), CellUse));
m_graph.convertToConstant(m_node, jsBoolean(false));
m_changed = true;
}
break;
}
// FIXME: We have a lot of string constant-folding rules here. It would be great to
// move these to the abstract interpreter once AbstractValue can support LazyJSValue.
// https://bugs.webkit.org/show_bug.cgi?id=155204
case ValueAdd: {
if (m_node->child1()->isConstant()
&& m_node->child2()->isConstant()
&& (!!m_node->child1()->tryGetString(m_graph) || !!m_node->child2()->tryGetString(m_graph))) {
auto tryGetConstantString = [&] (Node* node) -> String {
String string = node->tryGetString(m_graph);
if (!string.isEmpty())
return string;
JSValue value = node->constant()->value();
if (!value)
return String();
if (value.isInt32())
return String::number(value.asInt32());
if (value.isNumber())
return String::number(value.asNumber());
if (value.isBoolean())
return value.asBoolean() ? "true"_s : "false"_s;
if (value.isNull())
return "null"_s;
if (value.isUndefined())
return "undefined"_s;
return String();
};
String leftString = tryGetConstantString(m_node->child1().node());
if (!leftString)
break;
String rightString = tryGetConstantString(m_node->child2().node());
if (!rightString)
break;
StringBuilder builder;
builder.append(leftString);
builder.append(rightString);
convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
m_changed = true;
break;
}
if (m_node->binaryUseKind() == BigInt32Use || m_node->binaryUseKind() == HeapBigIntUse || m_node->binaryUseKind() == AnyBigIntUse)
handleCommutativity();
break;
}
case MakeRope:
case StrCat: {
String leftString = m_node->child1()->tryGetString(m_graph);
if (!leftString)
break;
String rightString = m_node->child2()->tryGetString(m_graph);
if (!rightString)
break;
String extraString;
if (m_node->child3()) {
extraString = m_node->child3()->tryGetString(m_graph);
if (!extraString)
break;
}
StringBuilder builder;
builder.append(leftString);
builder.append(rightString);
if (!!extraString)
builder.append(extraString);
convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
m_changed = true;
break;
}
case ToString:
case CallStringConstructor: {
Edge& child1 = m_node->child1();
switch (child1.useKind()) {
case Int32Use:
case Int52RepUse:
case DoubleRepUse: {
if (child1->hasConstant()) {
JSValue value = child1->constant()->value();
if (value) {
String result;
if (value.isInt32())
result = String::number(value.asInt32());
else if (value.isNumber())
result = String::number(value.asNumber());
if (!result.isNull()) {
convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, result));
m_changed = true;
}
}
}
break;
}
default:
break;
}
break;
}
case NumberToStringWithValidRadixConstant: {
Edge& child1 = m_node->child1();
if (child1->hasConstant()) {
JSValue value = child1->constant()->value();
if (value && value.isNumber()) {
String result = toStringWithRadix(value.asNumber(), m_node->validRadixConstant());
convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, result));
m_changed = true;
}
}
break;
}
case GetArrayLength: {
if (m_node->arrayMode().type() == Array::Generic
|| m_node->arrayMode().type() == Array::String) {
String string = m_node->child1()->tryGetString(m_graph);
if (!!string) {
m_graph.convertToConstant(m_node, jsNumber(string.length()));
m_changed = true;
break;
}
}
break;
}
case GetGlobalObject: {
if (JSObject* object = m_node->child1()->dynamicCastConstant<JSObject*>()) {
m_graph.convertToConstant(m_node, object->globalObject());
m_changed = true;
break;
}
break;
}
case RegExpExec:
case RegExpTest:
case RegExpMatchFast:
case RegExpExecNonGlobalOrSticky: {
JSGlobalObject* globalObject = m_node->child1()->dynamicCastConstant<JSGlobalObject*>();
if (!globalObject) {
if (verbose)
dataLog("Giving up because no global object.\n");
break;
}
if (globalObject->isHavingABadTime()) {
if (verbose)
dataLog("Giving up because bad time.\n");
break;
}
Node* regExpObjectNode = nullptr;
RegExp* regExp = nullptr;
bool regExpObjectNodeIsConstant = false;
if (m_node->op() == RegExpExec || m_node->op() == RegExpTest || m_node->op() == RegExpMatchFast) {
regExpObjectNode = m_node->child2().node();
if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>()) {
JSGlobalObject* globalObject = regExpObject->globalObject();
if (globalObject->isRegExpRecompiled()) {
if (verbose)
dataLog("Giving up because RegExp recompile happens.\n");
break;
}
m_graph.watchpoints().addLazily(globalObject->regExpRecompiledWatchpoint());
regExp = regExpObject->regExp();
regExpObjectNodeIsConstant = true;
} else if (regExpObjectNode->op() == NewRegexp) {
JSGlobalObject* globalObject = m_graph.globalObjectFor(regExpObjectNode->origin.semantic);
if (globalObject->isRegExpRecompiled()) {
if (verbose)
dataLog("Giving up because RegExp recompile happens.\n");
break;
}
m_graph.watchpoints().addLazily(globalObject->regExpRecompiledWatchpoint());
regExp = regExpObjectNode->castOperand<RegExp*>();
} else {
if (verbose)
dataLog("Giving up because the regexp is unknown.\n");
break;
}
} else
regExp = m_node->castOperand<RegExp*>();
if (m_node->op() == RegExpMatchFast) {
if (regExp->global()) {
if (regExp->sticky())
break;
if (m_node->child3().useKind() != StringUse)
break;
NodeOrigin origin = m_node->origin;
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
OpInfo(false),
Edge(regExpObjectNode, RegExpObjectUse),
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(0), UntypedUse));
origin = origin.withInvalidExit();
m_node->convertToRegExpMatchFastGlobalWithoutChecks(m_graph.freeze(regExp));
m_node->origin = origin;
m_changed = true;
break;
}
m_node->setOp(RegExpExec);
m_changed = true;
// Continue performing strength reduction onto RegExpExec node.
}
ASSERT(m_node->op() != RegExpMatchFast);
unsigned lastIndex = UINT_MAX;
if (m_node->op() != RegExpExecNonGlobalOrSticky) {
// This will only work if we can prove what the value of lastIndex is. To do this
// safely, we need to execute the insertion set so that we see any previous strength
// reductions. This is needed for soundness since otherwise the effectfulness of any
// previous strength reductions would be invisible to us.
ASSERT(regExpObjectNode);
executeInsertionSet();
for (unsigned otherNodeIndex = m_nodeIndex; otherNodeIndex--;) {
Node* otherNode = m_block->at(otherNodeIndex);
if (otherNode == regExpObjectNode) {
if (regExpObjectNodeIsConstant)
break;
lastIndex = 0;
break;
}
if (otherNode->op() == SetRegExpObjectLastIndex
&& otherNode->child1() == regExpObjectNode
&& otherNode->child2()->isInt32Constant()
&& otherNode->child2()->asInt32() >= 0) {
lastIndex = otherNode->child2()->asUInt32();
break;
}
if (writesOverlap(m_graph, otherNode, RegExpObject_lastIndex))
break;
}
if (lastIndex == UINT_MAX) {
if (verbose)
dataLog("Giving up because the last index is not known.\n");
break;
}
}
if (!regExp->globalOrSticky())
lastIndex = 0;
auto foldToConstant = [&] {
Node* stringNode = nullptr;
if (m_node->op() == RegExpExecNonGlobalOrSticky)
stringNode = m_node->child2().node();
else
stringNode = m_node->child3().node();
// NOTE: This mostly already protects us from having the compiler execute a regexp
// operation on a ginormous string by preventing us from getting our hands on ginormous
// strings in the first place.
String string = stringNode->tryGetString(m_graph);
if (!string) {
if (verbose)
dataLog("Giving up because the string is unknown.\n");
return false;
}
FrozenValue* regExpFrozenValue = m_graph.freeze(regExp);
// Refuse to do things with regular expressions that have a ginormous number of
// subpatterns.
unsigned ginormousNumberOfSubPatterns = 1000;
if (regExp->numSubpatterns() > ginormousNumberOfSubPatterns) {
if (verbose)
dataLog("Giving up because of pattern limit.\n");
return false;
}
if ((m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky)) {
if (regExp->hasNamedCaptures()) {
// FIXME: https://bugs.webkit.org/show_bug.cgi?id=176464
// Implement strength reduction optimization for named capture groups.
if (verbose)
dataLog("Giving up because of named capture groups.\n");
return false;
}
if (regExp->hasIndices()) {
// FIXME: https://bugs.webkit.org/show_bug.cgi?id=220930
// Implement strength reduction optimization for RegExp with match indices.
if (verbose)
dataLog("Giving up because of match indices.\n");
return false;
}
}
m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
Structure* structure = globalObject->regExpMatchesArrayStructure();
if (structure->indexingType() != ArrayWithContiguous) {
// This is further protection against a race with haveABadTime.
if (verbose)
dataLog("Giving up because the structure has the wrong indexing type.\n");
return false;
}
m_graph.registerStructure(structure);
FrozenValue* globalObjectFrozenValue = m_graph.freeze(globalObject);
MatchResult result;
Vector<int> ovector;
// We have to call the kind of match function that the main thread would have called.
// Otherwise, we might not have the desired Yarr code compiled, and the match will fail.
if (m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) {
int position;
if (!regExp->matchConcurrently(vm(), string, lastIndex, position, ovector)) {
if (verbose)
dataLog("Giving up because match failed.\n");
return false;
}
result.start = position;
result.end = ovector[1];
} else {
if (!regExp->matchConcurrently(vm(), string, lastIndex, result)) {
if (verbose)
dataLog("Giving up because match failed.\n");
return false;
}
}
// We've constant-folded the regexp. Now we're committed to replacing RegExpExec/Test.
m_changed = true;
NodeOrigin origin = m_node->origin;
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
if (m_node->op() == RegExpExec || m_node->op() == RegExpExecNonGlobalOrSticky) {
if (result) {
RegisteredStructureSet* structureSet = m_graph.addStructureSet(structure);
// Create an array modeling the JS array that we will try to allocate. This is
// basically createRegExpMatchesArray but over C++ strings instead of JSStrings.
Vector<String> resultArray;
resultArray.append(string.substring(result.start, result.end - result.start));
for (unsigned i = 1; i <= regExp->numSubpatterns(); ++i) {
int start = ovector[2 * i];
if (start >= 0)
resultArray.append(string.substring(start, ovector[2 * i + 1] - start));
else
resultArray.append(String());
}
unsigned publicLength = resultArray.size();
unsigned vectorLength =
Butterfly::optimalContiguousVectorLength(structure, publicLength);
UniquedStringImpl* indexUID = vm().propertyNames->index.impl();
UniquedStringImpl* inputUID = vm().propertyNames->input.impl();
UniquedStringImpl* groupsUID = vm().propertyNames->groups.impl();
unsigned indexIndex = m_graph.identifiers().ensure(indexUID);
unsigned inputIndex = m_graph.identifiers().ensure(inputUID);
unsigned groupsIndex = m_graph.identifiers().ensure(groupsUID);
unsigned firstChild = m_graph.m_varArgChildren.size();
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, structure, KnownCellUse));
ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(publicLength), KnownInt32Use));
data->m_properties.append(PublicLengthPLoc);
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(vectorLength), KnownInt32Use));
data->m_properties.append(VectorLengthPLoc);
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(result.start), UntypedUse));
data->m_properties.append(
PromotedLocationDescriptor(NamedPropertyPLoc, indexIndex));
m_graph.m_varArgChildren.append(Edge(stringNode, UntypedUse));
data->m_properties.append(
PromotedLocationDescriptor(NamedPropertyPLoc, inputIndex));
// FIXME: https://bugs.webkit.org/show_bug.cgi?id=176464
// Implement strength reduction optimization for named capture groups.
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsUndefined(), UntypedUse));
data->m_properties.append(
PromotedLocationDescriptor(NamedPropertyPLoc, groupsIndex));
auto materializeString = [&] (const String& string) -> Node* {
if (string.isNull())
return nullptr;
if (string.isEmpty()) {
return m_insertionSet.insertConstant(
m_nodeIndex, origin, vm().smallStrings.emptyString());
}
LazyJSValue value = LazyJSValue::newString(m_graph, string);
return m_insertionSet.insertNode(
m_nodeIndex, SpecNone, LazyJSConstant, origin,
OpInfo(m_graph.m_lazyJSValues.add(value)));
};
for (unsigned i = 0; i < resultArray.size(); ++i) {
if (Node* node = materializeString(resultArray[i])) {
m_graph.m_varArgChildren.append(Edge(node, UntypedUse));
data->m_properties.append(
PromotedLocationDescriptor(IndexedPropertyPLoc, i));
}
}
Node* resultNode = m_insertionSet.insertNode(
m_nodeIndex, SpecArray, Node::VarArg, MaterializeNewObject, origin,
OpInfo(structureSet), OpInfo(data), firstChild,
m_graph.m_varArgChildren.size() - firstChild);
m_node->convertToIdentityOn(resultNode);
} else
m_graph.convertToConstant(m_node, jsNull());
} else
m_graph.convertToConstant(m_node, jsBoolean(!!result));
// Whether it's Exec or Test, we need to tell the globalObject and RegExpObject what's up.
// Because SetRegExpObjectLastIndex may exit and it clobbers exit state, we do that
// first.
if (regExp->globalOrSticky()) {
ASSERT(regExpObjectNode);
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
OpInfo(false),
Edge(regExpObjectNode, RegExpObjectUse),
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(result ? result.end : 0), UntypedUse));
origin = origin.withInvalidExit();
}
if (result) {
unsigned firstChild = m_graph.m_varArgChildren.size();
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, globalObjectFrozenValue, KnownCellUse));
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, regExpFrozenValue, KnownCellUse));
m_graph.m_varArgChildren.append(Edge(stringNode, KnownCellUse));
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(result.start), KnownInt32Use));
m_graph.m_varArgChildren.append(
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(result.end), KnownInt32Use));
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Node::VarArg, RecordRegExpCachedResult, origin,
OpInfo(), OpInfo(), firstChild, m_graph.m_varArgChildren.size() - firstChild);
origin = origin.withInvalidExit();
}
m_node->origin = origin;
return true;
};
#if ENABLE(YARR_JIT_REGEXP_TEST_INLINE)
auto convertTestToTestInline = [&] {
if (m_node->op() != RegExpTest)
return false;
if (regExp->globalOrSticky())
return false;
if (regExp->unicode())
return false;
auto jitCodeBlock = regExp->getRegExpJITCodeBlock();
if (!jitCodeBlock)
return false;
auto inlineCodeStats8Bit = jitCodeBlock->get8BitInlineStats();
if (!inlineCodeStats8Bit.canInline())
return false;
unsigned codeSize = inlineCodeStats8Bit.codeSize();
if (codeSize > Options::maximumRegExpTestInlineCodesize())
return false;
unsigned alignedFrameSize = WTF::roundUpToMultipleOf(stackAlignmentBytes(), inlineCodeStats8Bit.stackSize());
if (alignedFrameSize)
m_graph.m_parameterSlots = std::max(m_graph.m_parameterSlots, argumentCountForStackSize(alignedFrameSize));
NodeOrigin origin = m_node->origin;
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
m_node->convertToRegExpTestInline(m_graph.freeze(globalObject), m_graph.freeze(regExp));
m_changed = true;
return true;
};
#endif
auto convertToStatic = [&] {
if (m_node->op() != RegExpExec)
return false;
if (regExp->globalOrSticky())
return false;
if (m_node->child3().useKind() != StringUse)
return false;
NodeOrigin origin = m_node->origin;
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
m_node->convertToRegExpExecNonGlobalOrStickyWithoutChecks(m_graph.freeze(regExp));
m_changed = true;
return true;
};
if (foldToConstant())
break;
#if ENABLE(YARR_JIT_REGEXP_TEST_INLINE)
if (convertTestToTestInline())
break;
#endif
if (convertToStatic())
break;
break;
}
case StringReplace:
case StringReplaceRegExp: {
Node* stringNode = m_node->child1().node();
String string = stringNode->tryGetString(m_graph);
if (!string)
break;
Node* regExpObjectNode = m_node->child2().node();
RegExp* regExp;
if (RegExpObject* regExpObject = regExpObjectNode->dynamicCastConstant<RegExpObject*>()) {
JSGlobalObject* globalObject = regExpObject->globalObject();
if (globalObject->isRegExpRecompiled()) {
if (verbose)
dataLog("Giving up because RegExp recompile happens.\n");
break;
}
m_graph.watchpoints().addLazily(globalObject->regExpRecompiledWatchpoint());
regExp = regExpObject->regExp();
} else if (regExpObjectNode->op() == NewRegexp) {
JSGlobalObject* globalObject = m_graph.globalObjectFor(regExpObjectNode->origin.semantic);
if (globalObject->isRegExpRecompiled()) {
if (verbose)
dataLog("Giving up because RegExp recompile happens.\n");
break;
}
m_graph.watchpoints().addLazily(globalObject->regExpRecompiledWatchpoint());
regExp = regExpObjectNode->castOperand<RegExp*>();
} else {
if (verbose)
dataLog("Giving up because the regexp is unknown.\n");
break;
}
String replace = m_node->child3()->tryGetString(m_graph);
if (!replace)
break;
StringBuilder builder;
unsigned lastIndex = 0;
unsigned startPosition = 0;
bool ok = true;
do {
MatchResult result;
Vector<int> ovector;
// Model which version of match() is called by the main thread.
if (replace.isEmpty() && regExp->global()) {
if (!regExp->matchConcurrently(vm(), string, startPosition, result)) {
ok = false;
break;
}
} else {
int position;
if (!regExp->matchConcurrently(vm(), string, startPosition, position, ovector)) {
ok = false;
break;
}
result.start = position;
result.end = ovector[1];
}
if (!result)
break;
unsigned replLen = replace.length();
if (lastIndex < result.start || replLen) {
builder.appendSubstring(string, lastIndex, result.start - lastIndex);
if (replLen) {
StringBuilder replacement;
substituteBackreferences(replacement, replace, string, ovector.data(), regExp);
builder.append(replacement);
}
}
lastIndex = result.end;
startPosition = lastIndex;
// special case of empty match
if (result.empty()) {
startPosition++;
if (startPosition > string.length())
break;
}
} while (regExp->global());
if (!ok)
break;
// We are committed at this point.
m_changed = true;
NodeOrigin origin = m_node->origin;
// Preserve any checks we have.
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, Check, origin, m_node->children.justChecks());
if (regExp->global()) {
m_insertionSet.insertNode(
m_nodeIndex, SpecNone, SetRegExpObjectLastIndex, origin,
OpInfo(false),
Edge(regExpObjectNode, RegExpObjectUse),
m_insertionSet.insertConstantForUse(
m_nodeIndex, origin, jsNumber(0), UntypedUse));
origin = origin.withInvalidExit();
}
if (!lastIndex && builder.isEmpty())
m_node->convertToIdentityOn(stringNode);
else {
builder.appendSubstring(string, lastIndex);
m_node->convertToLazyJSConstant(m_graph, LazyJSValue::newString(m_graph, builder.toString()));
}
m_node->origin = origin;
break;
}
case Call:
case Construct:
case TailCallInlinedCaller:
case TailCall: {
ExecutableBase* executable = nullptr;
Edge callee = m_graph.varArgChild(m_node, 0);
CallVariant callVariant;
if (JSFunction* function = callee->dynamicCastConstant<JSFunction*>()) {
executable = function->executable();
callVariant = CallVariant(function);
} else if (callee->isFunctionAllocation()) {
executable = callee->castOperand<FunctionExecutable*>();
callVariant = CallVariant(executable);
}
if (!executable)
break;
if (m_graph.m_plan.isUnlinked())
break;
if (m_graph.m_plan.isFTL()) {
if (Options::useDataICInFTL())
break;
}
// FIXME: Support wasm IC.
// DirectCall to wasm function has suboptimal implementation. We avoid using DirectCall if we know that function is a wasm function.
// https://bugs.webkit.org/show_bug.cgi?id=220339
if (executable->intrinsic() == WasmFunctionIntrinsic)
break;
if (FunctionExecutable* functionExecutable = jsDynamicCast<FunctionExecutable*>(executable)) {
if (m_node->op() == Construct && functionExecutable->constructAbility() == ConstructAbility::CannotConstruct)
break;
// We need to update m_parameterSlots before we get to the backend, but we don't
// want to do too much of this.
unsigned numAllocatedArgs =
static_cast<unsigned>(functionExecutable->parameterCount()) + 1;
if (numAllocatedArgs <= Options::maximumDirectCallStackSize()) {
m_graph.m_parameterSlots = std::max(
m_graph.m_parameterSlots,
Graph::parameterSlotsForArgCount(numAllocatedArgs));
}
}
m_graph.m_plan.recordedStatuses().addCallLinkStatus(m_node->origin.semantic, CallLinkStatus(callVariant));
m_node->convertToDirectCall(m_graph.freeze(executable));
m_changed = true;
break;
}
default:
break;
}
}
void convertToIdentityOverChild(unsigned childIndex)
{
ASSERT(!(m_node->flags() & NodeHasVarArgs));
m_insertionSet.insertCheck(m_graph, m_nodeIndex, m_node);
m_node->children.removeEdge(childIndex ^ 1);
m_node->convertToIdentity();
m_changed = true;
}
void convertToIdentityOverChild1()
{
convertToIdentityOverChild(0);
}
void convertToIdentityOverChild2()
{
convertToIdentityOverChild(1);
}
void convertToLazyJSValue(Node* node, LazyJSValue value)
{
m_insertionSet.insertCheck(m_graph, m_nodeIndex, node);
node->convertToLazyJSConstant(m_graph, value);
}
void handleCommutativity()
{
// It's definitely not sound to swap the lhs and rhs when we may be performing effectful
// calls on the lhs/rhs for valueOf.
if (m_node->child1().useKind() == UntypedUse || m_node->child2().useKind() == UntypedUse)
return;
// If the right side is a constant then there is nothing left to do.
if (m_node->child2()->hasConstant())
return;
// This case ensures that optimizations that look for x + const don't also have
// to look for const + x.
if (m_node->child1()->hasConstant() && !m_node->child1()->asJSValue().isCell()) {
std::swap(m_node->child1(), m_node->child2());
m_changed = true;
return;
}
// This case ensures that CSE is commutativity-aware.
if (m_node->child1().node() > m_node->child2().node()) {
std::swap(m_node->child1(), m_node->child2());
m_changed = true;
return;
}
}
void executeInsertionSet()
{
m_nodeIndex += m_insertionSet.execute(m_block);
}
InsertionSet m_insertionSet;
BasicBlock* m_block;
unsigned m_nodeIndex;
Node* m_node;
bool m_changed;
};
bool performStrengthReduction(Graph& graph)
{
return runPhase<StrengthReductionPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)