diff options
author | Andreas Kling <kling@serenityos.org> | 2021-10-24 15:34:30 +0200 |
---|---|---|
committer | Andreas Kling <kling@serenityos.org> | 2021-10-24 17:18:07 +0200 |
commit | da9821200113dc1edd59ffb5531c573e963a2ae4 (patch) | |
tree | 63f866d9bec0b42cbcba3b39f3f8c302288d9e0c /Userland/Libraries/LibJS | |
parent | 13f04e37e5005b92ea51996eff7466d9498b5684 (diff) | |
download | serenity-da9821200113dc1edd59ffb5531c573e963a2ae4.zip |
LibJS: Add a separate "identifier table" to bytecode executables
This is a specialized string table for storing identifiers only.
Identifiers are always FlyStrings, which makes many common operations
faster by allowing O(1) comparison.
Diffstat (limited to 'Userland/Libraries/LibJS')
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/ASTCodegen.cpp | 41 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Executable.cpp | 4 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Executable.h | 3 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Generator.cpp | 3 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Generator.h | 7 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/IdentifierTable.cpp | 33 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/IdentifierTable.h | 33 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Op.cpp | 16 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/Bytecode/Op.h | 17 | ||||
-rw-r--r-- | Userland/Libraries/LibJS/CMakeLists.txt | 1 |
10 files changed, 121 insertions, 37 deletions
diff --git a/Userland/Libraries/LibJS/Bytecode/ASTCodegen.cpp b/Userland/Libraries/LibJS/Bytecode/ASTCodegen.cpp index f7c47751e8..679025af80 100644 --- a/Userland/Libraries/LibJS/Bytecode/ASTCodegen.cpp +++ b/Userland/Libraries/LibJS/Bytecode/ASTCodegen.cpp @@ -30,7 +30,7 @@ void ScopeNode::generate_bytecode(Bytecode::Generator& generator) const // {Global, Block, Function, Eval}DeclarationInstantiation. for (auto& function : m_functions_hoistable_with_annexB_extension) { generator.emit<Bytecode::Op::NewFunction>(function); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(function.name())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(function.name())); } HashTable<FlyString> functions_initialized; @@ -39,7 +39,7 @@ void ScopeNode::generate_bytecode(Bytecode::Generator& generator) const return IterationDecision::Continue; generator.emit<Bytecode::Op::NewFunction>(function); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(function.name())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(function.name())); return IterationDecision::Continue; }); @@ -246,7 +246,7 @@ void RegExpLiteral::generate_bytecode(Bytecode::Generator& generator) const void Identifier::generate_bytecode(Bytecode::Generator& generator) const { - generator.emit<Bytecode::Op::GetVariable>(generator.intern_string(m_string)); + generator.emit<Bytecode::Op::GetVariable>(generator.intern_identifier(m_string)); } void AssignmentExpression::generate_bytecode(Bytecode::Generator& generator) const @@ -258,7 +258,7 @@ void AssignmentExpression::generate_bytecode(Bytecode::Generator& generator) con if (m_op == AssignmentOp::Assignment) { m_rhs->generate_bytecode(generator); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(identifier.string())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(identifier.string())); return; } @@ -345,7 +345,7 @@ void AssignmentExpression::generate_bytecode(Bytecode::Generator& generator) con TODO(); } - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(identifier.string())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(identifier.string())); if (end_block_ptr) { generator.emit<Bytecode::Op::Jump>().set_targets( @@ -372,7 +372,7 @@ void AssignmentExpression::generate_bytecode(Bytecode::Generator& generator) con generator.emit<Bytecode::Op::PutByValue>(object_reg, property_reg); } else { m_rhs->generate_bytecode(generator); - auto identifier_table_ref = generator.intern_string(verify_cast<Identifier>(expression.property()).string()); + auto identifier_table_ref = generator.intern_identifier(verify_cast<Identifier>(expression.property()).string()); generator.emit<Bytecode::Op::PutById>(object_reg, identifier_table_ref); } return; @@ -559,7 +559,7 @@ void ObjectExpression::generate_bytecode(Bytecode::Generator& generator) const if (is<StringLiteral>(property.key())) { auto& string_literal = static_cast<StringLiteral const&>(property.key()); - Bytecode::StringTableIndex key_name = generator.intern_string(string_literal.value()); + Bytecode::IdentifierTableIndex key_name = generator.intern_identifier(string_literal.value()); property.value().generate_bytecode(generator); generator.emit<Bytecode::Op::PutById>(object_reg, key_name); @@ -608,7 +608,7 @@ void MemberExpression::generate_bytecode(Bytecode::Generator& generator) const property().generate_bytecode(generator); generator.emit<Bytecode::Op::GetByValue>(object_reg); } else { - auto identifier_table_ref = generator.intern_string(verify_cast<Identifier>(property()).string()); + auto identifier_table_ref = generator.intern_identifier(verify_cast<Identifier>(property()).string()); generator.emit<Bytecode::Op::GetById>(identifier_table_ref); } } @@ -638,7 +638,7 @@ static void generate_object_binding_pattern_bytecode(Bytecode::Generator& genera VERIFY(!initializer); auto identifier = name.get<NonnullRefPtr<Identifier>>()->string(); - auto interned_identifier = generator.intern_string(identifier); + auto interned_identifier = generator.intern_identifier(identifier); generator.emit_with_extra_register_slots<Bytecode::Op::CopyObjectExcludingProperties>(excluded_property_names.size(), value_reg, excluded_property_names); generator.emit<Bytecode::Op::SetVariable>(interned_identifier); @@ -660,7 +660,7 @@ static void generate_object_binding_pattern_bytecode(Bytecode::Generator& genera } generator.emit<Bytecode::Op::Load>(value_reg); - generator.emit<Bytecode::Op::GetById>(name_index); + generator.emit<Bytecode::Op::GetById>(generator.intern_identifier(identifier)); } else { auto expression = name.get<NonnullRefPtr<Expression>>(); expression->generate_bytecode(generator); @@ -702,10 +702,11 @@ static void generate_object_binding_pattern_bytecode(Bytecode::Generator& genera TODO(); } - generator.emit<Bytecode::Op::SetVariable>(name_index); + auto& identifier = alias.get<NonnullRefPtr<Identifier>>()->string(); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(identifier)); } else { auto& identifier = alias.get<NonnullRefPtr<Identifier>>()->string(); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(identifier)); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(identifier)); } } } @@ -749,7 +750,7 @@ static void generate_array_binding_pattern_bytecode(Bytecode::Generator& generat // This element is an elision }, [&](NonnullRefPtr<Identifier> const& identifier) { - auto interned_index = generator.intern_string(identifier->string()); + auto interned_index = generator.intern_identifier(identifier->string()); generator.emit<Bytecode::Op::SetVariable>(interned_index); }, [&](NonnullRefPtr<BindingPattern> const& pattern) { @@ -881,7 +882,7 @@ void VariableDeclaration::generate_bytecode(Bytecode::Generator& generator) cons generator.emit<Bytecode::Op::LoadImmediate>(js_undefined()); declarator.target().visit( [&](NonnullRefPtr<Identifier> const& id) { - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(id->string())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(id->string())); }, [&](NonnullRefPtr<BindingPattern> const& pattern) { auto value_register = generator.allocate_register(); @@ -913,7 +914,7 @@ void CallExpression::generate_bytecode(Bytecode::Generator& generator) const // FIXME: Don't copy this logic here, make MemberExpression generate it. if (!is<Identifier>(member_expression.property())) TODO(); - auto identifier_table_ref = generator.intern_string(static_cast<Identifier const&>(member_expression.property()).string()); + auto identifier_table_ref = generator.intern_identifier(static_cast<Identifier const&>(member_expression.property()).string()); generator.emit<Bytecode::Op::GetById>(identifier_table_ref); generator.emit<Bytecode::Op::Store>(callee_reg); } @@ -1122,7 +1123,7 @@ void TaggedTemplateLiteral::generate_bytecode(Bytecode::Generator& generator) co generator.emit<Bytecode::Op::Store>(raw_strings_reg); generator.emit<Bytecode::Op::Load>(strings_reg); - generator.emit<Bytecode::Op::PutById>(raw_strings_reg, generator.intern_string("raw")); + generator.emit<Bytecode::Op::PutById>(raw_strings_reg, generator.intern_identifier("raw")); generator.emit<Bytecode::Op::LoadImmediate>(js_undefined()); auto this_reg = generator.allocate_register(); @@ -1135,7 +1136,7 @@ void UpdateExpression::generate_bytecode(Bytecode::Generator& generator) const { if (is<Identifier>(*m_argument)) { auto& identifier = static_cast<Identifier const&>(*m_argument); - generator.emit<Bytecode::Op::GetVariable>(generator.intern_string(identifier.string())); + generator.emit<Bytecode::Op::GetVariable>(generator.intern_identifier(identifier.string())); Optional<Bytecode::Register> previous_value_for_postfix_reg; if (!m_prefixed) { @@ -1148,7 +1149,7 @@ void UpdateExpression::generate_bytecode(Bytecode::Generator& generator) const else generator.emit<Bytecode::Op::Decrement>(); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(identifier.string())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(identifier.string())); if (!m_prefixed) generator.emit<Bytecode::Op::Load>(*previous_value_for_postfix_reg); @@ -1201,7 +1202,7 @@ void TryStatement::generate_bytecode(Bytecode::Generator& generator) const [&](FlyString const& parameter) { if (parameter.is_empty()) { // FIXME: We need a separate DeclarativeEnvironment here - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(parameter)); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(parameter)); } }, [&](NonnullRefPtr<BindingPattern> const&) { @@ -1295,7 +1296,7 @@ void SwitchStatement::generate_bytecode(Bytecode::Generator& generator) const void ClassDeclaration::generate_bytecode(Bytecode::Generator& generator) const { generator.emit<Bytecode::Op::NewClass>(m_class_expression); - generator.emit<Bytecode::Op::SetVariable>(generator.intern_string(m_class_expression.ptr()->name())); + generator.emit<Bytecode::Op::SetVariable>(generator.intern_identifier(m_class_expression.ptr()->name())); } void ThisExpression::generate_bytecode(Bytecode::Generator& generator) const diff --git a/Userland/Libraries/LibJS/Bytecode/Executable.cpp b/Userland/Libraries/LibJS/Bytecode/Executable.cpp index d2bd4423cc..d299edceb9 100644 --- a/Userland/Libraries/LibJS/Bytecode/Executable.cpp +++ b/Userland/Libraries/LibJS/Bytecode/Executable.cpp @@ -17,6 +17,10 @@ void Executable::dump() const outln(); string_table->dump(); } + if (!identifier_table->is_empty()) { + outln(); + identifier_table->dump(); + } } } diff --git a/Userland/Libraries/LibJS/Bytecode/Executable.h b/Userland/Libraries/LibJS/Bytecode/Executable.h index c861222d52..6f1c3f9939 100644 --- a/Userland/Libraries/LibJS/Bytecode/Executable.h +++ b/Userland/Libraries/LibJS/Bytecode/Executable.h @@ -9,6 +9,7 @@ #include <AK/FlyString.h> #include <AK/NonnullOwnPtrVector.h> #include <LibJS/Bytecode/BasicBlock.h> +#include <LibJS/Bytecode/IdentifierTable.h> #include <LibJS/Bytecode/StringTable.h> namespace JS::Bytecode { @@ -17,9 +18,11 @@ struct Executable { FlyString name; NonnullOwnPtrVector<BasicBlock> basic_blocks; NonnullOwnPtr<StringTable> string_table; + NonnullOwnPtr<IdentifierTable> identifier_table; size_t number_of_registers { 0 }; String const& get_string(StringTableIndex index) const { return string_table->get(index); } + FlyString const& get_identifier(IdentifierTableIndex index) const { return identifier_table->get(index); } void dump() const; }; diff --git a/Userland/Libraries/LibJS/Bytecode/Generator.cpp b/Userland/Libraries/LibJS/Bytecode/Generator.cpp index 7cf0718996..f6dfc923cc 100644 --- a/Userland/Libraries/LibJS/Bytecode/Generator.cpp +++ b/Userland/Libraries/LibJS/Bytecode/Generator.cpp @@ -15,6 +15,7 @@ namespace JS::Bytecode { Generator::Generator() : m_string_table(make<StringTable>()) + , m_identifier_table(make<IdentifierTable>()) { } @@ -44,7 +45,7 @@ Executable Generator::generate(ASTNode const& node, bool is_in_generator_functio generator.emit<Bytecode::Op::Yield>(nullptr); } } - return { {}, move(generator.m_root_basic_blocks), move(generator.m_string_table), generator.m_next_register }; + return { {}, move(generator.m_root_basic_blocks), move(generator.m_string_table), move(generator.m_identifier_table), generator.m_next_register }; } void Generator::grow(size_t additional_size) diff --git a/Userland/Libraries/LibJS/Bytecode/Generator.h b/Userland/Libraries/LibJS/Bytecode/Generator.h index e36702b29f..48140c9998 100644 --- a/Userland/Libraries/LibJS/Bytecode/Generator.h +++ b/Userland/Libraries/LibJS/Bytecode/Generator.h @@ -11,6 +11,7 @@ #include <AK/SinglyLinkedList.h> #include <LibJS/Bytecode/BasicBlock.h> #include <LibJS/Bytecode/Executable.h> +#include <LibJS/Bytecode/IdentifierTable.h> #include <LibJS/Bytecode/Label.h> #include <LibJS/Bytecode/Op.h> #include <LibJS/Bytecode/Register.h> @@ -102,6 +103,11 @@ public: return m_string_table->insert(move(string)); } + IdentifierTableIndex intern_identifier(FlyString string) + { + return m_identifier_table->insert(move(string)); + } + bool is_in_generator_function() const { return m_is_in_generator_function; } void enter_generator_context() { m_is_in_generator_function = true; } void leave_generator_context() { m_is_in_generator_function = false; } @@ -116,6 +122,7 @@ private: BasicBlock* m_current_basic_block { nullptr }; NonnullOwnPtrVector<BasicBlock> m_root_basic_blocks; NonnullOwnPtr<StringTable> m_string_table; + NonnullOwnPtr<IdentifierTable> m_identifier_table; u32 m_next_register { 2 }; u32 m_next_block { 1 }; diff --git a/Userland/Libraries/LibJS/Bytecode/IdentifierTable.cpp b/Userland/Libraries/LibJS/Bytecode/IdentifierTable.cpp new file mode 100644 index 0000000000..7299817438 --- /dev/null +++ b/Userland/Libraries/LibJS/Bytecode/IdentifierTable.cpp @@ -0,0 +1,33 @@ +/* + * Copyright (c) 2021, Gunnar Beutner <gbeutner@serenityos.org> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include <LibJS/Bytecode/IdentifierTable.h> + +namespace JS::Bytecode { + +IdentifierTableIndex IdentifierTable::insert(FlyString string) +{ + for (size_t i = 0; i < m_identifiers.size(); i++) { + if (m_identifiers[i] == string) + return i; + } + m_identifiers.append(move(string)); + return m_identifiers.size() - 1; +} + +FlyString const& IdentifierTable::get(IdentifierTableIndex index) const +{ + return m_identifiers[index.value()]; +} + +void IdentifierTable::dump() const +{ + outln("Identifier Table:"); + for (size_t i = 0; i < m_identifiers.size(); i++) + outln("{}: {}", i, m_identifiers[i]); +} + +} diff --git a/Userland/Libraries/LibJS/Bytecode/IdentifierTable.h b/Userland/Libraries/LibJS/Bytecode/IdentifierTable.h new file mode 100644 index 0000000000..9735f6ef59 --- /dev/null +++ b/Userland/Libraries/LibJS/Bytecode/IdentifierTable.h @@ -0,0 +1,33 @@ +/* + * Copyright (c) 2021, Andreas Kling <kling@serenityos.org> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#pragma once + +#include <AK/DistinctNumeric.h> +#include <AK/FlyString.h> +#include <AK/Vector.h> + +namespace JS::Bytecode { + +TYPEDEF_DISTINCT_NUMERIC_GENERAL(size_t, false, true, false, false, false, false, IdentifierTableIndex); + +class IdentifierTable { + AK_MAKE_NONMOVABLE(IdentifierTable); + AK_MAKE_NONCOPYABLE(IdentifierTable); + +public: + IdentifierTable() = default; + + IdentifierTableIndex insert(FlyString); + FlyString const& get(IdentifierTableIndex) const; + void dump() const; + bool is_empty() const { return m_identifiers.is_empty(); } + +private: + Vector<FlyString> m_identifiers; +}; + +} diff --git a/Userland/Libraries/LibJS/Bytecode/Op.cpp b/Userland/Libraries/LibJS/Bytecode/Op.cpp index 7082dfdef3..143cf9780f 100644 --- a/Userland/Libraries/LibJS/Bytecode/Op.cpp +++ b/Userland/Libraries/LibJS/Bytecode/Op.cpp @@ -239,7 +239,7 @@ void ConcatString::execute_impl(Bytecode::Interpreter& interpreter) const void GetVariable::execute_impl(Bytecode::Interpreter& interpreter) const { auto& vm = interpreter.vm(); - auto reference = vm.resolve_binding(interpreter.current_executable().get_string(m_identifier)); + auto reference = vm.resolve_binding(interpreter.current_executable().get_identifier(m_identifier)); if (vm.exception()) return; @@ -249,7 +249,7 @@ void GetVariable::execute_impl(Bytecode::Interpreter& interpreter) const void SetVariable::execute_impl(Bytecode::Interpreter& interpreter) const { auto& vm = interpreter.vm(); - auto reference = vm.resolve_binding(interpreter.current_executable().get_string(m_identifier)); + auto reference = vm.resolve_binding(interpreter.current_executable().get_identifier(m_identifier)); if (vm.exception()) return; @@ -262,7 +262,7 @@ void GetById::execute_impl(Bytecode::Interpreter& interpreter) const if (object_or_error.is_error()) return; auto* object = object_or_error.release_value(); - auto value_or_error = object->get(interpreter.current_executable().get_string(m_property)); + auto value_or_error = object->get(interpreter.current_executable().get_identifier(m_property)); if (value_or_error.is_error()) return; interpreter.accumulator() = value_or_error.release_value(); @@ -274,7 +274,7 @@ void PutById::execute_impl(Bytecode::Interpreter& interpreter) const if (object_or_error.is_error()) return; auto* object = object_or_error.release_value(); - MUST(object->set(interpreter.current_executable().get_string(m_property), interpreter.accumulator(), Object::ShouldThrowExceptions::Yes)); + MUST(object->set(interpreter.current_executable().get_identifier(m_property), interpreter.accumulator(), Object::ShouldThrowExceptions::Yes)); } void Jump::execute_impl(Bytecode::Interpreter& interpreter) const @@ -629,22 +629,22 @@ String ConcatString::to_string_impl(Bytecode::Executable const&) const String GetVariable::to_string_impl(Bytecode::Executable const& executable) const { - return String::formatted("GetVariable {} ({})", m_identifier, executable.string_table->get(m_identifier)); + return String::formatted("GetVariable {} ({})", m_identifier, executable.identifier_table->get(m_identifier)); } String SetVariable::to_string_impl(Bytecode::Executable const& executable) const { - return String::formatted("SetVariable {} ({})", m_identifier, executable.string_table->get(m_identifier)); + return String::formatted("SetVariable {} ({})", m_identifier, executable.identifier_table->get(m_identifier)); } String PutById::to_string_impl(Bytecode::Executable const& executable) const { - return String::formatted("PutById base:{}, property:{} ({})", m_base, m_property, executable.string_table->get(m_property)); + return String::formatted("PutById base:{}, property:{} ({})", m_base, m_property, executable.identifier_table->get(m_property)); } String GetById::to_string_impl(Bytecode::Executable const& executable) const { - return String::formatted("GetById {} ({})", m_property, executable.string_table->get(m_property)); + return String::formatted("GetById {} ({})", m_property, executable.identifier_table->get(m_property)); } String Jump::to_string_impl(Bytecode::Executable const&) const diff --git a/Userland/Libraries/LibJS/Bytecode/Op.h b/Userland/Libraries/LibJS/Bytecode/Op.h index 1a22f4ef3f..697da20715 100644 --- a/Userland/Libraries/LibJS/Bytecode/Op.h +++ b/Userland/Libraries/LibJS/Bytecode/Op.h @@ -9,6 +9,7 @@ #pragma once #include <LibCrypto/BigInt/SignedBigInteger.h> +#include <LibJS/Bytecode/IdentifierTable.h> #include <LibJS/Bytecode/Instruction.h> #include <LibJS/Bytecode/Label.h> #include <LibJS/Bytecode/Register.h> @@ -281,7 +282,7 @@ private: class SetVariable final : public Instruction { public: - explicit SetVariable(StringTableIndex identifier) + explicit SetVariable(IdentifierTableIndex identifier) : Instruction(Type::SetVariable) , m_identifier(identifier) { @@ -292,12 +293,12 @@ public: void replace_references_impl(BasicBlock const&, BasicBlock const&) { } private: - StringTableIndex m_identifier; + IdentifierTableIndex m_identifier; }; class GetVariable final : public Instruction { public: - explicit GetVariable(StringTableIndex identifier) + explicit GetVariable(IdentifierTableIndex identifier) : Instruction(Type::GetVariable) , m_identifier(identifier) { @@ -308,12 +309,12 @@ public: void replace_references_impl(BasicBlock const&, BasicBlock const&) { } private: - StringTableIndex m_identifier; + IdentifierTableIndex m_identifier; }; class GetById final : public Instruction { public: - explicit GetById(StringTableIndex property) + explicit GetById(IdentifierTableIndex property) : Instruction(Type::GetById) , m_property(property) { @@ -324,12 +325,12 @@ public: void replace_references_impl(BasicBlock const&, BasicBlock const&) { } private: - StringTableIndex m_property; + IdentifierTableIndex m_property; }; class PutById final : public Instruction { public: - explicit PutById(Register base, StringTableIndex property) + explicit PutById(Register base, IdentifierTableIndex property) : Instruction(Type::PutById) , m_base(base) , m_property(property) @@ -342,7 +343,7 @@ public: private: Register m_base; - StringTableIndex m_property; + IdentifierTableIndex m_property; }; class GetByValue final : public Instruction { diff --git a/Userland/Libraries/LibJS/CMakeLists.txt b/Userland/Libraries/LibJS/CMakeLists.txt index ecfaeb72ad..3b1c4218c2 100644 --- a/Userland/Libraries/LibJS/CMakeLists.txt +++ b/Userland/Libraries/LibJS/CMakeLists.txt @@ -4,6 +4,7 @@ set(SOURCES Bytecode/BasicBlock.cpp Bytecode/Executable.cpp Bytecode/Generator.cpp + Bytecode/IdentifierTable.cpp Bytecode/Instruction.cpp Bytecode/Interpreter.cpp Bytecode/Op.cpp |