structures.c

   1 /**
   2  * Author: Humberto Naves (hsnaves@gmail.com)
   3  */
   4
   5 #include "code.h"
   6 #include "utils.h"
   7
   8 static
   9 struct ctrlstruct *alloc_ctrlstruct (struct basicblock *block, enum ctrltype type)
  10 {
  11   struct ctrlstruct *st = fixedpool_alloc (block->sub->code->ctrlspool);
  12   st->start = block;
  13   st->type = type;
  14   return st;
  15 }
  16
  17 static
  18 int mark_backward (struct basicblock *start, list worklist, int num)
  19 {
  20   struct basicblock *block;
  21   element ref;
  22   int count = 0;
  23
  24   while (list_size (worklist) != 0) {
  25     block = list_removetail (worklist);
  26     if (block->mark1 == num) continue;
  27     block->mark1 = num;
  28     count++;
  29
  30     ref = list_head (block->inrefs);
  31     while (ref) {
  32       struct basicedge *edge = element_getvalue (ref);
  33       struct basicblock *next = edge->from;
  34       ref = element_next (ref);
  35
  36       if (next->node.dfsnum < start->node.dfsnum)
  37         continue;
  38
  39       if (next->node.dfsnum >= block->node.dfsnum)
  40         if (!dom_isancestor (&block->node, &next->node) ||
  41             !dom_isancestor (&block->revnode, &next->revnode))
  42           continue;
  43
  44       if (next->mark1 != num) {
  45         list_inserthead (worklist, next);
  46       }
  47     }
  48   }
  49
  50   return count;
  51 }
  52
  53 static
  54 void mark_forward (struct basicblock *start, struct ctrlstruct *loop, int num, int count)
  55 {
  56   element el, ref;
  57
  58   el = start->node.blockel;
  59   while (el && count) {
  60     struct basicblock *block = element_getvalue (el);
  61     if (block->mark1 == num) {
  62       block->loopst = loop; count--;
  63       ref = list_head (block->outrefs);
  64       while (ref) {
  65         struct basicedge *edge = element_getvalue (ref);
  66         struct basicblock *next = edge->to;
  67         if (next->mark1 != num) {
  68           /* edge->type = EDGE_GOTO;
  69           next->status |= BLOCK_STAT_HASLABEL; */
  70           if (!loop->end) loop->end = next;
  71           if (list_size (loop->end->inrefs) < list_size (next->inrefs))
  72             loop->end = next;
  73         }
  74         ref = element_next (ref);
  75       }
  76     }
  77
  78     el = element_next (el);
  79   }
  80 }
  81
  82 static
  83 void mark_loop (struct ctrlstruct *loop, int num)
  84 {
  85   element el;
  86   list worklist;
  87   int count;
  88
  89   worklist = list_alloc (loop->start->sub->code->lstpool);
  90   el = list_head (loop->info.loopctrl.edges);
  91   while (el) {
  92     struct basicedge *edge = element_getvalue (el);
  93     struct basicblock *block = edge->from;
  94
  95     list_inserttail (worklist, block);
  96     el = element_next (el);
  97   }
  98   count = mark_backward (loop->start, worklist, num);
  99
 100   mark_forward (loop->start, loop, num, count);
 101   if (loop->end) {
 102     /* loop->end->status &= ~BLOCK_STAT_HASLABEL; */
 103     el = list_head (loop->end->inrefs);
 104     while (el) {
 105       struct basicedge *edge = element_getvalue (el);
 106       if (edge->from->loopst == loop)
 107         edge->type = EDGE_BREAK;
 108       el = element_next (el);
 109     }
 110   }
 111
 112   list_free (worklist);
 113 }
 114
 115 static
 116 void extract_loops (struct subroutine *sub)
 117 {
 118   struct basicblock *block;
 119   struct basicedge *edge;
 120   struct ctrlstruct *loop;
 121   element el, ref;
 122   int num = 0;
 123
 124   el = list_head (sub->dfsblocks);
 125   while (el) {
 126     block = element_getvalue (el);
 127
 128     loop = NULL;
 129     ref = list_head (block->inrefs);
 130     while (ref) {
 131       edge = element_getvalue (ref);
 132       if (edge->from->node.dfsnum >= block->node.dfsnum) {
 133         edge->type = EDGE_CONTINUE;
 134         if (!dom_isancestor (&block->node, &edge->from->node)) {
 135           error (__FILE__ ": graph of sub 0x%08X is not reducible (using goto)", sub->begin->address);
 136           edge->type = EDGE_INVALID;
 137           edge->to->status |= BLOCK_STAT_HASLABEL;
 138         } else if (block->loopst == edge->from->loopst) {
 139           if (!loop) {
 140             loop = alloc_ctrlstruct (block, CONTROL_LOOP);
 141             loop->info.loopctrl.edges = list_alloc (sub->code->lstpool);
 142           }
 143           list_inserttail (loop->info.loopctrl.edges, edge);
 144         }/* else {
 145           edge->type = EDGE_GOTO;
 146           edge->to->status |= BLOCK_STAT_HASLABEL;
 147         }*/
 148       }
 149       ref = element_next (ref);
 150     }
 151     if (loop)
 152       mark_loop (loop, ++num);
 153     el = element_next (el);
 154   }
 155 }
 156
 157 static
 158 void extract_returns (struct subroutine *sub)
 159 {
 160
 161 }
 162
 163 static
 164 int struct_isancestor (struct ctrlstruct *ancestor, struct ctrlstruct *st)
 165 {
 166   while (st) {
 167     if (st == ancestor) return TRUE;
 168     st = st->parent;
 169   }
 170   return FALSE;
 171 }
 172
 173 static
 174 void structure_search (struct basicblock *block, struct ctrlstruct *parentst, int blockcond)
 175 {
 176   block->st = parentst;
 177   block->mark1 = 1;
 178   block->blockcond = blockcond;
 179
 180   if (block->loopst) {
 181     if (block->loopst->start == block) {
 182       block->st = block->loopst;
 183       block->st->parent = parentst;
 184       block->st->identsize = parentst->identsize + 1;
 185     }
 186   }
 187
 188   if (block->status & BLOCK_STAT_ISSWITCH) {
 189     struct ctrlstruct *nst;
 190     element ref;
 191
 192     nst = alloc_ctrlstruct (block, CONTROL_SWITCH);
 193     nst->end = element_getvalue (block->revnode.dominator->blockel);
 194     nst->parent = block->st;
 195     nst->identsize = block->st->identsize + 1;
 196     block->ifst = nst;
 197
 198     ref = list_head (block->outrefs);
 199     while (ref) {
 200       struct basicedge *edge = element_getvalue (ref);
 201
 202       if (edge->type == EDGE_UNKNOWN) {
 203         edge->type = EDGE_CASE;
 204         if (!edge->to->mark1) {
 205           structure_search (edge->to, nst, edge->fromnum);
 206         } else {
 207           if (edge->to->st != nst) {
 208             edge->type = EDGE_GOTO;
 209             edge->to->status |= BLOCK_STAT_HASLABEL;
 210           }
 211         }
 212       }
 213       ref = element_next (ref);
 214     }
 215   } else if (list_size (block->outrefs) == 2) {
 216     struct basicblock *end;
 217     struct basicedge *edge1, *edge2;
 218
 219     end = element_getvalue (block->revnode.dominator->blockel);
 220     edge1 = list_tailvalue (block->outrefs);
 221     edge2 = list_headvalue (block->outrefs);
 222
 223     if (edge1->to != end) {
 224       if (edge1->to->mark1) {
 225         edge1->type = EDGE_GOTO;
 226         edge1->to->status |= BLOCK_STAT_HASLABEL;
 227       }
 228     }
 229
 230     if (edge2->to != end) {
 231       if (edge2->to->mark1) {
 232         edge2->type = EDGE_GOTO;
 233         edge2->to->status |= BLOCK_STAT_HASLABEL;
 234       }
 235     }
 236
 237     if (edge1->type == EDGE_UNKNOWN && edge2->type == EDGE_UNKNOWN) {
 238       struct ctrlstruct *nst = alloc_ctrlstruct (block, CONTROL_IF);
 239       nst->end = end;
 240       nst->parent = block->st;
 241       nst->identsize = block->st->identsize + 1;
 242       block->ifst = nst;
 243
 244       if (!end->mark1) {
 245         nst->info.ifctrl.endfollow = TRUE;
 246         end->mark1 = TRUE;
 247       } else {
 248         if (!struct_isancestor (end->st, block->st)) {
 249           nst->hasendgoto = TRUE;
 250           end->status |= BLOCK_STAT_HASLABEL;
 251         }
 252       }
 253
 254       if (edge1->to == end) {
 255         edge1->type = EDGE_IFEXIT;
 256       } else {
 257         edge1->type = EDGE_IFENTER;
 258         structure_search (edge1->to, nst, TRUE);
 259       }
 260
 261       if (edge2->to == end) {
 262         edge2->type = EDGE_IFEXIT;
 263       } else {
 264         if (edge2->to->mark1) {
 265           edge2->type = EDGE_GOTO;
 266           edge2->to->status |= BLOCK_STAT_HASLABEL;
 267         } else {
 268           edge2->type = EDGE_IFENTER;
 269           structure_search (edge2->to, nst, FALSE);
 270         }
 271       }
 272
 273       if (edge2->type != EDGE_IFEXIT) {
 274         if (edge1->type == EDGE_IFEXIT)
 275           block->status |= BLOCK_STAT_REVCOND;
 276         else
 277           block->status |= BLOCK_STAT_HASELSE;
 278       }
 279
 280       if (nst->info.ifctrl.endfollow) {
 281         end->mark1 = 0;
 282         structure_search (end, block->st, blockcond);
 283       }
 284
 285     } else if (edge1->type == EDGE_UNKNOWN || edge2->type == EDGE_UNKNOWN) {
 286       struct basicedge *edge;
 287
 288       if (edge1->type == EDGE_UNKNOWN) {
 289         block->status |= BLOCK_STAT_REVCOND;
 290         edge = edge1;
 291       } else {
 292         edge = edge2;
 293       }
 294
 295       if (edge->to == block->st->end && block->st->type == CONTROL_IF) {
 296         edge->type = EDGE_IFEXIT;
 297       } else {
 298         if (edge->to->mark1) {
 299           edge->type = EDGE_GOTO;
 300           edge->to->status |= BLOCK_STAT_HASLABEL;
 301         } else {
 302           edge->type = EDGE_NEXT;
 303           structure_search (edge->to, block->st, blockcond);
 304         }
 305       }
 306     }
 307   } else {
 308     struct basicedge *edge;
 309     edge = list_headvalue (block->outrefs);
 310     if (edge) {
 311       if (edge->type == EDGE_UNKNOWN) {
 312         if (edge->to == block->st->end && block->st->type == CONTROL_IF) {
 313           edge->type = EDGE_IFEXIT;
 314         } else {
 315           if (edge->to->mark1) {
 316             edge->type = EDGE_GOTO;
 317             edge->to->status |= BLOCK_STAT_HASLABEL;
 318           } else {
 319             edge->type = EDGE_NEXT;
 320             structure_search (edge->to, block->st, blockcond);
 321           }
 322         }
 323       }
 324     }
 325   }
 326
 327   if (block->loopst) {
 328     if (block->loopst->start == block && block->loopst->end) {
 329       if (block->loopst->end->mark1) {
 330         block->loopst->hasendgoto = TRUE;
 331         block->loopst->end->status |= BLOCK_STAT_HASLABEL;
 332       } else {
 333         structure_search (block->loopst->end, parentst, blockcond);
 334       }
 335     }
 336   }
 337 }
 338
 339 void reset_marks (struct subroutine *sub)
 340 {
 341   element el = list_head (sub->blocks);
 342   while (el) {
 343     struct basicblock *block = element_getvalue (el);
 344     block->mark1 = block->mark2 = 0;
 345     el = element_next (el);
 346   }
 347 }
 348
 349 void extract_structures (struct subroutine *sub)
 350 {
 351   element el;
 352   struct ctrlstruct *st = fixedpool_alloc (sub->code->ctrlspool);
 353
 354   st->type = CONTROL_MAIN;
 355   st->start = sub->startblock;
 356   st->end = sub->endblock;
 357
 358   reset_marks (sub);
 359   extract_loops (sub);
 360
 361   extract_returns (sub);
 362
 363   reset_marks (sub);
 364   el = list_head (sub->blocks);
 365   while (el) {
 366     struct basicblock *block = element_getvalue (el);
 367     if (!block->mark1)
 368       structure_search (block, st, 0);
 369     el = element_next (el);
 370   }
 371 }