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