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(void)
  17 {
  18         int i;
  19
  20         edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
  21
  22         for (i = 0; i < 4; ++i) {
  23                 node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
  24         }
  25 }
  26
  27 static void fill_node_buckets(pbqp *pbqp)
  28 {
  29         unsigned node_index;
  30         unsigned node_len;
  31
  32         assert(pbqp);
  33         node_len = pbqp->num_nodes;
  34
  35         for (node_index = 0; node_index < node_len; ++node_index) {
  36                 unsigned   arity;
  37                 pbqp_node *node = get_node(pbqp, node_index);
  38
  39                 if (!node) continue;
  40
  41                 arity = ARR_LEN(node->edges);
  42
  43                 /* We have only one bucket for nodes with arity >= 3. */
  44                 if (arity > 3) {
  45                         arity = 3;
  46                 }
  47
  48                 ARR_APP1(pbqp_node *, node_buckets[arity], node);
  49         }
  50 }
  51
  52 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
  53 {
  54         pbqp_matrix    *mat;
  55         pbqp_node      *src_node;
  56         pbqp_node      *tgt_node;
  57         vector         *src_vec;
  58         vector         *tgt_vec;
  59         int             src_len;
  60         int             tgt_len;
  61         int             src_index;
  62         int             tgt_index;
  63
  64         assert(pbqp);
  65         assert(edge);
  66
  67         if(pbqp->dump_file) {
  68                 char txt[100];
  69                 sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt);
  70                 dump_section(pbqp->dump_file, 3, txt);
  71         }
  72
  73         src_node = get_node(pbqp, edge->src);
  74         tgt_node = get_node(pbqp, edge->tgt);
  75         assert(src_node);
  76         assert(tgt_node);
  77
  78         src_vec = src_node->costs;
  79         tgt_vec = tgt_node->costs;
  80         assert(src_vec);
  81         assert(tgt_vec);
  82
  83         src_len = src_vec->len;
  84         tgt_len = tgt_vec->len;
  85         assert(src_len > 0);
  86         assert(tgt_len > 0);
  87
  88         mat = edge->costs;
  89         assert(mat);
  90
  91         if (pbqp->dump_file) {
  92                 fputs("Input:<br>\n", pbqp->dump_file);
  93                 dump_simplifyedge(pbqp, edge);
  94         }
  95
  96         /* Normalize towards source node. */
  97         for (src_index = 0; src_index < src_len; ++src_index) {
  98                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
  99
 100                 if (min != 0) {
 101                         pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 102                         vector_add_value(src_vec, min);
 103
 104                         // TODO add to edge_list if inf
 105                 }
 106         }
 107
 108         /* Normalize towards target node. */
 109         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 110                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 111
 112                 if (min != 0) {
 113                         pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 114                         vector_add_value(tgt_vec, min);
 115
 116                         // TODO add to edge_list if inf
 117                 }
 118         }
 119
 120         if (pbqp->dump_file) {
 121                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 122                 dump_simplifyedge(pbqp, edge);
 123         }
 124
 125         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 126                 if (pbqp->dump_file) {
 127                         fputs("edge has been eliminated", pbqp->dump_file);
 128
 129                         delete_edge(pbqp, edge);
 130                 }
 131         }
 132 }
 133
 134 void solve_pbqp_heuristical(pbqp *pbqp)
 135 {
 136         unsigned node_index;
 137         unsigned node_len;
 138
 139         assert(pbqp);
 140
 141         if (pbqp->dump_file) {
 142                 pbqp_dump_input(pbqp);
 143                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 144         }
 145
 146         node_len = pbqp->num_nodes;
 147
 148         init_buckets();
 149
 150         /* First simplify all edges. */
 151         for (node_index = 0; node_index < node_len; ++node_index) {
 152                 unsigned    edge_index;
 153                 pbqp_node  *node = get_node(pbqp, node_index);
 154                 pbqp_edge **edges;
 155                 unsigned    edge_len;
 156
 157                 if (!node) continue;
 158
 159                 edges = node->edges;
 160                 edge_len = ARR_LEN(edges);
 161
 162                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 163                         pbqp_edge *edge = edges[edge_index];
 164
 165                         /* Simplify only once per edge. */
 166                         if (node_index != edge->src) continue;
 167
 168                         simplify_edge(pbqp, edge);
 169                 }
 170         }
 171
 172         /* Put node into bucket representing their arity. */
 173         fill_node_buckets(pbqp);
 174 }