Changeset 222518 in webkit for trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp

Timestamp:

Sep 26, 2017, 1:32:18 PM (8 years ago)

Author:

Yusuke Suzuki

Message:

Add Above/Below comparisons for UInt32 patterns
​https://bugs.webkit.org/show_bug.cgi?id=177281

Reviewed by Saam Barati.

JSTests:

• stress/uint32-comparison-jump.js: Added.

(shouldBe):
(above):
(aboveOrEqual):
(below):
(belowOrEqual):
(notAbove):
(notAboveOrEqual):
(notBelow):
(notBelowOrEqual):

• stress/uint32-comparison.js: Added.

(shouldBe):
(above):
(aboveOrEqual):
(below):
(belowOrEqual):
(aboveTest):
(aboveOrEqualTest):
(belowTest):
(belowOrEqualTest):

Source/JavaScriptCore:

Sometimes, we would like to have UInt32 operations in JS. While VM does
not support UInt32 nicely, VM supports efficient Int32 operations. As long
as signedness does not matter, we can just perform Int32 operations instead
and recognize its bit pattern as UInt32.

But of course, some operations respect signedness. The most frequently
used one is comparison. Octane/zlib performs UInt32 comparison by performing
val >>> 0. It emits op_urshift and op_unsigned. op_urshift produces
UInt32 in Int32 form. And op_unsigned will generate Double value if
the generated Int32 is < 0 (which should be UInt32).

There is a chance for optimization. The given code pattern is the following.

op_unsigned(op_urshift(@1)) lessThan:< op_unsigned(op_urshift(@2))

This can be converted to the following.

op_urshift(@1) below:< op_urshift(@2)

The above conversion is nice since

1. We can avoid op_unsigned. This could be unsignedness check in DFG. Since

this check depends on the value of Int32, dropping this check is not as easy as
removing Int32 edge filters.

2. We can perform unsigned comparison in Int32 form. We do not need to convert

them to DoubleRep.

Since the above comparison exists in Octane/zlib's *super* hot path, dropping
op_unsigned offers huge win.

At first, my patch attempts to convert the above thing in DFG pipeline.
However it poses several problems.

1. MovHint is not well removed. It makes UInt32ToNumber (which is for op_unsigned) live.
2. UInt32ToNumber could cause an OSR exit. So if we have the following nodes,

2: UInt32ToNumber(@0)
3: MovHint(@2, xxx)
4: UInt32ToNumber(@1)
5: MovHint(@1, xxx)

we could drop @5's MovHint. But @3 is difficult since @4 can exit.

So, instead, we start introducing a simple optimization in the bytecode compiler.
It performs pattern matching for op_urshift and comparison to drop op_unsigned.
We adds op_below and op_above families to bytecodes. They only accept Int32 and
perform unsigned comparison.

This offers 4% performance improvement in Octane/zlib.

baseline patched

zlib x2 431.07483+-16.28434 414.33407+-9.38375 might be 1.0404x faster

• bytecode/BytecodeDumper.cpp:

(JSC::BytecodeDumper<Block>::printCompareJump):
(JSC::BytecodeDumper<Block>::dumpBytecode):

• bytecode/BytecodeDumper.h:
• bytecode/BytecodeList.json:
• bytecode/BytecodeUseDef.h:

(JSC::computeUsesForBytecodeOffset):
(JSC::computeDefsForBytecodeOffset):

• bytecode/Opcode.h:

(JSC::isBranch):

• bytecode/PreciseJumpTargetsInlines.h:

(JSC::extractStoredJumpTargetsForBytecodeOffset):

• bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::emitJumpIfTrue):
(JSC::BytecodeGenerator::emitJumpIfFalse):

• bytecompiler/NodesCodegen.cpp:

(JSC::BinaryOpNode::emitBytecode):

• dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::parseBlock):

• dfg/DFGCapabilities.cpp:

(JSC::DFG::capabilityLevel):

• dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

• dfg/DFGDoesGC.cpp:

(JSC::DFG::doesGC):

• dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):

• dfg/DFGIntegerRangeOptimizationPhase.cpp:
• dfg/DFGNodeType.h:
• dfg/DFGPredictionPropagationPhase.cpp:
• dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

• dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compileCompareUnsigned):

• dfg/DFGSpeculativeJIT.h:
• dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGStrengthReductionPhase.cpp:

(JSC::DFG::StrengthReductionPhase::handleNode):

• dfg/DFGValidate.cpp:
• ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

• ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileCompareBelow):
(JSC::FTL::DFG::LowerDFGToB3::compileCompareBelowEq):

• jit/JIT.cpp:

(JSC::JIT::privateCompileMainPass):

• jit/JIT.h:
• jit/JITArithmetic.cpp:

(JSC::JIT::emit_op_below):
(JSC::JIT::emit_op_beloweq):
(JSC::JIT::emit_op_jbelow):
(JSC::JIT::emit_op_jbeloweq):
(JSC::JIT::emit_compareUnsignedAndJump):
(JSC::JIT::emit_compareUnsigned):

• jit/JITArithmetic32_64.cpp:

(JSC::JIT::emit_compareUnsignedAndJump):
(JSC::JIT::emit_compareUnsigned):

• llint/LowLevelInterpreter.asm:
• llint/LowLevelInterpreter32_64.asm:
• llint/LowLevelInterpreter64.asm:
• parser/Nodes.h:

(JSC::ExpressionNode::isBinaryOpNode const):

File:

• trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp

@@ -1982 +1982 @@
     OpcodeID opcodeID = this->opcodeID();
 
+    if (opcodeID == op_less || opcodeID == op_lesseq || opcodeID == op_greater || opcodeID == op_greatereq) {
+        enum class UInt32Result {
+            UInt32,
+            Constant,
+        };
+        auto isUInt32 = [&] (ExpressionNode* node) -> std::optional<UInt32Result> {
+            if (node->isBinaryOpNode() && static_cast<BinaryOpNode*>(node)->opcodeID() == op_urshift)
+                return UInt32Result::UInt32;
+            if (node->isNumber() && static_cast<NumberNode*>(node)->isIntegerNode()) {
+                int32_t value = static_cast<int32_t>(static_cast<IntegerNode*>(node)->value());
+                if (value >= 0)
+                    return UInt32Result::Constant;
+            }
+            return std::nullopt;
+        };
+        auto leftResult = isUInt32(m_expr1);
+        auto rightResult = isUInt32(m_expr2);
+        if ((leftResult && rightResult) && (leftResult.value() == UInt32Result::UInt32 || rightResult.value() == UInt32Result::UInt32)) {
+            auto* left = m_expr1;
+            auto* right = m_expr2;
+            if (left->isBinaryOpNode()) {
+                ASSERT(static_cast<BinaryOpNode*>(left)->opcodeID() == op_urshift);
+                static_cast<BinaryOpNode*>(left)->m_shouldToUnsignedResult = false;
+            }
+            if (right->isBinaryOpNode()) {
+                ASSERT(static_cast<BinaryOpNode*>(right)->opcodeID() == op_urshift);
+                static_cast<BinaryOpNode*>(right)->m_shouldToUnsignedResult = false;
+            }
+            RefPtr<RegisterID> src1 = generator.emitNodeForLeftHandSide(left, m_rightHasAssignments, right->isPure(generator));
+            RefPtr<RegisterID> src2 = generator.emitNode(right);
+            generator.emitExpressionInfo(position(), position(), position());
+
+            // Since the both sides only accept Int32, replacing operands is not observable to users.
+            bool replaceOperands = false;
+            OpcodeID resultOp = opcodeID;
+            switch (opcodeID) {
+            case op_less:
+                resultOp = op_below;
+                break;
+            case op_lesseq:
+                resultOp = op_beloweq;
+                break;
+            case op_greater:
+                resultOp = op_below;
+                replaceOperands = true;
+                break;
+            case op_greatereq:
+                resultOp = op_beloweq;
+                replaceOperands = true;
+                break;
+            default:
+                RELEASE_ASSERT_NOT_REACHED();
+            }
+            OperandTypes operandTypes(left->resultDescriptor(), right->resultDescriptor());
+            if (replaceOperands) {
+                std::swap(src1, src2);
+                operandTypes = OperandTypes(right->resultDescriptor(), left->resultDescriptor());
+            }
+            return generator.emitBinaryOp(resultOp, generator.finalDestination(dst, src1.get()), src1.get(), src2.get(), operandTypes);
+        }
+    }
+
     if (opcodeID == op_add && m_expr1->isAdd() && m_expr1->resultDescriptor().definitelyIsString()) {
         generator.emitExpressionInfo(position(), position(), position());
@@ -2017 +2079 @@
     }
     RegisterID* result = generator.emitBinaryOp(opcodeID, generator.finalDestination(dst, src1.get()), src1.get(), src2.get(), OperandTypes(left->resultDescriptor(), right->resultDescriptor()));
-    if (opcodeID == op_urshift && dst != generator.ignoredResult())
-        return generator.emitUnaryOp(op_unsigned, result, result);
+    if (m_shouldToUnsignedResult) {
+        if (opcodeID == op_urshift && dst != generator.ignoredResult())
+            return generator.emitUnaryOp(op_unsigned, result, result);
+    }
     return result;
 }