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