Ignore:
Timestamp:
Apr 23, 2013, 3:18:18 PM (12 years ago)
Author:
[email protected]
Message:

Source/JavaScriptCore: Filled out more cases of branch folding in bytecode when emitting
expressions into a branching context
​https://bugs.webkit.org/show_bug.cgi?id=115057

Reviewed by Filip Pizlo.

This covers a few cases like:

  • while (true) { }
  • while (1) { }
  • if (x) break;
  • if (x) continue;
  • if (boolean_expr == boolean_const) { }
  • if (boolean_expr == 1_or_0) { }
  • if (bitop == 1_or_0) { }

This also works, but will bring shame on your family:

  • while ("hello world") { }

No change on the benchmarks we track, but a 2.5X speedup on a microbenchmark
that uses these techniques.

  • bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::emitNewArray):
(JSC::BytecodeGenerator::emitThrowReferenceError):
(JSC::BytecodeGenerator::emitReadOnlyExceptionIfNeeded):

  • bytecompiler/BytecodeGenerator.h:

(JSC::BytecodeGenerator::shouldEmitDebugHooks): Updated ancillary code
for interface simplifications.

  • bytecompiler/NodesCodegen.cpp:

(JSC::ConstantNode::emitBytecodeInConditionContext): Constants can
jump unconditionally when used within a condition context.

(JSC::ConstantNode::emitBytecode):
(JSC::StringNode::jsValue): Gave constants a common base class so I
could implement their codegen just once.

(JSC::BinaryOpNode::emitBytecodeInConditionContext):
(JSC::canFoldToBranch):
(JSC::BinaryOpNode::tryFoldToBranch): Fold (!/=)= and (!/=)== where
appropriate. A lot of cases are not appropriate because of the surprising
type conversion semantics of ==. For example, if (number == true) { } is
not the same as if (number) { } because the former will up-convert true
to number and then do numeric comparison.

(JSC::singleStatement):
(JSC::IfElseNode::tryFoldBreakAndContinue):
(JSC::IfElseNode::emitBytecode):
(JSC::ContinueNode::trivialTarget):
(JSC::BreakNode::trivialTarget): Fold "if (expression) break" and
"if (expression) continue" into direct jumps from expression.

  • parser/ASTBuilder.h:

(ASTBuilder):
(JSC::ASTBuilder::createIfStatement):

  • parser/NodeConstructors.h:

(JSC::ConstantNode::ConstantNode):
(JSC):
(JSC::NullNode::NullNode):
(JSC::BooleanNode::BooleanNode):
(JSC::NumberNode::NumberNode):
(JSC::StringNode::StringNode):
(JSC::IfElseNode::IfElseNode):

  • parser/Nodes.h:

(JSC::ExpressionNode::isConstant):
(JSC::ExpressionNode::isBoolean):
(JSC::StatementNode::isBreak):
(JSC::StatementNode::isContinue):
(ConstantNode):
(JSC::ConstantNode::isPure):
(JSC::ConstantNode::isConstant):
(NullNode):
(JSC::NullNode::jsValue):
(JSC::BooleanNode::value):
(JSC::BooleanNode::isBoolean):
(JSC::BooleanNode::jsValue):
(JSC::NumberNode::value):
(NumberNode):
(JSC::NumberNode::jsValue):
(StringNode):
(BinaryOpNode):
(IfElseNode):
(ContinueNode):
(JSC::ContinueNode::isContinue):
(BreakNode):
(JSC::BreakNode::isBreak):

  • parser/Parser.cpp:

(JSC::::parseIfStatement):

  • parser/ResultType.h:

(JSC::ResultType::definitelyIsBoolean):
(ResultType):

  • runtime/JSCJSValueInlines.h:

(JSC::JSValue::pureToBoolean):

  • runtime/JSCell.h:
  • runtime/JSCellInlines.h:

(JSC::JSCell::pureToBoolean): Updated for interface changes above.

Source/WTF: Filled out more cases of branch folding in bytecode when emitting expressions into a branching context
​https://bugs.webkit.org/show_bug.cgi?id=115057

Reviewed by Filip Pizlo.

Added a helper constructor for TriState so clients can make one without
branching or making assumptions about the integer values of TriStates.

  • wtf/TriState.h:

(WTF::triState):
(WTF):

LayoutTests: Filled out more cases of branch folding in bytecode when emitting expressions into a branching context
​https://bugs.webkit.org/show_bug.cgi?id=115057

Reviewed by Filip Pizlo.

Added a performance test for interesting branch types.

  • fast/js/regress/branch-fold-expected.txt: Added.
  • fast/js/regress/branch-fold.html: Added.
  • fast/js/regress/script-tests/branch-fold.js: Added.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp

    r148696 r148999  
    9393}
    9494
    95 // ------------------------------ NullNode -------------------------------------
    96 
    97 RegisterID* NullNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
     95// ------------------------------ ConstantNode ----------------------------------
     96
     97void ConstantNode::emitBytecodeInConditionContext(BytecodeGenerator& generator, Label* trueTarget, Label* falseTarget, FallThroughMode fallThroughMode)
     98{
     99    TriState value = jsValue(generator).pureToBoolean();
     100    if (value == MixedTriState)
     101        ExpressionNode::emitBytecodeInConditionContext(generator, trueTarget, falseTarget, fallThroughMode);
     102    else if (value == TrueTriState && fallThroughMode == FallThroughMeansFalse)
     103        generator.emitJump(trueTarget);
     104    else if (value == FalseTriState && fallThroughMode == FallThroughMeansTrue)
     105        generator.emitJump(falseTarget);
     106
     107    // All other cases are unconditional fall-throughs, like "if (true)".
     108}
     109
     110RegisterID* ConstantNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    98111{
    99112    if (dst == generator.ignoredResult())
    100113        return 0;
    101     return generator.emitLoad(dst, jsNull());
    102 }
    103 
    104 // ------------------------------ BooleanNode ----------------------------------
    105 
    106 RegisterID* BooleanNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    107 {
    108     if (dst == generator.ignoredResult())
    109         return 0;
    110     return generator.emitLoad(dst, m_value);
    111 }
    112 
    113 // ------------------------------ NumberNode -----------------------------------
    114 
    115 RegisterID* NumberNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    116 {
    117     if (dst == generator.ignoredResult())
    118         return 0;
    119     return generator.emitLoad(dst, m_value);
    120 }
    121 
    122 // ------------------------------ StringNode -----------------------------------
    123 
    124 RegisterID* StringNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    125 {
    126     if (dst == generator.ignoredResult())
    127         return 0;
    128     return generator.emitLoad(dst, m_value);
     114    return generator.emitLoad(dst, jsValue(generator));
     115}
     116
     117JSValue StringNode::jsValue(BytecodeGenerator& generator) const
     118{
     119    return generator.addStringConstant(m_value);
    129120}
    130121
    … …  
    10431034}
    10441035
     1036void BinaryOpNode::emitBytecodeInConditionContext(BytecodeGenerator& generator, Label* trueTarget, Label* falseTarget, FallThroughMode fallThroughMode)
     1037{
     1038    TriState branchCondition;
     1039    ExpressionNode* branchExpression;
     1040    tryFoldToBranch(generator, branchCondition, branchExpression);
     1041
     1042    if (branchCondition == MixedTriState)
     1043        ExpressionNode::emitBytecodeInConditionContext(generator, trueTarget, falseTarget, fallThroughMode);
     1044    else if (branchCondition == TrueTriState)
     1045        generator.emitNodeInConditionContext(branchExpression, trueTarget, falseTarget, fallThroughMode);
     1046    else
     1047        generator.emitNodeInConditionContext(branchExpression, falseTarget, trueTarget, invert(fallThroughMode));
     1048}
     1049
     1050static inline bool canFoldToBranch(OpcodeID opcodeID, ExpressionNode* branchExpression, JSValue constant)
     1051{
     1052    ResultType expressionType = branchExpression->resultDescriptor();
     1053
     1054    if (expressionType.definitelyIsBoolean() && constant.isBoolean())
     1055        return true;
     1056    else if (expressionType.isInt32() && constant.isInt32() && (constant.asInt32() == 0 || constant.asInt32() == 1))
     1057        return true;
     1058    else if (expressionType.definitelyIsBoolean() && constant.isInt32() && (constant.asInt32() == 0 || constant.asInt32() == 1))
     1059        return opcodeID == op_eq || opcodeID == op_neq; // Strict equality is false in the case of type mismatch, so we can't fold to a branch based on truthiness.
     1060
     1061    return false;
     1062}
     1063
     1064void BinaryOpNode::tryFoldToBranch(BytecodeGenerator& generator, TriState& branchCondition, ExpressionNode*& branchExpression)
     1065{
     1066    branchCondition = MixedTriState;
     1067    branchExpression = 0;
     1068
     1069    ConstantNode* constant = 0;
     1070    if (m_expr1->isConstant()) {
     1071        constant = static_cast<ConstantNode*>(m_expr1);
     1072        branchExpression = m_expr2;
     1073    } else if (m_expr2->isConstant()) {
     1074        constant = static_cast<ConstantNode*>(m_expr2);
     1075        branchExpression = m_expr1;
     1076    }
     1077
     1078    if (!constant)
     1079        return;
     1080    ASSERT(branchExpression);
     1081
     1082    OpcodeID opcodeID = this->opcodeID();
     1083    JSValue value = constant->jsValue(generator);
     1084    bool canFoldToBranch = JSC::canFoldToBranch(opcodeID, branchExpression, value);
     1085    if (!canFoldToBranch)
     1086        return;
     1087
     1088    if (opcodeID == op_eq || opcodeID == op_stricteq)
     1089        branchCondition = triState(value.pureToBoolean());
     1090    else if (opcodeID == op_neq || opcodeID == op_nstricteq)
     1091        branchCondition = triState(!value.pureToBoolean());
     1092}
     1093
    10451094RegisterID* BinaryOpNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    10461095{
    … …  
    15051554}
    15061555
    1507 // ------------------------------ IfNode ---------------------------------------
    1508 
    1509 void IfNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
     1556// ------------------------------ IfElseNode ---------------------------------------
     1557
     1558static inline StatementNode* singleStatement(StatementNode* statementNode)
     1559{
     1560    if (statementNode->isBlock())
     1561        return static_cast<BlockNode*>(statementNode)->singleStatement();
     1562    return statementNode;
     1563}
     1564
     1565bool IfElseNode::tryFoldBreakAndContinue(BytecodeGenerator& generator, StatementNode* ifBlock,
     1566    Label*& trueTarget, FallThroughMode& fallThroughMode)
     1567{
     1568    StatementNode* singleStatement = JSC::singleStatement(ifBlock);
     1569    if (!singleStatement)
     1570        return false;
     1571
     1572    if (singleStatement->isBreak()) {
     1573        BreakNode* breakNode = static_cast<BreakNode*>(singleStatement);
     1574        Label* target = breakNode->trivialTarget(generator);
     1575        if (!target)
     1576            return false;
     1577        trueTarget = target;
     1578        fallThroughMode = FallThroughMeansFalse;
     1579        return true;
     1580    }
     1581
     1582    if (singleStatement->isContinue()) {
     1583        ContinueNode* continueNode = static_cast<ContinueNode*>(singleStatement);
     1584        Label* target = continueNode->trivialTarget(generator);
     1585        if (!target)
     1586            return false;
     1587        trueTarget = target;
     1588        fallThroughMode = FallThroughMeansFalse;
     1589        return true;
     1590    }
     1591
     1592    return false;
     1593}
     1594
     1595void IfElseNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    15101596{
    15111597    generator.emitDebugHook(WillExecuteStatement, firstLine(), lastLine(), charPosition());
    15121598   
    1513     RefPtr<Label> afterThen = generator.newLabel();
    1514 
    15151599    RefPtr<Label> beforeThen = generator.newLabel();
    1516     generator.emitNodeInConditionContext(m_condition, beforeThen.get(), afterThen.get(), FallThroughMeansTrue);
    1517     generator.emitLabel(beforeThen.get());
    1518 
    1519     generator.emitNode(dst, m_ifBlock);
    1520     generator.emitLabel(afterThen.get());
    1521 }
    1522 
    1523 // ------------------------------ IfElseNode ---------------------------------------
    1524 
    1525 void IfElseNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    1526 {
    1527     generator.emitDebugHook(WillExecuteStatement, firstLine(), lastLine(), charPosition());
    1528    
    15291600    RefPtr<Label> beforeElse = generator.newLabel();
    15301601    RefPtr<Label> afterElse = generator.newLabel();
    15311602
    1532     RefPtr<Label> beforeThen = generator.newLabel();
    1533     generator.emitNodeInConditionContext(m_condition, beforeThen.get(), beforeElse.get(), FallThroughMeansTrue);
     1603    Label* trueTarget = beforeThen.get();
     1604    Label* falseTarget = beforeElse.get();
     1605    FallThroughMode fallThroughMode = FallThroughMeansTrue;
     1606    bool didFoldIfBlock = tryFoldBreakAndContinue(generator, m_ifBlock, trueTarget, fallThroughMode);
     1607
     1608    generator.emitNodeInConditionContext(m_condition, trueTarget, falseTarget, fallThroughMode);
    15341609    generator.emitLabel(beforeThen.get());
    15351610
    1536     generator.emitNode(dst, m_ifBlock);
    1537     generator.emitJump(afterElse.get());
     1611    if (!didFoldIfBlock) {
     1612        generator.emitNode(dst, m_ifBlock);
     1613        if (m_elseBlock)
     1614            generator.emitJump(afterElse.get());
     1615    }
    15381616
    15391617    generator.emitLabel(beforeElse.get());
    15401618
    1541     generator.emitNode(dst, m_elseBlock);
     1619    if (m_elseBlock)
     1620        generator.emitNode(dst, m_elseBlock);
    15421621
    15431622    generator.emitLabel(afterElse.get());
    … …  
    17011780// ------------------------------ ContinueNode ---------------------------------
    17021781
     1782Label* ContinueNode::trivialTarget(BytecodeGenerator& generator)
     1783{
     1784    if (generator.shouldEmitDebugHooks())
     1785        return 0;
     1786
     1787    LabelScope* scope = generator.continueTarget(m_ident);
     1788    ASSERT(scope);
     1789
     1790    if (generator.scopeDepth() != scope->scopeDepth())
     1791        return 0;
     1792
     1793    return scope->continueTarget();
     1794}
     1795
    17031796void ContinueNode::emitBytecode(BytecodeGenerator& generator, RegisterID*)
    17041797{
    … …  
    17131806
    17141807// ------------------------------ BreakNode ------------------------------------
     1808
     1809Label* BreakNode::trivialTarget(BytecodeGenerator& generator)
     1810{
     1811    if (generator.shouldEmitDebugHooks())
     1812        return 0;
     1813
     1814    LabelScope* scope = generator.breakTarget(m_ident);
     1815    ASSERT(scope);
     1816
     1817    if (generator.scopeDepth() != scope->scopeDepth())
     1818        return 0;
     1819
     1820    return scope->breakTarget();
     1821}
    17151822
    17161823void BreakNode::emitBytecode(BytecodeGenerator& generator, RegisterID*)
Note: See TracChangeset for help on using the changeset viewer.