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  *IR Builder
  30  */
  31
  32 ir_builder* ir_builder_new(const char *modulename)
  33 {
  34     ir_builder* self;
  35
  36     self = (ir_builder*)mem_a(sizeof(*self));
  37     MEM_VECTOR_INIT(self, functions);
  38     MEM_VECTOR_INIT(self, globals);
  39     self->name = NULL;
  40     ir_builder_set_name(self, modulename);
  41
  42     /* globals which always exist */
  43
  44     /* for now we give it a vector size */
  45     ir_builder_create_global(self, "OFS_RETURN", qc_variant);
  46
  47     return self;
  48 }
  49
  50 MEM_VEC_FUNCTIONS(ir_builder, ir_value*, globals)
  51 MEM_VEC_FUNCTIONS(ir_builder, ir_function*, functions)
  52
  53 void ir_builder_delete(ir_builder* self)
  54 {
  55     size_t i;
  56     mem_d((void*)self->name);
  57     for (i = 0; i != self->functions_count; ++i) {
  58         ir_function_delete(self->functions[i]);
  59     }
  60     MEM_VECTOR_CLEAR(self, functions);
  61     for (i = 0; i != self->globals_count; ++i) {
  62         ir_value_delete(self->globals[i]);
  63     }
  64     MEM_VECTOR_CLEAR(self, globals);
  65     mem_d(self);
  66 }
  67
  68 void ir_builder_set_name(ir_builder *self, const char *name)
  69 {
  70     if (self->name)
  71         mem_d((void*)self->name);
  72     self->name = util_strdup(name);
  73 }
  74
  75 ir_function* ir_builder_get_function(ir_builder *self, const char *name)
  76 {
  77     size_t i;
  78     for (i = 0; i < self->functions_count; ++i) {
  79         if (!strcmp(name, self->functions[i]->name))
  80             return self->functions[i];
  81     }
  82     return NULL;
  83 }
  84
  85 ir_function* ir_builder_create_function(ir_builder *self, const char *name)
  86 {
  87     ir_function *fn = ir_builder_get_function(self, name);
  88     if (fn) {
  89         return NULL;
  90     }
  91
  92     fn = ir_function_new(self);
  93     ir_function_set_name(fn, name);
  94     ir_builder_functions_add(self, fn);
  95     return fn;
  96 }
  97
  98 ir_value* ir_builder_get_global(ir_builder *self, const char *name)
  99 {
 100     size_t i;
 101     for (i = 0; i < self->globals_count; ++i) {
 102         if (!strcmp(self->globals[i]->name, name))
 103             return self->globals[i];
 104     }
 105     return NULL;
 106 }
 107
 108 ir_value* ir_builder_create_global(ir_builder *self, const char *name, int vtype)
 109 {
 110     ir_value *ve = ir_builder_get_global(self, name);
 111     if (ve) {
 112         return NULL;
 113     }
 114
 115     ve = ir_value_var(name, store_global, vtype);
 116     ir_builder_globals_add(self, ve);
 117     return ve;
 118 }
 119
 120 /***********************************************************************
 121  *IR Function
 122  */
 123
 124 void ir_function_naive_phi(ir_function*);
 125 void ir_function_enumerate(ir_function*);
 126 void ir_function_calculate_liferanges(ir_function*);
 127
 128 ir_function* ir_function_new(ir_builder* owner)
 129 {
 130     ir_function *self;
 131     self = (ir_function*)mem_a(sizeof(*self));
 132     self->owner = owner;
 133     self->context.file = "<@no context>";
 134     self->context.line = 0;
 135     self->retype = qc_void;
 136     MEM_VECTOR_INIT(self, params);
 137     MEM_VECTOR_INIT(self, blocks);
 138     MEM_VECTOR_INIT(self, values);
 139     MEM_VECTOR_INIT(self, locals);
 140     ir_function_set_name(self, "<@unnamed>");
 141
 142     self->run_id = 0;
 143     return self;
 144 }
 145 MEM_VEC_FUNCTIONS(ir_function, ir_value*, values)
 146 MEM_VEC_FUNCTIONS(ir_function, ir_block*, blocks)
 147 MEM_VEC_FUNCTIONS(ir_function, ir_value*, locals)
 148
 149 void ir_function_set_name(ir_function *self, const char *name)
 150 {
 151     if (self->name)
 152         mem_d((void*)self->name);
 153     self->name = util_strdup(name);
 154 }
 155
 156 void ir_function_delete(ir_function *self)
 157 {
 158     size_t i;
 159     mem_d((void*)self->name);
 160
 161     for (i = 0; i != self->blocks_count; ++i)
 162         ir_block_delete(self->blocks[i]);
 163     MEM_VECTOR_CLEAR(self, blocks);
 164
 165     MEM_VECTOR_CLEAR(self, params);
 166
 167     for (i = 0; i != self->values_count; ++i)
 168         ir_value_delete(self->values[i]);
 169     MEM_VECTOR_CLEAR(self, values);
 170
 171     for (i = 0; i != self->locals_count; ++i)
 172         ir_value_delete(self->locals[i]);
 173     MEM_VECTOR_CLEAR(self, locals);
 174
 175     mem_d(self);
 176 }
 177
 178 void ir_function_collect_value(ir_function *self, ir_value *v)
 179 {
 180     ir_function_values_add(self, v);
 181 }
 182
 183 ir_block* ir_function_create_block(ir_function *self, const char *label)
 184 {
 185     ir_block* bn = ir_block_new(self, label);
 186     memcpy(&bn->context, &self->context, sizeof(self->context));
 187     ir_function_blocks_add(self, bn);
 188     return bn;
 189 }
 190
 191 void ir_function_finalize(ir_function *self)
 192 {
 193     ir_function_naive_phi(self);
 194     ir_function_enumerate(self);
 195     ir_function_calculate_liferanges(self);
 196 }
 197
 198 ir_value* ir_function_get_local(ir_function *self, const char *name)
 199 {
 200     size_t i;
 201     for (i = 0; i < self->locals_count; ++i) {
 202         if (!strcmp(self->locals[i]->name, name))
 203             return self->locals[i];
 204     }
 205     return NULL;
 206 }
 207
 208 ir_value* ir_function_create_local(ir_function *self, const char *name, int vtype)
 209 {
 210     ir_value *ve = ir_function_get_local(self, name);
 211     if (ve) {
 212         return NULL;
 213     }
 214
 215     ve = ir_value_var(name, store_local, vtype);
 216     ir_function_locals_add(self, ve);
 217     return ve;
 218 }
 219
 220 /***********************************************************************
 221  *IR Block
 222  */
 223
 224 ir_block* ir_block_new(ir_function* owner, const char *name)
 225 {
 226     ir_block *self;
 227     self = (ir_block*)mem_a(sizeof(*self));
 228     self->owner = owner;
 229     self->context.file = "<@no context>";
 230     self->context.line = 0;
 231     self->final = false;
 232     MEM_VECTOR_INIT(self, instr);
 233     MEM_VECTOR_INIT(self, entries);
 234     MEM_VECTOR_INIT(self, exits);
 235     self->label = NULL;
 236     ir_block_set_label(self, name);
 237
 238     self->eid = 0;
 239     self->is_return = false;
 240     self->run_id = 0;
 241     MEM_VECTOR_INIT(self, living);
 242     return self;
 243 }
 244 MEM_VEC_FUNCTIONS(ir_block, ir_instr*, instr)
 245 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, entries)
 246 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_block*, exits)
 247 MEM_VEC_FUNCTIONS_ALL(ir_block, ir_value*, living)
 248
 249 void ir_block_delete(ir_block* self)
 250 {
 251     size_t i;
 252     mem_d((void*)self->label);
 253     for (i = 0; i != self->instr_count; ++i)
 254         ir_instr_delete(self->instr[i]);
 255     MEM_VECTOR_CLEAR(self, instr);
 256     MEM_VECTOR_CLEAR(self, entries);
 257     MEM_VECTOR_CLEAR(self, exits);
 258     MEM_VECTOR_CLEAR(self, living);
 259     mem_d(self);
 260 }
 261
 262 void ir_block_set_label(ir_block *self, const char *name)
 263 {
 264     if (self->label)
 265         mem_d((void*)self->label);
 266     self->label = util_strdup(name);
 267 }
 268
 269 /***********************************************************************
 270  *IR Instructions
 271  */
 272
 273 ir_instr* ir_instr_new(ir_block* owner, int op)
 274 {
 275     ir_instr *self;
 276     self = (ir_instr*)mem_a(sizeof(*self));
 277     self->owner = owner;
 278     self->context.file = "<@no context>";
 279     self->context.line = 0;
 280     self->opcode = op;
 281     self->_ops[0] = NULL;
 282     self->_ops[1] = NULL;
 283     self->_ops[2] = NULL;
 284     self->bops[0] = NULL;
 285     self->bops[1] = NULL;
 286     MEM_VECTOR_INIT(self, phi);
 287
 288     self->eid = 0;
 289     return self;
 290 }
 291 MEM_VEC_FUNCTIONS(ir_instr, ir_phi_entry_t, phi)
 292
 293 void ir_instr_delete(ir_instr *self)
 294 {
 295     ir_instr_op(self, 0, NULL, false);
 296     ir_instr_op(self, 1, NULL, false);
 297     ir_instr_op(self, 2, NULL, false);
 298     MEM_VECTOR_CLEAR(self, phi);
 299     mem_d(self);
 300 }
 301
 302 void ir_instr_op(ir_instr *self, int op, ir_value *v, bool writing)
 303 {
 304     if (self->_ops[op]) {
 305         if (writing)
 306             ir_value_writes_add(self->_ops[op], self);
 307         else
 308             ir_value_reads_add(self->_ops[op], self);
 309     }
 310     if (v) {
 311         if (writing)
 312             ir_value_writes_add(v, self);
 313         else
 314             ir_value_reads_add(v, self);
 315     }
 316     self->_ops[op] = v;
 317 }
 318
 319 /***********************************************************************
 320  *IR Value
 321  */
 322
 323 ir_value* ir_value_var(const char *name, int storetype, int vtype)
 324 {
 325     ir_value *self;
 326     self = (ir_value*)mem_a(sizeof(*self));
 327     self->vtype = vtype;
 328     self->store = storetype;
 329     MEM_VECTOR_INIT(self, reads);
 330     MEM_VECTOR_INIT(self, writes);
 331     self->isconst = false;
 332     self->context.file = "<@no context>";
 333     self->context.line = 0;
 334     self->name = NULL;
 335     ir_value_set_name(self, name);
 336
 337     MEM_VECTOR_INIT(self, life);
 338     return self;
 339 }
 340 MEM_VEC_FUNCTIONS(ir_value, ir_life_entry_t, life)
 341 MEM_VEC_FUNCTIONS(ir_value, ir_instr*, reads)
 342 MEM_VEC_FUNCTIONS(ir_value, ir_instr*, writes)
 343
 344 ir_value* ir_value_out(ir_function *owner, const char *name, int storetype, int vtype)
 345 {
 346     ir_value *v = ir_value_var(name, storetype, vtype);
 347     ir_function_collect_value(owner, v);
 348     return v;
 349 }
 350
 351 void ir_value_delete(ir_value* self)
 352 {
 353     mem_d((void*)self->name);
 354     if (self->isconst)
 355     {
 356         if (self->vtype == qc_string)
 357             mem_d((void*)self->constval.vstring);
 358     }
 359     MEM_VECTOR_CLEAR(self, reads);
 360     MEM_VECTOR_CLEAR(self, writes);
 361     MEM_VECTOR_CLEAR(self, life);
 362     mem_d(self);
 363 }
 364
 365 void ir_value_set_name(ir_value *self, const char *name)
 366 {
 367     if (self->name)
 368         mem_d((void*)self->name);
 369     self->name = util_strdup(name);
 370 }
 371
 372 bool ir_value_set_float(ir_value *self, float f)
 373 {
 374     if (self->vtype != qc_float)
 375         return false;
 376     self->constval.vfloat = f;
 377     self->isconst = true;
 378     return true;
 379 }
 380
 381 bool ir_value_set_vector(ir_value *self, vector_t v)
 382 {
 383     if (self->vtype != qc_vector)
 384         return false;
 385     self->constval.vvec = v;
 386     self->isconst = true;
 387     return true;
 388 }
 389
 390 bool ir_value_set_string(ir_value *self, const char *str)
 391 {
 392     if (self->vtype != qc_string)
 393         return false;
 394     self->constval.vstring = util_strdup(str);
 395     self->isconst = true;
 396     return true;
 397 }
 398
 399 bool ir_value_set_int(ir_value *self, int i)
 400 {
 401     if (self->vtype != qc_int)
 402         return false;
 403     self->constval.vint = i;
 404     self->isconst = true;
 405     return true;
 406 }
 407
 408 bool ir_value_lives(ir_value *self, size_t at)
 409 {
 410     size_t i;
 411     for (i = 0; i < self->life_count; ++i)
 412     {
 413         ir_life_entry_t *life = &self->life[i];
 414         if (life->start <= at && at <= life->end)
 415             return true;
 416         if (life->start > at) /* since it's ordered */
 417             return false;
 418     }
 419     return false;
 420 }
 421
 422 void ir_value_life_insert(ir_value *self, size_t idx, ir_life_entry_t e)
 423 {
 424     size_t k;
 425     ir_value_life_add(self, e); /* naive... */
 426     for (k = self->life_count-1; k > idx; --k)
 427         self->life[k] = self->life[k-1];
 428     self->life[idx] = e;
 429 }
 430
 431 bool ir_value_life_merge(ir_value *self, size_t s)
 432 {
 433     size_t i;
 434     ir_life_entry_t *life = NULL;
 435     ir_life_entry_t *before = NULL;
 436     ir_life_entry_t new_entry;
 437
 438     /* Find the first range >= s */
 439     for (i = 0; i < self->life_count; ++i)
 440     {
 441         before = life;
 442         life = &self->life[i];
 443         if (life->start > s)
 444             break;
 445     }
 446     /* nothing found? append */
 447     if (i == self->life_count) {
 448         if (life && life->end+1 == s)
 449         {
 450             /* previous life range can be merged in */
 451             life->end++;
 452             return true;
 453         }
 454         if (life && life->end >= s)
 455             return false;
 456         ir_life_entry_t e;
 457         e.start = e.end = s;
 458         ir_value_life_add(self, e);
 459         return true;
 460     }
 461     /* found */
 462     if (before)
 463     {
 464         if (before->end + 1 == s &&
 465             life->start - 1 == s)
 466         {
 467             /* merge */
 468             before->end = life->end;
 469             ir_value_life_remove(self, i);
 470             return true;
 471         }
 472         if (before->end + 1 == s)
 473         {
 474             /* extend before */
 475             before->end++;
 476             return true;
 477         }
 478         /* already contained */
 479         if (before->end >= s)
 480             return false;
 481     }
 482     /* extend */
 483     if (life->start - 1 == s)
 484     {
 485         life->start--;
 486         return true;
 487     }
 488     /* insert a new entry */
 489     new_entry.start = new_entry.end = s;
 490     ir_value_life_insert(self, i, new_entry);
 491     return true;
 492 }
 493
 494 /***********************************************************************
 495  *IR main operations
 496  */
 497
 498 bool ir_block_create_store_op(ir_block *self, int op, ir_value *target, ir_value *what)
 499 {
 500     if (target->store == store_value) {
 501         fprintf(stderr, "cannot store to an SSA value\n");
 502         return false;
 503     } else {
 504         ir_instr *in = ir_instr_new(self, op);
 505         ir_instr_op(in, 0, target, true);
 506         ir_instr_op(in, 1, what, false);
 507         ir_block_instr_add(self, in);
 508         return true;
 509     }
 510 }
 511
 512 bool ir_block_create_store(ir_block *self, ir_value *target, ir_value *what)
 513 {
 514     int op = 0;
 515     int vtype;
 516     if (target->vtype == qc_variant)
 517         vtype = what->vtype;
 518     else
 519         vtype = target->vtype;
 520
 521     switch (vtype) {
 522         case qc_float:
 523 #if 0
 524             if (what->vtype == qc_int)
 525                 op = INSTR_CONV_ITOF;
 526             else
 527 #endif
 528                 op = INSTR_STORE_F;
 529             break;
 530         case qc_vector:
 531             op = INSTR_STORE_V;
 532             break;
 533         case qc_entity:
 534             op = INSTR_STORE_ENT;
 535             break;
 536         case qc_string:
 537             op = INSTR_STORE_S;
 538             break;
 539 #if 0
 540         case qc_int:
 541             if (what->vtype == qc_int)
 542                 op = INSTR_CONV_FTOI;
 543             else
 544                 op = INSTR_STORE_I;
 545             break;
 546 #endif
 547         case qc_pointer:
 548 #if 0
 549             op = INSTR_STORE_I;
 550 #else
 551             op = INSTR_STORE_ENT;
 552 #endif
 553             break;
 554     }
 555     return ir_block_create_store_op(self, op, target, what);
 556 }
 557
 558 void ir_block_create_return(ir_block *self, ir_value *v)
 559 {
 560     ir_instr *in;
 561     if (self->final) {
 562         fprintf(stderr, "block already ended (%s)\n", self->label);
 563         return;
 564     }
 565     self->final = true;
 566     self->is_return = true;
 567     in = ir_instr_new(self, INSTR_RETURN);
 568     ir_instr_op(in, 0, v, false);
 569     ir_block_instr_add(self, in);
 570 }
 571
 572 void ir_block_create_if(ir_block *self, ir_value *v,
 573                         ir_block *ontrue, ir_block *onfalse)
 574 {
 575     ir_instr *in;
 576     if (self->final) {
 577         fprintf(stderr, "block already ended (%s)\n", self->label);
 578         return;
 579     }
 580     self->final = true;
 581     //in = ir_instr_new(self, (v->vtype == qc_string ? INSTR_IF_S : INSTR_IF_F));
 582     in = ir_instr_new(self, VINSTR_COND);
 583     ir_instr_op(in, 0, v, false);
 584     in->bops[0] = ontrue;
 585     in->bops[1] = onfalse;
 586     ir_block_instr_add(self, in);
 587
 588     ir_block_exits_add(self, ontrue);
 589     ir_block_exits_add(self, onfalse);
 590     ir_block_entries_add(ontrue, self);
 591     ir_block_entries_add(onfalse, self);
 592 }
 593
 594 void ir_block_create_jump(ir_block *self, ir_block *to)
 595 {
 596     ir_instr *in;
 597     if (self->final) {
 598         fprintf(stderr, "block already ended (%s)\n", self->label);
 599         return;
 600     }
 601     self->final = true;
 602     in = ir_instr_new(self, VINSTR_JUMP);
 603     in->bops[0] = to;
 604     ir_block_instr_add(self, in);
 605
 606     ir_block_exits_add(self, to);
 607     ir_block_entries_add(to, self);
 608 }
 609
 610 void ir_block_create_goto(ir_block *self, ir_block *to)
 611 {
 612     ir_instr *in;
 613     if (self->final) {
 614         fprintf(stderr, "block already ended (%s)\n", self->label);
 615         return;
 616     }
 617     self->final = true;
 618     in = ir_instr_new(self, INSTR_GOTO);
 619     in->bops[0] = to;
 620     ir_block_instr_add(self, in);
 621
 622     ir_block_exits_add(self, to);
 623     ir_block_entries_add(to, self);
 624 }
 625
 626 ir_instr* ir_block_create_phi(ir_block *self, const char *label, int ot)
 627 {
 628     ir_value *out;
 629     ir_instr *in;
 630     in = ir_instr_new(self, VINSTR_PHI);
 631     out = ir_value_out(self->owner, label, store_local, ot);
 632     ir_instr_op(in, 0, out, true);
 633     ir_block_instr_add(self, in);
 634     return in;
 635 }
 636
 637 ir_value* ir_phi_value(ir_instr *self)
 638 {
 639     return self->_ops[0];
 640 }
 641
 642 void ir_phi_add(ir_instr* self, ir_block *b, ir_value *v)
 643 {
 644     ir_phi_entry_t pe;
 645
 646     if (!ir_block_entries_find(self->owner, b, NULL)) {
 647         /* Must not be possible to cause this, otherwise the AST
 648          * is doing something wrong.
 649          */
 650         fprintf(stderr, "Invalid entry block for PHI\n");
 651         abort();
 652     }
 653
 654     pe.value = v;
 655     pe.from = b;
 656     ir_value_reads_add(v, self);
 657     ir_instr_phi_add(self, pe);
 658 }
 659
 660 /* binary op related code */
 661
 662 ir_value* ir_block_create_binop(ir_block *self,
 663                                 const char *label, int opcode,
 664                                 ir_value *left, ir_value *right)
 665 {
 666     int ot = qc_void;
 667     switch (opcode) {
 668         case INSTR_ADD_F:
 669         case INSTR_SUB_F:
 670         case INSTR_DIV_F:
 671         case INSTR_MUL_F:
 672         case INSTR_MUL_V:
 673         case INSTR_AND:
 674         case INSTR_OR:
 675 #if 0
 676         case INSTR_AND_I:
 677         case INSTR_AND_IF:
 678         case INSTR_AND_FI:
 679         case INSTR_OR_I:
 680         case INSTR_OR_IF:
 681         case INSTR_OR_FI:
 682 #endif
 683         case INSTR_BITAND:
 684         case INSTR_BITOR:
 685 #if 0
 686         case INSTR_SUB_S: /* -- offset of string as float */
 687         case INSTR_MUL_IF:
 688         case INSTR_MUL_FI:
 689         case INSTR_DIV_IF:
 690         case INSTR_DIV_FI:
 691         case INSTR_BITOR_IF:
 692         case INSTR_BITOR_FI:
 693         case INSTR_BITAND_FI:
 694         case INSTR_BITAND_IF:
 695         case INSTR_EQ_I:
 696         case INSTR_NE_I:
 697 #endif
 698             ot = qc_float;
 699             break;
 700 #if 0
 701         case INSTR_ADD_I:
 702         case INSTR_ADD_IF:
 703         case INSTR_ADD_FI:
 704         case INSTR_SUB_I:
 705         case INSTR_SUB_FI:
 706         case INSTR_SUB_IF:
 707         case INSTR_MUL_I:
 708         case INSTR_DIV_I:
 709         case INSTR_BITAND_I:
 710         case INSTR_BITOR_I:
 711         case INSTR_XOR_I:
 712         case INSTR_RSHIFT_I:
 713         case INSTR_LSHIFT_I:
 714             ot = qc_int;
 715             break;
 716 #endif
 717         case INSTR_ADD_V:
 718         case INSTR_SUB_V:
 719         case INSTR_MUL_VF:
 720         case INSTR_MUL_FV:
 721 #if 0
 722         case INSTR_DIV_VF:
 723         case INSTR_MUL_IV:
 724         case INSTR_MUL_VI:
 725 #endif
 726             ot = qc_vector;
 727             break;
 728 #if 0
 729         case INSTR_ADD_SF:
 730             ot = qc_pointer;
 731             break;
 732 #endif
 733         default:
 734             // ranges:
 735             /* boolean operations result in floats */
 736             if (opcode >= INSTR_EQ_F && opcode <= INSTR_GT)
 737                 ot = qc_float;
 738             else if (opcode >= INSTR_LE && opcode <= INSTR_GT)
 739                 ot = qc_float;
 740 #if 0
 741             else if (opcode >= INSTR_LE_I && opcode <= INSTR_EQ_FI)
 742                 ot = qc_float;
 743 #endif
 744             break;
 745     };
 746     if (ot == qc_void) {
 747         /* The AST or parser were supposed to check this! */
 748         abort();
 749         return NULL;
 750     }
 751     ir_value *out = ir_value_out(self->owner, label, store_local, ot);
 752     ir_instr *in = ir_instr_new(self, opcode);
 753     ir_instr_op(in, 0, out, true);
 754     ir_instr_op(in, 1, left, false);
 755     ir_instr_op(in, 2, right, false);
 756     ir_block_instr_add(self, in);
 757     return out;
 758 }
 759
 760 ir_value* ir_block_create_add(ir_block *self,
 761                               const char *label,
 762                               ir_value *left, ir_value *right)
 763 {
 764     int op = 0;
 765     int l = left->vtype;
 766     int r = right->vtype;
 767     if (l == r) {
 768         switch (l) {
 769             default:
 770                 return NULL;
 771             case qc_float:
 772                 op = INSTR_ADD_F;
 773                 break;
 774 #if 0
 775             case qc_int:
 776                 op = INSTR_ADD_I;
 777                 break;
 778 #endif
 779             case qc_vector:
 780                 op = INSTR_ADD_V;
 781                 break;
 782         }
 783     } else {
 784 #if 0
 785         if ( (l == qc_float && r == qc_int) )
 786             op = INSTR_ADD_FI;
 787         else if ( (l == qc_int && r == qc_float) )
 788             op = INSTR_ADD_IF;
 789         else
 790 #endif
 791             return NULL;
 792     }
 793     return ir_block_create_binop(self, label, op, left, right);
 794 }
 795
 796 ir_value* ir_block_create_sub(ir_block *self,
 797                               const char *label,
 798                               ir_value *left, ir_value *right)
 799 {
 800     int op = 0;
 801     int l = left->vtype;
 802     int r = right->vtype;
 803     if (l == r) {
 804
 805         switch (l) {
 806             default:
 807                 return NULL;
 808             case qc_float:
 809                 op = INSTR_SUB_F;
 810                 break;
 811 #if 0
 812             case qc_int:
 813                 op = INSTR_SUB_I;
 814                 break;
 815 #endif
 816             case qc_vector:
 817                 op = INSTR_SUB_V;
 818                 break;
 819         }
 820     } else {
 821 #if 0
 822         if ( (l == qc_float && r == qc_int) )
 823             op = INSTR_SUB_FI;
 824         else if ( (l == qc_int && r == qc_float) )
 825             op = INSTR_SUB_IF;
 826         else
 827 #endif
 828             return NULL;
 829     }
 830     return ir_block_create_binop(self, label, op, left, right);
 831 }
 832
 833 ir_value* ir_block_create_mul(ir_block *self,
 834                               const char *label,
 835                               ir_value *left, ir_value *right)
 836 {
 837     int op = 0;
 838     int l = left->vtype;
 839     int r = right->vtype;
 840     if (l == r) {
 841
 842         switch (l) {
 843             default:
 844                 return NULL;
 845             case qc_float:
 846                 op = INSTR_MUL_F;
 847                 break;
 848 #if 0
 849             case qc_int:
 850                 op = INSTR_MUL_I;
 851                 break;
 852 #endif
 853             case qc_vector:
 854                 op = INSTR_MUL_V;
 855                 break;
 856         }
 857     } else {
 858         if ( (l == qc_vector && r == qc_float) )
 859             op = INSTR_MUL_VF;
 860         else if ( (l == qc_float && r == qc_vector) )
 861             op = INSTR_MUL_FV;
 862 #if 0
 863         else if ( (l == qc_vector && r == qc_int) )
 864             op = INSTR_MUL_VI;
 865         else if ( (l == qc_int && r == qc_vector) )
 866             op = INSTR_MUL_IV;
 867         else if ( (l == qc_float && r == qc_int) )
 868             op = INSTR_MUL_FI;
 869         else if ( (l == qc_int && r == qc_float) )
 870             op = INSTR_MUL_IF;
 871 #endif
 872         else
 873             return NULL;
 874     }
 875     return ir_block_create_binop(self, label, op, left, right);
 876 }
 877
 878 ir_value* ir_block_create_div(ir_block *self,
 879                               const char *label,
 880                               ir_value *left, ir_value *right)
 881 {
 882     int op = 0;
 883     int l = left->vtype;
 884     int r = right->vtype;
 885     if (l == r) {
 886
 887         switch (l) {
 888             default:
 889                 return NULL;
 890             case qc_float:
 891                 op = INSTR_DIV_F;
 892                 break;
 893 #if 0
 894             case qc_int:
 895                 op = INSTR_DIV_I;
 896                 break;
 897 #endif
 898         }
 899     } else {
 900 #if 0
 901         if ( (l == qc_vector && r == qc_float) )
 902             op = INSTR_DIV_VF;
 903         else if ( (l == qc_float && r == qc_int) )
 904             op = INSTR_DIV_FI;
 905         else if ( (l == qc_int && r == qc_float) )
 906             op = INSTR_DIV_IF;
 907         else
 908 #endif
 909             return NULL;
 910     }
 911     return ir_block_create_binop(self, label, op, left, right);
 912 }
 913
 914 /* PHI resolving breaks the SSA, and must thus be the last
 915  * step before life-range calculation.
 916  */
 917
 918 static void ir_block_naive_phi(ir_block *self);
 919 void ir_function_naive_phi(ir_function *self)
 920 {
 921     size_t i;
 922
 923     for (i = 0; i < self->blocks_count; ++i)
 924         ir_block_naive_phi(self->blocks[i]);
 925 }
 926
 927 static void ir_naive_phi_emit_store(ir_block *block, size_t iid, ir_value *old, ir_value *what)
 928 {
 929     ir_instr *instr;
 930     size_t i;
 931
 932     /* create a store */
 933     ir_block_create_store(block, old, what);
 934
 935     /* we now move it up */
 936     instr = block->instr[block->instr_count-1];
 937     for (i = block->instr_count; i > iid; --i)
 938         block->instr[i] = block->instr[i-1];
 939     block->instr[i] = instr;
 940 }
 941
 942 static void ir_block_naive_phi(ir_block *self)
 943 {
 944     size_t i, p, w;
 945     /* FIXME: optionally, create_phi can add the phis
 946      * to a list so we don't need to loop through blocks
 947      * - anyway: "don't optimize YET"
 948      */
 949     for (i = 0; i < self->instr_count; ++i)
 950     {
 951         ir_instr *instr = self->instr[i];
 952         if (instr->opcode != VINSTR_PHI)
 953             continue;
 954
 955         ir_block_instr_remove(self, i);
 956         --i; /* NOTE: i+1 below */
 957
 958         for (p = 0; p < instr->phi_count; ++p)
 959         {
 960             ir_value *v = instr->phi[p].value;
 961             for (w = 0; w < v->writes_count; ++w) {
 962                 ir_value *old;
 963
 964                 if (!v->writes[w]->_ops[0])
 965                     continue;
 966
 967                 /* When the write was to a global, we have to emit a mov */
 968                 old = v->writes[w]->_ops[0];
 969
 970                 /* The original instruction now writes to the PHI target local */
 971                 if (v->writes[w]->_ops[0] == v)
 972                     v->writes[w]->_ops[0] = instr->_ops[0];
 973
 974                 if (old->store != store_local)
 975                 {
 976                     /* If it originally wrote to a global we need to store the value
 977                      * there as welli
 978                      */
 979                     ir_naive_phi_emit_store(self, i+1, old, v);
 980                     if (i+1 < self->instr_count)
 981                         instr = self->instr[i+1];
 982                     else
 983                         instr = NULL;
 984                     /* In case I forget and access instr later, it'll be NULL
 985                      * when it's a problem, to make sure we crash, rather than accessing
 986                      * invalid data.
 987                      */
 988                 }
 989                 else
 990                 {
 991                     /* If it didn't, we can replace all reads by the phi target now. */
 992                     size_t r;
 993                     for (r = 0; r < old->reads_count; ++r)
 994                     {
 995                         size_t op;
 996                         ir_instr *ri = old->reads[r];
 997                         for (op = 0; op < ri->phi_count; ++op) {
 998                             if (ri->phi[op].value == old)
 999                                 ri->phi[op].value = v;
1000                         }
1001                         for (op = 0; op < 3; ++op) {
1002                             if (ri->_ops[op] == old)
1003                                 ri->_ops[op] = v;
1004                         }
1005                     }
1006                 }
1007             }
1008         }
1009         ir_instr_delete(instr);
1010     }
1011 }
1012
1013 /***********************************************************************
1014  *IR Temp allocation code
1015  * Propagating value life ranges by walking through the function backwards
1016  * until no more changes are made.
1017  * In theory this should happen once more than once for every nested loop
1018  * level.
1019  * Though this implementation might run an additional time for if nests.
1020  */
1021
1022 typedef struct
1023 {
1024     ir_value* *v;
1025     size_t    v_count;
1026     size_t    v_alloc;
1027 } new_reads_t;
1028 MEM_VEC_FUNCTIONS_ALL(new_reads_t, ir_value*, v)
1029
1030 /* Enumerate instructions used by value's life-ranges
1031  */
1032 static void ir_block_enumerate(ir_block *self, size_t *_eid)
1033 {
1034     size_t i;
1035     size_t eid = *_eid;
1036     for (i = 0; i < self->instr_count; ++i)
1037     {
1038         self->instr[i]->eid = eid++;
1039     }
1040     *_eid = eid;
1041 }
1042
1043 /* Enumerate blocks and instructions.
1044  * The block-enumeration is unordered!
1045  * We do not really use the block enumreation, however
1046  * the instruction enumeration is important for life-ranges.
1047  */
1048 void ir_function_enumerate(ir_function *self)
1049 {
1050     size_t i;
1051     size_t instruction_id = 0;
1052     for (i = 0; i < self->blocks_count; ++i)
1053     {
1054         self->blocks[i]->eid = i;
1055         self->blocks[i]->run_id = 0;
1056         ir_block_enumerate(self->blocks[i], &instruction_id);
1057     }
1058 }
1059
1060 static void ir_block_life_propagate(ir_block *b, ir_block *prev, bool *changed);
1061 void ir_function_calculate_liferanges(ir_function *self)
1062 {
1063     size_t i;
1064     bool changed;
1065
1066     do {
1067         self->run_id++;
1068         changed = false;
1069         for (i = 0; i != self->blocks_count; ++i)
1070         {
1071             if (self->blocks[i]->is_return)
1072                 ir_block_life_propagate(self->blocks[i], NULL, &changed);
1073         }
1074     } while (changed);
1075 }
1076
1077 /* Get information about which operand
1078  * is read from, or written to.
1079  */
1080 static void ir_op_read_write(int op, size_t *read, size_t *write)
1081 {
1082     switch (op)
1083     {
1084     case VINSTR_JUMP:
1085     case INSTR_GOTO:
1086         *write = 0;
1087         *read = 0;
1088         break;
1089     case INSTR_IF:
1090     case INSTR_IFNOT:
1091 #if 0
1092     case INSTR_IF_S:
1093     case INSTR_IFNOT_S:
1094 #endif
1095     case INSTR_RETURN:
1096     case VINSTR_COND:
1097         *write = 0;
1098         *read = 1;
1099         break;
1100     default:
1101         *write = 1;
1102         *read = 6;
1103         break;
1104     };
1105 }
1106
1107 static bool ir_block_living_add_instr(ir_block *self, size_t eid)
1108 {
1109     size_t i;
1110     bool changed = false;
1111     bool tempbool;
1112     for (i = 0; i != self->living_count; ++i)
1113     {
1114         tempbool = ir_value_life_merge(self->living[i], eid);
1115         /* debug
1116         if (tempbool)
1117             fprintf(stderr, "block_living_add_instr() value instruction added %s: %i\n", self->living[i]->_name, (int)eid);
1118         */
1119         changed = changed || tempbool;
1120     }
1121     return changed;
1122 }
1123
1124 static void ir_block_life_prop_previous(ir_block* self, ir_block *prev, bool *changed)
1125 {
1126     size_t i;
1127     /* values which have been read in a previous iteration are now
1128      * in the "living" array even if the previous block doesn't use them.
1129      * So we have to remove whatever does not exist in the previous block.
1130      * They will be re-added on-read, but the liferange merge won't cause
1131      * a change.
1132      */
1133     for (i = 0; i < self->living_count; ++i)
1134     {
1135         if (!ir_block_living_find(prev, self->living[i], NULL)) {
1136             ir_block_living_remove(self, i);
1137             --i;
1138         }
1139     }
1140
1141     /* Whatever the previous block still has in its living set
1142      * must now be added to ours as well.
1143      */
1144     for (i = 0; i < prev->living_count; ++i)
1145     {
1146         if (ir_block_living_find(self, prev->living[i], NULL))
1147             continue;
1148         ir_block_living_add(self, prev->living[i]);
1149         /*
1150         printf("%s got from prev: %s\n", self->label, prev->living[i]->_name);
1151         */
1152     }
1153 }
1154
1155 static void ir_block_life_propagate(ir_block *self, ir_block *prev, bool *changed)
1156 {
1157     ir_instr *instr;
1158     ir_value *value;
1159     bool  tempbool;
1160     size_t i, o, p, rd;
1161     /* bitmasks which operands are read from or written to */
1162     size_t read, write;
1163     new_reads_t new_reads;
1164     char dbg_ind[16] = { '#', '0' };
1165     (void)dbg_ind;
1166
1167     MEM_VECTOR_INIT(&new_reads, v);
1168
1169     if (prev)
1170         ir_block_life_prop_previous(self, prev, changed);
1171
1172     i = self->instr_count;
1173     while (i)
1174     { --i;
1175         instr = self->instr[i];
1176
1177         /* PHI operands are always read operands */
1178         for (p = 0; p < instr->phi_count; ++p)
1179         {
1180             value = instr->phi[p].value;
1181             /* used this before new_reads - puts the last read into the life range as well
1182             if (!ir_block_living_find(self, value, NULL))
1183                 ir_block_living_add(self, value);
1184             */
1185             /* fprintf(stderr, "read: %s\n", value->_name); */
1186             if (!new_reads_t_v_find(&new_reads, value, NULL))
1187                 new_reads_t_v_add(&new_reads, value);
1188         }
1189
1190         /* See which operands are read and write operands */
1191         ir_op_read_write(instr->opcode, &read, &write);
1192
1193         /* Go through the 3 main operands */
1194         for (o = 0; o < 3; ++o)
1195         {
1196             if (!instr->_ops[o]) /* no such operand */
1197                 continue;
1198
1199             value = instr->_ops[o];
1200
1201             /* We only care about locals */
1202             if (value->store != store_value &&
1203                 value->store != store_local)
1204                 continue;
1205
1206             /* read operands */
1207             if (read & (1<<o))
1208             {
1209                 /* used this before new_reads - puts the last read into the life range as well
1210                 if (!ir_block_living_find(self, value, NULL))
1211                     ir_block_living_add(self, value);
1212                 */
1213                 /* fprintf(stderr, "read: %s\n", value->_name); */
1214                 if (!new_reads_t_v_find(&new_reads, value, NULL))
1215                     new_reads_t_v_add(&new_reads, value);
1216             }
1217
1218             /* write operands */
1219             /* When we write to a local, we consider it "dead" for the
1220              * remaining upper part of the function, since in SSA a value
1221              * can only be written once (== created)
1222              */
1223             if (write & (1<<o))
1224             {
1225                 size_t idx, readidx;
1226                 bool in_living = ir_block_living_find(self, value, &idx);
1227                 bool in_reads = new_reads_t_v_find(&new_reads, value, &readidx);
1228                 if (!in_living && !in_reads)
1229                 {
1230                     /* If the value isn't alive it hasn't been read before... */
1231                     /* TODO: See if the warning can be emitted during parsing or AST processing
1232                      * otherwise have warning printed here.
1233                      * IF printing a warning here: include filecontext_t,
1234                      * and make sure it's only printed once
1235                      * since this function is run multiple times.
1236                      */
1237                     /* For now: debug info: */
1238                     fprintf(stderr, "Value only written %s\n", value->name);
1239                     tempbool = ir_value_life_merge(value, instr->eid);
1240                     *changed = *changed || tempbool;
1241                     /*
1242                     ir_instr_dump(instr, dbg_ind, printf);
1243                     abort();
1244                     */
1245                 } else {
1246                     /* since 'living' won't contain it
1247                      * anymore, merge the value, since
1248                      * (A) doesn't.
1249                      */
1250                     tempbool = ir_value_life_merge(value, instr->eid);
1251                     /*
1252                     if (tempbool)
1253                         fprintf(stderr, "value added id %s %i\n", value->name, (int)instr->eid);
1254                     */
1255                     *changed = *changed || tempbool;
1256                     /* Then remove */
1257                     ir_block_living_remove(self, idx);
1258                     if (in_reads)
1259                         new_reads_t_v_remove(&new_reads, readidx);
1260                 }
1261             }
1262         }
1263         /* (A) */
1264         tempbool = ir_block_living_add_instr(self, instr->eid);
1265         //fprintf(stderr, "living added values\n");
1266         *changed = *changed || tempbool;
1267
1268         /* new reads: */
1269         for (rd = 0; rd < new_reads.v_count; ++rd)
1270         {
1271             if (!ir_block_living_find(self, new_reads.v[rd], NULL)) {
1272                 ir_block_living_add(self, new_reads.v[rd]);
1273             }
1274             if (!i && !self->entries_count) {
1275                 /* fix the top */
1276                 *changed = *changed || ir_value_life_merge(new_reads.v[rd], instr->eid);
1277             }
1278         }
1279         new_reads_t_v_clear(&new_reads);
1280     }
1281
1282     if (self->run_id == self->owner->run_id)
1283         return;
1284     self->run_id = self->owner->run_id;
1285
1286     for (i = 0; i < self->entries_count; ++i)
1287     {
1288         ir_block *entry = self->entries[i];
1289         ir_block_life_propagate(entry, self, changed);
1290     }
1291 }