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