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