projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Vector names are const.
[libfirm]
/
heuristical.c
diff --git
a/heuristical.c
b/heuristical.c
index
90296b5
..
98e7c4b
100644
(file)
--- a/
heuristical.c
+++ b/
heuristical.c
@@
-4,7
+4,9
@@
#include "bucket.h"
#include "heuristical.h"
#include "bucket.h"
#include "heuristical.h"
+#if KAPS_DUMP
#include "html_dumper.h"
#include "html_dumper.h"
+#endif
#include "kaps.h"
#include "matrix.h"
#include "pbqp_edge.h"
#include "kaps.h"
#include "matrix.h"
#include "pbqp_edge.h"
@@
-18,6
+20,10
@@
static pbqp_node **node_buckets[4];
static pbqp_node **reduced_bucket = NULL;
static int buckets_filled = 0;
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);
/* Forward declarations. */
static void apply_Brute_Force(pbqp *pbqp);
@@
-227,6
+233,7
@@
static void reorder_node(pbqp_node *node)
node_bucket_insert(&node_buckets[degree], node);
}
node_bucket_insert(&node_buckets[degree], node);
}
+#if 0
static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
{
pbqp_matrix *mat;
static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
{
pbqp_matrix *mat;
@@
-324,6
+331,7
@@
static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
panic("Hurray");
}
}
panic("Hurray");
}
}
+#endif
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
{
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
{
@@
-347,11
+355,13
@@
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
return;
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);
}
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;
src_vec = src_node->costs;
tgt_vec = tgt_node->costs;
@@
-366,29
+376,39
@@
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
mat = edge->costs;
assert(mat);
mat = edge->costs;
assert(mat);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("Input:<br>\n", pbqp->dump_file);
dump_simplifyedge(pbqp, edge);
}
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);
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);
}
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 (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);
}
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);
delete_edge(edge);
reorder_node(src_node);
reorder_node(tgt_node);
- } else {
- //check_melting_possibility(pbqp, edge);
}
}
}
}
@@
-399,10
+419,12
@@
static void initial_simplify_edges(pbqp *pbqp)
assert(pbqp);
assert(pbqp);
+#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_input(pbqp);
dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
}
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;
node_len = pbqp->num_nodes;
@@
-431,19
+453,35
@@
static void initial_simplify_edges(pbqp *pbqp)
}
}
}
}
-
num determine_solution(FILE *file
)
+
static num determine_solution(pbqp *pbqp
)
{
unsigned node_index;
unsigned node_len;
num solution = 0;
{
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");
}
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]);
/* 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);
for (node_index = 0; node_index < node_len; ++node_index) {
pbqp_node *node = node_buckets[0][node_index];
assert(node);
@@
-451,16
+489,21
@@
num determine_solution(FILE *file)
node->solution = vector_get_min_index(node->costs);
solution = pbqp_add(solution,
node->costs->entries[node->solution].data);
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);
}
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);
}
if (file) {
dump_section(file, 2, "Minimum");
fprintf(file, "Minimum is equal to %lld.", solution);
}
+#endif
return solution;
}
return solution;
}
@@
-471,9
+514,12
@@
static void back_propagate(pbqp *pbqp)
unsigned node_len = node_bucket_get_length(reduced_bucket);
assert(pbqp);
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");
}
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];
for (node_index = node_len; node_index > 0; --node_index) {
pbqp_node *node = reduced_bucket[node_index - 1];
@@
-517,11
+563,23
@@
void solve_pbqp_heuristical(pbqp *pbqp)
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
/* ... 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);
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);
/* Solve reduced nodes. */
back_propagate(pbqp);
@@
-552,6
+610,7
@@
void apply_RI(pbqp *pbqp)
other_node = edge->src;
}
other_node = edge->src;
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RI-Reduction of Node n%d", node->index);
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RI-Reduction of Node n%d", node->index);
@@
-562,6
+621,7
@@
void apply_RI(pbqp *pbqp)
dump_node(pbqp->dump_file, other_node);
dump_edge(pbqp->dump_file, edge);
}
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);
if (is_src) {
pbqp_matrix_add_to_all_cols(mat, node->costs);
@@
-572,13
+632,21
@@
void apply_RI(pbqp *pbqp)
}
disconnect_edge(other_node, edge);
}
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);
}
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);
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);
}
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
}
@@
-637,6
+705,7
@@
void apply_RII(pbqp *pbqp)
tgt_is_src = tgt_edge->src == 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);
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RII-Reduction of Node n%d", node->index);
@@
-649,6
+718,7
@@
void apply_RII(pbqp *pbqp)
dump_edge(pbqp->dump_file, tgt_edge);
dump_node(pbqp->dump_file, tgt_node);
}
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;
src_mat = src_edge->costs;
tgt_mat = tgt_edge->costs;
@@
-691,6
+761,12
@@
void apply_RII(pbqp *pbqp)
disconnect_edge(src_node, src_edge);
disconnect_edge(tgt_node, tgt_edge);
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);
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
@@
-706,10
+782,12
@@
void apply_RII(pbqp *pbqp)
reorder_node(tgt_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);
}
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);
/* Edge has changed so we simplify it. */
simplify_edge(pbqp, edge);
@@
-824,19
+902,32
@@
void apply_RN(pbqp *pbqp)
assert(node);
assert(pbqp_node_get_degree(node) > 2);
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);
}
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);
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);
}
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);
/* Now that we found the local minimum set all other costs to infinity. */
select_alternative(node, min_index);
@@
-880,6
+971,8
@@
static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
unsigned bucket_0_length;
unsigned bucket_red_length;
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. */
node_bucket_init(&bucket_deg3);
/* Some node buckets and the edge bucket should be empty. */
@@
-890,7
+983,10
@@
static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
/* char *tmp = obstack_finish(&pbqp->obstack); */
/* Save current PBQP state. */
/* 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);
bucket_0_length = node_bucket_get_length(node_buckets[0]);
bucket_red_length = node_bucket_get_length(reduced_bucket);
@@
-898,7
+994,7
@@
static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
select_alternative(node_buckets[3][bucket_index], node_index);
apply_brute_force_reductions(pbqp);
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;
if (value < min) {
min = value;
@@
-916,11
+1012,14
@@
static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
/* ... and restore old PBQP state. */
node_bucket_shrink(&node_buckets[0], bucket_0_length);
node_bucket_shrink(&reduced_bucket, bucket_red_length);
/* ... 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);
/* Free copies. */
/* obstack_free(&pbqp->obstack, tmp); */
node_bucket_free(&bucket_deg3);
+
+ obstack_free(&pbqp->obstack, tmp);
}
return min_index;
}
return min_index;
@@
-938,20
+1037,38
@@
void apply_Brute_Force(pbqp *pbqp)
assert(node);
assert(pbqp_node_get_degree(node) > 2);
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);
}
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];
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);
}
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);
/* Now that we found the minimum set all other costs to infinity. */
select_alternative(node, min_index);
@@
-965,11
+1082,23
@@
void solve_pbqp_brute_force(pbqp *pbqp)
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
/* ... 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);
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);
/* Solve reduced nodes. */
back_propagate(pbqp);
@@
-1000,7
+1129,7
@@
void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
/* Update pointer for brute force solver. */
other = pbqp->nodes[other->index];
/* 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);
} else {
other = edge->src;
assert(other);
@@
-1008,13
+1137,14
@@
void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
/* Update pointer for brute force solver. */
other = pbqp->nodes[other->index];
/* 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);
}
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)
}
void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
@@
-1090,9
+1220,12
@@
void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
}
node->solution = vector_get_min_index(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);
}
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);
}
obstack_free(&pbqp->obstack, vec);
}