From 3553d48ad905f2af6c1120b9aa9a318fed181c29 Mon Sep 17 00:00:00 2001
From: Sebastian Hack <hack@ipd.info.uni-karlsruhe.de>
Date: Fri, 21 Apr 2006 15:38:00 +0000
Subject: [PATCH] Added new version of copy heuristic (still very alpha!)

---
 ir/be/becopyheur2.c | 540 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 540 insertions(+)
 create mode 100644 ir/be/becopyheur2.c

diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c
new file mode 100644
index 000000000..51bec74c6
--- /dev/null
+++ b/ir/be/becopyheur2.c
@@ -0,0 +1,540 @@
+
+/**
+ * More experiments on coalescing.
+ * @author Sebastian Hack
+ * @date   14.04.2006
+ */
+
+#include <stdlib.h>
+#include <limits.h>
+
+#include "list.h"
+#include "bitset.h"
+#include "debug.h"
+
+#include "irphase_t.h"
+#include "irgraph_t.h"
+#include "irnode_t.h"
+#include "irprintf.h"
+
+#include "beabi.h"
+#include "benode_t.h"
+#include "becopyopt.h"
+#include "becopyopt_t.h"
+#include "bechordal_t.h"
+
+typedef unsigned col_t;
+
+typedef struct _co2_irn_t co2_irn_t;
+
+typedef struct {
+	phase_t ph;
+	copy_opt_t *co;
+	bitset_t *ignore_regs;
+	co2_irn_t *touched;
+	DEBUG_ONLY(firm_dbg_module_t *dbg;)
+} co2_t;
+
+struct _co2_irn_t {
+	ir_node       *irn;
+	co2_irn_t     *touched_next;
+	int            costs;
+	col_t          tmp_col;
+	col_t          orig_col;
+	unsigned       fixed     : 1;
+	unsigned       tmp_fixed : 1;
+	struct list_head changed_list;
+};
+
+#define get_co2_irn(co2, irn)   ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
+
+static void co2_irn_init(phase_t *ph, ir_node *irn, void *data)
+{
+	co2_t *env    = (co2_t *) ph;
+	co2_irn_t *ci = data;
+
+	memset(ci, 0, sizeof(ci[0]));
+	INIT_LIST_HEAD(&ci->changed_list);
+	ci->irn          = irn;
+	ci->touched_next = env->touched;
+	ci->orig_col     = get_irn_col(env->co, irn);
+	env->touched     = ci;
+}
+
+
+static int co2_irn_cmp(const void *a, const void *b)
+{
+	const co2_irn_t **p = a;
+	const co2_irn_t **q = b;
+	return (*q)->costs - (*p)->costs;
+}
+
+typedef struct {
+	col_t col;
+	int costs;
+} col_cost_pair_t;
+
+/**
+ * An order on color/costs pairs.
+ * If the costs are equal, we use the color as a kind of normalization.
+ */
+static int col_cost_pair_lt(const void *a, const void *b)
+{
+	const col_cost_pair_t *p = a;
+	const col_cost_pair_t *q = b;
+	int cost_diff = p->costs - q->costs;
+
+	return cost_diff;
+	// return cost_diff != 0 ? cost_diff : p->col - q->col;
+}
+
+static col_t get_col(co2_t *env, ir_node *irn)
+{
+	co2_irn_t *ci = get_co2_irn(env, irn);
+	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
+}
+
+static INLINE color_is_fix(co2_t *env, ir_node *irn)
+{
+	co2_irn_t *ci = get_co2_irn(env, irn);
+	return ci->fixed || ci->tmp_fixed;
+}
+
+static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
+{
+	bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
+	arch_register_req_t req;
+
+	arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
+
+	if(arch_register_req_is(&req, limited)) {
+		bitset_pos_t elm;
+		int n_constr;
+
+		req.limited(req.limited_env, aux);
+		n_constr = bitset_popcnt(aux);
+		bitset_foreach(aux, elm)
+			col_costs[elm].costs += costs / n_constr;
+	}
+}
+
+/**
+ * Determine costs which shall indicate how cheap/expensive it is to try
+ * to assign a node some color.
+ * The costs are computed for all colors. INT_MAX means that it is impossible
+ * to give the node that specific color.
+ *
+ * @param env       The co2 this pointer.
+ * @param irn       The node.
+ * @param col_costs An array of colors x costs where the costs are written to.
+ */
+static void determine_color_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs)
+{
+	be_ifg_t *ifg      = env->co->cenv->ifg;
+	int n_regs         = env->co->cls->n_regs;
+	bitset_t *forb     = bitset_alloca(n_regs);
+	affinity_node_t *a = get_affinity_info(env->co, irn);
+
+	arch_register_req_t req;
+	bitset_pos_t elm;
+	ir_node *pos;
+	void *it;
+	int i;
+
+	/* Put all forbidden colors into the aux bitset. */
+	arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
+	if(arch_register_req_is(&req, limited)) {
+		req.limited(req.limited_env, forb);
+		bitset_flip_all(forb);
+	}
+	else
+		bitset_copy(forb, env->ignore_regs);
+
+	for(i = 0; i < n_regs; ++i) {
+		col_costs[i].col   = i;
+		col_costs[i].costs = 0;
+	}
+
+	if(a) {
+		neighb_t *n;
+
+		co_gs_foreach_neighb(a, n) {
+			co2_irn_t *ni = get_co2_irn(env, n->irn);
+
+			if(ni->fixed) {
+				col_t col = get_col(env, n->irn);
+				col_costs[col].costs -= 100 * n->costs;
+			}
+
+			incur_constraint_costs(env, n->irn, col_costs, -n->costs);
+		}
+	}
+
+	it = be_ifg_neighbours_iter_alloca(ifg);
+	be_ifg_foreach_neighbour(ifg, it, irn, pos) {
+		col_t col = get_col(env, pos);
+		if(color_is_fix(env, pos))
+			col_costs[col].costs = INT_MAX;
+		else {
+			incur_constraint_costs(env, pos, col_costs, INT_MAX);
+			col_costs[col].costs++;
+		}
+	}
+
+	/* Set the costs to infinity for each color which is not allowed at this node. */
+	bitset_foreach(forb, elm)
+		col_costs[elm].costs = INT_MAX;
+
+}
+
+static int curr_costs(co2_t *env, affinity_node_t *a)
+{
+	col_t a_col = get_col(env, a->irn);
+	int costs   = 0;
+	neighb_t *n;
+
+	co_gs_foreach_neighb(a, n) {
+		col_t n_col = get_col(env, n->irn);
+		costs += n_col != a_col ? n->costs : 0;
+	}
+
+	return costs;
+}
+
+static void reject_coloring(struct list_head *h)
+{
+	co2_irn_t *pos;
+
+	list_for_each_entry(co2_irn_t, pos, h, changed_list)
+		pos->tmp_fixed = 0;
+}
+
+static void materialize_coloring(co2_t *env, struct list_head *h)
+{
+	const arch_register_class_t *cls = env->co->cls;
+	const arch_env_t *aenv           = env->co->aenv;
+	co2_irn_t *pos;
+
+	list_for_each_entry(co2_irn_t, pos, h, changed_list) {
+		pos->orig_col = pos->tmp_col;
+		pos->tmp_fixed = 0;
+	}
+}
+
+static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
+
+
+static INLINE int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, int n_regs, struct list_head *parent_changed, int depth)
+{
+	be_ifg_t *ifg = env->co->cenv->ifg;
+	co2_irn_t *ci = get_co2_irn(env, irn);
+	int res       = 0;
+
+	int i;
+
+	for(i = 0; i < n_regs; ++i) {
+		col_t tgt_col  = col_list[i].col;
+		unsigned costs = col_list[i].costs;
+		int neigh_ok   = 1;
+
+		struct list_head changed;
+		ir_node *n;
+		void *it;
+
+		DBG((env->dbg, LEVEL_2, "\t%2Dtrying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
+
+		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
+		if(costs == INT_MAX) {
+			ci->tmp_fixed = 0;
+			return 0;
+		}
+
+		/* Set the new color of the node and mark the node as temporarily fixed. */
+		ci->tmp_col   = tgt_col;
+		ci->tmp_fixed = 1;
+
+		/*
+		If that color has costs > 0, there's at least one neighbor having that color,
+		so we will try to change the neighbors' colors, too.
+		*/
+		INIT_LIST_HEAD(&changed);
+		list_add(&ci->changed_list, &changed);
+
+		it = be_ifg_neighbours_iter_alloca(ifg);
+		be_ifg_foreach_neighbour(ifg, it, irn, n) {
+
+			/* try to re-color the neighbor if it has the target color. */
+			if(get_col(env, n) == tgt_col) {
+				struct list_head tmp;
+
+				/*
+				Try to change the color of the neighbor and record all nodes which
+				get changed in the tmp list. Add this list to the "changed" list for
+				that color. If we did not succeed to change the color of the neighbor,
+				we bail out and try the next color.
+				*/
+				INIT_LIST_HEAD(&tmp);
+				neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
+				list_splice(&tmp, &changed);
+				if(!neigh_ok)
+					break;
+			}
+		}
+
+
+		/*
+		We managed to assign the target color to all neighbors, so from the perspective
+		of the current node, every thing was ok and we can return safely.
+		*/
+		if(neigh_ok) {
+			DBG((env->dbg, LEVEL_2, "\t%2Dcolor %d(%d) was ok\n", depth, tgt_col, costs));
+			list_splice(&changed, parent_changed);
+			res = 1;
+			break;
+		}
+
+		/*
+		If not, that color did not succeed and we unfix all nodes we touched
+		by traversing the changed list and setting tmp_fixed to 0 for these nodes.
+		*/
+		else
+			reject_coloring(&changed);
+	}
+
+	return res;
+}
+
+static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
+{
+	co2_irn_t *ci = get_co2_irn(env, irn);
+	int res       = 0;
+	col_t col     = get_col(env, irn);
+
+	DBG((env->dbg, LEVEL_2, "\t%2Dclearing %+F(%d) of color %d\n", depth, irn, col, not_col));
+
+	/* the node does not have to forbidden color. That's fine, mark it as visited and return. */
+	if(col != not_col) {
+		if(!ci->tmp_fixed) {
+			ci->tmp_col   = col;
+			ci->tmp_fixed = 1;
+		}
+
+		list_add(&ci->changed_list, parent_changed);
+		return 1;
+	}
+
+	/* The node has the color it should not have _and_ has not been visited yet. */
+	if(!color_is_fix(env, irn)) {
+		int n_regs            = env->co->cls->n_regs;
+		col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
+
+		/* Get the costs for giving the node a specific color. */
+		determine_color_costs(env, irn, csts);
+
+		/* Since the node must not have the not_col, set the costs for that color to "infinity" */
+		csts[not_col].costs = INT_MAX;
+
+		/* sort the colors according costs, cheapest first. */
+		qsort(csts, n_regs, sizeof(csts[0]), col_cost_pair_lt);
+
+		/* Try recoloring the node using the color list. */
+		res = recolor(env, irn, csts, n_regs, parent_changed, depth);
+	}
+
+	/* If we came here, everything went ok. */
+	return res;
+}
+
+/**
+ * Try to bring a node to a certain color.
+ */
+static int try_color(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *changed)
+{
+	co2_irn_t *ci = get_co2_irn(env, irn);
+	be_ifg_t *ifg = env->co->cenv->ifg;
+
+	ir_node *n;
+	void *it;
+
+	ci->tmp_fixed = 1;
+	ci->tmp_col   = tgt_col;
+	list_add(&ci->changed_list, changed);
+
+	it = be_ifg_neighbours_iter_alloca(ifg);
+	be_ifg_foreach_neighbour(ifg, it, irn, n) {
+		col_t c = get_col(env, n);
+
+		/* If the neighbor has the target color, re-color the neighbor. */
+		if(c == tgt_col) {
+			int ok = change_color_not(env, n, tgt_col, changed, 1);
+			if(!ok)
+				return 0;
+		}
+	}
+
+	return 1;
+}
+
+static INLINE int costs_sufficient(co2_irn_t *irn, int costs)
+{
+	return costs == -irn->costs;
+}
+
+static void process_affinity_node(co2_t *env, co2_irn_t *ci)
+{
+	int n_regs               = env->co->cls->n_regs;
+	col_cost_pair_t *col_seq = alloca(n_regs * sizeof(col_seq[0]));
+	affinity_node_t *a       = get_affinity_info(env->co, ci->irn);
+	int best_cost            = curr_costs(env, a);
+	col_t best_col           = ci->orig_col;
+
+	neighb_t *n;
+	int i;
+
+	assert(a != NULL && "This node must be an affinity node");
+
+	/* If that node has already been fixed, leave it alone. */
+	if(ci->fixed)
+		return;
+
+	DB((env->dbg, LEVEL_1, "affinity node %+F cost %d\n", ci->irn, ci->costs));
+
+	/* determine the order in which the colors shall be tried. */
+	determine_color_costs(env, ci->irn, col_seq);
+	qsort(col_seq, n_regs, sizeof(col_seq[0]), col_cost_pair_lt);
+
+	/* Try the colors. */
+	for(i = 0; i < n_regs; ++i) {
+		col_t col = col_seq[i].col;
+		int costs = col_seq[i].costs;
+
+		struct list_head changed;
+		int ok;
+
+		DB((env->dbg, LEVEL_2, "\tbest color %d incurring costs %d\n", best_col, best_cost));
+
+		/* Also, if the costs are not more optimizable, we do not try additional colors and finish this node. */
+		if(best_cost == 0)
+			break;
+
+		if(costs == INT_MAX) {
+			DB((env->dbg, LEVEL_1, "\tall following colors after %d will be infeasible\n", col));
+			break;
+		}
+
+		INIT_LIST_HEAD(&changed);
+
+		DB((env->dbg, LEVEL_1, "\ttrying color %d costing %d\n", col, costs));
+
+		/* try to assign the same color to the node and all its neighbors. */
+		ok = try_color(env, a->irn, col, &changed);
+
+		if(!ok) {
+			DBG((env->dbg, LEVEL_2, "\t-> failed.\n"));
+			reject_coloring(&changed);
+			continue;
+		}
+
+		/*
+		Evaluate the recoloring and mark it is as new best if it was better
+		as the best current known solution.
+		*/
+		costs = curr_costs(env, a);
+		DBG((env->dbg, LEVEL_2, "\t-> cost: %d\n", costs));
+
+		if(costs < best_cost) {
+			best_cost = costs;
+			best_col  = col;
+
+			materialize_coloring(env, &changed);
+		}
+
+		/* If we had a better coloring already, reject the current one. */
+		else
+			reject_coloring(&changed);
+
+	}
+
+	/* We found the definite color for this node, so fix it. */
+	ci->fixed = 1;
+
+	DB((env->dbg, LEVEL_1, "\tusing %d(%d)\n", best_col, best_cost));
+
+	/* Now, investigate all affinity neighbors of this node. */
+	if(0) {
+		co2_irn_t **neighbors = alloca(a->degree * sizeof(neighbors[0]));
+
+		i = 0;
+		co_gs_foreach_neighb(a, n)
+			neighbors[i++] = get_co2_irn(env, n->irn);
+
+		qsort(neighbors, a->degree, sizeof(neighbors[0]), co2_irn_cmp);
+		for(i = 0; i < a->degree; ++i)
+			process_affinity_node(env, neighbors[i]);
+	}
+}
+
+static void process(co2_t *env)
+{
+	struct obstack obst;
+	affinity_node_t *an;
+	co2_irn_t **nodes;
+	int i, n;
+
+	obstack_init(&obst);
+
+	n = 0;
+	co_gs_foreach_aff_node(env->co, an) {
+		ir_node *irn   = an->irn;
+		co2_irn_t *ci  = get_co2_irn(env, irn);
+
+		neighb_t *neighb;
+
+		co_gs_foreach_neighb(an, neighb)
+			ci->costs += neighb->costs;
+
+		obstack_ptr_grow(&obst, ci);
+		n++;
+	}
+
+	nodes = obstack_finish(&obst);
+
+	/* sort the nodes according to processing order. */
+	qsort(nodes, n, sizeof(nodes[0]), co2_irn_cmp);
+
+	for(i = 0; i < n; ++i) {
+		if(!nodes[i]->fixed)
+			process_affinity_node(env, nodes[i]);
+	}
+
+	obstack_free(&obst, NULL);
+}
+
+static void writeback_colors(co2_t *env)
+{
+	const arch_env_t *aenv = env->co->aenv;
+	co2_irn_t *irn;
+
+	for(irn = env->touched; irn; irn = irn->touched_next) {
+		const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
+		arch_set_irn_register(aenv, irn->irn, reg);
+	}
+}
+
+void co_solve_heuristic_new(copy_opt_t *co)
+{
+	co2_t env;
+
+	phase_init(&env.ph, "co2", co->cenv->birg->irg, sizeof(co2_irn_t), PHASE_DEFAULT_GROWTH, co2_irn_init);
+	env.touched     = NULL;
+	env.co          = co;
+	env.ignore_regs = bitset_alloca(co->cls->n_regs);
+	arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
+	bitset_flip_all(env.ignore_regs);
+	be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
+	FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
+
+	process(&env);
+	writeback_colors(&env);
+	phase_free(&env.ph);
+}
-- 
2.20.1