Generator.h 7.6 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. void begin_continuable_scope(Label continue_target);
  72. void end_continuable_scope();
  73. void begin_breakable_scope(Label breakable_target);
  74. void end_breakable_scope();
  75. [[nodiscard]] Label nearest_continuable_scope() const;
  76. [[nodiscard]] Label nearest_breakable_scope() const;
  77. void switch_to_basic_block(BasicBlock& block)
  78. {
  79. m_current_basic_block = &block;
  80. }
  81. [[nodiscard]] BasicBlock& current_block() { return *m_current_basic_block; }
  82. BasicBlock& make_block(String name = {})
  83. {
  84. if (name.is_empty())
  85. name = String::number(m_next_block++);
  86. m_root_basic_blocks.append(BasicBlock::create(name));
  87. return m_root_basic_blocks.last();
  88. }
  89. bool is_current_block_terminated() const
  90. {
  91. return m_current_basic_block->is_terminated();
  92. }
  93. StringTableIndex intern_string(String string)
  94. {
  95. return m_string_table->insert(move(string));
  96. }
  97. IdentifierTableIndex intern_identifier(FlyString string)
  98. {
  99. return m_identifier_table->insert(move(string));
  100. }
  101. bool is_in_generator_or_async_function() const { return m_enclosing_function_kind == FunctionKind::Async || m_enclosing_function_kind == FunctionKind::Generator; }
  102. bool is_in_generator_function() const { return m_enclosing_function_kind == FunctionKind::Generator; }
  103. bool is_in_async_function() const { return m_enclosing_function_kind == FunctionKind::Async; }
  104. enum class BindingMode {
  105. Lexical,
  106. Var,
  107. Global,
  108. };
  109. struct LexicalScope {
  110. SurroundingScopeKind kind;
  111. BindingMode mode;
  112. HashTable<IdentifierTableIndex> known_bindings;
  113. };
  114. void register_binding(IdentifierTableIndex identifier, BindingMode mode = BindingMode::Lexical)
  115. {
  116. m_variable_scopes.last_matching([&](auto& x) { return x.mode == BindingMode::Global || x.mode == mode; })->known_bindings.set(identifier);
  117. }
  118. bool has_binding(IdentifierTableIndex identifier, Optional<BindingMode> const& specific_binding_mode = {})
  119. {
  120. for (auto index = m_variable_scopes.size(); index > 0; --index) {
  121. auto& scope = m_variable_scopes[index - 1];
  122. if (scope.mode != BindingMode::Global && specific_binding_mode.value_or(scope.mode) != scope.mode)
  123. continue;
  124. if (scope.known_bindings.contains(identifier))
  125. return true;
  126. }
  127. return false;
  128. }
  129. void begin_variable_scope(BindingMode mode = BindingMode::Lexical, SurroundingScopeKind kind = SurroundingScopeKind::Block)
  130. {
  131. m_variable_scopes.append({ kind, mode, {} });
  132. if (mode != BindingMode::Global) {
  133. emit<Bytecode::Op::CreateEnvironment>(
  134. mode == BindingMode::Lexical
  135. ? Bytecode::Op::EnvironmentMode::Lexical
  136. : Bytecode::Op::EnvironmentMode::Var);
  137. }
  138. }
  139. void end_variable_scope()
  140. {
  141. auto mode = m_variable_scopes.take_last().mode;
  142. if (mode != BindingMode::Global && !m_current_basic_block->is_terminated()) {
  143. emit<Bytecode::Op::LeaveEnvironment>(
  144. mode == BindingMode::Lexical
  145. ? Bytecode::Op::EnvironmentMode::Lexical
  146. : Bytecode::Op::EnvironmentMode::Var);
  147. }
  148. }
  149. enum class BlockBoundaryType {
  150. Break,
  151. Continue,
  152. Unwind,
  153. };
  154. template<typename OpType>
  155. void perform_needed_unwinds(bool is_break_node = false) requires(OpType::IsTerminator)
  156. {
  157. Optional<BlockBoundaryType> boundary_to_stop_at;
  158. if constexpr (IsSame<OpType, Bytecode::Op::Return> || IsSame<OpType, Bytecode::Op::Yield>)
  159. VERIFY(!is_break_node);
  160. else
  161. boundary_to_stop_at = is_break_node ? BlockBoundaryType::Break : BlockBoundaryType::Continue;
  162. for (size_t i = m_boundaries.size(); i > 0; --i) {
  163. auto boundary = m_boundaries[i - 1];
  164. if (boundary_to_stop_at.has_value() && boundary == *boundary_to_stop_at)
  165. break;
  166. if (boundary == BlockBoundaryType::Unwind)
  167. emit<Bytecode::Op::LeaveUnwindContext>();
  168. }
  169. }
  170. void start_boundary(BlockBoundaryType type) { m_boundaries.append(type); }
  171. void end_boundary(BlockBoundaryType type)
  172. {
  173. VERIFY(m_boundaries.last() == type);
  174. m_boundaries.take_last();
  175. }
  176. private:
  177. Generator();
  178. ~Generator();
  179. void grow(size_t);
  180. void* next_slot();
  181. BasicBlock* m_current_basic_block { nullptr };
  182. NonnullOwnPtrVector<BasicBlock> m_root_basic_blocks;
  183. NonnullOwnPtr<StringTable> m_string_table;
  184. NonnullOwnPtr<IdentifierTable> m_identifier_table;
  185. u32 m_next_register { 2 };
  186. u32 m_next_block { 1 };
  187. FunctionKind m_enclosing_function_kind { FunctionKind::Normal };
  188. Vector<Label> m_continuable_scopes;
  189. Vector<Label> m_breakable_scopes;
  190. Vector<LexicalScope> m_variable_scopes;
  191. Vector<BlockBoundaryType> m_boundaries;
  192. };
  193. }