graph.c

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