nsz Git - libfirm/blob - ir/kaps/kaps.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Partitioned Boolean Quadratic Problem (PBQP) solver.
   9  * @date    02.10.2008
  10  * @author  Sebastian Buchwald
  11  */
  12 #include "config.h"
  13
  14 #include "adt/array.h"
  15 #include "adt/xmalloc.h"
  16
  17 #include "kaps.h"
  18 #include "matrix.h"
  19 #include "pbqp_edge.h"
  20 #include "pbqp_edge_t.h"
  21 #include "pbqp_node.h"
  22 #include "pbqp_node_t.h"
  23 #include "vector.h"
  24
  25 pbqp_node_t *get_node(pbqp_t *pbqp, unsigned index)
  26 {
  27         return pbqp->nodes[index];
  28 }
  29
  30 pbqp_edge_t *get_edge(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index)
  31 {
  32         size_t i;
  33         size_t len;
  34         pbqp_node_t *src_node;
  35         pbqp_node_t *tgt_node;
  36
  37         if (tgt_index < src_index) {
  38                 unsigned tmp = src_index;
  39                 src_index    = tgt_index;
  40                 tgt_index    = tmp;
  41         }
  42
  43         src_node = get_node(pbqp, src_index);
  44         tgt_node = get_node(pbqp, tgt_index);
  45         assert(tgt_node);
  46
  47         len = ARR_LEN(src_node->edges);
  48
  49         for (i = 0; i < len; ++i) {
  50                 pbqp_edge_t *cur_edge = src_node->edges[i];
  51                 if (cur_edge->tgt == tgt_node) {
  52                         return cur_edge;
  53                 }
  54         }
  55
  56         return NULL;
  57 }
  58
  59 pbqp_t *alloc_pbqp(unsigned number_nodes)
  60 {
  61         pbqp_t *pbqp = XMALLOC(pbqp_t);
  62
  63         obstack_init(&pbqp->obstack);
  64
  65         pbqp->solution = 0;
  66         pbqp->num_nodes = number_nodes;
  67 #if KAPS_DUMP
  68         pbqp->dump_file = NULL;
  69 #endif
  70         pbqp->nodes = OALLOCNZ(&pbqp->obstack, pbqp_node_t*, number_nodes);
  71 #if KAPS_STATISTIC
  72         pbqp->num_bf = 0;
  73         pbqp->num_edges = 0;
  74         pbqp->num_r0 = 0;
  75         pbqp->num_r1 = 0;
  76         pbqp->num_r2 = 0;
  77         pbqp->num_rm = 0;
  78         pbqp->num_rn = 0;
  79 #endif
  80
  81         return pbqp;
  82 }
  83
  84 void free_pbqp(pbqp_t *pbqp)
  85 {
  86         obstack_free(&pbqp->obstack, NULL);
  87         xfree(pbqp);
  88 }
  89
  90 void add_node_costs(pbqp_t *pbqp, unsigned node_index, vector_t *costs)
  91 {
  92         pbqp_node_t *node = get_node(pbqp, node_index);
  93
  94         if (node == NULL) {
  95                 node = alloc_node(pbqp, node_index, costs);
  96                 pbqp->nodes[node_index] = node;
  97         } else {
  98                 vector_add(node->costs, costs);
  99         }
 100 }
 101
 102 void add_edge_costs(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index,
 103                     pbqp_matrix_t *costs)
 104 {
 105         pbqp_edge_t *edge = get_edge(pbqp, src_index, tgt_index);
 106
 107         if (tgt_index < src_index) {
 108                 pbqp_matrix_transpose(pbqp, costs);
 109                 add_edge_costs(pbqp, tgt_index, src_index, costs);
 110                 return;
 111         }
 112
 113         if (edge == NULL) {
 114                 alloc_edge(pbqp, src_index, tgt_index, costs);
 115         } else {
 116                 pbqp_matrix_add(edge->costs, costs);
 117         }
 118 }
 119
 120 num get_node_solution(pbqp_t *pbqp, unsigned node_index)
 121 {
 122         pbqp_node_t *node = get_node(pbqp, node_index);
 123
 124         return node->solution;
 125 }
 126
 127 num get_solution(pbqp_t *pbqp)
 128 {
 129         return pbqp->solution;
 130 }
 131
 132 #if KAPS_DUMP
 133 void set_dumpfile(pbqp *pbqp, FILE *f)
 134 {
 135         pbqp->dump_file = f;
 136 }
 137 #endif