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

   1 /**
   2  * @file   beifg.c
   3  * @date   18.11.2005
   4  * @author Sebastian Hack
   5  *
   6  * Copyright (C) 2005 Universitaet Karlsruhe
   7  * Released under the GPL
   8  */
   9
  10 #include <stdlib.h>
  11
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #ifdef HAVE_MALLOC_H
  17 #include <malloc.h>
  18 #endif
  19
  20 #ifdef __linux__
  21 #include <malloc.h>
  22 #endif /* __linux__ */
  23
  24 #ifdef HAVE_ALLOCA_H
  25 #include <alloca.h>
  26 #endif
  27
  28 #ifdef WITH_LIBCORE
  29 #include <libcore/lc_opts.h>
  30 #include <libcore/lc_opts_enum.h>
  31 #include <libcore/lc_timing.h>
  32 #endif /* WITH_LIBCORE */
  33
  34 #include "bitset.h"
  35
  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.h"
  44 #include "irphase_t.h"
  45 #include "bechordal.h"
  46
  47 #include "becopystat.h"
  48 #include "becopyopt.h"
  49
  50 /** Defines values for the ifg performance test */
  51 #define BE_CH_PERFORMANCETEST_MIN_NODES (50)
  52 #define BE_CH_PERFORMANCETEST_COUNT (500)
  53
  54 typedef struct _coloring_t coloring_t;
  55
  56 struct _coloring_t {
  57         phase_t ph;
  58         const arch_env_t *arch_env;
  59         ir_graph *irg;
  60 };
  61
  62 size_t (be_ifg_nodes_iter_size)(const void *self)
  63 {
  64         const be_ifg_t *ifg = self;
  65         return ifg->impl->nodes_iter_size;
  66 }
  67
  68 size_t (be_ifg_neighbours_iter_size)(const void *self)
  69 {
  70         const be_ifg_t *ifg = self;
  71         return ifg->impl->neighbours_iter_size;
  72 }
  73
  74 size_t (be_ifg_cliques_iter_size)(const void *self)
  75 {
  76         const be_ifg_t *ifg = self;
  77         return ifg->impl->cliques_iter_size;
  78 }
  79
  80 static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
  81 {
  82         coloring_t *coloring = (coloring_t *) ph;
  83         return (void *) arch_get_irn_register(coloring->arch_env, irn);
  84 }
  85
  86 coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
  87 {
  88         phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
  89         c->arch_env = aenv;
  90         c->irg = irg;
  91         return c;
  92 }
  93
  94 static void get_irn_color(ir_node *irn, void *c)
  95 {
  96         coloring_t *coloring = c;
  97         phase_get_or_set_irn_data(&coloring->ph, irn);
  98 }
  99
 100 static void restore_irn_color(ir_node *irn, void *c)
 101 {
 102         coloring_t *coloring = c;
 103         const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
 104         if(reg)
 105                 arch_set_irn_register(coloring->arch_env, irn, reg);
 106 }
 107
 108 void coloring_save(coloring_t *c)
 109 {
 110         irg_walk_graph(c->irg, NULL, get_irn_color, c);
 111 }
 112
 113 void coloring_restore(coloring_t *c)
 114 {
 115         irg_walk_graph(c->irg, NULL, restore_irn_color, c);
 116 }
 117
 118 void (be_ifg_free)(void *self)
 119 {
 120         be_ifg_t *ifg = self;
 121         ifg->impl->free(self);
 122 }
 123
 124 int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b)
 125 {
 126         const be_ifg_t *ifg = self;
 127         return ifg->impl->connected(self, a, b);
 128 }
 129
 130 ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn)
 131 {
 132         const be_ifg_t *ifg = self;
 133         return ifg->impl->neighbours_begin(self, iter, irn);
 134 }
 135
 136 ir_node *(be_ifg_neighbours_next)(const void *self, void *iter)
 137 {
 138         const be_ifg_t *ifg = self;
 139         return ifg->impl->neighbours_next(self, iter);
 140 }
 141
 142 void (be_ifg_neighbours_break)(const void *self, void *iter)
 143 {
 144         const be_ifg_t *ifg = self;
 145         ifg->impl->neighbours_break(self, iter);
 146 }
 147
 148 ir_node *(be_ifg_nodes_begin)(const void *self, void *iter)
 149 {
 150         const be_ifg_t *ifg = self;
 151         return ifg->impl->nodes_begin(self, iter);
 152 }
 153
 154 ir_node *(be_ifg_nodes_next)(const void *self, void *iter)
 155 {
 156         const be_ifg_t *ifg = self;
 157         return ifg->impl->nodes_next(self, iter);
 158 }
 159
 160 void (be_ifg_nodes_break)(const void *self, void *iter)
 161 {
 162         const be_ifg_t *ifg = self;
 163         ifg->impl->nodes_break(self, iter);
 164 }
 165
 166 int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf)
 167 {
 168         const be_ifg_t *ifg = self;
 169         return ifg->impl->cliques_begin(self, iter, buf);
 170 }
 171
 172 int (be_ifg_cliques_next)(const void *self, void *iter)
 173 {
 174         const be_ifg_t *ifg = self;
 175         return ifg->impl->cliques_next(self, iter);
 176 }
 177
 178 void (be_ifg_cliques_break)(const void *self, void *iter)
 179 {
 180         const be_ifg_t *ifg = self;
 181         ifg->impl->cliques_break(self, iter);
 182 }
 183
 184 int (be_ifg_degree)(const void *self, const ir_node *irn)
 185 {
 186         const be_ifg_t *ifg = self;
 187         return ifg->impl->degree(self, irn);
 188 }
 189
 190
 191 int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
 192 {
 193         int degree = be_ifg_degree(ifg, irn);
 194         void *iter = be_ifg_neighbours_iter_alloca(ifg);
 195
 196         ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
 197
 198         ir_node *curr;
 199         int i, j;
 200
 201         i = 0;
 202         be_ifg_foreach_neighbour(ifg, iter, irn, curr)
 203                 neighbours[i++] = curr;
 204
 205         for(i = 0; i < degree; ++i) {
 206                 for(j = 0; j < i; ++j)
 207                         if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
 208                                 free(neighbours);
 209                                 return 0;
 210                         }
 211         }
 212
 213
 214         free(neighbours);
 215         return 1;
 216 }
 217
 218 void be_ifg_check(const be_ifg_t *ifg)
 219 {
 220         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 221         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 222
 223         ir_node *n, *m;
 224         int node_count = 0;
 225         int neighbours_count = 0;
 226         int degree = 0;
 227
 228         /* count all nodes */
 229         ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
 230         be_ifg_foreach_node(ifg,iter1,n)
 231         {
 232                 node_count++;
 233                 degree = be_ifg_degree(ifg, n);
 234                 ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
 235         }
 236
 237         ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
 238
 239         /* Check, if all neighbours are indeed connected to the node. */
 240         be_ifg_foreach_node(ifg, iter1, n)
 241         {
 242                 ir_printf("\n%+F; ", n);
 243                 be_ifg_foreach_neighbour(ifg, iter2, n, m)
 244                 {
 245                         ir_printf("%+F; ", m);
 246                         neighbours_count++;
 247                         if(!be_ifg_connected(ifg, n, m))
 248                                 ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
 249                 }
 250         }
 251         ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
 252 }
 253
 254 int be_ifg_check_get_node_count(const be_ifg_t *ifg)
 255 {
 256         void *iter = be_ifg_nodes_iter_alloca(ifg);
 257         int node_count = 0;
 258         ir_node *n;
 259
 260         be_ifg_foreach_node(ifg, iter, n)
 261         {
 262                 node_count++;
 263         }
 264
 265         return node_count;
 266 }
 267
 268 static int be_ifg_check_cmp_nodes(const void *a, const void *b)
 269 {
 270         const ir_node *node_a = *(ir_node **)a;
 271         const ir_node *node_b = *(ir_node **)b;
 272
 273         int nr_a = node_a->node_nr;
 274         int nr_b = node_b->node_nr;
 275
 276         return QSORT_CMP(nr_a, nr_b);
 277 }
 278
 279 void be_ifg_check_sorted(const be_ifg_t *ifg)
 280 {
 281         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 282         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 283
 284         ir_node *n, *m;
 285         const int node_count = be_ifg_check_get_node_count(ifg);
 286         int i = 0;
 287
 288         ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
 289
 290         be_ifg_foreach_node(ifg, iter1, n)
 291         {
 292                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 293                 {
 294                         ir_printf("+%F is in ifg but not in the current irg!", n);
 295                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 296                 }
 297
 298                 all_nodes[i] = n;
 299                 i++;
 300         }
 301
 302         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 303
 304         for (i = 0; i < node_count; i++)
 305         {
 306                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 307                 int j = 0;
 308                 int k = 0;
 309                 int degree = 0;
 310
 311                 degree = be_ifg_degree(ifg, all_nodes[i]);
 312
 313                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 314                 {
 315                         neighbours[j] = m;
 316                         j++;
 317                 }
 318
 319                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 320
 321                 ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 322
 323                 for(k = 0; k < j; k++)
 324                 {
 325                         ir_printf("%+F, ", neighbours[k]);
 326                 }
 327
 328                 ir_printf("\n");
 329
 330                 free(neighbours);
 331         }
 332
 333         free(all_nodes);
 334
 335 }
 336
 337 void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
 338 {
 339         void *iter1 = be_ifg_nodes_iter_alloca(ifg);
 340         void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
 341
 342         ir_node *n, *m;
 343         const int node_count = be_ifg_check_get_node_count(ifg);
 344         int i = 0;
 345
 346         ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));
 347
 348         be_ifg_foreach_node(ifg, iter1, n)
 349         {
 350                 if(!node_is_in_irgs_storage(ifg->env->irg, n))
 351                 {
 352                         ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
 353                         assert (node_is_in_irgs_storage(ifg->env->irg, n));
 354                 }
 355
 356                 all_nodes[i] = n;
 357                 i++;
 358         }
 359
 360         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 361
 362         for (i = 0; i < node_count; i++)
 363         {
 364                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 365                 int j = 0;
 366                 int k = 0;
 367                 int degree = 0;
 368
 369                 degree = be_ifg_degree(ifg, all_nodes[i]);
 370
 371                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 372                 {
 373                         neighbours[j] = m;
 374                         j++;
 375                 }
 376
 377                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 378
 379                 ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 380
 381                 for(k = 0; k < j; k++)
 382                 {
 383                         ir_fprintf (f,"%+F, ", neighbours[k]);
 384                 }
 385
 386                 ir_fprintf (f,"\n");
 387
 388                 free(neighbours);
 389         }
 390
 391         free(all_nodes);
 392
 393 }
 394
 395 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
 396 {
 397 #ifdef WITH_LIBCORE
 398         int tests = BE_CH_PERFORMANCETEST_COUNT;
 399         coloring_t coloring;
 400
 401         int used_memory;
 402
 403         int i = 0;
 404         int rt;
 405         copy_opt_t *co;
 406         be_ifg_t *old_if = chordal_env->ifg;
 407
 408         lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
 409         unsigned long elapsed_usec = 0;
 410
 411         if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
 412         {
 413                 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
 414                 coloring_save(&coloring);
 415
 416                 lc_timer_reset(timer);
 417
 418                 for (i = 0; i<tests; i++) /* performance test with std */
 419                 {
 420
 421                         used_memory = lc_get_heap_used_bytes();
 422
 423                         rt = lc_timer_enter_high_priority();
 424                         lc_timer_start(timer);
 425
 426                         chordal_env->ifg = be_ifg_std_new(chordal_env);
 427
 428                         lc_timer_stop(timer);
 429                         rt = lc_timer_leave_high_priority();
 430
 431                         used_memory = lc_get_heap_used_bytes() - used_memory;
 432
 433                         coloring_restore(&coloring);
 434
 435                         co = NULL;
 436                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 437                         co_build_ou_structure(co);
 438                         co_build_graph_structure(co);
 439
 440                         rt = lc_timer_enter_high_priority();
 441                         lc_timer_start(timer);
 442
 443                         co_solve_heuristic_new(co);
 444
 445                         lc_timer_stop(timer);
 446                         rt = lc_timer_leave_high_priority();
 447
 448                         co_free_graph_structure(co);
 449                         co_free_ou_structure(co);
 450                         free_copy_opt(co);
 451                         be_ifg_free(chordal_env->ifg);
 452
 453                 }
 454
 455                 elapsed_usec = lc_timer_elapsed_usec(timer);
 456                 /* calculating average */
 457                 elapsed_usec = elapsed_usec / tests;
 458
 459                 ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 460
 461                 used_memory=0;
 462                 elapsed_usec=0;
 463
 464                 for (i = 0; i<tests; i++)  /* performance test with clique */
 465                 {
 466                         used_memory = lc_get_heap_used_bytes();
 467
 468                         rt = lc_timer_enter_high_priority();
 469                         lc_timer_start(timer);
 470
 471                         chordal_env->ifg = be_ifg_clique_new(chordal_env);
 472
 473                         lc_timer_stop(timer);
 474                         rt = lc_timer_leave_high_priority();
 475
 476                         used_memory = lc_get_heap_used_bytes() - used_memory;
 477
 478                         coloring_restore(&coloring);
 479
 480                         co = NULL;
 481                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 482                         co_build_ou_structure(co);
 483                         co_build_graph_structure(co);
 484
 485                         rt = lc_timer_enter_high_priority();
 486                         lc_timer_start(timer);
 487
 488                         co_solve_heuristic_new(co);
 489
 490                         lc_timer_stop(timer);
 491                         rt = lc_timer_leave_high_priority();
 492
 493                         co_free_graph_structure(co);
 494                         co_free_ou_structure(co);
 495                         free_copy_opt(co);
 496                         be_ifg_free(chordal_env->ifg);
 497
 498                 }
 499
 500                 elapsed_usec = lc_timer_elapsed_usec(timer);
 501                 /* calculating average */
 502                 elapsed_usec = elapsed_usec / tests;
 503
 504                 ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 505
 506                 used_memory=0;
 507                 elapsed_usec=0;
 508
 509                 for (i = 0; i<tests; i++)  /* performance test with list */
 510                 {
 511                         used_memory = lc_get_heap_used_bytes();
 512
 513                         rt = lc_timer_enter_high_priority();
 514                         lc_timer_start(timer);
 515
 516                         chordal_env->ifg = be_ifg_list_new(chordal_env);
 517
 518                         lc_timer_stop(timer);
 519                         rt = lc_timer_leave_high_priority();
 520
 521                         used_memory = lc_get_heap_used_bytes() - used_memory;
 522
 523                         coloring_restore(&coloring);
 524
 525                         co = NULL;
 526                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 527                         co_build_ou_structure(co);
 528                         co_build_graph_structure(co);
 529
 530                         rt = lc_timer_enter_high_priority();
 531                         lc_timer_start(timer);
 532
 533                         co_solve_heuristic_new(co);
 534
 535                         lc_timer_stop(timer);
 536                         rt = lc_timer_leave_high_priority();
 537
 538                         co_free_graph_structure(co);
 539                         co_free_ou_structure(co);
 540                         free_copy_opt(co);
 541                         be_ifg_free(chordal_env->ifg);
 542
 543                 }
 544
 545                 elapsed_usec = lc_timer_elapsed_usec(timer);
 546                 /* calculating average */
 547                 elapsed_usec = elapsed_usec / tests;
 548
 549                 ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 550
 551                 used_memory=0;
 552                 elapsed_usec=0;
 553
 554                 for (i = 0; i<tests; i++)  /* performance test with pointer */
 555                 {
 556                         used_memory = lc_get_heap_used_bytes();
 557
 558                         rt = lc_timer_enter_high_priority();
 559                         lc_timer_start(timer);
 560
 561                         chordal_env->ifg = be_ifg_pointer_new(chordal_env);
 562
 563                         lc_timer_stop(timer);
 564                         rt = lc_timer_leave_high_priority();
 565
 566                         used_memory = lc_get_heap_used_bytes() - used_memory;
 567
 568                         coloring_restore(&coloring);
 569
 570                         co = NULL;
 571                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 572                         co_build_ou_structure(co);
 573                         co_build_graph_structure(co);
 574
 575                         rt = lc_timer_enter_high_priority();
 576                         lc_timer_start(timer);
 577
 578                         co_solve_heuristic_new(co);
 579
 580                         lc_timer_stop(timer);
 581                         rt = lc_timer_leave_high_priority();
 582
 583                         co_free_graph_structure(co);
 584                         co_free_ou_structure(co);
 585                         free_copy_opt(co);
 586                         be_ifg_free(chordal_env->ifg);
 587
 588                 }
 589
 590                 elapsed_usec = lc_timer_elapsed_usec(timer);
 591                 /* calculating average */
 592                 elapsed_usec = elapsed_usec / tests;
 593
 594                 ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
 595
 596                 i=0;
 597                 used_memory=0;
 598                 elapsed_usec=0;
 599         }
 600
 601         chordal_env->ifg = old_if;
 602 #endif /* WITH_LIBCORE */
 603 }
 604
 605 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 606 {
 607         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 608         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 609         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 610
 611         ir_node *n, *m;
 612
 613         fprintf(file, "graph G {\n\tgraph [");
 614         if(cb->graph_attr)
 615                 cb->graph_attr(file, self);
 616         fprintf(file, "];\n");
 617
 618         if(cb->at_begin)
 619                 cb->at_begin(file, self);
 620
 621         be_ifg_foreach_node(ifg, nodes_it, n) {
 622                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 623                         int idx = get_irn_idx(n);
 624                         bitset_set(nodes, idx);
 625                         fprintf(file, "\tnode [");
 626                         if(cb->node_attr)
 627                                 cb->node_attr(file, self, n);
 628                         fprintf(file, "]; n%d;\n", idx);
 629                 }
 630         }
 631
 632         /* Check, if all neighbours are indeed connected to the node. */
 633         be_ifg_foreach_node(ifg, nodes_it, n) {
 634                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 635                         int n_idx = get_irn_idx(n);
 636                         int m_idx = get_irn_idx(m);
 637
 638                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 639                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 640                                 if(cb->edge_attr)
 641                                         cb->edge_attr(file, self, n, m);
 642                                 fprintf(file, "];\n");
 643                         }
 644                 }
 645         }
 646
 647         if(cb->at_end)
 648                 cb->at_end(file, self);
 649
 650         fprintf(file, "}\n");
 651         bitset_free(nodes);
 652 }
 653
 654 void be_ifg_stat(const be_ifg_t *ifg, ir_graph *irg, be_ifg_stat_t *stat)
 655 {
 656         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 657         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 658         bitset_t *nodes = bitset_irg_malloc(irg);
 659
 660         ir_node *n, *m;
 661
 662         memset(stat, 0, sizeof(stat[0]));
 663         be_ifg_foreach_node(ifg, nodes_it, n) {
 664                 stat->n_nodes += 1;
 665                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 666                         bitset_add_irn(nodes, n);
 667                         stat->n_edges += !bitset_contains_irn(nodes, m);
 668                 }
 669         }
 670
 671         bitset_free(nodes);
 672 }