Changeset 51735 in webkit for trunk/JavaScriptCore/parser

Timestamp:

Dec 6, 2009, 1:42:03 AM (15 years ago)

Author:

[email protected]

Message:

2009-12-05 Maciej Stachowiak <​[email protected]>

Reviewed by Oliver Hunt.

conway benchmark spends half it's time in op_less (jump fusion fails)
​https://bugs.webkit.org/show_bug.cgi?id=32190

<1% speedup on SunSpider and V8
2x speedup on "conway" benchmark

Two optimizations:

1) Improve codegen for logical operators &&,

and ! in a condition context

When generating code for combinations of &&,

and !, in a

condition context (i.e. in an if statement or loop condition), we
used to produce a value, and then separately jump based on its
truthiness. Now we pass the false and true targets in, and let the
logical operators generate jumps directly. This helps in four
ways:

a) Individual clauses of a short-circuit logical operator can now
jump directly to the then or else clause of an if statement (or to
the top or exit of a loop) instead of jumping to a jump.

b) It used to be that jump fusion with the condition of the first
clause of a logical operator was inhibited, because the register
was ref'd to be used later, in the actual condition jump; this no
longer happens since a jump straight to the final target is
generated directly.

c) It used to be that jump fusion with the condition of the second
clause of a logical operator was inhibited, because there was a
jump target right after the second clause and before the actual
condition jump. But now it's no longer necessary for the first
clause to jump there so jump fusion is not blocked.

d) We avoid generating excess mov statements in some cases.

As a concrete example this source:

if (!((x < q && y < q)

(t < q && z < q))) {

...

}

Used to generate this bytecode:

[ 34] less r1, r-15, r-19
[ 38] jfalse r1, 7(->45)
[ 41] less r1, r-16, r-19
[ 45] jtrue r1, 14(->59)
[ 48] less r1, r-17, r-19
[ 52] jfalse r1, 7(->59)
[ 55] less r1, r-18, r-19
[ 59] jtrue r1, 17(->76)

And now generates this bytecode (also taking advantage of the second optimization below):

[ 34] jnless r-15, r-19, 8(->42)
[ 38] jless r-16, r-19, 26(->64)
[ 42] jnless r-17, r-19, 8(->50)
[ 46] jless r-18, r-19, 18(->64)

Note the jump fusion and the fact that there's less jump
indirection - three of the four jumps go straight to the target
clause instead of indirecting through another jump.

2) Implement jless opcode to take advantage of the above, since we'll now often generate
a less followed by a jtrue where fusion is not forbidden.

• parser/Nodes.h: (JSC::ExpressionNode::hasConditionContextCodegen): Helper function to determine whether a node supports special conditional codegen. Return false as this is the default. (JSC::ExpressionNode::emitBytecodeInConditionContext): Assert not reached - only really defined for nodes that do have conditional codegen. (JSC::UnaryOpNode::expr): Add const version. (JSC::LogicalNotNode::hasConditionContextCodegen): Returne true only if subexpression supports it. (JSC::LogicalOpNode::hasConditionContextCodegen): Return true.
• parser/Nodes.cpp: (JSC::LogicalNotNode::emitBytecodeInConditionContext): Implemented - just swap the true and false targets for the child node. (JSC::LogicalOpNode::emitBytecodeInConditionContext): Implemented - handle jumps directly, improving codegen quality. Also handles further nested conditional codegen. (JSC::ConditionalNode::emitBytecode): Use condition context codegen when available. (JSC::IfNode::emitBytecode): ditto (JSC::IfElseNode::emitBytecode): ditto (JSC::DoWhileNode::emitBytecode): ditto (JSC::WhileNode::emitBytecode): ditto (JSC::ForNode::emitBytecode): ditto

• bytecode/Opcode.h:
• Added loop_if_false opcode - needed now that falsey jumps can be backwards.
• Added jless opcode to take advantage of new fusion opportunities.
• bytecode/CodeBlock.cpp: (JSC::CodeBlock::dump): Handle above.
• bytecompiler/BytecodeGenerator.cpp: (JSC::BytecodeGenerator::emitJumpIfTrue): Add peephole for less + jtrue ==> jless. (JSC::BytecodeGenerator::emitJumpIfFalse): Add handling of backwrds falsey jumps.
• bytecompiler/BytecodeGenerator.h: (JSC::BytecodeGenerator::emitNodeInConditionContext): Wrapper to handle tracking of overly deep expressions etc.
• interpreter/Interpreter.cpp: (JSC::Interpreter::privateExecute): Implement the two new opcodes (loop_if_false, jless).
• jit/JIT.cpp: (JSC::JIT::privateCompileMainPass): Implement JIT support for the two new opcodes. (JSC::JIT::privateCompileSlowCases): ditto
• jit/JIT.h:
• jit/JITArithmetic.cpp: (JSC::JIT::emit_op_jless): (JSC::JIT::emitSlow_op_jless): ditto (JSC::JIT::emitBinaryDoubleOp): ditto
• jit/JITOpcodes.cpp: (JSC::JIT::emitSlow_op_loop_if_less): ditto (JSC::JIT::emit_op_loop_if_false): ditto (JSC::JIT::emitSlow_op_loop_if_false): ditto
• jit/JITStubs.cpp:
• jit/JITStubs.h: (JSC::):

2009-12-05 Maciej Stachowiak <​[email protected]>

Reviewed by Oliver Hunt.

conway benchmark spends half it's time in op_less (jump fusion fails)
​https://bugs.webkit.org/show_bug.cgi?id=32190

• fast/js/codegen-loops-logical-nodes-expected.txt:
• fast/js/script-tests/codegen-loops-logical-nodes.js: Update to test some newly sensitive cases of codegen that were not already covered.

Location:

trunk/JavaScriptCore/parser

Files:

• Nodes.cpp (modified) (8 diffs)
• Nodes.h (modified) (5 diffs)

trunk/JavaScriptCore/parser/Nodes.cpp

@@ -812 +812 @@
 }
 
+
+// ------------------------------ LogicalNotNode -----------------------------------
+
+void LogicalNotNode::emitBytecodeInConditionContext(BytecodeGenerator& generator, Label* trueTarget, Label* falseTarget, bool fallThroughMeansTrue)
+{
+    ASSERT(expr()->hasConditionContextCodegen());
+
+    // reverse the true and false targets
+    generator.emitNodeInConditionContext(expr(), falseTarget, trueTarget, !fallThroughMeansTrue);
+}
+
+
 // ------------------------------ Binary Operation Nodes -----------------------------------
 
@@ -1018 +1030 @@
 }
 
+void LogicalOpNode::emitBytecodeInConditionContext(BytecodeGenerator& generator, Label* trueTarget, Label* falseTarget, bool fallThroughMeansTrue)
+{
+    if (m_expr1->hasConditionContextCodegen()) {
+        RefPtr<Label> afterExpr1 = generator.newLabel();
+        if (m_operator == OpLogicalAnd)
+            generator.emitNodeInConditionContext(m_expr1, afterExpr1.get(), falseTarget, true);
+        else 
+            generator.emitNodeInConditionContext(m_expr1, trueTarget, afterExpr1.get(), false);
+        generator.emitLabel(afterExpr1.get());
+    } else {
+        RegisterID* temp = generator.emitNode(m_expr1);
+        if (m_operator == OpLogicalAnd)
+            generator.emitJumpIfFalse(temp, falseTarget);
+        else
+            generator.emitJumpIfTrue(temp, trueTarget);
+    }
+
+    if (m_expr2->hasConditionContextCodegen())
+        generator.emitNodeInConditionContext(m_expr2, trueTarget, falseTarget, fallThroughMeansTrue);
+    else {
+        RegisterID* temp = generator.emitNode(m_expr2);
+        if (fallThroughMeansTrue)
+            generator.emitJumpIfFalse(temp, falseTarget);
+        else
+            generator.emitJumpIfTrue(temp, trueTarget);
+    }
+}
+
 // ------------------------------ ConditionalNode ------------------------------
 
@@ -1026 +1066 @@
     RefPtr<Label> afterElse = generator.newLabel();
 
-    RegisterID* cond = generator.emitNode(m_logical);
-    generator.emitJumpIfFalse(cond, beforeElse.get());
+    if (m_logical->hasConditionContextCodegen()) {
+        RefPtr<Label> beforeThen = generator.newLabel();
+        generator.emitNodeInConditionContext(m_logical, beforeThen.get(), beforeElse.get(), true);
+        generator.emitLabel(beforeThen.get());
+    } else {
+        RegisterID* cond = generator.emitNode(m_logical);
+        generator.emitJumpIfFalse(cond, beforeElse.get());
+    }
 
     generator.emitNode(newDst.get(), m_expr1);
@@ -1344 +1390 @@
     RefPtr<Label> afterThen = generator.newLabel();
 
-    RegisterID* cond = generator.emitNode(m_condition);
-    generator.emitJumpIfFalse(cond, afterThen.get());
+    if (m_condition->hasConditionContextCodegen()) {
+        RefPtr<Label> beforeThen = generator.newLabel();
+        generator.emitNodeInConditionContext(m_condition, beforeThen.get(), afterThen.get(), true);
+        generator.emitLabel(beforeThen.get());
+    } else {
+        RegisterID* cond = generator.emitNode(m_condition);
+        generator.emitJumpIfFalse(cond, afterThen.get());
+    }
 
     generator.emitNode(dst, m_ifBlock);
@@ -1363 +1415 @@
     RefPtr<Label> afterElse = generator.newLabel();
 
-    RegisterID* cond = generator.emitNode(m_condition);
-    generator.emitJumpIfFalse(cond, beforeElse.get());
+    if (m_condition->hasConditionContextCodegen()) {
+        RefPtr<Label> beforeThen = generator.newLabel();
+        generator.emitNodeInConditionContext(m_condition, beforeThen.get(), beforeElse.get(), true);
+        generator.emitLabel(beforeThen.get());
+    } else {
+        RegisterID* cond = generator.emitNode(m_condition);
+        generator.emitJumpIfFalse(cond, beforeElse.get());
+    }
 
     generator.emitNode(dst, m_ifBlock);
@@ -1394 +1452 @@
     generator.emitLabel(scope->continueTarget());
     generator.emitDebugHook(WillExecuteStatement, m_expr->lineNo(), m_expr->lineNo());
-    RegisterID* cond = generator.emitNode(m_expr);
-    generator.emitJumpIfTrue(cond, topOfLoop.get());
+    if (m_expr->hasConditionContextCodegen())
+        generator.emitNodeInConditionContext(m_expr, topOfLoop.get(), scope->breakTarget(), false);
+    else {
+        RegisterID* cond = generator.emitNode(m_expr);
+        generator.emitJumpIfTrue(cond, topOfLoop.get());
+    }
 
     generator.emitLabel(scope->breakTarget());
@@ -1416 +1478 @@
     generator.emitLabel(scope->continueTarget());
     generator.emitDebugHook(WillExecuteStatement, m_expr->lineNo(), m_expr->lineNo());
-    RegisterID* cond = generator.emitNode(m_expr);
-    generator.emitJumpIfTrue(cond, topOfLoop.get());
+
+    if (m_expr->hasConditionContextCodegen())
+        generator.emitNodeInConditionContext(m_expr, topOfLoop.get(), scope->breakTarget(), false);
+    else {
+        RegisterID* cond = generator.emitNode(m_expr);
+        generator.emitJumpIfTrue(cond, topOfLoop.get());
+    }
 
     generator.emitLabel(scope->breakTarget());
@@ -1451 +1518 @@
     generator.emitLabel(condition.get());
     if (m_expr2) {
-        RegisterID* cond = generator.emitNode(m_expr2);
-        generator.emitJumpIfTrue(cond, topOfLoop.get());
+        if (m_expr2->hasConditionContextCodegen())
+            generator.emitNodeInConditionContext(m_expr2, topOfLoop.get(), scope->breakTarget(), false);
+        else {
+            RegisterID* cond = generator.emitNode(m_expr2);
+            generator.emitJumpIfTrue(cond, topOfLoop.get());
+        }
     } else
         generator.emitJump(topOfLoop.get());

trunk/JavaScriptCore/parser/Nodes.h

@@ -41 +41 @@
     class BytecodeGenerator;
     class FunctionBodyNode;
+    class Label;
     class PropertyListNode;
     class ReadModifyResolveNode;
@@ -152 +153 @@
         virtual bool isSimpleArray() const { return false; }
         virtual bool isAdd() const { return false; }
+        virtual bool hasConditionContextCodegen() const { return false; }
+
+        virtual void emitBytecodeInConditionContext(BytecodeGenerator&, Label*, Label*, bool) { ASSERT_NOT_REACHED(); }
 
         virtual ExpressionNode* stripUnaryPlus() { return this; }
@@ -758 +762 @@
     protected:
         ExpressionNode* expr() { return m_expr; }
+        const ExpressionNode* expr() const { return m_expr; }
 
     private:
@@ -789 +794 @@
     public:
         LogicalNotNode(JSGlobalData*, ExpressionNode*);
+    private:
+        void emitBytecodeInConditionContext(BytecodeGenerator&, Label* trueTarget, Label* falseTarget, bool fallThroughMeansTrue);
+        virtual bool hasConditionContextCodegen() const { return expr()->hasConditionContextCodegen(); }
     };
 
@@ -953 +961 @@
     private:
         virtual RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0);
+        void emitBytecodeInConditionContext(BytecodeGenerator&, Label* trueTarget, Label* falseTarget, bool fallThroughMeansTrue);
+        virtual bool hasConditionContextCodegen() const { return true; }
 
         ExpressionNode* m_expr1;