X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fia32%2Fia32_x87.c;h=2a60119f29cf215f20d77aa952b5267d568a1277;hb=7d4dbfc7158613bdee5a2fa005ef06541eb1b81b;hp=1e4b0a17df08c1d4af654d196d9d1e15d89bf874;hpb=5b25a09b309b97b22a435ac82504c5d507e59093;p=libfirm diff --git a/ir/be/ia32/ia32_x87.c b/ir/be/ia32/ia32_x87.c index 1e4b0a17d..202f57bc5 100644 --- a/ir/be/ia32/ia32_x87.c +++ b/ir/be/ia32/ia32_x87.c @@ -1,15 +1,29 @@ -/** - * This file implements the x87 support and virtual to stack - * register translation for the ia32 backend. +/* + * Copyright (C) 1995-2010 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. * - * @author: Michael Beck + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. * - * $Id$ + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifdef HAVE_CONFIG_H +/** + * @file + * @brief This file implements the x87 support and virtual to stack + * register translation for the ia32 backend. + * @author Michael Beck + */ #include "config.h" -#endif /* HAVE_CONFIG_H */ #include @@ -19,37 +33,31 @@ #include "iredges_t.h" #include "irgmod.h" #include "ircons.h" +#include "irgwalk.h" #include "obst.h" #include "pmap.h" +#include "array_t.h" #include "pdeq.h" #include "irprintf.h" #include "debug.h" +#include "error.h" -#include "../belive_t.h" -#include "../besched.h" -#include "../benode_t.h" +#include "belive_t.h" +#include "besched.h" +#include "benode.h" +#include "bearch_ia32_t.h" #include "ia32_new_nodes.h" #include "gen_ia32_new_nodes.h" #include "gen_ia32_regalloc_if.h" #include "ia32_x87.h" - -#define N_x87_REGS 8 - -/* first and second binop index */ -#define BINOP_IDX_1 2 -#define BINOP_IDX_2 3 - -/* the unop index */ -#define UNOP_IDX 0 - -/* the store val index */ -#define STORE_VAL_IDX 2 - -#define MASK_TOS(x) ((x) & (N_x87_REGS - 1)) +#include "ia32_architecture.h" /** the debug handle */ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) +/* Forward declaration. */ +typedef struct x87_simulator x87_simulator; + /** * An exchange template. * Note that our virtual functions have the same inputs @@ -57,7 +65,7 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) * their opcodes! * Further, x87 supports inverse instructions, so we can handle them. */ -typedef struct _exchange_tmpl { +typedef struct exchange_tmpl { ir_op *normal_op; /**< the normal one */ ir_op *reverse_op; /**< the reverse one if exists */ ir_op *normal_pop_op; /**< the normal one with tos pop */ @@ -67,66 +75,83 @@ typedef struct _exchange_tmpl { /** * An entry on the simulated x87 stack. */ -typedef struct _st_entry { - int reg_idx; /**< the virtual register index of this stack value */ - ir_node *node; /**< the node that produced this value */ +typedef struct st_entry { + int reg_idx; /**< the virtual register index of this stack value */ + ir_node *node; /**< the node that produced this value */ } st_entry; /** * The x87 state. */ -typedef struct _x87_state { - st_entry st[N_x87_REGS]; /**< the register stack */ - int depth; /**< the current stack depth */ - int tos; /**< position of the tos */ +typedef struct x87_state { + st_entry st[N_ia32_st_REGS]; /**< the register stack */ + int depth; /**< the current stack depth */ + x87_simulator *sim; /**< The simulator. */ } x87_state; /** An empty state, used for blocks without fp instructions. */ -static const x87_state _empty = { {0, NULL}, 0, 0 }; -static x87_state *empty = (x87_state *)&_empty; +static x87_state empty = { { {0, NULL}, }, 0, NULL }; + +/** + * Return values of the instruction simulator functions. + */ +enum { + NO_NODE_ADDED = 0, /**< No node that needs simulation was added. */ + NODE_ADDED = 1 /**< A node that must be simulated was added by the simulator + in the schedule AFTER the current node. */ +}; -/** The type of an instruction simulator */ -typedef void (*sim_func)(x87_state *state, ir_node *n, const arch_env_t *env); +/** + * The type of an instruction simulator function. + * + * @param state the x87 state + * @param n the node to be simulated + * + * @return NODE_ADDED if a node was added AFTER n in schedule that MUST be + * simulated further + * NO_NODE_ADDED otherwise + */ +typedef int (*sim_func)(x87_state *state, ir_node *n); /** * A block state: Every block has a x87 state at the beginning and at the end. */ -typedef struct _blk_state { +typedef struct blk_state { x87_state *begin; /**< state at the begin or NULL if not assigned */ x87_state *end; /**< state at the end or NULL if not assigned */ } blk_state; -#define PTR_TO_BLKSTATE(p) ((blk_state *)(p)) +/** liveness bitset for vfp registers. */ +typedef unsigned char vfp_liveness; /** * The x87 simulator. */ -typedef struct _x87_simulator { - struct obstack obst; /**< an obstack for fast allocating */ - pmap *blk_states; /**< map blocks to states */ - const arch_env_t *env; /**< architecture environment */ -} x87_simulator; +struct x87_simulator { + struct obstack obst; /**< An obstack for fast allocating. */ + pmap *blk_states; /**< Map blocks to states. */ + be_lv_t *lv; /**< intrablock liveness. */ + vfp_liveness *live; /**< Liveness information. */ + unsigned n_idx; /**< The cached get_irg_last_idx() result. */ + waitq *worklist; /**< Worklist of blocks that must be processed. */ +}; /** - * Returns the stack depth. + * Returns the current stack depth. * * @param state the x87 state * * @return the x87 stack depth */ -static int x87_get_depth(const x87_state *state) { +static int x87_get_depth(const x87_state *state) +{ return state->depth; } -/** - * Check if the state is empty. - * - * @param state the x87 state - * - * returns non-zero if the x87 stack is empty - */ -static int x87_state_is_empty(const x87_state *state) { - return state->depth == 0; +static st_entry *x87_get_entry(x87_state *const state, int const pos) +{ + assert(0 <= pos && pos < state->depth); + return &state->st[N_ia32_st_REGS - state->depth + pos]; } /** @@ -137,22 +162,9 @@ static int x87_state_is_empty(const x87_state *state) { * * @return the vfp register index that produced the value at st(pos) */ -static int x87_get_st_reg(const x87_state *state, int pos) { - assert(pos < state->depth); - return state->st[MASK_TOS(state->tos + pos)].reg_idx; -} - -/** - * Return the node at st(pos). - * - * @param state the x87 state - * @param pos a stack position - * - * @return the IR node that produced the value at st(pos) - */ -static ir_node *x87_get_st_node(const x87_state *state, int pos) { - assert(pos < state->depth); - return state->st[MASK_TOS(state->tos + pos)].node; +static int x87_get_st_reg(const x87_state *state, int pos) +{ + return x87_get_entry((x87_state*)state, pos)->reg_idx; } #ifdef DEBUG_libfirm @@ -161,11 +173,11 @@ static ir_node *x87_get_st_node(const x87_state *state, int pos) { * * @param state the x87 state */ -static void x87_dump_stack(const x87_state *state) { - int i; - - for (i = state->depth - 1; i >= 0; --i) { - DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i))); +static void x87_dump_stack(const x87_state *state) +{ + for (int i = state->depth; i-- != 0;) { + st_entry const *const entry = x87_get_entry((x87_state*)state, i); + DB((dbg, LEVEL_2, "vf%d(%+F) ", entry->reg_idx, entry->node)); } DB((dbg, LEVEL_2, "<-- TOS\n")); } @@ -179,12 +191,14 @@ static void x87_dump_stack(const x87_state *state) { * @param node the IR node that produces the value of the vfp register * @param pos the stack position where the new value should be entered */ -static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) { - assert(0 < state->depth); - state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx; - state->st[MASK_TOS(state->tos + pos)].node = node; +static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) +{ + st_entry *const entry = x87_get_entry(state, pos); + entry->reg_idx = reg_idx; + entry->node = node; - DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state)); + DB((dbg, LEVEL_2, "After SET_REG: ")); + DEBUG_ONLY(x87_dump_stack(state);) } /** @@ -194,35 +208,27 @@ static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) { * @param reg_idx the vfp register index that should be set * @param node the IR node that produces the value of the vfp register */ -static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) { +static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) +{ x87_set_st(state, reg_idx, node, 0); } -/** - * Flush the x87 stack. - * - * @param state the x87 state - */ -static void x87_flush(x87_state *state) { - state->depth = 0; - state->tos = 0; -} - /** * Swap st(0) with st(pos). * * @param state the x87 state * @param pos the stack position to change the tos with */ -static void x87_fxch(x87_state *state, int pos) { - st_entry entry; - assert(pos < state->depth); - - entry = state->st[MASK_TOS(state->tos + pos)]; - state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)]; - state->st[MASK_TOS(state->tos)] = entry; - - DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state)); +static void x87_fxch(x87_state *state, int pos) +{ + st_entry *const a = x87_get_entry(state, pos); + st_entry *const b = x87_get_entry(state, 0); + st_entry const t = *a; + *a = *b; + *b = t; + + DB((dbg, LEVEL_2, "After FXCH: ")); + DEBUG_ONLY(x87_dump_stack(state);) } /** @@ -234,90 +240,92 @@ static void x87_fxch(x87_state *state, int pos) { * @return the stack position where the register is stacked * or -1 if the virtual register was not found */ -static int x87_on_stack(const x87_state *state, int reg_idx) { - int i, tos = state->tos; - - for (i = 0; i < state->depth; ++i) - if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx) +static int x87_on_stack(const x87_state *state, int reg_idx) +{ + for (int i = 0; i < state->depth; ++i) { + if (x87_get_st_reg(state, i) == reg_idx) return i; + } return -1; } /** - * Push a virtual Register onto the stack. + * Push a virtual Register onto the stack, double pushed allowed. * - * @param state the x87 state - * @param reg_idx the register vfp index - * @param node the node that produces the value of the vfp register + * @param state the x87 state + * @param reg_idx the register vfp index + * @param node the node that produces the value of the vfp register */ -static void x87_push(x87_state *state, int reg_idx, ir_node *node) { - assert(x87_on_stack(state, reg_idx) == -1 && "double push"); - assert(state->depth < N_x87_REGS && "stack overrun"); +static void x87_push_dbl(x87_state *state, int reg_idx, ir_node *node) +{ + assert(state->depth < N_ia32_st_REGS && "stack overrun"); ++state->depth; - state->tos = MASK_TOS(state->tos - 1); - state->st[state->tos].reg_idx = reg_idx; - state->st[state->tos].node = node; + st_entry *const entry = x87_get_entry(state, 0); + entry->reg_idx = reg_idx; + entry->node = node; - DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state)); + DB((dbg, LEVEL_2, "After PUSH: ")); DEBUG_ONLY(x87_dump_stack(state);) } /** - * Pop a virtual Register from the stack. + * Push a virtual Register onto the stack, double pushes are NOT allowed. + * + * @param state the x87 state + * @param reg_idx the register vfp index + * @param node the node that produces the value of the vfp register */ -static void x87_pop(x87_state *state) { - assert(state->depth > 0 && "stack underrun"); - - --state->depth; - state->tos = MASK_TOS(state->tos + 1); +static void x87_push(x87_state *state, int reg_idx, ir_node *node) +{ + assert(x87_on_stack(state, reg_idx) == -1 && "double push"); - DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state)); + x87_push_dbl(state, reg_idx, node); } /** - * Returns the block state of a block. - * - * @param sim the x87 simulator handle - * @param block the current block + * Pop a virtual Register from the stack. * - * @return the block state + * @param state the x87 state */ -static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) { - pmap_entry *entry = pmap_find(sim->blk_states, block); - - if (! entry) { - blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state)); - bl_state->begin = NULL; - bl_state->end = NULL; +static void x87_pop(x87_state *state) +{ + assert(state->depth > 0 && "stack underrun"); - pmap_insert(sim->blk_states, block, bl_state); - return bl_state; - } + --state->depth; - return entry ? PTR_TO_BLKSTATE(entry->value) : NULL; + DB((dbg, LEVEL_2, "After POP: ")); DEBUG_ONLY(x87_dump_stack(state);) } /** - * Creates a new x87 state. + * Empty the fpu stack * - * @param sim the x87 simulator handle - * @return a new x87 state + * @param state the x87 state */ -static x87_state *x87_alloc_state(x87_simulator *sim) { - x87_state *res = obstack_alloc(&sim->obst, sizeof(*res)); - return res; +static void x87_emms(x87_state *state) +{ + state->depth = 0; } /** - * Create a new empty x87 state. + * Returns the block state of a block. * * @param sim the x87 simulator handle - * @return a new empty x87 state + * @param block the current block + * + * @return the block state */ -static x87_state *x87_alloc_empty_state(x87_simulator *sim) { - x87_state *res = x87_alloc_state(sim); +static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) +{ + blk_state *res = pmap_get(blk_state, sim->blk_states, block); + + if (res == NULL) { + res = OALLOC(&sim->obst, blk_state); + res->begin = NULL; + res->end = NULL; + + pmap_insert(sim->blk_states, block, res); + } - x87_flush(res); return res; } @@ -329,21 +337,22 @@ static x87_state *x87_alloc_empty_state(x87_simulator *sim) { * * @return a cloned copy of the src state */ -static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) { - x87_state *res = x87_alloc_state(sim); - - memcpy(res, src, sizeof(*res)); +static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) +{ + x87_state *const res = OALLOC(&sim->obst, x87_state); + *res = *src; return res; } /** * Patch a virtual instruction into a x87 one and return - * the value node. + * the node representing the result value. * * @param n the IR node to patch * @param op the x87 opcode to patch in */ -static ir_node *x87_patch_insn(ir_node *n, ir_op *op) { +static ir_node *x87_patch_insn(ir_node *n, ir_op *op) +{ ir_mode *mode = get_irn_mode(n); ir_node *res = n; @@ -351,83 +360,94 @@ static ir_node *x87_patch_insn(ir_node *n, ir_op *op) { if (mode == mode_T) { /* patch all Proj's */ - const ir_edge_t *edge; - foreach_out_edge(n, edge) { ir_node *proj = get_edge_src_irn(edge); if (is_Proj(proj)) { mode = get_irn_mode(proj); if (mode_is_float(mode)) { res = proj; - set_irn_mode(proj, mode_E); + set_irn_mode(proj, ia32_reg_classes[CLASS_ia32_st].mode); } } } - } - else if (mode_is_float(mode)) - set_irn_mode(n, mode_E); + } else if (mode_is_float(mode)) + set_irn_mode(n, ia32_reg_classes[CLASS_ia32_st].mode); return res; } -/* -------------- x87 perm --------------- */ - /** - * Creates a fxch for shuffle. - * - * @param state the x87 state - * @param pos parameter for fxch - * @param dst_block the block of the user + * Returns the first Proj of a mode_T node having a given mode. * - * Creates a new fxch node and reroute the user of the old node - * to the fxch. - * - * @return the fxch node + * @param n the mode_T node + * @param m the desired mode of the Proj + * @return The first Proj of mode @p m found or NULL. */ -static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_node *dst_block) +static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m) { - const ir_edge_t *edge; - ir_node *n = x87_get_st_node(state, pos); - ir_node *user = NULL; - ir_node *fxch; - int node_idx; - ia32_attr_t *attr; - - if (block == get_nodes_block(n)) { - /* this is a node from out block: change it's user */ - foreach_out_edge(n, edge) { - ir_node *succ = get_edge_src_irn(edge); + assert(get_irn_mode(n) == mode_T && "Need mode_T node"); - if (is_Phi(succ) && get_nodes_block(succ) == dst_block) { - user = succ; - node_idx = get_edge_src_pos(edge); - break; - } - } - assert(user); + foreach_out_edge(n, edge) { + ir_node *proj = get_edge_src_irn(edge); + if (get_irn_mode(proj) == m) + return proj; } - fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, n, get_irn_mode(n)); - attr = get_ia32_attr(fxch); - attr->x87[0] = &ia32_st_regs[pos]; - attr->x87[2] = &ia32_st_regs[0]; + return NULL; +} - if (user) { - DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user)); - set_irn_n(user, node_idx, fxch); - } - else { - /* - * This is a node from a dominator block. Changing it's user might be wrong, - * so just keep it alive. - * The "right" solution would require a new Phi, but we don't care here. - */ - keep_alive(fxch); - } +/** + * Wrap the arch_* function here so we can check for errors. + */ +static inline const arch_register_t *x87_get_irn_register(const ir_node *irn) +{ + const arch_register_t *res = arch_get_irn_register(irn); + + assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]); + return res; +} + +static inline const arch_register_t *x87_irn_get_register(const ir_node *irn, + int pos) +{ + const arch_register_t *res = arch_get_irn_register_out(irn, pos); + + assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]); + return res; +} + +static inline const arch_register_t *get_st_reg(int index) +{ + return &ia32_registers[REG_ST0 + index]; +} +/** + * Create a fxch node before another node. + * + * @param state the x87 state + * @param n the node after the fxch + * @param pos exchange st(pos) with st(0) + * + * @return the fxch + */ +static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos) +{ x87_fxch(state, pos); + + ir_node *const block = get_nodes_block(n); + ir_node *const fxch = new_bd_ia32_fxch(NULL, block); + ia32_x87_attr_t *const attr = get_ia32_x87_attr(fxch); + attr->x87[0] = get_st_reg(pos); + attr->x87[2] = get_st_reg(0); + + keep_alive(fxch); + + sched_add_before(n, fxch); + DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name)); return fxch; } +/* -------------- x87 perm --------------- */ + /** * Calculate the necessary permutations to reach dst_state. * @@ -437,37 +457,33 @@ static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_n * Note that critical edges are removed here, so we need only * a shuffle if the current block has only one successor. * - * @param sim the simulator handle * @param block the current block * @param state the current x87 stack state, might be modified - * @param dst_block the destination block * @param dst_state destination state * * @return state */ -static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) { - int i, n_cycles, k, ri; +static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state) +{ + int i, n_cycles, k, ri; unsigned cycles[4], all_mask; - char cycle_idx[4][8]; - ir_node *fxch; - ir_node *before, *after; + char cycle_idx[4][8]; assert(state->depth == dst_state->depth); /* Some mathematics here: - If we have a cycle of lenght n that includes the tos, - we need n-1 exchange operations. - We can always add the tos and restore it, so we need - n+1 exchange operations for a cycle not containing the tos. - So, the maximum of needed operations is for a cycle of 7 - not including the tos == 8. - This is so same number of ops we would need for store, - so exchange is cheaper (we save the loads). - On the other hand, we might need an additional exchange - in the next block to bring one operand on top, so the - number of ops in the first case is identical. - Further, no more than 4 cycles can exists. - */ + * If we have a cycle of length n that includes the tos, + * we need n-1 exchange operations. + * We can always add the tos and restore it, so we need + * n+1 exchange operations for a cycle not containing the tos. + * So, the maximum of needed operations is for a cycle of 7 + * not including the tos == 8. + * This is the same number of ops we would need for using stores, + * so exchange is cheaper (we save the loads). + * On the other hand, we might need an additional exchange + * in the next block to bring one operand on top, so the + * number of ops in the first case is identical. + * Further, no more than 4 cycles can exists (4 x 2). */ all_mask = (1 << (state->depth)) - 1; for (n_cycles = 0; all_mask; ++n_cycles) { @@ -512,9 +528,9 @@ static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *sta /* Hmm: permutation needed */ DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block)); - DEBUG_ONLY(x87_dump_stack(state)); + DEBUG_ONLY(x87_dump_stack(state);) DB((dbg, LEVEL_2, " to\n")); - DEBUG_ONLY(x87_dump_stack(dst_state)); + DEBUG_ONLY(x87_dump_stack(dst_state);) #ifdef DEBUG_libfirm @@ -527,102 +543,52 @@ static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *sta } #endif - after = NULL; - /* * Find the place node must be insert. * We have only one successor block, so the last instruction should * be a jump. */ - before = sched_last(block); + ir_node *const before = sched_last(block); assert(is_cfop(before)); /* now do the permutations */ for (ri = 0; ri < n_cycles; ++ri) { if ((cycles[ri] & 1) == 0) { /* this cycle does not include the tos */ - fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block); - if (after) - sched_add_after(after, fxch); - else - sched_add_before(before, fxch); - after = fxch; + x87_create_fxch(state, before, cycle_idx[ri][0]); } for (k = 1; cycle_idx[ri][k] != -1; ++k) { - fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block, dst_block); - if (after) - sched_add_after(after, fxch); - else - sched_add_before(before, fxch); - after = fxch; + x87_create_fxch(state, before, cycle_idx[ri][k]); } if ((cycles[ri] & 1) == 0) { /* this cycle does not include the tos */ - fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block); - sched_add_after(after, fxch); + x87_create_fxch(state, before, cycle_idx[ri][0]); } } return state; } -/** - * Create a fxch node before another node. - * - * @param state the x87 state - * @param n the node before the fxch - * @param pos exchange st(pos) with st(0) - * @param op_idx if >= 0, replace input op_idx of n with the fxch result - * - * @return the fxch - */ -static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) { - ir_node *fxch, *pred; - ia32_attr_t *attr; - - x87_fxch(state, pos); - - if (op_idx >= 0) - pred = get_irn_n(n, op_idx); - else - pred = x87_get_st_node(state, pos); - - fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred)); - attr = get_ia32_attr(fxch); - attr->x87[0] = &ia32_st_regs[pos]; - attr->x87[2] = &ia32_st_regs[0]; - - if (op_idx >= 0) - set_irn_n(n, op_idx, fxch); - - sched_add_before(n, fxch); - DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name)); - return fxch; -} - /** * Create a fpush before node n. * - * @param state the x87 state - * @param n the node before the fpush - * @param pos push st(pos) on stack - * @param op_idx if >= 0, replace input op_idx of n with the fpush result + * @param state the x87 state + * @param n the node after the fpush + * @param pos push st(pos) on stack + * @param val the value to push */ -static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) { - ir_node *fpush, *pred; - ia32_attr_t *attr; - const arch_register_t *out = arch_get_irn_register(env, n); - - x87_push(state, arch_register_get_index(out), n); +static void x87_create_fpush(x87_state *state, ir_node *n, int pos, ir_node *const val) +{ + arch_register_t const *const out = x87_get_irn_register(val); + x87_push_dbl(state, arch_register_get_index(out), val); - pred = get_irn_n(n, op_idx); - fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred)); - attr = get_ia32_attr(fpush); - attr->x87[0] = &ia32_st_regs[pos]; - attr->x87[2] = &ia32_st_regs[0]; - if (op_idx >= 0) - set_irn_n(n, op_idx, fpush); + ir_node *const fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n)); + ia32_x87_attr_t *const attr = get_ia32_x87_attr(fpush); + attr->x87[0] = get_st_reg(pos); + attr->x87[2] = get_st_reg(0); + keep_alive(fpush); sched_add_before(n, fpush); + DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name)); } @@ -630,30 +596,32 @@ static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n * Create a fpop before node n. * * @param state the x87 state - * @param n the node before the fpop + * @param n the node after the fpop * @param num pop 1 or 2 values - * @param pred node to use as predecessor of the fpop * * @return the fpop node */ -static ir_node *x87_create_fpop(const arch_env_t *env, x87_state *state, ir_node *n, int num, ir_node *pred) { - ir_node *fpop; - ia32_attr_t *attr; +static ir_node *x87_create_fpop(x87_state *state, ir_node *n, int num) +{ + ir_node *fpop = NULL; + ia32_x87_attr_t *attr; - while (num > 0) { + assert(num > 0); + do { x87_pop(state); - fpop = new_rd_ia32_fpop(NULL, get_irn_irg(n), get_nodes_block(n), pred, mode_E); - attr = get_ia32_attr(fpop); - attr->x87[0] = &ia32_st_regs[0]; - attr->x87[1] = &ia32_st_regs[0]; - attr->x87[2] = &ia32_st_regs[0]; - + if (ia32_cg_config.use_ffreep) + fpop = new_bd_ia32_ffreep(NULL, get_nodes_block(n)); + else + fpop = new_bd_ia32_fpop(NULL, get_nodes_block(n)); + attr = get_ia32_x87_attr(fpop); + attr->x87[0] = get_st_reg(0); + attr->x87[1] = get_st_reg(0); + attr->x87[2] = get_st_reg(0); + + keep_alive(fpop); sched_add_before(n, fpop); DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name)); - - pred = fpop; - --num; - } + } while (--num > 0); return fpop; } @@ -663,84 +631,114 @@ static ir_node *x87_create_fpop(const arch_env_t *env, x87_state *state, ir_node * The liveness transfer function. * Updates a live set over a single step from a given node to its predecessor. * Everything defined at the node is removed from the set, the uses of the node get inserted. - * @param arch_env The architecture environment. + * * @param irn The node at which liveness should be computed. * @param live The bitset of registers live before @p irn. This set gets modified by updating it to * the registers live after irn. - * @return live. + * + * @return The live bitset. */ -static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live) +static vfp_liveness vfp_liveness_transfer(ir_node *irn, vfp_liveness live) { int i, n; const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp]; - if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) { - const arch_register_t *reg = arch_get_irn_register(arch_env, irn); - live &= ~(1 << reg->index); + if (get_irn_mode(irn) == mode_T) { + foreach_out_edge(irn, edge) { + ir_node *proj = get_edge_src_irn(edge); + + if (arch_irn_consider_in_reg_alloc(cls, proj)) { + const arch_register_t *reg = x87_get_irn_register(proj); + live &= ~(1 << arch_register_get_index(reg)); + } + } + } else if (arch_irn_consider_in_reg_alloc(cls, irn)) { + const arch_register_t *reg = x87_get_irn_register(irn); + live &= ~(1 << arch_register_get_index(reg)); } for (i = 0, n = get_irn_arity(irn); i < n; ++i) { ir_node *op = get_irn_n(irn, i); - if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) { - const arch_register_t *reg = arch_get_irn_register(arch_env, op); - live |= 1 << reg->index; + if (mode_is_float(get_irn_mode(op)) && + arch_irn_consider_in_reg_alloc(cls, op)) { + const arch_register_t *reg = x87_get_irn_register(op); + live |= 1 << arch_register_get_index(reg); } } - return live; } /** * Put all live virtual registers at the end of a block into a bitset. - * @param arch_env The architecture environment. - * @param bl The block. - * @return The live bitset. + * + * @param sim the simulator handle + * @param bl the block + * + * @return The live bitset at the end of this block */ -static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl) +static vfp_liveness vfp_liveness_end_of_block(x87_simulator *sim, const ir_node *block) { - irn_live_t *li; - unsigned live = 0; + vfp_liveness live = 0; const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp]; + const be_lv_t *lv = sim->lv; - live_foreach(bl, li) { - ir_node *irn = (ir_node *) li->irn; - if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) { - const arch_register_t *reg = arch_get_irn_register(arch_env, irn); - live |= 1 << reg->index; - } + be_lv_foreach(lv, block, be_lv_state_end, node) { + const arch_register_t *reg; + if (!arch_irn_consider_in_reg_alloc(cls, node)) + continue; + + reg = x87_get_irn_register(node); + live |= 1 << arch_register_get_index(reg); } return live; } +/** get the register mask from an arch_register */ +#define REGMASK(reg) (1 << (arch_register_get_index(reg))) + /** - * Compute a bitset of registers which are live at another node. - * @param arch_env The architecture environment. - * @param pos The node. + * Return a bitset of argument registers which are live at the end of a node. + * + * @param sim the simulator handle + * @param pos the node + * @param kill kill mask for the output registers + * * @return The live bitset. */ -static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos) +static unsigned vfp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill) { - const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos); - const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp]; - ir_node *irn; - unsigned live; + unsigned idx = get_irn_idx(pos); - live = vfp_liveness_end_of_block(arch_env, bl); + assert(idx < sim->n_idx); + return sim->live[idx] & ~kill; +} - sched_foreach_reverse(bl, irn) { - /* - * If we encounter the node we want to insert the Perm after, - * exit immediately, so that this node is still live - */ - if (irn == pos) - return live; +/** + * Calculate the liveness for a whole block and cache it. + * + * @param sim the simulator handle + * @param block the block + */ +static void update_liveness(x87_simulator *sim, ir_node *block) +{ + vfp_liveness live = vfp_liveness_end_of_block(sim, block); + unsigned idx; - live = vfp_liveness_transfer(arch_env, irn, live); - } + /* now iterate through the block backward and cache the results */ + sched_foreach_reverse(block, irn) { + /* stop at the first Phi: this produces the live-in */ + if (is_Phi(irn)) + break; - return live; + idx = get_irn_idx(irn); + sim->live[idx] = live; + + live = vfp_liveness_transfer(irn, live); + } + idx = get_irn_idx(block); + sim->live[idx] = live; } /** @@ -749,9 +747,7 @@ static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_ * @param reg_idx the vfp register index * @param live a live bitset */ -static unsigned is_vfp_live(int reg_idx, unsigned live) { - return live & (1 << reg_idx); -} +#define is_vfp_live(reg_idx, live) ((live) & (1 << (reg_idx))) #ifdef DEBUG_libfirm /** @@ -759,13 +755,14 @@ static unsigned is_vfp_live(int reg_idx, unsigned live) { * * @param live the live bitset */ -static void vfp_dump_live(unsigned live) { +static void vfp_dump_live(vfp_liveness live) +{ int i; - DB((dbg, LEVEL_2, "Live registers here: \n")); + DB((dbg, LEVEL_2, "Live after: ")); for (i = 0; i < 8; ++i) { if (live & (1 << i)) { - DB((dbg, LEVEL_2, " vf%d", i)); + DB((dbg, LEVEL_2, "vf%d ", i)); } } DB((dbg, LEVEL_2, "\n")); @@ -774,150 +771,178 @@ static void vfp_dump_live(unsigned live) { /* --------------------------------- simulators ---------------------------------------- */ -#define XCHG(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0) - /** * Simulate a virtual binop. * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment * @param tmpl the template containing the 4 possible x87 opcodes + * + * @return NO_NODE_ADDED */ -static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) { - int op2_idx, op1_idx = -1; - int out_idx, do_pop =0; - ia32_attr_t *attr; +static int sim_binop(x87_state *state, ir_node *n, const exchange_tmpl *tmpl) +{ + int op2_idx = 0, op1_idx; + int out_idx, do_pop = 0; + ia32_x87_attr_t *attr; + int permuted; + ir_node *patched_insn; ir_op *dst; - const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1)); - const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2)); - const arch_register_t *out = arch_get_irn_register(env, n); - unsigned live = vfp_liveness_nodes_live_at(env, n); - - DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n), - arch_register_get_name(op2), arch_register_get_name(op1), + x87_simulator *sim = state->sim; + ir_node *op1 = get_irn_n(n, n_ia32_binary_left); + ir_node *op2 = get_irn_n(n, n_ia32_binary_right); + const arch_register_t *op1_reg = x87_get_irn_register(op1); + const arch_register_t *op2_reg = x87_get_irn_register(op2); + const arch_register_t *out = x87_irn_get_register(n, pn_ia32_res); + int reg_index_1 = arch_register_get_index(op1_reg); + int reg_index_2 = arch_register_get_index(op2_reg); + vfp_liveness live = vfp_live_args_after(sim, n, REGMASK(out)); + int op1_live_after; + int op2_live_after; + + DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n, + arch_register_get_name(op1_reg), arch_register_get_name(op2_reg), arch_register_get_name(out))); - DEBUG_ONLY(vfp_dump_live(live)); + DEBUG_ONLY(vfp_dump_live(live);) + DB((dbg, LEVEL_1, "Stack before: ")); + DEBUG_ONLY(x87_dump_stack(state);) + + op1_idx = x87_on_stack(state, reg_index_1); + assert(op1_idx >= 0); + op1_live_after = is_vfp_live(reg_index_1, live); - op2_idx = x87_on_stack(state, arch_register_get_index(op2)); + attr = get_ia32_x87_attr(n); + permuted = attr->attr.data.ins_permuted; - if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) { - /* first operand is a vfp register */ - op1_idx = x87_on_stack(state, arch_register_get_index(op1)); + if (reg_index_2 != REG_VFP_VFP_NOREG) { + assert(!permuted); - if (is_vfp_live(op2->index, live)) { + /* second operand is a vfp register */ + op2_idx = x87_on_stack(state, reg_index_2); + assert(op2_idx >= 0); + op2_live_after = is_vfp_live(reg_index_2, live); + + if (op2_live_after) { /* Second operand is live. */ - if (is_vfp_live(op1->index, live)) { + if (op1_live_after) { /* Both operands are live: push the first one. This works even for op1 == op2. */ - x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2); - out_idx = op2_idx = 0; - ++op1_idx; + x87_create_fpush(state, n, op1_idx, op2); + /* now do fxxx (tos=tos X op) */ + op1_idx = 0; + op2_idx += 1; + out_idx = 0; dst = tmpl->normal_op; - do_pop = 0; - } - else { + } else { /* Second live, first operand is dead here, bring it to tos. */ if (op1_idx != 0) { - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); + x87_create_fxch(state, n, op1_idx); if (op2_idx == 0) op2_idx = op1_idx; + op1_idx = 0; } - op1_idx = out_idx = 0; + /* now do fxxx (tos=tos X op) */ + out_idx = 0; dst = tmpl->normal_op; - do_pop = 0; } - } - else { + } else { /* Second operand is dead. */ - if (is_vfp_live(op1->index, live)) { + if (op1_live_after) { /* First operand is live: bring second to tos. */ if (op2_idx != 0) { - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); + x87_create_fxch(state, n, op2_idx); if (op1_idx == 0) op1_idx = op2_idx; + op2_idx = 0; } - op2_idx = out_idx = 0; - dst = tmpl->normal_op; - do_pop = 0; - } - else { + /* now do fxxxr (tos = op X tos) */ + out_idx = 0; + dst = tmpl->reverse_op; + } else { /* Both operands are dead here, pop them from the stack. */ if (op2_idx == 0) { - out_idx = op1_idx; - XCHG(op2_idx, op1_idx); - if (op1_idx == op2_idx) { - /* Both are identically, no pop needed. */ - dst = tmpl->reverse_op; - do_pop = 0; - } - else { - dst = tmpl->reverse_pop_op; - do_pop = 1; - } - } - else if (op1_idx == 0) { - out_idx = op2_idx; - if (op1_idx == op2_idx) { - /* Both are identically, no pop needed. */ + if (op1_idx == 0) { + /* Both are identically and on tos, no pop needed. */ + /* here fxxx (tos = tos X tos) */ dst = tmpl->normal_op; - do_pop = 0; - } - else { + out_idx = 0; + } else { + /* now do fxxxp (op = op X tos, pop) */ dst = tmpl->normal_pop_op; do_pop = 1; + out_idx = op1_idx; } - } - else { - /* Bring the first on top. */ - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); + } else if (op1_idx == 0) { + assert(op1_idx != op2_idx); + /* now do fxxxrp (op = tos X op, pop) */ + dst = tmpl->reverse_pop_op; + do_pop = 1; + out_idx = op2_idx; + } else { + /* Bring the second on top. */ + x87_create_fxch(state, n, op2_idx); if (op1_idx == op2_idx) { - /* Both are identically, no pop needed. */ - out_idx = op1_idx = op2_idx = 0; - dst = tmpl->normal_op; - do_pop = 0; - } - else { + /* Both are identically and on tos now, no pop needed. */ op1_idx = 0; - out_idx = op2_idx; + op2_idx = 0; + /* use fxxx (tos = tos X tos) */ + dst = tmpl->normal_op; + out_idx = 0; + } else { + /* op2 is on tos now */ + op2_idx = 0; + /* use fxxxp (op = op X tos, pop) */ dst = tmpl->normal_pop_op; + out_idx = op1_idx; do_pop = 1; } } } } - } - else { - /* first operand is an address mode */ - if (is_vfp_live(op2->index, live)) { - /* second operand is live: push it here */ - x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2); - } - else { - /* second operand is dead: bring it to tos */ - if (op2_idx != 0) - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); + } else { + /* second operand is an address mode */ + if (op1_live_after) { + /* first operand is live: push it here */ + x87_create_fpush(state, n, op1_idx, op1); + op1_idx = 0; + } else { + /* first operand is dead: bring it to tos */ + if (op1_idx != 0) { + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; + } } - op2_idx = out_idx = 0; - dst = tmpl->normal_op; - do_pop = 0; + + /* use fxxx (tos = tos X mem) */ + dst = permuted ? tmpl->reverse_op : tmpl->normal_op; + out_idx = 0; } - x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx); - if (do_pop) + patched_insn = x87_patch_insn(n, dst); + x87_set_st(state, arch_register_get_index(out), patched_insn, out_idx); + if (do_pop) { x87_pop(state); + } /* patch the operation */ - attr = get_ia32_attr(n); - if (op1_idx >= 0) - attr->x87[0] = op1 = &ia32_st_regs[op1_idx]; - attr->x87[1] = op2 = &ia32_st_regs[op2_idx]; - attr->x87[2] = out = &ia32_st_regs[out_idx]; - - DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n), - arch_register_get_name(op2), arch_register_get_name(op1), - arch_register_get_name(out))); + attr->x87[0] = op1_reg = get_st_reg(op1_idx); + if (reg_index_2 != REG_VFP_VFP_NOREG) { + attr->x87[1] = op2_reg = get_st_reg(op2_idx); + } + attr->x87[2] = out = get_st_reg(out_idx); + + if (reg_index_2 != REG_VFP_VFP_NOREG) { + DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n), + arch_register_get_name(op1_reg), arch_register_get_name(op2_reg), + arch_register_get_name(out))); + } else { + DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n), + arch_register_get_name(op1_reg), + arch_register_get_name(out))); + } + + return NO_NODE_ADDED; } /** @@ -925,37 +950,37 @@ static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment * @param op the x87 opcode that will replace n's opcode + * + * @return NO_NODE_ADDED */ -static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) { - int op1_idx, out_idx; - const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX)); - const arch_register_t *out = arch_get_irn_register(env, n); - ia32_attr_t *attr; - unsigned live = vfp_liveness_nodes_live_at(env, n); - - DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name)); - DEBUG_ONLY(vfp_dump_live(live)); - - op1_idx = x87_on_stack(state, arch_register_get_index(op1)); - - if (is_vfp_live(op1->index, live)) { +static int sim_unop(x87_state *state, ir_node *n, ir_op *op) +{ + arch_register_t const *const out = x87_get_irn_register(n); + unsigned const live = vfp_live_args_after(state->sim, n, REGMASK(out)); + DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name)); + DEBUG_ONLY(vfp_dump_live(live);) + + ir_node *const op1 = get_irn_n(n, 0); + arch_register_t const *const op1_reg = x87_get_irn_register(op1); + int const op1_reg_idx = arch_register_get_index(op1_reg); + int const op1_idx = x87_on_stack(state, op1_reg_idx); + if (is_vfp_live(op1_reg_idx, live)) { /* push the operand here */ - x87_create_fpush(env, state, n, op1_idx, UNOP_IDX); - } - else { + x87_create_fpush(state, n, op1_idx, op1); + } else { /* operand is dead, bring it to tos */ - if (op1_idx != 0) - x87_create_fxch(state, n, op1_idx, UNOP_IDX); + if (op1_idx != 0) { + x87_create_fxch(state, n, op1_idx); + } } x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op)); - op1_idx = out_idx = 0; - attr = get_ia32_attr(n); - attr->x87[0] = op1 = &ia32_st_regs[0]; - attr->x87[2] = out = &ia32_st_regs[0]; - DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name)); + ia32_x87_attr_t *const attr = get_ia32_x87_attr(n); + attr->x87[2] = attr->x87[0] = get_st_reg(0); + DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), attr->x87[2]->name)); + + return NO_NODE_ADDED; } /** @@ -963,96 +988,172 @@ static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment * @param op the x87 opcode that will replace n's opcode + * + * @return NO_NODE_ADDED */ -static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) { - const arch_register_t *out = arch_get_irn_register(env, n); - ia32_attr_t *attr; +static int sim_load(x87_state *state, ir_node *n, ir_op *op, int res_pos) +{ + const arch_register_t *out = x87_irn_get_register(n, res_pos); + ia32_x87_attr_t *attr; - DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out))); + DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, arch_register_get_name(out))); x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op)); - attr = get_ia32_attr(n); - attr->x87[2] = out = &ia32_st_regs[0]; + assert(out == x87_irn_get_register(n, res_pos)); + attr = get_ia32_x87_attr(n); + attr->x87[2] = out = get_st_reg(0); DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out))); + + return NO_NODE_ADDED; } /** - * Simulate a virtual Store. + * Rewire all users of @p old_val to @new_val iff they are scheduled after @p store. + * + * @param store The store + * @param old_val The former value + * @param new_val The new value + */ +static void collect_and_rewire_users(ir_node *store, ir_node *old_val, ir_node *new_val) +{ + foreach_out_edge_safe(old_val, edge) { + ir_node *user = get_edge_src_irn(edge); + + if (! user || user == store) + continue; + + /* if the user is scheduled after the store: rewire */ + if (sched_is_scheduled(user) && sched_comes_after(store, user)) { + int i; + /* find the input of the user pointing to the old value */ + for (i = get_irn_arity(user) - 1; i >= 0; i--) { + if (get_irn_n(user, i) == old_val) + set_irn_n(user, i, new_val); + } + } + } +} + +/** + * Simulate a virtual Store. * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment * @param op the x87 store opcode * @param op_p the x87 store and pop opcode */ -static void sim_store(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op, ir_op *op_p) { - int op2_idx; - const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX)); - ia32_attr_t *attr; - unsigned live = vfp_liveness_nodes_live_at(env, n); - - op2_idx = x87_on_stack(state, arch_register_get_index(op2)); +static int sim_store(x87_state *state, ir_node *n, ir_op *op, ir_op *op_p) +{ + ir_node *const val = get_irn_n(n, n_ia32_vfst_val); + arch_register_t const *const op2 = x87_get_irn_register(val); + DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2))); + + int insn = NO_NODE_ADDED; + int const op2_reg_idx = arch_register_get_index(op2); + int const op2_idx = x87_on_stack(state, op2_reg_idx); + unsigned const live = vfp_live_args_after(state->sim, n, 0); + int const live_after_node = is_vfp_live(op2_reg_idx, live); assert(op2_idx >= 0); + if (live_after_node) { + /* Problem: fst doesn't support 80bit modes (spills), only fstp does + * fist doesn't support 64bit mode, only fistp + * Solution: + * - stack not full: push value and fstp + * - stack full: fstp value and load again + * Note that we cannot test on mode_E, because floats might be 80bit ... */ + ir_mode *const mode = get_ia32_ls_mode(n); + if (get_mode_size_bits(mode) > (mode_is_int(mode) ? 32 : 64)) { + if (x87_get_depth(state) < N_ia32_st_REGS) { + /* ok, we have a free register: push + fstp */ + x87_create_fpush(state, n, op2_idx, val); + x87_pop(state); + x87_patch_insn(n, op_p); + } else { + /* stack full here: need fstp + load */ + x87_pop(state); + x87_patch_insn(n, op_p); + + ir_node *const block = get_nodes_block(n); + ir_graph *const irg = get_irn_irg(n); + ir_node *const nomem = get_irg_no_mem(irg); + ir_node *const vfld = new_bd_ia32_vfld(NULL, block, get_irn_n(n, 0), get_irn_n(n, 1), nomem, mode); + + /* copy all attributes */ + set_ia32_frame_ent(vfld, get_ia32_frame_ent(n)); + if (is_ia32_use_frame(n)) + set_ia32_use_frame(vfld); + set_ia32_op_type(vfld, ia32_AddrModeS); + add_ia32_am_offs_int(vfld, get_ia32_am_offs_int(n)); + set_ia32_am_sc(vfld, get_ia32_am_sc(n)); + set_ia32_ls_mode(vfld, mode); + + ir_node *const rproj = new_r_Proj(vfld, mode, pn_ia32_vfld_res); + ir_node *const mproj = new_r_Proj(vfld, mode_M, pn_ia32_vfld_M); + ir_node *const mem = get_irn_Proj_for_mode(n, mode_M); + + assert(mem && "Store memory not found"); + + arch_set_irn_register(rproj, op2); + + /* reroute all former users of the store memory to the load memory */ + edges_reroute(mem, mproj); + /* set the memory input of the load to the store memory */ + set_irn_n(vfld, n_ia32_vfld_mem, mem); + + sched_add_after(n, vfld); + sched_add_after(vfld, rproj); + + /* rewire all users, scheduled after the store, to the loaded value */ + collect_and_rewire_users(n, val, rproj); + + insn = NODE_ADDED; + } + } else { + /* we can only store the tos to memory */ + if (op2_idx != 0) + x87_create_fxch(state, n, op2_idx); - DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2))); - - /* we can only store the tos to memory */ - if (op2_idx != 0) - x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX); + /* mode size 64 or smaller -> use normal fst */ + x87_patch_insn(n, op); + } + } else { + /* we can only store the tos to memory */ + if (op2_idx != 0) + x87_create_fxch(state, n, op2_idx); - if (is_vfp_live(op2->index, live)) - x87_patch_insn(n, op); - else { x87_pop(state); x87_patch_insn(n, op_p); } - attr = get_ia32_attr(n); - attr->x87[1] = op2 = &ia32_st_regs[0]; - DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2))); -} + ia32_x87_attr_t *const attr = get_ia32_x87_attr(n); + attr->x87[1] = get_st_reg(0); + DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(attr->x87[1]))); -/** - * Simulate a virtual Phi. - * Just for cosmetic reasons change the mode of Phi nodes to mode_E. - * - * @param state the x87 state - * @param n the node that should be simulated (and patched) - * @param env the architecture environment - */ -static void sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) { - ir_mode *mode = get_irn_mode(n); - - if (mode_is_float(mode)) - set_irn_mode(n, mode_E); + return insn; } - #define _GEN_BINOP(op, rev) \ -static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \ +static int sim_##op(x87_state *state, ir_node *n) { \ exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \ - sim_binop(state, n, env, &tmpl); \ + return sim_binop(state, n, &tmpl); \ } -#define GEN_BINOP(op) _GEN_BINOP(op, op) -#define GEN_BINOPR(op) _GEN_BINOP(op, op##r) +#define GEN_BINOP(op) _GEN_BINOP(op, op) +#define GEN_BINOPR(op) _GEN_BINOP(op, op##r) -#define GEN_LOAD2(op, nop) \ -static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \ - sim_load(state, n, env, op_ia32_##nop); \ +#define GEN_LOAD(op) \ +static int sim_##op(x87_state *state, ir_node *n) { \ + return sim_load(state, n, op_ia32_##op, pn_ia32_v##op##_res); \ } -#define GEN_LOAD(op) GEN_LOAD2(op, op) - #define GEN_UNOP(op) \ -static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \ - sim_unop(state, n, env, op_ia32_##op); \ +static int sim_##op(x87_state *state, ir_node *n) { \ + return sim_unop(state, n, op_ia32_##op); \ } #define GEN_STORE(op) \ -static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \ - sim_store(state, n, env, op_ia32_##op, op_ia32_##op##p); \ +static int sim_##op(x87_state *state, ir_node *n) { \ + return sim_store(state, n, op_ia32_##op, op_ia32_##op##p); \ } /* all stubs */ @@ -1060,106 +1161,204 @@ GEN_BINOP(fadd) GEN_BINOPR(fsub) GEN_BINOP(fmul) GEN_BINOPR(fdiv) +GEN_BINOP(fprem) GEN_UNOP(fabs) GEN_UNOP(fchs) -GEN_UNOP(fsin) -GEN_UNOP(fcos) -GEN_UNOP(fsqrt) GEN_LOAD(fld) GEN_LOAD(fild) GEN_LOAD(fldz) GEN_LOAD(fld1) -GEN_LOAD2(fConst, fldConst) GEN_STORE(fst) GEN_STORE(fist) /** - * Simulate a fCondJmp. + * Simulate a virtual fisttp. * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment + * + * @return NO_NODE_ADDED */ -static void sim_fCondJmp(x87_state *state, ir_node *n, const arch_env_t *env) { - int op2_idx, op1_idx = -1, pop_cnt = 0; - ia32_attr_t *attr; - ir_op *dst; - const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1)); - const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2)); - unsigned live = vfp_liveness_nodes_live_at(env, n); +static int sim_fisttp(x87_state *state, ir_node *n) +{ + ir_node *val = get_irn_n(n, n_ia32_vfst_val); + const arch_register_t *op2 = x87_get_irn_register(val); + ia32_x87_attr_t *attr; + int op2_reg_idx, op2_idx; + + op2_reg_idx = arch_register_get_index(op2); + op2_idx = x87_on_stack(state, op2_reg_idx); + DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2))); + assert(op2_idx >= 0); + + /* Note: although the value is still live here, it is destroyed because + of the pop. The register allocator is aware of that and introduced a copy + if the value must be alive. */ + + /* we can only store the tos to memory */ + if (op2_idx != 0) + x87_create_fxch(state, n, op2_idx); + + x87_pop(state); + x87_patch_insn(n, op_ia32_fisttp); + + attr = get_ia32_x87_attr(n); + attr->x87[1] = op2 = get_st_reg(0); + DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2))); + + return NO_NODE_ADDED; +} + +/** + * Simulate a virtual FtstFnstsw. + * + * @param state the x87 state + * @param n the node that should be simulated (and patched) + * + * @return NO_NODE_ADDED + */ +static int sim_FtstFnstsw(x87_state *state, ir_node *n) +{ + x87_simulator *sim = state->sim; + ia32_x87_attr_t *attr = get_ia32_x87_attr(n); + ir_node *op1_node = get_irn_n(n, n_ia32_vFtstFnstsw_left); + const arch_register_t *reg1 = x87_get_irn_register(op1_node); + int reg_index_1 = arch_register_get_index(reg1); + int op1_idx = x87_on_stack(state, reg_index_1); + unsigned live = vfp_live_args_after(sim, n, 0); + + DB((dbg, LEVEL_1, ">>> %+F %s\n", n, arch_register_get_name(reg1))); + DEBUG_ONLY(vfp_dump_live(live);) + DB((dbg, LEVEL_1, "Stack before: ")); + DEBUG_ONLY(x87_dump_stack(state);) + assert(op1_idx >= 0); + + if (op1_idx != 0) { + /* bring the value to tos */ + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; + } - DB((dbg, LEVEL_1, ">>> %s %s, %s\n", get_irn_opname(n), - arch_register_get_name(op2), arch_register_get_name(op1))); - DEBUG_ONLY(vfp_dump_live(live)); + /* patch the operation */ + x87_patch_insn(n, op_ia32_FtstFnstsw); + reg1 = get_st_reg(op1_idx); + attr->x87[0] = reg1; + attr->x87[1] = NULL; + attr->x87[2] = NULL; - op2_idx = x87_on_stack(state, arch_register_get_index(op2)); + if (!is_vfp_live(reg_index_1, live)) + x87_create_fpop(state, sched_next(n), 1); + + return NO_NODE_ADDED; +} + +/** + * Simulate a Fucom + * + * @param state the x87 state + * @param n the node that should be simulated (and patched) + * + * @return NO_NODE_ADDED + */ +static int sim_Fucom(x87_state *state, ir_node *n) +{ + int op1_idx; + int op2_idx = -1; + ia32_x87_attr_t *attr = get_ia32_x87_attr(n); + ir_op *dst; + x87_simulator *sim = state->sim; + ir_node *op1_node = get_irn_n(n, n_ia32_vFucomFnstsw_left); + ir_node *op2_node = get_irn_n(n, n_ia32_vFucomFnstsw_right); + const arch_register_t *op1 = x87_get_irn_register(op1_node); + const arch_register_t *op2 = x87_get_irn_register(op2_node); + int reg_index_1 = arch_register_get_index(op1); + int reg_index_2 = arch_register_get_index(op2); + unsigned live = vfp_live_args_after(sim, n, 0); + bool permuted = attr->attr.data.ins_permuted; + bool xchg = false; + int pops = 0; + + DB((dbg, LEVEL_1, ">>> %+F %s, %s\n", n, + arch_register_get_name(op1), arch_register_get_name(op2))); + DEBUG_ONLY(vfp_dump_live(live);) + DB((dbg, LEVEL_1, "Stack before: ")); + DEBUG_ONLY(x87_dump_stack(state);) + + op1_idx = x87_on_stack(state, reg_index_1); + assert(op1_idx >= 0); /* BEWARE: check for comp a,a cases, they might happen */ - if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) { - /* first operand is a vfp register */ - op1_idx = x87_on_stack(state, arch_register_get_index(op1)); + if (reg_index_2 != REG_VFP_VFP_NOREG) { + /* second operand is a vfp register */ + op2_idx = x87_on_stack(state, reg_index_2); + assert(op2_idx >= 0); - if (is_vfp_live(op2->index, live)) { + if (is_vfp_live(reg_index_2, live)) { /* second operand is live */ - if (is_vfp_live(op1->index, live)) { - /* both operands are live: move one of them to tos */ - if (op2_idx == 0) { - XCHG(op2_idx, op1_idx); - dst = op_ia32_fcomrJmp; - } - else if (op1_idx == 0) { - dst = op_ia32_fcomJmp; - } - else { - /* bring the first on top */ - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); - if (op1_idx == op2_idx) + if (is_vfp_live(reg_index_1, live)) { + /* both operands are live */ + + if (op1_idx == 0) { + /* res = tos X op */ + } else if (op2_idx == 0) { + /* res = op X tos */ + permuted = !permuted; + xchg = true; + } else { + /* bring the first one to tos */ + x87_create_fxch(state, n, op1_idx); + if (op1_idx == op2_idx) { op2_idx = 0; + } else if (op2_idx == 0) { + op2_idx = op1_idx; + } op1_idx = 0; - dst = op_ia32_fcomJmp; + /* res = tos X op */ } - } - else { + } else { /* second live, first operand is dead here, bring it to tos. This means further, op1_idx != op2_idx. */ + assert(op1_idx != op2_idx); if (op1_idx != 0) { - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); + x87_create_fxch(state, n, op1_idx); if (op2_idx == 0) op2_idx = op1_idx; + op1_idx = 0; } - op1_idx = 0; - dst = op_ia32_fcompJmp; - pop_cnt = 1; + /* res = tos X op, pop */ + pops = 1; } - } - else { + } else { /* second operand is dead */ - if (is_vfp_live(op1->index, live)) { + if (is_vfp_live(reg_index_1, live)) { /* first operand is live: bring second to tos. This means further, op1_idx != op2_idx. */ + assert(op1_idx != op2_idx); if (op2_idx != 0) { - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); + x87_create_fxch(state, n, op2_idx); if (op1_idx == 0) op1_idx = op2_idx; + op2_idx = 0; } - op2_idx = 0; - dst = op_ia32_fcomrpJmp; - pop_cnt = 1; - } - else { + /* res = op X tos, pop */ + pops = 1; + permuted = !permuted; + xchg = true; + } else { /* both operands are dead here, check first for identity. */ if (op1_idx == op2_idx) { - /* identically, one one needed */ + /* identically, one pop needed */ if (op1_idx != 0) { - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); - op1_idx = op2_idx = 0; + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; + op2_idx = 0; } - dst = op_ia32_fcompJmp; - pop_cnt = 1; + /* res = tos X op, pop */ + pops = 1; } /* different, move them to st and st(1) and pop both. The tricky part is to get one into st(1).*/ @@ -1167,271 +1366,516 @@ static void sim_fCondJmp(x87_state *state, ir_node *n, const arch_env_t *env) { /* good, second operand is already in the right place, move the first */ if (op1_idx != 0) { /* bring the first on top */ - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); + x87_create_fxch(state, n, op1_idx); + assert(op2_idx != 0); op1_idx = 0; } - dst = op_ia32_fcomppJmp; - pop_cnt = 2; - } - else if (op1_idx == 1) { + /* res = tos X op, pop, pop */ + pops = 2; + } else if (op1_idx == 1) { /* good, first operand is already in the right place, move the second */ if (op2_idx != 0) { /* bring the first on top */ - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); + x87_create_fxch(state, n, op2_idx); + assert(op1_idx != 0); op2_idx = 0; } - dst = op_ia32_fcomrppJmp; - pop_cnt = 2; - } - else { + /* res = op X tos, pop, pop */ + permuted = !permuted; + xchg = true; + pops = 2; + } else { /* if one is already the TOS, we need two fxch */ if (op1_idx == 0) { /* first one is TOS, move to st(1) */ - x87_create_fxch(state, n, 1, BINOP_IDX_1); + x87_create_fxch(state, n, 1); + assert(op2_idx != 1); op1_idx = 1; - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); + x87_create_fxch(state, n, op2_idx); op2_idx = 0; - dst = op_ia32_fcomrppJmp; - pop_cnt = 2; - } - else if (op2_idx == 0) { + /* res = op X tos, pop, pop */ + pops = 2; + permuted = !permuted; + xchg = true; + } else if (op2_idx == 0) { /* second one is TOS, move to st(1) */ - x87_create_fxch(state, n, 1, BINOP_IDX_2); + x87_create_fxch(state, n, 1); + assert(op1_idx != 1); op2_idx = 1; - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); + x87_create_fxch(state, n, op1_idx); op1_idx = 0; - dst = op_ia32_fcomrppJmp; - pop_cnt = 2; - } - else { + /* res = tos X op, pop, pop */ + pops = 2; + } else { /* none of them is either TOS or st(1), 3 fxch needed */ - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); - x87_create_fxch(state, n, 1, BINOP_IDX_2); - x87_create_fxch(state, n, op1_idx, BINOP_IDX_1); - op1_idx = 0; + x87_create_fxch(state, n, op2_idx); + assert(op1_idx != 0); + x87_create_fxch(state, n, 1); op2_idx = 1; - dst = op_ia32_fcomppJmp; - pop_cnt = 2; + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; + /* res = tos X op, pop, pop */ + pops = 2; } } } } - } - else { - /* first operand is an address mode */ - if (is_vfp_live(op2->index, live)) { - /* second operand is live: bring it to TOS */ - if (op2_idx != 0) { - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); - op2_idx = 0; + } else { + /* second operand is an address mode */ + if (is_vfp_live(reg_index_1, live)) { + /* first operand is live: bring it to TOS */ + if (op1_idx != 0) { + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; } - dst = op_ia32_fcomrJmp; - } - else { - /* second operand is dead: bring it to tos */ - if (op2_idx != 0) { - x87_create_fxch(state, n, op2_idx, BINOP_IDX_2); - op2_idx = 0; + } else { + /* first operand is dead: bring it to tos */ + if (op1_idx != 0) { + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; } + pops = 1; } - dst = op_ia32_fcomrpJmp; - pop_cnt = 1; + } + + /* patch the operation */ + if (is_ia32_vFucomFnstsw(n)) { + int i; + + switch (pops) { + case 0: dst = op_ia32_FucomFnstsw; break; + case 1: dst = op_ia32_FucompFnstsw; break; + case 2: dst = op_ia32_FucomppFnstsw; break; + default: panic("invalid popcount"); + } + + for (i = 0; i < pops; ++i) { + x87_pop(state); + } + } else if (is_ia32_vFucomi(n)) { + switch (pops) { + case 0: dst = op_ia32_Fucomi; break; + case 1: dst = op_ia32_Fucompi; x87_pop(state); break; + case 2: + dst = op_ia32_Fucompi; + x87_pop(state); + x87_create_fpop(state, sched_next(n), 1); + break; + default: panic("invalid popcount"); + } + } else { + panic("invalid operation %+F", n); } x87_patch_insn(n, dst); - if (pop_cnt > 1) - x87_pop(state); - if (pop_cnt > 0) - x87_pop(state); + if (xchg) { + int tmp = op1_idx; + op1_idx = op2_idx; + op2_idx = tmp; + } - /* patch the operation */ - attr = get_ia32_attr(n); - if (op1_idx >= 0) - attr->x87[0] = op1 = &ia32_st_regs[op1_idx]; - attr->x87[1] = op2 = &ia32_st_regs[op2_idx]; + op1 = get_st_reg(op1_idx); + attr->x87[0] = op1; + if (op2_idx >= 0) { + op2 = get_st_reg(op2_idx); + attr->x87[1] = op2; + } + attr->x87[2] = NULL; + attr->attr.data.ins_permuted = permuted; + + if (op2_idx >= 0) { + DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n), + arch_register_get_name(op1), arch_register_get_name(op2))); + } else { + DB((dbg, LEVEL_1, "<<< %s %s, [AM]\n", get_irn_opname(n), + arch_register_get_name(op1))); + } - DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n), - arch_register_get_name(op2), arch_register_get_name(op1))); + return NO_NODE_ADDED; } /** - * Simulate a be_Copy. + * Simulate a Keep. * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment + * + * @return NO_NODE_ADDED + */ +static int sim_Keep(x87_state *state, ir_node *node) +{ + const ir_node *op; + const arch_register_t *op_reg; + int reg_id; + int op_stack_idx; + unsigned live; + int i, arity; + + DB((dbg, LEVEL_1, ">>> %+F\n", node)); + + arity = get_irn_arity(node); + for (i = 0; i < arity; ++i) { + op = get_irn_n(node, i); + op_reg = arch_get_irn_register(op); + if (arch_register_get_class(op_reg) != &ia32_reg_classes[CLASS_ia32_vfp]) + continue; + + reg_id = arch_register_get_index(op_reg); + live = vfp_live_args_after(state->sim, node, 0); + + op_stack_idx = x87_on_stack(state, reg_id); + if (op_stack_idx >= 0 && !is_vfp_live(reg_id, live)) + x87_create_fpop(state, sched_next(node), 1); + } + + DB((dbg, LEVEL_1, "Stack after: ")); + DEBUG_ONLY(x87_dump_stack(state);) + + return NO_NODE_ADDED; +} + +/** + * Keep the given node alive by adding a be_Keep. + * + * @param node the node to kept alive + */ +static void keep_float_node_alive(ir_node *node) +{ + ir_node *block = get_nodes_block(node); + ir_node *keep = be_new_Keep(block, 1, &node); + + assert(sched_is_scheduled(node)); + sched_add_after(node, keep); +} + +/** + * Create a copy of a node. Recreate the node if it's a constant. + * + * @param state the x87 state + * @param n the node to be copied + * + * @return the copy of n */ -static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) { +static ir_node *create_Copy(x87_state *state, ir_node *n) +{ + dbg_info *n_dbg = get_irn_dbg_info(n); ir_mode *mode = get_irn_mode(n); + ir_node *block = get_nodes_block(n); + ir_node *pred = get_irn_n(n, 0); + ir_node *(*cnstr)(dbg_info *, ir_node *, ir_mode *) = NULL; + ir_node *res; + const arch_register_t *out; + const arch_register_t *op1; + ia32_x87_attr_t *attr; + + /* Do not copy constants, recreate them. */ + switch (get_ia32_irn_opcode(pred)) { + case iro_ia32_fldz: + cnstr = new_bd_ia32_fldz; + break; + case iro_ia32_fld1: + cnstr = new_bd_ia32_fld1; + break; + case iro_ia32_fldpi: + cnstr = new_bd_ia32_fldpi; + break; + case iro_ia32_fldl2e: + cnstr = new_bd_ia32_fldl2e; + break; + case iro_ia32_fldl2t: + cnstr = new_bd_ia32_fldl2t; + break; + case iro_ia32_fldlg2: + cnstr = new_bd_ia32_fldlg2; + break; + case iro_ia32_fldln2: + cnstr = new_bd_ia32_fldln2; + break; + default: + break; + } - if (mode_is_float(mode)) { - const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0)); - const arch_register_t *out = arch_get_irn_register(env, n); - ir_node *node, *next; - ia32_attr_t *attr; - int op1_idx, out_idx; - unsigned live = vfp_liveness_nodes_live_at(env, n); + out = x87_get_irn_register(n); + op1 = x87_get_irn_register(pred); - op1_idx = x87_on_stack(state, arch_register_get_index(op1)); + if (cnstr != NULL) { + /* copy a constant */ + res = (*cnstr)(n_dbg, block, mode); - DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n), - arch_register_get_name(op1), arch_register_get_name(out))); - DEBUG_ONLY(vfp_dump_live(live)); + x87_push(state, arch_register_get_index(out), res); - if (is_vfp_live(op1->index, live)) { - /* operand is still live,a real copy */ - node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode); - arch_set_irn_register(env, node, out); + attr = get_ia32_x87_attr(res); + attr->x87[2] = get_st_reg(0); + } else { + int op1_idx = x87_on_stack(state, arch_register_get_index(op1)); - x87_push(state, arch_register_get_index(out), node); + res = new_bd_ia32_fpushCopy(n_dbg, block, pred, mode); - attr = get_ia32_attr(node); - attr->x87[0] = op1 = &ia32_st_regs[op1_idx]; - attr->x87[2] = out = &ia32_st_regs[0]; + x87_push(state, arch_register_get_index(out), res); - next = sched_next(n); - sched_remove(n); - exchange(n, node); - sched_add_before(next, node); - DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name)); + attr = get_ia32_x87_attr(res); + attr->x87[0] = get_st_reg(op1_idx); + attr->x87[2] = get_st_reg(0); + } + arch_set_irn_register(res, out); + + return res; +} + +/** + * Simulate a be_Copy. + * + * @param state the x87 state + * @param n the node that should be simulated (and patched) + * + * @return NO_NODE_ADDED + */ +static int sim_Copy(x87_state *state, ir_node *n) +{ + arch_register_class_t const *const cls = arch_get_irn_reg_class(n); + if (cls != &ia32_reg_classes[CLASS_ia32_vfp]) + return NO_NODE_ADDED; + + ir_node *const pred = be_get_Copy_op(n); + arch_register_t const *const op1 = x87_get_irn_register(pred); + arch_register_t const *const out = x87_get_irn_register(n); + unsigned const live = vfp_live_args_after(state->sim, n, REGMASK(out)); + + DB((dbg, LEVEL_1, ">>> %+F %s -> %s\n", n, + arch_register_get_name(op1), arch_register_get_name(out))); + DEBUG_ONLY(vfp_dump_live(live);) + + if (is_vfp_live(arch_register_get_index(op1), live)) { + /* Operand is still live, a real copy. We need here an fpush that can + hold a a register, so use the fpushCopy or recreate constants */ + ir_node *const node = create_Copy(state, n); + + /* We have to make sure the old value doesn't go dead (which can happen + * when we recreate constants). As the simulator expected that value in + * the pred blocks. This is unfortunate as removing it would save us 1 + * instruction, but we would have to rerun all the simulation to get + * this correct... + */ + ir_node *const next = sched_next(n); + sched_remove(n); + exchange(n, node); + sched_add_before(next, node); + + if (get_irn_n_edges(pred) == 0) { + keep_float_node_alive(pred); } - else { - out_idx = x87_on_stack(state, arch_register_get_index(out)); - - if (out_idx >= 0 && out_idx != op1_idx) { - /* op1 must be killed and placed where out is */ - if (out_idx == 0) { - /* best case, simple remove and rename */ - x87_patch_insn(n, op_ia32_Pop); - attr = get_ia32_attr(n); - attr->x87[0] = op1 = &ia32_st_regs[0]; - - x87_pop(state); - x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1); - } - else { - /* move op1 to tos, store and pop it */ - if (op1_idx != 0) { - x87_create_fxch(state, n, op1_idx, 0); - op1_idx = 0; - } - x87_patch_insn(n, op_ia32_Pop); - attr = get_ia32_attr(n); - attr->x87[0] = op1 = &ia32_st_regs[out_idx]; - x87_pop(state); - x87_set_st(state, arch_register_get_index(out), n, out_idx - 1); + DB((dbg, LEVEL_1, "<<< %+F %s -> ?\n", node, op1->name)); + } else { + int const op1_idx = x87_on_stack(state, arch_register_get_index(op1)); + int const out_idx = x87_on_stack(state, arch_register_get_index(out)); + if (out_idx >= 0 && out_idx != op1_idx) { + /* Matze: out already on stack? how can this happen? */ + panic("invalid stack state"); + +#if 0 + /* op1 must be killed and placed where out is */ + if (out_idx == 0) { + ia32_x87_attr_t *attr; + /* best case, simple remove and rename */ + x87_patch_insn(n, op_ia32_Pop); + attr = get_ia32_x87_attr(n); + attr->x87[0] = op1 = get_st_reg(0); + + x87_pop(state); + x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1); + } else { + ia32_x87_attr_t *attr; + /* move op1 to tos, store and pop it */ + if (op1_idx != 0) { + x87_create_fxch(state, n, op1_idx); + op1_idx = 0; } - DB((dbg, LEVEL_1, ">>> %s %s\n", get_irn_opname(n), op1->name)); - } - else { - /* just a virtual copy */ - x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx); - sched_remove(n); - DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n))); - exchange(n, get_unop_op(n)); + x87_patch_insn(n, op_ia32_Pop); + attr = get_ia32_x87_attr(n); + attr->x87[0] = op1 = get_st_reg(out_idx); + + x87_pop(state); + x87_set_st(state, arch_register_get_index(out), n, out_idx - 1); } + DB((dbg, LEVEL_1, "<<< %+F %s\n", n, op1->name)); +#endif + } else { + /* just a virtual copy */ + x87_set_st(state, arch_register_get_index(out), pred, op1_idx); + /* don't remove the node to keep the verifier quiet :), + the emitter won't emit any code for the node */ +#if 0 + sched_remove(n); + DB((dbg, LEVEL_1, "<<< KILLED %s\n", get_irn_opname(n))); + exchange(n, pred); +#endif } } + return NO_NODE_ADDED; } /** - * Simulate a be_Call. + * Returns the vf0 result Proj of a Call. * - * @param state the x87 state - * @param n the node that should be simulated - * @param env the architecture environment + * @para call the Call node */ -static void sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) { - ir_type *call_tp = be_Call_get_type(n); +static ir_node *get_call_result_proj(ir_node *call) +{ + /* search the result proj */ + foreach_out_edge(call, edge) { + ir_node *proj = get_edge_src_irn(edge); + long pn = get_Proj_proj(proj); - /* at the begin of a call the x87 state should be empty */ - assert(state->depth == 0 && "stack not empty before call"); + if (pn == pn_ia32_Call_vf0) + return proj; + } - /* - * If the called function returns a float, it is returned in st(0). - * This even happens if the return value is NOT used. - * Moreover, only one return result is supported. - */ - if (get_method_n_ress(call_tp) > 0) { - ir_type *res_type = get_method_res_type(call_tp, 0); - ir_mode *mode = get_type_mode(res_type); + panic("result Proj missing"); +} - if (mode && mode_is_float(mode)) { - /* - * TODO: what to push here? The result might be unused and currently - * we have no possibility to detect this :-( - */ - x87_push(state, 0, n); - } +static int sim_Asm(x87_state *const state, ir_node *const n) +{ + (void)state; + + for (size_t i = get_irn_arity(n); i-- != 0;) { + arch_register_req_t const *const req = arch_get_irn_register_req_in(n, i); + if (req->cls == &ia32_reg_classes[CLASS_ia32_vfp]) + panic("cannot handle %+F with x87 constraints", n); } + + for (size_t i = arch_get_irn_n_outs(n); i-- != 0;) { + arch_register_req_t const *const req = arch_get_irn_register_req_out(n, i); + if (req->cls == &ia32_reg_classes[CLASS_ia32_vfp]) + panic("cannot handle %+F with x87 constraints", n); + } + + return NO_NODE_ADDED; } /** - * Simulate a be_Spill. + * Simulate a ia32_Call. * - * @param state the x87 state - * @param n the node that should be simulated (and patched) - * @param env the architecture environment + * @param state the x87 state + * @param n the node that should be simulated (and patched) * - * Should not happen, spills are lowered before x87 simulator see them. + * @return NO_NODE_ADDED */ -static void sim_Spill(x87_state *state, ir_node *n, const arch_env_t *env) { - assert(0 && "Spill not lowered"); - sim_fst(state, n, env); +static int sim_Call(x87_state *state, ir_node *n) +{ + DB((dbg, LEVEL_1, ">>> %+F\n", n)); + + /* at the begin of a call the x87 state should be empty */ + assert(state->depth == 0 && "stack not empty before call"); + + ir_type *const call_tp = get_ia32_call_attr_const(n)->call_tp; + if (get_method_n_ress(call_tp) != 0) { + /* If the called function returns a float, it is returned in st(0). + * This even happens if the return value is NOT used. + * Moreover, only one return result is supported. */ + ir_type *const res_type = get_method_res_type(call_tp, 0); + ir_mode *const mode = get_type_mode(res_type); + if (mode && mode_is_float(mode)) { + ir_node *const resproj = get_call_result_proj(n); + arch_register_t const *const reg = x87_get_irn_register(resproj); + x87_push(state, arch_register_get_index(reg), resproj); + } + } + DB((dbg, LEVEL_1, "Stack after: ")); + DEBUG_ONLY(x87_dump_stack(state);) + + return NO_NODE_ADDED; } /** - * Simulate a be_Reload. + * Simulate a be_Return. * * @param state the x87 state * @param n the node that should be simulated (and patched) - * @param env the architecture environment * - * Should not happen, reloads are lowered before x87 simulator see them. + * @return NO_NODE_ADDED */ -static void sim_Reload(x87_state *state, ir_node *n, const arch_env_t *env) { - assert(0 && "Reload not lowered"); - sim_fld(state, n, env); +static int sim_Return(x87_state *state, ir_node *n) +{ +#ifdef DEBUG_libfirm + /* only floating point return values must reside on stack */ + int n_float_res = 0; + int const n_res = be_Return_get_n_rets(n); + for (int i = 0; i < n_res; ++i) { + ir_node *const res = get_irn_n(n, n_be_Return_val + i); + if (mode_is_float(get_irn_mode(res))) + ++n_float_res; + } + assert(x87_get_depth(state) == n_float_res); +#endif + + /* pop them virtually */ + x87_emms(state); + return NO_NODE_ADDED; } /** - * Simulate a be_Return. + * Simulate a be_Perm. * * @param state the x87 state - * @param n the node that should be simulated (and patched) - * @param env the architecture environment + * @param irn the node that should be simulated (and patched) + * + * @return NO_NODE_ADDED */ -static void sim_Return(x87_state *state, ir_node *n, const arch_env_t *env) { - int n_res = be_Return_get_n_rets(n); - int i, n_float_res = 0; +static int sim_Perm(x87_state *state, ir_node *irn) +{ + int i, n; + ir_node *pred = get_irn_n(irn, 0); + int *stack_pos; - /* only floating point return values must resist on stack */ - for (i = 0; i < n_res; ++i) { - ir_node *res = get_irn_n(n, be_pos_Return_val + i); + /* handle only floating point Perms */ + if (! mode_is_float(get_irn_mode(pred))) + return NO_NODE_ADDED; - if (mode_is_float(get_irn_mode(res))) - ++n_float_res; + DB((dbg, LEVEL_1, ">>> %+F\n", irn)); + + /* Perm is a pure virtual instruction on x87. + All inputs must be on the FPU stack and are pairwise + different from each other. + So, all we need to do is to permutate the stack state. */ + n = get_irn_arity(irn); + NEW_ARR_A(int, stack_pos, n); + + /* collect old stack positions */ + for (i = 0; i < n; ++i) { + const arch_register_t *inreg = x87_get_irn_register(get_irn_n(irn, i)); + int idx = x87_on_stack(state, arch_register_get_index(inreg)); + + assert(idx >= 0 && "Perm argument not on x87 stack"); + + stack_pos[i] = idx; } - assert(x87_get_depth(state) == n_float_res); + /* now do the permutation */ + foreach_out_edge(irn, edge) { + ir_node *proj = get_edge_src_irn(edge); + const arch_register_t *out = x87_get_irn_register(proj); + long num = get_Proj_proj(proj); + + assert(0 <= num && num < n && "More Proj's than Perm inputs"); + x87_set_st(state, arch_register_get_index(out), proj, stack_pos[(unsigned)num]); + } + DB((dbg, LEVEL_1, "<<< %+F\n", irn)); - /* pop them virtually */ - for (i = n_float_res - 1; i >= 0; --i) - x87_pop(state); + return NO_NODE_ADDED; } /** * Kill any dead registers at block start by popping them from the stack. * - * @param sim the simulator handle - * @param block the current block - * @param start_state the x87 state at the begin of the block + * @param sim the simulator handle + * @param block the current block + * @param state the x87 state at the begin of the block */ -static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) { - x87_state *state = start_state; +static void x87_kill_deads(x87_simulator *const sim, ir_node *const block, x87_state *const state) +{ ir_node *first_insn = sched_first(block); ir_node *keep = NULL; - unsigned live = vfp_liveness_nodes_live_at(sim->env, block); + unsigned live = vfp_live_args_after(sim, block, 0); unsigned kill_mask; int i, depth, num_pop; @@ -1445,13 +1889,26 @@ static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state * } if (kill_mask) { - /* create a new state, will be changed */ - state = x87_clone_state(sim, state); - DB((dbg, LEVEL_1, "Killing deads:\n")); - DEBUG_ONLY(vfp_dump_live(live)); - DEBUG_ONLY(x87_dump_stack(state)); - + DEBUG_ONLY(vfp_dump_live(live);) + DEBUG_ONLY(x87_dump_stack(state);) + + if (kill_mask != 0 && live == 0) { + /* special case: kill all registers */ + if (ia32_cg_config.use_femms || ia32_cg_config.use_emms) { + if (ia32_cg_config.use_femms) { + /* use FEMMS on AMD processors to clear all */ + keep = new_bd_ia32_femms(NULL, block); + } else { + /* use EMMS to clear all */ + keep = new_bd_ia32_emms(NULL, block); + } + sched_add_before(first_insn, keep); + keep_alive(keep); + x87_emms(state); + return; + } + } /* now kill registers */ while (kill_mask) { /* we can only kill from TOS, so bring them up */ @@ -1467,10 +1924,8 @@ static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state * if (keep) x87_set_st(state, -1, keep, i); - keep = x87_create_fxch(state, first_insn, i, -1); + x87_create_fxch(state, first_insn, i); } - else if (! keep) - keep = x87_get_st_node(state, 0); if ((kill_mask & 3) == 3) { /* we can do a double-pop */ @@ -1483,11 +1938,10 @@ static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state * depth -= num_pop; kill_mask >>= num_pop; - keep = x87_create_fpop(sim->env, state, first_insn, num_pop, keep); + keep = x87_create_fpop(state, first_insn, num_pop); } - add_End_keepalive(get_irg_end(get_irn_irg(block)), keep); + keep_alive(keep); } - return state; } /** @@ -1495,130 +1949,144 @@ static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state * * * @param sim the simulator handle * @param block the current block - * - * @return non-zero if simulation is complete, - * zero if the simulation must be rerun */ -static int x87_simulate_block(x87_simulator *sim, ir_node *block) { +static void x87_simulate_block(x87_simulator *sim, ir_node *block) +{ ir_node *n, *next; blk_state *bl_state = x87_get_bl_state(sim, block); x87_state *state = bl_state->begin; - const ir_edge_t *edge; ir_node *start_block; - /* if we have no assigned start state, we must wait ... */ - if (! state) - return 0; - - assert(bl_state->end == NULL); + assert(state != NULL); + /* already processed? */ + if (bl_state->end != NULL) + return; DB((dbg, LEVEL_1, "Simulate %+F\n", block)); + DB((dbg, LEVEL_2, "State at Block begin:\n ")); + DEBUG_ONLY(x87_dump_stack(state);) + /* create a new state, will be changed */ + state = x87_clone_state(sim, state); /* at block begin, kill all dead registers */ - state = x87_kill_deads(sim, block, state); + x87_kill_deads(sim, block, state); - /* beware, n might changed */ + /* beware, n might change */ for (n = sched_first(block); !sched_is_end(n); n = next) { + int node_inserted; + sim_func func; ir_op *op = get_irn_op(n); + /* + * get the next node to be simulated here. + * n might be completely removed from the schedule- + */ next = sched_next(n); - if (op->ops.generic) { - sim_func func = (sim_func)op->ops.generic; - - /* have work to do */ - if (state == bl_state->begin) { - /* create a new state, will be changed */ - state = x87_clone_state(sim, state); - } + if (op->ops.generic != NULL) { + func = (sim_func)op->ops.generic; /* simulate it */ - (*func)(state, n, sim->env); + node_inserted = (*func)(state, n); + + /* + * sim_func might have added an additional node after n, + * so update next node + * beware: n must not be changed by sim_func + * (i.e. removed from schedule) in this case + */ + if (node_inserted != NO_NODE_ADDED) + next = sched_next(n); } } start_block = get_irg_start_block(get_irn_irg(block)); + DB((dbg, LEVEL_2, "State at Block end:\n ")); DEBUG_ONLY(x87_dump_stack(state);) + /* check if the state must be shuffled */ foreach_block_succ(block, edge) { ir_node *succ = get_edge_src_irn(edge); - blk_state *succ_state = x87_get_bl_state(sim, succ); + blk_state *succ_state; - if (succ_state->begin && succ != start_block) { - /* There is already a begin state for this block, bad. - Do the necessary permutations. - Note that critical edges are removed, so this is always possible. */ - x87_shuffle(sim, block, state, succ, succ_state->begin); - - /* Note further, that there can be only one such situation, - so we can break here. */ - break; - } - } - bl_state->end = state; + if (succ == start_block) + continue; - /* now propagate the state to all successor blocks */ - foreach_block_succ(block, edge) { - ir_node *succ = get_edge_src_irn(edge); - blk_state *succ_state = x87_get_bl_state(sim, succ); + succ_state = x87_get_bl_state(sim, succ); - if (! succ_state->begin) + if (succ_state->begin == NULL) { + DB((dbg, LEVEL_2, "Set begin state for succ %+F:\n", succ)); + DEBUG_ONLY(x87_dump_stack(state);) succ_state->begin = state; + + waitq_put(sim->worklist, succ); + } else { + DB((dbg, LEVEL_2, "succ %+F already has a state, shuffling\n", succ)); + /* There is already a begin state for the successor, bad. + Do the necessary permutations. + Note that critical edges are removed, so this is always possible: + If the successor has more than one possible input, then it must + be the only one. + */ + x87_shuffle(block, state, succ_state->begin); + } } + bl_state->end = state; +} - return 1; +/** + * Register a simulator function. + * + * @param op the opcode to simulate + * @param func the simulator function for the opcode + */ +static void register_sim(ir_op *op, sim_func func) +{ + assert(op->ops.generic == NULL); + op->ops.generic = (op_func) func; } /** * Create a new x87 simulator. * - * @param sim a simulator handle, will be initialized - * @param irg the current graph - * @param env the architecture environment + * @param sim a simulator handle, will be initialized + * @param irg the current graph */ -static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) { +static void x87_init_simulator(x87_simulator *sim, ir_graph *irg) +{ obstack_init(&sim->obst); sim->blk_states = pmap_create(); - sim->env = env; - - FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87"); - firm_dbg_set_mask(dbg, SET_LEVEL_2); + sim->n_idx = get_irg_last_idx(irg); + sim->live = OALLOCN(&sim->obst, vfp_liveness, sim->n_idx); DB((dbg, LEVEL_1, "--------------------------------\n" "x87 Simulator started for %+F\n", irg)); - /* set the generic function pointer of instruction we must simulate */ - clear_irp_opcodes_generic_func(); - -#define ASSOC(op) (op_ ## op)->ops.generic = (op_func)(sim_##op) -#define ASSOC_IA32(op) (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op) -#define ASSOC_BE(op) (op_be_ ## op)->ops.generic = (op_func)(sim_##op) - ASSOC_IA32(fConst); - ASSOC_IA32(fld); - ASSOC_IA32(fild); - ASSOC_IA32(fld1); - ASSOC_IA32(fldz); - ASSOC_IA32(fadd); - ASSOC_IA32(fsub); - ASSOC_IA32(fmul); - ASSOC_IA32(fdiv); - ASSOC_IA32(fldz); - ASSOC_IA32(fabs); - ASSOC_IA32(fchs); - ASSOC_IA32(fsin); - ASSOC_IA32(fcos); - ASSOC_IA32(fsqrt); - ASSOC_IA32(fist); - ASSOC_IA32(fst); - ASSOC_IA32(fCondJmp); - ASSOC_BE(Copy); - ASSOC_BE(Call); - ASSOC_BE(Spill); - ASSOC_BE(Reload); - ASSOC_BE(Return); - ASSOC(Phi); -#undef ASSOC_BE -#undef ASSOC_IA32 -#undef ASSOC + /* set the generic function pointer of instruction we must simulate */ + ir_clear_opcodes_generic_func(); + + register_sim(op_ia32_Asm, sim_Asm); + register_sim(op_ia32_Call, sim_Call); + register_sim(op_ia32_vfld, sim_fld); + register_sim(op_ia32_vfild, sim_fild); + register_sim(op_ia32_vfld1, sim_fld1); + register_sim(op_ia32_vfldz, sim_fldz); + register_sim(op_ia32_vfadd, sim_fadd); + register_sim(op_ia32_vfsub, sim_fsub); + register_sim(op_ia32_vfmul, sim_fmul); + register_sim(op_ia32_vfdiv, sim_fdiv); + register_sim(op_ia32_vfprem, sim_fprem); + register_sim(op_ia32_vfabs, sim_fabs); + register_sim(op_ia32_vfchs, sim_fchs); + register_sim(op_ia32_vfist, sim_fist); + register_sim(op_ia32_vfisttp, sim_fisttp); + register_sim(op_ia32_vfst, sim_fst); + register_sim(op_ia32_vFtstFnstsw, sim_FtstFnstsw); + register_sim(op_ia32_vFucomFnstsw, sim_Fucom); + register_sim(op_ia32_vFucomi, sim_Fucom); + register_sim(op_be_Copy, sim_Copy); + register_sim(op_be_Return, sim_Return); + register_sim(op_be_Perm, sim_Perm); + register_sim(op_be_Keep, sim_Keep); } /** @@ -1626,55 +2094,73 @@ static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env * * @param sim the simulator handle */ -static void x87_destroy_simulator(x87_simulator *sim) { +static void x87_destroy_simulator(x87_simulator *sim) +{ pmap_destroy(sim->blk_states); obstack_free(&sim->obst, NULL); DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n")); } /** + * Pre-block walker: calculate the liveness information for the block + * and store it into the sim->live cache. + */ +static void update_liveness_walker(ir_node *block, void *data) +{ + x87_simulator *sim = (x87_simulator*)data; + update_liveness(sim, block); +} + +/* * Run a simulation and fix all virtual instructions for a graph. - * - * @param env the architecture environment - * @param irg the current graph - * @param blk_list the block schedule list - * - * Needs a block-schedule. + * Replaces all virtual floating point instructions and registers + * by real ones. */ -void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) { - ir_node *block, *start_block; - pdeq *worklist; - blk_state *bl_state; - x87_simulator sim; - int i; +void ia32_x87_simulate_graph(ir_graph *irg) +{ + /* TODO improve code quality (less executed fxch) by using execfreqs */ - /* we need liveness info for the current graph */ - be_liveness(irg); + ir_node *block, *start_block; + blk_state *bl_state; + x87_simulator sim; /* create the simulator */ - x87_init_simulator(&sim, irg, env); + x87_init_simulator(&sim, irg); start_block = get_irg_start_block(irg); - bl_state = x87_get_bl_state(&sim, start_block); + bl_state = x87_get_bl_state(&sim, start_block); /* start with the empty state */ - bl_state->begin = empty; + empty.sim = ∼ + bl_state->begin = ∅ - worklist = new_pdeq(); + sim.worklist = new_waitq(); + waitq_put(sim.worklist, start_block); - /* create the worklist for the schedule. */ - for (i = 0; i < ARR_LEN(blk_list); ++i) - pdeq_putr(worklist, blk_list[i]); + be_assure_live_sets(irg); + sim.lv = be_get_irg_liveness(irg); + + /* Calculate the liveness for all nodes. We must precalculate this info, + * because the simulator adds new nodes (possible before Phi nodes) which + * would let a lazy calculation fail. + * On the other hand we reduce the computation amount due to + * precaching from O(n^2) to O(n) at the expense of O(n) cache memory. + */ + irg_block_walk_graph(irg, update_liveness_walker, NULL, &sim); /* iterate */ do { - block = pdeq_getl(worklist); - if (! x87_simulate_block(&sim, block)) { - pdeq_putr(worklist, block); - continue; - } - } while (! pdeq_empty(worklist)); + block = (ir_node*)waitq_get(sim.worklist); + x87_simulate_block(&sim, block); + } while (! waitq_empty(sim.worklist)); /* kill it */ + del_waitq(sim.worklist); x87_destroy_simulator(&sim); } + +/* Initializes the x87 simulator. */ +void ia32_init_x87(void) +{ + FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87"); +}