Generator.h 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225
  1. /*
  2. * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/NonnullOwnPtrVector.h>
  8. #include <AK/OwnPtr.h>
  9. #include <AK/SinglyLinkedList.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. namespace JS::Bytecode {
  21. class Generator {
  22. public:
  23. enum class SurroundingScopeKind {
  24. Global,
  25. Function,
  26. Block,
  27. };
  28. static CodeGenerationErrorOr<NonnullOwnPtr<Executable>> generate(ASTNode const&, FunctionKind = FunctionKind::Normal);
  29. Register allocate_register();
  30. void ensure_enough_space(size_t size)
  31. {
  32. // Make sure there's always enough space for a single jump at the end.
  33. if (!m_current_basic_block->can_grow(size + sizeof(Op::Jump))) {
  34. auto& new_block = make_block();
  35. emit<Op::Jump>().set_targets(
  36. Label { new_block },
  37. {});
  38. switch_to_basic_block(new_block);
  39. }
  40. }
  41. template<typename OpType, typename... Args>
  42. OpType& emit(Args&&... args)
  43. {
  44. VERIFY(!is_current_block_terminated());
  45. // If the block doesn't have enough space, switch to another block
  46. if constexpr (!OpType::IsTerminator)
  47. ensure_enough_space(sizeof(OpType));
  48. void* slot = next_slot();
  49. grow(sizeof(OpType));
  50. new (slot) OpType(forward<Args>(args)...);
  51. if constexpr (OpType::IsTerminator)
  52. m_current_basic_block->terminate({});
  53. return *static_cast<OpType*>(slot);
  54. }
  55. template<typename OpType, typename... Args>
  56. OpType& emit_with_extra_register_slots(size_t extra_register_slots, Args&&... args)
  57. {
  58. VERIFY(!is_current_block_terminated());
  59. // If the block doesn't have enough space, switch to another block
  60. if constexpr (!OpType::IsTerminator)
  61. ensure_enough_space(sizeof(OpType) + extra_register_slots * sizeof(Register));
  62. void* slot = next_slot();
  63. grow(sizeof(OpType) + extra_register_slots * sizeof(Register));
  64. new (slot) OpType(forward<Args>(args)...);
  65. if constexpr (OpType::IsTerminator)
  66. m_current_basic_block->terminate({});
  67. return *static_cast<OpType*>(slot);
  68. }
  69. CodeGenerationErrorOr<void> emit_load_from_reference(JS::ASTNode const&);
  70. CodeGenerationErrorOr<void> emit_store_to_reference(JS::ASTNode const&);
  71. CodeGenerationErrorOr<void> emit_delete_reference(JS::ASTNode const&);
  72. void begin_continuable_scope(Label continue_target, Vector<FlyString> const& language_label_set);
  73. void end_continuable_scope();
  74. void begin_breakable_scope(Label breakable_target, Vector<FlyString> const& language_label_set);
  75. void end_breakable_scope();
  76. [[nodiscard]] Label nearest_continuable_scope() const;
  77. [[nodiscard]] Label nearest_breakable_scope() const;
  78. void switch_to_basic_block(BasicBlock& block)
  79. {
  80. m_current_basic_block = &block;
  81. }
  82. [[nodiscard]] BasicBlock& current_block() { return *m_current_basic_block; }
  83. BasicBlock& make_block(String name = {})
  84. {
  85. if (name.is_empty())
  86. name = String::number(m_next_block++);
  87. m_root_basic_blocks.append(BasicBlock::create(name));
  88. return m_root_basic_blocks.last();
  89. }
  90. bool is_current_block_terminated() const
  91. {
  92. return m_current_basic_block->is_terminated();
  93. }
  94. StringTableIndex intern_string(String string)
  95. {
  96. return m_string_table->insert(move(string));
  97. }
  98. IdentifierTableIndex intern_identifier(FlyString string)
  99. {
  100. return m_identifier_table->insert(move(string));
  101. }
  102. bool is_in_generator_or_async_function() const { return m_enclosing_function_kind == FunctionKind::Async || m_enclosing_function_kind == FunctionKind::Generator; }
  103. bool is_in_generator_function() const { return m_enclosing_function_kind == FunctionKind::Generator; }
  104. bool is_in_async_function() const { return m_enclosing_function_kind == FunctionKind::Async; }
  105. enum class BindingMode {
  106. Lexical,
  107. Var,
  108. Global,
  109. };
  110. struct LexicalScope {
  111. SurroundingScopeKind kind;
  112. BindingMode mode;
  113. HashTable<IdentifierTableIndex> known_bindings;
  114. };
  115. void register_binding(IdentifierTableIndex identifier, BindingMode mode = BindingMode::Lexical)
  116. {
  117. m_variable_scopes.last_matching([&](auto& x) { return x.mode == BindingMode::Global || x.mode == mode; })->known_bindings.set(identifier);
  118. }
  119. bool has_binding(IdentifierTableIndex identifier, Optional<BindingMode> const& specific_binding_mode = {})
  120. {
  121. for (auto index = m_variable_scopes.size(); index > 0; --index) {
  122. auto& scope = m_variable_scopes[index - 1];
  123. if (scope.mode != BindingMode::Global && specific_binding_mode.value_or(scope.mode) != scope.mode)
  124. continue;
  125. if (scope.known_bindings.contains(identifier))
  126. return true;
  127. }
  128. return false;
  129. }
  130. void begin_variable_scope(BindingMode mode = BindingMode::Lexical, SurroundingScopeKind kind = SurroundingScopeKind::Block);
  131. void end_variable_scope();
  132. enum class BlockBoundaryType {
  133. Break,
  134. Continue,
  135. Unwind,
  136. LeaveLexicalEnvironment,
  137. LeaveVariableEnvironment,
  138. };
  139. template<typename OpType>
  140. void perform_needed_unwinds(bool is_break_node = false) requires(OpType::IsTerminator)
  141. {
  142. Optional<BlockBoundaryType> boundary_to_stop_at;
  143. if constexpr (IsSame<OpType, Bytecode::Op::Return> || IsSame<OpType, Bytecode::Op::Yield>)
  144. VERIFY(!is_break_node);
  145. else if constexpr (IsSame<OpType, Bytecode::Op::Throw>)
  146. boundary_to_stop_at = BlockBoundaryType::Unwind;
  147. else
  148. boundary_to_stop_at = is_break_node ? BlockBoundaryType::Break : BlockBoundaryType::Continue;
  149. for (size_t i = m_boundaries.size(); i > 0; --i) {
  150. auto boundary = m_boundaries[i - 1];
  151. if (boundary_to_stop_at.has_value() && boundary == *boundary_to_stop_at)
  152. break;
  153. if (boundary == BlockBoundaryType::Unwind)
  154. emit<Bytecode::Op::LeaveUnwindContext>();
  155. else if (boundary == BlockBoundaryType::LeaveLexicalEnvironment)
  156. emit<Bytecode::Op::LeaveEnvironment>(Bytecode::Op::EnvironmentMode::Lexical);
  157. else if (boundary == BlockBoundaryType::LeaveVariableEnvironment)
  158. emit<Bytecode::Op::LeaveEnvironment>(Bytecode::Op::EnvironmentMode::Var);
  159. }
  160. }
  161. Label perform_needed_unwinds_for_labelled_break_and_return_target_block(FlyString const& break_label);
  162. Label perform_needed_unwinds_for_labelled_continue_and_return_target_block(FlyString const& continue_label);
  163. void start_boundary(BlockBoundaryType type) { m_boundaries.append(type); }
  164. void end_boundary(BlockBoundaryType type)
  165. {
  166. VERIFY(m_boundaries.last() == type);
  167. m_boundaries.take_last();
  168. }
  169. private:
  170. Generator();
  171. ~Generator() = default;
  172. void grow(size_t);
  173. void* next_slot();
  174. struct LabelableScope {
  175. Label bytecode_target;
  176. Vector<FlyString> language_label_set;
  177. };
  178. BasicBlock* m_current_basic_block { nullptr };
  179. NonnullOwnPtrVector<BasicBlock> m_root_basic_blocks;
  180. NonnullOwnPtr<StringTable> m_string_table;
  181. NonnullOwnPtr<IdentifierTable> m_identifier_table;
  182. u32 m_next_register { 2 };
  183. u32 m_next_block { 1 };
  184. FunctionKind m_enclosing_function_kind { FunctionKind::Normal };
  185. Vector<LabelableScope> m_continuable_scopes;
  186. Vector<LabelableScope> m_breakable_scopes;
  187. Vector<LexicalScope> m_variable_scopes;
  188. Vector<BlockBoundaryType> m_boundaries;
  189. };
  190. }