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, irg, regs_irn_data_init);
  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 void be_ifg_check(const be_ifg_t *ifg)
 179 {
 180         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 181         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 182
 183         ir_node *n, *m;
 184         int node_count = 0;
 185         int neighbours_count = 0;
 186         int degree = 0;
 187
 188         /* count all nodes */
 189         ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
 190         be_ifg_foreach_node(ifg,iter1,n)
 191         {
 192                 node_count++;
 193                 degree = be_ifg_degree(ifg, n);
 194                 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
 195         }
 196
 197         ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
 198
 199         /* Check, if all neighbours are indeed connected to the node. */
 200         be_ifg_foreach_node(ifg, iter1, n)
 201         {
 202                 ir_printf("\n%+F; ", n);
 203                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 204                 {
 205                         ir_printf("%+F; ", m);
 206                         neighbours_count++;
 207                         if (!be_ifg_connected(ifg, n, m))
 208                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 209                 }
 210         }
 211         ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
 212 }
 213
 214 static int be_ifg_check_get_node_count(const be_ifg_t *ifg)
 215 {
 216         void *iter = be_ifg_nodes_iter_alloca(ifg);
 217         int node_count = 0;
 218         ir_node *n;
 219
 220         be_ifg_foreach_node(ifg, iter, n)
 221         {
 222                 node_count++;
 223         }
 224
 225         return node_count;
 226 }
 227
 228 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
 229 {
 230         const ir_node *node_a = *(ir_node **)a;
 231         const ir_node *node_b = *(ir_node **)b;
 232
 233         long nr_a = get_irn_idx(node_a);
 234         long nr_b = get_irn_idx(node_b);
 235
 236         return QSORT_CMP(nr_a, nr_b);
 237 }
 238
 239 void be_ifg_check_sorted(const be_ifg_t *ifg)
 240 {
 241         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 242         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 243
 244         ir_node *n, *m;
 245         const int node_count = be_ifg_check_get_node_count(ifg);
 246         int i = 0;
 247
 248         ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
 249
 250         be_ifg_foreach_node(ifg, iter1, n)
 251         {
 252                 if (!node_is_in_irgs_storage(ifg->env->irg, n))
 253                 {
 254                         ir_printf("+%F is in ifg but not in the current irg!", n);
 255                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 256                 }
 257
 258                 all_nodes[i] = n;
 259                 i++;
 260         }
 261
 262         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 263
 264         for (i = 0; i < node_count; i++)
 265         {
 266                 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
 267                 int j = 0;
 268                 int k = 0;
 269                 int degree = 0;
 270
 271                 degree = be_ifg_degree(ifg, all_nodes[i]);
 272
 273                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 274                 {
 275                         neighbours[j] = m;
 276                         j++;
 277                 }
 278
 279                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 280
 281                 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 282
 283                 for (k = 0; k < j; k++)
 284                 {
 285                         ir_printf("%+F, ", neighbours[k]);
 286                 }
 287
 288                 ir_printf("\n");
 289
 290                 free(neighbours);
 291         }
 292
 293         free(all_nodes);
 294
 295 }
 296
 297 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
 298 {
 299         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 300         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 301
 302         ir_node *n, *m;
 303         const int node_count = be_ifg_check_get_node_count(ifg);
 304         int i = 0;
 305
 306         ir_node **all_nodes = XMALLOCN(ir_node*, node_count);
 307
 308         be_ifg_foreach_node(ifg, iter1, n)
 309         {
 310                 if (!node_is_in_irgs_storage(ifg->env->irg, n))
 311                 {
 312                         ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
 313                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 314                 }
 315
 316                 all_nodes[i] = n;
 317                 i++;
 318         }
 319
 320         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 321
 322         for (i = 0; i < node_count; i++)
 323         {
 324                 ir_node **neighbours = XMALLOCN(ir_node*, node_count);
 325                 int j = 0;
 326                 int k = 0;
 327                 int degree = 0;
 328
 329                 degree = be_ifg_degree(ifg, all_nodes[i]);
 330
 331                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 332                 {
 333                         neighbours[j] = m;
 334                         j++;
 335                 }
 336
 337                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 338
 339                 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 340
 341                 for (k = 0; k < j; k++)
 342                 {
 343                         ir_fprintf (f,"%+F, ", neighbours[k]);
 344                 }
 345
 346                 ir_fprintf (f,"\n");
 347
 348                 free(neighbours);
 349         }
 350
 351         free(all_nodes);
 352
 353 }
 354
 355 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
 356 {
 357         int tests = BE_CH_PERFORMANCETEST_COUNT;
 358         coloring_t coloring;
 359
 360         int used_memory;
 361
 362         int i = 0;
 363         int rt;
 364         copy_opt_t *co;
 365         be_ifg_t *old_if = chordal_env->ifg;
 366
 367         ir_timer_t *timer = ir_timer_new();
 368         unsigned long elapsed_usec = 0;
 369
 370         if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
 371         {
 372                 coloring_init(&coloring, chordal_env->irg);
 373                 coloring_save(&coloring);
 374
 375                 ir_timer_reset(timer);
 376
 377                 for (i = 0; i<tests; i++) /* performance test with std */
 378                 {
 379
 380                         used_memory = ir_get_heap_used_bytes();
 381
 382                         rt = ir_timer_enter_high_priority();
 383                         ir_timer_start(timer);
 384
 385                         chordal_env->ifg = be_ifg_std_new(chordal_env);
 386
 387                         ir_timer_stop(timer);
 388                         rt = ir_timer_leave_high_priority();
 389
 390                         used_memory = ir_get_heap_used_bytes() - used_memory;
 391
 392                         coloring_restore(&coloring);
 393
 394                         co = NULL;
 395                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 396                         co_build_ou_structure(co);
 397                         co_build_graph_structure(co);
 398
 399                         rt = ir_timer_enter_high_priority();
 400                         ir_timer_start(timer);
 401
 402                         co_solve_heuristic_new(co);
 403
 404                         ir_timer_stop(timer);
 405                         rt = ir_timer_leave_high_priority();
 406
 407                         co_free_graph_structure(co);
 408                         co_free_ou_structure(co);
 409                         free_copy_opt(co);
 410                         be_ifg_free(chordal_env->ifg);
 411
 412                 }
 413
 414                 elapsed_usec = ir_timer_elapsed_usec(timer);
 415                 /* calculating average */
 416                 elapsed_usec = elapsed_usec / tests;
 417
 418                 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 419
 420                 used_memory=0;
 421                 elapsed_usec=0;
 422
 423                 for (i = 0; i<tests; i++)  /* performance test with clique */
 424                 {
 425                         used_memory = ir_get_heap_used_bytes();
 426
 427                         rt = ir_timer_enter_high_priority();
 428                         ir_timer_start(timer);
 429
 430                         chordal_env->ifg = be_ifg_clique_new(chordal_env);
 431
 432                         ir_timer_stop(timer);
 433                         rt = ir_timer_leave_high_priority();
 434
 435                         used_memory = ir_get_heap_used_bytes() - used_memory;
 436
 437                         coloring_restore(&coloring);
 438
 439                         co = NULL;
 440                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 441                         co_build_ou_structure(co);
 442                         co_build_graph_structure(co);
 443
 444                         rt = ir_timer_enter_high_priority();
 445                         ir_timer_start(timer);
 446
 447                         co_solve_heuristic_new(co);
 448
 449                         ir_timer_stop(timer);
 450                         rt = ir_timer_leave_high_priority();
 451
 452                         co_free_graph_structure(co);
 453                         co_free_ou_structure(co);
 454                         free_copy_opt(co);
 455                         be_ifg_free(chordal_env->ifg);
 456
 457                 }
 458
 459                 elapsed_usec = ir_timer_elapsed_usec(timer);
 460                 /* calculating average */
 461                 elapsed_usec = elapsed_usec / tests;
 462
 463                 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 464
 465                 used_memory=0;
 466                 elapsed_usec=0;
 467
 468                 for (i = 0; i<tests; i++)  /* performance test with list */
 469                 {
 470                         used_memory = ir_get_heap_used_bytes();
 471
 472                         rt = ir_timer_enter_high_priority();
 473                         ir_timer_start(timer);
 474
 475                         chordal_env->ifg = be_ifg_list_new(chordal_env);
 476
 477                         ir_timer_stop(timer);
 478                         rt = ir_timer_leave_high_priority();
 479
 480                         used_memory = ir_get_heap_used_bytes() - used_memory;
 481
 482                         coloring_restore(&coloring);
 483
 484                         co = NULL;
 485                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 486                         co_build_ou_structure(co);
 487                         co_build_graph_structure(co);
 488
 489                         rt = ir_timer_enter_high_priority();
 490                         ir_timer_start(timer);
 491
 492                         co_solve_heuristic_new(co);
 493
 494                         ir_timer_stop(timer);
 495                         rt = ir_timer_leave_high_priority();
 496
 497                         co_free_graph_structure(co);
 498                         co_free_ou_structure(co);
 499                         free_copy_opt(co);
 500                         be_ifg_free(chordal_env->ifg);
 501
 502                 }
 503
 504                 elapsed_usec = ir_timer_elapsed_usec(timer);
 505                 /* calculating average */
 506                 elapsed_usec = elapsed_usec / tests;
 507
 508                 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 509
 510                 used_memory=0;
 511                 elapsed_usec=0;
 512
 513                 for (i = 0; i<tests; i++)  /* performance test with pointer */
 514                 {
 515                         used_memory = ir_get_heap_used_bytes();
 516
 517                         rt = ir_timer_enter_high_priority();
 518                         ir_timer_start(timer);
 519
 520                         chordal_env->ifg = be_ifg_pointer_new(chordal_env);
 521
 522                         ir_timer_stop(timer);
 523                         rt = ir_timer_leave_high_priority();
 524
 525                         used_memory = ir_get_heap_used_bytes() - used_memory;
 526
 527                         coloring_restore(&coloring);
 528
 529                         co = NULL;
 530                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 531                         co_build_ou_structure(co);
 532                         co_build_graph_structure(co);
 533
 534                         rt = ir_timer_enter_high_priority();
 535                         ir_timer_start(timer);
 536
 537                         co_solve_heuristic_new(co);
 538
 539                         ir_timer_stop(timer);
 540                         rt = ir_timer_leave_high_priority();
 541
 542                         co_free_graph_structure(co);
 543                         co_free_ou_structure(co);
 544                         free_copy_opt(co);
 545                         be_ifg_free(chordal_env->ifg);
 546
 547                 }
 548
 549                 elapsed_usec = ir_timer_elapsed_usec(timer);
 550                 /* calculating average */
 551                 elapsed_usec = elapsed_usec / tests;
 552
 553                 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 554
 555                 i=0;
 556                 used_memory=0;
 557                 elapsed_usec=0;
 558         }
 559
 560         chordal_env->ifg = old_if;
 561
 562         ir_timer_free(timer);
 563 }
 564
 565 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 566 {
 567         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 568         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 569         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 570
 571         ir_node *n, *m;
 572
 573         fprintf(file, "graph G {\n\tgraph [");
 574         if (cb->graph_attr)
 575                 cb->graph_attr(file, self);
 576         fprintf(file, "];\n");
 577
 578         if (cb->at_begin)
 579                 cb->at_begin(file, self);
 580
 581         be_ifg_foreach_node(ifg, nodes_it, n) {
 582                 if (cb->is_dump_node && cb->is_dump_node(self, n)) {
 583                         int idx = get_irn_idx(n);
 584                         bitset_set(nodes, idx);
 585                         fprintf(file, "\tnode [");
 586                         if (cb->node_attr)
 587                                 cb->node_attr(file, self, n);
 588                         fprintf(file, "]; n%d;\n", idx);
 589                 }
 590         }
 591
 592         /* Check, if all neighbours are indeed connected to the node. */
 593         be_ifg_foreach_node(ifg, nodes_it, n) {
 594                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 595                         int n_idx = get_irn_idx(n);
 596                         int m_idx = get_irn_idx(m);
 597
 598                         if (n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 599                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 600                                 if (cb->edge_attr)
 601                                         cb->edge_attr(file, self, n, m);
 602                                 fprintf(file, "];\n");
 603                         }
 604                 }
 605         }
 606
 607         if (cb->at_end)
 608                 cb->at_end(file, self);
 609
 610         fprintf(file, "}\n");
 611         bitset_free(nodes);
 612 }
 613
 614 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
 615 {
 616         void    *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 617         ir_node *m;
 618
 619         be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 620                 if (bitset_contains_irn(seen, m))
 621                         continue;
 622
 623                 if (arch_get_register_req_out(m)->type & arch_register_req_type_ignore)
 624                         continue;
 625
 626                 bitset_add_irn(seen, m);
 627                 int_comp_rec(ifg, m, seen);
 628         }
 629
 630 }
 631
 632 static int int_component_stat(be_irg_t *birg, be_ifg_t *ifg)
 633 {
 634         int      n_comp    = 0;
 635         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 636         bitset_t *seen     = bitset_irg_malloc(birg->irg);
 637
 638         ir_node *n;
 639
 640         be_ifg_foreach_node(ifg, nodes_it, n) {
 641                 if (bitset_contains_irn(seen, n))
 642                         continue;
 643
 644                 if (arch_get_register_req_out(n)->type & arch_register_req_type_ignore)
 645                         continue;
 646
 647                 ++n_comp;
 648                 bitset_add_irn(seen, n);
 649                 int_comp_rec(ifg, n, seen);
 650         }
 651
 652         free(seen);
 653         return n_comp;
 654 }
 655
 656 void be_ifg_stat(be_irg_t *birg, be_ifg_t *ifg, be_ifg_stat_t *stat)
 657 {
 658         void     *nodes_it = be_ifg_nodes_iter_alloca(ifg);
 659         void     *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
 660         bitset_t *nodes    = bitset_irg_malloc(birg->irg);
 661         ir_node  *n, *m;
 662
 663         memset(stat, 0, sizeof(stat[0]));
 664
 665         be_ifg_foreach_node(ifg, nodes_it, n) {
 666                 stat->n_nodes += 1;
 667                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 668                         bitset_add_irn(nodes, n);
 669                         stat->n_edges += !bitset_contains_irn(nodes, m);
 670                 }
 671         }
 672
 673         stat->n_comps = int_component_stat(birg, ifg);
 674         bitset_free(nodes);
 675 }
 676
 677 enum {
 678         BE_IFG_STD = 1,
 679         BE_IFG_FAST = 2,
 680         BE_IFG_CLIQUE = 3,
 681         BE_IFG_POINTER = 4,
 682         BE_IFG_LIST = 5,
 683         BE_IFG_CHECK = 6
 684 };
 685
 686 static int ifg_flavor = BE_IFG_STD;
 687
 688 static const lc_opt_enum_int_items_t ifg_flavor_items[] = {
 689         { "std",     BE_IFG_STD     },
 690         { "fast",    BE_IFG_FAST    },
 691         { "clique",  BE_IFG_CLIQUE  },
 692         { "pointer", BE_IFG_POINTER },
 693         { "list",    BE_IFG_LIST    },
 694         { "check",   BE_IFG_CHECK   },
 695         { NULL,      0              }
 696 };
 697
 698 static lc_opt_enum_int_var_t ifg_flavor_var = {
 699         &ifg_flavor, ifg_flavor_items
 700 };
 701
 702 static const lc_opt_table_entry_t be_ifg_options[] = {
 703         LC_OPT_ENT_ENUM_PTR ("ifg", "interference graph flavour", &ifg_flavor_var),
 704         LC_OPT_LAST
 705 };
 706
 707 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ifg);
 708 void be_init_ifg(void)
 709 {
 710         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 711         lc_opt_entry_t *ifg_grp = lc_opt_get_grp(be_grp, "ifg");
 712
 713         lc_opt_add_table(ifg_grp, be_ifg_options);
 714 }
 715
 716
 717 static FILE *be_ifg_open(const be_chordal_env_t *env, const char *prefix)
 718 {
 719         FILE *result;
 720         char buf[1024];
 721
 722         ir_snprintf(buf, sizeof(buf), "%s%F_%s.log", prefix, env->irg, env->cls->name);
 723         result = fopen(buf, "wt");
 724         if (result == NULL) {
 725                 panic("Couldn't open '%s' for writing.", buf);
 726         }
 727
 728         return result;
 729 }
 730
 731 static void check_ifg_implementations(const be_chordal_env_t *chordal_env)
 732 {
 733         be_ifg_t *ifg;
 734         FILE *f;
 735
 736         f = be_ifg_open(chordal_env, "std");
 737         ifg = be_ifg_std_new(chordal_env);
 738         be_ifg_check_sorted_to_file(ifg, f);
 739         fclose(f);
 740         be_ifg_free(ifg);
 741
 742         f = be_ifg_open(chordal_env, "list");
 743         ifg = be_ifg_list_new(chordal_env);
 744         be_ifg_check_sorted_to_file(ifg, f);
 745         fclose(f);
 746         be_ifg_free(ifg);
 747
 748         f = be_ifg_open(chordal_env, "clique");
 749         ifg = be_ifg_clique_new(chordal_env);
 750         be_ifg_check_sorted_to_file(ifg, f);
 751         fclose(f);
 752         be_ifg_free(ifg);
 753
 754         f = be_ifg_open(chordal_env, "pointer");
 755         ifg = be_ifg_pointer_new(chordal_env);
 756         be_ifg_check_sorted_to_file(ifg, f);
 757         fclose(f);
 758         be_ifg_free(ifg);
 759 };
 760
 761 be_ifg_t *be_create_ifg(const be_chordal_env_t *chordal_env)
 762 {
 763         be_ifg_t *ifg = NULL;
 764
 765         switch (ifg_flavor) {
 766                 default:
 767                         panic("invalid ifg flavour selected");
 768                 case BE_IFG_STD:
 769                 case BE_IFG_FAST:
 770                         ifg = be_ifg_std_new(chordal_env);
 771                         break;
 772                 case BE_IFG_CLIQUE:
 773                         ifg = be_ifg_clique_new(chordal_env);
 774                         break;
 775                 case BE_IFG_POINTER:
 776                         ifg = be_ifg_pointer_new(chordal_env);
 777                         break;
 778                 case BE_IFG_LIST:
 779                         ifg = be_ifg_list_new(chordal_env);
 780                         break;
 781                 case BE_IFG_CHECK:
 782                         check_ifg_implementations(chordal_env);
 783                         /* Build the interference graph. */
 784                         ifg = be_ifg_std_new(chordal_env);
 785                         break;
 786         }
 787
 788         return ifg;
 789 }