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

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