cfg.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5 static
   6 struct basicblock *alloc_block (struct subroutine *sub, int insert)
   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   if (insert) {
  21     block->blockel = list_inserttail (sub->blocks, block);
  22   } else {
  23     block->blockel = element_alloc (sub->code->lstpool, block);
  24   }
  25
  26   return block;
  27 }
  28
  29 static
  30 void extract_blocks (struct subroutine *sub)
  31 {
  32   struct location *begin, *next;
  33   struct basicblock *block;
  34   int prevlikely = FALSE;
  35
  36   sub->blocks = list_alloc (sub->code->lstpool);
  37   sub->revdfsblocks = list_alloc (sub->code->lstpool);
  38   sub->dfsblocks = list_alloc (sub->code->lstpool);
  39
  40   block = alloc_block (sub, TRUE);
  41   block->type = BLOCK_START;
  42   sub->startblock = block;
  43
  44   begin = sub->begin;
  45
  46   while (1) {
  47     block = alloc_block (sub, TRUE);
  48     if (sub->firstblock) sub->firstblock = block;
  49
  50     if (!begin) break;
  51     next = begin;
  52
  53     block->type = BLOCK_SIMPLE;
  54     block->info.simple.begin = begin;
  55
  56     for (; next != sub->end; next++) {
  57       if (prevlikely) {
  58         prevlikely = FALSE;
  59         break;
  60       }
  61
  62       if (next->references && (next != begin)) {
  63         next--;
  64         break;
  65       }
  66
  67       if (next->insn->flags & (INSN_JUMP | INSN_BRANCH)) {
  68         block->info.simple.jumploc = next;
  69         if (next->insn->flags & INSN_BRANCHLIKELY)
  70           prevlikely = TRUE;
  71         if (!(next->insn->flags & INSN_BRANCHLIKELY) &&
  72             !next[1].references && location_branch_may_swap (next)) {
  73           next++;
  74         }
  75         break;
  76       }
  77     }
  78     block->info.simple.end = next;
  79
  80     do {
  81       begin->block = block;
  82     } while (begin++ != next);
  83
  84     begin = NULL;
  85     while (next++ != sub->end) {
  86       if (next->reachable == LOCATION_DELAY_SLOT) {
  87         if (!prevlikely) {
  88           begin = next;
  89           break;
  90         }
  91       } else if (next->reachable == LOCATION_REACHABLE) {
  92         if (next != &block->info.simple.end[1])
  93           prevlikely = FALSE;
  94         begin = next;
  95         break;
  96       }
  97     }
  98   }
  99   block->type = BLOCK_END;
 100   sub->endblock = block;
 101 }
 102
 103
 104 static
 105 void make_link (struct basicblock *from, struct basicblock *to)
 106 {
 107   struct basicedge *edge = fixedpool_alloc (from->sub->code->edgespool);
 108
 109   edge->from = from;
 110   edge->fromnum = list_size (from->outrefs);
 111   edge->to = to;
 112   edge->tonum = list_size (to->inrefs);
 113
 114   edge->fromel = list_inserttail (from->outrefs, edge);
 115   edge->toel = list_inserttail (to->inrefs, edge);
 116 }
 117
 118 static
 119 struct basicblock *make_link_and_insert (struct basicblock *from, struct basicblock *to, element el)
 120 {
 121   struct basicblock *block = alloc_block (from->sub, FALSE);
 122   element_insertbefore (el, block->blockel);
 123   make_link (from, block);
 124   make_link (block, to);
 125   return block;
 126 }
 127
 128 static
 129 void make_call (struct basicblock *block, struct location *loc)
 130 {
 131   block->type = BLOCK_CALL;
 132   list_inserttail (block->sub->callblocks, block);
 133   if (loc->target) {
 134     block->info.call.calltarget = loc->target->sub;
 135     list_inserttail (loc->target->sub->whereused, block);
 136   }
 137 }
 138
 139
 140 static
 141 void link_blocks (struct subroutine *sub)
 142 {
 143   struct basicblock *block, *next;
 144   struct basicblock *target;
 145   struct location *loc;
 146   element el;
 147
 148   el = list_head (sub->blocks);
 149
 150   while (el) {
 151     block = element_getvalue (el);
 152     if (block->type == BLOCK_END) break;
 153     if (block->type == BLOCK_START) {
 154       el = element_next (el);
 155       make_link (block, element_getvalue (el));
 156       continue;
 157     }
 158
 159     el = element_next (el);
 160     next = element_getvalue (el);
 161
 162
 163     if (block->info.simple.jumploc) {
 164       loc = block->info.simple.jumploc;
 165       if (loc->insn->flags & INSN_BRANCH) {
 166         if (!loc->branchalways) {
 167           if (loc->insn->flags & INSN_BRANCHLIKELY) {
 168             make_link (block, loc[2].block);
 169           } else {
 170             make_link (block, next);
 171           }
 172         }
 173
 174         if (loc == block->info.simple.end) {
 175           struct basicblock *slot = alloc_block (sub, FALSE);
 176           element_insertbefore (el, slot->blockel);
 177
 178           slot->type = BLOCK_SIMPLE;
 179           slot->info.simple.begin = &block->info.simple.end[1];
 180           slot->info.simple.end = slot->info.simple.begin;
 181           make_link (block, slot);
 182           block = slot;
 183         }
 184
 185         if (loc->insn->flags & INSN_LINK) {
 186           target = make_link_and_insert (block, loc[2].block, el);
 187           make_call (target, loc);
 188         } else if (loc->target->sub->begin == loc->target) {
 189           target = make_link_and_insert (block, sub->endblock, el);
 190           make_call (target, loc);
 191         } else {
 192           make_link (block, loc->target->block);
 193         }
 194
 195       } else {
 196         if (loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)) {
 197           target = make_link_and_insert (block, next, el);
 198           make_call (target, loc);
 199         } else {
 200           if (loc->target) {
 201             if (loc->target->sub->begin == loc->target) {
 202               target = make_link_and_insert (block, sub->endblock, el);
 203               make_call (target, loc);
 204             } else {
 205               make_link (block, loc->target->block);
 206             }
 207           } else {
 208             element ref;
 209             if (loc->cswitch && loc->cswitch->jumplocation == loc) {
 210               ref = list_head (loc->cswitch->references);
 211               while (ref) {
 212                 struct location *switchtarget = element_getvalue (ref);
 213                 make_link (block, switchtarget->block);
 214                 ref = element_next (ref);
 215               }
 216             } else
 217               make_link (block, sub->endblock);
 218           }
 219         }
 220       }
 221     } else {
 222       make_link (block, next);
 223     }
 224   }
 225 }
 226
 227 void extract_cfg (struct subroutine *sub)
 228 {
 229   extract_blocks (sub);
 230   link_blocks (sub);
 231 }