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