ssa.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5 static
   6 struct ssavar *alloc_variable (struct basicblock *block)
   7 {
   8   struct ssavar *var;
   9   var = fixedpool_alloc (block->sub->code->ssavarspool);
  10   var->uses = list_alloc (block->sub->code->lstpool);
  11   return var;
  12 }
  13
  14 static
  15 void ssa_place_phis (struct subroutine *sub, list *defblocks)
  16 {
  17   struct basicblock *block, *bref;
  18   struct basicblocknode *brefnode;
  19   element el, ref;
  20   int regno, i;
  21
  22   el = list_head (sub->blocks);
  23   while (el) {
  24     block = element_getvalue (el);
  25     block->mark1 = 0;
  26     block->mark2 = 0;
  27     el = element_next (el);
  28   }
  29
  30   for (regno = 1; regno < NUM_REGISTERS; regno++) {
  31     list worklist = defblocks[regno];
  32     el = list_head (worklist);
  33     while (el) {
  34       block = element_getvalue (el);
  35       block->mark1 = regno;
  36       el = element_next (el);
  37     }
  38
  39     while (list_size (worklist) != 0) {
  40       block = list_removehead (worklist);
  41       ref = list_head (block->node.frontier);
  42       while (ref) {
  43         brefnode = element_getvalue (ref);
  44         bref = element_getvalue (brefnode->blockel);
  45         if (bref->mark2 != regno && IS_BIT_SET (bref->reg_live_out, regno)) {
  46           struct operation *op;
  47
  48           bref->mark2 = regno;
  49           op = operation_alloc (bref);
  50           op->type = OP_PHI;
  51           value_append (sub, op->results, VAL_REGISTER, regno);
  52           for (i = list_size (bref->inrefs); i > 0; i--)
  53             value_append (sub, op->operands, VAL_REGISTER, regno);
  54           list_inserthead (bref->operations, op);
  55
  56           if (bref->mark1 != regno) {
  57             bref->mark1 = regno;
  58             list_inserttail (worklist, bref);
  59           }
  60         }
  61         ref = element_next (ref);
  62       }
  63     }
  64   }
  65 }
  66
  67 static
  68 void ssa_search (struct basicblock *block, list *vars)
  69 {
  70   element el;
  71   int regno, pushed[NUM_REGISTERS];
  72
  73   for (regno = 1; regno < NUM_REGISTERS; regno++)
  74     pushed[regno] = FALSE;
  75
  76   el = list_head (block->operations);
  77   while (el) {
  78     struct operation *op;
  79     struct ssavar *var;
  80     struct value *val;
  81     element opel, rel;
  82
  83     op = element_getvalue (el);
  84
  85     if (op->type != OP_PHI) {
  86       opel = list_head (op->operands);
  87       while (opel) {
  88         val = element_getvalue (opel);
  89         if (val->type == VAL_REGISTER) {
  90           var = list_headvalue (vars[val->val.intval]);
  91           val->type = VAL_SSAVAR;
  92           val->val.variable = var;
  93           list_inserttail (var->uses, op);
  94         }
  95         opel = element_next (opel);
  96       }
  97     }
  98
  99     rel = list_head (op->results);
 100     while (rel) {
 101       val = element_getvalue (rel);
 102       if (val->type == VAL_REGISTER) {
 103         val->type = VAL_SSAVAR;
 104         var = alloc_variable (block);
 105         var->name.type = VAL_REGISTER;
 106         var->name.val.intval = val->val.intval;
 107         var->def = op;
 108         list_inserttail (block->sub->ssavars, var);
 109         if (!pushed[val->val.intval]) {
 110           pushed[val->val.intval] = TRUE;
 111           list_inserthead (vars[val->val.intval], var);
 112         } else {
 113           element_setvalue (list_head (vars[val->val.intval]), var);
 114         }
 115         val->val.variable = var;
 116       }
 117       rel = element_next (rel);
 118     }
 119
 120     el = element_next (el);
 121   }
 122
 123   el = list_head (block->outrefs);
 124   while (el) {
 125     struct basicedge *edge;
 126     struct basicblock *ref;
 127     element phiel, opel;
 128
 129     edge = element_getvalue (el);
 130     ref = edge->to;
 131
 132     phiel = list_head (ref->operations);
 133     while (phiel) {
 134       struct operation *op;
 135       struct value *val;
 136
 137       op = element_getvalue (phiel);
 138       if (op->type != OP_PHI) break;
 139
 140       opel = list_head (op->operands);
 141       for (regno = edge->tonum; regno > 0; regno--)
 142         opel = element_next (opel);
 143
 144       val = element_getvalue (opel);
 145       val->type = VAL_SSAVAR;
 146       val->val.variable = list_headvalue (vars[val->val.intval]);
 147       list_inserttail (val->val.variable->uses, op);
 148       phiel = element_next (phiel);
 149     }
 150     el = element_next (el);
 151   }
 152
 153   el = list_head (block->node.children);
 154   while (el) {
 155     struct basicblocknode *childnode;
 156     struct basicblock *child;
 157
 158     childnode = element_getvalue (el);
 159     child = element_getvalue (childnode->blockel);
 160     ssa_search (child, vars);
 161     el = element_next (el);
 162   }
 163
 164   for (regno = 1; regno < NUM_REGISTERS; regno++)
 165     if (pushed[regno]) list_removehead (vars[regno]);
 166 }
 167
 168 void build_ssa (struct subroutine *sub)
 169 {
 170   list reglist[NUM_REGISTERS];
 171   element blockel;
 172   int regno;
 173
 174   reglist[0] = NULL;
 175   for (regno = 1; regno < NUM_REGISTERS; regno++) {
 176     reglist[regno] = list_alloc (sub->code->lstpool);
 177   }
 178
 179   sub->ssavars = list_alloc (sub->code->lstpool);
 180
 181   blockel = list_head (sub->blocks);
 182   while (blockel) {
 183     struct basicblock *block = element_getvalue (blockel);
 184     for (regno = 0; regno < NUM_REGISTERS; regno++) {
 185       if (IS_BIT_SET (block->reg_kill, regno))
 186         list_inserttail (reglist[regno], block);
 187     }
 188     blockel = element_next (blockel);
 189   }
 190
 191   ssa_place_phis (sub, reglist);
 192   ssa_search (sub->startblock, reglist);
 193
 194   for (regno = 1; regno < NUM_REGISTERS; regno++) {
 195     list_free (reglist[regno]);
 196   }
 197 }
 198
 199 void unbuild_ssa (struct subroutine *sub)
 200 {
 201   element varel, valel, blockel, opel;
 202
 203   blockel = list_head (sub->blocks);
 204   while (blockel) {
 205     struct basicblock *block = element_getvalue (blockel);
 206     opel = list_head (block->operations);
 207     while (opel) {
 208       struct operation *op = element_getvalue (opel);
 209       element nextopel;
 210
 211       nextopel = element_next (opel);
 212       if (op->type == OP_PHI) {
 213         element_remove (opel);
 214
 215         valel = list_head (op->operands);
 216         while (valel) {
 217           struct value *val = element_getvalue (valel);
 218           fixedpool_free (sub->code->valspool, val);
 219           valel = element_next (valel);
 220         }
 221         list_free (op->operands);
 222
 223         fixedpool_free (sub->code->valspool, list_headvalue (op->results));
 224         list_free (op->results);
 225       } else {
 226         valel = list_head (op->operands);
 227         while (valel) {
 228           struct value *val = element_getvalue (valel);
 229           if (val->type == VAL_SSAVAR) {
 230             val->type = VAL_REGISTER;
 231             val->val.intval = val->val.variable->name.val.intval;
 232           }
 233           valel = element_next (valel);
 234         }
 235
 236         valel = list_head (op->results);
 237         while (valel) {
 238           struct value *val = element_getvalue (valel);
 239           if (val->type == VAL_SSAVAR) {
 240             val->type = VAL_REGISTER;
 241             val->val.intval = val->val.variable->name.val.intval;
 242           }
 243           valel = element_next (valel);
 244         }
 245
 246       }
 247       opel = nextopel;
 248     }
 249     blockel = element_next (blockel);
 250   }
 251
 252   varel = list_head (sub->ssavars);
 253   while (varel) {
 254     struct ssavar *var = element_getvalue (varel);
 255     list_free (var->uses);
 256     fixedpool_free (sub->code->ssavarspool, var);
 257     varel = element_next (varel);
 258   }
 259   list_free (sub->ssavars);
 260
 261   sub->ssavars = NULL;
 262 }
 263
 264
 265
 266