ir.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "gmqcc.h"
   4 #include "ir.h"
   5
   6 /***********************************************************************
   7  *IR Builder
   8  */
   9
  10 ir_builder* ir_builder_new(const char *modulename)
  11 {
  12     ir_builder* self;
  13
  14     self = (ir_builder*)mem_a(sizeof(*self));
  15     MEM_VECTOR_INIT(self, functions);
  16     MEM_VECTOR_INIT(self, globals);
  17     self->name = NULL;
  18     ir_builder_set_name(self, modulename);
  19
  20     /* globals which always exist */
  21
  22     /* for now we give it a vector size */
  23     ir_builder_create_global(self, "OFS_RETURN", qc_variant);
  24
  25     return self;
  26 }
  27
  28 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, globals)
  29 MEM_VEC_FUNCTIONS(ir_builder, ir_function*, functions)
  30
  31 void ir_builder_delete(ir_builder* self)
  32 {
  33     size_t i;
  34     mem_d((void*)self->name);
  35     for (i = 0; i != self->functions_count; ++i) {
  36         ir_function_delete(self->functions[i]);
  37     }
  38     MEM_VECTOR_CLEAR(self, functions);
  39     for (i = 0; i != self->globals_count; ++i) {
  40         ir_value_delete(self->globals[i]);
  41     }
  42     MEM_VECTOR_CLEAR(self, globals);
  43     mem_d(self);
  44 }
  45
  46 void ir_builder_set_name(ir_builder *self, const char *name)
  47 {
  48     if (self->name)
  49         mem_d((void*)self->name);
  50     self->name = util_strdup(name);
  51 }
  52
  53 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
  54 {
  55     size_t i;
  56     for (i = 0; i < self->functions_count; ++i) {
  57         if (!strcmp(name, self->functions[i]->name))
  58             return self->functions[i];
  59     }
  60     return NULL;
  61 }
  62
  63 ir_function* ir_builder_create_function(ir_builder *self, const char *name)
  64 {
  65     ir_function *fn = ir_builder_get_function(self, name);
  66     if (fn) {
  67         return NULL;
  68     }
  69
  70     fn = ir_function_new(self);
  71     ir_function_set_name(fn, name);
  72     ir_builder_functions_add(self, fn);
  73     return fn;
  74 }
  75
  76 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
  77 {
  78     size_t i;
  79     for (i = 0; i < self->globals_count; ++i) {
  80         if (!strcmp(self->globals[i]->name, name))
  81             return self->globals[i];
  82     }
  83     return NULL;
  84 }
  85
  86 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
  87 {
  88     ir_value *ve = ir_builder_get_global(self, name);
  89     if (ve) {
  90         return NULL;
  91     }
  92
  93     ve = ir_value_var(name, store_global, vtype);
  94     ir_builder_globals_add(self, ve);
  95     return ve;
  96 }
  97
  98 /***********************************************************************
  99  *IR Function
 100  */
 101
 102 void ir_function_naive_phi(ir_function*);
 103 void ir_function_enumerate(ir_function*);
 104 void ir_function_calculate_liferanges(ir_function*);
 105
 106 ir_function* ir_function_new(ir_builder* owner)
 107 {
 108     ir_function *self;
 109     self = (ir_function*)mem_a(sizeof(*self));
 110     self->owner = owner;
 111     self->context.file = "<@no context>";
 112     self->context.line = 0;
 113     self->retype = qc_void;
 114     MEM_VECTOR_INIT(self, params);
 115     MEM_VECTOR_INIT(self, blocks);
 116     MEM_VECTOR_INIT(self, values);
 117     MEM_VECTOR_INIT(self, locals);
 118     ir_function_set_name(self, "<@unnamed>");
 119
 120     self->run_id = 0;
 121     return self;
 122 }
 123 MEM_VEC_FUNCTIONS(ir_function, ir_value*, values)
 124 MEM_VEC_FUNCTIONS(ir_function, ir_block*, blocks)
 125 MEM_VEC_FUNCTIONS(ir_function, ir_value*, locals)
 126
 127 void ir_function_set_name(ir_function *self, const char *name)
 128 {
 129     if (self->name)
 130         mem_d((void*)self->name);
 131     self->name = util_strdup(name);
 132 }
 133
 134 void ir_function_delete(ir_function *self)
 135 {
 136     size_t i;
 137     mem_d((void*)self->name);
 138
 139     for (i = 0; i != self->blocks_count; ++i)
 140         ir_block_delete(self->blocks[i]);
 141     MEM_VECTOR_CLEAR(self, blocks);
 142
 143     MEM_VECTOR_CLEAR(self, params);
 144
 145     for (i = 0; i != self->values_count; ++i)
 146         ir_value_delete(self->values[i]);
 147     MEM_VECTOR_CLEAR(self, values);
 148
 149     for (i = 0; i != self->locals_count; ++i)
 150         ir_value_delete(self->locals[i]);
 151     MEM_VECTOR_CLEAR(self, locals);
 152
 153     mem_d(self);
 154 }
 155
 156 void ir_function_collect_value(ir_function *self, ir_value *v)
 157 {
 158     ir_function_values_add(self, v);
 159 }
 160
 161 ir_block* ir_function_create_block(ir_function *self, const char *label)
 162 {
 163     ir_block* bn = ir_block_new(self, label);
 164     memcpy(&bn->context, &self->context, sizeof(self->context));
 165     ir_function_blocks_add(self, bn);
 166     return bn;
 167 }
 168
 169 void ir_function_finalize(ir_function *self)
 170 {
 171     ir_function_naive_phi(self);
 172     ir_function_enumerate(self);
 173     ir_function_calculate_liferanges(self);
 174 }
 175
 176 ir_value* ir_function_get_local(ir_function *self, const char *name)
 177 {
 178     size_t i;
 179     for (i = 0; i < self->locals_count; ++i) {
 180         if (!strcmp(self->locals[i]->name, name))
 181             return self->locals[i];
 182     }
 183     return NULL;
 184 }
 185
 186 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype)
 187 {
 188     ir_value *ve = ir_function_get_local(self, name);
 189     if (ve) {
 190         return NULL;
 191     }
 192
 193     ve = ir_value_var(name, store_local, vtype);
 194     ir_function_locals_add(self, ve);
 195     return ve;
 196 }
 197
 198 /***********************************************************************
 199  *IR Block
 200  */
 201
 202 ir_block* ir_block_new(ir_function* owner, const char *name)
 203 {
 204     ir_block *self;
 205     self = (ir_block*)mem_a(sizeof(*self));
 206     self->owner = owner;
 207     self->context.file = "<@no context>";
 208     self->context.line = 0;
 209     self->final = false;
 210     MEM_VECTOR_INIT(self, instr);
 211     MEM_VECTOR_INIT(self, entries);
 212     MEM_VECTOR_INIT(self, exits);
 213     self->label = NULL;
 214     ir_block_set_label(self, name);
 215
 216     self->eid = 0;
 217     self->is_return = false;
 218     self->run_id = 0;
 219     MEM_VECTOR_INIT(self, living);
 220     return self;
 221 }
 222 MEM_VEC_FUNCTIONS(ir_block, ir_instr*, instr)
 223 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, entries)
 224 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, exits)
 225 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_value*, living)
 226
 227 void ir_block_delete(ir_block* self)
 228 {
 229     size_t i;
 230     mem_d((void*)self->label);
 231     for (i = 0; i != self->instr_count; ++i)
 232         ir_instr_delete(self->instr[i]);
 233     MEM_VECTOR_CLEAR(self, instr);
 234     MEM_VECTOR_CLEAR(self, entries);
 235     MEM_VECTOR_CLEAR(self, exits);
 236     MEM_VECTOR_CLEAR(self, living);
 237     mem_d(self);
 238 }
 239
 240 void ir_block_set_label(ir_block *self, const char *name)
 241 {
 242     if (self->label)
 243         mem_d((void*)self->label);
 244     self->label = util_strdup(name);
 245 }
 246
 247 /***********************************************************************
 248  *IR Instructions
 249  */
 250
 251 ir_instr* ir_instr_new(ir_block* owner, int op)
 252 {
 253     ir_instr *self;
 254     self = (ir_instr*)mem_a(sizeof(*self));
 255     self->owner = owner;
 256     self->context.file = "<@no context>";
 257     self->context.line = 0;
 258     self->opcode = op;
 259     self->_ops[0] = NULL;
 260     self->_ops[1] = NULL;
 261     self->_ops[2] = NULL;
 262     self->bops[0] = NULL;
 263     self->bops[1] = NULL;
 264     MEM_VECTOR_INIT(self, phi);
 265
 266     self->eid = 0;
 267     return self;
 268 }
 269 MEM_VEC_FUNCTIONS(ir_instr, ir_phi_entry_t, phi)
 270
 271 void ir_instr_delete(ir_instr *self)
 272 {
 273     ir_instr_op(self, 0, NULL, false);
 274     ir_instr_op(self, 1, NULL, false);
 275     ir_instr_op(self, 2, NULL, false);
 276     MEM_VECTOR_CLEAR(self, phi);
 277     mem_d(self);
 278 }
 279
 280 void ir_instr_op(ir_instr *self, int op, ir_value *v, qbool writing)
 281 {
 282     if (self->_ops[op]) {
 283         if (writing)
 284             ir_value_writes_add(self->_ops[op], self);
 285         else
 286             ir_value_reads_add(self->_ops[op], self);
 287     }
 288     if (v) {
 289         if (writing)
 290             ir_value_writes_add(v, self);
 291         else
 292             ir_value_reads_add(v, self);
 293     }
 294     self->_ops[op] = v;
 295 }
 296
 297 /***********************************************************************
 298  *IR Value
 299  */
 300
 301 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 302 {
 303     ir_value *self;
 304     self = (ir_value*)mem_a(sizeof(*self));
 305     self->vtype = vtype;
 306     self->store = storetype;
 307     MEM_VECTOR_INIT(self, reads);
 308     MEM_VECTOR_INIT(self, writes);
 309     self->isconst = false;
 310     self->context.file = "<@no context>";
 311     self->context.line = 0;
 312     self->name = NULL;
 313     ir_value_set_name(self, name);
 314
 315     MEM_VECTOR_INIT(self, life);
 316     return self;
 317 }
 318 MEM_VEC_FUNCTIONS(ir_value, ir_life_entry_t, life)
 319 MEM_VEC_FUNCTIONS(ir_value, ir_instr*, reads)
 320 MEM_VEC_FUNCTIONS(ir_value, ir_instr*, writes)
 321
 322 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 323 {
 324     ir_value *v = ir_value_var(name, storetype, vtype);
 325     ir_function_collect_value(owner, v);
 326     return v;
 327 }
 328
 329 void ir_value_delete(ir_value* self)
 330 {
 331     mem_d((void*)self->name);
 332     if (self->isconst)
 333     {
 334         if (self->vtype == qc_string)
 335             mem_d((void*)self->constval.vstring);
 336     }
 337     MEM_VECTOR_CLEAR(self, reads);
 338     MEM_VECTOR_CLEAR(self, writes);
 339     MEM_VECTOR_CLEAR(self, life);
 340     mem_d(self);
 341 }
 342
 343 void ir_value_set_name(ir_value *self, const char *name)
 344 {
 345     if (self->name)
 346         mem_d((void*)self->name);
 347     self->name = util_strdup(name);
 348 }
 349
 350 qbool ir_value_set_float(ir_value *self, float f)
 351 {
 352     if (self->vtype != qc_float)
 353         return false;
 354     self->constval.vfloat = f;
 355     self->isconst = true;
 356     return true;
 357 }
 358
 359 qbool ir_value_set_vector(ir_value *self, vector_t v)
 360 {
 361     if (self->vtype != qc_vector)
 362         return false;
 363     self->constval.vvec = v;
 364     self->isconst = true;
 365     return true;
 366 }
 367
 368 qbool ir_value_set_string(ir_value *self, const char *str)
 369 {
 370     if (self->vtype != qc_string)
 371         return false;
 372     self->constval.vstring = util_strdup(str);
 373     self->isconst = true;
 374     return true;
 375 }
 376
 377 qbool ir_value_set_int(ir_value *self, int i)
 378 {
 379     if (self->vtype != qc_int)
 380         return false;
 381     self->constval.vint = i;
 382     self->isconst = true;
 383     return true;
 384 }
 385
 386 qbool ir_value_lives(ir_value *self, size_t at)
 387 {
 388     size_t i;
 389     for (i = 0; i < self->life_count; ++i)
 390     {
 391         ir_life_entry_t *life = &self->life[i];
 392         if (life->start <= at && at <= life->end)
 393             return true;
 394         if (life->start > at) /* since it's ordered */
 395             return false;
 396     }
 397     return false;
 398 }
 399
 400 void ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 401 {
 402     size_t k;
 403     ir_value_life_add(self, e); /* naive... */
 404     for (k = self->life_count-1; k > idx; --k)
 405         self->life[k] = self->life[k-1];
 406     self->life[idx] = e;
 407 }
 408
 409 qbool ir_value_life_merge(ir_value *self, size_t s)
 410 {
 411     size_t i;
 412     ir_life_entry_t *life = NULL;
 413     ir_life_entry_t *before = NULL;
 414     ir_life_entry_t new_entry;
 415
 416     /* Find the first range >= s */
 417     for (i = 0; i < self->life_count; ++i)
 418     {
 419         before = life;
 420         life = &self->life[i];
 421         if (life->start > s)
 422             break;
 423     }
 424     /* nothing found? append */
 425     if (i == self->life_count) {
 426         if (life && life->end+1 == s)
 427         {
 428             /* previous life range can be merged in */
 429             life->end++;
 430             return true;
 431         }
 432         if (life && life->end >= s)
 433             return false;
 434         ir_life_entry_t e;
 435         e.start = e.end = s;
 436         ir_value_life_add(self, e);
 437         return true;
 438     }
 439     /* found */
 440     if (before)
 441     {
 442         if (before->end + 1 == s &&
 443             life->start - 1 == s)
 444         {
 445             /* merge */
 446             before->end = life->end;
 447             ir_value_life_remove(self, i);
 448             return true;
 449         }
 450         if (before->end + 1 == s)
 451         {
 452             /* extend before */
 453             before->end++;
 454             return true;
 455         }
 456         /* already contained */
 457         if (before->end >= s)
 458             return false;
 459     }
 460     /* extend */
 461     if (life->start - 1 == s)
 462     {
 463         life->start--;
 464         return true;
 465     }
 466     /* insert a new entry */
 467     new_entry.start = new_entry.end = s;
 468     ir_value_life_insert(self, i, new_entry);
 469     return true;
 470 }
 471
 472 /***********************************************************************
 473  *IR main operations
 474  */
 475
 476 qbool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 477 {
 478     if (target->store == store_value) {
 479         fprintf(stderr, "cannot store to an SSA value\n");
 480         return false;
 481     } else {
 482         ir_instr *in = ir_instr_new(self, op);
 483         ir_instr_op(in, 0, target, true);
 484         ir_instr_op(in, 1, what, false);
 485         ir_block_instr_add(self, in);
 486         return true;
 487     }
 488 }
 489
 490 qbool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 491 {
 492     int op = 0;
 493     int vtype;
 494     if (target->vtype == qc_variant)
 495         vtype = what->vtype;
 496     else
 497         vtype = target->vtype;
 498
 499     switch (vtype) {
 500         case qc_float:
 501 #if 0
 502             if (what->vtype == qc_int)
 503                 op = INSTR_CONV_ITOF;
 504             else
 505 #endif
 506                 op = INSTR_STORE_F;
 507             break;
 508         case qc_vector:
 509             op = INSTR_STORE_V;
 510             break;
 511         case qc_entity:
 512             op = INSTR_STORE_ENT;
 513             break;
 514         case qc_string:
 515             op = INSTR_STORE_S;
 516             break;
 517 #if 0
 518         case qc_int:
 519             if (what->vtype == qc_int)
 520                 op = INSTR_CONV_FTOI;
 521             else
 522                 op = INSTR_STORE_I;
 523             break;
 524 #endif
 525         case qc_pointer:
 526 #if 0
 527             op = INSTR_STORE_I;
 528 #else
 529             op = INSTR_STORE_ENT;
 530 #endif
 531             break;
 532     }
 533     return ir_block_create_store_op(self, op, target, what);
 534 }
 535
 536 void ir_block_create_return(ir_block *self, ir_value *v)
 537 {
 538     ir_instr *in;
 539     if (self->final) {
 540         fprintf(stderr, "block already ended (%s)\n", self->label);
 541         return;
 542     }
 543     self->final = true;
 544     self->is_return = true;
 545     in = ir_instr_new(self, INSTR_RETURN);
 546     ir_instr_op(in, 0, v, false);
 547     ir_block_instr_add(self, in);
 548 }
 549
 550 void ir_block_create_if(ir_block *self, ir_value *v,
 551                         ir_block *ontrue, ir_block *onfalse)
 552 {
 553     ir_instr *in;
 554     if (self->final) {
 555         fprintf(stderr, "block already ended (%s)\n", self->label);
 556         return;
 557     }
 558     self->final = true;
 559     //in = ir_instr_new(self, (v->vtype == qc_string ? INSTR_IF_S : INSTR_IF_F));
 560     in = ir_instr_new(self, VINSTR_COND);
 561     ir_instr_op(in, 0, v, false);
 562     in->bops[0] = ontrue;
 563     in->bops[1] = onfalse;
 564     ir_block_instr_add(self, in);
 565
 566     ir_block_exits_add(self, ontrue);
 567     ir_block_exits_add(self, onfalse);
 568     ir_block_entries_add(ontrue, self);
 569     ir_block_entries_add(onfalse, self);
 570 }
 571
 572 void ir_block_create_jump(ir_block *self, ir_block *to)
 573 {
 574     ir_instr *in;
 575     if (self->final) {
 576         fprintf(stderr, "block already ended (%s)\n", self->label);
 577         return;
 578     }
 579     self->final = true;
 580     in = ir_instr_new(self, VINSTR_JUMP);
 581     in->bops[0] = to;
 582     ir_block_instr_add(self, in);
 583
 584     ir_block_exits_add(self, to);
 585     ir_block_entries_add(to, self);
 586 }
 587
 588 void ir_block_create_goto(ir_block *self, ir_block *to)
 589 {
 590     ir_instr *in;
 591     if (self->final) {
 592         fprintf(stderr, "block already ended (%s)\n", self->label);
 593         return;
 594     }
 595     self->final = true;
 596     in = ir_instr_new(self, INSTR_GOTO);
 597     in->bops[0] = to;
 598     ir_block_instr_add(self, in);
 599
 600     ir_block_exits_add(self, to);
 601     ir_block_entries_add(to, self);
 602 }
 603
 604 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
 605 {
 606     ir_value *out;
 607     ir_instr *in;
 608     in = ir_instr_new(self, VINSTR_PHI);
 609     out = ir_value_out(self->owner, label, store_local, ot);
 610     ir_instr_op(in, 0, out, true);
 611     ir_block_instr_add(self, in);
 612     return in;
 613 }
 614
 615 ir_value* ir_phi_value(ir_instr *self)
 616 {
 617     return self->_ops[0];
 618 }
 619
 620 void ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
 621 {
 622     ir_phi_entry_t pe;
 623
 624     if (!ir_block_entries_find(self->owner, b, NULL)) {
 625         /* Must not be possible to cause this, otherwise the AST
 626          * is doing something wrong.
 627          */
 628         fprintf(stderr, "Invalid entry block for PHI\n");
 629         abort();
 630     }
 631
 632     pe.value = v;
 633     pe.from = b;
 634     ir_value_reads_add(v, self);
 635     ir_instr_phi_add(self, pe);
 636 }
 637
 638 /* binary op related code */
 639
 640 ir_value* ir_block_create_binop(ir_block *self,
 641                                 const char *label, int opcode,
 642                                 ir_value *left, ir_value *right)
 643 {
 644     int ot = qc_void;
 645     switch (opcode) {
 646         case INSTR_ADD_F:
 647         case INSTR_SUB_F:
 648         case INSTR_DIV_F:
 649         case INSTR_MUL_F:
 650         case INSTR_MUL_V:
 651         case INSTR_AND:
 652         case INSTR_OR:
 653 #if 0
 654         case INSTR_AND_I:
 655         case INSTR_AND_IF:
 656         case INSTR_AND_FI:
 657         case INSTR_OR_I:
 658         case INSTR_OR_IF:
 659         case INSTR_OR_FI:
 660 #endif
 661         case INSTR_BITAND:
 662         case INSTR_BITOR:
 663 #if 0
 664         case INSTR_SUB_S: /* -- offset of string as float */
 665         case INSTR_MUL_IF:
 666         case INSTR_MUL_FI:
 667         case INSTR_DIV_IF:
 668         case INSTR_DIV_FI:
 669         case INSTR_BITOR_IF:
 670         case INSTR_BITOR_FI:
 671         case INSTR_BITAND_FI:
 672         case INSTR_BITAND_IF:
 673         case INSTR_EQ_I:
 674         case INSTR_NE_I:
 675 #endif
 676             ot = qc_float;
 677             break;
 678 #if 0
 679         case INSTR_ADD_I:
 680         case INSTR_ADD_IF:
 681         case INSTR_ADD_FI:
 682         case INSTR_SUB_I:
 683         case INSTR_SUB_FI:
 684         case INSTR_SUB_IF:
 685         case INSTR_MUL_I:
 686         case INSTR_DIV_I:
 687         case INSTR_BITAND_I:
 688         case INSTR_BITOR_I:
 689         case INSTR_XOR_I:
 690         case INSTR_RSHIFT_I:
 691         case INSTR_LSHIFT_I:
 692             ot = qc_int;
 693             break;
 694 #endif
 695         case INSTR_ADD_V:
 696         case INSTR_SUB_V:
 697         case INSTR_MUL_VF:
 698         case INSTR_MUL_FV:
 699 #if 0
 700         case INSTR_DIV_VF:
 701         case INSTR_MUL_IV:
 702         case INSTR_MUL_VI:
 703 #endif
 704             ot = qc_vector;
 705             break;
 706 #if 0
 707         case INSTR_ADD_SF:
 708             ot = qc_pointer;
 709             break;
 710 #endif
 711         default:
 712             // ranges:
 713             /* boolean operations result in floats */
 714             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
 715                 ot = qc_float;
 716             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
 717                 ot = qc_float;
 718 #if 0
 719             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
 720                 ot = qc_float;
 721 #endif
 722             break;
 723     };
 724     if (ot == qc_void) {
 725         /* The AST or parser were supposed to check this! */
 726         abort();
 727         return NULL;
 728     }
 729     ir_value *out = ir_value_out(self->owner, label, store_local, ot);
 730     ir_instr *in = ir_instr_new(self, opcode);
 731     ir_instr_op(in, 0, out, true);
 732     ir_instr_op(in, 1, left, false);
 733     ir_instr_op(in, 2, right, false);
 734     ir_block_instr_add(self, in);
 735     return out;
 736 }
 737
 738 ir_value* ir_block_create_add(ir_block *self,
 739                               const char *label,
 740                               ir_value *left, ir_value *right)
 741 {
 742     int op = 0;
 743     int l = left->vtype;
 744     int r = right->vtype;
 745     if (l == r) {
 746         switch (l) {
 747             default:
 748                 return NULL;
 749             case qc_float:
 750                 op = INSTR_ADD_F;
 751                 break;
 752 #if 0
 753             case qc_int:
 754                 op = INSTR_ADD_I;
 755                 break;
 756 #endif
 757             case qc_vector:
 758                 op = INSTR_ADD_V;
 759                 break;
 760         }
 761     } else {
 762 #if 0
 763         if ( (l == qc_float && r == qc_int) )
 764             op = INSTR_ADD_FI;
 765         else if ( (l == qc_int && r == qc_float) )
 766             op = INSTR_ADD_IF;
 767         else
 768 #endif
 769             return NULL;
 770     }
 771     return ir_block_create_binop(self, label, op, left, right);
 772 }
 773
 774 ir_value* ir_block_create_sub(ir_block *self,
 775                               const char *label,
 776                               ir_value *left, ir_value *right)
 777 {
 778     int op = 0;
 779     int l = left->vtype;
 780     int r = right->vtype;
 781     if (l == r) {
 782
 783         switch (l) {
 784             default:
 785                 return NULL;
 786             case qc_float:
 787                 op = INSTR_SUB_F;
 788                 break;
 789 #if 0
 790             case qc_int:
 791                 op = INSTR_SUB_I;
 792                 break;
 793 #endif
 794             case qc_vector:
 795                 op = INSTR_SUB_V;
 796                 break;
 797         }
 798     } else {
 799 #if 0
 800         if ( (l == qc_float && r == qc_int) )
 801             op = INSTR_SUB_FI;
 802         else if ( (l == qc_int && r == qc_float) )
 803             op = INSTR_SUB_IF;
 804         else
 805 #endif
 806             return NULL;
 807     }
 808     return ir_block_create_binop(self, label, op, left, right);
 809 }
 810
 811 ir_value* ir_block_create_mul(ir_block *self,
 812                               const char *label,
 813                               ir_value *left, ir_value *right)
 814 {
 815     int op = 0;
 816     int l = left->vtype;
 817     int r = right->vtype;
 818     if (l == r) {
 819
 820         switch (l) {
 821             default:
 822                 return NULL;
 823             case qc_float:
 824                 op = INSTR_MUL_F;
 825                 break;
 826 #if 0
 827             case qc_int:
 828                 op = INSTR_MUL_I;
 829                 break;
 830 #endif
 831             case qc_vector:
 832                 op = INSTR_MUL_V;
 833                 break;
 834         }
 835     } else {
 836         if ( (l == qc_vector && r == qc_float) )
 837             op = INSTR_MUL_VF;
 838         else if ( (l == qc_float && r == qc_vector) )
 839             op = INSTR_MUL_FV;
 840 #if 0
 841         else if ( (l == qc_vector && r == qc_int) )
 842             op = INSTR_MUL_VI;
 843         else if ( (l == qc_int && r == qc_vector) )
 844             op = INSTR_MUL_IV;
 845         else if ( (l == qc_float && r == qc_int) )
 846             op = INSTR_MUL_FI;
 847         else if ( (l == qc_int && r == qc_float) )
 848             op = INSTR_MUL_IF;
 849 #endif
 850         else
 851             return NULL;
 852     }
 853     return ir_block_create_binop(self, label, op, left, right);
 854 }
 855
 856 ir_value* ir_block_create_div(ir_block *self,
 857                               const char *label,
 858                               ir_value *left, ir_value *right)
 859 {
 860     int op = 0;
 861     int l = left->vtype;
 862     int r = right->vtype;
 863     if (l == r) {
 864
 865         switch (l) {
 866             default:
 867                 return NULL;
 868             case qc_float:
 869                 op = INSTR_DIV_F;
 870                 break;
 871 #if 0
 872             case qc_int:
 873                 op = INSTR_DIV_I;
 874                 break;
 875 #endif
 876         }
 877     } else {
 878 #if 0
 879         if ( (l == qc_vector && r == qc_float) )
 880             op = INSTR_DIV_VF;
 881         else if ( (l == qc_float && r == qc_int) )
 882             op = INSTR_DIV_FI;
 883         else if ( (l == qc_int && r == qc_float) )
 884             op = INSTR_DIV_IF;
 885         else
 886 #endif
 887             return NULL;
 888     }
 889     return ir_block_create_binop(self, label, op, left, right);
 890 }
 891
 892 /* PHI resolving breaks the SSA, and must thus be the last
 893  * step before life-range calculation.
 894  */
 895
 896 static void ir_block_naive_phi(ir_block *self);
 897 void ir_function_naive_phi(ir_function *self)
 898 {
 899     size_t i;
 900
 901     for (i = 0; i < self->blocks_count; ++i)
 902         ir_block_naive_phi(self->blocks[i]);
 903 }
 904
 905 static void ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
 906 {
 907     ir_instr *instr;
 908     size_t i;
 909
 910     /* create a store */
 911     ir_block_create_store(block, old, what);
 912
 913     /* we now move it up */
 914     instr = block->instr[block->instr_count-1];
 915     for (i = block->instr_count; i > iid; --i)
 916         block->instr[i] = block->instr[i-1];
 917     block->instr[i] = instr;
 918 }
 919
 920 static void ir_block_naive_phi(ir_block *self)
 921 {
 922     size_t i, p, w;
 923     /* FIXME: optionally, create_phi can add the phis
 924      * to a list so we don't need to loop through blocks
 925      * - anyway: "don't optimize YET"
 926      */
 927     for (i = 0; i < self->instr_count; ++i)
 928     {
 929         ir_instr *instr = self->instr[i];
 930         if (instr->opcode != VINSTR_PHI)
 931             continue;
 932
 933         ir_block_instr_remove(self, i);
 934         --i; /* NOTE: i+1 below */
 935
 936         for (p = 0; p < instr->phi_count; ++p)
 937         {
 938             ir_value *v = instr->phi[p].value;
 939             for (w = 0; w < v->writes_count; ++w) {
 940                 ir_value *old;
 941
 942                 if (!v->writes[w]->_ops[0])
 943                     continue;
 944
 945                 /* When the write was to a global, we have to emit a mov */
 946                 old = v->writes[w]->_ops[0];
 947
 948                 /* The original instruction now writes to the PHI target local */
 949                 if (v->writes[w]->_ops[0] == v)
 950                     v->writes[w]->_ops[0] = instr->_ops[0];
 951
 952                 if (old->store != store_local)
 953                 {
 954                     /* If it originally wrote to a global we need to store the value
 955                      * there as welli
 956                      */
 957                     ir_naive_phi_emit_store(self, i+1, old, v);
 958                     if (i+1 < self->instr_count)
 959                         instr = self->instr[i+1];
 960                     else
 961                         instr = NULL;
 962                     /* In case I forget and access instr later, it'll be NULL
 963                      * when it's a problem, to make sure we crash, rather than accessing
 964                      * invalid data.
 965                      */
 966                 }
 967                 else
 968                 {
 969                     /* If it didn't, we can replace all reads by the phi target now. */
 970                     size_t r;
 971                     for (r = 0; r < old->reads_count; ++r)
 972                     {
 973                         size_t op;
 974                         ir_instr *ri = old->reads[r];
 975                         for (op = 0; op < ri->phi_count; ++op) {
 976                             if (ri->phi[op].value == old)
 977                                 ri->phi[op].value = v;
 978                         }
 979                         for (op = 0; op < 3; ++op) {
 980                             if (ri->_ops[op] == old)
 981                                 ri->_ops[op] = v;
 982                         }
 983                     }
 984                 }
 985             }
 986         }
 987         ir_instr_delete(instr);
 988     }
 989 }
 990
 991 /***********************************************************************
 992  *IR Temp allocation code
 993  * Propagating value life ranges by walking through the function backwards
 994  * until no more changes are made.
 995  * In theory this should happen once more than once for every nested loop
 996  * level.
 997  * Though this implementation might run an additional time for if nests.
 998  */
 999
1000 typedef struct
1001 {
1002     ir_value* *v;
1003     size_t    v_count;
1004     size_t    v_alloc;
1005 } new_reads_t;
1006 MEM_VEC_FUNCTIONS_ALL(new_reads_t, ir_value*, v)
1007
1008 /* Enumerate instructions used by value's life-ranges
1009  */
1010 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1011 {
1012     size_t i;
1013     size_t eid = *_eid;
1014     for (i = 0; i < self->instr_count; ++i)
1015     {
1016         self->instr[i]->eid = eid++;
1017     }
1018     *_eid = eid;
1019 }
1020
1021 /* Enumerate blocks and instructions.
1022  * The block-enumeration is unordered!
1023  * We do not really use the block enumreation, however
1024  * the instruction enumeration is important for life-ranges.
1025  */
1026 void ir_function_enumerate(ir_function *self)
1027 {
1028     size_t i;
1029     size_t instruction_id = 0;
1030     for (i = 0; i < self->blocks_count; ++i)
1031     {
1032         self->blocks[i]->eid = i;
1033         self->blocks[i]->run_id = 0;
1034         ir_block_enumerate(self->blocks[i], &instruction_id);
1035     }
1036 }
1037
1038 static void ir_block_life_propagate(ir_block *b, ir_block *prev, qbool *changed);
1039 void ir_function_calculate_liferanges(ir_function *self)
1040 {
1041     size_t i;
1042     qbool changed;
1043
1044     do {
1045         self->run_id++;
1046         changed = false;
1047         for (i = 0; i != self->blocks_count; ++i)
1048         {
1049             if (self->blocks[i]->is_return)
1050                 ir_block_life_propagate(self->blocks[i], NULL, &changed);
1051         }
1052     } while (changed);
1053 }
1054
1055 /* Get information about which operand
1056  * is read from, or written to.
1057  */
1058 static void ir_op_read_write(int op, size_t *read, size_t *write)
1059 {
1060     switch (op)
1061     {
1062     case VINSTR_JUMP:
1063     case INSTR_GOTO:
1064         *write = 0;
1065         *read = 0;
1066         break;
1067     case INSTR_IF:
1068     case INSTR_IFNOT:
1069 #if 0
1070     case INSTR_IF_S:
1071     case INSTR_IFNOT_S:
1072 #endif
1073     case INSTR_RETURN:
1074     case VINSTR_COND:
1075         *write = 0;
1076         *read = 1;
1077         break;
1078     default:
1079         *write = 1;
1080         *read = 6;
1081         break;
1082     };
1083 }
1084
1085 static qbool ir_block_living_add_instr(ir_block *self, size_t eid)
1086 {
1087     size_t i;
1088     qbool changed = false;
1089     qbool tempbool;
1090     for (i = 0; i != self->living_count; ++i)
1091     {
1092         tempbool = ir_value_life_merge(self->living[i], eid);
1093         /* debug
1094         if (tempbool)
1095             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1096         */
1097         changed = changed || tempbool;
1098     }
1099     return changed;
1100 }
1101
1102 static void ir_block_life_prop_previous(ir_block* self, ir_block *prev, qbool *changed)
1103 {
1104     size_t i;
1105     /* values which have been read in a previous iteration are now
1106      * in the "living" array even if the previous block doesn't use them.
1107      * So we have to remove whatever does not exist in the previous block.
1108      * They will be re-added on-read, but the liferange merge won't cause
1109      * a change.
1110      */
1111     for (i = 0; i < self->living_count; ++i)
1112     {
1113         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1114             ir_block_living_remove(self, i);
1115             --i;
1116         }
1117     }
1118
1119     /* Whatever the previous block still has in its living set
1120      * must now be added to ours as well.
1121      */
1122     for (i = 0; i < prev->living_count; ++i)
1123     {
1124         if (ir_block_living_find(self, prev->living[i], NULL))
1125             continue;
1126         ir_block_living_add(self, prev->living[i]);
1127         /*
1128         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1129         */
1130     }
1131 }
1132
1133 static void ir_block_life_propagate(ir_block *self, ir_block *prev, qbool *changed)
1134 {
1135     ir_instr *instr;
1136     ir_value *value;
1137     qbool  tempbool;
1138     size_t i, o, p, rd;
1139     /* bitmasks which operands are read from or written to */
1140     size_t read, write;
1141     new_reads_t new_reads;
1142     char dbg_ind[16] = { '#', '0' };
1143     (void)dbg_ind;
1144
1145     MEM_VECTOR_INIT(&new_reads, v);
1146
1147     if (prev)
1148         ir_block_life_prop_previous(self, prev, changed);
1149
1150     i = self->instr_count;
1151     while (i)
1152     { --i;
1153         instr = self->instr[i];
1154
1155         /* PHI operands are always read operands */
1156         for (p = 0; p < instr->phi_count; ++p)
1157         {
1158             value = instr->phi[p].value;
1159             /* used this before new_reads - puts the last read into the life range as well
1160             if (!ir_block_living_find(self, value, NULL))
1161                 ir_block_living_add(self, value);
1162             */
1163             /* fprintf(stderr, "read: %s\n", value->_name); */
1164             if (!new_reads_t_v_find(&new_reads, value, NULL))
1165                 new_reads_t_v_add(&new_reads, value);
1166         }
1167
1168         /* See which operands are read and write operands */
1169         ir_op_read_write(instr->opcode, &read, &write);
1170
1171         /* Go through the 3 main operands */
1172         for (o = 0; o < 3; ++o)
1173         {
1174             if (!instr->_ops[o]) /* no such operand */
1175                 continue;
1176
1177             value = instr->_ops[o];
1178
1179             /* We only care about locals */
1180             if (value->store != store_value &&
1181                 value->store != store_local)
1182                 continue;
1183
1184             /* read operands */
1185             if (read & (1<<o))
1186             {
1187                 /* used this before new_reads - puts the last read into the life range as well
1188                 if (!ir_block_living_find(self, value, NULL))
1189                     ir_block_living_add(self, value);
1190                 */
1191                 /* fprintf(stderr, "read: %s\n", value->_name); */
1192                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1193                     new_reads_t_v_add(&new_reads, value);
1194             }
1195
1196             /* write operands */
1197             /* When we write to a local, we consider it "dead" for the
1198              * remaining upper part of the function, since in SSA a value
1199              * can only be written once (== created)
1200              */
1201             if (write & (1<<o))
1202             {
1203                 size_t idx, readidx;
1204                 qbool in_living = ir_block_living_find(self, value, &idx);
1205                 qbool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1206                 if (!in_living && !in_reads)
1207                 {
1208                     /* If the value isn't alive it hasn't been read before... */
1209                     /* TODO: See if the warning can be emitted during parsing or AST processing
1210                      * otherwise have warning printed here.
1211                      * IF printing a warning here: include filecontext_t,
1212                      * and make sure it's only printed once
1213                      * since this function is run multiple times.
1214                      */
1215                     /* For now: debug info: */
1216                     fprintf(stderr, "Value only written %s\n", value->name);
1217                     tempbool = ir_value_life_merge(value, instr->eid);
1218                     *changed = *changed || tempbool;
1219                     /*
1220                     ir_instr_dump(instr, dbg_ind, printf);
1221                     abort();
1222                     */
1223                 } else {
1224                     /* since 'living' won't contain it
1225                      * anymore, merge the value, since
1226                      * (A) doesn't.
1227                      */
1228                     tempbool = ir_value_life_merge(value, instr->eid);
1229                     /*
1230                     if (tempbool)
1231                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
1232                     */
1233                     *changed = *changed || tempbool;
1234                     /* Then remove */
1235                     ir_block_living_remove(self, idx);
1236                     if (in_reads)
1237                         new_reads_t_v_remove(&new_reads, readidx);
1238                 }
1239             }
1240         }
1241         /* (A) */
1242         tempbool = ir_block_living_add_instr(self, instr->eid);
1243         //fprintf(stderr, "living added values\n");
1244         *changed = *changed || tempbool;
1245
1246         /* new reads: */
1247         for (rd = 0; rd < new_reads.v_count; ++rd)
1248         {
1249             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
1250                 ir_block_living_add(self, new_reads.v[rd]);
1251             }
1252             if (!i && !self->entries_count) {
1253                 /* fix the top */
1254                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
1255             }
1256         }
1257         new_reads_t_v_clear(&new_reads);
1258     }
1259
1260     if (self->run_id == self->owner->run_id)
1261         return;
1262     self->run_id = self->owner->run_id;
1263
1264     for (i = 0; i < self->entries_count; ++i)
1265     {
1266         ir_block *entry = self->entries[i];
1267         ir_block_life_propagate(entry, self, changed);
1268     }
1269 }