ir.c

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