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