graph.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5 static
   6 void dfs_step (struct basicblock *block, int reverse)
   7 {
   8   struct basicblock *next;
   9   struct basicblocknode *node, *nextnode;
  10   list refs, out;
  11   element el;
  12
  13   if (reverse) {
  14     node = &block->revnode;
  15     refs = block->inrefs;
  16     out = block->sub->revdfsblocks;
  17   } else {
  18     node = &block->node;
  19     refs = block->outrefs;
  20     out = block->sub->dfsblocks;
  21   }
  22   node->dfsnum = -1;
  23
  24   el = list_head (refs);
  25   while (el) {
  26     struct basicedge *edge;
  27     edge = element_getvalue (el);
  28     if (reverse) {
  29       next = edge->from;
  30       nextnode = &next->revnode;
  31     } else {
  32       next = edge->to;
  33       nextnode = &next->node;
  34     }
  35
  36     if (!nextnode->dfsnum) {
  37       nextnode->parent = node;
  38       list_inserttail (node->children, nextnode);
  39       dfs_step (next, reverse);
  40     }
  41     el = element_next (el);
  42   }
  43
  44   node->dfsnum = block->sub->temp--;
  45   node->blockel = list_inserthead (out, block);
  46 }
  47
  48 static
  49 int cfg_dfs (struct subroutine *sub, int reverse)
  50 {
  51   struct basicblock *start;
  52   sub->temp = list_size (sub->blocks);
  53   start = reverse ? sub->endblock : sub->startblock;
  54
  55   dfs_step (start, reverse);
  56   return (sub->temp == 0);
  57 }
  58
  59 int dom_isancestor (struct basicblocknode *ancestor, struct basicblocknode *node)
  60 {
  61   return (ancestor->domdfsnum.first <= node->domdfsnum.first &&
  62           ancestor->domdfsnum.last <= node->domdfsnum.last);
  63 }
  64
  65 struct basicblocknode *dom_common (struct basicblocknode *n1, struct basicblocknode *n2)
  66 {
  67   while (n1 != n2) {
  68     while (n1->dfsnum > n2->dfsnum) {
  69       n1 = n1->dominator;
  70     }
  71     while (n2->dfsnum > n1->dfsnum) {
  72       n2 = n2->dominator;
  73     }
  74   }
  75   return n1;
  76 }
  77
  78 static
  79 void dom_dfs_step (struct basicblocknode *node, struct intpair *domdfsnum)
  80 {
  81   struct basicblocknode *next;
  82   element el;
  83
  84   node->domdfsnum.first = (domdfsnum->first)++;
  85   el = list_head (node->domchildren);
  86   while (el) {
  87     next = element_getvalue (el);
  88     if (!next->domdfsnum.first)
  89       dom_dfs_step (next, domdfsnum);
  90     el = element_next (el);
  91   }
  92   node->domdfsnum.last = (domdfsnum->last)--;
  93 }
  94
  95 static
  96 void cfg_dominance (struct subroutine *sub, int reverse)
  97 {
  98   struct basicblock *start;
  99   struct basicblocknode *startnode;
 100   struct intpair domdfsnum;
 101   int changed = TRUE;
 102   list blocks, refs;
 103   element el;
 104
 105   if (reverse) {
 106     blocks = sub->revdfsblocks;
 107     start = sub->endblock;
 108     startnode = start->revnode.dominator = &start->revnode;
 109   } else {
 110     blocks = sub->dfsblocks;
 111     start = sub->startblock;
 112     startnode = start->node.dominator = &start->node;
 113   }
 114
 115   while (changed) {
 116     changed = FALSE;
 117     el = list_head (blocks);
 118     el = element_next (el);
 119     while (el) {
 120       struct basicblock *block;
 121       struct basicblocknode *node, *dom = NULL;
 122       element ref;
 123
 124       block = element_getvalue (el);
 125       refs = (reverse) ? block->outrefs : block->inrefs;
 126       ref = list_head (refs);
 127       while (ref) {
 128         struct basicblock *bref;
 129         struct basicblocknode *brefnode;
 130         struct basicedge *edge;
 131
 132         edge = element_getvalue (ref);
 133         if (reverse) {
 134           bref = edge->to;
 135           brefnode = &bref->revnode;
 136         } else {
 137           bref = edge->from;
 138           brefnode = &bref->node;
 139         }
 140
 141         if (brefnode->dominator) {
 142           if (!dom) {
 143             dom = brefnode;
 144           } else {
 145             dom = dom_common (dom, brefnode);
 146           }
 147         }
 148
 149         ref = element_next (ref);
 150       }
 151
 152       node = (reverse) ? &block->revnode : &block->node;
 153       if (dom != node->dominator) {
 154         node->dominator = dom;
 155         changed = TRUE;
 156       }
 157
 158       el = element_next (el);
 159     }
 160   }
 161
 162   el = list_head (blocks);
 163   while (el) {
 164     struct basicblock *block;
 165     struct basicblocknode *node;
 166
 167     block = element_getvalue (el);
 168     node = (reverse) ? &block->revnode : &block->node;
 169     list_inserttail (node->dominator->domchildren, node);
 170
 171     el = element_next (el);
 172   }
 173
 174   domdfsnum.first = 0;
 175   domdfsnum.last = list_size (blocks);
 176   dom_dfs_step (startnode, &domdfsnum);
 177 }
 178
 179 static
 180 void cfg_frontier (struct subroutine *sub, int reverse)
 181 {
 182   struct basicblock *block;
 183   struct basicblocknode *blocknode, *runner;
 184   element el, ref;
 185   list refs;
 186
 187   el = (reverse) ? list_head (sub->revdfsblocks) : list_head (sub->dfsblocks);
 188
 189   while (el) {
 190     block = element_getvalue (el);
 191     if (reverse) {
 192       refs = block->outrefs;
 193       blocknode = &block->revnode;
 194     } else {
 195       refs = block->inrefs;
 196       blocknode = &block->node;
 197     }
 198     if (list_size (refs) >= 2) {
 199       ref = list_head (refs);
 200       while (ref) {
 201         struct basicedge *edge = element_getvalue (ref);
 202         runner = (reverse) ? &edge->to->revnode : &edge->from->node;
 203         while (runner != blocknode->dominator) {
 204           list_inserttail (runner->frontier, blocknode);
 205           runner = runner->dominator;
 206         }
 207         ref = element_next (ref);
 208       }
 209     }
 210     el = element_next (el);
 211   }
 212 }
 213
 214 void cfg_traverse (struct subroutine *sub, int reverse)
 215 {
 216   if (!reverse) {
 217     if (!cfg_dfs (sub, FALSE)) {
 218       error (__FILE__ ": unreachable code at subroutine 0x%08X", sub->begin->address);
 219       sub->haserror = TRUE;
 220       return;
 221     }
 222   } else {
 223     if (!cfg_dfs (sub, TRUE)) {
 224       error (__FILE__ ": infinite loop at subroutine 0x%08X", sub->begin->address);
 225       sub->haserror = TRUE;
 226       return;
 227     }
 228   }
 229
 230   cfg_dominance (sub, reverse);
 231   cfg_frontier (sub, reverse);
 232 }