X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=heuristical.c;h=23d04887db0bc0c9c0281d99333de7bece12bd54;hb=eb32c39340c33ad210747b1361f2d586198e93dc;hp=a2ec4c6a167dd8d8ab81b4f588f07a39f9f8e138;hpb=2c6199a3df7095ad63da82a2e1c7419ba2b81373;p=libfirm diff --git a/heuristical.c b/heuristical.c index a2ec4c6a1..23d04887d 100644 --- a/heuristical.c +++ b/heuristical.c @@ -18,6 +18,9 @@ static pbqp_node **node_buckets[4]; static pbqp_node **reduced_bucket = NULL; static int buckets_filled = 0; +/* Forward declarations. */ +static void apply_Brute_Force(pbqp *pbqp); + static void insert_into_edge_bucket(pbqp_edge *edge) { if (edge_bucket_contains(edge_bucket, edge)) { @@ -428,15 +431,15 @@ static void initial_simplify_edges(pbqp *pbqp) } } -num determine_solution(pbqp *pbqp) +num determine_solution(FILE *file) { unsigned node_index; unsigned node_len; num solution; - if (pbqp->dump_file) { - dump_section(pbqp->dump_file, 1, "4. Determine Solution/Minimum"); - dump_section(pbqp->dump_file, 2, "4.1. Trivial Solution"); + if (file) { + dump_section(file, 1, "4. Determine Solution/Minimum"); + dump_section(file, 2, "4.1. Trivial Solution"); } /* Solve trivial nodes and calculate solution. */ @@ -448,50 +451,30 @@ num determine_solution(pbqp *pbqp) node->solution = vector_get_min_index(node->costs); solution = pbqp_add(solution, node->costs->entries[node->solution].data); - if (pbqp->dump_file) { - fprintf(pbqp->dump_file, "node n%d is set to %d
\n", node->index, node->solution); - dump_node(pbqp, node); + if (file) { + fprintf(file, "node n%d is set to %d
\n", node->index, node->solution); + dump_node(file, node); } } + if (file) { + dump_section(file, 2, "Minimum"); + fprintf(file, "Minimum is equal to %lld.", solution); + } + return solution; } -void solve_pbqp_heuristical(pbqp *pbqp) +static void back_propagate(pbqp *pbqp) { unsigned node_index; - unsigned node_len; - - /* Reduce nodes degree ... */ - initial_simplify_edges(pbqp); - - /* ... and put node into bucket representing their degree. */ - fill_node_buckets(pbqp); - - for (;;) { - if (edge_bucket_get_length(edge_bucket) > 0) { - apply_edge(pbqp); - } else if (node_bucket_get_length(node_buckets[1]) > 0) { - apply_RI(pbqp); - } else if (node_bucket_get_length(node_buckets[2]) > 0) { - apply_RII(pbqp); - } else if (node_bucket_get_length(node_buckets[3]) > 0) { - apply_RN(pbqp); - } else { - break; - } - } - - pbqp->solution = determine_solution(pbqp); + unsigned node_len = node_bucket_get_length(reduced_bucket); + assert(pbqp); if (pbqp->dump_file) { - dump_section(pbqp->dump_file, 2, "Minimum"); - fprintf(pbqp->dump_file, "Minimum is equal to %lld.", pbqp->solution); dump_section(pbqp->dump_file, 2, "Back Propagation"); } - /* Solve reduced nodes. */ - 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]; @@ -507,6 +490,39 @@ void solve_pbqp_heuristical(pbqp *pbqp) break; } } +} + +static void apply_heuristic_reductions(pbqp *pbqp) +{ + for (;;) { + if (edge_bucket_get_length(edge_bucket) > 0) { + apply_edge(pbqp); + } else if (node_bucket_get_length(node_buckets[1]) > 0) { + apply_RI(pbqp); + } else if (node_bucket_get_length(node_buckets[2]) > 0) { + apply_RII(pbqp); + } else if (node_bucket_get_length(node_buckets[3]) > 0) { + apply_RN(pbqp); + } else { + return; + } + } +} + +void solve_pbqp_heuristical(pbqp *pbqp) +{ + /* Reduce nodes degree ... */ + initial_simplify_edges(pbqp); + + /* ... and put node into bucket representing their degree. */ + fill_node_buckets(pbqp); + + apply_heuristic_reductions(pbqp); + + pbqp->solution = determine_solution(pbqp->dump_file); + + /* Solve reduced nodes. */ + back_propagate(pbqp); free_buckets(); } @@ -538,9 +554,9 @@ void apply_RI(pbqp *pbqp) dump_section(pbqp->dump_file, 2, txt); pbqp_dump_graph(pbqp); fputs("
\nBefore reduction:
\n", pbqp->dump_file); - dump_node(pbqp, node); - dump_node(pbqp, other_node); - dump_edge(pbqp, edge); + dump_node(pbqp->dump_file, node); + dump_node(pbqp->dump_file, other_node); + dump_edge(pbqp->dump_file, edge); } if (is_src) { @@ -554,7 +570,7 @@ void apply_RI(pbqp *pbqp) if (pbqp->dump_file) { fputs("
\nAfter reduction:
\n", pbqp->dump_file); - dump_node(pbqp, other_node); + dump_node(pbqp->dump_file, other_node); } reorder_node(other_node); @@ -622,11 +638,11 @@ void apply_RII(pbqp *pbqp) dump_section(pbqp->dump_file, 2, txt); pbqp_dump_graph(pbqp); fputs("
\nBefore reduction:
\n", pbqp->dump_file); - dump_node(pbqp, src_node); - dump_edge(pbqp, src_edge); - dump_node(pbqp, node); - dump_edge(pbqp, tgt_edge); - dump_node(pbqp, tgt_node); + dump_node(pbqp->dump_file, src_node); + dump_edge(pbqp->dump_file, src_edge); + dump_node(pbqp->dump_file, node); + dump_edge(pbqp->dump_file, tgt_edge); + dump_node(pbqp->dump_file, tgt_node); } src_mat = src_edge->costs; @@ -687,19 +703,63 @@ void apply_RII(pbqp *pbqp) if (pbqp->dump_file) { fputs("
\nAfter reduction:
\n", pbqp->dump_file); - dump_edge(pbqp, edge); + dump_edge(pbqp->dump_file, edge); } /* Edge has changed so we simplify it. */ simplify_edge(pbqp, edge); } -void apply_RN(pbqp *pbqp) +static void select_alternative(pbqp_node *node, unsigned selected_index) +{ + unsigned edge_index; + unsigned node_index; + unsigned node_len; + vector *node_vec; + unsigned max_degree = pbqp_node_get_degree(node); + + assert(selected_index < max_degree); + assert(node); + node->solution = selected_index; + node_vec = node->costs; + node_len = node_vec->len; + + /* Set all other costs to infinity. */ + for (node_index = 0; node_index < node_len; ++node_index) { + if (node_index != selected_index) { + node_vec->entries[node_index].data = INF_COSTS; + } + } + + /* Add all incident edges to edge bucket, since they are now independent. */ + for (edge_index = 0; edge_index < max_degree; ++edge_index) { + insert_into_edge_bucket(node->edges[edge_index]); + } +} + +static pbqp_node *get_node_with_max_degree(void) { pbqp_node **bucket = node_buckets[3]; unsigned bucket_len = node_bucket_get_length(bucket); unsigned bucket_index; - pbqp_node *node = NULL; + unsigned max_degree = 0; + pbqp_node *result = NULL; + + 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) { + result = candidate; + max_degree = degree; + } + } + + return result; +} + +static unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node) +{ pbqp_edge *edge; vector *node_vec; vector *vec; @@ -713,28 +773,10 @@ void apply_RN(pbqp *pbqp) 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 = node_vec->entries[node_index].data; @@ -762,101 +804,161 @@ void apply_RN(pbqp *pbqp) } } + return min_index; +} + +void apply_RN(pbqp *pbqp) +{ + pbqp_node *node = NULL; + unsigned min_index = 0; + + assert(pbqp); + + /* We want to reduce a node with maximum degree. */ + node = get_node_with_max_degree(); + assert(node); + + 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); + } + + min_index = get_local_minimal_alternative(pbqp, node); + 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. */ - for (node_index = 0; node_index < node_len; ++node_index) { - if (node_index != min_index) { - node_vec->entries[node_index].data = INF_COSTS; - } - } + select_alternative(node, min_index); +} - /* Add all incident edges to edge bucket, since they are now independent. */ - for (edge_index = 0; edge_index < max_degree; ++edge_index) { - insert_into_edge_bucket(node->edges[edge_index]); +static void apply_brute_force_reductions(pbqp *pbqp) +{ + for (;;) { + if (edge_bucket_get_length(edge_bucket) > 0) { + apply_edge(pbqp); + } else if (node_bucket_get_length(node_buckets[1]) > 0) { + apply_RI(pbqp); + } else if (node_bucket_get_length(node_buckets[2]) > 0) { + apply_RII(pbqp); + } else if (node_bucket_get_length(node_buckets[3]) > 0) { + apply_Brute_Force(pbqp); + } else { + return; + } } } -void apply_Brute_Force(pbqp *pbqp) +static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node) { - 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; - vector *vec; - pbqp_matrix *mat; - unsigned edge_index; - unsigned max_degree = 0; unsigned node_index; 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 = node_vec->entries[node_index].data; + num value; + + /* Some node buckets and the edge bucket should be empty. */ + assert(node_bucket_get_length(node_buckets[1]) == 0); + assert(node_bucket_get_length(node_buckets[2]) == 0); + assert(edge_bucket_get_length(edge_bucket) == 0); + + /* Save current PBQP state. */ + pbqp_node_bucket *bucket_deg0 = node_bucket_deep_copy(node_buckets[0]); + pbqp_node_bucket *bucket_deg3 = node_bucket_deep_copy(node_buckets[3]); + pbqp_node_bucket *bucket_red = node_bucket_deep_copy(reduced_bucket); - /* TODO Copy PBQP */ + /* Select alternative and solve PBQP recursively. */ + select_alternative(node, node_index); + apply_brute_force_reductions(pbqp); + value = determine_solution(pbqp->dump_file); if (value < min) { min = value; min_index = node_index; } + + /* Some node buckets and the edge bucket should still be empty. */ + assert(node_bucket_get_length(node_buckets[1]) == 0); + assert(node_bucket_get_length(node_buckets[2]) == 0); + assert(edge_bucket_get_length(edge_bucket) == 0); + + /* Clear modified buckets... */ + node_bucket_clear(&node_buckets[0]); + node_bucket_clear(&node_buckets[3]); + node_bucket_clear(&reduced_bucket); + + /* ... and restore old PBQP state. */ + node_bucket_copy(&node_buckets[0], bucket_deg0); + node_bucket_copy(&node_buckets[3], bucket_deg3); + node_bucket_copy(&reduced_bucket, bucket_red); + + /* Free copies. */ + node_bucket_free(bucket_deg0); + node_bucket_free(bucket_deg3); + node_bucket_free(bucket_red); + } + + return min_index; +} + +void apply_Brute_Force(pbqp *pbqp) +{ + pbqp_node *node = NULL; + unsigned min_index = 0; + + assert(pbqp); + + /* We want to reduce a node with maximum degree. */ + node = get_node_with_max_degree(); + assert(node); + + if (pbqp->dump_file) { + char txt[100]; + sprintf(txt, "BF-Reduction of Node n%d", node->index); + dump_section(pbqp->dump_file, 2, txt); + pbqp_dump_graph(pbqp); } + min_index = get_minimal_alternative(pbqp, node); + 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 minimum set all other costs to infinity. */ + select_alternative(node, min_index); +} - /* Now that we found the local minimum set all other costs to infinity. */ - for (node_index = 0; node_index < node_len; ++node_index) { - if (node_index != min_index) { - node_vec->entries[node_index].data = INF_COSTS; - } - } +void solve_pbqp_brute_force(pbqp *pbqp) +{ + /* Reduce nodes degree ... */ + initial_simplify_edges(pbqp); - /* Add all incident edges to edge bucket, since they are now independent. */ - for (edge_index = 0; edge_index < max_degree; ++edge_index) { - insert_into_edge_bucket(node->edges[edge_index]); - } + /* ... and put node into bucket representing their degree. */ + fill_node_buckets(pbqp); + + apply_brute_force_reductions(pbqp); + + pbqp->solution = determine_solution(pbqp->dump_file); + + /* Solve reduced nodes. */ + back_propagate(pbqp); + + free_buckets(); } void back_propagate_RI(pbqp *pbqp, pbqp_node *node)