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