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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Interface for interference graphs.
  23  * @author      Sebastian Hack
  24  * @date        18.11.2005
  25  */
  26 #include "config.h"
  27
  28 #include <stdlib.h>
  29
  30 #include "lc_opts.h"
  31 #include "lc_opts_enum.h"
  32
  33 #include "timing.h"
  34 #include "bitset.h"
  35 #include "irgwalk.h"
  36 #include "irnode_t.h"
  37 #include "irprintf.h"
  38 #include "irtools.h"
  39 #include "beifg.h"
  40 #include "error.h"
  41 #include "xmalloc.h"
  42
  43 #include "becopystat.h"
  44 #include "becopyopt.h"
  45 #include "beirg.h"
  46 #include "bemodule.h"
  47 #include "beintlive_t.h"
  48
  49 void be_ifg_free(be_ifg_t *self)
  50 {
  51         free(self);
  52 }
  53
  54 int be_ifg_connected(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
  55 {
  56         be_lv_t *lv = be_get_irg_liveness(ifg->env->irg);
  57         return be_values_interfere(lv, a, b);
  58 }
  59
  60 static void nodes_walker(ir_node *bl, void *data)
  61 {
  62         nodes_iter_t     *it   = (nodes_iter_t*)data;
  63         struct list_head *head = get_block_border_head(it->env, bl);
  64         border_t         *b;
  65
  66         foreach_border_head(head, b) {
  67                 if (b->is_def && b->is_real) {
  68                         obstack_ptr_grow(&it->obst, b->irn);
  69                         it->n++;
  70                 }
  71         }
  72 }
  73
  74 static void find_nodes(const be_ifg_t *ifg, nodes_iter_t *iter)
  75 {
  76         obstack_init(&iter->obst);
  77         iter->n     = 0;
  78         iter->curr  = 0;
  79         iter->env   = ifg->env;
  80
  81         irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, iter);
  82         obstack_ptr_grow(&iter->obst, NULL);
  83         iter->nodes = (ir_node**)obstack_finish(&iter->obst);
  84 }
  85
  86 static inline void node_break(nodes_iter_t *it, int force)
  87 {
  88         if ((it->curr >= it->n || force) && it->nodes) {
  89                 obstack_free(&it->obst, NULL);
  90                 it->nodes = NULL;
  91         }
  92 }
  93
  94 static ir_node *get_next_node(nodes_iter_t *it)
  95 {
  96         ir_node *res = NULL;
  97
  98         if (it->curr < it->n)
  99                 res = it->nodes[it->curr++];
 100
 101         node_break(it, 0);
 102
 103         return res;
 104 }
 105
 106 ir_node *be_ifg_nodes_begin(const be_ifg_t *ifg, nodes_iter_t *iter)
 107 {
 108         find_nodes(ifg, iter);
 109         return get_next_node(iter);
 110 }
 111
 112 ir_node *be_ifg_nodes_next(nodes_iter_t *iter)
 113 {
 114         return get_next_node(iter);
 115 }
 116
 117 void be_ifg_nodes_break(nodes_iter_t *iter)
 118 {
 119         node_break(iter, 1);
 120 }
 121
 122 static void find_neighbour_walker(ir_node *block, void *data)
 123 {
 124         neighbours_iter_t *it    = (neighbours_iter_t*)data;
 125         struct list_head  *head  = get_block_border_head(it->env, block);
 126         be_lv_t           *lv    = be_get_irg_liveness(it->env->irg);
 127
 128         border_t *b;
 129         int has_started = 0;
 130
 131         if (!be_is_live_in(lv, block, it->irn) && block != get_nodes_block(it->irn))
 132                 return;
 133
 134         foreach_border_head(head, b) {
 135                 ir_node *irn = b->irn;
 136
 137                 if (irn == it->irn) {
 138                         if (b->is_def)
 139                                 has_started = 1;
 140                         else
 141                                 break; /* if we reached the end of the node's lifetime we can safely break */
 142                 }
 143                 else if (b->is_def) {
 144                         /* if any other node than the one in question starts living, add it to the set */
 145                         ir_nodeset_insert(&it->neighbours, irn);
 146                 }
 147                 else if (!has_started) {
 148                         /* we only delete, if the live range in question has not yet started */
 149                         ir_nodeset_remove(&it->neighbours, irn);
 150                 }
 151
 152         }
 153 }
 154
 155 static void find_neighbours(const be_ifg_t *ifg, neighbours_iter_t *it, const ir_node *irn)
 156 {
 157         it->env         = ifg->env;
 158         it->irn         = irn;
 159         it->valid       = 1;
 160         ir_nodeset_init(&it->neighbours);
 161
 162         dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
 163
 164         ir_nodeset_iterator_init(&it->iter, &it->neighbours);
 165 }
 166
 167 static inline void neighbours_break(neighbours_iter_t *it, int force)
 168 {
 169         (void) force;
 170         assert(it->valid == 1);
 171         ir_nodeset_destroy(&it->neighbours);
 172         it->valid = 0;
 173 }
 174
 175 static ir_node *get_next_neighbour(neighbours_iter_t *it)
 176 {
 177         ir_node *res = ir_nodeset_iterator_next(&it->iter);
 178
 179         if (res == NULL) {
 180                 ir_nodeset_destroy(&it->neighbours);
 181         }
 182         return res;
 183 }
 184
 185 ir_node *be_ifg_neighbours_begin(const be_ifg_t *ifg, neighbours_iter_t *iter,
 186                                  const ir_node *irn)
 187 {
 188         find_neighbours(ifg, iter, irn);
 189         return ir_nodeset_iterator_next(&iter->iter);
 190 }
 191
 192 ir_node *be_ifg_neighbours_next(neighbours_iter_t *iter)
 193 {
 194         return get_next_neighbour(iter);
 195 }
 196
 197 void be_ifg_neighbours_break(neighbours_iter_t *iter)
 198 {
 199         neighbours_break(iter, 1);
 200 }
 201
 202 static inline void free_clique_iter(cliques_iter_t *it)
 203 {
 204         it->n_blocks = -1;
 205         obstack_free(&it->ob, NULL);
 206         del_pset(it->living);
 207 }
 208
 209 static void get_blocks_dom_order(ir_node *blk, void *env)
 210 {
 211         cliques_iter_t *it = (cliques_iter_t*)env;
 212         obstack_ptr_grow(&it->ob, blk);
 213 }
 214
 215 /**
 216  * NOTE: Be careful when changing this function!
 217  *       First understand the control flow of consecutive calls.
 218  */
 219 static inline int get_next_clique(cliques_iter_t *it)
 220 {
 221
 222         /* continue in the block we left the last time */
 223         for (; it->blk < it->n_blocks; it->blk++) {
 224                 int output_on_shrink = 0;
 225                 struct list_head *head = get_block_border_head(it->cenv, it->blocks[it->blk]);
 226
 227                 /* on entry to a new block set the first border ... */
 228                 if (!it->bor)
 229                         it->bor = head->prev;
 230
 231                 /* ... otherwise continue with the border we left the last time */
 232                 for (; it->bor != head; it->bor = it->bor->prev) {
 233                         border_t *b = list_entry(it->bor, border_t, list);
 234
 235                         /* if its a definition irn starts living */
 236                         if (b->is_def) {
 237                                 pset_insert_ptr(it->living, b->irn);
 238                                 if (b->is_real)
 239                                         output_on_shrink = 1;
 240                         } else
 241
 242                         /* if its the last usage the irn dies */
 243                         {
 244                                 /* before shrinking the set, return the current maximal clique */
 245                                 if (output_on_shrink) {
 246                                         int count = 0;
 247                                         ir_node *irn;
 248
 249                                         /* fill the output buffer */
 250                                         for (irn = (ir_node*)pset_first(it->living); irn != NULL;
 251                                              irn = (ir_node*)pset_next(it->living)) {
 252                                                 it->buf[count++] = irn;
 253                                         }
 254
 255                                         assert(count > 0 && "We have a 'last usage', so there must be sth. in it->living");
 256
 257                                         return count;
 258                                 }
 259
 260                                 pset_remove_ptr(it->living, b->irn);
 261                         }
 262                 }
 263
 264                 it->bor = NULL;
 265                 assert(0 == pset_count(it->living) && "Something has survived! (At the end of the block it->living must be empty)");
 266         }
 267
 268         if (it->n_blocks != -1)
 269                 free_clique_iter(it);
 270
 271         return -1;
 272 }
 273
 274 int be_ifg_cliques_begin(const be_ifg_t *ifg, cliques_iter_t *it,
 275                          ir_node **buf)
 276 {
 277         ir_node *start_bl = get_irg_start_block(ifg->env->irg);
 278
 279         obstack_init(&it->ob);
 280         dom_tree_walk(start_bl, get_blocks_dom_order, NULL, it);
 281
 282         it->cenv     = ifg->env;
 283         it->buf      = buf;
 284         it->n_blocks = obstack_object_size(&it->ob) / sizeof(void *);
 285         it->blocks   = (ir_node**)obstack_finish(&it->ob);
 286         it->blk      = 0;
 287         it->bor      = NULL;
 288         it->living   = pset_new_ptr(2 * arch_register_class_n_regs(it->cenv->cls));
 289
 290         return get_next_clique(it);
 291 }
 292
 293 int be_ifg_cliques_next(cliques_iter_t *iter)
 294 {
 295         return get_next_clique(iter);
 296 }
 297
 298 void be_ifg_cliques_break(cliques_iter_t *iter)
 299 {
 300         free_clique_iter(iter);
 301 }
 302
 303 int be_ifg_degree(const be_ifg_t *ifg, const ir_node *irn)
 304 {
 305         neighbours_iter_t it;
 306         int degree;
 307         find_neighbours(ifg, &it, irn);
 308         degree = ir_nodeset_size(&it.neighbours);
 309         neighbours_break(&it, 1);
 310         return degree;
 311 }
 312
 313 be_ifg_t *be_create_ifg(const be_chordal_env_t *env)
 314 {
 315         be_ifg_t *ifg = XMALLOC(be_ifg_t);
 316         ifg->env = env;
 317
 318         return ifg;
 319 }
 320
 321 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 322 {
 323         nodes_iter_t nodes_it;
 324         neighbours_iter_t neigh_it;
 325         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 326
 327         ir_node *n, *m;
 328
 329         fprintf(file, "graph G {\n\tgraph [");
 330         if (cb->graph_attr)
 331                 cb->graph_attr(file, self);
 332         fprintf(file, "];\n");
 333
 334         if (cb->at_begin)
 335                 cb->at_begin(file, self);
 336
 337         be_ifg_foreach_node(ifg, &nodes_it, n) {
 338                 if (cb->is_dump_node && cb->is_dump_node(self, n)) {
 339                         int idx = get_irn_idx(n);
 340                         bitset_set(nodes, idx);
 341                         fprintf(file, "\tnode [");
 342                         if (cb->node_attr)
 343                                 cb->node_attr(file, self, n);
 344                         fprintf(file, "]; n%d;\n", idx);
 345                 }
 346         }
 347
 348         /* Check, if all neighbours are indeed connected to the node. */
 349         be_ifg_foreach_node(ifg, &nodes_it, n) {
 350                 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 351                         int n_idx = get_irn_idx(n);
 352                         int m_idx = get_irn_idx(m);
 353
 354                         if (n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 355                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 356                                 if (cb->edge_attr)
 357                                         cb->edge_attr(file, self, n, m);
 358                                 fprintf(file, "];\n");
 359                         }
 360                 }
 361         }
 362
 363         if (cb->at_end)
 364                 cb->at_end(file, self);
 365
 366         fprintf(file, "}\n");
 367         bitset_free(nodes);
 368 }
 369
 370 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 371 {
 372         neighbours_iter_t neigh_it;
 373         ir_node *m;
 374
 375         be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 376                 if (bitset_is_set(seen, get_irn_idx(m)))
 377                         continue;
 378
 379                 if (arch_get_irn_register_req(m)->type & arch_register_req_type_ignore)
 380                         continue;
 381
 382                 bitset_set(seen, get_irn_idx(m));
 383                 int_comp_rec(ifg, m, seen);
 384         }
 385
 386 }
 387
 388 static int int_component_stat(ir_graph *irg, be_ifg_t *ifg)
 389 {
 390         int      n_comp    = 0;
 391         nodes_iter_t nodes_it;
 392         bitset_t *seen     = bitset_malloc(get_irg_last_idx(irg));
 393
 394         ir_node *n;
 395
 396         be_ifg_foreach_node(ifg, &nodes_it, n) {
 397                 if (bitset_is_set(seen, get_irn_idx(n)))
 398                         continue;
 399
 400                 if (arch_get_irn_register_req(n)->type & arch_register_req_type_ignore)
 401                         continue;
 402
 403                 ++n_comp;
 404                 bitset_set(seen, get_irn_idx(n));
 405                 int_comp_rec(ifg, n, seen);
 406         }
 407
 408         free(seen);
 409         return n_comp;
 410 }
 411
 412 void be_ifg_stat(ir_graph *irg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 413 {
 414         nodes_iter_t      nodes_it;
 415         neighbours_iter_t neigh_it;
 416         bitset_t         *nodes    = bitset_malloc(get_irg_last_idx(irg));
 417         ir_node          *n, *m;
 418
 419         memset(stat, 0, sizeof(stat[0]));
 420
 421         be_ifg_foreach_node(ifg, &nodes_it, n) {
 422                 stat->n_nodes += 1;
 423                 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
 424                         bitset_set(nodes, get_irn_idx(n));
 425                         stat->n_edges += !bitset_is_set(nodes, get_irn_idx(m));
 426                 }
 427         }
 428
 429         stat->n_comps = int_component_stat(irg, ifg);
 430         bitset_free(nodes);
 431 }