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