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 qbool 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 qbool 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 qbool 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 qbool 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 qbool 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 void ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 400 {
 401     size_t k;
 402     ir_value_life_add(self, e); /* naive... */
 403     for (k = self->life_count-1; k > idx; --k)
 404         self->life[k] = self->life[k-1];
 405     self->life[idx] = e;
 406 }
 407
 408 qbool ir_value_life_merge(ir_value *self, size_t s)
 409 {
 410     size_t i;
 411     ir_life_entry_t *life = NULL;
 412     ir_life_entry_t *before = NULL;
 413     ir_life_entry_t new_entry;
 414
 415     /* Find the first range >= s */
 416     for (i = 0; i < self->life_count; ++i)
 417     {
 418         before = life;
 419         life = &self->life[i];
 420         if (life->start > s)
 421             break;
 422     }
 423     /* nothing found? append */
 424     if (i == self->life_count) {
 425         if (life && life->end+1 == s)
 426         {
 427             /* previous life range can be merged in */
 428             life->end++;
 429             return itrue;
 430         }
 431         if (life && life->end >= s)
 432             return ifalse;
 433         ir_life_entry_t e;
 434         e.start = e.end = s;
 435         ir_value_life_add(self, e);
 436         return itrue;
 437     }
 438     /* found */
 439     if (before)
 440     {
 441         if (before->end + 1 == s &&
 442             life->start - 1 == s)
 443         {
 444             /* merge */
 445             before->end = life->end;
 446             ir_value_life_remove(self, i);
 447             return itrue;
 448         }
 449         if (before->end + 1 == s)
 450         {
 451             /* extend before */
 452             before->end++;
 453             return itrue;
 454         }
 455         /* already contained */
 456         if (before->end >= s)
 457             return ifalse;
 458     }
 459     /* extend */
 460     if (life->start - 1 == s)
 461     {
 462         life->start--;
 463         return itrue;
 464     }
 465     /* insert a new entry */
 466     new_entry.start = new_entry.end = s;
 467     ir_value_life_insert(self, i, new_entry);
 468     return itrue;
 469 }
 470
 471 /***********************************************************************
 472  *IR main operations
 473  */
 474
 475 qbool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 476 {
 477     if (target->store == qc_localval) {
 478         fprintf(stderr, "cannot store to an SSA value\n");
 479         return ifalse;
 480     } else {
 481         ir_instr *in = ir_instr_new(self, op);
 482         ir_instr_op(in, 0, target, itrue);
 483         ir_instr_op(in, 1, what, ifalse);
 484         ir_block_instr_add(self, in);
 485         return itrue;
 486     }
 487 }
 488
 489 qbool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 490 {
 491     int op = 0;
 492     int vtype;
 493     if (target->vtype == qc_variant)
 494         vtype = what->vtype;
 495     else
 496         vtype = target->vtype;
 497
 498     switch (vtype) {
 499         case qc_float:
 500             if (what->vtype == qc_int)
 501                 op = INSTR_CONV_ITOF;
 502             else
 503                 op = INSTR_STORE_F;
 504             break;
 505         case qc_vector:
 506             op = INSTR_STORE_V;
 507             break;
 508         case qc_entity:
 509             op = INSTR_STORE_ENT;
 510             break;
 511         case qc_string:
 512             op = INSTR_STORE_S;
 513             break;
 514         case qc_int:
 515             if (what->vtype == qc_int)
 516                 op = INSTR_CONV_FTOI;
 517             else
 518                 op = INSTR_STORE_I;
 519             break;
 520         case qc_pointer:
 521             op = INSTR_STORE_I;
 522             break;
 523     }
 524     return ir_block_create_store_op(self, op, target, what);
 525 }
 526
 527 void ir_block_create_return(ir_block *self, ir_value *v)
 528 {
 529     ir_instr *in;
 530     if (self->final) {
 531         fprintf(stderr, "block already ended (%s)\n", self->_label);
 532         return;
 533     }
 534     self->final = itrue;
 535     self->is_return = itrue;
 536     in = ir_instr_new(self, INSTR_RETURN);
 537     ir_instr_op(in, 0, v, ifalse);
 538     ir_block_instr_add(self, in);
 539 }
 540
 541 void ir_block_create_if(ir_block *self, ir_value *v,
 542                         ir_block *ontrue, ir_block *onfalse)
 543 {
 544     ir_instr *in;
 545     if (self->final) {
 546         fprintf(stderr, "block already ended (%s)\n", self->_label);
 547         return;
 548     }
 549     self->final = itrue;
 550     //in = ir_instr_new(self, (v->vtype == qc_string ? INSTR_IF_S : INSTR_IF_F));
 551     in = ir_instr_new(self, VINSTR_COND);
 552     ir_instr_op(in, 0, v, ifalse);
 553     in->bops[0] = ontrue;
 554     in->bops[1] = onfalse;
 555     ir_block_instr_add(self, in);
 556
 557     ir_block_exits_add(self, ontrue);
 558     ir_block_exits_add(self, onfalse);
 559     ir_block_entries_add(ontrue, self);
 560     ir_block_entries_add(onfalse, self);
 561 }
 562
 563 void ir_block_create_jump(ir_block *self, ir_block *to)
 564 {
 565     ir_instr *in;
 566     if (self->final) {
 567         fprintf(stderr, "block already ended (%s)\n", self->_label);
 568         return;
 569     }
 570     self->final = itrue;
 571     in = ir_instr_new(self, VINSTR_JUMP);
 572     in->bops[0] = to;
 573     ir_block_instr_add(self, in);
 574
 575     ir_block_exits_add(self, to);
 576     ir_block_entries_add(to, self);
 577 }
 578
 579 void ir_block_create_goto(ir_block *self, ir_block *to)
 580 {
 581     ir_instr *in;
 582     if (self->final) {
 583         fprintf(stderr, "block already ended (%s)\n", self->_label);
 584         return;
 585     }
 586     self->final = itrue;
 587     in = ir_instr_new(self, INSTR_GOTO);
 588     in->bops[0] = to;
 589     ir_block_instr_add(self, in);
 590
 591     ir_block_exits_add(self, to);
 592     ir_block_entries_add(to, self);
 593 }
 594
 595 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
 596 {
 597     ir_value *out;
 598     ir_instr *in;
 599     in = ir_instr_new(self, VINSTR_PHI);
 600     out = ir_value_out(self->owner, label, qc_localval, ot);
 601     ir_instr_op(in, 0, out, itrue);
 602     ir_block_instr_add(self, in);
 603     return in;
 604 }
 605
 606 ir_value* ir_phi_value(ir_instr *self)
 607 {
 608     return self->_ops[0];
 609 }
 610
 611 void ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
 612 {
 613     ir_phi_entry_t pe;
 614
 615     if (!ir_block_entries_find(self->owner, b, NULL)) {
 616         /* Must not be possible to cause this, otherwise the AST
 617          * is doing something wrong.
 618          */
 619         fprintf(stderr, "Invalid entry block for PHI\n");
 620         abort();
 621     }
 622
 623     pe.value = v;
 624     pe.from = b;
 625     ir_value_reads_add(v, self);
 626     ir_instr_phi_add(self, pe);
 627 }