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