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->fieldtype = TYPE_VOID;
 385     self->store = storetype;
 386     MEM_VECTOR_INIT(self, reads);
 387     MEM_VECTOR_INIT(self, writes);
 388     self->isconst = false;
 389     self->context.file = "<@no context>";
 390     self->context.line = 0;
 391     self->name = NULL;
 392     ir_value_set_name(self, name);
 393
 394     memset(&self->constval, 0, sizeof(self->constval));
 395     memset(&self->code,     0, sizeof(self->code));
 396
 397     MEM_VECTOR_INIT(self, life);
 398     return self;
 399 }
 400 MEM_VEC_FUNCTIONS(ir_value, ir_life_entry_t, life)
 401 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, reads)
 402 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, writes)
 403
 404 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 405 {
 406     ir_value *v = ir_value_var(name, storetype, vtype);
 407     if (!v)
 408         return NULL;
 409     if (!ir_function_collect_value(owner, v))
 410     {
 411         ir_value_delete(v);
 412         return NULL;
 413     }
 414     return v;
 415 }
 416
 417 void ir_value_delete(ir_value* self)
 418 {
 419     mem_d((void*)self->name);
 420     if (self->isconst)
 421     {
 422         if (self->vtype == TYPE_STRING)
 423             mem_d((void*)self->constval.vstring);
 424     }
 425     MEM_VECTOR_CLEAR(self, reads);
 426     MEM_VECTOR_CLEAR(self, writes);
 427     MEM_VECTOR_CLEAR(self, life);
 428     mem_d(self);
 429 }
 430
 431 void ir_value_set_name(ir_value *self, const char *name)
 432 {
 433     if (self->name)
 434         mem_d((void*)self->name);
 435     self->name = util_strdup(name);
 436 }
 437
 438 bool ir_value_set_float(ir_value *self, float f)
 439 {
 440     if (self->vtype != TYPE_FLOAT)
 441         return false;
 442     self->constval.vfloat = f;
 443     self->isconst = true;
 444     return true;
 445 }
 446
 447 bool ir_value_set_vector(ir_value *self, vector v)
 448 {
 449     if (self->vtype != TYPE_VECTOR)
 450         return false;
 451     self->constval.vvec = v;
 452     self->isconst = true;
 453     return true;
 454 }
 455
 456 bool ir_value_set_string(ir_value *self, const char *str)
 457 {
 458     if (self->vtype != TYPE_STRING)
 459         return false;
 460     self->constval.vstring = util_strdup(str);
 461     self->isconst = true;
 462     return true;
 463 }
 464
 465 #if 0
 466 bool ir_value_set_int(ir_value *self, int i)
 467 {
 468     if (self->vtype != TYPE_INTEGER)
 469         return false;
 470     self->constval.vint = i;
 471     self->isconst = true;
 472     return true;
 473 }
 474 #endif
 475
 476 bool ir_value_lives(ir_value *self, size_t at)
 477 {
 478     size_t i;
 479     for (i = 0; i < self->life_count; ++i)
 480     {
 481         ir_life_entry_t *life = &self->life[i];
 482         if (life->start <= at && at <= life->end)
 483             return true;
 484         if (life->start > at) /* since it's ordered */
 485             return false;
 486     }
 487     return false;
 488 }
 489
 490 bool ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 491 {
 492     size_t k;
 493     if (!ir_value_life_add(self, e)) /* naive... */
 494         return false;
 495     for (k = self->life_count-1; k > idx; --k)
 496         self->life[k] = self->life[k-1];
 497     self->life[idx] = e;
 498     return true;
 499 }
 500
 501 bool ir_value_life_merge(ir_value *self, size_t s)
 502 {
 503     size_t i;
 504     ir_life_entry_t *life = NULL;
 505     ir_life_entry_t *before = NULL;
 506     ir_life_entry_t new_entry;
 507
 508     /* Find the first range >= s */
 509     for (i = 0; i < self->life_count; ++i)
 510     {
 511         before = life;
 512         life = &self->life[i];
 513         if (life->start > s)
 514             break;
 515     }
 516     /* nothing found? append */
 517     if (i == self->life_count) {
 518         ir_life_entry_t e;
 519         if (life && life->end+1 == s)
 520         {
 521             /* previous life range can be merged in */
 522             life->end++;
 523             return true;
 524         }
 525         if (life && life->end >= s)
 526             return false;
 527         e.start = e.end = s;
 528         if (!ir_value_life_add(self, e))
 529             return false; /* failing */
 530         return true;
 531     }
 532     /* found */
 533     if (before)
 534     {
 535         if (before->end + 1 == s &&
 536             life->start - 1 == s)
 537         {
 538             /* merge */
 539             before->end = life->end;
 540             if (!ir_value_life_remove(self, i))
 541                 return false; /* failing */
 542             return true;
 543         }
 544         if (before->end + 1 == s)
 545         {
 546             /* extend before */
 547             before->end++;
 548             return true;
 549         }
 550         /* already contained */
 551         if (before->end >= s)
 552             return false;
 553     }
 554     /* extend */
 555     if (life->start - 1 == s)
 556     {
 557         life->start--;
 558         return true;
 559     }
 560     /* insert a new entry */
 561     new_entry.start = new_entry.end = s;
 562     return ir_value_life_insert(self, i, new_entry);
 563 }
 564
 565 bool ir_values_overlap(ir_value *a, ir_value *b)
 566 {
 567     /* For any life entry in A see if it overlaps with
 568      * any life entry in B.
 569      * Note that the life entries are orderes, so we can make a
 570      * more efficient algorithm there than naively translating the
 571      * statement above.
 572      */
 573
 574     ir_life_entry_t *la, *lb, *enda, *endb;
 575
 576     /* first of all, if either has no life range, they cannot clash */
 577     if (!a->life_count || !b->life_count)
 578         return false;
 579
 580     la = a->life;
 581     lb = b->life;
 582     enda = la + a->life_count;
 583     endb = lb + b->life_count;
 584     while (true)
 585     {
 586         /* check if the entries overlap, for that,
 587          * both must start before the other one ends.
 588          */
 589 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
 590         if (la->start <= lb->end &&
 591             lb->start <= la->end)
 592 #else
 593         if (la->start <  lb->end &&
 594             lb->start <  la->end)
 595 #endif
 596         {
 597             return true;
 598         }
 599
 600         /* entries are ordered
 601          * one entry is earlier than the other
 602          * that earlier entry will be moved forward
 603          */
 604         if (la->end < lb->end)
 605         {
 606             /* order: A B, move A forward
 607              * check if we hit the end with A
 608              */
 609             if (++la == enda)
 610                 break;
 611         }
 612         else if (lb->end < la->end)
 613         {
 614             /* order: B A, move B forward
 615              * check if we hit the end with B
 616              */
 617             if (++lb == endb)
 618                 break;
 619         }
 620     }
 621     return false;
 622 }
 623
 624 /***********************************************************************
 625  *IR main operations
 626  */
 627
 628 bool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 629 {
 630     if (target->store == store_value) {
 631         fprintf(stderr, "cannot store to an SSA value\n");
 632         fprintf(stderr, "trying to store: %s <- %s\n", target->name, what->name);
 633         return false;
 634     } else {
 635         ir_instr *in = ir_instr_new(self, op);
 636         if (!in)
 637             return false;
 638         if (!ir_instr_op(in, 0, target, true) ||
 639             !ir_instr_op(in, 1, what, false)  ||
 640             !ir_block_instr_add(self, in) )
 641         {
 642             return false;
 643         }
 644         return true;
 645     }
 646 }
 647
 648 bool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 649 {
 650     int op = 0;
 651     int vtype;
 652     if (target->vtype == TYPE_VARIANT)
 653         vtype = what->vtype;
 654     else
 655         vtype = target->vtype;
 656
 657     switch (vtype) {
 658         case TYPE_FLOAT:
 659 #if 0
 660             if (what->vtype == TYPE_INTEGER)
 661                 op = INSTR_CONV_ITOF;
 662             else
 663 #endif
 664                 op = INSTR_STORE_F;
 665             break;
 666         case TYPE_VECTOR:
 667             op = INSTR_STORE_V;
 668             break;
 669         case TYPE_ENTITY:
 670             op = INSTR_STORE_ENT;
 671             break;
 672         case TYPE_STRING:
 673             op = INSTR_STORE_S;
 674             break;
 675         case TYPE_FIELD:
 676             op = INSTR_STORE_FLD;
 677             break;
 678 #if 0
 679         case TYPE_INTEGER:
 680             if (what->vtype == TYPE_INTEGER)
 681                 op = INSTR_CONV_FTOI;
 682             else
 683                 op = INSTR_STORE_I;
 684             break;
 685 #endif
 686         case TYPE_POINTER:
 687 #if 0
 688             op = INSTR_STORE_I;
 689 #else
 690             op = INSTR_STORE_ENT;
 691 #endif
 692             break;
 693         default:
 694             /* Unknown type */
 695             return false;
 696     }
 697     return ir_block_create_store_op(self, op, target, what);
 698 }
 699
 700 bool ir_block_create_storep(ir_block *self, ir_value *target, ir_value *what)
 701 {
 702     int op = 0;
 703     int vtype;
 704
 705     if (target->vtype != TYPE_POINTER)
 706         return false;
 707
 708     /* storing using pointer - target is a pointer, type must be
 709      * inferred from source
 710      */
 711     vtype = what->vtype;
 712
 713     switch (vtype) {
 714         case TYPE_FLOAT:
 715             op = INSTR_STOREP_F;
 716             break;
 717         case TYPE_VECTOR:
 718             op = INSTR_STOREP_V;
 719             break;
 720         case TYPE_ENTITY:
 721             op = INSTR_STOREP_ENT;
 722             break;
 723         case TYPE_STRING:
 724             op = INSTR_STOREP_S;
 725             break;
 726         case TYPE_FIELD:
 727             op = INSTR_STOREP_FLD;
 728             break;
 729 #if 0
 730         case TYPE_INTEGER:
 731             op = INSTR_STOREP_I;
 732             break;
 733 #endif
 734         case TYPE_POINTER:
 735 #if 0
 736             op = INSTR_STOREP_I;
 737 #else
 738             op = INSTR_STOREP_ENT;
 739 #endif
 740             break;
 741         default:
 742             /* Unknown type */
 743             return false;
 744     }
 745     return ir_block_create_store_op(self, op, target, what);
 746 }
 747
 748 bool ir_block_create_return(ir_block *self, ir_value *v)
 749 {
 750     ir_instr *in;
 751     if (self->final) {
 752         fprintf(stderr, "block already ended (%s)\n", self->label);
 753         return false;
 754     }
 755     self->final = true;
 756     self->is_return = true;
 757     in = ir_instr_new(self, INSTR_RETURN);
 758     if (!in)
 759         return false;
 760
 761     if (!ir_instr_op(in, 0, v, false) ||
 762         !ir_block_instr_add(self, in) )
 763     {
 764         return false;
 765     }
 766     return true;
 767 }
 768
 769 bool ir_block_create_if(ir_block *self, ir_value *v,
 770                         ir_block *ontrue, ir_block *onfalse)
 771 {
 772     ir_instr *in;
 773     if (self->final) {
 774         fprintf(stderr, "block already ended (%s)\n", self->label);
 775         return false;
 776     }
 777     self->final = true;
 778     /*in = ir_instr_new(self, (v->vtype == TYPE_STRING ? INSTR_IF_S : INSTR_IF_F));*/
 779     in = ir_instr_new(self, VINSTR_COND);
 780     if (!in)
 781         return false;
 782
 783     if (!ir_instr_op(in, 0, v, false)) {
 784         ir_instr_delete(in);
 785         return false;
 786     }
 787
 788     in->bops[0] = ontrue;
 789     in->bops[1] = onfalse;
 790
 791     if (!ir_block_instr_add(self, in))
 792         return false;
 793
 794     if (!ir_block_exits_add(self, ontrue)    ||
 795         !ir_block_exits_add(self, onfalse)   ||
 796         !ir_block_entries_add(ontrue, self)  ||
 797         !ir_block_entries_add(onfalse, self) )
 798     {
 799         return false;
 800     }
 801     return true;
 802 }
 803
 804 bool ir_block_create_jump(ir_block *self, ir_block *to)
 805 {
 806     ir_instr *in;
 807     if (self->final) {
 808         fprintf(stderr, "block already ended (%s)\n", self->label);
 809         return false;
 810     }
 811     self->final = true;
 812     in = ir_instr_new(self, VINSTR_JUMP);
 813     if (!in)
 814         return false;
 815
 816     in->bops[0] = to;
 817     if (!ir_block_instr_add(self, in))
 818         return false;
 819
 820     if (!ir_block_exits_add(self, to) ||
 821         !ir_block_entries_add(to, self) )
 822     {
 823         return false;
 824     }
 825     return true;
 826 }
 827
 828 bool ir_block_create_goto(ir_block *self, ir_block *to)
 829 {
 830     ir_instr *in;
 831     if (self->final) {
 832         fprintf(stderr, "block already ended (%s)\n", self->label);
 833         return false;
 834     }
 835     self->final = true;
 836     in = ir_instr_new(self, INSTR_GOTO);
 837     if (!in)
 838         return false;
 839
 840     in->bops[0] = to;
 841     if (!ir_block_instr_add(self, in))
 842         return false;
 843
 844     if (!ir_block_exits_add(self, to) ||
 845         !ir_block_entries_add(to, self) )
 846     {
 847         return false;
 848     }
 849     return true;
 850 }
 851
 852 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
 853 {
 854     ir_value *out;
 855     ir_instr *in;
 856     in = ir_instr_new(self, VINSTR_PHI);
 857     if (!in)
 858         return NULL;
 859     out = ir_value_out(self->owner, label, store_value, ot);
 860     if (!out) {
 861         ir_instr_delete(in);
 862         return NULL;
 863     }
 864     if (!ir_instr_op(in, 0, out, true)) {
 865         ir_instr_delete(in);
 866         ir_value_delete(out);
 867         return NULL;
 868     }
 869     if (!ir_block_instr_add(self, in)) {
 870         ir_instr_delete(in);
 871         ir_value_delete(out);
 872         return NULL;
 873     }
 874     return in;
 875 }
 876
 877 ir_value* ir_phi_value(ir_instr *self)
 878 {
 879     return self->_ops[0];
 880 }
 881
 882 bool ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
 883 {
 884     ir_phi_entry_t pe;
 885
 886     if (!ir_block_entries_find(self->owner, b, NULL)) {
 887         /* Must not be possible to cause this, otherwise the AST
 888          * is doing something wrong.
 889          */
 890         fprintf(stderr, "Invalid entry block for PHI\n");
 891         abort();
 892     }
 893
 894     pe.value = v;
 895     pe.from = b;
 896     if (!ir_value_reads_add(v, self))
 897         return false;
 898     return ir_instr_phi_add(self, pe);
 899 }
 900
 901 /* binary op related code */
 902
 903 ir_value* ir_block_create_binop(ir_block *self,
 904                                 const char *label, int opcode,
 905                                 ir_value *left, ir_value *right)
 906 {
 907     int ot = TYPE_VOID;
 908     switch (opcode) {
 909         case INSTR_ADD_F:
 910         case INSTR_SUB_F:
 911         case INSTR_DIV_F:
 912         case INSTR_MUL_F:
 913         case INSTR_MUL_V:
 914         case INSTR_AND:
 915         case INSTR_OR:
 916 #if 0
 917         case INSTR_AND_I:
 918         case INSTR_AND_IF:
 919         case INSTR_AND_FI:
 920         case INSTR_OR_I:
 921         case INSTR_OR_IF:
 922         case INSTR_OR_FI:
 923 #endif
 924         case INSTR_BITAND:
 925         case INSTR_BITOR:
 926 #if 0
 927         case INSTR_SUB_S: /* -- offset of string as float */
 928         case INSTR_MUL_IF:
 929         case INSTR_MUL_FI:
 930         case INSTR_DIV_IF:
 931         case INSTR_DIV_FI:
 932         case INSTR_BITOR_IF:
 933         case INSTR_BITOR_FI:
 934         case INSTR_BITAND_FI:
 935         case INSTR_BITAND_IF:
 936         case INSTR_EQ_I:
 937         case INSTR_NE_I:
 938 #endif
 939             ot = TYPE_FLOAT;
 940             break;
 941 #if 0
 942         case INSTR_ADD_I:
 943         case INSTR_ADD_IF:
 944         case INSTR_ADD_FI:
 945         case INSTR_SUB_I:
 946         case INSTR_SUB_FI:
 947         case INSTR_SUB_IF:
 948         case INSTR_MUL_I:
 949         case INSTR_DIV_I:
 950         case INSTR_BITAND_I:
 951         case INSTR_BITOR_I:
 952         case INSTR_XOR_I:
 953         case INSTR_RSHIFT_I:
 954         case INSTR_LSHIFT_I:
 955             ot = TYPE_INTEGER;
 956             break;
 957 #endif
 958         case INSTR_ADD_V:
 959         case INSTR_SUB_V:
 960         case INSTR_MUL_VF:
 961         case INSTR_MUL_FV:
 962 #if 0
 963         case INSTR_DIV_VF:
 964         case INSTR_MUL_IV:
 965         case INSTR_MUL_VI:
 966 #endif
 967             ot = TYPE_VECTOR;
 968             break;
 969 #if 0
 970         case INSTR_ADD_SF:
 971             ot = TYPE_POINTER;
 972             break;
 973 #endif
 974         default:
 975             /* ranges: */
 976             /* boolean operations result in floats */
 977             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
 978                 ot = TYPE_FLOAT;
 979             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
 980                 ot = TYPE_FLOAT;
 981 #if 0
 982             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
 983                 ot = TYPE_FLOAT;
 984 #endif
 985             break;
 986     };
 987     if (ot == TYPE_VOID) {
 988         /* The AST or parser were supposed to check this! */
 989         return NULL;
 990     }
 991
 992     return ir_block_create_general_instr(self, label, opcode, left, right, ot);
 993 }
 994
 995 ir_value* ir_block_create_general_instr(ir_block *self, const char *label,
 996                                         int op, ir_value *a, ir_value *b, int outype)
 997 {
 998     ir_instr *instr;
 999     ir_value *out;
1000
1001     out = ir_value_out(self->owner, label, store_value, outype);
1002     if (!out)
1003         return NULL;
1004
1005     instr = ir_instr_new(self, op);
1006     if (!instr) {
1007         ir_value_delete(out);
1008         return NULL;
1009     }
1010
1011     if (!ir_instr_op(instr, 0, out, true) ||
1012         !ir_instr_op(instr, 1, a, false) ||
1013         !ir_instr_op(instr, 2, b, false) )
1014     {
1015         goto on_error;
1016     }
1017
1018     if (!ir_block_instr_add(self, instr))
1019         goto on_error;
1020
1021     return out;
1022 on_error:
1023     ir_instr_delete(instr);
1024     ir_value_delete(out);
1025     return NULL;
1026 }
1027
1028 ir_value* ir_block_create_fieldaddress(ir_block *self, const char *label, ir_value *ent, ir_value *field)
1029 {
1030     /* Support for various pointer types todo if so desired */
1031     if (ent->vtype != TYPE_ENTITY)
1032         return NULL;
1033
1034     if (field->vtype != TYPE_FIELD)
1035         return NULL;
1036
1037     return ir_block_create_general_instr(self, label, INSTR_ADDRESS, ent, field, TYPE_POINTER);
1038 }
1039
1040 ir_value* ir_block_create_load_from_ent(ir_block *self, const char *label, ir_value *ent, ir_value *field, int outype)
1041 {
1042     int op;
1043     if (ent->vtype != TYPE_ENTITY)
1044         return NULL;
1045
1046     /* at some point we could redirect for TYPE_POINTER... but that could lead to carelessness */
1047     if (field->vtype != TYPE_FIELD)
1048         return NULL;
1049
1050     switch (outype)
1051     {
1052         case TYPE_FLOAT:   op = INSTR_LOAD_F;   break;
1053         case TYPE_VECTOR:  op = INSTR_LOAD_V;   break;
1054         case TYPE_STRING:  op = INSTR_LOAD_S;   break;
1055         case TYPE_FIELD:   op = INSTR_LOAD_FLD; break;
1056         case TYPE_ENTITY:  op = INSTR_LOAD_ENT; break;
1057 #if 0
1058         case TYPE_POINTER: op = INSTR_LOAD_I;   break;
1059         case TYPE_INTEGER: op = INSTR_LOAD_I;   break;
1060 #endif
1061         default:
1062             return NULL;
1063     }
1064
1065     return ir_block_create_general_instr(self, label, op, ent, field, outype);
1066 }
1067
1068 ir_value* ir_block_create_add(ir_block *self,
1069                               const char *label,
1070                               ir_value *left, ir_value *right)
1071 {
1072     int op = 0;
1073     int l = left->vtype;
1074     int r = right->vtype;
1075     if (l == r) {
1076         switch (l) {
1077             default:
1078                 return NULL;
1079             case TYPE_FLOAT:
1080                 op = INSTR_ADD_F;
1081                 break;
1082 #if 0
1083             case TYPE_INTEGER:
1084                 op = INSTR_ADD_I;
1085                 break;
1086 #endif
1087             case TYPE_VECTOR:
1088                 op = INSTR_ADD_V;
1089                 break;
1090         }
1091     } else {
1092 #if 0
1093         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1094             op = INSTR_ADD_FI;
1095         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1096             op = INSTR_ADD_IF;
1097         else
1098 #endif
1099             return NULL;
1100     }
1101     return ir_block_create_binop(self, label, op, left, right);
1102 }
1103
1104 ir_value* ir_block_create_sub(ir_block *self,
1105                               const char *label,
1106                               ir_value *left, ir_value *right)
1107 {
1108     int op = 0;
1109     int l = left->vtype;
1110     int r = right->vtype;
1111     if (l == r) {
1112
1113         switch (l) {
1114             default:
1115                 return NULL;
1116             case TYPE_FLOAT:
1117                 op = INSTR_SUB_F;
1118                 break;
1119 #if 0
1120             case TYPE_INTEGER:
1121                 op = INSTR_SUB_I;
1122                 break;
1123 #endif
1124             case TYPE_VECTOR:
1125                 op = INSTR_SUB_V;
1126                 break;
1127         }
1128     } else {
1129 #if 0
1130         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1131             op = INSTR_SUB_FI;
1132         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1133             op = INSTR_SUB_IF;
1134         else
1135 #endif
1136             return NULL;
1137     }
1138     return ir_block_create_binop(self, label, op, left, right);
1139 }
1140
1141 ir_value* ir_block_create_mul(ir_block *self,
1142                               const char *label,
1143                               ir_value *left, ir_value *right)
1144 {
1145     int op = 0;
1146     int l = left->vtype;
1147     int r = right->vtype;
1148     if (l == r) {
1149
1150         switch (l) {
1151             default:
1152                 return NULL;
1153             case TYPE_FLOAT:
1154                 op = INSTR_MUL_F;
1155                 break;
1156 #if 0
1157             case TYPE_INTEGER:
1158                 op = INSTR_MUL_I;
1159                 break;
1160 #endif
1161             case TYPE_VECTOR:
1162                 op = INSTR_MUL_V;
1163                 break;
1164         }
1165     } else {
1166         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1167             op = INSTR_MUL_VF;
1168         else if ( (l == TYPE_FLOAT && r == TYPE_VECTOR) )
1169             op = INSTR_MUL_FV;
1170 #if 0
1171         else if ( (l == TYPE_VECTOR && r == TYPE_INTEGER) )
1172             op = INSTR_MUL_VI;
1173         else if ( (l == TYPE_INTEGER && r == TYPE_VECTOR) )
1174             op = INSTR_MUL_IV;
1175         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1176             op = INSTR_MUL_FI;
1177         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1178             op = INSTR_MUL_IF;
1179 #endif
1180         else
1181             return NULL;
1182     }
1183     return ir_block_create_binop(self, label, op, left, right);
1184 }
1185
1186 ir_value* ir_block_create_div(ir_block *self,
1187                               const char *label,
1188                               ir_value *left, ir_value *right)
1189 {
1190     int op = 0;
1191     int l = left->vtype;
1192     int r = right->vtype;
1193     if (l == r) {
1194
1195         switch (l) {
1196             default:
1197                 return NULL;
1198             case TYPE_FLOAT:
1199                 op = INSTR_DIV_F;
1200                 break;
1201 #if 0
1202             case TYPE_INTEGER:
1203                 op = INSTR_DIV_I;
1204                 break;
1205 #endif
1206         }
1207     } else {
1208 #if 0
1209         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1210             op = INSTR_DIV_VF;
1211         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1212             op = INSTR_DIV_FI;
1213         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1214             op = INSTR_DIV_IF;
1215         else
1216 #endif
1217             return NULL;
1218     }
1219     return ir_block_create_binop(self, label, op, left, right);
1220 }
1221
1222 /* PHI resolving breaks the SSA, and must thus be the last
1223  * step before life-range calculation.
1224  */
1225
1226 static bool ir_block_naive_phi(ir_block *self);
1227 bool ir_function_naive_phi(ir_function *self)
1228 {
1229     size_t i;
1230
1231     for (i = 0; i < self->blocks_count; ++i)
1232     {
1233         if (!ir_block_naive_phi(self->blocks[i]))
1234             return false;
1235     }
1236     return true;
1237 }
1238
1239 static bool ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
1240 {
1241     ir_instr *instr;
1242     size_t i;
1243
1244     /* create a store */
1245     if (!ir_block_create_store(block, old, what))
1246         return false;
1247
1248     /* we now move it up */
1249     instr = block->instr[block->instr_count-1];
1250     for (i = block->instr_count; i > iid; --i)
1251         block->instr[i] = block->instr[i-1];
1252     block->instr[i] = instr;
1253
1254     return true;
1255 }
1256
1257 static bool ir_block_naive_phi(ir_block *self)
1258 {
1259     size_t i, p, w;
1260     /* FIXME: optionally, create_phi can add the phis
1261      * to a list so we don't need to loop through blocks
1262      * - anyway: "don't optimize YET"
1263      */
1264     for (i = 0; i < self->instr_count; ++i)
1265     {
1266         ir_instr *instr = self->instr[i];
1267         if (instr->opcode != VINSTR_PHI)
1268             continue;
1269
1270         if (!ir_block_instr_remove(self, i))
1271             return false;
1272         --i; /* NOTE: i+1 below */
1273
1274         for (p = 0; p < instr->phi_count; ++p)
1275         {
1276             ir_value *v = instr->phi[p].value;
1277             for (w = 0; w < v->writes_count; ++w) {
1278                 ir_value *old;
1279
1280                 if (!v->writes[w]->_ops[0])
1281                     continue;
1282
1283                 /* When the write was to a global, we have to emit a mov */
1284                 old = v->writes[w]->_ops[0];
1285
1286                 /* The original instruction now writes to the PHI target local */
1287                 if (v->writes[w]->_ops[0] == v)
1288                     v->writes[w]->_ops[0] = instr->_ops[0];
1289
1290                 if (old->store != store_value && old->store != store_local)
1291                 {
1292                     /* If it originally wrote to a global we need to store the value
1293                      * there as welli
1294                      */
1295                     if (!ir_naive_phi_emit_store(self, i+1, old, v))
1296                         return false;
1297                     if (i+1 < self->instr_count)
1298                         instr = self->instr[i+1];
1299                     else
1300                         instr = NULL;
1301                     /* In case I forget and access instr later, it'll be NULL
1302                      * when it's a problem, to make sure we crash, rather than accessing
1303                      * invalid data.
1304                      */
1305                 }
1306                 else
1307                 {
1308                     /* If it didn't, we can replace all reads by the phi target now. */
1309                     size_t r;
1310                     for (r = 0; r < old->reads_count; ++r)
1311                     {
1312                         size_t op;
1313                         ir_instr *ri = old->reads[r];
1314                         for (op = 0; op < ri->phi_count; ++op) {
1315                             if (ri->phi[op].value == old)
1316                                 ri->phi[op].value = v;
1317                         }
1318                         for (op = 0; op < 3; ++op) {
1319                             if (ri->_ops[op] == old)
1320                                 ri->_ops[op] = v;
1321                         }
1322                     }
1323                 }
1324             }
1325         }
1326         ir_instr_delete(instr);
1327     }
1328     return true;
1329 }
1330
1331 /***********************************************************************
1332  *IR Temp allocation code
1333  * Propagating value life ranges by walking through the function backwards
1334  * until no more changes are made.
1335  * In theory this should happen once more than once for every nested loop
1336  * level.
1337  * Though this implementation might run an additional time for if nests.
1338  */
1339
1340 typedef struct
1341 {
1342     ir_value* *v;
1343     size_t    v_count;
1344     size_t    v_alloc;
1345 } new_reads_t;
1346 MEM_VEC_FUNCTIONS_ALL(new_reads_t, ir_value*, v)
1347
1348 /* Enumerate instructions used by value's life-ranges
1349  */
1350 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1351 {
1352     size_t i;
1353     size_t eid = *_eid;
1354     for (i = 0; i < self->instr_count; ++i)
1355     {
1356         self->instr[i]->eid = eid++;
1357     }
1358     *_eid = eid;
1359 }
1360
1361 /* Enumerate blocks and instructions.
1362  * The block-enumeration is unordered!
1363  * We do not really use the block enumreation, however
1364  * the instruction enumeration is important for life-ranges.
1365  */
1366 void ir_function_enumerate(ir_function *self)
1367 {
1368     size_t i;
1369     size_t instruction_id = 0;
1370     for (i = 0; i < self->blocks_count; ++i)
1371     {
1372         self->blocks[i]->eid = i;
1373         self->blocks[i]->run_id = 0;
1374         ir_block_enumerate(self->blocks[i], &instruction_id);
1375     }
1376 }
1377
1378 static bool ir_block_life_propagate(ir_block *b, ir_block *prev, bool *changed);
1379 bool ir_function_calculate_liferanges(ir_function *self)
1380 {
1381     size_t i;
1382     bool changed;
1383
1384     do {
1385         self->run_id++;
1386         changed = false;
1387         for (i = 0; i != self->blocks_count; ++i)
1388         {
1389             if (self->blocks[i]->is_return)
1390             {
1391                 if (!ir_block_life_propagate(self->blocks[i], NULL, &changed))
1392                     return false;
1393             }
1394         }
1395     } while (changed);
1396     return true;
1397 }
1398
1399 /* Get information about which operand
1400  * is read from, or written to.
1401  */
1402 static void ir_op_read_write(int op, size_t *read, size_t *write)
1403 {
1404     switch (op)
1405     {
1406     case VINSTR_JUMP:
1407     case INSTR_GOTO:
1408         *write = 0;
1409         *read = 0;
1410         break;
1411     case INSTR_IF:
1412     case INSTR_IFNOT:
1413 #if 0
1414     case INSTR_IF_S:
1415     case INSTR_IFNOT_S:
1416 #endif
1417     case INSTR_RETURN:
1418     case VINSTR_COND:
1419         *write = 0;
1420         *read = 1;
1421         break;
1422     default:
1423         *write = 1;
1424         *read = 6;
1425         break;
1426     };
1427 }
1428
1429 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
1430 {
1431     size_t i;
1432     bool changed = false;
1433     bool tempbool;
1434     for (i = 0; i != self->living_count; ++i)
1435     {
1436         tempbool = ir_value_life_merge(self->living[i], eid);
1437         /* debug
1438         if (tempbool)
1439             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1440         */
1441         changed = changed || tempbool;
1442     }
1443     return changed;
1444 }
1445
1446 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
1447 {
1448     size_t i;
1449     /* values which have been read in a previous iteration are now
1450      * in the "living" array even if the previous block doesn't use them.
1451      * So we have to remove whatever does not exist in the previous block.
1452      * They will be re-added on-read, but the liferange merge won't cause
1453      * a change.
1454      */
1455     for (i = 0; i < self->living_count; ++i)
1456     {
1457         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1458             if (!ir_block_living_remove(self, i))
1459                 return false;
1460             --i;
1461         }
1462     }
1463
1464     /* Whatever the previous block still has in its living set
1465      * must now be added to ours as well.
1466      */
1467     for (i = 0; i < prev->living_count; ++i)
1468     {
1469         if (ir_block_living_find(self, prev->living[i], NULL))
1470             continue;
1471         if (!ir_block_living_add(self, prev->living[i]))
1472             return false;
1473         /*
1474         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1475         */
1476     }
1477     return true;
1478 }
1479
1480 static bool ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
1481 {
1482     ir_instr *instr;
1483     ir_value *value;
1484     bool  tempbool;
1485     size_t i, o, p;
1486     /* bitmasks which operands are read from or written to */
1487     size_t read, write;
1488 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1489     size_t rd;
1490     new_reads_t new_reads;
1491 #endif
1492     char dbg_ind[16] = { '#', '0' };
1493     (void)dbg_ind;
1494
1495 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1496     MEM_VECTOR_INIT(&new_reads, v);
1497 #endif
1498
1499     if (prev)
1500     {
1501         if (!ir_block_life_prop_previous(self, prev, changed))
1502             return false;
1503     }
1504
1505     i = self->instr_count;
1506     while (i)
1507     { --i;
1508         instr = self->instr[i];
1509
1510         /* PHI operands are always read operands */
1511         for (p = 0; p < instr->phi_count; ++p)
1512         {
1513             value = instr->phi[p].value;
1514 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1515             if (!ir_block_living_find(self, value, NULL) &&
1516                 !ir_block_living_add(self, value))
1517             {
1518                 goto on_error;
1519             }
1520 #else
1521             if (!new_reads_t_v_find(&new_reads, value, NULL))
1522             {
1523                 if (!new_reads_t_v_add(&new_reads, value))
1524                     goto on_error;
1525             }
1526 #endif
1527         }
1528
1529         /* See which operands are read and write operands */
1530         ir_op_read_write(instr->opcode, &read, &write);
1531
1532         /* Go through the 3 main operands */
1533         for (o = 0; o < 3; ++o)
1534         {
1535             if (!instr->_ops[o]) /* no such operand */
1536                 continue;
1537
1538             value = instr->_ops[o];
1539
1540             /* We only care about locals */
1541             if (value->store != store_value &&
1542                 value->store != store_local)
1543                 continue;
1544
1545             /* read operands */
1546             if (read & (1<<o))
1547             {
1548 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1549                 if (!ir_block_living_find(self, value, NULL) &&
1550                     !ir_block_living_add(self, value))
1551                 {
1552                     goto on_error;
1553                 }
1554 #else
1555                 /* fprintf(stderr, "read: %s\n", value->_name); */
1556                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1557                 {
1558                     if (!new_reads_t_v_add(&new_reads, value))
1559                         goto on_error;
1560                 }
1561 #endif
1562             }
1563
1564             /* write operands */
1565             /* When we write to a local, we consider it "dead" for the
1566              * remaining upper part of the function, since in SSA a value
1567              * can only be written once (== created)
1568              */
1569             if (write & (1<<o))
1570             {
1571                 size_t idx;
1572                 bool in_living = ir_block_living_find(self, value, &idx);
1573 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1574                 size_t readidx;
1575                 bool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1576                 if (!in_living && !in_reads)
1577 #else
1578                 if (!in_living)
1579 #endif
1580                 {
1581                     /* If the value isn't alive it hasn't been read before... */
1582                     /* TODO: See if the warning can be emitted during parsing or AST processing
1583                      * otherwise have warning printed here.
1584                      * IF printing a warning here: include filecontext_t,
1585                      * and make sure it's only printed once
1586                      * since this function is run multiple times.
1587                      */
1588                     /* For now: debug info: */
1589                     fprintf(stderr, "Value only written %s\n", value->name);
1590                     tempbool = ir_value_life_merge(value, instr->eid);
1591                     *changed = *changed || tempbool;
1592                     /*
1593                     ir_instr_dump(instr, dbg_ind, printf);
1594                     abort();
1595                     */
1596                 } else {
1597                     /* since 'living' won't contain it
1598                      * anymore, merge the value, since
1599                      * (A) doesn't.
1600                      */
1601                     tempbool = ir_value_life_merge(value, instr->eid);
1602                     /*
1603                     if (tempbool)
1604                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
1605                     */
1606                     *changed = *changed || tempbool;
1607                     /* Then remove */
1608 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1609                     if (!ir_block_living_remove(self, idx))
1610                         goto on_error;
1611 #else
1612                     if (in_reads)
1613                     {
1614                         if (!new_reads_t_v_remove(&new_reads, readidx))
1615                             goto on_error;
1616                     }
1617 #endif
1618                 }
1619             }
1620         }
1621         /* (A) */
1622         tempbool = ir_block_living_add_instr(self, instr->eid);
1623         /*fprintf(stderr, "living added values\n");*/
1624         *changed = *changed || tempbool;
1625
1626 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1627         /* new reads: */
1628         for (rd = 0; rd < new_reads.v_count; ++rd)
1629         {
1630             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
1631                 if (!ir_block_living_add(self, new_reads.v[rd]))
1632                     goto on_error;
1633             }
1634             if (!i && !self->entries_count) {
1635                 /* fix the top */
1636                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
1637             }
1638         }
1639         MEM_VECTOR_CLEAR(&new_reads, v);
1640 #endif
1641     }
1642
1643     if (self->run_id == self->owner->run_id)
1644         return true;
1645
1646     self->run_id = self->owner->run_id;
1647
1648     for (i = 0; i < self->entries_count; ++i)
1649     {
1650         ir_block *entry = self->entries[i];
1651         ir_block_life_propagate(entry, self, changed);
1652     }
1653
1654     return true;
1655 on_error:
1656 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1657     MEM_VECTOR_CLEAR(&new_reads, v);
1658 #endif
1659     return false;
1660 }
1661
1662 /***********************************************************************
1663  *IR Code-Generation
1664  *
1665  * Since the IR has the convention of putting 'write' operands
1666  * at the beginning, we have to rotate the operands of instructions
1667  * properly in order to generate valid QCVM code.
1668  *
1669  * Having destinations at a fixed position is more convenient. In QC
1670  * this is *mostly* OPC,  but FTE adds at least 2 instructions which
1671  * read from from OPA,  and store to OPB rather than OPC.   Which is
1672  * partially the reason why the implementation of these instructions
1673  * in darkplaces has been delayed for so long.
1674  *
1675  * Breaking conventions is annoying...
1676  */
1677 static bool ir_builder_gen_global(ir_builder *self, ir_value *global);
1678
1679 static bool gen_global_field(ir_value *global)
1680 {
1681     if (global->isconst)
1682     {
1683         ir_value *fld = global->constval.vpointer;
1684         if (!fld) {
1685             printf("Invalid field constant with no field: %s\n", global->name);
1686             return false;
1687         }
1688
1689         /* Now, in this case, a relocation would be impossible to code
1690          * since it looks like this:
1691          * .vector v = origin;     <- parse error, wtf is 'origin'?
1692          * .vector origin;
1693          *
1694          * But we will need a general relocation support later anyway
1695          * for functions... might as well support that here.
1696          */
1697         if (!fld->code.globaladdr) {
1698             printf("FIXME: Relocation support\n");
1699             return false;
1700         }
1701
1702         /* copy the field's value */
1703         global->code.globaladdr = code_globals_add(code_globals_data[fld->code.globaladdr]);
1704     }
1705     else
1706     {
1707         prog_section_field fld;
1708
1709         fld.name = global->code.name;
1710         fld.offset = code_fields_elements;
1711         fld.type = global->fieldtype;
1712
1713         if (fld.type == TYPE_VOID) {
1714             printf("Field is missing a type: %s\n", global->name);
1715             return false;
1716         }
1717
1718         if (code_fields_add(fld) < 0)
1719             return false;
1720
1721         global->code.globaladdr = code_globals_add(fld.offset);
1722     }
1723     if (global->code.globaladdr < 0)
1724         return false;
1725     return true;
1726 }
1727
1728 static bool gen_global_pointer(ir_value *global)
1729 {
1730     if (global->isconst)
1731     {
1732         ir_value *target = global->constval.vpointer;
1733         if (!target) {
1734             printf("Invalid pointer constant: %s\n", global->name);
1735             /* NULL pointers are pointing to the NULL constant, which also
1736              * sits at address 0, but still has an ir_value for itself.
1737              */
1738             return false;
1739         }
1740
1741         /* Here, relocations ARE possible - in fteqcc-enhanced-qc:
1742          * void() foo; <- proto
1743          * void() *fooptr = &foo;
1744          * void() foo = { code }
1745          */
1746         if (!target->code.globaladdr) {
1747             /* FIXME: Check for the constant nullptr ir_value!
1748              * because then code.globaladdr being 0 is valid.
1749              */
1750             printf("FIXME: Relocation support\n");
1751             return false;
1752         }
1753
1754         global->code.globaladdr = code_globals_add(target->code.globaladdr);
1755     }
1756     else
1757     {
1758         global->code.globaladdr = code_globals_add(0);
1759     }
1760     if (global->code.globaladdr < 0)
1761         return false;
1762     return true;
1763 }
1764
1765 static bool gen_function_code(ir_function *self)
1766 {
1767     return false;
1768 }
1769
1770 static bool gen_global_function(ir_builder *ir, ir_value *global)
1771 {
1772     prog_section_function fun;
1773     ir_function          *irfun;
1774
1775     size_t i;
1776
1777     if (!global->isconst ||
1778         !global->constval.vfunc)
1779     {
1780         printf("Invalid state of function-global: not constant: %s\n", global->name);
1781         return false;
1782     }
1783
1784     irfun = global->constval.vfunc;
1785
1786     fun.name    = global->code.name;
1787     fun.file    = code_cachedstring(global->context.file);
1788     fun.profile = 0; /* always 0 */
1789     fun.nargs   = irfun->params_count;
1790
1791     for (i = 0;i < 8; ++i) {
1792         if (i >= fun.nargs)
1793             fun.argsize[i] = 0;
1794         else if (irfun->params[i] == TYPE_VECTOR)
1795             fun.argsize[i] = 3;
1796         else
1797             fun.argsize[i] = 1;
1798     }
1799
1800     fun.locals = irfun->locals_count;
1801     fun.firstlocal = code_globals_elements;
1802     for (i = 0; i < irfun->locals_count; ++i) {
1803         if (!ir_builder_gen_global(ir, irfun->locals[i]))
1804             return false;
1805     }
1806
1807     fun.entry      = code_statements_elements;
1808     if (!gen_function_code(irfun))
1809         return false;
1810
1811     return (code_functions_add(fun) >= 0);
1812 }
1813
1814 static bool ir_builder_gen_global(ir_builder *self, ir_value *global)
1815 {
1816     int32_t         *iptr;
1817     prog_section_def def;
1818
1819     def.type = 0;
1820     def.offset = code_globals_elements;
1821     def.name   = global->code.name       = code_genstring(global->name);
1822
1823     switch (global->vtype)
1824     {
1825     case TYPE_POINTER:
1826         def.type = 7;
1827         if (code_defs_add(def) < 0)
1828             return false;
1829         return gen_global_pointer(global);
1830     case TYPE_FIELD:
1831         def.type = 5;
1832         if (code_defs_add(def) < 0)
1833             return false;
1834         return gen_global_field(global);
1835     case TYPE_ENTITY:
1836         def.type = 4;
1837         if (code_defs_add(def) < 0)
1838             return false;
1839     case TYPE_FLOAT:
1840     {
1841         def.type = 2;
1842
1843         if (code_defs_add(def) < 0)
1844             return false;
1845
1846         if (global->isconst) {
1847             iptr = (int32_t*)&global->constval.vfloat;
1848             global->code.globaladdr = code_globals_add(*iptr);
1849         } else
1850             global->code.globaladdr = code_globals_add(0);
1851
1852         return global->code.globaladdr >= 0;
1853     }
1854     case TYPE_STRING:
1855     {
1856         def.type = 1;
1857         if (code_defs_add(def) < 0)
1858             return false;
1859         if (global->isconst)
1860             global->code.globaladdr = code_globals_add(code_cachedstring(global->constval.vstring));
1861         else
1862             global->code.globaladdr = code_globals_add(0);
1863         return global->code.globaladdr >= 0;
1864     }
1865     case TYPE_VECTOR:
1866     {
1867         def.type = 3;
1868
1869         if (code_defs_add(def) < 0)
1870             return false;
1871
1872         if (global->isconst) {
1873             iptr = (int32_t*)&global->constval.vvec;
1874             global->code.globaladdr = code_globals_add(iptr[0]);
1875             if (code_globals_add(iptr[1]) < 0 || code_globals_add(iptr[2]) < 0)
1876                 return false;
1877         } else {
1878             global->code.globaladdr = code_globals_add(0);
1879             if (code_globals_add(0) < 0 || code_globals_add(0) < 0)
1880                 return false;
1881         }
1882         return global->code.globaladdr >= 0;
1883     }
1884     case TYPE_FUNCTION:
1885         def.type = 6;
1886         if (code_defs_add(def) < 0)
1887             return false;
1888         return gen_global_function(self, global);
1889     default:
1890         /* refuse to create 'void' type or any other fancy business. */
1891         printf("Invalid type for global variable %s\n", global->name);
1892         return false;
1893     }
1894 }
1895
1896 bool ir_builder_generate(ir_builder *self, const char *filename)
1897 {
1898     size_t i;
1899
1900     code_init();
1901
1902     /* FIXME: generate TYPE_FUNCTION globals and link them
1903      * to their ir_function.
1904      */
1905
1906     for (i = 0; i < self->globals_count; ++i)
1907     {
1908         if (!ir_builder_gen_global(self, self->globals[i]))
1909             return false;
1910     }
1911
1912     code_write(filename);
1913     return false;
1914 }
1915
1916 /***********************************************************************
1917  *IR DEBUG Dump functions...
1918  */
1919
1920 #define IND_BUFSZ 1024
1921
1922 const char *qc_opname(int op)
1923 {
1924     if (op < 0) return "<INVALID>";
1925     if (op < ( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
1926         return asm_instr[op].m;
1927     switch (op) {
1928         case VINSTR_PHI:  return "PHI";
1929         case VINSTR_JUMP: return "JUMP";
1930         case VINSTR_COND: return "COND";
1931         default:          return "<UNK>";
1932     }
1933 }
1934
1935 void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
1936 {
1937         size_t i;
1938         char indent[IND_BUFSZ];
1939         indent[0] = '\t';
1940         indent[1] = 0;
1941
1942         oprintf("module %s\n", b->name);
1943         for (i = 0; i < b->globals_count; ++i)
1944         {
1945                 oprintf("global ");
1946                 if (b->globals[i]->isconst)
1947                         oprintf("%s = ", b->globals[i]->name);
1948                 ir_value_dump(b->globals[i], oprintf);
1949                 oprintf("\n");
1950         }
1951         for (i = 0; i < b->functions_count; ++i)
1952                 ir_function_dump(b->functions[i], indent, oprintf);
1953         oprintf("endmodule %s\n", b->name);
1954 }
1955
1956 void ir_function_dump(ir_function *f, char *ind,
1957                       int (*oprintf)(const char*, ...))
1958 {
1959         size_t i;
1960         oprintf("%sfunction %s\n", ind, f->name);
1961         strncat(ind, "\t", IND_BUFSZ);
1962         if (f->locals_count)
1963         {
1964                 oprintf("%s%i locals:\n", ind, (int)f->locals_count);
1965                 for (i = 0; i < f->locals_count; ++i) {
1966                         oprintf("%s\t", ind);
1967                         ir_value_dump(f->locals[i], oprintf);
1968                         oprintf("\n");
1969                 }
1970         }
1971         if (f->blocks_count)
1972         {
1973                 oprintf("%slife passes (check): %i\n", ind, (int)f->run_id);
1974                 for (i = 0; i < f->blocks_count; ++i) {
1975                     if (f->blocks[i]->run_id != f->run_id) {
1976                         oprintf("%slife pass check fail! %i != %i\n", ind, (int)f->blocks[i]->run_id, (int)f->run_id);
1977                     }
1978                         ir_block_dump(f->blocks[i], ind, oprintf);
1979                 }
1980
1981         }
1982         ind[strlen(ind)-1] = 0;
1983         oprintf("%sendfunction %s\n", ind, f->name);
1984 }
1985
1986 void ir_block_dump(ir_block* b, char *ind,
1987                    int (*oprintf)(const char*, ...))
1988 {
1989         size_t i;
1990         oprintf("%s:%s\n", ind, b->label);
1991         strncat(ind, "\t", IND_BUFSZ);
1992
1993         for (i = 0; i < b->instr_count; ++i)
1994                 ir_instr_dump(b->instr[i], ind, oprintf);
1995         ind[strlen(ind)-1] = 0;
1996 }
1997
1998 void dump_phi(ir_instr *in, char *ind,
1999               int (*oprintf)(const char*, ...))
2000 {
2001         size_t i;
2002         oprintf("%s <- phi ", in->_ops[0]->name);
2003         for (i = 0; i < in->phi_count; ++i)
2004         {
2005                 oprintf("([%s] : %s) ", in->phi[i].from->label,
2006                                         in->phi[i].value->name);
2007         }
2008         oprintf("\n");
2009 }
2010
2011 void ir_instr_dump(ir_instr *in, char *ind,
2012                        int (*oprintf)(const char*, ...))
2013 {
2014         size_t i;
2015         const char *comma = NULL;
2016
2017         oprintf("%s (%i) ", ind, (int)in->eid);
2018
2019         if (in->opcode == VINSTR_PHI) {
2020                 dump_phi(in, ind, oprintf);
2021                 return;
2022         }
2023
2024         strncat(ind, "\t", IND_BUFSZ);
2025
2026         if (in->_ops[0] && (in->_ops[1] || in->_ops[2])) {
2027                 ir_value_dump(in->_ops[0], oprintf);
2028                 if (in->_ops[1] || in->_ops[2])
2029                         oprintf(" <- ");
2030         }
2031         oprintf("%s\t", qc_opname(in->opcode));
2032         if (in->_ops[0] && !(in->_ops[1] || in->_ops[2])) {
2033                 ir_value_dump(in->_ops[0], oprintf);
2034                 comma = ",\t";
2035         }
2036         else
2037         {
2038                 for (i = 1; i != 3; ++i) {
2039                         if (in->_ops[i]) {
2040                                 if (comma)
2041                                         oprintf(comma);
2042                                 ir_value_dump(in->_ops[i], oprintf);
2043                                 comma = ",\t";
2044                         }
2045                 }
2046         }
2047         if (in->bops[0]) {
2048                 if (comma)
2049                         oprintf(comma);
2050                 oprintf("[%s]", in->bops[0]->label);
2051                 comma = ",\t";
2052         }
2053         if (in->bops[1])
2054                 oprintf("%s[%s]", comma, in->bops[1]->label);
2055         oprintf("\n");
2056         ind[strlen(ind)-1] = 0;
2057 }
2058
2059 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
2060 {
2061         if (v->isconst) {
2062                 switch (v->vtype) {
2063                         case TYPE_VOID:
2064                                 oprintf("(void)");
2065                                 break;
2066                         case TYPE_FLOAT:
2067                                 oprintf("%g", v->constval.vfloat);
2068                                 break;
2069                         case TYPE_VECTOR:
2070                                 oprintf("'%g %g %g'",
2071                                         v->constval.vvec.x,
2072                                         v->constval.vvec.y,
2073                                         v->constval.vvec.z);
2074                                 break;
2075                         case TYPE_ENTITY:
2076                                 oprintf("(entity)");
2077                                 break;
2078                         case TYPE_STRING:
2079                                 oprintf("\"%s\"", v->constval.vstring);
2080                                 break;
2081 #if 0
2082                         case TYPE_INTEGER:
2083                                 oprintf("%i", v->constval.vint);
2084                                 break;
2085 #endif
2086                         case TYPE_POINTER:
2087                                 oprintf("&%s",
2088                                         v->constval.vpointer->name);
2089                                 break;
2090                 }
2091         } else {
2092                 oprintf("%s", v->name);
2093         }
2094 }
2095
2096 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...))
2097 {
2098         size_t i;
2099         oprintf("Life of %s:\n", self->name);
2100         for (i = 0; i < self->life_count; ++i)
2101         {
2102                 oprintf(" + [%i, %i]\n", self->life[i].start, self->life[i].end);
2103         }
2104 }