[INTL] Implement String.prototype.localeCompare in ECMA-402
https://bugs.webkit.org/show_bug.cgi?id=147607
Patch by Filip Pizlo <fpizlo@apple.com> and Andy VanWagoner <thetalecrafter@gmail.com> on 2016-04-24
Reviewed by Darin Adler.
Source/JavaScriptCore:
Part of this change is just rolling 194394 back in.
The other part is making that not a regression on CDjs. Other than the fact that it uses
bound functions, the problem with this new localeCompare implementation is that it uses
the arguments object. It uses it in a way that *seems* like ArgumentsEliminationPhase
ought to handle, but to my surprise it didn't:
- If we have a ForceExit GetByVal on the arguments object, we would previously assume that
it escaped. That's false since we just exit at ForceExit. On the other hand we probably
should be pruning unreachable paths before we get here, but that's a separate issue. I
don't want to play with phase order right now.
- If we have a OutOfBounds GetByVal on the arguments object, then the best that would
previously happen is that we'd compile it into an in-bounds arguments access. That's quite
bad, as Andy's localeCompare illustrates: it uses out-of-bounds access on the arguments
object to detect if an argument was passed. This change introduces an OutOfBounds version
of GetMyArgumentByVal for this purpose.
This change required registering sane chain watchpoints. In the process, I noticed that the
old way of doing it had a race condition: we might register watchpoints for the structure
that had become insane. This change introduces a double-checking idiom that I believe works
because once the structure becomes insane it can't go back to sane and watchpoints
registration already involves executing the hardest possible fences.
* builtins/StringPrototype.js:
(repeat):
(localeCompare):
(search):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGArgumentsEliminationPhase.cpp:
* dfg/DFGArrayMode.cpp:
(JSC::DFG::ArrayMode::refine):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::foldConstants):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGNodeType.h:
* dfg/DFGPreciseLocalClobberize.h:
(JSC::DFG::PreciseLocalClobberizeAdaptor::readTop):
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileGetByValOnString):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGValidate.cpp:
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileGetMyArgumentByVal):
(JSC::FTL::DFG::LowerDFGToB3::compilePutByVal):
(JSC::FTL::DFG::LowerDFGToB3::compileStringCharAt):
* ftl/FTLTypedPointer.h:
(JSC::FTL::TypedPointer::TypedPointer):
(JSC::FTL::TypedPointer::operator bool):
(JSC::FTL::TypedPointer::heap):
(JSC::FTL::TypedPointer::operator!): Deleted.
* runtime/StringPrototype.cpp:
(JSC::StringPrototype::finishCreation):
LayoutTests:
* js/dom/script-tests/string-prototype-properties.js:
* js/dom/string-prototype-properties-expected.txt:
* js/regress/locale-compare.html: Added.
* js/regress/locale-compare-expected.txt: Added.
* js/regress/scripts-tests/locale-compare.js: Added.
* js/script-tests/string-localeCompare.js:
* js/string-localeCompare-expected.txt:
* js/string-localeCompare.html:
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@199967 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
index 1004f91..45da2c2 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
@@ -1622,14 +1622,15 @@
forNode(node).makeHeapTop();
break;
- case GetMyArgumentByVal: {
+ case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds: {
JSValue index = forNode(node->child2()).m_value;
InlineCallFrame* inlineCallFrame = node->child1()->origin.semantic.inlineCallFrame;
if (index && index.isInt32()) {
// This pretends to return TOP for accesses that are actually proven out-of-bounds because
// that's the conservative thing to do. Otherwise we'd need to write more code to mark such
- // paths as unreachable, and it's almost certainly not worth the effort.
+ // paths as unreachable, or to return undefined. We could implement that eventually.
if (inlineCallFrame) {
if (index.asUInt32() < inlineCallFrame->arguments.size() - 1) {
@@ -1657,8 +1658,12 @@
virtualRegisterForArgument(i) + inlineCallFrame->stackOffset));
}
+ if (node->op() == GetMyArgumentByValOutOfBounds)
+ result.merge(SpecOther);
+
if (result.value())
m_state.setFoundConstants(true);
+
forNode(node) = result;
break;
}
diff --git a/Source/JavaScriptCore/dfg/DFGArgumentsEliminationPhase.cpp b/Source/JavaScriptCore/dfg/DFGArgumentsEliminationPhase.cpp
index 66cecd3..9192cf9 100644
--- a/Source/JavaScriptCore/dfg/DFGArgumentsEliminationPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGArgumentsEliminationPhase.cpp
@@ -134,11 +134,29 @@
escape(edge, source);
break;
- case Array::Int32:
- case Array::Double:
- case Array::Contiguous:
- if (edge->op() != CreateClonedArguments)
+ case Array::Contiguous: {
+ if (edge->op() != CreateClonedArguments) {
escape(edge, source);
+ return;
+ }
+
+ // Everything is fine if we're doing an in-bounds access.
+ if (mode.isInBounds())
+ break;
+
+ // If we're out-of-bounds then we proceed only if the object prototype is
+ // sane (i.e. doesn't have indexed properties).
+ JSGlobalObject* globalObject = m_graph.globalObjectFor(edge->origin.semantic);
+ if (globalObject->objectPrototypeIsSane()) {
+ m_graph.watchpoints().addLazily(globalObject->objectPrototype()->structure()->transitionWatchpointSet());
+ if (globalObject->objectPrototypeIsSane())
+ break;
+ }
+ escape(edge, source);
+ break;
+ }
+
+ case Array::ForceExit:
break;
default:
@@ -490,8 +508,13 @@
}
if (!result) {
+ NodeType op;
+ if (node->arrayMode().isInBounds())
+ op = GetMyArgumentByVal;
+ else
+ op = GetMyArgumentByValOutOfBounds;
result = insertionSet.insertNode(
- nodeIndex, node->prediction(), GetMyArgumentByVal, node->origin,
+ nodeIndex, node->prediction(), op, node->origin,
node->child1(), node->child2());
}
diff --git a/Source/JavaScriptCore/dfg/DFGArrayMode.cpp b/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
index 87ee3ad..162201d 100644
--- a/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
+++ b/Source/JavaScriptCore/dfg/DFGArrayMode.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -198,7 +198,8 @@
&& !graph.hasExitSite(node->origin.semantic, OutOfBounds)) {
graph.watchpoints().addLazily(globalObject->arrayPrototype()->structure()->transitionWatchpointSet());
graph.watchpoints().addLazily(globalObject->objectPrototype()->structure()->transitionWatchpointSet());
- return withSpeculation(Array::SaneChain);
+ if (globalObject->arrayPrototypeChainIsSane())
+ return withSpeculation(Array::SaneChain);
}
return ArrayMode(Array::Generic);
}
diff --git a/Source/JavaScriptCore/dfg/DFGClobberize.h b/Source/JavaScriptCore/dfg/DFGClobberize.h
index 71ef98a..2e0528a 100644
--- a/Source/JavaScriptCore/dfg/DFGClobberize.h
+++ b/Source/JavaScriptCore/dfg/DFGClobberize.h
@@ -661,7 +661,8 @@
return;
}
- case GetMyArgumentByVal: {
+ case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds: {
read(Stack);
// FIXME: It would be trivial to have a def here.
// https://bugs.webkit.org/show_bug.cgi?id=143077
diff --git a/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp b/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
index c9da359..029d61c 100644
--- a/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
@@ -288,7 +288,8 @@
break;
}
- case GetMyArgumentByVal: {
+ case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds: {
JSValue index = m_state.forNode(node->child2()).value();
if (!index || !index.isInt32())
break;
@@ -338,6 +339,9 @@
break;
}
+ if (node->op() == GetMyArgumentByValOutOfBounds)
+ break;
+
Node* length = emitCodeToGetArgumentsArrayLength(
m_insertionSet, arguments, indexInBlock, node->origin);
m_insertionSet.insertNode(
diff --git a/Source/JavaScriptCore/dfg/DFGDoesGC.cpp b/Source/JavaScriptCore/dfg/DFGDoesGC.cpp
index 02ef942..294fbf1 100644
--- a/Source/JavaScriptCore/dfg/DFGDoesGC.cpp
+++ b/Source/JavaScriptCore/dfg/DFGDoesGC.cpp
@@ -231,6 +231,7 @@
case PhantomDirectArguments:
case PhantomClonedArguments:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case ForwardVarargs:
case PutHint:
case CheckStructureImmediate:
diff --git a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
index 28bf040..344827e 100644
--- a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
@@ -713,7 +713,8 @@
globalObject->arrayPrototype()->structure()->transitionWatchpointSet());
m_graph.watchpoints().addLazily(
globalObject->objectPrototype()->structure()->transitionWatchpointSet());
- node->setArrayMode(arrayMode.withSpeculation(Array::SaneChain));
+ if (globalObject->arrayPrototypeChainIsSane())
+ node->setArrayMode(arrayMode.withSpeculation(Array::SaneChain));
}
}
}
@@ -1323,6 +1324,7 @@
case PhantomClonedArguments:
case ForwardVarargs:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case PutHint:
case CheckStructureImmediate:
case MaterializeNewObject:
diff --git a/Source/JavaScriptCore/dfg/DFGNodeType.h b/Source/JavaScriptCore/dfg/DFGNodeType.h
index 4f44749..529f571 100644
--- a/Source/JavaScriptCore/dfg/DFGNodeType.h
+++ b/Source/JavaScriptCore/dfg/DFGNodeType.h
@@ -177,6 +177,7 @@
/* opcodes use VarArgs beause they may have up to 4 children. */\
macro(GetByVal, NodeResultJS | NodeMustGenerate) \
macro(GetMyArgumentByVal, NodeResultJS | NodeMustGenerate) \
+ macro(GetMyArgumentByValOutOfBounds, NodeResultJS | NodeMustGenerate) \
macro(LoadVarargs, NodeMustGenerate) \
macro(ForwardVarargs, NodeMustGenerate) \
macro(PutByValDirect, NodeMustGenerate | NodeHasVarArgs) \
diff --git a/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h b/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h
index 3a7d716..3e5a833 100644
--- a/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h
+++ b/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -109,6 +109,7 @@
{
switch (m_node->op()) {
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case ForwardVarargs:
case CallForwardVarargs:
case ConstructForwardVarargs:
diff --git a/Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp b/Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
index 76ccc0e..f09dc54 100644
--- a/Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
@@ -955,6 +955,7 @@
case PhantomDirectArguments:
case PhantomClonedArguments:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case ForwardVarargs:
case PutHint:
case CheckStructureImmediate:
diff --git a/Source/JavaScriptCore/dfg/DFGSafeToExecute.h b/Source/JavaScriptCore/dfg/DFGSafeToExecute.h
index 0e5ea46..a88ca5d 100644
--- a/Source/JavaScriptCore/dfg/DFGSafeToExecute.h
+++ b/Source/JavaScriptCore/dfg/DFGSafeToExecute.h
@@ -339,6 +339,7 @@
case PhantomDirectArguments:
case PhantomClonedArguments:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case ForwardVarargs:
case CopyRest:
case StringReplace:
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
index 4b304e0..a3d0e56 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
@@ -1956,6 +1956,7 @@
#endif
JSGlobalObject* globalObject = m_jit.globalObjectFor(node->origin.semantic);
+ bool prototypeChainIsSane = false;
if (globalObject->stringPrototypeChainIsSane()) {
// FIXME: This could be captured using a Speculation mode that means "out-of-bounds
// loads return a trivial value". Something like SaneChainOutOfBounds. This should
@@ -1965,6 +1966,11 @@
// https://bugs.webkit.org/show_bug.cgi?id=144668
m_jit.graph().watchpoints().addLazily(globalObject->stringPrototype()->structure()->transitionWatchpointSet());
m_jit.graph().watchpoints().addLazily(globalObject->objectPrototype()->structure()->transitionWatchpointSet());
+ prototypeChainIsSane = globalObject->stringPrototypeChainIsSane();
+ }
+ if (prototypeChainIsSane) {
+ m_jit.graph().watchpoints().addLazily(globalObject->stringPrototype()->structure()->transitionWatchpointSet());
+ m_jit.graph().watchpoints().addLazily(globalObject->objectPrototype()->structure()->transitionWatchpointSet());
#if USE(JSVALUE64)
addSlowPathGenerator(std::make_unique<SaneStringGetByValSlowPathGenerator>(
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
index b52d10c..21f4207 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
@@ -5100,6 +5100,7 @@
case KillStack:
case GetStack:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
DFG_CRASH(m_jit.graph(), node, "unexpected node in DFG backend");
break;
}
diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
index 4d24a55..b52d47d 100644
--- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
+++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
@@ -5160,6 +5160,7 @@
case PhantomNewGeneratorFunction:
case PhantomCreateActivation:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case PutHint:
case CheckStructureImmediate:
case MaterializeCreateActivation:
diff --git a/Source/JavaScriptCore/dfg/DFGValidate.cpp b/Source/JavaScriptCore/dfg/DFGValidate.cpp
index cf86c5d..2b398eb 100644
--- a/Source/JavaScriptCore/dfg/DFGValidate.cpp
+++ b/Source/JavaScriptCore/dfg/DFGValidate.cpp
@@ -515,6 +515,7 @@
case PhantomNewGeneratorFunction:
case PhantomCreateActivation:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
case PutHint:
case CheckStructureImmediate:
case MaterializeCreateActivation:
@@ -662,6 +663,7 @@
case TailCallForwardVarargsInlinedCaller:
case ConstructForwardVarargs:
case GetMyArgumentByVal:
+ case GetMyArgumentByValOutOfBounds:
break;
case Check:
