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