ir.c

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