From b75c466f29badb225c40070d1249b3259ca32632 Mon Sep 17 00:00:00 2001
From: Sebastian Buchwald <Sebastian.Buchwald@kit.edu>
Date: Thu, 12 Aug 2010 18:38:05 +0000
Subject: [PATCH] Split RN into 2 phases.

This allows application of optimal reduction after merging neighbors into the RN node.

[r27925]
---
 heuristical_co.c | 29 ++++++++++++++++++++++++-----
 optimal.c        |  5 +++++
 optimal.h        |  1 +
 3 files changed, 30 insertions(+), 5 deletions(-)

diff --git a/heuristical_co.c b/heuristical_co.c
index cd5f83214..3e8ed968e 100644
--- a/heuristical_co.c
+++ b/heuristical_co.c
@@ -47,10 +47,9 @@
 #include "plist.h"
 #include "timing.h"
 
-static void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
+static void merge_into_RN_node(pbqp *pbqp, plist_t *rpeo)
 {
 	pbqp_node   *node         = NULL;
-	unsigned     min_index    = 0;
 
 	assert(pbqp);
 
@@ -77,9 +76,19 @@ static void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
 #endif
 	/* Check whether we can merge a neighbor into the current node. */
 	apply_RM(pbqp, node);
+}
+
+static void apply_RN_co(pbqp *pbqp)
+{
+	pbqp_node   *node      = NULL;
+	unsigned     min_index = 0;
+
+	assert(pbqp);
+
+	node = node_bucket_pop(&rn_bucket);
+	assert(node);
 
-	/* Apply optimal solution for the given node, if possible. */
-	if (pbqp_node_get_degree(node) < 3)
+	if (node_is_reduced(node))
 		return;
 
 	min_index = get_local_minimal_alternative(pbqp, node);
@@ -143,12 +152,22 @@ static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
 			#if KAPS_TIMING
 				ir_timer_stop(t_r2);
 			#endif
+		} else if (node_bucket_get_length(rn_bucket) > 0) {
+			#if KAPS_TIMING
+				ir_timer_start(t_rn);
+			#endif
+
+			apply_RN_co(pbqp);
+
+			#if KAPS_TIMING
+				ir_timer_stop(t_rn);
+			#endif
 		} else if (node_bucket_get_length(node_buckets[3]) > 0) {
 			#if KAPS_TIMING
 				ir_timer_start(t_rn);
 			#endif
 
-			apply_RN_co(pbqp, rpeo);
+			merge_into_RN_node(pbqp, rpeo);
 
 			#if KAPS_TIMING
 				ir_timer_stop(t_rn);
diff --git a/optimal.c b/optimal.c
index b5e834df8..98c87ed80 100644
--- a/optimal.c
+++ b/optimal.c
@@ -48,6 +48,7 @@
 
 pbqp_edge **edge_bucket;
 pbqp_edge **rm_bucket;
+pbqp_node **rn_bucket;
 pbqp_node **node_buckets[4];
 pbqp_node **reduced_bucket = NULL;
 static int         buckets_filled = 0;
@@ -79,6 +80,7 @@ static void init_buckets(void)
 	edge_bucket_init(&edge_bucket);
 	edge_bucket_init(&rm_bucket);
 	node_bucket_init(&reduced_bucket);
+	node_bucket_init(&rn_bucket);
 
 	for (i = 0; i < 4; ++i) {
 		node_bucket_init(&node_buckets[i]);
@@ -96,6 +98,7 @@ void free_buckets(void)
 	edge_bucket_free(&edge_bucket);
 	edge_bucket_free(&rm_bucket);
 	node_bucket_free(&reduced_bucket);
+	node_bucket_free(&rn_bucket);
 
 	buckets_filled = 0;
 }
@@ -625,6 +628,8 @@ void apply_RM(pbqp *pbqp, pbqp_node *node)
 		else
 			merge_source_into_target(pbqp, edge);
 	}
+
+	node_bucket_insert(&rn_bucket, node);
 }
 
 void reorder_node(pbqp_node *node)
diff --git a/optimal.h b/optimal.h
index 3d130427c..2432f8387 100644
--- a/optimal.h
+++ b/optimal.h
@@ -32,6 +32,7 @@
 extern pbqp_edge **edge_bucket;
 extern pbqp_node **node_buckets[4];
 extern pbqp_node **reduced_bucket;
+extern pbqp_node **rn_bucket;
 
 void apply_edge(pbqp *pbqp);
 
-- 
2.20.1