ir.c

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