#include "assert.h"
#include "error.h"
+#include "bucket.h"
#include "heuristical.h"
#include "html_dumper.h"
#include "kaps.h"
static void insert_into_edge_bucket(pbqp_edge *edge)
{
- unsigned bucket_len = ARR_LEN(edge_bucket);
-
- if (edge->bucket_index < bucket_len && edge_bucket[edge->bucket_index]
- == edge)
+ if (edge_bucket_contains(edge_bucket, edge)) {
/* Edge is already inserted. */
return;
+ }
- edge->bucket_index = bucket_len;
- ARR_APP1(pbqp_edge *, edge_bucket, edge);
+ edge_bucket_insert(&edge_bucket, edge);
}
static void init_buckets(void)
{
int i;
- edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
- reduced_bucket = NEW_ARR_F(pbqp_node *, 0);
+ edge_bucket_init(&edge_bucket);
+ node_bucket_init(&reduced_bucket);
for (i = 0; i < 4; ++i) {
- node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
+ node_bucket_init(&node_buckets[i]);
}
}
int i;
for (i = 0; i < 4; ++i) {
- DEL_ARR_F(node_buckets[i]);
- node_buckets[i] = NULL;
+ node_bucket_free(&node_buckets[i]);
}
- DEL_ARR_F(edge_bucket);
- edge_bucket = NULL;
-
- DEL_ARR_F(reduced_bucket);
- reduced_bucket = NULL;
+ edge_bucket_free(&edge_bucket);
+ node_bucket_free(&reduced_bucket);
buckets_filled = 0;
}
node_len = pbqp->num_nodes;
for (node_index = 0; node_index < node_len; ++node_index) {
- unsigned arity;
+ unsigned degree;
pbqp_node *node = get_node(pbqp, node_index);
if (!node) continue;
- arity = ARR_LEN(node->edges);
+ degree = pbqp_node_get_degree(node);
/* We have only one bucket for nodes with arity >= 3. */
- if (arity > 3) {
- arity = 3;
+ if (degree > 3) {
+ degree = 3;
}
- node->bucket_index = ARR_LEN(node_buckets[arity]);
-
- ARR_APP1(pbqp_node *, node_buckets[arity], node);
+ node_bucket_insert(&node_buckets[degree], node);
}
buckets_filled = 1;
num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
if (min != 0) {
- pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
+ 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);
+ }
src_vec->entries[src_index].data = pbqp_add(
src_vec->entries[src_index].data, min);
if (min == INF_COSTS) {
- insert_into_edge_bucket(edge);
+ 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);
+ }
+ }
}
}
}
num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
if (min != 0) {
- pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
+ 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);
+ }
tgt_vec->entries[tgt_index].data = pbqp_add(
tgt_vec->entries[tgt_index].data, min);
if (min == INF_COSTS) {
- insert_into_edge_bucket(edge);
+ 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);
+ }
+ }
}
}
}
static void reorder_node(pbqp_node *node)
{
- unsigned arity;
- unsigned old_arity;
- unsigned old_bucket_len;
- unsigned old_bucket_index;
- pbqp_node **old_bucket;
- pbqp_node *other;
+ unsigned degree = pbqp_node_get_degree(node);
+ /* Assume node lost one incident edge. */
+ unsigned old_degree = degree + 1;
if (!buckets_filled) return;
- assert(node);
-
- arity = ARR_LEN(node->edges);
-
/* Same bucket as before */
- if (arity > 2) return;
+ if (degree > 2) return;
- /* Assume node lost one incident edge. */
- old_arity = arity + 1;
- old_bucket = node_buckets[old_arity];
- old_bucket_len = ARR_LEN(old_bucket);
- old_bucket_index = node->bucket_index;
-
- if (old_bucket_len <= old_bucket_index ||
- old_bucket[old_bucket_index] != node) {
+ if (!node_bucket_contains(node_buckets[old_degree], node)) {
/* Old arity is new arity, so we have nothing to do. */
- assert(old_bucket_index < ARR_LEN(node_buckets[arity]) &&
- node_buckets[arity][old_bucket_index] == node);
+ assert(node_bucket_contains(node_buckets[degree], node));
return;
}
- assert(old_bucket[old_bucket_index] == node);
-
/* Delete node from old bucket... */
- other = old_bucket[old_bucket_len - 1];
- other->bucket_index = old_bucket_index;
- old_bucket[old_bucket_index] = other;
- ARR_SHRINKLEN(node_buckets[old_arity], old_bucket_len - 1);
+ node_bucket_remove(&node_buckets[old_degree], node);
/* ..and add to new one. */
- node->bucket_index = ARR_LEN(node_buckets[arity]);
- ARR_APP1(pbqp_node*, node_buckets[arity], node);
+ node_bucket_insert(&node_buckets[degree], node);
+}
+
+static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
+{
+ pbqp_matrix *mat;
+ pbqp_node *src_node;
+ pbqp_node *tgt_node;
+ vector *src_vec;
+ vector *tgt_vec;
+ int src_len;
+ int tgt_len;
+ int src_index;
+ int tgt_index;
+
+ assert(pbqp);
+ 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);
+
+ if (src_len == 1 && tgt_len == 1) {
+ //panic("Something is wrong");
+ }
+
+ int allRowsOk = 1;
+ for (src_index = 0; src_index < src_len; ++src_index) {
+ int onlyOneZero = 0;
+ if (src_vec->entries[src_index].data == INF_COSTS) {
+ continue;
+ }
+ for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+ if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
+ continue;
+ }
+ if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
+ if (onlyOneZero) {
+ onlyOneZero = 0;
+ break;
+ } else {
+ onlyOneZero = 1;
+ continue;
+ }
+ }
+ if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
+ continue;
+ }
+ onlyOneZero = 0;
+ break;
+ }
+ allRowsOk &= onlyOneZero;
+ }
+
+ int allColsOk = 1;
+ for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+ int onlyOneZero = 0;
+ if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
+ continue;
+ }
+ for (src_index = 0; src_index < src_len; ++src_index) {
+ if (src_vec->entries[src_index].data == INF_COSTS) {
+ continue;
+ }
+ if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
+ if (onlyOneZero) {
+ onlyOneZero = 0;
+ break;
+ } else {
+ onlyOneZero = 1;
+ continue;
+ }
+ }
+ if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
+ continue;
+ }
+ onlyOneZero = 0;
+ break;
+ }
+ allColsOk &= onlyOneZero;
+ }
+
+ if (allRowsOk && allColsOk) {
+ panic("Hurray");
+ }
}
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
delete_edge(edge);
reorder_node(src_node);
reorder_node(tgt_node);
+ } else {
+ //check_melting_possibility(pbqp, edge);
}
}
if (!node) continue;
edges = node->edges;
- edge_len = ARR_LEN(edges);
+ edge_len = pbqp_node_get_degree(node);
for (edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge *edge = edges[edge_index];
fill_node_buckets(pbqp);
for (;;) {
- if (ARR_LEN(edge_bucket) > 0) {
+ if (edge_bucket_get_length(edge_bucket) > 0) {
apply_edge(pbqp);
- } else if (ARR_LEN(node_buckets[1]) > 0) {
+ } else if (node_bucket_get_length(node_buckets[1]) > 0) {
apply_RI(pbqp);
- } else if (ARR_LEN(node_buckets[2]) > 0) {
+ } else if (node_bucket_get_length(node_buckets[2]) > 0) {
apply_RII(pbqp);
- } else if (ARR_LEN(node_buckets[3]) > 0) {
- panic("Please implement RN simplification");
+ } else if (node_bucket_get_length(node_buckets[3]) > 0) {
+ apply_RN(pbqp);
} else {
break;
}
}
/* Solve trivial nodes and calculate solution. */
- node_len = ARR_LEN(node_buckets[0]);
+ node_len = node_bucket_get_length(node_buckets[0]);
for (node_index = 0; node_index < node_len; ++node_index) {
pbqp_node *node = node_buckets[0][node_index];
assert(node);
if (pbqp->dump_file) {
dump_section(pbqp->dump_file, 2, "Minimum");
- fprintf(pbqp->dump_file, "Minimum is equal to %d.", pbqp->solution);
+ fprintf(pbqp->dump_file, "Minimum is equal to %lld.", pbqp->solution);
dump_section(pbqp->dump_file, 2, "Back Propagation");
}
/* Solve reduced nodes. */
- node_len = ARR_LEN(reduced_bucket);
+ node_len = node_bucket_get_length(reduced_bucket);
for (node_index = node_len; node_index > 0; --node_index) {
pbqp_node *node = reduced_bucket[node_index - 1];
- assert(node);
- switch (ARR_LEN(node->edges)) {
+ switch (pbqp_node_get_degree(node)) {
case 1:
back_propagate_RI(pbqp, node);
break;
void apply_edge(pbqp *pbqp)
{
- unsigned bucket_len = ARR_LEN(edge_bucket);
- pbqp_edge *edge = edge_bucket[bucket_len - 1];
-
- ARR_SHRINKLEN(edge_bucket, (int)bucket_len - 1);
+ pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
simplify_edge(pbqp, edge);
}
void apply_RI(pbqp *pbqp)
{
- pbqp_node **bucket = node_buckets[1];
- unsigned bucket_len = ARR_LEN(bucket);
- pbqp_node *node = bucket[bucket_len - 1];
+ pbqp_node *node = node_bucket_pop(&node_buckets[1]);
pbqp_edge *edge = node->edges[0];
pbqp_matrix *mat = edge->costs;
int is_src = edge->src == node;
if (pbqp->dump_file) {
char txt[100];
- sprintf(txt, "RI-Reduktion of Node n%d", node->index);
+ sprintf(txt, "RI-Reduction of Node n%d", node->index);
dump_section(pbqp->dump_file, 2, txt);
pbqp_dump_graph(pbqp);
fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
dump_node(pbqp, other_node);
}
- /* Remove node from bucket... */
- ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
reorder_node(other_node);
- /* ...and add it to back propagation list. */
- node->bucket_index = ARR_LEN(reduced_bucket);
- ARR_APP1(pbqp_node *, reduced_bucket, node);
+ /* Add node to back propagation list. */
+ node_bucket_insert(&reduced_bucket, node);
}
void apply_RII(pbqp *pbqp)
{
- pbqp_node **bucket = node_buckets[2];
- unsigned bucket_len = ARR_LEN(bucket);
- pbqp_node *node = bucket[bucket_len - 1];
+ pbqp_node *node = node_bucket_pop(&node_buckets[2]);
pbqp_edge *src_edge = node->edges[0];
pbqp_edge *tgt_edge = node->edges[1];
int src_is_src = src_edge->src == node;
if (pbqp->dump_file) {
char txt[100];
- sprintf(txt, "RII-Reduktion of Node n%d", node->index);
+ sprintf(txt, "RII-Reduction of Node n%d", node->index);
dump_section(pbqp->dump_file, 2, txt);
pbqp_dump_graph(pbqp);
fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
disconnect_edge(src_node, src_edge);
disconnect_edge(tgt_node, tgt_edge);
- /* Remove node from bucket... */
- ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
-
- /* ...and add it to back propagation list. */
- node->bucket_index = ARR_LEN(reduced_bucket);
- ARR_APP1(pbqp_node *, reduced_bucket, node);
+ /* Add node to back propagation list. */
+ node_bucket_insert(&reduced_bucket, node);
if (edge == NULL) {
edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
void apply_RN(pbqp *pbqp)
{
- pbqp_node **bucket = node_buckets[3];
- unsigned bucket_len = ARR_LEN(bucket);
- pbqp_node *node = bucket[bucket_len - 1];
+ pbqp_node **bucket = node_buckets[3];
+ unsigned bucket_len = node_bucket_get_length(bucket);
+ unsigned bucket_index;
+ pbqp_node *node = NULL;
pbqp_edge *edge;
- vector *node_vec = node->costs;
+ vector *node_vec;
vector *vec;
pbqp_matrix *mat;
unsigned edge_index;
- unsigned edge_len = ARR_LEN(node->edges);
+ unsigned max_degree = 0;
unsigned node_index;
- unsigned node_len = ARR_LEN(node_vec);
- unsigned min_index = 0;
- num min = INF_COSTS;
+ unsigned node_len;
+ unsigned min_index = 0;
+ num min = INF_COSTS;
int is_src;
assert(pbqp);
+ /* Search for node with maximum degree. */
+ for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
+ pbqp_node *candidate = bucket[bucket_index];
+ unsigned degree = pbqp_node_get_degree(candidate);
+
+ if (degree > max_degree) {
+ node = candidate;
+ max_degree = degree;
+ }
+ }
+ assert(node);
+ node_vec = node->costs;
+ node_len = node_vec->len;
+
+ if (pbqp->dump_file) {
+ char txt[100];
+ sprintf(txt, "RN-Reduction of Node n%d", node->index);
+ dump_section(pbqp->dump_file, 2, txt);
+ pbqp_dump_graph(pbqp);
+ }
+
for (node_index = 0; node_index < node_len; ++node_index) {
- num value = 0;
+ num value = node_vec->entries[node_index].data;
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (edge_index = 0; edge_index < max_degree; ++edge_index) {
edge = node->edges[edge_index];
mat = edge->costs;
is_src = edge->src == node;
}
}
+ if (pbqp->dump_file) {
+ fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
+ node->index, min_index);
+ fprintf(pbqp->dump_file, "Minimal cost of RN reduction: %lld<br>\n",
+ min);
+ }
+
node->solution = min_index;
/* Now that we found the local minimum set all other costs to infinity. */
}
/* Add all incident edges to edge bucket, since they are now independent. */
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
- insert_into_edge_bucket(node->edges[node_index]);
+ for (edge_index = 0; edge_index < max_degree; ++edge_index) {
+ insert_into_edge_bucket(node->edges[edge_index]);
}
}
{
if (!reduced_bucket) return 0;
- assert(node);
- if (ARR_LEN(node->edges) == 0) return 1;
-
- unsigned bucket_length = ARR_LEN(reduced_bucket);
- unsigned bucket_index = node->bucket_index;
+ if (pbqp_node_get_degree(node) == 0) return 1;
- return bucket_index < bucket_length && reduced_bucket[bucket_index] == node;
+ return node_bucket_contains(reduced_bucket, node);
}
projects / libfirm / blobdiff