| /* |
| * Example of how to write a compiler with sparse |
| */ |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <stdarg.h> |
| #include <string.h> |
| #include <assert.h> |
| |
| #include "symbol.h" |
| #include "expression.h" |
| #include "linearize.h" |
| #include "flow.h" |
| #include "storage.h" |
| #include "target.h" |
| |
| static const char *opcodes[] = { |
| [OP_BADOP] = "bad_op", |
| |
| /* Fn entrypoint */ |
| [OP_ENTRY] = "<entry-point>", |
| |
| /* Terminator */ |
| [OP_RET] = "ret", |
| [OP_BR] = "br", |
| [OP_SWITCH] = "switch", |
| [OP_INVOKE] = "invoke", |
| [OP_COMPUTEDGOTO] = "jmp *", |
| [OP_UNWIND] = "unwind", |
| |
| /* Binary */ |
| [OP_ADD] = "add", |
| [OP_SUB] = "sub", |
| [OP_MULU] = "mulu", |
| [OP_MULS] = "muls", |
| [OP_DIVU] = "divu", |
| [OP_DIVS] = "divs", |
| [OP_MODU] = "modu", |
| [OP_MODS] = "mods", |
| [OP_SHL] = "shl", |
| [OP_LSR] = "lsr", |
| [OP_ASR] = "asr", |
| |
| /* Logical */ |
| [OP_AND] = "and", |
| [OP_OR] = "or", |
| [OP_XOR] = "xor", |
| [OP_AND_BOOL] = "and-bool", |
| [OP_OR_BOOL] = "or-bool", |
| |
| /* Binary comparison */ |
| [OP_SET_EQ] = "seteq", |
| [OP_SET_NE] = "setne", |
| [OP_SET_LE] = "setle", |
| [OP_SET_GE] = "setge", |
| [OP_SET_LT] = "setlt", |
| [OP_SET_GT] = "setgt", |
| [OP_SET_B] = "setb", |
| [OP_SET_A] = "seta", |
| [OP_SET_BE] = "setbe", |
| [OP_SET_AE] = "setae", |
| |
| /* Uni */ |
| [OP_NOT] = "not", |
| [OP_NEG] = "neg", |
| |
| /* Special three-input */ |
| [OP_SEL] = "select", |
| |
| /* Memory */ |
| [OP_MALLOC] = "malloc", |
| [OP_FREE] = "free", |
| [OP_ALLOCA] = "alloca", |
| [OP_LOAD] = "load", |
| [OP_STORE] = "store", |
| [OP_SETVAL] = "set", |
| [OP_GET_ELEMENT_PTR] = "getelem", |
| |
| /* Other */ |
| [OP_PHI] = "phi", |
| [OP_PHISOURCE] = "phisrc", |
| [OP_COPY] = "copy", |
| [OP_CAST] = "cast", |
| [OP_SCAST] = "scast", |
| [OP_FPCAST] = "fpcast", |
| [OP_PTRCAST] = "ptrcast", |
| [OP_CALL] = "call", |
| [OP_VANEXT] = "va_next", |
| [OP_VAARG] = "va_arg", |
| [OP_SLICE] = "slice", |
| [OP_SNOP] = "snop", |
| [OP_LNOP] = "lnop", |
| [OP_NOP] = "nop", |
| [OP_DEATHNOTE] = "dead", |
| [OP_ASM] = "asm", |
| |
| /* Sparse tagging (line numbers, context, whatever) */ |
| [OP_CONTEXT] = "context", |
| }; |
| |
| static int last_reg, stack_offset; |
| |
| struct hardreg { |
| const char *name; |
| struct pseudo_list *contains; |
| unsigned busy:16, |
| dead:8, |
| used:1; |
| }; |
| |
| #define TAG_DEAD 1 |
| #define TAG_DIRTY 2 |
| |
| /* Our "switch" generation is very very stupid. */ |
| #define SWITCH_REG (1) |
| |
| static void output_bb(struct basic_block *bb, unsigned long generation); |
| |
| /* |
| * We only know about the caller-clobbered registers |
| * right now. |
| */ |
| static struct hardreg hardregs[] = { |
| { .name = "%eax" }, |
| { .name = "%edx" }, |
| { .name = "%ecx" }, |
| { .name = "%ebx" }, |
| { .name = "%esi" }, |
| { .name = "%edi" }, |
| |
| { .name = "%ebp" }, |
| { .name = "%esp" }, |
| }; |
| #define REGNO 6 |
| #define REG_EBP 6 |
| #define REG_ESP 7 |
| |
| struct bb_state { |
| struct position pos; |
| struct storage_hash_list *inputs; |
| struct storage_hash_list *outputs; |
| struct storage_hash_list *internal; |
| |
| /* CC cache.. */ |
| int cc_opcode, cc_dead; |
| pseudo_t cc_target; |
| }; |
| |
| enum optype { |
| OP_UNDEF, |
| OP_REG, |
| OP_VAL, |
| OP_MEM, |
| OP_ADDR, |
| }; |
| |
| struct operand { |
| enum optype type; |
| int size; |
| union { |
| struct hardreg *reg; |
| long long value; |
| struct /* OP_MEM and OP_ADDR */ { |
| unsigned int offset; |
| unsigned int scale; |
| struct symbol *sym; |
| struct hardreg *base; |
| struct hardreg *index; |
| }; |
| }; |
| }; |
| |
| static const char *show_op(struct bb_state *state, struct operand *op) |
| { |
| static char buf[256][4]; |
| static int bufnr; |
| char *p, *ret; |
| int nr; |
| |
| nr = (bufnr + 1) & 3; |
| bufnr = nr; |
| ret = p = buf[nr]; |
| |
| switch (op->type) { |
| case OP_UNDEF: |
| return "undef"; |
| case OP_REG: |
| return op->reg->name; |
| case OP_VAL: |
| sprintf(p, "$%lld", op->value); |
| break; |
| case OP_MEM: |
| case OP_ADDR: |
| if (op->offset) |
| p += sprintf(p, "%d", op->offset); |
| if (op->sym) |
| p += sprintf(p, "%s%s", |
| op->offset ? "+" : "", |
| show_ident(op->sym->ident)); |
| if (op->base || op->index) { |
| p += sprintf(p, "(%s%s%s", |
| op->base ? op->base->name : "", |
| (op->base && op->index) ? "," : "", |
| op->index ? op->index->name : ""); |
| if (op->scale > 1) |
| p += sprintf(p, ",%d", op->scale); |
| *p++ = ')'; |
| *p = '\0'; |
| } |
| break; |
| } |
| return ret; |
| } |
| |
| static struct storage_hash *find_storage_hash(pseudo_t pseudo, struct storage_hash_list *list) |
| { |
| struct storage_hash *entry; |
| FOR_EACH_PTR(list, entry) { |
| if (entry->pseudo == pseudo) |
| return entry; |
| } END_FOR_EACH_PTR(entry); |
| return NULL; |
| } |
| |
| static struct storage_hash *find_or_create_hash(pseudo_t pseudo, struct storage_hash_list **listp) |
| { |
| struct storage_hash *entry; |
| |
| entry = find_storage_hash(pseudo, *listp); |
| if (!entry) { |
| entry = alloc_storage_hash(alloc_storage()); |
| entry->pseudo = pseudo; |
| add_ptr_list(listp, entry); |
| } |
| return entry; |
| } |
| |
| /* Eventually we should just build it up in memory */ |
| static void FORMAT_ATTR(2) output_line(struct bb_state *state, const char *fmt, ...) |
| { |
| va_list args; |
| |
| va_start(args, fmt); |
| vprintf(fmt, args); |
| va_end(args); |
| } |
| |
| static void FORMAT_ATTR(2) output_label(struct bb_state *state, const char *fmt, ...) |
| { |
| static char buffer[512]; |
| va_list args; |
| |
| va_start(args, fmt); |
| vsnprintf(buffer, sizeof(buffer), fmt, args); |
| va_end(args); |
| |
| output_line(state, "%s:\n", buffer); |
| } |
| |
| static void FORMAT_ATTR(2) output_insn(struct bb_state *state, const char *fmt, ...) |
| { |
| static char buffer[512]; |
| va_list args; |
| |
| va_start(args, fmt); |
| vsnprintf(buffer, sizeof(buffer), fmt, args); |
| va_end(args); |
| |
| output_line(state, "\t%s\n", buffer); |
| } |
| |
| #define output_insn(state, fmt, arg...) \ |
| output_insn(state, fmt "\t\t# %s" , ## arg , __FUNCTION__) |
| |
| static void FORMAT_ATTR(2) output_comment(struct bb_state *state, const char *fmt, ...) |
| { |
| static char buffer[512]; |
| va_list args; |
| |
| if (!verbose) |
| return; |
| va_start(args, fmt); |
| vsnprintf(buffer, sizeof(buffer), fmt, args); |
| va_end(args); |
| |
| output_line(state, "\t# %s\n", buffer); |
| } |
| |
| static const char *show_memop(struct storage *storage) |
| { |
| static char buffer[1000]; |
| |
| if (!storage) |
| return "undef"; |
| switch (storage->type) { |
| case REG_FRAME: |
| sprintf(buffer, "%d(FP)", storage->offset); |
| break; |
| case REG_STACK: |
| sprintf(buffer, "%d(SP)", storage->offset); |
| break; |
| case REG_REG: |
| return hardregs[storage->regno].name; |
| default: |
| return show_storage(storage); |
| } |
| return buffer; |
| } |
| |
| static int alloc_stack_offset(int size) |
| { |
| int ret = stack_offset; |
| stack_offset = ret + size; |
| return ret; |
| } |
| |
| static void alloc_stack(struct bb_state *state, struct storage *storage) |
| { |
| storage->type = REG_STACK; |
| storage->offset = alloc_stack_offset(4); |
| } |
| |
| /* |
| * Can we re-generate the pseudo, so that we don't need to |
| * flush it to memory? We can regenerate: |
| * - immediates and symbol addresses |
| * - pseudos we got as input in non-registers |
| * - pseudos we've already saved off earlier.. |
| */ |
| static int can_regenerate(struct bb_state *state, pseudo_t pseudo) |
| { |
| struct storage_hash *in; |
| |
| switch (pseudo->type) { |
| case PSEUDO_VAL: |
| case PSEUDO_SYM: |
| return 1; |
| |
| default: |
| in = find_storage_hash(pseudo, state->inputs); |
| if (in && in->storage->type != REG_REG) |
| return 1; |
| in = find_storage_hash(pseudo, state->internal); |
| if (in) |
| return 1; |
| } |
| return 0; |
| } |
| |
| static void flush_one_pseudo(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo) |
| { |
| struct storage_hash *out; |
| struct storage *storage; |
| |
| if (can_regenerate(state, pseudo)) |
| return; |
| |
| output_comment(state, "flushing %s from %s", show_pseudo(pseudo), hardreg->name); |
| out = find_storage_hash(pseudo, state->internal); |
| if (!out) { |
| out = find_storage_hash(pseudo, state->outputs); |
| if (!out) |
| out = find_or_create_hash(pseudo, &state->internal); |
| } |
| storage = out->storage; |
| switch (storage->type) { |
| default: |
| /* |
| * Aieee - the next user wants it in a register, but we |
| * need to flush it to memory in between. Which means that |
| * we need to allocate an internal one, dammit.. |
| */ |
| out = find_or_create_hash(pseudo, &state->internal); |
| storage = out->storage; |
| /* Fall through */ |
| case REG_UDEF: |
| alloc_stack(state, storage); |
| /* Fall through */ |
| case REG_STACK: |
| output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage)); |
| break; |
| } |
| } |
| |
| /* Flush a hardreg out to the storage it has.. */ |
| static void flush_reg(struct bb_state *state, struct hardreg *reg) |
| { |
| pseudo_t pseudo; |
| |
| if (reg->busy) |
| output_comment(state, "reg %s flushed while busy is %d!", reg->name, reg->busy); |
| if (!reg->contains) |
| return; |
| reg->dead = 0; |
| reg->used = 1; |
| FOR_EACH_PTR(reg->contains, pseudo) { |
| if (CURRENT_TAG(pseudo) & TAG_DEAD) |
| continue; |
| if (!(CURRENT_TAG(pseudo) & TAG_DIRTY)) |
| continue; |
| flush_one_pseudo(state, reg, pseudo); |
| } END_FOR_EACH_PTR(pseudo); |
| free_ptr_list(®->contains); |
| } |
| |
| static struct storage_hash *find_pseudo_storage(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| struct storage_hash *src; |
| |
| src = find_storage_hash(pseudo, state->internal); |
| if (!src) { |
| src = find_storage_hash(pseudo, state->inputs); |
| if (!src) { |
| src = find_storage_hash(pseudo, state->outputs); |
| /* Undefined? Screw it! */ |
| if (!src) |
| return NULL; |
| |
| /* |
| * If we found output storage, it had better be local stack |
| * that we flushed to earlier.. |
| */ |
| if (src->storage->type != REG_STACK) |
| return NULL; |
| } |
| } |
| |
| /* |
| * Incoming pseudo with out any pre-set storage allocation? |
| * We can make up our own, and obviously prefer to get it |
| * in the register we already selected (if it hasn't been |
| * used yet). |
| */ |
| if (src->storage->type == REG_UDEF) { |
| if (reg && !reg->used) { |
| src->storage->type = REG_REG; |
| src->storage->regno = reg - hardregs; |
| return NULL; |
| } |
| alloc_stack(state, src->storage); |
| } |
| return src; |
| } |
| |
| static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| pseudo_t p; |
| |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p != pseudo) |
| continue; |
| if (CURRENT_TAG(p) & TAG_DEAD) |
| continue; |
| output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name); |
| TAG_CURRENT(p, TAG_DEAD); |
| reg->dead++; |
| } END_FOR_EACH_PTR(p); |
| } |
| |
| static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name); |
| add_ptr_list_tag(®->contains, pseudo, TAG_DIRTY); |
| } |
| |
| static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target) |
| { |
| struct storage_hash *dst; |
| |
| dst = find_storage_hash(target, state->outputs); |
| if (dst) { |
| struct storage *storage = dst->storage; |
| if (storage->type == REG_REG) |
| return hardregs + storage->regno; |
| } |
| return NULL; |
| } |
| |
| static struct hardreg *empty_reg(struct bb_state *state) |
| { |
| int i; |
| struct hardreg *reg = hardregs; |
| |
| for (i = 0; i < REGNO; i++, reg++) { |
| if (!reg->contains) |
| return reg; |
| } |
| return NULL; |
| } |
| |
| static struct hardreg *target_reg(struct bb_state *state, pseudo_t pseudo, pseudo_t target) |
| { |
| int i; |
| int unable_to_find_reg = 0; |
| struct hardreg *reg; |
| |
| /* First, see if we have a preferred target register.. */ |
| reg = preferred_reg(state, target); |
| if (reg && !reg->contains) |
| goto found; |
| |
| reg = empty_reg(state); |
| if (reg) |
| goto found; |
| |
| i = last_reg; |
| do { |
| i++; |
| if (i >= REGNO) |
| i = 0; |
| reg = hardregs + i; |
| if (!reg->busy) { |
| flush_reg(state, reg); |
| last_reg = i; |
| goto found; |
| } |
| } while (i != last_reg); |
| assert(unable_to_find_reg); |
| |
| found: |
| add_pseudo_reg(state, pseudo, reg); |
| return reg; |
| } |
| |
| static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo) |
| { |
| int i; |
| struct hardreg *reg; |
| |
| for (i = 0; i < REGNO; i++) { |
| pseudo_t p; |
| |
| reg = hardregs + i; |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p == pseudo) { |
| last_reg = i; |
| output_comment(state, "found pseudo %s in reg %s (busy=%d)", show_pseudo(pseudo), reg->name, reg->busy); |
| return reg; |
| } |
| } END_FOR_EACH_PTR(p); |
| } |
| return NULL; |
| } |
| |
| static void flush_pseudo(struct bb_state *state, pseudo_t pseudo, struct storage *storage) |
| { |
| struct hardreg *reg = find_in_reg(state, pseudo); |
| |
| if (reg) |
| flush_reg(state, reg); |
| } |
| |
| static void flush_cc_cache_to_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| int opcode = state->cc_opcode; |
| |
| state->cc_opcode = 0; |
| state->cc_target = NULL; |
| output_insn(state, "%s %s", opcodes[opcode], reg->name); |
| } |
| |
| static void flush_cc_cache(struct bb_state *state) |
| { |
| pseudo_t pseudo = state->cc_target; |
| |
| if (pseudo) { |
| struct hardreg *dst; |
| |
| state->cc_target = NULL; |
| |
| if (!state->cc_dead) { |
| dst = target_reg(state, pseudo, pseudo); |
| flush_cc_cache_to_reg(state, pseudo, dst); |
| } |
| } |
| } |
| |
| static void add_cc_cache(struct bb_state *state, int opcode, pseudo_t pseudo) |
| { |
| assert(!state->cc_target); |
| state->cc_target = pseudo; |
| state->cc_opcode = opcode; |
| state->cc_dead = 0; |
| output_comment(state, "caching %s", opcodes[opcode]); |
| } |
| |
| /* Fill a hardreg with the pseudo it has */ |
| static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo) |
| { |
| struct storage_hash *src; |
| struct instruction *def; |
| |
| if (state->cc_target == pseudo) { |
| flush_cc_cache_to_reg(state, pseudo, hardreg); |
| return hardreg; |
| } |
| |
| switch (pseudo->type) { |
| case PSEUDO_VAL: |
| output_insn(state, "movl $%lld,%s", pseudo->value, hardreg->name); |
| break; |
| case PSEUDO_SYM: |
| src = find_pseudo_storage(state, pseudo, NULL); |
| /* Static thing? */ |
| if (!src) { |
| output_insn(state, "movl $<%s>,%s", show_pseudo(pseudo), hardreg->name); |
| break; |
| } |
| switch (src->storage->type) { |
| case REG_REG: |
| /* Aiaiaiaiaii! Need to flush it to temporary memory */ |
| src = find_or_create_hash(pseudo, &state->internal); |
| /* Fall through */ |
| default: |
| alloc_stack(state, src->storage); |
| /* Fall through */ |
| case REG_STACK: |
| case REG_FRAME: |
| flush_pseudo(state, pseudo, src->storage); |
| output_insn(state, "leal %s,%s", show_memop(src->storage), hardreg->name); |
| break; |
| } |
| break; |
| case PSEUDO_ARG: |
| case PSEUDO_REG: |
| def = pseudo->def; |
| if (def && def->opcode == OP_SETVAL) { |
| output_insn(state, "movl $<%s>,%s", show_pseudo(def->target), hardreg->name); |
| break; |
| } |
| src = find_pseudo_storage(state, pseudo, hardreg); |
| if (!src) |
| break; |
| if (src->flags & TAG_DEAD) |
| mark_reg_dead(state, pseudo, hardreg); |
| output_insn(state, "mov.%d %s,%s", 32, show_memop(src->storage), hardreg->name); |
| break; |
| default: |
| output_insn(state, "reload %s from %s", hardreg->name, show_pseudo(pseudo)); |
| break; |
| } |
| return hardreg; |
| } |
| |
| static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target) |
| { |
| struct hardreg *reg; |
| |
| reg = find_in_reg(state, pseudo); |
| if (reg) |
| return reg; |
| reg = target_reg(state, pseudo, target); |
| return fill_reg(state, reg, pseudo); |
| } |
| |
| static void move_reg(struct bb_state *state, struct hardreg *src, struct hardreg *dst) |
| { |
| output_insn(state, "movl %s,%s", src->name, dst->name); |
| } |
| |
| static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target) |
| { |
| int i; |
| struct hardreg *reg; |
| |
| /* If the container has been killed off, just re-use it */ |
| if (!src->contains) |
| return src; |
| |
| /* If "src" only has one user, and the contents are dead, we can re-use it */ |
| if (src->busy == 1 && src->dead == 1) |
| return src; |
| |
| reg = preferred_reg(state, target); |
| if (reg && !reg->contains) { |
| output_comment(state, "copying %s to preferred target %s", show_pseudo(target), reg->name); |
| move_reg(state, src, reg); |
| return reg; |
| } |
| |
| for (i = 0; i < REGNO; i++) { |
| reg = hardregs + i; |
| if (!reg->contains) { |
| output_comment(state, "copying %s to %s", show_pseudo(target), reg->name); |
| output_insn(state, "movl %s,%s", src->name, reg->name); |
| return reg; |
| } |
| } |
| |
| flush_reg(state, src); |
| return src; |
| } |
| |
| static void put_operand(struct bb_state *state, struct operand *op) |
| { |
| switch (op->type) { |
| case OP_REG: |
| op->reg->busy--; |
| break; |
| case OP_ADDR: |
| case OP_MEM: |
| if (op->base) |
| op->base->busy--; |
| if (op->index) |
| op->index->busy--; |
| break; |
| default: |
| break; |
| } |
| } |
| |
| static struct operand *alloc_op(void) |
| { |
| struct operand *op = malloc(sizeof(*op)); |
| memset(op, 0, sizeof(*op)); |
| return op; |
| } |
| |
| static struct operand *get_register_operand(struct bb_state *state, pseudo_t pseudo, pseudo_t target) |
| { |
| struct operand *op = alloc_op(); |
| op->type = OP_REG; |
| op->reg = getreg(state, pseudo, target); |
| op->reg->busy++; |
| return op; |
| } |
| |
| static int get_sym_frame_offset(struct bb_state *state, pseudo_t pseudo) |
| { |
| int offset = pseudo->nr; |
| if (offset < 0) { |
| offset = alloc_stack_offset(4); |
| pseudo->nr = offset; |
| } |
| return offset; |
| } |
| |
| static struct operand *get_generic_operand(struct bb_state *state, pseudo_t pseudo) |
| { |
| struct hardreg *reg; |
| struct storage *src; |
| struct storage_hash *hash; |
| struct operand *op = malloc(sizeof(*op)); |
| |
| memset(op, 0, sizeof(*op)); |
| switch (pseudo->type) { |
| case PSEUDO_VAL: |
| op->type = OP_VAL; |
| op->value = pseudo->value; |
| break; |
| |
| case PSEUDO_SYM: { |
| struct symbol *sym = pseudo->sym; |
| op->type = OP_ADDR; |
| if (sym->ctype.modifiers & MOD_NONLOCAL) { |
| op->sym = sym; |
| break; |
| } |
| op->base = hardregs + REG_EBP; |
| op->offset = get_sym_frame_offset(state, pseudo); |
| break; |
| } |
| |
| default: |
| reg = find_in_reg(state, pseudo); |
| if (reg) { |
| op->type = OP_REG; |
| op->reg = reg; |
| reg->busy++; |
| break; |
| } |
| hash = find_pseudo_storage(state, pseudo, NULL); |
| if (!hash) |
| break; |
| src = hash->storage; |
| switch (src->type) { |
| case REG_REG: |
| op->type = OP_REG; |
| op->reg = hardregs + src->regno; |
| op->reg->busy++; |
| break; |
| case REG_FRAME: |
| op->type = OP_MEM; |
| op->offset = src->offset; |
| op->base = hardregs + REG_EBP; |
| break; |
| case REG_STACK: |
| op->type = OP_MEM; |
| op->offset = src->offset; |
| op->base = hardregs + REG_ESP; |
| break; |
| default: |
| break; |
| } |
| } |
| return op; |
| } |
| |
| /* Callers should be made to use the proper "operand" formats */ |
| static const char *generic(struct bb_state *state, pseudo_t pseudo) |
| { |
| struct hardreg *reg; |
| struct operand *op = get_generic_operand(state, pseudo); |
| static char buf[100]; |
| const char *str; |
| |
| switch (op->type) { |
| case OP_ADDR: |
| if (!op->offset && op->base && !op->sym) |
| return op->base->name; |
| if (op->sym && !op->base) { |
| int len = sprintf(buf, "$ %s", show_op(state, op)); |
| if (op->offset) |
| sprintf(buf + len, " + %d", op->offset); |
| return buf; |
| } |
| str = show_op(state, op); |
| put_operand(state, op); |
| reg = target_reg(state, pseudo, NULL); |
| output_insn(state, "lea %s,%s", show_op(state, op), reg->name); |
| return reg->name; |
| |
| default: |
| str = show_op(state, op); |
| } |
| put_operand(state, op); |
| return str; |
| } |
| |
| static struct operand *get_address_operand(struct bb_state *state, struct instruction *memop) |
| { |
| struct hardreg *base; |
| struct operand *op = get_generic_operand(state, memop->src); |
| |
| switch (op->type) { |
| case OP_ADDR: |
| op->offset += memop->offset; |
| break; |
| default: |
| put_operand(state, op); |
| base = getreg(state, memop->src, NULL); |
| op->type = OP_ADDR; |
| op->base = base; |
| base->busy++; |
| op->offset = memop->offset; |
| op->sym = NULL; |
| } |
| return op; |
| } |
| |
| static const char *address(struct bb_state *state, struct instruction *memop) |
| { |
| struct operand *op = get_address_operand(state, memop); |
| const char *str = show_op(state, op); |
| put_operand(state, op); |
| return str; |
| } |
| |
| static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo) |
| { |
| switch(pseudo->type) { |
| case PSEUDO_VAL: |
| return show_pseudo(pseudo); |
| default: |
| return getreg(state, pseudo, NULL)->name; |
| } |
| } |
| |
| static void kill_dead_reg(struct hardreg *reg) |
| { |
| if (reg->dead) { |
| pseudo_t p; |
| |
| FOR_EACH_PTR(reg->contains, p) { |
| if (CURRENT_TAG(p) & TAG_DEAD) { |
| DELETE_CURRENT_PTR(p); |
| reg->dead--; |
| } |
| } END_FOR_EACH_PTR(p); |
| PACK_PTR_LIST(®->contains); |
| assert(!reg->dead); |
| } |
| } |
| |
| static struct hardreg *target_copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target) |
| { |
| kill_dead_reg(src); |
| return copy_reg(state, src, target); |
| } |
| |
| static void do_binop(struct bb_state *state, struct instruction *insn, pseudo_t val1, pseudo_t val2) |
| { |
| const char *op = opcodes[insn->opcode]; |
| struct operand *src = get_register_operand(state, val1, insn->target); |
| struct operand *src2 = get_generic_operand(state, val2); |
| struct hardreg *dst; |
| |
| dst = target_copy_reg(state, src->reg, insn->target); |
| output_insn(state, "%s.%d %s,%s", op, insn->size, show_op(state, src2), dst->name); |
| put_operand(state, src); |
| put_operand(state, src2); |
| add_pseudo_reg(state, insn->target, dst); |
| } |
| |
| static void generate_binop(struct bb_state *state, struct instruction *insn) |
| { |
| flush_cc_cache(state); |
| do_binop(state, insn, insn->src1, insn->src2); |
| } |
| |
| static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| pseudo_t p; |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p == pseudo) |
| return CURRENT_TAG(p) & TAG_DEAD; |
| } END_FOR_EACH_PTR(p); |
| return 0; |
| } |
| |
| /* |
| * Commutative binops are much more flexible, since we can switch the |
| * sources around to satisfy the target register, or to avoid having |
| * to load one of them into a register.. |
| */ |
| static void generate_commutative_binop(struct bb_state *state, struct instruction *insn) |
| { |
| pseudo_t src1, src2; |
| struct hardreg *reg1, *reg2; |
| |
| flush_cc_cache(state); |
| src1 = insn->src1; |
| src2 = insn->src2; |
| reg2 = find_in_reg(state, src2); |
| if (!reg2) |
| goto dont_switch; |
| reg1 = find_in_reg(state, src1); |
| if (!reg1) |
| goto do_switch; |
| if (!is_dead_reg(state, src2, reg2)) |
| goto dont_switch; |
| if (!is_dead_reg(state, src1, reg1)) |
| goto do_switch; |
| |
| /* Both are dead. Is one preferable? */ |
| if (reg2 != preferred_reg(state, insn->target)) |
| goto dont_switch; |
| |
| do_switch: |
| src1 = src2; |
| src2 = insn->src1; |
| dont_switch: |
| do_binop(state, insn, src1, src2); |
| } |
| |
| /* |
| * This marks a pseudo dead. It still stays on the hardreg list (the hardreg |
| * still has its value), but it's scheduled to be killed after the next |
| * "sequence point" when we call "kill_read_pseudos()" |
| */ |
| static void mark_pseudo_dead(struct bb_state *state, pseudo_t pseudo) |
| { |
| int i; |
| struct storage_hash *src; |
| |
| if (state->cc_target == pseudo) |
| state->cc_dead = 1; |
| src = find_pseudo_storage(state, pseudo, NULL); |
| if (src) |
| src->flags |= TAG_DEAD; |
| for (i = 0; i < REGNO; i++) |
| mark_reg_dead(state, pseudo, hardregs + i); |
| } |
| |
| static void kill_dead_pseudos(struct bb_state *state) |
| { |
| int i; |
| |
| for (i = 0; i < REGNO; i++) { |
| kill_dead_reg(hardregs + i); |
| } |
| } |
| |
| static void generate_store(struct instruction *insn, struct bb_state *state) |
| { |
| output_insn(state, "mov.%d %s,%s", insn->size, reg_or_imm(state, insn->target), address(state, insn)); |
| } |
| |
| static void generate_load(struct instruction *insn, struct bb_state *state) |
| { |
| const char *input = address(state, insn); |
| struct hardreg *dst; |
| |
| kill_dead_pseudos(state); |
| dst = target_reg(state, insn->target, NULL); |
| output_insn(state, "mov.%d %s,%s", insn->size, input, dst->name); |
| } |
| |
| static void kill_pseudo(struct bb_state *state, pseudo_t pseudo) |
| { |
| int i; |
| struct hardreg *reg; |
| |
| output_comment(state, "killing pseudo %s", show_pseudo(pseudo)); |
| for (i = 0; i < REGNO; i++) { |
| pseudo_t p; |
| |
| reg = hardregs + i; |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p != pseudo) |
| continue; |
| if (CURRENT_TAG(p) & TAG_DEAD) |
| reg->dead--; |
| output_comment(state, "removing pseudo %s from reg %s", |
| show_pseudo(pseudo), reg->name); |
| DELETE_CURRENT_PTR(p); |
| } END_FOR_EACH_PTR(p); |
| PACK_PTR_LIST(®->contains); |
| } |
| } |
| |
| static void generate_copy(struct bb_state *state, struct instruction *insn) |
| { |
| struct hardreg *src = getreg(state, insn->src, insn->target); |
| kill_pseudo(state, insn->target); |
| add_pseudo_reg(state, insn->target, src); |
| } |
| |
| static void generate_cast(struct bb_state *state, struct instruction *insn) |
| { |
| struct hardreg *src = getreg(state, insn->src, insn->target); |
| struct hardreg *dst; |
| unsigned int old = insn->orig_type ? insn->orig_type->bit_size : 0; |
| unsigned int new = insn->size; |
| |
| /* |
| * Cast to smaller type? Ignore the high bits, we |
| * just keep both pseudos in the same register. |
| */ |
| if (old >= new) { |
| add_pseudo_reg(state, insn->target, src); |
| return; |
| } |
| |
| dst = target_copy_reg(state, src, insn->target); |
| |
| if (insn->orig_type && (insn->orig_type->ctype.modifiers & MOD_SIGNED)) { |
| output_insn(state, "sext.%d.%d %s", old, new, dst->name); |
| } else { |
| unsigned long long mask; |
| mask = ~(~0ULL << old); |
| mask &= ~(~0ULL << new); |
| output_insn(state, "andl.%d $%#llx,%s", insn->size, mask, dst->name); |
| } |
| add_pseudo_reg(state, insn->target, dst); |
| } |
| |
| static void generate_output_storage(struct bb_state *state); |
| |
| static const char *conditional[] = { |
| [OP_SET_EQ] = "e", |
| [OP_SET_NE] = "ne", |
| [OP_SET_LE] = "le", |
| [OP_SET_GE] = "ge", |
| [OP_SET_LT] = "lt", |
| [OP_SET_GT] = "gt", |
| [OP_SET_B] = "b", |
| [OP_SET_A] = "a", |
| [OP_SET_BE] = "be", |
| [OP_SET_AE] = "ae" |
| }; |
| |
| |
| static void generate_branch(struct bb_state *state, struct instruction *br) |
| { |
| const char *cond = "XXX"; |
| struct basic_block *target; |
| |
| if (br->cond) { |
| if (state->cc_target == br->cond) { |
| cond = conditional[state->cc_opcode]; |
| } else { |
| struct hardreg *reg = getreg(state, br->cond, NULL); |
| output_insn(state, "testl %s,%s", reg->name, reg->name); |
| cond = "ne"; |
| } |
| } |
| generate_output_storage(state); |
| target = br->bb_true; |
| if (br->cond) { |
| output_insn(state, "j%s .L%p", cond, target); |
| target = br->bb_false; |
| } |
| output_insn(state, "jmp .L%p", target); |
| } |
| |
| /* We've made sure that there is a dummy reg live for the output */ |
| static void generate_switch(struct bb_state *state, struct instruction *insn) |
| { |
| struct hardreg *reg = hardregs + SWITCH_REG; |
| |
| generate_output_storage(state); |
| output_insn(state, "switch on %s", reg->name); |
| output_insn(state, "unimplemented: %s", show_instruction(insn)); |
| } |
| |
| static void generate_ret(struct bb_state *state, struct instruction *ret) |
| { |
| if (ret->src && ret->src != VOID) { |
| struct hardreg *wants = hardregs+0; |
| struct hardreg *reg = getreg(state, ret->src, NULL); |
| if (reg != wants) |
| output_insn(state, "movl %s,%s", reg->name, wants->name); |
| } |
| output_insn(state, "ret"); |
| } |
| |
| /* |
| * Fake "call" linearization just as a taster.. |
| */ |
| static void generate_call(struct bb_state *state, struct instruction *insn) |
| { |
| int offset = 0; |
| pseudo_t arg; |
| |
| FOR_EACH_PTR(insn->arguments, arg) { |
| output_insn(state, "pushl %s", generic(state, arg)); |
| offset += 4; |
| } END_FOR_EACH_PTR(arg); |
| flush_reg(state, hardregs+0); |
| flush_reg(state, hardregs+1); |
| flush_reg(state, hardregs+2); |
| output_insn(state, "call %s", show_pseudo(insn->func)); |
| if (offset) |
| output_insn(state, "addl $%d,%%esp", offset); |
| if (insn->target && insn->target != VOID) |
| add_pseudo_reg(state, insn->target, hardregs+0); |
| } |
| |
| static void generate_select(struct bb_state *state, struct instruction *insn) |
| { |
| const char *cond; |
| struct hardreg *src1, *src2, *dst; |
| |
| src1 = getreg(state, insn->src2, NULL); |
| dst = copy_reg(state, src1, insn->target); |
| add_pseudo_reg(state, insn->target, dst); |
| src2 = getreg(state, insn->src3, insn->target); |
| |
| if (state->cc_target == insn->src1) { |
| cond = conditional[state->cc_opcode]; |
| } else { |
| struct hardreg *reg = getreg(state, insn->src1, NULL); |
| output_insn(state, "testl %s,%s", reg->name, reg->name); |
| cond = "ne"; |
| } |
| |
| output_insn(state, "sel%s %s,%s", cond, src2->name, dst->name); |
| } |
| |
| struct asm_arg { |
| const struct ident *name; |
| const char *value; |
| pseudo_t pseudo; |
| struct hardreg *reg; |
| }; |
| |
| static void replace_asm_arg(char **dst_p, struct asm_arg *arg) |
| { |
| char *dst = *dst_p; |
| int len = strlen(arg->value); |
| |
| memcpy(dst, arg->value, len); |
| *dst_p = dst + len; |
| } |
| |
| static void replace_asm_percent(const char **src_p, char **dst_p, struct asm_arg *args, int nr) |
| { |
| const char *src = *src_p; |
| char c; |
| int index; |
| |
| c = *src++; |
| switch (c) { |
| case '0' ... '9': |
| index = c - '0'; |
| if (index < nr) |
| replace_asm_arg(dst_p, args+index); |
| break; |
| } |
| *src_p = src; |
| return; |
| } |
| |
| static void replace_asm_named(const char **src_p, char **dst_p, struct asm_arg *args, int nr) |
| { |
| const char *src = *src_p; |
| const char *end = src; |
| |
| for(;;) { |
| char c = *end++; |
| if (!c) |
| return; |
| if (c == ']') { |
| int i; |
| |
| *src_p = end; |
| for (i = 0; i < nr; i++) { |
| const struct ident *ident = args[i].name; |
| int len; |
| if (!ident) |
| continue; |
| len = ident->len; |
| if (memcmp(src, ident->name, len)) |
| continue; |
| replace_asm_arg(dst_p, args+i); |
| return; |
| } |
| } |
| } |
| } |
| |
| static const char *replace_asm_args(const char *str, struct asm_arg *args, int nr) |
| { |
| static char buffer[1000]; |
| char *p = buffer; |
| |
| for (;;) { |
| char c = *str; |
| *p = c; |
| if (!c) |
| return buffer; |
| str++; |
| switch (c) { |
| case '%': |
| if (*str == '%') { |
| str++; |
| p++; |
| continue; |
| } |
| replace_asm_percent(&str, &p, args, nr); |
| continue; |
| case '[': |
| replace_asm_named(&str, &p, args, nr); |
| continue; |
| default: |
| break; |
| } |
| p++; |
| } |
| } |
| |
| #define MAX_ASM_ARG (50) |
| static struct asm_arg asm_arguments[MAX_ASM_ARG]; |
| |
| static struct asm_arg *generate_asm_inputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg) |
| { |
| struct asm_constraint *entry; |
| |
| FOR_EACH_PTR(list, entry) { |
| const char *constraint = entry->constraint; |
| pseudo_t pseudo = entry->pseudo; |
| struct hardreg *reg, *orig; |
| const char *string; |
| int index; |
| |
| string = "undef"; |
| switch (*constraint) { |
| case 'r': |
| string = getreg(state, pseudo, NULL)->name; |
| break; |
| case '0' ... '9': |
| index = *constraint - '0'; |
| reg = asm_arguments[index].reg; |
| orig = find_in_reg(state, pseudo); |
| if (orig) |
| move_reg(state, orig, reg); |
| else |
| fill_reg(state, reg, pseudo); |
| string = reg->name; |
| break; |
| default: |
| string = generic(state, pseudo); |
| break; |
| } |
| |
| output_insn(state, "# asm input \"%s\": %s : %s", constraint, show_pseudo(pseudo), string); |
| |
| arg->name = entry->ident; |
| arg->value = string; |
| arg->pseudo = NULL; |
| arg->reg = NULL; |
| arg++; |
| } END_FOR_EACH_PTR(entry); |
| return arg; |
| } |
| |
| static struct asm_arg *generate_asm_outputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg) |
| { |
| struct asm_constraint *entry; |
| |
| FOR_EACH_PTR(list, entry) { |
| const char *constraint = entry->constraint; |
| pseudo_t pseudo = entry->pseudo; |
| struct hardreg *reg; |
| const char *string; |
| |
| while (*constraint == '=' || *constraint == '+') |
| constraint++; |
| |
| string = "undef"; |
| switch (*constraint) { |
| case 'r': |
| default: |
| reg = target_reg(state, pseudo, NULL); |
| arg->pseudo = pseudo; |
| arg->reg = reg; |
| string = reg->name; |
| break; |
| } |
| |
| output_insn(state, "# asm output \"%s\": %s : %s", constraint, show_pseudo(pseudo), string); |
| |
| arg->name = entry->ident; |
| arg->value = string; |
| arg++; |
| } END_FOR_EACH_PTR(entry); |
| return arg; |
| } |
| |
| static void generate_asm(struct bb_state *state, struct instruction *insn) |
| { |
| const char *str = insn->string; |
| |
| if (insn->asm_rules->outputs || insn->asm_rules->inputs) { |
| struct asm_arg *arg; |
| |
| arg = generate_asm_outputs(state, insn->asm_rules->outputs, asm_arguments); |
| arg = generate_asm_inputs(state, insn->asm_rules->inputs, arg); |
| str = replace_asm_args(str, asm_arguments, arg - asm_arguments); |
| } |
| output_insn(state, "%s", str); |
| } |
| |
| static void generate_compare(struct bb_state *state, struct instruction *insn) |
| { |
| struct hardreg *src; |
| const char *src2; |
| int opcode; |
| |
| flush_cc_cache(state); |
| opcode = insn->opcode; |
| |
| /* |
| * We should try to switch these around if necessary, |
| * and update the opcode to match.. |
| */ |
| src = getreg(state, insn->src1, insn->target); |
| src2 = generic(state, insn->src2); |
| |
| output_insn(state, "cmp.%d %s,%s", insn->size, src2, src->name); |
| |
| add_cc_cache(state, opcode, insn->target); |
| } |
| |
| static void generate_one_insn(struct instruction *insn, struct bb_state *state) |
| { |
| if (verbose) |
| output_comment(state, "%s", show_instruction(insn)); |
| |
| switch (insn->opcode) { |
| case OP_ENTRY: { |
| struct symbol *sym = insn->bb->ep->name; |
| const char *name = show_ident(sym->ident); |
| if (sym->ctype.modifiers & MOD_STATIC) |
| printf("\n\n%s:\n", name); |
| else |
| printf("\n\n.globl %s\n%s:\n", name, name); |
| break; |
| } |
| |
| /* |
| * OP_SETVAL likewise doesn't actually generate any |
| * code. On use, the "def" of the pseudo will be |
| * looked up. |
| */ |
| case OP_SETVAL: |
| break; |
| |
| case OP_STORE: |
| generate_store(insn, state); |
| break; |
| |
| case OP_LOAD: |
| generate_load(insn, state); |
| break; |
| |
| case OP_DEATHNOTE: |
| mark_pseudo_dead(state, insn->target); |
| return; |
| |
| case OP_COPY: |
| generate_copy(state, insn); |
| break; |
| |
| case OP_ADD: case OP_MULU: case OP_MULS: |
| case OP_AND: case OP_OR: case OP_XOR: |
| case OP_AND_BOOL: case OP_OR_BOOL: |
| generate_commutative_binop(state, insn); |
| break; |
| |
| case OP_SUB: case OP_DIVU: case OP_DIVS: |
| case OP_MODU: case OP_MODS: |
| case OP_SHL: case OP_LSR: case OP_ASR: |
| generate_binop(state, insn); |
| break; |
| |
| case OP_BINCMP ... OP_BINCMP_END: |
| generate_compare(state, insn); |
| break; |
| |
| case OP_CAST: case OP_SCAST: case OP_FPCAST: case OP_PTRCAST: |
| generate_cast(state, insn); |
| break; |
| |
| case OP_SEL: |
| generate_select(state, insn); |
| break; |
| |
| case OP_BR: |
| generate_branch(state, insn); |
| break; |
| |
| case OP_SWITCH: |
| generate_switch(state, insn); |
| break; |
| |
| case OP_CALL: |
| generate_call(state, insn); |
| break; |
| |
| case OP_RET: |
| generate_ret(state, insn); |
| break; |
| |
| case OP_ASM: |
| generate_asm(state, insn); |
| break; |
| |
| case OP_PHI: |
| case OP_PHISOURCE: |
| default: |
| output_insn(state, "unimplemented: %s", show_instruction(insn)); |
| break; |
| } |
| kill_dead_pseudos(state); |
| } |
| |
| #define VERY_BUSY 1000 |
| #define REG_FIXED 2000 |
| |
| static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, pseudo_t pseudo, struct storage *storage) |
| { |
| int i; |
| struct hardreg *out; |
| |
| switch (storage->type) { |
| case REG_REG: |
| out = hardregs + storage->regno; |
| if (reg == out) |
| return; |
| output_insn(state, "movl %s,%s", reg->name, out->name); |
| return; |
| case REG_UDEF: |
| if (reg->busy < VERY_BUSY) { |
| storage->type = REG_REG; |
| storage->regno = reg - hardregs; |
| reg->busy = REG_FIXED; |
| return; |
| } |
| |
| /* Try to find a non-busy register.. */ |
| for (i = 0; i < REGNO; i++) { |
| out = hardregs + i; |
| if (out->contains) |
| continue; |
| output_insn(state, "movl %s,%s", reg->name, out->name); |
| storage->type = REG_REG; |
| storage->regno = i; |
| out->busy = REG_FIXED; |
| return; |
| } |
| |
| /* Fall back on stack allocation ... */ |
| alloc_stack(state, storage); |
| /* Fall through */ |
| default: |
| output_insn(state, "movl %s,%s", reg->name, show_memop(storage)); |
| return; |
| } |
| } |
| |
| static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage) |
| { |
| struct hardreg *out; |
| |
| switch (storage->type) { |
| case REG_UDEF: |
| alloc_stack(state, storage); |
| default: |
| output_insn(state, "movl %s,%s", show_pseudo(src), show_memop(storage)); |
| break; |
| case REG_REG: |
| out = hardregs + storage->regno; |
| output_insn(state, "movl %s,%s", show_pseudo(src), out->name); |
| } |
| } |
| |
| static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out) |
| { |
| int i; |
| struct storage_hash *in; |
| struct instruction *def; |
| |
| /* Is that pseudo a constant value? */ |
| switch (pseudo->type) { |
| case PSEUDO_VAL: |
| write_val_to_storage(state, pseudo, out); |
| return; |
| case PSEUDO_REG: |
| def = pseudo->def; |
| if (def && def->opcode == OP_SETVAL) { |
| write_val_to_storage(state, pseudo, out); |
| return; |
| } |
| default: |
| break; |
| } |
| |
| /* See if we have that pseudo in a register.. */ |
| for (i = 0; i < REGNO; i++) { |
| struct hardreg *reg = hardregs + i; |
| pseudo_t p; |
| |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p == pseudo) { |
| write_reg_to_storage(state, reg, pseudo, out); |
| return; |
| } |
| } END_FOR_EACH_PTR(p); |
| } |
| |
| /* Do we have it in another storage? */ |
| in = find_storage_hash(pseudo, state->internal); |
| if (!in) { |
| in = find_storage_hash(pseudo, state->inputs); |
| /* Undefined? */ |
| if (!in) |
| return; |
| } |
| switch (out->type) { |
| case REG_UDEF: |
| *out = *in->storage; |
| break; |
| case REG_REG: |
| output_insn(state, "movl %s,%s", show_memop(in->storage), hardregs[out->regno].name); |
| break; |
| default: |
| if (out == in->storage) |
| break; |
| if ((out->type == in->storage->type) && (out->regno == in->storage->regno)) |
| break; |
| output_insn(state, "movl %s,%s", show_memop(in->storage), show_memop(out)); |
| break; |
| } |
| return; |
| } |
| |
| static int final_pseudo_flush(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg) |
| { |
| struct storage_hash *hash; |
| struct storage *out; |
| struct hardreg *dst; |
| |
| /* |
| * Since this pseudo is live at exit, we'd better have output |
| * storage for it.. |
| */ |
| hash = find_storage_hash(pseudo, state->outputs); |
| if (!hash) |
| return 1; |
| out = hash->storage; |
| |
| /* If the output is in a register, try to get it there.. */ |
| if (out->type == REG_REG) { |
| dst = hardregs + out->regno; |
| /* |
| * Two good cases: nobody is using the right register, |
| * or we've already set it aside for output.. |
| */ |
| if (!dst->contains || dst->busy > VERY_BUSY) |
| goto copy_to_dst; |
| |
| /* Aiee. Try to keep it in a register.. */ |
| dst = empty_reg(state); |
| if (dst) |
| goto copy_to_dst; |
| |
| return 0; |
| } |
| |
| /* If the output is undefined, let's see if we can put it in a register.. */ |
| if (out->type == REG_UDEF) { |
| dst = empty_reg(state); |
| if (dst) { |
| out->type = REG_REG; |
| out->regno = dst - hardregs; |
| goto copy_to_dst; |
| } |
| /* Uhhuh. Not so good. No empty registers right now */ |
| return 0; |
| } |
| |
| /* If we know we need to flush it, just do so already .. */ |
| output_insn(state, "movl %s,%s", reg->name, show_memop(out)); |
| return 1; |
| |
| copy_to_dst: |
| if (reg == dst) |
| return 1; |
| output_insn(state, "movl %s,%s", reg->name, dst->name); |
| add_pseudo_reg(state, pseudo, dst); |
| return 1; |
| } |
| |
| /* |
| * This tries to make sure that we put all the pseudos that are |
| * live on exit into the proper storage |
| */ |
| static void generate_output_storage(struct bb_state *state) |
| { |
| struct storage_hash *entry; |
| |
| /* Go through the fixed outputs, making sure we have those regs free */ |
| FOR_EACH_PTR(state->outputs, entry) { |
| struct storage *out = entry->storage; |
| if (out->type == REG_REG) { |
| struct hardreg *reg = hardregs + out->regno; |
| pseudo_t p; |
| int flushme = 0; |
| |
| reg->busy = REG_FIXED; |
| FOR_EACH_PTR(reg->contains, p) { |
| if (p == entry->pseudo) { |
| flushme = -100; |
| continue; |
| } |
| if (CURRENT_TAG(p) & TAG_DEAD) |
| continue; |
| |
| /* Try to write back the pseudo to where it should go ... */ |
| if (final_pseudo_flush(state, p, reg)) { |
| DELETE_CURRENT_PTR(p); |
| continue; |
| } |
| flushme++; |
| } END_FOR_EACH_PTR(p); |
| PACK_PTR_LIST(®->contains); |
| if (flushme > 0) |
| flush_reg(state, reg); |
| } |
| } END_FOR_EACH_PTR(entry); |
| |
| FOR_EACH_PTR(state->outputs, entry) { |
| fill_output(state, entry->pseudo, entry->storage); |
| } END_FOR_EACH_PTR(entry); |
| } |
| |
| static void generate(struct basic_block *bb, struct bb_state *state) |
| { |
| int i; |
| struct storage_hash *entry; |
| struct instruction *insn; |
| |
| for (i = 0; i < REGNO; i++) { |
| free_ptr_list(&hardregs[i].contains); |
| hardregs[i].busy = 0; |
| hardregs[i].dead = 0; |
| hardregs[i].used = 0; |
| } |
| |
| FOR_EACH_PTR(state->inputs, entry) { |
| struct storage *storage = entry->storage; |
| const char *name = show_storage(storage); |
| output_comment(state, "incoming %s in %s", show_pseudo(entry->pseudo), name); |
| if (storage->type == REG_REG) { |
| int regno = storage->regno; |
| add_pseudo_reg(state, entry->pseudo, hardregs + regno); |
| name = hardregs[regno].name; |
| } |
| } END_FOR_EACH_PTR(entry); |
| |
| output_label(state, ".L%p", bb); |
| FOR_EACH_PTR(bb->insns, insn) { |
| if (!insn->bb) |
| continue; |
| generate_one_insn(insn, state); |
| } END_FOR_EACH_PTR(insn); |
| |
| if (verbose) { |
| output_comment(state, "--- in ---"); |
| FOR_EACH_PTR(state->inputs, entry) { |
| output_comment(state, "%s <- %s", show_pseudo(entry->pseudo), show_storage(entry->storage)); |
| } END_FOR_EACH_PTR(entry); |
| output_comment(state, "--- spill ---"); |
| FOR_EACH_PTR(state->internal, entry) { |
| output_comment(state, "%s <-> %s", show_pseudo(entry->pseudo), show_storage(entry->storage)); |
| } END_FOR_EACH_PTR(entry); |
| output_comment(state, "--- out ---"); |
| FOR_EACH_PTR(state->outputs, entry) { |
| output_comment(state, "%s -> %s", show_pseudo(entry->pseudo), show_storage(entry->storage)); |
| } END_FOR_EACH_PTR(entry); |
| } |
| printf("\n"); |
| } |
| |
| static void generate_list(struct basic_block_list *list, unsigned long generation) |
| { |
| struct basic_block *bb; |
| FOR_EACH_PTR(list, bb) { |
| if (bb->generation == generation) |
| continue; |
| output_bb(bb, generation); |
| } END_FOR_EACH_PTR(bb); |
| } |
| |
| /* |
| * Mark all the output registers of all the parents |
| * as being "used" - this does not mean that we cannot |
| * re-use them, but it means that we cannot ask the |
| * parents to pass in another pseudo in one of those |
| * registers that it already uses for another child. |
| */ |
| static void mark_used_registers(struct basic_block *bb, struct bb_state *state) |
| { |
| struct basic_block *parent; |
| |
| FOR_EACH_PTR(bb->parents, parent) { |
| struct storage_hash_list *outputs = gather_storage(parent, STOR_OUT); |
| struct storage_hash *entry; |
| |
| FOR_EACH_PTR(outputs, entry) { |
| struct storage *s = entry->storage; |
| if (s->type == REG_REG) { |
| struct hardreg *reg = hardregs + s->regno; |
| reg->used = 1; |
| } |
| } END_FOR_EACH_PTR(entry); |
| } END_FOR_EACH_PTR(parent); |
| } |
| |
| static void output_bb(struct basic_block *bb, unsigned long generation) |
| { |
| struct bb_state state; |
| |
| bb->generation = generation; |
| |
| /* Make sure all parents have been generated first */ |
| generate_list(bb->parents, generation); |
| |
| state.pos = bb->pos; |
| state.inputs = gather_storage(bb, STOR_IN); |
| state.outputs = gather_storage(bb, STOR_OUT); |
| state.internal = NULL; |
| state.cc_opcode = 0; |
| state.cc_target = NULL; |
| |
| /* Mark incoming registers used */ |
| mark_used_registers(bb, &state); |
| |
| generate(bb, &state); |
| |
| free_ptr_list(&state.inputs); |
| free_ptr_list(&state.outputs); |
| |
| /* Generate all children... */ |
| generate_list(bb->children, generation); |
| } |
| |
| /* |
| * We should set up argument sources here.. |
| * |
| * Things like "first three arguments in registers" etc |
| * are all for this place. |
| * |
| * On x86, we default to stack, unless it's a static |
| * function that doesn't have its address taken. |
| * |
| * I should implement the -mregparm=X cmd line option. |
| */ |
| static void set_up_arch_entry(struct entrypoint *ep, struct instruction *entry) |
| { |
| pseudo_t arg; |
| struct symbol *sym, *argtype; |
| int i, offset, regparm; |
| |
| sym = ep->name; |
| regparm = 0; |
| if (!(sym->ctype.modifiers & MOD_ADDRESSABLE)) |
| regparm = 3; |
| sym = sym->ctype.base_type; |
| i = 0; |
| offset = 0; |
| PREPARE_PTR_LIST(sym->arguments, argtype); |
| FOR_EACH_PTR(entry->arg_list, arg) { |
| struct storage *in = lookup_storage(entry->bb, arg, STOR_IN); |
| if (!in) { |
| in = alloc_storage(); |
| add_storage(in, entry->bb, arg, STOR_IN); |
| } |
| if (i < regparm) { |
| in->type = REG_REG; |
| in->regno = i; |
| } else { |
| int bits = argtype ? argtype->bit_size : 0; |
| |
| if (bits < bits_in_int) |
| bits = bits_in_int; |
| |
| in->type = REG_FRAME; |
| in->offset = offset; |
| |
| offset += bits_to_bytes(bits); |
| } |
| i++; |
| NEXT_PTR_LIST(argtype); |
| } END_FOR_EACH_PTR(arg); |
| FINISH_PTR_LIST(argtype); |
| } |
| |
| /* |
| * Set up storage information for "return" |
| * |
| * Not strictly necessary, since the code generator will |
| * certainly move the return value to the right register, |
| * but it can help register allocation if the allocator |
| * sees that the target register is going to return in %eax. |
| */ |
| static void set_up_arch_exit(struct basic_block *bb, struct instruction *ret) |
| { |
| pseudo_t pseudo = ret->src; |
| |
| if (pseudo && pseudo != VOID) { |
| struct storage *out = lookup_storage(bb, pseudo, STOR_OUT); |
| if (!out) { |
| out = alloc_storage(); |
| add_storage(out, bb, pseudo, STOR_OUT); |
| } |
| out->type = REG_REG; |
| out->regno = 0; |
| } |
| } |
| |
| /* |
| * Set up dummy/silly output storage information for a switch |
| * instruction. We need to make sure that a register is available |
| * when we generate code for switch, so force that by creating |
| * a dummy output rule. |
| */ |
| static void set_up_arch_switch(struct basic_block *bb, struct instruction *insn) |
| { |
| pseudo_t pseudo = insn->cond; |
| struct storage *out = lookup_storage(bb, pseudo, STOR_OUT); |
| if (!out) { |
| out = alloc_storage(); |
| add_storage(out, bb, pseudo, STOR_OUT); |
| } |
| out->type = REG_REG; |
| out->regno = SWITCH_REG; |
| } |
| |
| static void arch_set_up_storage(struct entrypoint *ep) |
| { |
| struct basic_block *bb; |
| |
| /* Argument storage etc.. */ |
| set_up_arch_entry(ep, ep->entry); |
| |
| FOR_EACH_PTR(ep->bbs, bb) { |
| struct instruction *insn = last_instruction(bb->insns); |
| if (!insn) |
| continue; |
| switch (insn->opcode) { |
| case OP_RET: |
| set_up_arch_exit(bb, insn); |
| break; |
| case OP_SWITCH: |
| set_up_arch_switch(bb, insn); |
| break; |
| default: |
| /* nothing */; |
| } |
| } END_FOR_EACH_PTR(bb); |
| } |
| |
| static void output(struct entrypoint *ep) |
| { |
| unsigned long generation = ++bb_generation; |
| |
| last_reg = -1; |
| stack_offset = 0; |
| |
| /* Get rid of SSA form (phinodes etc) */ |
| unssa(ep); |
| |
| /* Set up initial inter-bb storage links */ |
| set_up_storage(ep); |
| |
| /* Architecture-specific storage rules.. */ |
| arch_set_up_storage(ep); |
| |
| /* Show the results ... */ |
| output_bb(ep->entry->bb, generation); |
| |
| /* Clear the storage hashes for the next function.. */ |
| free_storage(); |
| } |
| |
| static int compile(struct symbol_list *list) |
| { |
| struct symbol *sym; |
| FOR_EACH_PTR(list, sym) { |
| struct entrypoint *ep; |
| expand_symbol(sym); |
| ep = linearize_symbol(sym); |
| if (ep) |
| output(ep); |
| } END_FOR_EACH_PTR(sym); |
| |
| return 0; |
| } |
| |
| int main(int argc, char **argv) |
| { |
| struct string_list *filelist = NULL; |
| char *file; |
| |
| compile(sparse_initialize(argc, argv, &filelist)); |
| dbg_dead = 1; |
| FOR_EACH_PTR_NOTAG(filelist, file) { |
| compile(sparse(file)); |
| } END_FOR_EACH_PTR_NOTAG(file); |
| return 0; |
| } |
| |