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 const char *type_name[TYPE_COUNT] = {
  33     "void",
  34     "string",
  35     "float",
  36     "vector",
  37     "entity",
  38     "field",
  39     "function",
  40     "pointer",
  41     "integer",
  42     "variant",
  43     "struct",
  44     "union",
  45     "array"
  46 };
  47
  48 size_t type_sizeof[TYPE_COUNT] = {
  49     1, /* TYPE_VOID     */
  50     1, /* TYPE_STRING   */
  51     1, /* TYPE_FLOAT    */
  52     3, /* TYPE_VECTOR   */
  53     1, /* TYPE_ENTITY   */
  54     1, /* TYPE_FIELD    */
  55     1, /* TYPE_FUNCTION */
  56     1, /* TYPE_POINTER  */
  57     1, /* TYPE_INTEGER  */
  58     3, /* TYPE_VARIANT  */
  59     0, /* TYPE_STRUCT   */
  60     0, /* TYPE_UNION    */
  61     0, /* TYPE_ARRAY    */
  62 };
  63
  64 uint16_t type_store_instr[TYPE_COUNT] = {
  65     INSTR_STORE_F, /* should use I when having integer support */
  66     INSTR_STORE_S,
  67     INSTR_STORE_F,
  68     INSTR_STORE_V,
  69     INSTR_STORE_ENT,
  70     INSTR_STORE_FLD,
  71     INSTR_STORE_FNC,
  72     INSTR_STORE_ENT, /* should use I */
  73 #if 0
  74     INSTR_STORE_I, /* integer type */
  75 #else
  76     INSTR_STORE_F,
  77 #endif
  78
  79     INSTR_STORE_V, /* variant, should never be accessed */
  80
  81     AINSTR_END, /* struct */
  82     AINSTR_END, /* union  */
  83     AINSTR_END, /* array  */
  84 };
  85
  86 uint16_t field_store_instr[TYPE_COUNT] = {
  87     INSTR_STORE_FLD,
  88     INSTR_STORE_FLD,
  89     INSTR_STORE_FLD,
  90     INSTR_STORE_V,
  91     INSTR_STORE_FLD,
  92     INSTR_STORE_FLD,
  93     INSTR_STORE_FLD,
  94     INSTR_STORE_FLD,
  95 #if 0
  96     INSTR_STORE_FLD, /* integer type */
  97 #else
  98     INSTR_STORE_FLD,
  99 #endif
 100
 101     INSTR_STORE_V, /* variant, should never be accessed */
 102
 103     AINSTR_END, /* struct */
 104     AINSTR_END, /* union  */
 105     AINSTR_END, /* array  */
 106 };
 107
 108 uint16_t type_storep_instr[TYPE_COUNT] = {
 109     INSTR_STOREP_F, /* should use I when having integer support */
 110     INSTR_STOREP_S,
 111     INSTR_STOREP_F,
 112     INSTR_STOREP_V,
 113     INSTR_STOREP_ENT,
 114     INSTR_STOREP_FLD,
 115     INSTR_STOREP_FNC,
 116     INSTR_STOREP_ENT, /* should use I */
 117 #if 0
 118     INSTR_STOREP_ENT, /* integer type */
 119 #else
 120     INSTR_STOREP_F,
 121 #endif
 122
 123     INSTR_STOREP_V, /* variant, should never be accessed */
 124
 125     AINSTR_END, /* struct */
 126     AINSTR_END, /* union  */
 127     AINSTR_END, /* array  */
 128 };
 129
 130 uint16_t type_eq_instr[TYPE_COUNT] = {
 131     INSTR_EQ_F, /* should use I when having integer support */
 132     INSTR_EQ_S,
 133     INSTR_EQ_F,
 134     INSTR_EQ_V,
 135     INSTR_EQ_E,
 136     INSTR_EQ_E, /* FLD has no comparison */
 137     INSTR_EQ_FNC,
 138     INSTR_EQ_E, /* should use I */
 139 #if 0
 140     INSTR_EQ_I,
 141 #else
 142     INSTR_EQ_F,
 143 #endif
 144
 145     INSTR_EQ_V, /* variant, should never be accessed */
 146
 147     AINSTR_END, /* struct */
 148     AINSTR_END, /* union  */
 149     AINSTR_END, /* array  */
 150 };
 151
 152 uint16_t type_ne_instr[TYPE_COUNT] = {
 153     INSTR_NE_F, /* should use I when having integer support */
 154     INSTR_NE_S,
 155     INSTR_NE_F,
 156     INSTR_NE_V,
 157     INSTR_NE_E,
 158     INSTR_NE_E, /* FLD has no comparison */
 159     INSTR_NE_FNC,
 160     INSTR_NE_E, /* should use I */
 161 #if 0
 162     INSTR_NE_I,
 163 #else
 164     INSTR_NE_F,
 165 #endif
 166
 167     INSTR_NE_V, /* variant, should never be accessed */
 168
 169     AINSTR_END, /* struct */
 170     AINSTR_END, /* union  */
 171     AINSTR_END, /* array  */
 172 };
 173
 174 uint16_t type_not_instr[TYPE_COUNT] = {
 175     INSTR_NOT_F, /* should use I when having integer support */
 176     INSTR_NOT_S,
 177     INSTR_NOT_F,
 178     INSTR_NOT_V,
 179     INSTR_NOT_ENT,
 180     INSTR_NOT_ENT,
 181     INSTR_NOT_FNC,
 182     INSTR_NOT_ENT, /* should use I */
 183 #if 0
 184     INSTR_NOT_I, /* integer type */
 185 #else
 186     INSTR_NOT_F,
 187 #endif
 188
 189     INSTR_NOT_V, /* variant, should never be accessed */
 190
 191     AINSTR_END, /* struct */
 192     AINSTR_END, /* union  */
 193     AINSTR_END, /* array  */
 194 };
 195
 196 static void irerror(lex_ctx ctx, const char *msg, ...)
 197 {
 198     va_list ap;
 199     va_start(ap, msg);
 200     con_cvprintmsg((void*)&ctx, LVL_ERROR, "internal error", msg, ap);
 201     va_end(ap);
 202 }
 203
 204 static bool irwarning(lex_ctx ctx, int warntype, const char *fmt, ...)
 205 {
 206         va_list ap;
 207         int lvl = LVL_WARNING;
 208
 209     if (warntype && !OPTS_WARN(warntype))
 210         return false;
 211
 212     if (opts_werror)
 213             lvl = LVL_ERROR;
 214
 215         va_start(ap, fmt);
 216     con_vprintmsg(lvl, ctx.file, ctx.line, "warning", fmt, ap);
 217         va_end(ap);
 218
 219         return opts_werror;
 220 }
 221
 222 /***********************************************************************
 223  * Vector utility functions
 224  */
 225
 226 bool GMQCC_WARN vec_ir_value_find(ir_value **vec, ir_value *what, size_t *idx)
 227 {
 228     size_t i;
 229     size_t len = vec_size(vec);
 230     for (i = 0; i < len; ++i) {
 231         if (vec[i] == what) {
 232             if (idx) *idx = i;
 233             return true;
 234         }
 235     }
 236     return false;
 237 }
 238
 239 bool GMQCC_WARN vec_ir_block_find(ir_block **vec, ir_block *what, size_t *idx)
 240 {
 241     size_t i;
 242     size_t len = vec_size(vec);
 243     for (i = 0; i < len; ++i) {
 244         if (vec[i] == what) {
 245             if (idx) *idx = i;
 246             return true;
 247         }
 248     }
 249     return false;
 250 }
 251
 252 bool GMQCC_WARN vec_ir_instr_find(ir_instr **vec, ir_instr *what, size_t *idx)
 253 {
 254     size_t i;
 255     size_t len = vec_size(vec);
 256     for (i = 0; i < len; ++i) {
 257         if (vec[i] == what) {
 258             if (idx) *idx = i;
 259             return true;
 260         }
 261     }
 262     return false;
 263 }
 264
 265 /***********************************************************************
 266  * IR Builder
 267  */
 268
 269 static void ir_block_delete_quick(ir_block* self);
 270 static void ir_instr_delete_quick(ir_instr *self);
 271 static void ir_function_delete_quick(ir_function *self);
 272
 273 ir_builder* ir_builder_new(const char *modulename)
 274 {
 275     ir_builder* self;
 276
 277     self = (ir_builder*)mem_a(sizeof(*self));
 278     if (!self)
 279         return NULL;
 280
 281     self->functions   = NULL;
 282     self->globals     = NULL;
 283     self->fields      = NULL;
 284     self->extparams   = NULL;
 285     self->filenames   = NULL;
 286     self->filestrings = NULL;
 287     self->htglobals   = util_htnew(IR_HT_SIZE);
 288     self->htfields    = util_htnew(IR_HT_SIZE);
 289     self->htfunctions = util_htnew(IR_HT_SIZE);
 290
 291     self->str_immediate = 0;
 292     self->name = NULL;
 293     if (!ir_builder_set_name(self, modulename)) {
 294         mem_d(self);
 295         return NULL;
 296     }
 297
 298     return self;
 299 }
 300
 301 void ir_builder_delete(ir_builder* self)
 302 {
 303     size_t i;
 304     util_htdel(self->htglobals);
 305     util_htdel(self->htfields);
 306     util_htdel(self->htfunctions);
 307     mem_d((void*)self->name);
 308     for (i = 0; i != vec_size(self->functions); ++i) {
 309         ir_function_delete_quick(self->functions[i]);
 310     }
 311     vec_free(self->functions);
 312     for (i = 0; i != vec_size(self->extparams); ++i) {
 313         ir_value_delete(self->extparams[i]);
 314     }
 315     vec_free(self->extparams);
 316     for (i = 0; i != vec_size(self->globals); ++i) {
 317         ir_value_delete(self->globals[i]);
 318     }
 319     vec_free(self->globals);
 320     for (i = 0; i != vec_size(self->fields); ++i) {
 321         ir_value_delete(self->fields[i]);
 322     }
 323     vec_free(self->fields);
 324     vec_free(self->filenames);
 325     vec_free(self->filestrings);
 326     mem_d(self);
 327 }
 328
 329 bool ir_builder_set_name(ir_builder *self, const char *name)
 330 {
 331     if (self->name)
 332         mem_d((void*)self->name);
 333     self->name = util_strdup(name);
 334     return !!self->name;
 335 }
 336
 337 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
 338 {
 339     return (ir_function*)util_htget(self->htfunctions, name);
 340 }
 341
 342 ir_function* ir_builder_create_function(ir_builder *self, const char *name, int outtype)
 343 {
 344     ir_function *fn = ir_builder_get_function(self, name);
 345     if (fn) {
 346         return NULL;
 347     }
 348
 349     fn = ir_function_new(self, outtype);
 350     if (!ir_function_set_name(fn, name))
 351     {
 352         ir_function_delete(fn);
 353         return NULL;
 354     }
 355     vec_push(self->functions, fn);
 356     util_htset(self->htfunctions, name, fn);
 357
 358     fn->value = ir_builder_create_global(self, fn->name, TYPE_FUNCTION);
 359     if (!fn->value) {
 360         ir_function_delete(fn);
 361         return NULL;
 362     }
 363
 364     fn->value->isconst = true;
 365     fn->value->outtype = outtype;
 366     fn->value->constval.vfunc = fn;
 367     fn->value->context = fn->context;
 368
 369     return fn;
 370 }
 371
 372 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
 373 {
 374     return (ir_value*)util_htget(self->htglobals, name);
 375 }
 376
 377 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
 378 {
 379     ir_value *ve;
 380
 381     if (name && name[0] != '#')
 382     {
 383         ve = ir_builder_get_global(self, name);
 384         if (ve) {
 385             return NULL;
 386         }
 387     }
 388
 389     ve = ir_value_var(name, store_global, vtype);
 390     vec_push(self->globals, ve);
 391     util_htset(self->htglobals, name, ve);
 392     return ve;
 393 }
 394
 395 ir_value* ir_builder_get_field(ir_builder *self, const char *name)
 396 {
 397     return (ir_value*)util_htget(self->htfields, name);
 398 }
 399
 400
 401 ir_value* ir_builder_create_field(ir_builder *self, const char *name, int vtype)
 402 {
 403     ir_value *ve = ir_builder_get_field(self, name);
 404     if (ve) {
 405         return NULL;
 406     }
 407
 408     ve = ir_value_var(name, store_global, TYPE_FIELD);
 409     ve->fieldtype = vtype;
 410     vec_push(self->fields, ve);
 411     util_htset(self->htfields, name, ve);
 412     return ve;
 413 }
 414
 415 /***********************************************************************
 416  *IR Function
 417  */
 418
 419 bool ir_function_naive_phi(ir_function*);
 420 void ir_function_enumerate(ir_function*);
 421 bool ir_function_calculate_liferanges(ir_function*);
 422 bool ir_function_allocate_locals(ir_function*);
 423
 424 ir_function* ir_function_new(ir_builder* owner, int outtype)
 425 {
 426     ir_function *self;
 427     self = (ir_function*)mem_a(sizeof(*self));
 428
 429     if (!self)
 430         return NULL;
 431
 432     memset(self, 0, sizeof(*self));
 433
 434     self->name = NULL;
 435     if (!ir_function_set_name(self, "<@unnamed>")) {
 436         mem_d(self);
 437         return NULL;
 438     }
 439     self->owner = owner;
 440     self->context.file = "<@no context>";
 441     self->context.line = 0;
 442     self->outtype = outtype;
 443     self->value = NULL;
 444     self->builtin = 0;
 445
 446     self->params = NULL;
 447     self->blocks = NULL;
 448     self->values = NULL;
 449     self->locals = NULL;
 450
 451     self->code_function_def = -1;
 452     self->allocated_locals = 0;
 453
 454     self->run_id = 0;
 455     return self;
 456 }
 457
 458 bool ir_function_set_name(ir_function *self, const char *name)
 459 {
 460     if (self->name)
 461         mem_d((void*)self->name);
 462     self->name = util_strdup(name);
 463     return !!self->name;
 464 }
 465
 466 static void ir_function_delete_quick(ir_function *self)
 467 {
 468     size_t i;
 469     mem_d((void*)self->name);
 470
 471     for (i = 0; i != vec_size(self->blocks); ++i)
 472         ir_block_delete_quick(self->blocks[i]);
 473     vec_free(self->blocks);
 474
 475     vec_free(self->params);
 476
 477     for (i = 0; i != vec_size(self->values); ++i)
 478         ir_value_delete(self->values[i]);
 479     vec_free(self->values);
 480
 481     for (i = 0; i != vec_size(self->locals); ++i)
 482         ir_value_delete(self->locals[i]);
 483     vec_free(self->locals);
 484
 485     /* self->value is deleted by the builder */
 486
 487     mem_d(self);
 488 }
 489
 490 void ir_function_delete(ir_function *self)
 491 {
 492     size_t i;
 493     mem_d((void*)self->name);
 494
 495     for (i = 0; i != vec_size(self->blocks); ++i)
 496         ir_block_delete(self->blocks[i]);
 497     vec_free(self->blocks);
 498
 499     vec_free(self->params);
 500
 501     for (i = 0; i != vec_size(self->values); ++i)
 502         ir_value_delete(self->values[i]);
 503     vec_free(self->values);
 504
 505     for (i = 0; i != vec_size(self->locals); ++i)
 506         ir_value_delete(self->locals[i]);
 507     vec_free(self->locals);
 508
 509     /* self->value is deleted by the builder */
 510
 511     mem_d(self);
 512 }
 513
 514 void ir_function_collect_value(ir_function *self, ir_value *v)
 515 {
 516     vec_push(self->values, v);
 517 }
 518
 519 ir_block* ir_function_create_block(ir_function *self, const char *label)
 520 {
 521     ir_block* bn = ir_block_new(self, label);
 522     memcpy(&bn->context, &self->context, sizeof(self->context));
 523     vec_push(self->blocks, bn);
 524     return bn;
 525 }
 526
 527 bool ir_function_finalize(ir_function *self)
 528 {
 529     if (self->builtin)
 530         return true;
 531
 532     if (!ir_function_naive_phi(self))
 533         return false;
 534
 535     ir_function_enumerate(self);
 536
 537     if (!ir_function_calculate_liferanges(self))
 538         return false;
 539     if (!ir_function_allocate_locals(self))
 540         return false;
 541     return true;
 542 }
 543
 544 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype, bool param)
 545 {
 546     ir_value *ve;
 547
 548     if (param &&
 549         vec_size(self->locals) &&
 550         self->locals[vec_size(self->locals)-1]->store != store_param) {
 551         irerror(self->context, "cannot add parameters after adding locals");
 552         return NULL;
 553     }
 554
 555     ve = ir_value_var(name, (param ? store_param : store_local), vtype);
 556     vec_push(self->locals, ve);
 557     return ve;
 558 }
 559
 560 /***********************************************************************
 561  *IR Block
 562  */
 563
 564 ir_block* ir_block_new(ir_function* owner, const char *name)
 565 {
 566     ir_block *self;
 567     self = (ir_block*)mem_a(sizeof(*self));
 568     if (!self)
 569         return NULL;
 570
 571     memset(self, 0, sizeof(*self));
 572
 573     self->label = NULL;
 574     if (name && !ir_block_set_label(self, name)) {
 575         mem_d(self);
 576         return NULL;
 577     }
 578     self->owner = owner;
 579     self->context.file = "<@no context>";
 580     self->context.line = 0;
 581     self->final = false;
 582
 583     self->instr   = NULL;
 584     self->entries = NULL;
 585     self->exits   = NULL;
 586
 587     self->eid = 0;
 588     self->is_return = false;
 589     self->run_id = 0;
 590
 591     self->living = NULL;
 592
 593     self->generated = false;
 594
 595     return self;
 596 }
 597
 598 static void ir_block_delete_quick(ir_block* self)
 599 {
 600     size_t i;
 601     if (self->label) mem_d(self->label);
 602     for (i = 0; i != vec_size(self->instr); ++i)
 603         ir_instr_delete_quick(self->instr[i]);
 604     vec_free(self->instr);
 605     vec_free(self->entries);
 606     vec_free(self->exits);
 607     vec_free(self->living);
 608     mem_d(self);
 609 }
 610
 611 void ir_block_delete(ir_block* self)
 612 {
 613     size_t i;
 614     if (self->label) mem_d(self->label);
 615     for (i = 0; i != vec_size(self->instr); ++i)
 616         ir_instr_delete(self->instr[i]);
 617     vec_free(self->instr);
 618     vec_free(self->entries);
 619     vec_free(self->exits);
 620     vec_free(self->living);
 621     mem_d(self);
 622 }
 623
 624 bool ir_block_set_label(ir_block *self, const char *name)
 625 {
 626     if (self->label)
 627         mem_d((void*)self->label);
 628     self->label = util_strdup(name);
 629     return !!self->label;
 630 }
 631
 632 /***********************************************************************
 633  *IR Instructions
 634  */
 635
 636 ir_instr* ir_instr_new(ir_block* owner, int op)
 637 {
 638     ir_instr *self;
 639     self = (ir_instr*)mem_a(sizeof(*self));
 640     if (!self)
 641         return NULL;
 642
 643     self->owner = owner;
 644     self->context.file = "<@no context>";
 645     self->context.line = 0;
 646     self->opcode = op;
 647     self->_ops[0] = NULL;
 648     self->_ops[1] = NULL;
 649     self->_ops[2] = NULL;
 650     self->bops[0] = NULL;
 651     self->bops[1] = NULL;
 652
 653     self->phi    = NULL;
 654     self->params = NULL;
 655
 656     self->eid = 0;
 657
 658     self->likely = true;
 659     return self;
 660 }
 661
 662 static void ir_instr_delete_quick(ir_instr *self)
 663 {
 664     vec_free(self->phi);
 665     vec_free(self->params);
 666     mem_d(self);
 667 }
 668
 669 void ir_instr_delete(ir_instr *self)
 670 {
 671     size_t i;
 672     /* The following calls can only delete from
 673      * vectors, we still want to delete this instruction
 674      * so ignore the return value. Since with the warn_unused_result attribute
 675      * gcc doesn't care about an explicit: (void)foo(); to ignore the result,
 676      * I have to improvise here and use if(foo());
 677      */
 678     for (i = 0; i < vec_size(self->phi); ++i) {
 679         size_t idx;
 680         if (vec_ir_instr_find(self->phi[i].value->writes, self, &idx))
 681             vec_remove(self->phi[i].value->writes, idx, 1);
 682         if (vec_ir_instr_find(self->phi[i].value->reads, self, &idx))
 683             vec_remove(self->phi[i].value->reads, idx, 1);
 684     }
 685     vec_free(self->phi);
 686     for (i = 0; i < vec_size(self->params); ++i) {
 687         size_t idx;
 688         if (vec_ir_instr_find(self->params[i]->writes, self, &idx))
 689             vec_remove(self->params[i]->writes, idx, 1);
 690         if (vec_ir_instr_find(self->params[i]->reads, self, &idx))
 691             vec_remove(self->params[i]->reads, idx, 1);
 692     }
 693     vec_free(self->params);
 694     (void)!ir_instr_op(self, 0, NULL, false);
 695     (void)!ir_instr_op(self, 1, NULL, false);
 696     (void)!ir_instr_op(self, 2, NULL, false);
 697     mem_d(self);
 698 }
 699
 700 bool ir_instr_op(ir_instr *self, int op, ir_value *v, bool writing)
 701 {
 702     if (self->_ops[op]) {
 703         size_t idx;
 704         if (writing && vec_ir_instr_find(self->_ops[op]->writes, self, &idx))
 705             vec_remove(self->_ops[op]->writes, idx, 1);
 706         else if (vec_ir_instr_find(self->_ops[op]->reads, self, &idx))
 707             vec_remove(self->_ops[op]->reads, idx, 1);
 708     }
 709     if (v) {
 710         if (writing)
 711             vec_push(v->writes, self);
 712         else
 713             vec_push(v->reads, self);
 714     }
 715     self->_ops[op] = v;
 716     return true;
 717 }
 718
 719 /***********************************************************************
 720  *IR Value
 721  */
 722
 723 void ir_value_code_setaddr(ir_value *self, int32_t gaddr)
 724 {
 725     self->code.globaladdr = gaddr;
 726     if (self->members[0]) self->members[0]->code.globaladdr = gaddr;
 727     if (self->members[1]) self->members[1]->code.globaladdr = gaddr;
 728     if (self->members[2]) self->members[2]->code.globaladdr = gaddr;
 729 }
 730
 731 int32_t ir_value_code_addr(const ir_value *self)
 732 {
 733     if (self->store == store_return)
 734         return OFS_RETURN + self->code.addroffset;
 735     return self->code.globaladdr + self->code.addroffset;
 736 }
 737
 738 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 739 {
 740     ir_value *self;
 741     self = (ir_value*)mem_a(sizeof(*self));
 742     self->vtype = vtype;
 743     self->fieldtype = TYPE_VOID;
 744     self->outtype = TYPE_VOID;
 745     self->store = storetype;
 746
 747     self->reads  = NULL;
 748     self->writes = NULL;
 749
 750     self->isconst = false;
 751     self->context.file = "<@no context>";
 752     self->context.line = 0;
 753     self->name = NULL;
 754     if (name && !ir_value_set_name(self, name)) {
 755         irerror(self->context, "out of memory");
 756         mem_d(self);
 757         return NULL;
 758     }
 759
 760     memset(&self->constval, 0, sizeof(self->constval));
 761     memset(&self->code,     0, sizeof(self->code));
 762
 763     self->members[0] = NULL;
 764     self->members[1] = NULL;
 765     self->members[2] = NULL;
 766     self->memberof = NULL;
 767
 768     self->life = NULL;
 769     return self;
 770 }
 771
 772 ir_value* ir_value_vector_member(ir_value *self, unsigned int member)
 773 {
 774     ir_value *m;
 775     if (member >= 3)
 776         return NULL;
 777
 778     if (self->members[member])
 779         return self->members[member];
 780
 781     if (self->vtype == TYPE_VECTOR)
 782     {
 783         m = ir_value_var(self->name, self->store, TYPE_FLOAT);
 784         if (!m)
 785             return NULL;
 786         m->context = self->context;
 787
 788         self->members[member] = m;
 789         m->code.addroffset = member;
 790     }
 791     else if (self->vtype == TYPE_FIELD)
 792     {
 793         if (self->fieldtype != TYPE_VECTOR)
 794             return NULL;
 795         m = ir_value_var(self->name, self->store, TYPE_FIELD);
 796         if (!m)
 797             return NULL;
 798         m->fieldtype = TYPE_FLOAT;
 799         m->context = self->context;
 800
 801         self->members[member] = m;
 802         m->code.addroffset = member;
 803     }
 804     else
 805     {
 806         irerror(self->context, "invalid member access on %s", self->name);
 807         return NULL;
 808     }
 809
 810     m->memberof = self;
 811     return m;
 812 }
 813
 814 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 815 {
 816     ir_value *v = ir_value_var(name, storetype, vtype);
 817     if (!v)
 818         return NULL;
 819     ir_function_collect_value(owner, v);
 820     return v;
 821 }
 822
 823 void ir_value_delete(ir_value* self)
 824 {
 825     size_t i;
 826     if (self->name)
 827         mem_d((void*)self->name);
 828     if (self->isconst)
 829     {
 830         if (self->vtype == TYPE_STRING)
 831             mem_d((void*)self->constval.vstring);
 832     }
 833     for (i = 0; i < 3; ++i) {
 834         if (self->members[i])
 835             ir_value_delete(self->members[i]);
 836     }
 837     vec_free(self->reads);
 838     vec_free(self->writes);
 839     vec_free(self->life);
 840     mem_d(self);
 841 }
 842
 843 bool ir_value_set_name(ir_value *self, const char *name)
 844 {
 845     if (self->name)
 846         mem_d((void*)self->name);
 847     self->name = util_strdup(name);
 848     return !!self->name;
 849 }
 850
 851 bool ir_value_set_float(ir_value *self, float f)
 852 {
 853     if (self->vtype != TYPE_FLOAT)
 854         return false;
 855     self->constval.vfloat = f;
 856     self->isconst = true;
 857     return true;
 858 }
 859
 860 bool ir_value_set_func(ir_value *self, int f)
 861 {
 862     if (self->vtype != TYPE_FUNCTION)
 863         return false;
 864     self->constval.vint = f;
 865     self->isconst = true;
 866     return true;
 867 }
 868
 869 bool ir_value_set_vector(ir_value *self, vector v)
 870 {
 871     if (self->vtype != TYPE_VECTOR)
 872         return false;
 873     self->constval.vvec = v;
 874     self->isconst = true;
 875     return true;
 876 }
 877
 878 bool ir_value_set_field(ir_value *self, ir_value *fld)
 879 {
 880     if (self->vtype != TYPE_FIELD)
 881         return false;
 882     self->constval.vpointer = fld;
 883     self->isconst = true;
 884     return true;
 885 }
 886
 887 static char *ir_strdup(const char *str)
 888 {
 889     if (str && !*str) {
 890         /* actually dup empty strings */
 891         char *out = mem_a(1);
 892         *out = 0;
 893         return out;
 894     }
 895     return util_strdup(str);
 896 }
 897
 898 bool ir_value_set_string(ir_value *self, const char *str)
 899 {
 900     if (self->vtype != TYPE_STRING)
 901         return false;
 902     self->constval.vstring = ir_strdup(str);
 903     self->isconst = true;
 904     return true;
 905 }
 906
 907 #if 0
 908 bool ir_value_set_int(ir_value *self, int i)
 909 {
 910     if (self->vtype != TYPE_INTEGER)
 911         return false;
 912     self->constval.vint = i;
 913     self->isconst = true;
 914     return true;
 915 }
 916 #endif
 917
 918 bool ir_value_lives(ir_value *self, size_t at)
 919 {
 920     size_t i;
 921     for (i = 0; i < vec_size(self->life); ++i)
 922     {
 923         ir_life_entry_t *life = &self->life[i];
 924         if (life->start <= at && at <= life->end)
 925             return true;
 926         if (life->start > at) /* since it's ordered */
 927             return false;
 928     }
 929     return false;
 930 }
 931
 932 bool ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 933 {
 934     size_t k;
 935     vec_push(self->life, e);
 936     for (k = vec_size(self->life)-1; k > idx; --k)
 937         self->life[k] = self->life[k-1];
 938     self->life[idx] = e;
 939     return true;
 940 }
 941
 942 bool ir_value_life_merge(ir_value *self, size_t s)
 943 {
 944     size_t i;
 945     ir_life_entry_t *life = NULL;
 946     ir_life_entry_t *before = NULL;
 947     ir_life_entry_t new_entry;
 948
 949     /* Find the first range >= s */
 950     for (i = 0; i < vec_size(self->life); ++i)
 951     {
 952         before = life;
 953         life = &self->life[i];
 954         if (life->start > s)
 955             break;
 956     }
 957     /* nothing found? append */
 958     if (i == vec_size(self->life)) {
 959         ir_life_entry_t e;
 960         if (life && life->end+1 == s)
 961         {
 962             /* previous life range can be merged in */
 963             life->end++;
 964             return true;
 965         }
 966         if (life && life->end >= s)
 967             return false;
 968         e.start = e.end = s;
 969         vec_push(self->life, e);
 970         return true;
 971     }
 972     /* found */
 973     if (before)
 974     {
 975         if (before->end + 1 == s &&
 976             life->start - 1 == s)
 977         {
 978             /* merge */
 979             before->end = life->end;
 980             vec_remove(self->life, i, 1);
 981             return true;
 982         }
 983         if (before->end + 1 == s)
 984         {
 985             /* extend before */
 986             before->end++;
 987             return true;
 988         }
 989         /* already contained */
 990         if (before->end >= s)
 991             return false;
 992     }
 993     /* extend */
 994     if (life->start - 1 == s)
 995     {
 996         life->start--;
 997         return true;
 998     }
 999     /* insert a new entry */
1000     new_entry.start = new_entry.end = s;
1001     return ir_value_life_insert(self, i, new_entry);
1002 }
1003
1004 bool ir_value_life_merge_into(ir_value *self, const ir_value *other)
1005 {
1006     size_t i, myi;
1007
1008     if (!vec_size(other->life))
1009         return true;
1010
1011     if (!vec_size(self->life)) {
1012         size_t count = vec_size(other->life);
1013         ir_life_entry_t *life = vec_add(self->life, count);
1014         memcpy(life, other->life, count * sizeof(*life));
1015         return true;
1016     }
1017
1018     myi = 0;
1019     for (i = 0; i < vec_size(other->life); ++i)
1020     {
1021         const ir_life_entry_t *life = &other->life[i];
1022         while (true)
1023         {
1024             ir_life_entry_t *entry = &self->life[myi];
1025
1026             if (life->end+1 < entry->start)
1027             {
1028                 /* adding an interval before entry */
1029                 if (!ir_value_life_insert(self, myi, *life))
1030                     return false;
1031                 ++myi;
1032                 break;
1033             }
1034
1035             if (life->start <  entry->start &&
1036                 life->end+1 >= entry->start)
1037             {
1038                 /* starts earlier and overlaps */
1039                 entry->start = life->start;
1040             }
1041
1042             if (life->end   >  entry->end &&
1043                 life->start <= entry->end+1)
1044             {
1045                 /* ends later and overlaps */
1046                 entry->end = life->end;
1047             }
1048
1049             /* see if our change combines it with the next ranges */
1050             while (myi+1 < vec_size(self->life) &&
1051                    entry->end+1 >= self->life[1+myi].start)
1052             {
1053                 /* overlaps with (myi+1) */
1054                 if (entry->end < self->life[1+myi].end)
1055                     entry->end = self->life[1+myi].end;
1056                 vec_remove(self->life, myi+1, 1);
1057                 entry = &self->life[myi];
1058             }
1059
1060             /* see if we're after the entry */
1061             if (life->start > entry->end)
1062             {
1063                 ++myi;
1064                 /* append if we're at the end */
1065                 if (myi >= vec_size(self->life)) {
1066                     vec_push(self->life, *life);
1067                     break;
1068                 }
1069                 /* otherweise check the next range */
1070                 continue;
1071             }
1072             break;
1073         }
1074     }
1075     return true;
1076 }
1077
1078 bool ir_values_overlap(const ir_value *a, const ir_value *b)
1079 {
1080     /* For any life entry in A see if it overlaps with
1081      * any life entry in B.
1082      * Note that the life entries are orderes, so we can make a
1083      * more efficient algorithm there than naively translating the
1084      * statement above.
1085      */
1086
1087     ir_life_entry_t *la, *lb, *enda, *endb;
1088
1089     /* first of all, if either has no life range, they cannot clash */
1090     if (!vec_size(a->life) || !vec_size(b->life))
1091         return false;
1092
1093     la = a->life;
1094     lb = b->life;
1095     enda = la + vec_size(a->life);
1096     endb = lb + vec_size(b->life);
1097     while (true)
1098     {
1099         /* check if the entries overlap, for that,
1100          * both must start before the other one ends.
1101          */
1102         if (la->start < lb->end &&
1103             lb->start < la->end)
1104         {
1105             return true;
1106         }
1107
1108         /* entries are ordered
1109          * one entry is earlier than the other
1110          * that earlier entry will be moved forward
1111          */
1112         if (la->start < lb->start)
1113         {
1114             /* order: A B, move A forward
1115              * check if we hit the end with A
1116              */
1117             if (++la == enda)
1118                 break;
1119         }
1120         else /* if (lb->start < la->start)  actually <= */
1121         {
1122             /* order: B A, move B forward
1123              * check if we hit the end with B
1124              */
1125             if (++lb == endb)
1126                 break;
1127         }
1128     }
1129     return false;
1130 }
1131
1132 /***********************************************************************
1133  *IR main operations
1134  */
1135
1136 bool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
1137 {
1138     ir_instr *in;
1139     if (self->final) {
1140         irerror(self->context, "unreachable statement (%s)", self->label);
1141         return false;
1142     }
1143     in = ir_instr_new(self, op);
1144     if (!in)
1145         return false;
1146
1147     if (target->store == store_value &&
1148         (op < INSTR_STOREP_F || op > INSTR_STOREP_FNC))
1149     {
1150         irerror(self->context, "cannot store to an SSA value");
1151         irerror(self->context, "trying to store: %s <- %s", target->name, what->name);
1152         irerror(self->context, "instruction: %s", asm_instr[op].m);
1153         return false;
1154     }
1155
1156     if (!ir_instr_op(in, 0, target, true) ||
1157         !ir_instr_op(in, 1, what, false))
1158     {
1159         return false;
1160     }
1161     vec_push(self->instr, in);
1162     return true;
1163 }
1164
1165 bool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
1166 {
1167     int op = 0;
1168     int vtype;
1169     if (target->vtype == TYPE_VARIANT)
1170         vtype = what->vtype;
1171     else
1172         vtype = target->vtype;
1173
1174 #if 0
1175     if      (vtype == TYPE_FLOAT   && what->vtype == TYPE_INTEGER)
1176         op = INSTR_CONV_ITOF;
1177     else if (vtype == TYPE_INTEGER && what->vtype == TYPE_FLOAT)
1178         op = INSTR_CONV_FTOI;
1179 #endif
1180         op = type_store_instr[vtype];
1181
1182     if (OPTS_FLAG(ADJUST_VECTOR_FIELDS)) {
1183         if (op == INSTR_STORE_FLD && what->fieldtype == TYPE_VECTOR)
1184             op = INSTR_STORE_V;
1185     }
1186
1187     return ir_block_create_store_op(self, op, target, what);
1188 }
1189
1190 bool ir_block_create_storep(ir_block *self, ir_value *target, ir_value *what)
1191 {
1192     int op = 0;
1193     int vtype;
1194
1195     if (target->vtype != TYPE_POINTER)
1196         return false;
1197
1198     /* storing using pointer - target is a pointer, type must be
1199      * inferred from source
1200      */
1201     vtype = what->vtype;
1202
1203     op = type_storep_instr[vtype];
1204     if (OPTS_FLAG(ADJUST_VECTOR_FIELDS)) {
1205         if (op == INSTR_STOREP_FLD && what->fieldtype == TYPE_VECTOR)
1206             op = INSTR_STOREP_V;
1207     }
1208
1209     return ir_block_create_store_op(self, op, target, what);
1210 }
1211
1212 bool ir_block_create_return(ir_block *self, ir_value *v)
1213 {
1214     ir_instr *in;
1215     if (self->final) {
1216         irerror(self->context, "unreachable statement (%s)", self->label);
1217         return false;
1218     }
1219     self->final = true;
1220     self->is_return = true;
1221     in = ir_instr_new(self, INSTR_RETURN);
1222     if (!in)
1223         return false;
1224
1225     if (v && !ir_instr_op(in, 0, v, false))
1226         return false;
1227
1228     vec_push(self->instr, in);
1229     return true;
1230 }
1231
1232 bool ir_block_create_if(ir_block *self, ir_value *v,
1233                         ir_block *ontrue, ir_block *onfalse)
1234 {
1235     ir_instr *in;
1236     if (self->final) {
1237         irerror(self->context, "unreachable statement (%s)", self->label);
1238         return false;
1239     }
1240     self->final = true;
1241     /*in = ir_instr_new(self, (v->vtype == TYPE_STRING ? INSTR_IF_S : INSTR_IF_F));*/
1242     in = ir_instr_new(self, VINSTR_COND);
1243     if (!in)
1244         return false;
1245
1246     if (!ir_instr_op(in, 0, v, false)) {
1247         ir_instr_delete(in);
1248         return false;
1249     }
1250
1251     in->bops[0] = ontrue;
1252     in->bops[1] = onfalse;
1253
1254     vec_push(self->instr, in);
1255
1256     vec_push(self->exits, ontrue);
1257     vec_push(self->exits, onfalse);
1258     vec_push(ontrue->entries,  self);
1259     vec_push(onfalse->entries, self);
1260     return true;
1261 }
1262
1263 bool ir_block_create_jump(ir_block *self, ir_block *to)
1264 {
1265     ir_instr *in;
1266     if (self->final) {
1267         irerror(self->context, "unreachable statement (%s)", self->label);
1268         return false;
1269     }
1270     self->final = true;
1271     in = ir_instr_new(self, VINSTR_JUMP);
1272     if (!in)
1273         return false;
1274
1275     in->bops[0] = to;
1276     vec_push(self->instr, in);
1277
1278     vec_push(self->exits, to);
1279     vec_push(to->entries, self);
1280     return true;
1281 }
1282
1283 bool ir_block_create_goto(ir_block *self, ir_block *to)
1284 {
1285     ir_instr *in;
1286     if (self->final) {
1287         irerror(self->context, "unreachable statement (%s)", self->label);
1288         return false;
1289     }
1290     self->final = true;
1291     in = ir_instr_new(self, INSTR_GOTO);
1292     if (!in)
1293         return false;
1294
1295     in->bops[0] = to;
1296     vec_push(self->instr, in);
1297
1298     vec_push(self->exits, to);
1299     vec_push(to->entries, self);
1300     return true;
1301 }
1302
1303 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
1304 {
1305     ir_value *out;
1306     ir_instr *in;
1307     in = ir_instr_new(self, VINSTR_PHI);
1308     if (!in)
1309         return NULL;
1310     out = ir_value_out(self->owner, label, store_value, ot);
1311     if (!out) {
1312         ir_instr_delete(in);
1313         return NULL;
1314     }
1315     if (!ir_instr_op(in, 0, out, true)) {
1316         ir_instr_delete(in);
1317         ir_value_delete(out);
1318         return NULL;
1319     }
1320     vec_push(self->instr, in);
1321     return in;
1322 }
1323
1324 ir_value* ir_phi_value(ir_instr *self)
1325 {
1326     return self->_ops[0];
1327 }
1328
1329 void ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
1330 {
1331     ir_phi_entry_t pe;
1332
1333     if (!vec_ir_block_find(self->owner->entries, b, NULL)) {
1334         /* Must not be possible to cause this, otherwise the AST
1335          * is doing something wrong.
1336          */
1337         irerror(self->context, "Invalid entry block for PHI");
1338         abort();
1339     }
1340
1341     pe.value = v;
1342     pe.from = b;
1343     vec_push(v->reads, self);
1344     vec_push(self->phi, pe);
1345 }
1346
1347 /* call related code */
1348 ir_instr* ir_block_create_call(ir_block *self, const char *label, ir_value *func)
1349 {
1350     ir_value *out;
1351     ir_instr *in;
1352     in = ir_instr_new(self, INSTR_CALL0);
1353     if (!in)
1354         return NULL;
1355     out = ir_value_out(self->owner, label, (func->outtype == TYPE_VOID) ? store_return : store_value, func->outtype);
1356     if (!out) {
1357         ir_instr_delete(in);
1358         return NULL;
1359     }
1360     if (!ir_instr_op(in, 0, out, true) ||
1361         !ir_instr_op(in, 1, func, false))
1362     {
1363         ir_instr_delete(in);
1364         ir_value_delete(out);
1365         return NULL;
1366     }
1367     vec_push(self->instr, in);
1368     return in;
1369 }
1370
1371 ir_value* ir_call_value(ir_instr *self)
1372 {
1373     return self->_ops[0];
1374 }
1375
1376 void ir_call_param(ir_instr* self, ir_value *v)
1377 {
1378     vec_push(self->params, v);
1379     vec_push(v->reads, self);
1380 }
1381
1382 /* binary op related code */
1383
1384 ir_value* ir_block_create_binop(ir_block *self,
1385                                 const char *label, int opcode,
1386                                 ir_value *left, ir_value *right)
1387 {
1388     int ot = TYPE_VOID;
1389     switch (opcode) {
1390         case INSTR_ADD_F:
1391         case INSTR_SUB_F:
1392         case INSTR_DIV_F:
1393         case INSTR_MUL_F:
1394         case INSTR_MUL_V:
1395         case INSTR_AND:
1396         case INSTR_OR:
1397 #if 0
1398         case INSTR_AND_I:
1399         case INSTR_AND_IF:
1400         case INSTR_AND_FI:
1401         case INSTR_OR_I:
1402         case INSTR_OR_IF:
1403         case INSTR_OR_FI:
1404 #endif
1405         case INSTR_BITAND:
1406         case INSTR_BITOR:
1407 #if 0
1408         case INSTR_SUB_S: /* -- offset of string as float */
1409         case INSTR_MUL_IF:
1410         case INSTR_MUL_FI:
1411         case INSTR_DIV_IF:
1412         case INSTR_DIV_FI:
1413         case INSTR_BITOR_IF:
1414         case INSTR_BITOR_FI:
1415         case INSTR_BITAND_FI:
1416         case INSTR_BITAND_IF:
1417         case INSTR_EQ_I:
1418         case INSTR_NE_I:
1419 #endif
1420             ot = TYPE_FLOAT;
1421             break;
1422 #if 0
1423         case INSTR_ADD_I:
1424         case INSTR_ADD_IF:
1425         case INSTR_ADD_FI:
1426         case INSTR_SUB_I:
1427         case INSTR_SUB_FI:
1428         case INSTR_SUB_IF:
1429         case INSTR_MUL_I:
1430         case INSTR_DIV_I:
1431         case INSTR_BITAND_I:
1432         case INSTR_BITOR_I:
1433         case INSTR_XOR_I:
1434         case INSTR_RSHIFT_I:
1435         case INSTR_LSHIFT_I:
1436             ot = TYPE_INTEGER;
1437             break;
1438 #endif
1439         case INSTR_ADD_V:
1440         case INSTR_SUB_V:
1441         case INSTR_MUL_VF:
1442         case INSTR_MUL_FV:
1443 #if 0
1444         case INSTR_DIV_VF:
1445         case INSTR_MUL_IV:
1446         case INSTR_MUL_VI:
1447 #endif
1448             ot = TYPE_VECTOR;
1449             break;
1450 #if 0
1451         case INSTR_ADD_SF:
1452             ot = TYPE_POINTER;
1453             break;
1454 #endif
1455         default:
1456             /* ranges: */
1457             /* boolean operations result in floats */
1458             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
1459                 ot = TYPE_FLOAT;
1460             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
1461                 ot = TYPE_FLOAT;
1462 #if 0
1463             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
1464                 ot = TYPE_FLOAT;
1465 #endif
1466             break;
1467     };
1468     if (ot == TYPE_VOID) {
1469         /* The AST or parser were supposed to check this! */
1470         return NULL;
1471     }
1472
1473     return ir_block_create_general_instr(self, label, opcode, left, right, ot);
1474 }
1475
1476 ir_value* ir_block_create_unary(ir_block *self,
1477                                 const char *label, int opcode,
1478                                 ir_value *operand)
1479 {
1480     int ot = TYPE_FLOAT;
1481     switch (opcode) {
1482         case INSTR_NOT_F:
1483         case INSTR_NOT_V:
1484         case INSTR_NOT_S:
1485         case INSTR_NOT_ENT:
1486         case INSTR_NOT_FNC:
1487 #if 0
1488         case INSTR_NOT_I:
1489 #endif
1490             ot = TYPE_FLOAT;
1491             break;
1492         /* QC doesn't have other unary operations. We expect extensions to fill
1493          * the above list, otherwise we assume out-type = in-type, eg for an
1494          * unary minus
1495          */
1496         default:
1497             ot = operand->vtype;
1498             break;
1499     };
1500     if (ot == TYPE_VOID) {
1501         /* The AST or parser were supposed to check this! */
1502         return NULL;
1503     }
1504
1505     /* let's use the general instruction creator and pass NULL for OPB */
1506     return ir_block_create_general_instr(self, label, opcode, operand, NULL, ot);
1507 }
1508
1509 ir_value* ir_block_create_general_instr(ir_block *self, const char *label,
1510                                         int op, ir_value *a, ir_value *b, int outype)
1511 {
1512     ir_instr *instr;
1513     ir_value *out;
1514
1515     out = ir_value_out(self->owner, label, store_value, outype);
1516     if (!out)
1517         return NULL;
1518
1519     instr = ir_instr_new(self, op);
1520     if (!instr) {
1521         ir_value_delete(out);
1522         return NULL;
1523     }
1524
1525     if (!ir_instr_op(instr, 0, out, true) ||
1526         !ir_instr_op(instr, 1, a, false) ||
1527         !ir_instr_op(instr, 2, b, false) )
1528     {
1529         goto on_error;
1530     }
1531
1532     vec_push(self->instr, instr);
1533
1534     return out;
1535 on_error:
1536     ir_instr_delete(instr);
1537     ir_value_delete(out);
1538     return NULL;
1539 }
1540
1541 ir_value* ir_block_create_fieldaddress(ir_block *self, const char *label, ir_value *ent, ir_value *field)
1542 {
1543     ir_value *v;
1544
1545     /* Support for various pointer types todo if so desired */
1546     if (ent->vtype != TYPE_ENTITY)
1547         return NULL;
1548
1549     if (field->vtype != TYPE_FIELD)
1550         return NULL;
1551
1552     v = ir_block_create_general_instr(self, label, INSTR_ADDRESS, ent, field, TYPE_POINTER);
1553     v->fieldtype = field->fieldtype;
1554     return v;
1555 }
1556
1557 ir_value* ir_block_create_load_from_ent(ir_block *self, const char *label, ir_value *ent, ir_value *field, int outype)
1558 {
1559     int op;
1560     if (ent->vtype != TYPE_ENTITY)
1561         return NULL;
1562
1563     /* at some point we could redirect for TYPE_POINTER... but that could lead to carelessness */
1564     if (field->vtype != TYPE_FIELD)
1565         return NULL;
1566
1567     switch (outype)
1568     {
1569         case TYPE_FLOAT:    op = INSTR_LOAD_F;   break;
1570         case TYPE_VECTOR:   op = INSTR_LOAD_V;   break;
1571         case TYPE_STRING:   op = INSTR_LOAD_S;   break;
1572         case TYPE_FIELD:    op = INSTR_LOAD_FLD; break;
1573         case TYPE_ENTITY:   op = INSTR_LOAD_ENT; break;
1574         case TYPE_FUNCTION: op = INSTR_LOAD_FNC; break;
1575 #if 0
1576         case TYPE_POINTER: op = INSTR_LOAD_I;   break;
1577         case TYPE_INTEGER: op = INSTR_LOAD_I;   break;
1578 #endif
1579         default:
1580             irerror(self->context, "invalid type for ir_block_create_load_from_ent: %s", type_name[outype]);
1581             return NULL;
1582     }
1583
1584     return ir_block_create_general_instr(self, label, op, ent, field, outype);
1585 }
1586
1587 ir_value* ir_block_create_add(ir_block *self,
1588                               const char *label,
1589                               ir_value *left, ir_value *right)
1590 {
1591     int op = 0;
1592     int l = left->vtype;
1593     int r = right->vtype;
1594     if (l == r) {
1595         switch (l) {
1596             default:
1597                 irerror(self->context, "invalid type for ir_block_create_add: %s", type_name[l]);
1598                 return NULL;
1599             case TYPE_FLOAT:
1600                 op = INSTR_ADD_F;
1601                 break;
1602 #if 0
1603             case TYPE_INTEGER:
1604                 op = INSTR_ADD_I;
1605                 break;
1606 #endif
1607             case TYPE_VECTOR:
1608                 op = INSTR_ADD_V;
1609                 break;
1610         }
1611     } else {
1612 #if 0
1613         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1614             op = INSTR_ADD_FI;
1615         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1616             op = INSTR_ADD_IF;
1617         else
1618 #endif
1619         {
1620             irerror(self->context, "invalid type for ir_block_create_add: %s", type_name[l]);
1621             return NULL;
1622         }
1623     }
1624     return ir_block_create_binop(self, label, op, left, right);
1625 }
1626
1627 ir_value* ir_block_create_sub(ir_block *self,
1628                               const char *label,
1629                               ir_value *left, ir_value *right)
1630 {
1631     int op = 0;
1632     int l = left->vtype;
1633     int r = right->vtype;
1634     if (l == r) {
1635
1636         switch (l) {
1637             default:
1638                 irerror(self->context, "invalid type for ir_block_create_sub: %s", type_name[l]);
1639                 return NULL;
1640             case TYPE_FLOAT:
1641                 op = INSTR_SUB_F;
1642                 break;
1643 #if 0
1644             case TYPE_INTEGER:
1645                 op = INSTR_SUB_I;
1646                 break;
1647 #endif
1648             case TYPE_VECTOR:
1649                 op = INSTR_SUB_V;
1650                 break;
1651         }
1652     } else {
1653 #if 0
1654         if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1655             op = INSTR_SUB_FI;
1656         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1657             op = INSTR_SUB_IF;
1658         else
1659 #endif
1660         {
1661             irerror(self->context, "invalid type for ir_block_create_sub: %s", type_name[l]);
1662             return NULL;
1663         }
1664     }
1665     return ir_block_create_binop(self, label, op, left, right);
1666 }
1667
1668 ir_value* ir_block_create_mul(ir_block *self,
1669                               const char *label,
1670                               ir_value *left, ir_value *right)
1671 {
1672     int op = 0;
1673     int l = left->vtype;
1674     int r = right->vtype;
1675     if (l == r) {
1676
1677         switch (l) {
1678             default:
1679                 irerror(self->context, "invalid type for ir_block_create_mul: %s", type_name[l]);
1680                 return NULL;
1681             case TYPE_FLOAT:
1682                 op = INSTR_MUL_F;
1683                 break;
1684 #if 0
1685             case TYPE_INTEGER:
1686                 op = INSTR_MUL_I;
1687                 break;
1688 #endif
1689             case TYPE_VECTOR:
1690                 op = INSTR_MUL_V;
1691                 break;
1692         }
1693     } else {
1694         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1695             op = INSTR_MUL_VF;
1696         else if ( (l == TYPE_FLOAT && r == TYPE_VECTOR) )
1697             op = INSTR_MUL_FV;
1698 #if 0
1699         else if ( (l == TYPE_VECTOR && r == TYPE_INTEGER) )
1700             op = INSTR_MUL_VI;
1701         else if ( (l == TYPE_INTEGER && r == TYPE_VECTOR) )
1702             op = INSTR_MUL_IV;
1703         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1704             op = INSTR_MUL_FI;
1705         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1706             op = INSTR_MUL_IF;
1707 #endif
1708         else {
1709             irerror(self->context, "invalid type for ir_block_create_mul: %s", type_name[l]);
1710             return NULL;
1711         }
1712     }
1713     return ir_block_create_binop(self, label, op, left, right);
1714 }
1715
1716 ir_value* ir_block_create_div(ir_block *self,
1717                               const char *label,
1718                               ir_value *left, ir_value *right)
1719 {
1720     int op = 0;
1721     int l = left->vtype;
1722     int r = right->vtype;
1723     if (l == r) {
1724
1725         switch (l) {
1726             default:
1727                 irerror(self->context, "invalid type for ir_block_create_div: %s", type_name[l]);
1728                 return NULL;
1729             case TYPE_FLOAT:
1730                 op = INSTR_DIV_F;
1731                 break;
1732 #if 0
1733             case TYPE_INTEGER:
1734                 op = INSTR_DIV_I;
1735                 break;
1736 #endif
1737         }
1738     } else {
1739 #if 0
1740         if ( (l == TYPE_VECTOR && r == TYPE_FLOAT) )
1741             op = INSTR_DIV_VF;
1742         else if ( (l == TYPE_FLOAT && r == TYPE_INTEGER) )
1743             op = INSTR_DIV_FI;
1744         else if ( (l == TYPE_INTEGER && r == TYPE_FLOAT) )
1745             op = INSTR_DIV_IF;
1746         else
1747 #endif
1748         {
1749             irerror(self->context, "invalid type for ir_block_create_div: %s", type_name[l]);
1750             return NULL;
1751         }
1752     }
1753     return ir_block_create_binop(self, label, op, left, right);
1754 }
1755
1756 /* PHI resolving breaks the SSA, and must thus be the last
1757  * step before life-range calculation.
1758  */
1759
1760 static bool ir_block_naive_phi(ir_block *self);
1761 bool ir_function_naive_phi(ir_function *self)
1762 {
1763     size_t i;
1764
1765     for (i = 0; i < vec_size(self->blocks); ++i)
1766     {
1767         if (!ir_block_naive_phi(self->blocks[i]))
1768             return false;
1769     }
1770     return true;
1771 }
1772
1773 #if 0
1774 static bool ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
1775 {
1776     ir_instr *instr;
1777     size_t i;
1778
1779     /* create a store */
1780     if (!ir_block_create_store(block, old, what))
1781         return false;
1782
1783     /* we now move it up */
1784     instr = vec_last(block->instr);
1785     for (i = vec_size(block->instr)-1; i > iid; --i)
1786         block->instr[i] = block->instr[i-1];
1787     block->instr[i] = instr;
1788
1789     return true;
1790 }
1791 #endif
1792
1793 static bool ir_block_naive_phi(ir_block *self)
1794 {
1795     size_t i, p; /*, w;*/
1796     /* FIXME: optionally, create_phi can add the phis
1797      * to a list so we don't need to loop through blocks
1798      * - anyway: "don't optimize YET"
1799      */
1800     for (i = 0; i < vec_size(self->instr); ++i)
1801     {
1802         ir_instr *instr = self->instr[i];
1803         if (instr->opcode != VINSTR_PHI)
1804             continue;
1805
1806         vec_remove(self->instr, i, 1);
1807         --i; /* NOTE: i+1 below */
1808
1809         for (p = 0; p < vec_size(instr->phi); ++p)
1810         {
1811             ir_value *v = instr->phi[p].value;
1812             ir_block *b = instr->phi[p].from;
1813
1814             if (v->store == store_value &&
1815                 vec_size(v->reads) == 1 &&
1816                 vec_size(v->writes) == 1)
1817             {
1818                 /* replace the value */
1819                 if (!ir_instr_op(v->writes[0], 0, instr->_ops[0], true))
1820                     return false;
1821             }
1822             else
1823             {
1824                 /* force a move instruction */
1825                 ir_instr *prevjump = vec_last(b->instr);
1826                 vec_pop(b->instr);
1827                 b->final = false;
1828                 instr->_ops[0]->store = store_global;
1829                 if (!ir_block_create_store(b, instr->_ops[0], v))
1830                     return false;
1831                 instr->_ops[0]->store = store_value;
1832                 vec_push(b->instr, prevjump);
1833                 b->final = true;
1834             }
1835
1836 #if 0
1837             ir_value *v = instr->phi[p].value;
1838             for (w = 0; w < vec_size(v->writes); ++w) {
1839                 ir_value *old;
1840
1841                 if (!v->writes[w]->_ops[0])
1842                     continue;
1843
1844                 /* When the write was to a global, we have to emit a mov */
1845                 old = v->writes[w]->_ops[0];
1846
1847                 /* The original instruction now writes to the PHI target local */
1848                 if (v->writes[w]->_ops[0] == v)
1849                     v->writes[w]->_ops[0] = instr->_ops[0];
1850
1851                 if (old->store != store_value && old->store != store_local && old->store != store_param)
1852                 {
1853                     /* If it originally wrote to a global we need to store the value
1854                      * there as welli
1855                      */
1856                     if (!ir_naive_phi_emit_store(self, i+1, old, v))
1857                         return false;
1858                     if (i+1 < vec_size(self->instr))
1859                         instr = self->instr[i+1];
1860                     else
1861                         instr = NULL;
1862                     /* In case I forget and access instr later, it'll be NULL
1863                      * when it's a problem, to make sure we crash, rather than accessing
1864                      * invalid data.
1865                      */
1866                 }
1867                 else
1868                 {
1869                     /* If it didn't, we can replace all reads by the phi target now. */
1870                     size_t r;
1871                     for (r = 0; r < vec_size(old->reads); ++r)
1872                     {
1873                         size_t op;
1874                         ir_instr *ri = old->reads[r];
1875                         for (op = 0; op < vec_size(ri->phi); ++op) {
1876                             if (ri->phi[op].value == old)
1877                                 ri->phi[op].value = v;
1878                         }
1879                         for (op = 0; op < 3; ++op) {
1880                             if (ri->_ops[op] == old)
1881                                 ri->_ops[op] = v;
1882                         }
1883                     }
1884                 }
1885             }
1886 #endif
1887         }
1888         ir_instr_delete(instr);
1889     }
1890     return true;
1891 }
1892
1893 /***********************************************************************
1894  *IR Temp allocation code
1895  * Propagating value life ranges by walking through the function backwards
1896  * until no more changes are made.
1897  * In theory this should happen once more than once for every nested loop
1898  * level.
1899  * Though this implementation might run an additional time for if nests.
1900  */
1901
1902 /* Enumerate instructions used by value's life-ranges
1903  */
1904 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1905 {
1906     size_t i;
1907     size_t eid = *_eid;
1908     for (i = 0; i < vec_size(self->instr); ++i)
1909     {
1910         self->instr[i]->eid = eid++;
1911     }
1912     *_eid = eid;
1913 }
1914
1915 /* Enumerate blocks and instructions.
1916  * The block-enumeration is unordered!
1917  * We do not really use the block enumreation, however
1918  * the instruction enumeration is important for life-ranges.
1919  */
1920 void ir_function_enumerate(ir_function *self)
1921 {
1922     size_t i;
1923     size_t instruction_id = 0;
1924     for (i = 0; i < vec_size(self->blocks); ++i)
1925     {
1926         self->blocks[i]->eid = i;
1927         self->blocks[i]->run_id = 0;
1928         ir_block_enumerate(self->blocks[i], &instruction_id);
1929     }
1930 }
1931
1932 static bool ir_block_life_propagate(ir_block *b, ir_block *prev, bool *changed);
1933 bool ir_function_calculate_liferanges(ir_function *self)
1934 {
1935     size_t i;
1936     bool changed;
1937
1938     do {
1939         self->run_id++;
1940         changed = false;
1941         for (i = 0; i != vec_size(self->blocks); ++i)
1942         {
1943             if (self->blocks[i]->is_return)
1944             {
1945                 vec_free(self->blocks[i]->living);
1946                 if (!ir_block_life_propagate(self->blocks[i], NULL, &changed))
1947                     return false;
1948             }
1949         }
1950     } while (changed);
1951     if (vec_size(self->blocks)) {
1952         ir_block *block = self->blocks[0];
1953         for (i = 0; i < vec_size(block->living); ++i) {
1954             ir_value *v = block->living[i];
1955             if (v->memberof || v->store != store_local)
1956                 continue;
1957             if (irwarning(v->context, WARN_USED_UNINITIALIZED,
1958                           "variable `%s` may be used uninitialized in this function", v->name))
1959             {
1960                 return false;
1961             }
1962         }
1963     }
1964     return true;
1965 }
1966
1967 /* Local-value allocator
1968  * After finishing creating the liferange of all values used in a function
1969  * we can allocate their global-positions.
1970  * This is the counterpart to register-allocation in register machines.
1971  */
1972 typedef struct {
1973     ir_value **locals;
1974     size_t    *sizes;
1975     size_t    *positions;
1976 } function_allocator;
1977
1978 static bool function_allocator_alloc(function_allocator *alloc, const ir_value *var)
1979 {
1980     ir_value *slot;
1981     size_t vsize = type_sizeof[var->vtype];
1982
1983     slot = ir_value_var("reg", store_global, var->vtype);
1984     if (!slot)
1985         return false;
1986
1987     if (!ir_value_life_merge_into(slot, var))
1988         goto localerror;
1989
1990     vec_push(alloc->locals, slot);
1991     vec_push(alloc->sizes, vsize);
1992
1993     return true;
1994
1995 localerror:
1996     ir_value_delete(slot);
1997     return false;
1998 }
1999
2000 bool ir_function_allocate_locals(ir_function *self)
2001 {
2002     size_t i, a;
2003     bool   retval = true;
2004     size_t pos;
2005
2006     ir_value *slot;
2007     const ir_value *v;
2008
2009     function_allocator alloc;
2010
2011     if (!vec_size(self->locals) && !vec_size(self->values))
2012         return true;
2013
2014     alloc.locals    = NULL;
2015     alloc.sizes     = NULL;
2016     alloc.positions = NULL;
2017
2018     for (i = 0; i < vec_size(self->locals); ++i)
2019     {
2020         if (!function_allocator_alloc(&alloc, self->locals[i]))
2021             goto error;
2022     }
2023
2024     /* Allocate a slot for any value that still exists */
2025     for (i = 0; i < vec_size(self->values); ++i)
2026     {
2027         v = self->values[i];
2028
2029         if (!vec_size(v->life))
2030             continue;
2031
2032         for (a = 0; a < vec_size(alloc.locals); ++a)
2033         {
2034             slot = alloc.locals[a];
2035
2036             if (ir_values_overlap(v, slot))
2037                 continue;
2038
2039             if (!ir_value_life_merge_into(slot, v))
2040                 goto error;
2041
2042             /* adjust size for this slot */
2043             if (alloc.sizes[a] < type_sizeof[v->vtype])
2044                 alloc.sizes[a] = type_sizeof[v->vtype];
2045
2046             self->values[i]->code.local = a;
2047             break;
2048         }
2049         if (a >= vec_size(alloc.locals)) {
2050             self->values[i]->code.local = vec_size(alloc.locals);
2051             if (!function_allocator_alloc(&alloc, v))
2052                 goto error;
2053         }
2054     }
2055
2056     if (!alloc.sizes) {
2057         goto cleanup;
2058     }
2059
2060     /* Adjust slot positions based on sizes */
2061     vec_push(alloc.positions, 0);
2062
2063     if (vec_size(alloc.sizes))
2064         pos = alloc.positions[0] + alloc.sizes[0];
2065     else
2066         pos = 0;
2067     for (i = 1; i < vec_size(alloc.sizes); ++i)
2068     {
2069         pos = alloc.positions[i-1] + alloc.sizes[i-1];
2070         vec_push(alloc.positions, pos);
2071     }
2072
2073     self->allocated_locals = pos + vec_last(alloc.sizes);
2074
2075     /* Take over the actual slot positions */
2076     for (i = 0; i < vec_size(self->values); ++i) {
2077         self->values[i]->code.local = alloc.positions[self->values[i]->code.local];
2078     }
2079
2080     goto cleanup;
2081
2082 error:
2083     retval = false;
2084 cleanup:
2085     for (i = 0; i < vec_size(alloc.locals); ++i)
2086         ir_value_delete(alloc.locals[i]);
2087     vec_free(alloc.locals);
2088     vec_free(alloc.sizes);
2089     vec_free(alloc.positions);
2090     return retval;
2091 }
2092
2093 /* Get information about which operand
2094  * is read from, or written to.
2095  */
2096 static void ir_op_read_write(int op, size_t *read, size_t *write)
2097 {
2098     switch (op)
2099     {
2100     case VINSTR_JUMP:
2101     case INSTR_GOTO:
2102         *write = 0;
2103         *read = 0;
2104         break;
2105     case INSTR_IF:
2106     case INSTR_IFNOT:
2107 #if 0
2108     case INSTR_IF_S:
2109     case INSTR_IFNOT_S:
2110 #endif
2111     case INSTR_RETURN:
2112     case VINSTR_COND:
2113         *write = 0;
2114         *read = 1;
2115         break;
2116     case INSTR_STOREP_F:
2117     case INSTR_STOREP_V:
2118     case INSTR_STOREP_S:
2119     case INSTR_STOREP_ENT:
2120     case INSTR_STOREP_FLD:
2121     case INSTR_STOREP_FNC:
2122         *write = 0;
2123         *read  = 7;
2124         break;
2125     default:
2126         *write = 1;
2127         *read = 6;
2128         break;
2129     };
2130 }
2131
2132 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
2133 {
2134     size_t i;
2135     bool changed = false;
2136     bool tempbool;
2137     for (i = 0; i != vec_size(self->living); ++i)
2138     {
2139         tempbool = ir_value_life_merge(self->living[i], eid);
2140         /* debug
2141         if (tempbool)
2142             irerror(self->context, "block_living_add_instr() value instruction added %s: %i", self->living[i]->_name, (int)eid);
2143         */
2144         changed = changed || tempbool;
2145     }
2146     return changed;
2147 }
2148
2149 static bool ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
2150 {
2151     size_t i;
2152
2153     (void)changed;
2154
2155     /* values which have been read in a previous iteration are now
2156      * in the "living" array even if the previous block doesn't use them.
2157      * So we have to remove whatever does not exist in the previous block.
2158      * They will be re-added on-read, but the liferange merge won't cause
2159      * a change.
2160      */
2161     for (i = 0; i < vec_size(self->living); ++i)
2162     {
2163         if (!vec_ir_value_find(prev->living, self->living[i], NULL)) {
2164             vec_remove(self->living, i, 1);
2165             --i;
2166         }
2167     }
2168
2169     /* Whatever the previous block still has in its living set
2170      * must now be added to ours as well.
2171      */
2172     for (i = 0; i < vec_size(prev->living); ++i)
2173     {
2174         if (vec_ir_value_find(self->living, prev->living[i], NULL))
2175             continue;
2176         vec_push(self->living, prev->living[i]);
2177         /*
2178         irerror(self->contextt from prev: %s", self->label, prev->living[i]->_name);
2179         */
2180     }
2181     return true;
2182 }
2183
2184 static bool ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
2185 {
2186     ir_instr *instr;
2187     ir_value *value;
2188     bool  tempbool;
2189     size_t i, o, p;
2190     /* bitmasks which operands are read from or written to */
2191     size_t read, write;
2192     char dbg_ind[16] = { '#', '0' };
2193     (void)dbg_ind;
2194
2195     if (prev)
2196     {
2197         if (!ir_block_life_prop_previous(self, prev, changed))
2198             return false;
2199     }
2200
2201     i = vec_size(self->instr);
2202     while (i)
2203     { --i;
2204         instr = self->instr[i];
2205
2206         /* PHI operands are always read operands */
2207         for (p = 0; p < vec_size(instr->phi); ++p)
2208         {
2209             value = instr->phi[p].value;
2210             if (value->memberof)
2211                 value = value->memberof;
2212             if (!vec_ir_value_find(self->living, value, NULL))
2213                 vec_push(self->living, value);
2214         }
2215
2216         /* call params are read operands too */
2217         for (p = 0; p < vec_size(instr->params); ++p)
2218         {
2219             value = instr->params[p];
2220             if (value->memberof)
2221                 value = value->memberof;
2222             if (!vec_ir_value_find(self->living, value, NULL))
2223                 vec_push(self->living, value);
2224         }
2225
2226         /* See which operands are read and write operands */
2227         ir_op_read_write(instr->opcode, &read, &write);
2228
2229         if (instr->opcode == INSTR_MUL_VF)
2230         {
2231             /* the float source will get an additional lifetime */
2232             tempbool = ir_value_life_merge(instr->_ops[2], instr->eid+1);
2233             *changed = *changed || tempbool;
2234         }
2235         else if (instr->opcode == INSTR_MUL_FV)
2236         {
2237             /* the float source will get an additional lifetime */
2238             tempbool = ir_value_life_merge(instr->_ops[1], instr->eid+1);
2239             *changed = *changed || tempbool;
2240         }
2241
2242         /* Go through the 3 main operands */
2243         for (o = 0; o < 3; ++o)
2244         {
2245             if (!instr->_ops[o]) /* no such operand */
2246                 continue;
2247
2248             value = instr->_ops[o];
2249             if (value->memberof)
2250                 value = value->memberof;
2251
2252             /* We only care about locals */
2253             /* we also calculate parameter liferanges so that locals
2254              * can take up parameter slots */
2255             if (value->store != store_value &&
2256                 value->store != store_local &&
2257                 value->store != store_param)
2258                 continue;
2259
2260             /* read operands */
2261             if (read & (1<<o))
2262             {
2263                 if (!vec_ir_value_find(self->living, value, NULL))
2264                     vec_push(self->living, value);
2265             }
2266
2267             /* write operands */
2268             /* When we write to a local, we consider it "dead" for the
2269              * remaining upper part of the function, since in SSA a value
2270              * can only be written once (== created)
2271              */
2272             if (write & (1<<o))
2273             {
2274                 size_t idx;
2275                 bool in_living = vec_ir_value_find(self->living, value, &idx);
2276                 if (!in_living)
2277                 {
2278                     /* If the value isn't alive it hasn't been read before... */
2279                     /* TODO: See if the warning can be emitted during parsing or AST processing
2280                      * otherwise have warning printed here.
2281                      * IF printing a warning here: include filecontext_t,
2282                      * and make sure it's only printed once
2283                      * since this function is run multiple times.
2284                      */
2285                     /* For now: debug info: */
2286                     /* con_err( "Value only written %s\n", value->name); */
2287                     tempbool = ir_value_life_merge(value, instr->eid);
2288                     *changed = *changed || tempbool;
2289                     /*
2290                     ir_instr_dump(instr, dbg_ind, printf);
2291                     abort();
2292                     */
2293                 } else {
2294                     /* since 'living' won't contain it
2295                      * anymore, merge the value, since
2296                      * (A) doesn't.
2297                      */
2298                     tempbool = ir_value_life_merge(value, instr->eid);
2299                     /*
2300                     if (tempbool)
2301                         con_err( "value added id %s %i\n", value->name, (int)instr->eid);
2302                     */
2303                     *changed = *changed || tempbool;
2304                     /* Then remove */
2305                     vec_remove(self->living, idx, 1);
2306                 }
2307             }
2308         }
2309         /* (A) */
2310         tempbool = ir_block_living_add_instr(self, instr->eid);
2311         /*con_err( "living added values\n");*/
2312         *changed = *changed || tempbool;
2313
2314     }
2315
2316     if (self->run_id == self->owner->run_id)
2317         return true;
2318
2319     self->run_id = self->owner->run_id;
2320
2321     for (i = 0; i < vec_size(self->entries); ++i)
2322     {
2323         ir_block *entry = self->entries[i];
2324         ir_block_life_propagate(entry, self, changed);
2325     }
2326
2327     return true;
2328 }
2329
2330 /***********************************************************************
2331  *IR Code-Generation
2332  *
2333  * Since the IR has the convention of putting 'write' operands
2334  * at the beginning, we have to rotate the operands of instructions
2335  * properly in order to generate valid QCVM code.
2336  *
2337  * Having destinations at a fixed position is more convenient. In QC
2338  * this is *mostly* OPC,  but FTE adds at least 2 instructions which
2339  * read from from OPA,  and store to OPB rather than OPC.   Which is
2340  * partially the reason why the implementation of these instructions
2341  * in darkplaces has been delayed for so long.
2342  *
2343  * Breaking conventions is annoying...
2344  */
2345 static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool islocal);
2346
2347 static bool gen_global_field(ir_value *global)
2348 {
2349     if (global->isconst)
2350     {
2351         ir_value *fld = global->constval.vpointer;
2352         if (!fld) {
2353             irerror(global->context, "Invalid field constant with no field: %s", global->name);
2354             return false;
2355         }
2356
2357         /* Now, in this case, a relocation would be impossible to code
2358          * since it looks like this:
2359          * .vector v = origin;     <- parse error, wtf is 'origin'?
2360          * .vector origin;
2361          *
2362          * But we will need a general relocation support later anyway
2363          * for functions... might as well support that here.
2364          */
2365         if (!fld->code.globaladdr) {
2366             irerror(global->context, "FIXME: Relocation support");
2367             return false;
2368         }
2369
2370         /* copy the field's value */
2371         ir_value_code_setaddr(global, vec_size(code_globals));
2372         vec_push(code_globals, code_globals[fld->code.globaladdr]);
2373         if (global->fieldtype == TYPE_VECTOR) {
2374             vec_push(code_globals, code_globals[fld->code.globaladdr]+1);
2375             vec_push(code_globals, code_globals[fld->code.globaladdr]+2);
2376         }
2377     }
2378     else
2379     {
2380         ir_value_code_setaddr(global, vec_size(code_globals));
2381         vec_push(code_globals, 0);
2382         if (global->fieldtype == TYPE_VECTOR) {
2383             vec_push(code_globals, 0);
2384             vec_push(code_globals, 0);
2385         }
2386     }
2387     if (global->code.globaladdr < 0)
2388         return false;
2389     return true;
2390 }
2391
2392 static bool gen_global_pointer(ir_value *global)
2393 {
2394     if (global->isconst)
2395     {
2396         ir_value *target = global->constval.vpointer;
2397         if (!target) {
2398             irerror(global->context, "Invalid pointer constant: %s", global->name);
2399             /* NULL pointers are pointing to the NULL constant, which also
2400              * sits at address 0, but still has an ir_value for itself.
2401              */
2402             return false;
2403         }
2404
2405         /* Here, relocations ARE possible - in fteqcc-enhanced-qc:
2406          * void() foo; <- proto
2407          * void() *fooptr = &foo;
2408          * void() foo = { code }
2409          */
2410         if (!target->code.globaladdr) {
2411             /* FIXME: Check for the constant nullptr ir_value!
2412              * because then code.globaladdr being 0 is valid.
2413              */
2414             irerror(global->context, "FIXME: Relocation support");
2415             return false;
2416         }
2417
2418         ir_value_code_setaddr(global, vec_size(code_globals));
2419         vec_push(code_globals, target->code.globaladdr);
2420     }
2421     else
2422     {
2423         ir_value_code_setaddr(global, vec_size(code_globals));
2424         vec_push(code_globals, 0);
2425     }
2426     if (global->code.globaladdr < 0)
2427         return false;
2428     return true;
2429 }
2430
2431 static bool gen_blocks_recursive(ir_function *func, ir_block *block)
2432 {
2433     prog_section_statement stmt;
2434     ir_instr *instr;
2435     ir_block *target;
2436     ir_block *ontrue;
2437     ir_block *onfalse;
2438     size_t    stidx;
2439     size_t    i;
2440
2441 tailcall:
2442     block->generated = true;
2443     block->code_start = vec_size(code_statements);
2444     for (i = 0; i < vec_size(block->instr); ++i)
2445     {
2446         instr = block->instr[i];
2447
2448         if (instr->opcode == VINSTR_PHI) {
2449             irerror(block->context, "cannot generate virtual instruction (phi)");
2450             return false;
2451         }
2452
2453         if (instr->opcode == VINSTR_JUMP) {
2454             target = instr->bops[0];
2455             /* for uncoditional jumps, if the target hasn't been generated
2456              * yet, we generate them right here.
2457              */
2458             if (!target->generated) {
2459                 block = target;
2460                 goto tailcall;
2461             }
2462
2463             /* otherwise we generate a jump instruction */
2464             stmt.opcode = INSTR_GOTO;
2465             stmt.o1.s1 = (target->code_start) - vec_size(code_statements);
2466             stmt.o2.s1 = 0;
2467             stmt.o3.s1 = 0;
2468             vec_push(code_statements, stmt);
2469
2470             /* no further instructions can be in this block */
2471             return true;
2472         }
2473
2474         if (instr->opcode == VINSTR_COND) {
2475             ontrue  = instr->bops[0];
2476             onfalse = instr->bops[1];
2477             /* TODO: have the AST signal which block should
2478              * come first: eg. optimize IFs without ELSE...
2479              */
2480
2481             stmt.o1.u1 = ir_value_code_addr(instr->_ops[0]);
2482             stmt.o2.u1 = 0;
2483             stmt.o3.s1 = 0;
2484
2485             if (ontrue->generated) {
2486                 stmt.opcode = INSTR_IF;
2487                 stmt.o2.s1 = (ontrue->code_start) - vec_size(code_statements);
2488                 vec_push(code_statements, stmt);
2489             }
2490             if (onfalse->generated) {
2491                 stmt.opcode = INSTR_IFNOT;
2492                 stmt.o2.s1 = (onfalse->code_start) - vec_size(code_statements);
2493                 vec_push(code_statements, stmt);
2494             }
2495             if (!ontrue->generated) {
2496                 if (onfalse->generated) {
2497                     block = ontrue;
2498                     goto tailcall;
2499                 }
2500             }
2501             if (!onfalse->generated) {
2502                 if (ontrue->generated) {
2503                     block = onfalse;
2504                     goto tailcall;
2505                 }
2506             }
2507             /* neither ontrue nor onfalse exist */
2508             stmt.opcode = INSTR_IFNOT;
2509             if (!instr->likely) {
2510                 /* Honor the likelyhood hint */
2511                 ir_block *tmp = onfalse;
2512                 stmt.opcode = INSTR_IF;
2513                 onfalse = ontrue;
2514                 ontrue = tmp;
2515             }
2516             stidx = vec_size(code_statements);
2517             vec_push(code_statements, stmt);
2518             /* on false we jump, so add ontrue-path */
2519             if (!gen_blocks_recursive(func, ontrue))
2520                 return false;
2521             /* fixup the jump address */
2522             code_statements[stidx].o2.s1 = vec_size(code_statements) - stidx;
2523             /* generate onfalse path */
2524             if (onfalse->generated) {
2525                 /* fixup the jump address */
2526                 code_statements[stidx].o2.s1 = (onfalse->code_start) - (stidx);
2527                 stmt.opcode = vec_last(code_statements).opcode;
2528                 if (stmt.opcode == INSTR_GOTO ||
2529                     stmt.opcode == INSTR_IF ||
2530                     stmt.opcode == INSTR_IFNOT ||
2531                     stmt.opcode == INSTR_RETURN ||
2532                     stmt.opcode == INSTR_DONE)
2533                 {
2534                     /* no use jumping from here */
2535                     return true;
2536                 }
2537                 /* may have been generated in the previous recursive call */
2538                 stmt.opcode = INSTR_GOTO;
2539                 stmt.o1.s1 = (onfalse->code_start) - vec_size(code_statements);
2540                 stmt.o2.s1 = 0;
2541                 stmt.o3.s1 = 0;
2542                 vec_push(code_statements, stmt);
2543                 return true;
2544             }
2545             /* if not, generate now */
2546             block = onfalse;
2547             goto tailcall;
2548         }
2549
2550         if (instr->opcode >= INSTR_CALL0 && instr->opcode <= INSTR_CALL8) {
2551             /* Trivial call translation:
2552              * copy all params to OFS_PARM*
2553              * if the output's storetype is not store_return,
2554              * add append a STORE instruction!
2555              *
2556              * NOTES on how to do it better without much trouble:
2557              * -) The liferanges!
2558              *      Simply check the liferange of all parameters for
2559              *      other CALLs. For each param with no CALL in its
2560              *      liferange, we can store it in an OFS_PARM at
2561              *      generation already. This would even include later
2562              *      reuse.... probably... :)
2563              */
2564             size_t p, first;
2565             ir_value *retvalue;
2566
2567             first = vec_size(instr->params);
2568             if (first > 8)
2569                 first = 8;
2570             for (p = 0; p < first; ++p)
2571             {
2572                 ir_value *param = instr->params[p];
2573
2574                 stmt.opcode = INSTR_STORE_F;
2575                 stmt.o3.u1 = 0;
2576
2577                 if (param->vtype == TYPE_FIELD)
2578                     stmt.opcode = field_store_instr[param->fieldtype];
2579                 else
2580                     stmt.opcode = type_store_instr[param->vtype];
2581                 stmt.o1.u1 = ir_value_code_addr(param);
2582                 stmt.o2.u1 = OFS_PARM0 + 3 * p;
2583                 vec_push(code_statements, stmt);
2584             }
2585             /* Now handle extparams */
2586             first = vec_size(instr->params);
2587             for (; p < first; ++p)
2588             {
2589                 ir_builder *ir = func->owner;
2590                 ir_value *param = instr->params[p];
2591                 ir_value *targetparam;
2592
2593                 if (p-8 >= vec_size(ir->extparams)) {
2594                     irerror(instr->context, "Not enough extparam-globals have been created");
2595                     return false;
2596                 }
2597
2598                 targetparam = ir->extparams[p-8];
2599
2600                 stmt.opcode = INSTR_STORE_F;
2601                 stmt.o3.u1 = 0;
2602
2603                 if (param->vtype == TYPE_FIELD)
2604                     stmt.opcode = field_store_instr[param->fieldtype];
2605                 else
2606                     stmt.opcode = type_store_instr[param->vtype];
2607                 stmt.o1.u1 = ir_value_code_addr(param);
2608                 stmt.o2.u1 = ir_value_code_addr(targetparam);
2609                 vec_push(code_statements, stmt);
2610             }
2611
2612             stmt.opcode = INSTR_CALL0 + vec_size(instr->params);
2613             if (stmt.opcode > INSTR_CALL8)
2614                 stmt.opcode = INSTR_CALL8;
2615             stmt.o1.u1 = ir_value_code_addr(instr->_ops[1]);
2616             stmt.o2.u1 = 0;
2617             stmt.o3.u1 = 0;
2618             vec_push(code_statements, stmt);
2619
2620             retvalue = instr->_ops[0];
2621             if (retvalue && retvalue->store != store_return && vec_size(retvalue->life))
2622             {
2623                 /* not to be kept in OFS_RETURN */
2624                 if (retvalue->vtype == TYPE_FIELD)
2625                     stmt.opcode = field_store_instr[retvalue->vtype];
2626                 else
2627                     stmt.opcode = type_store_instr[retvalue->vtype];
2628                 stmt.o1.u1 = OFS_RETURN;
2629                 stmt.o2.u1 = ir_value_code_addr(retvalue);
2630                 stmt.o3.u1 = 0;
2631                 vec_push(code_statements, stmt);
2632             }
2633             continue;
2634         }
2635
2636         if (instr->opcode == INSTR_STATE) {
2637             irerror(block->context, "TODO: state instruction");
2638             return false;
2639         }
2640
2641         stmt.opcode = instr->opcode;
2642         stmt.o1.u1 = 0;
2643         stmt.o2.u1 = 0;
2644         stmt.o3.u1 = 0;
2645
2646         /* This is the general order of operands */
2647         if (instr->_ops[0])
2648             stmt.o3.u1 = ir_value_code_addr(instr->_ops[0]);
2649
2650         if (instr->_ops[1])
2651             stmt.o1.u1 = ir_value_code_addr(instr->_ops[1]);
2652
2653         if (instr->_ops[2])
2654             stmt.o2.u1 = ir_value_code_addr(instr->_ops[2]);
2655
2656         if (stmt.opcode == INSTR_RETURN || stmt.opcode == INSTR_DONE)
2657         {
2658             stmt.o1.u1 = stmt.o3.u1;
2659             stmt.o3.u1 = 0;
2660         }
2661         else if ((stmt.opcode >= INSTR_STORE_F &&
2662                   stmt.opcode <= INSTR_STORE_FNC) ||
2663                  (stmt.opcode >= INSTR_STOREP_F &&
2664                   stmt.opcode <= INSTR_STOREP_FNC))
2665         {
2666             /* 2-operand instructions with A -> B */
2667             stmt.o2.u1 = stmt.o3.u1;
2668             stmt.o3.u1 = 0;
2669         }
2670
2671         vec_push(code_statements, stmt);
2672     }
2673     return true;
2674 }
2675
2676 static bool gen_function_code(ir_function *self)
2677 {
2678     ir_block *block;
2679     prog_section_statement stmt;
2680
2681     /* Starting from entry point, we generate blocks "as they come"
2682      * for now. Dead blocks will not be translated obviously.
2683      */
2684     if (!vec_size(self->blocks)) {
2685         irerror(self->context, "Function '%s' declared without body.", self->name);
2686         return false;
2687     }
2688
2689     block = self->blocks[0];
2690     if (block->generated)
2691         return true;
2692
2693     if (!gen_blocks_recursive(self, block)) {
2694         irerror(self->context, "failed to generate blocks for '%s'", self->name);
2695         return false;
2696     }
2697
2698     /* otherwise code_write crashes since it debug-prints functions until AINSTR_END */
2699     stmt.opcode = AINSTR_END;
2700     stmt.o1.u1 = 0;
2701     stmt.o2.u1 = 0;
2702     stmt.o3.u1 = 0;
2703     vec_push(code_statements, stmt);
2704     return true;
2705 }
2706
2707 static qcint ir_builder_filestring(ir_builder *ir, const char *filename)
2708 {
2709     /* NOTE: filename pointers are copied, we never strdup them,
2710      * thus we can use pointer-comparison to find the string.
2711      */
2712     size_t i;
2713     qcint  str;
2714
2715     for (i = 0; i < vec_size(ir->filenames); ++i) {
2716         if (ir->filenames[i] == filename)
2717             return ir->filestrings[i];
2718     }
2719
2720     str = code_genstring(filename);
2721     vec_push(ir->filenames, filename);
2722     vec_push(ir->filestrings, str);
2723     return str;
2724 }
2725
2726 static bool gen_global_function(ir_builder *ir, ir_value *global)
2727 {
2728     prog_section_function fun;
2729     ir_function          *irfun;
2730
2731     size_t i;
2732     size_t local_var_end;
2733
2734     if (!global->isconst || (!global->constval.vfunc))
2735     {
2736         irerror(global->context, "Invalid state of function-global: not constant: %s", global->name);
2737         return false;
2738     }
2739
2740     irfun = global->constval.vfunc;
2741
2742     fun.name    = global->code.name;
2743     fun.file    = ir_builder_filestring(ir, global->context.file);
2744     fun.profile = 0; /* always 0 */
2745     fun.nargs   = vec_size(irfun->params);
2746     if (fun.nargs > 8)
2747         fun.nargs = 8;
2748
2749     for (i = 0;i < 8; ++i) {
2750         if (i >= fun.nargs)
2751             fun.argsize[i] = 0;
2752         else
2753             fun.argsize[i] = type_sizeof[irfun->params[i]];
2754     }
2755
2756     fun.firstlocal = vec_size(code_globals);
2757
2758     local_var_end = fun.firstlocal;
2759     for (i = 0; i < vec_size(irfun->locals); ++i) {
2760         if (!ir_builder_gen_global(ir, irfun->locals[i], true)) {
2761             irerror(irfun->locals[i]->context, "Failed to generate local %s", irfun->locals[i]->name);
2762             return false;
2763         }
2764     }
2765     if (vec_size(irfun->locals)) {
2766         ir_value *last = vec_last(irfun->locals);
2767         local_var_end = last->code.globaladdr;
2768         local_var_end += type_sizeof[last->vtype];
2769     }
2770     for (i = 0; i < vec_size(irfun->values); ++i)
2771     {
2772         /* generate code.globaladdr for ssa values */
2773         ir_value *v = irfun->values[i];
2774         ir_value_code_setaddr(v, local_var_end + v->code.local);
2775     }
2776     for (i = 0; i < irfun->allocated_locals; ++i) {
2777         /* fill the locals with zeros */
2778         vec_push(code_globals, 0);
2779     }
2780
2781     fun.locals = vec_size(code_globals) - fun.firstlocal;
2782
2783     if (irfun->builtin)
2784         fun.entry = irfun->builtin;
2785     else {
2786         irfun->code_function_def = vec_size(code_functions);
2787         fun.entry = vec_size(code_statements);
2788     }
2789
2790     vec_push(code_functions, fun);
2791     return true;
2792 }
2793
2794 static void ir_gen_extparam(ir_builder *ir)
2795 {
2796     prog_section_def def;
2797     ir_value        *global;
2798     char             name[128];
2799
2800     snprintf(name, sizeof(name), "EXTPARM#%i", (int)(vec_size(ir->extparams)+8));
2801     global = ir_value_var(name, store_global, TYPE_VECTOR);
2802
2803     def.name = code_genstring(name);
2804     def.type = TYPE_VECTOR;
2805     def.offset = vec_size(code_globals);
2806
2807     vec_push(code_defs, def);
2808     ir_value_code_setaddr(global, def.offset);
2809     vec_push(code_globals, 0);
2810     vec_push(code_globals, 0);
2811     vec_push(code_globals, 0);
2812
2813     vec_push(ir->extparams, global);
2814 }
2815
2816 static bool gen_function_extparam_copy(ir_function *self)
2817 {
2818     size_t i, ext, numparams;
2819
2820     ir_builder *ir = self->owner;
2821     ir_value   *ep;
2822     prog_section_statement stmt;
2823
2824     numparams = vec_size(self->params);
2825     if (!numparams)
2826         return true;
2827
2828     stmt.opcode = INSTR_STORE_F;
2829     stmt.o3.s1 = 0;
2830     for (i = 8; i < numparams; ++i) {
2831         ext = i - 8;
2832         if (ext >= vec_size(ir->extparams))
2833             ir_gen_extparam(ir);
2834
2835         ep = ir->extparams[ext];
2836
2837         stmt.opcode = type_store_instr[self->locals[i]->vtype];
2838         if (self->locals[i]->vtype == TYPE_FIELD &&
2839             self->locals[i]->fieldtype == TYPE_VECTOR)
2840         {
2841             stmt.opcode = INSTR_STORE_V;
2842         }
2843         stmt.o1.u1 = ir_value_code_addr(ep);
2844         stmt.o2.u1 = ir_value_code_addr(self->locals[i]);
2845         vec_push(code_statements, stmt);
2846     }
2847
2848     return true;
2849 }
2850
2851 static bool gen_global_function_code(ir_builder *ir, ir_value *global)
2852 {
2853     prog_section_function *fundef;
2854     ir_function           *irfun;
2855
2856     (void)ir;
2857
2858     irfun = global->constval.vfunc;
2859     if (!irfun) {
2860         irwarning(global->context, WARN_IMPLICIT_FUNCTION_POINTER,
2861                   "function `%s` has no body and in QC implicitly becomes a function-pointer", global->name);
2862         /* this was a function pointer, don't generate code for those */
2863         return true;
2864     }
2865
2866     if (irfun->builtin)
2867         return true;
2868
2869     if (irfun->code_function_def < 0) {
2870         irerror(irfun->context, "`%s`: IR global wasn't generated, failed to access function-def", irfun->name);
2871         return false;
2872     }
2873     fundef = &code_functions[irfun->code_function_def];
2874
2875     fundef->entry = vec_size(code_statements);
2876     if (!gen_function_extparam_copy(irfun)) {
2877         irerror(irfun->context, "Failed to generate extparam-copy code for function %s", irfun->name);
2878         return false;
2879     }
2880     if (!gen_function_code(irfun)) {
2881         irerror(irfun->context, "Failed to generate code for function %s", irfun->name);
2882         return false;
2883     }
2884     return true;
2885 }
2886
2887 static bool ir_builder_gen_global(ir_builder *self, ir_value *global, bool islocal)
2888 {
2889     size_t           i;
2890     int32_t         *iptr;
2891     prog_section_def def;
2892
2893     def.type   = global->vtype;
2894     def.offset = vec_size(code_globals);
2895
2896     if (global->name) {
2897         if (global->name[0] == '#') {
2898             if (!self->str_immediate)
2899                 self->str_immediate = code_genstring("IMMEDIATE");
2900             def.name = global->code.name = self->str_immediate;
2901         }
2902         else
2903             def.name = global->code.name = code_genstring(global->name);
2904     }
2905     else
2906         def.name   = 0;
2907
2908     switch (global->vtype)
2909     {
2910     case TYPE_VOID:
2911         if (!strcmp(global->name, "end_sys_globals")) {
2912             /* TODO: remember this point... all the defs before this one
2913              * should be checksummed and added to progdefs.h when we generate it.
2914              */
2915         }
2916         else if (!strcmp(global->name, "end_sys_fields")) {
2917             /* TODO: same as above but for entity-fields rather than globsl
2918              */
2919         }
2920         else
2921             irwarning(global->context, WARN_VOID_VARIABLES, "unrecognized variable of type void `%s`",
2922                       global->name);
2923         /* I'd argue setting it to 0 is sufficient, but maybe some depend on knowing how far
2924          * the system fields actually go? Though the engine knows this anyway...
2925          * Maybe this could be an -foption
2926          * fteqcc creates data for end_sys_* - of size 1, so let's do the same
2927          */
2928         ir_value_code_setaddr(global, vec_size(code_globals));
2929         vec_push(code_globals, 0);
2930         /* Add the def */
2931         vec_push(code_defs, def);
2932         return true;
2933     case TYPE_POINTER:
2934         vec_push(code_defs, def);
2935         return gen_global_pointer(global);
2936     case TYPE_FIELD:
2937         vec_push(code_defs, def);
2938         return gen_global_field(global);
2939     case TYPE_ENTITY:
2940         /* fall through */
2941     case TYPE_FLOAT:
2942     {
2943         ir_value_code_setaddr(global, vec_size(code_globals));
2944         if (global->isconst) {
2945             iptr = (int32_t*)&global->constval.ivec[0];
2946             vec_push(code_globals, *iptr);
2947         } else {
2948             vec_push(code_globals, 0);
2949             if (!islocal)
2950                 def.type |= DEF_SAVEGLOBAL;
2951         }
2952         vec_push(code_defs, def);
2953
2954         return global->code.globaladdr >= 0;
2955     }
2956     case TYPE_STRING:
2957     {
2958         ir_value_code_setaddr(global, vec_size(code_globals));
2959         if (global->isconst) {
2960             vec_push(code_globals, code_genstring(global->constval.vstring));
2961         } else {
2962             vec_push(code_globals, 0);
2963             if (!islocal)
2964                 def.type |= DEF_SAVEGLOBAL;
2965         }
2966         vec_push(code_defs, def);
2967         return global->code.globaladdr >= 0;
2968     }
2969     case TYPE_VECTOR:
2970     {
2971         size_t d;
2972         ir_value_code_setaddr(global, vec_size(code_globals));
2973         if (global->isconst) {
2974             iptr = (int32_t*)&global->constval.ivec[0];
2975             vec_push(code_globals, iptr[0]);
2976             if (global->code.globaladdr < 0)
2977                 return false;
2978             for (d = 1; d < type_sizeof[global->vtype]; ++d)
2979             {
2980                 vec_push(code_globals, iptr[d]);
2981             }
2982         } else {
2983             vec_push(code_globals, 0);
2984             if (global->code.globaladdr < 0)
2985                 return false;
2986             for (d = 1; d < type_sizeof[global->vtype]; ++d)
2987             {
2988                 vec_push(code_globals, 0);
2989             }
2990             if (!islocal)
2991                 def.type |= DEF_SAVEGLOBAL;
2992         }
2993
2994         vec_push(code_defs, def);
2995         return global->code.globaladdr >= 0;
2996     }
2997     case TYPE_FUNCTION:
2998         ir_value_code_setaddr(global, vec_size(code_globals));
2999         if (!global->isconst) {
3000             vec_push(code_globals, 0);
3001             if (global->code.globaladdr < 0)
3002                 return false;
3003         } else {
3004             vec_push(code_globals, vec_size(code_functions));
3005             if (!gen_global_function(self, global))
3006                 return false;
3007             if (!islocal)
3008                 def.type |= DEF_SAVEGLOBAL;
3009         }
3010         vec_push(code_defs, def);
3011         return true;
3012     case TYPE_VARIANT:
3013         /* assume biggest type */
3014             ir_value_code_setaddr(global, vec_size(code_globals));
3015             vec_push(code_globals, 0);
3016             for (i = 1; i < type_sizeof[TYPE_VARIANT]; ++i)
3017                 vec_push(code_globals, 0);
3018             return true;
3019     default:
3020         /* refuse to create 'void' type or any other fancy business. */
3021         irerror(global->context, "Invalid type for global variable `%s`: %s",
3022                 global->name, type_name[global->vtype]);
3023         return false;
3024     }
3025 }
3026
3027 static bool ir_builder_gen_field(ir_builder *self, ir_value *field)
3028 {
3029     prog_section_def def;
3030     prog_section_field fld;
3031
3032     (void)self;
3033
3034     def.type   = (uint16_t)field->vtype;
3035     def.offset = (uint16_t)vec_size(code_globals);
3036
3037     /* create a global named the same as the field */
3038     if (opts_standard == COMPILER_GMQCC) {
3039         /* in our standard, the global gets a dot prefix */
3040         size_t len = strlen(field->name);
3041         char name[1024];
3042
3043         /* we really don't want to have to allocate this, and 1024
3044          * bytes is more than enough for a variable/field name
3045          */
3046         if (len+2 >= sizeof(name)) {
3047             irerror(field->context, "invalid field name size: %u", (unsigned int)len);
3048             return false;
3049         }
3050
3051         name[0] = '.';
3052         memcpy(name+1, field->name, len); /* no strncpy - we used strlen above */
3053         name[len+1] = 0;
3054
3055         def.name = code_genstring(name);
3056         fld.name = def.name + 1; /* we reuse that string table entry */
3057     } else {
3058         /* in plain QC, there cannot be a global with the same name,
3059          * and so we also name the global the same.
3060          * FIXME: fteqcc should create a global as well
3061          * check if it actually uses the same name. Probably does
3062          */
3063         def.name = code_genstring(field->name);
3064         fld.name = def.name;
3065     }
3066
3067     field->code.name = def.name;
3068
3069     vec_push(code_defs, def);
3070
3071     fld.type = field->fieldtype;
3072
3073     if (fld.type == TYPE_VOID) {
3074         irerror(field->context, "field is missing a type: %s - don't know its size", field->name);
3075         return false;
3076     }
3077
3078     fld.offset = code_alloc_field(type_sizeof[field->fieldtype]);
3079
3080     vec_push(code_fields, fld);
3081
3082     ir_value_code_setaddr(field, vec_size(code_globals));
3083     vec_push(code_globals, fld.offset);
3084     if (fld.type == TYPE_VECTOR) {
3085         vec_push(code_globals, fld.offset+1);
3086         vec_push(code_globals, fld.offset+2);
3087     }
3088
3089     return field->code.globaladdr >= 0;
3090 }
3091
3092 bool ir_builder_generate(ir_builder *self, const char *filename)
3093 {
3094     prog_section_statement stmt;
3095     size_t i;
3096
3097     code_init();
3098
3099     for (i = 0; i < vec_size(self->globals); ++i)
3100     {
3101         if (!ir_builder_gen_global(self, self->globals[i], false)) {
3102             return false;
3103         }
3104     }
3105
3106     for (i = 0; i < vec_size(self->fields); ++i)
3107     {
3108         if (!ir_builder_gen_field(self, self->fields[i])) {
3109             return false;
3110         }
3111     }
3112
3113     /* generate function code */
3114     for (i = 0; i < vec_size(self->globals); ++i)
3115     {
3116         if (self->globals[i]->vtype == TYPE_FUNCTION) {
3117             if (!gen_global_function_code(self, self->globals[i])) {
3118                 return false;
3119             }
3120         }
3121     }
3122
3123     if (vec_size(code_globals) >= 65536) {
3124         irerror(vec_last(self->globals)->context, "This progs file would require more globals than the metadata can handle. Bailing out.");
3125         return false;
3126     }
3127
3128     /* DP errors if the last instruction is not an INSTR_DONE
3129      * and for debugging purposes we add an additional AINSTR_END
3130      * to the end of functions, so here it goes:
3131      */
3132     stmt.opcode = INSTR_DONE;
3133     stmt.o1.u1 = 0;
3134     stmt.o2.u1 = 0;
3135     stmt.o3.u1 = 0;
3136     vec_push(code_statements, stmt);
3137
3138     if (!opts_pp_only)
3139         con_out("writing '%s'...\n", filename);
3140     return code_write(filename);
3141 }
3142
3143 /***********************************************************************
3144  *IR DEBUG Dump functions...
3145  */
3146
3147 #define IND_BUFSZ 1024
3148
3149 #ifdef WIN32
3150 # define strncat(dst, src, sz) strncat_s(dst, sz, src, _TRUNCATE)
3151 #endif
3152
3153 const char *qc_opname(int op)
3154 {
3155     if (op < 0) return "<INVALID>";
3156     if (op < (int)( sizeof(asm_instr) / sizeof(asm_instr[0]) ))
3157         return asm_instr[op].m;
3158     switch (op) {
3159         case VINSTR_PHI:  return "PHI";
3160         case VINSTR_JUMP: return "JUMP";
3161         case VINSTR_COND: return "COND";
3162         default:          return "<UNK>";
3163     }
3164 }
3165
3166 void ir_builder_dump(ir_builder *b, int (*oprintf)(const char*, ...))
3167 {
3168     size_t i;
3169     char indent[IND_BUFSZ];
3170     indent[0] = '\t';
3171     indent[1] = 0;
3172
3173     oprintf("module %s\n", b->name);
3174     for (i = 0; i < vec_size(b->globals); ++i)
3175     {
3176         oprintf("global ");
3177         if (b->globals[i]->isconst)
3178             oprintf("%s = ", b->globals[i]->name);
3179         ir_value_dump(b->globals[i], oprintf);
3180         oprintf("\n");
3181     }
3182     for (i = 0; i < vec_size(b->functions); ++i)
3183         ir_function_dump(b->functions[i], indent, oprintf);
3184     oprintf("endmodule %s\n", b->name);
3185 }
3186
3187 void ir_function_dump(ir_function *f, char *ind,
3188                       int (*oprintf)(const char*, ...))
3189 {
3190     size_t i;
3191     if (f->builtin != 0) {
3192         oprintf("%sfunction %s = builtin %i\n", ind, f->name, -f->builtin);
3193         return;
3194     }
3195     oprintf("%sfunction %s\n", ind, f->name);
3196     strncat(ind, "\t", IND_BUFSZ);
3197     if (vec_size(f->locals))
3198     {
3199         oprintf("%s%i locals:\n", ind, (int)vec_size(f->locals));
3200         for (i = 0; i < vec_size(f->locals); ++i) {
3201             oprintf("%s\t", ind);
3202             ir_value_dump(f->locals[i], oprintf);
3203             oprintf("\n");
3204         }
3205     }
3206     oprintf("%sliferanges:\n", ind);
3207     for (i = 0; i < vec_size(f->locals); ++i) {
3208         size_t l;
3209         ir_value *v = f->locals[i];
3210         oprintf("%s\t%s: unique ", ind, v->name);
3211         for (l = 0; l < vec_size(v->life); ++l) {
3212             oprintf("[%i,%i] ", v->life[l].start, v->life[l].end);
3213         }
3214         oprintf("\n");
3215     }
3216     for (i = 0; i < vec_size(f->values); ++i) {
3217         size_t l;
3218         ir_value *v = f->values[i];
3219         oprintf("%s\t%s: @%i ", ind, v->name, (int)v->code.local);
3220         for (l = 0; l < vec_size(v->life); ++l) {
3221             oprintf("[%i,%i] ", v->life[l].start, v->life[l].end);
3222         }
3223         oprintf("\n");
3224     }
3225     if (vec_size(f->blocks))
3226     {
3227         oprintf("%slife passes (check): %i\n", ind, (int)f->run_id);
3228         for (i = 0; i < vec_size(f->blocks); ++i) {
3229             if (f->blocks[i]->run_id != f->run_id) {
3230                 oprintf("%slife pass check fail! %i != %i\n", ind, (int)f->blocks[i]->run_id, (int)f->run_id);
3231             }
3232             ir_block_dump(f->blocks[i], ind, oprintf);
3233         }
3234
3235     }
3236     ind[strlen(ind)-1] = 0;
3237     oprintf("%sendfunction %s\n", ind, f->name);
3238 }
3239
3240 void ir_block_dump(ir_block* b, char *ind,
3241                    int (*oprintf)(const char*, ...))
3242 {
3243     size_t i;
3244     oprintf("%s:%s\n", ind, b->label);
3245     strncat(ind, "\t", IND_BUFSZ);
3246
3247     for (i = 0; i < vec_size(b->instr); ++i)
3248         ir_instr_dump(b->instr[i], ind, oprintf);
3249     ind[strlen(ind)-1] = 0;
3250 }
3251
3252 void dump_phi(ir_instr *in, int (*oprintf)(const char*, ...))
3253 {
3254     size_t i;
3255     oprintf("%s <- phi ", in->_ops[0]->name);
3256     for (i = 0; i < vec_size(in->phi); ++i)
3257     {
3258         oprintf("([%s] : %s) ", in->phi[i].from->label,
3259                                 in->phi[i].value->name);
3260     }
3261     oprintf("\n");
3262 }
3263
3264 void ir_instr_dump(ir_instr *in, char *ind,
3265                        int (*oprintf)(const char*, ...))
3266 {
3267     size_t i;
3268     const char *comma = NULL;
3269
3270     oprintf("%s (%i) ", ind, (int)in->eid);
3271
3272     if (in->opcode == VINSTR_PHI) {
3273         dump_phi(in, oprintf);
3274         return;
3275     }
3276
3277     strncat(ind, "\t", IND_BUFSZ);
3278
3279     if (in->_ops[0] && (in->_ops[1] || in->_ops[2])) {
3280         ir_value_dump(in->_ops[0], oprintf);
3281         if (in->_ops[1] || in->_ops[2])
3282             oprintf(" <- ");
3283     }
3284     if (in->opcode == INSTR_CALL0) {
3285         oprintf("CALL%i\t", vec_size(in->params));
3286     } else
3287         oprintf("%s\t", qc_opname(in->opcode));
3288
3289     if (in->_ops[0] && !(in->_ops[1] || in->_ops[2])) {
3290         ir_value_dump(in->_ops[0], oprintf);
3291         comma = ",\t";
3292     }
3293     else
3294     {
3295         for (i = 1; i != 3; ++i) {
3296             if (in->_ops[i]) {
3297                 if (comma)
3298                     oprintf(comma);
3299                 ir_value_dump(in->_ops[i], oprintf);
3300                 comma = ",\t";
3301             }
3302         }
3303     }
3304     if (in->bops[0]) {
3305         if (comma)
3306             oprintf(comma);
3307         oprintf("[%s]", in->bops[0]->label);
3308         comma = ",\t";
3309     }
3310     if (in->bops[1])
3311         oprintf("%s[%s]", comma, in->bops[1]->label);
3312     if (vec_size(in->params)) {
3313         oprintf("\tparams: ");
3314         for (i = 0; i != vec_size(in->params); ++i) {
3315             oprintf("%s, ", in->params[i]->name);
3316         }
3317     }
3318     oprintf("\n");
3319     ind[strlen(ind)-1] = 0;
3320 }
3321
3322 void ir_value_dump_string(const char *str, int (*oprintf)(const char*, ...))
3323 {
3324     oprintf("\"");
3325     for (; *str; ++str) {
3326         switch (*str) {
3327             case '\n': oprintf("\\n"); break;
3328             case '\r': oprintf("\\r"); break;
3329             case '\t': oprintf("\\t"); break;
3330             case '\v': oprintf("\\v"); break;
3331             case '\f': oprintf("\\f"); break;
3332             case '\b': oprintf("\\b"); break;
3333             case '\a': oprintf("\\a"); break;
3334             case '\\': oprintf("\\\\"); break;
3335             case '"': oprintf("\\\""); break;
3336             default: oprintf("%c", *str); break;
3337         }
3338     }
3339     oprintf("\"");
3340 }
3341
3342 void ir_value_dump(ir_value* v, int (*oprintf)(const char*, ...))
3343 {
3344     if (v->isconst) {
3345         switch (v->vtype) {
3346             default:
3347             case TYPE_VOID:
3348                 oprintf("(void)");
3349                 break;
3350             case TYPE_FUNCTION:
3351                 oprintf("fn:%s", v->name);
3352                 break;
3353             case TYPE_FLOAT:
3354                 oprintf("%g", v->constval.vfloat);
3355                 break;
3356             case TYPE_VECTOR:
3357                 oprintf("'%g %g %g'",
3358                         v->constval.vvec.x,
3359                         v->constval.vvec.y,
3360                         v->constval.vvec.z);
3361                 break;
3362             case TYPE_ENTITY:
3363                 oprintf("(entity)");
3364                 break;
3365             case TYPE_STRING:
3366                 ir_value_dump_string(v->constval.vstring, oprintf);
3367                 break;
3368 #if 0
3369             case TYPE_INTEGER:
3370                 oprintf("%i", v->constval.vint);
3371                 break;
3372 #endif
3373             case TYPE_POINTER:
3374                 oprintf("&%s",
3375                     v->constval.vpointer->name);
3376                 break;
3377         }
3378     } else {
3379         oprintf("%s", v->name);
3380     }
3381 }
3382
3383 void ir_value_dump_life(const ir_value *self, int (*oprintf)(const char*,...))
3384 {
3385     size_t i;
3386     oprintf("Life of %12s:", self->name);
3387     for (i = 0; i < vec_size(self->life); ++i)
3388     {
3389         oprintf(" + [%i, %i]\n", self->life[i].start, self->life[i].end);
3390     }
3391 }