ir.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "ir.h"
   4
   5 /***********************************************************************
   6  *IR Builder
   7  */
   8
   9 ir_builder* ir_builder_new(const char *modulename)
  10 {
  11     ir_builder* self;
  12
  13     self = (ir_builder*)mem_a(sizeof(*self));
  14     MEM_VECTOR_INIT(self, functions);
  15     MEM_VECTOR_INIT(self, globals);
  16     self->name = NULL;
  17     ir_builder_set_name(self, modulename);
  18
  19     /* globals which always exist */
  20
  21     /* for now we give it a vector size */
  22     ir_builder_create_global(self, "OFS_RETURN", qc_variant);
  23
  24     return self;
  25 }
  26
  27 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, globals)
  28 MEM_VECTOR_FUNCTIONS(ir_builder, ir_function*, functions)
  29
  30 void ir_builder_delete(ir_builder* self)
  31 {
  32     size_t i;
  33     mem_d((void*)self->name);
  34     for (i = 0; i != self->functions_count; ++i) {
  35         ir_function_delete(self->functions[i]);
  36     }
  37     MEM_VECTOR_CLEAR(self, functions);
  38     for (i = 0; i != self->globals_count; ++i) {
  39         ir_value_delete(self->globals[i]);
  40     }
  41     MEM_VECTOR_CLEAR(self, globals);
  42     mem_d(self);
  43 }
  44
  45 void ir_builder_set_name(ir_builder *self, const char *name)
  46 {
  47     if (self->name)
  48         mem_d((void*)self->name);
  49     self->name = util_strdup(name);
  50 }
  51
  52 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
  53 {
  54     size_t i;
  55     for (i = 0; i < self->functions_count; ++i) {
  56         if (!strcmp(name, self->functions[i]->name))
  57             return self->functions[i];
  58     }
  59     return NULL;
  60 }
  61
  62 ir_function* ir_builder_create_function(ir_builder *self, const char *name)
  63 {
  64     ir_function *fn = ir_builder_get_function(self, name);
  65     if (fn) {
  66         return NULL;
  67     }
  68
  69     fn = ir_function_new(self);
  70     ir_function_set_name(fn, name);
  71     ir_builder_functions_add(self, fn);
  72     return fn;
  73 }
  74
  75 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
  76 {
  77     size_t i;
  78     for (i = 0; i < self->globals_count; ++i) {
  79         if (!strcmp(self->globals[i]->name, name))
  80             return self->globals[i];
  81     }
  82     return NULL;
  83 }
  84
  85 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
  86 {
  87     ir_value *ve = ir_builder_get_global(self, name);
  88     if (ve) {
  89         return NULL;
  90     }
  91
  92     ve = ir_value_var(name, qc_global, vtype);
  93     ir_builder_globals_add(self, ve);
  94     return ve;
  95 }
  96
  97 /***********************************************************************
  98  *IR Function
  99  */
 100
 101 void ir_function_naive_phi(ir_function*);
 102 void ir_function_enumerate(ir_function*);
 103 void ir_function_calculate_liferanges(ir_function*);
 104
 105 ir_function* ir_function_new(ir_builder* owner)
 106 {
 107     ir_function *self;
 108     self = (ir_function*)mem_a(sizeof(*self));
 109     self->owner = owner;
 110     self->context.file = "<@no context>";
 111     self->context.line = 0;
 112     self->retype = qc_void;
 113     MEM_VECTOR_INIT(self, params);
 114     MEM_VECTOR_INIT(self, blocks);
 115     MEM_VECTOR_INIT(self, values);
 116     MEM_VECTOR_INIT(self, locals);
 117     ir_function_set_name(self, "<@unnamed>");
 118
 119     self->run_id = 0;
 120     return self;
 121 }
 122 MEM_VECTOR_FUNCTIONS(ir_function, ir_value*, values)
 123 MEM_VECTOR_FUNCTIONS(ir_function, ir_block*, blocks)
 124 MEM_VECTOR_FUNCTIONS(ir_function, ir_value*, locals)
 125
 126 void ir_function_set_name(ir_function *self, const char *name)
 127 {
 128     if (self->name)
 129         mem_d((void*)self->name);
 130     self->name = util_strdup(name);
 131 }
 132
 133 void ir_function_delete(ir_function *self)
 134 {
 135     size_t i;
 136     mem_d((void*)self->name);
 137
 138     for (i = 0; i != self->blocks_count; ++i)
 139         ir_block_delete(self->blocks[i]);
 140     MEM_VECTOR_CLEAR(self, blocks);
 141
 142     MEM_VECTOR_CLEAR(self, params);
 143
 144     for (i = 0; i != self->values_count; ++i)
 145         ir_value_delete(self->values[i]);
 146     MEM_VECTOR_CLEAR(self, values);
 147
 148     for (i = 0; i != self->locals_count; ++i)
 149         ir_value_delete(self->locals[i]);
 150     MEM_VECTOR_CLEAR(self, locals);
 151
 152     mem_d(self);
 153 }
 154
 155 void ir_function_collect_value(ir_function *self, ir_value *v)
 156 {
 157     ir_function_values_add(self, v);
 158 }
 159
 160 ir_block* ir_function_create_block(ir_function *self, const char *label)
 161 {
 162     ir_block* bn = ir_block_new(self, label);
 163     memcpy(&bn->context, &self->context, sizeof(self->context));
 164     ir_function_blocks_add(self, bn);
 165     return bn;
 166 }
 167
 168 void ir_function_finalize(ir_function *self)
 169 {
 170     ir_function_naive_phi(self);
 171     ir_function_enumerate(self);
 172     ir_function_calculate_liferanges(self);
 173 }
 174
 175 ir_value* ir_function_get_local(ir_function *self, const char *name)
 176 {
 177     size_t i;
 178     for (i = 0; i < self->locals_count; ++i) {
 179         if (!strcmp(self->locals[i]->name, name))
 180             return self->locals[i];
 181     }
 182     return NULL;
 183 }
 184
 185 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype)
 186 {
 187     ir_value *ve = ir_function_get_local(self, name);
 188     if (ve) {
 189         return NULL;
 190     }
 191
 192     ve = ir_value_var(name, qc_localvar, vtype);
 193     ir_function_locals_add(self, ve);
 194     return ve;
 195 }
 196
 197 /***********************************************************************
 198  *IR Block
 199  */
 200
 201 ir_block* ir_block_new(ir_function* owner, const char *name)
 202 {
 203     ir_block *self;
 204     self = (ir_block*)mem_a(sizeof(*self));
 205     self->owner = owner;
 206     self->context.file = "<@no context>";
 207     self->context.line = 0;
 208     self->final = ifalse;
 209     MEM_VECTOR_INIT(self, instr);
 210     MEM_VECTOR_INIT(self, entries);
 211     MEM_VECTOR_INIT(self, exits);
 212     self->label = NULL;
 213     ir_block_set_label(self, name);
 214
 215     self->eid = 0;
 216     self->is_return = ifalse;
 217     self->run_id = 0;
 218     MEM_VECTOR_INIT(self, living);
 219     return self;
 220 }
 221 MEM_VECTOR_FUNCTIONS(ir_block, ir_instr*, instr)
 222 MEM_VECTOR_FUNCTIONS_ALL(ir_block, ir_block*, entries)
 223 MEM_VECTOR_FUNCTIONS_ALL(ir_block, ir_block*, exits)
 224 MEM_VECTOR_FUNCTIONS_ALL(ir_block, ir_value*, living)
 225
 226 void ir_block_delete(ir_block* self)
 227 {
 228     size_t i;
 229     mem_d((void*)self->label);
 230     for (i = 0; i != self->instr_count; ++i)
 231         ir_instr_delete(self->instr[i]);
 232     MEM_VECTOR_CLEAR(self, instr);
 233     MEM_VECTOR_CLEAR(self, entries);
 234     MEM_VECTOR_CLEAR(self, exits);
 235     MEM_VECTOR_CLEAR(self, living);
 236     mem_d(self);
 237 }
 238
 239 void ir_block_set_label(ir_block *self, const char *name)
 240 {
 241     if (self->label)
 242         mem_d((void*)self->label);
 243     self->label = util_strdup(name);
 244 }
 245
 246 /***********************************************************************
 247  *IR Instructions
 248  */
 249
 250 ir_instr* ir_instr_new(ir_block* owner, int op)
 251 {
 252     ir_instr *self;
 253     self = (ir_instr*)mem_a(sizeof(*self));
 254     self->owner = owner;
 255     self->context.file = "<@no context>";
 256     self->context.line = 0;
 257     self->opcode = op;
 258     self->_ops[0] = NULL;
 259     self->_ops[1] = NULL;
 260     self->_ops[2] = NULL;
 261     self->bops[0] = NULL;
 262     self->bops[1] = NULL;
 263     MEM_VECTOR_INIT(self, phi);
 264
 265     self->eid = 0;
 266     return self;
 267 }
 268 MEM_VECTOR_FUNCTIONS(ir_instr, ir_phi_entry_t, phi)
 269
 270 void ir_instr_delete(ir_instr *self)
 271 {
 272     ir_instr_op(self, 0, NULL, ifalse);
 273     ir_instr_op(self, 1, NULL, ifalse);
 274     ir_instr_op(self, 2, NULL, ifalse);
 275     MEM_VECTOR_CLEAR(self, phi);
 276     mem_d(self);
 277 }
 278
 279 void ir_instr_op(ir_instr *self, int op, ir_value *v, qbool writing)
 280 {
 281     if (self->_ops[op]) {
 282         if (writing)
 283             ir_value_writes_add(self->_ops[op], self);
 284         else
 285             ir_value_reads_add(self->_ops[op], self);
 286     }
 287     if (v) {
 288         if (writing)
 289             ir_value_writes_add(v, self);
 290         else
 291             ir_value_reads_add(v, self);
 292     }
 293     self->_ops[op] = v;
 294 }
 295
 296 /***********************************************************************
 297  *IR Value
 298  */
 299
 300 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 301 {
 302     ir_value *self;
 303     self = (ir_value*)mem_a(sizeof(*self));
 304     self->vtype = vtype;
 305     self->store = storetype;
 306     MEM_VECTOR_INIT(self, reads);
 307     MEM_VECTOR_INIT(self, writes);
 308     self->has_constval = ifalse;
 309     self->context.file = "<@no context>";
 310     self->context.line = 0;
 311     self->name = NULL;
 312     ir_value_set_name(self, name);
 313
 314     MEM_VECTOR_INIT(self, life);
 315     return self;
 316 }
 317 MEM_VECTOR_FUNCTIONS(ir_value, ir_life_entry_t, life)
 318 MEM_VECTOR_FUNCTIONS(ir_value, ir_instr*, reads)
 319 MEM_VECTOR_FUNCTIONS(ir_value, ir_instr*, writes)
 320
 321 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 322 {
 323     ir_value *v = ir_value_var(name, storetype, vtype);
 324     ir_function_collect_value(owner, v);
 325     return v;
 326 }
 327
 328 void ir_value_delete(ir_value* self)
 329 {
 330     mem_d((void*)self->name);
 331     if (self->has_constval)
 332     {
 333         if (self->vtype == qc_string)
 334             mem_d((void*)self->cvalue.vstring);
 335     }
 336     MEM_VECTOR_CLEAR(self, reads);
 337     MEM_VECTOR_CLEAR(self, writes);
 338     MEM_VECTOR_CLEAR(self, life);
 339     mem_d(self);
 340 }
 341
 342 void ir_value_set_name(ir_value *self, const char *name)
 343 {
 344     if (self->name)
 345         mem_d((void*)self->name);
 346     self->name = util_strdup(name);
 347 }
 348
 349 ir_bool ir_value_set_float(ir_value *self, float f)
 350 {
 351     if (self->vtype != qc_float)
 352         return ifalse;
 353     self->cvalue.vfloat = f;
 354     self->has_constval = itrue;
 355     return itrue;
 356 }
 357
 358 ir_bool ir_value_set_vector(ir_value *self, qc_vec_t v)
 359 {
 360     if (self->vtype != qc_vector)
 361         return ifalse;
 362     self->cvalue.vvec = v;
 363     self->has_constval = itrue;
 364     return itrue;
 365 }
 366
 367 ir_bool ir_value_set_string(ir_value *self, const char *str)
 368 {
 369     if (self->vtype != qc_string)
 370         return ifalse;
 371     self->cvalue.vstring = util_strdup(str);
 372     self->has_constval = itrue;
 373     return itrue;
 374 }
 375
 376 ir_bool ir_value_set_int(ir_value *self, int i)
 377 {
 378     if (self->vtype != qc_int)
 379         return ifalse;
 380     self->cvalue.vint = i;
 381     self->has_constval = itrue;
 382     return itrue;
 383 }
 384
 385 ir_bool ir_value_lives(ir_value *self, size_t at)
 386 {
 387     size_t i;
 388     for (i = 0; i < self->life_count; ++i)
 389     {
 390         ir_life_entry_t *life = &self->life[i];
 391         if (life->start <= at && at <= life->end)
 392             return itrue;
 393         if (life->start > at) /* since it's ordered */
 394             return ifalse;
 395     }
 396     return ifalse;
 397 }
 398
 399 /*
 400 void ir_value_life_remove(ir_value *self, size_t idx)
 401 {
 402     size_t i;
 403     if (idx >= self->life_count)
 404         return;
 405     for (i = idx; i < self->life_count-1; ++i)
 406         self->life[i] = self->life[i+1];
 407     self->life_count--;
 408     if (self->life_count < self->life_alloc/2)
 409     {
 410         self->life_alloc /= 2;
 411         self->life = (ir_life_entry_t*)realloc(self->life,
 412             self->life_alloc * sizeof(ir_life_entry_t));
 413     }
 414 }
 415 */
 416
 417 void ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 418 {
 419     size_t k;
 420     ir_value_life_add(self, e); /* naive... */
 421     for (k = self->life_count-1; k > idx; --k)
 422         self->life[k] = self->life[k-1];
 423     self->life[idx] = e;
 424 }
 425
 426 ir_bool ir_value_life_merge(ir_value *self, size_t s)
 427 {
 428     size_t i;
 429     ir_life_entry_t *life = NULL;
 430     ir_life_entry_t *before = NULL;
 431     ir_life_entry_t new_entry;
 432
 433     /* Find the first range >= s */
 434     for (i = 0; i < self->life_count; ++i)
 435     {
 436         before = life;
 437         life = &self->life[i];
 438         if (life->start > s)
 439             break;
 440     }
 441     /* nothing found? append */
 442     if (i == self->life_count) {
 443         if (life && life->end+1 == s)
 444         {
 445             /* previous life range can be merged in */
 446             life->end++;
 447             return itrue;
 448         }
 449         if (life && life->end >= s)
 450             return ifalse;
 451         ir_life_entry_t e;
 452         e.start = e.end = s;
 453         ir_value_life_add(self, e);
 454         return itrue;
 455     }
 456     /* found */
 457     if (before)
 458     {
 459         if (before->end + 1 == s &&
 460             life->start - 1 == s)
 461         {
 462             /* merge */
 463             before->end = life->end;
 464             ir_value_life_remove(self, i);
 465             return itrue;
 466         }
 467         if (before->end + 1 == s)
 468         {
 469             /* extend before */
 470             before->end++;
 471             return itrue;
 472         }
 473         /* already contained */
 474         if (before->end >= s)
 475             return ifalse;
 476     }
 477     /* extend */
 478     if (life->start - 1 == s)
 479     {
 480         life->start--;
 481         return itrue;
 482     }
 483     /* insert a new entry */
 484     new_entry.start = new_entry.end = s;
 485     ir_value_life_insert(self, i, new_entry);
 486     return itrue;
 487 }