Ignore:
Timestamp:
Dec 15, 2020, 3:18:33 PM (4 years ago)
Author:
[email protected]
Message:

Switch to using a linked list for the TDZ environment instead of a Vector
​https://bugs.webkit.org/show_bug.cgi?id=219909
<rdar://71441753>

Reviewed by Tadeu Zagallo.

Before, we'd represent the TDZ stack in terms of a Vector. While the entries
in the Vector were reference counted, the spine of the Vector itself would
match the length of the TDZ scope stack. It turns out this spine itself can
use non-trivial amounts of memory. We are seeing about a 0.5% regression from
this inside RAMification. This change makes it so that we now use a tree-like
data structure for scope stack entries. The data structure is a tree with only
parent pointers. Any field that used to be a vector of entries is now a
pointer to a node in this tree. So any pointer into this tree will have a
linked-list window into the tree, where the linked-list represents the same
data as the previous vector-as-stack data structure.

Initial testing shows this might be up to a 0.5% progression on RAMification.

  • builtins/BuiltinExecutables.cpp:

(JSC::BuiltinExecutables::createExecutable):

  • bytecode/UnlinkedFunctionExecutable.cpp:

(JSC::UnlinkedFunctionExecutable::UnlinkedFunctionExecutable):

  • bytecode/UnlinkedFunctionExecutable.h:
  • bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::BytecodeGenerator):
(JSC::BytecodeGenerator::popLexicalScopeInternal):
(JSC::BytecodeGenerator::needsTDZCheck):
(JSC::BytecodeGenerator::liftTDZCheckIfPossible):
(JSC::BytecodeGenerator::pushTDZVariables):
(JSC::BytecodeGenerator::getVariablesUnderTDZ):
(JSC::BytecodeGenerator::preserveTDZStack):
(JSC::BytecodeGenerator::restoreTDZStack):

  • bytecompiler/BytecodeGenerator.h:

(JSC::BytecodeGenerator::generate):

  • parser/VariableEnvironment.h:

(JSC::TDZEnvironmentLink::TDZEnvironmentLink):
(JSC::TDZEnvironmentLink::create):
(JSC::TDZEnvironmentLink::contains const):
(JSC::TDZEnvironmentLink::parent):

  • runtime/CachedTypes.cpp:

(JSC::CachedTDZEnvironmentLink::encode):
(JSC::CachedTDZEnvironmentLink::decode const):

  • runtime/CodeCache.cpp:

(JSC::generateUnlinkedCodeBlockImpl):
(JSC::CodeCache::getUnlinkedGlobalFunctionExecutable):

Location:
trunk/Source/JavaScriptCore/bytecompiler
Files:
2 edited

Legend:

Unmodified
Added
Removed

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

    r269939 r270870  
    290290}
    291291
    292 BytecodeGenerator::BytecodeGenerator(VM& vm, ProgramNode* programNode, UnlinkedProgramCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const CachedTDZStack& parentScopeTDZVariables, ECMAMode ecmaMode)
     292BytecodeGenerator::BytecodeGenerator(VM& vm, ProgramNode* programNode, UnlinkedProgramCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const RefPtr<TDZEnvironmentLink>& parentScopeTDZVariables, ECMAMode ecmaMode)
    293293    : BytecodeGeneratorBase(makeUnique<UnlinkedCodeBlockGenerator>(vm, codeBlock), CodeBlock::llintBaselineCalleeSaveSpaceAsVirtualRegisters())
    294294    , m_codeGenerationMode(codeGenerationMode)
    … …  
    305305    , m_ecmaMode(ecmaMode)
    306306{
    307     ASSERT_UNUSED(parentScopeTDZVariables, !parentScopeTDZVariables.size());
     307    ASSERT_UNUSED(parentScopeTDZVariables, !parentScopeTDZVariables);
    308308
    309309    m_codeBlock->setNumParameters(1); // Allocate space for "this"
    … …  
    337337}
    338338
    339 BytecodeGenerator::BytecodeGenerator(VM& vm, FunctionNode* functionNode, UnlinkedFunctionCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const CachedTDZStack& parentScopeTDZVariables, ECMAMode ecmaMode)
     339BytecodeGenerator::BytecodeGenerator(VM& vm, FunctionNode* functionNode, UnlinkedFunctionCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const RefPtr<TDZEnvironmentLink>& parentScopeTDZVariables, ECMAMode ecmaMode)
    340340    : BytecodeGeneratorBase(makeUnique<UnlinkedCodeBlockGenerator>(vm, codeBlock), CodeBlock::llintBaselineCalleeSaveSpaceAsVirtualRegisters())
    341341    , m_codeGenerationMode(codeGenerationMode)
    … …  
    364364    int symbolTableConstantIndex = 0;
    365365
    366     m_parentScopeTDZStackSize = parentScopeTDZVariables.size();
    367     m_cachedVariablesUnderTDZ = parentScopeTDZVariables;
     366    m_cachedParentTDZ = parentScopeTDZVariables;
    368367
    369368    FunctionParameters& parameters = *functionNode->parameters();
    … …  
    840839}
    841840
    842 BytecodeGenerator::BytecodeGenerator(VM& vm, EvalNode* evalNode, UnlinkedEvalCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const CachedTDZStack& parentScopeTDZVariables, ECMAMode ecmaMode)
     841BytecodeGenerator::BytecodeGenerator(VM& vm, EvalNode* evalNode, UnlinkedEvalCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const RefPtr<TDZEnvironmentLink>& parentScopeTDZVariables, ECMAMode ecmaMode)
    843842    : BytecodeGeneratorBase(makeUnique<UnlinkedCodeBlockGenerator>(vm, codeBlock), CodeBlock::llintBaselineCalleeSaveSpaceAsVirtualRegisters())
    844843    , m_codeGenerationMode(codeGenerationMode)
    … …  
    858857    m_codeBlock->setNumParameters(1);
    859858
    860     m_parentScopeTDZStackSize = parentScopeTDZVariables.size();
    861     m_cachedVariablesUnderTDZ = parentScopeTDZVariables;
     859    m_cachedParentTDZ = parentScopeTDZVariables;
    862860
    863861    emitEnter();
    … …  
    904902}
    905903
    906 BytecodeGenerator::BytecodeGenerator(VM& vm, ModuleProgramNode* moduleProgramNode, UnlinkedModuleProgramCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const CachedTDZStack& parentScopeTDZVariables, ECMAMode ecmaMode)
     904BytecodeGenerator::BytecodeGenerator(VM& vm, ModuleProgramNode* moduleProgramNode, UnlinkedModuleProgramCodeBlock* codeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const RefPtr<TDZEnvironmentLink>& parentScopeTDZVariables, ECMAMode ecmaMode)
    907905    : BytecodeGeneratorBase(makeUnique<UnlinkedCodeBlockGenerator>(vm, codeBlock), CodeBlock::llintBaselineCalleeSaveSpaceAsVirtualRegisters())
    908906    , m_codeGenerationMode(codeGenerationMode)
    … …  
    919917    , m_ecmaMode(ecmaMode)
    920918{
    921     ASSERT_UNUSED(parentScopeTDZVariables, !parentScopeTDZVariables.size());
     919    ASSERT_UNUSED(parentScopeTDZVariables, !parentScopeTDZVariables);
    922920
    923921    SymbolTable* moduleEnvironmentSymbolTable = SymbolTable::create(m_vm);
    … …  
    21692167
    21702168    m_TDZStack.removeLast();
    2171     m_cachedVariablesUnderTDZ.removeLast();
    21722169}
    21732170
    … …  
    28512848{
    28522849    for (unsigned i = m_TDZStack.size(); i--;) {
    2853         auto iter = m_TDZStack[i].find(variable.ident().impl());
    2854         if (iter == m_TDZStack[i].end())
     2850        auto iter = m_TDZStack[i].first.find(variable.ident().impl());
     2851        if (iter == m_TDZStack[i].first.end())
    28552852            continue;
    28562853        return iter->value != TDZNecessityLevel::NotNeeded;
    28572854    }
    28582855
    2859     for (unsigned i = m_parentScopeTDZStackSize; i--;) {
    2860         if (m_cachedVariablesUnderTDZ[i].environment().toTDZEnvironment().contains(variable.ident().impl()))
    2861             return true;
    2862     }
    2863 
     2856    {
     2857        TDZEnvironmentLink* environment = m_cachedParentTDZ.get();
     2858        while (environment) {
     2859            if (environment->contains(variable.ident().impl()))
     2860                return true;
     2861            environment = environment->parent();
     2862        }
     2863    }
    28642864    return false;
    28652865}
    … …  
    28822882    RefPtr<UniquedStringImpl> identifier(variable.ident().impl());
    28832883    for (unsigned i = m_TDZStack.size(); i--;) {
    2884         auto iter = m_TDZStack[i].find(identifier);
    2885         if (iter != m_TDZStack[i].end()) {
     2884        auto iter = m_TDZStack[i].first.find(identifier);
     2885        if (iter != m_TDZStack[i].first.end()) {
    28862886            if (iter->value == TDZNecessityLevel::Optimize)
    28872887                iter->value = TDZNecessityLevel::NotNeeded;
    … …  
    29092909        map.add(entry.key, entry.value.isFunction() ? TDZNecessityLevel::NotNeeded : level);
    29102910
    2911     m_TDZStack.append(WTFMove(map));
    2912     m_cachedVariablesUnderTDZ.append({ });
    2913 }
    2914 
    2915 Optional<BytecodeGenerator::CachedTDZStack> BytecodeGenerator::getVariablesUnderTDZ()
    2916 {
     2911    m_TDZStack.append(TDZStackEntry { WTFMove(map), nullptr });
     2912}
     2913
     2914RefPtr<TDZEnvironmentLink> BytecodeGenerator::getVariablesUnderTDZ()
     2915{
     2916    RefPtr<TDZEnvironmentLink> parent = m_cachedParentTDZ;
     2917    if (!m_TDZStack.size())
     2918        return parent;
     2919
    29172920    auto assertCacheIsCoherent = [&] {
    29182921#if ASSERT_ENABLED
    2919         for (size_t i = 0; i < m_cachedVariablesUnderTDZ.size(); ++i)
    2920             ASSERT(!!m_cachedVariablesUnderTDZ[i]);
     2922        TDZEnvironmentLink* parent = m_cachedParentTDZ.get();
     2923        for (auto& entry : m_TDZStack) {
     2924            ASSERT(entry.second);
     2925            ASSERT(entry.second->parent() == parent);
     2926            parent = entry.second.get();
     2927        }
    29212928#endif
    29222929    };
    29232930
    2924     RELEASE_ASSERT(m_TDZStack.size() + m_parentScopeTDZStackSize == m_cachedVariablesUnderTDZ.size());
    2925 
    2926     if (m_cachedVariablesUnderTDZ.isEmpty())
    2927         return WTF::nullopt;
    2928 
    2929     if (m_cachedVariablesUnderTDZ.last()) {
     2931    if (m_TDZStack.last().second) {
    29302932        assertCacheIsCoherent();
    2931         return m_cachedVariablesUnderTDZ;
    2932     }
    2933 
    2934     for (size_t i = m_TDZStack.size(); i--;) {
    2935         if (m_cachedVariablesUnderTDZ[i + m_parentScopeTDZStackSize])
    2936             break;
    2937 
    2938         auto& map = m_TDZStack[i];
    2939         TDZEnvironment environment;
    2940         for (auto& entry : map) {
    2941             if (entry.value != TDZNecessityLevel::NotNeeded)
    2942                 environment.add(entry.key.get());
    2943         }
    2944         m_cachedVariablesUnderTDZ[i + m_parentScopeTDZStackSize] = m_vm.m_compactVariableMap->get(environment);
     2933        return m_TDZStack.last().second;
     2934    }
     2935
     2936    for (auto& entry : m_TDZStack) {
     2937        if (!entry.second) {
     2938            auto& map = entry.first;
     2939            TDZEnvironment environment;
     2940            for (auto& entry : map) {
     2941                if (entry.value != TDZNecessityLevel::NotNeeded)
     2942                    environment.add(entry.key.get());
     2943            }
     2944            entry.second = TDZEnvironmentLink::create(m_vm.m_compactVariableMap->get(environment), parent);
     2945        }
     2946        parent = entry.second;
    29452947    }
    29462948
    29472949    assertCacheIsCoherent();
    2948     return m_cachedVariablesUnderTDZ;
     2950
     2951    return parent;
    29492952}
    29502953
    … …  
    29522955{
    29532956    preservedStack.m_preservedTDZStack = m_TDZStack;
    2954     preservedStack.m_cachedTDZStack = m_cachedVariablesUnderTDZ;
    29552957}
    29562958
    … …  
    29582960{
    29592961    m_TDZStack = preservedStack.m_preservedTDZStack;
    2960     m_cachedVariablesUnderTDZ = preservedStack.m_cachedTDZStack;
    29612962}
    29622963

  • trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h

    r269922 r270870  
    408408    public:
    409409        typedef DeclarationStacks::FunctionStack FunctionStack;
    410         using CachedTDZStack = Vector<CompactTDZEnvironmentMap::Handle>;
    411 
    412         BytecodeGenerator(VM&, ProgramNode*, UnlinkedProgramCodeBlock*, OptionSet<CodeGenerationMode>, const CachedTDZStack&, ECMAMode);
    413         BytecodeGenerator(VM&, FunctionNode*, UnlinkedFunctionCodeBlock*, OptionSet<CodeGenerationMode>, const CachedTDZStack&, ECMAMode);
    414         BytecodeGenerator(VM&, EvalNode*, UnlinkedEvalCodeBlock*, OptionSet<CodeGenerationMode>, const CachedTDZStack&, ECMAMode);
    415         BytecodeGenerator(VM&, ModuleProgramNode*, UnlinkedModuleProgramCodeBlock*, OptionSet<CodeGenerationMode>, const CachedTDZStack&, ECMAMode);
     410
     411        BytecodeGenerator(VM&, ProgramNode*, UnlinkedProgramCodeBlock*, OptionSet<CodeGenerationMode>, const RefPtr<TDZEnvironmentLink>&, ECMAMode);
     412        BytecodeGenerator(VM&, FunctionNode*, UnlinkedFunctionCodeBlock*, OptionSet<CodeGenerationMode>, const RefPtr<TDZEnvironmentLink>&, ECMAMode);
     413        BytecodeGenerator(VM&, EvalNode*, UnlinkedEvalCodeBlock*, OptionSet<CodeGenerationMode>, const RefPtr<TDZEnvironmentLink>&, ECMAMode);
     414        BytecodeGenerator(VM&, ModuleProgramNode*, UnlinkedModuleProgramCodeBlock*, OptionSet<CodeGenerationMode>, const RefPtr<TDZEnvironmentLink>&, ECMAMode);
    416415
    417416        ~BytecodeGenerator();
    … …  
    433432
    434433        template<typename Node, typename UnlinkedCodeBlock>
    435         static ParserError generate(VM& vm, Node* node, const SourceCode& sourceCode, UnlinkedCodeBlock* unlinkedCodeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const CachedTDZStack& parentScopeTDZVariables, ECMAMode ecmaMode)
     434        static ParserError generate(VM& vm, Node* node, const SourceCode& sourceCode, UnlinkedCodeBlock* unlinkedCodeBlock, OptionSet<CodeGenerationMode> codeGenerationMode, const RefPtr<TDZEnvironmentLink>& parentScopeTDZVariables, ECMAMode ecmaMode)
    436435        {
    437436            MonotonicTime before;
    … …  
    11991198        }
    12001199
    1201         Optional<CachedTDZStack> getVariablesUnderTDZ();
     1200        RefPtr<TDZEnvironmentLink> getVariablesUnderTDZ();
    12021201
    12031202        RegisterID* emitConstructVarargs(RegisterID* dst, RegisterID* func, RegisterID* thisRegister, RegisterID* arguments, RegisterID* firstFreeRegister, int32_t firstVarArgOffset, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, DebuggableCall);
    … …  
    12301229        RegisterID* emitThrowExpressionTooDeepException();
    12311230
     1231        using TDZStackEntry = std::pair<TDZMap, RefPtr<TDZEnvironmentLink>>;
     1232
    12321233        class PreservedTDZStack {
    12331234        private:
    1234             Vector<TDZMap> m_preservedTDZStack;
    1235             CachedTDZStack m_cachedTDZStack;
     1235            Vector<TDZStackEntry> m_preservedTDZStack;
    12361236            friend class BytecodeGenerator;
    12371237        };
    … …  
    12651265        Vector<LexicalScopeStackEntry> m_lexicalScopeStack;
    12661266
    1267         size_t m_parentScopeTDZStackSize { 0 };
    1268         Vector<TDZMap> m_TDZStack;
    1269         CachedTDZStack m_cachedVariablesUnderTDZ;
     1267        RefPtr<TDZEnvironmentLink> m_cachedParentTDZ;
     1268        Vector<TDZStackEntry> m_TDZStack;
    12701269        Optional<size_t> m_varScopeLexicalScopeStackIndex;
    12711270        void pushTDZVariables(const VariableEnvironment&, TDZCheckOptimization, TDZRequirement);
Note: See TracChangeset for help on using the changeset viewer.