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