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