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 inline void node_break(nodes_iter_t *it, int force)
  72 {
  73         if ((it->curr >= it->n || force) && it->nodes) {
  74                 obstack_free(&it->obst, NULL);
  75                 it->nodes = NULL;
  76         }
  77 }
  78
  79 static ir_node *get_next_node(nodes_iter_t *it)
  80 {
  81         ir_node *res = NULL;
  82
  83         if (it->curr < it->n)
  84                 res = it->nodes[it->curr++];
  85
  86         node_break(it, 0);
  87
  88         return res;
  89 }
  90
  91 ir_node *be_ifg_nodes_begin(const be_ifg_t *ifg, nodes_iter_t *iter)
  92 {
  93         find_nodes(ifg, iter);
  94         return get_next_node(iter);
  95 }
  96
  97 ir_node *be_ifg_nodes_next(nodes_iter_t *iter)
  98 {
  99         return get_next_node(iter);
 100 }
 101
 102 void be_ifg_nodes_break(nodes_iter_t *iter)
 103 {
 104         node_break(iter, 1);
 105 }
 106
 107 static void find_neighbour_walker(ir_node *block, void *data)
 108 {
 109         neighbours_iter_t *it    = (neighbours_iter_t*)data;
 110         struct list_head  *head  = get_block_border_head(it->env, block);
 111         be_lv_t           *lv    = be_get_irg_liveness(it->env->irg);
 112
 113         int has_started = 0;
 114
 115         if (!be_is_live_in(lv, block, it->irn) && block != get_nodes_block(it->irn))
 116                 return;
 117
 118         foreach_border_head(head, b) {
 119                 ir_node *irn = b->irn;
 120
 121                 if (irn == it->irn) {
 122                         if (b->is_def)
 123                                 has_started = 1;
 124                         else
 125                                 break; /* if we reached the end of the node's lifetime we can safely break */
 126                 }
 127                 else if (b->is_def) {
 128                         /* if any other node than the one in question starts living, add it to the set */
 129                         ir_nodeset_insert(&it->neighbours, irn);
 130                 }
 131                 else if (!has_started) {
 132                         /* we only delete, if the live range in question has not yet started */
 133                         ir_nodeset_remove(&it->neighbours, irn);
 134                 }
 135
 136         }
 137 }
 138
 139 static void find_neighbours(const be_ifg_t *ifg, neighbours_iter_t *it, const ir_node *irn)
 140 {
 141         it->env         = ifg->env;
 142         it->irn         = irn;
 143         it->valid       = 1;
 144         ir_nodeset_init(&it->neighbours);
 145
 146         dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
 147
 148         ir_nodeset_iterator_init(&it->iter, &it->neighbours);
 149 }
 150
 151 static inline void neighbours_break(neighbours_iter_t *it, int force)
 152 {
 153         (void) force;
 154         assert(it->valid == 1);
 155         ir_nodeset_destroy(&it->neighbours);
 156         it->valid = 0;
 157 }
 158
 159 static ir_node *get_next_neighbour(neighbours_iter_t *it)
 160 {
 161         ir_node *res = ir_nodeset_iterator_next(&it->iter);
 162
 163         if (res == NULL) {
 164                 ir_nodeset_destroy(&it->neighbours);
 165         }
 166         return res;
 167 }
 168
 169 ir_node *be_ifg_neighbours_begin(const be_ifg_t *ifg, neighbours_iter_t *iter,
 170                                  const ir_node *irn)
 171 {
 172         find_neighbours(ifg, iter, irn);
 173         return get_next_neighbour(iter);
 174 }
 175
 176 ir_node *be_ifg_neighbours_next(neighbours_iter_t *iter)
 177 {
 178         return get_next_neighbour(iter);
 179 }
 180
 181 void be_ifg_neighbours_break(neighbours_iter_t *iter)
 182 {
 183         neighbours_break(iter, 1);
 184 }
 185
 186 static inline void free_clique_iter(cliques_iter_t *it)
 187 {
 188         it->n_blocks = -1;
 189         obstack_free(&it->ob, NULL);
 190         del_pset(it->living);
 191 }
 192
 193 static void get_blocks_dom_order(ir_node *blk, void *env)
 194 {
 195         cliques_iter_t *it = (cliques_iter_t*)env;
 196         obstack_ptr_grow(&it->ob, blk);
 197 }
 198
 199 /**
 200  * NOTE: Be careful when changing this function!
 201  *       First understand the control flow of consecutive calls.
 202  */
 203 static inline int get_next_clique(cliques_iter_t *it)
 204 {
 205
 206         /* continue in the block we left the last time */
 207         for (; it->blk < it->n_blocks; it->blk++) {
 208                 int output_on_shrink = 0;
 209                 struct list_head *head = get_block_border_head(it->cenv, it->blocks[it->blk]);
 210
 211                 /* on entry to a new block set the first border ... */
 212                 if (!it->bor)
 213                         it->bor = head->prev;
 214
 215                 /* ... otherwise continue with the border we left the last time */
 216                 for (; it->bor != head; it->bor = it->bor->prev) {
 217                         border_t *b = list_entry(it->bor, border_t, list);
 218
 219                         /* if its a definition irn starts living */
 220                         if (b->is_def) {
 221                                 pset_insert_ptr(it->living, b->irn);
 222                                 if (b->is_real)
 223                                         output_on_shrink = 1;
 224                         } else
 225
 226                         /* if its the last usage the irn dies */
 227                         {
 228                                 /* before shrinking the set, return the current maximal clique */
 229                                 if (output_on_shrink) {
 230                                         int count = 0;
 231
 232                                         /* fill the output buffer */
 233                                         foreach_pset(it->living, ir_node, irn) {
 234                                                 it->buf[count++] = irn;
 235                                         }
 236
 237                                         assert(count > 0 && "We have a 'last usage', so there must be sth. in it->living");
 238
 239                                         return count;
 240                                 }
 241
 242                                 pset_remove_ptr(it->living, b->irn);
 243                         }
 244                 }
 245
 246                 it->bor = NULL;
 247                 assert(0 == pset_count(it->living) && "Something has survived! (At the end of the block it->living must be empty)");
 248         }
 249
 250         if (it->n_blocks != -1)
 251                 free_clique_iter(it);
 252
 253         return -1;
 254 }
 255
 256 int be_ifg_cliques_begin(const be_ifg_t *ifg, cliques_iter_t *it,
 257                          ir_node **buf)
 258 {
 259         obstack_init(&it->ob);
 260         dom_tree_walk_irg(ifg->env->irg, get_blocks_dom_order, NULL, it);
 261
 262         it->cenv     = ifg->env;
 263         it->buf      = buf;
 264         it->n_blocks = obstack_object_size(&it->ob) / sizeof(void *);
 265         it->blocks   = (ir_node**)obstack_finish(&it->ob);
 266         it->blk      = 0;
 267         it->bor      = NULL;
 268         it->living   = pset_new_ptr(2 * arch_register_class_n_regs(it->cenv->cls));
 269
 270         return get_next_clique(it);
 271 }
 272
 273 int be_ifg_cliques_next(cliques_iter_t *iter)
 274 {
 275         return get_next_clique(iter);
 276 }
 277
 278 void be_ifg_cliques_break(cliques_iter_t *iter)
 279 {
 280         free_clique_iter(iter);
 281 }
 282
 283 int be_ifg_degree(const be_ifg_t *ifg, const ir_node *irn)
 284 {
 285         neighbours_iter_t it;
 286         int degree;
 287         find_neighbours(ifg, &it, irn);
 288         degree = ir_nodeset_size(&it.neighbours);
 289         neighbours_break(&it, 1);
 290         return degree;
 291 }
 292
 293 be_ifg_t *be_create_ifg(const be_chordal_env_t *env)
 294 {
 295         be_ifg_t *ifg = XMALLOC(be_ifg_t);
 296         ifg->env = env;
 297
 298         return ifg;
 299 }
 300
 301 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 302 {
 303         neighbours_iter_t neigh_it;
 304
 305         be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 306                 if (bitset_is_set(seen, get_irn_idx(m)))
 307                         continue;
 308
 309                 arch_register_req_t const *const req = arch_get_irn_register_req(m);
 310                 if (arch_register_req_is(req, ignore))
 311                         continue;
 312
 313                 bitset_set(seen, get_irn_idx(m));
 314                 int_comp_rec(ifg, m, seen);
 315         }
 316
 317 }
 318
 319 static int int_component_stat(ir_graph *irg, be_ifg_t *ifg)
 320 {
 321         int      n_comp    = 0;
 322         nodes_iter_t nodes_it;
 323         bitset_t *seen     = bitset_malloc(get_irg_last_idx(irg));
 324
 325         be_ifg_foreach_node(ifg, &nodes_it, n) {
 326                 if (bitset_is_set(seen, get_irn_idx(n)))
 327                         continue;
 328
 329                 arch_register_req_t const *const req = arch_get_irn_register_req(n);
 330                 if (arch_register_req_is(req, ignore))
 331                         continue;
 332
 333                 ++n_comp;
 334                 bitset_set(seen, get_irn_idx(n));
 335                 int_comp_rec(ifg, n, seen);
 336         }
 337
 338         free(seen);
 339         return n_comp;
 340 }
 341
 342 void be_ifg_stat(ir_graph *irg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 343 {
 344         nodes_iter_t      nodes_it;
 345         neighbours_iter_t neigh_it;
 346
 347         memset(stat, 0, sizeof(stat[0]));
 348
 349         size_t n_edges = 0;
 350         be_ifg_foreach_node(ifg, &nodes_it, n) {
 351                 stat->n_nodes += 1;
 352                 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 353                         ++n_edges;
 354                 }
 355         }
 356
 357         /* Every interference edge was counted twice, once for each end. */
 358         stat->n_edges = n_edges / 2;
 359         stat->n_comps = int_component_stat(irg, ifg);
 360 }