X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=brute_force.c;h=a1631260ba5db85b18c841a5ce069819dcec1051;hb=5b64da5ba16ded414f572766bb2d50673cb63d2a;hp=d5e15aa6f5d64fd16892a8955bef6f51de6c369e;hpb=f723e9a536df09b809a7e860c152cc6e3435cc05;p=libfirm

diff --git a/brute_force.c b/brute_force.c
index d5e15aa6f..a1631260b 100644
--- a/brute_force.c
+++ b/brute_force.c
@@ -43,6 +43,10 @@
 #include "pbqp_node_t.h"
 #include "vector.h"
 
+#if KAPS_STATISTIC
+static int dump = 0;
+#endif
+
 /* Forward declarations. */
 static void apply_Brute_Force(pbqp *pbqp);
 
@@ -138,7 +142,7 @@ static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 	return min_index;
 }
 
-void apply_Brute_Force(pbqp *pbqp)
+static void apply_Brute_Force(pbqp *pbqp)
 {
 	pbqp_node   *node         = NULL;
 	unsigned     min_index    = 0;
@@ -187,6 +191,162 @@ void apply_Brute_Force(pbqp *pbqp)
 	select_alternative(node, min_index);
 }
 
+
+
+static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
+{
+	pbqp_edge   *edge;
+	pbqp_node   *other;
+	pbqp_matrix *mat;
+	vector      *vec;
+	int          is_src;
+
+	assert(pbqp);
+	assert(node);
+
+	edge = node->edges[0];
+	mat = edge->costs;
+	is_src = edge->src == node;
+	vec = node->costs;
+
+	if (is_src) {
+		other = edge->tgt;
+		assert(other);
+
+		/* Update pointer for brute force solver. */
+		other = pbqp->nodes[other->index];
+
+		node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
+	} else {
+		other = edge->src;
+		assert(other);
+
+		/* Update pointer for brute force solver. */
+		other = pbqp->nodes[other->index];
+
+		node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
+	}
+
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
+	}
+#endif
+}
+
+static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
+{
+	pbqp_edge   *src_edge   = node->edges[0];
+	pbqp_edge   *tgt_edge   = node->edges[1];
+	int          src_is_src = src_edge->src == node;
+	int          tgt_is_src = tgt_edge->src == node;
+	pbqp_matrix *src_mat;
+	pbqp_matrix *tgt_mat;
+	pbqp_node   *src_node;
+	pbqp_node   *tgt_node;
+	vector      *vec;
+	vector      *node_vec;
+	unsigned     col_index;
+	unsigned     row_index;
+
+	assert(pbqp);
+
+	if (src_is_src) {
+		src_node = src_edge->tgt;
+	} else {
+		src_node = src_edge->src;
+	}
+
+	if (tgt_is_src) {
+		tgt_node = tgt_edge->tgt;
+	} else {
+		tgt_node = tgt_edge->src;
+	}
+
+	/* Swap nodes if necessary. */
+	if (tgt_node->index < src_node->index) {
+		pbqp_node *tmp_node;
+		pbqp_edge *tmp_edge;
+
+		tmp_node = src_node;
+		src_node = tgt_node;
+		tgt_node = tmp_node;
+
+		tmp_edge = src_edge;
+		src_edge = tgt_edge;
+		tgt_edge = tmp_edge;
+
+		src_is_src = src_edge->src == node;
+		tgt_is_src = tgt_edge->src == node;
+	}
+
+	/* Update pointer for brute force solver. */
+	src_node = pbqp->nodes[src_node->index];
+	tgt_node = pbqp->nodes[tgt_node->index];
+
+	src_mat = src_edge->costs;
+	tgt_mat = tgt_edge->costs;
+
+	node_vec = node->costs;
+
+	row_index = src_node->solution;
+	col_index = tgt_node->solution;
+
+	vec = vector_copy(pbqp, node_vec);
+
+	if (src_is_src) {
+		vector_add_matrix_col(vec, src_mat, row_index);
+	} else {
+		vector_add_matrix_row(vec, src_mat, row_index);
+	}
+
+	if (tgt_is_src) {
+		vector_add_matrix_col(vec, tgt_mat, col_index);
+	} else {
+		vector_add_matrix_row(vec, tgt_mat, col_index);
+	}
+
+	node->solution = vector_get_min_index(vec);
+
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
+	}
+#endif
+
+	obstack_free(&pbqp->obstack, vec);
+}
+
+static void back_propagate_brute_force(pbqp *pbqp)
+{
+	unsigned node_index;
+	unsigned node_len   = node_bucket_get_length(reduced_bucket);
+
+	assert(pbqp);
+
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		dump_section(pbqp->dump_file, 2, "Back Propagation");
+	}
+#endif
+
+	for (node_index = node_len; node_index > 0; --node_index) {
+		pbqp_node *node = reduced_bucket[node_index - 1];
+
+		switch (pbqp_node_get_degree(node)) {
+			case 1:
+				back_propagate_RI(pbqp, node);
+				break;
+			case 2:
+				back_propagate_RII(pbqp, node);
+				break;
+			default:
+				panic("Only nodes with degree one or two should be in this bucket");
+				break;
+		}
+	}
+}
+
 void solve_pbqp_brute_force(pbqp *pbqp)
 {
 	/* Reduce nodes degree ... */
@@ -207,14 +367,20 @@ void solve_pbqp_brute_force(pbqp *pbqp)
 
 #if KAPS_STATISTIC
 	fh = fopen("solutions.pb", "a");
-	fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
-			pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
-			pbqp->num_bf);
+	#if KAPS_USE_UNSIGNED
+		fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
+				pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+				pbqp->num_rm, pbqp->num_rn);
+	#else
+		fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
+				pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+				pbqp->num_rm, pbqp->num_bf);
+	#endif
 	fclose(fh);
 #endif
 
 	/* Solve reduced nodes. */
-	back_propagate(pbqp);
+	back_propagate_brute_force(pbqp);
 
 	free_buckets();
 }