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 *call, struct basicblock *from, struct location *loc)
 133 {
 134   call->type = BLOCK_CALL;
 135   list_inserttail (call->sub->callblocks, call);
 136   call->info.call.from = from;
 137   if (loc->target) {
 138     call->info.call.calltarget = loc->target->sub;
 139     list_inserttail (loc->target->sub->whereused, call);
 140   }
 141 }
 142
 143
 144 static
 145 void link_blocks (struct subroutine *sub)
 146 {
 147   struct basicblock *block, *next;
 148   struct basicblock *target;
 149   struct location *loc;
 150   element el;
 151
 152   el = list_head (sub->blocks);
 153
 154   while (el) {
 155     block = element_getvalue (el);
 156     if (block->type == BLOCK_END) break;
 157     if (block->type == BLOCK_START) {
 158       el = element_next (el);
 159       make_link (block, element_getvalue (el));
 160       continue;
 161     }
 162
 163     el = element_next (el);
 164     next = element_getvalue (el);
 165
 166
 167     if (block->info.simple.jumploc) {
 168       loc = block->info.simple.jumploc;
 169       if (loc->insn->flags & INSN_BRANCH) {
 170         if (!loc->branchalways) {
 171           if (loc->insn->flags & INSN_BRANCHLIKELY) {
 172             make_link (block, loc[2].block);
 173           } else {
 174             make_link (block, next);
 175           }
 176         }
 177
 178         if (loc == block->info.simple.end) {
 179           struct basicblock *slot = alloc_block (sub, FALSE);
 180           element_insertbefore (el, slot->blockel);
 181
 182           slot->type = BLOCK_SIMPLE;
 183           slot->info.simple.begin = &block->info.simple.end[1];
 184           slot->info.simple.end = slot->info.simple.begin;
 185           make_link (block, slot);
 186           block = slot;
 187         }
 188
 189         if (loc->insn->flags & INSN_LINK) {
 190           target = make_link_and_insert (block, loc[2].block, el);
 191           make_call (target, block, loc);
 192         } else if (loc->target->sub->begin == loc->target) {
 193           target = make_link_and_insert (block, sub->endblock, el);
 194           make_call (target, block, loc);
 195         } else {
 196           make_link (block, loc->target->block);
 197         }
 198
 199       } else {
 200         if (loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)) {
 201           target = make_link_and_insert (block, next, el);
 202           make_call (target, block, loc);
 203         } else {
 204           if (loc->target) {
 205             if (loc->target->sub->begin == loc->target) {
 206               target = make_link_and_insert (block, sub->endblock, el);
 207               make_call (target, block, loc);
 208             } else {
 209               make_link (block, loc->target->block);
 210             }
 211           } else {
 212             element ref;
 213             if (loc->cswitch && loc->cswitch->jumplocation == loc) {
 214               block->status |= BLOCK_STAT_ISSWITCH;
 215               ref = list_head (loc->cswitch->references);
 216               while (ref) {
 217                 struct location *switchtarget = element_getvalue (ref);
 218                 make_link (block, switchtarget->block);
 219                 switchtarget->block->status |= BLOCK_STAT_ISSWITCHTARGET;
 220                 ref = element_next (ref);
 221               }
 222             } else
 223               make_link (block, sub->endblock);
 224           }
 225         }
 226       }
 227     } else {
 228       make_link (block, next);
 229     }
 230   }
 231 }
 232
 233 void extract_cfg (struct subroutine *sub)
 234 {
 235   extract_blocks (sub);
 236   link_blocks (sub);
 237 }