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