nsz Git - libfirm/blob - heuristical.c

   1 #include "adt/array.h"
   2 #include "assert.h"
   3
   4 #include "heuristical.h"
   5 #include "html_dumper.h"
   6 #include "kaps.h"
   7 #include "matrix.h"
   8 #include "pbqp_edge.h"
   9 #include "pbqp_edge_t.h"
  10 #include "pbqp_node_t.h"
  11 #include "vector.h"
  12
  13 static pbqp_edge **edge_bucket;
  14 static pbqp_node **node_buckets[4];
  15
  16 static void init_buckets(pbqp *pbqp)
  17 {
  18         // TODO
  19 }
  20
  21 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
  22 {
  23         pbqp_matrix    *mat;
  24         pbqp_node      *src_node;
  25         pbqp_node      *tgt_node;
  26         vector         *src_vec;
  27         vector         *tgt_vec;
  28         int             src_len;
  29         int             tgt_len;
  30         int             src_index;
  31         int             tgt_index;
  32
  33         assert(pbqp);
  34         assert(edge);
  35
  36         if(pbqp->dump_file) {
  37                 char txt[100];
  38                 sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt);
  39                 dump_section(pbqp->dump_file, 3, txt);
  40         }
  41
  42         src_node = get_node(pbqp, edge->src);
  43         tgt_node = get_node(pbqp, edge->tgt);
  44         assert(src_node);
  45         assert(tgt_node);
  46
  47         src_vec = src_node->costs;
  48         tgt_vec = tgt_node->costs;
  49         assert(src_vec);
  50         assert(tgt_vec);
  51
  52         src_len = src_vec->len;
  53         tgt_len = tgt_vec->len;
  54         assert(src_len > 0);
  55         assert(tgt_len > 0);
  56
  57         mat = edge->costs;
  58         assert(mat);
  59
  60         if (pbqp->dump_file) {
  61                 fputs("Input:<br>\n", pbqp->dump_file);
  62                 dump_simplifyedge(pbqp, edge);
  63         }
  64
  65         /* Normalize towards source node. */
  66         for (src_index = 0; src_index < src_len; ++src_index) {
  67                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
  68
  69                 if (min != 0) {
  70                         pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
  71                         vector_add_value(src_vec, min);
  72
  73                         // TODO add to edge_list if inf
  74                 }
  75         }
  76
  77         /* Normalize towards target node. */
  78         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
  79                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
  80
  81                 if (min != 0) {
  82                         pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
  83                         vector_add_value(tgt_vec, min);
  84
  85                         // TODO add to edge_list if inf
  86                 }
  87         }
  88
  89         if (pbqp->dump_file) {
  90                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
  91                 dump_simplifyedge(pbqp, edge);
  92         }
  93
  94         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
  95                 if (pbqp->dump_file) {
  96                         fputs("edge has been eliminated", pbqp->dump_file);
  97
  98                         delete_edge(pbqp, edge);
  99                 }
 100         }
 101 }
 102
 103 void solve_pbqp_heuristical(pbqp *pbqp)
 104 {
 105         unsigned node_index;
 106         unsigned node_len;
 107
 108         assert(pbqp);
 109
 110         if (pbqp->dump_file) {
 111                 pbqp_dump_input(pbqp);
 112                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 113         }
 114
 115         node_len = pbqp->num_nodes;
 116
 117         init_buckets(pbqp);
 118
 119         /* First simplify all edges. */
 120         for (node_index = 0; node_index < node_len; ++node_index) {
 121                 unsigned    edge_index;
 122                 pbqp_node  *node = get_node(pbqp, node_index);
 123                 pbqp_edge **edges;
 124                 unsigned    edge_len;
 125
 126                 if (!node) continue;
 127
 128                 edges = node->edges;
 129                 edge_len = ARR_LEN(edges);
 130
 131                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 132                         pbqp_edge *edge = edges[edge_index];
 133
 134                         /* Simplify only once per edge. */
 135                         if (node_index != edge->src) continue;
 136
 137                         simplify_edge(pbqp, edge);
 138                 }
 139         }
 140 }