ir.c

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