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