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