nsz Git - libfirm/blob - ir/stat/firmstat.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/firmstat.c
   4  * Purpose:     Statistics for Firm.
   5  * Author:      Michael Beck
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 2004 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 #ifdef HAVE_CONFIG_H
  13 # include "config.h"
  14 #endif
  15
  16 # include <string.h>
  17
  18 # include "irop_t.h"
  19 # include "irnode_t.h"
  20 # include "irgraph_t.h"
  21 # include "pset.h"
  22 # include "irprog.h"
  23 # include "irgwalk.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27
  28 #undef obstack_chunk_alloc
  29 #undef obstack_chunk_free
  30 #define obstack_chunk_alloc     malloc
  31 #define obstack_chunk_free      free
  32 #include <obstack.h>
  33
  34 #ifdef FIRM_STATISTICS
  35
  36 #include "firmstat.h"
  37
  38 /*
  39  * 32 bit should be enough for now
  40  */
  41 #define STAT_CNT_NUM 1
  42
  43 typedef struct _counter_t {
  44   unsigned cnt[STAT_CNT_NUM];
  45 } counter_t;
  46
  47 /*
  48  * An entry for ir_nodes
  49  */
  50 typedef struct _node_entry_t {
  51   counter_t   count;                    /**< amount of nodes in this entry */
  52   counter_t   new_node;                 /**< amount of new nodes for this entry */
  53   counter_t   into_Id;                  /**< amount of nodes that turned into Id's for this entry */
  54   const ir_op *op;                      /**< the op for this entry */
  55 } node_entry_t;
  56
  57 /*
  58  * An entry for ir_graphs
  59  */
  60 typedef struct _graph_entry_t {
  61   pset           *opcode_hash;                  /**< hash map containing the opcode counter */
  62   counter_t      walked;                        /**< walker walked over the graph */
  63   counter_t      walked_blocks;                 /**< walker walked over the graph blocks */
  64   counter_t      was_inlined;                   /**< number of times other graph were inlined */
  65   counter_t      got_inlined;                   /**< number of times this graph was inlined */
  66   pset           *opt_hash[STAT_OPT_MAX];       /**< hash maps containing opcode counter for optimizations */
  67   ir_graph       *irg;                          /**< the graph of this object */
  68   entity         *ent;                          /**< the entity of this graph if one exists */
  69   int            deleted;                       /**< set if this irg was deleted */
  70 } graph_entry_t;
  71
  72 /**
  73  * An entry for optimized ir_nodes
  74  */
  75 typedef struct _opt_entry_t {
  76   counter_t   count;                    /**< optimization counter */
  77   const ir_op *op;                      /**< the op for this entry */
  78 } opt_entry_t;
  79
  80 /**
  81  * statistics info
  82  */
  83 typedef struct _statistic_info_t {
  84   struct obstack cnts;                  /**< obstack containing the counters */
  85   pset           *opcode_hash;          /**< hash map containing the opcode counter */
  86   pset           *irg_hash;             /**< hash map containing the counter for irgs */
  87   FILE           *f;                    /**< outputfile */
  88   ir_op          *op_Phi0;              /**< needed pseudo op */
  89   int            recursive;             /**< flag for detecting recursive hook calls */
  90   int            in_dead_node_elim;     /**< set, if dead node elimination runs */
  91 } stat_info_t;
  92
  93 #define STAT_ENTER              ++status->recursive
  94 #define STAT_LEAVE              --status->recursive
  95 #define STAT_ENTER_SINGLE       do { if (status->recursive > 0) return; ++status->recursive; } while (0)
  96
  97 /*
  98  * global status
  99  */
 100 static stat_info_t _status, *status = &_status;
 101
 102 /**
 103  * increase a counter
 104  */
 105 static INLINE void cnt_inc(counter_t *cnt)
 106 {
 107   int i;
 108
 109   for (i = 0; i < STAT_CNT_NUM; ++i) {
 110     if (++cnt->cnt[i])
 111       break;
 112   }
 113 }
 114
 115 /**
 116  * decreace a counter
 117  */
 118 static INLINE void cnt_dec(counter_t *cnt)
 119 {
 120   int i;
 121
 122   for (i = 0; i < STAT_CNT_NUM; ++i) {
 123     if (--cnt->cnt[i] != -1)
 124       break;
 125   }
 126 }
 127
 128 /**
 129  * set a counter to zero
 130  */
 131 static INLINE void cnt_clr(counter_t *cnt)
 132 {
 133   memset(cnt->cnt, 0, sizeof(cnt->cnt));
 134 }
 135
 136 /**
 137  * add a counter to another
 138  */
 139 static inline void cnt_add(counter_t *dst, const counter_t *src)
 140 {
 141   int i;
 142
 143   for (i = 0; i < STAT_CNT_NUM; ++i) {
 144     unsigned a = dst->cnt[i] + src->cnt[i];
 145     unsigned no_carry = a >= dst->cnt[i];
 146
 147     dst->cnt[i] = a;
 148
 149     if (no_carry) {
 150       /* no carry */
 151       break;
 152     }
 153   }
 154 }
 155
 156 /*
 157  * compare two elements of the opcode hash
 158  */
 159 static int opcode_cmp(const void *elt, const void *key)
 160 {
 161   const node_entry_t *e1 = elt;
 162   const node_entry_t *e2 = key;
 163
 164   return e1->op->code - e2->op->code;
 165 }
 166
 167 /*
 168  * compare two elements of the graph hash
 169  */
 170 static int graph_cmp(const void *elt, const void *key)
 171 {
 172   const graph_entry_t *e1 = elt;
 173   const graph_entry_t *e2 = key;
 174
 175   return e1->irg != e2->irg;
 176 }
 177
 178 /*
 179  * compare two elements of the optimization hash
 180  */
 181 static int opt_cmp(const void *elt, const void *key)
 182 {
 183   const opt_entry_t *e1 = elt;
 184   const opt_entry_t *e2 = key;
 185
 186   return e1->op->code != e2->op->code;
 187 }
 188
 189 /**
 190  * Returns the associates node_entry_t for an ir_op
 191  */
 192 static node_entry_t *opcode_get_entry(const ir_op *op, pset *set)
 193 {
 194   node_entry_t key;
 195   node_entry_t *elem;
 196
 197   key.op = op;
 198
 199   elem = pset_find(set, &key, op->code);
 200   if (elem)
 201     return elem;
 202
 203   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 204
 205   /* clear counter */
 206   cnt_clr(&elem->count);
 207   cnt_clr(&elem->new_node);
 208   cnt_clr(&elem->into_Id);
 209
 210   elem->op = op;
 211
 212   return pset_insert(set, elem, op->code);
 213 }
 214
 215 /**
 216  * calculates a hash value for an irg
 217  * Addresses are typically aligned at 32bit, so we ignore the lowest bits
 218  */
 219 static INLINE unsigned irg_hash(const ir_graph *irg)
 220 {
 221   return (unsigned)irg >> 3;
 222 }
 223
 224 /**
 225  * Returns the acssociates graph_entry_t for an irg
 226  */
 227 static graph_entry_t *graph_get_entry(ir_graph *irg, pset *set)
 228 {
 229   graph_entry_t key;
 230   graph_entry_t *elem;
 231   int i;
 232
 233   key.irg = irg;
 234
 235   elem = pset_find(set, &key, irg_hash(irg));
 236   if (elem)
 237     return elem;
 238
 239   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 240
 241   cnt_clr(&elem->walked);
 242   cnt_clr(&elem->walked_blocks);
 243   cnt_clr(&elem->got_inlined);
 244   cnt_clr(&elem->was_inlined);
 245
 246   /* new hash table for opcodes here  */
 247   elem->opcode_hash  = new_pset(opcode_cmp, 5);
 248   elem->irg          = irg;
 249
 250   for (i = 0; i < sizeof(elem->opt_hash)/sizeof(elem->opt_hash[0]); ++i)
 251     elem->opt_hash[i] = new_pset(opt_cmp, 4);
 252
 253   return pset_insert(set, elem, irg_hash(irg));
 254 }
 255
 256 /**
 257  * Returns the associates opt_entry_t for an ir_op
 258  */
 259 static opt_entry_t *opt_get_entry(const ir_op *op, pset *set)
 260 {
 261   opt_entry_t key;
 262   opt_entry_t *elem;
 263
 264   key.op = op;
 265
 266   elem = pset_find(set, &key, op->code);
 267   if (elem)
 268     return elem;
 269
 270   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 271
 272   /* clear new counter */
 273   cnt_clr(&elem->count);
 274
 275   elem->op = op;
 276
 277   return pset_insert(set, elem, op->code);
 278 }
 279
 280 /**
 281  * walker for reachable nodes count
 282  */
 283 static void count_nodes(ir_node *node, void *env)
 284 {
 285   pset *set = env;
 286   node_entry_t *entry;
 287   ir_op *op = get_irn_op(node);
 288
 289   if (op->code == iro_Phi && get_irn_arity(node) == 0) {
 290     /* special case, a Phi0 node, count on extra counter */
 291     op = status->op_Phi0;
 292   }
 293
 294   entry = opcode_get_entry(op, set);
 295
 296   cnt_inc(&entry->count);
 297 }
 298
 299 /**
 300  * count all reachable nodes in a graph
 301  */
 302 static void count_nodes_in_graph(ir_graph *irg, pset *set)
 303 {
 304   irg_walk_graph(irg, count_nodes, NULL, set);
 305 }
 306
 307 /* ---------------------------------------------------------------------- */
 308
 309 /* initialize the statistics module. */
 310 void stat_init(void)
 311 {
 312   obstack_init(&status->cnts);
 313
 314   /* create the hash-tables */
 315   status->opcode_hash = new_pset(opcode_cmp, 8);
 316   status->irg_hash    = new_pset(graph_cmp, 8);
 317
 318   status->f           = fopen("firmstat.txt", "w");
 319   status->op_Phi0     = NULL;
 320 }
 321
 322 /* A new IR op is registered. */
 323 void stat_new_ir_op(const ir_op *op)
 324 {
 325   STAT_ENTER;
 326   {
 327     /* execute for side effect :-) */
 328     opcode_get_entry(op, status->opcode_hash);
 329   }
 330   STAT_LEAVE;
 331 }
 332
 333 /* An IR op is freed. */
 334 void stat_free_ir_op(const ir_op *op)
 335 {
 336   STAT_ENTER;
 337   {
 338   }
 339   STAT_LEAVE;
 340 }
 341
 342 /* A new node is created. */
 343 void stat_new_node(const ir_node *node)
 344 {
 345   /* do NOT count during dead node elimination */
 346   if (status->in_dead_node_elim > 0)
 347     return;
 348
 349   STAT_ENTER;
 350   {
 351     node_entry_t *entry;
 352     graph_entry_t *graph;
 353     ir_op *op = get_irn_op(node);
 354
 355     if (op->code == iro_Phi && get_irn_arity(node) == 0) {
 356       /* special case, a Phi0 node, count on extra counter */
 357       if (! status->op_Phi0) {
 358         ir_op *op_Phi = get_op_Phi();
 359
 360         status->op_Phi0 = new_ir_op(0xFFFF, "Phi0", op_Phi->pinned, op_Phi->flags, op_Phi->opar, op_Phi->op_index, op_Phi->attr_size);
 361       }
 362       op = status->op_Phi0;
 363     }
 364
 365     entry = opcode_get_entry(op, status->opcode_hash);
 366     graph = graph_get_entry(current_ir_graph, status->irg_hash);
 367
 368     /* increase global value */
 369     cnt_inc(&entry->new_node);
 370
 371     /* increase local value */
 372     entry = opcode_get_entry(op, graph->opcode_hash);
 373     cnt_inc(&entry->new_node);
 374   }
 375   STAT_LEAVE;
 376 }
 377
 378 /* A node is changed into a Id node */
 379 void stat_turn_into_id(const ir_node *node)
 380 {
 381   STAT_ENTER;
 382   {
 383     node_entry_t *entry;
 384     graph_entry_t *graph;
 385     ir_op *op = get_irn_op(node);
 386
 387     if (op->code == iro_Phi && get_irn_arity(node) == 0) {
 388       /* special case, a Phi0 node, count on extra counter */
 389       if (! status->op_Phi0) {
 390         ir_op *op_Phi = get_op_Phi();
 391
 392         status->op_Phi0 = new_ir_op(0xFFFF, "Phi0", op_Phi->pinned, op_Phi->flags, op_Phi->opar, op_Phi->op_index, op_Phi->attr_size);
 393       }
 394       op = status->op_Phi0;
 395     }
 396
 397     entry = opcode_get_entry(op, status->opcode_hash);
 398     graph = graph_get_entry(current_ir_graph, status->irg_hash);
 399
 400     /* increase global value */
 401     cnt_inc(&entry->into_Id);
 402
 403     /* increase local value */
 404     entry = opcode_get_entry(op, graph->opcode_hash);
 405     cnt_inc(&entry->into_Id);
 406   }
 407   STAT_LEAVE;
 408 }
 409
 410 /* A new graph was created */
 411 void stat_new_graph(ir_graph *irg, entity *ent)
 412 {
 413   STAT_ENTER;
 414   {
 415     /* execute for side effect :-) */
 416     graph_entry_t * graph = graph_get_entry(irg, status->irg_hash);
 417
 418     graph->ent     = ent;
 419     graph->deleted = 0;
 420   }
 421   STAT_LEAVE;
 422 }
 423
 424 /*
 425  * A graph was deleted
 426  */
 427 void stat_free_graph(ir_graph *irg)
 428 {
 429   STAT_ENTER;
 430   {
 431     graph_entry_t * graph = graph_get_entry(irg, status->irg_hash);
 432
 433     graph->deleted = 1;
 434
 435     /* count the nodes of the graph yet, it will be destroyed later */
 436     count_nodes_in_graph(irg, graph->opcode_hash);
 437   }
 438   STAT_LEAVE;
 439 }
 440
 441 /*
 442  * A walk over a graph is initiated. Do not count walks from statistic code.
 443  */
 444 void stat_irg_walk(ir_graph *irg, void *pre, void *post)
 445 {
 446   STAT_ENTER_SINGLE;
 447   {
 448     graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
 449
 450     cnt_inc(&graph->walked);
 451   }
 452   STAT_LEAVE;
 453 }
 454
 455 /*
 456  * A walk over the graph's blocks is initiated. Do not count walks from statistic code.
 457  */
 458 void stat_irg_block_walk(ir_graph *irg, const ir_node *node, void *pre, void *post)
 459 {
 460   STAT_ENTER_SINGLE;
 461   {
 462     graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
 463
 464     cnt_inc(&graph->walked_blocks);
 465   }
 466   STAT_LEAVE;
 467 }
 468
 469 /**
 470  * called for every node that is removed due to an optimization
 471  */
 472 static void removed_due_opt(ir_node *n, pset *set)
 473 {
 474   ir_op *op          = get_irn_op(n);
 475   opt_entry_t *entry = opt_get_entry(op, set);
 476
 477   /* increase global value */
 478   cnt_inc(&entry->count);
 479 }
 480
 481 /*
 482  * Some nodes were optimized into some others due to an optimization
 483  */
 484 void stat_merge_nodes(
 485     ir_node **new_node_array, int new_num_entries,
 486     ir_node **old_node_array, int old_num_entries,
 487     stat_opt_kind opt)
 488 {
 489   STAT_ENTER;
 490   {
 491     int i, j;
 492     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
 493
 494     for (i = 0; i < old_num_entries; ++i) {
 495       for (j = 0; j < new_num_entries; ++j)
 496         if (old_node_array[i] == new_node_array[j])
 497           break;
 498
 499       /* nodes might be in new and old, these are NOT removed */
 500       if (j >= new_num_entries) {
 501         removed_due_opt(old_node_array[i], graph->opt_hash[opt]);
 502       }
 503     }
 504   }
 505   STAT_LEAVE;
 506 }
 507
 508 /*
 509  * A node was lowered into other nodes
 510  */
 511 void stat_lower(ir_node *node)
 512 {
 513   STAT_ENTER;
 514   {
 515     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
 516
 517     removed_due_opt(node, graph->opt_hash[STAT_LOWERED]);
 518   }
 519   STAT_LEAVE;
 520 }
 521
 522 /*
 523  * A graph was inlined
 524  */
 525 void stat_inline(ir_node *call, ir_graph *called_irg)
 526 {
 527   STAT_ENTER;
 528   {
 529     ir_graph *irg = get_irn_irg(call);
 530     graph_entry_t *i_graph = graph_get_entry(called_irg, status->irg_hash);
 531     graph_entry_t *graph   = graph_get_entry(irg, status->irg_hash);
 532
 533     cnt_inc(&graph->got_inlined);
 534     cnt_inc(&i_graph->was_inlined);
 535   }
 536   STAT_LEAVE;
 537 }
 538
 539 /*
 540  * Start the dead node elimination.
 541  */
 542 void stat_dead_node_elim_start(ir_graph *irg)
 543 {
 544   ++status->in_dead_node_elim;
 545 }
 546
 547 /*
 548  * Stops the dead node elimination.
 549  */
 550 void stat_dead_node_elim_stop(ir_graph *irg)
 551 {
 552   --status->in_dead_node_elim;
 553 }
 554
 555 /**
 556  * dumps a opcode hash
 557  */
 558 static void dump_opcode_hash(pset *set)
 559 {
 560   node_entry_t *entry;
 561   counter_t f_count;
 562   counter_t f_new_node;
 563   counter_t f_Id;
 564
 565   cnt_clr(&f_count);
 566   cnt_clr(&f_new_node);
 567   cnt_clr(&f_Id);
 568
 569   fprintf(status->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
 570   for (entry = pset_first(set); entry; entry = pset_next(set)) {
 571     fprintf(status->f, "%-16s %8d %8d %8d\n",
 572         get_id_str(entry->op->name), entry->count.cnt[0], entry->new_node.cnt[0], entry->into_Id.cnt[0]);
 573
 574     cnt_add(&f_count,    &entry->count);
 575     cnt_add(&f_new_node, &entry->new_node);
 576     cnt_add(&f_Id,       &entry->into_Id);
 577   }
 578   fprintf(status->f, "-------------------------------------------\n");
 579   fprintf(status->f, "%-16s %8d %8d %8d\n", "Sum",
 580      f_count.cnt[0],
 581      f_new_node.cnt[0],
 582      f_Id.cnt[0]);
 583 }
 584
 585 static const char *opt_names[] = {
 586   "straightening optimization",
 587   "if simplification",
 588   "algebraic simplification",
 589   "Phi optmization",
 590   "Write-After-Write optimization",
 591   "Write-After-Read optimization",
 592   "Tuple optimization",
 593   "ID optimization",
 594   "Constant evaluation",
 595   "Lowered",
 596 };
 597
 598 /**
 599  * dumps a optimization hash
 600  */
 601 static void dump_opt_hash(pset *set, int index)
 602 {
 603   opt_entry_t *entry = pset_first(set);
 604
 605   if (entry) {
 606     fprintf(status->f, "\n%s:\n", opt_names[index]);
 607     fprintf(status->f, "%-16s %-8s\n", "Opcode", "deref");
 608
 609     for (; entry; entry = pset_next(set)) {
 610       fprintf(status->f, "%-16s %8d\n",
 611           get_id_str(entry->op->name), entry->count.cnt[0]);
 612     }
 613   }
 614 }
 615
 616 /* Finish the statistics */
 617 void stat_finish(void)
 618 {
 619   STAT_ENTER;
 620   {
 621     int i;
 622     graph_entry_t *entry;
 623     ir_graph *const_irg = get_const_code_irg();
 624
 625     /* dump global */
 626     fprintf(status->f, "\nGlobal counts:\n");
 627     dump_opcode_hash(status->opcode_hash);
 628
 629     for (entry = pset_first(status->irg_hash); entry; entry = pset_next(status->irg_hash)) {
 630       entity *ent = entry->ent;
 631
 632       if (! entry->deleted) {
 633         /* the graph is still alive, count the nodes on it */
 634         count_nodes_in_graph(entry->irg, entry->opcode_hash);
 635       }
 636
 637       if (entry->irg == const_irg) {
 638         fprintf(status->f, "\nConst code Irg %p", entry->irg);
 639       }
 640       else {
 641         if (ent)
 642           fprintf(status->f, "\nEntity %s, Irg %p", get_entity_name(ent), entry->irg);
 643         else
 644           fprintf(status->f, "\nIrg %p", entry->irg);
 645       }
 646
 647       fprintf(status->f, " %swalked %d over blocks %d was inlined %d got inlined %d:\n",
 648           entry->deleted ? "DELETED " : "",
 649           entry->walked.cnt[0], entry->walked_blocks.cnt[0],
 650           entry->was_inlined.cnt[0],
 651           entry->got_inlined.cnt[0]
 652           );
 653
 654       dump_opcode_hash(entry->opcode_hash);
 655
 656       for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
 657         dump_opt_hash(entry->opt_hash[i], i);
 658       }
 659     }
 660
 661     fclose(status->f);
 662   }
 663   STAT_LEAVE;
 664 }
 665
 666 #else
 667
 668 /* need this for prototypes */
 669 #define FIRM_STATISTICS
 670 #include "firmstat.h"
 671
 672 void stat_init(void) {}
 673
 674 void stat_finish(void) {}
 675
 676 void stat_new_ir_op(const ir_op *op) {}
 677
 678 void stat_free_ir_op(const ir_op *op) {}
 679
 680 void stat_new_node(const ir_node *node) {}
 681
 682 void stat_turn_into_id(const ir_node *node) {}
 683
 684 void stat_new_graph(const ir_graph *irg, entity *ent) {}
 685
 686 void stat_free_graph(const ir_graph *irg) {}
 687
 688 void stat_irg_walk(const ir_graph *irg, void *pre, void *post) {}
 689
 690 void stat_irg_block_walk(const ir_graph *irg, const ir_node *node, void *pre, void *post) {}
 691
 692 void stat_merge_nodes(
 693     ir_node **new_node_array, int new_num_entries,
 694     ir_node **old_node_array, int old_num_entries,
 695     stat_opt_kind opt) {}
 696
 697 void stat_lower(ir_node *node) {}
 698
 699 void stat_inline(const ir_node *call, const ir_graph *irg) {}
 700
 701 void stat_dead_node_elim_start(ir_graph *irg) {}
 702
 703 void stat_dead_node_elim_stop(ir_graph *irg) {}
 704
 705 #endif