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