SSABuildingPass.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453
  1. /*
  2. * Copyright (c) 2023, Dan Klishch <danilklishch@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Queue.h>
  7. #include "AST/AST.h"
  8. #include "Compiler/GenericASTPass.h"
  9. #include "Compiler/Passes/SSABuildingPass.h"
  10. #include "Function.h"
  11. namespace JSSpecCompiler {
  12. void SSABuildingPass::process_function()
  13. {
  14. m_dtree_timer = 0;
  15. m_order.clear();
  16. m_mark_version = 1;
  17. m_def_stack.clear();
  18. m_next_id.clear();
  19. m_undo_vector.clear();
  20. m_graph = m_function->m_cfg;
  21. with_graph(m_graph->blocks_count(), [&] {
  22. compute_dominator_tree();
  23. compute_dominance_frontiers();
  24. place_phi_nodes();
  25. rename_variables();
  26. });
  27. }
  28. // ===== compute_dominator_tree =====
  29. namespace {
  30. class DSU {
  31. struct NodeData {
  32. size_t sdom;
  33. size_t parent;
  34. };
  35. public:
  36. DSU(size_t n)
  37. : n(n)
  38. {
  39. m_nodes.resize(n);
  40. for (size_t i = 0; i < n; ++i)
  41. m_nodes[i] = { i, i };
  42. }
  43. NodeData get(size_t u)
  44. {
  45. if (m_nodes[u].parent == u)
  46. return { n, u };
  47. auto [sdom, root] = get(m_nodes[u].parent);
  48. sdom = min(sdom, m_nodes[u].sdom);
  49. return m_nodes[u] = { sdom, root };
  50. }
  51. void merge(size_t u, size_t v, size_t v_sdom)
  52. {
  53. m_nodes[v] = { v_sdom, u };
  54. }
  55. private:
  56. size_t n;
  57. Vector<NodeData> m_nodes;
  58. };
  59. }
  60. void SSABuildingPass::compute_order(BasicBlockRef u, Vertex parent)
  61. {
  62. if (m_nodes[u->m_index].is_used)
  63. return;
  64. m_nodes[u->m_index].is_used = true;
  65. Vertex reordered_u = m_order.size();
  66. m_order.append(RefPtr<BasicBlock>(u).release_nonnull());
  67. reordered_u->parent = parent;
  68. for (auto* v : u->m_continuation->references())
  69. compute_order(*v, reordered_u);
  70. }
  71. void SSABuildingPass::compute_dominator_tree()
  72. {
  73. size_t n = m_graph->blocks_count();
  74. m_nodes.resize(n);
  75. // Algorithm is from https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/ ,
  76. // an author writes awful CP-style write-only code, but the explanation is pretty good.
  77. // Step 1
  78. compute_order(m_graph->start_block);
  79. VERIFY(m_order.size() == n);
  80. for (size_t i = 0; i < n; ++i)
  81. m_order[i]->m_index = i;
  82. m_graph->blocks = m_order;
  83. for (size_t i = 0; i < n; ++i) {
  84. Vertex u = i;
  85. for (auto* reference : u.block()->m_continuation->references()) {
  86. Vertex v { *reference };
  87. v->incoming_edges.append(u);
  88. u->outgoing_edges.append(v);
  89. }
  90. }
  91. // Steps 2 & 3
  92. DSU dsu(n);
  93. for (size_t i = n - 1; i > 0; --i) {
  94. Vertex u = i;
  95. Vertex& current_sdom = u->semi_dominator;
  96. current_sdom = n;
  97. for (Vertex v : u->incoming_edges) {
  98. if (v < u)
  99. current_sdom = min(current_sdom, v);
  100. else
  101. current_sdom = min(current_sdom, dsu.get(v).sdom);
  102. }
  103. current_sdom->buckets.append(u);
  104. for (Vertex w : u->buckets) {
  105. Vertex v = dsu.get(w).sdom;
  106. if (v->semi_dominator == w->semi_dominator)
  107. w->immediate_dominator = v->semi_dominator;
  108. else
  109. w->immediate_dominator = v;
  110. }
  111. dsu.merge(u->parent, u, current_sdom);
  112. }
  113. m_nodes[0].immediate_dominator = invalid_node;
  114. for (size_t i = 1; i < n; ++i) {
  115. Vertex u = i;
  116. if (u->immediate_dominator.is_invalid())
  117. u->immediate_dominator = 0;
  118. else if (u->immediate_dominator != u->semi_dominator)
  119. u->immediate_dominator = u->immediate_dominator->immediate_dominator;
  120. }
  121. // Populate dtree_children & BasicBlock::immediate_dominator
  122. for (size_t i = 0; i < n; ++i) {
  123. Vertex u = i;
  124. if (i != 0) {
  125. u.block()->m_immediate_dominator = u->immediate_dominator.block();
  126. u->immediate_dominator->dtree_children.append(u);
  127. } else {
  128. u.block()->m_immediate_dominator = nullptr;
  129. }
  130. }
  131. }
  132. // ===== compute_dominance_frontiers =====
  133. template<typename... Args>
  134. Vector<SSABuildingPass::Vertex> SSABuildingPass::unique(Args const&... args)
  135. {
  136. ++m_mark_version;
  137. Vector<Vertex> result;
  138. (([&](auto const& list) {
  139. for (Vertex u : list) {
  140. if (u->mark != m_mark_version) {
  141. u->mark = m_mark_version;
  142. result.append(u);
  143. }
  144. }
  145. })(args),
  146. ...);
  147. return result;
  148. }
  149. void SSABuildingPass::compute_dtree_tin_tout(Vertex u)
  150. {
  151. u->tin = m_dtree_timer++;
  152. for (Vertex v : u->dtree_children)
  153. compute_dtree_tin_tout(v);
  154. u->tout = m_dtree_timer++;
  155. }
  156. bool SSABuildingPass::is_strictly_dominating(Vertex u, Vertex v)
  157. {
  158. return u != v && u->tin <= v->tin && v->tout <= u->tout;
  159. }
  160. void SSABuildingPass::compute_dominance_frontiers()
  161. {
  162. compute_dtree_tin_tout(0);
  163. // Algorithm from https://en.wikipedia.org/wiki/Static_single-assignment_form#Converting%20to%20SSA:~:text=their%20paper%20titled-,A%20Simple%2C%20Fast%20Dominance%20Algorithm,-%3A%5B13%5D .
  164. // DF(u) = {w : !(u sdom w) /\ (\exists v \in incoming_edges(v) : u dom v)}
  165. for (size_t wi = 0; wi < m_nodes.size(); ++wi) {
  166. Vertex w = wi;
  167. for (Vertex v : w->incoming_edges) {
  168. Vertex u = v;
  169. while (u != invalid_node && !is_strictly_dominating(u, w)) {
  170. u->d_frontier.append(w);
  171. u = u->immediate_dominator;
  172. }
  173. }
  174. }
  175. for (size_t i = 0; i < m_nodes.size(); ++i) {
  176. Vertex u = i;
  177. u->d_frontier = unique(u->d_frontier);
  178. }
  179. }
  180. // ===== place_phi_nodes =====
  181. namespace {
  182. class VariableAssignmentCollector : private RecursiveASTVisitor {
  183. public:
  184. VariableAssignmentCollector(OrderedHashMap<NamedVariableDeclarationRef, Vector<BasicBlockRef>>& declarations)
  185. : m_declarations(declarations)
  186. {
  187. }
  188. void run(BasicBlockRef block)
  189. {
  190. m_current_block = block;
  191. for (auto& expression : block->m_expressions)
  192. run_in_subtree(expression);
  193. run_in_const_subtree(block->m_continuation);
  194. }
  195. protected:
  196. RecursionDecision on_entry(Tree tree) override
  197. {
  198. if (tree->is_statement())
  199. TODO();
  200. return RecursionDecision::Recurse;
  201. }
  202. void on_leave(Tree tree) override
  203. {
  204. if (auto binary_operation = as<BinaryOperation>(tree); binary_operation) {
  205. if (binary_operation->m_operation != BinaryOperator::Assignment)
  206. return;
  207. if (auto variable = as<Variable>(binary_operation->m_left); variable) {
  208. auto& vector = m_declarations.get(variable->m_name).value();
  209. if (vector.is_empty() || vector.last() != m_current_block)
  210. vector.append(m_current_block);
  211. }
  212. }
  213. }
  214. private:
  215. BasicBlockRef m_current_block;
  216. OrderedHashMap<NamedVariableDeclarationRef, Vector<BasicBlockRef>>& m_declarations;
  217. };
  218. }
  219. void SSABuildingPass::add_phi_node(BasicBlockRef block, NamedVariableDeclarationRef decl)
  220. {
  221. BasicBlock::PhiNode node { .var = make_ref_counted<Variable>(decl) };
  222. for (Vertex incoming : Vertex(block)->incoming_edges) {
  223. BasicBlockRef incoming_block = incoming.block();
  224. auto value = make_ref_counted<Variable>(decl);
  225. node.branches.append({ .block = incoming_block, .value = value });
  226. }
  227. block->m_phi_nodes.append(move(node));
  228. }
  229. void SSABuildingPass::place_phi_nodes()
  230. {
  231. // Entry block has implicit declarations of all variables.
  232. OrderedHashMap<NamedVariableDeclarationRef, Vector<BasicBlockRef>> m_declarations;
  233. for (auto const& [name, var_decl] : m_function->m_local_variables)
  234. m_declarations.set(var_decl, { m_order[0] });
  235. m_declarations.set(m_function->m_named_return_value, { m_order[0] });
  236. VariableAssignmentCollector collector(m_declarations);
  237. for (auto const& block : m_order)
  238. collector.run(block);
  239. for (auto const& [decl, blocks] : m_declarations) {
  240. ++m_mark_version;
  241. Queue<BasicBlockRef> queue;
  242. for (auto const& block : blocks)
  243. queue.enqueue(block);
  244. while (!queue.is_empty()) {
  245. Vertex u(queue.dequeue());
  246. for (Vertex frontier : u->d_frontier) {
  247. if (frontier->mark == m_mark_version)
  248. continue;
  249. frontier->mark = m_mark_version;
  250. add_phi_node(frontier.block(), decl);
  251. }
  252. }
  253. }
  254. }
  255. // ===== rename_variables =====
  256. namespace {
  257. template<typename CreateSSAVariableFunc, typename RenameVariableFunc>
  258. class VariableRenamer : private RecursiveASTVisitor {
  259. public:
  260. VariableRenamer(CreateSSAVariableFunc create, RenameVariableFunc rename)
  261. : m_create(create)
  262. , m_rename(rename)
  263. {
  264. }
  265. void run(BasicBlockRef block)
  266. {
  267. for (auto& expression : block->m_expressions)
  268. run_in_subtree(expression);
  269. run_in_const_subtree(block->m_continuation);
  270. }
  271. protected:
  272. RecursionDecision on_entry(Tree tree) override
  273. {
  274. if (tree->is_statement())
  275. TODO();
  276. auto binary_operation = as<BinaryOperation>(tree);
  277. if (binary_operation && binary_operation->m_operation == BinaryOperator::Assignment) {
  278. run_in_subtree(binary_operation->m_right);
  279. if (auto variable = as<Variable>(binary_operation->m_left); variable) {
  280. m_create(variable->m_name);
  281. m_rename(variable.release_nonnull());
  282. } else {
  283. run_in_subtree(binary_operation->m_left);
  284. }
  285. return RecursionDecision::Continue;
  286. }
  287. if (auto variable = as<Variable>(tree); variable) {
  288. m_rename(variable.release_nonnull());
  289. return RecursionDecision::Continue;
  290. }
  291. return RecursionDecision::Recurse;
  292. }
  293. private:
  294. CreateSSAVariableFunc m_create;
  295. RenameVariableFunc m_rename;
  296. };
  297. }
  298. void SSABuildingPass::make_new_ssa_variable_for(NamedVariableDeclarationRef var)
  299. {
  300. m_undo_vector.append(var);
  301. u64 id = 0;
  302. if (auto it = m_next_id.find(var); it == m_next_id.end())
  303. m_next_id.set(var, 1);
  304. else
  305. id = it->value++;
  306. auto ssa_decl = make_ref_counted<SSAVariableDeclaration>(id);
  307. m_function->m_local_ssa_variables.append(ssa_decl);
  308. if (auto it = m_def_stack.find(var); it == m_def_stack.end())
  309. m_def_stack.set(var, { ssa_decl });
  310. else
  311. it->value.append(ssa_decl);
  312. }
  313. void SSABuildingPass::rename_variable(VariableRef var)
  314. {
  315. var->m_ssa = m_def_stack.get(var->m_name).value().last();
  316. }
  317. void SSABuildingPass::rename_variables(Vertex u, Vertex from)
  318. {
  319. size_t rollback_point = m_undo_vector.size();
  320. for (auto& phi_node : u.block()->m_phi_nodes) {
  321. // TODO: Find the right branch index without iterating through all of the branches.
  322. bool found = false;
  323. for (auto& branch : phi_node.branches) {
  324. if (branch.block->m_index == from) {
  325. rename_variable(branch.value);
  326. found = true;
  327. break;
  328. }
  329. }
  330. VERIFY(found);
  331. }
  332. if (u->mark == m_mark_version)
  333. return;
  334. u->mark = m_mark_version;
  335. for (auto& phi_node : u.block()->m_phi_nodes) {
  336. make_new_ssa_variable_for(phi_node.var->m_name);
  337. rename_variable(phi_node.var);
  338. }
  339. VariableRenamer renamer(
  340. [&](NamedVariableDeclarationRef decl) {
  341. make_new_ssa_variable_for(move(decl));
  342. },
  343. [&](VariableRef var) {
  344. rename_variable(move(var));
  345. });
  346. renamer.run(u.block());
  347. if (auto function_return = as<ControlFlowFunctionReturn>(u.block()->m_continuation); function_return) {
  348. // CFG should have exactly one ControlFlowFunctionReturn.
  349. VERIFY(m_function->m_return_value == nullptr);
  350. m_function->m_return_value = function_return->m_return_value->m_ssa;
  351. }
  352. for (size_t j : u->outgoing_edges)
  353. rename_variables(j, u);
  354. while (m_undo_vector.size() > rollback_point)
  355. (void)m_def_stack.get(m_undo_vector.take_last()).value().take_last();
  356. }
  357. void SSABuildingPass::rename_variables()
  358. {
  359. HashMap<StringView, size_t> argument_index_by_name;
  360. for (size_t i = 0; i < m_function->m_arguments.size(); ++i)
  361. argument_index_by_name.set(m_function->m_arguments[i].name, i);
  362. m_function->m_ssa_arguments.resize(m_function->m_arguments.size());
  363. for (auto const& [name, var_decl] : m_function->m_local_variables) {
  364. make_new_ssa_variable_for(var_decl);
  365. if (auto maybe_index = argument_index_by_name.get(name); maybe_index.has_value()) {
  366. size_t index = maybe_index.value();
  367. m_function->m_ssa_arguments[index] = m_def_stack.get(var_decl).value()[0];
  368. }
  369. }
  370. make_new_ssa_variable_for(m_function->m_named_return_value);
  371. ++m_mark_version;
  372. rename_variables(0);
  373. VERIFY(m_function->m_return_value);
  374. m_function->reindex_ssa_variables();
  375. }
  376. }