Bug 42182 - Change how numeric compare functions are detected
authorbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 13 Jul 2010 20:34:11 +0000 (20:34 +0000)
committerbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 13 Jul 2010 20:34:11 +0000 (20:34 +0000)
Reviewed by Oliver Hunt.

JavaScriptCore:

There are three problems with the current mechanism:
  * It requires that a function executable be bytecode compiled without
    being JIT generated (in order to copy the bytecode from the numeric
    compare function).  This is a problem since we have an invariant when
    running with the JIT that functions are never bytecode compiled without
    also being JIT generated (after checking the codeblock we assume the
    function has JIT code).  To help maintain this invariant
  * This implementation will prevent us from experimenting with alternate
    compilation paths which do not compile via bytecode.
  * It doesn't work.  Functions passing more than two arguments will match
    if they are comparing their last two arguments, not the first two.
    Generally the mapping back from bytecode to semantics may be more
    complex then initially expected.

* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::generate):
(JSC::BytecodeGenerator::setIsNumericCompareFunction):
(JSC::BytecodeGenerator::argumentNumberFor):
* bytecompiler/BytecodeGenerator.h:
* bytecompiler/NodesCodegen.cpp:
(JSC::BlockNode::singleStatement):
(JSC::FunctionBodyNode::emitBytecode):
* parser/Nodes.h:
(JSC::ExpressionNode::isSubtract):
(JSC::BinaryOpNode::lhs):
(JSC::BinaryOpNode::rhs):
(JSC::SubNode::isSubtract):
(JSC::ReturnNode::value):
* runtime/JSGlobalData.cpp:
(JSC::JSGlobalData::JSGlobalData):
* runtime/JSGlobalData.h:

LayoutTests:

Test case.

* fast/js/array-sort-numericCompare-expected.txt: Added.
* fast/js/array-sort-numericCompare.html: Added.
* fast/js/script-tests/array-sort-numericCompare.js: Added.
(doSort):
(dontSort):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@63244 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
JavaScriptCore/bytecompiler/BytecodeGenerator.h
JavaScriptCore/bytecompiler/NodesCodegen.cpp
JavaScriptCore/parser/Nodes.cpp
JavaScriptCore/parser/Nodes.h
JavaScriptCore/runtime/JSGlobalData.cpp
JavaScriptCore/runtime/JSGlobalData.h
LayoutTests/ChangeLog
LayoutTests/fast/js/array-sort-numericCompare-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/array-sort-numericCompare.html [new file with mode: 0644]
LayoutTests/fast/js/script-tests/array-sort-numericCompare.js [new file with mode: 0644]

index f7a6dc8290fa47ed8d216619d5ec9760a981bdc5..eefcf40d2966a368784115ab7e28d6d57e754a46 100644 (file)
@@ -1,3 +1,41 @@
+2010-07-13  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Bug 42182 - Change how numeric compare functions are detected
+
+        There are three problems with the current mechanism:
+          * It requires that a function executable be bytecode compiled without
+            being JIT generated (in order to copy the bytecode from the numeric
+            compare function).  This is a problem since we have an invariant when
+            running with the JIT that functions are never bytecode compiled without
+            also being JIT generated (after checking the codeblock we assume the
+            function has JIT code).  To help maintain this invariant 
+          * This implementation will prevent us from experimenting with alternate
+            compilation paths which do not compile via bytecode.
+          * It doesn't work.  Functions passing more than two arguments will match
+            if they are comparing their last two arguments, not the first two.
+            Generally the mapping back from bytecode to semantics may be more
+            complex then initially expected.
+
+        * bytecompiler/BytecodeGenerator.cpp:
+        (JSC::BytecodeGenerator::generate):
+        (JSC::BytecodeGenerator::setIsNumericCompareFunction):
+        (JSC::BytecodeGenerator::argumentNumberFor):
+        * bytecompiler/BytecodeGenerator.h:
+        * bytecompiler/NodesCodegen.cpp:
+        (JSC::BlockNode::singleStatement):
+        (JSC::FunctionBodyNode::emitBytecode):
+        * parser/Nodes.h:
+        (JSC::ExpressionNode::isSubtract):
+        (JSC::BinaryOpNode::lhs):
+        (JSC::BinaryOpNode::rhs):
+        (JSC::SubNode::isSubtract):
+        (JSC::ReturnNode::value):
+        * runtime/JSGlobalData.cpp:
+        (JSC::JSGlobalData::JSGlobalData):
+        * runtime/JSGlobalData.h:
+
 2010-07-12  Oliver Hunt  <oliver@apple.com>
 
         Reviewed by Gavin Barraclough.
index 8ff1b5d91bb2d90bd39ac5b8ceeacb39a347808a..ff8a9c66d9280bb10ee673c9b9397185bfce9c63 100644 (file)
@@ -152,8 +152,6 @@ void BytecodeGenerator::generate()
 
     if ((m_codeType == FunctionCode && !m_codeBlock->needsFullScopeChain() && !m_codeBlock->usesArguments()) || m_codeType == EvalCode)
         symbolTable().clear();
-        
-    m_codeBlock->setIsNumericCompareFunction(instructions() == m_globalData->numericCompareFunction(m_scopeChain->globalObject()->globalExec()));
 
 #if !ENABLE(OPCODE_SAMPLING)
     if (!m_regeneratingForExceptionInfo && !m_usesExceptions && (m_codeType == FunctionCode || m_codeType == EvalCode))
@@ -2045,4 +2043,16 @@ RegisterID* BytecodeGenerator::emitThrowExpressionTooDeepException()
     return exception;
 }
 
+void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
+{
+    m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
+}
+
+int BytecodeGenerator::argumentNumberFor(const Identifier& ident)
+{
+    int parameterCount = m_parameters.size(); // includes 'this'
+    int index = registerFor(ident)->index() + RegisterFile::CallFrameHeaderSize + parameterCount;
+    return (index > 0 && index < parameterCount) ? index : 0;
+}
+
 } // namespace JSC
index 2b231a7de1e2baf92dad796d66ff6795ee262384..ad0ae4ef9095116311e2977fa8f3a8319478c770 100644 (file)
@@ -108,7 +108,12 @@ namespace JSC {
         // such register exists. Registers returned by registerFor do not
         // require explicit reference counting.
         RegisterID* registerFor(const Identifier&);
-        
+
+        // Returns the agument number if this is an argument, or 0 if not.
+        int argumentNumberFor(const Identifier&);
+
+        void setIsNumericCompareFunction(bool isNumericCompareFunction);
+
         bool willResolveToArguments(const Identifier&);
         RegisterID* uncheckedRegisterForArguments();
 
index e50ce2d9dc51e5319f90553467312e85330f360d..1337ab704df1760ccaa1eca89023ab818e0b25c6 100644 (file)
@@ -1359,6 +1359,11 @@ inline StatementNode* BlockNode::lastStatement() const
     return m_statements ? m_statements->lastStatement() : 0;
 }
 
+inline StatementNode* BlockNode::singleStatement() const
+{
+    return m_statements ? m_statements->singleStatement() : 0;
+}
+
 RegisterID* BlockNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
 {
     if (m_statements)
@@ -2011,16 +2016,38 @@ RegisterID* FunctionBodyNode::emitBytecode(BytecodeGenerator& generator, Registe
 {
     generator.emitDebugHook(DidEnterCallFrame, firstLine(), lastLine());
     emitStatementsBytecode(generator, generator.ignoredResult());
+
     StatementNode* singleStatement = this->singleStatement();
+    ReturnNode* returnNode = 0;
+
+    // Check for a return statement at the end of a function composed of a single block.
     if (singleStatement && singleStatement->isBlock()) {
         StatementNode* lastStatementInBlock = static_cast<BlockNode*>(singleStatement)->lastStatement();
         if (lastStatementInBlock && lastStatementInBlock->isReturnNode())
-            return 0;
+            returnNode = static_cast<ReturnNode*>(lastStatementInBlock);
+    }
+
+    // If there is no return we must automatically insert one.
+    if (!returnNode) {
+        RegisterID* r0 = generator.isConstructor() ? generator.thisRegister() : generator.emitLoad(0, jsUndefined());
+        generator.emitDebugHook(WillLeaveCallFrame, firstLine(), lastLine());
+        generator.emitReturn(r0);
+        return 0;
+    }
+
+    // If there is a return statment, and it is the only statement in the function, check if this is a numeric compare.
+    if (returnNode && static_cast<BlockNode*>(singleStatement)->singleStatement()) {
+        ExpressionNode* returnValueExpression = returnNode->value();
+        if (returnValueExpression && returnValueExpression->isSubtract()) {
+            ExpressionNode* lhsExpression = static_cast<SubNode*>(returnValueExpression)->lhs();
+            ExpressionNode* rhsExpression = static_cast<SubNode*>(returnValueExpression)->rhs();
+            if (lhsExpression->isResolveNode() && rhsExpression->isResolveNode()) {
+                generator.setIsNumericCompareFunction(generator.argumentNumberFor(static_cast<ResolveNode*>(lhsExpression)->identifier()) == 1
+                    && generator.argumentNumberFor(static_cast<ResolveNode*>(rhsExpression)->identifier()) == 2);
+            }
+        }
     }
 
-    RegisterID* r0 = generator.isConstructor() ? generator.thisRegister() : generator.emitLoad(0, jsUndefined());
-    generator.emitDebugHook(WillLeaveCallFrame, firstLine(), lastLine());
-    generator.emitReturn(r0);
     return 0;
 }
 
index ffea524a0eebbdcfbfdc6d9b475c65ab69837d0c..c41d735cd61e5f3ce53c2cc8c813f4629e6f5f1f 100644 (file)
@@ -67,7 +67,7 @@ void SourceElements::append(StatementNode* statement)
     m_statements.append(statement);
 }
 
-inline StatementNode* SourceElements::singleStatement() const
+StatementNode* SourceElements::singleStatement() const
 {
     size_t size = m_statements.size();
     return size == 1 ? m_statements[0] : 0;
index 62063842be5dbe49c3b3df3e3099100ebe7feaad..d25079b5def3121cd82e86e66f0e64d6d583a30c 100644 (file)
@@ -152,6 +152,7 @@ namespace JSC {
         virtual bool isCommaNode() const { return false; }
         virtual bool isSimpleArray() const { return false; }
         virtual bool isAdd() const { return false; }
+        virtual bool isSubtract() const { return false; }
         virtual bool hasConditionContextCodegen() const { return false; }
 
         virtual void emitBytecodeInConditionContext(BytecodeGenerator&, Label*, Label*, bool) { ASSERT_NOT_REACHED(); }
@@ -806,6 +807,9 @@ namespace JSC {
 
         RegisterID* emitStrcat(BytecodeGenerator& generator, RegisterID* destination, RegisterID* lhs = 0, ReadModifyResolveNode* emitExpressionInfoForMe = 0);
 
+        ExpressionNode* lhs() { return m_expr1; };
+        ExpressionNode* rhs() { return m_expr2; };
+
     private:
         virtual RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0);
 
@@ -854,6 +858,8 @@ namespace JSC {
     class SubNode : public BinaryOpNode {
     public:
         SubNode(JSGlobalData*, ExpressionNode* expr1, ExpressionNode* expr2, bool rightHasAssignments);
+
+        virtual bool isSubtract() const { return true; }
     };
 
     class LeftShiftNode : public BinaryOpNode {
@@ -1143,6 +1149,7 @@ namespace JSC {
     public:
         BlockNode(JSGlobalData*, SourceElements* = 0);
 
+        StatementNode* singleStatement() const;
         StatementNode* lastStatement() const;
 
     private:
@@ -1294,6 +1301,8 @@ namespace JSC {
     public:
         ReturnNode(JSGlobalData*, ExpressionNode* value);
 
+        ExpressionNode* value() { return m_value; }
+
     private:
         virtual RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0);
 
index 15087504f6648e01a6ebbc94b4121b5dc3d17391..b23606eda3e5edd39c07f1f3482ae41c66ebbda0 100644 (file)
@@ -140,7 +140,6 @@ JSGlobalData::JSGlobalData(GlobalDataType globalDataType, ThreadStackType thread
     , jitStubs(this)
 #endif
     , heap(this)
-    , initializingLazyNumericCompareFunction(false)
     , head(0)
     , dynamicGlobalObject(0)
     , functionCodeBlockBeingReparsed(0)
@@ -257,19 +256,6 @@ JSGlobalData*& JSGlobalData::sharedInstanceInternal()
     return sharedInstance;
 }
 
-// FIXME: We can also detect forms like v1 < v2 ? -1 : 0, reverse comparison, etc.
-const Vector<Instruction>& JSGlobalData::numericCompareFunction(ExecState* exec)
-{
-    if (!lazyNumericCompareFunction.size() && !initializingLazyNumericCompareFunction) {
-        initializingLazyNumericCompareFunction = true;
-        RefPtr<FunctionExecutable> function = FunctionExecutable::fromGlobalCode(Identifier(exec, "numericCompare"), exec, 0, makeSource(UString("(function (v1, v2) { return v1 - v2; })")), 0, 0);
-        lazyNumericCompareFunction = function->bytecodeForCall(exec, exec->scopeChain())->instructions();
-        initializingLazyNumericCompareFunction = false;
-    }
-
-    return lazyNumericCompareFunction;
-}
-
 #if ENABLE(JIT)
 PassRefPtr<NativeExecutable> JSGlobalData::getHostFunction(NativeFunction function)
 {
index f3f6cba1f12286daa161f115869d22574df92c96..bbb1e31010dd1c7f3f8ffea22b4e93d7f30544a4 100644 (file)
@@ -195,10 +195,6 @@ namespace JSC {
         ReturnAddressPtr exceptionLocation;
 #endif
 
-        const Vector<Instruction>& numericCompareFunction(ExecState*);
-        Vector<Instruction> lazyNumericCompareFunction;
-        bool initializingLazyNumericCompareFunction;
-
         HashMap<OpaqueJSClass*, OpaqueJSClassContextData*> opaqueJSClassData;
 
         JSGlobalObject* head;
index e3ab66a4be09128d74a04dac358a46b20d705820..972851a614b9d6f8b5b91d1ec9afc937b60f865c 100644 (file)
@@ -1,3 +1,17 @@
+2010-07-13  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Bug 42182 - Change how numeric compare functions are detected
+
+        Test case.
+
+        * fast/js/array-sort-numericCompare-expected.txt: Added.
+        * fast/js/array-sort-numericCompare.html: Added.
+        * fast/js/script-tests/array-sort-numericCompare.js: Added.
+        (doSort):
+        (dontSort):
+
 2010-07-13  Eric Carlson  <eric.carlson@apple.com>
 
         Reviewed by Dan Bernstein.
diff --git a/LayoutTests/fast/js/array-sort-numericCompare-expected.txt b/LayoutTests/fast/js/array-sort-numericCompare-expected.txt
new file mode 100644 (file)
index 0000000..a17a715
--- /dev/null
@@ -0,0 +1,11 @@
+This tests that a call to array.sort(compareFunction) works correctly for numeric comparisons (arg1 - arg2), and also for things that might look like numeric comparisons.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS [3,1,5,2,4].sort(doSort) is [1,2,3,4,5]
+PASS [3,1,5,2,4].sort(dontSort) is [3,1,5,2,4]
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/array-sort-numericCompare.html b/LayoutTests/fast/js/array-sort-numericCompare.html
new file mode 100644 (file)
index 0000000..44124f9
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="script-tests/array-sort-numericCompare.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/script-tests/array-sort-numericCompare.js b/LayoutTests/fast/js/script-tests/array-sort-numericCompare.js
new file mode 100644 (file)
index 0000000..1bcc67e
--- /dev/null
@@ -0,0 +1,18 @@
+description(
+"This tests that a call to array.sort(compareFunction) works correctly for numeric comparisons (arg1 - arg2), and also for things that might look like numeric comparisons."
+);
+
+function doSort(x, y)
+{
+    return x - y;
+}
+
+function dontSort(w, x, y)
+{
+    return x - y;
+}
+
+shouldBe("[3,1,5,2,4].sort(doSort)", "[1,2,3,4,5]");
+shouldBe("[3,1,5,2,4].sort(dontSort)", "[3,1,5,2,4]");
+
+var successfullyParsed = true;