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  * Type sizes used at multiple points in the IR codegen
  30  */
  31
  32 size_t type_sizeof[TYPE_COUNT] = {
  33     1, /* TYPE_VOID     */
  34     1, /* TYPE_STRING   */
  35     1, /* TYPE_FLOAT    */
  36     3, /* TYPE_VECTOR   */
  37     1, /* TYPE_ENTITY   */
  38     1, /* TYPE_FIELD    */
  39     1, /* TYPE_FUNCTION */
  40     1, /* TYPE_POINTER  */
  41 #if 0
  42     1, /* TYPE_INTEGER  */
  43 #endif
  44     3, /* TYPE_VARIANT  */
  45 };
  46
  47 uint16_t type_store_instr[TYPE_COUNT] = {
  48     INSTR_STORE_F, /* should use I when having integer support */
  49     INSTR_STORE_S,
  50     INSTR_STORE_F,
  51     INSTR_STORE_V,
  52     INSTR_STORE_ENT,
  53     INSTR_STORE_FLD,
  54     INSTR_STORE_FNC,
  55     INSTR_STORE_ENT, /* should use I */
  56 #if 0
  57     INSTR_STORE_ENT, /* integer type */
  58 #endif
  59     INSTR_STORE_V, /* variant, should never be accessed */
  60 };
  61
  62 uint16_t type_storep_instr[TYPE_COUNT] = {
  63     INSTR_STOREP_F, /* should use I when having integer support */
  64     INSTR_STOREP_S,
  65     INSTR_STOREP_F,
  66     INSTR_STOREP_V,
  67     INSTR_STOREP_ENT,
  68     INSTR_STOREP_FLD,
  69     INSTR_STOREP_FNC,
  70     INSTR_STOREP_ENT, /* should use I */
  71 #if 0
  72     INSTR_STOREP_ENT, /* integer type */
  73 #endif
  74     INSTR_STOREP_V, /* variant, should never be accessed */
  75 };
  76
  77 MEM_VEC_FUNCTIONS(ir_value_vector, ir_value*, v)
  78
  79 /***********************************************************************
  80  *IR Builder
  81  */
  82
  83 ir_builder* ir_builder_new(const char *modulename)
  84 {
  85     ir_builder* self;
  86
  87     self = (ir_builder*)mem_a(sizeof(*self));
  88     if (!self)
  89         return NULL;
  90
  91     MEM_VECTOR_INIT(self, functions);
  92     MEM_VECTOR_INIT(self, globals);
  93     MEM_VECTOR_INIT(self, fields);
  94     self->name = NULL;
  95     if (!ir_builder_set_name(self, modulename)) {
  96         mem_d(self);
  97         return NULL;
  98     }
  99
 100     /* globals which always exist */
 101
 102     /* for now we give it a vector size */
 103     ir_builder_create_global(self, "OFS_RETURN", TYPE_VARIANT);
 104
 105     return self;
 106 }
 107
 108 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, globals)
 109 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, fields)
 110 MEM_VEC_FUNCTIONS(ir_builder, ir_function*, functions)
 111
 112 void ir_builder_delete(ir_builder* self)
 113 {
 114     size_t i;
 115     mem_d((void*)self->name);
 116     for (i = 0; i != self->functions_count; ++i) {
 117         ir_function_delete(self->functions[i]);
 118     }
 119     MEM_VECTOR_CLEAR(self, functions);
 120     for (i = 0; i != self->globals_count; ++i) {
 121         ir_value_delete(self->globals[i]);
 122     }
 123     MEM_VECTOR_CLEAR(self, fields);
 124     for (i = 0; i != self->fields_count; ++i) {
 125         ir_value_delete(self->fields[i]);
 126     }
 127     MEM_VECTOR_CLEAR(self, fields);
 128     mem_d(self);
 129 }
 130
 131 bool ir_builder_set_name(ir_builder *self, const char *name)
 132 {
 133     if (self->name)
 134         mem_d((void*)self->name);
 135     self->name = util_strdup(name);
 136     return !!self->name;
 137 }
 138
 139 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
 140 {
 141     size_t i;
 142     for (i = 0; i < self->functions_count; ++i) {
 143         if (!strcmp(name, self->functions[i]->name))
 144             return self->functions[i];
 145     }
 146     return NULL;
 147 }
 148
 149 ir_function* ir_builder_create_function(ir_builder *self, const char *name, int outtype)
 150 {
 151     ir_function *fn = ir_builder_get_function(self, name);
 152     if (fn) {
 153         return NULL;
 154     }
 155
 156     fn = ir_function_new(self, outtype);
 157     if (!ir_function_set_name(fn, name) ||
 158         !ir_builder_functions_add(self, fn) )
 159     {
 160         ir_function_delete(fn);
 161         return NULL;
 162     }
 163
 164     fn->value = ir_builder_create_global(self, fn->name, TYPE_FUNCTION);
 165     if (!fn->value) {
 166         ir_function_delete(fn);
 167         return NULL;
 168     }
 169
 170     fn->value->isconst = true;
 171     fn->value->outtype = outtype;
 172     fn->value->constval.vfunc = fn;
 173     fn->value->context = fn->context;
 174
 175     return fn;
 176 }
 177
 178 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
 179 {
 180     size_t i;
 181     for (i = 0; i < self->globals_count; ++i) {
 182         if (!strcmp(self->globals[i]->name, name))
 183             return self->globals[i];
 184     }
 185     return NULL;
 186 }
 187
 188 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
 189 {
 190     ir_value *ve = ir_builder_get_global(self, name);
 191     if (ve) {
 192         return NULL;
 193     }
 194
 195     ve = ir_value_var(name, store_global, vtype);
 196     if (!ir_builder_globals_add(self, ve)) {
 197         ir_value_delete(ve);
 198         return NULL;
 199     }
 200     return ve;
 201 }
 202
 203 ir_value* ir_builder_get_field(ir_builder *self, const char *name)
 204 {
 205     size_t i;
 206     for (i = 0; i < self->fields_count; ++i) {
 207         if (!strcmp(self->fields[i]->name, name))
 208             return self->fields[i];
 209     }
 210     return NULL;
 211 }
 212
 213
 214 ir_value* ir_builder_create_field(ir_builder *self, const char *name, int vtype)
 215 {
 216     ir_value *ve = ir_builder_get_field(self, name);
 217     if (ve) {
 218         return NULL;
 219     }
 220
 221     ve = ir_value_var(name, store_global, TYPE_FIELD);
 222     ve->fieldtype = vtype;
 223     if (!ir_builder_fields_add(self, ve)) {
 224         ir_value_delete(ve);
 225         return NULL;
 226     }
 227     return ve;
 228 }
 229
 230 /***********************************************************************
 231  *IR Function
 232  */
 233
 234 bool ir_function_naive_phi(ir_function*);
 235 void ir_function_enumerate(ir_function*);
 236 bool ir_function_calculate_liferanges(ir_function*);
 237 bool ir_function_allocate_locals(ir_function*);
 238
 239 ir_function* ir_function_new(ir_builder* owner, int outtype)
 240 {
 241     ir_function *self;
 242     self = (ir_function*)mem_a(sizeof(*self));
 243
 244     if (!self)
 245         return NULL;
 246
 247     self->name = NULL;
 248     if (!ir_function_set_name(self, "<@unnamed>")) {
 249         mem_d(self);
 250         return NULL;
 251     }
 252     self->owner = owner;
 253     self->context.file = "<@no context>";
 254     self->context.line = 0;
 255     self->outtype = outtype;
 256     self->value = NULL;
 257     self->builtin = 0;
 258     MEM_VECTOR_INIT(self, params);
 259     MEM_VECTOR_INIT(self, blocks);
 260     MEM_VECTOR_INIT(self, values);
 261     MEM_VECTOR_INIT(self, locals);
 262
 263     self->run_id = 0;
 264     return self;
 265 }
 266 MEM_VEC_FUNCTIONS(ir_function, ir_value*, values)
 267 MEM_VEC_FUNCTIONS(ir_function, ir_block*, blocks)
 268 MEM_VEC_FUNCTIONS(ir_function, ir_value*, locals)
 269 MEM_VEC_FUNCTIONS(ir_function, int,       params)
 270
 271 bool ir_function_set_name(ir_function *self, const char *name)
 272 {
 273     if (self->name)
 274         mem_d((void*)self->name);
 275     self->name = util_strdup(name);
 276     return !!self->name;
 277 }
 278
 279 void ir_function_delete(ir_function *self)
 280 {
 281     size_t i;
 282     mem_d((void*)self->name);
 283
 284     for (i = 0; i != self->blocks_count; ++i)
 285         ir_block_delete(self->blocks[i]);
 286     MEM_VECTOR_CLEAR(self, blocks);
 287
 288     MEM_VECTOR_CLEAR(self, params);
 289
 290     for (i = 0; i != self->values_count; ++i)
 291         ir_value_delete(self->values[i]);
 292     MEM_VECTOR_CLEAR(self, values);
 293
 294     for (i = 0; i != self->locals_count; ++i)
 295         ir_value_delete(self->locals[i]);
 296     MEM_VECTOR_CLEAR(self, locals);
 297
 298     /* self->value is deleted by the builder */
 299
 300     mem_d(self);
 301 }
 302
 303 bool GMQCC_WARN ir_function_collect_value(ir_function *self, ir_value *v)
 304 {
 305     return ir_function_values_add(self, v);
 306 }
 307
 308 ir_block* ir_function_create_block(ir_function *self, const char *label)
 309 {
 310     ir_block* bn = ir_block_new(self, label);
 311     memcpy(&bn->context, &self->context, sizeof(self->context));
 312     if (!ir_function_blocks_add(self, bn)) {
 313         ir_block_delete(bn);
 314         return NULL;
 315     }
 316     return bn;
 317 }
 318
 319 bool ir_function_finalize(ir_function *self)
 320 {
 321     if (self->builtin)
 322         return true;
 323
 324     if (!ir_function_naive_phi(self))
 325         return false;
 326
 327     ir_function_enumerate(self);
 328
 329     if (!ir_function_calculate_liferanges(self))
 330         return false;
 331
 332     if (!ir_function_allocate_locals(self))
 333         return false;
 334     return true;
 335 }
 336
 337 ir_value* ir_function_get_local(ir_function *self, const char *name)
 338 {
 339     size_t i;
 340     for (i = 0; i < self->locals_count; ++i) {
 341         if (!strcmp(self->locals[i]->name, name))
 342             return self->locals[i];
 343     }
 344     return NULL;
 345 }
 346
 347 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype, bool param)
 348 {
 349     ir_value *ve = ir_function_get_local(self, name);
 350     if (ve) {
 351         return NULL;
 352     }
 353
 354     if (param &&
 355         self->locals_count &&
 356         self->locals[self->locals_count-1]->store != store_param) {
 357         printf("cannot add parameters after adding locals\n");
 358         return NULL;
 359     }
 360
 361     ve = ir_value_var(name, (param ? store_param : store_local), vtype);
 362     if (!ir_function_locals_add(self, ve)) {
 363         ir_value_delete(ve);
 364         return NULL;
 365     }
 366     return ve;
 367 }
 368
 369 /***********************************************************************
 370  *IR Block
 371  */
 372
 373 ir_block* ir_block_new(ir_function* owner, const char *name)
 374 {
 375     ir_block *self;
 376     self = (ir_block*)mem_a(sizeof(*self));
 377     if (!self)
 378         return NULL;
 379
 380     memset(self, 0, sizeof(*self));
 381
 382     self->label = NULL;
 383     if (!ir_block_set_label(self, name)) {
 384         mem_d(self);
 385         return NULL;
 386     }
 387     self->owner = owner;
 388     self->context.file = "<@no context>";
 389     self->context.line = 0;
 390     self->final = false;
 391     MEM_VECTOR_INIT(self, instr);
 392     MEM_VECTOR_INIT(self, entries);
 393     MEM_VECTOR_INIT(self, exits);
 394
 395     self->eid = 0;
 396     self->is_return = false;
 397     self->run_id = 0;
 398     MEM_VECTOR_INIT(self, living);
 399
 400     self->generated = false;
 401
 402     return self;
 403 }
 404 MEM_VEC_FUNCTIONS(ir_block, ir_instr*, instr)
 405 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, entries)
 406 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, exits)
 407 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_value*, living)
 408
 409 void ir_block_delete(ir_block* self)
 410 {
 411     size_t i;
 412     mem_d(self->label);
 413     for (i = 0; i != self->instr_count; ++i)
 414         ir_instr_delete(self->instr[i]);
 415     MEM_VECTOR_CLEAR(self, instr);
 416     MEM_VECTOR_CLEAR(self, entries);
 417     MEM_VECTOR_CLEAR(self, exits);
 418     MEM_VECTOR_CLEAR(self, living);
 419     mem_d(self);
 420 }
 421
 422 bool ir_block_set_label(ir_block *self, const char *name)
 423 {
 424     if (self->label)
 425         mem_d((void*)self->label);
 426     self->label = util_strdup(name);
 427     return !!self->label;
 428 }
 429
 430 /***********************************************************************
 431  *IR Instructions
 432  */
 433
 434 ir_instr* ir_instr_new(ir_block* owner, int op)
 435 {
 436     ir_instr *self;
 437     self = (ir_instr*)mem_a(sizeof(*self));
 438     if (!self)
 439         return NULL;
 440
 441     self->owner = owner;
 442     self->context.file = "<@no context>";
 443     self->context.line = 0;
 444     self->opcode = op;
 445     self->_ops[0] = NULL;
 446     self->_ops[1] = NULL;
 447     self->_ops[2] = NULL;
 448     self->bops[0] = NULL;
 449     self->bops[1] = NULL;
 450     MEM_VECTOR_INIT(self, phi);
 451     MEM_VECTOR_INIT(self, params);
 452
 453     self->eid = 0;
 454     return self;
 455 }
 456 MEM_VEC_FUNCTIONS(ir_instr, ir_phi_entry_t, phi)
 457 MEM_VEC_FUNCTIONS(ir_instr, ir_value*, params)
 458
 459 void ir_instr_delete(ir_instr *self)
 460 {
 461     size_t i;
 462     /* The following calls can only delete from
 463      * vectors, we still want to delete this instruction
 464      * so ignore the return value. Since with the warn_unused_result attribute
 465      * gcc doesn't care about an explicit: (void)foo(); to ignore the result,
 466      * I have to improvise here and use if(foo());
 467      */
 468     for (i = 0; i < self->phi_count; ++i) {
 469         size_t idx;
 470         if (ir_value_writes_find(self->phi[i].value, self, &idx))
 471             if (ir_value_writes_remove(self->phi[i].value, idx)) GMQCC_SUPPRESS_EMPTY_BODY;
 472         if (ir_value_reads_find(self->phi[i].value, self, &idx))
 473             if (ir_value_reads_remove (self->phi[i].value, idx)) GMQCC_SUPPRESS_EMPTY_BODY;
 474     }
 475     MEM_VECTOR_CLEAR(self, phi);
 476     for (i = 0; i < self->params_count; ++i) {
 477         size_t idx;
 478         if (ir_value_writes_find(self->params[i], self, &idx))
 479             if (ir_value_writes_remove(self->params[i], idx)) GMQCC_SUPPRESS_EMPTY_BODY;
 480         if (ir_value_reads_find(self->params[i], self, &idx))
 481             if (ir_value_reads_remove (self->params[i], idx)) GMQCC_SUPPRESS_EMPTY_BODY;
 482     }
 483     MEM_VECTOR_CLEAR(self, params);
 484     if (ir_instr_op(self, 0, NULL, false)) GMQCC_SUPPRESS_EMPTY_BODY;
 485     if (ir_instr_op(self, 1, NULL, false)) GMQCC_SUPPRESS_EMPTY_BODY;
 486     if (ir_instr_op(self, 2, NULL, false)) GMQCC_SUPPRESS_EMPTY_BODY;
 487     mem_d(self);
 488 }
 489
 490 bool ir_instr_op(ir_instr *self, int op, ir_value *v, bool writing)
 491 {
 492     if (self->_ops[op]) {
 493         size_t idx;
 494         if (writing && ir_value_writes_find(self->_ops[op], self, &idx))
 495         {
 496             if (!ir_value_writes_remove(self->_ops[op], idx))
 497                 return false;
 498         }
 499         else if (ir_value_reads_find(self->_ops[op], self, &idx))
 500         {
 501             if (!ir_value_reads_remove(self->_ops[op], idx))
 502                 return false;
 503         }
 504     }
 505     if (v) {
 506         if (writing) {
 507             if (!ir_value_writes_add(v, self))
 508                 return false;
 509         } else {
 510             if (!ir_value_reads_add(v, self))
 511                 return false;
 512         }
 513     }
 514     self->_ops[op] = v;
 515     return true;
 516 }
 517
 518 /***********************************************************************
 519  *IR Value
 520  */
 521
 522 void ir_value_code_setaddr(ir_value *self, int32_t gaddr)
 523 {
 524     self->code.globaladdr = gaddr;
 525     if (self->members[0]) self->members[0]->code.globaladdr = gaddr;
 526     if (self->members[1]) self->members[1]->code.globaladdr = gaddr;
 527     if (self->members[2]) self->members[2]->code.globaladdr = gaddr;
 528 }
 529
 530 int32_t ir_value_code_addr(const ir_value *self)
 531 {
 532     return self->code.globaladdr + self->code.addroffset;
 533 }
 534
 535 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 536 {
 537     ir_value *self;
 538     self = (ir_value*)mem_a(sizeof(*self));
 539     self->vtype = vtype;
 540     self->fieldtype = TYPE_VOID;
 541     self->outtype = TYPE_VOID;
 542     self->store = storetype;
 543     MEM_VECTOR_INIT(self, reads);
 544     MEM_VECTOR_INIT(self, writes);
 545     self->isconst = false;
 546     self->context.file = "<@no context>";
 547     self->context.line = 0;
 548     self->name = NULL;
 549     ir_value_set_name(self, name);
 550
 551     memset(&self->constval, 0, sizeof(self->constval));
 552     memset(&self->code,     0, sizeof(self->code));
 553
 554     MEM_VECTOR_INIT(self, life);
 555     return self;
 556 }
 557
 558 ir_value* ir_value_vector_member(ir_value *self, unsigned int member)
 559 {
 560     ir_value *m;
 561     if (member >= 3)
 562         return NULL;
 563
 564     if (self->members[member])
 565         return self->members[member];
 566
 567     m = ir_value_var(self->name, self->store, TYPE_FLOAT);
 568     if (!m)
 569         return NULL;
 570     m->context = self->context;
 571
 572     self->members[member] = m;
 573     m->code.addroffset = member;
 574
 575     return m;
 576 }
 577
 578 MEM_VEC_FUNCTIONS(ir_value, ir_life_entry_t, life)
 579 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, reads)
 580 MEM_VEC_FUNCTIONS_ALL(ir_value, ir_instr*, writes)
 581
 582 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 583 {
 584     ir_value *v = ir_value_var(name, storetype, vtype);
 585     if (!v)
 586         return NULL;
 587     if (!ir_function_collect_value(owner, v))
 588     {
 589         ir_value_delete(v);
 590         return NULL;
 591     }
 592     return v;
 593 }
 594
 595 void ir_value_delete(ir_value* self)
 596 {
 597     size_t i;
 598     if (self->name)
 599         mem_d((void*)self->name);
 600     if (self->isconst)
 601     {
 602         if (self->vtype == TYPE_STRING)
 603             mem_d((void*)self->constval.vstring);
 604     }
 605     for (i = 0; i < 3; ++i) {
 606         if (self->members[i])
 607             ir_value_delete(self->members[i]);
 608     }
 609     MEM_VECTOR_CLEAR(self, reads);
 610     MEM_VECTOR_CLEAR(self, writes);
 611     MEM_VECTOR_CLEAR(self, life);
 612     mem_d(self);
 613 }
 614
 615 void ir_value_set_name(ir_value *self, const char *name)
 616 {
 617     if (self->name)
 618         mem_d((void*)self->name);
 619     self->name = util_strdup(name);
 620 }
 621
 622 bool ir_value_set_float(ir_value *self, float f)
 623 {
 624     if (self->vtype != TYPE_FLOAT)
 625         return false;
 626     self->constval.vfloat = f;
 627     self->isconst = true;
 628     return true;
 629 }
 630
 631 bool ir_value_set_func(ir_value *self, int f)
 632 {
 633     if (self->vtype != TYPE_FUNCTION)
 634         return false;
 635     self->constval.vint = f;
 636     self->isconst = true;
 637     return true;
 638 }
 639
 640 bool ir_value_set_vector(ir_value *self, vector v)
 641 {
 642     if (self->vtype != TYPE_VECTOR)
 643         return false;
 644     self->constval.vvec = v;
 645     self->isconst = true;
 646     return true;
 647 }
 648
 649 bool ir_value_set_string(ir_value *self, const char *str)
 650 {
 651     if (self->vtype != TYPE_STRING)
 652         return false;
 653     self->constval.vstring = util_strdup(str);
 654     self->isconst = true;
 655     return true;
 656 }
 657
 658 #if 0
 659 bool ir_value_set_int(ir_value *self, int i)
 660 {
 661     if (self->vtype != TYPE_INTEGER)
 662         return false;
 663     self->constval.vint = i;
 664     self->isconst = true;
 665     return true;
 666 }
 667 #endif
 668
 669 bool ir_value_lives(ir_value *self, size_t at)
 670 {
 671     size_t i;
 672     for (i = 0; i < self->life_count; ++i)
 673     {
 674         ir_life_entry_t *life = &self->life[i];
 675         if (life->start <= at && at <= life->end)
 676             return true;
 677         if (life->start > at) /* since it's ordered */
 678             return false;
 679     }
 680     return false;
 681 }
 682
 683 bool ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 684 {
 685     size_t k;
 686     if (!ir_value_life_add(self, e)) /* naive... */
 687         return false;
 688     for (k = self->life_count-1; k > idx; --k)
 689         self->life[k] = self->life[k-1];
 690     self->life[idx] = e;
 691     return true;
 692 }
 693
 694 bool ir_value_life_merge(ir_value *self, size_t s)
 695 {
 696     size_t i;
 697     ir_life_entry_t *life = NULL;
 698     ir_life_entry_t *before = NULL;
 699     ir_life_entry_t new_entry;
 700
 701     /* Find the first range >= s */
 702     for (i = 0; i < self->life_count; ++i)
 703     {
 704         before = life;
 705         life = &self->life[i];
 706         if (life->start > s)
 707             break;
 708     }
 709     /* nothing found? append */
 710     if (i == self->life_count) {
 711         ir_life_entry_t e;
 712         if (life && life->end+1 == s)
 713         {
 714             /* previous life range can be merged in */
 715             life->end++;
 716             return true;
 717         }
 718         if (life && life->end >= s)
 719             return false;
 720         e.start = e.end = s;
 721         if (!ir_value_life_add(self, e))
 722             return false; /* failing */
 723         return true;
 724     }
 725     /* found */
 726     if (before)
 727     {
 728         if (before->end + 1 == s &&
 729             life->start - 1 == s)
 730         {
 731             /* merge */
 732             before->end = life->end;
 733             if (!ir_value_life_remove(self, i))
 734                 return false; /* failing */
 735             return true;
 736         }
 737         if (before->end + 1 == s)
 738         {
 739             /* extend before */
 740             before->end++;
 741             return true;
 742         }
 743         /* already contained */
 744         if (before->end >= s)
 745             return false;
 746     }
 747     /* extend */
 748     if (life->start - 1 == s)
 749     {
 750         life->start--;
 751         return true;
 752     }
 753     /* insert a new entry */
 754     new_entry.start = new_entry.end = s;
 755     return ir_value_life_insert(self, i, new_entry);
 756 }
 757
 758 bool ir_value_life_merge_into(ir_value *self, const ir_value *other)
 759 {
 760     size_t i, myi;
 761
 762     if (!other->life_count)
 763         return true;
 764
 765     if (!self->life_count) {
 766         for (i = 0; i < other->life_count; ++i) {
 767             if (!ir_value_life_add(self, other->life[i]))
 768                 return false;
 769         }
 770         return true;
 771     }
 772
 773     myi = 0;
 774     for (i = 0; i < other->life_count; ++i)
 775     {
 776         const ir_life_entry_t *life = &other->life[i];
 777         while (true)
 778         {
 779             ir_life_entry_t *entry = &self->life[myi];
 780
 781             if (life->end+1 < entry->start)
 782             {
 783                 /* adding an interval before entry */
 784                 if (!ir_value_life_insert(self, myi, *life))
 785                     return false;
 786                 ++myi;
 787                 break;
 788             }
 789
 790             if (life->start <  entry->start &&
 791                 life->end   >= entry->start)
 792             {
 793                 /* starts earlier and overlaps */
 794                 entry->start = life->start;
 795             }
 796
 797             if (life->end     >  entry->end &&
 798                 life->start-1 <= entry->end)
 799             {
 800                 /* ends later and overlaps */
 801                 entry->end = life->end;
 802             }
 803
 804             /* see if our change combines it with the next ranges */
 805             while (myi+1 < self->life_count &&
 806                    entry->end+1 >= self->life[1+myi].start)
 807             {
 808                 /* overlaps with (myi+1) */
 809                 if (entry->end < self->life[1+myi].end)
 810                     entry->end = self->life[1+myi].end;
 811                 if (!ir_value_life_remove(self, myi+1))
 812                     return false;
 813                 entry = &self->life[myi];
 814             }
 815
 816             /* see if we're after the entry */
 817             if (life->start > entry->end)
 818             {
 819                 ++myi;
 820                 /* append if we're at the end */
 821                 if (myi >= self->life_count) {
 822                     if (!ir_value_life_add(self, *life))
 823                         return false;
 824                     break;
 825                 }
 826                 /* otherweise check the next range */
 827                 continue;
 828             }
 829             break;
 830         }
 831     }
 832     return true;
 833 }
 834
 835 bool ir_values_overlap(const ir_value *a, const ir_value *b)
 836 {
 837     /* For any life entry in A see if it overlaps with
 838      * any life entry in B.
 839      * Note that the life entries are orderes, so we can make a
 840      * more efficient algorithm there than naively translating the
 841      * statement above.
 842      */
 843
 844     ir_life_entry_t *la, *lb, *enda, *endb;
 845
 846     /* first of all, if either has no life range, they cannot clash */
 847     if (!a->life_count || !b->life_count)
 848         return false;
 849
 850     la = a->life;
 851     lb = b->life;
 852     enda = la + a->life_count;
 853     endb = lb + b->life_count;
 854     while (true)
 855     {
 856         /* check if the entries overlap, for that,
 857          * both must start before the other one ends.
 858          */
 859 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
 860         if (la->start <= lb->end &&
 861             lb->start <= la->end)
 862 #else
 863         if (la->start <  lb->end &&
 864             lb->start <  la->end)
 865 #endif
 866         {
 867             return true;
 868         }
 869
 870         /* entries are ordered
 871          * one entry is earlier than the other
 872          * that earlier entry will be moved forward
 873          */
 874         if (la->start < lb->start)
 875         {
 876             /* order: A B, move A forward
 877              * check if we hit the end with A
 878              */
 879             if (++la == enda)
 880                 break;
 881         }
 882         else if (lb->start < la->start)
 883         {
 884             /* order: B A, move B forward
 885              * check if we hit the end with B
 886              */
 887             if (++lb == endb)
 888                 break;
 889         }
 890     }
 891     return false;
 892 }
 893
 894 /***********************************************************************
 895  *IR main operations
 896  */
 897
 898 bool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 899 {
 900     if (target->store == store_value) {
 901         fprintf(stderr, "cannot store to an SSA value\n");
 902         fprintf(stderr, "trying to store: %s <- %s\n", target->name, what->name);
 903         return false;
 904     } else {
 905         ir_instr *in = ir_instr_new(self, op);
 906         if (!in)
 907             return false;
 908         if (!ir_instr_op(in, 0, target, true) ||
 909             !ir_instr_op(in, 1, what, false)  ||
 910             !ir_block_instr_add(self, in) )
 911         {
 912             return false;
 913         }
 914         return true;
 915     }
 916 }
 917
 918 bool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 919 {
 920     int op = 0;
 921     int vtype;
 922     if (target->vtype == TYPE_VARIANT)
 923         vtype = what->vtype;
 924     else
 925         vtype = target->vtype;
 926
 927 #if 0
 928     if      (vtype == TYPE_FLOAT   && what->vtype == TYPE_INTEGER)
 929         op = INSTR_CONV_ITOF;
 930     else if (vtype == TYPE_INTEGER && what->vtype == TYPE_FLOAT)
 931         op = INSTR_CONV_FTOI;
 932 #endif
 933         op = type_store_instr[vtype];
 934
 935     return ir_block_create_store_op(self, op, target, what);
 936 }
 937
 938 bool ir_block_create_storep(ir_block *self, ir_value *target, ir_value *what)
 939 {
 940     int op = 0;
 941     int vtype;
 942
 943     if (target->vtype != TYPE_POINTER)
 944         return false;
 945
 946     /* storing using pointer - target is a pointer, type must be
 947      * inferred from source
 948      */
 949     vtype = what->vtype;
 950
 951     op = type_storep_instr[vtype];
 952
 953     return ir_block_create_store_op(self, op, target, what);
 954 }
 955
 956 bool ir_block_create_return(ir_block *self, ir_value *v)
 957 {
 958     ir_instr *in;
 959     if (self->final) {
 960         fprintf(stderr, "block already ended (%s)\n", self->label);
 961         return false;
 962     }
 963     self->final = true;
 964     self->is_return = true;
 965     in = ir_instr_new(self, INSTR_RETURN);
 966     if (!in)
 967         return false;
 968
 969     if (!ir_instr_op(in, 0, v, false) ||
 970         !ir_block_instr_add(self, in) )
 971     {
 972         return false;
 973     }
 974     return true;
 975 }
 976
 977 bool ir_block_create_if(ir_block *self, ir_value *v,
 978                         ir_block *ontrue, ir_block *onfalse)
 979 {
 980     ir_instr *in;
 981     if (self->final) {
 982         fprintf(stderr, "block already ended (%s)\n", self->label);
 983         return false;
 984     }
 985     self->final = true;
 986     /*in = ir_instr_new(self, (v->vtype == TYPE_STRING ? INSTR_IF_S : INSTR_IF_F));*/
 987     in = ir_instr_new(self, VINSTR_COND);
 988     if (!in)
 989         return false;
 990
 991     if (!ir_instr_op(in, 0, v, false)) {
 992         ir_instr_delete(in);
 993         return false;
 994     }
 995
 996     in->bops[0] = ontrue;
 997     in->bops[1] = onfalse;
 998
 999     if (!ir_block_instr_add(self, in))
1000         return false;
1001
1002     if (!ir_block_exits_add(self, ontrue)    ||
1003         !ir_block_exits_add(self, onfalse)   ||
1004         !ir_block_entries_add(ontrue, self)  ||
1005         !ir_block_entries_add(onfalse, self) )
1006     {
1007         return false;
1008     }
1009     return true;
1010 }
1011
1012 bool ir_block_create_jump(ir_block *self, ir_block *to)
1013 {
1014     ir_instr *in;
1015     if (self->final) {
1016         fprintf(stderr, "block already ended (%s)\n", self->label);
1017         return false;
1018     }
1019     self->final = true;
1020     in = ir_instr_new(self, VINSTR_JUMP);
1021     if (!in)
1022         return false;
1023
1024     in->bops[0] = to;
1025     if (!ir_block_instr_add(self, in))
1026         return false;
1027
1028     if (!ir_block_exits_add(self, to) ||
1029         !ir_block_entries_add(to, self) )
1030     {
1031         return false;
1032     }
1033     return true;
1034 }
1035
1036 bool ir_block_create_goto(ir_block *self, ir_block *to)
1037 {
1038     ir_instr *in;
1039     if (self->final) {
1040         fprintf(stderr, "block already ended (%s)\n", self->label);
1041         return false;
1042     }
1043     self->final = true;
1044     in = ir_instr_new(self, INSTR_GOTO);
1045     if (!in)
1046         return false;
1047
1048     in->bops[0] = to;
1049     if (!ir_block_instr_add(self, in))
1050         return false;
1051
1052     if (!ir_block_exits_add(self, to) ||
1053         !ir_block_entries_add(to, self) )
1054     {
1055         return false;
1056     }
1057     return true;
1058 }
1059
1060 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
1061 {
1062     ir_value *out;
1063     ir_instr *in;
1064     in = ir_instr_new(self, VINSTR_PHI);
1065     if (!in)
1066         return NULL;
1067     out = ir_value_out(self->owner, label, store_value, ot);
1068     if (!out) {
1069         ir_instr_delete(in);
1070         return NULL;
1071     }
1072     if (!ir_instr_op(in, 0, out, true)) {
1073         ir_instr_delete(in);
1074         ir_value_delete(out);
1075         return NULL;
1076     }
1077     if (!ir_block_instr_add(self, in)) {
1078         ir_instr_delete(in);
1079         ir_value_delete(out);
1080         return NULL;
1081     }
1082     return in;
1083 }
1084
1085 ir_value* ir_phi_value(ir_instr *self)
1086 {
1087     return self->_ops[0];
1088 }
1089
1090 bool ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
1091 {
1092     ir_phi_entry_t pe;
1093
1094     if (!ir_block_entries_find(self->owner, b, NULL)) {
1095         /* Must not be possible to cause this, otherwise the AST
1096          * is doing something wrong.
1097          */
1098         fprintf(stderr, "Invalid entry block for PHI\n");
1099         abort();
1100     }
1101
1102     pe.value = v;
1103     pe.from = b;
1104     if (!ir_value_reads_add(v, self))
1105         return false;
1106     return ir_instr_phi_add(self, pe);
1107 }
1108
1109 /* call related code */
1110 ir_instr* ir_block_create_call(ir_block *self, const char *label, ir_value *func)
1111 {
1112     ir_value *out;
1113     ir_instr *in;
1114     in = ir_instr_new(self, INSTR_CALL0);
1115     if (!in)
1116         return NULL;
1117     out = ir_value_out(self->owner, label, store_return, func->outtype);
1118     if (!out) {
1119         ir_instr_delete(in);
1120         return NULL;
1121     }
1122     if (!ir_instr_op(in, 0, out, true) ||
1123         !ir_instr_op(in, 1, func, false) ||
1124         !ir_block_instr_add(self, in))
1125     {
1126         ir_instr_delete(in);
1127         ir_value_delete(out);
1128         return NULL;
1129     }
1130     return in;
1131 }
1132
1133 ir_value* ir_call_value(ir_instr *self)
1134 {
1135     return self->_ops[0];
1136 }
1137
1138 bool ir_call_param(ir_instr* self, ir_value *v)
1139 {
1140     if (!ir_instr_params_add(self, v))
1141         return false;
1142     if (!ir_value_reads_add(v, self)) {
1143         if (!ir_instr_params_remove(self, self->params_count-1))
1144             GMQCC_SUPPRESS_EMPTY_BODY;
1145         return false;
1146     }
1147     return true;
1148 }
1149
1150 /* binary op related code */
1151
1152 ir_value* ir_block_create_binop(ir_block *self,
1153                                 const char *label, int opcode,
1154                                 ir_value *left, ir_value *right)
1155 {
1156     int ot = TYPE_VOID;
1157     switch (opcode) {
1158         case INSTR_ADD_F:
1159         case INSTR_SUB_F:
1160         case INSTR_DIV_F:
1161         case INSTR_MUL_F:
1162         case INSTR_MUL_V:
1163         case INSTR_AND:
1164         case INSTR_OR:
1165 #if 0
1166         case INSTR_AND_I:
1167         case INSTR_AND_IF:
1168         case INSTR_AND_FI:
1169         case INSTR_OR_I:
1170         case INSTR_OR_IF:
1171         case INSTR_OR_FI:
1172 #endif
1173         case INSTR_BITAND:
1174         case INSTR_BITOR:
1175 #if 0
1176         case INSTR_SUB_S: /* -- offset of string as float */
1177         case INSTR_MUL_IF:
1178         case INSTR_MUL_FI:
1179         case INSTR_DIV_IF:
1180         case INSTR_DIV_FI:
1181         case INSTR_BITOR_IF:
1182         case INSTR_BITOR_FI:
1183         case INSTR_BITAND_FI:
1184         case INSTR_BITAND_IF:
1185         case INSTR_EQ_I:
1186         case INSTR_NE_I:
1187 #endif
1188             ot = TYPE_FLOAT;
1189             break;
1190 #if 0
1191         case INSTR_ADD_I:
1192         case INSTR_ADD_IF:
1193         case INSTR_ADD_FI:
1194         case INSTR_SUB_I:
1195         case INSTR_SUB_FI:
1196         case INSTR_SUB_IF:
1197         case INSTR_MUL_I:
1198         case INSTR_DIV_I:
1199         case INSTR_BITAND_I:
1200         case INSTR_BITOR_I:
1201         case INSTR_XOR_I:
1202         case INSTR_RSHIFT_I:
1203         case INSTR_LSHIFT_I:
1204             ot = TYPE_INTEGER;
1205             break;
1206 #endif
1207         case INSTR_ADD_V:
1208         case INSTR_SUB_V:
1209         case INSTR_MUL_VF:
1210         case INSTR_MUL_FV:
1211 #if 0
1212         case INSTR_DIV_VF:
1213         case INSTR_MUL_IV:
1214         case INSTR_MUL_VI:
1215 #endif
1216             ot = TYPE_VECTOR;
1217             break;
1218 #if 0
1219         case INSTR_ADD_SF:
1220             ot = TYPE_POINTER;
1221             break;
1222 #endif
1223         default:
1224             /* ranges: */
1225             /* boolean operations result in floats */
1226             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
1227                 ot = TYPE_FLOAT;
1228             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
1229                 ot = TYPE_FLOAT;
1230 #if 0
1231             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
1232                 ot = TYPE_FLOAT;
1233 #endif
1234             break;
1235     };
1236     if (ot == TYPE_VOID) {
1237         /* The AST or parser were supposed to check this! */
1238         return NULL;
1239     }
1240
1241     return ir_block_create_general_instr(self, label, opcode, left, right, ot);
1242 }
1243
1244 ir_value* ir_block_create_unary(ir_block *self,
1245                                 const char *label, int opcode,
1246                                 ir_value *operand)
1247 {
1248     int ot = TYPE_FLOAT;
1249     switch (opcode) {
1250         case INSTR_NOT_F:
1251         case INSTR_NOT_V:
1252         case INSTR_NOT_S:
1253         case INSTR_NOT_ENT:
1254         case INSTR_NOT_FNC:
1255 #if 0
1256         case INSTR_NOT_I:
1257 #endif
1258             ot = TYPE_FLOAT;
1259             break;
1260         /* QC doesn't have other unary operations. We expect extensions to fill
1261          * the above list, otherwise we assume out-type = in-type, eg for an
1262          * unary minus
1263          */
1264         default:
1265             ot = operand->vtype;
1266             break;
1267     };
1268     if (ot == TYPE_VOID) {
1269         /* The AST or parser were supposed to check this! */
1270         return NULL;
1271     }
1272
1273     /* let's use the general instruction creator and pass NULL for OPB */
1274     return ir_block_create_general_instr(self, label, opcode, operand, NULL, ot);
1275 }
1276
1277 ir_value* ir_block_create_general_instr(ir_block *self, const char *label,
1278                                         int op, ir_value *a, ir_value *b, int outype)
1279 {
1280     ir_instr *instr;
1281     ir_value *out;
1282
1283     out = ir_value_out(self->owner, label, store_value, outype);
1284     if (!out)
1285         return NULL;
1286
1287     instr = ir_instr_new(self, op);
1288     if (!instr) {
1289         ir_value_delete(out);
1290         return NULL;
1291     }
1292
1293     if (!ir_instr_op(instr, 0, out, true) ||
1294         !ir_instr_op(instr, 1, a, false) ||
1295         !ir_instr_op(instr, 2, b, false) )
1296     {
1297         goto on_error;
1298     }
1299
1300     if (!ir_block_instr_add(self, instr))
1301         goto on_error;
1302
1303     return out;
1304 on_error:
1305     ir_instr_delete(instr);
1306     ir_value_delete(out);
1307     return NULL;
1308 }
1309
1310 ir_value* ir_block_create_fieldaddress(ir_block *self, const char *label, ir_value *ent, ir_value *field)
1311 {
1312     ir_value *v;
1313
1314     /* Support for various pointer types todo if so desired */
1315     if (ent->vtype != TYPE_ENTITY)
1316         return NULL;
1317
1318     if (field->vtype != TYPE_FIELD)
1319         return NULL;
1320
1321     v = ir_block_create_general_instr(self, label, INSTR_ADDRESS, ent, field, TYPE_POINTER);
1322     v->fieldtype = field->fieldtype;
1323     return v;
1324 }
1325
1326 ir_value* ir_block_create_load_from_ent(ir_block *self, const char *label, ir_value *ent, ir_value *field, int outype)
1327 {
1328     int op;
1329     if (ent->vtype != TYPE_ENTITY)
1330         return NULL;
1331
1332     /* at some point we could redirect for TYPE_POINTER... but that could lead to carelessness */
1333     if (field->vtype != TYPE_FIELD)
1334         return NULL;
1335
1336     switch (outype)
1337     {
1338         case TYPE_FLOAT:   op = INSTR_LOAD_F;   break;
1339         case TYPE_VECTOR:  op = INSTR_LOAD_V;   break;
1340         case TYPE_STRING:  op = INSTR_LOAD_S;   break;
1341         case TYPE_FIELD:   op = INSTR_LOAD_FLD; break;
1342         case TYPE_ENTITY:  op = INSTR_LOAD_ENT; break;
1343 #if 0
1344         case TYPE_POINTER: op = INSTR_LOAD_I;   break;
1345         case TYPE_INTEGER: op = INSTR_LOAD_I;   break;
1346 #endif
1347         default:
1348             return NULL;
1349     }
1350
1351     return ir_block_create_general_instr(self, label, op, ent, field, outype);
1352 }
1353
1354 ir_value* ir_block_create_add(ir_block *self,
1355                               const char *label,
1356                               ir_value *left, ir_value *right)
1357 {
1358     int op = 0;
1359     int l = left->vtype;
1360     int r = right->vtype;
1361     if (l == r) {
1362         switch (l) {
1363             default:
1364                 return NULL;
1365             case TYPE_FLOAT:
1366                 op = INSTR_ADD_F;
1367                 break;
1368 #if 0
1369             case TYPE_INTEGER:
1370                 op = INSTR_ADD_I;
1371                 break;
1372 #endif
1373             case TYPE_VECTOR:
1374                 op = INSTR_ADD_V;
1375                 break;
1376         }
1377     } else {
1378 #if 0
1379         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1380             op = INSTR_ADD_FI;
1381         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1382             op = INSTR_ADD_IF;
1383         else
1384 #endif
1385             return NULL;
1386     }
1387     return ir_block_create_binop(self, label, op, left, right);
1388 }
1389
1390 ir_value* ir_block_create_sub(ir_block *self,
1391                               const char *label,
1392                               ir_value *left, ir_value *right)
1393 {
1394     int op = 0;
1395     int l = left->vtype;
1396     int r = right->vtype;
1397     if (l == r) {
1398
1399         switch (l) {
1400             default:
1401                 return NULL;
1402             case TYPE_FLOAT:
1403                 op = INSTR_SUB_F;
1404                 break;
1405 #if 0
1406             case TYPE_INTEGER:
1407                 op = INSTR_SUB_I;
1408                 break;
1409 #endif
1410             case TYPE_VECTOR:
1411                 op = INSTR_SUB_V;
1412                 break;
1413         }
1414     } else {
1415 #if 0
1416         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1417             op = INSTR_SUB_FI;
1418         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1419             op = INSTR_SUB_IF;
1420         else
1421 #endif
1422             return NULL;
1423     }
1424     return ir_block_create_binop(self, label, op, left, right);
1425 }
1426
1427 ir_value* ir_block_create_mul(ir_block *self,
1428                               const char *label,
1429                               ir_value *left, ir_value *right)
1430 {
1431     int op = 0;
1432     int l = left->vtype;
1433     int r = right->vtype;
1434     if (l == r) {
1435
1436         switch (l) {
1437             default:
1438                 return NULL;
1439             case TYPE_FLOAT:
1440                 op = INSTR_MUL_F;
1441                 break;
1442 #if 0
1443             case TYPE_INTEGER:
1444                 op = INSTR_MUL_I;
1445                 break;
1446 #endif
1447             case TYPE_VECTOR:
1448                 op = INSTR_MUL_V;
1449                 break;
1450         }
1451     } else {
1452         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1453             op = INSTR_MUL_VF;
1454         else if ( (l == TYPE_FLOAT && r == TYPE_VECTOR) )
1455             op = INSTR_MUL_FV;
1456 #if 0
1457         else if ( (l == TYPE_VECTOR && r == TYPE_INTEGER) )
1458             op = INSTR_MUL_VI;
1459         else if ( (l == TYPE_INTEGER && r == TYPE_VECTOR) )
1460             op = INSTR_MUL_IV;
1461         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1462             op = INSTR_MUL_FI;
1463         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1464             op = INSTR_MUL_IF;
1465 #endif
1466         else
1467             return NULL;
1468     }
1469     return ir_block_create_binop(self, label, op, left, right);
1470 }
1471
1472 ir_value* ir_block_create_div(ir_block *self,
1473                               const char *label,
1474                               ir_value *left, ir_value *right)
1475 {
1476     int op = 0;
1477     int l = left->vtype;
1478     int r = right->vtype;
1479     if (l == r) {
1480
1481         switch (l) {
1482             default:
1483                 return NULL;
1484             case TYPE_FLOAT:
1485                 op = INSTR_DIV_F;
1486                 break;
1487 #if 0
1488             case TYPE_INTEGER:
1489                 op = INSTR_DIV_I;
1490                 break;
1491 #endif
1492         }
1493     } else {
1494 #if 0
1495         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1496             op = INSTR_DIV_VF;
1497         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1498             op = INSTR_DIV_FI;
1499         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1500             op = INSTR_DIV_IF;
1501         else
1502 #endif
1503             return NULL;
1504     }
1505     return ir_block_create_binop(self, label, op, left, right);
1506 }
1507
1508 /* PHI resolving breaks the SSA, and must thus be the last
1509  * step before life-range calculation.
1510  */
1511
1512 static bool ir_block_naive_phi(ir_block *self);
1513 bool ir_function_naive_phi(ir_function *self)
1514 {
1515     size_t i;
1516
1517     for (i = 0; i < self->blocks_count; ++i)
1518     {
1519         if (!ir_block_naive_phi(self->blocks[i]))
1520             return false;
1521     }
1522     return true;
1523 }
1524
1525 static bool ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
1526 {
1527     ir_instr *instr;
1528     size_t i;
1529
1530     /* create a store */
1531     if (!ir_block_create_store(block, old, what))
1532         return false;
1533
1534     /* we now move it up */
1535     instr = block->instr[block->instr_count-1];
1536     for (i = block->instr_count; i > iid; --i)
1537         block->instr[i] = block->instr[i-1];
1538     block->instr[i] = instr;
1539
1540     return true;
1541 }
1542
1543 static bool ir_block_naive_phi(ir_block *self)
1544 {
1545     size_t i, p, w;
1546     /* FIXME: optionally, create_phi can add the phis
1547      * to a list so we don't need to loop through blocks
1548      * - anyway: "don't optimize YET"
1549      */
1550     for (i = 0; i < self->instr_count; ++i)
1551     {
1552         ir_instr *instr = self->instr[i];
1553         if (instr->opcode != VINSTR_PHI)
1554             continue;
1555
1556         if (!ir_block_instr_remove(self, i))
1557             return false;
1558         --i; /* NOTE: i+1 below */
1559
1560         for (p = 0; p < instr->phi_count; ++p)
1561         {
1562             ir_value *v = instr->phi[p].value;
1563             for (w = 0; w < v->writes_count; ++w) {
1564                 ir_value *old;
1565
1566                 if (!v->writes[w]->_ops[0])
1567                     continue;
1568
1569                 /* When the write was to a global, we have to emit a mov */
1570                 old = v->writes[w]->_ops[0];
1571
1572                 /* The original instruction now writes to the PHI target local */
1573                 if (v->writes[w]->_ops[0] == v)
1574                     v->writes[w]->_ops[0] = instr->_ops[0];
1575
1576                 if (old->store != store_value && old->store != store_local && old->store != store_param)
1577                 {
1578                     /* If it originally wrote to a global we need to store the value
1579                      * there as welli
1580                      */
1581                     if (!ir_naive_phi_emit_store(self, i+1, old, v))
1582                         return false;
1583                     if (i+1 < self->instr_count)
1584                         instr = self->instr[i+1];
1585                     else
1586                         instr = NULL;
1587                     /* In case I forget and access instr later, it'll be NULL
1588                      * when it's a problem, to make sure we crash, rather than accessing
1589                      * invalid data.
1590                      */
1591                 }
1592                 else
1593                 {
1594                     /* If it didn't, we can replace all reads by the phi target now. */
1595                     size_t r;
1596                     for (r = 0; r < old->reads_count; ++r)
1597                     {
1598                         size_t op;
1599                         ir_instr *ri = old->reads[r];
1600                         for (op = 0; op < ri->phi_count; ++op) {
1601                             if (ri->phi[op].value == old)
1602                                 ri->phi[op].value = v;
1603                         }
1604                         for (op = 0; op < 3; ++op) {
1605                             if (ri->_ops[op] == old)
1606                                 ri->_ops[op] = v;
1607                         }
1608                     }
1609                 }
1610             }
1611         }
1612         ir_instr_delete(instr);
1613     }
1614     return true;
1615 }
1616
1617 /***********************************************************************
1618  *IR Temp allocation code
1619  * Propagating value life ranges by walking through the function backwards
1620  * until no more changes are made.
1621  * In theory this should happen once more than once for every nested loop
1622  * level.
1623  * Though this implementation might run an additional time for if nests.
1624  */
1625
1626 typedef struct
1627 {
1628     ir_value* *v;
1629     size_t    v_count;
1630     size_t    v_alloc;
1631 } new_reads_t;
1632 MEM_VEC_FUNCTIONS_ALL(new_reads_t, ir_value*, v)
1633
1634 /* Enumerate instructions used by value's life-ranges
1635  */
1636 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1637 {
1638     size_t i;
1639     size_t eid = *_eid;
1640     for (i = 0; i < self->instr_count; ++i)
1641     {
1642         self->instr[i]->eid = eid++;
1643     }
1644     *_eid = eid;
1645 }
1646
1647 /* Enumerate blocks and instructions.
1648  * The block-enumeration is unordered!
1649  * We do not really use the block enumreation, however
1650  * the instruction enumeration is important for life-ranges.
1651  */
1652 void ir_function_enumerate(ir_function *self)
1653 {
1654     size_t i;
1655     size_t instruction_id = 0;
1656     for (i = 0; i < self->blocks_count; ++i)
1657     {
1658         self->blocks[i]->eid = i;
1659         self->blocks[i]->run_id = 0;
1660         ir_block_enumerate(self->blocks[i], &instruction_id);
1661     }
1662 }
1663
1664 static bool ir_block_life_propagate(ir_block *b, ir_block *prev, bool *changed);
1665 bool ir_function_calculate_liferanges(ir_function *self)
1666 {
1667     size_t i;
1668     bool changed;
1669
1670     do {
1671         self->run_id++;
1672         changed = false;
1673         for (i = 0; i != self->blocks_count; ++i)
1674         {
1675             if (self->blocks[i]->is_return)
1676             {
1677                 if (!ir_block_life_propagate(self->blocks[i], NULL, &changed))
1678                     return false;
1679             }
1680         }
1681     } while (changed);
1682     return true;
1683 }
1684
1685 /* Local-value allocator
1686  * After finishing creating the liferange of all values used in a function
1687  * we can allocate their global-positions.
1688  * This is the counterpart to register-allocation in register machines.
1689  */
1690 typedef struct {
1691     MEM_VECTOR_MAKE(ir_value*, locals);
1692     MEM_VECTOR_MAKE(size_t,    sizes);
1693     MEM_VECTOR_MAKE(size_t,    positions);
1694 } function_allocator;
1695 MEM_VEC_FUNCTIONS(function_allocator, ir_value*, locals)
1696 MEM_VEC_FUNCTIONS(function_allocator, size_t,    sizes)
1697 MEM_VEC_FUNCTIONS(function_allocator, size_t,    positions)
1698
1699 static bool function_allocator_alloc(function_allocator *alloc, const ir_value *var)
1700 {
1701     ir_value *slot;
1702     size_t vsize = type_sizeof[var->vtype];
1703
1704     slot = ir_value_var("reg", store_global, var->vtype);
1705     if (!slot)
1706         return false;
1707
1708     if (!ir_value_life_merge_into(slot, var))
1709         goto localerror;
1710
1711     if (!function_allocator_locals_add(alloc, slot))
1712         goto localerror;
1713
1714     if (!function_allocator_sizes_add(alloc, vsize))
1715         goto localerror;
1716
1717     return true;
1718
1719 localerror:
1720     ir_value_delete(slot);
1721     return false;
1722 }
1723
1724 bool ir_function_allocate_locals(ir_function *self)
1725 {
1726     size_t i, a;
1727     bool   retval = true;
1728     size_t pos;
1729
1730     ir_value *slot;
1731     const ir_value *v;
1732
1733     function_allocator alloc;
1734
1735     if (!self->locals_count)
1736         return true;
1737
1738     MEM_VECTOR_INIT(&alloc, locals);
1739     MEM_VECTOR_INIT(&alloc, sizes);
1740     MEM_VECTOR_INIT(&alloc, positions);
1741
1742     for (i = 0; i < self->locals_count; ++i)
1743     {
1744         if (!function_allocator_alloc(&alloc, self->locals[i]))
1745             goto error;
1746     }
1747
1748     /* Allocate a slot for any value that still exists */
1749     for (i = 0; i < self->values_count; ++i)
1750     {
1751         v = self->values[i];
1752
1753         if (!v->life_count)
1754             continue;
1755
1756         for (a = 0; a < alloc.locals_count; ++a)
1757         {
1758             slot = alloc.locals[a];
1759
1760             if (ir_values_overlap(v, slot))
1761                 continue;
1762
1763             if (!ir_value_life_merge_into(slot, v))
1764                 goto error;
1765
1766             /* adjust size for this slot */
1767             if (alloc.sizes[a] < type_sizeof[v->vtype])
1768                 alloc.sizes[a] = type_sizeof[v->vtype];
1769
1770             self->values[i]->code.local = a;
1771             break;
1772         }
1773         if (a >= alloc.locals_count) {
1774             self->values[i]->code.local = alloc.locals_count;
1775             if (!function_allocator_alloc(&alloc, v))
1776                 goto error;
1777         }
1778     }
1779
1780     /* Adjust slot positions based on sizes */
1781     if (!function_allocator_positions_add(&alloc, 0))
1782         goto error;
1783
1784     if (alloc.sizes_count)
1785         pos = alloc.positions[0] + alloc.sizes[0];
1786     else
1787         pos = 0;
1788     for (i = 1; i < alloc.sizes_count; ++i)
1789     {
1790         pos = alloc.positions[i-1] + alloc.sizes[i-1];
1791         if (!function_allocator_positions_add(&alloc, pos))
1792             goto error;
1793     }
1794
1795     self->allocated_locals = pos + alloc.sizes[alloc.sizes_count-1];
1796
1797     /* Take over the actual slot positions */
1798     for (i = 0; i < self->values_count; ++i)
1799         self->values[i]->code.local = alloc.positions[self->values[i]->code.local];
1800
1801     goto cleanup;
1802
1803 error:
1804     retval = false;
1805 cleanup:
1806     for (i = 0; i < alloc.locals_count; ++i)
1807         ir_value_delete(alloc.locals[i]);
1808     MEM_VECTOR_CLEAR(&alloc, locals);
1809     MEM_VECTOR_CLEAR(&alloc, sizes);
1810     MEM_VECTOR_CLEAR(&alloc, positions);
1811     return retval;
1812 }
1813
1814 /* Get information about which operand
1815  * is read from, or written to.
1816  */
1817 static void ir_op_read_write(int op, size_t *read, size_t *write)
1818 {
1819     switch (op)
1820     {
1821     case VINSTR_JUMP:
1822     case INSTR_GOTO:
1823         *write = 0;
1824         *read = 0;
1825         break;
1826     case INSTR_IF:
1827     case INSTR_IFNOT:
1828 #if 0
1829     case INSTR_IF_S:
1830     case INSTR_IFNOT_S:
1831 #endif
1832     case INSTR_RETURN:
1833     case VINSTR_COND:
1834         *write = 0;
1835         *read = 1;
1836         break;
1837     default:
1838         *write = 1;
1839         *read = 6;
1840         break;
1841     };
1842 }
1843
1844 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
1845 {
1846     size_t i;
1847     bool changed = false;
1848     bool tempbool;
1849     for (i = 0; i != self->living_count; ++i)
1850     {
1851         tempbool = ir_value_life_merge(self->living[i], eid);
1852         /* debug
1853         if (tempbool)
1854             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1855         */
1856         changed = changed || tempbool;
1857     }
1858     return changed;
1859 }
1860
1861 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
1862 {
1863     size_t i;
1864     /* values which have been read in a previous iteration are now
1865      * in the "living" array even if the previous block doesn't use them.
1866      * So we have to remove whatever does not exist in the previous block.
1867      * They will be re-added on-read, but the liferange merge won't cause
1868      * a change.
1869      */
1870     for (i = 0; i < self->living_count; ++i)
1871     {
1872         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1873             if (!ir_block_living_remove(self, i))
1874                 return false;
1875             --i;
1876         }
1877     }
1878
1879     /* Whatever the previous block still has in its living set
1880      * must now be added to ours as well.
1881      */
1882     for (i = 0; i < prev->living_count; ++i)
1883     {
1884         if (ir_block_living_find(self, prev->living[i], NULL))
1885             continue;
1886         if (!ir_block_living_add(self, prev->living[i]))
1887             return false;
1888         /*
1889         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1890         */
1891     }
1892     return true;
1893 }
1894
1895 static bool ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
1896 {
1897     ir_instr *instr;
1898     ir_value *value;
1899     bool  tempbool;
1900     size_t i, o, p;
1901     /* bitmasks which operands are read from or written to */
1902     size_t read, write;
1903 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1904     size_t rd;
1905     new_reads_t new_reads;
1906 #endif
1907     char dbg_ind[16] = { '#', '0' };
1908     (void)dbg_ind;
1909
1910 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1911     MEM_VECTOR_INIT(&new_reads, v);
1912 #endif
1913
1914     if (prev)
1915     {
1916         if (!ir_block_life_prop_previous(self, prev, changed))
1917             return false;
1918     }
1919
1920     i = self->instr_count;
1921     while (i)
1922     { --i;
1923         instr = self->instr[i];
1924
1925         /* PHI operands are always read operands */
1926         for (p = 0; p < instr->phi_count; ++p)
1927         {
1928             value = instr->phi[p].value;
1929 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1930             if (!ir_block_living_find(self, value, NULL) &&
1931                 !ir_block_living_add(self, value))
1932             {
1933                 goto on_error;
1934             }
1935 #else
1936             if (!new_reads_t_v_find(&new_reads, value, NULL))
1937             {
1938                 if (!new_reads_t_v_add(&new_reads, value))
1939                     goto on_error;
1940             }
1941 #endif
1942         }
1943
1944         /* See which operands are read and write operands */
1945         ir_op_read_write(instr->opcode, &read, &write);
1946
1947         /* Go through the 3 main operands */
1948         for (o = 0; o < 3; ++o)
1949         {
1950             if (!instr->_ops[o]) /* no such operand */
1951                 continue;
1952
1953             value = instr->_ops[o];
1954
1955             /* We only care about locals */
1956             /* we also calculate parameter liferanges so that locals
1957              * can take up parameter slots */
1958             if (value->store != store_value &&
1959                 value->store != store_local &&
1960                 value->store != store_param)
1961                 continue;
1962
1963             /* read operands */
1964             if (read & (1<<o))
1965             {
1966 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1967                 if (!ir_block_living_find(self, value, NULL) &&
1968                     !ir_block_living_add(self, value))
1969                 {
1970                     goto on_error;
1971                 }
1972 #else
1973                 /* fprintf(stderr, "read: %s\n", value->_name); */
1974                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1975                 {
1976                     if (!new_reads_t_v_add(&new_reads, value))
1977                         goto on_error;
1978                 }
1979 #endif
1980             }
1981
1982             /* write operands */
1983             /* When we write to a local, we consider it "dead" for the
1984              * remaining upper part of the function, since in SSA a value
1985              * can only be written once (== created)
1986              */
1987             if (write & (1<<o))
1988             {
1989                 size_t idx;
1990                 bool in_living = ir_block_living_find(self, value, &idx);
1991 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1992                 size_t readidx;
1993                 bool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1994                 if (!in_living && !in_reads)
1995 #else
1996                 if (!in_living)
1997 #endif
1998                 {
1999                     /* If the value isn't alive it hasn't been read before... */
2000                     /* TODO: See if the warning can be emitted during parsing or AST processing
2001                      * otherwise have warning printed here.
2002                      * IF printing a warning here: include filecontext_t,
2003                      * and make sure it's only printed once
2004                      * since this function is run multiple times.
2005                      */
2006                     /* For now: debug info: */
2007                     fprintf(stderr, "Value only written %s\n", value->name);
2008                     tempbool = ir_value_life_merge(value, instr->eid);
2009                     *changed = *changed || tempbool;
2010                     /*
2011                     ir_instr_dump(instr, dbg_ind, printf);
2012                     abort();
2013                     */
2014                 } else {
2015                     /* since 'living' won't contain it
2016                      * anymore, merge the value, since
2017                      * (A) doesn't.
2018                      */
2019                     tempbool = ir_value_life_merge(value, instr->eid);
2020                     /*
2021                     if (tempbool)
2022                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
2023                     */
2024                     *changed = *changed || tempbool;
2025                     /* Then remove */
2026 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
2027                     if (!ir_block_living_remove(self, idx))
2028                         goto on_error;
2029 #else
2030                     if (in_reads)
2031                     {
2032                         if (!new_reads_t_v_remove(&new_reads, readidx))
2033                             goto on_error;
2034                     }
2035 #endif
2036                 }
2037             }
2038         }
2039         /* (A) */
2040         tempbool = ir_block_living_add_instr(self, instr->eid);
2041         /*fprintf(stderr, "living added values\n");*/
2042         *changed = *changed || tempbool;
2043
2044 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
2045         /* new reads: */
2046         for (rd = 0; rd < new_reads.v_count; ++rd)
2047         {
2048             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
2049                 if (!ir_block_living_add(self, new_reads.v[rd]))
2050                     goto on_error;
2051             }
2052             if (!i && !self->entries_count) {
2053                 /* fix the top */
2054                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
2055             }
2056         }
2057         MEM_VECTOR_CLEAR(&new_reads, v);
2058 #endif
2059     }
2060
2061     if (self->run_id == self->owner->run_id)
2062         return true;
2063
2064     self->run_id = self->owner->run_id;
2065
2066     for (i = 0; i < self->entries_count; ++i)
2067     {
2068         ir_block *entry = self->entries[i];
2069         ir_block_life_propagate(entry, self, changed);
2070     }
2071
2072     return true;
2073 on_error:
2074 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
2075     MEM_VECTOR_CLEAR(&new_reads, v);
2076 #endif
2077     return false;
2078 }
2079
2080 /***********************************************************************
2081  *IR Code-Generation
2082  *
2083  * Since the IR has the convention of putting 'write' operands
2084  * at the beginning, we have to rotate the operands of instructions
2085  * properly in order to generate valid QCVM code.
2086  *
2087  * Having destinations at a fixed position is more convenient. In QC
2088  * this is *mostly* OPC,  but FTE adds at least 2 instructions which
2089  * read from from OPA,  and store to OPB rather than OPC.   Which is
2090  * partially the reason why the implementation of these instructions
2091  * in darkplaces has been delayed for so long.
2092  *
2093  * Breaking conventions is annoying...
2094  */
2095 static bool ir_builder_gen_global(ir_builder *self, ir_value *global);
2096
2097 static bool gen_global_field(ir_value *global)
2098 {
2099     if (global->isconst)
2100     {
2101         ir_value *fld = global->constval.vpointer;
2102         if (!fld) {
2103             printf("Invalid field constant with no field: %s\n", global->name);
2104             return false;
2105         }
2106
2107         /* Now, in this case, a relocation would be impossible to code
2108          * since it looks like this:
2109          * .vector v = origin;     <- parse error, wtf is 'origin'?
2110          * .vector origin;
2111          *
2112          * But we will need a general relocation support later anyway
2113          * for functions... might as well support that here.
2114          */
2115         if (!fld->code.globaladdr) {
2116             printf("FIXME: Relocation support\n");
2117             return false;
2118         }
2119
2120         /* copy the field's value */
2121         ir_value_code_setaddr(global, code_globals_add(code_globals_data[fld->code.globaladdr]));
2122     }
2123     else
2124     {
2125         ir_value_code_setaddr(global, code_globals_add(0));
2126     }
2127     if (global->code.globaladdr < 0)
2128         return false;
2129     return true;
2130 }
2131
2132 static bool gen_global_pointer(ir_value *global)
2133 {
2134     if (global->isconst)
2135     {
2136         ir_value *target = global->constval.vpointer;
2137         if (!target) {
2138             printf("Invalid pointer constant: %s\n", global->name);
2139             /* NULL pointers are pointing to the NULL constant, which also
2140              * sits at address 0, but still has an ir_value for itself.
2141              */
2142             return false;
2143         }
2144
2145         /* Here, relocations ARE possible - in fteqcc-enhanced-qc:
2146          * void() foo; <- proto
2147          * void() *fooptr = &foo;
2148          * void() foo = { code }
2149          */
2150         if (!target->code.globaladdr) {
2151             /* FIXME: Check for the constant nullptr ir_value!
2152              * because then code.globaladdr being 0 is valid.
2153              */
2154             printf("FIXME: Relocation support\n");
2155             return false;
2156         }
2157
2158         ir_value_code_setaddr(global, code_globals_add(target->code.globaladdr));
2159     }
2160     else
2161     {
2162         ir_value_code_setaddr(global, code_globals_add(0));
2163     }
2164     if (global->code.globaladdr < 0)
2165         return false;
2166     return true;
2167 }
2168
2169 static bool gen_blocks_recursive(ir_function *func, ir_block *block)
2170 {
2171     prog_section_statement stmt;
2172     ir_instr *instr;
2173     ir_block *target;
2174     ir_block *ontrue;
2175     ir_block *onfalse;
2176     size_t    stidx;
2177     size_t    i;
2178
2179 tailcall:
2180     block->generated = true;
2181     block->code_start = code_statements_elements;
2182     for (i = 0; i < block->instr_count; ++i)
2183     {
2184         instr = block->instr[i];
2185
2186         if (instr->opcode == VINSTR_PHI) {
2187             printf("cannot generate virtual instruction (phi)\n");
2188             return false;
2189         }
2190
2191         if (instr->opcode == VINSTR_JUMP) {
2192             target = instr->bops[0];
2193             /* for uncoditional jumps, if the target hasn't been generated
2194              * yet, we generate them right here.
2195              */
2196             if (!target->generated) {
2197                 block = target;
2198                 goto tailcall;
2199             }
2200
2201             /* otherwise we generate a jump instruction */
2202             stmt.opcode = INSTR_GOTO;
2203             stmt.o1.s1 = (target->code_start) - code_statements_elements;
2204             stmt.o2.s1 = 0;
2205             stmt.o3.s1 = 0;
2206             if (code_statements_add(stmt) < 0)
2207                 return false;
2208
2209             /* no further instructions can be in this block */
2210             return true;
2211         }
2212
2213         if (instr->opcode == VINSTR_COND) {
2214             ontrue  = instr->bops[0];
2215             onfalse = instr->bops[1];
2216             /* TODO: have the AST signal which block should
2217              * come first: eg. optimize IFs without ELSE...
2218              */
2219
2220             stmt.o1.u1 = ir_value_code_addr(instr->_ops[0]);
2221             stmt.o2.u1 = 0;
2222             stmt.o3.s1 = 0;
2223
2224             if (ontrue->generated) {
2225                 stmt.opcode = INSTR_IF;
2226                 stmt.o2.s1 = (ontrue->code_start-1) - code_statements_elements;
2227                 if (code_statements_add(stmt) < 0)
2228                     return false;
2229             }
2230             if (onfalse->generated) {
2231                 stmt.opcode = INSTR_IFNOT;
2232                 stmt.o2.s1 = (onfalse->code_start-1) - code_statements_elements;
2233                 if (code_statements_add(stmt) < 0)
2234                     return false;
2235             }
2236             if (!ontrue->generated) {
2237                 if (onfalse->generated) {
2238                     block = ontrue;
2239                     goto tailcall;
2240                 }
2241             }
2242             if (!onfalse->generated) {
2243                 if (ontrue->generated) {
2244                     block = onfalse;
2245                     goto tailcall;
2246                 }
2247             }
2248             /* neither ontrue nor onfalse exist */
2249             stmt.opcode = INSTR_IFNOT;
2250             stidx = code_statements_elements;
2251             if (code_statements_add(stmt) < 0)
2252                 return false;
2253             /* on false we jump, so add ontrue-path */
2254             if (!gen_blocks_recursive(func, ontrue))
2255                 return false;
2256             /* fixup the jump address */
2257             code_statements_data[stidx].o2.s1 = code_statements_elements - stidx;
2258             /* generate onfalse path */
2259             if (onfalse->generated) {
2260                 /* fixup the jump address */
2261                 code_statements_data[stidx].o2.s1 = (onfalse->code_start) - (stidx);
2262                 /* may have been generated in the previous recursive call */
2263                 stmt.opcode = INSTR_GOTO;
2264                 stmt.o1.s1 = (onfalse->code_start) - code_statements_elements;
2265                 stmt.o2.s1 = 0;
2266                 stmt.o3.s1 = 0;
2267                 return (code_statements_add(stmt) >= 0);
2268             }
2269             /* if not, generate now */
2270             block = onfalse;
2271             goto tailcall;
2272         }
2273
2274         if (instr->opcode >= INSTR_CALL0 && instr->opcode <= INSTR_CALL8) {
2275             /* Trivial call translation:
2276              * copy all params to OFS_PARM*
2277              * if the output's storetype is not store_return,
2278              * add append a STORE instruction!
2279              *
2280              * NOTES on how to do it better without much trouble:
2281              * -) The liferanges!
2282              *      Simply check the liferange of all parameters for
2283              *      other CALLs. For each param with no CALL in its
2284              *      liferange, we can store it in an OFS_PARM at
2285              *      generation already. This would even include later
2286              *      reuse.... probably... :)
2287              */
2288             size_t p;
2289             ir_value *retvalue;
2290
2291             for (p = 0; p < instr->params_count; ++p)
2292             {
2293                 ir_value *param = instr->params[p];
2294
2295                 stmt.opcode = INSTR_STORE_F;
2296                 stmt.o3.u1 = 0;
2297
2298                 stmt.opcode = type_store_instr[param->vtype];
2299                 stmt.o1.u1 = ir_value_code_addr(param);
2300                 stmt.o2.u1 = OFS_PARM0 + 3 * p;
2301                 if (code_statements_add(stmt) < 0)
2302                     return false;
2303             }
2304             stmt.opcode = INSTR_CALL0 + instr->params_count;
2305             if (stmt.opcode > INSTR_CALL8)
2306                 stmt.opcode = INSTR_CALL8;
2307             stmt.o1.u1 = ir_value_code_addr(instr->_ops[1]);
2308             stmt.o2.u1 = 0;
2309             stmt.o3.u1 = 0;
2310             if (code_statements_add(stmt) < 0)
2311                 return false;
2312
2313             retvalue = instr->_ops[0];
2314             if (retvalue && retvalue->store != store_return && retvalue->life_count)
2315             {
2316                 /* not to be kept in OFS_RETURN */
2317                 stmt.opcode = type_store_instr[retvalue->vtype];
2318                 stmt.o1.u1 = OFS_RETURN;
2319                 stmt.o2.u1 = ir_value_code_addr(retvalue);
2320                 stmt.o3.u1 = 0;
2321                 if (code_statements_add(stmt) < 0)
2322                     return false;
2323             }
2324             continue;
2325         }
2326
2327         if (instr->opcode == INSTR_STATE) {
2328             printf("TODO: state instruction\n");
2329             return false;
2330         }
2331
2332         stmt.opcode = instr->opcode;
2333         stmt.o1.u1 = 0;
2334         stmt.o2.u1 = 0;
2335         stmt.o3.u1 = 0;
2336
2337         /* This is the general order of operands */
2338         if (instr->_ops[0])
2339             stmt.o3.u1 = ir_value_code_addr(instr->_ops[0]);
2340
2341         if (instr->_ops[1])
2342             stmt.o1.u1 = ir_value_code_addr(instr->_ops[1]);
2343
2344         if (instr->_ops[2])
2345             stmt.o2.u1 = ir_value_code_addr(instr->_ops[2]);
2346
2347         if (stmt.opcode == INSTR_RETURN || stmt.opcode == INSTR_DONE)
2348         {
2349             stmt.o1.u1 = stmt.o3.u1;
2350             stmt.o3.u1 = 0;
2351         }
2352         else if (stmt.opcode >= INSTR_STORE_F &&
2353                  stmt.opcode <= INSTR_STORE_FNC)
2354         {
2355             /* 2-operand instructions with A -> B */
2356             stmt.o2.u1 = stmt.o3.u1;
2357             stmt.o3.u1 = 0;
2358         }
2359
2360         if (code_statements_add(stmt) < 0)
2361             return false;
2362     }
2363     return true;
2364 }
2365
2366 static bool gen_function_code(ir_function *self)
2367 {
2368     ir_block *block;
2369     prog_section_statement stmt;
2370
2371     /* Starting from entry point, we generate blocks "as they come"
2372      * for now. Dead blocks will not be translated obviously.
2373      */
2374     if (!self->blocks_count) {
2375         printf("Function '%s' declared without body.\n", self->name);
2376         return false;
2377     }
2378
2379     block = self->blocks[0];
2380     if (block->generated)
2381         return true;
2382
2383     if (!gen_blocks_recursive(self, block)) {
2384         printf("failed to generate blocks for '%s'\n", self->name);
2385         return false;
2386     }
2387
2388     /* otherwise code_write crashes since it debug-prints functions until AINSTR_END */
2389     stmt.opcode = AINSTR_END;
2390     stmt.o1.u1 = 0;
2391     stmt.o2.u1 = 0;
2392     stmt.o3.u1 = 0;
2393     if (code_statements_add(stmt) < 0)
2394         return false;
2395     return true;
2396 }
2397
2398 static bool gen_global_function(ir_builder *ir, ir_value *global)
2399 {
2400     prog_section_function fun;
2401     ir_function          *irfun;
2402
2403     size_t i;
2404     size_t local_var_end;
2405
2406     if (!global->isconst || (!global->constval.vfunc))
2407     {
2408         printf("Invalid state of function-global: not constant: %s\n", global->name);
2409         return false;
2410     }
2411
2412     irfun = global->constval.vfunc;
2413
2414     fun.name    = global->code.name;
2415     fun.file    = code_cachedstring(global->context.file);
2416     fun.profile = 0; /* always 0 */
2417     fun.nargs   = irfun->params_count;
2418
2419     for (i = 0;i < 8; ++i) {
2420         if (i >= fun.nargs)
2421             fun.argsize[i] = 0;
2422         else
2423             fun.argsize[i] = type_sizeof[irfun->params[i]];
2424     }
2425
2426     fun.firstlocal = code_globals_elements;
2427     fun.locals     = irfun->allocated_locals + irfun->locals_count;
2428
2429     local_var_end = 0;
2430     for (i = 0; i < irfun->locals_count; ++i) {
2431         if (!ir_builder_gen_global(ir, irfun->locals[i])) {
2432             printf("Failed to generate global %s\n", irfun->locals[i]->name);
2433             return false;
2434         }
2435     }
2436     if (irfun->locals_count) {
2437         ir_value *last = irfun->locals[irfun->locals_count-1];
2438         local_var_end = last->code.globaladdr;
2439         local_var_end += type_sizeof[last->vtype];
2440     }
2441     for (i = 0; i < irfun->values_count; ++i)
2442     {
2443         /* generate code.globaladdr for ssa values */
2444         ir_value *v = irfun->values[i];
2445         ir_value_code_setaddr(v, local_var_end + v->code.local);
2446     }
2447     for (i = 0; i < irfun->locals_count; ++i) {
2448         /* fill the locals with zeros */
2449         code_globals_add(0);
2450     }
2451
2452     if (irfun->builtin)
2453         fun.entry = irfun->builtin;
2454     else {
2455         fun.entry = code_statements_elements;
2456         if (!gen_function_code(irfun)) {
2457             printf("Failed to generate code for function %s\n", irfun->name);
2458             return false;
2459         }
2460     }
2461
2462     return (code_functions_add(fun) >= 0);
2463 }
2464
2465 static bool ir_builder_gen_global(ir_builder *self, ir_value *global)
2466 {
2467     size_t           i;
2468     int32_t         *iptr;
2469     prog_section_def def;
2470
2471     def.type   = global->vtype;
2472     def.offset = code_globals_elements;
2473     def.name   = global->code.name       = code_genstring(global->name);
2474
2475     switch (global->vtype)
2476     {
2477     case TYPE_POINTER:
2478         if (code_defs_add(def) < 0)
2479             return false;
2480         return gen_global_pointer(global);
2481     case TYPE_FIELD:
2482         if (code_defs_add(def) < 0)
2483             return false;
2484         return gen_global_field(global);
2485     case TYPE_ENTITY:
2486         /* fall through */
2487     case TYPE_FLOAT:
2488     {
2489         if (code_defs_add(def) < 0)
2490             return false;
2491
2492         if (global->isconst) {
2493             iptr = (int32_t*)&global->constval.vfloat;
2494             ir_value_code_setaddr(global, code_globals_add(*iptr));
2495         } else
2496             ir_value_code_setaddr(global, code_globals_add(0));
2497
2498         return global->code.globaladdr >= 0;
2499     }
2500     case TYPE_STRING:
2501     {
2502         if (code_defs_add(def) < 0)
2503             return false;
2504         if (global->isconst)
2505             ir_value_code_setaddr(global, code_globals_add(code_cachedstring(global->constval.vstring)));
2506         else
2507             ir_value_code_setaddr(global, code_globals_add(0));
2508         return global->code.globaladdr >= 0;
2509     }
2510     case TYPE_VECTOR:
2511     {
2512         size_t d;
2513         if (code_defs_add(def) < 0)
2514             return false;
2515
2516         if (global->isconst) {
2517             iptr = (int32_t*)&global->constval.vvec;
2518             ir_value_code_setaddr(global, code_globals_add(iptr[0]));
2519             if (global->code.globaladdr < 0)
2520                 return false;
2521             for (d = 1; d < type_sizeof[global->vtype]; ++d)
2522             {
2523                 if (code_globals_add(iptr[d]) < 0)
2524                     return false;
2525             }
2526         } else {
2527             ir_value_code_setaddr(global, code_globals_add(0));
2528             if (global->code.globaladdr < 0)
2529                 return false;
2530             for (d = 1; d < type_sizeof[global->vtype]; ++d)
2531             {
2532                 if (code_globals_add(0) < 0)
2533                     return false;
2534             }
2535         }
2536         return global->code.globaladdr >= 0;
2537     }
2538     case TYPE_FUNCTION:
2539         if (code_defs_add(def) < 0)
2540             return false;
2541         ir_value_code_setaddr(global, code_globals_elements);
2542         code_globals_add(code_functions_elements);
2543         return gen_global_function(self, global);
2544     case TYPE_VARIANT:
2545         /* assume biggest type */
2546             ir_value_code_setaddr(global, code_globals_add(0));
2547             for (i = 1; i < type_sizeof[TYPE_VARIANT]; ++i)
2548                 code_globals_add(0);
2549             return true;
2550     default:
2551         /* refuse to create 'void' type or any other fancy business. */
2552         printf("Invalid type for global variable %s\n", global->name);
2553         return false;
2554     }
2555 }
2556
2557 static bool ir_builder_gen_field(ir_builder *self, ir_value *field)
2558 {
2559     prog_section_def def;
2560     prog_section_field fld;
2561
2562     def.type   = field->vtype;
2563     def.offset = code_globals_elements;
2564     def.name   = field->code.name = code_genstring(field->name);
2565
2566     if (code_defs_add(def) < 0)
2567         return false;
2568
2569     fld.name = def.name;
2570     fld.offset = code_fields_elements;
2571     fld.type = field->fieldtype;
2572
2573     if (fld.type == TYPE_VOID) {
2574         printf("field is missing a type: %s - don't know its size\n", field->name);
2575         return false;
2576     }
2577
2578     if (code_fields_add(fld) < 0)
2579         return false;
2580
2581     if (!code_globals_add(code_alloc_field(type_sizeof[field->fieldtype])))
2582         return false;
2583
2584     ir_value_code_setaddr(field, code_globals_add(fld.offset));
2585     return field->code.globaladdr >= 0;
2586 }
2587
2588 bool ir_builder_generate(ir_builder *self, const char *filename)
2589 {
2590     size_t i;
2591
2592     code_init();
2593
2594     for (i = 0; i < self->fields_count; ++i)
2595     {
2596         if (!ir_builder_gen_field(self, self->fields[i])) {
2597             return false;
2598         }
2599     }
2600
2601     for (i = 0; i < self->globals_count; ++i)
2602     {
2603         if (!ir_builder_gen_global(self, self->globals[i])) {
2604             return false;
2605         }
2606     }
2607
2608     printf("writing '%s'...\n", filename);
2609     return code_write(filename);
2610 }
2611
2612 /***********************************************************************
2613  *IR DEBUG Dump functions...
2614  */
2615
2616 #define IND_BUFSZ 1024
2617
2618 const char *qc_opname(int op)
2619 {
2620     if (op < 0) return "<INVALID>";
2621     if (op < ( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
2622         return asm_instr[op].m;
2623     switch (op) {
2624         case VINSTR_PHI:  return "PHI";
2625         case VINSTR_JUMP: return "JUMP";
2626         case VINSTR_COND: return "COND";
2627         default:          return "<UNK>";
2628     }
2629 }
2630
2631 void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
2632 {
2633         size_t i;
2634         char indent[IND_BUFSZ];
2635         indent[0] = '\t';
2636         indent[1] = 0;
2637
2638         oprintf("module %s\n", b->name);
2639         for (i = 0; i < b->globals_count; ++i)
2640         {
2641                 oprintf("global ");
2642                 if (b->globals[i]->isconst)
2643                         oprintf("%s = ", b->globals[i]->name);
2644                 ir_value_dump(b->globals[i], oprintf);
2645                 oprintf("\n");
2646         }
2647         for (i = 0; i < b->functions_count; ++i)
2648                 ir_function_dump(b->functions[i], indent, oprintf);
2649         oprintf("endmodule %s\n", b->name);
2650 }
2651
2652 void ir_function_dump(ir_function *f, char *ind,
2653                       int (*oprintf)(const char*, ...))
2654 {
2655         size_t i;
2656         if (f->builtin != 0) {
2657             oprintf("%sfunction %s = builtin %i\n", ind, f->name, -f->builtin);
2658             return;
2659         }
2660         oprintf("%sfunction %s\n", ind, f->name);
2661         strncat(ind, "\t", IND_BUFSZ);
2662         if (f->locals_count)
2663         {
2664                 oprintf("%s%i locals:\n", ind, (int)f->locals_count);
2665                 for (i = 0; i < f->locals_count; ++i) {
2666                         oprintf("%s\t", ind);
2667                         ir_value_dump(f->locals[i], oprintf);
2668                         oprintf("\n");
2669                 }
2670         }
2671         if (f->blocks_count)
2672         {
2673                 oprintf("%slife passes (check): %i\n", ind, (int)f->run_id);
2674                 for (i = 0; i < f->blocks_count; ++i) {
2675                     if (f->blocks[i]->run_id != f->run_id) {
2676                         oprintf("%slife pass check fail! %i != %i\n", ind, (int)f->blocks[i]->run_id, (int)f->run_id);
2677                     }
2678                         ir_block_dump(f->blocks[i], ind, oprintf);
2679                 }
2680
2681         }
2682         ind[strlen(ind)-1] = 0;
2683         oprintf("%sendfunction %s\n", ind, f->name);
2684 }
2685
2686 void ir_block_dump(ir_block* b, char *ind,
2687                    int (*oprintf)(const char*, ...))
2688 {
2689         size_t i;
2690         oprintf("%s:%s\n", ind, b->label);
2691         strncat(ind, "\t", IND_BUFSZ);
2692
2693         for (i = 0; i < b->instr_count; ++i)
2694                 ir_instr_dump(b->instr[i], ind, oprintf);
2695         ind[strlen(ind)-1] = 0;
2696 }
2697
2698 void dump_phi(ir_instr *in, char *ind,
2699               int (*oprintf)(const char*, ...))
2700 {
2701         size_t i;
2702         oprintf("%s <- phi ", in->_ops[0]->name);
2703         for (i = 0; i < in->phi_count; ++i)
2704         {
2705                 oprintf("([%s] : %s) ", in->phi[i].from->label,
2706                                         in->phi[i].value->name);
2707         }
2708         oprintf("\n");
2709 }
2710
2711 void ir_instr_dump(ir_instr *in, char *ind,
2712                        int (*oprintf)(const char*, ...))
2713 {
2714         size_t i;
2715         const char *comma = NULL;
2716
2717         oprintf("%s (%i) ", ind, (int)in->eid);
2718
2719         if (in->opcode == VINSTR_PHI) {
2720                 dump_phi(in, ind, oprintf);
2721                 return;
2722         }
2723
2724         strncat(ind, "\t", IND_BUFSZ);
2725
2726         if (in->_ops[0] && (in->_ops[1] || in->_ops[2])) {
2727                 ir_value_dump(in->_ops[0], oprintf);
2728                 if (in->_ops[1] || in->_ops[2])
2729                         oprintf(" <- ");
2730         }
2731         oprintf("%s\t", qc_opname(in->opcode));
2732         if (in->_ops[0] && !(in->_ops[1] || in->_ops[2])) {
2733                 ir_value_dump(in->_ops[0], oprintf);
2734                 comma = ",\t";
2735         }
2736         else
2737         {
2738                 for (i = 1; i != 3; ++i) {
2739                         if (in->_ops[i]) {
2740                                 if (comma)
2741                                         oprintf(comma);
2742                                 ir_value_dump(in->_ops[i], oprintf);
2743                                 comma = ",\t";
2744                         }
2745                 }
2746         }
2747         if (in->bops[0]) {
2748                 if (comma)
2749                         oprintf(comma);
2750                 oprintf("[%s]", in->bops[0]->label);
2751                 comma = ",\t";
2752         }
2753         if (in->bops[1])
2754                 oprintf("%s[%s]", comma, in->bops[1]->label);
2755         oprintf("\n");
2756         ind[strlen(ind)-1] = 0;
2757 }
2758
2759 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
2760 {
2761         if (v->isconst) {
2762                 switch (v->vtype) {
2763                         case TYPE_VOID:
2764                                 oprintf("(void)");
2765                                 break;
2766                         case TYPE_FLOAT:
2767                                 oprintf("%g", v->constval.vfloat);
2768                                 break;
2769                         case TYPE_VECTOR:
2770                                 oprintf("'%g %g %g'",
2771                                         v->constval.vvec.x,
2772                                         v->constval.vvec.y,
2773                                         v->constval.vvec.z);
2774                                 break;
2775                         case TYPE_ENTITY:
2776                                 oprintf("(entity)");
2777                                 break;
2778                         case TYPE_STRING:
2779                                 oprintf("\"%s\"", v->constval.vstring);
2780                                 break;
2781 #if 0
2782                         case TYPE_INTEGER:
2783                                 oprintf("%i", v->constval.vint);
2784                                 break;
2785 #endif
2786                         case TYPE_POINTER:
2787                                 oprintf("&%s",
2788                                         v->constval.vpointer->name);
2789                                 break;
2790                 }
2791         } else {
2792                 oprintf("%s", v->name);
2793         }
2794 }
2795
2796 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...))
2797 {
2798         size_t i;
2799         oprintf("Life of %s:\n", self->name);
2800         for (i = 0; i < self->life_count; ++i)
2801         {
2802                 oprintf(" + [%i, %i]\n", self->life[i].start, self->life[i].end);
2803         }
2804 }