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