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         i = last_reg+1;
 336         if (i >= REGNO)
 337                 i = 0;
 338         last_reg = i;
 339         reg = hardregs + i;
 340         flush_reg(state, reg);
 341
 342 found:
 343         add_pseudo_reg(state, pseudo, reg);
 344         return reg;
 345 }
 346
 347 static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 348 {
 349         int i;
 350         struct hardreg *reg;
 351
 352         for (i = 0; i < REGNO; i++) {
 353                 pseudo_t p;
 354
 355                 reg = hardregs + i;
 356                 FOR_EACH_PTR(reg->contains, p) {
 357                         if (p == pseudo) {
 358                                 last_reg = i;
 359                                 output_comment(state, "found pseudo %s in reg %s", show_pseudo(pseudo), reg->name);
 360                                 return reg;
 361                         }
 362                 } END_FOR_EACH_PTR(p);
 363         }
 364         reg = target_reg(state, pseudo, target);
 365         return fill_reg(state, reg, pseudo);
 366 }
 367
 368 static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 369 {
 370         int i;
 371         struct hardreg *reg;
 372
 373         if (!src->busy)
 374                 return src;
 375
 376         reg = preferred_reg(state, target);
 377         if (reg && !reg->busy) {
 378                 output_comment(state, "copying %s to preferred target %s", show_pseudo(target), reg->name);
 379                 output_insn(state, "movl %s,%s", src->name, reg->name);
 380                 return reg;
 381         }
 382
 383         for (i = 0; i < REGNO; i++) {
 384                 struct hardreg *reg = hardregs + i;
 385                 if (!reg->busy) {
 386                         output_comment(state, "copying %s to %s", show_pseudo(target), reg->name);
 387                         output_insn(state, "movl %s,%s", src->name, reg->name);
 388                         return reg;
 389                 }
 390         }
 391
 392         flush_reg(state, src);
 393         return src;
 394 }
 395
 396 static const char *generic(struct bb_state *state, pseudo_t pseudo)
 397 {
 398         struct hardreg *reg;
 399
 400         switch (pseudo->type) {
 401         case PSEUDO_SYM:
 402         case PSEUDO_VAL:
 403                 return show_pseudo(pseudo);
 404         default:
 405                 reg = getreg(state, pseudo, NULL);
 406                 return reg->name;
 407         }
 408 }
 409
 410 static const char *address(struct bb_state *state, struct instruction *memop)
 411 {
 412         struct symbol *sym;
 413         struct hardreg *base;
 414         static char buffer[100];
 415         pseudo_t addr = memop->src;
 416
 417         switch(addr->type) {
 418         case PSEUDO_SYM:
 419                 sym = addr->sym;
 420                 if (sym->ctype.modifiers & MOD_NONLOCAL) {
 421                         sprintf(buffer, "%s+%d", show_ident(sym->ident), memop->offset);
 422                         return buffer;
 423                 }
 424                 sprintf(buffer, "%d+%s(SP)", memop->offset, show_ident(sym->ident));
 425                 return buffer;
 426         default:
 427                 base = getreg(state, addr, NULL);
 428                 sprintf(buffer, "%d(%s)", memop->offset, base->name);
 429                 return buffer;
 430         }
 431 }
 432
 433 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
 434 {
 435         switch(pseudo->type) {
 436         case PSEUDO_VAL:
 437                 return show_pseudo(pseudo);
 438         default:
 439                 return getreg(state, pseudo, NULL)->name;
 440         }
 441 }
 442
 443 static void generate_store(struct instruction *insn, struct bb_state *state)
 444 {
 445         output_insn(state, "mov.%d %s,%s", insn->size, reg_or_imm(state, insn->target), address(state, insn));
 446 }
 447
 448 static void generate_load(struct instruction *insn, struct bb_state *state)
 449 {
 450         const char *input = address(state, insn);
 451         output_insn(state, "mov.%d %s,%s", insn->size, input, target_reg(state, insn->target, NULL)->name);
 452 }
 453
 454 static const char* opcodes[] = {
 455         [OP_BADOP] = "bad_op",
 456
 457         /* Fn entrypoint */
 458         [OP_ENTRY] = "<entry-point>",
 459
 460         /* Terminator */
 461         [OP_RET] = "ret",
 462         [OP_BR] = "br",
 463         [OP_SWITCH] = "switch",
 464         [OP_INVOKE] = "invoke",
 465         [OP_COMPUTEDGOTO] = "jmp *",
 466         [OP_UNWIND] = "unwind",
 467
 468         /* Binary */
 469         [OP_ADD] = "add",
 470         [OP_SUB] = "sub",
 471         [OP_MUL] = "mul",
 472         [OP_DIV] = "div",
 473         [OP_MOD] = "mod",
 474         [OP_SHL] = "shl",
 475         [OP_SHR] = "shr",
 476
 477         /* Logical */
 478         [OP_AND] = "and",
 479         [OP_OR] = "or",
 480         [OP_XOR] = "xor",
 481         [OP_AND_BOOL] = "and-bool",
 482         [OP_OR_BOOL] = "or-bool",
 483
 484         /* Binary comparison */
 485         [OP_SET_EQ] = "seteq",
 486         [OP_SET_NE] = "setne",
 487         [OP_SET_LE] = "setle",
 488         [OP_SET_GE] = "setge",
 489         [OP_SET_LT] = "setlt",
 490         [OP_SET_GT] = "setgt",
 491         [OP_SET_B] = "setb",
 492         [OP_SET_A] = "seta",
 493         [OP_SET_BE] = "setbe",
 494         [OP_SET_AE] = "setae",
 495
 496         /* Uni */
 497         [OP_NOT] = "not",
 498         [OP_NEG] = "neg",
 499
 500         /* Special three-input */
 501         [OP_SEL] = "select",
 502
 503         /* Memory */
 504         [OP_MALLOC] = "malloc",
 505         [OP_FREE] = "free",
 506         [OP_ALLOCA] = "alloca",
 507         [OP_LOAD] = "load",
 508         [OP_STORE] = "store",
 509         [OP_SETVAL] = "set",
 510         [OP_GET_ELEMENT_PTR] = "getelem",
 511
 512         /* Other */
 513         [OP_PHI] = "phi",
 514         [OP_PHISOURCE] = "phisrc",
 515         [OP_CAST] = "cast",
 516         [OP_PTRCAST] = "ptrcast",
 517         [OP_CALL] = "call",
 518         [OP_VANEXT] = "va_next",
 519         [OP_VAARG] = "va_arg",
 520         [OP_SLICE] = "slice",
 521         [OP_SNOP] = "snop",
 522         [OP_LNOP] = "lnop",
 523         [OP_NOP] = "nop",
 524         [OP_DEATHNOTE] = "dead",
 525         [OP_ASM] = "asm",
 526
 527         /* Sparse tagging (line numbers, context, whatever) */
 528         [OP_CONTEXT] = "context",
 529 };
 530
 531 static void generate_binop(struct bb_state *state, struct instruction *insn)
 532 {
 533         const char *op = opcodes[insn->opcode];
 534         struct hardreg *src = getreg(state, insn->src1, insn->target);
 535         struct hardreg *dst = copy_reg(state, src, insn->target);
 536
 537         output_insn(state, "%s.%d %s,%s", op, insn->size, reg_or_imm(state, insn->src2), dst->name);
 538         add_pseudo_reg(state, insn->target, dst);
 539 }
 540
 541 static void mark_pseudo_dead(struct bb_state *state, pseudo_t pseudo)
 542 {
 543         int i;
 544
 545         for (i = 0; i < REGNO; i++) {
 546                 pseudo_t p;
 547                 struct hardreg *reg = hardregs + i;
 548                 FOR_EACH_PTR(reg->contains, p) {
 549                         if (p != pseudo)
 550                                 continue;
 551                         if (CURRENT_TAG(p) & TAG_DEAD)
 552                                 continue;
 553                         output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
 554                         TAG_CURRENT(p, TAG_DEAD);
 555                         reg->busy--;
 556                 } END_FOR_EACH_PTR(p);
 557         }
 558 }
 559
 560 /*
 561  * A PHI source can define a pseudo that we already
 562  * have in another register. We need to invalidate the
 563  * old register so that we don't end up with the same
 564  * pseudo in "two places".
 565  */
 566 static void remove_pseudo_reg(struct bb_state *state, pseudo_t pseudo)
 567 {
 568         int i;
 569
 570         output_comment(state, "pseudo %s died", show_pseudo(pseudo));
 571         for (i = 0; i < REGNO; i++) {
 572                 struct hardreg *reg = hardregs + i;
 573                 if (remove_pseudo(&reg->contains, pseudo))
 574                         output_comment(state, "removed pseudo %s from reg %s", show_pseudo(pseudo), reg->name);
 575         }
 576 }
 577
 578 static void generate_phisource(struct instruction *insn, struct bb_state *state)
 579 {
 580         struct instruction *user;
 581         struct hardreg *reg;
 582
 583         /* Mark all the target pseudos dead first */
 584         FOR_EACH_PTR(insn->phi_users, user) {
 585                 mark_pseudo_dead(state, user->target);
 586         } END_FOR_EACH_PTR(user);
 587
 588         reg = NULL;
 589         FOR_EACH_PTR(insn->phi_users, user) {
 590                 if (!reg)
 591                         reg = getreg(state, insn->phi_src, user->target);
 592                 remove_pseudo_reg(state, user->target);
 593                 add_pseudo_reg(state, user->target, reg);
 594         } END_FOR_EACH_PTR(user);
 595 }
 596
 597 static void generate_output_storage(struct bb_state *state);
 598
 599 static void generate_branch(struct bb_state *state, struct instruction *br)
 600 {
 601         if (br->cond) {
 602                 struct hardreg *reg = getreg(state, br->cond, NULL);
 603                 output_insn(state, "testl %s,%s", reg->name, reg->name);
 604         }
 605         generate_output_storage(state);
 606         if (br->cond)
 607                 output_insn(state, "je .L%p", br->bb_false);
 608         output_insn(state, "jmp .L%p", br->bb_true);
 609 }
 610
 611 static void generate_ret(struct bb_state *state, struct instruction *ret)
 612 {
 613         if (ret->src && ret->src != VOID) {
 614                 struct hardreg *wants = hardregs+0;
 615                 struct hardreg *reg = getreg(state, ret->src, NULL);
 616                 if (reg != wants)
 617                         output_insn(state, "movl %s,%s", reg->name, wants->name);
 618         }
 619         output_insn(state, "ret");
 620 }
 621
 622 /*
 623  * Fake "call" linearization just as a taster..
 624  */
 625 static void generate_call(struct bb_state *state, struct instruction *insn)
 626 {
 627         int offset = 0;
 628         pseudo_t arg;
 629
 630         FOR_EACH_PTR(insn->arguments, arg) {
 631                 output_insn(state, "pushl %s", generic(state, arg));
 632                 offset += 4;
 633         } END_FOR_EACH_PTR(arg);
 634         flush_reg(state, hardregs+0);
 635         flush_reg(state, hardregs+1);
 636         flush_reg(state, hardregs+2);
 637         output_insn(state, "call %s", show_pseudo(insn->func));
 638         if (offset)
 639                 output_insn(state, "addl $%d,%%esp", offset);
 640         add_pseudo_reg(state, insn->target, hardregs+0);
 641 }
 642
 643 static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 644 {
 645         if (verbose)
 646                 output_comment(state, "%s", show_instruction(insn));
 647
 648         switch (insn->opcode) {
 649         case OP_ENTRY: {
 650                 struct symbol *sym = insn->bb->ep->name;
 651                 const char *name = show_ident(sym->ident);
 652                 if (sym->ctype.modifiers & MOD_STATIC)
 653                         printf("\n\n%s:\n", name);
 654                 else
 655                         printf("\n\n.globl %s\n%s:\n", name, name);
 656                 break;
 657         }
 658
 659         /*
 660          * OP_PHI doesn't actually generate any code. It has been
 661          * done by the storage allocator and the OP_PHISOURCE.
 662          */
 663         case OP_PHI:
 664                 break;
 665
 666         case OP_PHISOURCE:
 667                 generate_phisource(insn, state);
 668                 break;
 669
 670         /*
 671          * OP_SETVAL likewise doesn't actually generate any
 672          * code. On use, the "def" of the pseudo will be
 673          * looked up.
 674          */
 675         case OP_SETVAL:
 676                 break;
 677
 678         case OP_STORE:
 679                 generate_store(insn, state);
 680                 break;
 681
 682         case OP_LOAD:
 683                 generate_load(insn, state);
 684                 break;
 685
 686         case OP_DEATHNOTE:
 687                 mark_pseudo_dead(state, insn->target);
 688                 break;
 689
 690         case OP_BINARY ... OP_BINARY_END:
 691         case OP_BINCMP ... OP_BINCMP_END:
 692                 generate_binop(state, insn);
 693                 break;
 694
 695         case OP_BR:
 696                 generate_branch(state, insn);
 697                 break;
 698
 699         case OP_CALL:
 700                 generate_call(state, insn);
 701                 break;
 702
 703         case OP_RET:
 704                 generate_ret(state, insn);
 705                 break;
 706
 707         default:
 708                 output_insn(state, "unimplemented: %s", show_instruction(insn));
 709                 break;
 710         }
 711 }
 712
 713 #define VERY_BUSY 1000
 714 #define REG_FIXED 2000
 715
 716 static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, pseudo_t pseudo, struct storage *storage)
 717 {
 718         int i;
 719         struct hardreg *out;
 720
 721         switch (storage->type) {
 722         case REG_REG:
 723                 out = hardregs + storage->regno;
 724                 if (reg == out)
 725                         return;
 726                 output_insn(state, "movl %s,%s", reg->name, out->name);
 727                 return;
 728         case REG_UDEF:
 729                 if (reg->busy < VERY_BUSY) {
 730                         storage->type = REG_REG;
 731                         storage->regno = reg - hardregs;
 732                         reg->busy = REG_FIXED;
 733                         return;
 734                 }
 735
 736                 /* Try to find a non-busy register.. */
 737                 for (i = 0; i < REGNO; i++) {
 738                         out = hardregs + i;
 739                         if (out->busy)
 740                                 continue;
 741                         output_insn(state, "movl %s,%s", reg->name, out->name);
 742                         storage->type = REG_REG;
 743                         storage->regno = i;
 744                         reg->busy = REG_FIXED;
 745                         return;
 746                 }
 747
 748                 /* Fall back on stack allocation ... */
 749                 alloc_stack(state, storage);
 750                 /* Fallthroigh */
 751         default:
 752                 output_insn(state, "movl %s,%s", reg->name, show_memop(storage));
 753                 return;
 754         }
 755 }
 756
 757 static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage)
 758 {
 759         struct hardreg *out;
 760
 761         switch (storage->type) {
 762         case REG_UDEF:
 763                 alloc_stack(state, storage);
 764         default:
 765                 output_insn(state, "movl %s,%s", show_pseudo(src), show_memop(storage));
 766                 break;
 767         case REG_REG:
 768                 out = hardregs + storage->regno;
 769                 output_insn(state, "movl %s,%s", show_pseudo(src), out->name);
 770         }
 771 }
 772
 773 static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out)
 774 {
 775         int i;
 776         struct storage_hash *in;
 777         struct instruction *def;
 778
 779         /* Is that pseudo a constant value? */
 780         switch (pseudo->type) {
 781         case PSEUDO_VAL:
 782                 write_val_to_storage(state, pseudo, out);
 783                 return;
 784         case PSEUDO_REG:
 785                 def = pseudo->def;
 786                 if (def->opcode == OP_SETVAL) {
 787                         write_val_to_storage(state, def->symbol, out);
 788                         return;
 789                 }
 790         default:
 791                 break;
 792         }
 793
 794         /* See if we have that pseudo in a register.. */
 795         for (i = 0; i < REGNO; i++) {
 796                 struct hardreg *reg = hardregs + i;
 797                 pseudo_t p;
 798
 799                 FOR_EACH_PTR(reg->contains, p) {
 800                         if (p == pseudo) {
 801                                 write_reg_to_storage(state, reg, pseudo, out);
 802                                 return;
 803                         }
 804                 } END_FOR_EACH_PTR(p);
 805         }
 806
 807         /* Do we have it in another storage? */
 808         in = find_storage_hash(pseudo, state->internal);
 809         if (!in) {
 810                 in = find_storage_hash(pseudo, state->inputs);
 811                 /* Undefined? */
 812                 if (!in)
 813                         return;
 814         }
 815         switch (out->type) {
 816         case REG_UDEF:
 817                 *out = *in->storage;
 818                 break;
 819         case REG_REG:
 820                 output_insn(state, "movl %s,%s", show_memop(in->storage), hardregs[out->regno].name);
 821                 break;
 822         default:
 823                 output_insn(state, "movl %s,tmp", show_memop(in->storage));
 824                 output_insn(state, "movl tmp,%s", show_memop(out));
 825                 break;
 826         }
 827         return;
 828 }
 829
 830 static int final_pseudo_flush(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 831 {
 832         struct storage_hash *hash;
 833         struct storage *out;
 834         struct hardreg *dst;
 835
 836         /*
 837          * Since this pseudo is live at exit, we'd better have output
 838          * storage for it..
 839          */
 840         hash = find_storage_hash(pseudo, state->outputs);
 841         if (!hash)
 842                 return 1;
 843         out = hash->storage;
 844
 845         /* If the output is in a register, try to get it there.. */
 846         if (out->type == REG_REG) {
 847                 dst = hardregs + out->regno;
 848                 /*
 849                  * Two good cases: nobody is using the right register,
 850                  * or we've already set it aside for output..
 851                  */
 852                 if (!dst->busy || dst->busy > VERY_BUSY)
 853                         goto copy_to_dst;
 854
 855                 /* Aiee. Try to keep it in a register.. */
 856                 dst = empty_reg(state);
 857                 if (dst)
 858                         goto copy_to_dst;
 859
 860                 return 0;
 861         }
 862
 863         /* If the output is undefined, let's see if we can put it in a register.. */
 864         if (out->type == REG_UDEF) {
 865                 dst = empty_reg(state);
 866                 if (dst) {
 867                         out->type = REG_REG;
 868                         out->regno = dst - hardregs;
 869                         goto copy_to_dst;
 870                 }
 871                 /* Uhhuh. Not so good. No empty registers right now */
 872                 return 0;
 873         }
 874
 875         /* If we know we need to flush it, just do so already .. */
 876         output_insn(state, "movl %s,%s", reg->name, show_memop(out));
 877         return 1;
 878
 879 copy_to_dst:
 880         if (reg == dst)
 881                 return 1;
 882         output_insn(state, "movl %s,%s", reg->name, dst->name);
 883         add_pseudo_reg(state, pseudo, dst);
 884         return 1;
 885 }
 886
 887 /*
 888  * This tries to make sure that we put all the pseudos that are
 889  * live on exit into the proper storage
 890  */
 891 static void generate_output_storage(struct bb_state *state)
 892 {
 893         struct storage_hash *entry;
 894
 895         /* Go through the fixed outputs, making sure we have those regs free */
 896         FOR_EACH_PTR(state->outputs, entry) {
 897                 struct storage *out = entry->storage;
 898                 if (out->type == REG_REG) {
 899                         struct hardreg *reg = hardregs + out->regno;
 900                         pseudo_t p;
 901                         int flushme = 0;
 902
 903                         reg->busy = REG_FIXED;
 904                         FOR_EACH_PTR(reg->contains, p) {
 905                                 if (p == entry->pseudo) {
 906                                         flushme = -100;
 907                                         continue;
 908                                 }
 909                                 if (CURRENT_TAG(p) & TAG_DEAD)
 910                                         continue;
 911
 912                                 /* Try to write back the pseudo to where it should go ... */
 913                                 if (final_pseudo_flush(state, p, reg)) {
 914                                         DELETE_CURRENT_PTR(p);
 915                                         reg->busy--;
 916                                         continue;
 917                                 }
 918                                 flushme++;
 919                         } END_FOR_EACH_PTR(p);
 920                         PACK_PTR_LIST(&reg->contains);
 921                         if (flushme > 0)
 922                                 flush_reg(state, reg);
 923                 }
 924         } END_FOR_EACH_PTR(entry);
 925
 926         FOR_EACH_PTR(state->outputs, entry) {
 927                 fill_output(state, entry->pseudo, entry->storage);
 928         } END_FOR_EACH_PTR(entry);
 929 }
 930
 931 static void generate(struct basic_block *bb, struct bb_state *state)
 932 {
 933         int i;
 934         struct storage_hash *entry;
 935         struct instruction *insn;
 936
 937         for (i = 0; i < REGNO; i++) {
 938                 free_ptr_list(&hardregs[i].contains);
 939                 hardregs[i].busy = 0;
 940                 hardregs[i].used = 0;
 941         }
 942
 943         FOR_EACH_PTR(state->inputs, entry) {
 944                 struct storage *storage = entry->storage;
 945                 const char *name = show_storage(storage);
 946                 if (storage->type == REG_REG) {
 947                         int regno = storage->regno;
 948                         add_pseudo_reg(state, entry->pseudo, hardregs + regno);
 949                         name = hardregs[regno].name;
 950                 }
 951         } END_FOR_EACH_PTR(entry);
 952
 953         output_label(state, ".L%p", bb);
 954         FOR_EACH_PTR(bb->insns, insn) {
 955                 if (!insn->bb)
 956                         continue;
 957                 generate_one_insn(insn, state);
 958         } END_FOR_EACH_PTR(insn);
 959
 960         if (verbose) {
 961                 output_comment(state, "--- in ---");
 962                 FOR_EACH_PTR(state->inputs, entry) {
 963                         output_comment(state, "%s <- %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 964                 } END_FOR_EACH_PTR(entry);
 965                 output_comment(state, "--- spill ---");
 966                 FOR_EACH_PTR(state->internal, entry) {
 967                         output_comment(state, "%s <-> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 968                 } END_FOR_EACH_PTR(entry);
 969                 output_comment(state, "--- out ---");
 970                 FOR_EACH_PTR(state->outputs, entry) {
 971                         output_comment(state, "%s -> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
 972                 } END_FOR_EACH_PTR(entry);
 973         }
 974         printf("\n");
 975 }
 976
 977 static void generate_list(struct basic_block_list *list, unsigned long generation)
 978 {
 979         struct basic_block *bb;
 980         FOR_EACH_PTR(list, bb) {
 981                 if (bb->generation == generation)
 982                         continue;
 983                 output_bb(bb, generation);
 984         } END_FOR_EACH_PTR(bb);
 985 }
 986
 987 static void output_bb(struct basic_block *bb, unsigned long generation)
 988 {
 989         struct bb_state state;
 990
 991         bb->generation = generation;
 992
 993         /* Make sure all parents have been generated first */
 994         generate_list(bb->parents, generation);
 995
 996         state.inputs = gather_storage(bb, STOR_IN);
 997         state.outputs = gather_storage(bb, STOR_OUT);
 998         state.internal = NULL;
 999         state.stack_offset = 0;
1000
1001         generate(bb, &state);
1002
1003         free_ptr_list(&state.inputs);
1004         free_ptr_list(&state.outputs);
1005
1006         /* Generate all children... */
1007         generate_list(bb->children, generation);
1008 }
1009
1010 static void output(struct entrypoint *ep)
1011 {
1012         unsigned long generation = ++bb_generation;
1013
1014         last_reg = -1;
1015
1016         /* Set up initial inter-bb storage links */
1017         set_up_storage(ep);
1018
1019         /* Show the results ... */
1020         output_bb(ep->entry->bb, generation);
1021
1022         /* Clear the storage hashes for the next function.. */
1023         free_storage();
1024 }
1025
1026 static int compile(struct symbol_list *list)
1027 {
1028         struct symbol *sym;
1029         FOR_EACH_PTR(list, sym) {
1030                 struct entrypoint *ep;
1031                 expand_symbol(sym);
1032                 ep = linearize_symbol(sym);
1033                 if (ep)
1034                         output(ep);
1035         } END_FOR_EACH_PTR(sym);
1036
1037         return 0;
1038 }
1039
1040 int main(int argc, char **argv)
1041 {
1042         return compile(sparse(argc, argv));
1043 }
1044