Print this page
new smatch


   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 #include "target.h"
  16 
  17 static const char *opcodes[] = {
  18         [OP_BADOP] = "bad_op",
  19 
  20         /* Fn entrypoint */
  21         [OP_ENTRY] = "<entry-point>",
  22 
  23         /* Terminator */
  24         [OP_RET] = "ret",
  25         [OP_BR] = "br",
  26         [OP_CBR] = "cbr",
  27         [OP_SWITCH] = "switch",
  28         [OP_INVOKE] = "invoke",
  29         [OP_COMPUTEDGOTO] = "jmp *",
  30         [OP_UNWIND] = "unwind",
  31         
  32         /* Binary */
  33         [OP_ADD] = "add",
  34         [OP_SUB] = "sub",
  35         [OP_MULU] = "mulu",
  36         [OP_MULS] = "muls",
  37         [OP_DIVU] = "divu",
  38         [OP_DIVS] = "divs",
  39         [OP_MODU] = "modu",
  40         [OP_MODS] = "mods",
  41         [OP_SHL] = "shl",
  42         [OP_LSR] = "lsr",
  43         [OP_ASR] = "asr",
  44         
  45         /* Logical */
  46         [OP_AND] = "and",
  47         [OP_OR] = "or",
  48         [OP_XOR] = "xor",
  49         [OP_AND_BOOL] = "and-bool",
  50         [OP_OR_BOOL] = "or-bool",
  51 
  52         /* Binary comparison */
  53         [OP_SET_EQ] = "seteq",
  54         [OP_SET_NE] = "setne",
  55         [OP_SET_LE] = "setle",
  56         [OP_SET_GE] = "setge",
  57         [OP_SET_LT] = "setlt",
  58         [OP_SET_GT] = "setgt",
  59         [OP_SET_B] = "setb",
  60         [OP_SET_A] = "seta",
  61         [OP_SET_BE] = "setbe",
  62         [OP_SET_AE] = "setae",
  63 
  64         /* Uni */
  65         [OP_NOT] = "not",
  66         [OP_NEG] = "neg",
  67 
  68         /* Special three-input */
  69         [OP_SEL] = "select",
  70         
  71         /* Memory */
  72         [OP_MALLOC] = "malloc",
  73         [OP_FREE] = "free",
  74         [OP_ALLOCA] = "alloca",
  75         [OP_LOAD] = "load",
  76         [OP_STORE] = "store",
  77         [OP_SETVAL] = "set",
  78         [OP_GET_ELEMENT_PTR] = "getelem",
  79 
  80         /* Other */
  81         [OP_PHI] = "phi",
  82         [OP_PHISOURCE] = "phisrc",
  83         [OP_COPY] = "copy",
  84         [OP_CAST] = "cast",
  85         [OP_SCAST] = "scast",
  86         [OP_FPCAST] = "fpcast",







  87         [OP_PTRCAST] = "ptrcast",
  88         [OP_CALL] = "call",
  89         [OP_VANEXT] = "va_next",
  90         [OP_VAARG] = "va_arg",
  91         [OP_SLICE] = "slice",
  92         [OP_SNOP] = "snop",
  93         [OP_LNOP] = "lnop",
  94         [OP_NOP] = "nop",
  95         [OP_DEATHNOTE] = "dead",
  96         [OP_ASM] = "asm",
  97 
  98         /* Sparse tagging (line numbers, context, whatever) */
  99         [OP_CONTEXT] = "context",
 100 };
 101 
 102 static int last_reg, stack_offset;
 103 
 104 struct hardreg {
 105         const char *name;
 106         struct pseudo_list *contains;
 107         unsigned busy:16,
 108                  dead:8,
 109                  used:1;
 110 };
 111 
 112 #define TAG_DEAD 1
 113 #define TAG_DIRTY 2


 377         case REG_UDEF:
 378                 alloc_stack(state, storage);
 379                 /* Fall through */
 380         case REG_STACK:
 381                 output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage));
 382                 break;
 383         }
 384 }
 385 
 386 /* Flush a hardreg out to the storage it has.. */
 387 static void flush_reg(struct bb_state *state, struct hardreg *reg)
 388 {
 389         pseudo_t pseudo;
 390 
 391         if (reg->busy)
 392                 output_comment(state, "reg %s flushed while busy is %d!", reg->name, reg->busy);
 393         if (!reg->contains)
 394                 return;
 395         reg->dead = 0;
 396         reg->used = 1;
 397         FOR_EACH_PTR(reg->contains, pseudo) {
 398                 if (CURRENT_TAG(pseudo) & TAG_DEAD)
 399                         continue;
 400                 if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
 401                         continue;
 402                 flush_one_pseudo(state, reg, pseudo);
 403         } END_FOR_EACH_PTR(pseudo);
 404         free_ptr_list(&reg->contains);
 405 }
 406 
 407 static struct storage_hash *find_pseudo_storage(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 408 {
 409         struct storage_hash *src;
 410 
 411         src = find_storage_hash(pseudo, state->internal);
 412         if (!src) {
 413                 src = find_storage_hash(pseudo, state->inputs);
 414                 if (!src) {
 415                         src = find_storage_hash(pseudo, state->outputs);
 416                         /* Undefined? Screw it! */
 417                         if (!src)


 430          * Incoming pseudo with out any pre-set storage allocation?
 431          * We can make up our own, and obviously prefer to get it
 432          * in the register we already selected (if it hasn't been
 433          * used yet).
 434          */
 435         if (src->storage->type == REG_UDEF) {
 436                 if (reg && !reg->used) {
 437                         src->storage->type = REG_REG;
 438                         src->storage->regno = reg - hardregs;
 439                         return NULL;
 440                 }
 441                 alloc_stack(state, src->storage);
 442         }
 443         return src;
 444 }
 445 
 446 static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 447 {
 448         pseudo_t p;
 449 
 450         FOR_EACH_PTR(reg->contains, p) {
 451                 if (p != pseudo)
 452                         continue;
 453                 if (CURRENT_TAG(p) & TAG_DEAD)
 454                         continue;
 455                 output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
 456                 TAG_CURRENT(p, TAG_DEAD);
 457                 reg->dead++;
 458         } END_FOR_EACH_PTR(p);
 459 }
 460 
 461 static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 462 {
 463         output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name);
 464         add_ptr_list_tag(&reg->contains, pseudo, TAG_DIRTY);
 465 }
 466 
 467 static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target)
 468 {
 469         struct storage_hash *dst;
 470 


 515                         last_reg = i;
 516                         goto found;
 517                 }
 518         } while (i != last_reg);
 519         assert(unable_to_find_reg);
 520 
 521 found:
 522         add_pseudo_reg(state, pseudo, reg);
 523         return reg;
 524 }
 525 
 526 static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo)
 527 {
 528         int i;
 529         struct hardreg *reg;
 530 
 531         for (i = 0; i < REGNO; i++) {
 532                 pseudo_t p;
 533 
 534                 reg = hardregs + i;
 535                 FOR_EACH_PTR(reg->contains, p) {
 536                         if (p == pseudo) {
 537                                 last_reg = i;
 538                                 output_comment(state, "found pseudo %s in reg %s (busy=%d)", show_pseudo(pseudo), reg->name, reg->busy);
 539                                 return reg;
 540                         }
 541                 } END_FOR_EACH_PTR(p);
 542         }
 543         return NULL;
 544 }
 545 
 546 static void flush_pseudo(struct bb_state *state, pseudo_t pseudo, struct storage *storage)
 547 {
 548         struct hardreg *reg = find_in_reg(state, pseudo);
 549 
 550         if (reg)
 551                 flush_reg(state, reg);
 552 }
 553 
 554 static void flush_cc_cache_to_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 555 {


 855         const char *str = show_op(state, op);
 856         put_operand(state, op);
 857         return str;
 858 }
 859 
 860 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
 861 {
 862         switch(pseudo->type) {
 863         case PSEUDO_VAL:
 864                 return show_pseudo(pseudo);
 865         default:
 866                 return getreg(state, pseudo, NULL)->name;
 867         }
 868 }
 869 
 870 static void kill_dead_reg(struct hardreg *reg)
 871 {
 872         if (reg->dead) {
 873                 pseudo_t p;
 874                 
 875                 FOR_EACH_PTR(reg->contains, p) {
 876                         if (CURRENT_TAG(p) & TAG_DEAD) {
 877                                 DELETE_CURRENT_PTR(p);
 878                                 reg->dead--;
 879                         }
 880                 } END_FOR_EACH_PTR(p);
 881                 PACK_PTR_LIST(&reg->contains);
 882                 assert(!reg->dead);
 883         }
 884 }
 885 
 886 static struct hardreg *target_copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 887 {
 888         kill_dead_reg(src);
 889         return copy_reg(state, src, target);
 890 }
 891 
 892 static void do_binop(struct bb_state *state, struct instruction *insn, pseudo_t val1, pseudo_t val2)
 893 {
 894         const char *op = opcodes[insn->opcode];
 895         struct operand *src = get_register_operand(state, val1, insn->target);
 896         struct operand *src2 = get_generic_operand(state, val2);
 897         struct hardreg *dst;
 898 
 899         dst = target_copy_reg(state, src->reg, insn->target);
 900         output_insn(state, "%s.%d %s,%s", op, insn->size, show_op(state, src2), dst->name);
 901         put_operand(state, src);
 902         put_operand(state, src2);
 903         add_pseudo_reg(state, insn->target, dst);
 904 }
 905 
 906 static void generate_binop(struct bb_state *state, struct instruction *insn)
 907 {
 908         flush_cc_cache(state);
 909         do_binop(state, insn, insn->src1, insn->src2);
 910 }
 911 
 912 static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 913 {
 914         pseudo_t p;
 915         FOR_EACH_PTR(reg->contains, p) {
 916                 if (p == pseudo)
 917                         return CURRENT_TAG(p) & TAG_DEAD;
 918         } END_FOR_EACH_PTR(p);
 919         return 0;
 920 }
 921 
 922 /*
 923  * Commutative binops are much more flexible, since we can switch the
 924  * sources around to satisfy the target register, or to avoid having
 925  * to load one of them into a register..
 926  */
 927 static void generate_commutative_binop(struct bb_state *state, struct instruction *insn)
 928 {
 929         pseudo_t src1, src2;
 930         struct hardreg *reg1, *reg2;
 931 
 932         flush_cc_cache(state);
 933         src1 = insn->src1;
 934         src2 = insn->src2;
 935         reg2 = find_in_reg(state, src2);


 990 static void generate_load(struct instruction *insn, struct bb_state *state)
 991 {
 992         const char *input = address(state, insn);
 993         struct hardreg *dst;
 994 
 995         kill_dead_pseudos(state);
 996         dst = target_reg(state, insn->target, NULL);
 997         output_insn(state, "mov.%d %s,%s", insn->size, input, dst->name);
 998 }
 999 
1000 static void kill_pseudo(struct bb_state *state, pseudo_t pseudo)
1001 {
1002         int i;
1003         struct hardreg *reg;
1004 
1005         output_comment(state, "killing pseudo %s", show_pseudo(pseudo));
1006         for (i = 0; i < REGNO; i++) {
1007                 pseudo_t p;
1008 
1009                 reg = hardregs + i;
1010                 FOR_EACH_PTR(reg->contains, p) {
1011                         if (p != pseudo)
1012                                 continue;
1013                         if (CURRENT_TAG(p) & TAG_DEAD)
1014                                 reg->dead--;
1015                         output_comment(state, "removing pseudo %s from reg %s", 
1016                                 show_pseudo(pseudo), reg->name);
1017                         DELETE_CURRENT_PTR(p);
1018                 } END_FOR_EACH_PTR(p);
1019                 PACK_PTR_LIST(&reg->contains);
1020         }
1021 }
1022 
1023 static void generate_copy(struct bb_state *state, struct instruction *insn)
1024 {
1025         struct hardreg *src = getreg(state, insn->src, insn->target);
1026         kill_pseudo(state, insn->target);
1027         add_pseudo_reg(state, insn->target, src);
1028 }
1029 
1030 static void generate_cast(struct bb_state *state, struct instruction *insn)


1387          */
1388         case OP_SETVAL:
1389                 break;
1390 
1391         case OP_STORE:
1392                 generate_store(insn, state);
1393                 break;
1394 
1395         case OP_LOAD:
1396                 generate_load(insn, state);
1397                 break;
1398 
1399         case OP_DEATHNOTE:
1400                 mark_pseudo_dead(state, insn->target);
1401                 return;
1402 
1403         case OP_COPY:
1404                 generate_copy(state, insn);
1405                 break;
1406 
1407         case OP_ADD: case OP_MULU: case OP_MULS:
1408         case OP_AND: case OP_OR: case OP_XOR:
1409         case OP_AND_BOOL: case OP_OR_BOOL:
1410                 generate_commutative_binop(state, insn);
1411                 break;
1412 
1413         case OP_SUB: case OP_DIVU: case OP_DIVS:
1414         case OP_MODU: case OP_MODS:
1415         case OP_SHL: case OP_LSR: case OP_ASR:
1416                 generate_binop(state, insn);
1417                 break;
1418 
1419         case OP_BINCMP ... OP_BINCMP_END:
1420                 generate_compare(state, insn);
1421                 break;
1422 
1423         case OP_CAST: case OP_SCAST: case OP_FPCAST: case OP_PTRCAST:







1424                 generate_cast(state, insn);
1425                 break;
1426 
1427         case OP_SEL:
1428                 generate_select(state, insn);
1429                 break;
1430 
1431         case OP_BR:
1432         case OP_CBR:
1433                 generate_branch(state, insn);
1434                 break;
1435 
1436         case OP_SWITCH:
1437                 generate_switch(state, insn);
1438                 break;
1439 
1440         case OP_CALL:
1441                 generate_call(state, insn);
1442                 break;
1443 


1527         /* Is that pseudo a constant value? */
1528         switch (pseudo->type) {
1529         case PSEUDO_VAL:
1530                 write_val_to_storage(state, pseudo, out);
1531                 return;
1532         case PSEUDO_REG:
1533                 def = pseudo->def;
1534                 if (def && def->opcode == OP_SETVAL) {
1535                         write_val_to_storage(state, pseudo, out);
1536                         return;
1537                 }
1538         default:
1539                 break;
1540         }
1541 
1542         /* See if we have that pseudo in a register.. */
1543         for (i = 0; i < REGNO; i++) {
1544                 struct hardreg *reg = hardregs + i;
1545                 pseudo_t p;
1546 
1547                 FOR_EACH_PTR(reg->contains, p) {
1548                         if (p == pseudo) {
1549                                 write_reg_to_storage(state, reg, pseudo, out);
1550                                 return;
1551                         }
1552                 } END_FOR_EACH_PTR(p);
1553         }
1554 
1555         /* Do we have it in another storage? */
1556         in = find_storage_hash(pseudo, state->internal);
1557         if (!in) {
1558                 in = find_storage_hash(pseudo, state->inputs);
1559                 /* Undefined? */
1560                 if (!in)
1561                         return;
1562         }
1563         switch (out->type) {
1564         case REG_UDEF:
1565                 *out = *in->storage;
1566                 break;
1567         case REG_REG:


1635         return 1;
1636 }
1637 
1638 /*
1639  * This tries to make sure that we put all the pseudos that are
1640  * live on exit into the proper storage
1641  */
1642 static void generate_output_storage(struct bb_state *state)
1643 {
1644         struct storage_hash *entry;
1645 
1646         /* Go through the fixed outputs, making sure we have those regs free */
1647         FOR_EACH_PTR(state->outputs, entry) {
1648                 struct storage *out = entry->storage;
1649                 if (out->type == REG_REG) {
1650                         struct hardreg *reg = hardregs + out->regno;
1651                         pseudo_t p;
1652                         int flushme = 0;
1653 
1654                         reg->busy = REG_FIXED;
1655                         FOR_EACH_PTR(reg->contains, p) {
1656                                 if (p == entry->pseudo) {
1657                                         flushme = -100;
1658                                         continue;
1659                                 }
1660                                 if (CURRENT_TAG(p) & TAG_DEAD)
1661                                         continue;
1662 
1663                                 /* Try to write back the pseudo to where it should go ... */
1664                                 if (final_pseudo_flush(state, p, reg)) {
1665                                         DELETE_CURRENT_PTR(p);
1666                                         continue;
1667                                 }
1668                                 flushme++;
1669                         } END_FOR_EACH_PTR(p);
1670                         PACK_PTR_LIST(&reg->contains);
1671                         if (flushme > 0)
1672                                 flush_reg(state, reg);
1673                 }
1674         } END_FOR_EACH_PTR(entry);
1675 


1932 {
1933         struct symbol *sym;
1934         FOR_EACH_PTR(list, sym) {
1935                 struct entrypoint *ep;
1936                 expand_symbol(sym);
1937                 ep = linearize_symbol(sym);
1938                 if (ep)
1939                         output(ep);
1940         } END_FOR_EACH_PTR(sym);
1941         
1942         return 0;
1943 }
1944 
1945 int main(int argc, char **argv)
1946 {
1947         struct string_list *filelist = NULL;
1948         char *file;
1949 
1950         compile(sparse_initialize(argc, argv, &filelist));
1951         dbg_dead = 1;
1952         FOR_EACH_PTR_NOTAG(filelist, file) {
1953                 compile(sparse(file));
1954         } END_FOR_EACH_PTR_NOTAG(file);
1955         return 0;
1956 }
1957 


   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 #include "target.h"
  16 
  17 static const char *opcodes[] = {
  18         [OP_BADOP] = "bad_op",
  19 
  20         /* Fn entrypoint */
  21         [OP_ENTRY] = "<entry-point>",
  22 
  23         /* Terminator */
  24         [OP_RET] = "ret",
  25         [OP_BR] = "br",
  26         [OP_CBR] = "cbr",
  27         [OP_SWITCH] = "switch",

  28         [OP_COMPUTEDGOTO] = "jmp *",

  29         
  30         /* Binary */
  31         [OP_ADD] = "add",
  32         [OP_SUB] = "sub",
  33         [OP_MUL] = "mul",

  34         [OP_DIVU] = "divu",
  35         [OP_DIVS] = "divs",
  36         [OP_MODU] = "modu",
  37         [OP_MODS] = "mods",
  38         [OP_SHL] = "shl",
  39         [OP_LSR] = "lsr",
  40         [OP_ASR] = "asr",
  41         
  42         /* Logical */
  43         [OP_AND] = "and",
  44         [OP_OR] = "or",
  45         [OP_XOR] = "xor",


  46 
  47         /* Binary comparison */
  48         [OP_SET_EQ] = "seteq",
  49         [OP_SET_NE] = "setne",
  50         [OP_SET_LE] = "setle",
  51         [OP_SET_GE] = "setge",
  52         [OP_SET_LT] = "setlt",
  53         [OP_SET_GT] = "setgt",
  54         [OP_SET_B] = "setb",
  55         [OP_SET_A] = "seta",
  56         [OP_SET_BE] = "setbe",
  57         [OP_SET_AE] = "setae",
  58 
  59         /* Uni */
  60         [OP_NOT] = "not",
  61         [OP_NEG] = "neg",
  62 
  63         /* Special three-input */
  64         [OP_SEL] = "select",
  65         
  66         /* Memory */



  67         [OP_LOAD] = "load",
  68         [OP_STORE] = "store",
  69         [OP_SETVAL] = "set",

  70 
  71         /* Other */
  72         [OP_PHI] = "phi",
  73         [OP_PHISOURCE] = "phisrc",
  74         [OP_COPY] = "copy",
  75         [OP_SEXT] = "sext",
  76         [OP_ZEXT] = "zext",
  77         [OP_TRUNC] = "trunc",
  78         [OP_FCVTU] = "fcvtu",
  79         [OP_FCVTS] = "fcvts",
  80         [OP_UCVTF] = "ucvtf",
  81         [OP_SCVTF] = "scvtf",
  82         [OP_FCVTF] = "fcvtf",
  83         [OP_UTPTR] = "utptr",
  84         [OP_PTRTU] = "utptr",
  85         [OP_PTRCAST] = "ptrcast",
  86         [OP_CALL] = "call",


  87         [OP_SLICE] = "slice",


  88         [OP_NOP] = "nop",
  89         [OP_DEATHNOTE] = "dead",
  90         [OP_ASM] = "asm",
  91 
  92         /* Sparse tagging (line numbers, context, whatever) */
  93         [OP_CONTEXT] = "context",
  94 };
  95 
  96 static int last_reg, stack_offset;
  97 
  98 struct hardreg {
  99         const char *name;
 100         struct pseudo_list *contains;
 101         unsigned busy:16,
 102                  dead:8,
 103                  used:1;
 104 };
 105 
 106 #define TAG_DEAD 1
 107 #define TAG_DIRTY 2


 371         case REG_UDEF:
 372                 alloc_stack(state, storage);
 373                 /* Fall through */
 374         case REG_STACK:
 375                 output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage));
 376                 break;
 377         }
 378 }
 379 
 380 /* Flush a hardreg out to the storage it has.. */
 381 static void flush_reg(struct bb_state *state, struct hardreg *reg)
 382 {
 383         pseudo_t pseudo;
 384 
 385         if (reg->busy)
 386                 output_comment(state, "reg %s flushed while busy is %d!", reg->name, reg->busy);
 387         if (!reg->contains)
 388                 return;
 389         reg->dead = 0;
 390         reg->used = 1;
 391         FOR_EACH_PTR_TAG(reg->contains, pseudo) {
 392                 if (CURRENT_TAG(pseudo) & TAG_DEAD)
 393                         continue;
 394                 if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
 395                         continue;
 396                 flush_one_pseudo(state, reg, pseudo);
 397         } END_FOR_EACH_PTR(pseudo);
 398         free_ptr_list(&reg->contains);
 399 }
 400 
 401 static struct storage_hash *find_pseudo_storage(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 402 {
 403         struct storage_hash *src;
 404 
 405         src = find_storage_hash(pseudo, state->internal);
 406         if (!src) {
 407                 src = find_storage_hash(pseudo, state->inputs);
 408                 if (!src) {
 409                         src = find_storage_hash(pseudo, state->outputs);
 410                         /* Undefined? Screw it! */
 411                         if (!src)


 424          * Incoming pseudo with out any pre-set storage allocation?
 425          * We can make up our own, and obviously prefer to get it
 426          * in the register we already selected (if it hasn't been
 427          * used yet).
 428          */
 429         if (src->storage->type == REG_UDEF) {
 430                 if (reg && !reg->used) {
 431                         src->storage->type = REG_REG;
 432                         src->storage->regno = reg - hardregs;
 433                         return NULL;
 434                 }
 435                 alloc_stack(state, src->storage);
 436         }
 437         return src;
 438 }
 439 
 440 static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 441 {
 442         pseudo_t p;
 443 
 444         FOR_EACH_PTR_TAG(reg->contains, p) {
 445                 if (p != pseudo)
 446                         continue;
 447                 if (CURRENT_TAG(p) & TAG_DEAD)
 448                         continue;
 449                 output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
 450                 TAG_CURRENT(p, TAG_DEAD);
 451                 reg->dead++;
 452         } END_FOR_EACH_PTR(p);
 453 }
 454 
 455 static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 456 {
 457         output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name);
 458         add_ptr_list_tag(&reg->contains, pseudo, TAG_DIRTY);
 459 }
 460 
 461 static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target)
 462 {
 463         struct storage_hash *dst;
 464 


 509                         last_reg = i;
 510                         goto found;
 511                 }
 512         } while (i != last_reg);
 513         assert(unable_to_find_reg);
 514 
 515 found:
 516         add_pseudo_reg(state, pseudo, reg);
 517         return reg;
 518 }
 519 
 520 static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo)
 521 {
 522         int i;
 523         struct hardreg *reg;
 524 
 525         for (i = 0; i < REGNO; i++) {
 526                 pseudo_t p;
 527 
 528                 reg = hardregs + i;
 529                 FOR_EACH_PTR_TAG(reg->contains, p) {
 530                         if (p == pseudo) {
 531                                 last_reg = i;
 532                                 output_comment(state, "found pseudo %s in reg %s (busy=%d)", show_pseudo(pseudo), reg->name, reg->busy);
 533                                 return reg;
 534                         }
 535                 } END_FOR_EACH_PTR(p);
 536         }
 537         return NULL;
 538 }
 539 
 540 static void flush_pseudo(struct bb_state *state, pseudo_t pseudo, struct storage *storage)
 541 {
 542         struct hardreg *reg = find_in_reg(state, pseudo);
 543 
 544         if (reg)
 545                 flush_reg(state, reg);
 546 }
 547 
 548 static void flush_cc_cache_to_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 549 {


 849         const char *str = show_op(state, op);
 850         put_operand(state, op);
 851         return str;
 852 }
 853 
 854 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
 855 {
 856         switch(pseudo->type) {
 857         case PSEUDO_VAL:
 858                 return show_pseudo(pseudo);
 859         default:
 860                 return getreg(state, pseudo, NULL)->name;
 861         }
 862 }
 863 
 864 static void kill_dead_reg(struct hardreg *reg)
 865 {
 866         if (reg->dead) {
 867                 pseudo_t p;
 868                 
 869                 FOR_EACH_PTR_TAG(reg->contains, p) {
 870                         if (CURRENT_TAG(p) & TAG_DEAD) {
 871                                 DELETE_CURRENT_PTR(p);
 872                                 reg->dead--;
 873                         }
 874                 } END_FOR_EACH_PTR(p);
 875                 PACK_PTR_LIST(&reg->contains);
 876                 assert(!reg->dead);
 877         }
 878 }
 879 
 880 static struct hardreg *target_copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
 881 {
 882         kill_dead_reg(src);
 883         return copy_reg(state, src, target);
 884 }
 885 
 886 static void do_binop(struct bb_state *state, struct instruction *insn, pseudo_t val1, pseudo_t val2)
 887 {
 888         const char *op = opcodes[insn->opcode];
 889         struct operand *src = get_register_operand(state, val1, insn->target);
 890         struct operand *src2 = get_generic_operand(state, val2);
 891         struct hardreg *dst;
 892 
 893         dst = target_copy_reg(state, src->reg, insn->target);
 894         output_insn(state, "%s.%d %s,%s", op, insn->size, show_op(state, src2), dst->name);
 895         put_operand(state, src);
 896         put_operand(state, src2);
 897         add_pseudo_reg(state, insn->target, dst);
 898 }
 899 
 900 static void generate_binop(struct bb_state *state, struct instruction *insn)
 901 {
 902         flush_cc_cache(state);
 903         do_binop(state, insn, insn->src1, insn->src2);
 904 }
 905 
 906 static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
 907 {
 908         pseudo_t p;
 909         FOR_EACH_PTR_TAG(reg->contains, p) {
 910                 if (p == pseudo)
 911                         return CURRENT_TAG(p) & TAG_DEAD;
 912         } END_FOR_EACH_PTR(p);
 913         return 0;
 914 }
 915 
 916 /*
 917  * Commutative binops are much more flexible, since we can switch the
 918  * sources around to satisfy the target register, or to avoid having
 919  * to load one of them into a register..
 920  */
 921 static void generate_commutative_binop(struct bb_state *state, struct instruction *insn)
 922 {
 923         pseudo_t src1, src2;
 924         struct hardreg *reg1, *reg2;
 925 
 926         flush_cc_cache(state);
 927         src1 = insn->src1;
 928         src2 = insn->src2;
 929         reg2 = find_in_reg(state, src2);


 984 static void generate_load(struct instruction *insn, struct bb_state *state)
 985 {
 986         const char *input = address(state, insn);
 987         struct hardreg *dst;
 988 
 989         kill_dead_pseudos(state);
 990         dst = target_reg(state, insn->target, NULL);
 991         output_insn(state, "mov.%d %s,%s", insn->size, input, dst->name);
 992 }
 993 
 994 static void kill_pseudo(struct bb_state *state, pseudo_t pseudo)
 995 {
 996         int i;
 997         struct hardreg *reg;
 998 
 999         output_comment(state, "killing pseudo %s", show_pseudo(pseudo));
1000         for (i = 0; i < REGNO; i++) {
1001                 pseudo_t p;
1002 
1003                 reg = hardregs + i;
1004                 FOR_EACH_PTR_TAG(reg->contains, p) {
1005                         if (p != pseudo)
1006                                 continue;
1007                         if (CURRENT_TAG(p) & TAG_DEAD)
1008                                 reg->dead--;
1009                         output_comment(state, "removing pseudo %s from reg %s", 
1010                                 show_pseudo(pseudo), reg->name);
1011                         DELETE_CURRENT_PTR(p);
1012                 } END_FOR_EACH_PTR(p);
1013                 PACK_PTR_LIST(&reg->contains);
1014         }
1015 }
1016 
1017 static void generate_copy(struct bb_state *state, struct instruction *insn)
1018 {
1019         struct hardreg *src = getreg(state, insn->src, insn->target);
1020         kill_pseudo(state, insn->target);
1021         add_pseudo_reg(state, insn->target, src);
1022 }
1023 
1024 static void generate_cast(struct bb_state *state, struct instruction *insn)


1381          */
1382         case OP_SETVAL:
1383                 break;
1384 
1385         case OP_STORE:
1386                 generate_store(insn, state);
1387                 break;
1388 
1389         case OP_LOAD:
1390                 generate_load(insn, state);
1391                 break;
1392 
1393         case OP_DEATHNOTE:
1394                 mark_pseudo_dead(state, insn->target);
1395                 return;
1396 
1397         case OP_COPY:
1398                 generate_copy(state, insn);
1399                 break;
1400 
1401         case OP_ADD: case OP_MUL:
1402         case OP_AND: case OP_OR: case OP_XOR:

1403                 generate_commutative_binop(state, insn);
1404                 break;
1405 
1406         case OP_SUB: case OP_DIVU: case OP_DIVS:
1407         case OP_MODU: case OP_MODS:
1408         case OP_SHL: case OP_LSR: case OP_ASR:
1409                 generate_binop(state, insn);
1410                 break;
1411 
1412         case OP_BINCMP ... OP_BINCMP_END:
1413                 generate_compare(state, insn);
1414                 break;
1415 
1416         case OP_SEXT: case OP_ZEXT:
1417         case OP_TRUNC:
1418         case OP_PTRCAST:
1419         case OP_UTPTR:
1420         case OP_PTRTU:
1421         case OP_FCVTU: case OP_FCVTS:
1422         case OP_UCVTF: case OP_SCVTF:
1423         case OP_FCVTF:
1424                 generate_cast(state, insn);
1425                 break;
1426 
1427         case OP_SEL:
1428                 generate_select(state, insn);
1429                 break;
1430 
1431         case OP_BR:
1432         case OP_CBR:
1433                 generate_branch(state, insn);
1434                 break;
1435 
1436         case OP_SWITCH:
1437                 generate_switch(state, insn);
1438                 break;
1439 
1440         case OP_CALL:
1441                 generate_call(state, insn);
1442                 break;
1443 


1527         /* Is that pseudo a constant value? */
1528         switch (pseudo->type) {
1529         case PSEUDO_VAL:
1530                 write_val_to_storage(state, pseudo, out);
1531                 return;
1532         case PSEUDO_REG:
1533                 def = pseudo->def;
1534                 if (def && def->opcode == OP_SETVAL) {
1535                         write_val_to_storage(state, pseudo, out);
1536                         return;
1537                 }
1538         default:
1539                 break;
1540         }
1541 
1542         /* See if we have that pseudo in a register.. */
1543         for (i = 0; i < REGNO; i++) {
1544                 struct hardreg *reg = hardregs + i;
1545                 pseudo_t p;
1546 
1547                 FOR_EACH_PTR_TAG(reg->contains, p) {
1548                         if (p == pseudo) {
1549                                 write_reg_to_storage(state, reg, pseudo, out);
1550                                 return;
1551                         }
1552                 } END_FOR_EACH_PTR(p);
1553         }
1554 
1555         /* Do we have it in another storage? */
1556         in = find_storage_hash(pseudo, state->internal);
1557         if (!in) {
1558                 in = find_storage_hash(pseudo, state->inputs);
1559                 /* Undefined? */
1560                 if (!in)
1561                         return;
1562         }
1563         switch (out->type) {
1564         case REG_UDEF:
1565                 *out = *in->storage;
1566                 break;
1567         case REG_REG:


1635         return 1;
1636 }
1637 
1638 /*
1639  * This tries to make sure that we put all the pseudos that are
1640  * live on exit into the proper storage
1641  */
1642 static void generate_output_storage(struct bb_state *state)
1643 {
1644         struct storage_hash *entry;
1645 
1646         /* Go through the fixed outputs, making sure we have those regs free */
1647         FOR_EACH_PTR(state->outputs, entry) {
1648                 struct storage *out = entry->storage;
1649                 if (out->type == REG_REG) {
1650                         struct hardreg *reg = hardregs + out->regno;
1651                         pseudo_t p;
1652                         int flushme = 0;
1653 
1654                         reg->busy = REG_FIXED;
1655                         FOR_EACH_PTR_TAG(reg->contains, p) {
1656                                 if (p == entry->pseudo) {
1657                                         flushme = -100;
1658                                         continue;
1659                                 }
1660                                 if (CURRENT_TAG(p) & TAG_DEAD)
1661                                         continue;
1662 
1663                                 /* Try to write back the pseudo to where it should go ... */
1664                                 if (final_pseudo_flush(state, p, reg)) {
1665                                         DELETE_CURRENT_PTR(p);
1666                                         continue;
1667                                 }
1668                                 flushme++;
1669                         } END_FOR_EACH_PTR(p);
1670                         PACK_PTR_LIST(&reg->contains);
1671                         if (flushme > 0)
1672                                 flush_reg(state, reg);
1673                 }
1674         } END_FOR_EACH_PTR(entry);
1675 


1932 {
1933         struct symbol *sym;
1934         FOR_EACH_PTR(list, sym) {
1935                 struct entrypoint *ep;
1936                 expand_symbol(sym);
1937                 ep = linearize_symbol(sym);
1938                 if (ep)
1939                         output(ep);
1940         } END_FOR_EACH_PTR(sym);
1941         
1942         return 0;
1943 }
1944 
1945 int main(int argc, char **argv)
1946 {
1947         struct string_list *filelist = NULL;
1948         char *file;
1949 
1950         compile(sparse_initialize(argc, argv, &filelist));
1951         dbg_dead = 1;
1952         FOR_EACH_PTR(filelist, file) {
1953                 compile(sparse(file));
1954         } END_FOR_EACH_PTR(file);
1955         return 0;
1956 }
1957