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