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