#include "bucket.h"
#include "heuristical.h"
+#if KAPS_DUMP
#include "html_dumper.h"
+#endif
#include "kaps.h"
#include "matrix.h"
#include "pbqp_edge.h"
static pbqp_node **reduced_bucket = NULL;
static int buckets_filled = 0;
+#if KAPS_STATISTIC
+static int dump = 0;
+#endif
+
/* Forward declarations. */
static void apply_Brute_Force(pbqp *pbqp);
node_bucket_insert(&node_buckets[degree], node);
}
+#if 0
static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
{
pbqp_matrix *mat;
panic("Hurray");
}
}
+#endif
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
{
if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
return;
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
dump_section(pbqp->dump_file, 3, txt);
}
+#endif
src_vec = src_node->costs;
tgt_vec = tgt_node->costs;
mat = edge->costs;
assert(mat);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("Input:<br>\n", pbqp->dump_file);
dump_simplifyedge(pbqp, edge);
}
+#endif
normalize_towards_source(pbqp, edge);
normalize_towards_target(pbqp, edge);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
dump_simplifyedge(pbqp, edge);
}
+#endif
if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("edge has been eliminated<br>\n", pbqp->dump_file);
}
+#endif
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_edges++;
+ }
+#endif
delete_edge(edge);
reorder_node(src_node);
reorder_node(tgt_node);
- } else {
- //check_melting_possibility(pbqp, edge);
}
}
assert(pbqp);
+#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_input(pbqp);
dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
}
+#endif
node_len = pbqp->num_nodes;
}
}
-num determine_solution(FILE *file)
+static num determine_solution(pbqp *pbqp)
{
unsigned node_index;
unsigned node_len;
num solution = 0;
+#if KAPS_DUMP
+ FILE *file;
+#endif
+
+ assert(pbqp);
+
+#if KAPS_DUMP
+ file = pbqp->dump_file;
if (file) {
dump_section(file, 1, "4. Determine Solution/Minimum");
dump_section(file, 2, "4.1. Trivial Solution");
}
+#endif
/* Solve trivial nodes and calculate solution. */
node_len = node_bucket_get_length(node_buckets[0]);
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r0 = node_len;
+ }
+#endif
+
for (node_index = 0; node_index < node_len; ++node_index) {
pbqp_node *node = node_buckets[0][node_index];
assert(node);
node->solution = vector_get_min_index(node->costs);
solution = pbqp_add(solution,
node->costs->entries[node->solution].data);
+
+#if KAPS_DUMP
if (file) {
fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
dump_node(file, node);
}
+#endif
}
+#if KAPS_DUMP
if (file) {
dump_section(file, 2, "Minimum");
fprintf(file, "Minimum is equal to %lld.", solution);
}
+#endif
return solution;
}
unsigned node_len = node_bucket_get_length(reduced_bucket);
assert(pbqp);
+
+#if KAPS_DUMP
if (pbqp->dump_file) {
dump_section(pbqp->dump_file, 2, "Back Propagation");
}
+#endif
for (node_index = node_len; node_index > 0; --node_index) {
pbqp_node *node = reduced_bucket[node_index - 1];
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
+#if KAPS_STATISTIC
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "Solution");
+ fclose(fh);
+#endif
+
apply_heuristic_reductions(pbqp);
- pbqp->solution = determine_solution(pbqp->dump_file);
+ pbqp->solution = determine_solution(pbqp);
- //printf("solution: %lld\n", pbqp->solution);
+#if KAPS_STATISTIC
+ fh = fopen("solutions.pb", "a");
+ fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+ pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+ pbqp->num_rn);
+ fclose(fh);
+#endif
/* Solve reduced nodes. */
back_propagate(pbqp);
other_node = edge->src;
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RI-Reduction of Node n%d", node->index);
dump_node(pbqp->dump_file, other_node);
dump_edge(pbqp->dump_file, edge);
}
+#endif
if (is_src) {
pbqp_matrix_add_to_all_cols(mat, node->costs);
}
disconnect_edge(other_node, edge);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
dump_node(pbqp->dump_file, other_node);
}
+#endif
reorder_node(other_node);
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r1++;
+ }
+#endif
+
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
}
tgt_is_src = tgt_edge->src == node;
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RII-Reduction of Node n%d", node->index);
dump_edge(pbqp->dump_file, tgt_edge);
dump_node(pbqp->dump_file, tgt_node);
}
+#endif
src_mat = src_edge->costs;
tgt_mat = tgt_edge->costs;
disconnect_edge(src_node, src_edge);
disconnect_edge(tgt_node, tgt_edge);
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r2++;
+ }
+#endif
+
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
reorder_node(tgt_node);
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
dump_edge(pbqp->dump_file, edge);
}
+#endif
/* Edge has changed so we simplify it. */
simplify_edge(pbqp, edge);
assert(node);
assert(pbqp_node_get_degree(node) > 2);
+#if KAPS_DUMP
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);
}
+#endif
min_index = get_local_minimal_alternative(pbqp, node);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
node->index, min_index);
}
+#endif
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "[%u]", min_index);
+ fclose(fh);
+ pbqp->num_rn++;
+ }
+#endif
/* Now that we found the local minimum set all other costs to infinity. */
select_alternative(node, min_index);
unsigned bucket_0_length;
unsigned bucket_red_length;
+ char *tmp = obstack_finish(&pbqp->obstack);
+
node_bucket_init(&bucket_deg3);
/* Some node buckets and the edge bucket should be empty. */
/* char *tmp = obstack_finish(&pbqp->obstack); */
/* Save current PBQP state. */
- node_bucket_deep_copy(pbqp, &bucket_deg3, node_buckets[3]);
+ node_bucket_copy(&bucket_deg3, node_buckets[3]);
+ node_bucket_shrink(&node_buckets[3], 0);
+ node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
+ node_bucket_update(pbqp, node_buckets[3]);
bucket_0_length = node_bucket_get_length(node_buckets[0]);
bucket_red_length = node_bucket_get_length(reduced_bucket);
select_alternative(node_buckets[3][bucket_index], node_index);
apply_brute_force_reductions(pbqp);
- value = determine_solution(pbqp->dump_file);
+ value = determine_solution(pbqp);
if (value < min) {
min = value;
/* ... and restore old PBQP state. */
node_bucket_shrink(&node_buckets[0], bucket_0_length);
node_bucket_shrink(&reduced_bucket, bucket_red_length);
- node_bucket_copy(pbqp, &node_buckets[3], bucket_deg3);
+ node_bucket_copy(&node_buckets[3], bucket_deg3);
+ node_bucket_update(pbqp, node_buckets[3]);
/* Free copies. */
/* obstack_free(&pbqp->obstack, tmp); */
node_bucket_free(&bucket_deg3);
+
+ obstack_free(&pbqp->obstack, tmp);
}
return min_index;
assert(node);
assert(pbqp_node_get_degree(node) > 2);
+#if KAPS_DUMP
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);
}
+#endif
+
+#if KAPS_STATISTIC
+ dump++;
+#endif
min_index = get_minimal_alternative(pbqp, node);
node = pbqp->nodes[node->index];
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
node->index, min_index);
}
+#endif
+
+#if KAPS_STATISTIC
+ dump--;
+ if (dump == 0) {
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "[%u]", min_index);
+ fclose(fh);
+ pbqp->num_bf++;
+ }
+#endif
/* Now that we found the minimum set all other costs to infinity. */
select_alternative(node, min_index);
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
+#if KAPS_STATISTIC
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "Solution");
+ fclose(fh);
+#endif
+
apply_brute_force_reductions(pbqp);
- pbqp->solution = determine_solution(pbqp->dump_file);
+ pbqp->solution = determine_solution(pbqp);
- //printf("solution: %lld\n", pbqp->solution);
+#if KAPS_STATISTIC
+ fh = fopen("solutions.pb", "a");
+ fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+ pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+ pbqp->num_bf);
+ fclose(fh);
+#endif
/* Solve reduced nodes. */
back_propagate(pbqp);
/* Update pointer for brute force solver. */
other = pbqp->nodes[other->index];
- vector_add_matrix_col(vec, mat, other->solution);
+ node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
} else {
other = edge->src;
assert(other);
/* Update pointer for brute force solver. */
other = pbqp->nodes[other->index];
- vector_add_matrix_row(vec, mat, other->solution);
+ node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
}
- node->solution = vector_get_min_index(vec);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
}
+#endif
}
void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
}
node->solution = vector_get_min_index(vec);
+
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
}
+#endif
obstack_free(&pbqp->obstack, vec);
}
projects / libfirm / blobdiff