ir.c

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