Changeset 223318 in webkit for trunk/Source/JavaScriptCore/dfg


Ignore:
Timestamp:
Oct 14, 2017, 8:35:48 AM (8 years ago)
Author:
Yusuke Suzuki
Message:

Reland "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:

We reland this patch without DFGStrengthReduction change to see what causes
regression in the iOS bot.

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.

  1. 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/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):

Location:
trunk/Source/JavaScriptCore/dfg
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h

    r222689 r223318  
    14081408        break;
    14091409    }
    1410            
     1410
     1411    case CompareBelow:
     1412    case CompareBelowEq: {
     1413        JSValue leftConst = forNode(node->child1()).value();
     1414        JSValue rightConst = forNode(node->child2()).value();
     1415        if (leftConst && rightConst) {
     1416            if (leftConst.isInt32() && rightConst.isInt32()) {
     1417                uint32_t a = static_cast<uint32_t>(leftConst.asInt32());
     1418                uint32_t b = static_cast<uint32_t>(rightConst.asInt32());
     1419                switch (node->op()) {
     1420                case CompareBelow:
     1421                    setConstant(node, jsBoolean(a < b));
     1422                    break;
     1423                case CompareBelowEq:
     1424                    setConstant(node, jsBoolean(a <= b));
     1425                    break;
     1426                default:
     1427                    RELEASE_ASSERT_NOT_REACHED();
     1428                    break;
     1429                }
     1430                break;
     1431            }
     1432        }
     1433
     1434        if (node->child1() == node->child2()) {
     1435            switch (node->op()) {
     1436            case CompareBelow:
     1437                setConstant(node, jsBoolean(false));
     1438                break;
     1439            case CompareBelowEq:
     1440                setConstant(node, jsBoolean(true));
     1441                break;
     1442            default:
     1443                DFG_CRASH(m_graph, node, "Unexpected node type");
     1444                break;
     1445            }
     1446            break;
     1447        }
     1448        forNode(node).setType(SpecBoolean);
     1449        break;
     1450    }
     1451
    14111452    case CompareLess:
    14121453    case CompareLessEq:

  • trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp

    r223159 r223318  
    46354635        }
    46364636
     4637        case op_below: {
     4638            Node* op1 = get(VirtualRegister(currentInstruction[2].u.operand));
     4639            Node* op2 = get(VirtualRegister(currentInstruction[3].u.operand));
     4640            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(CompareBelow, op1, op2));
     4641            NEXT_OPCODE(op_below);
     4642        }
     4643
     4644        case op_beloweq: {
     4645            Node* op1 = get(VirtualRegister(currentInstruction[2].u.operand));
     4646            Node* op2 = get(VirtualRegister(currentInstruction[3].u.operand));
     4647            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(CompareBelowEq, op1, op2));
     4648            NEXT_OPCODE(op_beloweq);
     4649        }
     4650
    46374651        case op_eq: {
    46384652            Node* op1 = get(VirtualRegister(currentInstruction[2].u.operand));
    … …  
    50805094            LAST_OPCODE(op_jngreatereq);
    50815095        }
    5082            
     5096
     5097        case op_jbelow: {
     5098            unsigned relativeOffset = currentInstruction[3].u.operand;
     5099            Node* op1 = get(VirtualRegister(currentInstruction[1].u.operand));
     5100            Node* op2 = get(VirtualRegister(currentInstruction[2].u.operand));
     5101            Node* condition = addToGraph(CompareBelow, op1, op2);
     5102            addToGraph(Branch, OpInfo(branchData(m_currentIndex + relativeOffset, m_currentIndex + OPCODE_LENGTH(op_jbelow))), condition);
     5103            LAST_OPCODE(op_jbelow);
     5104        }
     5105
     5106        case op_jbeloweq: {
     5107            unsigned relativeOffset = currentInstruction[3].u.operand;
     5108            Node* op1 = get(VirtualRegister(currentInstruction[1].u.operand));
     5109            Node* op2 = get(VirtualRegister(currentInstruction[2].u.operand));
     5110            Node* condition = addToGraph(CompareBelowEq, op1, op2);
     5111            addToGraph(Branch, OpInfo(branchData(m_currentIndex + relativeOffset, m_currentIndex + OPCODE_LENGTH(op_jbeloweq))), condition);
     5112            LAST_OPCODE(op_jbeloweq);
     5113        }
     5114
    50835115        case op_switch_imm: {
    50845116            SwitchData& data = *m_graph.m_switchData.add();

  • trunk/Source/JavaScriptCore/dfg/DFGCapabilities.cpp

    r222689 r223318  
    152152    case op_greater:
    153153    case op_greatereq:
     154    case op_below:
     155    case op_beloweq:
    154156    case op_eq:
    155157    case op_eq_null:
    … …  
    193195    case op_jngreater:
    194196    case op_jngreatereq:
     197    case op_jbelow:
     198    case op_jbeloweq:
    195199    case op_loop_hint:
    196200    case op_check_traps:

  • trunk/Source/JavaScriptCore/dfg/DFGClobberize.h

    r222689 r223318  
    14871487        def(PureValue(node));
    14881488        return;
     1489
     1490    case CompareBelow:
     1491    case CompareBelowEq:
     1492        def(PureValue(node));
     1493        return;
    14891494       
    14901495    case CompareEq:

  • trunk/Source/JavaScriptCore/dfg/DFGDoesGC.cpp

    r222689 r223318  
    144144    case CompareGreater:
    145145    case CompareGreaterEq:
     146    case CompareBelow:
     147    case CompareBelowEq:
    146148    case CompareEq:
    147149    case CompareStrictEq:

  • trunk/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp

    r222689 r223318  
    143143            else {
    144144                node->setArithMode(Arith::DoOverflow);
    145                 node->clearFlags(NodeMustGenerate);
    146145                node->setResult(enableInt52() ? NodeResultInt52 : NodeResultDouble);
    147146            }
    … …  
    15951594        case GetTypedArrayByteOffset: {
    15961595            fixEdge<KnownCellUse>(node->child1());
     1596            break;
     1597        }
     1598
     1599        case CompareBelow:
     1600        case CompareBelowEq: {
     1601            fixEdge<Int32Use>(node->child1());
     1602            fixEdge<Int32Use>(node->child2());
    15971603            break;
    15981604        }

  • trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp

    r223047 r223318  
    11411141                            terminal->child1().node(), m_zero, Relationship::NotEqual, 0);
    11421142                    } else {
     1143                        // FIXME: Handle CompareBelow and CompareBelowEq.
    11431144                        Node* compare = terminal->child1().node();
    11441145                        switch (compare->op()) {

  • trunk/Source/JavaScriptCore/dfg/DFGNodeType.h

    r222689 r223318  
    122122    macro(ValueToInt32, NodeResultInt32) \
    123123    /* Used to box the result of URShift nodes (result has range 0..2^32-1). */\
    124     macro(UInt32ToNumber, NodeResultNumber | NodeMustGenerate) \
     124    macro(UInt32ToNumber, NodeResultNumber) \
    125125    /* Converts booleans to numbers but passes everything else through. */\
    126126    macro(BooleanToNumber, NodeResultJS) \
    … …  
    287287    macro(CompareGreater, NodeResultBoolean | NodeMustGenerate) \
    288288    macro(CompareGreaterEq, NodeResultBoolean | NodeMustGenerate) \
     289    macro(CompareBelow, NodeResultBoolean) \
     290    macro(CompareBelowEq, NodeResultBoolean) \
    289291    macro(CompareEq, NodeResultBoolean | NodeMustGenerate) \
    290292    macro(CompareStrictEq, NodeResultBoolean) \

  • trunk/Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp

    r222689 r223318  
    819819        case CompareGreater:
    820820        case CompareGreaterEq:
     821        case CompareBelow:
     822        case CompareBelowEq:
    821823        case CompareEq:
    822824        case CompareStrictEq:

  • trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h

    r222689 r223318  
    267267    case CompareGreater:
    268268    case CompareGreaterEq:
     269    case CompareBelow:
     270    case CompareBelowEq:
    269271    case CompareEq:
    270272    case CompareStrictEq:

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp

    r222827 r223318  
    57305730}
    57315731
     5732void SpeculativeJIT::compileCompareUnsigned(Node* node, MacroAssembler::RelationalCondition condition)
     5733{
     5734    compileInt32Compare(node, condition);
     5735}
     5736
    57325737bool SpeculativeJIT::compileStrictEq(Node* node)
    57335738{

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h

    r223047 r223318  
    27412741   
    27422742    bool compare(Node*, MacroAssembler::RelationalCondition, MacroAssembler::DoubleCondition, S_JITOperation_EJJ);
     2743    void compileCompareUnsigned(Node*, MacroAssembler::RelationalCondition);
    27432744    bool compilePeepHoleBranch(Node*, MacroAssembler::RelationalCondition, MacroAssembler::DoubleCondition, S_JITOperation_EJJ);
    27442745    void compilePeepHoleInt32Branch(Node*, Node* branchNode, JITCompiler::RelationalCondition);

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp

    r222689 r223318  
    25212521        if (compare(node, JITCompiler::GreaterThanOrEqual, JITCompiler::DoubleGreaterThanOrEqual, operationCompareGreaterEq))
    25222522            return;
     2523        break;
     2524
     2525    case CompareBelow:
     2526        compileCompareUnsigned(node, JITCompiler::Below);
     2527        break;
     2528
     2529    case CompareBelowEq:
     2530        compileCompareUnsigned(node, JITCompiler::BelowOrEqual);
    25232531        break;
    25242532

  • trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp

    r222827 r223318  
    26632663        if (compare(node, JITCompiler::GreaterThanOrEqual, JITCompiler::DoubleGreaterThanOrEqual, operationCompareGreaterEq))
    26642664            return;
     2665        break;
     2666
     2667    case CompareBelow:
     2668        compileCompareUnsigned(node, JITCompiler::Below);
     2669        break;
     2670
     2671    case CompareBelowEq:
     2672        compileCompareUnsigned(node, JITCompiler::BelowOrEqual);
    26652673        break;
    26662674

  • trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp

    r222689 r223318  
    268268                case CompareGreater:
    269269                case CompareGreaterEq:
     270                case CompareBelow:
     271                case CompareBelowEq:
    270272                case CompareEq:
    271273                case CompareStrictEq:
Note: See TracChangeset for help on using the changeset viewer.