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