<commit_before>/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief       This file implements the x87 support and virtual to stack
 *              register translation for the ia32 backend.
 * @author      <NAME>
 */
#include <assert.h>

#include "beirg.h"
#include "irnode_t.h"
#include "irop_t.h"
#include "irprog.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "ircons.h"
#include "irgwalk.h"
#include "irtools.h"
#include "obst.h"
#include "pmap.h"
#include "array.h"
#include "pdeq.h"
#include "debug.h"
#include "panic.h"

#include "belive.h"
#include "besched.h"
#include "benode.h"
#include "bessaconstr.h"
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
#include "ia32_architecture.h"

#define N_FLOAT_REGS  (N_ia32_fp_REGS-1)  // exclude NOREG

/** the debug handle */
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

/* Forward declaration. */
typedef struct x87_simulator x87_simulator;

/**
 * An entry on the simulated x87 stack.
 */
typedef struct st_entry {
	unsigned 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_FLOAT_REGS]; /**< the register stack */
	unsigned       depth;            /**< the current stack depth */
	x87_simulator *sim;              /**< The simulator. */
} x87_state;

/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
 */
typedef void (*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 {
	x87_state const *begin; /**< state at the begin or NULL if not assigned */
	x87_state const *end;   /**< state at the end or NULL if not assigned */
} blk_state;

/** liveness bitset for fp registers. */
typedef unsigned char fp_liveness;

/**
 * The 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. */
	fp_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 current stack depth.
 *
 * @param state  the x87 state
 * @return the x87 stack depth
 */
static unsigned x87_get_depth(const x87_state *state)
{
	return state->depth;
}

static st_entry *x87_get_entry(x87_state *const state, unsigned const pos)
{
	assert(pos < state->depth);
	return &state->st[N_FLOAT_REGS - state->depth + pos];
}

/**
 * Return the node at st(pos).
 *
 * @param state  the x87 state
 * @param pos    a stack position
 * @return the node that produced the value at st(pos)
 */
static ir_node *x87_get_st_node(x87_state const *const state, unsigned const pos)
{
	return x87_get_entry((x87_state*)state, pos)->node;
}

/**
 * Return the virtual register index at st(pos).
 *
 * @param state  the x87 state
 * @param pos    a stack position
 * @return the fp register index that produced the value at st(pos)
 */
static unsigned x87_get_st_reg(const x87_state *state, unsigned pos)
{
	return x87_get_entry((x87_state*)state, pos)->reg_idx;
}

#ifdef DEBUG_libfirm
/**
 * Dump the stack for debugging.
 *
 * @param state  the x87 state
 */
static void x87_dump_stack(const x87_state *state)
{
	for (unsigned 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"));
}
#endif /* DEBUG_libfirm */

/**
 * Set a node to st(pos).
 *
 * @param state    the x87 state
 * @param node     the IR node that produces the value of the fp register
 * @param pos      the stack position where the new value should be entered
 */
static void x87_set_st(x87_state *const state, ir_node *const node, unsigned const pos)
{
	st_entry *const entry = x87_get_entry(state, pos);
	entry->reg_idx = arch_get_irn_register(node)->index;
	entry->node    = node;

	DB((dbg, LEVEL_2, "After SET_REG: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * 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, unsigned 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);)
}

/**
 * Convert a node to the stack index.
 *
 * @param state    the x87 state
 * @param node     the node to find
 * @return the stack position where the node is stacked
 *         or -1 if the node was not found
 */
static unsigned x87_on_stack(x87_state const *const state, ir_node const *const node)
{
	unsigned const reg_idx = arch_get_irn_register(node)->index;
	for (unsigned i = 0; i < state->depth; ++i) {
		if (x87_get_st_reg(state, i) == reg_idx)
			return i;
	}
	return (unsigned)-1;
}

static unsigned is_at_pos(x87_state const *const state, ir_node const *const val, unsigned const pos)
{
	arch_register_t const *const reg = arch_get_irn_register(val);
	return x87_get_st_reg(state, pos) == reg->index;
}

/**
 * Push a node onto the stack, double pushes are NOT allowed.
 *
 * @param state     the x87 state
 * @param node      the node that produces the value of the fp register
 */
static void x87_push(x87_state *const state, ir_node *const node)
{
	assert(x87_on_stack(state, node) == (unsigned)-1 && "double push");
	assert(state->depth < N_FLOAT_REGS && "stack overrun");

	++state->depth;
	st_entry *const entry = x87_get_entry(state, 0);
	entry->reg_idx = arch_get_irn_register(node)->index;
	entry->node    = node;

	DB((dbg, LEVEL_2, "After PUSH: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * Pop a virtual Register from the stack.
 *
 * @param state     the x87 state
 */
static void x87_pop(x87_state *state)
{
	assert(state->depth > 0 && "stack underrun");
	--state->depth;
	DB((dbg, LEVEL_2, "After POP: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
static void x87_emms(x87_state *state)
{
	state->depth = 0;
}

/**
 * Returns the block state of a block.
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 * @return the block state
 */
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);
	}
	return res;
}

/**
 * Clone a x87 state.
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 * @return a cloned copy of the src state
 */
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;
}

static inline const arch_register_t *get_st_reg(unsigned 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)
 */
static void x87_create_fxch(x87_state *state, ir_node *n, unsigned 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->reg = get_st_reg(pos);

	keep_alive(fxch);

	sched_add_before(n, fxch);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fxch), attr->reg->name));
}

static void move_to_pos(x87_state *const state, ir_node *const before, ir_node *const val, unsigned const to)
{
	unsigned const from = x87_on_stack(state, val);
	assert(from != (unsigned)-1);
	if (from != to) {
		if (from != 0)
			x87_create_fxch(state, before, from);
		if (to != 0)
			x87_create_fxch(state, before, to);
	}
}

static void move_to_tos(x87_state *const state, ir_node *const before, ir_node *const val)
{
	move_to_pos(state, before, val, 0);
}

/* -------------- x87 perm --------------- */

/**
 * Calculate the necessary permutations to reach dst_state.
 *
 * These permutations are done with fxch instructions and placed
 * at the end of the block.
 *
 * Note that critical edges are removed here, so we need only
 * a shuffle if the current block has only one successor.
 *
 * @param block      the current block
 * @param state      the current x87 stack state, might be modified
 * @param dst_state  destination state
 * @return state
 */
static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state)
{
	assert(state->depth == dst_state->depth);

	/* Some mathematics here:
	 * 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). */
	unsigned all_mask = (1 << (state->depth)) - 1;

	unsigned      cycles[4];
	unsigned char cycle_idx[4][8];
	unsigned      n_cycles;
	for (n_cycles = 0; all_mask != 0; ++n_cycles) {
		/* find the first free slot */
		unsigned i;
		for (i = 0; i < state->depth; ++i) {
			if (all_mask & (1 << i)) {
				all_mask &= ~(1 << i);

				/* check if there are differences here */
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
					break;
			}
		}

		if (all_mask == 0) {
			/* no more cycles found */
			break;
		}

		unsigned k = 0;
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
		for (unsigned src_idx = i, dst_idx; ; src_idx = dst_idx) {
			dst_idx = x87_on_stack(dst_state, x87_get_st_node(state, src_idx));

			if ((all_mask & (1 << dst_idx)) == 0)
				break;

			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
			all_mask       &= ~(1 << dst_idx);
		}
		cycle_idx[n_cycles][k] = (unsigned char)-1;
	}

	if (n_cycles == 0) {
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
	DEBUG_ONLY(x87_dump_stack(state);)
	DB((dbg, LEVEL_2, "                  to\n"));
	DEBUG_ONLY(x87_dump_stack(dst_state);)

#ifdef DEBUG_libfirm
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
		for (unsigned k = 0; cycle_idx[ri][k] != (unsigned char)-1; ++k)
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

	/* Find the place node must be insert.
	 * We have only one successor block, so the last instruction should
	 * be a jump. */
	ir_node *const before = sched_last(block);
	assert(is_cfop(before));

	/* now do the permutations */
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0)
			x87_create_fxch(state, before, cycle_idx[ri][0]);
		for (unsigned k = 1; cycle_idx[ri][k] != (unsigned char)-1; ++k) {
			x87_create_fxch(state, before, cycle_idx[ri][k]);
		}
		if ((cycles[ri] & 1) == 0)
			x87_create_fxch(state, before, cycle_idx[ri][0]);
	}
	return state;
}

static ir_node *x87_create_fdup(x87_state *const state, ir_node *const block, ir_node *const val, arch_register_t const *const out)
{
	ir_node         *const fdup = new_bd_ia32_fdup(NULL, block, val);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fdup);
	unsigned         const pos  = x87_on_stack(state, val);
	attr->reg = get_st_reg(pos);
	arch_set_irn_register(fdup, out);
	x87_push(state, fdup);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fdup), attr->reg->name));
	return fdup;
}

/**
 * Create an fdup before node @p n replacing operand @p op_n.
 *
 * @param state     the x87 state
 * @param n         the node after the fdup
 * @param val       the value to duplicate
 */
static ir_node *x87_dup_operand(x87_state *const state, ir_node *const n, unsigned const op_n, ir_node *const val, arch_register_t const *const out)
{
	ir_node *const block = get_nodes_block(n);
	ir_node *const fdup  = x87_create_fdup(state, block, val, out);
	sched_add_before(n, fdup);
	set_irn_n(n, op_n, fdup);
	return fdup;
}

/**
 * Create a fpop before node n.
 * This overwrites st(pos) with st(0) and pops st(0).
 *
 * @param state   the x87 state
 * @param n       the node after which to schedule the fpop
 * @param pos     the index of the entry to remove the register stack
 * @return the fpop node
 */
static ir_node *x87_create_fpop(x87_state *const state, ir_node *const n,
                                unsigned const pos)
{
	if (pos != 0) {
		st_entry *const dst = x87_get_entry(state, pos);
		st_entry *const src = x87_get_entry(state, 0);
		*dst = *src;
	}
	x87_pop(state);
	ir_node *const block = get_block(n);
	ir_node *const fpop  = pos == 0 && ia32_cg_config.use_ffreep ?
		new_bd_ia32_ffreep(NULL, block) :
		new_bd_ia32_fpop(  NULL, block);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fpop);
	attr->reg = get_st_reg(pos);

	keep_alive(fpop);
	sched_add_after(n, fpop);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->reg->name));
	return fpop;
}

/* --------------------------------- liveness ------------------------------------------ */

/**
 * 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 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 The live bitset.
 */
static fp_liveness fp_liveness_transfer(ir_node *irn, fp_liveness live)
{
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_fp];
	be_foreach_definition(irn, cls, def, req,
		const arch_register_t *reg = arch_get_irn_register(def);
		live &= ~(1 << reg->index);
	);
	be_foreach_use(irn, cls, in_req_, op, op_req_,
		const arch_register_t *reg = arch_get_irn_register(op);
		live |= 1 << reg->index;
	);
	return live;
}

/**
 * Put all live virtual registers at the end of a block into a bitset.
 *
 * @param sim      the simulator handle
 * @param bl       the block
 * @return The live bitset at the end of this block
 */
static fp_liveness fp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
{
	fp_liveness                  live = 0;
	const arch_register_class_t *cls  = &ia32_reg_classes[CLASS_ia32_fp];
	const be_lv_t               *lv   = sim->lv;

	be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
		const arch_register_t *reg = arch_get_irn_register(node);
		live |= 1 << reg->index;
	}

	return live;
}

/** get the register mask from an arch_register */
#define REGMASK(reg)    (1 << (reg->index))

/**
 * 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 fp_liveness fp_live_args_after(x87_simulator *sim, const ir_node *pos,
                                      fp_liveness kill)
{
	unsigned idx = get_irn_idx(pos);
	assert(idx < sim->n_idx);
	return sim->live[idx] & ~kill;
}

/**
 * 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)
{
	fp_liveness live = fp_liveness_end_of_block(sim, block);
	/* 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;

		unsigned idx = get_irn_idx(irn);
		sim->live[idx] = live;

		live = fp_liveness_transfer(irn, live);
	}
	unsigned idx = get_irn_idx(block);
	sim->live[idx] = live;
}

/**
 * Returns true if node is live in the set.
 *
 * @param node  the node to check
 * @param live  a live bitset
 */
static inline bool is_fp_live(ir_node const *const node, fp_liveness const live)
{
	unsigned const reg_idx = arch_get_irn_register(node)->index;
	return live & (1 << reg_idx);
}

#ifdef DEBUG_libfirm
/**
 * Dump liveness info.
 *
 * @param live  the live bitset
 */
static void fp_dump_live(fp_liveness live)
{
	DB((dbg, LEVEL_2, "Live after: "));
	for (unsigned i = 0; i < N_FLOAT_REGS; ++i) {
		if (live & (1 << i)) {
			DB((dbg, LEVEL_2, "vf%d ", i));
		}
	}
	DB((dbg, LEVEL_2, "\n"));
}
#endif /* DEBUG_libfirm */

/* --------------------------------- simulators ---------------------------------------- */

static ir_node *get_result_node(ir_node *const n)
{
	return get_irn_mode(n) != mode_T ? n : get_Proj_for_pn(n, pn_ia32_res);
}

/**
 * Simulate a virtual binop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_binop(x87_state *const state, ir_node *const n)
{
	ir_node                     *op1            = get_irn_n(n, n_ia32_binary_left);
	ir_node               *const op2            = get_irn_n(n, n_ia32_binary_right);
	arch_register_t const *const out            = arch_get_irn_register_out(n, pn_ia32_res);
	fp_liveness            const live           = fp_live_args_after(state->sim, n, REGMASK(out));
	bool                   const op1_live_after = is_fp_live(op1, live);

	DB((dbg, LEVEL_1, ">>> %+F %+F, %+F -> %s\n", n, op1, op2, out->name));
	DEBUG_ONLY(fp_dump_live(live);)
	DB((dbg, LEVEL_1, "Stack before: "));
	DEBUG_ONLY(x87_dump_stack(state);)

	if (is_ia32_NoReg_FP(op2)) {
		/* Second operand is an address mode. */
		if (op1_live_after) {
			/* First operand is live: Duplicate it. */
			x87_dup_operand(state, n, n_ia32_binary_left, op1, out);
		} else {
			/* First operand is dead: Move it to tos. */
			move_to_tos(state, n, op1);
		}
		x87_set_st(state, get_result_node(n), 0);
	} else {
		bool       reverse;
		bool       to_reg;
		bool       pop            = false;
		bool const op2_live_after = is_fp_live(op2, live);
		if (op1_live_after) {
			if (op2_live_after) {
				/* Both operands are live: push the first one.
				 * This works even for op1 == op2. */
				op1     = x87_dup_operand(state, n, n_ia32_binary_left, op1, out);
				reverse = false;
				to_reg  = false;
			} else {
				/* First live, second dead: Overwrite second. */
				if (is_at_pos(state, op1, 0)) {
					reverse = false;
					to_reg  = true;
				} else {
					move_to_tos(state, n, op2);
					reverse = true;
					to_reg  = false;
				}
			}
		} else {
			if (op2_live_after) {
				/* First dead, Second live: Overwrite first. */
				if (is_at_pos(state, op2, 0)) {
					reverse = true;
					to_reg  = true;
				} else {
					move_to_tos(state, n, op1);
					reverse = false;
					to_reg  = false;
				}
			} else {
				/* Both dead. */
				if (op1 == op2) {
					/* Operands are identical: No pop. */
					move_to_tos(state, n, op1);
					reverse = false;
					to_reg  = false;
				} else {
					/* Bring one operand to tos. Heuristically swap the operand not at
					 * st(1) to tos. This way, if any operand was at st(1), the result
					 * will end up in the new st(0) after the implicit pop. If the next
					 * operation uses the result, then no fxch will be necessary. */
					if (is_at_pos(state, op1, 0)) {
						reverse = false;
					} else if (is_at_pos(state, op2, 0)) {
						reverse = true;
					} else if (is_at_pos(state, op1, 1)) {
						move_to_tos(state, n, op2);
						reverse = true;
					} else {
						move_to_tos(state, n, op1);
						reverse = false;
					}
					to_reg = true;
					pop    = true;
				}
			}
		}

		unsigned const op_reg = x87_on_stack(state, reverse ? op1 : op2);
		/* Patch the operation. */
		ia32_x87_attr_t *const attr = get_ia32_x87_attr(n);
		attr->reg               = get_st_reg(op_reg);
		attr->attr.ins_permuted = reverse;
		attr->res_in_reg        = to_reg;
		attr->pop               = pop;

		x87_set_st(state, get_result_node(n), to_reg ? op_reg : 0);
		if (pop)
			x87_pop(state);
	}

	DEBUG_ONLY(
		ia32_x87_attr_t const *const attr = get_ia32_x87_attr(n);
		char            const *const st0  = get_st_reg(0)->name;
		char            const *const reg  =  attr->reg ? attr->reg->name : "[AM]";
		char            const *const l    =  attr->attr.ins_permuted ? reg : st0;
		char            const *const r    = !attr->attr.ins_permuted ? reg : st0;
		char            const *const o    =  attr->res_in_reg        ? reg : st0;
		char            const *const pop  =  attr->pop ? " [pop]" : "";
		DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s%s\n", get_irn_opname(n), l, r, o, pop));
	)
}

/**
 * Simulate a virtual Unop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_unop(x87_state *state, ir_node *n)
{
	arch_register_t const *const out  = arch_get_irn_register(n);
	fp_liveness            const live = fp_live_args_after(state->sim, n, REGMASK(out));
	DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
	DEBUG_ONLY(fp_dump_live(live);)

	ir_node *const val = get_irn_n(n, 0);
	if (is_fp_live(val, live)) {
		/* push the operand here */
		x87_dup_operand(state, n, 0, val, out);
	} else {
		/* operand is dead, bring it to tos */
		move_to_tos(state, n, val);
	}

	x87_set_st(state, n, 0);
	DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), get_st_reg(0)->name));
}

/**
 * Simulate a virtual Load instruction.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_load(x87_state *state, ir_node *n)
{
	assert((unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fild_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fld1_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fldz_res);

	DB((dbg, LEVEL_1, ">>> %+F\n", n));
	x87_push(state, get_result_node(n));
	DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), get_st_reg(0)->name));
}

/**
 * Simulate a virtual Store.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_store(x87_state *state, ir_node *n)
{
	ir_node *const val = get_irn_n(n, n_ia32_fst_val);
	DB((dbg, LEVEL_1, ">>> %+F %+F ->\n", n, val));

	fp_liveness const live = fp_live_args_after(state->sim, n, 0);
	if (!is_fp_live(val, live)) {
		/* we can only store the tos to memory */
		move_to_tos(state, n, val);
		goto do_pop;
	} else {
		/* 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 */
		ir_mode *const mode = get_ia32_ls_mode(n);
		if (get_mode_size_bits(mode) > (mode_is_int(mode) ? 32U : 64U)) {
			if (x87_get_depth(state) < N_FLOAT_REGS) {
				/* ok, we have a free register: push + fstp */
				arch_register_t const *const out = get_st_reg(REG_FP_FP_NOREG);
				x87_dup_operand(state, n, n_ia32_fst_val, val, out);
do_pop:
				x87_pop(state);
			} else {
				/* we can only store the tos to memory */
				move_to_tos(state, n, val);

				/* stack full here: need fstp + load */
				ir_node *const block = get_nodes_block(n);
				ir_node *const mem   = get_Proj_for_pn(n, pn_ia32_st_M);
				ir_node *const vfld  = new_bd_ia32_fld(NULL, block, get_irn_n(n, 0), get_irn_n(n, 1), mem, mode);

				/* copy all attributes */
				ia32_copy_am_attrs(vfld, n);
				set_ia32_op_type(vfld, ia32_AddrModeS);

				ir_node *const rproj = new_r_Proj(vfld, mode, pn_ia32_fld_res);
				ir_node *const mproj = new_r_Proj(vfld, mode_M, pn_ia32_fld_M);

				arch_set_irn_register(rproj, arch_get_irn_register(val));
				/* Replace TOS by the reloaded value. */
				x87_set_st(state, rproj, 0);

				/* reroute all former users of the store memory to the load memory */
				edges_reroute_except(mem, mproj, vfld);

				sched_add_after(n, vfld);

				/* rewire all users, scheduled after the store, to the loaded value */
				ir_graph *irg = get_irn_irg(val);
				be_ssa_construction_env_t env;
				be_ssa_construction_init(&env, irg);
				be_ssa_construction_add_copy(&env, rproj);<commit_msg>ia32: Use symbolic names.<commit_after>/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief       This file implements the x87 support and virtual to stack
 *              register translation for the ia32 backend.
 * @author      <NAME>
 */
#include <assert.h>

#include "beirg.h"
#include "irnode_t.h"
#include "irop_t.h"
#include "irprog.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "ircons.h"
#include "irgwalk.h"
#include "irtools.h"
#include "obst.h"
#include "pmap.h"
#include "array.h"
#include "pdeq.h"
#include "debug.h"
#include "panic.h"

#include "belive.h"
#include "besched.h"
#include "benode.h"
#include "bessaconstr.h"
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
#include "ia32_architecture.h"

#define N_FLOAT_REGS  (N_ia32_fp_REGS-1)  // exclude NOREG

/** the debug handle */
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

/* Forward declaration. */
typedef struct x87_simulator x87_simulator;

/**
 * An entry on the simulated x87 stack.
 */
typedef struct st_entry {
	unsigned 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_FLOAT_REGS]; /**< the register stack */
	unsigned       depth;            /**< the current stack depth */
	x87_simulator *sim;              /**< The simulator. */
} x87_state;

/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
 */
typedef void (*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 {
	x87_state const *begin; /**< state at the begin or NULL if not assigned */
	x87_state const *end;   /**< state at the end or NULL if not assigned */
} blk_state;

/** liveness bitset for fp registers. */
typedef unsigned char fp_liveness;

/**
 * The 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. */
	fp_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 current stack depth.
 *
 * @param state  the x87 state
 * @return the x87 stack depth
 */
static unsigned x87_get_depth(const x87_state *state)
{
	return state->depth;
}

static st_entry *x87_get_entry(x87_state *const state, unsigned const pos)
{
	assert(pos < state->depth);
	return &state->st[N_FLOAT_REGS - state->depth + pos];
}

/**
 * Return the node at st(pos).
 *
 * @param state  the x87 state
 * @param pos    a stack position
 * @return the node that produced the value at st(pos)
 */
static ir_node *x87_get_st_node(x87_state const *const state, unsigned const pos)
{
	return x87_get_entry((x87_state*)state, pos)->node;
}

/**
 * Return the virtual register index at st(pos).
 *
 * @param state  the x87 state
 * @param pos    a stack position
 * @return the fp register index that produced the value at st(pos)
 */
static unsigned x87_get_st_reg(const x87_state *state, unsigned pos)
{
	return x87_get_entry((x87_state*)state, pos)->reg_idx;
}

#ifdef DEBUG_libfirm
/**
 * Dump the stack for debugging.
 *
 * @param state  the x87 state
 */
static void x87_dump_stack(const x87_state *state)
{
	for (unsigned 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"));
}
#endif /* DEBUG_libfirm */

/**
 * Set a node to st(pos).
 *
 * @param state    the x87 state
 * @param node     the IR node that produces the value of the fp register
 * @param pos      the stack position where the new value should be entered
 */
static void x87_set_st(x87_state *const state, ir_node *const node, unsigned const pos)
{
	st_entry *const entry = x87_get_entry(state, pos);
	entry->reg_idx = arch_get_irn_register(node)->index;
	entry->node    = node;

	DB((dbg, LEVEL_2, "After SET_REG: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * 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, unsigned 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);)
}

/**
 * Convert a node to the stack index.
 *
 * @param state    the x87 state
 * @param node     the node to find
 * @return the stack position where the node is stacked
 *         or -1 if the node was not found
 */
static unsigned x87_on_stack(x87_state const *const state, ir_node const *const node)
{
	unsigned const reg_idx = arch_get_irn_register(node)->index;
	for (unsigned i = 0; i < state->depth; ++i) {
		if (x87_get_st_reg(state, i) == reg_idx)
			return i;
	}
	return (unsigned)-1;
}

static unsigned is_at_pos(x87_state const *const state, ir_node const *const val, unsigned const pos)
{
	arch_register_t const *const reg = arch_get_irn_register(val);
	return x87_get_st_reg(state, pos) == reg->index;
}

/**
 * Push a node onto the stack, double pushes are NOT allowed.
 *
 * @param state     the x87 state
 * @param node      the node that produces the value of the fp register
 */
static void x87_push(x87_state *const state, ir_node *const node)
{
	assert(x87_on_stack(state, node) == (unsigned)-1 && "double push");
	assert(state->depth < N_FLOAT_REGS && "stack overrun");

	++state->depth;
	st_entry *const entry = x87_get_entry(state, 0);
	entry->reg_idx = arch_get_irn_register(node)->index;
	entry->node    = node;

	DB((dbg, LEVEL_2, "After PUSH: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * Pop a virtual Register from the stack.
 *
 * @param state     the x87 state
 */
static void x87_pop(x87_state *state)
{
	assert(state->depth > 0 && "stack underrun");
	--state->depth;
	DB((dbg, LEVEL_2, "After POP: "));
	DEBUG_ONLY(x87_dump_stack(state);)
}

/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
static void x87_emms(x87_state *state)
{
	state->depth = 0;
}

/**
 * Returns the block state of a block.
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 * @return the block state
 */
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);
	}
	return res;
}

/**
 * Clone a x87 state.
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 * @return a cloned copy of the src state
 */
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;
}

static inline const arch_register_t *get_st_reg(unsigned 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)
 */
static void x87_create_fxch(x87_state *state, ir_node *n, unsigned 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->reg = get_st_reg(pos);

	keep_alive(fxch);

	sched_add_before(n, fxch);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fxch), attr->reg->name));
}

static void move_to_pos(x87_state *const state, ir_node *const before, ir_node *const val, unsigned const to)
{
	unsigned const from = x87_on_stack(state, val);
	assert(from != (unsigned)-1);
	if (from != to) {
		if (from != 0)
			x87_create_fxch(state, before, from);
		if (to != 0)
			x87_create_fxch(state, before, to);
	}
}

static void move_to_tos(x87_state *const state, ir_node *const before, ir_node *const val)
{
	move_to_pos(state, before, val, 0);
}

/* -------------- x87 perm --------------- */

/**
 * Calculate the necessary permutations to reach dst_state.
 *
 * These permutations are done with fxch instructions and placed
 * at the end of the block.
 *
 * Note that critical edges are removed here, so we need only
 * a shuffle if the current block has only one successor.
 *
 * @param block      the current block
 * @param state      the current x87 stack state, might be modified
 * @param dst_state  destination state
 * @return state
 */
static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state)
{
	assert(state->depth == dst_state->depth);

	/* Some mathematics here:
	 * 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). */
	unsigned all_mask = (1 << (state->depth)) - 1;

	unsigned      cycles[4];
	unsigned char cycle_idx[4][8];
	unsigned      n_cycles;
	for (n_cycles = 0; all_mask != 0; ++n_cycles) {
		/* find the first free slot */
		unsigned i;
		for (i = 0; i < state->depth; ++i) {
			if (all_mask & (1 << i)) {
				all_mask &= ~(1 << i);

				/* check if there are differences here */
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
					break;
			}
		}

		if (all_mask == 0) {
			/* no more cycles found */
			break;
		}

		unsigned k = 0;
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
		for (unsigned src_idx = i, dst_idx; ; src_idx = dst_idx) {
			dst_idx = x87_on_stack(dst_state, x87_get_st_node(state, src_idx));

			if ((all_mask & (1 << dst_idx)) == 0)
				break;

			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
			all_mask       &= ~(1 << dst_idx);
		}
		cycle_idx[n_cycles][k] = (unsigned char)-1;
	}

	if (n_cycles == 0) {
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
	DEBUG_ONLY(x87_dump_stack(state);)
	DB((dbg, LEVEL_2, "                  to\n"));
	DEBUG_ONLY(x87_dump_stack(dst_state);)

#ifdef DEBUG_libfirm
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
		for (unsigned k = 0; cycle_idx[ri][k] != (unsigned char)-1; ++k)
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

	/* Find the place node must be insert.
	 * We have only one successor block, so the last instruction should
	 * be a jump. */
	ir_node *const before = sched_last(block);
	assert(is_cfop(before));

	/* now do the permutations */
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0)
			x87_create_fxch(state, before, cycle_idx[ri][0]);
		for (unsigned k = 1; cycle_idx[ri][k] != (unsigned char)-1; ++k) {
			x87_create_fxch(state, before, cycle_idx[ri][k]);
		}
		if ((cycles[ri] & 1) == 0)
			x87_create_fxch(state, before, cycle_idx[ri][0]);
	}
	return state;
}

static ir_node *x87_create_fdup(x87_state *const state, ir_node *const block, ir_node *const val, arch_register_t const *const out)
{
	ir_node         *const fdup = new_bd_ia32_fdup(NULL, block, val);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fdup);
	unsigned         const pos  = x87_on_stack(state, val);
	attr->reg = get_st_reg(pos);
	arch_set_irn_register(fdup, out);
	x87_push(state, fdup);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fdup), attr->reg->name));
	return fdup;
}

/**
 * Create an fdup before node @p n replacing operand @p op_n.
 *
 * @param state     the x87 state
 * @param n         the node after the fdup
 * @param val       the value to duplicate
 */
static ir_node *x87_dup_operand(x87_state *const state, ir_node *const n, unsigned const op_n, ir_node *const val, arch_register_t const *const out)
{
	ir_node *const block = get_nodes_block(n);
	ir_node *const fdup  = x87_create_fdup(state, block, val, out);
	sched_add_before(n, fdup);
	set_irn_n(n, op_n, fdup);
	return fdup;
}

/**
 * Create a fpop before node n.
 * This overwrites st(pos) with st(0) and pops st(0).
 *
 * @param state   the x87 state
 * @param n       the node after which to schedule the fpop
 * @param pos     the index of the entry to remove the register stack
 * @return the fpop node
 */
static ir_node *x87_create_fpop(x87_state *const state, ir_node *const n,
                                unsigned const pos)
{
	if (pos != 0) {
		st_entry *const dst = x87_get_entry(state, pos);
		st_entry *const src = x87_get_entry(state, 0);
		*dst = *src;
	}
	x87_pop(state);
	ir_node *const block = get_block(n);
	ir_node *const fpop  = pos == 0 && ia32_cg_config.use_ffreep ?
		new_bd_ia32_ffreep(NULL, block) :
		new_bd_ia32_fpop(  NULL, block);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fpop);
	attr->reg = get_st_reg(pos);

	keep_alive(fpop);
	sched_add_after(n, fpop);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->reg->name));
	return fpop;
}

/* --------------------------------- liveness ------------------------------------------ */

/**
 * 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 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 The live bitset.
 */
static fp_liveness fp_liveness_transfer(ir_node *irn, fp_liveness live)
{
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_fp];
	be_foreach_definition(irn, cls, def, req,
		const arch_register_t *reg = arch_get_irn_register(def);
		live &= ~(1 << reg->index);
	);
	be_foreach_use(irn, cls, in_req_, op, op_req_,
		const arch_register_t *reg = arch_get_irn_register(op);
		live |= 1 << reg->index;
	);
	return live;
}

/**
 * Put all live virtual registers at the end of a block into a bitset.
 *
 * @param sim      the simulator handle
 * @param bl       the block
 * @return The live bitset at the end of this block
 */
static fp_liveness fp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
{
	fp_liveness                  live = 0;
	const arch_register_class_t *cls  = &ia32_reg_classes[CLASS_ia32_fp];
	const be_lv_t               *lv   = sim->lv;

	be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
		const arch_register_t *reg = arch_get_irn_register(node);
		live |= 1 << reg->index;
	}

	return live;
}

/** get the register mask from an arch_register */
#define REGMASK(reg)    (1 << (reg->index))

/**
 * 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 fp_liveness fp_live_args_after(x87_simulator *sim, const ir_node *pos,
                                      fp_liveness kill)
{
	unsigned idx = get_irn_idx(pos);
	assert(idx < sim->n_idx);
	return sim->live[idx] & ~kill;
}

/**
 * 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)
{
	fp_liveness live = fp_liveness_end_of_block(sim, block);
	/* 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;

		unsigned idx = get_irn_idx(irn);
		sim->live[idx] = live;

		live = fp_liveness_transfer(irn, live);
	}
	unsigned idx = get_irn_idx(block);
	sim->live[idx] = live;
}

/**
 * Returns true if node is live in the set.
 *
 * @param node  the node to check
 * @param live  a live bitset
 */
static inline bool is_fp_live(ir_node const *const node, fp_liveness const live)
{
	unsigned const reg_idx = arch_get_irn_register(node)->index;
	return live & (1 << reg_idx);
}

#ifdef DEBUG_libfirm
/**
 * Dump liveness info.
 *
 * @param live  the live bitset
 */
static void fp_dump_live(fp_liveness live)
{
	DB((dbg, LEVEL_2, "Live after: "));
	for (unsigned i = 0; i < N_FLOAT_REGS; ++i) {
		if (live & (1 << i)) {
			DB((dbg, LEVEL_2, "vf%d ", i));
		}
	}
	DB((dbg, LEVEL_2, "\n"));
}
#endif /* DEBUG_libfirm */

/* --------------------------------- simulators ---------------------------------------- */

static ir_node *get_result_node(ir_node *const n)
{
	return get_irn_mode(n) != mode_T ? n : get_Proj_for_pn(n, pn_ia32_res);
}

/**
 * Simulate a virtual binop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_binop(x87_state *const state, ir_node *const n)
{
	ir_node                     *op1            = get_irn_n(n, n_ia32_binary_left);
	ir_node               *const op2            = get_irn_n(n, n_ia32_binary_right);
	arch_register_t const *const out            = arch_get_irn_register_out(n, pn_ia32_res);
	fp_liveness            const live           = fp_live_args_after(state->sim, n, REGMASK(out));
	bool                   const op1_live_after = is_fp_live(op1, live);

	DB((dbg, LEVEL_1, ">>> %+F %+F, %+F -> %s\n", n, op1, op2, out->name));
	DEBUG_ONLY(fp_dump_live(live);)
	DB((dbg, LEVEL_1, "Stack before: "));
	DEBUG_ONLY(x87_dump_stack(state);)

	if (is_ia32_NoReg_FP(op2)) {
		/* Second operand is an address mode. */
		if (op1_live_after) {
			/* First operand is live: Duplicate it. */
			x87_dup_operand(state, n, n_ia32_binary_left, op1, out);
		} else {
			/* First operand is dead: Move it to tos. */
			move_to_tos(state, n, op1);
		}
		x87_set_st(state, get_result_node(n), 0);
	} else {
		bool       reverse;
		bool       to_reg;
		bool       pop            = false;
		bool const op2_live_after = is_fp_live(op2, live);
		if (op1_live_after) {
			if (op2_live_after) {
				/* Both operands are live: push the first one.
				 * This works even for op1 == op2. */
				op1     = x87_dup_operand(state, n, n_ia32_binary_left, op1, out);
				reverse = false;
				to_reg  = false;
			} else {
				/* First live, second dead: Overwrite second. */
				if (is_at_pos(state, op1, 0)) {
					reverse = false;
					to_reg  = true;
				} else {
					move_to_tos(state, n, op2);
					reverse = true;
					to_reg  = false;
				}
			}
		} else {
			if (op2_live_after) {
				/* First dead, Second live: Overwrite first. */
				if (is_at_pos(state, op2, 0)) {
					reverse = true;
					to_reg  = true;
				} else {
					move_to_tos(state, n, op1);
					reverse = false;
					to_reg  = false;
				}
			} else {
				/* Both dead. */
				if (op1 == op2) {
					/* Operands are identical: No pop. */
					move_to_tos(state, n, op1);
					reverse = false;
					to_reg  = false;
				} else {
					/* Bring one operand to tos. Heuristically swap the operand not at
					 * st(1) to tos. This way, if any operand was at st(1), the result
					 * will end up in the new st(0) after the implicit pop. If the next
					 * operation uses the result, then no fxch will be necessary. */
					if (is_at_pos(state, op1, 0)) {
						reverse = false;
					} else if (is_at_pos(state, op2, 0)) {
						reverse = true;
					} else if (is_at_pos(state, op1, 1)) {
						move_to_tos(state, n, op2);
						reverse = true;
					} else {
						move_to_tos(state, n, op1);
						reverse = false;
					}
					to_reg = true;
					pop    = true;
				}
			}
		}

		unsigned const op_reg = x87_on_stack(state, reverse ? op1 : op2);
		/* Patch the operation. */
		ia32_x87_attr_t *const attr = get_ia32_x87_attr(n);
		attr->reg               = get_st_reg(op_reg);
		attr->attr.ins_permuted = reverse;
		attr->res_in_reg        = to_reg;
		attr->pop               = pop;

		x87_set_st(state, get_result_node(n), to_reg ? op_reg : 0);
		if (pop)
			x87_pop(state);
	}

	DEBUG_ONLY(
		ia32_x87_attr_t const *const attr = get_ia32_x87_attr(n);
		char            const *const st0  = get_st_reg(0)->name;
		char            const *const reg  =  attr->reg ? attr->reg->name : "[AM]";
		char            const *const l    =  attr->attr.ins_permuted ? reg : st0;
		char            const *const r    = !attr->attr.ins_permuted ? reg : st0;
		char            const *const o    =  attr->res_in_reg        ? reg : st0;
		char            const *const pop  =  attr->pop ? " [pop]" : "";
		DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s%s\n", get_irn_opname(n), l, r, o, pop));
	)
}

/**
 * Simulate a virtual Unop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_unop(x87_state *state, ir_node *n)
{
	arch_register_t const *const out  = arch_get_irn_register(n);
	fp_liveness            const live = fp_live_args_after(state->sim, n, REGMASK(out));
	DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
	DEBUG_ONLY(fp_dump_live(live);)

	ir_node *const val = get_irn_n(n, 0);
	if (is_fp_live(val, live)) {
		/* push the operand here */
		x87_dup_operand(state, n, 0, val, out);
	} else {
		/* operand is dead, bring it to tos */
		move_to_tos(state, n, val);
	}

	x87_set_st(state, n, 0);
	DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), get_st_reg(0)->name));
}

/**
 * Simulate a virtual Load instruction.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_load(x87_state *state, ir_node *n)
{
	assert((unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fild_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fld1_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fldz_res);

	DB((dbg, LEVEL_1, ">>> %+F\n", n));
	x87_push(state, get_result_node(n));
	DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), get_st_reg(0)->name));
}

/**
 * Simulate a virtual Store.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 */
static void sim_store(x87_state *state, ir_node *n)
{
	ir_node *const val = get_irn_n(n, n_ia32_fst_val);
	DB((dbg, LEVEL_1, ">>> %+F %+F ->\n", n, val));

	fp_liveness const live = fp_live_args_after(state->sim, n, 0);
	if (!is_fp_live(val, live)) {
		/* we can only store the tos to memory */
		move_to_tos(state, n, val);
		goto do_pop;
	} else {
		/* 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 */
		ir_mode *const mode = get_ia32_ls_mode(n);
		if (get_mode_size_bits(mode) > (mode_is_int(mode) ? 32U : 64U)) {
			if (x87_get_depth(state) < N_FLOAT_REGS) {
				/* ok, we have a free register: push + fstp */
				arch_register_t const *const out = get_st_reg(REG_FP_FP_NOREG);
				x87_dup_operand(state, n, n_ia32_fst_val, val, out);
do_pop:
				x87_pop(state);
			} else {
				/* we can only store the tos to memory */
				move_to_tos(state, n, val);

				/* stack full here: need fstp + load */
				ir_node *const block = get_nodes_block(n);
				ir_node *const mem   = get_Proj_for_pn(n, pn_ia32_st_M);
				ir_node *const base  = get_irn_n(n, n_ia32_base);
				ir_node *const idx   = get_irn_n(n, n_ia32_index);
				ir_node *const vfld  = new_bd_ia32_fld(NULL, block, base, idx, mem, mode);

				/* copy all attributes */
				ia32_copy_am_attrs(vfld, n);
				set_ia32_op_type(vfld, ia32_AddrModeS);

				ir_node *const rproj = new_r_Proj(vfld, mode, pn_ia32_fld_res);
				ir_node *const mproj = new_r_Proj(vfld, mode_M, pn_ia32_fld_M);

				arch_set_irn_register(rproj, arch_get_irn_register(val));
				/* Replace TOS by the reloaded value. */
				x87_set_st(state, rproj, 0);

				/* reroute all former users of the store memory to the load memory */
				edges_reroute_except(mem, mproj, vfld);

				sched_add_after(n, vfld);

				/* rewire all users, scheduled after the store, to the loaded value */
				ir_graph *irg = get_irn_irg(val);
				be_ssa_construction_env_t env;
				be_ssa_construction_init(&env, irg);
				be_ssa_construction_add_copy(&env, rproj);
{'fraction_non_alphanumeric': 0.13501637772629224, 'fraction_numerical': 0.022769034113605497, 'mean_word_length': 3.1983062217004865, 'pattern_counts': {'":': 0, '<': 141, '<?xml version=': 0, '>': 193, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '620410', 'n_tokens_mistral': 20248, 'n_tokens_neox': 18569, 'n_words': 5370}