belower.c

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

/**
 * @file
 * @brief       Performs lowering of perm nodes. Inserts copies to assure
 *              register constraints.
 * @author      Christian Wuerdig
 * @date        14.12.2005
 */
#include <stdlib.h>

#include "ircons.h"
#include "debug.h"
#include "xmalloc.h"
#include "irnodeset.h"
#include "irnodehashmap.h"
#include "irgmod.h"
#include "iredges_t.h"
#include "irgwalk.h"
#include "array.h"
#include "raw_bitset.h"
#include "adt/obstack.h"
#include "util.h"

#include "bearch.h"
#include "beirg.h"
#include "belower.h"
#include "benode.h"
#include "besched.h"
#include "bestat.h"
#include "bessaconstr.h"
#include "belive.h"

#undef KEEP_ALIVE_COPYKEEP_HACK

DEBUG_ONLY(static firm_dbg_module_t *dbg;)
DEBUG_ONLY(static firm_dbg_module_t *dbg_constr;)
DEBUG_ONLY(static firm_dbg_module_t *dbg_permmove;)

/** Associates an ir_node with its copy and CopyKeep. */
typedef struct {
	ir_nodeset_t copies; /**< all non-spillable copies of this irn */
	const arch_register_class_t *cls;
} op_copy_assoc_t;

/** Environment for constraints. */
typedef struct {
	ir_graph        *irg;
	ir_nodehashmap_t op_set;
	struct obstack   obst;
} constraint_env_t;

/** Lowering walker environment. */
typedef struct lower_env_t {
	bool             use_copies;
	struct obstack   obst;
	ir_nodehashmap_t live_regs; /**< maps Perm nodes to a raw bitset that
	                                 maps register indices to register state
	                                 at end of Perm's block (used=0, free=1) */
} lower_env_t;

/** Holds a Perm register pair. */
typedef struct reg_pair_t {
	const arch_register_t *in_reg;    /**< a perm IN register */
	ir_node               *in_node;   /**< the in node to which the register belongs */

	const arch_register_t *out_reg;   /**< a perm OUT register */
	ir_node               *out_node;  /**< the out node to which the register belongs */
} reg_pair_t;

static void set_reg_free(unsigned *free_regs, ir_node const *irn, bool const reg_is_free)
{
	if (!mode_is_data(get_irn_mode(irn)))
		return;
	arch_register_t const *reg = arch_get_irn_register(irn);
	if (reg_is_free) {
		rbitset_set(free_regs, reg->global_index);
	} else {
		rbitset_clear(free_regs, reg->global_index);
	}
}

/* Save the register situation at the end of the Perm's block, i.e. mark all
 * registers holding live values as used.
 * As we do this before we modify the graph, we might mark more registers
 * as used than really necessary.
 */
static void mark_live_nodes_registers(const ir_node *irn, lower_env_t *env)
{
	ir_node                     *block     = get_nodes_block(irn);
	ir_graph                    *irg       = get_irn_irg(irn);
	arch_register_class_t const *reg_class = arch_get_irn_register(get_irn_n(irn, 0))->reg_class;
	arch_env_t const            *arch_env  = be_get_irg_arch_env(irg);
	be_irg_t                    *birg      = be_birg_from_irg(irg);
	unsigned                     n_regs    = arch_env->n_registers;
	unsigned                    *free_regs = rbitset_duplicate_obstack_alloc(&env->obst, birg->allocatable_regs, n_regs);

	be_lv_t *lv = be_get_irg_liveness(irg);
	assert(lv->sets_valid && "Live sets are invalid");
	be_lv_foreach_cls(lv, block, be_lv_state_end, reg_class, live) {
		set_reg_free(free_regs, live, false);
	}

	ir_nodehashmap_insert(&env->live_regs, (ir_node*)irn, free_regs);
}

static void live_nodes_registers_walker(ir_node *irn, void *env)
{
	if (!be_is_Perm(irn))
		return;

	mark_live_nodes_registers(irn, (lower_env_t*)env);
}

static arch_register_t const *get_free_register(ir_node *const perm, lower_env_t *env)
{
	if (!env->use_copies)
		return NULL;

	ir_node                     *block     = get_nodes_block(perm);
	ir_graph                    *irg       = get_irn_irg(perm);
	arch_register_class_t const *reg_class = arch_get_irn_register(get_irn_n(perm, 0))->reg_class;
	arch_env_t const            *arch_env  = be_get_irg_arch_env(irg);
	unsigned                     n_regs    = arch_env->n_registers;
	unsigned                    *free_regs = (unsigned*)ir_nodehashmap_get(arch_register_t const, &env->live_regs, perm);

	sched_foreach_reverse(block, node) {
		if (is_Phi(node))
			break;

		/* If we later implement first the chains and then the cycles
		   of the Perm, we *cannot* regard the Perm's own outputs as
		   free registers. */
		bool const reg_is_free = perm != node;
		if (get_irn_mode(node) == mode_T) {
			foreach_out_edge(node, edge) {
				ir_node *proj = get_edge_src_irn(edge);
				set_reg_free(free_regs, proj, reg_is_free);
			}
		} else {
			set_reg_free(free_regs, node, reg_is_free);
		}

		foreach_irn_in(node, i, in) {
			set_reg_free(free_regs, in, false);
		}

		if (perm == node)
			break;
	}

	rbitset_foreach(free_regs, n_regs, free_idx) {
		arch_register_t const *free_reg = &arch_env->registers[free_idx];
		if (free_reg->reg_class != reg_class)
			continue;

		return free_reg;
	}

	return NULL;
}

static bool is_same_value(const ir_node *a, const ir_node *b)
{
	return (be_is_Copy(a) && be_get_Copy_op(a) == b)
	    || (be_is_CopyKeep(a) && be_get_CopyKeep_op(a) == b)
	    || (be_is_Copy(b) && be_get_Copy_op(b) == a)
	    || (be_is_CopyKeep(b) && be_get_CopyKeep_op(b) == a);
}

/**
 * Lowers a perm node.  Resolves cycles and creates a bunch of
 * copy and swap operations to permute registers.
 *
 * @param perm        The perm node
 * @param env         The lowering environment, containing information on,
 *                    i.e., whether to use copies if free register available
 */
static void lower_perm_node(ir_node *const perm, lower_env_t *env)
{
	DBG((dbg, LEVEL_1, "lowering %+F\n", perm));

	bool const                         use_copies = env->use_copies;
	arch_register_class_t const *const cls        = arch_get_irn_register_req_out(perm, 0)->cls;
	unsigned                     const n_regs     = cls->n_regs;
	/* Registers used as inputs of the Perm. */
	unsigned                    *const inregs     = rbitset_alloca(n_regs);
	/* Map from register index to pair with this register as output. */
	reg_pair_t                 **const oregmap    = ALLOCANZ(reg_pair_t*, n_regs);
	size_t                       const arity      = get_irn_arity(perm);
	reg_pair_t                  *const pairs      = ALLOCAN(reg_pair_t, arity);
	reg_pair_t                        *pair       = pairs;
	arch_register_t const             *free_reg   = NULL;

	/* Collect all input-output pairs of the Perm. */
	foreach_out_edge_safe(perm, edge) {
		ir_node               *const out  = get_edge_src_irn(edge);
		unsigned               const pos  = get_Proj_proj(out);
		ir_node               *const in   = get_irn_n(perm, pos);
		arch_register_t const *const ireg = arch_get_irn_register(in);
		arch_register_t const *const oreg = arch_get_irn_register_out(perm, pos);

		if (ireg == oreg) {
			DBG((dbg, LEVEL_2, "%+F: removing equal perm register pair (%+F, %+F, %s)\n", perm, in, out, oreg->name));
			exchange(out, in);
			continue;
		}

		pair->in_reg   = ireg;
		pair->in_node  = in;
		pair->out_reg  = oreg;
		pair->out_node = out;

		oregmap[oreg->index] = pair++;
		rbitset_set(inregs, ireg->index);
	}

	if (pair == pairs) {
		DBG((dbg, LEVEL_1, "%+F is identity\n", perm));
		goto done;
	}

	DBG((dbg, LEVEL_1, "%+F has %d unresolved constraints\n", perm, (int)(pair - pairs)));

	ir_node *const block = get_nodes_block(perm);
	/* Build Copy chains. */
	for (unsigned i = 0; i != n_regs; ++i) {
		if (rbitset_is_set(inregs, i))
			continue;
		/* Found end of chain, i.e. register which is written to, but not read.
		 * Generate copies by following the chain backwards. */
		unsigned k = i;
		for (reg_pair_t const *p; (p = oregmap[k]);) {
			oregmap[k] = NULL;
			ir_node *const copy = be_new_Copy(block, p->in_node);
			DBG((dbg, LEVEL_2, "%+F: inserting %+F for %+F from %s to %s\n", perm, copy, p->in_node, p->in_reg, p->out_reg));
			arch_set_irn_register(copy, p->out_reg);
			exchange(p->out_node, copy);
			sched_add_before(perm, copy);

			const unsigned new_k = p->in_reg->index;
			if (oregmap[new_k] == NULL) {
				/* The invariant of Perm nodes allows us to overwrite
				 * the first register in a chain with an arbitrary value. */
				free_reg = p->in_reg;
			}
			k = new_k;

			rbitset_clear(inregs, k);
		}
	}

	if (arity == 2 && !rbitset_is_empty(inregs, n_regs)) {
		DBG((dbg, LEVEL_1, "%+F is transposition\n", perm));
		return;
	}

	if (use_copies && free_reg == NULL) {
		free_reg = get_free_register(perm, env);
	}

	if (use_copies && free_reg != NULL) {
		/* Implement cycles using copies and the free register. */
		for (unsigned i = 0; i != n_regs; /* empty */) {
			if (!rbitset_is_set(inregs, i)) {
				++i;
				continue;
			}
			reg_pair_t *start = oregmap[i];

			ir_node *save_copy = be_new_Copy(block, start->in_node);
			arch_set_irn_register(save_copy, free_reg);
			sched_add_before(perm, save_copy);

			reg_pair_t *p = oregmap[start->in_reg->index];
			do {
				ir_node *copy = be_new_Copy(block, p->in_node);
				arch_set_irn_register(copy, p->out_reg);
				exchange(p->out_node, copy);
				sched_add_before(perm, copy);
				unsigned const in_idx = p->in_reg->index;
				rbitset_clear(inregs, in_idx);
				p = oregmap[in_idx];
			} while (p != start);

			rbitset_clear(inregs, start->in_reg->index);
			ir_node *restore_copy = be_new_Copy(block, save_copy);
			arch_set_irn_register(restore_copy, start->out_reg);
			exchange(start->out_node, restore_copy);
			sched_add_before(perm, restore_copy);
		}
	} else {
		/* Decompose cycles into transpositions.
		 *
		 * Use as many independent transpositions as possible and do not thread
		 * one value through all transpositions.
		 * I.e., for the first level of decomposition of a n-Perm do floor(n/2)
		 * transpositions. This puts floor(n/2) values into the right registers.
		 * Repeat this for all remaining values until all have the right
		 * register.
		 * This way no value is threaded through more than ceil(ld(n/2))
		 * transpositions (compared to one value being threaded through all
		 * transpositions using a naive decomposition).
		 *
		 * good:            bad:
		 * r1 r2 r3 r4 r5   r1 r2 r3 r4 r5
		 * +---+ +---+      +---+
		 *    +------+         +---+
		 *          +---+         +---+
		 * r2 r3 r4 r5 r1            +---+
		 *                  r2 r3 r4 r5 r1
		 */
		for (unsigned i = 0; i != n_regs;) {
			if (!rbitset_is_set(inregs, i)) {
				++i;
				continue;
			}
			reg_pair_t             *p     = oregmap[i];
			reg_pair_t const *const start = p;
			ir_mode          *const mode  = get_irn_mode(p->out_node);
			for (;;) {
				reg_pair_t const *const q = oregmap[p->in_reg->index];
				if (q == start)
					break;

				rbitset_clear(inregs, q->out_reg->index);
				p->in_reg = q->in_reg;

				ir_node *new_p;
				ir_node *new_q;
				if (is_same_value(p->in_node, q->in_node)) {
					new_p = q->in_node;
					new_q = p->in_node;
				} else {
					ir_node *const in[]  = { p->in_node, q->in_node };
					ir_node *const xchg  = be_new_Perm(cls, block, ARRAY_SIZE(in), in);
					DBG((dbg, LEVEL_2, "%+F: inserting %+F for %+F (%s) and %+F (%s)\n", perm, xchg, in[0], arch_get_irn_register(in[0]), in[1], arch_get_irn_register(in[1])));
					new_p = new_r_Proj(xchg, mode, 0);
					new_q = new_r_Proj(xchg, mode, 1);
					arch_set_irn_register_out(xchg, 0, q->in_reg);
					arch_set_irn_register_out(xchg, 1, q->out_reg);
					sched_add_before(perm, xchg);
				}
				p->in_node = new_p;
				exchange(q->out_node, new_q);

				p = oregmap[q->in_reg->index];
				if (p == start) {
					if (start->in_reg == start->out_reg) {
						rbitset_clear(inregs, q->in_reg->index);
						exchange(start->out_node, start->in_node);
					}
					break;
				}
			}
		}
	}

done:
	sched_remove(perm);
	kill_node(perm);
}

static int has_irn_users(const ir_node *irn)
{
	return get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL) != 0;
}

static ir_node *find_copy(ir_node *irn, ir_node *op)
{
	ir_node *cur_node;

	for (cur_node = irn;;) {
		cur_node = sched_prev(cur_node);
		if (! be_is_Copy(cur_node))
			return NULL;
		if (be_get_Copy_op(cur_node) == op && arch_irn_is(cur_node, dont_spill))
			return cur_node;
	}
}

static void gen_assure_different_pattern(ir_node *irn, ir_node *other_different, constraint_env_t *env)
{
	ir_nodehashmap_t            *op_set;
	ir_node                     *block;
	const arch_register_class_t *cls;
	ir_node                     *keep, *cpy;
	op_copy_assoc_t             *entry;

	arch_register_req_t const *const req = arch_get_irn_register_req(other_different);
	if (arch_register_req_is(req, ignore) ||
			!mode_is_data(get_irn_mode(other_different))) {
		DB((dbg_constr, LEVEL_1, "ignore constraint for %+F because other_irn is ignore or not a data node\n", irn));
		return;
	}

	op_set = &env->op_set;
	block  = get_nodes_block(irn);
	cls    = req->cls;

	/* Make a not spillable copy of the different node   */
	/* this is needed because the different irn could be */
	/* in block far far away                             */
	/* The copy is optimized later if not needed         */

	/* check if already exists such a copy in the schedule immediately before */
	cpy = find_copy(skip_Proj(irn), other_different);
	if (! cpy) {
		cpy = be_new_Copy(block, other_different);
		arch_set_irn_flags(cpy, arch_irn_flag_dont_spill);
		DB((dbg_constr, LEVEL_1, "created non-spillable %+F for value %+F\n", cpy, other_different));
	} else {
		DB((dbg_constr, LEVEL_1, "using already existing %+F for value %+F\n", cpy, other_different));
	}

	/* Add the Keep resp. CopyKeep and reroute the users */
	/* of the other_different irn in case of CopyKeep.   */
	if (has_irn_users(other_different)) {
		keep = be_new_CopyKeep_single(block, cpy, irn);
		be_node_set_reg_class_in(keep, 1, cls);
	} else {
		ir_node *in[2];

		in[0] = irn;
		in[1] = cpy;
		keep = be_new_Keep(block, 2, in);
	}

	DB((dbg_constr, LEVEL_1, "created %+F(%+F, %+F)\n\n", keep, irn, cpy));

	/* insert copy and keep into schedule */
	assert(sched_is_scheduled(irn) && "need schedule to assure constraints");
	if (! sched_is_scheduled(cpy))
		sched_add_before(skip_Proj(irn), cpy);
	sched_add_after(skip_Proj(irn), keep);

	/* insert the other different and its copies into the map */
	entry = ir_nodehashmap_get(op_copy_assoc_t, op_set, other_different);
	if (! entry) {
		entry      = OALLOC(&env->obst, op_copy_assoc_t);
		entry->cls = cls;
		ir_nodeset_init(&entry->copies);

		ir_nodehashmap_insert(op_set, other_different, entry);
	}

	/* insert copy */
	ir_nodeset_insert(&entry->copies, cpy);

	/* insert keep in case of CopyKeep */
	if (be_is_CopyKeep(keep))
		ir_nodeset_insert(&entry->copies, keep);
}

/**
 * Checks if node has a must_be_different constraint in output and adds a Keep
 * then to assure the constraint.
 *
 * @param irn          the node to check
 * @param skipped_irn  if irn is a Proj node, its predecessor, else irn
 * @param env          the constraint environment
 */
static void assure_different_constraints(ir_node *irn, ir_node *skipped_irn, constraint_env_t *env)
{
	const arch_register_req_t *req = arch_get_irn_register_req(irn);

	if (arch_register_req_is(req, must_be_different)) {
		const unsigned other = req->other_different;
		int i;

		if (arch_register_req_is(req, should_be_same)) {
			const unsigned same = req->other_same;

			if (is_po2(other) && is_po2(same)) {
				int idx_other = ntz(other);
				int idx_same  = ntz(same);

				/*
				 * We can safely ignore a should_be_same x must_be_different y
				 * IFF both inputs are equal!
				 */
				if (get_irn_n(skipped_irn, idx_other) == get_irn_n(skipped_irn, idx_same)) {
					return;
				}
			}
		}
		for (i = 0; 1U << i <= other; ++i) {
			if (other & (1U << i)) {
				ir_node *different_from = get_irn_n(skipped_irn, i);
				gen_assure_different_pattern(irn, different_from, env);
			}
		}
	}
}

/**
 * Calls the functions to assure register constraints.
 *
 * @param block    The block to be checked
 * @param walk_env The walker environment
 */
static void assure_constraints_walker(ir_node *block, void *walk_env)
{
	constraint_env_t *env = (constraint_env_t*)walk_env;

	sched_foreach_reverse(block, irn) {
		be_foreach_value(irn, value,
			if (mode_is_data(get_irn_mode(value)))
				assure_different_constraints(value, irn, env);
		);
	}
}

/**
 * Melt all copykeeps pointing to the same node
 * (or Projs of the same node), copying the same operand.
 */
static void melt_copykeeps(constraint_env_t *cenv)
{
	ir_nodehashmap_iterator_t map_iter;
	ir_nodehashmap_entry_t    map_entry;

	/* for all */
	foreach_ir_nodehashmap(&cenv->op_set, map_entry, map_iter) {
		op_copy_assoc_t *entry = (op_copy_assoc_t*)map_entry.data;
		int     idx, num_ck;
		struct obstack obst;
		ir_node **ck_arr, **melt_arr;

		obstack_init(&obst);

		/* collect all copykeeps */
		num_ck = idx = 0;
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			if (be_is_CopyKeep(cp)) {
				obstack_grow(&obst, &cp, sizeof(cp));
				++num_ck;
#ifdef KEEP_ALIVE_COPYKEEP_HACK
			} else {
				set_irn_mode(cp, mode_ANY);
				keep_alive(cp);
#endif
			}
		}

		/* compare each copykeep with all other copykeeps */
		ck_arr = (ir_node **)obstack_finish(&obst);
		for (idx = 0; idx < num_ck; ++idx) {
			ir_node *ref, *ref_mode_T;

			if (ck_arr[idx]) {
				int j, n_melt;
				ir_node *sched_pt = NULL;

				n_melt     = 1;
				ref        = ck_arr[idx];
				ref_mode_T = skip_Proj(get_irn_n(ref, 1));
				obstack_grow(&obst, &ref, sizeof(ref));

				DB((dbg_constr, LEVEL_1, "Trying to melt %+F:\n", ref));

				/* check for copykeeps pointing to the same mode_T node as the reference copykeep */
				for (j = 0; j < num_ck; ++j) {
					ir_node *cur_ck = ck_arr[j];

					if (j != idx && cur_ck && skip_Proj(get_irn_n(cur_ck, 1)) == ref_mode_T) {
						obstack_grow(&obst, &cur_ck, sizeof(cur_ck));
						ir_nodeset_remove(&entry->copies, cur_ck);
						DB((dbg_constr, LEVEL_1, "\t%+F\n", cur_ck));
						ck_arr[j] = NULL;
						++n_melt;
						sched_remove(cur_ck);
					}
				}
				ck_arr[idx] = NULL;

				/* check, if we found some candidates for melting */
				if (n_melt == 1) {
					DB((dbg_constr, LEVEL_1, "\tno candidate found\n"));
					continue;
				}

				ir_nodeset_remove(&entry->copies, ref);
				sched_remove(ref);

				melt_arr = (ir_node **)obstack_finish(&obst);
				/* melt all found copykeeps */
				ir_node **new_ck_in = ALLOCAN(ir_node*,n_melt);
				for (j = 0; j < n_melt; ++j) {
					new_ck_in[j] = get_irn_n(melt_arr[j], 1);

					/* now, we can kill the melted keep, except the */
					/* ref one, we still need some information      */
					if (melt_arr[j] != ref)
						kill_node(melt_arr[j]);
				}

				ir_node *const new_ck = be_new_CopyKeep(get_nodes_block(ref), be_get_CopyKeep_op(ref), n_melt, new_ck_in);
#ifdef KEEP_ALIVE_COPYKEEP_HACK
				keep_alive(new_ck);
#endif /* KEEP_ALIVE_COPYKEEP_HACK */

				/* set register class for all kept inputs */
				for (j = 1; j <= n_melt; ++j)
					be_node_set_reg_class_in(new_ck, j, entry->cls);

				ir_nodeset_insert(&entry->copies, new_ck);

				/* find scheduling point */
				sched_pt = ref_mode_T;
				do {
					/* just walk along the schedule until a non-Keep/CopyKeep node is found */
					sched_pt = sched_next(sched_pt);
				} while (be_is_Keep(sched_pt) || be_is_CopyKeep(sched_pt));

				sched_add_before(sched_pt, new_ck);
				DB((dbg_constr, LEVEL_1, "created %+F, scheduled before %+F\n", new_ck, sched_pt));

				/* finally: kill the reference copykeep */
				kill_node(ref);
			}
		}

		obstack_free(&obst, NULL);
	}
}

void assure_constraints(ir_graph *irg)
{
	constraint_env_t          cenv;
	ir_nodehashmap_iterator_t map_iter;
	ir_nodehashmap_entry_t    map_entry;

	FIRM_DBG_REGISTER(dbg_constr, "firm.be.lower.constr");

	cenv.irg = irg;
	ir_nodehashmap_init(&cenv.op_set);
	obstack_init(&cenv.obst);

	irg_block_walk_graph(irg, NULL, assure_constraints_walker, &cenv);

	/* melt copykeeps, pointing to projs of */
	/* the same mode_T node and keeping the */
	/* same operand                         */
	melt_copykeeps(&cenv);

	/* for all */
	foreach_ir_nodehashmap(&cenv.op_set, map_entry, map_iter) {
		op_copy_assoc_t          *entry = (op_copy_assoc_t*)map_entry.data;
		size_t                    n     = ir_nodeset_size(&entry->copies);
		ir_node                 **nodes = ALLOCAN(ir_node*, n);
		be_ssa_construction_env_t senv;

		/* put the node in an array */
		DBG((dbg_constr, LEVEL_1, "introduce copies for %+F ", map_entry.node));

		/* collect all copies */
		n = 0;
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			nodes[n++] = cp;
			DB((dbg_constr, LEVEL_1, ", %+F ", cp));
		}

		DB((dbg_constr, LEVEL_1, "\n"));

		/* introduce the copies for the operand and its copies */
		be_ssa_construction_init(&senv, irg);
		be_ssa_construction_add_copy(&senv, map_entry.node);
		be_ssa_construction_add_copies(&senv, nodes, n);
		be_ssa_construction_fix_users(&senv, map_entry.node);
		be_ssa_construction_destroy(&senv);

		/* Could be that not all CopyKeeps are really needed, */
		/* so we transform unnecessary ones into Keeps.       */
		foreach_ir_nodeset(&entry->copies, cp, iter) {
			if (be_is_CopyKeep(cp) && get_irn_n_edges(cp) < 1) {
				int      n   = get_irn_arity(cp);
				ir_node *keep;

				keep = be_new_Keep(get_nodes_block(cp), n, get_irn_in(cp) + 1);
				sched_replace(cp, keep);

				/* Set all ins (including the block) of the CopyKeep BAD to keep the verifier happy. */
				kill_node(cp);
			}
		}

		ir_nodeset_destroy(&entry->copies);
	}

	ir_nodehashmap_destroy(&cenv.op_set);
	obstack_free(&cenv.obst, NULL);
	be_invalidate_live_sets(irg);
}

/**
 * Push nodes that do not need to be permed through the Perm.
 * This is commonly a reload cascade at block ends.
 * @note This routine needs interference.
 * @note Probably, we can implement it a little more efficient.
 *       Especially searching the frontier lazily might be better.
 *
 * @param perm The perm
 * @param env  The lowerer environment
 *
 * @return     1, if there is something left to perm over.
 *             0, if removed the complete perm.
 */
static int push_through_perm(ir_node *perm)
{
	ir_graph *irg     = get_irn_irg(perm);
	ir_node *bl       = get_nodes_block(perm);
	int  arity        = get_irn_arity(perm);
	int *map;
	int *proj_map;
	bitset_t *moved   = bitset_alloca(arity);
	int n_moved;
	int new_size;
	ir_node *frontier = bl;
	int i, n;

	/* get some Proj and find out the register class of that Proj. */
	ir_node                     *one_proj = get_edge_src_irn(get_irn_out_edge_first_kind(perm, EDGE_KIND_NORMAL));
	const arch_register_class_t *cls      = arch_get_irn_reg_class(one_proj);
	assert(is_Proj(one_proj));

	(void)irg;
	DB((dbg_permmove, LEVEL_1, "perm move %+F irg %+F\n", perm, irg));

	/* Find the point in the schedule after which the
	 * potentially movable nodes must be defined.
	 * A Perm will only be pushed up to first instruction
	 * which lets an operand of itself die.
	 * If we would allow to move the Perm above this instruction,
	 * the former dead operand would be live now at the point of
	 * the Perm, increasing the register pressure by one.
	 */
	sched_foreach_reverse_before(perm, irn) {
		if (is_Phi(irn)) {
			frontier = irn;
			goto found_front;
		}
		be_foreach_use(irn, cls, in_req_, op, op_req_,
			if (!be_value_live_after(op, perm)) {
				frontier = irn;
				goto found_front;
			}
		);
	}
found_front:

	DB((dbg_permmove, LEVEL_2, "\tfrontier: %+F\n", frontier));

	n_moved = 0;
	for (;;) {
		ir_node *const node = sched_prev(perm);
		if (node == frontier)
			break;

		be_foreach_use(node, cls, in_req, value, value_req,
			goto done;
		);

		be_foreach_definition(node, cls, value, req,
			if (req->type != arch_register_req_type_normal &&
			    req->type != arch_register_req_type_should_be_same)
				goto done;
		);

		DBG((dbg_permmove, LEVEL_2, "\tmoving %+F after %+F\n", node, perm));

		/* move the movable node in front of the Perm */
		sched_remove(node);
		sched_add_after(perm, node);

		/* Rewire Perm results to pushed through instruction. */
		foreach_out_edge_safe(perm, edge) {
			ir_node *const proj = get_edge_src_irn(edge);
			int      const pn   = get_Proj_proj(proj);
			ir_node *const in   = get_irn_n(perm, pn);
			if (in == node || (is_Proj(in) && get_Proj_pred(in) == node)) {
				/* Give it the proj's register. */
				arch_set_irn_register(in, arch_get_irn_register_out(perm, pn));
				/* Reroute all users of the proj to the moved node. */
				exchange(proj, in);
				bitset_set(moved, pn);
				++n_moved;
			}
		}
	}
done:

	/* well, we could not push anything through the perm */
	if (n_moved == 0)
		return 1;

	new_size = arity - n_moved;
	if (new_size == 0) {
		sched_remove(perm);
		kill_node(perm);
		return 0;
	}

	map      = ALLOCAN(int, new_size);
	proj_map = ALLOCAN(int, arity);
	memset(proj_map, -1, sizeof(proj_map[0]));
	n   = 0;
	for (i = 0; i < arity; ++i) {
		if (bitset_is_set(moved, i))
			continue;
		map[n]      = i;
		proj_map[i] = n;
		n++;
	}
	assert(n == new_size);
	foreach_out_edge(perm, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		int      pn   = get_Proj_proj(proj);
		pn = proj_map[pn];
		assert(pn >= 0);
		set_Proj_proj(proj, pn);
	}

	be_Perm_reduce(perm, new_size, map);
	return 1;
}

/**
 * Calls the corresponding lowering function for the node.
 *
 * @param irn      The node to be checked for lowering
 * @param walk_env The walker environment
 */
static void lower_nodes_after_ra_walker(ir_node *irn, void *walk_env)
{
	if (!be_is_Perm(irn))
		return;

	const bool perm_stayed = push_through_perm(irn);
	if (perm_stayed) {
		lower_env_t *env = (lower_env_t*)walk_env;
		lower_perm_node(irn, env);
	}
}

void lower_nodes_after_ra(ir_graph *irg, bool use_copies)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.lower");
	FIRM_DBG_REGISTER(dbg_permmove, "firm.be.lower.permmove");

	/* we will need interference */
	be_assure_live_chk(irg);

	lower_env_t env;
	env.use_copies = use_copies;

	if (use_copies) {
		ir_nodehashmap_init(&env.live_regs);
		obstack_init(&env.obst);
		be_assure_live_sets(irg);
		irg_walk_graph(irg, NULL, live_nodes_registers_walker, &env);
	}

	irg_walk_graph(irg, NULL, lower_nodes_after_ra_walker, &env);

	if (use_copies) {
		ir_nodehashmap_destroy(&env.live_regs);
		obstack_free(&env.obst, NULL);
		be_invalidate_live_sets(irg);
	}
}