X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=optimal.c;h=9d6d2b619939de9cd4b1de85193c6757ec9333e0;hb=48aa7d4df41739507dec1350eadb0b459550455e;hp=6cf744db168d6d747018085168f6081f5eccf3cc;hpb=5b64da5ba16ded414f572766bb2d50673cb63d2a;p=libfirm

diff --git a/optimal.c b/optimal.c
index 6cf744db1..9d6d2b619 100644
--- a/optimal.c
+++ b/optimal.c
@@ -50,7 +50,8 @@ pbqp_edge **edge_bucket;
 pbqp_edge **rm_bucket;
 pbqp_node **node_buckets[4];
 pbqp_node **reduced_bucket = NULL;
-static int         buckets_filled = 0;
+pbqp_node  *merged_node = NULL;
+static int  buckets_filled = 0;
 
 static void insert_into_edge_bucket(pbqp_edge *edge)
 {
@@ -109,8 +110,8 @@ void fill_node_buckets(pbqp *pbqp)
 	node_len = pbqp->num_nodes;
 
 	#if KAPS_TIMING
-		ir_timer_t *t_fill_buckets = ir_timer_register("be_pbqp_fill_buckets", "PBQP Fill Nodes into buckets");
-		ir_timer_reset_and_start(t_fill_buckets);
+		ir_timer_t *t_fill_buckets = ir_timer_new();
+		ir_timer_start(t_fill_buckets);
 	#endif
 
 	for (node_index = 0; node_index < node_len; ++node_index) {
@@ -133,7 +134,7 @@ void fill_node_buckets(pbqp *pbqp)
 
 	#if KAPS_TIMING
 		ir_timer_stop(t_fill_buckets);
-		printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_fill_buckets), (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
+		printf("PBQP Fill Nodes into buckets: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
 	#endif
 }
 
@@ -144,9 +145,10 @@ static void normalize_towards_source(pbqp_edge *edge)
 	pbqp_node      *tgt_node;
 	vector         *src_vec;
 	vector         *tgt_vec;
-	int             src_len;
-	int             tgt_len;
-	int             src_index;
+	unsigned        src_len;
+	unsigned        tgt_len;
+	unsigned        src_index;
+	unsigned        new_infinity = 0;
 
 	assert(edge);
 
@@ -175,22 +177,28 @@ static void normalize_towards_source(pbqp_edge *edge)
 		if (min != 0) {
 			if (src_vec->entries[src_index].data == INF_COSTS) {
 				pbqp_matrix_set_row_value(mat, src_index, 0);
-			} else {
-				pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
+				continue;
 			}
+
+			pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 			src_vec->entries[src_index].data = pbqp_add(
 					src_vec->entries[src_index].data, min);
 
 			if (min == INF_COSTS) {
-				unsigned edge_index;
-				unsigned edge_len = pbqp_node_get_degree(src_node);
-
-				for (edge_index = 0; edge_index < edge_len; ++edge_index) {
-					pbqp_edge *edge_candidate = src_node->edges[edge_index];
-					if (edge_candidate != edge) {
-						insert_into_edge_bucket(edge_candidate);
-					}
-				}
+				new_infinity = 1;
+			}
+		}
+	}
+
+	if (new_infinity) {
+		unsigned edge_index;
+		unsigned edge_len = pbqp_node_get_degree(src_node);
+
+		for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+			pbqp_edge *edge_candidate = src_node->edges[edge_index];
+
+			if (edge_candidate != edge) {
+				insert_into_edge_bucket(edge_candidate);
 			}
 		}
 	}
@@ -203,9 +211,10 @@ static void normalize_towards_target(pbqp_edge *edge)
 	pbqp_node      *tgt_node;
 	vector         *src_vec;
 	vector         *tgt_vec;
-	int             src_len;
-	int             tgt_len;
-	int             tgt_index;
+	unsigned        src_len;
+	unsigned        tgt_len;
+	unsigned        tgt_index;
+	unsigned        new_infinity = 0;
 
 	assert(edge);
 
@@ -227,28 +236,35 @@ static void normalize_towards_target(pbqp_edge *edge)
 	mat = edge->costs;
 	assert(mat);
 
+	/* Normalize towards target node. */
 	for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 		num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 
 		if (min != 0) {
 			if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 				pbqp_matrix_set_col_value(mat, tgt_index, 0);
-			} else {
-				pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
+				continue;
 			}
+
+			pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 			tgt_vec->entries[tgt_index].data = pbqp_add(
 					tgt_vec->entries[tgt_index].data, min);
 
 			if (min == INF_COSTS) {
-				unsigned edge_index;
-				unsigned edge_len = pbqp_node_get_degree(tgt_node);
-
-				for (edge_index = 0; edge_index < edge_len; ++edge_index) {
-					pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
-					if (edge_candidate != edge) {
-						insert_into_edge_bucket(edge_candidate);
-					}
-				}
+				new_infinity = 1;
+			}
+		}
+	}
+
+	if (new_infinity) {
+		unsigned edge_index;
+		unsigned edge_len = pbqp_node_get_degree(tgt_node);
+
+		for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+			pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
+
+			if (edge_candidate != edge) {
+				insert_into_edge_bucket(edge_candidate);
 			}
 		}
 	}
@@ -332,6 +348,14 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 	pbqp->num_rm++;
 #endif
 
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		char txt[100];
+		sprintf(txt, "Merging n%d into n%d", src_node->index, tgt_node->index);
+		dump_section(pbqp->dump_file, 3, txt);
+	}
+#endif
+
 	/* Reconnect the source's edges with the target node. */
 	for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 		pbqp_edge   *old_edge = src_node->edges[edge_index];
@@ -353,11 +377,11 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 		assert(old_matrix);
 
 		if (old_edge->tgt == src_node) {
-			other_node = edge->src;
+			other_node = old_edge->src;
 			other_len  = old_matrix->rows;
 		}
 		else {
-			other_node = edge->tgt;
+			other_node = old_edge->tgt;
 			other_len = old_matrix->cols;
 		}
 		assert(other_node);
@@ -398,18 +422,26 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 			}
 		}
 
+		new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+
 		add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
 
+		if (new_edge == NULL) {
+			reorder_node_after_edge_insertion(tgt_node);
+			reorder_node_after_edge_insertion(other_node);
+		}
+
 		delete_edge(old_edge);
-		reorder_node(src_node);
-		reorder_node(other_node);
 
 		new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+		simplify_edge(pbqp, new_edge);
+
 		insert_into_rm_bucket(new_edge);
 	}
 
-	/* Reduce the remaining source node via RI. */
-	apply_RI(pbqp);
+#if KAPS_STATISTIC
+	pbqp->num_r1--;
+#endif
 }
 
 /**
@@ -490,6 +522,14 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 	pbqp->num_rm++;
 #endif
 
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		char txt[100];
+		sprintf(txt, "Merging n%d into n%d", tgt_node->index, src_node->index);
+		dump_section(pbqp->dump_file, 3, txt);
+	}
+#endif
+
 	/* Reconnect the target's edges with the source node. */
 	for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 		pbqp_edge   *old_edge = tgt_node->edges[edge_index];
@@ -511,11 +551,11 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 		assert(old_matrix);
 
 		if (old_edge->tgt == tgt_node) {
-			other_node = edge->src;
+			other_node = old_edge->src;
 			other_len  = old_matrix->rows;
 		}
 		else {
-			other_node = edge->tgt;
+			other_node = old_edge->tgt;
 			other_len = old_matrix->cols;
 		}
 		assert(other_node);
@@ -556,18 +596,26 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 			}
 		}
 
+		new_edge = get_edge(pbqp, src_node->index, other_node->index);
+
 		add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
 
+		if (new_edge == NULL) {
+			reorder_node_after_edge_insertion(src_node);
+			reorder_node_after_edge_insertion(other_node);
+		}
+
 		delete_edge(old_edge);
-		reorder_node(tgt_node);
-		reorder_node(other_node);
 
 		new_edge = get_edge(pbqp, src_node->index, other_node->index);
+		simplify_edge(pbqp, new_edge);
+
 		insert_into_rm_bucket(new_edge);
 	}
 
-	/* Reduce the remaining source node via RI. */
-	apply_RI(pbqp);
+#if KAPS_STATISTIC
+	pbqp->num_r1--;
+#endif
 }
 
 /**
@@ -597,14 +645,17 @@ void apply_RM(pbqp *pbqp, pbqp_node *node)
 		pbqp_edge *edge = edge_bucket_pop(&rm_bucket);
 		assert(edge);
 
+		/* If the edge is not deleted: Try a merge. */
 		if (edge->src == node)
 			merge_target_into_source(pbqp, edge);
-		else
+		else if (edge->tgt == node)
 			merge_source_into_target(pbqp, edge);
 	}
+
+	merged_node = node;
 }
 
-void reorder_node(pbqp_node *node)
+void reorder_node_after_edge_deletion(pbqp_node *node)
 {
 	unsigned    degree     = pbqp_node_get_degree(node);
 	/* Assume node lost one incident edge. */
@@ -615,11 +666,23 @@ void reorder_node(pbqp_node *node)
 	/* Same bucket as before */
 	if (degree > 2) return;
 
-	if (!node_bucket_contains(node_buckets[old_degree], node)) {
-		/* Old arity is new arity, so we have nothing to do. */
-		assert(node_bucket_contains(node_buckets[degree], node));
-		return;
-	}
+	/* Delete node from old bucket... */
+	node_bucket_remove(&node_buckets[old_degree], node);
+
+	/* ..and add to new one. */
+	node_bucket_insert(&node_buckets[degree], node);
+}
+
+void reorder_node_after_edge_insertion(pbqp_node *node)
+{
+	unsigned    degree     = pbqp_node_get_degree(node);
+	/* Assume node lost one incident edge. */
+	unsigned    old_degree = degree - 1;
+
+	if (!buckets_filled) return;
+
+	/* Same bucket as before */
+	if (old_degree > 2) return;
 
 	/* Delete node from old bucket... */
 	node_bucket_remove(&node_buckets[old_degree], node);
@@ -641,13 +704,15 @@ void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 	assert(pbqp);
 	assert(edge);
 
+	(void) pbqp;
+
 	src_node = edge->src;
 	tgt_node = edge->tgt;
 	assert(src_node);
 	assert(tgt_node);
 
 	/* If edge are already deleted, we have nothing to do. */
-	if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
+	if (is_deleted(edge))
 		return;
 
 #if	KAPS_DUMP
@@ -700,8 +765,6 @@ void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 #endif
 
 		delete_edge(edge);
-		reorder_node(src_node);
-		reorder_node(tgt_node);
 	}
 }
 
@@ -713,8 +776,8 @@ void initial_simplify_edges(pbqp *pbqp)
 	assert(pbqp);
 
 	#if KAPS_TIMING
-		ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
-		ir_timer_reset_and_start(t_int_simpl);
+		ir_timer_t *t_int_simpl = ir_timer_new();
+		ir_timer_start(t_int_simpl);
 	#endif
 
 #if	KAPS_DUMP
@@ -752,7 +815,7 @@ void initial_simplify_edges(pbqp *pbqp)
 
 	#if KAPS_TIMING
 		ir_timer_stop(t_int_simpl);
-		printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
+		printf("PBQP Initial simplify edges:  %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 	#endif
 }
 
@@ -763,7 +826,7 @@ num determine_solution(pbqp *pbqp)
 	num      solution   = 0;
 
 	#if KAPS_TIMING
-		ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
+		ir_timer_t *t_det_solution = ir_timer_new();
 		ir_timer_reset_and_start(t_det_solution);
 	#endif
 
@@ -773,6 +836,8 @@ num determine_solution(pbqp *pbqp)
 
 	assert(pbqp);
 
+	(void) pbqp;
+
 #if	KAPS_DUMP
 	file = pbqp->dump_file;
 
@@ -818,7 +883,7 @@ num determine_solution(pbqp *pbqp)
 
 	#if KAPS_TIMING
 		ir_timer_stop(t_det_solution);
-		printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
+		printf("PBQP Determine Solution:      %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 	#endif
 
 	return solution;
@@ -835,6 +900,8 @@ static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 	assert(pbqp);
 	assert(node);
 
+	(void) pbqp;
+
 	edge = node->edges[0];
 	mat = edge->costs;
 	is_src = edge->src == node;
@@ -1021,7 +1088,7 @@ void apply_RI(pbqp *pbqp)
 	}
 #endif
 
-	reorder_node(other_node);
+	reorder_node_after_edge_deletion(other_node);
 
 #if KAPS_STATISTIC
 	pbqp->num_r1++;
@@ -1157,8 +1224,8 @@ void apply_RII(pbqp *pbqp)
 		/* Free local matrix. */
 		obstack_free(&pbqp->obstack, mat);
 
-		reorder_node(src_node);
-		reorder_node(tgt_node);
+		reorder_node_after_edge_deletion(src_node);
+		reorder_node_after_edge_deletion(tgt_node);
 	}
 
 #if	KAPS_DUMP
@@ -1172,6 +1239,119 @@ void apply_RII(pbqp *pbqp)
 	simplify_edge(pbqp, edge);
 }
 
+static void select_column(pbqp_edge *edge, unsigned col_index)
+{
+	pbqp_matrix    *mat;
+	pbqp_node      *src_node;
+	pbqp_node      *tgt_node;
+	vector         *src_vec;
+	vector         *tgt_vec;
+	unsigned        src_len;
+	unsigned        tgt_len;
+	unsigned        src_index;
+	unsigned        new_infinity = 0;
+
+	assert(edge);
+
+	src_node = edge->src;
+	tgt_node = edge->tgt;
+	assert(src_node);
+	assert(tgt_node);
+
+	src_vec = src_node->costs;
+	tgt_vec = tgt_node->costs;
+	assert(src_vec);
+	assert(tgt_vec);
+
+	src_len = src_vec->len;
+	tgt_len = tgt_vec->len;
+	assert(src_len > 0);
+	assert(tgt_len > 0);
+
+	mat = edge->costs;
+	assert(mat);
+
+	for (src_index = 0; src_index < src_len; ++src_index) {
+		num elem = mat->entries[src_index * tgt_len + col_index];
+
+		if (elem != 0) {
+			if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
+				new_infinity = 1;
+
+			src_vec->entries[src_index].data = pbqp_add(
+					src_vec->entries[src_index].data, elem);
+		}
+	}
+
+	if (new_infinity) {
+		unsigned edge_index;
+		unsigned edge_len = pbqp_node_get_degree(src_node);
+
+		for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+			pbqp_edge *edge_candidate = src_node->edges[edge_index];
+
+			if (edge_candidate != edge) {
+				insert_into_edge_bucket(edge_candidate);
+			}
+		}
+	}
+
+	delete_edge(edge);
+}
+
+static void select_row(pbqp_edge *edge, unsigned row_index)
+{
+	pbqp_matrix    *mat;
+	pbqp_node      *src_node;
+	pbqp_node      *tgt_node;
+	vector         *tgt_vec;
+	unsigned        tgt_len;
+	unsigned        tgt_index;
+	unsigned        new_infinity = 0;
+
+	assert(edge);
+
+	src_node = edge->src;
+	tgt_node = edge->tgt;
+	assert(tgt_node);
+
+	tgt_vec = tgt_node->costs;
+	assert(tgt_vec);
+
+	tgt_len = tgt_vec->len;
+	assert(tgt_len > 0);
+
+	mat = edge->costs;
+	assert(mat);
+
+	for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+		num elem = mat->entries[row_index * tgt_len + tgt_index];
+
+		if (elem != 0) {
+			if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
+				new_infinity = 1;
+
+			tgt_vec->entries[tgt_index].data = pbqp_add(
+					tgt_vec->entries[tgt_index].data, elem);
+		}
+	}
+
+	if (new_infinity) {
+		unsigned edge_index;
+		unsigned edge_len = pbqp_node_get_degree(tgt_node);
+
+		for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+			pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
+
+			if (edge_candidate != edge) {
+				insert_into_edge_bucket(edge_candidate);
+			}
+		}
+	}
+
+	delete_edge(edge);
+}
+
 void select_alternative(pbqp_node *node, unsigned selected_index)
 {
 	unsigned  edge_index;
@@ -1193,9 +1373,14 @@ void select_alternative(pbqp_node *node, unsigned selected_index)
 		}
 	}
 
-	/* Add all incident edges to edge bucket, since they are now independent. */
+	/* Select corresponding row/column for incident edges. */
 	for (edge_index = 0; edge_index < max_degree; ++edge_index) {
-		insert_into_edge_bucket(node->edges[edge_index]);
+		pbqp_edge *edge = node->edges[edge_index];
+
+		if (edge->src == node)
+			select_row(edge, selected_index);
+		else
+			select_column(edge, selected_index);
 	}
 }