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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Interface for interference graphs.
  23  * @author      Sebastian Hack
  24  * @date        18.11.2005
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include <stdlib.h>
  30
  31 #include "lc_opts.h"
  32 #include "lc_opts_enum.h"
  33
  34 #include "timing.h"
  35 #include "bitset.h"
  36 #include "irgwalk.h"
  37 #include "irnode_t.h"
  38 #include "irprintf.h"
  39 #include "irtools.h"
  40 #include "irbitset.h"
  41 #include "beifg_t.h"
  42 #include "beifg_impl.h"
  43 #include "irphase_t.h"
  44 #include "error.h"
  45 #include "xmalloc.h"
  46
  47 #include "becopystat.h"
  48 #include "becopyopt.h"
  49 #include "beirg.h"
  50 #include "bemodule.h"
  51
  52 /** Defines values for the ifg performance test */
  53 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
  54 #define BE_CH_PERFORMANCETEST_COUNT (500)
  55
  56 typedef struct _coloring_t coloring_t;
  57
  58 struct _coloring_t {
  59         ir_phase         ph;
  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(ir_phase *ph, const ir_node *irn, void *data)
  79 {
  80         (void)ph;
  81         (void)data;
  82
  83         return (void*)arch_get_irn_register(irn);
  84 }
  85
  86 static coloring_t *coloring_init(coloring_t *c, ir_graph *irg)
  87 {
  88         phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init, NULL);
  89         c->irg = irg;
  90         return c;
  91 }
  92
  93 static void get_irn_color(ir_node *irn, void *c)
  94 {
  95         coloring_t *coloring = c;
  96         phase_get_or_set_irn_data(&coloring->ph, irn);
  97 }
  98
  99 static void restore_irn_color(ir_node *irn, void *c)
 100 {
 101         coloring_t *coloring = c;
 102         const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
 103         if(reg)
 104                 arch_set_irn_register(irn, reg);
 105 }
 106
 107 static void coloring_save(coloring_t *c)
 108 {
 109         irg_walk_graph(c->irg, NULL, get_irn_color, c);
 110 }
 111
 112 static void coloring_restore(coloring_t *c)
 113 {
 114         irg_walk_graph(c->irg, NULL, restore_irn_color, c);
 115 }
 116
 117 void (be_ifg_free)(be_ifg_t *ifg)
 118 {
 119         ifg->impl->free(ifg);
 120 }
 121
 122 int (be_ifg_connected)(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
 123 {
 124         return ifg->impl->connected(ifg, a, b);
 125 }
 126
 127 ir_node *(be_ifg_neighbours_begin)(const be_ifg_t *ifg, void *iter, const ir_node *irn)
 128 {
 129         return ifg->impl->neighbours_begin(ifg, iter, irn);
 130 }
 131
 132 ir_node *(be_ifg_neighbours_next)(const be_ifg_t *ifg, void *iter)
 133 {
 134         return ifg->impl->neighbours_next(ifg, iter);
 135 }
 136
 137 void (be_ifg_neighbours_break)(const be_ifg_t *ifg, void *iter)
 138 {
 139         ifg->impl->neighbours_break(ifg, iter);
 140 }
 141
 142 ir_node *(be_ifg_nodes_begin)(const be_ifg_t *ifg, void *iter)
 143 {
 144         return ifg->impl->nodes_begin(ifg, iter);
 145 }
 146
 147 ir_node *(be_ifg_nodes_next)(const be_ifg_t *ifg, void *iter)
 148 {
 149         return ifg->impl->nodes_next(ifg, iter);
 150 }
 151
 152 void (be_ifg_nodes_break)(const be_ifg_t *ifg, void *iter)
 153 {
 154         ifg->impl->nodes_break(ifg, iter);
 155 }
 156
 157 int (be_ifg_cliques_begin)(const be_ifg_t *ifg, void *iter, ir_node **buf)
 158 {
 159         return ifg->impl->cliques_begin(ifg, iter, buf);
 160 }
 161
 162 int (be_ifg_cliques_next)(const be_ifg_t *ifg, void *iter)
 163 {
 164         return ifg->impl->cliques_next(ifg, iter);
 165 }
 166
 167 void (be_ifg_cliques_break)(const be_ifg_t *ifg, void *iter)
 168 {
 169         ifg->impl->cliques_break(ifg, iter);
 170 }
 171
 172 int (be_ifg_degree)(const be_ifg_t *ifg, const ir_node *irn)
 173 {
 174         return ifg->impl->degree(ifg, irn);
 175 }
 176
 177
 178 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
 179 {
 180         int degree = be_ifg_degree(ifg, irn);
 181         void *iter = be_ifg_neighbours_iter_alloca(ifg);
 182
 183         ir_node **neighbours = XMALLOCN(ir_node*, degree);
 184
 185         ir_node *curr;
 186         int i, j;
 187
 188         i = 0;
 189         be_ifg_foreach_neighbour(ifg, iter, irn, curr)
 190                 neighbours[i++] = curr;
 191
 192         for(i = 0; i < degree; ++i) {
 193                 for(j = 0; j < i; ++j)
 194                         if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
 195                                 free(neighbours);
 196                                 return 0;
 197                         }
 198         }
 199
 200
 201         free(neighbours);
 202         return 1;
 203 }
 204
 205 void be_ifg_check(const be_ifg_t *ifg)
 206 {
 207         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 208         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 209
 210         ir_node *n, *m;
 211         int node_count = 0;
 212         int neighbours_count = 0;
 213         int degree = 0;
 214
 215         /* count all nodes */
 216         ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
 217         be_ifg_foreach_node(ifg,iter1,n)
 218         {
 219                 node_count++;
 220                 degree = be_ifg_degree(ifg, n);
 221                 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
 222         }
 223
 224         ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
 225
 226         /* Check, if all neighbours are indeed connected to the node. */
 227         be_ifg_foreach_node(ifg, iter1, n)
 228         {
 229                 ir_printf("\n%+F; ", n);
 230                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 231                 {
 232                         ir_printf("%+F; ", m);
 233                         neighbours_count++;
 234                         if(!be_ifg_connected(ifg, n, m))
 235                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 236                 }
 237         }
 238         ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
 239 }
 240
 241 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
 242 {
 243         void *iter = be_ifg_nodes_iter_alloca(ifg);
 244         int node_count = 0;
 245         ir_node *n;
 246
 247         be_ifg_foreach_node(ifg, iter, n)
 248         {
 249                 node_count++;
 250         }
 251
 252         return node_count;
 253 }
 254
 255 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
 256 {
 257         const ir_node *node_a = *(ir_node **)a;
 258         const ir_node *node_b = *(ir_node **)b;
 259
 260         long nr_a = get_irn_idx(node_a);
 261         long nr_b = get_irn_idx(node_b);
 262
 263         return QSORT_CMP(nr_a, nr_b);
 264 }
 265
 266 void be_ifg_check_sorted(const be_ifg_t *ifg)
 267 {
 268         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 269         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 270
 271         ir_node *n, *m;
 272         const int node_count = be_ifg_check_get_node_count(ifg);
 273         int i = 0;
 274
 275         ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
 276
 277         be_ifg_foreach_node(ifg, iter1, n)
 278         {
 279                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 280                 {
 281                         ir_printf("+%F is in ifg but not in the current irg!", n);
 282                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 283                 }
 284
 285                 all_nodes[i] = n;
 286                 i++;
 287         }
 288
 289         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 290
 291         for (i = 0; i < node_count; i++)
 292         {
 293                 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
 294                 int j = 0;
 295                 int k = 0;
 296                 int degree = 0;
 297
 298                 degree = be_ifg_degree(ifg, all_nodes[i]);
 299
 300                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 301                 {
 302                         neighbours[j] = m;
 303                         j++;
 304                 }
 305
 306                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 307
 308                 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 309
 310                 for(k = 0; k < j; k++)
 311                 {
 312                         ir_printf("%+F, ", neighbours[k]);
 313                 }
 314
 315                 ir_printf("\n");
 316
 317                 free(neighbours);
 318         }
 319
 320         free(all_nodes);
 321
 322 }
 323
 324 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
 325 {
 326         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 327         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 328
 329         ir_node *n, *m;
 330         const int node_count = be_ifg_check_get_node_count(ifg);
 331         int i = 0;
 332
 333         ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
 334
 335         be_ifg_foreach_node(ifg, iter1, n)
 336         {
 337                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 338                 {
 339                         ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
 340                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 341                 }
 342
 343                 all_nodes[i] = n;
 344                 i++;
 345         }
 346
 347         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 348
 349         for (i = 0; i < node_count; i++)
 350         {
 351                 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
 352                 int j = 0;
 353                 int k = 0;
 354                 int degree = 0;
 355
 356                 degree = be_ifg_degree(ifg, all_nodes[i]);
 357
 358                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 359                 {
 360                         neighbours[j] = m;
 361                         j++;
 362                 }
 363
 364                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 365
 366                 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 367
 368                 for(k = 0; k < j; k++)
 369                 {
 370                         ir_fprintf (f,"%+F, ", neighbours[k]);
 371                 }
 372
 373                 ir_fprintf (f,"\n");
 374
 375                 free(neighbours);
 376         }
 377
 378         free(all_nodes);
 379
 380 }
 381
 382 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
 383 {
 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         ir_timer_t *timer = ir_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);
 400                 coloring_save(&coloring);
 401
 402                 ir_timer_reset(timer);
 403
 404                 for (i = 0; i<tests; i++) /* performance test with std */
 405                 {
 406
 407                         used_memory = ir_get_heap_used_bytes();
 408
 409                         rt = ir_timer_enter_high_priority();
 410                         ir_timer_start(timer);
 411
 412                         chordal_env->ifg = be_ifg_std_new(chordal_env);
 413
 414                         ir_timer_stop(timer);
 415                         rt = ir_timer_leave_high_priority();
 416
 417                         used_memory = ir_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 = ir_timer_enter_high_priority();
 427                         ir_timer_start(timer);
 428
 429                         co_solve_heuristic_new(co);
 430
 431                         ir_timer_stop(timer);
 432                         rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
 453
 454                         rt = ir_timer_enter_high_priority();
 455                         ir_timer_start(timer);
 456
 457                         chordal_env->ifg = be_ifg_clique_new(chordal_env);
 458
 459                         ir_timer_stop(timer);
 460                         rt = ir_timer_leave_high_priority();
 461
 462                         used_memory = ir_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 = ir_timer_enter_high_priority();
 472                         ir_timer_start(timer);
 473
 474                         co_solve_heuristic_new(co);
 475
 476                         ir_timer_stop(timer);
 477                         rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
 498
 499                         rt = ir_timer_enter_high_priority();
 500                         ir_timer_start(timer);
 501
 502                         chordal_env->ifg = be_ifg_list_new(chordal_env);
 503
 504                         ir_timer_stop(timer);
 505                         rt = ir_timer_leave_high_priority();
 506
 507                         used_memory = ir_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 = ir_timer_enter_high_priority();
 517                         ir_timer_start(timer);
 518
 519                         co_solve_heuristic_new(co);
 520
 521                         ir_timer_stop(timer);
 522                         rt = ir_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 = ir_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 = ir_get_heap_used_bytes();
 543
 544                         rt = ir_timer_enter_high_priority();
 545                         ir_timer_start(timer);
 546
 547                         chordal_env->ifg = be_ifg_pointer_new(chordal_env);
 548
 549                         ir_timer_stop(timer);
 550                         rt = ir_timer_leave_high_priority();
 551
 552                         used_memory = ir_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 = ir_timer_enter_high_priority();
 562                         ir_timer_start(timer);
 563
 564                         co_solve_heuristic_new(co);
 565
 566                         ir_timer_stop(timer);
 567                         rt = ir_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 = ir_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 }
 589
 590 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 591 {
 592         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 593         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 594         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 595
 596         ir_node *n, *m;
 597
 598         fprintf(file, "graph G {\n\tgraph [");
 599         if(cb->graph_attr)
 600                 cb->graph_attr(file, self);
 601         fprintf(file, "];\n");
 602
 603         if(cb->at_begin)
 604                 cb->at_begin(file, self);
 605
 606         be_ifg_foreach_node(ifg, nodes_it, n) {
 607                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 608                         int idx = get_irn_idx(n);
 609                         bitset_set(nodes, idx);
 610                         fprintf(file, "\tnode [");
 611                         if(cb->node_attr)
 612                                 cb->node_attr(file, self, n);
 613                         fprintf(file, "]; n%d;\n", idx);
 614                 }
 615         }
 616
 617         /* Check, if all neighbours are indeed connected to the node. */
 618         be_ifg_foreach_node(ifg, nodes_it, n) {
 619                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 620                         int n_idx = get_irn_idx(n);
 621                         int m_idx = get_irn_idx(m);
 622
 623                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 624                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 625                                 if(cb->edge_attr)
 626                                         cb->edge_attr(file, self, n, m);
 627                                 fprintf(file, "];\n");
 628                         }
 629                 }
 630         }
 631
 632         if(cb->at_end)
 633                 cb->at_end(file, self);
 634
 635         fprintf(file, "}\n");
 636         bitset_free(nodes);
 637 }
 638
 639 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 640 {
 641         void    *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 642         ir_node *m;
 643
 644         be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 645                 if (bitset_contains_irn(seen, m))
 646                         continue;
 647
 648                 if (arch_get_register_req_out(m)->type & arch_register_req_type_ignore)
 649                         continue;
 650
 651                 bitset_add_irn(seen, m);
 652                 int_comp_rec(ifg, m, seen);
 653         }
 654
 655 }
 656
 657 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
 658 {
 659         int      n_comp    = 0;
 660         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 661         bitset_t *seen     = bitset_irg_malloc(birg->irg);
 662
 663         ir_node *n;
 664
 665         be_ifg_foreach_node(ifg, nodes_it, n) {
 666                 if (bitset_contains_irn(seen, n))
 667                         continue;
 668
 669                 if (arch_get_register_req_out(n)->type & arch_register_req_type_ignore)
 670                         continue;
 671
 672                 ++n_comp;
 673                 bitset_add_irn(seen, n);
 674                 int_comp_rec(ifg, n, seen);
 675         }
 676
 677         free(seen);
 678         return n_comp;
 679 }
 680
 681 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 682 {
 683         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 684         void     *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 685         bitset_t *nodes    = bitset_irg_malloc(birg->irg);
 686         ir_node  *n, *m;
 687
 688         memset(stat, 0, sizeof(stat[0]));
 689
 690         be_ifg_foreach_node(ifg, nodes_it, n) {
 691                 stat->n_nodes += 1;
 692                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 693                         bitset_add_irn(nodes, n);
 694                         stat->n_edges += !bitset_contains_irn(nodes, m);
 695                 }
 696         }
 697
 698         stat->n_comps = int_component_stat(birg, ifg);
 699         bitset_free(nodes);
 700 }
 701
 702 enum {
 703         BE_IFG_STD = 1,
 704         BE_IFG_FAST = 2,
 705         BE_IFG_CLIQUE = 3,
 706         BE_IFG_POINTER = 4,
 707         BE_IFG_LIST = 5,
 708         BE_IFG_CHECK = 6
 709 };
 710
 711 static int ifg_flavor = BE_IFG_STD;
 712
 713 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
 714         { "std",     BE_IFG_STD     },
 715         { "fast",    BE_IFG_FAST    },
 716         { "clique",  BE_IFG_CLIQUE  },
 717         { "pointer", BE_IFG_POINTER },
 718         { "list",    BE_IFG_LIST    },
 719         { "check",   BE_IFG_CHECK   },
 720         { NULL,      0              }
 721 };
 722
 723 static lc_opt_enum_int_var_t ifg_flavor_var = {
 724         &ifg_flavor, ifg_flavor_items
 725 };
 726
 727 static const lc_opt_table_entry_t be_ifg_options[] = {
 728         LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
 729         LC_OPT_LAST
 730 };
 731
 732 void be_init_ifg(void)
 733 {
 734         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 735         lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
 736
 737         lc_opt_add_table(ifg_grp, be_ifg_options);
 738 }
 739
 740 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
 741
 742 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
 743 {
 744         FILE *result;
 745         char buf[1024];
 746
 747         ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
 748         result = fopen(buf, "wt");
 749         if(result == NULL) {
 750                 panic("Couldn't open '%s' for writing.", buf);
 751         }
 752
 753         return result;
 754 }
 755
 756 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
 757 {
 758         be_ifg_t *ifg;
 759         FILE *f;
 760
 761         f = be_ifg_open(chordal_env, "std");
 762         ifg = be_ifg_std_new(chordal_env);
 763         be_ifg_check_sorted_to_file(ifg, f);
 764         fclose(f);
 765         be_ifg_free(ifg);
 766
 767         f = be_ifg_open(chordal_env, "list");
 768         ifg = be_ifg_list_new(chordal_env);
 769         be_ifg_check_sorted_to_file(ifg, f);
 770         fclose(f);
 771         be_ifg_free(ifg);
 772
 773         f = be_ifg_open(chordal_env, "clique");
 774         ifg = be_ifg_clique_new(chordal_env);
 775         be_ifg_check_sorted_to_file(ifg, f);
 776         fclose(f);
 777         be_ifg_free(ifg);
 778
 779         f = be_ifg_open(chordal_env, "pointer");
 780         ifg = be_ifg_pointer_new(chordal_env);
 781         be_ifg_check_sorted_to_file(ifg, f);
 782         fclose(f);
 783         be_ifg_free(ifg);
 784 };
 785
 786 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
 787 {
 788         be_ifg_t *ifg = NULL;
 789
 790         switch (ifg_flavor) {
 791                 default:
 792                         assert(0);
 793                         fprintf(stderr, "no valid ifg flavour selected. falling back to std\n");
 794                 case BE_IFG_STD:
 795                 case BE_IFG_FAST:
 796                         ifg = be_ifg_std_new(chordal_env);
 797                         break;
 798                 case BE_IFG_CLIQUE:
 799                         ifg = be_ifg_clique_new(chordal_env);
 800                         break;
 801                 case BE_IFG_POINTER:
 802                         ifg = be_ifg_pointer_new(chordal_env);
 803                         break;
 804                 case BE_IFG_LIST:
 805                         ifg = be_ifg_list_new(chordal_env);
 806                         break;
 807                 case BE_IFG_CHECK:
 808                         check_ifg_implementations(chordal_env);
 809                         /* Build the interference graph. */
 810                         ifg = be_ifg_std_new(chordal_env);
 811                         break;
 812         }
 813
 814         return ifg;
 815 }