structures.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5
   6 static
   7 void mark_backward (struct subroutine *sub, struct basicblock *block, int num, int end)
   8 {
   9   element el, ref;
  10   int count = 1;
  11
  12   el = block->node.blockel;
  13   while (el && count) {
  14     struct basicblock *block = element_getvalue (el);
  15     if (block->node.dfsnum < end) break;
  16     if (block->mark1 == num) {
  17       count--;
  18       ref = list_head (block->inrefs);
  19       while (ref) {
  20         struct basicedge *edge = element_getvalue (ref);
  21         struct basicblock *next = edge->from;
  22         if (next->node.dfsnum >= end &&
  23             next->node.dfsnum < block->node.dfsnum) {
  24           if (next->mark1 != num) count++;
  25           next->mark1 = num;
  26         }
  27         ref = element_next (ref);
  28       }
  29     }
  30
  31     el = element_previous (el);
  32   }
  33 }
  34
  35 static
  36 void mark_forward (struct subroutine *sub, struct basicblock *block,
  37                    struct loopstructure *loop, int num, int end)
  38 {
  39   element el, ref;
  40
  41   el = block->node.blockel;
  42   while (el) {
  43     struct basicblock *block = element_getvalue (el);
  44     if (block->node.dfsnum > end) break;
  45     if (block->mark2 == num) {
  46       block->loopst = loop;
  47       ref = list_head (block->outrefs);
  48       while (ref) {
  49         struct basicedge *edge = element_getvalue (ref);
  50         struct basicblock *next = edge->to;
  51         if (next->node.dfsnum > block->node.dfsnum) {
  52           if (next->mark1 == num) next->mark2 = num;
  53           else {
  54             if (!loop->end) loop->end = next;
  55             if (list_size (loop->end->inrefs) < list_size (next->inrefs))
  56               loop->end = next;
  57           }
  58         }
  59         ref = element_next (ref);
  60       }
  61     }
  62
  63     el = element_next (el);
  64   }
  65 }
  66
  67
  68 static
  69 void mark_loop (struct subroutine *sub, struct loopstructure *loop)
  70 {
  71   element el;
  72   int num = ++sub->temp;
  73   int maxdfs = -1;
  74
  75   el = list_head (loop->edges);
  76   while (el) {
  77     struct basicedge *edge = element_getvalue (el);
  78     struct basicblock *block = edge->from;
  79
  80     if (maxdfs < block->node.dfsnum)
  81       maxdfs = block->node.dfsnum;
  82
  83     if (block->mark1 != num) {
  84       block->mark1 = num;
  85       mark_backward (sub, block, num, loop->start->node.dfsnum);
  86     }
  87     el = element_next (el);
  88   }
  89
  90   loop->start->mark2 = num;
  91   mark_forward (sub, loop->start, loop, num, maxdfs);
  92
  93   if (loop->end) {
  94     el = list_head (loop->end->inrefs);
  95     while (el) {
  96       struct basicedge *edge = element_getvalue (el);
  97       struct basicblock *block = edge->from;
  98       if (block->loopst == loop)
  99         edge->type = EDGE_BREAK;
 100       el = element_next (el);
 101     }
 102   }
 103 }
 104
 105 static
 106 void extract_loops (struct subroutine *sub)
 107 {
 108   struct basicblock *block;
 109   struct basicedge *edge;
 110   struct loopstructure *loop;
 111   element el, ref;
 112
 113   el = list_head (sub->dfsblocks);
 114   while (el) {
 115     block = element_getvalue (el);
 116
 117     loop = NULL;
 118     ref = list_head (block->inrefs);
 119     while (ref) {
 120       edge = element_getvalue (ref);
 121       if (edge->from->node.dfsnum >= block->node.dfsnum) {
 122         edge->type = EDGE_CONTINUE;
 123         if (!dom_isancestor (&block->node, &edge->from->node)) {
 124           error (__FILE__ ": graph of sub 0x%08X is not reducible (using goto)", sub->begin->address);
 125           edge->type = EDGE_GOTO;
 126           edge->to->haslabel = TRUE;
 127         } else if (block->loopst == edge->from->loopst ||
 128             dom_isancestor (&block->revnode, &edge->from->revnode)) {
 129           if (!loop) {
 130             loop = fixedpool_alloc (sub->code->loopspool);
 131             loop->start = block;
 132             loop->edges = list_alloc (sub->code->lstpool);
 133           }
 134           list_inserttail (loop->edges, edge);
 135         } else {
 136           edge->type = EDGE_GOTO;
 137           edge->to->haslabel = TRUE;
 138         }
 139       }
 140       ref = element_next (ref);
 141     }
 142     if (loop) mark_loop (sub, loop);
 143     el = element_next (el);
 144   }
 145 }
 146
 147 static
 148 void extract_ifs (struct subroutine *sub)
 149 {
 150   struct basicblock *block;
 151   struct ifstructure *ifst;
 152   list unresolved;
 153   element el;
 154
 155   unresolved = list_alloc (sub->code->lstpool);
 156
 157   el = list_tail (sub->dfsblocks);
 158   while (el) {
 159     int hasswitch = FALSE;
 160     block = element_getvalue (el);
 161
 162     if (block->type == BLOCK_SIMPLE) {
 163       if (block->info.simple.jumploc) {
 164         if (block->info.simple.jumploc->cswitch)
 165           hasswitch = TRUE;
 166       }
 167     }
 168
 169     if (list_size (block->outrefs) == 2 && !hasswitch) {
 170       struct basicedge *edge1, *edge2;
 171
 172       ifst = fixedpool_alloc (sub->code->ifspool);
 173       block->ifst = ifst;
 174
 175       edge1 = list_headvalue (block->outrefs);
 176       edge2 = list_tailvalue (block->outrefs);
 177       if (edge1->type == EDGE_UNKNOWN || edge2->type == EDGE_UNKNOWN) {
 178         element domel;
 179
 180         list_inserthead (unresolved, block);
 181         domel = list_head (block->node.domchildren);
 182         while (domel) {
 183           int incount = 0;
 184           struct basicblocknode *dom = element_getvalue (domel);
 185           struct basicblock *domblock = element_getvalue (dom->blockel);
 186           element ref;
 187
 188           ref = list_head (domblock->inrefs);
 189           while (ref) {
 190             struct basicedge *edge = element_getvalue (ref);
 191             if (edge->from->node.dfsnum < domblock->node.dfsnum)
 192               incount++;
 193             ref = element_next (ref);
 194           }
 195
 196           if (incount > 1) {
 197             block->ifst->outermost = TRUE;
 198             while (list_size (unresolved) != 0) {
 199               struct basicblock *ifblock = list_removehead (unresolved);
 200               ifblock->ifst->end = domblock;
 201             }
 202             break;
 203           }
 204           domel = element_next (domel);
 205         }
 206       }
 207     }
 208
 209     el = element_previous (el);
 210   }
 211
 212   list_free (unresolved);
 213 }
 214
 215 static
 216 void structure_search (struct basicblock *block, int identsize, struct ifstructure *ifst)
 217 {
 218   struct basicedge *edge;
 219   struct basicblock *ifend = NULL;
 220   element ref;
 221
 222   if (ifst)
 223     ifend = ifst->end;
 224
 225   if (block->ifst)
 226     if (block->ifst->end)
 227       ifend = block->ifst->end;
 228
 229   block->mark1 = 1;
 230
 231   if (block->loopst) {
 232     if (block->loopst->start == block) {
 233       identsize++;
 234       if (block->loopst->end) {
 235         if (!block->loopst->end->mark1)
 236           structure_search (block->loopst->end, identsize - 1, ifst);
 237         else {
 238           block->loopst->end->haslabel = TRUE;
 239           block->loopst->hasendgoto = TRUE;
 240         }
 241       }
 242     }
 243   }
 244
 245   if (block->ifst) {
 246     if (block->ifst->end && block->ifst->outermost) {
 247       if (!block->ifst->end->mark1)
 248         structure_search (block->ifst->end, identsize, ifst);
 249       else {
 250         block->ifst->end->haslabel = TRUE;
 251         block->ifst->hasendgoto = TRUE;
 252       }
 253     }
 254   }
 255
 256   block->identsize = identsize;
 257
 258   ref = list_head (block->outrefs);
 259   while (ref) {
 260     edge = element_getvalue (ref);
 261     if (edge->type == EDGE_UNKNOWN) {
 262       if (edge->to->loopst != block->loopst) {
 263         if (edge->to->loopst) {
 264           if (edge->to->loopst->start != edge->to) {
 265             edge->type = EDGE_GOTO;
 266             edge->to->haslabel = TRUE;
 267           }
 268         } else {
 269           edge->type = EDGE_GOTO;
 270           edge->to->haslabel = TRUE;
 271         }
 272       }
 273     }
 274
 275     if (edge->type == EDGE_UNKNOWN) {
 276       if (edge->to == ifend) {
 277         edge->type = EDGE_IFEXIT;
 278       } else {
 279         if (edge->to->mark1) {
 280           edge->type = EDGE_GOTO;
 281           edge->to->haslabel = TRUE;
 282         } else {
 283           edge->type = EDGE_FOLLOW;
 284           if (block->ifst) {
 285             structure_search (edge->to, identsize + 1, block->ifst);
 286           } else {
 287             structure_search (edge->to, identsize, ifst);
 288           }
 289         }
 290       }
 291     }
 292     ref = element_next (ref);
 293   }
 294 }
 295
 296 void reset_marks (struct subroutine *sub)
 297 {
 298   element el = list_head (sub->blocks);
 299   while (el) {
 300     struct basicblock *block = element_getvalue (el);
 301     block->mark1 = block->mark2 = 0;
 302     el = element_next (el);
 303   }
 304 }
 305
 306 void extract_structures (struct subroutine *sub)
 307 {
 308   element el;
 309   sub->temp = 0;
 310   reset_marks (sub);
 311
 312   extract_loops (sub);
 313   extract_ifs (sub);
 314
 315   reset_marks (sub);
 316   el = list_head (sub->blocks);
 317   while (el) {
 318     struct basicblock *block = element_getvalue (el);
 319     if (!block->mark1)
 320       structure_search (block, 0, NULL);
 321     el = element_next (el);
 322   }
 323 }