nsz Git - libfirm/blob - ir/be/beifg.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Interface for interference graphs.
   9  * @author      Sebastian Hack
  10  * @date        18.11.2005
  11  */
  12 #include "config.h"
  13
  14 #include <stdlib.h>
  15
  16 #include "lc_opts.h"
  17 #include "lc_opts_enum.h"
  18
  19 #include "timing.h"
  20 #include "bitset.h"
  21 #include "irgwalk.h"
  22 #include "irnode_t.h"
  23 #include "irprintf.h"
  24 #include "irtools.h"
  25 #include "beifg.h"
  26 #include "error.h"
  27 #include "xmalloc.h"
  28
  29 #include "becopystat.h"
  30 #include "becopyopt.h"
  31 #include "beirg.h"
  32 #include "bemodule.h"
  33 #include "beintlive_t.h"
  34
  35 void be_ifg_free(be_ifg_t *self)
  36 {
  37         free(self);
  38 }
  39
  40 int be_ifg_connected(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
  41 {
  42         be_lv_t *lv = be_get_irg_liveness(ifg->env->irg);
  43         return be_values_interfere(lv, a, b);
  44 }
  45
  46 static void nodes_walker(ir_node *bl, void *data)
  47 {
  48         nodes_iter_t     *it   = (nodes_iter_t*)data;
  49         struct list_head *head = get_block_border_head(it->env, bl);
  50
  51         foreach_border_head(head, b) {
  52                 if (b->is_def && b->is_real) {
  53                         obstack_ptr_grow(&it->obst, b->irn);
  54                         it->n++;
  55                 }
  56         }
  57 }
  58
  59 static void find_nodes(const be_ifg_t *ifg, nodes_iter_t *iter)
  60 {
  61         obstack_init(&iter->obst);
  62         iter->n     = 0;
  63         iter->curr  = 0;
  64         iter->env   = ifg->env;
  65
  66         irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, iter);
  67         obstack_ptr_grow(&iter->obst, NULL);
  68         iter->nodes = (ir_node**)obstack_finish(&iter->obst);
  69 }
  70
  71 static ir_node *get_next_node(nodes_iter_t *it)
  72 {
  73         if (it->curr < it->n) {
  74                 return it->nodes[it->curr++];
  75         } else {
  76                 obstack_free(&it->obst, NULL);
  77                 return NULL;
  78         }
  79 }
  80
  81 ir_node *be_ifg_nodes_begin(const be_ifg_t *ifg, nodes_iter_t *iter)
  82 {
  83         find_nodes(ifg, iter);
  84         return get_next_node(iter);
  85 }
  86
  87 ir_node *be_ifg_nodes_next(nodes_iter_t *iter)
  88 {
  89         return get_next_node(iter);
  90 }
  91
  92 static void find_neighbour_walker(ir_node *block, void *data)
  93 {
  94         neighbours_iter_t *it    = (neighbours_iter_t*)data;
  95         struct list_head  *head  = get_block_border_head(it->env, block);
  96         be_lv_t           *lv    = be_get_irg_liveness(it->env->irg);
  97
  98         int has_started = 0;
  99
 100         if (!be_is_live_in(lv, block, it->irn) && block != get_nodes_block(it->irn))
 101                 return;
 102
 103         foreach_border_head(head, b) {
 104                 ir_node *irn = b->irn;
 105
 106                 if (irn == it->irn) {
 107                         if (b->is_def)
 108                                 has_started = 1;
 109                         else
 110                                 break; /* if we reached the end of the node's lifetime we can safely break */
 111                 }
 112                 else if (b->is_def) {
 113                         /* if any other node than the one in question starts living, add it to the set */
 114                         ir_nodeset_insert(&it->neighbours, irn);
 115                 }
 116                 else if (!has_started) {
 117                         /* we only delete, if the live range in question has not yet started */
 118                         ir_nodeset_remove(&it->neighbours, irn);
 119                 }
 120
 121         }
 122 }
 123
 124 static void find_neighbours(const be_ifg_t *ifg, neighbours_iter_t *it, const ir_node *irn)
 125 {
 126         it->env         = ifg->env;
 127         it->irn         = irn;
 128         it->valid       = 1;
 129         ir_nodeset_init(&it->neighbours);
 130
 131         dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
 132
 133         ir_nodeset_iterator_init(&it->iter, &it->neighbours);
 134 }
 135
 136 static inline void neighbours_break(neighbours_iter_t *it, int force)
 137 {
 138         (void) force;
 139         assert(it->valid == 1);
 140         ir_nodeset_destroy(&it->neighbours);
 141         it->valid = 0;
 142 }
 143
 144 static ir_node *get_next_neighbour(neighbours_iter_t *it)
 145 {
 146         ir_node *res = ir_nodeset_iterator_next(&it->iter);
 147
 148         if (res == NULL) {
 149                 ir_nodeset_destroy(&it->neighbours);
 150         }
 151         return res;
 152 }
 153
 154 ir_node *be_ifg_neighbours_begin(const be_ifg_t *ifg, neighbours_iter_t *iter,
 155                                  const ir_node *irn)
 156 {
 157         find_neighbours(ifg, iter, irn);
 158         return get_next_neighbour(iter);
 159 }
 160
 161 ir_node *be_ifg_neighbours_next(neighbours_iter_t *iter)
 162 {
 163         return get_next_neighbour(iter);
 164 }
 165
 166 void be_ifg_neighbours_break(neighbours_iter_t *iter)
 167 {
 168         neighbours_break(iter, 1);
 169 }
 170
 171 static inline void free_clique_iter(cliques_iter_t *it)
 172 {
 173         it->n_blocks = -1;
 174         obstack_free(&it->ob, NULL);
 175         del_pset(it->living);
 176 }
 177
 178 static void get_blocks_dom_order(ir_node *blk, void *env)
 179 {
 180         cliques_iter_t *it = (cliques_iter_t*)env;
 181         obstack_ptr_grow(&it->ob, blk);
 182 }
 183
 184 /**
 185  * NOTE: Be careful when changing this function!
 186  *       First understand the control flow of consecutive calls.
 187  */
 188 static inline int get_next_clique(cliques_iter_t *it)
 189 {
 190
 191         /* continue in the block we left the last time */
 192         for (; it->blk < it->n_blocks; it->blk++) {
 193                 int output_on_shrink = 0;
 194                 struct list_head *head = get_block_border_head(it->cenv, it->blocks[it->blk]);
 195
 196                 /* on entry to a new block set the first border ... */
 197                 if (!it->bor)
 198                         it->bor = head->prev;
 199
 200                 /* ... otherwise continue with the border we left the last time */
 201                 for (; it->bor != head; it->bor = it->bor->prev) {
 202                         border_t *b = list_entry(it->bor, border_t, list);
 203
 204                         /* if its a definition irn starts living */
 205                         if (b->is_def) {
 206                                 pset_insert_ptr(it->living, b->irn);
 207                                 if (b->is_real)
 208                                         output_on_shrink = 1;
 209                         } else
 210
 211                         /* if its the last usage the irn dies */
 212                         {
 213                                 /* before shrinking the set, return the current maximal clique */
 214                                 if (output_on_shrink) {
 215                                         int count = 0;
 216
 217                                         /* fill the output buffer */
 218                                         foreach_pset(it->living, ir_node, irn) {
 219                                                 it->buf[count++] = irn;
 220                                         }
 221
 222                                         assert(count > 0 && "We have a 'last usage', so there must be sth. in it->living");
 223
 224                                         return count;
 225                                 }
 226
 227                                 pset_remove_ptr(it->living, b->irn);
 228                         }
 229                 }
 230
 231                 it->bor = NULL;
 232                 assert(0 == pset_count(it->living) && "Something has survived! (At the end of the block it->living must be empty)");
 233         }
 234
 235         if (it->n_blocks != -1)
 236                 free_clique_iter(it);
 237
 238         return -1;
 239 }
 240
 241 int be_ifg_cliques_begin(const be_ifg_t *ifg, cliques_iter_t *it,
 242                          ir_node **buf)
 243 {
 244         obstack_init(&it->ob);
 245         dom_tree_walk_irg(ifg->env->irg, get_blocks_dom_order, NULL, it);
 246
 247         it->cenv     = ifg->env;
 248         it->buf      = buf;
 249         it->n_blocks = obstack_object_size(&it->ob) / sizeof(void *);
 250         it->blocks   = (ir_node**)obstack_finish(&it->ob);
 251         it->blk      = 0;
 252         it->bor      = NULL;
 253         it->living   = pset_new_ptr(2 * arch_register_class_n_regs(it->cenv->cls));
 254
 255         return get_next_clique(it);
 256 }
 257
 258 int be_ifg_cliques_next(cliques_iter_t *iter)
 259 {
 260         return get_next_clique(iter);
 261 }
 262
 263 void be_ifg_cliques_break(cliques_iter_t *iter)
 264 {
 265         free_clique_iter(iter);
 266 }
 267
 268 int be_ifg_degree(const be_ifg_t *ifg, const ir_node *irn)
 269 {
 270         neighbours_iter_t it;
 271         int degree;
 272         find_neighbours(ifg, &it, irn);
 273         degree = ir_nodeset_size(&it.neighbours);
 274         neighbours_break(&it, 1);
 275         return degree;
 276 }
 277
 278 be_ifg_t *be_create_ifg(const be_chordal_env_t *env)
 279 {
 280         be_ifg_t *ifg = XMALLOC(be_ifg_t);
 281         ifg->env = env;
 282
 283         return ifg;
 284 }
 285
 286 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 287 {
 288         neighbours_iter_t neigh_it;
 289
 290         be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 291                 if (bitset_is_set(seen, get_irn_idx(m)))
 292                         continue;
 293
 294                 arch_register_req_t const *const req = arch_get_irn_register_req(m);
 295                 if (arch_register_req_is(req, ignore))
 296                         continue;
 297
 298                 bitset_set(seen, get_irn_idx(m));
 299                 int_comp_rec(ifg, m, seen);
 300         }
 301
 302 }
 303
 304 static int int_component_stat(ir_graph *irg, be_ifg_t *ifg)
 305 {
 306         int      n_comp    = 0;
 307         bitset_t *seen     = bitset_malloc(get_irg_last_idx(irg));
 308
 309         be_ifg_foreach_node(ifg, n) {
 310                 if (bitset_is_set(seen, get_irn_idx(n)))
 311                         continue;
 312
 313                 arch_register_req_t const *const req = arch_get_irn_register_req(n);
 314                 if (arch_register_req_is(req, ignore))
 315                         continue;
 316
 317                 ++n_comp;
 318                 bitset_set(seen, get_irn_idx(n));
 319                 int_comp_rec(ifg, n, seen);
 320         }
 321
 322         free(seen);
 323         return n_comp;
 324 }
 325
 326 void be_ifg_stat(ir_graph *irg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 327 {
 328         neighbours_iter_t neigh_it;
 329
 330         size_t n_nodes = 0;
 331         size_t n_edges = 0;
 332         be_ifg_foreach_node(ifg, n) {
 333                 ++n_nodes;
 334                 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 335                         ++n_edges;
 336                 }
 337         }
 338
 339         stat->n_nodes = n_nodes;
 340         /* Every interference edge was counted twice, once for each end. */
 341         stat->n_edges = n_edges / 2;
 342         stat->n_comps = int_component_stat(irg, ifg);
 343 }