1 /*
2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file
22 * @brief Optimal reductions and helper functions.
23 * @date 28.12.2009
24 * @author Sebastian Buchwald
25 */
26 #include "config.h"
27
28 #include "adt/array.h"
29 #include "assert.h"
30 #include "error.h"
31
32 #include "bucket.h"
33 #if KAPS_DUMP
34 #include "html_dumper.h"
35 #endif
36 #include "kaps.h"
37 #include "matrix.h"
38 #include "optimal.h"
39 #include "pbqp_edge.h"
40 #include "pbqp_edge_t.h"
41 #include "pbqp_node.h"
42 #include "pbqp_node_t.h"
43 #include "vector.h"
44
45 #include "plist.h"
46 #include "timing.h"
47
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;
54
insert_into_edge_bucket(pbqp_edge_t * edge)55 static void insert_into_edge_bucket(pbqp_edge_t *edge)
56 {
57 if (edge_bucket_contains(edge_bucket, edge)) {
58 /* Edge is already inserted. */
59 return;
60 }
61
62 edge_bucket_insert(&edge_bucket, edge);
63 }
64
insert_into_rm_bucket(pbqp_edge_t * edge)65 static void insert_into_rm_bucket(pbqp_edge_t *edge)
66 {
67 if (edge_bucket_contains(rm_bucket, edge)) {
68 /* Edge is already inserted. */
69 return;
70 }
71
72 edge_bucket_insert(&rm_bucket, edge);
73 }
74
init_buckets(void)75 static void init_buckets(void)
76 {
77 int i;
78
79 edge_bucket_init(&edge_bucket);
80 edge_bucket_init(&rm_bucket);
81 node_bucket_init(&reduced_bucket);
82
83 for (i = 0; i < 4; ++i) {
84 node_bucket_init(&node_buckets[i]);
85 }
86 }
87
free_buckets(void)88 void free_buckets(void)
89 {
90 int i;
91
92 for (i = 0; i < 4; ++i) {
93 node_bucket_free(&node_buckets[i]);
94 }
95
96 edge_bucket_free(&edge_bucket);
97 edge_bucket_free(&rm_bucket);
98 node_bucket_free(&reduced_bucket);
99
100 buckets_filled = 0;
101 }
102
fill_node_buckets(pbqp_t * pbqp)103 void fill_node_buckets(pbqp_t *pbqp)
104 {
105 unsigned node_index;
106 unsigned node_len;
107
108 node_len = pbqp->num_nodes;
109
110 #if KAPS_TIMING
111 ir_timer_t *t_fill_buckets = ir_timer_new();
112 ir_timer_start(t_fill_buckets);
113 #endif
114
115 for (node_index = 0; node_index < node_len; ++node_index) {
116 unsigned degree;
117 pbqp_node_t *node = get_node(pbqp, node_index);
118
119 if (!node) continue;
120
121 degree = pbqp_node_get_degree(node);
122
123 /* We have only one bucket for nodes with arity >= 3. */
124 if (degree > 3) {
125 degree = 3;
126 }
127
128 node_bucket_insert(&node_buckets[degree], node);
129 }
130
131 buckets_filled = 1;
132
133 #if KAPS_TIMING
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);
136 #endif
137 }
138
normalize_towards_source(pbqp_edge_t * edge)139 static void normalize_towards_source(pbqp_edge_t *edge)
140 {
141 pbqp_matrix_t *mat;
142 pbqp_node_t *src_node;
143 pbqp_node_t *tgt_node;
144 vector_t *src_vec;
145 vector_t *tgt_vec;
146 unsigned src_len;
147 unsigned tgt_len;
148 unsigned src_index;
149 unsigned new_infinity = 0;
150
151 src_node = edge->src;
152 tgt_node = edge->tgt;
153
154 src_vec = src_node->costs;
155 tgt_vec = tgt_node->costs;
156
157 src_len = src_vec->len;
158 tgt_len = tgt_vec->len;
159 assert(src_len > 0);
160 assert(tgt_len > 0);
161
162 mat = edge->costs;
163
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);
167
168 if (min != 0) {
169 if (src_vec->entries[src_index].data == INF_COSTS) {
170 pbqp_matrix_set_row_value(mat, src_index, 0);
171 continue;
172 }
173
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);
177
178 if (min == INF_COSTS) {
179 new_infinity = 1;
180 }
181 }
182 }
183
184 if (new_infinity) {
185 unsigned edge_index;
186 unsigned edge_len = pbqp_node_get_degree(src_node);
187
188 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
189 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
190
191 if (edge_candidate != edge) {
192 insert_into_edge_bucket(edge_candidate);
193 }
194 }
195 }
196 }
197
normalize_towards_target(pbqp_edge_t * edge)198 static void normalize_towards_target(pbqp_edge_t *edge)
199 {
200 pbqp_matrix_t *mat;
201 pbqp_node_t *src_node;
202 pbqp_node_t *tgt_node;
203 vector_t *src_vec;
204 vector_t *tgt_vec;
205 unsigned src_len;
206 unsigned tgt_len;
207 unsigned tgt_index;
208 unsigned new_infinity = 0;
209
210 src_node = edge->src;
211 tgt_node = edge->tgt;
212
213 src_vec = src_node->costs;
214 tgt_vec = tgt_node->costs;
215
216 src_len = src_vec->len;
217 tgt_len = tgt_vec->len;
218 assert(src_len > 0);
219 assert(tgt_len > 0);
220
221 mat = edge->costs;
222
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);
226
227 if (min != 0) {
228 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
229 pbqp_matrix_set_col_value(mat, tgt_index, 0);
230 continue;
231 }
232
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);
236
237 if (min == INF_COSTS) {
238 new_infinity = 1;
239 }
240 }
241 }
242
243 if (new_infinity) {
244 unsigned edge_index;
245 unsigned edge_len = pbqp_node_get_degree(tgt_node);
246
247 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
248 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
249
250 if (edge_candidate != edge) {
251 insert_into_edge_bucket(edge_candidate);
252 }
253 }
254 }
255 }
256
257 /**
258 * Tries to apply RM for the source node of the given edge.
259 *
260 * Checks whether the source node of edge can be merged into the target node of
261 * edge, and performs the merge, if possible.
262 */
merge_source_into_target(pbqp_t * pbqp,pbqp_edge_t * edge)263 static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
264 {
265 pbqp_matrix_t *mat;
266 pbqp_node_t *src_node;
267 pbqp_node_t *tgt_node;
268 vector_t *src_vec;
269 vector_t *tgt_vec;
270 unsigned *mapping;
271 unsigned src_len;
272 unsigned tgt_len;
273 unsigned tgt_index;
274 unsigned edge_index;
275 unsigned edge_len;
276
277 src_node = edge->src;
278 tgt_node = edge->tgt;
279
280 src_vec = src_node->costs;
281 tgt_vec = tgt_node->costs;
282
283 src_len = src_vec->len;
284 tgt_len = tgt_vec->len;
285
286 /* Matrizes are normalized. */
287 assert(src_len > 1);
288 assert(tgt_len > 1);
289
290 mat = edge->costs;
291
292 mapping = NEW_ARR_F(unsigned, tgt_len);
293
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;
297 unsigned src_index;
298
299 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
300 continue;
301
302 for (src_index = 0; src_index < src_len; ++src_index) {
303 if (src_vec->entries[src_index].data == INF_COSTS)
304 continue;
305
306 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
307 continue;
308
309 /* Matrix entry is finite. */
310 if (onlyOneZero) {
311 DEL_ARR_F(mapping);
312 return;
313 }
314
315 onlyOneZero = 1;
316 mapping[tgt_index] = src_index;
317 }
318 }
319
320 /* We know that we can merge the source node into the target node. */
321 edge_len = pbqp_node_get_degree(src_node);
322
323 #if KAPS_STATISTIC
324 pbqp->num_rm++;
325 #endif
326
327 #if KAPS_DUMP
328 if (pbqp->dump_file) {
329 char txt[100];
330 sprintf(txt, "Merging n%d into n%d", src_node->index, tgt_node->index);
331 pbqp_dump_section(pbqp->dump_file, 3, txt);
332 }
333 #endif
334
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;
342 vector_t *other_vec;
343 unsigned other_len;
344 unsigned other_index;
345
346 assert(old_edge);
347 if (old_edge == edge)
348 continue;
349
350 old_matrix = old_edge->costs;
351
352 if (old_edge->tgt == src_node) {
353 other_node = old_edge->src;
354 other_len = old_matrix->rows;
355 }
356 else {
357 other_node = old_edge->tgt;
358 other_len = old_matrix->cols;
359 }
360 other_vec = other_node->costs;
361
362 new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
363
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];
368
369 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
370 continue;
371
372 for (other_index = 0; other_index < other_len; ++other_index) {
373 if (other_vec->entries[other_index].data == INF_COSTS)
374 continue;
375
376 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+src_index];
377 }
378 }
379 }
380 /* Source node selects the row of the old_matrix. */
381 else {
382 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
383 unsigned src_index = mapping[tgt_index];
384
385 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
386 continue;
387
388 for (other_index = 0; other_index < other_len; ++other_index) {
389 if (other_vec->entries[other_index].data == INF_COSTS)
390 continue;
391
392 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[src_index*other_len+other_index];
393 }
394 }
395 }
396
397 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
398
399 add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
400
401 if (new_edge == NULL) {
402 reorder_node_after_edge_insertion(tgt_node);
403 reorder_node_after_edge_insertion(other_node);
404 }
405
406 delete_edge(old_edge);
407
408 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
409 simplify_edge(pbqp, new_edge);
410
411 insert_into_rm_bucket(new_edge);
412 }
413
414 #if KAPS_STATISTIC
415 pbqp->num_r1--;
416 #endif
417 }
418
419 /**
420 * Tries to apply RM for the target node of the given edge.
421 *
422 * Checks whether the target node of edge can be merged into the source node of
423 * edge, and performs the merge, if possible.
424 */
merge_target_into_source(pbqp_t * pbqp,pbqp_edge_t * edge)425 static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
426 {
427 pbqp_matrix_t *mat;
428 pbqp_node_t *src_node;
429 pbqp_node_t *tgt_node;
430 vector_t *src_vec;
431 vector_t *tgt_vec;
432 unsigned *mapping;
433 unsigned src_len;
434 unsigned tgt_len;
435 unsigned src_index;
436 unsigned edge_index;
437 unsigned edge_len;
438
439 src_node = edge->src;
440 tgt_node = edge->tgt;
441
442 src_vec = src_node->costs;
443 tgt_vec = tgt_node->costs;
444
445 src_len = src_vec->len;
446 tgt_len = tgt_vec->len;
447
448 /* Matrizes are normalized. */
449 assert(src_len > 1);
450 assert(tgt_len > 1);
451
452 mat = edge->costs;
453
454 mapping = NEW_ARR_F(unsigned, src_len);
455
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;
459 unsigned tgt_index;
460
461 if (src_vec->entries[src_index].data == INF_COSTS)
462 continue;
463
464 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
465 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
466 continue;
467
468 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
469 continue;
470
471 /* Matrix entry is finite. */
472 if (onlyOneZero) {
473 DEL_ARR_F(mapping);
474 return;
475 }
476
477 onlyOneZero = 1;
478 mapping[src_index] = tgt_index;
479 }
480 }
481
482 /* We know that we can merge the target node into the source node. */
483 edge_len = pbqp_node_get_degree(tgt_node);
484
485 #if KAPS_STATISTIC
486 pbqp->num_rm++;
487 #endif
488
489 #if KAPS_DUMP
490 if (pbqp->dump_file) {
491 char txt[100];
492 sprintf(txt, "Merging n%d into n%d", tgt_node->index, src_node->index);
493 pbqp_dump_section(pbqp->dump_file, 3, txt);
494 }
495 #endif
496
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;
504 vector_t *other_vec;
505 unsigned other_len;
506 unsigned other_index;
507
508 assert(old_edge);
509
510 if (old_edge == edge)
511 continue;
512
513 old_matrix = old_edge->costs;
514
515 if (old_edge->tgt == tgt_node) {
516 other_node = old_edge->src;
517 other_len = old_matrix->rows;
518 }
519 else {
520 other_node = old_edge->tgt;
521 other_len = old_matrix->cols;
522 }
523 other_vec = other_node->costs;
524
525 new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len);
526
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];
531
532 if (src_vec->entries[src_index].data == INF_COSTS)
533 continue;
534
535 for (other_index = 0; other_index < other_len; ++other_index) {
536 if (other_vec->entries[other_index].data == INF_COSTS)
537 continue;
538
539 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[other_index*tgt_len+tgt_index];
540 }
541 }
542 }
543 /* Source node selects the row of the old_matrix. */
544 else {
545 for (src_index = 0; src_index < src_len; ++src_index) {
546 unsigned tgt_index = mapping[src_index];
547
548 if (src_vec->entries[src_index].data == INF_COSTS)
549 continue;
550
551 for (other_index = 0; other_index < other_len; ++other_index) {
552 if (other_vec->entries[other_index].data == INF_COSTS)
553 continue;
554
555 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[tgt_index*other_len+other_index];
556 }
557 }
558 }
559
560 new_edge = get_edge(pbqp, src_node->index, other_node->index);
561
562 add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
563
564 if (new_edge == NULL) {
565 reorder_node_after_edge_insertion(src_node);
566 reorder_node_after_edge_insertion(other_node);
567 }
568
569 delete_edge(old_edge);
570
571 new_edge = get_edge(pbqp, src_node->index, other_node->index);
572 simplify_edge(pbqp, new_edge);
573
574 insert_into_rm_bucket(new_edge);
575 }
576
577 #if KAPS_STATISTIC
578 pbqp->num_r1--;
579 #endif
580 }
581
582 /**
583 * Merge neighbors into the given node.
584 */
apply_RM(pbqp_t * pbqp,pbqp_node_t * node)585 void apply_RM(pbqp_t *pbqp, pbqp_node_t *node)
586 {
587 pbqp_edge_t **edges;
588 unsigned edge_index;
589 unsigned edge_len;
590
591 edges = node->edges;
592 edge_len = pbqp_node_get_degree(node);
593
594 /* Check all incident edges. */
595 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
596 pbqp_edge_t *edge = edges[edge_index];
597
598 insert_into_rm_bucket(edge);
599 }
600
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);
604
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);
610 }
611
612 merged_node = node;
613 }
614
reorder_node_after_edge_deletion(pbqp_node_t * node)615 void reorder_node_after_edge_deletion(pbqp_node_t *node)
616 {
617 unsigned degree = pbqp_node_get_degree(node);
618 /* Assume node lost one incident edge. */
619 unsigned old_degree = degree + 1;
620
621 if (!buckets_filled) return;
622
623 /* Same bucket as before */
624 if (degree > 2) return;
625
626 /* Delete node from old bucket... */
627 node_bucket_remove(&node_buckets[old_degree], node);
628
629 /* ..and add to new one. */
630 node_bucket_insert(&node_buckets[degree], node);
631 }
632
reorder_node_after_edge_insertion(pbqp_node_t * node)633 void reorder_node_after_edge_insertion(pbqp_node_t *node)
634 {
635 unsigned degree = pbqp_node_get_degree(node);
636 /* Assume node lost one incident edge. */
637 unsigned old_degree = degree - 1;
638
639 if (!buckets_filled) return;
640
641 /* Same bucket as before */
642 if (old_degree > 2) return;
643
644 /* Delete node from old bucket... */
645 node_bucket_remove(&node_buckets[old_degree], node);
646
647 /* ..and add to new one. */
648 node_bucket_insert(&node_buckets[degree], node);
649 }
650
simplify_edge(pbqp_t * pbqp,pbqp_edge_t * edge)651 void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
652 {
653 pbqp_matrix_t *mat;
654 pbqp_node_t *src_node;
655 pbqp_node_t *tgt_node;
656 vector_t *src_vec;
657 vector_t *tgt_vec;
658 int src_len;
659 int tgt_len;
660
661 (void) pbqp;
662
663 src_node = edge->src;
664 tgt_node = edge->tgt;
665 assert(src_node);
666 assert(tgt_node);
667
668 /* If edge are already deleted, we have nothing to do. */
669 if (is_deleted(edge))
670 return;
671
672 #if KAPS_DUMP
673 if (pbqp->dump_file) {
674 char txt[100];
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);
677 }
678 #endif
679
680 src_vec = src_node->costs;
681 tgt_vec = tgt_node->costs;
682
683 src_len = src_vec->len;
684 tgt_len = tgt_vec->len;
685 assert(src_len > 0);
686 assert(tgt_len > 0);
687
688 mat = edge->costs;
689
690 #if KAPS_DUMP
691 if (pbqp->dump_file) {
692 fputs("Input:<br>\n", pbqp->dump_file);
693 pbqp_dump_simplifyedge(pbqp, edge);
694 }
695 #endif
696
697 normalize_towards_source(edge);
698 normalize_towards_target(edge);
699
700 #if KAPS_DUMP
701 if (pbqp->dump_file) {
702 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
703 pbqp_dump_simplifyedge(pbqp, edge);
704 }
705 #endif
706
707 if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
708 #if KAPS_DUMP
709 if (pbqp->dump_file) {
710 fputs("edge has been eliminated<br>\n", pbqp->dump_file);
711 }
712 #endif
713
714 #if KAPS_STATISTIC
715 pbqp->num_edges++;
716 #endif
717
718 delete_edge(edge);
719 }
720 }
721
initial_simplify_edges(pbqp_t * pbqp)722 void initial_simplify_edges(pbqp_t *pbqp)
723 {
724 unsigned node_index;
725 unsigned node_len;
726
727 #if KAPS_TIMING
728 ir_timer_t *t_int_simpl = ir_timer_new();
729 ir_timer_start(t_int_simpl);
730 #endif
731
732 #if KAPS_DUMP
733 if (pbqp->dump_file) {
734 pbqp_dump_input(pbqp);
735 pbqp_dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
736 }
737 #endif
738
739 node_len = pbqp->num_nodes;
740
741 init_buckets();
742
743 /* First simplify all edges. */
744 for (node_index = 0; node_index < node_len; ++node_index) {
745 unsigned edge_index;
746 pbqp_node_t *node = get_node(pbqp, node_index);
747 pbqp_edge_t **edges;
748 unsigned edge_len;
749
750 if (!node) continue;
751
752 edges = node->edges;
753 edge_len = pbqp_node_get_degree(node);
754
755 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
756 pbqp_edge_t *edge = edges[edge_index];
757
758 /* Simplify only once per edge. */
759 if (node != edge->src) continue;
760
761 simplify_edge(pbqp, edge);
762 }
763 }
764
765 #if KAPS_TIMING
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);
768 #endif
769 }
770
determine_solution(pbqp_t * pbqp)771 num determine_solution(pbqp_t *pbqp)
772 {
773 unsigned node_index;
774 unsigned node_len;
775 num solution = 0;
776
777 #if KAPS_TIMING
778 ir_timer_t *t_det_solution = ir_timer_new();
779 ir_timer_reset_and_start(t_det_solution);
780 #endif
781
782 #if KAPS_DUMP
783 FILE *file;
784 #endif
785
786 (void) pbqp;
787
788 #if KAPS_DUMP
789 file = pbqp->dump_file;
790
791 if (file) {
792 pbqp_dump_section(file, 1, "4. Determine Solution/Minimum");
793 pbqp_dump_section(file, 2, "4.1. Trivial Solution");
794 }
795 #endif
796
797 /* Solve trivial nodes and calculate solution. */
798 node_len = node_bucket_get_length(node_buckets[0]);
799
800 #if KAPS_STATISTIC
801 pbqp->num_r0 = node_len;
802 #endif
803
804 for (node_index = 0; node_index < node_len; ++node_index) {
805 pbqp_node_t *node = node_buckets[0][node_index];
806
807 node->solution = vector_get_min_index(node->costs);
808 solution = pbqp_add(solution,
809 node->costs->entries[node->solution].data);
810
811 #if KAPS_DUMP
812 if (file) {
813 fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
814 pbqp_dump_node(file, node);
815 }
816 #endif
817 }
818
819 #if KAPS_DUMP
820 if (file) {
821 pbqp_dump_section(file, 2, "Minimum");
822 #if KAPS_USE_UNSIGNED
823 fprintf(file, "Minimum is equal to %u.", solution);
824 #else
825 fprintf(file, "Minimum is equal to %lld.", solution);
826 #endif
827 }
828 #endif
829
830 #if KAPS_TIMING
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);
833 #endif
834
835 return solution;
836 }
837
back_propagate_RI(pbqp_t * pbqp,pbqp_node_t * node)838 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
839 {
840 pbqp_edge_t *edge;
841 pbqp_node_t *other;
842 pbqp_matrix_t *mat;
843 vector_t *vec;
844 int is_src;
845 (void) pbqp;
846
847 edge = node->edges[0];
848 mat = edge->costs;
849 is_src = edge->src == node;
850 vec = node->costs;
851
852 if (is_src) {
853 other = edge->tgt;
854 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
855 } else {
856 other = edge->src;
857 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
858 }
859
860 #if KAPS_DUMP
861 if (pbqp->dump_file) {
862 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
863 }
864 #endif
865 }
866
back_propagate_RII(pbqp_t * pbqp,pbqp_node_t * node)867 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
868 {
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;
877 vector_t *vec;
878 vector_t *node_vec;
879 unsigned col_index;
880 unsigned row_index;
881
882 if (src_is_src) {
883 src_node = src_edge->tgt;
884 } else {
885 src_node = src_edge->src;
886 }
887
888 if (tgt_is_src) {
889 tgt_node = tgt_edge->tgt;
890 } else {
891 tgt_node = tgt_edge->src;
892 }
893
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;
898
899 tmp_node = src_node;
900 src_node = tgt_node;
901 tgt_node = tmp_node;
902
903 tmp_edge = src_edge;
904 src_edge = tgt_edge;
905 tgt_edge = tmp_edge;
906
907 src_is_src = src_edge->src == node;
908 tgt_is_src = tgt_edge->src == node;
909 }
910
911 src_mat = src_edge->costs;
912 tgt_mat = tgt_edge->costs;
913
914 node_vec = node->costs;
915
916 row_index = src_node->solution;
917 col_index = tgt_node->solution;
918
919 vec = vector_copy(pbqp, node_vec);
920
921 if (src_is_src) {
922 vector_add_matrix_col(vec, src_mat, row_index);
923 } else {
924 vector_add_matrix_row(vec, src_mat, row_index);
925 }
926
927 if (tgt_is_src) {
928 vector_add_matrix_col(vec, tgt_mat, col_index);
929 } else {
930 vector_add_matrix_row(vec, tgt_mat, col_index);
931 }
932
933 node->solution = vector_get_min_index(vec);
934
935 #if KAPS_DUMP
936 if (pbqp->dump_file) {
937 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
938 }
939 #endif
940
941 obstack_free(&pbqp->obstack, vec);
942 }
943
back_propagate(pbqp_t * pbqp)944 void back_propagate(pbqp_t *pbqp)
945 {
946 unsigned node_index;
947 unsigned node_len = node_bucket_get_length(reduced_bucket);
948
949 #if KAPS_DUMP
950 if (pbqp->dump_file) {
951 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
952 }
953 #endif
954
955 for (node_index = node_len; node_index > 0; --node_index) {
956 pbqp_node_t *node = reduced_bucket[node_index - 1];
957
958 switch (pbqp_node_get_degree(node)) {
959 case 1:
960 back_propagate_RI(pbqp, node);
961 break;
962 case 2:
963 back_propagate_RII(pbqp, node);
964 break;
965 default:
966 panic("Only nodes with degree one or two should be in this bucket");
967 }
968 }
969 }
970
apply_edge(pbqp_t * pbqp)971 void apply_edge(pbqp_t *pbqp)
972 {
973 pbqp_edge_t *edge = edge_bucket_pop(&edge_bucket);
974
975 simplify_edge(pbqp, edge);
976 }
977
apply_RI(pbqp_t * pbqp)978 void apply_RI(pbqp_t *pbqp)
979 {
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;
985
986 (void) pbqp;
987 assert(pbqp_node_get_degree(node) == 1);
988
989 if (is_src) {
990 other_node = edge->tgt;
991 } else {
992 other_node = edge->src;
993 }
994
995 #if KAPS_DUMP
996 if (pbqp->dump_file) {
997 char txt[100];
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);
1005 }
1006 #endif
1007
1008 if (is_src) {
1009 pbqp_matrix_add_to_all_cols(mat, node->costs);
1010 normalize_towards_target(edge);
1011 } else {
1012 pbqp_matrix_add_to_all_rows(mat, node->costs);
1013 normalize_towards_source(edge);
1014 }
1015 disconnect_edge(other_node, edge);
1016
1017 #if KAPS_DUMP
1018 if (pbqp->dump_file) {
1019 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1020 pbqp_dump_node(pbqp->dump_file, other_node);
1021 }
1022 #endif
1023
1024 reorder_node_after_edge_deletion(other_node);
1025
1026 #if KAPS_STATISTIC
1027 pbqp->num_r1++;
1028 #endif
1029
1030 /* Add node to back propagation list. */
1031 node_bucket_insert(&reduced_bucket, node);
1032 }
1033
apply_RII(pbqp_t * pbqp)1034 void apply_RII(pbqp_t *pbqp)
1035 {
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;
1045 pbqp_edge_t *edge;
1046 pbqp_matrix_t *mat;
1047 vector_t *vec;
1048 vector_t *node_vec;
1049 vector_t *src_vec;
1050 vector_t *tgt_vec;
1051 unsigned col_index;
1052 unsigned col_len;
1053 unsigned row_index;
1054 unsigned row_len;
1055
1056 assert(pbqp_node_get_degree(node) == 2);
1057
1058 if (src_is_src) {
1059 src_node = src_edge->tgt;
1060 } else {
1061 src_node = src_edge->src;
1062 }
1063
1064 if (tgt_is_src) {
1065 tgt_node = tgt_edge->tgt;
1066 } else {
1067 tgt_node = tgt_edge->src;
1068 }
1069
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;
1074
1075 tmp_node = src_node;
1076 src_node = tgt_node;
1077 tgt_node = tmp_node;
1078
1079 tmp_edge = src_edge;
1080 src_edge = tgt_edge;
1081 tgt_edge = tmp_edge;
1082
1083 src_is_src = src_edge->src == node;
1084 tgt_is_src = tgt_edge->src == node;
1085 }
1086
1087 #if KAPS_DUMP
1088 if (pbqp->dump_file) {
1089 char txt[100];
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);
1099 }
1100 #endif
1101
1102 src_mat = src_edge->costs;
1103 tgt_mat = tgt_edge->costs;
1104
1105 src_vec = src_node->costs;
1106 tgt_vec = tgt_node->costs;
1107 node_vec = node->costs;
1108
1109 row_len = src_vec->len;
1110 col_len = tgt_vec->len;
1111
1112 mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
1113
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);
1117
1118 if (src_is_src) {
1119 vector_add_matrix_col(vec, src_mat, row_index);
1120 } else {
1121 vector_add_matrix_row(vec, src_mat, row_index);
1122 }
1123
1124 if (tgt_is_src) {
1125 vector_add_matrix_col(vec, tgt_mat, col_index);
1126 } else {
1127 vector_add_matrix_row(vec, tgt_mat, col_index);
1128 }
1129
1130 mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1131
1132 obstack_free(&pbqp->obstack, vec);
1133 }
1134 }
1135
1136 edge = get_edge(pbqp, src_node->index, tgt_node->index);
1137
1138 /* Disconnect node. */
1139 disconnect_edge(src_node, src_edge);
1140 disconnect_edge(tgt_node, tgt_edge);
1141
1142 #if KAPS_STATISTIC
1143 pbqp->num_r2++;
1144 #endif
1145
1146 /* Add node to back propagation list. */
1147 node_bucket_insert(&reduced_bucket, node);
1148
1149 if (edge == NULL) {
1150 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1151 } else {
1152 // matrix
1153 pbqp_matrix_add(edge->costs, mat);
1154
1155 /* Free local matrix. */
1156 obstack_free(&pbqp->obstack, mat);
1157
1158 reorder_node_after_edge_deletion(src_node);
1159 reorder_node_after_edge_deletion(tgt_node);
1160 }
1161
1162 #if KAPS_DUMP
1163 if (pbqp->dump_file) {
1164 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1165 pbqp_dump_edge(pbqp->dump_file, edge);
1166 }
1167 #endif
1168
1169 /* Edge has changed so we simplify it. */
1170 simplify_edge(pbqp, edge);
1171 }
1172
select_column(pbqp_edge_t * edge,unsigned col_index)1173 static void select_column(pbqp_edge_t *edge, unsigned col_index)
1174 {
1175 pbqp_matrix_t *mat;
1176 pbqp_node_t *src_node;
1177 pbqp_node_t *tgt_node;
1178 vector_t *src_vec;
1179 vector_t *tgt_vec;
1180 unsigned src_len;
1181 unsigned tgt_len;
1182 unsigned src_index;
1183 unsigned new_infinity = 0;
1184
1185 src_node = edge->src;
1186 tgt_node = edge->tgt;
1187
1188 src_vec = src_node->costs;
1189 tgt_vec = tgt_node->costs;
1190
1191 src_len = src_vec->len;
1192 tgt_len = tgt_vec->len;
1193 assert(src_len > 0);
1194 assert(tgt_len > 0);
1195
1196 mat = edge->costs;
1197
1198 for (src_index = 0; src_index < src_len; ++src_index) {
1199 num elem = mat->entries[src_index * tgt_len + col_index];
1200
1201 if (elem != 0) {
1202 if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
1203 new_infinity = 1;
1204
1205 src_vec->entries[src_index].data = pbqp_add(
1206 src_vec->entries[src_index].data, elem);
1207 }
1208 }
1209
1210 if (new_infinity) {
1211 unsigned edge_index;
1212 unsigned edge_len = pbqp_node_get_degree(src_node);
1213
1214 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1215 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
1216
1217 if (edge_candidate != edge) {
1218 insert_into_edge_bucket(edge_candidate);
1219 }
1220 }
1221 }
1222
1223 delete_edge(edge);
1224 }
1225
select_row(pbqp_edge_t * edge,unsigned row_index)1226 static void select_row(pbqp_edge_t *edge, unsigned row_index)
1227 {
1228 pbqp_matrix_t *mat;
1229 pbqp_node_t *tgt_node;
1230 vector_t *tgt_vec;
1231 unsigned tgt_len;
1232 unsigned tgt_index;
1233 unsigned new_infinity = 0;
1234
1235 tgt_node = edge->tgt;
1236
1237 tgt_vec = tgt_node->costs;
1238
1239 tgt_len = tgt_vec->len;
1240 assert(tgt_len > 0);
1241
1242 mat = edge->costs;
1243
1244 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
1245 num elem = mat->entries[row_index * tgt_len + tgt_index];
1246
1247 if (elem != 0) {
1248 if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
1249 new_infinity = 1;
1250
1251 tgt_vec->entries[tgt_index].data = pbqp_add(
1252 tgt_vec->entries[tgt_index].data, elem);
1253 }
1254 }
1255
1256 if (new_infinity) {
1257 unsigned edge_index;
1258 unsigned edge_len = pbqp_node_get_degree(tgt_node);
1259
1260 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1261 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
1262
1263 if (edge_candidate != edge) {
1264 insert_into_edge_bucket(edge_candidate);
1265 }
1266 }
1267 }
1268
1269 delete_edge(edge);
1270 }
1271
select_alternative(pbqp_node_t * node,unsigned selected_index)1272 void select_alternative(pbqp_node_t *node, unsigned selected_index)
1273 {
1274 unsigned edge_index;
1275 unsigned node_index;
1276 unsigned node_len;
1277 vector_t *node_vec;
1278 unsigned max_degree = pbqp_node_get_degree(node);
1279
1280 node->solution = selected_index;
1281 node_vec = node->costs;
1282 node_len = node_vec->len;
1283 assert(selected_index < node_len);
1284
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;
1289 }
1290 }
1291
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];
1295
1296 if (edge->src == node)
1297 select_row(edge, selected_index);
1298 else
1299 select_column(edge, selected_index);
1300 }
1301 }
1302
get_node_with_max_degree(void)1303 pbqp_node_t *get_node_with_max_degree(void)
1304 {
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;
1310
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);
1314
1315 if (degree > max_degree) {
1316 result = candidate;
1317 max_degree = degree;
1318 }
1319 }
1320
1321 return result;
1322 }
1323
get_local_minimal_alternative(pbqp_t * pbqp,pbqp_node_t * node)1324 unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
1325 {
1326 pbqp_edge_t *edge;
1327 vector_t *node_vec;
1328 vector_t *vec;
1329 pbqp_matrix_t *mat;
1330 unsigned edge_index;
1331 unsigned max_degree;
1332 unsigned node_index;
1333 unsigned node_len;
1334 unsigned min_index = 0;
1335 num min = INF_COSTS;
1336 int is_src;
1337
1338 node_vec = node->costs;
1339 node_len = node_vec->len;
1340 max_degree = pbqp_node_get_degree(node);
1341
1342 for (node_index = 0; node_index < node_len; ++node_index) {
1343 num value = node_vec->entries[node_index].data;
1344
1345 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1346 edge = node->edges[edge_index];
1347 mat = edge->costs;
1348 is_src = edge->src == node;
1349
1350 if (is_src) {
1351 vec = vector_copy(pbqp, edge->tgt->costs);
1352 vector_add_matrix_row(vec, mat, node_index);
1353 } else {
1354 vec = vector_copy(pbqp, edge->src->costs);
1355 vector_add_matrix_col(vec, mat, node_index);
1356 }
1357
1358 value = pbqp_add(value, vector_get_min(vec));
1359
1360 obstack_free(&pbqp->obstack, vec);
1361 }
1362
1363 if (value < min) {
1364 min = value;
1365 min_index = node_index;
1366 }
1367 }
1368
1369 return min_index;
1370 }
1371
node_is_reduced(pbqp_node_t * node)1372 int node_is_reduced(pbqp_node_t *node)
1373 {
1374 if (!reduced_bucket) return 0;
1375
1376 if (pbqp_node_get_degree(node) == 0) return 1;
1377
1378 return node_bucket_contains(reduced_bucket, node);
1379 }
1380