⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 184032 in webkit


Ignore:
Timestamp:
May 8, 2015, 5:18:43 PM (11 years ago)
Author:
fpizlo@apple.com
Message:

Extend the SaneChain optimization to Contiguous arrays
​https://bugs.webkit.org/show_bug.cgi?id=144664

Reviewed by Mark Lam.

Previously if you loaded from a hole, you'd either have to take slow path for the array
load (which means C++ calls and prototype chain walks) or you'd exit (if you hadn't
gathered the necessary profiling yet). But that's unnecessary if we know that the
prototype chain is sane - i.e. has no indexed properties. Then we can just return
Undefined for the hole.

Making this change requires setting more watchpoints on the array prototype chain. But
that hit a horrible bug: ArrayPrototype still uses the static lookup tables and builds
itself up lazily. This means that this increased the number of recompilations we'd get
due to the array prototype chain being built up.

So, this change also removes the laziness and static tables from ArrayPrototype.

But to make that change, I also had to add a helper for eagerly building up a prototype
that has builtin functions.

  • CMakeLists.txt:
  • DerivedSources.make:
  • dfg/DFGArrayMode.h:
  • dfg/DFGFixupPhase.cpp:

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

  • dfg/DFGSpeculativeJIT32_64.cpp:

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

  • dfg/DFGSpeculativeJIT64.cpp:

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

  • ftl/FTLLowerDFGToLLVM.cpp:

(JSC::FTL::LowerDFGToLLVM::compileGetByVal):

  • runtime/ArrayPrototype.cpp:

(JSC::ArrayPrototype::finishCreation):
(JSC::ArrayPrototype::getOwnPropertySlot): Deleted.

  • runtime/ArrayPrototype.h:
  • runtime/JSObject.h:
Location:
trunk/Source/JavaScriptCore
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r183779 r184032  
    606606    runtime/ArrayConstructor.cpp
    607607    runtime/ArrayIteratorPrototype.cpp
    608     runtime/ArrayPrototype.cpp
    609608    runtime/BooleanPrototype.cpp
    610609    runtime/DateConstructor.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r184019 r184032  
     12015-05-08  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Extend the SaneChain optimization to Contiguous arrays
     4        https://bugs.webkit.org/show_bug.cgi?id=144664
     5
     6        Reviewed by Mark Lam.
     7       
     8        Previously if you loaded from a hole, you'd either have to take slow path for the array
     9        load (which means C++ calls and prototype chain walks) or you'd exit (if you hadn't
     10        gathered the necessary profiling yet). But that's unnecessary if we know that the
     11        prototype chain is sane - i.e. has no indexed properties. Then we can just return
     12        Undefined for the hole.
     13       
     14        Making this change requires setting more watchpoints on the array prototype chain. But
     15        that hit a horrible bug: ArrayPrototype still uses the static lookup tables and builds
     16        itself up lazily. This means that this increased the number of recompilations we'd get
     17        due to the array prototype chain being built up.
     18       
     19        So, this change also removes the laziness and static tables from ArrayPrototype.
     20       
     21        But to make that change, I also had to add a helper for eagerly building up a prototype
     22        that has builtin functions.
     23
     24        * CMakeLists.txt:
     25        * DerivedSources.make:
     26        * dfg/DFGArrayMode.h:
     27        * dfg/DFGFixupPhase.cpp:
     28        (JSC::DFG::FixupPhase::fixupNode):
     29        * dfg/DFGSpeculativeJIT32_64.cpp:
     30        (JSC::DFG::SpeculativeJIT::compile):
     31        * dfg/DFGSpeculativeJIT64.cpp:
     32        (JSC::DFG::SpeculativeJIT::compile):
     33        * ftl/FTLLowerDFGToLLVM.cpp:
     34        (JSC::FTL::LowerDFGToLLVM::compileGetByVal):
     35        * runtime/ArrayPrototype.cpp:
     36        (JSC::ArrayPrototype::finishCreation):
     37        (JSC::ArrayPrototype::getOwnPropertySlot): Deleted.
     38        * runtime/ArrayPrototype.h:
     39        * runtime/JSObject.h:
     40
    1412015-05-08  Michael Saboff  <msaboff@apple.com>
    242

  • trunk/Source/JavaScriptCore/DerivedSources.make

    r183738 r184032  
    1 # Copyright (C) 2006, 2007, 2008, 2009, 2011, 2013 Apple Inc. All rights reserved.
     1# Copyright (C) 2006, 2007, 2008, 2009, 2011, 2013, 2015 Apple Inc. All rights reserved.
    22#
    33# Redistribution and use in source and binary forms, with or without
    … …  
    3838    ArrayConstructor.lut.h \
    3939    ArrayIteratorPrototype.lut.h \
    40     ArrayPrototype.lut.h \
    4140    BooleanPrototype.lut.h \
    4241    DateConstructor.lut.h \

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

    r183708 r184032  
    9090enum Speculation {
    9191    SaneChain, // In bounds and the array prototype chain is still intact, i.e. loading a hole doesn't require special treatment.
     92   
    9293    InBounds, // In bounds and not loading a hole.
    9394    ToHole, // Potentially storing to a hole.

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

    r183963 r184032  
    539539            ArrayMode arrayMode = node->arrayMode();
    540540            switch (arrayMode.type()) {
     541            case Array::Contiguous:
    541542            case Array::Double:
    542543                if (arrayMode.arrayClass() == Array::OriginalArray
    543544                    && arrayMode.speculation() == Array::InBounds) {
    544545                    JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
    545                     if (globalObject->arrayPrototypeChainIsSane()
    546                         && !(node->flags() & NodeBytecodeUsesAsOther)) {
    547                         m_graph.watchpoints().addLazily(
    548                             globalObject->arrayPrototype()->structure()->transitionWatchpointSet());
    549                         m_graph.watchpoints().addLazily(
    550                             globalObject->objectPrototype()->structure()->transitionWatchpointSet());
    551                         node->setArrayMode(arrayMode.withSpeculation(Array::SaneChain));
     546                    if (globalObject->arrayPrototypeChainIsSane()) {
     547                        // Check if SaneChain will work on a per-type basis. Note that:
     548                        //
     549                        // 1) We don't want double arrays to sometimes return undefined, since
     550                        // that would require a change to the return type and it would pessimise
     551                        // things a lot. So, we'd only want to do that if we actually had
     552                        // evidence that we could read from a hole. That's pretty annoying.
     553                        // Likely the best way to handle that case is with an equivalent of
     554                        // SaneChain for OutOfBounds. For now we just detect when Undefined and
     555                        // NaN are indistinguishable according to backwards propagation, and just
     556                        // use SaneChain in that case. This happens to catch a lot of cases.
     557                        //
     558                        // 2) We don't want int32 array loads to have to do a hole check just to
     559                        // coerce to Undefined, since that would mean twice the checks.
     560                        //
     561                        // This has two implications. First, we have to do more checks than we'd
     562                        // like. It's unfortunate that we have to do the hole check. Second,
     563                        // some accesses that hit a hole will now need to take the full-blown
     564                        // out-of-bounds slow path. We can fix that with:
     565                        // https://bugs.webkit.org/show_bug.cgi?id=144668
     566                       
     567                        bool canDoSaneChain = false;
     568                        switch (arrayMode.type()) {
     569                        case Array::Contiguous:
     570                            // This is happens to be entirely natural. We already would have
     571                            // returned any JSValue, and now we'll return Undefined. We still do
     572                            // the check but it doesn't require taking any kind of slow path.
     573                            canDoSaneChain = true;
     574                            break;
     575                           
     576                        case Array::Double:
     577                            if (!(node->flags() & NodeBytecodeUsesAsOther)) {
     578                                // Holes look like NaN already, so if the user doesn't care
     579                                // about the difference between Undefined and NaN then we can
     580                                // do this.
     581                                canDoSaneChain = true;
     582                            }
     583                            break;
     584                           
     585                        default:
     586                            break;
     587                        }
     588                       
     589                        if (canDoSaneChain) {
     590                            m_graph.watchpoints().addLazily(
     591                                globalObject->arrayPrototype()->structure()->transitionWatchpointSet());
     592                            m_graph.watchpoints().addLazily(
     593                                globalObject->objectPrototype()->structure()->transitionWatchpointSet());
     594                            node->setArrayMode(arrayMode.withSpeculation(Array::SaneChain));
     595                        }
    552596                    }
    553597                }

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

    r183963 r184032  
    23102310                GPRTemporary resultPayload(this);
    23112311                if (node->arrayMode().type() == Array::Int32) {
     2312                    ASSERT(!node->arrayMode().isSaneChain());
     2313                   
    23122314                    speculationCheck(
    23132315                        OutOfBounds, JSValueRegs(), 0,
    23142316                        m_jit.branch32(
    23152317                            MacroAssembler::Equal,
    2316                             MacroAssembler::BaseIndex(storageReg, propertyReg, MacroAssembler::TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.tag)),
     2318                            MacroAssembler::BaseIndex(
     2319                                storageReg, propertyReg, MacroAssembler::TimesEight, TagOffset),
    23172320                            TrustedImm32(JSValue::EmptyValueTag)));
    2318                     m_jit.load32(MacroAssembler::BaseIndex(storageReg, propertyReg, MacroAssembler::TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.payload)), resultPayload.gpr());
     2321                    m_jit.load32(
     2322                        MacroAssembler::BaseIndex(
     2323                            storageReg, propertyReg, MacroAssembler::TimesEight, PayloadOffset),
     2324                        resultPayload.gpr());
    23192325                    int32Result(resultPayload.gpr(), node);
    23202326                    break;
    … …  
    23222328               
    23232329                GPRTemporary resultTag(this);
    2324                 m_jit.load32(MacroAssembler::BaseIndex(storageReg, propertyReg, MacroAssembler::TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.tag)), resultTag.gpr());
    2325                 speculationCheck(LoadFromHole, JSValueRegs(), 0, m_jit.branch32(MacroAssembler::Equal, resultTag.gpr(), TrustedImm32(JSValue::EmptyValueTag)));
    2326                 m_jit.load32(MacroAssembler::BaseIndex(storageReg, propertyReg, MacroAssembler::TimesEight, OBJECT_OFFSETOF(JSValue, u.asBits.payload)), resultPayload.gpr());
     2330                m_jit.load32(
     2331                    MacroAssembler::BaseIndex(
     2332                        storageReg, propertyReg, MacroAssembler::TimesEight, TagOffset),
     2333                    resultTag.gpr());
     2334                m_jit.load32(
     2335                    MacroAssembler::BaseIndex(
     2336                        storageReg, propertyReg, MacroAssembler::TimesEight, PayloadOffset),
     2337                    resultPayload.gpr());
     2338                if (node->arrayMode().isSaneChain()) {
     2339                    JITCompiler::Jump notHole = m_jit.branch32(
     2340                        MacroAssembler::NotEqual, resultTag.gpr(),
     2341                        TrustedImm32(JSValue::EmptyValueTag));
     2342                    m_jit.move(TrustedImm32(JSValue::UndefinedTag), resultTag.gpr());
     2343                    m_jit.move(TrustedImm32(0), resultPayload.gpr());
     2344                    notHole.link(&m_jit);
     2345                } else {
     2346                    speculationCheck(
     2347                        LoadFromHole, JSValueRegs(), 0,
     2348                        m_jit.branch32(
     2349                            MacroAssembler::Equal, resultTag.gpr(),
     2350                            TrustedImm32(JSValue::EmptyValueTag)));
     2351                }
    23272352                jsValueResult(resultTag.gpr(), resultPayload.gpr(), node);
    23282353                break;

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

    r183963 r184032  
    24482448                GPRTemporary result(this);
    24492449                m_jit.load64(MacroAssembler::BaseIndex(storageReg, propertyReg, MacroAssembler::TimesEight), result.gpr());
    2450                 speculationCheck(LoadFromHole, JSValueRegs(), 0, m_jit.branchTest64(MacroAssembler::Zero, result.gpr()));
     2450                if (node->arrayMode().isSaneChain()) {
     2451                    ASSERT(node->arrayMode().type() == Array::Contiguous);
     2452                    JITCompiler::Jump notHole = m_jit.branchTest64(
     2453                        MacroAssembler::NonZero, result.gpr());
     2454                    m_jit.move(TrustedImm64(JSValue::encode(jsUndefined())), result.gpr());
     2455                    notHole.link(&m_jit);
     2456                } else {
     2457                    speculationCheck(
     2458                        LoadFromHole, JSValueRegs(), 0,
     2459                        m_jit.branchTest64(MacroAssembler::Zero, result.gpr()));
     2460                }
    24512461                jsValueResult(result.gpr(), node, node->arrayMode().type() == Array::Int32 ? DataFormatJSInt32 : DataFormatJS);
    24522462                break;

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

    r183963 r184032  
    22642264            if (m_node->arrayMode().isInBounds()) {
    22652265                LValue result = m_out.load64(baseIndex(heap, storage, index, m_node->child2()));
    2266                 speculate(LoadFromHole, noValue(), 0, m_out.isZero64(result));
     2266                LValue isHole = m_out.isZero64(result);
     2267                if (m_node->arrayMode().isSaneChain()) {
     2268                    DFG_ASSERT(
     2269                        m_graph, m_node, m_node->arrayMode().type() == Array::Contiguous);
     2270                    result = m_out.select(
     2271                        isHole, m_out.constInt64(JSValue::encode(jsUndefined())), result);
     2272                } else
     2273                    speculate(LoadFromHole, noValue(), 0, isHole);
    22672274                setJSValue(result);
    22682275                return;

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

    r183570 r184032  
    3333#include "JIT.h"
    3434#include "JSArrayIterator.h"
     35#include "JSCBuiltins.h"
     36#include "JSCInlines.h"
    3537#include "JSStringBuilder.h"
    3638#include "JSStringJoiner.h"
    … …  
    3840#include "ObjectConstructor.h"
    3941#include "ObjectPrototype.h"
    40 #include "JSCInlines.h"
    4142#include "StringRecursionChecker.h"
    4243#include <algorithm>
    … …  
    6465EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*);
    6566
    66 }
    67 
    68 #include "ArrayPrototype.lut.h"
    69 
    70 namespace JSC {
    71 
    7267// ------------------------------ ArrayPrototype ----------------------------
    7368
    74 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
    75 
    76 /* Source for ArrayPrototype.lut.h
    77 @begin arrayPrototypeTable 16
    78   toString       arrayProtoFuncToString       DontEnum|Function 0
    79   toLocaleString arrayProtoFuncToLocaleString DontEnum|Function 0
    80   concat         arrayProtoFuncConcat         DontEnum|Function 1
    81   fill           arrayProtoFuncFill           DontEnum|Function 1
    82   join           arrayProtoFuncJoin           DontEnum|Function 1
    83   pop            arrayProtoFuncPop            DontEnum|Function 0
    84   push           arrayProtoFuncPush           DontEnum|Function 1
    85   reverse        arrayProtoFuncReverse        DontEnum|Function 0
    86   shift          arrayProtoFuncShift          DontEnum|Function 0
    87   slice          arrayProtoFuncSlice          DontEnum|Function 2
    88   sort           arrayProtoFuncSort           DontEnum|Function 1
    89   splice         arrayProtoFuncSplice         DontEnum|Function 2
    90   unshift        arrayProtoFuncUnShift        DontEnum|Function 1
    91   every          arrayProtoFuncEvery          DontEnum|Function 1
    92   forEach        arrayProtoFuncForEach        DontEnum|Function 1
    93   some           arrayProtoFuncSome           DontEnum|Function 1
    94   indexOf        arrayProtoFuncIndexOf        DontEnum|Function 1
    95   lastIndexOf    arrayProtoFuncLastIndexOf    DontEnum|Function 1
    96   filter         arrayProtoFuncFilter         DontEnum|Function 1
    97   reduce         arrayProtoFuncReduce         DontEnum|Function 1
    98   reduceRight    arrayProtoFuncReduceRight    DontEnum|Function 1
    99   map            arrayProtoFuncMap            DontEnum|Function 1
    100   entries        arrayProtoFuncEntries        DontEnum|Function 0
    101   keys           arrayProtoFuncKeys           DontEnum|Function 0
    102   find           arrayProtoFuncFind           DontEnum|Function 1
    103   findIndex      arrayProtoFuncFindIndex      DontEnum|Function 1
    104   includes       arrayProtoFuncIncludes       DontEnum|Function 1
    105 @end
    106 */
     69const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, nullptr, CREATE_METHOD_TABLE(ArrayPrototype)};
    10770
    10871ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
    … …  
    12790    putDirectWithoutTransition(vm, vm.propertyNames->values, globalObject->arrayProtoValuesFunction(), DontEnum);
    12891    putDirectWithoutTransition(vm, vm.propertyNames->iteratorSymbol, globalObject->arrayProtoValuesFunction(), DontEnum);
    129 
     92   
     93    JSC_NATIVE_FUNCTION(vm.propertyNames->toString, arrayProtoFuncToString, DontEnum, 0);
     94    JSC_NATIVE_FUNCTION(vm.propertyNames->toLocaleString, arrayProtoFuncToLocaleString, DontEnum, 0);
     95    JSC_NATIVE_FUNCTION("concat", arrayProtoFuncConcat, DontEnum, 1);
     96    JSC_BUILTIN_FUNCTION("fill", arrayPrototypeFillCodeGenerator, DontEnum);
     97    JSC_NATIVE_FUNCTION(vm.propertyNames->join, arrayProtoFuncJoin, DontEnum, 1);
     98    JSC_NATIVE_INTRINSIC_FUNCTION("pop", arrayProtoFuncPop, DontEnum, 0, ArrayPopIntrinsic);
     99    JSC_NATIVE_INTRINSIC_FUNCTION("push", arrayProtoFuncPush, DontEnum, 1, ArrayPushIntrinsic);
     100    JSC_NATIVE_FUNCTION("reverse", arrayProtoFuncReverse, DontEnum, 0);
     101    JSC_NATIVE_FUNCTION("shift", arrayProtoFuncShift, DontEnum, 0);
     102    JSC_NATIVE_FUNCTION(vm.propertyNames->slice, arrayProtoFuncSlice, DontEnum, 2);
     103    JSC_BUILTIN_FUNCTION("sort", arrayPrototypeSortCodeGenerator, DontEnum);
     104    JSC_NATIVE_FUNCTION("splice", arrayProtoFuncSplice, DontEnum, 2);
     105    JSC_NATIVE_FUNCTION("unshift", arrayProtoFuncUnShift, DontEnum, 1);
     106    JSC_BUILTIN_FUNCTION("every", arrayPrototypeEveryCodeGenerator, DontEnum);
     107    JSC_BUILTIN_FUNCTION("forEach", arrayPrototypeForEachCodeGenerator, DontEnum);
     108    JSC_BUILTIN_FUNCTION("some", arrayPrototypeSomeCodeGenerator, DontEnum);
     109    JSC_NATIVE_FUNCTION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1);
     110    JSC_NATIVE_FUNCTION("lastIndexOf", arrayProtoFuncLastIndexOf, DontEnum, 1);
     111    JSC_BUILTIN_FUNCTION("filter", arrayPrototypeFilterCodeGenerator, DontEnum);
     112    JSC_NATIVE_FUNCTION("reduce", arrayProtoFuncReduce, DontEnum, 1);
     113    JSC_NATIVE_FUNCTION("reduceRight", arrayProtoFuncReduceRight, DontEnum, 1);
     114    JSC_BUILTIN_FUNCTION("map", arrayPrototypeMapCodeGenerator, DontEnum);
     115    JSC_NATIVE_FUNCTION(vm.propertyNames->entries, arrayProtoFuncEntries, DontEnum, 0);
     116    JSC_NATIVE_FUNCTION(vm.propertyNames->keys, arrayProtoFuncKeys, DontEnum, 0);
     117    JSC_BUILTIN_FUNCTION("find", arrayPrototypeFindCodeGenerator, DontEnum);
     118    JSC_BUILTIN_FUNCTION("findIndex", arrayPrototypeFindIndexCodeGenerator, DontEnum);
     119    JSC_BUILTIN_FUNCTION("includes", arrayPrototypeIncludesCodeGenerator, DontEnum);
     120   
    130121    if (!globalObject->runtimeFlags().isSymbolDisabled()) {
    131122        JSObject* unscopables = constructEmptyObject(globalObject->globalExec(), globalObject->nullPrototypeObjectStructure());
    … …  
    143134        putDirectWithoutTransition(vm, vm.propertyNames->unscopablesSymbol, unscopables, DontEnum | ReadOnly);
    144135    }
    145 }
    146 
    147 bool ArrayPrototype::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
    148 {
    149     return getStaticFunctionSlot<JSArray>(exec, arrayPrototypeTable, jsCast<ArrayPrototype*>(object), propertyName, slot);
    150136}
    151137

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

    r182911 r184032  
    11/*
    22 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
    3  *  Copyright (C) 2007, 2011 Apple Inc. All rights reserved.
     3 *  Copyright (C) 2007, 2011, 2015 Apple Inc. All rights reserved.
    44 *
    55 *  This library is free software; you can redistribute it and/or
    … …  
    3636    static ArrayPrototype* create(VM&, JSGlobalObject*, Structure*);
    3737       
    38     static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
    39 
    4038    DECLARE_INFO;
    4139

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

    r183935 r184032  
    22 *  Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
    33 *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
    4  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2012, 2013, 2014 Apple Inc. All rights reserved.
     4 *  Copyright (C) 2003-2009, 2012-2015 Apple Inc. All rights reserved.
    55 *
    66 *  This library is free software; you can redistribute it and/or
    … …  
    15581558    JSC_NATIVE_INTRINSIC_FUNCTION(jsName, cppName, (attributes), (length), NoIntrinsic)
    15591559
     1560// Identical helpers but for builtins. Note that currently, we don't support builtins that are
     1561// also intrinsics, but we probably will do that eventually.
     1562#define JSC_BUILTIN_FUNCTION(jsName, generatorName, attributes) \
     1563    putDirectBuiltinFunction(\
     1564        vm, globalObject, makeIdentifier(vm, (jsName)), (generatorName)(vm), (attributes))
     1565
    15601566} // namespace JSC
    15611567
Note: See TracChangeset for help on using the changeset viewer.