structures.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5
   6 static
   7 void mark_backward (struct subroutine *sub, struct basicblock *start,
   8                     struct basicblock *block, int num, int *count)
   9 {
  10   element el, ref;
  11   int remaining = 1;
  12
  13   block->mark1 = num;
  14   el = block->node.blockel;
  15   while (el && remaining) {
  16     struct basicblock *block = element_getvalue (el);
  17     if (block == start) break;
  18     if (block->mark1 == num) {
  19       remaining--;
  20       ref = list_head (block->inrefs);
  21       while (ref) {
  22         struct basicedge *edge = element_getvalue (ref);
  23         struct basicblock *next = edge->from;
  24         ref = element_next (ref);
  25
  26         if (next->node.dfsnum >= block->node.dfsnum)
  27           if (!dom_isancestor (&block->node, &next->node) ||
  28               !dom_isancestor (&block->revnode, &next->revnode))
  29             continue;
  30         if (next->mark1 != num) {
  31           remaining++;
  32           (*count)++;
  33         }
  34         next->mark1 = num;
  35       }
  36     }
  37
  38     el = element_previous (el);
  39   }
  40 }
  41
  42 static
  43 void mark_forward (struct subroutine *sub, struct basicblock *start,
  44                    struct ctrlstruct *loop, int num, int count)
  45 {
  46   element el, ref;
  47
  48   el = start->node.blockel;
  49   while (el && count) {
  50     struct basicblock *block = element_getvalue (el);
  51     if (block->mark1 == num) {
  52       block->loopst = loop; count--;
  53       ref = list_head (block->outrefs);
  54       while (ref) {
  55         struct basicedge *edge = element_getvalue (ref);
  56         struct basicblock *next = edge->to;
  57         if (next->mark1 != num) {
  58           edge->type = EDGE_GOTO;
  59           next->haslabel = TRUE;
  60           if (!loop->end) loop->end = next;
  61           if (list_size (loop->end->inrefs) < list_size (next->inrefs))
  62             loop->end = next;
  63         }
  64         ref = element_next (ref);
  65       }
  66     }
  67
  68     el = element_next (el);
  69   }
  70 }
  71
  72
  73 static
  74 void mark_loop (struct subroutine *sub, struct ctrlstruct *loop)
  75 {
  76   element el;
  77   int num = ++sub->temp;
  78   int count = 0;
  79
  80   el = list_head (loop->info.loopctrl.edges);
  81   while (el) {
  82     struct basicedge *edge = element_getvalue (el);
  83     struct basicblock *block = edge->from;
  84
  85     if (block->mark1 != num) {
  86       mark_backward (sub, loop->start, block, num, &count);
  87     }
  88     el = element_next (el);
  89   }
  90
  91   mark_forward (sub, loop->start, loop, num, count);
  92
  93   if (loop->end) {
  94     loop->end->haslabel = FALSE;
  95     el = list_head (loop->end->inrefs);
  96     while (el) {
  97       struct basicedge *edge = element_getvalue (el);
  98       struct basicblock *block = edge->from;
  99       if (block->loopst == loop) 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 ctrlstruct *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           if (!loop) {
 129             loop = fixedpool_alloc (sub->code->ctrlspool);
 130             loop->start = block;
 131             loop->type = CONTROL_LOOP;
 132             loop->info.loopctrl.edges = list_alloc (sub->code->lstpool);
 133           }
 134           list_inserttail (loop->info.loopctrl.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_branches (struct subroutine *sub)
 149 {
 150   struct basicblock *block;
 151   struct ctrlstruct *st;
 152   list unresolvedifs;
 153   element el;
 154
 155   unresolvedifs = 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     if (hasswitch) {
 168       st = fixedpool_alloc (sub->code->ctrlspool);
 169       st->type = CONTROL_SWITCH;
 170       block->st = st;
 171
 172     } else if (list_size (block->outrefs) == 2) {
 173       struct basicedge *edge1, *edge2;
 174
 175       st = fixedpool_alloc (sub->code->ctrlspool);
 176       st->type = CONTROL_IF;
 177       block->st = st;
 178
 179       edge1 = list_headvalue (block->outrefs);
 180       edge2 = list_tailvalue (block->outrefs);
 181       if (edge1->type == EDGE_UNKNOWN && edge2->type == EDGE_UNKNOWN) {
 182         element domel;
 183
 184         list_inserthead (unresolvedifs, block);
 185         domel = list_head (block->node.domchildren);
 186         while (domel) {
 187           struct basicblocknode *dom = element_getvalue (domel);
 188           struct basicblock *domblock = element_getvalue (dom->blockel);
 189
 190           if (list_size (domblock->inrefs) > 1) {
 191             block->st->info.ifctrl.isoutermost = TRUE;
 192             while (list_size (unresolvedifs) != 0) {
 193               struct basicblock *ifblock = list_removehead (unresolvedifs);
 194               ifblock->st->end = domblock;
 195             }
 196             break;
 197           }
 198           domel = element_next (domel);
 199         }
 200       } else if (edge1->type == EDGE_UNKNOWN || edge2->type == EDGE_UNKNOWN) {
 201         if (edge1->type == EDGE_UNKNOWN) {
 202           edge1->type = EDGE_IFEXIT;
 203           st->end = edge1->to;
 204         } else {
 205           edge2->type = EDGE_IFEXIT;
 206           st->end = edge2->to;
 207         }
 208
 209       }
 210     }
 211
 212     el = element_previous (el);
 213   }
 214
 215   list_free (unresolvedifs);
 216 }
 217
 218 static
 219 void structure_search (struct basicblock *block, int identsize, struct ctrlstruct *ifst)
 220 {
 221   struct basicedge *edge;
 222   struct basicblock *ifend = NULL;
 223   element ref;
 224
 225   if (ifst)
 226     ifend = ifst->end;
 227
 228   if (block->st)
 229     if (block->st->end)
 230       ifend = block->st->end;
 231
 232   block->mark1 = 1;
 233
 234   if (block->loopst) {
 235     if (block->loopst->start == block) {
 236       identsize++;
 237       if (block->loopst->end) {
 238         if (!block->loopst->end->mark1)
 239           structure_search (block->loopst->end, identsize - 1, ifst);
 240         else {
 241           block->loopst->end->haslabel = TRUE;
 242           block->loopst->hasendgoto = TRUE;
 243         }
 244       }
 245     }
 246   }
 247
 248   if (block->st) {
 249     if (block->st->end && block->st->info.ifctrl.isoutermost) {
 250       if (!block->st->end->mark1)
 251         structure_search (block->st->end, identsize, ifst);
 252       else {
 253         block->st->end->haslabel = TRUE;
 254         block->st->hasendgoto = TRUE;
 255       }
 256     }
 257   }
 258
 259   block->identsize = identsize;
 260
 261   ref = list_head (block->outrefs);
 262   while (ref) {
 263     edge = element_getvalue (ref);
 264     if (edge->type == EDGE_UNKNOWN) {
 265       if (edge->to->loopst != block->loopst) {
 266         if (edge->to->loopst) {
 267           if (edge->to->loopst->start != edge->to) {
 268             edge->type = EDGE_GOTO;
 269             edge->to->haslabel = TRUE;
 270           }
 271         } else {
 272           edge->type = EDGE_GOTO;
 273           edge->to->haslabel = TRUE;
 274         }
 275       }
 276     }
 277
 278     if (edge->type == EDGE_UNKNOWN) {
 279       if (edge->to == ifend) {
 280         edge->type = EDGE_IFEXIT;
 281       } else {
 282         if (edge->to->mark1) {
 283           edge->type = EDGE_GOTO;
 284           edge->to->haslabel = TRUE;
 285         } else {
 286           edge->type = EDGE_FOLLOW;
 287           if (block->st) {
 288             structure_search (edge->to, identsize + 1, block->st);
 289           } else {
 290             structure_search (edge->to, identsize, ifst);
 291           }
 292         }
 293       }
 294     }
 295     ref = element_next (ref);
 296   }
 297 }
 298
 299 void reset_marks (struct subroutine *sub)
 300 {
 301   element el = list_head (sub->blocks);
 302   while (el) {
 303     struct basicblock *block = element_getvalue (el);
 304     block->mark1 = block->mark2 = 0;
 305     el = element_next (el);
 306   }
 307 }
 308
 309 void extract_structures (struct subroutine *sub)
 310 {
 311   element el;
 312   sub->temp = 0;
 313   reset_marks (sub);
 314
 315   extract_loops (sub);
 316   extract_branches (sub);
 317
 318   reset_marks (sub);
 319   el = list_head (sub->blocks);
 320   while (el) {
 321     struct basicblock *block = element_getvalue (el);
 322     if (!block->mark1)
 323       structure_search (block, 0, NULL);
 324     el = element_next (el);
 325   }
 326 }