flowgraph.c

   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 }