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

   1 /**
   2  * @file   beifg.c
   3  * @date   18.11.2005
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #include <stdlib.h>
  14
  15 #include <libcore/lc_opts.h>
  16 #include <libcore/lc_opts_enum.h>
  17 #include <libcore/lc_timing.h>
  18
  19 #include "bitset.h"
  20
  21 #include "irgwalk.h"
  22 #include "irnode_t.h"
  23 #include "irprintf.h"
  24 #include "irtools.h"
  25 #include "irbitset.h"
  26 #include "beifg_t.h"
  27 #include "beifg_impl.h"
  28 #include "irphase.h"
  29 #include "irphase_t.h"
  30 #include "bechordal.h"
  31 #include "error.h"
  32 #include "xmalloc.h"
  33
  34 #include "becopystat.h"
  35 #include "becopyopt.h"
  36 #include "beirg_t.h"
  37
  38 /** Defines values for the ifg performance test */
  39 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
  40 #define BE_CH_PERFORMANCETEST_COUNT (500)
  41
  42 typedef struct _coloring_t coloring_t;
  43
  44 struct _coloring_t {
  45         phase_t ph;
  46         const arch_env_t *arch_env;
  47         ir_graph *irg;
  48 };
  49
  50 size_t (be_ifg_nodes_iter_size)(const be_ifg_t *ifg)
  51 {
  52         return ifg->impl->nodes_iter_size;
  53 }
  54
  55 size_t (be_ifg_neighbours_iter_size)(const be_ifg_t *ifg)
  56 {
  57         return ifg->impl->neighbours_iter_size;
  58 }
  59
  60 size_t (be_ifg_cliques_iter_size)(const be_ifg_t *ifg)
  61 {
  62         return ifg->impl->cliques_iter_size;
  63 }
  64
  65 static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
  66 {
  67         coloring_t *coloring = (coloring_t *) ph;
  68         return (void *) arch_get_irn_register(coloring->arch_env, irn);
  69 }
  70
  71 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
  72 {
  73         phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
  74         c->arch_env = aenv;
  75         c->irg = irg;
  76         return c;
  77 }
  78
  79 static void get_irn_color(ir_node *irn, void *c)
  80 {
  81         coloring_t *coloring = c;
  82         phase_get_or_set_irn_data(&coloring->ph, irn);
  83 }
  84
  85 static void restore_irn_color(ir_node *irn, void *c)
  86 {
  87         coloring_t *coloring = c;
  88         const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
  89         if(reg)
  90                 arch_set_irn_register(coloring->arch_env, irn, reg);
  91 }
  92
  93 void coloring_save(coloring_t *c)
  94 {
  95         irg_walk_graph(c->irg, NULL, get_irn_color, c);
  96 }
  97
  98 void coloring_restore(coloring_t *c)
  99 {
 100         irg_walk_graph(c->irg, NULL, restore_irn_color, c);
 101 }
 102
 103 void (be_ifg_free)(be_ifg_t *ifg)
 104 {
 105         ifg->impl->free(ifg);
 106 }
 107
 108 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
 109 {
 110         return ifg->impl->connected(ifg, a, b);
 111 }
 112
 113 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
 114 {
 115         return ifg->impl->neighbours_begin(ifg, iter, irn);
 116 }
 117
 118 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
 119 {
 120         return ifg->impl->neighbours_next(ifg, iter);
 121 }
 122
 123 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
 124 {
 125         ifg->impl->neighbours_break(ifg, iter);
 126 }
 127
 128 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
 129 {
 130         return ifg->impl->nodes_begin(ifg, iter);
 131 }
 132
 133 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
 134 {
 135         return ifg->impl->nodes_next(ifg, iter);
 136 }
 137
 138 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
 139 {
 140         ifg->impl->nodes_break(ifg, iter);
 141 }
 142
 143 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
 144 {
 145         return ifg->impl->cliques_begin(ifg, iter, buf);
 146 }
 147
 148 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
 149 {
 150         return ifg->impl->cliques_next(ifg, iter);
 151 }
 152
 153 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
 154 {
 155         ifg->impl->cliques_break(ifg, iter);
 156 }
 157
 158 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
 159 {
 160         return ifg->impl->degree(ifg, irn);
 161 }
 162
 163
 164 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
 165 {
 166         int degree = be_ifg_degree(ifg, irn);
 167         void *iter = be_ifg_neighbours_iter_alloca(ifg);
 168
 169         ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
 170
 171         ir_node *curr;
 172         int i, j;
 173
 174         i = 0;
 175         be_ifg_foreach_neighbour(ifg, iter, irn, curr)
 176                 neighbours[i++] = curr;
 177
 178         for(i = 0; i < degree; ++i) {
 179                 for(j = 0; j < i; ++j)
 180                         if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
 181                                 free(neighbours);
 182                                 return 0;
 183                         }
 184         }
 185
 186
 187         free(neighbours);
 188         return 1;
 189 }
 190
 191 void be_ifg_check(const be_ifg_t *ifg)
 192 {
 193         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 194         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 195
 196         ir_node *n, *m;
 197         int node_count = 0;
 198         int neighbours_count = 0;
 199         int degree = 0;
 200
 201         /* count all nodes */
 202         ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
 203         be_ifg_foreach_node(ifg,iter1,n)
 204         {
 205                 node_count++;
 206                 degree = be_ifg_degree(ifg, n);
 207                 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
 208         }
 209
 210         ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
 211
 212         /* Check, if all neighbours are indeed connected to the node. */
 213         be_ifg_foreach_node(ifg, iter1, n)
 214         {
 215                 ir_printf("\n%+F; ", n);
 216                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 217                 {
 218                         ir_printf("%+F; ", m);
 219                         neighbours_count++;
 220                         if(!be_ifg_connected(ifg, n, m))
 221                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 222                 }
 223         }
 224         ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
 225 }
 226
 227 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
 228 {
 229         void *iter = be_ifg_nodes_iter_alloca(ifg);
 230         int node_count = 0;
 231         ir_node *n;
 232
 233         be_ifg_foreach_node(ifg, iter, n)
 234         {
 235                 node_count++;
 236         }
 237
 238         return node_count;
 239 }
 240
 241 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
 242 {
 243         const ir_node *node_a = *(ir_node **)a;
 244         const ir_node *node_b = *(ir_node **)b;
 245
 246         long nr_a = get_irn_node_nr(node_a);
 247         long nr_b = get_irn_node_nr(node_b);
 248
 249         return QSORT_CMP(nr_a, nr_b);
 250 }
 251
 252 void be_ifg_check_sorted(const be_ifg_t *ifg)
 253 {
 254         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 255         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 256
 257         ir_node *n, *m;
 258         const int node_count = be_ifg_check_get_node_count(ifg);
 259         int i = 0;
 260
 261         ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
 262
 263         be_ifg_foreach_node(ifg, iter1, n)
 264         {
 265                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 266                 {
 267                         ir_printf("+%F is in ifg but not in the current irg!", n);
 268                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 269                 }
 270
 271                 all_nodes[i] = n;
 272                 i++;
 273         }
 274
 275         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 276
 277         for (i = 0; i < node_count; i++)
 278         {
 279                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 280                 int j = 0;
 281                 int k = 0;
 282                 int degree = 0;
 283
 284                 degree = be_ifg_degree(ifg, all_nodes[i]);
 285
 286                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 287                 {
 288                         neighbours[j] = m;
 289                         j++;
 290                 }
 291
 292                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 293
 294                 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 295
 296                 for(k = 0; k < j; k++)
 297                 {
 298                         ir_printf("%+F, ", neighbours[k]);
 299                 }
 300
 301                 ir_printf("\n");
 302
 303                 free(neighbours);
 304         }
 305
 306         free(all_nodes);
 307
 308 }
 309
 310 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
 311 {
 312         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 313         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 314
 315         ir_node *n, *m;
 316         const int node_count = be_ifg_check_get_node_count(ifg);
 317         int i = 0;
 318
 319         ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
 320
 321         be_ifg_foreach_node(ifg, iter1, n)
 322         {
 323                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 324                 {
 325                         ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
 326                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 327                 }
 328
 329                 all_nodes[i] = n;
 330                 i++;
 331         }
 332
 333         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 334
 335         for (i = 0; i < node_count; i++)
 336         {
 337                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 338                 int j = 0;
 339                 int k = 0;
 340                 int degree = 0;
 341
 342                 degree = be_ifg_degree(ifg, all_nodes[i]);
 343
 344                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 345                 {
 346                         neighbours[j] = m;
 347                         j++;
 348                 }
 349
 350                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 351
 352                 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 353
 354                 for(k = 0; k < j; k++)
 355                 {
 356                         ir_fprintf (f,"%+F, ", neighbours[k]);
 357                 }
 358
 359                 ir_fprintf (f,"\n");
 360
 361                 free(neighbours);
 362         }
 363
 364         free(all_nodes);
 365
 366 }
 367
 368 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
 369 {
 370         int tests = BE_CH_PERFORMANCETEST_COUNT;
 371         coloring_t coloring;
 372
 373         int used_memory;
 374
 375         int i = 0;
 376         int rt;
 377         copy_opt_t *co;
 378         be_ifg_t *old_if = chordal_env->ifg;
 379
 380         lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
 381         unsigned long elapsed_usec = 0;
 382
 383         if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
 384         {
 385                 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
 386                 coloring_save(&coloring);
 387
 388                 lc_timer_reset(timer);
 389
 390                 for (i = 0; i<tests; i++) /* performance test with std */
 391                 {
 392
 393                         used_memory = lc_get_heap_used_bytes();
 394
 395                         rt = lc_timer_enter_high_priority();
 396                         lc_timer_start(timer);
 397
 398                         chordal_env->ifg = be_ifg_std_new(chordal_env);
 399
 400                         lc_timer_stop(timer);
 401                         rt = lc_timer_leave_high_priority();
 402
 403                         used_memory = lc_get_heap_used_bytes() - used_memory;
 404
 405                         coloring_restore(&coloring);
 406
 407                         co = NULL;
 408                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 409                         co_build_ou_structure(co);
 410                         co_build_graph_structure(co);
 411
 412                         rt = lc_timer_enter_high_priority();
 413                         lc_timer_start(timer);
 414
 415                         co_solve_heuristic_new(co);
 416
 417                         lc_timer_stop(timer);
 418                         rt = lc_timer_leave_high_priority();
 419
 420                         co_free_graph_structure(co);
 421                         co_free_ou_structure(co);
 422                         free_copy_opt(co);
 423                         be_ifg_free(chordal_env->ifg);
 424
 425                 }
 426
 427                 elapsed_usec = lc_timer_elapsed_usec(timer);
 428                 /* calculating average */
 429                 elapsed_usec = elapsed_usec / tests;
 430
 431                 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 432
 433                 used_memory=0;
 434                 elapsed_usec=0;
 435
 436                 for (i = 0; i<tests; i++)  /* performance test with clique */
 437                 {
 438                         used_memory = lc_get_heap_used_bytes();
 439
 440                         rt = lc_timer_enter_high_priority();
 441                         lc_timer_start(timer);
 442
 443                         chordal_env->ifg = be_ifg_clique_new(chordal_env);
 444
 445                         lc_timer_stop(timer);
 446                         rt = lc_timer_leave_high_priority();
 447
 448                         used_memory = lc_get_heap_used_bytes() - used_memory;
 449
 450                         coloring_restore(&coloring);
 451
 452                         co = NULL;
 453                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 454                         co_build_ou_structure(co);
 455                         co_build_graph_structure(co);
 456
 457                         rt = lc_timer_enter_high_priority();
 458                         lc_timer_start(timer);
 459
 460                         co_solve_heuristic_new(co);
 461
 462                         lc_timer_stop(timer);
 463                         rt = lc_timer_leave_high_priority();
 464
 465                         co_free_graph_structure(co);
 466                         co_free_ou_structure(co);
 467                         free_copy_opt(co);
 468                         be_ifg_free(chordal_env->ifg);
 469
 470                 }
 471
 472                 elapsed_usec = lc_timer_elapsed_usec(timer);
 473                 /* calculating average */
 474                 elapsed_usec = elapsed_usec / tests;
 475
 476                 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 477
 478                 used_memory=0;
 479                 elapsed_usec=0;
 480
 481                 for (i = 0; i<tests; i++)  /* performance test with list */
 482                 {
 483                         used_memory = lc_get_heap_used_bytes();
 484
 485                         rt = lc_timer_enter_high_priority();
 486                         lc_timer_start(timer);
 487
 488                         chordal_env->ifg = be_ifg_list_new(chordal_env);
 489
 490                         lc_timer_stop(timer);
 491                         rt = lc_timer_leave_high_priority();
 492
 493                         used_memory = lc_get_heap_used_bytes() - used_memory;
 494
 495                         coloring_restore(&coloring);
 496
 497                         co = NULL;
 498                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 499                         co_build_ou_structure(co);
 500                         co_build_graph_structure(co);
 501
 502                         rt = lc_timer_enter_high_priority();
 503                         lc_timer_start(timer);
 504
 505                         co_solve_heuristic_new(co);
 506
 507                         lc_timer_stop(timer);
 508                         rt = lc_timer_leave_high_priority();
 509
 510                         co_free_graph_structure(co);
 511                         co_free_ou_structure(co);
 512                         free_copy_opt(co);
 513                         be_ifg_free(chordal_env->ifg);
 514
 515                 }
 516
 517                 elapsed_usec = lc_timer_elapsed_usec(timer);
 518                 /* calculating average */
 519                 elapsed_usec = elapsed_usec / tests;
 520
 521                 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 522
 523                 used_memory=0;
 524                 elapsed_usec=0;
 525
 526                 for (i = 0; i<tests; i++)  /* performance test with pointer */
 527                 {
 528                         used_memory = lc_get_heap_used_bytes();
 529
 530                         rt = lc_timer_enter_high_priority();
 531                         lc_timer_start(timer);
 532
 533                         chordal_env->ifg = be_ifg_pointer_new(chordal_env);
 534
 535                         lc_timer_stop(timer);
 536                         rt = lc_timer_leave_high_priority();
 537
 538                         used_memory = lc_get_heap_used_bytes() - used_memory;
 539
 540                         coloring_restore(&coloring);
 541
 542                         co = NULL;
 543                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 544                         co_build_ou_structure(co);
 545                         co_build_graph_structure(co);
 546
 547                         rt = lc_timer_enter_high_priority();
 548                         lc_timer_start(timer);
 549
 550                         co_solve_heuristic_new(co);
 551
 552                         lc_timer_stop(timer);
 553                         rt = lc_timer_leave_high_priority();
 554
 555                         co_free_graph_structure(co);
 556                         co_free_ou_structure(co);
 557                         free_copy_opt(co);
 558                         be_ifg_free(chordal_env->ifg);
 559
 560                 }
 561
 562                 elapsed_usec = lc_timer_elapsed_usec(timer);
 563                 /* calculating average */
 564                 elapsed_usec = elapsed_usec / tests;
 565
 566                 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 567
 568                 i=0;
 569                 used_memory=0;
 570                 elapsed_usec=0;
 571         }
 572
 573         chordal_env->ifg = old_if;
 574 }
 575
 576 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 577 {
 578         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 579         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 580         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 581
 582         ir_node *n, *m;
 583
 584         fprintf(file, "graph G {\n\tgraph [");
 585         if(cb->graph_attr)
 586                 cb->graph_attr(file, self);
 587         fprintf(file, "];\n");
 588
 589         if(cb->at_begin)
 590                 cb->at_begin(file, self);
 591
 592         be_ifg_foreach_node(ifg, nodes_it, n) {
 593                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 594                         int idx = get_irn_idx(n);
 595                         bitset_set(nodes, idx);
 596                         fprintf(file, "\tnode [");
 597                         if(cb->node_attr)
 598                                 cb->node_attr(file, self, n);
 599                         fprintf(file, "]; n%d;\n", idx);
 600                 }
 601         }
 602
 603         /* Check, if all neighbours are indeed connected to the node. */
 604         be_ifg_foreach_node(ifg, nodes_it, n) {
 605                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 606                         int n_idx = get_irn_idx(n);
 607                         int m_idx = get_irn_idx(m);
 608
 609                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 610                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 611                                 if(cb->edge_attr)
 612                                         cb->edge_attr(file, self, n, m);
 613                                 fprintf(file, "];\n");
 614                         }
 615                 }
 616         }
 617
 618         if(cb->at_end)
 619                 cb->at_end(file, self);
 620
 621         fprintf(file, "}\n");
 622         bitset_free(nodes);
 623 }
 624
 625 static void int_comp_rec(be_irg_t *birg, be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 626 {
 627         void    *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 628         ir_node *m;
 629
 630         be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 631                 if(!bitset_contains_irn(seen, m) && !arch_irn_is(birg->main_env->arch_env, m, ignore)) {
 632                         bitset_add_irn(seen, m);
 633                         int_comp_rec(birg, ifg, m, seen);
 634                 }
 635         }
 636
 637 }
 638
 639 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
 640 {
 641         int      n_comp    = 0;
 642         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 643         bitset_t *seen     = bitset_irg_malloc(birg->irg);
 644
 645         ir_node *n;
 646
 647         be_ifg_foreach_node(ifg, nodes_it, n) {
 648                 if (! bitset_contains_irn(seen, n) && ! arch_irn_is(birg->main_env->arch_env, n, ignore)) {
 649                         ++n_comp;
 650                         bitset_add_irn(seen, n);
 651                         int_comp_rec(birg, ifg, n, seen);
 652                 }
 653         }
 654
 655         free(seen);
 656         return n_comp;
 657 }
 658
 659 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 660 {
 661         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 662         void     *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 663         bitset_t *nodes    = bitset_irg_malloc(birg->irg);
 664         ir_node  *n, *m;
 665
 666         memset(stat, 0, sizeof(stat[0]));
 667
 668         be_ifg_foreach_node(ifg, nodes_it, n) {
 669                 stat->n_nodes += 1;
 670                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 671                         bitset_add_irn(nodes, n);
 672                         stat->n_edges += !bitset_contains_irn(nodes, m);
 673                 }
 674         }
 675
 676         stat->n_comps = int_component_stat(birg, ifg);
 677         bitset_free(nodes);
 678 }
 679
 680 enum {
 681         BE_IFG_STD = 1,
 682         BE_IFG_FAST = 2,
 683         BE_IFG_CLIQUE = 3,
 684         BE_IFG_POINTER = 4,
 685         BE_IFG_LIST = 5,
 686         BE_IFG_CHECK = 6
 687 };
 688
 689 static int ifg_flavor = BE_IFG_STD;
 690
 691 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
 692         { "std",     BE_IFG_STD     },
 693         { "fast",    BE_IFG_FAST    },
 694         { "clique",  BE_IFG_CLIQUE  },
 695         { "pointer", BE_IFG_POINTER },
 696         { "list",    BE_IFG_LIST    },
 697         { "check",   BE_IFG_CHECK   },
 698         { NULL,      0              }
 699 };
 700
 701 static lc_opt_enum_int_var_t ifg_flavor_var = {
 702         &ifg_flavor, ifg_flavor_items
 703 };
 704
 705 static const lc_opt_table_entry_t be_ifg_options[] = {
 706         LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
 707         { NULL }
 708 };
 709
 710 void be_init_ifg(void)
 711 {
 712         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 713         lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
 714
 715         lc_opt_add_table(ifg_grp, be_ifg_options);
 716 }
 717
 718 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
 719
 720 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
 721 {
 722         FILE *result;
 723         char buf[1024];
 724
 725         ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
 726         result = fopen(buf, "wt");
 727         if(result == NULL) {
 728                 panic("Couldn't open '%s' for writing.", buf);
 729         }
 730
 731         return result;
 732 }
 733
 734 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
 735 {
 736         be_ifg_t *ifg;
 737         FILE *f;
 738
 739         f = be_ifg_open(chordal_env, "std");
 740         ifg = be_ifg_std_new(chordal_env);
 741         be_ifg_check_sorted_to_file(ifg, f);
 742         fclose(f);
 743         be_ifg_free(ifg);
 744
 745         f = be_ifg_open(chordal_env, "list");
 746         ifg = be_ifg_list_new(chordal_env);
 747         be_ifg_check_sorted_to_file(ifg, f);
 748         fclose(f);
 749         be_ifg_free(ifg);
 750
 751         f = be_ifg_open(chordal_env, "clique");
 752         ifg = be_ifg_clique_new(chordal_env);
 753         be_ifg_check_sorted_to_file(ifg, f);
 754         fclose(f);
 755         be_ifg_free(ifg);
 756
 757         f = be_ifg_open(chordal_env, "pointer");
 758         ifg = be_ifg_pointer_new(chordal_env);
 759         be_ifg_check_sorted_to_file(ifg, f);
 760         fclose(f);
 761         be_ifg_free(ifg);
 762 };
 763
 764 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
 765 {
 766         be_ifg_t *ifg = NULL;
 767
 768         switch (ifg_flavor) {
 769                 default:
 770                         assert(0);
 771                         fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
 772                 case BE_IFG_STD:
 773                 case BE_IFG_FAST:
 774                         ifg = be_ifg_std_new(chordal_env);
 775                         break;
 776                 case BE_IFG_CLIQUE:
 777                         ifg = be_ifg_clique_new(chordal_env);
 778                         break;
 779                 case BE_IFG_POINTER:
 780                         ifg = be_ifg_pointer_new(chordal_env);
 781                         break;
 782                 case BE_IFG_LIST:
 783                         ifg = be_ifg_list_new(chordal_env);
 784                         break;
 785                 case BE_IFG_CHECK:
 786                         check_ifg_implementations(chordal_env);
 787                         /* Build the interference graph. */
 788                         ifg = be_ifg_std_new(chordal_env);
 789                         break;
 790         }
 791
 792         return ifg;
 793 }