beschedrss.c

/**
 * Implementation of a register saturating list scheduler
 * as described in: Sid-Ahmed-Ali Touati
 * Register Saturation in Superscalar and VLIW Codes
 *
 * @license This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 * @author  Christian Wuerdig
 * @date    29.08.2006
 * @cvs-id  $Id$
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <limits.h>

#include "obst.h"
#include "debug.h"

#include "irgraph_t.h"
#include "irnode_t.h"
#include "iredges_t.h"
#include "ircons_t.h"
#include "irphase_t.h"
#include "irgwalk.h"
#include "irdump.h"
#include "irtools.h"
#include "irbitset.h"
#include "irprintf.h"
#include "bipartite.h"
#include "hungarian.h"
#include "plist.h"

#include "height.h"

#include "beabi.h"
#include "benode_t.h"
#include "besched_t.h"

#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#endif /* WITH_LIBCORE */


#define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)

#define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
#define BSEARCH_IRN_ARR(val, arr) \
	bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)

#define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)

/* the rss options */
typedef struct _rss_opts_t {
	int dump_flags;
} rss_opts_t;

/* Represents a child with associated costs */
typedef struct _child {
	ir_node *irn;
	float   cost;
} child_t;

/* We need edges for several purposes. */
typedef struct _rss_edge {
	ir_node *src;
	ir_node *tgt;
	void    *next;
} rss_edge_t;

/* Represents a connected bipartite component. */
typedef struct _cbc {
	nodeset *parents;       /**< = S  a set of value producers */
	nodeset *children;      /**< = T  a set of value consumers */
	pset    *kill_edges;    /**< = E  a set of edges (t in T, s in S) such as each s in S gets killed by at least one t in T */
	int     nr;             /**< a deterministic index for set insertion (used as hash) */
} cbc_t;

/* Represents a disjoint value DAG. */
typedef struct _dvg {
	nodeset *nodes;
	pset    *edges;
} dvg_t;

/* Represents a chain of nodes. */
typedef struct _chain {
	plist_t *elements;   /**< List of chain elements */
	int     nr;          /**< a deterministic index for set insertion (used as hash) */
} chain_t;

typedef struct _rss_irn {
	plist_t  *consumer_list;    /**< List of consumers */
	ir_node **consumer;         /**< Sorted consumer array (needed for faster access) */

	plist_t  *parent_list;      /**< List of parents */
	plist_t  *pkiller_list;     /**< List of potential killers */

	plist_t  *descendant_list;  /**< List of descendants */
	ir_node **descendants;      /**< Sorted descendant array (needed for faster access) */

	ir_node  *killer;           /**< The selected unique killer */
	ir_node  *irn;              /**< The corresponding firm node to this rss_irn */

	chain_t  *chain;            /**< The chain, this node is associated to */

	unsigned desc_walk;         /**< visited flag for collecting descendants */
	unsigned kill_count;        /**< number of nodes killed by this one */

	unsigned live_out : 1;      /**< irn has consumers outside of it's block */
	unsigned visited  : 1;      /**< visited flag for bipartite decomposition */
	unsigned havecons : 1;      /**< visited flag collect consumer */
	unsigned handled  : 1;      /**< flag indicating whether or not the list structures have been build */
	unsigned dumped   : 1;      /**< flag indication whether or not this node was dumped */
} rss_irn_t;

/* Represents a serialization edge with associated costs. */
typedef struct _serialization {
	rss_irn_t  *u;       /* the top node */
	rss_irn_t  *v;       /* the node about to be serialized after u */
	rss_edge_t *edge;    /* the edge selected for the serialization */
	int        omega1;   /* estimated: available regs - RS reduction */
	int        omega2;   /* increase in critical path length */
	int        new_killer;
} serialization_t;

typedef struct _rss {
	phase_t          ph;              /**< Phase to hold some data */
	heights_t        *h;              /**< The current height object */
	ir_graph         *irg;            /**< The irg to preprocess */
	plist_t          *nodes;          /**< The list of interesting nodes */
	const arch_env_t *arch_env;       /**< The architecture environment */
	be_abi_irg_t     *abi;            /**< The abi for this irg */
	pset             *cbc_set;        /**< A set of connected bipartite components */
	ir_node          *block;          /**< The current block in progress. */
	int              *idx_map;        /**< Mapping irn indices to per block indices */
	unsigned         max_height;      /**< maximum height in the current block */
	rss_opts_t       *opts;           /**< The options */
	be_lv_t          *liveness;       /**< The liveness information for this irg */
	pset             *live_block;     /**< Values alive at end of block */
	const arch_register_class_t *cls; /**< The current register class */
	DEBUG_ONLY(firm_dbg_module_t *dbg);
} rss_t;

#define get_rss_irn(rss, irn)  (phase_get_or_set_irn_data(&rss->ph, irn))

/**
 * We need some special nodes:
 * a source and a sink for all live-in and live-out values of a block
 */

enum {
	iro_rss_Source,
	iro_rss_Sink,
	iro_rss_last
};

static ir_node *_source = NULL;
static ir_node *_sink   = NULL;

#define is_Source(irn) ((irn) == _source)
#define is_Sink(irn)   ((irn) == _sink)

enum {
	RSS_DUMP_NONE  = 0,
	RSS_DUMP_CBC   = 1 << 0,
	RSS_DUMP_PKG   = 1 << 1,
	RSS_DUMP_KILL  = 1 << 2,
	RSS_DUMP_DVG   = 1 << 3,
	RSS_DUMP_MAXAC = 1 << 4,
	RSS_DUMP_ALL   = (RSS_DUMP_MAXAC << 1) - 1,
};

static rss_opts_t rss_options = {
	RSS_DUMP_NONE,
};

#ifdef WITH_LIBCORE
static const lc_opt_enum_int_items_t dump_items[] = {
	{ "none",  RSS_DUMP_NONE  },
	{ "cbc",   RSS_DUMP_CBC   },
	{ "pkg",   RSS_DUMP_PKG   },
	{ "kill",  RSS_DUMP_KILL  },
	{ "dvg",   RSS_DUMP_DVG   },
	{ "maxac", RSS_DUMP_MAXAC },
	{ "all",   RSS_DUMP_ALL   },
	{ NULL, 0 }
};

static lc_opt_enum_int_var_t dump_var = {
	&rss_options.dump_flags, dump_items
};

static const lc_opt_table_entry_t rss_option_table[] = {
	LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
	{ NULL }
};
#endif /* WITH_LIBCORE */

/******************************************************************************
 *  _          _                    __                  _   _
 * | |        | |                  / _|                | | (_)
 * | |__   ___| |_ __   ___ _ __  | |_ _   _ _ __   ___| |_ _  ___  _ __  ___
 * | '_ \ / _ \ | '_ \ / _ \ '__| |  _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
 * | | | |  __/ | |_) |  __/ |    | | | |_| | | | | (__| |_| | (_) | | | \__ \
 * |_| |_|\___|_| .__/ \___|_|    |_|  \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
 *            | |
 *            |_|
 ******************************************************************************/

/**
 * Acquire opcodes and create source and sink nodes.
 */
static void init_rss_special_nodes(ir_graph *irg) {
	ir_node *block         = get_irg_start_block(irg);
	int     iro_rss_base   = get_next_ir_opcodes(iro_rss_last);
	ir_op   *op_rss_Source = new_ir_op(iro_rss_base + iro_rss_Source, "rss_Source", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
	ir_op   *op_rss_Sink   = new_ir_op(iro_rss_base + iro_rss_Sink,   "rss_Sink",   op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
	_source                = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
	_sink                  = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
}

static int cmp_int(const void *a, const void *b) {
	const int *i1 = a;
	const int *i2 = b;

	return QSORT_CMP(*i1, *i2);
}

static int cmp_child_costs(const void *a, const void *b) {
	const child_t *c1 = a;
	const child_t *c2 = b;

	return QSORT_CMP(c1->cost, c2->cost);
}

static int cmp_irn_idx(const void *a, const void *b) {
	const ir_node *n1 = *(ir_node **)a;
	const ir_node *n2 = *(ir_node **)b;

	return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
}

static int cmp_rss_edges(const void *a, const void *b) {
	const rss_edge_t *e1 = a;
	const rss_edge_t *e2 = b;

	return (e1->src != e2->src) || (e1->tgt != e2->tgt);
}

static int bsearch_for_index(int key, int *arr, size_t len, int force) {
	int left = 0;
	int right = len;

	while (right >= left) {
		int idx = (left + right) / 2;

		if (key < arr[idx])
			right = idx - 1;
		else if (key > arr[idx])
			left = idx + 1;
		else
			return idx;
	}

	if (force)
		assert(0 && "Something is wrong, key not found.");
	return -1;
}

static ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst) {
	plist_element_t *el;
	int     i     = 0;
	int     len   = plist_count(irn_list);
	ir_node **arr = NEW_ARR_D(ir_node *, obst, len);

	/* copy the list into the array */
	foreach_plist(irn_list, el) {
		arr[i++] = plist_element_get_value(el);
	}

	/* sort the array by node index */
	qsort(arr, len, sizeof(arr[0]), cmp_irn_idx);

	return arr;
}

/*****************************************************
 *      _      _                       _
 *     | |    | |                     (_)
 *   __| | ___| |__  _   _  __ _  __ _ _ _ __   __ _
 *  / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
 * | (_| |  __/ |_) | |_| | (_| | (_| | | | | | (_| |
 *  \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
 *                          __/ | __/ |         __/ |
 *                         |___/ |___/         |___/
 *
 *****************************************************/

static void dump_nodeset(nodeset *ns, const char *prefix) {
	ir_node *irn;
	foreach_nodeset(ns, irn) {
		ir_fprintf(stderr, "%s%+F\n", prefix, irn);
	}
}

static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len) {
	const char *irg_name;

	memset(buf, 0, len);
	irg_name = get_entity_name(get_irg_entity(rss->irg));
	snprintf(buf, len - suf_len, "%s-%s-block-%ld",
		irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
	strcat(buf, suffix);
}

/* Dumps all collected bipartite components of current irg as vcg. */
static void debug_vcg_dump_bipartite(rss_t *rss) {
	cbc_t *cbc;
	FILE  *f;
	char  file_name[256];
	static const char suffix[] = "-RSS-CBC.vcg";

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	foreach_pset(rss->cbc_set, cbc) {
		ir_node    *n;
		rss_edge_t *ke;

		fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
		foreach_nodeset(cbc->parents, n) {
			ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
		}
		foreach_nodeset(cbc->children, n) {
			ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
		}
		foreach_pset(cbc->kill_edges, ke) {
			ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
				get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
		}
		fprintf(f, "}\n\n");
	}
	fprintf(f, "}\n");
	fclose(f);
}

/* Dump the computed killing function as vcg. */
static void debug_vcg_dump_kill(rss_t *rss) {
	FILE            *f;
	char            file_name[256];
	plist_element_t *el;
	static const char suffix[] = "-RSS-KILL.vcg";

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	/* first: reset dumped flag of all nodes */
	foreach_plist(rss->nodes, el) {
		ir_node   *irn  = plist_element_get_value(el);
		rss_irn_t *rirn = get_rss_irn(rss, irn);
		rirn->dumped = 0;
	}

	/* dump all nodes and their killers */
	foreach_plist(rss->nodes, el) {
		ir_node   *irn     = plist_element_get_value(el);
		rss_irn_t *rirn    = get_rss_irn(rss, irn);
		rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);

		if (! rirn->dumped) {
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
			rirn->dumped = 1;
		}

		if (! pk_rirn->dumped) {
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
			pk_rirn->dumped = 1;
		}

		ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
			get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
	}

	fprintf(f, "}\n");
	fclose(f);
}

/* Dumps the potential killing DAG (PKG) as vcg. */
static void debug_vcg_dump_pkg(rss_t *rss, nodeset *max_ac, int iteration) {
	FILE              *f;
	char              file_name[256];
	char              *suffix   = alloca(32);
	static const char suffix1[] = "-RSS-PKG.vcg";
	static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
	plist_element_t   *el;

	if (! max_ac) {
		snprintf(suffix, 32, "%s", suffix1);
	}
	else {
		snprintf(suffix, 32, "-%02d%s", iteration, suffix2);
	}

	build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	foreach_plist(rss->nodes, el) {
		ir_node   *irn  = plist_element_get_value(el);
		rss_irn_t *rirn = get_rss_irn(rss, irn);
		char      *c1   = "";
		plist_element_t *k_el;

		/* dump selected saturating values in yellow */
		if (max_ac && nodeset_find(max_ac, irn))
			c1 = "color:yellow";

		if (rirn->chain)
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F   c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
		else
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
		rirn->dumped = 1;

		foreach_plist(rirn->pkiller_list, k_el) {
			ir_node   *pkiller = plist_element_get_value(k_el);
			rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
			char      *c2      = "";

			if (max_ac && nodeset_find(max_ac, pkiller))
				c2 = "color:yellow";

			if (! pk_rirn->dumped) {
				if (pk_rirn->chain)
					ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F   c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
				else
					ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
				pk_rirn->dumped = 1;
			}
			ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
				get_irn_node_nr(pkiller), get_irn_node_nr(irn));
		}
	}
	fprintf(f, "}\n");
	fclose(f);
}

/* Dumps the disjoint value DAG (DVG) as vcg. */
static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg) {
	static const char suffix[] = "-RSS-DVG.vcg";
	FILE       *f;
	char       file_name[256];
	ir_node    *irn;
	rss_edge_t *edge;

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	/* dump all nodes */
	foreach_nodeset(dvg->nodes, irn) {
		ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
	}

	/* dump all edges */
	foreach_pset(dvg->edges, edge) {
		ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
			get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
	}

	fprintf(f, "}\n");
	fclose(f);
}

#if 0
/* Dumps the PKG(DVG). */
static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg) {
	static const char suffix[] = "-RSS-DVG-PKG.vcg";
	FILE       *f;
	char       file_name[256];
	ir_node    *irn;

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	/* dump all nodes */
	foreach_nodeset(dvg->nodes, irn) {
		ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
	}

	/* dump all edges */
	foreach_nodeset(dvg->nodes, irn) {
		rss_irn_t       *node = get_rss_irn(rss, irn);
		plist_element_t *el;

		foreach_plist(node->dvg_pkiller_list, el) {
			ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
				get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
		}
	}

	fprintf(f, "}\n");
	fclose(f);
}
#endif /* if 0 */

/**
 * In case there is no rss information for irn, initialize it.
 */
static void *init_rss_irn(phase_t *ph, ir_node *irn, void *old) {
	rss_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));

	res->descendant_list = plist_obstack_new(phase_obst(ph));
	res->descendants     = NULL;

	res->consumer_list   = plist_obstack_new(phase_obst(ph));
	res->consumer        = NULL;

	res->pkiller_list    = plist_obstack_new(phase_obst(ph));

	res->parent_list     = plist_obstack_new(phase_obst(ph));

	res->killer          = NULL;
	res->irn             = irn;
	res->chain           = NULL;

	res->kill_count      = 0;
	res->desc_walk       = 0;
	res->live_out        = 0;
	res->visited         = 0;
	res->handled         = 0;
	res->dumped          = 0;
	res->havecons        = 0;

	return res;
}

/**
 * Collect all nodes data dependent on current node.
 */
static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk) {
	const ir_edge_t *edge;
	rss_irn_t       *cur_node = get_rss_irn(rss, irn);
	ir_node         *block    = rss->block;
	ir_edge_kind_t  ekind[2]  = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
	int             i;

	if (cur_node->desc_walk >= cur_desc_walk)
		return;
	cur_node->desc_walk = cur_desc_walk;

	/* Stop at Barriers */
	if (be_is_Barrier(irn))
		return;

	/* loop over normal and dependency edges */
	for (i = 0; i < 2; ++i) {
		foreach_out_edge_kind(irn, edge, ekind[i]) {
			ir_node *user = get_edge_src_irn(edge);

			/* skip ignore nodes as they do not really contribute to register pressure */
			if (arch_irn_is(rss->arch_env, user, ignore))
				continue;

			if (get_irn_mode(user) == mode_X) {
				if (! *got_sink)
					goto force_sink;
				else
					continue;
			}

			if (is_Proj(user)) {

				//if (arch_get_irn_reg_class(rss->arch_env, user, -1) == rss->cls)
					collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
			}
			else {
				/* check if user lives in block and is not a control flow node */
				if (get_nodes_block(user) == block) {
					if (! plist_has_value(rirn->descendant_list, user)) {
						plist_insert_back(rirn->descendant_list, user);
						DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
					}
					collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
				}
				else if (! *got_sink) {
force_sink:
					/* user lives out of block: add sink as descendant if not already done */
					plist_insert_back(rirn->descendant_list, _sink);
					*got_sink = 1;
					DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
				}
			}
		}
	}
}

/**
 * Handles a single consumer.
 */
static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink) {
	ir_node *block = rss->block;

	assert(! is_Proj(consumer) && "Cannot handle Projs");

	if (! is_Block(consumer) && get_nodes_block(consumer) == block) {
		if (! arch_irn_is(rss->arch_env, consumer, ignore) && ! plist_has_value(rss_irn->consumer_list, consumer)) {
			plist_insert_back(rss_irn->consumer_list, consumer);
			DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
		}
	}
	else {
		rss_irn->live_out = 1;
		DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
		if (! *got_sink) {
			plist_insert_back(rss_irn->consumer_list, _sink);
			*got_sink = 1;
			DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
		}
		DB((rss->dbg, LEVEL_2, "\n"));
	}
}

/**
 * Collect all nodes consuming the value(s) produced by current node.
 */
static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink) {
	const ir_edge_t *edge;
	int             i;
	ir_edge_kind_t  ekind[2]  = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
	rss_irn_t       *cur_node = get_rss_irn(rss, irn);

	if (cur_node->havecons)
		return;
	cur_node->havecons = 1;

	for (i = 0; i < 2; ++i) {
		foreach_out_edge_kind(irn, edge, ekind[i]) {
			ir_node *consumer = get_edge_src_irn(edge);

			if (is_Proj(consumer)) {
				//if (arch_get_irn_reg_class(rss->arch_env, consumer, -1) == rss->cls)
					collect_consumer(rss, rss_irn, consumer, got_sink);
			}
			else
				collect_single_consumer(rss, rss_irn, consumer, got_sink);
		}
	}
}

/**
 * Collects all consumer and descendant of a irn.
 */
static void collect_node_info(rss_t *rss, ir_node *irn) {
	static unsigned cur_desc_walk = 0;
	rss_irn_t       *rss_irn      = get_rss_irn(rss, irn);
	int             got_sink;

	assert(! is_Proj(irn) && "Cannot handle Projs.");

	/* check if node info is already available */
	if (rss_irn->handled)
		return;
		//phase_reinit_single_irn_data(&rss->ph, irn);

	DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));

	/* collect all consumer */
	got_sink = 0;
	collect_consumer(rss, rss_irn, irn, &got_sink);

	/* build sorted consumer array */
	rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));

	DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));

	/* collect descendants */
	got_sink = 0;
	collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);

	/* build sorted descendant array */
	rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));

	rss_irn->handled = 1;
}

/**
 * Checks if v is a potential killer of u.
 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
 *
 * @param rss   The rss object
 * @param v      The node to check for killer
 * @param u      The potentially killed value
 * @return 1 if v is in pkill(u), 0 otherwise
 */
static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u) {
	plist_t *list;
	ir_node **arr;
	plist_element_t *el;

	assert(is_Sink(v->irn) || ((plist_count(v->descendant_list) > 0 && v->descendants) || 1));
	assert(is_Sink(u->irn) || ((plist_count(u->consumer_list)   > 0 && u->consumer)    || 1));

	/* as we loop over the list: loop over the shorter one */
	if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
		list = u->consumer_list;
		arr  = v->descendants;
	}
	else {
		list = v->descendant_list;
		arr  = u->consumer;
	}

	/* for each list element: try to find element in array */
	foreach_plist(list, el) {
		ir_node *irn   = plist_element_get_value(el);
		ir_node *match = BSEARCH_IRN_ARR(irn, arr);

		if (match && match != irn)
			return 0;
	}

	return 1;
}

/**
 * Update descendants, consumer and pkiller list for the given irn.
 */
static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn) {
	rss_irn_t *node    = get_rss_irn(rss, irn);
	rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);

	/* add consumer and rebuild the consumer array */
	if (! plist_has_value(node->consumer_list, pk_irn)) {
		plist_insert_back(node->consumer_list, pk_irn);
		node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
	}

	/* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
	if (! plist_has_value(node->descendant_list, pk_irn)) {
		plist_element_t *el;

		plist_insert_back(node->descendant_list, pk_irn);

		foreach_plist(pkiller->descendant_list, el) {
			ir_node *desc = plist_element_get_value(el);

			if (! plist_has_value(node->descendant_list, desc))
				plist_insert_back(node->descendant_list, desc);
		}

		node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
	}

}

/**
 * Compute the potential killing set PK.
 */
static void compute_pkill_set(rss_t *rss) {
	plist_element_t *u_el, *v_el;

	foreach_plist(rss->nodes, u_el) {
		ir_node   *u_irn = plist_element_get_value(u_el);
		rss_irn_t *u     = get_rss_irn(rss, u_irn);

		DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));

		/* check each consumer if it is a potential killer  */
		foreach_plist(u->consumer_list, v_el) {
			ir_node   *v_irn = plist_element_get_value(v_el);
			rss_irn_t *v     = get_rss_irn(rss, v_irn);

			/* check, if v is a potential killer of u */
			if (is_potential_killer(rss, v, u)) {
				if (! plist_has_value(u->pkiller_list, v_irn))
					plist_insert_back(u->pkiller_list, v_irn);
				v->kill_count++;
				DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
			}
		}

		u->killer = _sink;
	}

	if (rss->opts->dump_flags & RSS_DUMP_PKG)
		debug_vcg_dump_pkg(rss, NULL, 0);
}

/**
 * Build set of killing edges (from values to their potential killers)
 */
static void build_kill_edges(rss_t *rss, pset *epk) {
	plist_element_t *el, *k_el;

	foreach_plist(rss->nodes, el) {
		ir_node    *irn  = plist_element_get_value(el);
		rss_irn_t *rirn = get_rss_irn(rss, irn);

		DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));

		foreach_plist(rirn->pkiller_list, k_el) {
			ir_node    *pkiller = plist_element_get_value(k_el);
			rss_edge_t *ke      = obstack_alloc(phase_obst(&rss->ph), sizeof(*ke));

			ke->src  = irn;
			ke->tgt  = pkiller;
			ke->next = NULL;

			DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));

			pset_insert(epk, ke, HASH_RSS_EDGE(ke));
		}
	}
}

/* print the given cbc for debugging purpose */
static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc) {
	ir_node    *n;
	rss_edge_t *ke;

	DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
	foreach_nodeset(cbc->parents, n) {
		DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
	}
	DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
	foreach_nodeset(cbc->children, n) {
		DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
	}
	DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
	foreach_pset(cbc->kill_edges, ke) {
		DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
	}
}

/**
 * Construct the bipartite decomposition.
 * Sid-Ahmed-Ali Touati, Phd Thesis
 * Register Pressure in Instruction Level Parallelism, p. 71
 */
static void compute_bipartite_decomposition(rss_t *rss) {
	pset *epk    = new_pset(cmp_rss_edges, 10);
	int  cur_num = 0;

	plist_element_t *el;

	DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));

	build_kill_edges(rss, epk);

	foreach_plist(rss->nodes, el) {
		ir_node   *u_irn   = plist_element_get_value(el);
		rss_irn_t *u       = get_rss_irn(rss, u_irn);
		int       p_change = 1;
		int       c_change = 1;

		cbc_t           *cbc;
		plist_element_t *el2;
		rss_edge_t      *k_edge;
		rss_edge_t      *kedge_root = NULL;
		ir_node         *t_irn, *s_irn;

		if (u->visited || u_irn == _sink)
			continue;

		DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));

		cbc     = obstack_alloc(phase_obst(&rss->ph), sizeof(*cbc));
		cbc->nr = cur_num++;

		/* initialize S_cb */
		cbc->parents = new_nodeset(5);
		nodeset_insert(cbc->parents, u_irn);
		DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));

		/* E_cb = empty */
		cbc->kill_edges = new_pset(cmp_rss_edges, 5);

		/* each parent gets killed by at least one value from children */

		/* T_cb = PK_successors(u) */
		cbc->children = new_nodeset(5);
		foreach_plist(u->pkiller_list, el2) {
			nodeset_insert(cbc->children, plist_element_get_value(el2));
			DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
		}

		/*
			Now: insert the parents of all children into the parent set
			and insert the children of all parents into the children set
			until the sets don't change any more
		*/
		while (p_change || c_change) {
			p_change = c_change = 0;

			/* accumulate parents */
			foreach_nodeset(cbc->children, t_irn) {
				foreach_pset(epk, k_edge) {
					ir_node *val = k_edge->src;

					if (k_edge->tgt == t_irn && ! nodeset_find(cbc->parents, val)) {
						nodeset_insert(cbc->parents, val);
						p_change = 1;
						DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents\n", val));
					}
				}
			}

			/* accumulate children */
			foreach_nodeset(cbc->parents, s_irn) {
				foreach_pset(epk, k_edge) {
					ir_node *val = k_edge->tgt;

					if (k_edge->src == s_irn  && ! nodeset_find(cbc->children, val)) {
						nodeset_insert(cbc->children, val);
						c_change = 1;
						DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children\n", val));
					}
				}
			}
		}

		/* mark all parent values as visited */
		foreach_nodeset(cbc->parents, s_irn) {
			rss_irn_t *s = get_rss_irn(rss, s_irn);
			s->visited = 1;
			/* assure bipartite property */
			if (nodeset_find(cbc->children, s_irn)) {
				nodeset_remove(cbc->children, s_irn);
				DBG((rss->dbg, LEVEL_3, "\t\t\t%+F removed from to children\n", s_irn));
			}
		}

		/* update edges */
		foreach_pset(epk, k_edge) {
			if (nodeset_find(cbc->parents, k_edge->src) && nodeset_find(cbc->children, k_edge->tgt)) {
				pset_insert(cbc->kill_edges, k_edge, HASH_RSS_EDGE(k_edge));
				/*
					Link all k_edges which are about to be removed together.
					Beware: pset_remove kills the iterator.
				*/
				k_edge->next = kedge_root;
				kedge_root   = k_edge;
			}
		}

		/* remove all linked k_edges */
		for (; kedge_root; kedge_root = kedge_root->next) {
			pset_remove(epk, kedge_root, HASH_RSS_EDGE(kedge_root));
		}

		/* add the connected bipartite component */
		if (nodeset_count(cbc->parents) > 0 && nodeset_count(cbc->children) > 0 && pset_count(cbc->kill_edges) > 0)
			pset_insert(rss->cbc_set, cbc, (unsigned)cbc->nr);
		DBG((rss->dbg, LEVEL_2, "\tbipartite component %d inserted:\n", cbc->nr));
		DEBUG_ONLY(
			if (firm_dbg_get_mask(rss->dbg) & LEVEL_2)
				debug_print_cbc(rss->dbg, cbc);
		);
	}

	if (rss->opts->dump_flags & RSS_DUMP_CBC)
		debug_vcg_dump_bipartite(rss);

	del_pset(epk);
}

/**
 * Select the child with the maximum cost.
 */
static child_t *select_child_max_cost(rss_t *rss, nodeset *x, nodeset *y, child_t *t, cbc_t *cbc) {
	ir_node *child;
	float   max_cost = -1.0f;

	DBG((rss->dbg, LEVEL_2, "\t\tcomputing children costs:\n"));

	foreach_nodeset(cbc->children, child) {