flowgraph.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224
  1. // SPDX-License-Identifier: MIT
  2. //
  3. // Various utilities for flowgraphs.
  4. //
  5. // Copyright (c) 2017 Luc Van Oostenryck.
  6. //
  7. #include "flowgraph.h"
  8. #include "linearize.h"
  9. #include "flow.h" // for bb_generation
  10. #include <assert.h>
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. struct cfg_info {
  14. struct basic_block_list *list;
  15. unsigned long gen;
  16. unsigned int nr;
  17. };
  18. static void label_postorder(struct basic_block *bb, struct cfg_info *info)
  19. {
  20. struct basic_block *child;
  21. if (bb->generation == info->gen)
  22. return;
  23. bb->generation = info->gen;
  24. FOR_EACH_PTR_REVERSE(bb->children, child) {
  25. label_postorder(child, info);
  26. } END_FOR_EACH_PTR_REVERSE(child);
  27. bb->postorder_nr = info->nr++;
  28. add_bb(&info->list, bb);
  29. }
  30. static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src)
  31. {
  32. struct basic_block *bb;
  33. FOR_EACH_PTR_REVERSE(src, bb) {
  34. add_bb(dst, bb);
  35. } END_FOR_EACH_PTR_REVERSE(bb);
  36. }
  37. static void debug_postorder(struct entrypoint *ep)
  38. {
  39. struct basic_block *bb;
  40. printf("%s's reverse postorder:\n", show_ident(ep->name->ident));
  41. FOR_EACH_PTR(ep->bbs, bb) {
  42. printf("\t.L%u: %u\n", bb->nr, bb->postorder_nr);
  43. } END_FOR_EACH_PTR(bb);
  44. }
  45. //
  46. // cfg_postorder - Set the BB's reverse postorder links
  47. //
  48. // Do a postorder DFS walk and set the links
  49. // (which will do the reverse part).
  50. //
  51. int cfg_postorder(struct entrypoint *ep)
  52. {
  53. struct cfg_info info = {
  54. .gen = ++bb_generation,
  55. };
  56. label_postorder(ep->entry->bb, &info);
  57. // OK, now info.list contains the node in postorder
  58. // Reuse ep->bbs for the reverse postorder.
  59. free_ptr_list(&ep->bbs);
  60. ep->bbs = NULL;
  61. reverse_bbs(&ep->bbs, info.list);
  62. free_ptr_list(&info.list);
  63. if (dbg_postorder)
  64. debug_postorder(ep);
  65. return info.nr;
  66. }
  67. //
  68. // Calculate the dominance tree following:
  69. // "A simple, fast dominance algorithm"
  70. // by K. D. Cooper, T. J. Harvey, and K. Kennedy.
  71. // cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf
  72. //
  73. static struct basic_block *intersect_dom(struct basic_block *doms[],
  74. struct basic_block *b1, struct basic_block *b2)
  75. {
  76. int f1 = b1->postorder_nr, f2 = b2->postorder_nr;
  77. while (f1 != f2) {
  78. while (f1 < f2) {
  79. b1 = doms[f1];
  80. f1 = b1->postorder_nr;
  81. }
  82. while (f2 < f1) {
  83. b2 = doms[f2];
  84. f2 = b2->postorder_nr;
  85. }
  86. }
  87. return b1;
  88. }
  89. static void debug_domtree(struct entrypoint *ep)
  90. {
  91. struct basic_block *bb = ep->entry->bb;
  92. printf("%s's idoms:\n", show_ident(ep->name->ident));
  93. FOR_EACH_PTR(ep->bbs, bb) {
  94. if (bb == ep->entry->bb)
  95. continue; // entry node has no idom
  96. printf("\t%s <- %s\n", show_label(bb), show_label(bb->idom));
  97. } END_FOR_EACH_PTR(bb);
  98. }
  99. void domtree_build(struct entrypoint *ep)
  100. {
  101. struct basic_block *entry = ep->entry->bb;
  102. struct basic_block **doms;
  103. struct basic_block *bb;
  104. unsigned int size;
  105. int max_level = 0;
  106. int changed;
  107. // First calculate the (reverse) postorder.
  108. // This will give use us:
  109. // - the links to do a reverse postorder traversal
  110. // - the order number for each block
  111. size = cfg_postorder(ep);
  112. // initialize the dominators array
  113. doms = calloc(size, sizeof(*doms));
  114. assert(entry->postorder_nr == size-1);
  115. doms[size-1] = entry;
  116. do {
  117. struct basic_block *b;
  118. changed = 0;
  119. FOR_EACH_PTR(ep->bbs, b) {
  120. struct basic_block *p;
  121. int bnr = b->postorder_nr;
  122. struct basic_block *new_idom = NULL;
  123. if (b == entry)
  124. continue; // ignore entry node
  125. FOR_EACH_PTR(b->parents, p) {
  126. unsigned int pnr = p->postorder_nr;
  127. if (!doms[pnr])
  128. continue;
  129. if (!new_idom) {
  130. new_idom = p;
  131. continue;
  132. }
  133. new_idom = intersect_dom(doms, p, new_idom);
  134. } END_FOR_EACH_PTR(p);
  135. assert(new_idom);
  136. if (doms[bnr] != new_idom) {
  137. doms[bnr] = new_idom;
  138. changed = 1;
  139. }
  140. } END_FOR_EACH_PTR(b);
  141. } while (changed);
  142. FOR_EACH_PTR(ep->bbs, bb) {
  143. free_ptr_list(&bb->doms);
  144. } END_FOR_EACH_PTR(bb);
  145. // set the idom links
  146. FOR_EACH_PTR(ep->bbs, bb) {
  147. struct basic_block *idom = doms[bb->postorder_nr];
  148. if (bb == entry)
  149. continue; // ignore entry node
  150. bb->idom = idom;
  151. add_bb(&idom->doms, bb);
  152. } END_FOR_EACH_PTR(bb);
  153. entry->idom = NULL;
  154. // set the dominance levels
  155. FOR_EACH_PTR(ep->bbs, bb) {
  156. struct basic_block *idom = bb->idom;
  157. int level = idom ? idom->dom_level + 1 : 0;
  158. bb->dom_level = level;
  159. if (max_level < level)
  160. max_level = level;
  161. } END_FOR_EACH_PTR(bb);
  162. ep->dom_levels = max_level + 1;
  163. free(doms);
  164. if (dbg_domtree)
  165. debug_domtree(ep);
  166. }
  167. // dt_dominates - does BB a dominates BB b?
  168. bool domtree_dominates(struct basic_block *a, struct basic_block *b)
  169. {
  170. if (a == b) // dominance is reflexive
  171. return true;
  172. if (a == b->idom)
  173. return true;
  174. if (b == a->idom)
  175. return false;
  176. // can't dominate if deeper in the DT
  177. if (a->dom_level >= b->dom_level)
  178. return false;
  179. // FIXME: can be faster if we have the DFS in-out numbers
  180. // walk up the dominator tree
  181. for (b = b->idom; b; b = b->idom) {
  182. if (b == a)
  183. return true;
  184. }
  185. return false;
  186. }