liveness.c

   1 /**
   2  * Author: Humberto Naves (hsnaves@gmail.com)
   3  */
   4
   5 #include "code.h"
   6 #include "utils.h"
   7
   8 static
   9 void live_analysis (list worklist)
  10 {
  11   while (list_size (worklist) != 0) {
  12     struct basicedge *edge;
  13     struct basicblock *block, *bref;
  14     struct subroutine *sub;
  15     int i, changed, regno;
  16     element ref;
  17
  18     block = list_removehead (worklist);
  19     block->mark1 = 0;
  20     for (i = 0; i < NUM_REGMASK; i++)
  21       block->reg_live_out[i] =
  22         (block->reg_live_in[i] & ~(block->reg_kill[i])) | block->reg_gen[i];
  23
  24     ref = list_head (block->inrefs);
  25     while (ref) {
  26       changed = FALSE;
  27
  28       edge = element_getvalue (ref);
  29       bref = edge->from;
  30
  31       for (i = 0; i < NUM_REGMASK; i++) {
  32         changed = changed || (block->reg_live_out[i] & (~bref->reg_live_in[i]));
  33         bref->reg_live_in[i] |= block->reg_live_out[i];
  34       }
  35
  36       if (changed && !bref->mark1) {
  37         list_inserttail (worklist, bref);
  38         bref->mark1 = 1;
  39       }
  40
  41       ref = element_next (ref);
  42     }
  43
  44     sub = block->info.call.calltarget;
  45     if (block->type == BLOCK_CALL && sub) {
  46
  47       for (regno = REGISTER_GPR_V0; regno <= REGISTER_GPR_V1; regno++) {
  48         if (IS_BIT_SET (block->reg_live_in, regno)) {
  49           sub->numregout = MAX (sub->numregout, regno - REGISTER_GPR_V0 + 1);
  50         }
  51       }
  52
  53       if (sub->status & SUB_STAT_OPERATIONS_EXTRACTED) {
  54         changed = FALSE;
  55         for (regno = REGISTER_GPR_V0; regno <= REGISTER_GPR_V1; regno++) {
  56           if (IS_BIT_SET (block->reg_live_in, regno)) {
  57             changed = changed || !IS_BIT_SET (sub->endblock->reg_gen, regno);
  58             BIT_SET (sub->endblock->reg_gen, regno);
  59           }
  60         }
  61         if (changed && !sub->endblock->mark1) {
  62           list_inserttail (worklist, sub->endblock);
  63           sub->endblock->mark1 = 1;
  64         }
  65       }
  66     }
  67
  68     if (block->type == BLOCK_START) {
  69       sub = block->sub;
  70
  71       for (regno = REGISTER_GPR_A0; regno <= REGISTER_GPR_T3; regno++) {
  72         if (IS_BIT_SET (block->reg_live_in, regno)) {
  73           sub->numregargs = MAX (sub->numregargs, regno - REGISTER_GPR_A0 + 1);
  74         }
  75       }
  76
  77       ref = list_head (sub->whereused);
  78       while (ref) {
  79         bref = element_getvalue (ref);
  80         changed = FALSE;
  81         for (regno = REGISTER_GPR_A0; regno <= REGISTER_GPR_T3; regno++) {
  82           if (IS_BIT_SET (block->reg_live_in, regno)) {
  83             changed = changed || !IS_BIT_SET (bref->reg_gen, regno);
  84             BIT_SET (bref->reg_gen, regno);
  85           }
  86         }
  87         if (changed && !bref->mark1) {
  88           list_inserttail (worklist, bref);
  89           bref->mark1 = 1;
  90         }
  91         ref = element_next (ref);
  92       }
  93     }
  94   }
  95 }
  96
  97 void live_registers (struct code *c)
  98 {
  99   list worklist = list_alloc (c->lstpool);
 100   element el = list_head (c->subroutines);
 101
 102   while (el) {
 103     struct subroutine *sub = element_getvalue (el);
 104     if (!sub->import && !sub->haserror) {
 105       reset_marks (sub);
 106       sub->status |= SUB_STAT_LIVE_REGISTERS;
 107       sub->endblock->mark1 = 1;
 108       list_inserthead (worklist, sub->endblock);
 109     }
 110     el = element_next (el);
 111   }
 112
 113   live_analysis (worklist);
 114   list_free (worklist);
 115 }
 116
 117 void live_registers_imports (struct code *c)
 118 {
 119   element el = list_head (c->subroutines);
 120
 121   while (el) {
 122     struct subroutine *sub = element_getvalue (el);
 123     if (sub->import && sub->numregargs == -1) {
 124       element ref;
 125
 126       ref = list_head (sub->whereused);
 127       while (ref) {
 128         struct basicblock *block = element_getvalue (ref);
 129         struct operation *op = list_tailvalue (block->operations);
 130         int count = 0, maxcount = 0;
 131         element opel;
 132
 133         opel = list_head (op->info.callop.arguments);
 134         while (opel) {
 135           struct value *val = element_getvalue (opel);
 136           count++;
 137
 138           if (list_size (val->val.variable->uses) == 1 &&
 139               val->val.variable->def->type != OP_START &&
 140               val->val.variable->def->type != OP_CALL) {
 141             if (maxcount < count) maxcount = count;
 142           }
 143           opel = element_next (opel);
 144         }
 145
 146         if (sub->numregargs < maxcount)
 147           sub->numregargs = maxcount;
 148
 149         ref = element_next (ref);
 150       }
 151
 152       ref = list_head (sub->whereused);
 153       while (ref) {
 154         struct basicblock *block = element_getvalue (ref);
 155         struct subroutine *target = block->sub;
 156
 157         target->status &= ~(SUB_STAT_SSA | SUB_STAT_FIXUP_CALL_ARGS);
 158         ref = element_next (ref);
 159       }
 160     }
 161     el = element_next (el);
 162   }
 163
 164   el = list_head (c->subroutines);
 165
 166   while (el) {
 167     struct subroutine *sub = element_getvalue (el);
 168     if (!sub->import && !sub->haserror &&
 169         !(sub->status & SUB_STAT_SSA)) {
 170       unbuild_ssa (sub);
 171       remove_call_arguments (sub);
 172     }
 173     el = element_next (el);
 174   }
 175
 176 }