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_step (struct basicblock *block)
 159 {
 160   element ref;
 161   struct basicedge *edge;
 162
 163   block->status &= ~BLOCK_STAT_HASLABEL;
 164   ref = list_head (block->inrefs);
 165   while (ref) {
 166     edge = element_getvalue (ref);
 167     edge->type = EDGE_RETURN;
 168     if (list_size (edge->from->outrefs) == 1) {
 169       extract_returns_step (edge->from);
 170     }
 171     ref = element_next (ref);
 172   }
 173 }
 174
 175 static
 176 void extract_returns (struct subroutine *sub)
 177 {
 178   extract_returns_step (sub->endblock);
 179 }
 180
 181 static
 182 void structure_search (struct basicblock *block, struct ctrlstruct *parentst, int blockcond)
 183 {
 184   block->st = parentst;
 185   block->mark1 = 1;
 186   block->blockcond = blockcond;
 187
 188   if (block->loopst) {
 189     if (block->loopst->start == block) {
 190       if (block->loopst->end) {
 191         if (block->loopst->end->mark1) {
 192           if (parentst->end != block->loopst->end) {
 193             block->loopst->hasendgoto = TRUE;
 194             block->loopst->end->status |= BLOCK_STAT_HASLABEL;
 195           }
 196         } else {
 197           block->loopst->endfollow = TRUE;
 198           structure_search (block->loopst->end, parentst, blockcond);
 199         }
 200       }
 201
 202       block->st = block->loopst;
 203       block->st->parent = parentst;
 204       block->st->identsize = parentst->identsize + 1;
 205     }
 206   }
 207
 208   if (block->status & BLOCK_STAT_ISSWITCH) {
 209     struct ctrlstruct *nst;
 210     element ref;
 211
 212     nst = alloc_ctrlstruct (block, CONTROL_SWITCH);
 213     nst->end = element_getvalue (block->revnode.dominator->blockel);
 214     nst->parent = block->st;
 215     nst->identsize = block->st->identsize + 1;
 216     block->ifst = nst;
 217
 218     ref = list_head (block->outrefs);
 219     while (ref) {
 220       struct basicedge *edge = element_getvalue (ref);
 221
 222       if (edge->type == EDGE_UNKNOWN) {
 223         edge->type = EDGE_CASE;
 224         if (!edge->to->mark1) {
 225           structure_search (edge->to, nst, edge->fromnum);
 226         } else {
 227           if (edge->to->st != nst) {
 228             edge->type = EDGE_GOTO;
 229             edge->to->status |= BLOCK_STAT_HASLABEL;
 230           }
 231         }
 232       }
 233       ref = element_next (ref);
 234     }
 235   } else if (list_size (block->outrefs) == 2) {
 236     struct basicblock *end;
 237     struct basicedge *edge1, *edge2;
 238
 239     end = element_getvalue (block->revnode.dominator->blockel);
 240     edge1 = list_tailvalue (block->outrefs);
 241     edge2 = list_headvalue (block->outrefs);
 242
 243     if (edge1->to != end && edge1->to->mark1 && edge1->type == EDGE_UNKNOWN) {
 244       edge1->type = EDGE_GOTO;
 245       edge1->to->status |= BLOCK_STAT_HASLABEL;
 246     }
 247
 248     if (edge2->to != end && edge2->to->mark1 && edge2->type == EDGE_UNKNOWN) {
 249       edge2->type = EDGE_GOTO;
 250       edge2->to->status |= BLOCK_STAT_HASLABEL;
 251     }
 252
 253     if (edge1->type == EDGE_UNKNOWN && edge2->type == EDGE_UNKNOWN) {
 254       struct ctrlstruct *nst = alloc_ctrlstruct (block, CONTROL_IF);
 255       nst->end = end;
 256       nst->parent = block->st;
 257       nst->identsize = block->st->identsize + 1;
 258       block->ifst = nst;
 259
 260       if (!end->mark1) {
 261         nst->endfollow = TRUE;
 262         end->mark1 = TRUE;
 263       } else {
 264         if (block->st->end != end) {
 265           nst->hasendgoto = TRUE;
 266           end->status |= BLOCK_STAT_HASLABEL;
 267         }
 268       }
 269
 270       if (edge1->to == end) {
 271         edge1->type = EDGE_IFEXIT;
 272       } else {
 273         edge1->type = EDGE_IFENTER;
 274         structure_search (edge1->to, nst, TRUE);
 275       }
 276
 277       if (edge2->to == end) {
 278         edge2->type = EDGE_IFEXIT;
 279       } else {
 280         if (edge2->to->mark1) {
 281           edge2->type = EDGE_GOTO;
 282           edge2->to->status |= BLOCK_STAT_HASLABEL;
 283         } else {
 284           edge2->type = EDGE_IFENTER;
 285           structure_search (edge2->to, nst, FALSE);
 286         }
 287       }
 288
 289       if (edge2->type != EDGE_IFEXIT) {
 290         if (edge1->type == EDGE_IFEXIT)
 291           block->status |= BLOCK_STAT_REVCOND;
 292         else
 293           block->status |= BLOCK_STAT_HASELSE;
 294       }
 295
 296       if (nst->endfollow) {
 297         end->mark1 = 0;
 298         structure_search (end, block->st, blockcond);
 299       }
 300
 301     } else if (edge1->type == EDGE_UNKNOWN || edge2->type == EDGE_UNKNOWN) {
 302       struct basicedge *edge;
 303
 304       if (edge1->type == EDGE_UNKNOWN) {
 305         block->status |= BLOCK_STAT_REVCOND;
 306         edge = edge1;
 307       } else {
 308         edge = edge2;
 309       }
 310
 311       if (edge->to == block->st->end && block->st->type == CONTROL_IF) {
 312         edge->type = EDGE_IFEXIT;
 313       } else {
 314         if (edge->to->mark1) {
 315           edge->type = EDGE_GOTO;
 316           edge->to->status |= BLOCK_STAT_HASLABEL;
 317         } else {
 318           edge->type = EDGE_NEXT;
 319           structure_search (edge->to, block->st, blockcond);
 320         }
 321       }
 322     }
 323   } else {
 324     struct basicedge *edge;
 325     edge = list_headvalue (block->outrefs);
 326     if (edge) {
 327       if (edge->type == EDGE_UNKNOWN) {
 328         if (edge->to == block->st->end && block->st->type == CONTROL_IF) {
 329           edge->type = EDGE_IFEXIT;
 330         } else {
 331           if (edge->to->mark1) {
 332             edge->type = EDGE_GOTO;
 333             edge->to->status |= BLOCK_STAT_HASLABEL;
 334           } else {
 335             edge->type = EDGE_NEXT;
 336             structure_search (edge->to, block->st, blockcond);
 337           }
 338         }
 339       }
 340     }
 341   }
 342 }
 343
 344 void reset_marks (struct subroutine *sub)
 345 {
 346   element el = list_head (sub->blocks);
 347   while (el) {
 348     struct basicblock *block = element_getvalue (el);
 349     block->mark1 = block->mark2 = 0;
 350     el = element_next (el);
 351   }
 352 }
 353
 354 void extract_structures (struct subroutine *sub)
 355 {
 356   element el;
 357   struct ctrlstruct *st = fixedpool_alloc (sub->code->ctrlspool);
 358
 359   st->type = CONTROL_MAIN;
 360   st->start = sub->startblock;
 361   st->end = sub->endblock;
 362
 363   reset_marks (sub);
 364   extract_loops (sub);
 365
 366   /* extract_returns (sub); */
 367
 368   reset_marks (sub);
 369   el = list_head (sub->blocks);
 370   while (el) {
 371     struct basicblock *block = element_getvalue (el);
 372     if (!block->mark1)
 373       structure_search (block, st, 0);
 374     el = element_next (el);
 375   }
 376 }