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