ir.c

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