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, FILE *f)
 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                 all_nodes[i] = n;
 289                 i++;
 290         }
 291
 292         qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);
 293
 294         for (i = 0; i < node_count; i++)
 295         {
 296                 ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
 297                 int j = 0;
 298                 int k = 0;
 299                 int degree = 0;
 300
 301                 degree = be_ifg_degree(ifg, all_nodes[i]);
 302
 303                 be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
 304                 {
 305                         neighbours[j] = m;
 306                         j++;
 307                 }
 308
 309                 qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);
 310
 311                 ir_fprintf(f, "%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
 312
 313                 for(k = 0; k < j; k++)
 314                 {
 315                         ir_fprintf(f, "%+F, ", neighbours[k]);
 316                 }
 317
 318                 ir_fprintf(f, "\n");
 319
 320                 free(neighbours);
 321         }
 322
 323         free(all_nodes);
 324
 325 }
 326
 327 void be_ifg_check_performance(be_chordal_env_t *chordal_env)
 328 {
 329         int tests = BE_CH_PERFORMANCETEST_COUNT;
 330         coloring_t coloring;
 331
 332 #ifdef linux
 333         struct mallinfo minfo;
 334         int used_memory = 0;
 335 #endif /* linux */
 336
 337         int i = 0;
 338         int rt;
 339         copy_opt_t *co;
 340         be_ifg_t *old_if = chordal_env->ifg;
 341
 342         lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
 343         unsigned long elapsed_usec = 0;
 344
 345         if ((int) get_irg_estimated_node_cnt >= BE_CH_PERFORMANCETEST_MIN_NODES)
 346         {
 347
 348                 coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
 349                 coloring_save(&coloring);
 350
 351                 lc_timer_reset(timer);
 352
 353                 for (i = 0; i<tests; i++) /* performance test with std */
 354                 {
 355 #ifdef linux
 356                         minfo = mallinfo();
 357                         used_memory = minfo.uordblks;
 358 #endif /* linux */
 359
 360                         rt = lc_timer_enter_high_priority();
 361                         lc_timer_start(timer);
 362
 363                         chordal_env->ifg = be_ifg_std_new(chordal_env);
 364
 365                         lc_timer_stop(timer);
 366                         rt = lc_timer_leave_high_priority();
 367
 368 #ifdef linux
 369                         minfo = mallinfo();
 370                         used_memory = minfo.uordblks - used_memory;
 371 #endif /* linux */
 372
 373                         coloring_restore(&coloring);
 374
 375                         co = NULL;
 376                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 377                         co_build_ou_structure(co);
 378                         co_build_graph_structure(co);
 379
 380                         rt = lc_timer_enter_high_priority();
 381                         lc_timer_start(timer);
 382
 383                         co_solve_heuristic_new(co);
 384
 385                         lc_timer_stop(timer);
 386                         rt = lc_timer_leave_high_priority();
 387
 388                         co_free_graph_structure(co);
 389                         co_free_ou_structure(co);
 390                         free_copy_opt(co);
 391                         be_ifg_free(chordal_env->ifg);
 392
 393                 }
 394
 395                 elapsed_usec = lc_timer_elapsed_usec(timer);
 396                 /* calculating average */
 397                 elapsed_usec = elapsed_usec / tests;
 398
 399                 ir_printf("\nstd:; %+F; ",current_ir_graph);
 400 #ifdef linux
 401                 ir_printf("%u; ", used_memory);
 402 #endif /* linux */
 403                 ir_printf("%u; ", elapsed_usec);
 404
 405                 i=0;
 406 #ifdef linux
 407                 used_memory=0;
 408 #endif /* linux */
 409                 elapsed_usec=0;
 410
 411                 for (i = 0; i<tests; i++)  /* performance test with clique */
 412                 {
 413 #ifdef linux
 414                         minfo = mallinfo();
 415                         used_memory = minfo.uordblks;
 416 #endif /* linux */
 417
 418                         rt = lc_timer_enter_high_priority();
 419                         lc_timer_start(timer);
 420
 421                         chordal_env->ifg = be_ifg_clique_new(chordal_env);
 422
 423                         lc_timer_stop(timer);
 424                         rt = lc_timer_leave_high_priority();
 425
 426 #ifdef linux
 427                         minfo = mallinfo();
 428                         used_memory = minfo.uordblks - used_memory;
 429 #endif /* linux */
 430
 431                         coloring_restore(&coloring);
 432
 433                         co = NULL;
 434                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 435                         co_build_ou_structure(co);
 436                         co_build_graph_structure(co);
 437
 438                         rt = lc_timer_enter_high_priority();
 439                         lc_timer_start(timer);
 440
 441                         co_solve_heuristic_new(co);
 442
 443                         lc_timer_stop(timer);
 444                         rt = lc_timer_leave_high_priority();
 445
 446                         co_free_graph_structure(co);
 447                         co_free_ou_structure(co);
 448                         free_copy_opt(co);
 449                         be_ifg_free(chordal_env->ifg);
 450
 451                 }
 452
 453                 elapsed_usec = lc_timer_elapsed_usec(timer);
 454                 /* calculating average */
 455                 elapsed_usec = elapsed_usec / tests;
 456
 457                 ir_printf("\nclique:; %+F; ",current_ir_graph);
 458 #ifdef linux
 459                 ir_printf("%u; ", used_memory);
 460 #endif /* linux */
 461                 ir_printf("%u; ", elapsed_usec);
 462
 463                 i=0;
 464 #ifdef linux
 465                 used_memory=0;
 466 #endif /* linux */
 467                 elapsed_usec=0;
 468
 469                 for (i = 0; i<tests; i++)  /* performance test with list */
 470                 {
 471 #ifdef linux
 472                         minfo = mallinfo();
 473                         used_memory = minfo.uordblks;
 474 #endif /* linux */
 475
 476                         rt = lc_timer_enter_high_priority();
 477                         lc_timer_start(timer);
 478
 479                         chordal_env->ifg = be_ifg_list_new(chordal_env);
 480
 481                         lc_timer_stop(timer);
 482                         rt = lc_timer_leave_high_priority();
 483
 484 #ifdef linux
 485                         minfo = mallinfo();
 486                         used_memory = minfo.uordblks - used_memory;
 487 #endif /* linux */
 488
 489                         coloring_restore(&coloring);
 490
 491                         co = NULL;
 492                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 493                         co_build_ou_structure(co);
 494                         co_build_graph_structure(co);
 495
 496                         rt = lc_timer_enter_high_priority();
 497                         lc_timer_start(timer);
 498
 499                         co_solve_heuristic_new(co);
 500
 501                         lc_timer_stop(timer);
 502                         rt = lc_timer_leave_high_priority();
 503
 504                         co_free_graph_structure(co);
 505                         co_free_ou_structure(co);
 506                         free_copy_opt(co);
 507                         be_ifg_free(chordal_env->ifg);
 508
 509                 }
 510
 511                 elapsed_usec = lc_timer_elapsed_usec(timer);
 512                 /* calculating average */
 513                 elapsed_usec = elapsed_usec / tests;
 514
 515                 ir_printf("\nlist:; %+F; ",current_ir_graph);
 516 #ifdef linux
 517                 ir_printf("%u; ", used_memory);
 518 #endif /* linux */
 519                 ir_printf("%u; ", elapsed_usec);
 520
 521                 i=0;
 522 #ifdef linux
 523                 used_memory=0;
 524 #endif /* linux */
 525                 elapsed_usec=0;
 526
 527                 for (i = 0; i<tests; i++)  /* performance test with pointer */
 528                 {
 529 #ifdef linux
 530                         minfo = mallinfo();
 531                         used_memory = minfo.uordblks;
 532 #endif /* linux */
 533
 534                         rt = lc_timer_enter_high_priority();
 535                         lc_timer_start(timer);
 536
 537                         chordal_env->ifg = be_ifg_pointer_new(chordal_env);
 538
 539                         lc_timer_stop(timer);
 540                         rt = lc_timer_leave_high_priority();
 541
 542 #ifdef linux
 543                         minfo = mallinfo();
 544                         used_memory = minfo.uordblks - used_memory;
 545 #endif /* linux */
 546
 547                         coloring_restore(&coloring);
 548
 549                         co = NULL;
 550                         co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
 551                         co_build_ou_structure(co);
 552                         co_build_graph_structure(co);
 553
 554                         rt = lc_timer_enter_high_priority();
 555                         lc_timer_start(timer);
 556
 557                         co_solve_heuristic_new(co);
 558
 559                         lc_timer_stop(timer);
 560                         rt = lc_timer_leave_high_priority();
 561
 562                         co_free_graph_structure(co);
 563                         co_free_ou_structure(co);
 564                         free_copy_opt(co);
 565                         be_ifg_free(chordal_env->ifg);
 566
 567                 }
 568
 569                 elapsed_usec = lc_timer_elapsed_usec(timer);
 570                 /* calculating average */
 571                 elapsed_usec = elapsed_usec / tests;
 572
 573                 ir_printf("\npointer:; %+F; ",current_ir_graph);
 574 #ifdef linux
 575                 ir_printf("%u; ", used_memory);
 576 #endif /* linux */
 577                 ir_printf("%u; ", elapsed_usec);
 578
 579                 i=0;
 580 #ifdef linux
 581                 used_memory=0;
 582 #endif /* linux */
 583                 elapsed_usec=0;
 584         }
 585
 586         chordal_env->ifg = old_if;
 587 }
 588
 589 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
 590 {
 591         void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
 592         void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
 593         bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
 594
 595         ir_node *n, *m;
 596
 597         fprintf(file, "graph G {\n\tgraph [");
 598         if(cb->graph_attr)
 599                 cb->graph_attr(file, self);
 600         fprintf(file, "];\n");
 601
 602         if(cb->at_begin)
 603                 cb->at_begin(file, self);
 604
 605         be_ifg_foreach_node(ifg, nodes_it, n) {
 606                 if(cb->is_dump_node && cb->is_dump_node(self, n)) {
 607                         int idx = get_irn_idx(n);
 608                         bitset_set(nodes, idx);
 609                         fprintf(file, "\tnode [");
 610                         if(cb->node_attr)
 611                                 cb->node_attr(file, self, n);
 612                         fprintf(file, "]; n%d;\n", idx);
 613                 }
 614         }
 615
 616         /* Check, if all neighbours are indeed connected to the node. */
 617         be_ifg_foreach_node(ifg, nodes_it, n) {
 618                 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
 619                         int n_idx = get_irn_idx(n);
 620                         int m_idx = get_irn_idx(m);
 621
 622                         if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
 623                                 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
 624                                 if(cb->edge_attr)
 625                                         cb->edge_attr(file, self, n, m);
 626                                 fprintf(file, "];\n");
 627                         }
 628                 }
 629         }
 630
 631         if(cb->at_end)
 632                 cb->at_end(file, self);
 633
 634         fprintf(file, "}\n");
 635         bitset_free(nodes);
 636 }