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 <string.h>
   8 #include <assert.h>
   9
  10 #include "symbol.h"
  11 #include "expression.h"
  12 #include "linearize.h"
  13 #include "flow.h"
  14 #include "storage.h"
  15
  16 static const char* opcodes[] = {
  17         [OP_BADOP] = "bad_op",
  18
  19         /* Fn entrypoint */
  20         [OP_ENTRY] = "<entry-point>",
  21
  22         /* Terminator */
  23         [OP_RET] = "ret",
  24         [OP_BR] = "br",
  25         [OP_SWITCH] = "switch",
  26         [OP_INVOKE] = "invoke",
  27         [OP_COMPUTEDGOTO] = "jmp *",
  28         [OP_UNWIND] = "unwind",
  29
  30         /* Binary */
  31         [OP_ADD] = "add",
  32         [OP_SUB] = "sub",
  33         [OP_MUL] = "mul",
  34         [OP_DIV] = "div",
  35         [OP_MOD] = "mod",
  36         [OP_SHL] = "shl",
  37         [OP_SHR] = "shr",
  38
  39         /* Logical */
  40         [OP_AND] = "and",
  41         [OP_OR] = "or",
  42         [OP_XOR] = "xor",
  43         [OP_AND_BOOL] = "and-bool",
  44         [OP_OR_BOOL] = "or-bool",
  45
  46         /* Binary comparison */
  47         [OP_SET_EQ] = "seteq",
  48         [OP_SET_NE] = "setne",
  49         [OP_SET_LE] = "setle",
  50         [OP_SET_GE] = "setge",
  51         [OP_SET_LT] = "setlt",
  52         [OP_SET_GT] = "setgt",
  53         [OP_SET_B] = "setb",
  54         [OP_SET_A] = "seta",
  55         [OP_SET_BE] = "setbe",
  56         [OP_SET_AE] = "setae",
  57
  58         /* Uni */
  59         [OP_NOT] = "not",
  60         [OP_NEG] = "neg",
  61
  62         /* Special three-input */
  63         [OP_SEL] = "select",
  64
  65         /* Memory */
  66         [OP_MALLOC] = "malloc",
  67         [OP_FREE] = "free",
  68         [OP_ALLOCA] = "alloca",
  69         [OP_LOAD] = "load",
  70         [OP_STORE] = "store",
  71         [OP_SETVAL] = "set",
  72         [OP_GET_ELEMENT_PTR] = "getelem",
  73
  74         /* Other */
  75         [OP_PHI] = "phi",
  76         [OP_PHISOURCE] = "phisrc",
  77         [OP_CAST] = "cast",
  78         [OP_PTRCAST] = "ptrcast",
  79         [OP_CALL] = "call",
  80         [OP_VANEXT] = "va_next",
  81         [OP_VAARG] = "va_arg",
  82         [OP_SLICE] = "slice",
  83         [OP_SNOP] = "snop",
  84         [OP_LNOP] = "lnop",
  85         [OP_NOP] = "nop",
  86         [OP_DEATHNOTE] = "dead",
  87         [OP_ASM] = "asm",
  88
  89         /* Sparse tagging (line numbers, context, whatever) */
  90         [OP_CONTEXT] = "context",
  91 };
  92
  93 static int last_reg, stack_offset;
  94
  95 struct hardreg {
  96         const char *name;
  97         struct pseudo_list *contains;
  98         unsigned busy:16,
  99                  dead:8,
 100                  used:1;
 101 };
 102
 103 #define TAG_DEAD 1
 104 #define TAG_DIRTY 2
 105
 106 /* Our "switch" generation is very very stupid. */
 107 #define SWITCH_REG (1)
 108
 109 static void output_bb(struct basic_block *bb, unsigned long generation);
 110
 111 /*
 112  * We only know about the caller-clobbered registers
 113  * right now.
 114  */
 115 static struct hardreg hardregs[] = {
 116         { .name = "%eax" },
 117         { .name = "%edx" },
 118         { .name = "%ecx" },
 119         { .name = "%ebx" },
 120         { .name = "%esi" },
 121         { .name = "%edi" },
 122
 123         { .name = "%ebp" },
 124         { .name = "%esp" },
 125 };
 126 #define REGNO 6
 127 #define REG_EBP 6
 128 #define REG_ESP 7
 129
 130 struct bb_state {
 131         struct position pos;
 132         struct storage_hash_list *inputs;
 133         struct storage_hash_list *outputs;
 134         struct storage_hash_list *internal;
 135
 136         /* CC cache.. */
 137         int cc_opcode, cc_dead;
 138         pseudo_t cc_target;
 139 };
 140
 141 enum optype {
 142         OP_UNDEF,
 143         OP_REG,
 144         OP_VAL,
 145         OP_MEM,
 146         OP_ADDR,
 147 };
 148
 149 struct operand {
 150         enum optype type;
 151         int size;
 152         union {
 153                 struct hardreg *reg;
 154                 long long value;
 155                 struct /* OP_MEM and OP_ADDR */ {
 156                         unsigned int offset;
 157                         unsigned int scale;
 158                         struct symbol *sym;
 159                         struct hardreg *base;
 160                         struct hardreg *index;
 161                 };
 162         };
 163 };
 164
 165 static const char *show_op(struct bb_state *state, struct operand *op)
 166 {
 167         static char buf[256][4];
 168         static int bufnr;
 169         char *p, *ret;
 170         int nr;
 171
 172         nr = (bufnr + 1) & 3;
 173         bufnr = nr;
 174         ret = p = buf[nr];
 175
 176         switch (op->type) {
 177         case OP_UNDEF:
 178                 return "undef";
 179         case OP_REG:
 180                 return op->reg->name;
 181         case OP_VAL:
 182                 sprintf(p, "$%lld", op->value);
 183                 break;
 184         case OP_MEM:
 185         case OP_ADDR:
 186                 if (op->offset)
 187                         p += sprintf(p, "%d", op->offset);
 188                 if (op->sym)
 189                         p += sprintf(p, "%s%s",
 190                                 op->offset ? "+" : "",
 191                                 show_ident(op->sym->ident));
 192                 if (op->base || op->index) {
 193                         p += sprintf(p, "(%s%s%s",
 194                                 op->base ? op->base->name : "",
 195                                 (op->base && op->index) ? "," : "",
 196                                 op->index ? op->index->name : "");
 197                         if (op->scale > 1)
 198                                 p += sprintf(p, ",%d", op->scale);
 199                         *p++ = ')';
 200                         *p = '\0';
 201                 }
 202                 break;
 203         }
 204         return ret;
 205 }
 206
 207 static struct storage_hash *find_storage_hash(pseudo_t pseudo, struct storage_hash_list *list)
 208 {
 209         struct storage_hash *entry;
 210         FOR_EACH_PTR(list, entry) {
 211                 if (entry->pseudo == pseudo)
 212                         return entry;
 213         } END_FOR_EACH_PTR(entry);
 214         return NULL;
 215 }
 216
 217 static struct storage_hash *find_or_create_hash(pseudo_t pseudo, struct storage_hash_list **listp)
 218 {
 219         struct storage_hash *entry;
 220
 221         entry = find_storage_hash(pseudo, *listp);
 222         if (!entry) {
 223                 entry = alloc_storage_hash(alloc_storage());
 224                 entry->pseudo = pseudo;
 225                 add_ptr_list(listp, entry);
 226         }
 227         return entry;
 228 }
 229
 230 /* Eventually we should just build it up in memory */
 231 static void output_line(struct bb_state *state, const char *fmt, ...)
 232 {
 233         va_list args;
 234
 235         va_start(args, fmt);
 236         vprintf(fmt, args);
 237         va_end(args);
 238 }
 239
 240 static void output_label(struct bb_state *state, const char *fmt, ...)
 241 {
 242         static char buffer[512];
 243         va_list args;
 244
 245         va_start(args, fmt);
 246         vsnprintf(buffer, sizeof(buffer), fmt, args);
 247         va_end(args);
 248
 249         output_line(state, "%s:\n", buffer);
 250 }
 251
 252 static void output_insn(struct bb_state *state, const char *fmt, ...)
 253 {
 254         static char buffer[512];
 255         va_list args;
 256
 257         va_start(args, fmt);
 258         vsnprintf(buffer, sizeof(buffer), fmt, args);
 259         va_end(args);
 260
 261         output_line(state, "\t%s\n", buffer);
 262 }
 263
 264 static void output_comment(struct bb_state *state, const char *fmt, ...)
 265 {
 266         static char buffer[512];
 267         va_list args;
 268
 269         if (!verbose)
 270                 return;
 271         va_start(args, fmt);
 272         vsnprintf(buffer, sizeof(buffer), fmt, args);
 273         va_end(args);
 274
 275         output_line(state, "\t# %s\n", buffer);
 276 }
 277
 278 static const char *show_memop(struct storage *storage)
 279 {
 280         static char buffer[1000];
 281
 282         if (!storage)
 283                 return "undef";
 284         switch (storage->type) {
 285         case REG_FRAME:
 286                 sprintf(buffer, "%d(FP)", storage->offset);
 287                 break;
 288         case REG_STACK:
 289                 sprintf(buffer, "%d(SP)", storage->offset);
 290                 break;
 291         case REG_REG:
 292                 return hardregs[storage->regno].name;
 293         default:
 294                 return show_storage(storage);
 295         }
 296         return buffer;
 297 }
 298
 299 static void alloc_stack(struct bb_state *state, struct storage *storage)
 300 {
 301         storage->type = REG_STACK;
 302         storage->offset = stack_offset;
 303         stack_offset += 4;
 304 }
 305
 306 /*
 307  * Can we re-generate the pseudo, so that we don't need to
 308  * flush it to memory? We can regenerate:
 309  *  - immediates and symbol addresses
 310  *  - pseudos we got as input in non-registers
 311  *  - pseudos we've already saved off earlier..
 312  */
 313 static int can_regenerate(struct bb_state *state, pseudo_t pseudo)
 314 {
 315         struct storage_hash *in;
 316
 317         switch (pseudo->type) {
 318         case PSEUDO_VAL:
 319         case PSEUDO_SYM:
 320                 return 1;
 321
 322         default:
 323                 in = find_storage_hash(pseudo, state->inputs);
 324                 if (in && in->storage->type != REG_REG)
 325                         return 1;
 326                 in = find_storage_hash(pseudo, state->internal);
 327                 if (in)
 328                         return 1;
 329         }
 330         return 0;
 331 }
 332
 333 static void flush_one_pseudo(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
 334 {
 335         struct storage_hash *out;
 336         struct storage *storage;
 337
 338         if (can_regenerate(state, pseudo))
 339                 return;
 340
 341         output_comment(state, "flushing %s from %s", show_pseudo(pseudo), hardreg->name);
 342         out = find_storage_hash(pseudo, state->internal);
 343         if (!out) {
 344                 out = find_storage_hash(pseudo, state->outputs);
 345                 if (!out)
 346                         out = find_or_create_hash(pseudo, &state->internal);
 347         }
 348         storage = out->storage;
 349         switch (storage->type) {
 350         default:
 351                 /*
 352                  * Aieee - the next user wants it in a register, but we
 353                  * need to flush it to memory in between. Which means that
 354                  * we need to allocate an internal one, dammit..
 355                  */
 356                 out = find_or_create_hash(pseudo, &state->internal);
 357                 storage = out->storage;
 358                 /* Fall through */
 359         case REG_UDEF:
 360                 alloc_stack(state, storage);
 361                 /* Fall through */
 362         case REG_STACK:
 363                 output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage));
 364                 break;
 365         }
 366 }
 367
 368 /* Flush a hardreg out to the storage it has.. */
 369 static void flush_reg(struct bb_state *state, struct hardreg *hardreg)
 370 {
 371         pseudo_t pseudo;
 372
 373         if (!hardreg->busy)
 374                 return;
 375         hardreg->busy = 0;
 376         hardreg->dead = 0;
 377         hardreg->used = 1;
 378         FOR_EACH_PTR(hardreg->contains, pseudo) {
 379                 if (CURRENT_TAG(pseudo) & TAG_DEAD)
 380                         continue;
 381                 if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
 382                         continue;
 383                 flush_one_pseudo(state, hardreg, pseudo);
 384         } END_FOR_EACH_PTR(pseudo);
 385         free_ptr_list(&hardreg->contains);
 386 }
 387
 388 static struct storage_hash *find_pseudo_storage(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 389 {
 390         struct storage_hash *src;
 391
 392         src = find_storage_hash(pseudo, state->internal);
 393         if (!src) {
 394                 src = find_storage_hash(pseudo, state->inputs);
 395                 if (!src) {
 396                         src = find_storage_hash(pseudo, state->outputs);
 397                         /* Undefined? Screw it! */
 398                         if (!src)
 399                                 return NULL;
 400
 401                         /*
 402                          * If we found output storage, it had better be local stack
 403                          * that we flushed to earlier..
 404                          */
 405                         if (src->storage->type != REG_STACK)
 406                                 return NULL;
 407                 }
 408         }
 409
 410         /*
 411          * Incoming pseudo with out any pre-set storage allocation?
 412          * We can make up our own, and obviously prefer to get it
 413          * in the register we already selected (if it hasn't been
 414          * used yet).
 415          */
 416         if (src->storage->type == REG_UDEF) {
 417                 if (reg && !reg->used) {
 418                         src->storage->type = REG_REG;
 419                         src->storage->regno = reg - hardregs;
 420                         return NULL;
 421                 }
 422                 alloc_stack(state, src->storage);
 423         }
 424         return src;
 425 }
 426
 427 static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 428 {
 429         pseudo_t p;
 430
 431         FOR_EACH_PTR(reg->contains, p) {
 432                 if (p != pseudo)
 433                         continue;
 434                 if (CURRENT_TAG(p) & TAG_DEAD)
 435                         continue;
 436                 output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
 437                 TAG_CURRENT(p, TAG_DEAD);
 438                 reg->dead++;
 439         } END_FOR_EACH_PTR(p);
 440 }
 441
 442 static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 443 {
 444         output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name);
 445         add_ptr_list_tag(&reg->contains, pseudo, TAG_DIRTY);
 446         reg->busy++;
 447 }
 448
 449 static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target)
 450 {
 451         struct storage_hash *dst;
 452
 453         dst = find_storage_hash(target, state->outputs);
 454         if (dst) {
 455                 struct storage *storage = dst->storage;
 456                 if (storage->type == REG_REG)
 457                         return hardregs + storage->regno;
 458         }
 459         return NULL;
 460 }
 461
 462 static struct hardreg *empty_reg(struct bb_state *state)
 463 {
 464         int i;
 465         struct hardreg *reg = hardregs;
 466
 467         for (i = 0; i < REGNO; i++, reg++) {
 468                 if (!reg->busy)
 469                         return reg;
 470         }
 471         return NULL;
 472 }
 473
 474 static struct hardreg *target_reg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 475 {
 476         int i;
 477         struct hardreg *reg;
 478
 479         /* First, see if we have a preferred target register.. */
 480         reg = preferred_reg(state, target);
 481         if (reg && !reg->busy)
 482                 goto found;
 483
 484         reg = empty_reg(state);
 485         if (reg)
 486                 goto found;
 487
 488         i = last_reg+1;
 489         if (i >= REGNO)
 490                 i = 0;
 491         last_reg = i;
 492         reg = hardregs + i;
 493         flush_reg(state, reg);
 494
 495 found:
 496         add_pseudo_reg(state, pseudo, reg);
 497         return reg;
 498 }
 499
 500 static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo)
 501 {
 502         int i;
 503         struct hardreg *reg;
 504
 505         for (i = 0; i < REGNO; i++) {
 506                 pseudo_t p;
 507
 508                 reg = hardregs + i;
 509                 FOR_EACH_PTR(reg->contains, p) {
 510                         if (p == pseudo) {
 511                                 last_reg = i;
 512                                 output_comment(state, "found pseudo %s in reg %s", show_pseudo(pseudo), reg->name);
 513                                 return reg;
 514                         }
 515                 } END_FOR_EACH_PTR(p);
 516         }
 517         return NULL;
 518 }
 519
 520 static void flush_cc_cache_to_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 521 {
 522         int opcode = state->cc_opcode;
 523
 524         state->cc_opcode = 0;
 525         state->cc_target = NULL;
 526         output_insn(state, "%s %s", opcodes[opcode], reg->name);
 527 }
 528
 529 static void flush_cc_cache(struct bb_state *state)
 530 {
 531         pseudo_t pseudo = state->cc_target;
 532
 533         if (pseudo) {
 534                 struct hardreg *dst;
 535
 536                 state->cc_target = NULL;
 537
 538                 if (!state->cc_dead) {
 539                         dst = target_reg(state, pseudo, pseudo);
 540                         flush_cc_cache_to_reg(state, pseudo, dst);
 541                 }
 542         }
 543 }
 544
 545 static void add_cc_cache(struct bb_state *state, int opcode, pseudo_t pseudo)
 546 {
 547         assert(!state->cc_target);
 548         state->cc_target = pseudo;
 549         state->cc_opcode = opcode;
 550         state->cc_dead = 0;
 551         output_comment(state, "caching %s", opcodes[opcode]);
 552 }
 553
 554 /* Fill a hardreg with the pseudo it has */
 555 static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
 556 {
 557         struct storage_hash *src;
 558         struct instruction *def;
 559
 560         if (state->cc_target == pseudo) {
 561                 flush_cc_cache_to_reg(state, pseudo, hardreg);
 562                 return hardreg;
 563         }
 564
 565         switch (pseudo->type) {
 566         case PSEUDO_VAL:
 567                 output_insn(state, "movl $%lld,%s", pseudo->value, hardreg->name);
 568                 break;
 569         case PSEUDO_SYM:
 570                 output_insn(state, "movl $<%s>,%s", show_pseudo(pseudo), hardreg->name);
 571                 break;
 572         case PSEUDO_ARG:
 573         case PSEUDO_REG:
 574                 def = pseudo->def;
 575                 if (def->opcode == OP_SETVAL) {
 576                         output_insn(state, "movl $<%s>,%s", show_pseudo(def->target), hardreg->name);
 577                         break;
 578                 }
 579                 src = find_pseudo_storage(state, pseudo, hardreg);
 580                 if (!src)
 581                         break;
 582                 if (src->flags & TAG_DEAD)
 583                         mark_reg_dead(state, pseudo, hardreg);
 584                 output_insn(state, "mov.%d %s,%s", 32, show_memop(src->storage), hardreg->name);
 585                 break;
 586         default:
 587                 output_insn(state, "reload %s from %s", hardreg->name, show_pseudo(pseudo));
 588                 break;
 589         }
 590         return hardreg;
 591 }
 592
 593 static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 594 {
 595         struct hardreg *reg;
 596
 597         reg = find_in_reg(state, pseudo);
 598         if (reg)
 599                 return reg;
 600         reg = target_reg(state, pseudo, target);
 601         return fill_reg(state, reg, pseudo);
 602 }
 603
 604 static void move_reg(struct bb_state *state, struct hardreg *src, struct hardreg *dst)
 605 {
 606         output_insn(state, "movl %s,%s", src->name, dst->name);
 607 }
 608
 609 static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 610 {
 611         int i;
 612         struct hardreg *reg;
 613
 614         if (!src->busy)
 615                 return src;
 616
 617         reg = preferred_reg(state, target);
 618         if (reg && !reg->busy) {
 619                 output_comment(state, "copying %s to preferred target %s", show_pseudo(target), reg->name);
 620                 move_reg(state, src, reg);
 621                 return reg;
 622         }
 623
 624         for (i = 0; i < REGNO; i++) {
 625                 struct hardreg *reg = hardregs + i;
 626                 if (!reg->busy) {
 627                         output_comment(state, "copying %s to %s", show_pseudo(target), reg->name);
 628                         output_insn(state, "movl %s,%s", src->name, reg->name);
 629                         return reg;
 630                 }
 631         }
 632
 633         flush_reg(state, src);
 634         return src;
 635 }
 636
 637 static void put_operand(struct bb_state *state, struct operand *op)
 638 {
 639 }
 640
 641 static struct operand *alloc_op(void)
 642 {
 643         struct operand *op = malloc(sizeof(*op));
 644         memset(op, 0, sizeof(*op));
 645         return op;
 646 }
 647
 648 static struct operand *get_register_operand(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
 649 {
 650         struct operand *op = alloc_op();
 651         op->type = OP_REG;
 652         op->reg = getreg(state, pseudo, target);
 653         return op;
 654 }
 655
 656 static struct operand *get_generic_operand(struct bb_state *state, pseudo_t pseudo)
 657 {
 658         struct hardreg *reg;
 659         struct storage *src;
 660         struct storage_hash *hash;
 661         struct operand *op = malloc(sizeof(*op));
 662
 663         memset(op, 0, sizeof(*op));
 664         switch (pseudo->type) {
 665         case PSEUDO_VAL:
 666                 op->type = OP_VAL;
 667                 op->value = pseudo->value;
 668                 break;
 669
 670         case PSEUDO_SYM:
 671                 op->type = OP_ADDR;
 672                 op->sym = pseudo->sym;
 673                 break;
 674
 675         default:
 676                 reg = find_in_reg(state, pseudo);
 677                 if (reg) {
 678                         op->type = OP_REG;
 679                         op->reg = reg;
 680                         break;
 681                 }
 682                 hash = find_pseudo_storage(state, pseudo, NULL);
 683                 if (!hash)
 684                         break;
 685                 src = hash->storage;
 686                 switch (src->type) {
 687                 case REG_REG:
 688                         op->type = OP_REG;
 689                         op->reg = hardregs + src->regno;
 690                         break;
 691                 case REG_FRAME:
 692                         op->type = OP_MEM;
 693                         op->offset = src->offset;
 694                         op->base = hardregs + REG_EBP;
 695                         break;
 696                 case REG_STACK:
 697                         op->type = OP_MEM;
 698                         op->offset = src->offset;
 699                         op->base = hardregs + REG_ESP;
 700                         break;
 701                 default:
 702                         break;
 703                 }
 704         }
 705         return op;
 706 }
 707
 708 static const char *generic(struct bb_state *state, pseudo_t pseudo)
 709 {
 710         return show_op(state, get_generic_operand(state, pseudo));
 711 }
 712
 713 static const char *address(struct bb_state *state, struct instruction *memop)
 714 {
 715         struct symbol *sym;
 716         struct hardreg *base;
 717         static char buffer[100];
 718         pseudo_t addr = memop->src;
 719
 720         switch(addr->type) {
 721         case PSEUDO_SYM:
 722                 sym = addr->sym;
 723                 if (sym->ctype.modifiers & MOD_NONLOCAL) {
 724                         sprintf(buffer, "%s+%d", show_ident(sym->ident), memop->offset);
 725                         return buffer;
 726                 }
 727                 sprintf(buffer, "%d+%s(SP)", memop->offset, show_ident(sym->ident));
 728                 return buffer;
 729         default:
 730                 base = getreg(state, addr, NULL);
 731                 sprintf(buffer, "%d(%s)", memop->offset, base->name);
 732                 return buffer;
 733         }
 734 }
 735
 736 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
 737 {
 738         switch(pseudo->type) {
 739         case PSEUDO_VAL:
 740                 return show_pseudo(pseudo);
 741         default:
 742                 return getreg(state, pseudo, NULL)->name;
 743         }
 744 }
 745
 746 static void kill_dead_reg(struct hardreg *reg)
 747 {
 748         if (reg->dead) {
 749                 pseudo_t p;
 750
 751                 FOR_EACH_PTR(reg->contains, p) {
 752                         if (CURRENT_TAG(p) & TAG_DEAD) {
 753                                 DELETE_CURRENT_PTR(p);
 754                                 reg->busy--;
 755                                 reg->dead--;
 756                         }
 757                 } END_FOR_EACH_PTR(p);
 758                 PACK_PTR_LIST(&reg->contains);
 759                 assert(!reg->dead);
 760         }
 761 }
 762
 763 static struct hardreg *target_copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 764 {
 765         kill_dead_reg(src);
 766         return copy_reg(state, src, target);
 767 }
 768
 769 static void do_binop(struct bb_state *state, struct instruction *insn, pseudo_t val1, pseudo_t val2)
 770 {
 771         const char *op = opcodes[insn->opcode];
 772         struct operand *src = get_register_operand(state, val1, insn->target);
 773         struct operand *src2 = get_generic_operand(state, val2);
 774         struct hardreg *dst;
 775
 776         dst = target_copy_reg(state, src->reg, insn->target);
 777         output_insn(state, "%s.%d %s,%s", op, insn->size, show_op(state, src2), dst->name);
 778         put_operand(state, src);
 779         put_operand(state, src2);
 780         add_pseudo_reg(state, insn->target, dst);
 781 }
 782
 783 static void generate_binop(struct bb_state *state, struct instruction *insn)
 784 {
 785         flush_cc_cache(state);
 786         do_binop(state, insn, insn->src1, insn->src2);
 787 }
 788
 789 static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 790 {
 791         pseudo_t p;
 792         FOR_EACH_PTR(reg->contains, p) {
 793                 if (p == pseudo)
 794                         return CURRENT_TAG(p) & TAG_DEAD;
 795         } END_FOR_EACH_PTR(p);
 796         return 0;
 797 }
 798
 799 /*
 800  * Commutative binops are much more flexible, since we can switch the
 801  * sources around to satisfy the target register, or to avoid having
 802  * to load one of them into a register..
 803  */
 804 static void generate_commutative_binop(struct bb_state *state, struct instruction *insn)
 805 {
 806         pseudo_t src1, src2;
 807         struct hardreg *reg1, *reg2;
 808
 809         flush_cc_cache(state);
 810         src1 = insn->src1;
 811         src2 = insn->src2;
 812         reg2 = find_in_reg(state, src2);
 813         if (!reg2)
 814                 goto dont_switch;
 815         reg1 = find_in_reg(state, src1);
 816         if (!reg1)
 817                 goto do_switch;
 818         if (!is_dead_reg(state, src2, reg2))
 819                 goto dont_switch;
 820         if (!is_dead_reg(state, src1, reg1))
 821                 goto do_switch;
 822
 823         /* Both are dead. Is one preferrable? */
 824         if (reg2 != preferred_reg(state, insn->target))
 825                 goto dont_switch;
 826
 827 do_switch:
 828         src1 = src2;
 829         src2 = insn->src1;
 830 dont_switch:
 831         do_binop(state, insn, src1, src2);
 832 }
 833
 834 /*
 835  * This marks a pseudo dead. It still stays on the hardreg list (the hardreg
 836  * still has its value), but it's scheduled to be killed after the next
 837  * "sequence point" when we call "kill_read_pseudos()"
 838  */
 839 static void mark_pseudo_dead(struct bb_state *state, pseudo_t pseudo)
 840 {
 841         int i;
 842         struct storage_hash *src;
 843
 844         if (state->cc_target == pseudo)
 845                 state->cc_dead = 1;
 846         src = find_pseudo_storage(state, pseudo, NULL);
 847         if (src)
 848                 src->flags |= TAG_DEAD;
 849         for (i = 0; i < REGNO; i++)
 850                 mark_reg_dead(state, pseudo, hardregs + i);
 851 }
 852
 853 static void kill_dead_pseudos(struct bb_state *state)
 854 {
 855         int i;
 856
 857         for (i = 0; i < REGNO; i++) {
 858                 kill_dead_reg(hardregs + i);
 859         }
 860 }
 861
 862 /*
 863  * A PHI source can define a pseudo that we already
 864  * have in another register. We need to invalidate the
 865  * old register so that we don't end up with the same
 866  * pseudo in "two places".
 867  */
 868 static void remove_pseudo_reg(struct bb_state *state, pseudo_t pseudo)
 869 {
 870         int i;
 871
 872         output_comment(state, "pseudo %s died", show_pseudo(pseudo));
 873         for (i = 0; i < REGNO; i++) {
 874                 struct hardreg *reg = hardregs + i;
 875                 pseudo_t p;
 876                 FOR_EACH_PTR(reg->contains, p) {
 877                         if (p != pseudo)
 878                                 continue;
 879                         if (CURRENT_TAG(p) & TAG_DEAD)
 880                                 reg->dead--;
 881                         reg->busy--;
 882                         DELETE_CURRENT_PTR(p);
 883                         output_comment(state, "removed pseudo %s from reg %s", show_pseudo(pseudo), reg->name);
 884                 } END_FOR_EACH_PTR(p);
 885                 PACK_PTR_LIST(&reg->contains);
 886         }
 887 }
 888
 889 static void generate_store(struct instruction *insn, struct bb_state *state)
 890 {
 891         output_insn(state, "mov.%d %s,%s", insn->size, reg_or_imm(state, insn->target), address(state, insn));
 892 }
 893
 894 static void generate_load(struct instruction *insn, struct bb_state *state)
 895 {
 896         const char *input = address(state, insn);
 897         struct hardreg *dst;
 898
 899         kill_dead_pseudos(state);
 900         dst = target_reg(state, insn->target, NULL);
 901         output_insn(state, "mov.%d %s,%s", insn->size, input, dst->name);
 902 }
 903
 904 static void generate_phisource(struct instruction *insn, struct bb_state *state)
 905 {
 906         struct instruction *user;
 907         struct hardreg *reg;
 908
 909         /* Mark all the target pseudos dead first */
 910         FOR_EACH_PTR(insn->phi_users, user) {
 911                 mark_pseudo_dead(state, user->target);
 912         } END_FOR_EACH_PTR(user);
 913
 914         reg = NULL;
 915         FOR_EACH_PTR(insn->phi_users, user) {
 916                 if (!reg)
 917                         reg = getreg(state, insn->phi_src, user->target);
 918                 remove_pseudo_reg(state, user->target);
 919                 add_pseudo_reg(state, user->target, reg);
 920         } END_FOR_EACH_PTR(user);
 921 }
 922
 923 static void generate_cast(struct bb_state *state, struct instruction *insn)
 924 {
 925         struct hardreg *src = getreg(state, insn->src, insn->target);
 926         struct hardreg *dst;
 927         unsigned int old = insn->orig_type ? insn->orig_type->bit_size : 0;
 928         unsigned int new = insn->size;
 929
 930         /*
 931          * Cast to smaller type? Ignore the high bits, we
 932          * just keep both pseudos in the same register.
 933          */
 934         if (old >= new) {
 935                 add_pseudo_reg(state, insn->target, src);
 936                 return;
 937         }
 938
 939         dst = target_copy_reg(state, src, insn->target);
 940
 941         if (insn->orig_type && (insn->orig_type->ctype.modifiers & MOD_SIGNED)) {
 942                 output_insn(state, "sext.%d.%d %s", old, new, dst->name);
 943         } else {
 944                 unsigned long long mask;
 945                 mask = ~(~0ULL << old);
 946                 mask &= ~(~0ULL << new);
 947                 output_insn(state, "andl.%d $%#llx,%s", insn->size, mask, dst->name);
 948         }
 949         add_pseudo_reg(state, insn->target, dst);
 950 }
 951
 952 static void generate_output_storage(struct bb_state *state);
 953
 954 static const char *conditional[] = {
 955         [OP_SET_EQ] = "e",
 956         [OP_SET_NE] = "ne",
 957         [OP_SET_LE] = "le",
 958         [OP_SET_GE] = "ge",
 959         [OP_SET_LT] = "lt",
 960         [OP_SET_GT] = "gt",
 961         [OP_SET_B] = "b",
 962         [OP_SET_A] = "a",
 963         [OP_SET_BE] = "be",
 964         [OP_SET_AE] = "ae"
 965 };
 966
 967
 968 static void generate_branch(struct bb_state *state, struct instruction *br)
 969 {
 970         const char *cond = "XXX";
 971         struct basic_block *target;
 972
 973         if (br->cond) {
 974                 if (state->cc_target == br->cond) {
 975                         cond = conditional[state->cc_opcode];
 976                 } else {
 977                         struct hardreg *reg = getreg(state, br->cond, NULL);
 978                         output_insn(state, "testl %s,%s", reg->name, reg->name);
 979                         cond = "ne";
 980                 }
 981         }
 982         generate_output_storage(state);
 983         target = br->bb_true;
 984         if (br->cond) {
 985                 output_insn(state, "j%s .L%p", cond, target);
 986                 target = br->bb_false;
 987         }
 988         output_insn(state, "jmp .L%p", target);
 989 }
 990
 991 /* We've made sure that there is a dummy reg live for the output */
 992 static void generate_switch(struct bb_state *state, struct instruction *insn)
 993 {
 994         struct hardreg *reg = hardregs + SWITCH_REG;
 995
 996         generate_output_storage(state);
 997         output_insn(state, "switch on %s", reg->name);
 998         output_insn(state, "unimplemented: %s", show_instruction(insn));
 999 }
1000
1001 static void generate_ret(struct bb_state *state, struct instruction *ret)
1002 {
1003         if (ret->src && ret->src != VOID) {
1004                 struct hardreg *wants = hardregs+0;
1005                 struct hardreg *reg = getreg(state, ret->src, NULL);
1006                 if (reg != wants)
1007                         output_insn(state, "movl %s,%s", reg->name, wants->name);
1008         }
1009         output_insn(state, "ret");
1010 }
1011
1012 /*
1013  * Fake "call" linearization just as a taster..
1014  */
1015 static void generate_call(struct bb_state *state, struct instruction *insn)
1016 {
1017         int offset = 0;
1018         pseudo_t arg;
1019
1020         FOR_EACH_PTR(insn->arguments, arg) {
1021                 output_insn(state, "pushl %s", generic(state, arg));
1022                 offset += 4;
1023         } END_FOR_EACH_PTR(arg);
1024         flush_reg(state, hardregs+0);
1025         flush_reg(state, hardregs+1);
1026         flush_reg(state, hardregs+2);
1027         output_insn(state, "call %s", show_pseudo(insn->func));
1028         if (offset)
1029                 output_insn(state, "addl $%d,%%esp", offset);
1030         add_pseudo_reg(state, insn->target, hardregs+0);
1031 }
1032
1033 static void generate_select(struct bb_state *state, struct instruction *insn)
1034 {
1035         const char *cond;
1036         struct hardreg *src1, *src2, *dst;
1037
1038         src1 = getreg(state, insn->src2, NULL);
1039         dst = copy_reg(state, src1, insn->target);
1040         add_pseudo_reg(state, insn->target, dst);
1041         src2 = getreg(state, insn->src3, insn->target);
1042
1043         if (state->cc_target == insn->src1) {
1044                 cond = conditional[state->cc_opcode];
1045         } else {
1046                 struct hardreg *reg = getreg(state, insn->src1, NULL);
1047                 output_insn(state, "testl %s,%s", reg->name, reg->name);
1048                 cond = "ne";
1049         }
1050
1051         output_insn(state, "sel%s %s,%s", cond, src2->name, dst->name);
1052 }
1053
1054 struct asm_arg {
1055         const struct ident *name;
1056         const char *value;
1057         pseudo_t pseudo;
1058         struct hardreg *reg;
1059 };
1060
1061 static void replace_asm_arg(char **dst_p, struct asm_arg *arg)
1062 {
1063         char *dst = *dst_p;
1064         int len = strlen(arg->value);
1065
1066         memcpy(dst, arg->value, len);
1067         *dst_p = dst + len;
1068 }
1069
1070 static void replace_asm_percent(const char **src_p, char **dst_p, struct asm_arg *args, int nr)
1071 {
1072         const char *src = *src_p;
1073         char c;
1074         int index;
1075
1076         c = *src++;
1077         switch (c) {
1078         case '0' ... '9':
1079                 index = c - '0';
1080                 if (index < nr)
1081                         replace_asm_arg(dst_p, args+index);
1082                 break;
1083         }
1084         *src_p = src;
1085         return;
1086 }
1087
1088 static void replace_asm_named(const char **src_p, char **dst_p, struct asm_arg *args, int nr)
1089 {
1090         const char *src = *src_p;
1091         const char *end = src;
1092
1093         for(;;) {
1094                 char c = *end++;
1095                 if (!c)
1096                         return;
1097                 if (c == ']') {
1098                         int i;
1099
1100                         *src_p = end;
1101                         for (i = 0; i < nr; i++) {
1102                                 const struct ident *ident = args[i].name;
1103                                 int len;
1104                                 if (!ident)
1105                                         continue;
1106                                 len = ident->len;
1107                                 if (memcmp(src, ident->name, len))
1108                                         continue;
1109                                 replace_asm_arg(dst_p, args+i);
1110                                 return;
1111                         }
1112                 }
1113         }
1114 }
1115
1116 static const char *replace_asm_args(const char *str, struct asm_arg *args, int nr)
1117 {
1118         static char buffer[1000];
1119         char *p = buffer;
1120
1121         for (;;) {
1122                 char c = *str;
1123                 *p = c;
1124                 if (!c)
1125                         return buffer;
1126                 str++;
1127                 switch (c) {
1128                 case '%':
1129                         if (*str == '%') {
1130                                 str++;
1131                                 p++;
1132                                 continue;
1133                         }
1134                         replace_asm_percent(&str, &p, args, nr);
1135                         continue;
1136                 case '[':
1137                         replace_asm_named(&str, &p, args, nr);
1138                         continue;
1139                 default:
1140                         break;
1141                 }
1142                 p++;
1143         }
1144 }
1145
1146 #define MAX_ASM_ARG (50)
1147 static struct asm_arg asm_arguments[MAX_ASM_ARG];
1148
1149 static struct asm_arg *generate_asm_inputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg)
1150 {
1151         struct asm_constraint *entry;
1152
1153         FOR_EACH_PTR(list, entry) {
1154                 const char *constraint = entry->constraint;
1155                 pseudo_t pseudo = entry->pseudo;
1156                 struct hardreg *reg, *orig;
1157                 const char *string;
1158                 int index;
1159
1160                 string = "undef";
1161                 switch (*constraint) {
1162                 case 'r':
1163                         string = getreg(state, pseudo, NULL)->name;
1164                         break;
1165                 case '0' ... '9':
1166                         index = *constraint - '0';
1167                         reg = asm_arguments[index].reg;
1168                         orig = find_in_reg(state, pseudo);
1169                         if (orig)
1170                                 move_reg(state, orig, reg);
1171                         else
1172                                 fill_reg(state, reg, pseudo);
1173                         string = reg->name;
1174                         break;
1175                 default:
1176                         string = generic(state, pseudo);
1177                         break;
1178                 }
1179
1180                 output_insn(state, "# asm input \"%s\": %s : %s", constraint, show_pseudo(pseudo), string);
1181
1182                 arg->name = entry->ident;
1183                 arg->value = string;
1184                 arg->pseudo = NULL;
1185                 arg->reg = NULL;
1186                 arg++;
1187         } END_FOR_EACH_PTR(entry);
1188         return arg;
1189 }
1190
1191 static struct asm_arg *generate_asm_outputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg)
1192 {
1193         struct asm_constraint *entry;
1194
1195         FOR_EACH_PTR(list, entry) {
1196                 const char *constraint = entry->constraint;
1197                 pseudo_t pseudo = entry->pseudo;
1198                 struct hardreg *reg;
1199                 const char *string;
1200
1201                 while (*constraint == '=' || *constraint == '+')
1202                         constraint++;
1203
1204                 string = "undef";
1205                 switch (*constraint) {
1206                 case 'r':
1207                 default:
1208                         reg = target_reg(state, pseudo, NULL);
1209                         arg->pseudo = pseudo;
1210                         arg->reg = reg;
1211                         string = reg->name;
1212                         break;
1213                 }
1214
1215                 output_insn(state, "# asm output \"%s\": %s : %s", constraint, show_pseudo(pseudo), string);
1216
1217                 arg->name = entry->ident;
1218                 arg->value = string;
1219                 arg++;
1220         } END_FOR_EACH_PTR(entry);
1221         return arg;
1222 }
1223
1224 static void generate_asm(struct bb_state *state, struct instruction *insn)
1225 {
1226         const char *str = insn->string;
1227
1228         if (insn->asm_rules->outputs || insn->asm_rules->inputs) {
1229                 struct asm_arg *arg;
1230
1231                 arg = generate_asm_outputs(state, insn->asm_rules->outputs, asm_arguments);
1232                 arg = generate_asm_inputs(state, insn->asm_rules->inputs, arg);
1233                 str = replace_asm_args(str, asm_arguments, arg - asm_arguments);
1234         }
1235         output_insn(state, "%s", str);
1236 }
1237
1238 static void generate_compare(struct bb_state *state, struct instruction *insn)
1239 {
1240         struct hardreg *src;
1241         const char *src2;
1242         int opcode;
1243
1244         flush_cc_cache(state);
1245         opcode = insn->opcode;
1246
1247         /*
1248          * We should try to switch these around if necessary,
1249          * and update the opcode to match..
1250          */
1251         src = getreg(state, insn->src1, insn->target);
1252         src2 = generic(state, insn->src2);
1253
1254         output_insn(state, "cmp.%d %s,%s", insn->size, src2, src->name);
1255
1256         add_cc_cache(state, opcode, insn->target);
1257 }
1258
1259 static void generate_one_insn(struct instruction *insn, struct bb_state *state)
1260 {
1261         if (verbose)
1262                 output_comment(state, "%s", show_instruction(insn));
1263
1264         switch (insn->opcode) {
1265         case OP_ENTRY: {
1266                 struct symbol *sym = insn->bb->ep->name;
1267                 const char *name = show_ident(sym->ident);
1268                 if (sym->ctype.modifiers & MOD_STATIC)
1269                         printf("\n\n%s:\n", name);
1270                 else
1271                         printf("\n\n.globl %s\n%s:\n", name, name);
1272                 break;
1273         }
1274
1275         /*
1276          * OP_PHI doesn't actually generate any code. It has been
1277          * done by the storage allocator and the OP_PHISOURCE.
1278          */
1279         case OP_PHI:
1280                 break;
1281
1282         case OP_PHISOURCE:
1283                 generate_phisource(insn, state);
1284                 break;
1285
1286         /*
1287          * OP_SETVAL likewise doesn't actually generate any
1288          * code. On use, the "def" of the pseudo will be
1289          * looked up.
1290          */
1291         case OP_SETVAL:
1292                 break;
1293
1294         case OP_STORE:
1295                 generate_store(insn, state);
1296                 break;
1297
1298         case OP_LOAD:
1299                 generate_load(insn, state);
1300                 break;
1301
1302         case OP_DEATHNOTE:
1303                 mark_pseudo_dead(state, insn->target);
1304                 return;
1305
1306         case OP_ADD: case OP_MUL:
1307         case OP_AND: case OP_OR: case OP_XOR:
1308         case OP_AND_BOOL: case OP_OR_BOOL:
1309                 generate_commutative_binop(state, insn);
1310                 break;
1311
1312         case OP_SUB: case OP_DIV: case OP_MOD:
1313         case OP_SHL: case OP_SHR:
1314                 generate_binop(state, insn);
1315                 break;
1316
1317         case OP_BINCMP ... OP_BINCMP_END:
1318                 generate_compare(state, insn);
1319                 break;
1320
1321         case OP_CAST: case OP_PTRCAST:
1322                 generate_cast(state, insn);
1323                 break;
1324
1325         case OP_SEL:
1326                 generate_select(state, insn);
1327                 break;
1328
1329         case OP_BR:
1330                 generate_branch(state, insn);
1331                 break;
1332
1333         case OP_SWITCH:
1334                 generate_switch(state, insn);
1335                 break;
1336
1337         case OP_CALL:
1338                 generate_call(state, insn);
1339                 break;
1340
1341         case OP_RET:
1342                 generate_ret(state, insn);
1343                 break;
1344
1345         case OP_ASM:
1346                 generate_asm(state, insn);
1347                 break;
1348
1349         default:
1350                 output_insn(state, "unimplemented: %s", show_instruction(insn));
1351                 break;
1352         }
1353         kill_dead_pseudos(state);
1354 }
1355
1356 #define VERY_BUSY 1000
1357 #define REG_FIXED 2000
1358
1359 static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, pseudo_t pseudo, struct storage *storage)
1360 {
1361         int i;
1362         struct hardreg *out;
1363
1364         switch (storage->type) {
1365         case REG_REG:
1366                 out = hardregs + storage->regno;
1367                 if (reg == out)
1368                         return;
1369                 output_insn(state, "movl %s,%s", reg->name, out->name);
1370                 return;
1371         case REG_UDEF:
1372                 if (reg->busy < VERY_BUSY) {
1373                         storage->type = REG_REG;
1374                         storage->regno = reg - hardregs;
1375                         reg->busy = REG_FIXED;
1376                         return;
1377                 }
1378
1379                 /* Try to find a non-busy register.. */
1380                 for (i = 0; i < REGNO; i++) {
1381                         out = hardregs + i;
1382                         if (out->busy)
1383                                 continue;
1384                         output_insn(state, "movl %s,%s", reg->name, out->name);
1385                         storage->type = REG_REG;
1386                         storage->regno = i;
1387                         out->busy = REG_FIXED;
1388                         return;
1389                 }
1390
1391                 /* Fall back on stack allocation ... */
1392                 alloc_stack(state, storage);
1393                 /* Fallthroigh */
1394         default:
1395                 output_insn(state, "movl %s,%s", reg->name, show_memop(storage));
1396                 return;
1397         }
1398 }
1399
1400 static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage)
1401 {
1402         struct hardreg *out;
1403
1404         switch (storage->type) {
1405         case REG_UDEF:
1406                 alloc_stack(state, storage);
1407         default:
1408                 output_insn(state, "movl %s,%s", show_pseudo(src), show_memop(storage));
1409                 break;
1410         case REG_REG:
1411                 out = hardregs + storage->regno;
1412                 output_insn(state, "movl %s,%s", show_pseudo(src), out->name);
1413         }
1414 }
1415
1416 static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out)
1417 {
1418         int i;
1419         struct storage_hash *in;
1420         struct instruction *def;
1421
1422         /* Is that pseudo a constant value? */
1423         switch (pseudo->type) {
1424         case PSEUDO_VAL:
1425                 write_val_to_storage(state, pseudo, out);
1426                 return;
1427         case PSEUDO_REG:
1428                 def = pseudo->def;
1429                 if (def->opcode == OP_SETVAL) {
1430                         write_val_to_storage(state, pseudo, out);
1431                         return;
1432                 }
1433         default:
1434                 break;
1435         }
1436
1437         /* See if we have that pseudo in a register.. */
1438         for (i = 0; i < REGNO; i++) {
1439                 struct hardreg *reg = hardregs + i;
1440                 pseudo_t p;
1441
1442                 FOR_EACH_PTR(reg->contains, p) {
1443                         if (p == pseudo) {
1444                                 write_reg_to_storage(state, reg, pseudo, out);
1445                                 return;
1446                         }
1447                 } END_FOR_EACH_PTR(p);
1448         }
1449
1450         /* Do we have it in another storage? */
1451         in = find_storage_hash(pseudo, state->internal);
1452         if (!in) {
1453                 in = find_storage_hash(pseudo, state->inputs);
1454                 /* Undefined? */
1455                 if (!in)
1456                         return;
1457         }
1458         switch (out->type) {
1459         case REG_UDEF:
1460                 *out = *in->storage;
1461                 break;
1462         case REG_REG:
1463                 output_insn(state, "movl %s,%s", show_memop(in->storage), hardregs[out->regno].name);
1464                 break;
1465         default:
1466                 if (out == in->storage)
1467                         break;
1468                 if (out->type == in->storage->type == out->regno == in->storage->regno)
1469                         break;
1470                 output_insn(state, "movl %s,%s", show_memop(in->storage), show_memop(out));
1471                 break;
1472         }
1473         return;
1474 }
1475
1476 static int final_pseudo_flush(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
1477 {
1478         struct storage_hash *hash;
1479         struct storage *out;
1480         struct hardreg *dst;
1481
1482         /*
1483          * Since this pseudo is live at exit, we'd better have output
1484          * storage for it..
1485          */
1486         hash = find_storage_hash(pseudo, state->outputs);
1487         if (!hash)
1488                 return 1;
1489         out = hash->storage;
1490
1491         /* If the output is in a register, try to get it there.. */
1492         if (out->type == REG_REG) {
1493                 dst = hardregs + out->regno;
1494                 /*
1495                  * Two good cases: nobody is using the right register,
1496                  * or we've already set it aside for output..
1497                  */
1498                 if (!dst->busy || dst->busy > VERY_BUSY)
1499                         goto copy_to_dst;
1500
1501                 /* Aiee. Try to keep it in a register.. */
1502                 dst = empty_reg(state);
1503                 if (dst)
1504                         goto copy_to_dst;
1505
1506                 return 0;
1507         }
1508
1509         /* If the output is undefined, let's see if we can put it in a register.. */
1510         if (out->type == REG_UDEF) {
1511                 dst = empty_reg(state);
1512                 if (dst) {
1513                         out->type = REG_REG;
1514                         out->regno = dst - hardregs;
1515                         goto copy_to_dst;
1516                 }
1517                 /* Uhhuh. Not so good. No empty registers right now */
1518                 return 0;
1519         }
1520
1521         /* If we know we need to flush it, just do so already .. */
1522         output_insn(state, "movl %s,%s", reg->name, show_memop(out));
1523         return 1;
1524
1525 copy_to_dst:
1526         if (reg == dst)
1527                 return 1;
1528         output_insn(state, "movl %s,%s", reg->name, dst->name);
1529         add_pseudo_reg(state, pseudo, dst);
1530         return 1;
1531 }
1532
1533 /*
1534  * This tries to make sure that we put all the pseudos that are
1535  * live on exit into the proper storage
1536  */
1537 static void generate_output_storage(struct bb_state *state)
1538 {
1539         struct storage_hash *entry;
1540
1541         /* Go through the fixed outputs, making sure we have those regs free */
1542         FOR_EACH_PTR(state->outputs, entry) {
1543                 struct storage *out = entry->storage;
1544                 if (out->type == REG_REG) {
1545                         struct hardreg *reg = hardregs + out->regno;
1546                         pseudo_t p;
1547                         int flushme = 0;
1548
1549                         reg->busy = REG_FIXED;
1550                         FOR_EACH_PTR(reg->contains, p) {
1551                                 if (p == entry->pseudo) {
1552                                         flushme = -100;
1553                                         continue;
1554                                 }
1555                                 if (CURRENT_TAG(p) & TAG_DEAD)
1556                                         continue;
1557
1558                                 /* Try to write back the pseudo to where it should go ... */
1559                                 if (final_pseudo_flush(state, p, reg)) {
1560                                         DELETE_CURRENT_PTR(p);
1561                                         reg->busy--;
1562                                         continue;
1563                                 }
1564                                 flushme++;
1565                         } END_FOR_EACH_PTR(p);
1566                         PACK_PTR_LIST(&reg->contains);
1567                         if (flushme > 0)
1568                                 flush_reg(state, reg);
1569                 }
1570         } END_FOR_EACH_PTR(entry);
1571
1572         FOR_EACH_PTR(state->outputs, entry) {
1573                 fill_output(state, entry->pseudo, entry->storage);
1574         } END_FOR_EACH_PTR(entry);
1575 }
1576
1577 static void generate(struct basic_block *bb, struct bb_state *state)
1578 {
1579         int i;
1580         struct storage_hash *entry;
1581         struct instruction *insn;
1582
1583         for (i = 0; i < REGNO; i++) {
1584                 free_ptr_list(&hardregs[i].contains);
1585                 hardregs[i].busy = 0;
1586                 hardregs[i].dead = 0;
1587                 hardregs[i].used = 0;
1588         }
1589
1590         FOR_EACH_PTR(state->inputs, entry) {
1591                 struct storage *storage = entry->storage;
1592                 const char *name = show_storage(storage);
1593                 output_comment(state, "incoming %s in %s", show_pseudo(entry->pseudo), name);
1594                 if (storage->type == REG_REG) {
1595                         int regno = storage->regno;
1596                         add_pseudo_reg(state, entry->pseudo, hardregs + regno);
1597                         name = hardregs[regno].name;
1598                 }
1599         } END_FOR_EACH_PTR(entry);
1600
1601         output_label(state, ".L%p", bb);
1602         FOR_EACH_PTR(bb->insns, insn) {
1603                 if (!insn->bb)
1604                         continue;
1605                 generate_one_insn(insn, state);
1606         } END_FOR_EACH_PTR(insn);
1607
1608         if (verbose) {
1609                 output_comment(state, "--- in ---");
1610                 FOR_EACH_PTR(state->inputs, entry) {
1611                         output_comment(state, "%s <- %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1612                 } END_FOR_EACH_PTR(entry);
1613                 output_comment(state, "--- spill ---");
1614                 FOR_EACH_PTR(state->internal, entry) {
1615                         output_comment(state, "%s <-> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1616                 } END_FOR_EACH_PTR(entry);
1617                 output_comment(state, "--- out ---");
1618                 FOR_EACH_PTR(state->outputs, entry) {
1619                         output_comment(state, "%s -> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1620                 } END_FOR_EACH_PTR(entry);
1621         }
1622         printf("\n");
1623 }
1624
1625 static void generate_list(struct basic_block_list *list, unsigned long generation)
1626 {
1627         struct basic_block *bb;
1628         FOR_EACH_PTR(list, bb) {
1629                 if (bb->generation == generation)
1630                         continue;
1631                 output_bb(bb, generation);
1632         } END_FOR_EACH_PTR(bb);
1633 }
1634
1635 /*
1636  * Mark all the output registers of all the parents
1637  * as being "used" - this does not mean that we cannot
1638  * re-use them, but it means that we cannot ask the
1639  * parents to pass in another pseudo in one of those
1640  * registers that it already uses for another child.
1641  */
1642 static void mark_used_registers(struct basic_block *bb, struct bb_state *state)
1643 {
1644         struct basic_block *parent;
1645
1646         FOR_EACH_PTR(bb->parents, parent) {
1647                 struct storage_hash_list *outputs = gather_storage(parent, STOR_OUT);
1648                 struct storage_hash *entry;
1649
1650                 FOR_EACH_PTR(outputs, entry) {
1651                         struct storage *s = entry->storage;
1652                         if (s->type == REG_REG) {
1653                                 struct hardreg *reg = hardregs + s->regno;
1654                                 reg->used = 1;
1655                         }
1656                 } END_FOR_EACH_PTR(entry);
1657         } END_FOR_EACH_PTR(parent);
1658 }
1659
1660 static void output_bb(struct basic_block *bb, unsigned long generation)
1661 {
1662         struct bb_state state;
1663
1664         bb->generation = generation;
1665
1666         /* Make sure all parents have been generated first */
1667         generate_list(bb->parents, generation);
1668
1669         state.pos = bb->pos;
1670         state.inputs = gather_storage(bb, STOR_IN);
1671         state.outputs = gather_storage(bb, STOR_OUT);
1672         state.internal = NULL;
1673         state.cc_opcode = 0;
1674         state.cc_target = NULL;
1675
1676         /* Mark incoming registers used */
1677         mark_used_registers(bb, &state);
1678
1679         generate(bb, &state);
1680
1681         free_ptr_list(&state.inputs);
1682         free_ptr_list(&state.outputs);
1683
1684         /* Generate all children... */
1685         generate_list(bb->children, generation);
1686 }
1687
1688 static void set_up_arch_entry(struct entrypoint *ep, struct instruction *entry)
1689 {
1690         int i;
1691         pseudo_t arg;
1692
1693         /*
1694          * We should set up argument sources here..
1695          *
1696          * Things like "first three arguments in registers" etc
1697          * are all for this place.
1698          */
1699         i = 0;
1700         FOR_EACH_PTR(entry->arg_list, arg) {
1701                 struct storage *in = lookup_storage(entry->bb, arg, STOR_IN);
1702                 if (!in) {
1703                         in = alloc_storage();
1704                         add_storage(in, entry->bb, arg, STOR_IN);
1705                 }
1706                 if (i < 3) {
1707                         in->type = REG_REG;
1708                         in->regno = i;
1709                 } else {
1710                         in->type = REG_FRAME;
1711                         in->offset = (i-3)*4;
1712                 }
1713                 i++;
1714         } END_FOR_EACH_PTR(arg);
1715 }
1716
1717 /*
1718  * Set up storage information for "return"
1719  *
1720  * Not strictly necessary, since the code generator will
1721  * certainly move the return value to the right register,
1722  * but it can help register allocation if the allocator
1723  * sees that the target register is going to return in %eax.
1724  */
1725 static void set_up_arch_exit(struct basic_block *bb, struct instruction *ret)
1726 {
1727         pseudo_t pseudo = ret->src;
1728
1729         if (pseudo && pseudo != VOID) {
1730                 struct storage *out = lookup_storage(bb, pseudo, STOR_OUT);
1731                 if (!out) {
1732                         out = alloc_storage();
1733                         add_storage(out, bb, pseudo, STOR_OUT);
1734                 }
1735                 out->type = REG_REG;
1736                 out->regno = 0;
1737         }
1738 }
1739
1740 /*
1741  * Set up dummy/silly output storage information for a switch
1742  * instruction. We need to make sure that a register is available
1743  * when we generate code for switch, so force that by creating
1744  * a dummy output rule.
1745  */
1746 static void set_up_arch_switch(struct basic_block *bb, struct instruction *insn)
1747 {
1748         pseudo_t pseudo = insn->cond;
1749         struct storage *out = lookup_storage(bb, pseudo, STOR_OUT);
1750         if (!out) {
1751                 out = alloc_storage();
1752                 add_storage(out, bb, pseudo, STOR_OUT);
1753         }
1754         out->type = REG_REG;
1755         out->regno = SWITCH_REG;
1756 }
1757
1758 static void arch_set_up_storage(struct entrypoint *ep)
1759 {
1760         struct basic_block *bb;
1761
1762         /* Argument storage etc.. */
1763         set_up_arch_entry(ep, ep->entry);
1764
1765         FOR_EACH_PTR(ep->bbs, bb) {
1766                 struct instruction *insn = last_instruction(bb->insns);
1767                 if (!insn)
1768                         continue;
1769                 switch (insn->opcode) {
1770                 case OP_RET:
1771                         set_up_arch_exit(bb, insn);
1772                         break;
1773                 case OP_SWITCH:
1774                         set_up_arch_switch(bb, insn);
1775                         break;
1776                 default:
1777                         /* nothing */;
1778                 }
1779         } END_FOR_EACH_PTR(bb);
1780 }
1781
1782 static void output(struct entrypoint *ep)
1783 {
1784         unsigned long generation = ++bb_generation;
1785
1786         last_reg = -1;
1787         stack_offset = 0;
1788
1789         /* Set up initial inter-bb storage links */
1790         set_up_storage(ep);
1791
1792         /* Architecture-specific storage rules.. */
1793         arch_set_up_storage(ep);
1794
1795         /* Show the results ... */
1796         output_bb(ep->entry->bb, generation);
1797
1798         /* Clear the storage hashes for the next function.. */
1799         free_storage();
1800 }
1801
1802 static int compile(struct symbol_list *list)
1803 {
1804         struct symbol *sym;
1805         FOR_EACH_PTR(list, sym) {
1806                 struct entrypoint *ep;
1807                 expand_symbol(sym);
1808                 ep = linearize_symbol(sym);
1809                 if (ep)
1810                         output(ep);
1811         } END_FOR_EACH_PTR(sym);
1812
1813         return 0;
1814 }
1815
1816 int main(int argc, char **argv)
1817 {
1818         return compile(sparse(argc, argv));
1819 }
1820