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