2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Optimal reductions and helper functions.
24 * @author Sebastian Buchwald
28 #include "adt/array.h"
34 #include "html_dumper.h"
39 #include "pbqp_edge.h"
40 #include "pbqp_edge_t.h"
41 #include "pbqp_node.h"
42 #include "pbqp_node_t.h"
48 pbqp_edge_t **edge_bucket;
49 static pbqp_edge_t **rm_bucket;
50 pbqp_node_t **node_buckets[4];
51 pbqp_node_t **reduced_bucket = NULL;
52 pbqp_node_t *merged_node = NULL;
53 static int buckets_filled = 0;
55 static void insert_into_edge_bucket(pbqp_edge_t *edge)
57 if (edge_bucket_contains(edge_bucket, edge)) {
58 /* Edge is already inserted. */
62 edge_bucket_insert(&edge_bucket, edge);
65 static void insert_into_rm_bucket(pbqp_edge_t *edge)
67 if (edge_bucket_contains(rm_bucket, edge)) {
68 /* Edge is already inserted. */
72 edge_bucket_insert(&rm_bucket, edge);
75 static void init_buckets(void)
79 edge_bucket_init(&edge_bucket);
80 edge_bucket_init(&rm_bucket);
81 node_bucket_init(&reduced_bucket);
83 for (i = 0; i < 4; ++i) {
84 node_bucket_init(&node_buckets[i]);
88 void free_buckets(void)
92 for (i = 0; i < 4; ++i) {
93 node_bucket_free(&node_buckets[i]);
96 edge_bucket_free(&edge_bucket);
97 edge_bucket_free(&rm_bucket);
98 node_bucket_free(&reduced_bucket);
103 void fill_node_buckets(pbqp_t *pbqp)
108 node_len = pbqp->num_nodes;
111 ir_timer_t *t_fill_buckets = ir_timer_new();
112 ir_timer_start(t_fill_buckets);
115 for (node_index = 0; node_index < node_len; ++node_index) {
117 pbqp_node_t *node = get_node(pbqp, node_index);
121 degree = pbqp_node_get_degree(node);
123 /* We have only one bucket for nodes with arity >= 3. */
128 node_bucket_insert(&node_buckets[degree], node);
134 ir_timer_stop(t_fill_buckets);
135 printf("PBQP Fill Nodes into buckets: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
139 static void normalize_towards_source(pbqp_edge_t *edge)
142 pbqp_node_t *src_node;
143 pbqp_node_t *tgt_node;
149 unsigned new_infinity = 0;
151 src_node = edge->src;
152 tgt_node = edge->tgt;
154 src_vec = src_node->costs;
155 tgt_vec = tgt_node->costs;
157 src_len = src_vec->len;
158 tgt_len = tgt_vec->len;
164 /* Normalize towards source node. */
165 for (src_index = 0; src_index < src_len; ++src_index) {
166 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
169 if (src_vec->entries[src_index].data == INF_COSTS) {
170 pbqp_matrix_set_row_value(mat, src_index, 0);
174 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
175 src_vec->entries[src_index].data = pbqp_add(
176 src_vec->entries[src_index].data, min);
178 if (min == INF_COSTS) {
186 unsigned edge_len = pbqp_node_get_degree(src_node);
188 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
189 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
191 if (edge_candidate != edge) {
192 insert_into_edge_bucket(edge_candidate);
198 static void normalize_towards_target(pbqp_edge_t *edge)
201 pbqp_node_t *src_node;
202 pbqp_node_t *tgt_node;
208 unsigned new_infinity = 0;
210 src_node = edge->src;
211 tgt_node = edge->tgt;
213 src_vec = src_node->costs;
214 tgt_vec = tgt_node->costs;
216 src_len = src_vec->len;
217 tgt_len = tgt_vec->len;
223 /* Normalize towards target node. */
224 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
225 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
228 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
229 pbqp_matrix_set_col_value(mat, tgt_index, 0);
233 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
234 tgt_vec->entries[tgt_index].data = pbqp_add(
235 tgt_vec->entries[tgt_index].data, min);
237 if (min == INF_COSTS) {
245 unsigned edge_len = pbqp_node_get_degree(tgt_node);
247 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
248 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
250 if (edge_candidate != edge) {
251 insert_into_edge_bucket(edge_candidate);
258 * Tries to apply RM for the source node of the given edge.
260 * Checks whether the source node of edge can be merged into the target node of
261 * edge, and performs the merge, if possible.
263 static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
266 pbqp_node_t *src_node;
267 pbqp_node_t *tgt_node;
277 src_node = edge->src;
278 tgt_node = edge->tgt;
280 src_vec = src_node->costs;
281 tgt_vec = tgt_node->costs;
283 src_len = src_vec->len;
284 tgt_len = tgt_vec->len;
286 /* Matrizes are normalized. */
292 mapping = NEW_ARR_F(unsigned, tgt_len);
294 /* Check that each column has at most one zero entry. */
295 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
296 unsigned onlyOneZero = 0;
299 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
302 for (src_index = 0; src_index < src_len; ++src_index) {
303 if (src_vec->entries[src_index].data == INF_COSTS)
306 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
309 /* Matrix entry is finite. */
316 mapping[tgt_index] = src_index;
320 /* We know that we can merge the source node into the target node. */
321 edge_len = pbqp_node_get_degree(src_node);
328 if (pbqp->dump_file) {
330 sprintf(txt, "Merging n%d into n%d", src_node->index, tgt_node->index);
331 pbqp_dump_section(pbqp->dump_file, 3, txt);
335 /* Reconnect the source's edges with the target node. */
336 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
337 pbqp_edge_t *old_edge = src_node->edges[edge_index];
338 pbqp_edge_t *new_edge;
339 pbqp_matrix_t *old_matrix;
340 pbqp_matrix_t *new_matrix;
341 pbqp_node_t *other_node;
344 unsigned other_index;
347 if (old_edge == edge)
350 old_matrix = old_edge->costs;
352 if (old_edge->tgt == src_node) {
353 other_node = old_edge->src;
354 other_len = old_matrix->rows;
357 other_node = old_edge->tgt;
358 other_len = old_matrix->cols;
360 other_vec = other_node->costs;
362 new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
364 /* Source node selects the column of the old_matrix. */
365 if (old_edge->tgt == src_node) {
366 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
367 unsigned src_index = mapping[tgt_index];
369 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
372 for (other_index = 0; other_index < other_len; ++other_index) {
373 if (other_vec->entries[other_index].data == INF_COSTS)
376 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+src_index];
380 /* Source node selects the row of the old_matrix. */
382 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
383 unsigned src_index = mapping[tgt_index];
385 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
388 for (other_index = 0; other_index < other_len; ++other_index) {
389 if (other_vec->entries[other_index].data == INF_COSTS)
392 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[src_index*other_len+other_index];
397 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
399 add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
401 if (new_edge == NULL) {
402 reorder_node_after_edge_insertion(tgt_node);
403 reorder_node_after_edge_insertion(other_node);
406 delete_edge(old_edge);
408 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
409 simplify_edge(pbqp, new_edge);
411 insert_into_rm_bucket(new_edge);
420 * Tries to apply RM for the target node of the given edge.
422 * Checks whether the target node of edge can be merged into the source node of
423 * edge, and performs the merge, if possible.
425 static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
428 pbqp_node_t *src_node;
429 pbqp_node_t *tgt_node;
439 src_node = edge->src;
440 tgt_node = edge->tgt;
442 src_vec = src_node->costs;
443 tgt_vec = tgt_node->costs;
445 src_len = src_vec->len;
446 tgt_len = tgt_vec->len;
448 /* Matrizes are normalized. */
454 mapping = NEW_ARR_F(unsigned, src_len);
456 /* Check that each row has at most one zero entry. */
457 for (src_index = 0; src_index < src_len; ++src_index) {
458 unsigned onlyOneZero = 0;
461 if (src_vec->entries[src_index].data == INF_COSTS)
464 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
465 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
468 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
471 /* Matrix entry is finite. */
478 mapping[src_index] = tgt_index;
482 /* We know that we can merge the target node into the source node. */
483 edge_len = pbqp_node_get_degree(tgt_node);
490 if (pbqp->dump_file) {
492 sprintf(txt, "Merging n%d into n%d", tgt_node->index, src_node->index);
493 pbqp_dump_section(pbqp->dump_file, 3, txt);
497 /* Reconnect the target's edges with the source node. */
498 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
499 pbqp_edge_t *old_edge = tgt_node->edges[edge_index];
500 pbqp_edge_t *new_edge;
501 pbqp_matrix_t *old_matrix;
502 pbqp_matrix_t *new_matrix;
503 pbqp_node_t *other_node;
506 unsigned other_index;
510 if (old_edge == edge)
513 old_matrix = old_edge->costs;
515 if (old_edge->tgt == tgt_node) {
516 other_node = old_edge->src;
517 other_len = old_matrix->rows;
520 other_node = old_edge->tgt;
521 other_len = old_matrix->cols;
523 other_vec = other_node->costs;
525 new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len);
527 /* Target node selects the column of the old_matrix. */
528 if (old_edge->tgt == tgt_node) {
529 for (src_index = 0; src_index < src_len; ++src_index) {
530 unsigned tgt_index = mapping[src_index];
532 if (src_vec->entries[src_index].data == INF_COSTS)
535 for (other_index = 0; other_index < other_len; ++other_index) {
536 if (other_vec->entries[other_index].data == INF_COSTS)
539 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[other_index*tgt_len+tgt_index];
543 /* Source node selects the row of the old_matrix. */
545 for (src_index = 0; src_index < src_len; ++src_index) {
546 unsigned tgt_index = mapping[src_index];
548 if (src_vec->entries[src_index].data == INF_COSTS)
551 for (other_index = 0; other_index < other_len; ++other_index) {
552 if (other_vec->entries[other_index].data == INF_COSTS)
555 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[tgt_index*other_len+other_index];
560 new_edge = get_edge(pbqp, src_node->index, other_node->index);
562 add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
564 if (new_edge == NULL) {
565 reorder_node_after_edge_insertion(src_node);
566 reorder_node_after_edge_insertion(other_node);
569 delete_edge(old_edge);
571 new_edge = get_edge(pbqp, src_node->index, other_node->index);
572 simplify_edge(pbqp, new_edge);
574 insert_into_rm_bucket(new_edge);
583 * Merge neighbors into the given node.
585 void apply_RM(pbqp_t *pbqp, pbqp_node_t *node)
592 edge_len = pbqp_node_get_degree(node);
594 /* Check all incident edges. */
595 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
596 pbqp_edge_t *edge = edges[edge_index];
598 insert_into_rm_bucket(edge);
601 /* ALAP: Merge neighbors into given node. */
602 while(edge_bucket_get_length(rm_bucket) > 0) {
603 pbqp_edge_t *edge = edge_bucket_pop(&rm_bucket);
605 /* If the edge is not deleted: Try a merge. */
606 if (edge->src == node)
607 merge_target_into_source(pbqp, edge);
608 else if (edge->tgt == node)
609 merge_source_into_target(pbqp, edge);
615 void reorder_node_after_edge_deletion(pbqp_node_t *node)
617 unsigned degree = pbqp_node_get_degree(node);
618 /* Assume node lost one incident edge. */
619 unsigned old_degree = degree + 1;
621 if (!buckets_filled) return;
623 /* Same bucket as before */
624 if (degree > 2) return;
626 /* Delete node from old bucket... */
627 node_bucket_remove(&node_buckets[old_degree], node);
629 /* ..and add to new one. */
630 node_bucket_insert(&node_buckets[degree], node);
633 void reorder_node_after_edge_insertion(pbqp_node_t *node)
635 unsigned degree = pbqp_node_get_degree(node);
636 /* Assume node lost one incident edge. */
637 unsigned old_degree = degree - 1;
639 if (!buckets_filled) return;
641 /* Same bucket as before */
642 if (old_degree > 2) return;
644 /* Delete node from old bucket... */
645 node_bucket_remove(&node_buckets[old_degree], node);
647 /* ..and add to new one. */
648 node_bucket_insert(&node_buckets[degree], node);
651 void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
654 pbqp_node_t *src_node;
655 pbqp_node_t *tgt_node;
663 src_node = edge->src;
664 tgt_node = edge->tgt;
668 /* If edge are already deleted, we have nothing to do. */
669 if (is_deleted(edge))
673 if (pbqp->dump_file) {
675 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
676 pbqp_dump_section(pbqp->dump_file, 3, txt);
680 src_vec = src_node->costs;
681 tgt_vec = tgt_node->costs;
683 src_len = src_vec->len;
684 tgt_len = tgt_vec->len;
691 if (pbqp->dump_file) {
692 fputs("Input:<br>\n", pbqp->dump_file);
693 pbqp_dump_simplifyedge(pbqp, edge);
697 normalize_towards_source(edge);
698 normalize_towards_target(edge);
701 if (pbqp->dump_file) {
702 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
703 pbqp_dump_simplifyedge(pbqp, edge);
707 if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
709 if (pbqp->dump_file) {
710 fputs("edge has been eliminated<br>\n", pbqp->dump_file);
722 void initial_simplify_edges(pbqp_t *pbqp)
728 ir_timer_t *t_int_simpl = ir_timer_new();
729 ir_timer_start(t_int_simpl);
733 if (pbqp->dump_file) {
734 pbqp_dump_input(pbqp);
735 pbqp_dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
739 node_len = pbqp->num_nodes;
743 /* First simplify all edges. */
744 for (node_index = 0; node_index < node_len; ++node_index) {
746 pbqp_node_t *node = get_node(pbqp, node_index);
753 edge_len = pbqp_node_get_degree(node);
755 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
756 pbqp_edge_t *edge = edges[edge_index];
758 /* Simplify only once per edge. */
759 if (node != edge->src) continue;
761 simplify_edge(pbqp, edge);
766 ir_timer_stop(t_int_simpl);
767 printf("PBQP Initial simplify edges: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
771 num determine_solution(pbqp_t *pbqp)
778 ir_timer_t *t_det_solution = ir_timer_new();
779 ir_timer_reset_and_start(t_det_solution);
789 file = pbqp->dump_file;
792 pbqp_dump_section(file, 1, "4. Determine Solution/Minimum");
793 pbqp_dump_section(file, 2, "4.1. Trivial Solution");
797 /* Solve trivial nodes and calculate solution. */
798 node_len = node_bucket_get_length(node_buckets[0]);
801 pbqp->num_r0 = node_len;
804 for (node_index = 0; node_index < node_len; ++node_index) {
805 pbqp_node_t *node = node_buckets[0][node_index];
807 node->solution = vector_get_min_index(node->costs);
808 solution = pbqp_add(solution,
809 node->costs->entries[node->solution].data);
813 fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
814 pbqp_dump_node(file, node);
821 pbqp_dump_section(file, 2, "Minimum");
822 #if KAPS_USE_UNSIGNED
823 fprintf(file, "Minimum is equal to %u.", solution);
825 fprintf(file, "Minimum is equal to %lld.", solution);
831 ir_timer_stop(t_det_solution);
832 printf("PBQP Determine Solution: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
838 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
847 edge = node->edges[0];
849 is_src = edge->src == node;
854 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
857 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
861 if (pbqp->dump_file) {
862 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
867 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
869 pbqp_edge_t *src_edge = node->edges[0];
870 pbqp_edge_t *tgt_edge = node->edges[1];
871 int src_is_src = src_edge->src == node;
872 int tgt_is_src = tgt_edge->src == node;
873 pbqp_matrix_t *src_mat;
874 pbqp_matrix_t *tgt_mat;
875 pbqp_node_t *src_node;
876 pbqp_node_t *tgt_node;
883 src_node = src_edge->tgt;
885 src_node = src_edge->src;
889 tgt_node = tgt_edge->tgt;
891 tgt_node = tgt_edge->src;
894 /* Swap nodes if necessary. */
895 if (tgt_node->index < src_node->index) {
896 pbqp_node_t *tmp_node;
897 pbqp_edge_t *tmp_edge;
907 src_is_src = src_edge->src == node;
908 tgt_is_src = tgt_edge->src == node;
911 src_mat = src_edge->costs;
912 tgt_mat = tgt_edge->costs;
914 node_vec = node->costs;
916 row_index = src_node->solution;
917 col_index = tgt_node->solution;
919 vec = vector_copy(pbqp, node_vec);
922 vector_add_matrix_col(vec, src_mat, row_index);
924 vector_add_matrix_row(vec, src_mat, row_index);
928 vector_add_matrix_col(vec, tgt_mat, col_index);
930 vector_add_matrix_row(vec, tgt_mat, col_index);
933 node->solution = vector_get_min_index(vec);
936 if (pbqp->dump_file) {
937 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
941 obstack_free(&pbqp->obstack, vec);
944 void back_propagate(pbqp_t *pbqp)
947 unsigned node_len = node_bucket_get_length(reduced_bucket);
950 if (pbqp->dump_file) {
951 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
955 for (node_index = node_len; node_index > 0; --node_index) {
956 pbqp_node_t *node = reduced_bucket[node_index - 1];
958 switch (pbqp_node_get_degree(node)) {
960 back_propagate_RI(pbqp, node);
963 back_propagate_RII(pbqp, node);
966 panic("Only nodes with degree one or two should be in this bucket");
971 void apply_edge(pbqp_t *pbqp)
973 pbqp_edge_t *edge = edge_bucket_pop(&edge_bucket);
975 simplify_edge(pbqp, edge);
978 void apply_RI(pbqp_t *pbqp)
980 pbqp_node_t *node = node_bucket_pop(&node_buckets[1]);
981 pbqp_edge_t *edge = node->edges[0];
982 pbqp_matrix_t *mat = edge->costs;
983 int is_src = edge->src == node;
984 pbqp_node_t *other_node;
987 assert(pbqp_node_get_degree(node) == 1);
990 other_node = edge->tgt;
992 other_node = edge->src;
996 if (pbqp->dump_file) {
998 sprintf(txt, "RI-Reduction of Node n%d", node->index);
999 pbqp_dump_section(pbqp->dump_file, 2, txt);
1000 pbqp_dump_graph(pbqp);
1001 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1002 pbqp_dump_node(pbqp->dump_file, node);
1003 pbqp_dump_node(pbqp->dump_file, other_node);
1004 pbqp_dump_edge(pbqp->dump_file, edge);
1009 pbqp_matrix_add_to_all_cols(mat, node->costs);
1010 normalize_towards_target(edge);
1012 pbqp_matrix_add_to_all_rows(mat, node->costs);
1013 normalize_towards_source(edge);
1015 disconnect_edge(other_node, edge);
1018 if (pbqp->dump_file) {
1019 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1020 pbqp_dump_node(pbqp->dump_file, other_node);
1024 reorder_node_after_edge_deletion(other_node);
1030 /* Add node to back propagation list. */
1031 node_bucket_insert(&reduced_bucket, node);
1034 void apply_RII(pbqp_t *pbqp)
1036 pbqp_node_t *node = node_bucket_pop(&node_buckets[2]);
1037 pbqp_edge_t *src_edge = node->edges[0];
1038 pbqp_edge_t *tgt_edge = node->edges[1];
1039 int src_is_src = src_edge->src == node;
1040 int tgt_is_src = tgt_edge->src == node;
1041 pbqp_matrix_t *src_mat;
1042 pbqp_matrix_t *tgt_mat;
1043 pbqp_node_t *src_node;
1044 pbqp_node_t *tgt_node;
1056 assert(pbqp_node_get_degree(node) == 2);
1059 src_node = src_edge->tgt;
1061 src_node = src_edge->src;
1065 tgt_node = tgt_edge->tgt;
1067 tgt_node = tgt_edge->src;
1070 /* Swap nodes if necessary. */
1071 if (tgt_node->index < src_node->index) {
1072 pbqp_node_t *tmp_node;
1073 pbqp_edge_t *tmp_edge;
1075 tmp_node = src_node;
1076 src_node = tgt_node;
1077 tgt_node = tmp_node;
1079 tmp_edge = src_edge;
1080 src_edge = tgt_edge;
1081 tgt_edge = tmp_edge;
1083 src_is_src = src_edge->src == node;
1084 tgt_is_src = tgt_edge->src == node;
1088 if (pbqp->dump_file) {
1090 sprintf(txt, "RII-Reduction of Node n%d", node->index);
1091 pbqp_dump_section(pbqp->dump_file, 2, txt);
1092 pbqp_dump_graph(pbqp);
1093 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1094 pbqp_dump_node(pbqp->dump_file, src_node);
1095 pbqp_dump_edge(pbqp->dump_file, src_edge);
1096 pbqp_dump_node(pbqp->dump_file, node);
1097 pbqp_dump_edge(pbqp->dump_file, tgt_edge);
1098 pbqp_dump_node(pbqp->dump_file, tgt_node);
1102 src_mat = src_edge->costs;
1103 tgt_mat = tgt_edge->costs;
1105 src_vec = src_node->costs;
1106 tgt_vec = tgt_node->costs;
1107 node_vec = node->costs;
1109 row_len = src_vec->len;
1110 col_len = tgt_vec->len;
1112 mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
1114 for (row_index = 0; row_index < row_len; ++row_index) {
1115 for (col_index = 0; col_index < col_len; ++col_index) {
1116 vec = vector_copy(pbqp, node_vec);
1119 vector_add_matrix_col(vec, src_mat, row_index);
1121 vector_add_matrix_row(vec, src_mat, row_index);
1125 vector_add_matrix_col(vec, tgt_mat, col_index);
1127 vector_add_matrix_row(vec, tgt_mat, col_index);
1130 mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1132 obstack_free(&pbqp->obstack, vec);
1136 edge = get_edge(pbqp, src_node->index, tgt_node->index);
1138 /* Disconnect node. */
1139 disconnect_edge(src_node, src_edge);
1140 disconnect_edge(tgt_node, tgt_edge);
1146 /* Add node to back propagation list. */
1147 node_bucket_insert(&reduced_bucket, node);
1150 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1153 pbqp_matrix_add(edge->costs, mat);
1155 /* Free local matrix. */
1156 obstack_free(&pbqp->obstack, mat);
1158 reorder_node_after_edge_deletion(src_node);
1159 reorder_node_after_edge_deletion(tgt_node);
1163 if (pbqp->dump_file) {
1164 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1165 pbqp_dump_edge(pbqp->dump_file, edge);
1169 /* Edge has changed so we simplify it. */
1170 simplify_edge(pbqp, edge);
1173 static void select_column(pbqp_edge_t *edge, unsigned col_index)
1176 pbqp_node_t *src_node;
1177 pbqp_node_t *tgt_node;
1183 unsigned new_infinity = 0;
1185 src_node = edge->src;
1186 tgt_node = edge->tgt;
1188 src_vec = src_node->costs;
1189 tgt_vec = tgt_node->costs;
1191 src_len = src_vec->len;
1192 tgt_len = tgt_vec->len;
1193 assert(src_len > 0);
1194 assert(tgt_len > 0);
1198 for (src_index = 0; src_index < src_len; ++src_index) {
1199 num elem = mat->entries[src_index * tgt_len + col_index];
1202 if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
1205 src_vec->entries[src_index].data = pbqp_add(
1206 src_vec->entries[src_index].data, elem);
1211 unsigned edge_index;
1212 unsigned edge_len = pbqp_node_get_degree(src_node);
1214 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1215 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
1217 if (edge_candidate != edge) {
1218 insert_into_edge_bucket(edge_candidate);
1226 static void select_row(pbqp_edge_t *edge, unsigned row_index)
1229 pbqp_node_t *tgt_node;
1233 unsigned new_infinity = 0;
1235 tgt_node = edge->tgt;
1237 tgt_vec = tgt_node->costs;
1239 tgt_len = tgt_vec->len;
1240 assert(tgt_len > 0);
1244 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
1245 num elem = mat->entries[row_index * tgt_len + tgt_index];
1248 if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
1251 tgt_vec->entries[tgt_index].data = pbqp_add(
1252 tgt_vec->entries[tgt_index].data, elem);
1257 unsigned edge_index;
1258 unsigned edge_len = pbqp_node_get_degree(tgt_node);
1260 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1261 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
1263 if (edge_candidate != edge) {
1264 insert_into_edge_bucket(edge_candidate);
1272 void select_alternative(pbqp_node_t *node, unsigned selected_index)
1274 unsigned edge_index;
1275 unsigned node_index;
1278 unsigned max_degree = pbqp_node_get_degree(node);
1280 node->solution = selected_index;
1281 node_vec = node->costs;
1282 node_len = node_vec->len;
1283 assert(selected_index < node_len);
1285 /* Set all other costs to infinity. */
1286 for (node_index = 0; node_index < node_len; ++node_index) {
1287 if (node_index != selected_index) {
1288 node_vec->entries[node_index].data = INF_COSTS;
1292 /* Select corresponding row/column for incident edges. */
1293 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1294 pbqp_edge_t *edge = node->edges[edge_index];
1296 if (edge->src == node)
1297 select_row(edge, selected_index);
1299 select_column(edge, selected_index);
1303 pbqp_node_t *get_node_with_max_degree(void)
1305 pbqp_node_t **bucket = node_buckets[3];
1306 unsigned bucket_len = node_bucket_get_length(bucket);
1307 unsigned bucket_index;
1308 unsigned max_degree = 0;
1309 pbqp_node_t *result = NULL;
1311 for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1312 pbqp_node_t *candidate = bucket[bucket_index];
1313 unsigned degree = pbqp_node_get_degree(candidate);
1315 if (degree > max_degree) {
1317 max_degree = degree;
1324 unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
1330 unsigned edge_index;
1331 unsigned max_degree;
1332 unsigned node_index;
1334 unsigned min_index = 0;
1335 num min = INF_COSTS;
1338 node_vec = node->costs;
1339 node_len = node_vec->len;
1340 max_degree = pbqp_node_get_degree(node);
1342 for (node_index = 0; node_index < node_len; ++node_index) {
1343 num value = node_vec->entries[node_index].data;
1345 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1346 edge = node->edges[edge_index];
1348 is_src = edge->src == node;
1351 vec = vector_copy(pbqp, edge->tgt->costs);
1352 vector_add_matrix_row(vec, mat, node_index);
1354 vec = vector_copy(pbqp, edge->src->costs);
1355 vector_add_matrix_col(vec, mat, node_index);
1358 value = pbqp_add(value, vector_get_min(vec));
1360 obstack_free(&pbqp->obstack, vec);
1365 min_index = node_index;
1372 int node_is_reduced(pbqp_node_t *node)
1374 if (!reduced_bucket) return 0;
1376 if (pbqp_node_get_degree(node) == 0) return 1;
1378 return node_bucket_contains(reduced_bucket, node);