X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=heuristical.c;h=97471439fb317b59bd41cc60aff32e06f31f0a02;hb=7c6d83c487a8233944cf05eb9d3ef1ac522463da;hp=2ceae6e951a2c9b2ae97a389aa2935d1fdcaf4c6;hpb=930c6cbc8d17486522ba3039b06ab8d47d4c2fba;p=libfirm diff --git a/heuristical.c b/heuristical.c index 2ceae6e95..97471439f 100644 --- a/heuristical.c +++ b/heuristical.c @@ -2,6 +2,7 @@ #include "assert.h" #include "error.h" +#include "bucket.h" #include "heuristical.h" #include "html_dumper.h" #include "kaps.h" @@ -19,26 +20,23 @@ static int buckets_filled = 0; 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]); } } @@ -47,15 +45,11 @@ static void free_buckets(void) 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; } @@ -69,21 +63,19 @@ static void fill_node_buckets(pbqp *pbqp) 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; @@ -126,12 +118,24 @@ static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge) 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); + } + } } } } @@ -173,12 +177,24 @@ static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge) 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); + } + } } } } @@ -186,47 +202,124 @@ static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge) 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) @@ -291,6 +384,8 @@ 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); } } @@ -320,7 +415,7 @@ void solve_pbqp_heuristical(pbqp *pbqp) 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]; @@ -336,14 +431,14 @@ void solve_pbqp_heuristical(pbqp *pbqp) 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; } @@ -355,7 +450,7 @@ void solve_pbqp_heuristical(pbqp *pbqp) } /* 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); @@ -371,17 +466,16 @@ void solve_pbqp_heuristical(pbqp *pbqp) 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; @@ -399,19 +493,14 @@ void solve_pbqp_heuristical(pbqp *pbqp) 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; @@ -425,7 +514,7 @@ void apply_RI(pbqp *pbqp) 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("
\nBefore reduction:
\n", pbqp->dump_file); @@ -448,20 +537,15 @@ void apply_RI(pbqp *pbqp) 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; @@ -514,7 +598,7 @@ void apply_RII(pbqp *pbqp) 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("
\nBefore reduction:
\n", pbqp->dump_file); @@ -566,12 +650,8 @@ void apply_RII(pbqp *pbqp) 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); @@ -596,27 +676,49 @@ void apply_RII(pbqp *pbqp) 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; @@ -640,6 +742,13 @@ void apply_RN(pbqp *pbqp) } } + if (pbqp->dump_file) { + fprintf(pbqp->dump_file, "node n%d is set to %d

\n", + node->index, min_index); + fprintf(pbqp->dump_file, "Minimal cost of RN reduction: %lld
\n", + min); + } + node->solution = min_index; /* Now that we found the local minimum set all other costs to infinity. */ @@ -650,8 +759,8 @@ void apply_RN(pbqp *pbqp) } /* 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]); } } @@ -767,11 +876,7 @@ int node_is_reduced(pbqp_node *node) { 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); }