ir.c

   1 /*
   2  * Copyright (C) 2012
   3  *     Wolfgang Bumiller
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include "gmqcc.h"
  26 #include "ir.h"
  27
  28 /***********************************************************************
  29  *IR Builder
  30  */
  31
  32 ir_builder* ir_builder_new(const char *modulename)
  33 {
  34     ir_builder* self;
  35
  36     self = (ir_builder*)mem_a(sizeof(*self));
  37     MEM_VECTOR_INIT(self, functions);
  38     MEM_VECTOR_INIT(self, globals);
  39     self->name = NULL;
  40     if (!ir_builder_set_name(self, modulename)) {
  41         mem_d(self);
  42         return NULL;
  43     }
  44
  45     /* globals which always exist */
  46
  47     /* for now we give it a vector size */
  48     ir_builder_create_global(self, "OFS_RETURN", TYPE_VARIANT);
  49
  50     return self;
  51 }
  52
  53 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, globals)
  54 MEM_VEC_FUNCTIONS(ir_builder, ir_function*, functions)
  55
  56 void ir_builder_delete(ir_builder* self)
  57 {
  58     size_t i;
  59     mem_d((void*)self->name);
  60     for (i = 0; i != self->functions_count; ++i) {
  61         ir_function_delete(self->functions[i]);
  62     }
  63     MEM_VECTOR_CLEAR(self, functions);
  64     for (i = 0; i != self->globals_count; ++i) {
  65         ir_value_delete(self->globals[i]);
  66     }
  67     MEM_VECTOR_CLEAR(self, globals);
  68     mem_d(self);
  69 }
  70
  71 bool ir_builder_set_name(ir_builder *self, const char *name)
  72 {
  73     if (self->name)
  74         mem_d((void*)self->name);
  75     self->name = util_strdup(name);
  76     return !!self->name;
  77 }
  78
  79 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
  80 {
  81     size_t i;
  82     for (i = 0; i < self->functions_count; ++i) {
  83         if (!strcmp(name, self->functions[i]->name))
  84             return self->functions[i];
  85     }
  86     return NULL;
  87 }
  88
  89 ir_function* ir_builder_create_function(ir_builder *self, const char *name)
  90 {
  91     ir_function *fn = ir_builder_get_function(self, name);
  92     if (fn) {
  93         return NULL;
  94     }
  95
  96     fn = ir_function_new(self);
  97     if (!ir_function_set_name(fn, name) ||
  98         !ir_builder_functions_add(self, fn) )
  99     {
 100         ir_function_delete(fn);
 101         return NULL;
 102     }
 103     return fn;
 104 }
 105
 106 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
 107 {
 108     size_t i;
 109     for (i = 0; i < self->globals_count; ++i) {
 110         if (!strcmp(self->globals[i]->name, name))
 111             return self->globals[i];
 112     }
 113     return NULL;
 114 }
 115
 116 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
 117 {
 118     ir_value *ve = ir_builder_get_global(self, name);
 119     if (ve) {
 120         return NULL;
 121     }
 122
 123     ve = ir_value_var(name, store_global, vtype);
 124     if (!ir_builder_globals_add(self, ve)) {
 125         ir_value_delete(ve);
 126         return NULL;
 127     }
 128     return ve;
 129 }
 130
 131 /***********************************************************************
 132  *IR Function
 133  */
 134
 135 bool ir_function_naive_phi(ir_function*);
 136 void ir_function_enumerate(ir_function*);
 137 bool ir_function_calculate_liferanges(ir_function*);
 138
 139 ir_function* ir_function_new(ir_builder* owner)
 140 {
 141     ir_function *self;
 142     self = (ir_function*)mem_a(sizeof(*self));
 143     self->name = NULL;
 144     if (!ir_function_set_name(self, "<@unnamed>")) {
 145         mem_d(self);
 146         return NULL;
 147     }
 148     self->owner = owner;
 149     self->context.file = "<@no context>";
 150     self->context.line = 0;
 151     self->retype = TYPE_VOID;
 152     MEM_VECTOR_INIT(self, params);
 153     MEM_VECTOR_INIT(self, blocks);
 154     MEM_VECTOR_INIT(self, values);
 155     MEM_VECTOR_INIT(self, locals);
 156
 157     self->run_id = 0;
 158     return self;
 159 }
 160 MEM_VEC_FUNCTIONS(ir_function, ir_value*, values)
 161 MEM_VEC_FUNCTIONS(ir_function, ir_block*, blocks)
 162 MEM_VEC_FUNCTIONS(ir_function, ir_value*, locals)
 163
 164 bool ir_function_set_name(ir_function *self, const char *name)
 165 {
 166     if (self->name)
 167         mem_d((void*)self->name);
 168     self->name = util_strdup(name);
 169     return !!self->name;
 170 }
 171
 172 void ir_function_delete(ir_function *self)
 173 {
 174     size_t i;
 175     mem_d((void*)self->name);
 176
 177     for (i = 0; i != self->blocks_count; ++i)
 178         ir_block_delete(self->blocks[i]);
 179     MEM_VECTOR_CLEAR(self, blocks);
 180
 181     MEM_VECTOR_CLEAR(self, params);
 182
 183     for (i = 0; i != self->values_count; ++i)
 184         ir_value_delete(self->values[i]);
 185     MEM_VECTOR_CLEAR(self, values);
 186
 187     for (i = 0; i != self->locals_count; ++i)
 188         ir_value_delete(self->locals[i]);
 189     MEM_VECTOR_CLEAR(self, locals);
 190
 191     mem_d(self);
 192 }
 193
 194 bool GMQCC_WARN ir_function_collect_value(ir_function *self, ir_value *v)
 195 {
 196     return ir_function_values_add(self, v);
 197 }
 198
 199 ir_block* ir_function_create_block(ir_function *self, const char *label)
 200 {
 201     ir_block* bn = ir_block_new(self, label);
 202     memcpy(&bn->context, &self->context, sizeof(self->context));
 203     if (!ir_function_blocks_add(self, bn)) {
 204         ir_block_delete(bn);
 205         return NULL;
 206     }
 207     return bn;
 208 }
 209
 210 bool ir_function_finalize(ir_function *self)
 211 {
 212     if (!ir_function_naive_phi(self))
 213         return false;
 214
 215     ir_function_enumerate(self);
 216
 217     if (!ir_function_calculate_liferanges(self))
 218         return false;
 219     return true;
 220 }
 221
 222 ir_value* ir_function_get_local(ir_function *self, const char *name)
 223 {
 224     size_t i;
 225     for (i = 0; i < self->locals_count; ++i) {
 226         if (!strcmp(self->locals[i]->name, name))
 227             return self->locals[i];
 228     }
 229     return NULL;
 230 }
 231
 232 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype)
 233 {
 234     ir_value *ve = ir_function_get_local(self, name);
 235     if (ve) {
 236         return NULL;
 237     }
 238
 239     ve = ir_value_var(name, store_local, vtype);
 240     if (!ir_function_locals_add(self, ve)) {
 241         ir_value_delete(ve);
 242         return NULL;
 243     }
 244     return ve;
 245 }
 246
 247 /***********************************************************************
 248  *IR Block
 249  */
 250
 251 ir_block* ir_block_new(ir_function* owner, const char *name)
 252 {
 253     ir_block *self;
 254     self = (ir_block*)mem_a(sizeof(*self));
 255     self->label = NULL;
 256     if (!ir_block_set_label(self, name)) {
 257         mem_d(self);
 258         return NULL;
 259     }
 260     self->owner = owner;
 261     self->context.file = "<@no context>";
 262     self->context.line = 0;
 263     self->final = false;
 264     MEM_VECTOR_INIT(self, instr);
 265     MEM_VECTOR_INIT(self, entries);
 266     MEM_VECTOR_INIT(self, exits);
 267
 268     self->eid = 0;
 269     self->is_return = false;
 270     self->run_id = 0;
 271     MEM_VECTOR_INIT(self, living);
 272     return self;
 273 }
 274 MEM_VEC_FUNCTIONS(ir_block, ir_instr*, instr)
 275 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, entries)
 276 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, exits)
 277 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_value*, living)
 278
 279 void ir_block_delete(ir_block* self)
 280 {
 281     size_t i;
 282     mem_d(self->label);
 283     for (i = 0; i != self->instr_count; ++i)
 284         ir_instr_delete(self->instr[i]);
 285     MEM_VECTOR_CLEAR(self, instr);
 286     MEM_VECTOR_CLEAR(self, entries);
 287     MEM_VECTOR_CLEAR(self, exits);
 288     MEM_VECTOR_CLEAR(self, living);
 289     mem_d(self);
 290 }
 291
 292 bool ir_block_set_label(ir_block *self, const char *name)
 293 {
 294     if (self->label)
 295         mem_d((void*)self->label);
 296     self->label = util_strdup(name);
 297     return !!self->label;
 298 }
 299
 300 /***********************************************************************
 301  *IR Instructions
 302  */
 303
 304 ir_instr* ir_instr_new(ir_block* owner, int op)
 305 {
 306     ir_instr *self;
 307     self = (ir_instr*)mem_a(sizeof(*self));
 308     self->owner = owner;
 309     self->context.file = "<@no context>";
 310     self->context.line = 0;
 311     self->opcode = op;
 312     self->_ops[0] = NULL;
 313     self->_ops[1] = NULL;
 314     self->_ops[2] = NULL;
 315     self->bops[0] = NULL;
 316     self->bops[1] = NULL;
 317     MEM_VECTOR_INIT(self, phi);
 318
 319     self->eid = 0;
 320     return self;
 321 }
 322 MEM_VEC_FUNCTIONS(ir_instr, ir_phi_entry_t, phi)
 323
 324 void ir_instr_delete(ir_instr *self)
 325 {
 326     size_t i;
 327     /* The following calls can only delete from
 328      * vectors, we still want to delete this instruction
 329      * so ignore the return value. Since with the warn_unused_result attribute
 330      * gcc doesn't care about an explicit: (void)foo(); to ignore the result,
 331      * I have to improvise here and use if(foo());
 332      */
 333     for (i = 0; i < self->phi_count; ++i) {
 334         size_t idx;
 335         if (ir_value_writes_find(self->phi[i].value, self, &idx))
 336             if (ir_value_writes_remove(self->phi[i].value, idx)) GMQCC_SUPRESS_EMPTY_BODY;
 337         if (ir_value_reads_find(self->phi[i].value, self, &idx))
 338             if (ir_value_reads_remove (self->phi[i].value, idx)) GMQCC_SUPRESS_EMPTY_BODY;
 339     }
 340     MEM_VECTOR_CLEAR(self, phi);
 341     if (ir_instr_op(self, 0, NULL, false)) GMQCC_SUPRESS_EMPTY_BODY;
 342     if (ir_instr_op(self, 1, NULL, false)) GMQCC_SUPRESS_EMPTY_BODY;
 343     if (ir_instr_op(self, 2, NULL, false)) GMQCC_SUPRESS_EMPTY_BODY;
 344     mem_d(self);
 345 }
 346
 347 bool ir_instr_op(ir_instr *self, int op, ir_value *v, bool writing)
 348 {
 349     if (self->_ops[op]) {
 350         size_t idx;
 351         if (writing && ir_value_writes_find(self->_ops[op], self, &idx))
 352         {
 353             if (!ir_value_writes_remove(self->_ops[op], idx))
 354                 return false;
 355         }
 356         else if (ir_value_reads_find(self->_ops[op], self, &idx))
 357         {
 358             if (!ir_value_reads_remove(self->_ops[op], idx))
 359                 return false;
 360         }
 361     }
 362     if (v) {
 363         if (writing) {
 364             if (!ir_value_writes_add(v, self))
 365                 return false;
 366         } else {
 367             if (!ir_value_reads_add(v, self))
 368                 return false;
 369         }
 370     }
 371     self->_ops[op] = v;
 372     return true;
 373 }
 374
 375 /***********************************************************************
 376  *IR Value
 377  */
 378
 379 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 380 {
 381     ir_value *self;
 382     self = (ir_value*)mem_a(sizeof(*self));
 383     self->vtype = vtype;
 384     self->store = storetype;
 385     MEM_VECTOR_INIT(self, reads);
 386     MEM_VECTOR_INIT(self, writes);
 387     self->isconst = false;
 388     self->context.file = "<@no context>";
 389     self->context.line = 0;
 390     self->name = NULL;
 391     ir_value_set_name(self, name);
 392
 393     MEM_VECTOR_INIT(self, life);
 394     return self;
 395 }
 396 MEM_VEC_FUNCTIONS(ir_value, ir_life_entry_t, life)
 397 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, reads)
 398 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, writes)
 399
 400 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 401 {
 402     ir_value *v = ir_value_var(name, storetype, vtype);
 403     if (!v)
 404         return NULL;
 405     if (!ir_function_collect_value(owner, v))
 406     {
 407         ir_value_delete(v);
 408         return NULL;
 409     }
 410     return v;
 411 }
 412
 413 void ir_value_delete(ir_value* self)
 414 {
 415     mem_d((void*)self->name);
 416     if (self->isconst)
 417     {
 418         if (self->vtype == TYPE_STRING)
 419             mem_d((void*)self->constval.vstring);
 420     }
 421     MEM_VECTOR_CLEAR(self, reads);
 422     MEM_VECTOR_CLEAR(self, writes);
 423     MEM_VECTOR_CLEAR(self, life);
 424     mem_d(self);
 425 }
 426
 427 void ir_value_set_name(ir_value *self, const char *name)
 428 {
 429     if (self->name)
 430         mem_d((void*)self->name);
 431     self->name = util_strdup(name);
 432 }
 433
 434 bool ir_value_set_float(ir_value *self, float f)
 435 {
 436     if (self->vtype != TYPE_FLOAT)
 437         return false;
 438     self->constval.vfloat = f;
 439     self->isconst = true;
 440     return true;
 441 }
 442
 443 bool ir_value_set_vector(ir_value *self, vector v)
 444 {
 445     if (self->vtype != TYPE_VECTOR)
 446         return false;
 447     self->constval.vvec = v;
 448     self->isconst = true;
 449     return true;
 450 }
 451
 452 bool ir_value_set_string(ir_value *self, const char *str)
 453 {
 454     if (self->vtype != TYPE_STRING)
 455         return false;
 456     self->constval.vstring = util_strdup(str);
 457     self->isconst = true;
 458     return true;
 459 }
 460
 461 #if 0
 462 bool ir_value_set_int(ir_value *self, int i)
 463 {
 464     if (self->vtype != TYPE_INTEGER)
 465         return false;
 466     self->constval.vint = i;
 467     self->isconst = true;
 468     return true;
 469 }
 470 #endif
 471
 472 bool ir_value_lives(ir_value *self, size_t at)
 473 {
 474     size_t i;
 475     for (i = 0; i < self->life_count; ++i)
 476     {
 477         ir_life_entry_t *life = &self->life[i];
 478         if (life->start <= at && at <= life->end)
 479             return true;
 480         if (life->start > at) /* since it's ordered */
 481             return false;
 482     }
 483     return false;
 484 }
 485
 486 bool ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 487 {
 488     size_t k;
 489     if (!ir_value_life_add(self, e)) /* naive... */
 490         return false;
 491     for (k = self->life_count-1; k > idx; --k)
 492         self->life[k] = self->life[k-1];
 493     self->life[idx] = e;
 494     return true;
 495 }
 496
 497 bool ir_value_life_merge(ir_value *self, size_t s)
 498 {
 499     size_t i;
 500     ir_life_entry_t *life = NULL;
 501     ir_life_entry_t *before = NULL;
 502     ir_life_entry_t new_entry;
 503
 504     /* Find the first range >= s */
 505     for (i = 0; i < self->life_count; ++i)
 506     {
 507         before = life;
 508         life = &self->life[i];
 509         if (life->start > s)
 510             break;
 511     }
 512     /* nothing found? append */
 513     if (i == self->life_count) {
 514         ir_life_entry_t e;
 515         if (life && life->end+1 == s)
 516         {
 517             /* previous life range can be merged in */
 518             life->end++;
 519             return true;
 520         }
 521         if (life && life->end >= s)
 522             return false;
 523         e.start = e.end = s;
 524         if (!ir_value_life_add(self, e))
 525             return false; /* failing */
 526         return true;
 527     }
 528     /* found */
 529     if (before)
 530     {
 531         if (before->end + 1 == s &&
 532             life->start - 1 == s)
 533         {
 534             /* merge */
 535             before->end = life->end;
 536             if (!ir_value_life_remove(self, i))
 537                 return false; /* failing */
 538             return true;
 539         }
 540         if (before->end + 1 == s)
 541         {
 542             /* extend before */
 543             before->end++;
 544             return true;
 545         }
 546         /* already contained */
 547         if (before->end >= s)
 548             return false;
 549     }
 550     /* extend */
 551     if (life->start - 1 == s)
 552     {
 553         life->start--;
 554         return true;
 555     }
 556     /* insert a new entry */
 557     new_entry.start = new_entry.end = s;
 558     return ir_value_life_insert(self, i, new_entry);
 559 }
 560
 561 bool ir_values_overlap(ir_value *a, ir_value *b)
 562 {
 563     /* For any life entry in A see if it overlaps with
 564      * any life entry in B.
 565      * Note that the life entries are orderes, so we can make a
 566      * more efficient algorithm there than naively translating the
 567      * statement above.
 568      */
 569
 570     ir_life_entry_t *la, *lb, *enda, *endb;
 571
 572     /* first of all, if either has no life range, they cannot clash */
 573     if (!a->life_count || !b->life_count)
 574         return false;
 575
 576     la = a->life;
 577     lb = b->life;
 578     enda = la + a->life_count;
 579     endb = lb + b->life_count;
 580     while (true)
 581     {
 582         /* check if the entries overlap, for that,
 583          * both must start before the other one ends.
 584          */
 585         if (la->start <= lb->end &&
 586             lb->start <= la->end)
 587         {
 588             return true;
 589         }
 590
 591         /* entries are ordered
 592          * one entry is earlier than the other
 593          * that earlier entry will be moved forward
 594          */
 595         if (la->end < lb->end)
 596         {
 597             /* order: A B, move A forward
 598              * check if we hit the end with A
 599              */
 600             if (++la == enda)
 601                 break;
 602         }
 603         else if (lb->end < la->end)
 604         {
 605             /* order: B A, move B forward
 606              * check if we hit the end with B
 607              */
 608             if (++lb == endb)
 609                 break;
 610         }
 611     }
 612     return false;
 613 }
 614
 615 /***********************************************************************
 616  *IR main operations
 617  */
 618
 619 bool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 620 {
 621     if (target->store == store_value) {
 622         fprintf(stderr, "cannot store to an SSA value\n");
 623         return false;
 624     } else {
 625         ir_instr *in = ir_instr_new(self, op);
 626         if (!in)
 627             return false;
 628         if (!ir_instr_op(in, 0, target, true) ||
 629             !ir_instr_op(in, 1, what, false)  ||
 630             !ir_block_instr_add(self, in) )
 631         {
 632             return false;
 633         }
 634         return true;
 635     }
 636 }
 637
 638 bool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 639 {
 640     int op = 0;
 641     int vtype;
 642     if (target->vtype == TYPE_VARIANT)
 643         vtype = what->vtype;
 644     else
 645         vtype = target->vtype;
 646
 647     switch (vtype) {
 648         case TYPE_FLOAT:
 649 #if 0
 650             if (what->vtype == TYPE_INTEGER)
 651                 op = INSTR_CONV_ITOF;
 652             else
 653 #endif
 654                 op = INSTR_STORE_F;
 655             break;
 656         case TYPE_VECTOR:
 657             op = INSTR_STORE_V;
 658             break;
 659         case TYPE_ENTITY:
 660             op = INSTR_STORE_ENT;
 661             break;
 662         case TYPE_STRING:
 663             op = INSTR_STORE_S;
 664             break;
 665         case TYPE_FIELD:
 666             op = INSTR_STORE_FLD;
 667             break;
 668 #if 0
 669         case TYPE_INTEGER:
 670             if (what->vtype == TYPE_INTEGER)
 671                 op = INSTR_CONV_FTOI;
 672             else
 673                 op = INSTR_STORE_I;
 674             break;
 675 #endif
 676         case TYPE_POINTER:
 677 #if 0
 678             op = INSTR_STORE_I;
 679 #else
 680             op = INSTR_STORE_ENT;
 681 #endif
 682             break;
 683         default:
 684             /* Unknown type */
 685             return false;
 686     }
 687     return ir_block_create_store_op(self, op, target, what);
 688 }
 689
 690 bool ir_block_create_storep(ir_block *self, ir_value *target, ir_value *what)
 691 {
 692     int op = 0;
 693     int vtype;
 694
 695     if (target->vtype != TYPE_POINTER)
 696         return false;
 697
 698     /* storing using pointer - target is a pointer, type must be
 699      * inferred from source
 700      */
 701     vtype = what->vtype;
 702
 703     switch (vtype) {
 704         case TYPE_FLOAT:
 705             op = INSTR_STOREP_F;
 706             break;
 707         case TYPE_VECTOR:
 708             op = INSTR_STOREP_V;
 709             break;
 710         case TYPE_ENTITY:
 711             op = INSTR_STOREP_ENT;
 712             break;
 713         case TYPE_STRING:
 714             op = INSTR_STOREP_S;
 715             break;
 716         case TYPE_FIELD:
 717             op = INSTR_STOREP_FLD;
 718             break;
 719 #if 0
 720         case TYPE_INTEGER:
 721             op = INSTR_STOREP_I;
 722             break;
 723 #endif
 724         case TYPE_POINTER:
 725 #if 0
 726             op = INSTR_STOREP_I;
 727 #else
 728             op = INSTR_STOREP_ENT;
 729 #endif
 730             break;
 731         default:
 732             /* Unknown type */
 733             return false;
 734     }
 735     return ir_block_create_store_op(self, op, target, what);
 736 }
 737
 738 bool ir_block_create_return(ir_block *self, ir_value *v)
 739 {
 740     ir_instr *in;
 741     if (self->final) {
 742         fprintf(stderr, "block already ended (%s)\n", self->label);
 743         return false;
 744     }
 745     self->final = true;
 746     self->is_return = true;
 747     in = ir_instr_new(self, INSTR_RETURN);
 748     if (!in)
 749         return false;
 750
 751     if (!ir_instr_op(in, 0, v, false) ||
 752         !ir_block_instr_add(self, in) )
 753     {
 754         return false;
 755     }
 756     return true;
 757 }
 758
 759 bool ir_block_create_if(ir_block *self, ir_value *v,
 760                         ir_block *ontrue, ir_block *onfalse)
 761 {
 762     ir_instr *in;
 763     if (self->final) {
 764         fprintf(stderr, "block already ended (%s)\n", self->label);
 765         return false;
 766     }
 767     self->final = true;
 768     /*in = ir_instr_new(self, (v->vtype == TYPE_STRING ? INSTR_IF_S : INSTR_IF_F));*/
 769     in = ir_instr_new(self, VINSTR_COND);
 770     if (!in)
 771         return false;
 772
 773     if (!ir_instr_op(in, 0, v, false)) {
 774         ir_instr_delete(in);
 775         return false;
 776     }
 777
 778     in->bops[0] = ontrue;
 779     in->bops[1] = onfalse;
 780
 781     if (!ir_block_instr_add(self, in))
 782         return false;
 783
 784     if (!ir_block_exits_add(self, ontrue)    ||
 785         !ir_block_exits_add(self, onfalse)   ||
 786         !ir_block_entries_add(ontrue, self)  ||
 787         !ir_block_entries_add(onfalse, self) )
 788     {
 789         return false;
 790     }
 791     return true;
 792 }
 793
 794 bool ir_block_create_jump(ir_block *self, ir_block *to)
 795 {
 796     ir_instr *in;
 797     if (self->final) {
 798         fprintf(stderr, "block already ended (%s)\n", self->label);
 799         return false;
 800     }
 801     self->final = true;
 802     in = ir_instr_new(self, VINSTR_JUMP);
 803     if (!in)
 804         return false;
 805
 806     in->bops[0] = to;
 807     if (!ir_block_instr_add(self, in))
 808         return false;
 809
 810     if (!ir_block_exits_add(self, to) ||
 811         !ir_block_entries_add(to, self) )
 812     {
 813         return false;
 814     }
 815     return true;
 816 }
 817
 818 bool ir_block_create_goto(ir_block *self, ir_block *to)
 819 {
 820     ir_instr *in;
 821     if (self->final) {
 822         fprintf(stderr, "block already ended (%s)\n", self->label);
 823         return false;
 824     }
 825     self->final = true;
 826     in = ir_instr_new(self, INSTR_GOTO);
 827     if (!in)
 828         return false;
 829
 830     in->bops[0] = to;
 831     if (!ir_block_instr_add(self, in))
 832         return false;
 833
 834     if (!ir_block_exits_add(self, to) ||
 835         !ir_block_entries_add(to, self) )
 836     {
 837         return false;
 838     }
 839     return true;
 840 }
 841
 842 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
 843 {
 844     ir_value *out;
 845     ir_instr *in;
 846     in = ir_instr_new(self, VINSTR_PHI);
 847     if (!in)
 848         return NULL;
 849     out = ir_value_out(self->owner, label, store_local, ot);
 850     if (!out) {
 851         ir_instr_delete(in);
 852         return NULL;
 853     }
 854     if (!ir_instr_op(in, 0, out, true)) {
 855         ir_instr_delete(in);
 856         ir_value_delete(out);
 857         return NULL;
 858     }
 859     if (!ir_block_instr_add(self, in)) {
 860         ir_instr_delete(in);
 861         ir_value_delete(out);
 862         return NULL;
 863     }
 864     return in;
 865 }
 866
 867 ir_value* ir_phi_value(ir_instr *self)
 868 {
 869     return self->_ops[0];
 870 }
 871
 872 bool ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
 873 {
 874     ir_phi_entry_t pe;
 875
 876     if (!ir_block_entries_find(self->owner, b, NULL)) {
 877         /* Must not be possible to cause this, otherwise the AST
 878          * is doing something wrong.
 879          */
 880         fprintf(stderr, "Invalid entry block for PHI\n");
 881         abort();
 882     }
 883
 884     pe.value = v;
 885     pe.from = b;
 886     if (!ir_value_reads_add(v, self))
 887         return false;
 888     return ir_instr_phi_add(self, pe);
 889 }
 890
 891 /* binary op related code */
 892
 893 ir_value* ir_block_create_binop(ir_block *self,
 894                                 const char *label, int opcode,
 895                                 ir_value *left, ir_value *right)
 896 {
 897     ir_value *out = NULL;
 898     ir_instr *in  = NULL;
 899
 900     int ot = TYPE_VOID;
 901     switch (opcode) {
 902         case INSTR_ADD_F:
 903         case INSTR_SUB_F:
 904         case INSTR_DIV_F:
 905         case INSTR_MUL_F:
 906         case INSTR_MUL_V:
 907         case INSTR_AND:
 908         case INSTR_OR:
 909 #if 0
 910         case INSTR_AND_I:
 911         case INSTR_AND_IF:
 912         case INSTR_AND_FI:
 913         case INSTR_OR_I:
 914         case INSTR_OR_IF:
 915         case INSTR_OR_FI:
 916 #endif
 917         case INSTR_BITAND:
 918         case INSTR_BITOR:
 919 #if 0
 920         case INSTR_SUB_S: /* -- offset of string as float */
 921         case INSTR_MUL_IF:
 922         case INSTR_MUL_FI:
 923         case INSTR_DIV_IF:
 924         case INSTR_DIV_FI:
 925         case INSTR_BITOR_IF:
 926         case INSTR_BITOR_FI:
 927         case INSTR_BITAND_FI:
 928         case INSTR_BITAND_IF:
 929         case INSTR_EQ_I:
 930         case INSTR_NE_I:
 931 #endif
 932             ot = TYPE_FLOAT;
 933             break;
 934 #if 0
 935         case INSTR_ADD_I:
 936         case INSTR_ADD_IF:
 937         case INSTR_ADD_FI:
 938         case INSTR_SUB_I:
 939         case INSTR_SUB_FI:
 940         case INSTR_SUB_IF:
 941         case INSTR_MUL_I:
 942         case INSTR_DIV_I:
 943         case INSTR_BITAND_I:
 944         case INSTR_BITOR_I:
 945         case INSTR_XOR_I:
 946         case INSTR_RSHIFT_I:
 947         case INSTR_LSHIFT_I:
 948             ot = TYPE_INTEGER;
 949             break;
 950 #endif
 951         case INSTR_ADD_V:
 952         case INSTR_SUB_V:
 953         case INSTR_MUL_VF:
 954         case INSTR_MUL_FV:
 955 #if 0
 956         case INSTR_DIV_VF:
 957         case INSTR_MUL_IV:
 958         case INSTR_MUL_VI:
 959 #endif
 960             ot = TYPE_VECTOR;
 961             break;
 962 #if 0
 963         case INSTR_ADD_SF:
 964             ot = TYPE_POINTER;
 965             break;
 966 #endif
 967         default:
 968             /* ranges: */
 969             /* boolean operations result in floats */
 970             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
 971                 ot = TYPE_FLOAT;
 972             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
 973                 ot = TYPE_FLOAT;
 974 #if 0
 975             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
 976                 ot = TYPE_FLOAT;
 977 #endif
 978             break;
 979     };
 980     if (ot == TYPE_VOID) {
 981         /* The AST or parser were supposed to check this! */
 982         return NULL;
 983     }
 984
 985     out = ir_value_out(self->owner, label, store_local, ot);
 986     if (!out)
 987         return NULL;
 988
 989     in = ir_instr_new(self, opcode);
 990     if (!in) {
 991         ir_value_delete(out);
 992         return NULL;
 993     }
 994
 995     if (!ir_instr_op(in, 0, out, true) ||
 996         !ir_instr_op(in, 1, left, false) ||
 997         !ir_instr_op(in, 2, right, false) )
 998     {
 999         goto on_error;
1000     }
1001
1002     if (!ir_block_instr_add(self, in))
1003         goto on_error;
1004
1005     return out;
1006 on_error:
1007     ir_instr_delete(in);
1008     ir_value_delete(out);
1009     return NULL;
1010 }
1011
1012 ir_value* ir_block_create_fieldaddress(ir_block *self, const char *label, ir_value *ent, ir_value *field)
1013 {
1014     ir_instr *instr;
1015     ir_value *out;
1016
1017     /* Support for various pointer types todo if so desired */
1018     if (ent->vtype != TYPE_ENTITY)
1019         return NULL;
1020
1021     if (field->vtype != TYPE_FIELD)
1022         return NULL;
1023
1024     out = ir_value_out(self->owner, label, store_value, TYPE_POINTER);
1025     if (!out)
1026         return NULL;
1027
1028     instr = ir_instr_new(self, INSTR_ADDRESS);
1029     if (!instr) {
1030         ir_value_delete(out);
1031         return NULL;
1032     }
1033
1034     if (!ir_instr_op(instr, 0, out, true) ||
1035         !ir_instr_op(instr, 1, ent, false) ||
1036         !ir_instr_op(instr, 2, field, false) )
1037     {
1038         goto on_error;
1039     }
1040
1041     if (!ir_block_instr_add(self, instr))
1042         goto on_error;
1043
1044     return out;
1045 on_error:
1046     ir_instr_delete(instr);
1047     ir_value_delete(out);
1048     return NULL;
1049 }
1050
1051 ir_value* ir_block_create_load_from_ent(ir_block *self, const char *label, ir_value *ent, ir_value *field, int outype)
1052 {
1053     ir_instr *instr;
1054     ir_value *out;
1055     int       op;
1056
1057     if (ent->vtype != TYPE_ENTITY)
1058         return NULL;
1059
1060     /* at some point we could redirect for TYPE_POINTER... but that could lead to carelessness */
1061     if (field->vtype != TYPE_FIELD)
1062         return NULL;
1063
1064     switch (outype)
1065     {
1066         case TYPE_FLOAT:   op = INSTR_LOAD_F;   break;
1067         case TYPE_VECTOR:  op = INSTR_LOAD_V;   break;
1068         case TYPE_STRING:  op = INSTR_LOAD_S;   break;
1069         case TYPE_FIELD:   op = INSTR_LOAD_FLD; break;
1070         case TYPE_ENTITY:  op = INSTR_LOAD_ENT; break;
1071 #if 0
1072         case TYPE_POINTER: op = INSTR_LOAD_I;   break;
1073         case TYPE_INTEGER: op = INSTR_LOAD_I;   break;
1074 #endif
1075         default:
1076             return NULL;
1077     }
1078
1079     out = ir_value_out(self->owner, label, store_value, outype);
1080     if (!out)
1081         return NULL;
1082
1083     instr = ir_instr_new(self, op);
1084     if (!instr) {
1085         ir_value_delete(out);
1086         return NULL;
1087     }
1088
1089     if (!ir_instr_op(instr, 0, out, true) ||
1090         !ir_instr_op(instr, 1, ent, false) ||
1091         !ir_instr_op(instr, 2, field, false) )
1092     {
1093         goto on_error;
1094     }
1095
1096     if (!ir_block_instr_add(self, instr))
1097         goto on_error;
1098
1099     return out;
1100 on_error:
1101     ir_instr_delete(instr);
1102     ir_value_delete(out);
1103     return NULL;
1104 }
1105
1106 ir_value* ir_block_create_add(ir_block *self,
1107                               const char *label,
1108                               ir_value *left, ir_value *right)
1109 {
1110     int op = 0;
1111     int l = left->vtype;
1112     int r = right->vtype;
1113     if (l == r) {
1114         switch (l) {
1115             default:
1116                 return NULL;
1117             case TYPE_FLOAT:
1118                 op = INSTR_ADD_F;
1119                 break;
1120 #if 0
1121             case TYPE_INTEGER:
1122                 op = INSTR_ADD_I;
1123                 break;
1124 #endif
1125             case TYPE_VECTOR:
1126                 op = INSTR_ADD_V;
1127                 break;
1128         }
1129     } else {
1130 #if 0
1131         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1132             op = INSTR_ADD_FI;
1133         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1134             op = INSTR_ADD_IF;
1135         else
1136 #endif
1137             return NULL;
1138     }
1139     return ir_block_create_binop(self, label, op, left, right);
1140 }
1141
1142 ir_value* ir_block_create_sub(ir_block *self,
1143                               const char *label,
1144                               ir_value *left, ir_value *right)
1145 {
1146     int op = 0;
1147     int l = left->vtype;
1148     int r = right->vtype;
1149     if (l == r) {
1150
1151         switch (l) {
1152             default:
1153                 return NULL;
1154             case TYPE_FLOAT:
1155                 op = INSTR_SUB_F;
1156                 break;
1157 #if 0
1158             case TYPE_INTEGER:
1159                 op = INSTR_SUB_I;
1160                 break;
1161 #endif
1162             case TYPE_VECTOR:
1163                 op = INSTR_SUB_V;
1164                 break;
1165         }
1166     } else {
1167 #if 0
1168         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1169             op = INSTR_SUB_FI;
1170         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1171             op = INSTR_SUB_IF;
1172         else
1173 #endif
1174             return NULL;
1175     }
1176     return ir_block_create_binop(self, label, op, left, right);
1177 }
1178
1179 ir_value* ir_block_create_mul(ir_block *self,
1180                               const char *label,
1181                               ir_value *left, ir_value *right)
1182 {
1183     int op = 0;
1184     int l = left->vtype;
1185     int r = right->vtype;
1186     if (l == r) {
1187
1188         switch (l) {
1189             default:
1190                 return NULL;
1191             case TYPE_FLOAT:
1192                 op = INSTR_MUL_F;
1193                 break;
1194 #if 0
1195             case TYPE_INTEGER:
1196                 op = INSTR_MUL_I;
1197                 break;
1198 #endif
1199             case TYPE_VECTOR:
1200                 op = INSTR_MUL_V;
1201                 break;
1202         }
1203     } else {
1204         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1205             op = INSTR_MUL_VF;
1206         else if ( (l == TYPE_FLOAT && r == TYPE_VECTOR) )
1207             op = INSTR_MUL_FV;
1208 #if 0
1209         else if ( (l == TYPE_VECTOR && r == TYPE_INTEGER) )
1210             op = INSTR_MUL_VI;
1211         else if ( (l == TYPE_INTEGER && r == TYPE_VECTOR) )
1212             op = INSTR_MUL_IV;
1213         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1214             op = INSTR_MUL_FI;
1215         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1216             op = INSTR_MUL_IF;
1217 #endif
1218         else
1219             return NULL;
1220     }
1221     return ir_block_create_binop(self, label, op, left, right);
1222 }
1223
1224 ir_value* ir_block_create_div(ir_block *self,
1225                               const char *label,
1226                               ir_value *left, ir_value *right)
1227 {
1228     int op = 0;
1229     int l = left->vtype;
1230     int r = right->vtype;
1231     if (l == r) {
1232
1233         switch (l) {
1234             default:
1235                 return NULL;
1236             case TYPE_FLOAT:
1237                 op = INSTR_DIV_F;
1238                 break;
1239 #if 0
1240             case TYPE_INTEGER:
1241                 op = INSTR_DIV_I;
1242                 break;
1243 #endif
1244         }
1245     } else {
1246 #if 0
1247         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1248             op = INSTR_DIV_VF;
1249         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1250             op = INSTR_DIV_FI;
1251         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1252             op = INSTR_DIV_IF;
1253         else
1254 #endif
1255             return NULL;
1256     }
1257     return ir_block_create_binop(self, label, op, left, right);
1258 }
1259
1260 /* PHI resolving breaks the SSA, and must thus be the last
1261  * step before life-range calculation.
1262  */
1263
1264 static bool ir_block_naive_phi(ir_block *self);
1265 bool ir_function_naive_phi(ir_function *self)
1266 {
1267     size_t i;
1268
1269     for (i = 0; i < self->blocks_count; ++i)
1270     {
1271         if (!ir_block_naive_phi(self->blocks[i]))
1272             return false;
1273     }
1274     return true;
1275 }
1276
1277 static bool ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
1278 {
1279     ir_instr *instr;
1280     size_t i;
1281
1282     /* create a store */
1283     if (!ir_block_create_store(block, old, what))
1284         return false;
1285
1286     /* we now move it up */
1287     instr = block->instr[block->instr_count-1];
1288     for (i = block->instr_count; i > iid; --i)
1289         block->instr[i] = block->instr[i-1];
1290     block->instr[i] = instr;
1291
1292     return true;
1293 }
1294
1295 static bool ir_block_naive_phi(ir_block *self)
1296 {
1297     size_t i, p, w;
1298     /* FIXME: optionally, create_phi can add the phis
1299      * to a list so we don't need to loop through blocks
1300      * - anyway: "don't optimize YET"
1301      */
1302     for (i = 0; i < self->instr_count; ++i)
1303     {
1304         ir_instr *instr = self->instr[i];
1305         if (instr->opcode != VINSTR_PHI)
1306             continue;
1307
1308         if (!ir_block_instr_remove(self, i))
1309             return false;
1310         --i; /* NOTE: i+1 below */
1311
1312         for (p = 0; p < instr->phi_count; ++p)
1313         {
1314             ir_value *v = instr->phi[p].value;
1315             for (w = 0; w < v->writes_count; ++w) {
1316                 ir_value *old;
1317
1318                 if (!v->writes[w]->_ops[0])
1319                     continue;
1320
1321                 /* When the write was to a global, we have to emit a mov */
1322                 old = v->writes[w]->_ops[0];
1323
1324                 /* The original instruction now writes to the PHI target local */
1325                 if (v->writes[w]->_ops[0] == v)
1326                     v->writes[w]->_ops[0] = instr->_ops[0];
1327
1328                 if (old->store != store_local)
1329                 {
1330                     /* If it originally wrote to a global we need to store the value
1331                      * there as welli
1332                      */
1333                     if (!ir_naive_phi_emit_store(self, i+1, old, v))
1334                         return false;
1335                     if (i+1 < self->instr_count)
1336                         instr = self->instr[i+1];
1337                     else
1338                         instr = NULL;
1339                     /* In case I forget and access instr later, it'll be NULL
1340                      * when it's a problem, to make sure we crash, rather than accessing
1341                      * invalid data.
1342                      */
1343                 }
1344                 else
1345                 {
1346                     /* If it didn't, we can replace all reads by the phi target now. */
1347                     size_t r;
1348                     for (r = 0; r < old->reads_count; ++r)
1349                     {
1350                         size_t op;
1351                         ir_instr *ri = old->reads[r];
1352                         for (op = 0; op < ri->phi_count; ++op) {
1353                             if (ri->phi[op].value == old)
1354                                 ri->phi[op].value = v;
1355                         }
1356                         for (op = 0; op < 3; ++op) {
1357                             if (ri->_ops[op] == old)
1358                                 ri->_ops[op] = v;
1359                         }
1360                     }
1361                 }
1362             }
1363         }
1364         ir_instr_delete(instr);
1365     }
1366     return true;
1367 }
1368
1369 /***********************************************************************
1370  *IR Temp allocation code
1371  * Propagating value life ranges by walking through the function backwards
1372  * until no more changes are made.
1373  * In theory this should happen once more than once for every nested loop
1374  * level.
1375  * Though this implementation might run an additional time for if nests.
1376  */
1377
1378 typedef struct
1379 {
1380     ir_value* *v;
1381     size_t    v_count;
1382     size_t    v_alloc;
1383 } new_reads_t;
1384 MEM_VEC_FUNCTIONS_ALL(new_reads_t, ir_value*, v)
1385
1386 /* Enumerate instructions used by value's life-ranges
1387  */
1388 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1389 {
1390     size_t i;
1391     size_t eid = *_eid;
1392     for (i = 0; i < self->instr_count; ++i)
1393     {
1394         self->instr[i]->eid = eid++;
1395     }
1396     *_eid = eid;
1397 }
1398
1399 /* Enumerate blocks and instructions.
1400  * The block-enumeration is unordered!
1401  * We do not really use the block enumreation, however
1402  * the instruction enumeration is important for life-ranges.
1403  */
1404 void ir_function_enumerate(ir_function *self)
1405 {
1406     size_t i;
1407     size_t instruction_id = 0;
1408     for (i = 0; i < self->blocks_count; ++i)
1409     {
1410         self->blocks[i]->eid = i;
1411         self->blocks[i]->run_id = 0;
1412         ir_block_enumerate(self->blocks[i], &instruction_id);
1413     }
1414 }
1415
1416 static bool ir_block_life_propagate(ir_block *b, ir_block *prev, bool *changed);
1417 bool ir_function_calculate_liferanges(ir_function *self)
1418 {
1419     size_t i;
1420     bool changed;
1421
1422     do {
1423         self->run_id++;
1424         changed = false;
1425         for (i = 0; i != self->blocks_count; ++i)
1426         {
1427             if (self->blocks[i]->is_return)
1428             {
1429                 if (!ir_block_life_propagate(self->blocks[i], NULL, &changed))
1430                     return false;
1431             }
1432         }
1433     } while (changed);
1434     return true;
1435 }
1436
1437 /* Get information about which operand
1438  * is read from, or written to.
1439  */
1440 static void ir_op_read_write(int op, size_t *read, size_t *write)
1441 {
1442     switch (op)
1443     {
1444     case VINSTR_JUMP:
1445     case INSTR_GOTO:
1446         *write = 0;
1447         *read = 0;
1448         break;
1449     case INSTR_IF:
1450     case INSTR_IFNOT:
1451 #if 0
1452     case INSTR_IF_S:
1453     case INSTR_IFNOT_S:
1454 #endif
1455     case INSTR_RETURN:
1456     case VINSTR_COND:
1457         *write = 0;
1458         *read = 1;
1459         break;
1460     default:
1461         *write = 1;
1462         *read = 6;
1463         break;
1464     };
1465 }
1466
1467 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
1468 {
1469     size_t i;
1470     bool changed = false;
1471     bool tempbool;
1472     for (i = 0; i != self->living_count; ++i)
1473     {
1474         tempbool = ir_value_life_merge(self->living[i], eid);
1475         /* debug
1476         if (tempbool)
1477             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1478         */
1479         changed = changed || tempbool;
1480     }
1481     return changed;
1482 }
1483
1484 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
1485 {
1486     size_t i;
1487     /* values which have been read in a previous iteration are now
1488      * in the "living" array even if the previous block doesn't use them.
1489      * So we have to remove whatever does not exist in the previous block.
1490      * They will be re-added on-read, but the liferange merge won't cause
1491      * a change.
1492      */
1493     for (i = 0; i < self->living_count; ++i)
1494     {
1495         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1496             if (!ir_block_living_remove(self, i))
1497                 return false;
1498             --i;
1499         }
1500     }
1501
1502     /* Whatever the previous block still has in its living set
1503      * must now be added to ours as well.
1504      */
1505     for (i = 0; i < prev->living_count; ++i)
1506     {
1507         if (ir_block_living_find(self, prev->living[i], NULL))
1508             continue;
1509         if (!ir_block_living_add(self, prev->living[i]))
1510             return false;
1511         /*
1512         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1513         */
1514     }
1515     return true;
1516 }
1517
1518 static bool ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
1519 {
1520     ir_instr *instr;
1521     ir_value *value;
1522     bool  tempbool;
1523     size_t i, o, p, rd;
1524     /* bitmasks which operands are read from or written to */
1525     size_t read, write;
1526     new_reads_t new_reads;
1527     char dbg_ind[16] = { '#', '0' };
1528     (void)dbg_ind;
1529
1530     MEM_VECTOR_INIT(&new_reads, v);
1531
1532     if (prev)
1533     {
1534         if (!ir_block_life_prop_previous(self, prev, changed))
1535             return false;
1536     }
1537
1538     i = self->instr_count;
1539     while (i)
1540     { --i;
1541         instr = self->instr[i];
1542
1543         /* PHI operands are always read operands */
1544         for (p = 0; p < instr->phi_count; ++p)
1545         {
1546             value = instr->phi[p].value;
1547             /* used this before new_reads - puts the last read into the life range as well
1548             if (!ir_block_living_find(self, value, NULL))
1549                 ir_block_living_add(self, value);
1550             */
1551             /* fprintf(stderr, "read: %s\n", value->_name); */
1552             if (!new_reads_t_v_find(&new_reads, value, NULL))
1553             {
1554                 if (!new_reads_t_v_add(&new_reads, value))
1555                     goto on_error;
1556             }
1557         }
1558
1559         /* See which operands are read and write operands */
1560         ir_op_read_write(instr->opcode, &read, &write);
1561
1562         /* Go through the 3 main operands */
1563         for (o = 0; o < 3; ++o)
1564         {
1565             if (!instr->_ops[o]) /* no such operand */
1566                 continue;
1567
1568             value = instr->_ops[o];
1569
1570             /* We only care about locals */
1571             if (value->store != store_value &&
1572                 value->store != store_local)
1573                 continue;
1574
1575             /* read operands */
1576             if (read & (1<<o))
1577             {
1578                 /* used this before new_reads - puts the last read into the life range as well
1579                 if (!ir_block_living_find(self, value, NULL))
1580                     ir_block_living_add(self, value);
1581                 */
1582                 /* fprintf(stderr, "read: %s\n", value->_name); */
1583                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1584                 {
1585                     if (!new_reads_t_v_add(&new_reads, value))
1586                         goto on_error;
1587                 }
1588             }
1589
1590             /* write operands */
1591             /* When we write to a local, we consider it "dead" for the
1592              * remaining upper part of the function, since in SSA a value
1593              * can only be written once (== created)
1594              */
1595             if (write & (1<<o))
1596             {
1597                 size_t idx, readidx;
1598                 bool in_living = ir_block_living_find(self, value, &idx);
1599                 bool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1600                 if (!in_living && !in_reads)
1601                 {
1602                     /* If the value isn't alive it hasn't been read before... */
1603                     /* TODO: See if the warning can be emitted during parsing or AST processing
1604                      * otherwise have warning printed here.
1605                      * IF printing a warning here: include filecontext_t,
1606                      * and make sure it's only printed once
1607                      * since this function is run multiple times.
1608                      */
1609                     /* For now: debug info: */
1610                     fprintf(stderr, "Value only written %s\n", value->name);
1611                     tempbool = ir_value_life_merge(value, instr->eid);
1612                     *changed = *changed || tempbool;
1613                     /*
1614                     ir_instr_dump(instr, dbg_ind, printf);
1615                     abort();
1616                     */
1617                 } else {
1618                     /* since 'living' won't contain it
1619                      * anymore, merge the value, since
1620                      * (A) doesn't.
1621                      */
1622                     tempbool = ir_value_life_merge(value, instr->eid);
1623                     /*
1624                     if (tempbool)
1625                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
1626                     */
1627                     *changed = *changed || tempbool;
1628                     /* Then remove */
1629                     if (!ir_block_living_remove(self, idx))
1630                         goto on_error;
1631                     if (in_reads)
1632                     {
1633                         if (!new_reads_t_v_remove(&new_reads, readidx))
1634                             goto on_error;
1635                     }
1636                 }
1637             }
1638         }
1639         /* (A) */
1640         tempbool = ir_block_living_add_instr(self, instr->eid);
1641         /*fprintf(stderr, "living added values\n");*/
1642         *changed = *changed || tempbool;
1643
1644         /* new reads: */
1645         for (rd = 0; rd < new_reads.v_count; ++rd)
1646         {
1647             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
1648                 if (!ir_block_living_add(self, new_reads.v[rd]))
1649                     goto on_error;
1650             }
1651             if (!i && !self->entries_count) {
1652                 /* fix the top */
1653                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
1654             }
1655         }
1656         MEM_VECTOR_CLEAR(&new_reads, v);
1657     }
1658
1659     if (self->run_id == self->owner->run_id)
1660         return true;
1661
1662     self->run_id = self->owner->run_id;
1663
1664     for (i = 0; i < self->entries_count; ++i)
1665     {
1666         ir_block *entry = self->entries[i];
1667         ir_block_life_propagate(entry, self, changed);
1668     }
1669
1670     return true;
1671 on_error:
1672     MEM_VECTOR_CLEAR(&new_reads, v);
1673     return false;
1674 }
1675
1676 /***********************************************************************
1677  *IR DEBUG Dump functions...
1678  */
1679
1680 #define IND_BUFSZ 1024
1681
1682 const char *qc_opname(int op)
1683 {
1684     if (op < 0) return "<INVALID>";
1685     if (op < ( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
1686         return asm_instr[op].m;
1687     switch (op) {
1688         case VINSTR_PHI:  return "PHI";
1689         case VINSTR_JUMP: return "JUMP";
1690         case VINSTR_COND: return "COND";
1691         default:          return "<UNK>";
1692     }
1693 }
1694
1695 void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
1696 {
1697         size_t i;
1698         char indent[IND_BUFSZ];
1699         indent[0] = '\t';
1700         indent[1] = 0;
1701
1702         oprintf("module %s\n", b->name);
1703         for (i = 0; i < b->globals_count; ++i)
1704         {
1705                 oprintf("global ");
1706                 if (b->globals[i]->isconst)
1707                         oprintf("%s = ", b->globals[i]->name);
1708                 ir_value_dump(b->globals[i], oprintf);
1709                 oprintf("\n");
1710         }
1711         for (i = 0; i < b->functions_count; ++i)
1712                 ir_function_dump(b->functions[i], indent, oprintf);
1713         oprintf("endmodule %s\n", b->name);
1714 }
1715
1716 void ir_function_dump(ir_function *f, char *ind,
1717                       int (*oprintf)(const char*, ...))
1718 {
1719         size_t i;
1720         oprintf("%sfunction %s\n", ind, f->name);
1721         strncat(ind, "\t", IND_BUFSZ);
1722         if (f->locals_count)
1723         {
1724                 oprintf("%s%i locals:\n", ind, (int)f->locals_count);
1725                 for (i = 0; i < f->locals_count; ++i) {
1726                         oprintf("%s\t", ind);
1727                         ir_value_dump(f->locals[i], oprintf);
1728                         oprintf("\n");
1729                 }
1730         }
1731         if (f->blocks_count)
1732         {
1733
1734                 oprintf("%slife passes: %i\n", ind, (int)f->blocks[0]->run_id);
1735                 for (i = 0; i < f->blocks_count; ++i)
1736                         ir_block_dump(f->blocks[i], ind, oprintf);
1737
1738         }
1739         ind[strlen(ind)-1] = 0;
1740         oprintf("%sendfunction %s\n", ind, f->name);
1741 }
1742
1743 void ir_block_dump(ir_block* b, char *ind,
1744                    int (*oprintf)(const char*, ...))
1745 {
1746         size_t i;
1747         oprintf("%s:%s\n", ind, b->label);
1748         strncat(ind, "\t", IND_BUFSZ);
1749
1750         for (i = 0; i < b->instr_count; ++i)
1751                 ir_instr_dump(b->instr[i], ind, oprintf);
1752         ind[strlen(ind)-1] = 0;
1753 }
1754
1755 void dump_phi(ir_instr *in, char *ind,
1756               int (*oprintf)(const char*, ...))
1757 {
1758         size_t i;
1759         oprintf("%s <- phi ", in->_ops[0]->name);
1760         for (i = 0; i < in->phi_count; ++i)
1761         {
1762                 oprintf("([%s] : %s) ", in->phi[i].from->label,
1763                                         in->phi[i].value->name);
1764         }
1765         oprintf("\n");
1766 }
1767
1768 void ir_instr_dump(ir_instr *in, char *ind,
1769                        int (*oprintf)(const char*, ...))
1770 {
1771         size_t i;
1772         const char *comma = NULL;
1773
1774         oprintf("%s (%i) ", ind, (int)in->eid);
1775
1776         if (in->opcode == VINSTR_PHI) {
1777                 dump_phi(in, ind, oprintf);
1778                 return;
1779         }
1780
1781         strncat(ind, "\t", IND_BUFSZ);
1782
1783         if (in->_ops[0] && (in->_ops[1] || in->_ops[2])) {
1784                 ir_value_dump(in->_ops[0], oprintf);
1785                 if (in->_ops[1] || in->_ops[2])
1786                         oprintf(" <- ");
1787         }
1788         oprintf("%s\t", qc_opname(in->opcode));
1789         if (in->_ops[0] && !(in->_ops[1] || in->_ops[2])) {
1790                 ir_value_dump(in->_ops[0], oprintf);
1791                 comma = ",\t";
1792         }
1793         else
1794         {
1795                 for (i = 1; i != 3; ++i) {
1796                         if (in->_ops[i]) {
1797                                 if (comma)
1798                                         oprintf(comma);
1799                                 ir_value_dump(in->_ops[i], oprintf);
1800                                 comma = ",\t";
1801                         }
1802                 }
1803         }
1804         if (in->bops[0]) {
1805                 if (comma)
1806                         oprintf(comma);
1807                 oprintf("[%s]", in->bops[0]->label);
1808                 comma = ",\t";
1809         }
1810         if (in->bops[1])
1811                 oprintf("%s[%s]", comma, in->bops[1]->label);
1812         oprintf("\n");
1813         ind[strlen(ind)-1] = 0;
1814 }
1815
1816 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
1817 {
1818         if (v->isconst) {
1819                 switch (v->vtype) {
1820                         case TYPE_VOID:
1821                                 oprintf("(void)");
1822                                 break;
1823                         case TYPE_FLOAT:
1824                                 oprintf("%g", v->constval.vfloat);
1825                                 break;
1826                         case TYPE_VECTOR:
1827                                 oprintf("'%g %g %g'",
1828                                         v->constval.vvec.x,
1829                                         v->constval.vvec.y,
1830                                         v->constval.vvec.z);
1831                                 break;
1832                         case TYPE_ENTITY:
1833                                 oprintf("(entity)");
1834                                 break;
1835                         case TYPE_STRING:
1836                                 oprintf("\"%s\"", v->constval.vstring);
1837                                 break;
1838 #if 0
1839                         case TYPE_INTEGER:
1840                                 oprintf("%i", v->constval.vint);
1841                                 break;
1842 #endif
1843                         case TYPE_POINTER:
1844                                 oprintf("&%s",
1845                                         v->constval.vpointer->name);
1846                                 break;
1847                 }
1848         } else {
1849                 oprintf("%s", v->name);
1850         }
1851 }
1852
1853 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...))
1854 {
1855         size_t i;
1856         oprintf("Life of %s:\n", self->name);
1857         for (i = 0; i < self->life_count; ++i)
1858         {
1859                 oprintf(" + [%i, %i]\n", self->life[i].start, self->life[i].end);
1860         }
1861 }