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