ssa.c

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