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