ir.c

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