nsz Git - libfirm/blob - heuristical.c

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