ir.c

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