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