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