controlflow.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5 static
   6 struct basicblock *alloc_block (struct subroutine *sub)
   7 {
   8   struct basicblock *block;
   9   block = fixedpool_alloc (sub->code->blockspool);
  10
  11   block->inrefs = list_alloc (sub->code->lstpool);
  12   block->outrefs = list_alloc (sub->code->lstpool);
  13   block->node.children = list_alloc (sub->code->lstpool);
  14   block->revnode.children = list_alloc (sub->code->lstpool);
  15   block->node.domchildren = list_alloc (sub->code->lstpool);
  16   block->revnode.domchildren = list_alloc (sub->code->lstpool);
  17   block->node.frontier = list_alloc (sub->code->lstpool);
  18   block->revnode.frontier = list_alloc (sub->code->lstpool);
  19   block->sub = sub;
  20
  21   return block;
  22 }
  23
  24 static
  25 void extract_blocks (struct subroutine *sub)
  26 {
  27   struct location *begin, *next;
  28   struct basicblock *block;
  29   int prevlikely = FALSE;
  30
  31   sub->blocks = list_alloc (sub->code->lstpool);
  32   sub->revdfsblocks = list_alloc (sub->code->lstpool);
  33   sub->dfsblocks = list_alloc (sub->code->lstpool);
  34
  35   block = alloc_block (sub);
  36   block->blockel = list_inserttail (sub->blocks, block);
  37   block->type = BLOCK_START;
  38   sub->startblock = block;
  39
  40   begin = sub->begin;
  41
  42   while (1) {
  43     block = alloc_block (sub);
  44     block->blockel = list_inserttail (sub->blocks, block);
  45
  46     if (!begin) break;
  47     next = begin;
  48
  49     block->type = BLOCK_SIMPLE;
  50     block->info.simple.begin = begin;
  51
  52     for (; next != sub->end; next++) {
  53       if (prevlikely) {
  54         prevlikely = FALSE;
  55         break;
  56       }
  57
  58       if (next->references && (next != begin)) {
  59         next--;
  60         break;
  61       }
  62
  63       if (next->insn->flags & (INSN_JUMP | INSN_BRANCH)) {
  64         block->info.simple.jumploc = next;
  65         if (next->insn->flags & INSN_BRANCHLIKELY)
  66           prevlikely = TRUE;
  67         if (!(next->insn->flags & INSN_BRANCHLIKELY) &&
  68             !next[1].references && location_branch_may_swap (next)) {
  69           next++;
  70         }
  71         break;
  72       }
  73     }
  74     block->info.simple.end = next;
  75
  76     do {
  77       begin->block = block;
  78     } while (begin++ != next);
  79
  80     begin = NULL;
  81     while (next++ != sub->end) {
  82       if (next->reachable == LOCATION_DELAY_SLOT) {
  83         if (!prevlikely) {
  84           begin = next;
  85           break;
  86         }
  87       } else if (next->reachable == LOCATION_REACHABLE) {
  88         if (next != &block->info.simple.end[1])
  89           prevlikely = FALSE;
  90         begin = next;
  91         break;
  92       }
  93     }
  94   }
  95   block->type = BLOCK_END;
  96   sub->endblock = block;
  97 }
  98
  99
 100 static
 101 void make_link (struct basicblock *from, struct basicblock *to)
 102 {
 103   struct basicedge *edge = fixedpool_alloc (from->sub->code->edgespool);
 104
 105   edge->from = from;
 106   edge->fromnum = list_size (from->outrefs);
 107   edge->to = to;
 108   edge->tonum = list_size (to->inrefs);
 109
 110   edge->fromel = list_inserttail (from->outrefs, edge);
 111   edge->toel = list_inserttail (to->inrefs, edge);
 112 }
 113
 114 static
 115 struct basicblock *make_link_and_insert (struct basicblock *from, struct basicblock *to, element el)
 116 {
 117   struct basicblock *block = alloc_block (from->sub);
 118   block->blockel = element_alloc (from->sub->code->lstpool, block);
 119   element_insertbefore (el, block->blockel);
 120   make_link (from, block);
 121   make_link (block, to);
 122   return block;
 123 }
 124
 125 static
 126 void make_call (struct basicblock *block, struct location *loc)
 127 {
 128   block->type = BLOCK_CALL;
 129   if (loc->target) {
 130     block->info.call.calltarget = loc->target->sub;
 131     list_inserttail (loc->target->sub->whereused, block);
 132   }
 133 }
 134
 135
 136 static
 137 void link_blocks (struct subroutine *sub)
 138 {
 139   struct basicblock *block, *next;
 140   struct basicblock *target;
 141   struct location *loc;
 142   element el;
 143
 144   el = list_head (sub->blocks);
 145
 146   while (el) {
 147     block = element_getvalue (el);
 148     if (block->type == BLOCK_END) break;
 149     if (block->type == BLOCK_START) {
 150       el = element_next (el);
 151       make_link (block, element_getvalue (el));
 152       continue;
 153     }
 154
 155     el = element_next (el);
 156     next = element_getvalue (el);
 157
 158
 159     if (block->info.simple.jumploc) {
 160       loc = block->info.simple.jumploc;
 161       if (loc->insn->flags & INSN_BRANCH) {
 162         if (!loc->branchalways) {
 163           if (loc->insn->flags & INSN_BRANCHLIKELY) {
 164             make_link (block, loc[2].block);
 165           } else {
 166             make_link (block, next);
 167           }
 168         }
 169
 170         if (loc == block->info.simple.end) {
 171           struct basicblock *slot = alloc_block (sub);
 172           slot->blockel = element_alloc (sub->code->lstpool, slot);
 173           element_insertbefore (el, slot->blockel);
 174
 175           slot->type = BLOCK_SIMPLE;
 176           slot->info.simple.begin = &block->info.simple.end[1];
 177           slot->info.simple.end = slot->info.simple.begin;
 178           make_link (block, slot);
 179           block = slot;
 180         }
 181
 182         if (loc->insn->flags & INSN_LINK) {
 183           target = make_link_and_insert (block, loc[2].block, el);
 184           make_call (target, loc);
 185         } else if (loc->target->sub->begin == loc->target) {
 186           target = make_link_and_insert (block, sub->endblock, el);
 187           make_call (target, loc);
 188         } else {
 189           make_link (block, loc->target->block);
 190         }
 191
 192       } else {
 193         if (loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)) {
 194           target = make_link_and_insert (block, next, el);
 195           make_call (target, loc);
 196         } else {
 197           if (loc->target) {
 198             if (loc->target->sub->begin == loc->target) {
 199               target = make_link_and_insert (block, sub->endblock, el);
 200               make_call (target, loc);
 201             } else {
 202               make_link (block, loc->target->block);
 203             }
 204           } else {
 205             element ref;
 206             if (loc->cswitch && loc->cswitch->jumplocation == loc) {
 207               ref = list_head (loc->cswitch->references);
 208               while (ref) {
 209                 struct location *switchtarget = element_getvalue (ref);
 210                 make_link (block, switchtarget->block);
 211                 ref = element_next (ref);
 212               }
 213             } else
 214               make_link (block, sub->endblock);
 215           }
 216         }
 217       }
 218     } else {
 219       make_link (block, next);
 220     }
 221   }
 222 }
 223
 224 void extract_cfg (struct subroutine *sub)
 225 {
 226   extract_blocks (sub);
 227   link_blocks (sub);
 228   if (!cfg_dfs (sub, 0)) {
 229     error (__FILE__ ": unreachable code at subroutine 0x%08X", sub->begin->address);
 230     sub->haserror = TRUE;
 231     return;
 232   }
 233   if (!cfg_dfs (sub, 1)) {
 234     error (__FILE__ ": infinite loop at subroutine 0x%08X", sub->begin->address);
 235     sub->haserror = TRUE;
 236     return;
 237   }
 238
 239   cfg_dominance (sub, 0);
 240   cfg_frontier (sub, 0);
 241
 242   cfg_dominance (sub, 1);
 243   cfg_frontier (sub, 1);
 244 }
 245
 246
 247 static
 248 void mark_backward (struct subroutine *sub, struct basicblock *block, int num, int end)
 249 {
 250   element el, ref;
 251   int count = 1;
 252
 253   el = block->node.blockel;
 254   while (el && count) {
 255     struct basicblock *block = element_getvalue (el);
 256     if (block->node.dfsnum < end) break;
 257     if (block->mark1 == num) {
 258       count--;
 259       ref = list_head (block->inrefs);
 260       while (ref) {
 261         struct basicedge *edge = element_getvalue (ref);
 262         struct basicblock *next = edge->from;
 263         if (next->node.dfsnum >= end &&
 264             next->node.dfsnum < block->node.dfsnum) {
 265           if (next->mark1 != num) count++;
 266           next->mark1 = num;
 267         }
 268         ref = element_next (ref);
 269       }
 270     }
 271
 272     el = element_previous (el);
 273   }
 274 }
 275
 276 static
 277 void mark_forward (struct subroutine *sub, struct basicblock *block,
 278                    struct loopstructure *loop, int num, int end)
 279 {
 280   element el, ref;
 281
 282   el = block->node.blockel;
 283   while (el) {
 284     struct basicblock *block = element_getvalue (el);
 285     if (block->node.dfsnum > end) break;
 286     if (block->mark2 == num) {
 287       block->loopst = loop;
 288       ref = list_head (block->outrefs);
 289       while (ref) {
 290         struct basicedge *edge = element_getvalue (ref);
 291         struct basicblock *next = edge->to;
 292         if (next->node.dfsnum > block->node.dfsnum) {
 293           if (next->mark1 == num) next->mark2 = num;
 294           else {
 295             if (!loop->end) loop->end = next;
 296             if (list_size (loop->end->inrefs) < list_size (next->inrefs))
 297               loop->end = next;
 298           }
 299         }
 300         ref = element_next (ref);
 301       }
 302     }
 303
 304     el = element_next (el);
 305   }
 306 }
 307
 308
 309 static
 310 void mark_loop (struct subroutine *sub, struct loopstructure *loop)
 311 {
 312   element el;
 313   int num = ++sub->temp;
 314   int maxdfs = -1;
 315
 316   el = list_head (loop->edges);
 317   while (el) {
 318     struct basicedge *edge = element_getvalue (el);
 319     struct basicblock *block = edge->from;
 320
 321     if (maxdfs < block->node.dfsnum)
 322       maxdfs = block->node.dfsnum;
 323
 324     if (block->mark1 != num) {
 325       block->mark1 = num;
 326       mark_backward (sub, block, num, loop->start->node.dfsnum);
 327     }
 328     el = element_next (el);
 329   }
 330
 331   loop->start->mark2 = num;
 332   mark_forward (sub, loop->start, loop, num, maxdfs);
 333
 334   if (loop->end) {
 335     el = list_head (loop->end->inrefs);
 336     while (el) {
 337       struct basicedge *edge = element_getvalue (el);
 338       struct basicblock *block = edge->from;
 339       if (block->loopst == loop)
 340         edge->type = EDGE_BREAK;
 341       el = element_next (el);
 342     }
 343   }
 344 }
 345
 346 static
 347 void extract_loops (struct subroutine *sub)
 348 {
 349   struct basicblock *block;
 350   struct basicedge *edge;
 351   struct loopstructure *loop;
 352   element el, ref;
 353
 354   el = list_head (sub->dfsblocks);
 355   while (el) {
 356     block = element_getvalue (el);
 357
 358     loop = NULL;
 359     ref = list_head (block->inrefs);
 360     while (ref) {
 361       edge = element_getvalue (ref);
 362       if (edge->from->node.dfsnum >= block->node.dfsnum) {
 363         edge->type = EDGE_CONTINUE;
 364         if (!dom_isancestor (&block->node, &edge->from->node)) {
 365           error (__FILE__ ": graph of sub 0x%08X is not reducible (using goto)", sub->begin->address);
 366           edge->type = EDGE_GOTO;
 367           edge->to->haslabel = TRUE;
 368         } else if (block->loopst == edge->from->loopst ||
 369             dom_isancestor (&block->revnode, &edge->from->revnode)) {
 370           if (!loop) {
 371             loop = fixedpool_alloc (sub->code->loopspool);
 372             loop->start = block;
 373             loop->edges = list_alloc (sub->code->lstpool);
 374           }
 375           list_inserttail (loop->edges, edge);
 376         } else {
 377           edge->type = EDGE_GOTO;
 378           edge->to->haslabel = TRUE;
 379         }
 380       }
 381       ref = element_next (ref);
 382     }
 383     if (loop) mark_loop (sub, loop);
 384     el = element_next (el);
 385   }
 386 }
 387
 388 static
 389 void extract_ifs (struct subroutine *sub)
 390 {
 391   struct basicblock *block;
 392   struct ifstructure *ifst;
 393   list unresolved;
 394   element el;
 395
 396   unresolved = list_alloc (sub->code->lstpool);
 397
 398   el = list_tail (sub->dfsblocks);
 399   while (el) {
 400     int hasswitch = FALSE;
 401     block = element_getvalue (el);
 402
 403     if (block->type == BLOCK_SIMPLE) {
 404       if (block->info.simple.jumploc) {
 405         if (block->info.simple.jumploc->cswitch)
 406           hasswitch = TRUE;
 407       }
 408     }
 409
 410     if (list_size (block->outrefs) == 2 && !hasswitch) {
 411       struct basicedge *edge1, *edge2;
 412
 413       ifst = fixedpool_alloc (sub->code->ifspool);
 414       block->ifst = ifst;
 415
 416       edge1 = list_headvalue (block->outrefs);
 417       edge2 = list_tailvalue (block->outrefs);
 418       if (edge1->type == EDGE_UNKNOWN || edge2->type == EDGE_UNKNOWN) {
 419         element domel;
 420
 421         list_inserthead (unresolved, block);
 422         domel = list_head (block->node.domchildren);
 423         while (domel) {
 424           int incount = 0;
 425           struct basicblocknode *dom = element_getvalue (domel);
 426           struct basicblock *domblock = element_getvalue (dom->blockel);
 427           element ref;
 428
 429           ref = list_head (domblock->inrefs);
 430           while (ref) {
 431             struct basicedge *edge = element_getvalue (ref);
 432             if (edge->from->node.dfsnum < domblock->node.dfsnum)
 433               incount++;
 434             ref = element_next (ref);
 435           }
 436
 437           if (incount > 1) {
 438             block->ifst->outermost = TRUE;
 439             while (list_size (unresolved) != 0) {
 440               struct basicblock *ifblock = list_removehead (unresolved);
 441               ifblock->ifst->end = domblock;
 442             }
 443             break;
 444           }
 445           domel = element_next (domel);
 446         }
 447       }
 448     }
 449
 450     el = element_previous (el);
 451   }
 452
 453   list_free (unresolved);
 454 }
 455
 456 static
 457 void structure_search (struct basicblock *block, int identsize, struct ifstructure *ifst)
 458 {
 459   struct basicedge *edge;
 460   struct basicblock *ifend = NULL;
 461   element ref;
 462
 463   if (ifst)
 464     ifend = ifst->end;
 465
 466   if (block->ifst)
 467     if (block->ifst->end)
 468       ifend = block->ifst->end;
 469
 470   block->mark1 = 1;
 471
 472   if (block->loopst) {
 473     if (block->loopst->start == block) {
 474       identsize++;
 475       if (block->loopst->end) {
 476         if (!block->loopst->end->mark1)
 477           structure_search (block->loopst->end, identsize - 1, ifst);
 478         else {
 479           block->loopst->end->haslabel = TRUE;
 480           block->loopst->hasendgoto = TRUE;
 481         }
 482       }
 483     }
 484   }
 485
 486   if (block->ifst) {
 487     if (block->ifst->end && block->ifst->outermost) {
 488       if (!block->ifst->end->mark1)
 489         structure_search (block->ifst->end, identsize, ifst);
 490       else {
 491         block->ifst->end->haslabel = TRUE;
 492         block->ifst->hasendgoto = TRUE;
 493       }
 494     }
 495   }
 496
 497   block->identsize = identsize;
 498
 499   ref = list_head (block->outrefs);
 500   while (ref) {
 501     edge = element_getvalue (ref);
 502     if (edge->type == EDGE_UNKNOWN) {
 503       if (edge->to->loopst != block->loopst) {
 504         if (edge->to->loopst) {
 505           if (edge->to->loopst->start != edge->to) {
 506             edge->type = EDGE_GOTO;
 507             edge->to->haslabel = TRUE;
 508           }
 509         } else {
 510           edge->type = EDGE_GOTO;
 511           edge->to->haslabel = TRUE;
 512         }
 513       }
 514     }
 515
 516     if (edge->type == EDGE_UNKNOWN) {
 517       if (edge->to == ifend) {
 518         edge->type = EDGE_IFEXIT;
 519       } else {
 520         if (edge->to->mark1) {
 521           edge->type = EDGE_GOTO;
 522           edge->to->haslabel = TRUE;
 523         } else {
 524           edge->type = EDGE_FOLLOW;
 525           if (block->ifst) {
 526             structure_search (edge->to, identsize + 1, block->ifst);
 527           } else {
 528             structure_search (edge->to, identsize, ifst);
 529           }
 530         }
 531       }
 532     }
 533     ref = element_next (ref);
 534   }
 535 }
 536
 537 void reset_marks (struct subroutine *sub)
 538 {
 539   element el = list_head (sub->blocks);
 540   while (el) {
 541     struct basicblock *block = element_getvalue (el);
 542     block->mark1 = block->mark2 = 0;
 543     el = element_next (el);
 544   }
 545 }
 546
 547 void extract_structures (struct subroutine *sub)
 548 {
 549   element el;
 550   sub->temp = 0;
 551   reset_marks (sub);
 552
 553   extract_loops (sub);
 554   extract_ifs (sub);
 555
 556   reset_marks (sub);
 557   sub->temp = 0;
 558
 559   el = list_head (sub->blocks);
 560   while (el) {
 561     struct basicblock *block = element_getvalue (el);
 562     if (!block->mark1)
 563       structure_search (block, 0, NULL);
 564     el = element_next (el);
 565   }
 566 }