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