example.c

   1 /*
   2  * Example of how to write a compiler with sparse
   3  */
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <stdarg.h>
   7 #include <assert.h>
   8
   9 #include "symbol.h"
  10 #include "expression.h"
  11 #include "linearize.h"
  12 #include "flow.h"
  13 #include "storage.h"
  14
  15 struct hardreg {
  16         const char *name;
  17         struct pseudo_list *contains;
  18         unsigned busy:16,
  19                  used:1;
  20 };
  21
  22 #define TAG_DEAD 1
  23 #define TAG_DIRTY 2
  24
  25 static void output_bb(struct basic_block *bb, unsigned long generation);
  26
  27 /*
  28  * We only know about the caller-clobbered registers
  29  * right now.
  30  */
  31 static struct hardreg hardregs[] = {
  32         { .name = "%eax" },
  33         { .name = "%edx" },
  34         { .name = "%ecx" },
  35         { .name = "%ebx" },
  36         { .name = "%esi" },
  37         { .name = "%edi" },
  38 };
  39 #define REGNO (sizeof(hardregs)/sizeof(struct hardreg))
  40
  41 struct bb_state {
  42         struct basic_block *bb;
  43         unsigned long stack_offset;
  44         struct storage_hash_list *inputs;
  45         struct storage_hash_list *outputs;
  46         struct storage_hash_list *internal;
  47 };
  48
  49 static struct storage_hash *find_storage_hash(pseudo_t pseudo, struct storage_hash_list *list)
  50 {
  51         struct storage_hash *entry;
  52         FOR_EACH_PTR(list, entry) {
  53                 if (entry->pseudo == pseudo)
  54                         return entry;
  55         } END_FOR_EACH_PTR(entry);
  56         return NULL;
  57 }
  58
  59 static struct storage_hash *find_or_create_hash(pseudo_t pseudo, struct storage_hash_list **listp)
  60 {
  61         struct storage_hash *entry;
  62
  63         entry = find_storage_hash(pseudo, *listp);
  64         if (!entry) {
  65                 entry = alloc_storage_hash(alloc_storage());
  66                 entry->pseudo = pseudo;
  67                 add_ptr_list(listp, entry);
  68         }
  69         return entry;
  70 }
  71
  72 /* Eventually we should just build it up in memory */
  73 static void output_line(struct bb_state *state, const char *fmt, ...)
  74 {
  75         va_list args;
  76
  77         va_start(args, fmt);
  78         vprintf(fmt, args);
  79         va_end(args);
  80 }
  81
  82 static void output_label(struct bb_state *state, const char *fmt, ...)
  83 {
  84         static char buffer[512];
  85         va_list args;
  86
  87         va_start(args, fmt);
  88         vsnprintf(buffer, sizeof(buffer), fmt, args);
  89         va_end(args);
  90
  91         output_line(state, "%s:\n", buffer);
  92 }
  93
  94 static void output_insn(struct bb_state *state, const char *fmt, ...)
  95 {
  96         static char buffer[512];
  97         va_list args;
  98
  99         va_start(args, fmt);
 100         vsnprintf(buffer, sizeof(buffer), fmt, args);
 101         va_end(args);
 102
 103         output_line(state, "\t%s\n", buffer);
 104 }
 105
 106 static void output_comment(struct bb_state *state, const char *fmt, ...)
 107 {
 108         static char buffer[512];
 109         va_list args;
 110
 111         if (!verbose)
 112                 return;
 113         va_start(args, fmt);
 114         vsnprintf(buffer, sizeof(buffer), fmt, args);
 115         va_end(args);
 116
 117         output_line(state, "\t# %s\n", buffer);
 118 }
 119
 120 static const char *show_memop(struct storage *storage)
 121 {
 122         static char buffer[1000];
 123         switch (storage->type) {
 124         case REG_ARG:
 125                 sprintf(buffer, "%d(FP)", storage->regno * 4);
 126                 break;
 127         case REG_STACK:
 128                 sprintf(buffer, "%d(SP)", storage->offset);
 129                 break;
 130         case REG_REG:
 131                 return hardregs[storage->regno].name;
 132         default:
 133                 return show_storage(storage);
 134         }
 135         return buffer;
 136 }
 137
 138 static void alloc_stack(struct bb_state *state, struct storage *storage)
 139 {
 140         storage->type = REG_STACK;
 141         storage->offset = state->stack_offset;
 142         state->stack_offset += 4;
 143 }
 144
 145 /*
 146  * Can we re-generate the pseudo, so that we don't need to
 147  * flush it to memory? We can regenerate:
 148  *  - immediates and symbol addresses
 149  *  - pseudos we got as input in non-registers
 150  *  - pseudos we've already saved off earlier..
 151  */
 152 static int can_regenerate(struct bb_state *state, pseudo_t pseudo)
 153 {
 154         struct storage_hash *in;
 155
 156         switch (pseudo->type) {
 157         case PSEUDO_VAL:
 158         case PSEUDO_SYM:
 159                 return 1;
 160
 161         default:
 162                 in = find_storage_hash(pseudo, state->inputs);
 163                 if (in && in->storage->type != REG_REG)
 164                         return 1;
 165                 in = find_storage_hash(pseudo, state->internal);
 166                 if (in)
 167                         return 1;
 168         }
 169         return 0;
 170 }
 171
 172 static void flush_one_pseudo(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
 173 {
 174         struct storage_hash *out;
 175         struct storage *storage;
 176
 177         if (can_regenerate(state, pseudo))
 178                 return;
 179
 180         output_comment(state, "flushing %s from %s", show_pseudo(pseudo), hardreg->name);
 181         out = find_storage_hash(pseudo, state->internal);
 182         if (!out) {
 183                 out = find_storage_hash(pseudo, state->outputs);
 184                 if (!out)
 185                         out = find_or_create_hash(pseudo, &state->internal);
 186         }
 187         storage = out->storage;
 188         switch (storage->type) {
 189         default:
 190                 /*
 191                  * Aieee - the next user wants it in a register, but we
 192                  * need to flush it to memory in between. Which means that
 193                  * we need to allocate an internal one, dammit..
 194                  */
 195                 out = find_or_create_hash(pseudo, &state->internal);
 196                 storage = out->storage;
 197                 /* Fall through */
 198         case REG_UDEF:
 199                 alloc_stack(state, storage);
 200                 /* Fall through */
 201         case REG_STACK:
 202                 output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage));
 203                 break;
 204         }
 205 }
 206
 207 /* Flush a hardreg out to the storage it has.. */
 208 static void flush_reg(struct bb_state *state, struct hardreg *hardreg)
 209 {
 210         pseudo_t pseudo;
 211
 212         if (!hardreg->busy)
 213                 return;
 214         hardreg->busy = 0;
 215         hardreg->used = 1;
 216         FOR_EACH_PTR(hardreg->contains, pseudo) {
 217                 if (CURRENT_TAG(pseudo) & TAG_DEAD)
 218                         continue;
 219                 if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
 220                         continue;
 221                 flush_one_pseudo(state, hardreg, pseudo);
 222         } END_FOR_EACH_PTR(pseudo);
 223         free_ptr_list(&hardreg->contains);
 224 }
 225
 226 /* Fill a hardreg with the pseudo it has */
 227 static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
 228 {
 229         struct storage_hash *src;
 230         struct instruction *def;
 231
 232         switch (pseudo->type) {
 233         case PSEUDO_VAL:
 234                 output_insn(state, "movl $%lld,%s", pseudo->value, hardreg->name);
 235                 break;
 236         case PSEUDO_SYM:
 237                 output_insn(state, "movl $<%s>,%s", show_pseudo(pseudo), hardreg->name);
 238                 break;
 239         case PSEUDO_ARG:
 240         case PSEUDO_REG:
 241                 def = pseudo->def;
 242                 if (def->opcode == OP_SETVAL) {
 243                         output_insn(state, "movl $<%s>,%s", show_pseudo(def->symbol), hardreg->name);
 244                         break;
 245                 }
 246                 src = find_storage_hash(pseudo, state->internal);
 247                 if (!src) {
 248                         src = find_storage_hash(pseudo, state->inputs);
 249                         if (!src) {
 250                                 src = find_storage_hash(pseudo, state->outputs);
 251                                 /* Undefined? Screw it! */
 252                                 if (!src) {
 253                                         output_insn(state, "undef %s ??", show_pseudo(pseudo));
 254                                         break;
 255                                 }
 256
 257                                 /*
 258                                  * If we found output storage, it had better be local stack
 259                                  * that we flushed to earlier..
 260                                  */
 261                                 if (src->storage->type != REG_STACK) {
 262                                         output_insn(state, "fill_reg on undef storage %s ??", show_pseudo(pseudo));
 263                                         break;
 264                                 }
 265                         }
 266                 }
 267
 268                 /*
 269                  * Incoming pseudo with out any pre-set storage allocation?
 270                  * We can make up our own, and obviously prefer to get it
 271                  * in the register we already selected (if it hasn't been
 272                  * used yet).
 273                  */
 274                 if (src->storage->type == REG_UDEF) {
 275                         if (!hardreg->used) {
 276                                 src->storage->type = REG_REG;
 277                                 src->storage->regno = hardreg - hardregs;
 278                                 break;
 279                         }
 280                         alloc_stack(state, src->storage);
 281                 }
 282                 output_insn(state, "mov.%d %s,%s", 32, show_memop(src->storage), hardreg->name);
 283                 break;
 284         default:
 285                 output_insn(state, "reload %s from %s", hardreg->name, show_pseudo(pseudo));
 286                 break;
 287         }
 288         return hardreg;
 289 }
 290
 291 static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 292 {
 293         output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name);
 294         add_ptr_list_tag(&reg->contains, pseudo, TAG_DIRTY);
 295         reg->busy++;
 296 }
 297
 298 static int last_reg;
 299
 300 static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target)
 301 {
 302         struct storage_hash *dst;
 303
 304         dst = find_storage_hash(target, state->outputs);
 305         if (dst) {
 306                 struct storage *storage = dst->storage;
 307                 if (storage->type == REG_REG)
 308                         return hardregs + storage->regno;
 309         }
 310         return NULL;
 311 }
 312
 313 static struct hardreg *empty_reg(struct bb_state *state)
 314 {
 315         int i;
 316         struct hardreg *reg = hardregs;
 317
 318         for (i = 0; i < REGNO; i++, reg++) {
 319                 if (!reg->busy)
 320                         return reg;
 321         }
 322         return NULL;
 323 }
 324
 325 static struct hardreg *target_reg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 326 {
 327         int i;
 328         struct hardreg *reg;
 329
 330         /* First, see if we have a preferred target register.. */
 331         reg = preferred_reg(state, target);
 332         if (reg && !reg->busy)
 333                 goto found;
 334
 335         reg = empty_reg(state);
 336         if (reg)
 337                 goto found;
 338
 339         i = last_reg+1;
 340         if (i >= REGNO)
 341                 i = 0;
 342         last_reg = i;
 343         reg = hardregs + i;
 344         flush_reg(state, reg);
 345
 346 found:
 347         add_pseudo_reg(state, pseudo, reg);
 348         return reg;
 349 }
 350
 351 static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 352 {
 353         int i;
 354         struct hardreg *reg;
 355
 356         for (i = 0; i < REGNO; i++) {
 357                 pseudo_t p;
 358
 359                 reg = hardregs + i;
 360                 FOR_EACH_PTR(reg->contains, p) {
 361                         if (p == pseudo) {
 362                                 last_reg = i;
 363                                 output_comment(state, "found pseudo %s in reg %s", show_pseudo(pseudo), reg->name);
 364                                 return reg;
 365                         }
 366                 } END_FOR_EACH_PTR(p);
 367         }
 368         reg = target_reg(state, pseudo, target);
 369         return fill_reg(state, reg, pseudo);
 370 }
 371
 372 static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 373 {
 374         int i;
 375         struct hardreg *reg;
 376
 377         if (!src->busy)
 378                 return src;
 379
 380         reg = preferred_reg(state, target);
 381         if (reg && !reg->busy) {
 382                 output_comment(state, "copying %s to preferred target %s", show_pseudo(target), reg->name);
 383                 output_insn(state, "movl %s,%s", src->name, reg->name);
 384                 return reg;
 385         }
 386
 387         for (i = 0; i < REGNO; i++) {
 388                 struct hardreg *reg = hardregs + i;
 389                 if (!reg->busy) {
 390                         output_comment(state, "copying %s to %s", show_pseudo(target), reg->name);
 391                         output_insn(state, "movl %s,%s", src->name, reg->name);
 392                         return reg;
 393                 }
 394         }
 395
 396         flush_reg(state, src);
 397         return src;
 398 }
 399
 400 static const char *generic(struct bb_state *state, pseudo_t pseudo)
 401 {
 402         struct hardreg *reg;
 403
 404         switch (pseudo->type) {
 405         case PSEUDO_SYM:
 406         case PSEUDO_VAL:
 407                 return show_pseudo(pseudo);
 408         default:
 409                 reg = getreg(state, pseudo, NULL);
 410                 return reg->name;
 411         }
 412 }
 413
 414 static const char *address(struct bb_state *state, struct instruction *memop)
 415 {
 416         struct symbol *sym;
 417         struct hardreg *base;
 418         static char buffer[100];
 419         pseudo_t addr = memop->src;
 420
 421         switch(addr->type) {
 422         case PSEUDO_SYM:
 423                 sym = addr->sym;
 424                 if (sym->ctype.modifiers & MOD_NONLOCAL) {
 425                         sprintf(buffer, "%s+%d", show_ident(sym->ident), memop->offset);
 426                         return buffer;
 427                 }
 428                 sprintf(buffer, "%d+%s(SP)", memop->offset, show_ident(sym->ident));
 429                 return buffer;
 430         default:
 431                 base = getreg(state, addr, NULL);
 432                 sprintf(buffer, "%d(%s)", memop->offset, base->name);
 433                 return buffer;
 434         }
 435 }
 436
 437 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
 438 {
 439         switch(pseudo->type) {
 440         case PSEUDO_VAL:
 441                 return show_pseudo(pseudo);
 442         default:
 443                 return getreg(state, pseudo, NULL)->name;
 444         }
 445 }
 446
 447 static void generate_store(struct instruction *insn, struct bb_state *state)
 448 {
 449         output_insn(state, "mov.%d %s,%s", insn->size, reg_or_imm(state, insn->target), address(state, insn));
 450 }
 451
 452 static void generate_load(struct instruction *insn, struct bb_state *state)
 453 {
 454         const char *input = address(state, insn);
 455         output_insn(state, "mov.%d %s,%s", insn->size, input, target_reg(state, insn->target, NULL)->name);
 456 }
 457
 458 static const char* opcodes[] = {
 459         [OP_BADOP] = "bad_op",
 460
 461         /* Fn entrypoint */
 462         [OP_ENTRY] = "<entry-point>",
 463
 464         /* Terminator */
 465         [OP_RET] = "ret",
 466         [OP_BR] = "br",
 467         [OP_SWITCH] = "switch",
 468         [OP_INVOKE] = "invoke",
 469         [OP_COMPUTEDGOTO] = "jmp *",
 470         [OP_UNWIND] = "unwind",
 471
 472         /* Binary */
 473         [OP_ADD] = "add",
 474         [OP_SUB] = "sub",
 475         [OP_MUL] = "mul",
 476         [OP_DIV] = "div",
 477         [OP_MOD] = "mod",
 478         [OP_SHL] = "shl",
 479         [OP_SHR] = "shr",
 480
 481         /* Logical */
 482         [OP_AND] = "and",
 483         [OP_OR] = "or",
 484         [OP_XOR] = "xor",
 485         [OP_AND_BOOL] = "and-bool",
 486         [OP_OR_BOOL] = "or-bool",
 487
 488         /* Binary comparison */
 489         [OP_SET_EQ] = "seteq",
 490         [OP_SET_NE] = "setne",
 491         [OP_SET_LE] = "setle",
 492         [OP_SET_GE] = "setge",
 493         [OP_SET_LT] = "setlt",
 494         [OP_SET_GT] = "setgt",
 495         [OP_SET_B] = "setb",
 496         [OP_SET_A] = "seta",
 497         [OP_SET_BE] = "setbe",
 498         [OP_SET_AE] = "setae",
 499
 500         /* Uni */
 501         [OP_NOT] = "not",
 502         [OP_NEG] = "neg",
 503
 504         /* Special three-input */
 505         [OP_SEL] = "select",
 506
 507         /* Memory */
 508         [OP_MALLOC] = "malloc",
 509         [OP_FREE] = "free",
 510         [OP_ALLOCA] = "alloca",
 511         [OP_LOAD] = "load",
 512         [OP_STORE] = "store",
 513         [OP_SETVAL] = "set",
 514         [OP_GET_ELEMENT_PTR] = "getelem",
 515
 516         /* Other */
 517         [OP_PHI] = "phi",
 518         [OP_PHISOURCE] = "phisrc",
 519         [OP_CAST] = "cast",
 520         [OP_PTRCAST] = "ptrcast",
 521         [OP_CALL] = "call",
 522         [OP_VANEXT] = "va_next",
 523         [OP_VAARG] = "va_arg",
 524         [OP_SLICE] = "slice",
 525         [OP_SNOP] = "snop",
 526         [OP_LNOP] = "lnop",
 527         [OP_NOP] = "nop",
 528         [OP_DEATHNOTE] = "dead",
 529         [OP_ASM] = "asm",
 530
 531         /* Sparse tagging (line numbers, context, whatever) */
 532         [OP_CONTEXT] = "context",
 533 };
 534
 535 static void generate_binop(struct bb_state *state, struct instruction *insn)
 536 {
 537         const char *op = opcodes[insn->opcode];
 538         struct hardreg *src = getreg(state, insn->src1, insn->target);
 539         struct hardreg *dst = copy_reg(state, src, insn->target);
 540
 541         output_insn(state, "%s.%d %s,%s", op, insn->size, reg_or_imm(state, insn->src2), dst->name);
 542         add_pseudo_reg(state, insn->target, dst);
 543 }
 544
 545 static void mark_pseudo_dead(struct bb_state *state, pseudo_t pseudo)
 546 {
 547         int i;
 548
 549         for (i = 0; i < REGNO; i++) {
 550                 pseudo_t p;
 551                 struct hardreg *reg = hardregs + i;
 552                 FOR_EACH_PTR(reg->contains, p) {
 553                         if (p != pseudo)
 554                                 continue;
 555                         if (CURRENT_TAG(p) & TAG_DEAD)
 556                                 continue;
 557                         output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
 558                         TAG_CURRENT(p, TAG_DEAD);
 559                         reg->busy--;
 560                 } END_FOR_EACH_PTR(p);
 561         }
 562 }
 563
 564 /*
 565  * A PHI source can define a pseudo that we already
 566  * have in another register. We need to invalidate the
 567  * old register so that we don't end up with the same
 568  * pseudo in "two places".
 569  */
 570 static void remove_pseudo_reg(struct bb_state *state, pseudo_t pseudo)
 571 {
 572         int i;
 573
 574         output_comment(state, "pseudo %s died", show_pseudo(pseudo));
 575         for (i = 0; i < REGNO; i++) {
 576                 struct hardreg *reg = hardregs + i;
 577                 if (remove_pseudo(&reg->contains, pseudo))
 578                         output_comment(state, "removed pseudo %s from reg %s", show_pseudo(pseudo), reg->name);
 579         }
 580 }
 581
 582 static void generate_phisource(struct instruction *insn, struct bb_state *state)
 583 {
 584         struct instruction *user;
 585         struct hardreg *reg;
 586
 587         /* Mark all the target pseudos dead first */
 588         FOR_EACH_PTR(insn->phi_users, user) {
 589                 mark_pseudo_dead(state, user->target);
 590         } END_FOR_EACH_PTR(user);
 591
 592         reg = NULL;
 593         FOR_EACH_PTR(insn->phi_users, user) {
 594                 if (!reg)
 595                         reg = getreg(state, insn->phi_src, user->target);
 596                 remove_pseudo_reg(state, user->target);
 597                 add_pseudo_reg(state, user->target, reg);
 598         } END_FOR_EACH_PTR(user);
 599 }
 600
 601 static void generate_cast(struct bb_state *state, struct instruction *insn)
 602 {
 603         struct hardreg *src = getreg(state, insn->src, insn->target);
 604         struct hardreg *dst = copy_reg(state, src, insn->target);
 605         unsigned int old = insn->orig_type ? insn->orig_type->bit_size : 0;
 606         unsigned int new = insn->size;
 607         unsigned long long mask;
 608
 609         /* No, we shouldn't just mask it, but this is just for an example */
 610         if (old > new) {
 611                 mask = ~(~0ULL << new);
 612         } else {
 613                 mask = ~(~0ULL << old);
 614         }
 615
 616         output_insn(state, "andl.%d $%#llx,%s", insn->size, mask, dst->name);
 617         add_pseudo_reg(state, insn->target, dst);
 618 }
 619
 620 static void generate_output_storage(struct bb_state *state);
 621
 622 static void generate_branch(struct bb_state *state, struct instruction *br)
 623 {
 624         if (br->cond) {
 625                 struct hardreg *reg = getreg(state, br->cond, NULL);
 626                 output_insn(state, "testl %s,%s", reg->name, reg->name);
 627         }
 628         generate_output_storage(state);
 629         if (br->cond)
 630                 output_insn(state, "je .L%p", br->bb_false);
 631         output_insn(state, "jmp .L%p", br->bb_true);
 632 }
 633
 634 static void generate_ret(struct bb_state *state, struct instruction *ret)
 635 {
 636         if (ret->src && ret->src != VOID) {
 637                 struct hardreg *wants = hardregs+0;
 638                 struct hardreg *reg = getreg(state, ret->src, NULL);
 639                 if (reg != wants)
 640                         output_insn(state, "movl %s,%s", reg->name, wants->name);
 641         }
 642         output_insn(state, "ret");
 643 }
 644
 645 /*
 646  * Fake "call" linearization just as a taster..
 647  */
 648 static void generate_call(struct bb_state *state, struct instruction *insn)
 649 {
 650         int offset = 0;
 651         pseudo_t arg;
 652
 653         FOR_EACH_PTR(insn->arguments, arg) {
 654                 output_insn(state, "pushl %s", generic(state, arg));
 655                 offset += 4;
 656         } END_FOR_EACH_PTR(arg);
 657         flush_reg(state, hardregs+0);
 658         flush_reg(state, hardregs+1);
 659         flush_reg(state, hardregs+2);
 660         output_insn(state, "call %s", show_pseudo(insn->func));
 661         if (offset)
 662                 output_insn(state, "addl $%d,%%esp", offset);
 663         add_pseudo_reg(state, insn->target, hardregs+0);
 664 }
 665
 666 static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 667 {
 668         if (verbose)
 669                 output_comment(state, "%s", show_instruction(insn));
 670
 671         switch (insn->opcode) {
 672         case OP_ENTRY: {
 673                 struct symbol *sym = insn->bb->ep->name;
 674                 const char *name = show_ident(sym->ident);
 675                 if (sym->ctype.modifiers & MOD_STATIC)
 676                         printf("\n\n%s:\n", name);
 677                 else
 678                         printf("\n\n.globl %s\n%s:\n", name, name);
 679                 break;
 680         }
 681
 682         /*
 683          * OP_PHI doesn't actually generate any code. It has been
 684          * done by the storage allocator and the OP_PHISOURCE.
 685          */
 686         case OP_PHI:
 687                 break;
 688
 689         case OP_PHISOURCE:
 690                 generate_phisource(insn, state);
 691                 break;
 692
 693         /*
 694          * OP_SETVAL likewise doesn't actually generate any
 695          * code. On use, the "def" of the pseudo will be
 696          * looked up.
 697          */
 698         case OP_SETVAL:
 699                 break;
 700
 701         case OP_STORE:
 702                 generate_store(insn, state);
 703                 break;
 704
 705         case OP_LOAD:
 706                 generate_load(insn, state);
 707                 break;
 708
 709         case OP_DEATHNOTE:
 710                 mark_pseudo_dead(state, insn->target);
 711                 break;
 712
 713         case OP_BINARY ... OP_BINARY_END:
 714         case OP_BINCMP ... OP_BINCMP_END:
 715                 generate_binop(state, insn);
 716                 break;
 717
 718         case OP_CAST: case OP_PTRCAST:
 719                 generate_cast(state, insn);
 720                 break;
 721
 722         case OP_BR:
 723                 generate_branch(state, insn);
 724                 break;
 725
 726         case OP_CALL:
 727                 generate_call(state, insn);
 728                 break;
 729
 730         case OP_RET:
 731                 generate_ret(state, insn);
 732                 break;
 733
 734         default:
 735                 output_insn(state, "unimplemented: %s", show_instruction(insn));
 736                 break;
 737         }
 738 }
 739
 740 #define VERY_BUSY 1000
 741 #define REG_FIXED 2000
 742
 743 static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, pseudo_t pseudo, struct storage *storage)
 744 {
 745         int i;
 746         struct hardreg *out;
 747
 748         switch (storage->type) {
 749         case REG_REG:
 750                 out = hardregs + storage->regno;
 751                 if (reg == out)
 752                         return;
 753                 output_insn(state, "movl %s,%s", reg->name, out->name);
 754                 return;
 755         case REG_UDEF:
 756                 if (reg->busy < VERY_BUSY) {
 757                         storage->type = REG_REG;
 758                         storage->regno = reg - hardregs;
 759                         reg->busy = REG_FIXED;
 760                         return;
 761                 }
 762
 763                 /* Try to find a non-busy register.. */
 764                 for (i = 0; i < REGNO; i++) {
 765                         out = hardregs + i;
 766                         if (out->busy)
 767                                 continue;
 768                         output_insn(state, "movl %s,%s", reg->name, out->name);
 769                         storage->type = REG_REG;
 770                         storage->regno = i;
 771                         reg->busy = REG_FIXED;
 772                         return;
 773                 }
 774
 775                 /* Fall back on stack allocation ... */
 776                 alloc_stack(state, storage);
 777                 /* Fallthroigh */
 778         default:
 779                 output_insn(state, "movl %s,%s", reg->name, show_memop(storage));
 780                 return;
 781         }
 782 }
 783
 784 static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage)
 785 {
 786         struct hardreg *out;
 787
 788         switch (storage->type) {
 789         case REG_UDEF:
 790                 alloc_stack(state, storage);
 791         default:
 792                 output_insn(state, "movl %s,%s", show_pseudo(src), show_memop(storage));
 793                 break;
 794         case REG_REG:
 795                 out = hardregs + storage->regno;
 796                 output_insn(state, "movl %s,%s", show_pseudo(src), out->name);
 797         }
 798 }
 799
 800 static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out)
 801 {
 802         int i;
 803         struct storage_hash *in;
 804         struct instruction *def;
 805
 806         /* Is that pseudo a constant value? */
 807         switch (pseudo->type) {
 808         case PSEUDO_VAL:
 809                 write_val_to_storage(state, pseudo, out);
 810                 return;
 811         case PSEUDO_REG:
 812                 def = pseudo->def;
 813                 if (def->opcode == OP_SETVAL) {
 814                         write_val_to_storage(state, def->symbol, out);
 815                         return;
 816                 }
 817         default:
 818                 break;
 819         }
 820
 821         /* See if we have that pseudo in a register.. */
 822         for (i = 0; i < REGNO; i++) {
 823                 struct hardreg *reg = hardregs + i;
 824                 pseudo_t p;
 825
 826                 FOR_EACH_PTR(reg->contains, p) {
 827                         if (p == pseudo) {
 828                                 write_reg_to_storage(state, reg, pseudo, out);
 829                                 return;
 830                         }
 831                 } END_FOR_EACH_PTR(p);
 832         }
 833
 834         /* Do we have it in another storage? */
 835         in = find_storage_hash(pseudo, state->internal);
 836         if (!in) {
 837                 in = find_storage_hash(pseudo, state->inputs);
 838                 /* Undefined? */
 839                 if (!in)
 840                         return;
 841         }
 842         switch (out->type) {
 843         case REG_UDEF:
 844                 *out = *in->storage;
 845                 break;
 846         case REG_REG:
 847                 output_insn(state, "movl %s,%s", show_memop(in->storage), hardregs[out->regno].name);
 848                 break;
 849         default:
 850                 output_insn(state, "movl %s,tmp", show_memop(in->storage));
 851                 output_insn(state, "movl tmp,%s", show_memop(out));
 852                 break;
 853         }
 854         return;
 855 }
 856
 857 static int final_pseudo_flush(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 858 {
 859         struct storage_hash *hash;
 860         struct storage *out;
 861         struct hardreg *dst;
 862
 863         /*
 864          * Since this pseudo is live at exit, we'd better have output
 865          * storage for it..
 866          */
 867         hash = find_storage_hash(pseudo, state->outputs);
 868         if (!hash)
 869                 return 1;
 870         out = hash->storage;
 871
 872         /* If the output is in a register, try to get it there.. */
 873         if (out->type == REG_REG) {
 874                 dst = hardregs + out->regno;
 875                 /*
 876                  * Two good cases: nobody is using the right register,
 877                  * or we've already set it aside for output..
 878                  */
 879                 if (!dst->busy || dst->busy > VERY_BUSY)
 880                         goto copy_to_dst;
 881
 882                 /* Aiee. Try to keep it in a register.. */
 883                 dst = empty_reg(state);
 884                 if (dst)
 885                         goto copy_to_dst;
 886
 887                 return 0;
 888         }
 889
 890         /* If the output is undefined, let's see if we can put it in a register.. */
 891         if (out->type == REG_UDEF) {
 892                 dst = empty_reg(state);
 893                 if (dst) {
 894                         out->type = REG_REG;
 895                         out->regno = dst - hardregs;
 896                         goto copy_to_dst;
 897                 }
 898                 /* Uhhuh. Not so good. No empty registers right now */
 899                 return 0;
 900         }
 901
 902         /* If we know we need to flush it, just do so already .. */
 903         output_insn(state, "movl %s,%s", reg->name, show_memop(out));
 904         return 1;
 905
 906 copy_to_dst:
 907         if (reg == dst)
 908                 return 1;
 909         output_insn(state, "movl %s,%s", reg->name, dst->name);
 910         add_pseudo_reg(state, pseudo, dst);
 911         return 1;
 912 }
 913
 914 /*
 915  * This tries to make sure that we put all the pseudos that are
 916  * live on exit into the proper storage
 917  */
 918 static void generate_output_storage(struct bb_state *state)
 919 {
 920         struct storage_hash *entry;
 921
 922         /* Go through the fixed outputs, making sure we have those regs free */
 923         FOR_EACH_PTR(state->outputs, entry) {
 924                 struct storage *out = entry->storage;
 925                 if (out->type == REG_REG) {
 926                         struct hardreg *reg = hardregs + out->regno;
 927                         pseudo_t p;
 928                         int flushme = 0;
 929
 930                         reg->busy = REG_FIXED;
 931                         FOR_EACH_PTR(reg->contains, p) {
 932                                 if (p == entry->pseudo) {
 933                                         flushme = -100;
 934                                         continue;
 935                                 }
 936                                 if (CURRENT_TAG(p) & TAG_DEAD)
 937                                         continue;
 938
 939                                 /* Try to write back the pseudo to where it should go ... */
 940                                 if (final_pseudo_flush(state, p, reg)) {
 941                                         DELETE_CURRENT_PTR(p);
 942                                         reg->busy--;
 943                                         continue;
 944                                 }
 945                                 flushme++;
 946                         } END_FOR_EACH_PTR(p);
 947                         PACK_PTR_LIST(&reg->contains);
 948                         if (flushme > 0)
 949                                 flush_reg(state, reg);
 950                 }
 951         } END_FOR_EACH_PTR(entry);
 952
 953         FOR_EACH_PTR(state->outputs, entry) {
 954                 fill_output(state, entry->pseudo, entry->storage);
 955         } END_FOR_EACH_PTR(entry);
 956 }
 957
 958 static void generate(struct basic_block *bb, struct bb_state *state)
 959 {
 960         int i;
 961         struct storage_hash *entry;
 962         struct instruction *insn;
 963
 964         for (i = 0; i < REGNO; i++) {
 965                 free_ptr_list(&hardregs[i].contains);
 966                 hardregs[i].busy = 0;
 967                 hardregs[i].used = 0;
 968         }
 969
 970         FOR_EACH_PTR(state->inputs, entry) {
 971                 struct storage *storage = entry->storage;
 972                 const char *name = show_storage(storage);
 973                 if (storage->type == REG_REG) {
 974                         int regno = storage->regno;
 975                         add_pseudo_reg(state, entry->pseudo, hardregs + regno);
 976                         name = hardregs[regno].name;
 977                 }
 978         } END_FOR_EACH_PTR(entry);
 979
 980         output_label(state, ".L%p", bb);
 981         FOR_EACH_PTR(bb->insns, insn) {
 982                 if (!insn->bb)
 983                         continue;
 984                 generate_one_insn(insn, state);
 985         } END_FOR_EACH_PTR(insn);
 986
 987         if (verbose) {
 988                 output_comment(state, "--- in ---");
 989                 FOR_EACH_PTR(state->inputs, entry) {
 990                         output_comment(state, "%s <- %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 991                 } END_FOR_EACH_PTR(entry);
 992                 output_comment(state, "--- spill ---");
 993                 FOR_EACH_PTR(state->internal, entry) {
 994                         output_comment(state, "%s <-> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 995                 } END_FOR_EACH_PTR(entry);
 996                 output_comment(state, "--- out ---");
 997                 FOR_EACH_PTR(state->outputs, entry) {
 998                         output_comment(state, "%s -> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 999                 } END_FOR_EACH_PTR(entry);
1000         }
1001         printf("\n");
1002 }
1003
1004 static void generate_list(struct basic_block_list *list, unsigned long generation)
1005 {
1006         struct basic_block *bb;
1007         FOR_EACH_PTR(list, bb) {
1008                 if (bb->generation == generation)
1009                         continue;
1010                 output_bb(bb, generation);
1011         } END_FOR_EACH_PTR(bb);
1012 }
1013
1014 static void output_bb(struct basic_block *bb, unsigned long generation)
1015 {
1016         struct bb_state state;
1017
1018         bb->generation = generation;
1019
1020         /* Make sure all parents have been generated first */
1021         generate_list(bb->parents, generation);
1022
1023         state.inputs = gather_storage(bb, STOR_IN);
1024         state.outputs = gather_storage(bb, STOR_OUT);
1025         state.internal = NULL;
1026         state.stack_offset = 0;
1027
1028         generate(bb, &state);
1029
1030         free_ptr_list(&state.inputs);
1031         free_ptr_list(&state.outputs);
1032
1033         /* Generate all children... */
1034         generate_list(bb->children, generation);
1035 }
1036
1037 static void output(struct entrypoint *ep)
1038 {
1039         unsigned long generation = ++bb_generation;
1040
1041         last_reg = -1;
1042
1043         /* Set up initial inter-bb storage links */
1044         set_up_storage(ep);
1045
1046         /* Show the results ... */
1047         output_bb(ep->entry->bb, generation);
1048
1049         /* Clear the storage hashes for the next function.. */
1050         free_storage();
1051 }
1052
1053 static int compile(struct symbol_list *list)
1054 {
1055         struct symbol *sym;
1056         FOR_EACH_PTR(list, sym) {
1057                 struct entrypoint *ep;
1058                 expand_symbol(sym);
1059                 ep = linearize_symbol(sym);
1060                 if (ep)
1061                         output(ep);
1062         } END_FOR_EACH_PTR(sym);
1063
1064         return 0;
1065 }
1066
1067 int main(int argc, char **argv)
1068 {
1069         return compile(sparse(argc, argv));
1070 }
1071