MergeBlocks.cpp 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178
  1. /*
  2. * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <LibJS/Bytecode/PassManager.h>
  7. namespace JS::Bytecode::Passes {
  8. void MergeBlocks::perform(PassPipelineExecutable& executable)
  9. {
  10. started();
  11. VERIFY(executable.cfg.has_value());
  12. VERIFY(executable.inverted_cfg.has_value());
  13. auto cfg = executable.cfg.release_value();
  14. auto inverted_cfg = executable.inverted_cfg.release_value();
  15. // Figure out which blocks can be merged
  16. HashTable<BasicBlock const*> blocks_to_merge;
  17. HashMap<BasicBlock const*, BasicBlock const*> blocks_to_replace;
  18. Vector<BasicBlock const*> blocks_to_remove;
  19. Vector<size_t> boundaries;
  20. for (auto& entry : cfg) {
  21. if (entry.value.size() != 1)
  22. continue;
  23. if (executable.exported_blocks->contains(*entry.value.begin()))
  24. continue;
  25. {
  26. InstructionStreamIterator it { entry.key->instruction_stream() };
  27. auto& first_instruction = *it;
  28. if (first_instruction.type() == Instruction::Type::Jump) {
  29. auto const* replacing_block = &static_cast<Op::Jump const&>(first_instruction).true_target()->block();
  30. if (replacing_block != entry.key) {
  31. blocks_to_replace.set(entry.key, replacing_block);
  32. }
  33. continue;
  34. }
  35. }
  36. if (auto cfg_iter = inverted_cfg.find(*entry.value.begin()); cfg_iter != inverted_cfg.end()) {
  37. auto& predecessor_entry = cfg_iter->value;
  38. if (predecessor_entry.size() != 1)
  39. continue;
  40. }
  41. // The two blocks are safe to merge.
  42. blocks_to_merge.set(entry.key);
  43. }
  44. for (auto& entry : blocks_to_replace) {
  45. auto const* replacement = entry.value;
  46. for (;;) {
  47. auto lookup = blocks_to_replace.get(replacement);
  48. if (!lookup.has_value())
  49. break;
  50. if (replacement == *lookup)
  51. break;
  52. replacement = *lookup;
  53. }
  54. entry.value = replacement;
  55. }
  56. auto replace_blocks = [&](auto& blocks, auto& replacement) {
  57. Optional<size_t> first_successor_position;
  58. for (auto& entry : blocks) {
  59. blocks_to_remove.append(entry);
  60. auto it = executable.executable.basic_blocks.find_if([entry](auto& block) { return entry == block; });
  61. VERIFY(!it.is_end());
  62. if (!first_successor_position.has_value())
  63. first_successor_position = it.index();
  64. }
  65. for (auto& block : executable.executable.basic_blocks) {
  66. InstructionStreamIterator it { block.instruction_stream() };
  67. while (!it.at_end()) {
  68. auto& instruction = *it;
  69. ++it;
  70. for (auto& entry : blocks)
  71. const_cast<Instruction&>(instruction).replace_references(*entry, replacement);
  72. }
  73. }
  74. return first_successor_position;
  75. };
  76. for (auto& entry : blocks_to_replace) {
  77. AK::Array candidates { entry.key };
  78. (void)replace_blocks(candidates, *entry.value);
  79. }
  80. while (!blocks_to_merge.is_empty()) {
  81. auto it = blocks_to_merge.begin();
  82. auto const* current_block = *it;
  83. blocks_to_merge.remove(it);
  84. Vector<BasicBlock const*> successors { current_block };
  85. for (;;) {
  86. auto const* last = successors.last();
  87. auto entry = cfg.find(last);
  88. if (entry == cfg.end())
  89. break;
  90. auto const* successor = *entry->value.begin();
  91. successors.append(successor);
  92. if (!blocks_to_merge.remove(successor))
  93. break;
  94. }
  95. auto blocks_to_merge_copy = blocks_to_merge;
  96. // We need to do the following multiple times, due to it not being
  97. // guaranteed, that the blocks are in sequential order
  98. bool did_prepend = true;
  99. while (did_prepend) {
  100. did_prepend = false;
  101. for (auto const* last : blocks_to_merge) {
  102. auto entry = cfg.find(last);
  103. if (entry == cfg.end())
  104. continue;
  105. auto const* successor = *entry->value.begin();
  106. if (successor == successors.first()) {
  107. successors.prepend(last);
  108. blocks_to_merge_copy.remove(last);
  109. did_prepend = true;
  110. }
  111. }
  112. }
  113. blocks_to_merge = move(blocks_to_merge_copy);
  114. size_t size = 0;
  115. StringBuilder builder;
  116. builder.append("merge"sv);
  117. for (auto& entry : successors) {
  118. size += entry->size();
  119. builder.append('.');
  120. builder.append(entry->name());
  121. }
  122. auto new_block = BasicBlock::create(builder.build(), size);
  123. auto& block = *new_block;
  124. auto first_successor_position = replace_blocks(successors, *new_block);
  125. VERIFY(first_successor_position.has_value());
  126. size_t last_successor_index = successors.size() - 1;
  127. for (size_t i = 0; i < successors.size(); ++i) {
  128. auto& entry = successors[i];
  129. InstructionStreamIterator it { entry->instruction_stream() };
  130. while (!it.at_end()) {
  131. auto& instruction = *it;
  132. ++it;
  133. if (instruction.is_terminator() && last_successor_index != i)
  134. break;
  135. // FIXME: Op::NewBigInt is not trivially copyable, so we cant use
  136. // a simple memcpy to transfer them.
  137. // When this is resolved we can use a single memcpy to copy
  138. // the whole block at once
  139. if (instruction.type() == Instruction::Type::NewBigInt) {
  140. new (block.next_slot()) Op::NewBigInt(static_cast<Op::NewBigInt const&>(instruction));
  141. block.grow(sizeof(Op::NewBigInt));
  142. } else {
  143. auto instruction_size = instruction.length();
  144. memcpy(block.next_slot(), &instruction, instruction_size);
  145. block.grow(instruction_size);
  146. }
  147. }
  148. }
  149. executable.executable.basic_blocks.insert(*first_successor_position, move(new_block));
  150. }
  151. executable.executable.basic_blocks.remove_all_matching([&blocks_to_remove](auto& candidate) { return blocks_to_remove.contains_slow(candidate.ptr()); });
  152. finished();
  153. }
  154. }