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