cfg.c

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