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     if (!self->locals_count)
1667         return true;
1668
1669     MEM_VECTOR_INIT(&alloc, locals);
1670     MEM_VECTOR_INIT(&alloc, sizes);
1671     MEM_VECTOR_INIT(&alloc, positions);
1672
1673     for (i = 0; i < self->locals_count; ++i)
1674     {
1675         if (!function_allocator_alloc(&alloc, self->locals[i]))
1676             goto error;
1677     }
1678
1679     /* Allocate a slot for any value that still exists */
1680     for (i = 0; i < self->values_count; ++i)
1681     {
1682         v = self->values[i];
1683
1684         if (!v->life_count)
1685             continue;
1686
1687         for (a = 0; a < alloc.locals_count; ++a)
1688         {
1689             slot = alloc.locals[a];
1690
1691             if (ir_values_overlap(v, slot))
1692                 continue;
1693
1694             if (!ir_value_life_merge_into(slot, v))
1695                 goto error;
1696
1697             /* adjust size for this slot */
1698             if (alloc.sizes[a] < type_sizeof[v->vtype])
1699                 alloc.sizes[a] = type_sizeof[v->vtype];
1700
1701             self->values[i]->code.local = a;
1702             break;
1703         }
1704         if (a >= alloc.locals_count) {
1705             self->values[i]->code.local = alloc.locals_count;
1706             if (!function_allocator_alloc(&alloc, v))
1707                 goto error;
1708         }
1709     }
1710
1711     /* Adjust slot positions based on sizes */
1712     if (!function_allocator_positions_add(&alloc, 0))
1713         goto error;
1714
1715     if (alloc.sizes_count)
1716         pos = alloc.positions[0] + alloc.sizes[0];
1717     else
1718         pos = 0;
1719     for (i = 1; i < alloc.sizes_count; ++i)
1720     {
1721         pos = alloc.positions[i-1] + alloc.sizes[i-1];
1722         if (!function_allocator_positions_add(&alloc, pos))
1723             goto error;
1724     }
1725
1726     self->allocated_locals = pos + alloc.sizes[alloc.sizes_count-1];
1727
1728     /* Take over the actual slot positions */
1729     for (i = 0; i < self->values_count; ++i)
1730         self->values[i]->code.local = alloc.positions[self->values[i]->code.local];
1731
1732     goto cleanup;
1733
1734 error:
1735     retval = false;
1736 cleanup:
1737     for (i = 0; i < alloc.locals_count; ++i)
1738         ir_value_delete(alloc.locals[i]);
1739     MEM_VECTOR_CLEAR(&alloc, locals);
1740     MEM_VECTOR_CLEAR(&alloc, sizes);
1741     MEM_VECTOR_CLEAR(&alloc, positions);
1742     return retval;
1743 }
1744
1745 /* Get information about which operand
1746  * is read from, or written to.
1747  */
1748 static void ir_op_read_write(int op, size_t *read, size_t *write)
1749 {
1750     switch (op)
1751     {
1752     case VINSTR_JUMP:
1753     case INSTR_GOTO:
1754         *write = 0;
1755         *read = 0;
1756         break;
1757     case INSTR_IF:
1758     case INSTR_IFNOT:
1759 #if 0
1760     case INSTR_IF_S:
1761     case INSTR_IFNOT_S:
1762 #endif
1763     case INSTR_RETURN:
1764     case VINSTR_COND:
1765         *write = 0;
1766         *read = 1;
1767         break;
1768     default:
1769         *write = 1;
1770         *read = 6;
1771         break;
1772     };
1773 }
1774
1775 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
1776 {
1777     size_t i;
1778     bool changed = false;
1779     bool tempbool;
1780     for (i = 0; i != self->living_count; ++i)
1781     {
1782         tempbool = ir_value_life_merge(self->living[i], eid);
1783         /* debug
1784         if (tempbool)
1785             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1786         */
1787         changed = changed || tempbool;
1788     }
1789     return changed;
1790 }
1791
1792 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
1793 {
1794     size_t i;
1795     /* values which have been read in a previous iteration are now
1796      * in the "living" array even if the previous block doesn't use them.
1797      * So we have to remove whatever does not exist in the previous block.
1798      * They will be re-added on-read, but the liferange merge won't cause
1799      * a change.
1800      */
1801     for (i = 0; i < self->living_count; ++i)
1802     {
1803         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1804             if (!ir_block_living_remove(self, i))
1805                 return false;
1806             --i;
1807         }
1808     }
1809
1810     /* Whatever the previous block still has in its living set
1811      * must now be added to ours as well.
1812      */
1813     for (i = 0; i < prev->living_count; ++i)
1814     {
1815         if (ir_block_living_find(self, prev->living[i], NULL))
1816             continue;
1817         if (!ir_block_living_add(self, prev->living[i]))
1818             return false;
1819         /*
1820         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1821         */
1822     }
1823     return true;
1824 }
1825
1826 static bool ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
1827 {
1828     ir_instr *instr;
1829     ir_value *value;
1830     bool  tempbool;
1831     size_t i, o, p;
1832     /* bitmasks which operands are read from or written to */
1833     size_t read, write;
1834 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1835     size_t rd;
1836     new_reads_t new_reads;
1837 #endif
1838     char dbg_ind[16] = { '#', '0' };
1839     (void)dbg_ind;
1840
1841 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1842     MEM_VECTOR_INIT(&new_reads, v);
1843 #endif
1844
1845     if (prev)
1846     {
1847         if (!ir_block_life_prop_previous(self, prev, changed))
1848             return false;
1849     }
1850
1851     i = self->instr_count;
1852     while (i)
1853     { --i;
1854         instr = self->instr[i];
1855
1856         /* PHI operands are always read operands */
1857         for (p = 0; p < instr->phi_count; ++p)
1858         {
1859             value = instr->phi[p].value;
1860 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1861             if (!ir_block_living_find(self, value, NULL) &&
1862                 !ir_block_living_add(self, value))
1863             {
1864                 goto on_error;
1865             }
1866 #else
1867             if (!new_reads_t_v_find(&new_reads, value, NULL))
1868             {
1869                 if (!new_reads_t_v_add(&new_reads, value))
1870                     goto on_error;
1871             }
1872 #endif
1873         }
1874
1875         /* See which operands are read and write operands */
1876         ir_op_read_write(instr->opcode, &read, &write);
1877
1878         /* Go through the 3 main operands */
1879         for (o = 0; o < 3; ++o)
1880         {
1881             if (!instr->_ops[o]) /* no such operand */
1882                 continue;
1883
1884             value = instr->_ops[o];
1885
1886             /* We only care about locals */
1887             if (value->store != store_value &&
1888                 value->store != store_local)
1889                 continue;
1890
1891             /* read operands */
1892             if (read & (1<<o))
1893             {
1894 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1895                 if (!ir_block_living_find(self, value, NULL) &&
1896                     !ir_block_living_add(self, value))
1897                 {
1898                     goto on_error;
1899                 }
1900 #else
1901                 /* fprintf(stderr, "read: %s\n", value->_name); */
1902                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1903                 {
1904                     if (!new_reads_t_v_add(&new_reads, value))
1905                         goto on_error;
1906                 }
1907 #endif
1908             }
1909
1910             /* write operands */
1911             /* When we write to a local, we consider it "dead" for the
1912              * remaining upper part of the function, since in SSA a value
1913              * can only be written once (== created)
1914              */
1915             if (write & (1<<o))
1916             {
1917                 size_t idx;
1918                 bool in_living = ir_block_living_find(self, value, &idx);
1919 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1920                 size_t readidx;
1921                 bool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1922                 if (!in_living && !in_reads)
1923 #else
1924                 if (!in_living)
1925 #endif
1926                 {
1927                     /* If the value isn't alive it hasn't been read before... */
1928                     /* TODO: See if the warning can be emitted during parsing or AST processing
1929                      * otherwise have warning printed here.
1930                      * IF printing a warning here: include filecontext_t,
1931                      * and make sure it's only printed once
1932                      * since this function is run multiple times.
1933                      */
1934                     /* For now: debug info: */
1935                     fprintf(stderr, "Value only written %s\n", value->name);
1936                     tempbool = ir_value_life_merge(value, instr->eid);
1937                     *changed = *changed || tempbool;
1938                     /*
1939                     ir_instr_dump(instr, dbg_ind, printf);
1940                     abort();
1941                     */
1942                 } else {
1943                     /* since 'living' won't contain it
1944                      * anymore, merge the value, since
1945                      * (A) doesn't.
1946                      */
1947                     tempbool = ir_value_life_merge(value, instr->eid);
1948                     /*
1949                     if (tempbool)
1950                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
1951                     */
1952                     *changed = *changed || tempbool;
1953                     /* Then remove */
1954 #if ! defined(LIFE_RANGE_WITHOUT_LAST_READ)
1955                     if (!ir_block_living_remove(self, idx))
1956                         goto on_error;
1957 #else
1958                     if (in_reads)
1959                     {
1960                         if (!new_reads_t_v_remove(&new_reads, readidx))
1961                             goto on_error;
1962                     }
1963 #endif
1964                 }
1965             }
1966         }
1967         /* (A) */
1968         tempbool = ir_block_living_add_instr(self, instr->eid);
1969         /*fprintf(stderr, "living added values\n");*/
1970         *changed = *changed || tempbool;
1971
1972 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
1973         /* new reads: */
1974         for (rd = 0; rd < new_reads.v_count; ++rd)
1975         {
1976             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
1977                 if (!ir_block_living_add(self, new_reads.v[rd]))
1978                     goto on_error;
1979             }
1980             if (!i && !self->entries_count) {
1981                 /* fix the top */
1982                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
1983             }
1984         }
1985         MEM_VECTOR_CLEAR(&new_reads, v);
1986 #endif
1987     }
1988
1989     if (self->run_id == self->owner->run_id)
1990         return true;
1991
1992     self->run_id = self->owner->run_id;
1993
1994     for (i = 0; i < self->entries_count; ++i)
1995     {
1996         ir_block *entry = self->entries[i];
1997         ir_block_life_propagate(entry, self, changed);
1998     }
1999
2000     return true;
2001 on_error:
2002 #if defined(LIFE_RANGE_WITHOUT_LAST_READ)
2003     MEM_VECTOR_CLEAR(&new_reads, v);
2004 #endif
2005     return false;
2006 }
2007
2008 /***********************************************************************
2009  *IR Code-Generation
2010  *
2011  * Since the IR has the convention of putting 'write' operands
2012  * at the beginning, we have to rotate the operands of instructions
2013  * properly in order to generate valid QCVM code.
2014  *
2015  * Having destinations at a fixed position is more convenient. In QC
2016  * this is *mostly* OPC,  but FTE adds at least 2 instructions which
2017  * read from from OPA,  and store to OPB rather than OPC.   Which is
2018  * partially the reason why the implementation of these instructions
2019  * in darkplaces has been delayed for so long.
2020  *
2021  * Breaking conventions is annoying...
2022  */
2023 static bool ir_builder_gen_global(ir_builder *self, ir_value *global);
2024
2025 static bool gen_global_field(ir_value *global)
2026 {
2027     if (global->isconst)
2028     {
2029         ir_value *fld = global->constval.vpointer;
2030         if (!fld) {
2031             printf("Invalid field constant with no field: %s\n", global->name);
2032             return false;
2033         }
2034
2035         /* Now, in this case, a relocation would be impossible to code
2036          * since it looks like this:
2037          * .vector v = origin;     <- parse error, wtf is 'origin'?
2038          * .vector origin;
2039          *
2040          * But we will need a general relocation support later anyway
2041          * for functions... might as well support that here.
2042          */
2043         if (!fld->code.globaladdr) {
2044             printf("FIXME: Relocation support\n");
2045             return false;
2046         }
2047
2048         /* copy the field's value */
2049         global->code.globaladdr = code_globals_add(code_globals_data[fld->code.globaladdr]);
2050     }
2051     else
2052     {
2053         prog_section_field fld;
2054
2055         fld.name = global->code.name;
2056         fld.offset = code_fields_elements;
2057         fld.type = global->fieldtype;
2058
2059         if (fld.type == TYPE_VOID) {
2060             printf("Field is missing a type: %s\n", global->name);
2061             return false;
2062         }
2063
2064         if (code_fields_add(fld) < 0)
2065             return false;
2066
2067         global->code.globaladdr = code_globals_add(fld.offset);
2068     }
2069     if (global->code.globaladdr < 0)
2070         return false;
2071     return true;
2072 }
2073
2074 static bool gen_global_pointer(ir_value *global)
2075 {
2076     if (global->isconst)
2077     {
2078         ir_value *target = global->constval.vpointer;
2079         if (!target) {
2080             printf("Invalid pointer constant: %s\n", global->name);
2081             /* NULL pointers are pointing to the NULL constant, which also
2082              * sits at address 0, but still has an ir_value for itself.
2083              */
2084             return false;
2085         }
2086
2087         /* Here, relocations ARE possible - in fteqcc-enhanced-qc:
2088          * void() foo; <- proto
2089          * void() *fooptr = &foo;
2090          * void() foo = { code }
2091          */
2092         if (!target->code.globaladdr) {
2093             /* FIXME: Check for the constant nullptr ir_value!
2094              * because then code.globaladdr being 0 is valid.
2095              */
2096             printf("FIXME: Relocation support\n");
2097             return false;
2098         }
2099
2100         global->code.globaladdr = code_globals_add(target->code.globaladdr);
2101     }
2102     else
2103     {
2104         global->code.globaladdr = code_globals_add(0);
2105     }
2106     if (global->code.globaladdr < 0)
2107         return false;
2108     return true;
2109 }
2110
2111 static bool gen_blocks_recursive(ir_function *func, ir_block *block)
2112 {
2113     prog_section_statement stmt;
2114     ir_instr *instr;
2115     ir_block *target;
2116     ir_block *ontrue;
2117     ir_block *onfalse;
2118     size_t    stidx;
2119     size_t    i;
2120
2121 tailcall:
2122     block->generated = true;
2123     block->code_start = code_statements_elements;
2124     for (i = 0; i < block->instr_count; ++i)
2125     {
2126         instr = block->instr[i];
2127
2128         if (instr->opcode == VINSTR_PHI) {
2129             printf("cannot generate virtual instruction (phi)\n");
2130             return false;
2131         }
2132
2133         if (instr->opcode == VINSTR_JUMP) {
2134             target = instr->bops[0];
2135             /* for uncoditional jumps, if the target hasn't been generated
2136              * yet, we generate them right here.
2137              */
2138             if (!target->generated) {
2139                 block = target;
2140                 goto tailcall;
2141             }
2142
2143             /* otherwise we generate a jump instruction */
2144             stmt.opcode = INSTR_GOTO;
2145             stmt.o1.s1 = (target->code_start) - code_statements_elements;
2146             stmt.o2.s1 = 0;
2147             stmt.o3.s1 = 0;
2148             if (code_statements_add(stmt) < 0)
2149                 return false;
2150
2151             /* no further instructions can be in this block */
2152             return true;
2153         }
2154
2155         if (instr->opcode == VINSTR_COND) {
2156             ontrue  = instr->bops[0];
2157             onfalse = instr->bops[1];
2158             /* TODO: have the AST signal which block should
2159              * come first: eg. optimize IFs without ELSE...
2160              */
2161
2162             stmt.o1.u1 = instr->_ops[0]->code.globaladdr;
2163             stmt.o2.u1 = 0;
2164             stmt.o3.s1 = 0;
2165
2166             if (ontrue->generated) {
2167                 stmt.opcode = INSTR_IF;
2168                 stmt.o2.s1 = (ontrue->code_start-1) - code_statements_elements;
2169                 if (code_statements_add(stmt) < 0)
2170                     return false;
2171             }
2172             if (onfalse->generated) {
2173                 stmt.opcode = INSTR_IFNOT;
2174                 stmt.o2.s1 = (onfalse->code_start-1) - code_statements_elements;
2175                 if (code_statements_add(stmt) < 0)
2176                     return false;
2177             }
2178             if (!ontrue->generated) {
2179                 if (onfalse->generated) {
2180                     block = ontrue;
2181                     goto tailcall;
2182                 }
2183             }
2184             if (!onfalse->generated) {
2185                 if (ontrue->generated) {
2186                     block = onfalse;
2187                     goto tailcall;
2188                 }
2189             }
2190             /* neither ontrue nor onfalse exist */
2191             stmt.opcode = INSTR_IFNOT;
2192             stidx = code_statements_elements;
2193             if (code_statements_add(stmt) < 0)
2194                 return false;
2195             /* on false we jump, so add ontrue-path */
2196             if (!gen_blocks_recursive(func, ontrue))
2197                 return false;
2198             /* fixup the jump address */
2199             code_statements_data[stidx].o2.s1 = code_statements_elements - stidx;
2200             /* generate onfalse path */
2201             if (onfalse->generated) {
2202                 /* fixup the jump address */
2203                 code_statements_data[stidx].o2.s1 = (onfalse->code_start) - (stidx);
2204                 /* may have been generated in the previous recursive call */
2205                 stmt.opcode = INSTR_GOTO;
2206                 stmt.o1.s1 = (onfalse->code_start) - code_statements_elements;
2207                 stmt.o2.s1 = 0;
2208                 stmt.o3.s1 = 0;
2209                 return (code_statements_add(stmt) >= 0);
2210             }
2211             /* if not, generate now */
2212             block = onfalse;
2213             goto tailcall;
2214         }
2215
2216         if (instr->opcode >= INSTR_CALL0 && instr->opcode <= INSTR_CALL8) {
2217             /* Trivial call translation:
2218              * copy all params to OFS_PARM*
2219              * if the output's storetype is not store_return,
2220              * add append a STORE instruction!
2221              *
2222              * NOTES on how to do it better without much trouble:
2223              * -) The liferanges!
2224              *      Simply check the liferange of all parameters for
2225              *      other CALLs. For each param with no CALL in its
2226              *      liferange, we can store it in an OFS_PARM at
2227              *      generation already. This would even include later
2228              *      reuse.... probably... :)
2229              */
2230             size_t p;
2231             ir_value *retvalue;
2232
2233             for (p = 0; p < instr->params_count; ++p)
2234             {
2235                 ir_value *param = instr->params[p];
2236
2237                 stmt.opcode = INSTR_STORE_F;
2238                 stmt.o3.u1 = 0;
2239
2240                 stmt.opcode = type_store_instr[param->vtype];
2241                 stmt.o1.u1 = param->code.globaladdr;
2242                 stmt.o2.u1 = OFS_PARM0 + 3 * p;
2243                 if (code_statements_add(stmt) < 0)
2244                     return false;
2245             }
2246             stmt.opcode = INSTR_CALL0 + instr->params_count;
2247             if (stmt.opcode > INSTR_CALL8)
2248                 stmt.opcode = INSTR_CALL8;
2249             stmt.o1.u1 = instr->_ops[1]->code.globaladdr;
2250             stmt.o2.u1 = 0;
2251             stmt.o3.u1 = 0;
2252             if (code_statements_add(stmt) < 0)
2253                 return false;
2254
2255             retvalue = instr->_ops[0];
2256             if (retvalue && retvalue->store != store_return && retvalue->life_count)
2257             {
2258                 /* not to be kept in OFS_RETURN */
2259                 stmt.opcode = type_store_instr[retvalue->vtype];
2260                 stmt.o1.u1 = OFS_RETURN;
2261                 stmt.o2.u1 = retvalue->code.globaladdr;
2262                 stmt.o3.u1 = 0;
2263                 if (code_statements_add(stmt) < 0)
2264                     return false;
2265             }
2266             return false;
2267         }
2268
2269         if (instr->opcode == INSTR_STATE) {
2270             printf("TODO: state instruction\n");
2271             return false;
2272         }
2273
2274         stmt.opcode = instr->opcode;
2275         stmt.o1.u1 = 0;
2276         stmt.o2.u1 = 0;
2277         stmt.o3.u1 = 0;
2278
2279         /* This is the general order of operands */
2280         if (instr->_ops[0])
2281             stmt.o3.u1 = instr->_ops[0]->code.globaladdr;
2282
2283         if (instr->_ops[1])
2284             stmt.o1.u1 = instr->_ops[1]->code.globaladdr;
2285
2286         if (instr->_ops[2])
2287             stmt.o2.u1 = instr->_ops[2]->code.globaladdr;
2288
2289         if (stmt.opcode == INSTR_RETURN || stmt.opcode == INSTR_DONE)
2290         {
2291             stmt.o1.u1 = stmt.o3.u1;
2292             stmt.o3.u1 = 0;
2293         }
2294         else if ((stmt.opcode >= INSTR_STORE_F    &&
2295                   stmt.opcode <= INSTR_STORE_FNC)    ||
2296                  (stmt.opcode >= INSTR_NOT_F      &&
2297                   stmt.opcode <= INSTR_NOT_FNC))
2298         {
2299             /* 2-operand instructions with A -> B */
2300             stmt.o2.u1 = stmt.o3.u1;
2301             stmt.o3.u1 = 0;
2302         }
2303
2304         if (code_statements_add(stmt) < 0)
2305             return false;
2306     }
2307     return true;
2308 }
2309
2310 static bool gen_function_code(ir_function *self)
2311 {
2312     ir_block *block;
2313
2314     /* Starting from entry point, we generate blocks "as they come"
2315      * for now. Dead blocks will not be translated obviously.
2316      */
2317     if (!self->blocks_count) {
2318         printf("Function '%s' declared without body.\n", self->name);
2319         return false;
2320     }
2321
2322     block = self->blocks[0];
2323     if (block->generated)
2324         return true;
2325
2326     if (!gen_blocks_recursive(self, block)) {
2327         printf("failed to generate blocks for '%s'\n", self->name);
2328         return false;
2329     }
2330     return true;
2331 }
2332
2333 static bool gen_global_function(ir_builder *ir, ir_value *global)
2334 {
2335     prog_section_function fun;
2336     ir_function          *irfun;
2337
2338     size_t i;
2339     size_t local_var_end;
2340
2341     if (!global->isconst || (!global->constval.vfunc))
2342     {
2343         printf("Invalid state of function-global: not constant: %s\n", global->name);
2344         return false;
2345     }
2346
2347     irfun = global->constval.vfunc;
2348
2349     fun.name    = global->code.name;
2350     fun.file    = code_cachedstring(global->context.file);
2351     fun.profile = 0; /* always 0 */
2352     fun.nargs   = irfun->params_count;
2353
2354     for (i = 0;i < 8; ++i) {
2355         if (i >= fun.nargs)
2356             fun.argsize[i] = 0;
2357         else if (irfun->params[i] == TYPE_VECTOR)
2358             fun.argsize[i] = 3;
2359         else
2360             fun.argsize[i] = 1;
2361     }
2362
2363     fun.firstlocal = code_globals_elements;
2364     fun.locals     = irfun->allocated_locals + irfun->locals_count;
2365
2366     local_var_end = 0;
2367     for (i = 0; i < irfun->locals_count; ++i) {
2368         if (!ir_builder_gen_global(ir, irfun->locals[i])) {
2369             printf("Failed to generate global %s\n", irfun->locals[i]->name);
2370             return false;
2371         }
2372     }
2373     if (irfun->locals_count) {
2374         ir_value *last = irfun->locals[irfun->locals_count-1];
2375         local_var_end = last->code.globaladdr;
2376         local_var_end += type_sizeof[last->vtype];
2377     }
2378     for (i = 0; i < irfun->values_count; ++i)
2379     {
2380         /* generate code.globaladdr for ssa values */
2381         ir_value *v = irfun->values[i];
2382         v->code.globaladdr = local_var_end + v->code.local;
2383     }
2384     for (i = 0; i < irfun->locals_count; ++i) {
2385         /* fill the locals with zeros */
2386         code_globals_add(0);
2387     }
2388
2389     if (irfun->builtin)
2390         fun.entry = irfun->builtin;
2391     else {
2392         fun.entry = code_statements_elements;
2393         if (!gen_function_code(irfun)) {
2394             printf("Failed to generate code for function %s\n", irfun->name);
2395             return false;
2396         }
2397     }
2398
2399     return (code_functions_add(fun) >= 0);
2400 }
2401
2402 static bool ir_builder_gen_global(ir_builder *self, ir_value *global)
2403 {
2404     int32_t         *iptr;
2405     prog_section_def def;
2406
2407     def.type   = global->vtype;
2408     def.offset = code_globals_elements;
2409     def.name   = global->code.name       = code_genstring(global->name);
2410
2411     switch (global->vtype)
2412     {
2413     case TYPE_POINTER:
2414         if (code_defs_add(def) < 0)
2415             return false;
2416         return gen_global_pointer(global);
2417     case TYPE_FIELD:
2418         if (code_defs_add(def) < 0)
2419             return false;
2420         return gen_global_field(global);
2421     case TYPE_ENTITY:
2422         /* fall through */
2423     case TYPE_FLOAT:
2424     {
2425         if (code_defs_add(def) < 0)
2426             return false;
2427
2428         if (global->isconst) {
2429             iptr = (int32_t*)&global->constval.vfloat;
2430             global->code.globaladdr = code_globals_add(*iptr);
2431         } else
2432             global->code.globaladdr = code_globals_add(0);
2433
2434         return global->code.globaladdr >= 0;
2435     }
2436     case TYPE_STRING:
2437     {
2438         if (code_defs_add(def) < 0)
2439             return false;
2440         if (global->isconst)
2441             global->code.globaladdr = code_globals_add(code_cachedstring(global->constval.vstring));
2442         else
2443             global->code.globaladdr = code_globals_add(0);
2444         return global->code.globaladdr >= 0;
2445     }
2446     case TYPE_VECTOR:
2447     {
2448         if (code_defs_add(def) < 0)
2449             return false;
2450
2451         if (global->isconst) {
2452             iptr = (int32_t*)&global->constval.vvec;
2453             global->code.globaladdr = code_globals_add(iptr[0]);
2454             if (code_globals_add(iptr[1]) < 0 || code_globals_add(iptr[2]) < 0)
2455                 return false;
2456         } else {
2457             global->code.globaladdr = code_globals_add(0);
2458             if (code_globals_add(0) < 0 || code_globals_add(0) < 0)
2459                 return false;
2460         }
2461         return global->code.globaladdr >= 0;
2462     }
2463     case TYPE_FUNCTION:
2464         if (code_defs_add(def) < 0)
2465             return false;
2466         code_globals_add(code_functions_elements);
2467         return gen_global_function(self, global);
2468     case TYPE_VARIANT:
2469         /* assume biggest type */
2470             global->code.globaladdr = code_globals_add(0);
2471             code_globals_add(0);
2472             code_globals_add(0);
2473             return true;
2474     default:
2475         /* refuse to create 'void' type or any other fancy business. */
2476         printf("Invalid type for global variable %s\n", global->name);
2477         return false;
2478     }
2479 }
2480
2481 bool ir_builder_generate(ir_builder *self, const char *filename)
2482 {
2483     size_t i;
2484
2485     code_init();
2486
2487     for (i = 0; i < self->globals_count; ++i)
2488     {
2489         if (!ir_builder_gen_global(self, self->globals[i])) {
2490             return false;
2491         }
2492     }
2493
2494     printf("writing '%s'...\n", filename);
2495     return code_write(filename);
2496 }
2497
2498 /***********************************************************************
2499  *IR DEBUG Dump functions...
2500  */
2501
2502 #define IND_BUFSZ 1024
2503
2504 const char *qc_opname(int op)
2505 {
2506     if (op < 0) return "<INVALID>";
2507     if (op < ( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
2508         return asm_instr[op].m;
2509     switch (op) {
2510         case VINSTR_PHI:  return "PHI";
2511         case VINSTR_JUMP: return "JUMP";
2512         case VINSTR_COND: return "COND";
2513         default:          return "<UNK>";
2514     }
2515 }
2516
2517 void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
2518 {
2519         size_t i;
2520         char indent[IND_BUFSZ];
2521         indent[0] = '\t';
2522         indent[1] = 0;
2523
2524         oprintf("module %s\n", b->name);
2525         for (i = 0; i < b->globals_count; ++i)
2526         {
2527                 oprintf("global ");
2528                 if (b->globals[i]->isconst)
2529                         oprintf("%s = ", b->globals[i]->name);
2530                 ir_value_dump(b->globals[i], oprintf);
2531                 oprintf("\n");
2532         }
2533         for (i = 0; i < b->functions_count; ++i)
2534                 ir_function_dump(b->functions[i], indent, oprintf);
2535         oprintf("endmodule %s\n", b->name);
2536 }
2537
2538 void ir_function_dump(ir_function *f, char *ind,
2539                       int (*oprintf)(const char*, ...))
2540 {
2541         size_t i;
2542         oprintf("%sfunction %s\n", ind, f->name);
2543         strncat(ind, "\t", IND_BUFSZ);
2544         if (f->locals_count)
2545         {
2546                 oprintf("%s%i locals:\n", ind, (int)f->locals_count);
2547                 for (i = 0; i < f->locals_count; ++i) {
2548                         oprintf("%s\t", ind);
2549                         ir_value_dump(f->locals[i], oprintf);
2550                         oprintf("\n");
2551                 }
2552         }
2553         if (f->blocks_count)
2554         {
2555                 oprintf("%slife passes (check): %i\n", ind, (int)f->run_id);
2556                 for (i = 0; i < f->blocks_count; ++i) {
2557                     if (f->blocks[i]->run_id != f->run_id) {
2558                         oprintf("%slife pass check fail! %i != %i\n", ind, (int)f->blocks[i]->run_id, (int)f->run_id);
2559                     }
2560                         ir_block_dump(f->blocks[i], ind, oprintf);
2561                 }
2562
2563         }
2564         ind[strlen(ind)-1] = 0;
2565         oprintf("%sendfunction %s\n", ind, f->name);
2566 }
2567
2568 void ir_block_dump(ir_block* b, char *ind,
2569                    int (*oprintf)(const char*, ...))
2570 {
2571         size_t i;
2572         oprintf("%s:%s\n", ind, b->label);
2573         strncat(ind, "\t", IND_BUFSZ);
2574
2575         for (i = 0; i < b->instr_count; ++i)
2576                 ir_instr_dump(b->instr[i], ind, oprintf);
2577         ind[strlen(ind)-1] = 0;
2578 }
2579
2580 void dump_phi(ir_instr *in, char *ind,
2581               int (*oprintf)(const char*, ...))
2582 {
2583         size_t i;
2584         oprintf("%s <- phi ", in->_ops[0]->name);
2585         for (i = 0; i < in->phi_count; ++i)
2586         {
2587                 oprintf("([%s] : %s) ", in->phi[i].from->label,
2588                                         in->phi[i].value->name);
2589         }
2590         oprintf("\n");
2591 }
2592
2593 void ir_instr_dump(ir_instr *in, char *ind,
2594                        int (*oprintf)(const char*, ...))
2595 {
2596         size_t i;
2597         const char *comma = NULL;
2598
2599         oprintf("%s (%i) ", ind, (int)in->eid);
2600
2601         if (in->opcode == VINSTR_PHI) {
2602                 dump_phi(in, ind, oprintf);
2603                 return;
2604         }
2605
2606         strncat(ind, "\t", IND_BUFSZ);
2607
2608         if (in->_ops[0] && (in->_ops[1] || in->_ops[2])) {
2609                 ir_value_dump(in->_ops[0], oprintf);
2610                 if (in->_ops[1] || in->_ops[2])
2611                         oprintf(" <- ");
2612         }
2613         oprintf("%s\t", qc_opname(in->opcode));
2614         if (in->_ops[0] && !(in->_ops[1] || in->_ops[2])) {
2615                 ir_value_dump(in->_ops[0], oprintf);
2616                 comma = ",\t";
2617         }
2618         else
2619         {
2620                 for (i = 1; i != 3; ++i) {
2621                         if (in->_ops[i]) {
2622                                 if (comma)
2623                                         oprintf(comma);
2624                                 ir_value_dump(in->_ops[i], oprintf);
2625                                 comma = ",\t";
2626                         }
2627                 }
2628         }
2629         if (in->bops[0]) {
2630                 if (comma)
2631                         oprintf(comma);
2632                 oprintf("[%s]", in->bops[0]->label);
2633                 comma = ",\t";
2634         }
2635         if (in->bops[1])
2636                 oprintf("%s[%s]", comma, in->bops[1]->label);
2637         oprintf("\n");
2638         ind[strlen(ind)-1] = 0;
2639 }
2640
2641 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
2642 {
2643         if (v->isconst) {
2644                 switch (v->vtype) {
2645                         case TYPE_VOID:
2646                                 oprintf("(void)");
2647                                 break;
2648                         case TYPE_FLOAT:
2649                                 oprintf("%g", v->constval.vfloat);
2650                                 break;
2651                         case TYPE_VECTOR:
2652                                 oprintf("'%g %g %g'",
2653                                         v->constval.vvec.x,
2654                                         v->constval.vvec.y,
2655                                         v->constval.vvec.z);
2656                                 break;
2657                         case TYPE_ENTITY:
2658                                 oprintf("(entity)");
2659                                 break;
2660                         case TYPE_STRING:
2661                                 oprintf("\"%s\"", v->constval.vstring);
2662                                 break;
2663 #if 0
2664                         case TYPE_INTEGER:
2665                                 oprintf("%i", v->constval.vint);
2666                                 break;
2667 #endif
2668                         case TYPE_POINTER:
2669                                 oprintf("&%s",
2670                                         v->constval.vpointer->name);
2671                                 break;
2672                 }
2673         } else {
2674                 oprintf("%s", v->name);
2675         }
2676 }
2677
2678 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...))
2679 {
2680         size_t i;
2681         oprintf("Life of %s:\n", self->name);
2682         for (i = 0; i < self->life_count; ++i)
2683         {
2684                 oprintf(" + [%i, %i]\n", self->life[i].start, self->life[i].end);
2685         }
2686 }