Generator.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323
  1. /*
  2. * Copyright (c) 2021-2024, Andreas Kling <kling@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/OwnPtr.h>
  8. #include <AK/SinglyLinkedList.h>
  9. #include <LibJS/AST.h>
  10. #include <LibJS/Bytecode/BasicBlock.h>
  11. #include <LibJS/Bytecode/CodeGenerationError.h>
  12. #include <LibJS/Bytecode/Executable.h>
  13. #include <LibJS/Bytecode/IdentifierTable.h>
  14. #include <LibJS/Bytecode/Label.h>
  15. #include <LibJS/Bytecode/Op.h>
  16. #include <LibJS/Bytecode/Register.h>
  17. #include <LibJS/Bytecode/StringTable.h>
  18. #include <LibJS/Forward.h>
  19. #include <LibJS/Runtime/FunctionKind.h>
  20. #include <LibRegex/Regex.h>
  21. namespace JS::Bytecode {
  22. class Generator {
  23. public:
  24. VM& vm() { return m_vm; }
  25. enum class SurroundingScopeKind {
  26. Global,
  27. Function,
  28. Block,
  29. };
  30. static CodeGenerationErrorOr<NonnullGCPtr<Executable>> generate(VM&, ASTNode const&, ReadonlySpan<FunctionParameter> parameters, FunctionKind = FunctionKind::Normal);
  31. Register allocate_register();
  32. void set_local_initialized(u32 local_index);
  33. [[nodiscard]] bool is_local_initialized(u32 local_index) const;
  34. class SourceLocationScope {
  35. public:
  36. SourceLocationScope(Generator&, ASTNode const& node);
  37. ~SourceLocationScope();
  38. private:
  39. Generator& m_generator;
  40. ASTNode const* m_previous_node { nullptr };
  41. };
  42. class UnwindContext {
  43. public:
  44. UnwindContext(Generator&, Optional<Label> finalizer);
  45. UnwindContext const* previous() const { return m_previous_context; }
  46. void set_handler(Label handler) { m_handler = handler; }
  47. Optional<Label> handler() const { return m_handler; }
  48. Optional<Label> finalizer() const { return m_finalizer; }
  49. ~UnwindContext();
  50. private:
  51. Generator& m_generator;
  52. Optional<Label> m_finalizer;
  53. Optional<Label> m_handler {};
  54. UnwindContext const* m_previous_context { nullptr };
  55. };
  56. template<typename OpType, typename... Args>
  57. void emit(Args&&... args)
  58. {
  59. VERIFY(!is_current_block_terminated());
  60. size_t slot_offset = m_current_basic_block->size();
  61. grow(sizeof(OpType));
  62. void* slot = m_current_basic_block->data() + slot_offset;
  63. new (slot) OpType(forward<Args>(args)...);
  64. if constexpr (OpType::IsTerminator)
  65. m_current_basic_block->terminate({});
  66. auto* op = static_cast<OpType*>(slot);
  67. op->set_source_record({ m_current_ast_node->start_offset(), m_current_ast_node->end_offset() });
  68. }
  69. template<typename OpType, typename ExtraSlotType, typename... Args>
  70. void emit_with_extra_slots(size_t extra_slot_count, Args&&... args)
  71. {
  72. VERIFY(!is_current_block_terminated());
  73. size_t size_to_allocate = round_up_to_power_of_two(sizeof(OpType) + extra_slot_count * sizeof(ExtraSlotType), alignof(void*));
  74. size_t slot_offset = m_current_basic_block->size();
  75. grow(size_to_allocate);
  76. void* slot = m_current_basic_block->data() + slot_offset;
  77. new (slot) OpType(forward<Args>(args)...);
  78. if constexpr (OpType::IsTerminator)
  79. m_current_basic_block->terminate({});
  80. auto* op = static_cast<OpType*>(slot);
  81. op->set_source_record({ m_current_ast_node->start_offset(), m_current_ast_node->end_offset() });
  82. }
  83. template<typename OpType, typename... Args>
  84. void emit_with_extra_operand_slots(size_t extra_operand_slots, Args&&... args)
  85. {
  86. emit_with_extra_slots<OpType, Operand>(extra_operand_slots, forward<Args>(args)...);
  87. }
  88. template<typename OpType, typename... Args>
  89. void emit_with_extra_value_slots(size_t extra_operand_slots, Args&&... args)
  90. {
  91. emit_with_extra_slots<OpType, Value>(extra_operand_slots, forward<Args>(args)...);
  92. }
  93. struct ReferenceOperands {
  94. Optional<Operand> base {}; // [[Base]]
  95. Optional<Operand> referenced_name {}; // [[ReferencedName]] as an operand
  96. Optional<IdentifierTableIndex> referenced_identifier {}; // [[ReferencedName]] as an identifier
  97. Optional<IdentifierTableIndex> referenced_private_identifier {}; // [[ReferencedName]] as a private identifier
  98. Optional<Operand> this_value {}; // [[ThisValue]]
  99. Optional<Operand> loaded_value {}; // Loaded value, if we've performed a load.
  100. };
  101. CodeGenerationErrorOr<ReferenceOperands> emit_load_from_reference(JS::ASTNode const&, Optional<Operand> preferred_dst = {});
  102. CodeGenerationErrorOr<void> emit_store_to_reference(JS::ASTNode const&, Operand value);
  103. CodeGenerationErrorOr<void> emit_store_to_reference(ReferenceOperands const&, Operand value);
  104. CodeGenerationErrorOr<Optional<Operand>> emit_delete_reference(JS::ASTNode const&);
  105. CodeGenerationErrorOr<ReferenceOperands> emit_super_reference(MemberExpression const&);
  106. void emit_set_variable(JS::Identifier const& identifier, Operand value, Bytecode::Op::SetVariable::InitializationMode initialization_mode = Bytecode::Op::SetVariable::InitializationMode::Set, Bytecode::Op::EnvironmentMode mode = Bytecode::Op::EnvironmentMode::Lexical);
  107. void push_home_object(Operand);
  108. void pop_home_object();
  109. void emit_new_function(Operand dst, JS::FunctionExpression const&, Optional<IdentifierTableIndex> lhs_name);
  110. CodeGenerationErrorOr<Optional<Operand>> emit_named_evaluation_if_anonymous_function(Expression const&, Optional<IdentifierTableIndex> lhs_name, Optional<Operand> preferred_dst = {});
  111. void begin_continuable_scope(Label continue_target, Vector<DeprecatedFlyString> const& language_label_set);
  112. void end_continuable_scope();
  113. void begin_breakable_scope(Label breakable_target, Vector<DeprecatedFlyString> const& language_label_set);
  114. void end_breakable_scope();
  115. [[nodiscard]] Label nearest_continuable_scope() const;
  116. [[nodiscard]] Label nearest_breakable_scope() const;
  117. void switch_to_basic_block(BasicBlock& block)
  118. {
  119. m_current_basic_block = &block;
  120. }
  121. [[nodiscard]] BasicBlock& current_block() { return *m_current_basic_block; }
  122. BasicBlock& make_block(String name = {})
  123. {
  124. if (name.is_empty())
  125. name = MUST(String::number(m_next_block++));
  126. auto block = BasicBlock::create(name);
  127. if (auto const* context = m_current_unwind_context) {
  128. if (context->handler().has_value())
  129. block->set_handler(context->handler().value().block());
  130. if (m_current_unwind_context->finalizer().has_value())
  131. block->set_finalizer(context->finalizer().value().block());
  132. }
  133. m_root_basic_blocks.append(move(block));
  134. return *m_root_basic_blocks.last();
  135. }
  136. bool is_current_block_terminated() const
  137. {
  138. return m_current_basic_block->is_terminated();
  139. }
  140. StringTableIndex intern_string(ByteString string)
  141. {
  142. return m_string_table->insert(move(string));
  143. }
  144. RegexTableIndex intern_regex(ParsedRegex regex)
  145. {
  146. return m_regex_table->insert(move(regex));
  147. }
  148. IdentifierTableIndex intern_identifier(DeprecatedFlyString string)
  149. {
  150. return m_identifier_table->insert(move(string));
  151. }
  152. Optional<IdentifierTableIndex> intern_identifier_for_expression(Expression const& expression);
  153. bool is_in_generator_or_async_function() const { return m_enclosing_function_kind == FunctionKind::Async || m_enclosing_function_kind == FunctionKind::Generator || m_enclosing_function_kind == FunctionKind::AsyncGenerator; }
  154. bool is_in_generator_function() const { return m_enclosing_function_kind == FunctionKind::Generator || m_enclosing_function_kind == FunctionKind::AsyncGenerator; }
  155. bool is_in_async_function() const { return m_enclosing_function_kind == FunctionKind::Async || m_enclosing_function_kind == FunctionKind::AsyncGenerator; }
  156. bool is_in_async_generator_function() const { return m_enclosing_function_kind == FunctionKind::AsyncGenerator; }
  157. enum class BindingMode {
  158. Lexical,
  159. Var,
  160. Global,
  161. };
  162. struct LexicalScope {
  163. SurroundingScopeKind kind;
  164. };
  165. void block_declaration_instantiation(ScopeNode const&);
  166. void begin_variable_scope();
  167. void end_variable_scope();
  168. enum class BlockBoundaryType {
  169. Break,
  170. Continue,
  171. Unwind,
  172. ReturnToFinally,
  173. LeaveLexicalEnvironment,
  174. };
  175. template<typename OpType>
  176. void perform_needed_unwinds()
  177. requires(OpType::IsTerminator && !IsSame<OpType, Op::Jump>)
  178. {
  179. for (size_t i = m_boundaries.size(); i > 0; --i) {
  180. auto boundary = m_boundaries[i - 1];
  181. using enum BlockBoundaryType;
  182. switch (boundary) {
  183. case Unwind:
  184. if constexpr (IsSame<OpType, Bytecode::Op::Throw>)
  185. return;
  186. emit<Bytecode::Op::LeaveUnwindContext>();
  187. break;
  188. case LeaveLexicalEnvironment:
  189. emit<Bytecode::Op::LeaveLexicalEnvironment>();
  190. break;
  191. case Break:
  192. case Continue:
  193. break;
  194. case ReturnToFinally:
  195. return;
  196. };
  197. }
  198. }
  199. void generate_break();
  200. void generate_break(DeprecatedFlyString const& break_label);
  201. void generate_continue();
  202. void generate_continue(DeprecatedFlyString const& continue_label);
  203. void start_boundary(BlockBoundaryType type) { m_boundaries.append(type); }
  204. void end_boundary(BlockBoundaryType type)
  205. {
  206. VERIFY(m_boundaries.last() == type);
  207. m_boundaries.take_last();
  208. }
  209. void emit_get_by_id(Operand dst, Operand base, IdentifierTableIndex property_identifier, Optional<IdentifierTableIndex> base_identifier = {});
  210. void emit_get_by_id_with_this(Operand dst, Operand base, IdentifierTableIndex, Operand this_value);
  211. void emit_iterator_value(Operand dst, Operand result);
  212. void emit_iterator_complete(Operand dst, Operand result);
  213. [[nodiscard]] size_t next_global_variable_cache() { return m_next_global_variable_cache++; }
  214. [[nodiscard]] size_t next_environment_variable_cache() { return m_next_environment_variable_cache++; }
  215. [[nodiscard]] size_t next_property_lookup_cache() { return m_next_property_lookup_cache++; }
  216. enum class DeduplicateConstant {
  217. Yes,
  218. No,
  219. };
  220. [[nodiscard]] Operand add_constant(Value value, DeduplicateConstant deduplicate_constant = DeduplicateConstant::Yes)
  221. {
  222. if (deduplicate_constant == DeduplicateConstant::Yes) {
  223. for (size_t i = 0; i < m_constants.size(); ++i) {
  224. if (m_constants[i] == value)
  225. return Operand(Operand::Type::Constant, i);
  226. }
  227. }
  228. m_constants.append(value);
  229. return Operand(Operand::Type::Constant, m_constants.size() - 1);
  230. }
  231. private:
  232. VM& m_vm;
  233. enum class JumpType {
  234. Continue,
  235. Break,
  236. };
  237. void generate_scoped_jump(JumpType);
  238. void generate_labelled_jump(JumpType, DeprecatedFlyString const& label);
  239. explicit Generator(VM&);
  240. ~Generator() = default;
  241. void grow(size_t);
  242. struct LabelableScope {
  243. Label bytecode_target;
  244. Vector<DeprecatedFlyString> language_label_set;
  245. };
  246. BasicBlock* m_current_basic_block { nullptr };
  247. ASTNode const* m_current_ast_node { nullptr };
  248. UnwindContext const* m_current_unwind_context { nullptr };
  249. Vector<NonnullOwnPtr<BasicBlock>> m_root_basic_blocks;
  250. NonnullOwnPtr<StringTable> m_string_table;
  251. NonnullOwnPtr<IdentifierTable> m_identifier_table;
  252. NonnullOwnPtr<RegexTable> m_regex_table;
  253. MarkedVector<Value> m_constants;
  254. u32 m_next_register { Register::reserved_register_count };
  255. u32 m_next_block { 1 };
  256. u32 m_next_property_lookup_cache { 0 };
  257. u32 m_next_global_variable_cache { 0 };
  258. u32 m_next_environment_variable_cache { 0 };
  259. FunctionKind m_enclosing_function_kind { FunctionKind::Normal };
  260. Vector<LabelableScope> m_continuable_scopes;
  261. Vector<LabelableScope> m_breakable_scopes;
  262. Vector<BlockBoundaryType> m_boundaries;
  263. Vector<Operand> m_home_objects;
  264. HashTable<u32> m_initialized_locals;
  265. };
  266. }