Changeset 246041 in webkit


Ignore:
Timestamp:
Jun 3, 2019 11:42:34 AM (5 years ago)
Author:
Caio Lima
Message:

[ESNext][BigInt] Implement support for ""
​https://bugs.webkit.org/show_bug.cgi?id=190799

Reviewed by Saam Barati.

JSTests:

  • stress/big-int-exp-basic.js: Added.
  • stress/big-int-exp-jit-osr.js: Added.
  • stress/big-int-exp-jit-untyped.js: Added.
  • stress/big-int-exp-jit.js: Added.
  • stress/big-int-exp-negative-exponent.js: Added.
  • stress/big-int-exp-to-primitive.js: Added.
  • stress/big-int-exp-type-error.js: Added.
  • stress/big-int-exp-wrapped-value.js: Added.
  • stress/value-pow-ai-rule.js: Added.

Source/JavaScriptCore:

We are introducing support for BigInt into "" operator. This Patch
also includes changes into DFG, introducing a new node "ValuePow" that
is responsible to handle UntypedUse and BigIntUse.

  • dfg/DFGAbstractInterpreterInlines.h:

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

ValuePow(Untyped, Untyped) still can propagate constant if AI proves
it. We are doing so if AI proves rhs and lhs as numbers.

  • dfg/DFGByteCodeParser.cpp:

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

When compiling op_pow, we first verify if rhs and lhs can be any Int
or number. If this happen, we emit ArithPow, otherwise we fallback to
ValuePow and rely on fixup to convert it to ArithPow if possible.

  • dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

We only clobberize world if ValuePow is UntypedUse. Otherwise, we can
properly support CSE.

  • dfg/DFGDoesGC.cpp:

(JSC::DFG::doesGC):

JSBigInt::exponentiate allocates JSBigInts to perform calculation and
it can trigger GC. ValuePow(UntypedUse) can trigger GC because it can
execute user code.

  • dfg/DFGFixupPhase.cpp:

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

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

(JSC::DFG::safeToExecute):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compileValuePow):

  • 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::compileValuePow):

  • runtime/CommonSlowPaths.cpp:

(JSC::SLOW_PATH_DECL):

We are adding proper support to BigInt on op_pow. The specification
defines that we can only apply pow when both operands have the same
type after calling ToNumeric().

  • runtime/JSBigInt.cpp:

(JSC::JSBigInt::exponentiate):

  • runtime/JSBigInt.h:
Location:
trunk
Files:
9 added
22 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r245906 r246041  
     12019-06-03  Caio Lima  <ticaiolima@gmail.com>
     2
     3        [ESNext][BigInt] Implement support for "**"
     4        https://bugs.webkit.org/show_bug.cgi?id=190799
     5
     6        Reviewed by Saam Barati.
     7
     8        * stress/big-int-exp-basic.js: Added.
     9        * stress/big-int-exp-jit-osr.js: Added.
     10        * stress/big-int-exp-jit-untyped.js: Added.
     11        * stress/big-int-exp-jit.js: Added.
     12        * stress/big-int-exp-negative-exponent.js: Added.
     13        * stress/big-int-exp-to-primitive.js: Added.
     14        * stress/big-int-exp-type-error.js: Added.
     15        * stress/big-int-exp-wrapped-value.js: Added.
     16        * stress/value-pow-ai-rule.js: Added.
     17
    1182019-05-30  Tadeu Zagallo  <tzagallo@apple.com> and Yusuke Suzuki  <ysuzuki@apple.com>
    219

  • trunk/Source/JavaScriptCore/ChangeLog

    r246040 r246041  
     12019-06-03  Caio Lima  <ticaiolima@gmail.com>
     2
     3        [ESNext][BigInt] Implement support for "**"
     4        https://bugs.webkit.org/show_bug.cgi?id=190799
     5
     6        Reviewed by Saam Barati.
     7
     8        We are introducing support for BigInt into "**" operator. This Patch
     9        also includes changes into DFG, introducing a new node "ValuePow" that
     10        is responsible to handle UntypedUse and BigIntUse.
     11
     12        * dfg/DFGAbstractInterpreterInlines.h:
     13        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
     14
     15        ValuePow(Untyped, Untyped) still can propagate constant if AI proves
     16        it. We are doing so if AI proves rhs and lhs as numbers.
     17
     18        * dfg/DFGByteCodeParser.cpp:
     19        (JSC::DFG::ByteCodeParser::parseBlock):
     20
     21        When compiling op_pow, we first verify if rhs and lhs can be any Int
     22        or number. If this happen, we emit ArithPow, otherwise we fallback to
     23        ValuePow and rely on fixup to convert it to ArithPow if possible.
     24
     25        * dfg/DFGClobberize.h:
     26        (JSC::DFG::clobberize):
     27
     28        We only clobberize world if ValuePow is UntypedUse. Otherwise, we can
     29        properly support CSE.
     30
     31        * dfg/DFGDoesGC.cpp:
     32        (JSC::DFG::doesGC):
     33
     34        JSBigInt::exponentiate allocates JSBigInts to perform calculation and
     35        it can trigger GC. ValuePow(UntypedUse) can trigger GC because it can
     36        execute user code.
     37
     38        * dfg/DFGFixupPhase.cpp:
     39        (JSC::DFG::FixupPhase::fixupArithPow):
     40        (JSC::DFG::FixupPhase::fixupNode):
     41        * dfg/DFGNodeType.h:
     42        * dfg/DFGOperations.cpp:
     43        * dfg/DFGOperations.h:
     44        * dfg/DFGPredictionPropagationPhase.cpp:
     45        * dfg/DFGSafeToExecute.h:
     46        (JSC::DFG::safeToExecute):
     47        * dfg/DFGSpeculativeJIT.cpp:
     48        (JSC::DFG::SpeculativeJIT::compileValuePow):
     49        * dfg/DFGSpeculativeJIT.h:
     50        * dfg/DFGSpeculativeJIT32_64.cpp:
     51        (JSC::DFG::SpeculativeJIT::compile):
     52        * dfg/DFGSpeculativeJIT64.cpp:
     53        (JSC::DFG::SpeculativeJIT::compile):
     54        * dfg/DFGValidate.cpp:
     55        * ftl/FTLCapabilities.cpp:
     56        (JSC::FTL::canCompile):
     57        * ftl/FTLLowerDFGToB3.cpp:
     58        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
     59        (JSC::FTL::DFG::LowerDFGToB3::compileValuePow):
     60        * runtime/CommonSlowPaths.cpp:
     61        (JSC::SLOW_PATH_DECL):
     62
     63        We are adding proper support to BigInt on op_pow. The specification
     64        defines that we can only apply pow when both operands have the same
     65        type after calling ToNumeric().
     66
     67        * runtime/JSBigInt.cpp:
     68        (JSC::JSBigInt::exponentiate):
     69        * runtime/JSBigInt.h:
     70
    1712019-06-03  Yusuke Suzuki  <ysuzuki@apple.com>
    272

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

    r245063 r246041  
    903903    }
    904904       
     905    case ValuePow: {
     906        JSValue childX = forNode(node->child1()).value();
     907        JSValue childY = forNode(node->child2()).value();
     908        if (childX && childY && childX.isNumber() && childY.isNumber()) {
     909            // We need to call `didFoldClobberWorld` here because this path is only possible
     910            // when node->useKind is UntypedUse. In the case of BigIntUse, children will be
     911            // cleared by `AbstractInterpreter::executeEffects`.
     912            didFoldClobberWorld();
     913            setConstant(node, jsDoubleNumber(operationMathPow(childX.asNumber(), childY.asNumber())));
     914            break;
     915        }
     916
     917        if (node->binaryUseKind() == BigIntUse)
     918            setTypeForNode(node, SpecBigInt);
     919        else {
     920            clobberWorld();
     921            setTypeForNode(node, SpecBytecodeNumber | SpecBigInt);
     922        }
     923        break;
     924    }
     925
    905926    case ValueMul: {
    906927        if (node->binaryUseKind() == BigIntUse)

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

    r245667 r246041  
    51265126
    51275127        case op_pow: {
    5128             // FIXME: ArithPow(Untyped, Untyped) should be supported as the same to ArithMul, ArithSub etc.
    5129             // https://bugs.webkit.org/show_bug.cgi?id=160012
    51305128            auto bytecode = currentInstruction->as<OpPow>();
    51315129            Node* op1 = get(bytecode.m_lhs);
    51325130            Node* op2 = get(bytecode.m_rhs);
    5133             set(bytecode.m_dst, addToGraph(ArithPow, op1, op2));
     5131            if (op1->hasNumberOrAnyIntResult() && op2->hasNumberOrAnyIntResult())
     5132                set(bytecode.m_dst, addToGraph(ArithPow, op1, op2));
     5133            else
     5134                set(bytecode.m_dst, addToGraph(ValuePow, op1, op2));
    51345135            NEXT_OPCODE(op_pow);
    51355136        }

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

    r245063 r246041  
    682682    case ValueDiv:
    683683    case ValueMod:
     684    case ValuePow:
    684685        if (node->isBinaryUseKind(BigIntUse)) {
    685686            def(PureValue(node));

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

    r245063 r246041  
    381381    case ValueDiv:
    382382    case ValueMod:
     383    case ValuePow:
    383384    case ValueBitNot:
    384385    case ValueNegate:

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

    r245063 r246041  
    109109    }
    110110
     111    void fixupArithPow(Node* node)
     112    {
     113        if (node->child2()->shouldSpeculateInt32OrBooleanForArithmetic()) {
     114            fixDoubleOrBooleanEdge(node->child1());
     115            fixIntOrBooleanEdge(node->child2());
     116            return;
     117        }
     118
     119        fixDoubleOrBooleanEdge(node->child1());
     120        fixDoubleOrBooleanEdge(node->child2());
     121    }
     122
    111123    void fixupArithDiv(Node* node, Edge& leftChild, Edge& rightChild)
    112124    {
    … …  
    590602        }
    591603
     604        case ValuePow: {
     605            if (Node::shouldSpeculateBigInt(node->child1().node(), node->child2().node())) {
     606                fixEdge<BigIntUse>(node->child1());
     607                fixEdge<BigIntUse>(node->child2());
     608                node->clearFlags(NodeMustGenerate);
     609                break;
     610            }
     611
     612            if (Node::shouldSpeculateUntypedForArithmetic(node->child1().node(), node->child2().node())) {
     613                fixEdge<UntypedUse>(node->child1());
     614                fixEdge<UntypedUse>(node->child2());
     615                break;
     616            }
     617
     618            node->setOp(ArithPow);
     619            node->clearFlags(NodeMustGenerate);
     620            node->setResult(NodeResultDouble);
     621
     622            fixupArithPow(node);
     623            break;
     624        }
     625
    592626        case ArithPow: {
    593             if (node->child2()->shouldSpeculateInt32OrBooleanForArithmetic()) {
    594                 fixDoubleOrBooleanEdge(node->child1());
    595                 fixIntOrBooleanEdge(node->child2());
    596                 break;
    597             }
    598 
    599             fixDoubleOrBooleanEdge(node->child1());
    600             fixDoubleOrBooleanEdge(node->child2());
     627            fixupArithPow(node);
    601628            break;
    602629        }

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

    r245063 r246041  
    180180    macro(ValueMul, NodeResultJS | NodeMustGenerate) \
    181181    macro(ValueDiv, NodeResultJS | NodeMustGenerate) \
     182    macro(ValuePow, NodeResultJS | NodeMustGenerate) \
    182183    macro(ValueMod, NodeResultJS | NodeMustGenerate) \
    183184    \

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

    r245658 r246041  
    549549}
    550550
     551EncodedJSValue JIT_OPERATION operationValuePow(ExecState* exec, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2)
     552{
     553    auto bigIntOp = [] (ExecState* exec, JSBigInt* left, JSBigInt* right) -> JSBigInt* {
     554        return JSBigInt::exponentiate(exec, left, right);
     555    };
     556
     557    auto numberOp = [] (double left, double right) -> double {
     558        return operationMathPow(left, right);
     559    };
     560
     561    return binaryOp(exec, encodedOp1, encodedOp2, bigIntOp, numberOp, "Invalid mix of BigInt and other type in exponentiation operation."_s);
     562}
     563
    551564double JIT_OPERATION operationArithAbs(ExecState* exec, EncodedJSValue encodedOp1)
    552565{
    … …  
    13951408   
    13961409    return JSBigInt::divide(exec, leftOperand, rightOperand);
     1410}
     1411
     1412JSCell* JIT_OPERATION operationPowBigInt(ExecState* exec, JSCell* op1, JSCell* op2)
     1413{
     1414    VM* vm = &exec->vm();
     1415    NativeCallFrameTracer tracer(vm, exec);
     1416   
     1417    JSBigInt* leftOperand = jsCast<JSBigInt*>(op1);
     1418    JSBigInt* rightOperand = jsCast<JSBigInt*>(op2);
     1419   
     1420    return JSBigInt::exponentiate(exec, leftOperand, rightOperand);
    13971421}
    13981422

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

    r245063 r246041  
    6161EncodedJSValue JIT_OPERATION operationValueAddNotNumber(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
    6262EncodedJSValue JIT_OPERATION operationValueDiv(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
     63EncodedJSValue JIT_OPERATION operationValuePow(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
    6364double JIT_OPERATION operationArithAbs(ExecState*, EncodedJSValue encodedOp1) WTF_INTERNAL;
    6465uint32_t JIT_OPERATION operationArithClz32(ExecState*, EncodedJSValue encodedOp1) WTF_INTERNAL;
    … …  
    172173JSCell* JIT_OPERATION operationModBigInt(ExecState*, JSCell* op1, JSCell* op2) WTF_INTERNAL;
    173174JSCell* JIT_OPERATION operationDivBigInt(ExecState*, JSCell* op1, JSCell* op2) WTF_INTERNAL;
     175JSCell* JIT_OPERATION operationPowBigInt(ExecState*, JSCell* op1, JSCell* op2) WTF_INTERNAL;
    174176JSCell* JIT_OPERATION operationBitAndBigInt(ExecState*, JSCell* op1, JSCell* op2) WTF_INTERNAL;
    175177JSCell* JIT_OPERATION operationBitNotBigInt(ExecState*, JSCell* op1) WTF_INTERNAL;

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

    r245063 r246041  
    275275            }
    276276
     277            break;
     278        }
     279
     280        case ValuePow: {
     281            SpeculatedType left = node->child1()->prediction();
     282            SpeculatedType right = node->child2()->prediction();
     283
     284            if (left && right) {
     285                if (node->child1()->shouldSpeculateBigInt() && node->child2()->shouldSpeculateBigInt())         
     286                    changed |= mergePrediction(SpecBigInt);
     287                else if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
     288                    && isFullNumberOrBooleanSpeculationExpectingDefined(right))
     289                    setPrediction(SpecBytecodeDouble);
     290                else
     291                    setPrediction(SpecBytecodeDouble | SpecBigInt);
     292            }
    277293            break;
    278294        }
    … …  
    11211137        case ValueDiv:
    11221138        case ValueMod:
     1139        case ValuePow:
    11231140        case ArithAdd:
    11241141        case ArithSub:

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

    r245063 r246041  
    240240    case ValueDiv:
    241241    case ValueMod:
     242    case ValuePow:
    242243    case TryGetById:
    243244    case DeleteById:

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

    r246038 r246041  
    57975797}
    57985798
     5799void SpeculativeJIT::compileValuePow(Node* node)
     5800{
     5801    Edge& leftChild = node->child1();
     5802    Edge& rightChild = node->child2();
     5803
     5804    if (node->binaryUseKind() == BigIntUse) {
     5805        SpeculateCellOperand left(this, leftChild);
     5806        SpeculateCellOperand right(this, rightChild);
     5807        GPRReg leftGPR = left.gpr();
     5808        GPRReg rightGPR = right.gpr();
     5809
     5810        speculateBigInt(leftChild, leftGPR);
     5811        speculateBigInt(rightChild, rightGPR);
     5812
     5813        flushRegisters();
     5814        GPRFlushedCallResult result(this);
     5815        GPRReg resultGPR = result.gpr();
     5816
     5817        callOperation(operationPowBigInt, resultGPR, leftGPR, rightGPR);
     5818
     5819        m_jit.exceptionCheck();
     5820        cellResult(resultGPR, node);
     5821        return;
     5822    }
     5823
     5824    DFG_ASSERT(m_jit.graph(), node, node->binaryUseKind() == UntypedUse, node->binaryUseKind());
     5825
     5826    JSValueOperand left(this, leftChild);
     5827    JSValueOperand right(this, rightChild);
     5828    JSValueRegs leftRegs = left.jsValueRegs();
     5829    JSValueRegs rightRegs = right.jsValueRegs();
     5830
     5831    flushRegisters();
     5832    JSValueRegsFlushedCallResult result(this);
     5833    JSValueRegs resultRegs = result.regs();
     5834    callOperation(operationValuePow, resultRegs, leftRegs, rightRegs);
     5835    m_jit.exceptionCheck();
     5836
     5837    jsValueResult(resultRegs, node);
     5838}
     5839
    57995840void SpeculativeJIT::compileArithPow(Node* node)
    58005841{

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

    r245064 r246041  
    13601360    void compileArithMod(Node*);
    13611361    void compileArithPow(Node*);
     1362    void compileValuePow(Node*);
    13621363    void compileArithRounding(Node*);
    13631364    void compileArithRandom(Node*);

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

    r245063 r246041  
    20952095    case ArithMod: {
    20962096        compileArithMod(node);
     2097        break;
     2098    }
     2099
     2100    case ValuePow: {
     2101        compileValuePow(node);
    20972102        break;
    20982103    }

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

    r245064 r246041  
    22532253        break;
    22542254    }
     2255
     2256    case ValuePow:
     2257        compileValuePow(node);
     2258        break;
    22552259
    22562260    case ArithPow:

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

    r245063 r246041  
    259259                case ValueDiv:
    260260                case ValueMod:
     261                case ValuePow:
    261262                case ArithAdd:
    262263                case ArithSub:

  • trunk/Source/JavaScriptCore/ftl/FTLCapabilities.cpp

    r245063 r246041  
    100100    case ValueDiv:
    101101    case ValueMod:
     102    case ValuePow:
    102103    case StrCat:
    103104    case ArithAdd:

  • trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

    r246038 r246041  
    794794            compileArithAbs();
    795795            break;
     796        case ValuePow:
     797            compileValuePow();
     798            break;
    796799        case ArithPow:
    797800            compileArithPow();
    … …  
    27172720        LValue result = vmCall(Double, m_out.operation(DFG::arithUnaryOperation(m_node->arithUnaryType())), m_callFrame, argument);
    27182721        setDouble(result);
     2722    }
     2723
     2724    void compileValuePow()
     2725    {
     2726        if (m_node->isBinaryUseKind(BigIntUse)) {
     2727            LValue base = lowBigInt(m_node->child1());
     2728            LValue exponent = lowBigInt(m_node->child2());
     2729           
     2730            LValue result = vmCall(pointerType(), m_out.operation(operationPowBigInt), m_callFrame, base, exponent);
     2731            setJSValue(result);
     2732            return;
     2733        }
     2734
     2735        LValue base = lowJSValue(m_node->child1());
     2736        LValue exponent = lowJSValue(m_node->child2());
     2737        LValue result = vmCall(Int64, m_out.operation(operationValuePow), m_callFrame, base, exponent);
     2738        setJSValue(result);
    27192739    }
    27202740

  • trunk/Source/JavaScriptCore/runtime/CommonSlowPaths.cpp

    r245658 r246041  
    637637    BEGIN();
    638638    auto bytecode = pc->as<OpPow>();
    639     double a = GET_C(bytecode.m_lhs).jsValue().toNumber(exec);
    640     if (UNLIKELY(throwScope.exception()))
    641         RETURN(JSValue());
    642     double b = GET_C(bytecode.m_rhs).jsValue().toNumber(exec);
    643     if (UNLIKELY(throwScope.exception()))
    644         RETURN(JSValue());
     639    JSValue left = GET_C(bytecode.m_lhs).jsValue();
     640    JSValue right = GET_C(bytecode.m_rhs).jsValue();
     641    auto leftNumeric = left.toNumeric(exec);
     642    CHECK_EXCEPTION();
     643    auto rightNumeric = right.toNumeric(exec);
     644    CHECK_EXCEPTION();
     645
     646    if (WTF::holds_alternative<JSBigInt*>(leftNumeric) || WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
     647        if (WTF::holds_alternative<JSBigInt*>(leftNumeric) && WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
     648            JSBigInt* result = JSBigInt::exponentiate(exec, WTF::get<JSBigInt*>(leftNumeric), WTF::get<JSBigInt*>(rightNumeric));
     649            CHECK_EXCEPTION();
     650            RETURN(result);
     651        }
     652
     653        THROW(createTypeError(exec, "Invalid mix of BigInt and other type in exponentiation operation."));
     654    }
     655   
     656    double a = WTF::get<double>(leftNumeric);
     657    double b = WTF::get<double>(rightNumeric);
     658
    645659    RETURN(jsNumber(operationMathPow(a, b)));
    646660}

  • trunk/Source/JavaScriptCore/runtime/JSBigInt.cpp

    r243418 r246041  
    238238}
    239239
     240JSBigInt* JSBigInt::exponentiate(ExecState* exec, JSBigInt* base, JSBigInt* exponent)
     241{
     242    VM& vm = exec->vm();
     243    auto scope = DECLARE_THROW_SCOPE(vm);
     244
     245    if (exponent->sign()) {
     246        throwRangeError(exec, scope, "Negative exponent is not allowed"_s);
     247        return nullptr;
     248    }
     249
     250    // 2. If base is 0n and exponent is 0n, return 1n.
     251    if (exponent->isZero())
     252        return JSBigInt::createFrom(vm, 1);
     253   
     254    // 3. Return a BigInt representing the mathematical value of base raised
     255    //    to the power exponent.
     256    if (base->isZero())
     257        return base;
     258
     259    if (base->length() == 1 && base->digit(0) == 1) {
     260        // (-1) ** even_number == 1.
     261        if (base->sign() && !(exponent->digit(0) & 1))
     262            return JSBigInt::unaryMinus(vm, base);
     263
     264        // (-1) ** odd_number == -1; 1 ** anything == 1.
     265        return base;
     266    }
     267
     268    // For all bases >= 2, very large exponents would lead to unrepresentable
     269    // results.
     270    static_assert(maxLengthBits < std::numeric_limits<Digit>::max(), "maxLengthBits needs to be less than digit::max()");
     271    if (exponent->length() > 1) {
     272        throwRangeError(exec, scope, "BigInt generated from this operation is too big"_s);
     273        return nullptr;
     274    }
     275
     276    Digit expValue = exponent->digit(0);
     277    if (expValue == 1)
     278        return base;
     279    if (expValue >= maxLengthBits) {
     280        throwRangeError(exec, scope, "BigInt generated from this operation is too big"_s);
     281        return nullptr;
     282    }
     283
     284    static_assert(maxLengthBits <= maxInt, "maxLengthBits needs to be <= maxInt");
     285    int n = static_cast<int>(expValue);
     286    if (base->length() == 1 && base->digit(0) == 2) {
     287        // Fast path for 2^n.
     288        int neededDigits = 1 + (n / digitBits);
     289        JSBigInt* result = JSBigInt::tryCreateWithLength(exec, neededDigits);
     290        RETURN_IF_EXCEPTION(scope, nullptr);
     291
     292        result->initialize(InitializationType::WithZero);
     293        // All bits are zero. Now set the n-th bit.
     294        Digit msd = static_cast<Digit>(1) << (n % digitBits);
     295        result->setDigit(neededDigits - 1, msd);
     296        // Result is negative for odd powers of -2n.
     297        if (base->sign())
     298            result->setSign(static_cast<bool>(n & 1));
     299
     300        return result;
     301    }
     302
     303    JSBigInt* result = nullptr;
     304    JSBigInt* runningSquare = base;
     305
     306    // This implicitly sets the result's sign correctly.
     307    if (n & 1)
     308        result = base;
     309
     310    n >>= 1;
     311    for (; n; n >>= 1) {
     312        JSBigInt* maybeResult = JSBigInt::multiply(exec, runningSquare, runningSquare);
     313        RETURN_IF_EXCEPTION(scope, nullptr);
     314        runningSquare = maybeResult;
     315        if (n & 1) {
     316            if (!result)
     317                result = runningSquare;
     318            else {
     319                maybeResult = JSBigInt::multiply(exec, result, runningSquare);
     320                RETURN_IF_EXCEPTION(scope, nullptr);
     321                result = maybeResult;
     322            }
     323        }
     324    }
     325
     326    return result;
     327}
     328
    240329JSBigInt* JSBigInt::multiply(ExecState* exec, JSBigInt* x, JSBigInt* y)
    241330{
    … …  
    10561145}
    10571146
    1058 // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
     1147// Returns whether (factor1 * factor2) > (high << digitBits) + low.
    10591148inline bool JSBigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low)
    10601149{

  • trunk/Source/JavaScriptCore/runtime/JSBigInt.h

    r242715 r246041  
    112112    inline bool toBoolean() const { return !isZero(); }
    113113
     114    static JSBigInt* exponentiate(ExecState*, JSBigInt* base, JSBigInt* exponent);
     115
    114116    static JSBigInt* multiply(ExecState*, JSBigInt* x, JSBigInt* y);
    115117   
Note: See TracChangeset for help on using the changeset viewer.