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 #ifdef FIRM_STATISTICS
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "firmstat_t.h"
  23 #include "pattern.h"
  24 #include "dags.h"
  25
  26 /**
  27  * names of the optimizations
  28  */
  29 static const char *opt_names[] = {
  30   "straightening optimization",
  31   "if simplification",
  32   "constant evaluation",
  33   "algebraic simplification",
  34   "Phi optmization",
  35   "Write-After-Write optimization",
  36   "Write-After-Read optimization",
  37   "Read-After-Write optimization",
  38   "Read-After-Read optimization",
  39   "Read-a-Const optimization",
  40   "Tuple optimization",
  41   "ID optimization",
  42   "Common subexpression elimination",
  43   "Strength reduction",
  44   "Architecture dependant optimization",
  45   "Reassociation optimization",
  46   "Polymorphic call optimization",
  47   "Lowered",
  48 };
  49
  50 /*
  51  * need this to be static:
  52  * Special pseudo Opcodes that we need to count some interesting cases
  53  */
  54
  55 /**
  56  * The Phi0, a node that is created during SSA construction
  57  */
  58 static ir_op _op_Phi0;
  59
  60 /** The PhiM, just to count memorty Phi's. */
  61 static ir_op _op_PhiM;
  62
  63 /** The Mul by Const node. */
  64 static ir_op _op_MulC;
  65
  66 /** The Div by Const node. */
  67 static ir_op _op_DivC;
  68
  69 /** The Div by Const node. */
  70 static ir_op _op_ModC;
  71
  72 /** The Div by Const node. */
  73 static ir_op _op_DivModC;
  74
  75 /* ---------------------------------------------------------------------------------- */
  76
  77 #define STAT_ENTER              ++status->recursive
  78 #define STAT_LEAVE              --status->recursive
  79 #define STAT_ENTER_SINGLE       do { if (status->recursive > 0) return; ++status->recursive; } while (0)
  80
  81 /**
  82  * global status
  83  */
  84 static stat_info_t _status, *status = &_status;
  85
  86 /**
  87  * compare two elements of the opcode hash
  88  */
  89 static int opcode_cmp(const void *elt, const void *key)
  90 {
  91   const node_entry_t *e1 = elt;
  92   const node_entry_t *e2 = key;
  93
  94   return e1->op->code - e2->op->code;
  95 }
  96
  97 /**
  98  * compare two elements of the graph hash
  99  */
 100 static int graph_cmp(const void *elt, const void *key)
 101 {
 102   const graph_entry_t *e1 = elt;
 103   const graph_entry_t *e2 = key;
 104
 105   return e1->irg != e2->irg;
 106 }
 107
 108 /**
 109  * compare two elements of the optimization hash
 110  */
 111 static int opt_cmp(const void *elt, const void *key)
 112 {
 113   const opt_entry_t *e1 = elt;
 114   const opt_entry_t *e2 = key;
 115
 116   return e1->op->code != e2->op->code;
 117 }
 118
 119 /**
 120  * compare two elements of the block hash
 121  */
 122 static int block_cmp(const void *elt, const void *key)
 123 {
 124   const block_entry_t *e1 = elt;
 125   const block_entry_t *e2 = key;
 126
 127   return e1->block_nr != e2->block_nr;
 128 }
 129
 130 /**
 131  * compare two elements of the ir_op hash
 132  */
 133 static int opcode_cmp_2(const void *elt, const void *key)
 134 {
 135   const ir_op *e1 = elt;
 136   const ir_op *e2 = key;
 137
 138   return e1->code != e2->code;
 139 }
 140
 141 /**
 142  * clears all counter in a node_entry_t
 143  */
 144 static void opcode_clear_entry(node_entry_t *elem)
 145 {
 146   cnt_clr(&elem->cnt_alive);
 147   cnt_clr(&elem->new_node);
 148   cnt_clr(&elem->into_Id);
 149 }
 150
 151 /**
 152  * Returns the associates node_entry_t for an ir_op
 153  */
 154 static node_entry_t *opcode_get_entry(const ir_op *op, pset *set)
 155 {
 156   node_entry_t key;
 157   node_entry_t *elem;
 158
 159   key.op = op;
 160
 161   elem = pset_find(set, &key, op->code);
 162   if (elem)
 163     return elem;
 164
 165   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 166
 167   /* clear counter */
 168   opcode_clear_entry(elem);
 169
 170   elem->op = op;
 171
 172   return pset_insert(set, elem, op->code);
 173 }
 174
 175 /**
 176  * Returns the associates ir_op for an opcode
 177  */
 178 static ir_op *opcode_find_entry(opcode code, pset *set)
 179 {
 180   ir_op key;
 181
 182   key.code = code;
 183   return pset_find(set, &key, code);
 184 }
 185
 186 /**
 187  * calculates a hash value for an irg
 188  * Addresses are typically aligned at 32bit, so we ignore the lowest bits
 189  */
 190 static INLINE unsigned irg_hash(const ir_graph *irg)
 191 {
 192   return (unsigned)irg >> 3;
 193 }
 194
 195 /**
 196  * clears all counter in a graph_entry_t
 197  */
 198 static void graph_clear_entry(graph_entry_t *elem)
 199 {
 200   cnt_clr(&elem->cnt_walked);
 201   cnt_clr(&elem->cnt_walked_blocks);
 202   cnt_clr(&elem->cnt_was_inlined);
 203   cnt_clr(&elem->cnt_got_inlined);
 204   cnt_clr(&elem->cnt_strength_red);
 205   cnt_clr(&elem->cnt_edges);
 206 }
 207
 208 /**
 209  * Returns the acssociates graph_entry_t for an irg
 210  */
 211 static graph_entry_t *graph_get_entry(ir_graph *irg, pset *set)
 212 {
 213   graph_entry_t key;
 214   graph_entry_t *elem;
 215   int i;
 216
 217   key.irg = irg;
 218
 219   elem = pset_find(set, &key, irg_hash(irg));
 220   if (elem)
 221     return elem;
 222
 223   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 224
 225   /* clear counter */
 226   graph_clear_entry(elem);
 227
 228   /* new hash table for opcodes here  */
 229   elem->opcode_hash  = new_pset(opcode_cmp, 5);
 230   elem->block_hash   = new_pset(block_cmp, 5);
 231   elem->irg          = irg;
 232
 233   for (i = 0; i < sizeof(elem->opt_hash)/sizeof(elem->opt_hash[0]); ++i)
 234     elem->opt_hash[i] = new_pset(opt_cmp, 4);
 235
 236   return pset_insert(set, elem, irg_hash(irg));
 237 }
 238
 239 /**
 240  * clears all counter in an opt_entry_t
 241  */
 242 static void opt_clear_entry(opt_entry_t *elem)
 243 {
 244   cnt_clr(&elem->count);
 245 }
 246
 247 /**
 248  * Returns the associates opt_entry_t for an ir_op
 249  */
 250 static opt_entry_t *opt_get_entry(const ir_op *op, pset *set)
 251 {
 252   opt_entry_t key;
 253   opt_entry_t *elem;
 254
 255   key.op = op;
 256
 257   elem = pset_find(set, &key, op->code);
 258   if (elem)
 259     return elem;
 260
 261   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 262
 263   /* clear new counter */
 264   opt_clear_entry(elem);
 265
 266   elem->op = op;
 267
 268   return pset_insert(set, elem, op->code);
 269 }
 270
 271 /**
 272  * clears all counter in a block_entry_t
 273  */
 274 static void block_clear_entry(block_entry_t *elem)
 275 {
 276   cnt_clr(&elem->cnt_nodes);
 277   cnt_clr(&elem->cnt_edges);
 278   cnt_clr(&elem->cnt_in_edges);
 279   cnt_clr(&elem->cnt_out_edges);
 280 }
 281
 282 /**
 283  * Returns the associates block_entry_t for an block
 284  */
 285 static block_entry_t *block_get_entry(long block_nr, pset *set)
 286 {
 287   block_entry_t key;
 288   block_entry_t *elem;
 289
 290   key.block_nr = block_nr;
 291
 292   elem = pset_find(set, &key, block_nr);
 293   if (elem)
 294     return elem;
 295
 296   elem = obstack_alloc(&status->cnts, sizeof(*elem));
 297
 298   /* clear new counter */
 299   block_clear_entry(elem);
 300
 301   elem->block_nr = block_nr;
 302
 303   return pset_insert(set, elem, block_nr);
 304 }
 305
 306
 307 /**
 308  * Returns the ir_op for an IR-node,
 309  * handles special cases and return pseudo op codes
 310  */
 311 static ir_op *stat_get_irn_op(ir_node *node)
 312 {
 313   ir_op *op = get_irn_op(node);
 314
 315   if (op->code == iro_Phi && get_irn_arity(node) == 0) {
 316     /* special case, a Phi0 node, count on extra counter */
 317     op = status->op_Phi0;
 318   }
 319   else if (op->code == iro_Phi && get_irn_mode(node) == mode_M) {
 320     /* special case, a Memory Phi node, count on extra counter */
 321     op = status->op_PhiM;
 322   }
 323   else if (op->code == iro_Mul &&
 324            (get_irn_op(get_Mul_left(node)) == op_Const || get_irn_op(get_Mul_right(node)) == op_Const)) {
 325     /* special case, a Multiply by a const, count on extra counter */
 326     op = status->op_MulC ? status->op_MulC : op_Mul;
 327   }
 328   else if (op->code == iro_Div && get_irn_op(get_Div_right(node)) == op_Const) {
 329     /* special case, a division by a const, count on extra counter */
 330     op = status->op_DivC ? status->op_DivC : op_Div;
 331   }
 332   else if (op->code == iro_Mod && get_irn_op(get_Mod_right(node)) == op_Const) {
 333     /* special case, a module by a const, count on extra counter */
 334     op = status->op_ModC ? status->op_ModC : op_Mod;
 335   }
 336   else if (op->code == iro_DivMod && get_irn_op(get_DivMod_right(node)) == op_Const) {
 337     /* special case, a division/modulo by a const, count on extra counter */
 338     op = status->op_DivModC ? status->op_DivModC : op_DivMod;
 339   }
 340
 341   return op;
 342 }
 343
 344 /**
 345  * update the block counter
 346  */
 347 static void count_block_info(ir_node *node, graph_entry_t *graph)
 348 {
 349   ir_op *op = get_irn_op(node);
 350   ir_node *block;
 351   block_entry_t *b_entry;
 352   int i, arity;
 353
 354   /* check for block */
 355   if (op == op_Block) {
 356     arity = get_irn_arity(node);
 357     b_entry = block_get_entry(get_irn_node_nr(node), graph->block_hash);
 358
 359     /* count all incoming edges */
 360     for (i = 0; i < arity; ++i) {
 361       ir_node *pred = get_irn_n(node, i);
 362       ir_node *other_block = get_nodes_block(pred);
 363       block_entry_t *b_entry_other = block_get_entry(get_irn_node_nr(other_block), graph->block_hash);
 364
 365       cnt_inc(&b_entry->cnt_in_edges);  /* an edge coming from another block */
 366       cnt_inc(&b_entry_other->cnt_out_edges);
 367     }
 368     return;
 369   }
 370   else if (op == op_Call) {
 371     // return;
 372   }
 373
 374   block   = get_nodes_block(node);
 375   b_entry = block_get_entry(get_irn_node_nr(block), graph->block_hash);
 376
 377   /* we have a new nodes */
 378   cnt_inc(&b_entry->cnt_nodes);
 379
 380   arity = get_irn_arity(node);
 381
 382   for (i = 0; i < arity; ++i) {
 383     ir_node *pred = get_irn_n(node, i);
 384     ir_node *other_block;
 385
 386     if (get_irn_op(pred) == op_Block)
 387       continue;
 388
 389     other_block = get_nodes_block(pred);
 390
 391     if (other_block == block)
 392       cnt_inc(&b_entry->cnt_edges);     /* a in block edge */
 393     else {
 394       block_entry_t *b_entry_other = block_get_entry(get_irn_node_nr(other_block), graph->block_hash);
 395
 396       cnt_inc(&b_entry->cnt_in_edges);  /* an edge coming from another block */
 397       cnt_inc(&b_entry_other->cnt_out_edges);
 398     }
 399   }
 400 }
 401
 402 /**
 403  * update info on calls
 404  */
 405 static void count_call(ir_node *call, graph_entry_t *graph)
 406 {
 407   ir_node *ptr = get_Call_ptr(call);
 408   entity *ent = NULL;
 409
 410   /* found a call, is not a leaf function */
 411   graph->is_leaf = 0;
 412
 413   if (get_irn_op(ptr) == op_SymConst) {
 414     if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 415       /* ok, we seems to know the entity */
 416       ent = get_SymConst_entity(ptr);
 417
 418       if (get_entity_irg(ent) == graph->irg)
 419         graph->is_recursive = 1;
 420     }
 421   }
 422
 423   /* check, if it's a chain-call: Then, the call-block
 424    * must dominate the end block. */
 425   {
 426     ir_node *curr = get_irg_end_block(graph->irg);
 427     ir_node *block  = get_nodes_block(call);
 428     int depth = get_Block_dom_depth(block);
 429
 430     for (; curr != block && get_Block_dom_depth(curr) > depth;) {
 431       curr = get_Block_idom(curr);
 432
 433       if (! curr || is_no_Block(curr))
 434         break;
 435     }
 436
 437     if (curr != block)
 438       graph->is_chain_call = 0;
 439   }
 440 }
 441
 442 /**
 443  * walker for reachable nodes count
 444  */
 445 static void count_nodes(ir_node *node, void *env)
 446 {
 447   graph_entry_t *graph = env;
 448   node_entry_t *entry;
 449
 450   ir_op *op = stat_get_irn_op(node);
 451   int arity = get_irn_arity(node);
 452
 453   entry = opcode_get_entry(op, graph->opcode_hash);
 454
 455   cnt_inc(&entry->cnt_alive);
 456   cnt_add_i(&graph->cnt_edges, arity);
 457
 458   /* count block edges */
 459   count_block_info(node, graph);
 460
 461   /* check for leaf functions */
 462   if (get_irn_op(node) == op_Call)
 463     count_call(node, graph);
 464 }
 465
 466 /**
 467  * count all alive nodes and edges in a graph
 468  */
 469 static void count_nodes_in_graph(graph_entry_t *global, graph_entry_t *graph)
 470 {
 471   node_entry_t *entry;
 472
 473   /* clear first the alive counter in the graph */
 474   for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
 475     cnt_clr(&entry->cnt_alive);
 476   }
 477
 478   /* set pessimistic values */
 479   graph->is_leaf       = 1;
 480   graph->is_recursive  = 0;
 481   graph->is_chain_call = 1;
 482
 483   /* we need dominator info */
 484   if (graph->irg != get_const_code_irg())
 485     if (get_irg_dom_state(graph->irg) != dom_consistent)
 486       compute_doms(graph->irg);
 487
 488   /* count the nodes in the graph */
 489   irg_walk_graph(graph->irg, count_nodes, NULL, graph);
 490
 491 #if 0
 492   entry = opcode_get_entry(op_Call, graph->opcode_hash);
 493
 494   /* check if we have more than 1 call */
 495   if (cnt_gt(entry->cnt_alive, 1))
 496     graph->is_chain_call = 0;
 497 #endif
 498
 499   /* recursive functions are never chain calls, leafs don't have calls */
 500   if (graph->is_recursive || graph->is_leaf)
 501     graph->is_chain_call = 0;
 502
 503   /* assume we walk every graph only ONCE, we could sum here the global count */
 504   for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
 505     node_entry_t *g_entry = opcode_get_entry(entry->op, global->opcode_hash);
 506
 507     /* update the node counter */
 508     cnt_add(&g_entry->cnt_alive, &entry->cnt_alive);
 509   }
 510
 511   /* update the edge counter */
 512   cnt_add(&global->cnt_edges, &graph->cnt_edges);
 513 }
 514
 515 /**
 516  * register a dumper
 517  */
 518 static void stat_register_dumper(dumper_t *dumper)
 519 {
 520   dumper->next   = status->dumper;
 521   status->dumper = dumper;
 522 }
 523
 524 /**
 525  * dumps an irg
 526  */
 527 static void dump_graph(graph_entry_t *entry)
 528 {
 529   dumper_t *dumper;
 530
 531   for (dumper = status->dumper; dumper; dumper = dumper->next) {
 532     if (dumper->dump_graph)
 533       dumper->dump_graph(dumper, entry);
 534   }
 535 }
 536
 537 /**
 538  * initialise the dumper
 539  */
 540 static void dump_init(const char *name)
 541 {
 542   dumper_t *dumper;
 543
 544   for (dumper = status->dumper; dumper; dumper = dumper->next) {
 545     if (dumper->init)
 546       dumper->init(dumper, name);
 547   }
 548 }
 549
 550 /**
 551  * finish the dumper
 552  */
 553 static void dump_finish(void)
 554 {
 555   dumper_t *dumper;
 556
 557   for (dumper = status->dumper; dumper; dumper = dumper->next) {
 558     if (dumper->finish)
 559       dumper->finish(dumper);
 560   }
 561 }
 562
 563 /* ---------------------------------------------------------------------- */
 564
 565 /**
 566  * dumps a opcode hash into human readable form
 567  */
 568 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
 569 {
 570   node_entry_t *entry;
 571   counter_t f_alive;
 572   counter_t f_new_node;
 573   counter_t f_Id;
 574
 575   cnt_clr(&f_alive);
 576   cnt_clr(&f_new_node);
 577   cnt_clr(&f_Id);
 578
 579   fprintf(dmp->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
 580   for (entry = pset_first(set); entry; entry = pset_next(set)) {
 581     fprintf(dmp->f, "%-16s %8d %8d %8d\n",
 582       get_id_str(entry->op->name), entry->cnt_alive.cnt[0], entry->new_node.cnt[0], entry->into_Id.cnt[0]);
 583
 584     cnt_add(&f_alive,    &entry->cnt_alive);
 585     cnt_add(&f_new_node, &entry->new_node);
 586     cnt_add(&f_Id,       &entry->into_Id);
 587   }
 588   fprintf(dmp->f, "-------------------------------------------\n");
 589   fprintf(dmp->f, "%-16s %8d %8d %8d\n", "Sum",
 590      f_alive.cnt[0],
 591      f_new_node.cnt[0],
 592      f_Id.cnt[0]);
 593 }
 594
 595 /**
 596  * dumps a optimization hash into human readable form
 597  */
 598 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
 599 {
 600   opt_entry_t *entry = pset_first(set);
 601
 602   if (entry) {
 603     fprintf(dmp->f, "\n%s:\n", opt_names[index]);
 604     fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
 605
 606     for (; entry; entry = pset_next(set)) {
 607       fprintf(dmp->f, "%-16s %8d\n",
 608         get_id_str(entry->op->name), entry->count.cnt[0]);
 609     }
 610   }
 611 }
 612
 613 /**
 614  * dumps the endges count
 615  */
 616 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
 617 {
 618   fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt->cnt[0]);
 619 }
 620
 621 /**
 622  * dumps the IRG
 623  */
 624 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
 625 {
 626   int dump_opts = 1;
 627   block_entry_t *b_entry;
 628
 629   if (entry->irg) {
 630     ir_graph *const_irg = get_const_code_irg();
 631
 632     if (entry->irg == const_irg) {
 633       fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
 634     }
 635     else {
 636       if (entry->ent)
 637         fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_name(entry->ent), (void *)entry->irg);
 638       else
 639         fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
 640     }
 641
 642     fprintf(dmp->f, " %swalked %d over blocks %d:\n"
 643                     " was inlined:   %d\n"
 644                     " got inlined:   %d\n"
 645                     " strength red:  %d\n"
 646                     " leaf function: %s\n"
 647                     " recursive    : %s\n"
 648                     " chain call   : %s\n",
 649         entry->is_deleted ? "DELETED " : "",
 650         entry->cnt_walked.cnt[0], entry->cnt_walked_blocks.cnt[0],
 651         entry->cnt_was_inlined.cnt[0],
 652         entry->cnt_got_inlined.cnt[0],
 653         entry->cnt_strength_red.cnt[0],
 654         entry->is_leaf ? "YES" : "NO",
 655         entry->is_recursive ? "YES" : "NO",
 656         entry->is_chain_call ? "YES" : "NO"
 657     );
 658   }
 659   else {
 660     fprintf(dmp->f, "\nGlobals counts:\n");
 661     fprintf(dmp->f, "--------------\n");
 662     dump_opts = 0;
 663   }
 664
 665   simple_dump_opcode_hash(dmp, entry->opcode_hash);
 666   simple_dump_edges(dmp, &entry->cnt_edges);
 667
 668   /* effects of optimizations */
 669   if (dump_opts) {
 670     int i;
 671
 672     for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
 673       simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
 674     }
 675
 676     /* dump block info */
 677     fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "quot");
 678     for (b_entry = pset_first(entry->block_hash);
 679          b_entry;
 680          b_entry = pset_next(entry->block_hash)) {
 681       fprintf(dmp->f, "BLK %12ld %12u %12u %12u %12u %4.8f\n",
 682           b_entry->block_nr,
 683           b_entry->cnt_nodes.cnt[0],
 684           b_entry->cnt_edges.cnt[0],
 685           b_entry->cnt_in_edges.cnt[0],
 686           b_entry->cnt_out_edges.cnt[0],
 687           (double)b_entry->cnt_edges.cnt[0] / (double)b_entry->cnt_nodes.cnt[0]
 688       );
 689     }
 690   }
 691 }
 692
 693 /**
 694  * initialise the simple dumper
 695  */
 696 static void simple_init(dumper_t *dmp, const char *name)
 697 {
 698   char fname[2048];
 699
 700   snprintf(fname, sizeof(fname), "%s.txt", name);
 701   dmp->f = fopen(fname, "w");
 702 }
 703
 704 /**
 705  * finishes the simple dumper
 706  */
 707 static void simple_finish(dumper_t *dmp)
 708 {
 709   fclose(dmp->f);
 710   dmp->f = NULL;
 711 }
 712
 713 /**
 714  * the simple human readable dumper
 715  */
 716 static dumper_t simple_dumper = {
 717   simple_dump_graph,
 718   simple_init,
 719   simple_finish,
 720   NULL,
 721   NULL,
 722 };
 723
 724 /* ---------------------------------------------------------------------- */
 725
 726 /**
 727  * count the nodes as needed:
 728  *
 729  * 1 normal (data) Phi's
 730  * 2 memory Phi's
 731  * 3 Proj
 732  * 0 all other nodes
 733  */
 734 static void csv_count_nodes(graph_entry_t *graph, counter_t cnt[])
 735 {
 736   node_entry_t *entry;
 737   int i;
 738
 739   for (i = 0; i < 4; ++i)
 740     cnt_clr(&cnt[i]);
 741
 742   for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
 743     if (entry->op == op_Phi) {
 744       /* normal Phi */
 745       cnt_add(&cnt[1], &entry->cnt_alive);
 746     }
 747     else if (entry->op == status->op_PhiM) {
 748       /* memory Phi */
 749       cnt_add(&cnt[2], &entry->cnt_alive);
 750     }
 751     else if (entry->op == op_Proj) {
 752       /* Proj */
 753       cnt_add(&cnt[3], &entry->cnt_alive);
 754     }
 755     else {
 756       /* all other nodes */
 757       cnt_add(&cnt[0], &entry->cnt_alive);
 758     }
 759   }
 760 }
 761
 762 /**
 763  * dumps the IRG
 764  */
 765 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
 766 {
 767   const char *name;
 768
 769   counter_t cnt[4];
 770
 771   if (entry->irg && !entry->is_deleted) {
 772     ir_graph *const_irg = get_const_code_irg();
 773
 774     if (entry->irg == const_irg) {
 775       name = "<Const code Irg>";
 776       return;
 777     }
 778     else {
 779       if (entry->ent)
 780         name = get_entity_name(entry->ent);
 781       else
 782         name = "<UNKNOWN IRG>";
 783     }
 784
 785     csv_count_nodes(entry, cnt);
 786
 787     fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
 788         name,
 789         (void *)entry->irg,
 790         cnt[0].cnt[0],
 791         cnt[1].cnt[0],
 792         cnt[2].cnt[0],
 793         cnt[3].cnt[0]
 794     );
 795   }
 796 }
 797
 798 /**
 799  * initialise the simple dumper
 800  */
 801 static void csv_init(dumper_t *dmp, const char *name)
 802 {
 803   char fname[2048];
 804
 805   snprintf(fname, sizeof(fname), "%s.csv", name);
 806   dmp->f = fopen(fname, "a");
 807 }
 808
 809 /**
 810  * finishes the simple dumper
 811  */
 812 static void csv_finish(dumper_t *dmp)
 813 {
 814   fclose(dmp->f);
 815   dmp->f = NULL;
 816 }
 817
 818 /**
 819  * the simple human readable dumper
 820  */
 821 static dumper_t csv_dumper = {
 822   csv_dump_graph,
 823   csv_init,
 824   csv_finish,
 825   NULL,
 826   NULL,
 827 };
 828
 829
 830 /* ---------------------------------------------------------------------- */
 831
 832 /*
 833  * helper: get an ir_op from an opcode
 834  */
 835 ir_op *stat_get_op_from_opcode(opcode code)
 836 {
 837   return opcode_find_entry(code, status->ir_op_hash);
 838 }
 839
 840 /* initialize the statistics module. */
 841 void init_stat(unsigned enable_options)
 842 {
 843 #define X(a)  a, sizeof(a)-1
 844
 845   int pseudo_id = 0;
 846
 847   /* enable statistics */
 848   status->enable = enable_options & FIRMSTAT_ENABLED;
 849
 850   if (! status->enable)
 851    return;
 852
 853   obstack_init(&status->cnts);
 854
 855   /* build the pseudo-ops */
 856   _op_Phi0.code = --pseudo_id;
 857   _op_Phi0.name = new_id_from_chars(X("Phi0"));
 858
 859   _op_PhiM.code = --pseudo_id;
 860   _op_PhiM.name = new_id_from_chars(X("PhiM"));
 861
 862   _op_MulC.code = --pseudo_id;
 863   _op_MulC.name = new_id_from_chars(X("MulC"));
 864
 865   _op_DivC.code = --pseudo_id;
 866   _op_DivC.name = new_id_from_chars(X("DivC"));
 867
 868   _op_ModC.code = --pseudo_id;
 869   _op_ModC.name = new_id_from_chars(X("ModC"));
 870
 871   _op_DivModC.code = --pseudo_id;
 872   _op_DivModC.name = new_id_from_chars(X("DivModC"));
 873
 874   /* create the hash-tables */
 875   status->irg_hash   = new_pset(graph_cmp, 8);
 876   status->ir_op_hash = new_pset(opcode_cmp_2, 1);
 877
 878   status->op_Phi0    = &_op_Phi0;
 879   status->op_PhiM    = &_op_PhiM;
 880
 881   if (enable_options & FIRMSTAT_COUNT_STRONG_OP) {
 882     status->op_MulC    = &_op_MulC;
 883     status->op_DivC    = &_op_DivC;
 884     status->op_ModC    = &_op_ModC;
 885     status->op_DivModC = &_op_DivModC;
 886   }
 887   else {
 888     status->op_MulC    = NULL;
 889     status->op_DivC    = NULL;
 890     status->op_ModC    = NULL;
 891     status->op_DivModC = NULL;
 892   }
 893
 894   stat_register_dumper(&simple_dumper);
 895   stat_register_dumper(&csv_dumper);
 896
 897   /* initialize the pattern hash */
 898   stat_init_pattern_history(enable_options & FIRMSTAT_PATTERN_ENABLED);
 899 #undef X
 900 }
 901
 902 /* A new IR op is registered. */
 903 void stat_new_ir_op(const ir_op *op)
 904 {
 905   if (! status->enable)
 906     return;
 907
 908   STAT_ENTER;
 909   {
 910     graph_entry_t *graph = graph_get_entry(NULL, status->irg_hash);
 911
 912     /* execute for side effect :-) */
 913     opcode_get_entry(op, graph->opcode_hash);
 914
 915     pset_insert(status->ir_op_hash, op, op->code);
 916   }
 917   STAT_LEAVE;
 918 }
 919
 920 /* An IR op is freed. */
 921 void stat_free_ir_op(const ir_op *op)
 922 {
 923   if (! status->enable)
 924     return;
 925
 926   STAT_ENTER;
 927   {
 928   }
 929   STAT_LEAVE;
 930 }
 931
 932 /* A new node is created. */
 933 void stat_new_node(ir_node *node)
 934 {
 935   if (! status->enable)
 936     return;
 937
 938   /* do NOT count during dead node elimination */
 939   if (status->in_dead_node_elim > 0)
 940     return;
 941
 942   STAT_ENTER;
 943   {
 944     node_entry_t *entry;
 945     graph_entry_t *graph;
 946     ir_op *op = stat_get_irn_op(node);
 947
 948     /* increase global value */
 949     graph = graph_get_entry(NULL, status->irg_hash);
 950     entry = opcode_get_entry(op, graph->opcode_hash);
 951     cnt_inc(&entry->new_node);
 952
 953     /* increase local value */
 954     graph = graph_get_entry(current_ir_graph, status->irg_hash);
 955     entry = opcode_get_entry(op, graph->opcode_hash);
 956     cnt_inc(&entry->new_node);
 957   }
 958   STAT_LEAVE;
 959 }
 960
 961 /* A node is changed into a Id node */
 962 void stat_turn_into_id(ir_node *node)
 963 {
 964   if (! status->enable)
 965     return;
 966
 967   STAT_ENTER;
 968   {
 969     node_entry_t *entry;
 970     graph_entry_t *graph;
 971     ir_op *op = stat_get_irn_op(node);
 972
 973     /* increase global value */
 974     graph = graph_get_entry(NULL, status->irg_hash);
 975     entry = opcode_get_entry(op, graph->opcode_hash);
 976     cnt_inc(&entry->into_Id);
 977
 978     /* increase local value */
 979     graph = graph_get_entry(current_ir_graph, status->irg_hash);
 980     entry = opcode_get_entry(op, graph->opcode_hash);
 981     cnt_inc(&entry->into_Id);
 982   }
 983   STAT_LEAVE;
 984 }
 985
 986 /* A new graph was created */
 987 void stat_new_graph(ir_graph *irg, entity *ent)
 988 {
 989   if (! status->enable)
 990     return;
 991
 992   STAT_ENTER;
 993   {
 994     /* execute for side effect :-) */
 995     graph_entry_t * graph = graph_get_entry(irg, status->irg_hash);
 996
 997     graph->ent           = ent;
 998     graph->is_deleted    = 0;
 999     graph->is_leaf       = 0;
1000     graph->is_recursive  = 0;
1001     graph->is_chain_call = 0;
1002   }
1003   STAT_LEAVE;
1004 }
1005
1006 /*
1007  * A graph was deleted
1008  */
1009 void stat_free_graph(ir_graph *irg)
1010 {
1011   if (! status->enable)
1012     return;
1013
1014   STAT_ENTER;
1015   {
1016     graph_entry_t *graph  = graph_get_entry(irg, status->irg_hash);
1017     graph_entry_t *global = graph_get_entry(NULL, status->irg_hash);
1018
1019     graph->is_deleted = 1;
1020
1021     /* count the nodes of the graph yet, it will be destroyed later */
1022     count_nodes_in_graph(global, graph);
1023
1024     /* count the DAG's */
1025 //    count_dags_in_graph(global, graph);
1026
1027     /* calculate the pattern */
1028     stat_calc_pattern_history(irg);
1029   }
1030   STAT_LEAVE;
1031 }
1032
1033 /*
1034  * A walk over a graph is initiated. Do not count walks from statistic code.
1035  */
1036 void stat_irg_walk(ir_graph *irg, void *pre, void *post)
1037 {
1038   if (! status->enable)
1039     return;
1040
1041   STAT_ENTER_SINGLE;
1042   {
1043     graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
1044
1045     cnt_inc(&graph->cnt_walked);
1046   }
1047   STAT_LEAVE;
1048 }
1049
1050 /*
1051  * A walk over a graph in block-wise order is initiated. Do not count walks from statistic code.
1052  */
1053 void stat_irg_walk_blkwise(ir_graph *irg, void *pre, void *post)
1054 {
1055   /* for now, do NOT differentiate between blockwise and normal */
1056   stat_irg_walk(irg, pre, post);
1057 }
1058
1059 /*
1060  * A walk over the graph's blocks is initiated. Do not count walks from statistic code.
1061  */
1062 void stat_irg_block_walk(ir_graph *irg, const ir_node *node, void *pre, void *post)
1063 {
1064   if (! status->enable)
1065     return;
1066
1067   STAT_ENTER_SINGLE;
1068   {
1069     graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
1070
1071     cnt_inc(&graph->cnt_walked_blocks);
1072   }
1073   STAT_LEAVE;
1074 }
1075
1076 /**
1077  * called for every node that is removed due to an optimization
1078  */
1079 static void removed_due_opt(ir_node *n, pset *set)
1080 {
1081   ir_op *op          = stat_get_irn_op(n);
1082   opt_entry_t *entry = opt_get_entry(op, set);
1083
1084   /* increase global value */
1085   cnt_inc(&entry->count);
1086 }
1087
1088 /*
1089  * Some nodes were optimized into some others due to an optimization
1090  */
1091 void stat_merge_nodes(
1092     ir_node **new_node_array, int new_num_entries,
1093     ir_node **old_node_array, int old_num_entries,
1094     stat_opt_kind opt)
1095 {
1096   if (! status->enable)
1097     return;
1098
1099   STAT_ENTER;
1100   {
1101     int i, j;
1102     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1103
1104     if (status->reassoc_run)
1105       opt = STAT_OPT_REASSOC;
1106
1107     for (i = 0; i < old_num_entries; ++i) {
1108       for (j = 0; j < new_num_entries; ++j)
1109         if (old_node_array[i] == new_node_array[j])
1110           break;
1111
1112       /* nodes might be in new and old, these are NOT removed */
1113       if (j >= new_num_entries) {
1114         removed_due_opt(old_node_array[i], graph->opt_hash[opt]);
1115       }
1116     }
1117   }
1118   STAT_LEAVE;
1119 }
1120
1121 /*
1122  * reassociation started/stopped.
1123  */
1124 void stat_reassociate(int flag)
1125 {
1126   if (! status->enable)
1127     return;
1128
1129   STAT_ENTER;
1130   {
1131     status->reassoc_run = flag;
1132   }
1133   STAT_LEAVE;
1134 }
1135
1136 /*
1137  * A node was lowered into other nodes
1138  */
1139 void stat_lower(ir_node *node)
1140 {
1141   if (! status->enable)
1142     return;
1143
1144   STAT_ENTER;
1145   {
1146     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1147
1148     removed_due_opt(node, graph->opt_hash[STAT_LOWERED]);
1149   }
1150   STAT_LEAVE;
1151 }
1152
1153 /*
1154  * A graph was inlined
1155  */
1156 void stat_inline(ir_node *call, ir_graph *called_irg)
1157 {
1158   if (! status->enable)
1159     return;
1160
1161   STAT_ENTER;
1162   {
1163     ir_graph *irg = get_irn_irg(call);
1164     graph_entry_t *i_graph = graph_get_entry(called_irg, status->irg_hash);
1165     graph_entry_t *graph   = graph_get_entry(irg, status->irg_hash);
1166
1167     cnt_inc(&graph->cnt_got_inlined);
1168     cnt_inc(&i_graph->cnt_was_inlined);
1169   }
1170   STAT_LEAVE;
1171 }
1172
1173 /*
1174  * A graph with tail-recursions was optimized.
1175  */
1176 void stat_tail_rec(ir_graph *irg)
1177 {
1178   if (! status->enable)
1179     return;
1180
1181   STAT_ENTER;
1182   {
1183   }
1184   STAT_LEAVE;
1185 }
1186
1187 /*
1188  * Strength reduction was performed on an iteration variable.
1189  */
1190 void stat_strength_red(ir_graph *irg, ir_node *strong, ir_node *cmp)
1191 {
1192   if (! status->enable)
1193     return;
1194
1195   STAT_ENTER;
1196   {
1197     graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
1198     cnt_inc(&graph->cnt_strength_red);
1199
1200     removed_due_opt(strong, graph->opt_hash[STAT_OPT_STRENGTH_RED]);
1201   }
1202   STAT_LEAVE;
1203 }
1204
1205 /*
1206  * Start the dead node elimination.
1207  */
1208 void stat_dead_node_elim_start(ir_graph *irg)
1209 {
1210   if (! status->enable)
1211     return;
1212
1213   ++status->in_dead_node_elim;
1214 }
1215
1216 /*
1217  * Stops the dead node elimination.
1218  */
1219 void stat_dead_node_elim_stop(ir_graph *irg)
1220 {
1221   if (! status->enable)
1222     return;
1223
1224   --status->in_dead_node_elim;
1225 }
1226
1227 /*
1228  * A multiply was replaced by a series of Shifts/Adds/Subs
1229  */
1230 void stat_arch_dep_replace_mul_with_shifts(ir_node *mul)
1231 {
1232   if (! status->enable)
1233     return;
1234
1235   STAT_ENTER;
1236   {
1237     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1238     removed_due_opt(mul, graph->opt_hash[STAT_OPT_ARCH_DEP]);
1239   }
1240   STAT_LEAVE;
1241 }
1242
1243 /**
1244  * A division was replaced by a series of Shifts/Muls
1245  */
1246 void stat_arch_dep_replace_div_by_const(ir_node *div)
1247 {
1248   if (! status->enable)
1249     return;
1250
1251   STAT_ENTER;
1252   {
1253     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1254     removed_due_opt(div, graph->opt_hash[STAT_OPT_ARCH_DEP]);
1255   }
1256   STAT_LEAVE;
1257 }
1258
1259 /**
1260  * A modulo was replaced by a series of Shifts/Muls
1261  */
1262 void stat_arch_dep_replace_mod_by_const(ir_node *mod)
1263 {
1264   if (! status->enable)
1265     return;
1266
1267   STAT_ENTER;
1268   {
1269     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1270     removed_due_opt(mod, graph->opt_hash[STAT_OPT_ARCH_DEP]);
1271   }
1272   STAT_LEAVE;
1273 }
1274
1275 /**
1276  * A DivMod was replaced by a series of Shifts/Muls
1277  */
1278 void stat_arch_dep_replace_DivMod_by_const(ir_node *divmod)
1279 {
1280   if (! status->enable)
1281     return;
1282
1283   STAT_ENTER;
1284   {
1285     graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
1286     removed_due_opt(divmod, graph->opt_hash[STAT_OPT_ARCH_DEP]);
1287   }
1288   STAT_LEAVE;
1289 }
1290
1291 /* Finish the statistics */
1292 void stat_finish(const char *name)
1293 {
1294   if (! status->enable)
1295     return;
1296
1297   STAT_ENTER;
1298   {
1299     graph_entry_t *entry;
1300     graph_entry_t *global = graph_get_entry(NULL, status->irg_hash);
1301
1302     dump_init(name);
1303
1304     /* dump per graph */
1305     for (entry = pset_first(status->irg_hash); entry; entry = pset_next(status->irg_hash)) {
1306
1307       if (entry->irg == NULL) {
1308         /* special entry for the global count */
1309         continue;
1310       }
1311
1312       if (! entry->is_deleted) {
1313         /* the graph is still alive, count the nodes on it */
1314         count_nodes_in_graph(global, entry);
1315
1316         /* count the DAG's */
1317 //        count_dags_in_graph(global, entry);
1318
1319         /* calculate the pattern */
1320         stat_calc_pattern_history(entry->irg);
1321       }
1322
1323       dump_graph(entry);
1324
1325       /* clear the counter here:
1326        * we need only the edge counter to be cleared, all others are cumulative
1327        */
1328       cnt_clr(&entry->cnt_edges);
1329     }
1330
1331     /* dump global */
1332     dump_graph(global);
1333     dump_finish();
1334
1335     stat_finish_pattern_history();
1336
1337     /* clear the global counter here */
1338     {
1339       node_entry_t *entry;
1340
1341       for (entry = pset_first(global->opcode_hash); entry; entry = pset_next(global->opcode_hash)) {
1342         opcode_clear_entry(entry);
1343       }
1344       graph_clear_entry(global);
1345     }
1346
1347     /* finished */
1348 //    status->enable = 0;
1349   }
1350   STAT_LEAVE;
1351 }
1352
1353 #else
1354
1355 /* need this for prototypes */
1356 #define FIRM_STATISTICS
1357 #include "firmstat.h"
1358
1359 void init_stat(unsigned enable_options) {}
1360
1361 void stat_finish(const char *name) {}
1362
1363 void stat_new_ir_op(const ir_op *op) {}
1364
1365 void stat_free_ir_op(const ir_op *op) {}
1366
1367 void stat_new_node(ir_node *node) {}
1368
1369 void stat_turn_into_id(ir_node *node) {}
1370
1371 void stat_new_graph(ir_graph *irg, entity *ent) {}
1372
1373 void stat_free_graph(ir_graph *irg) {}
1374
1375 void stat_irg_walk(ir_graph *irg, void *pre, void *post) {}
1376
1377 void stat_irg_block_walk(ir_graph *irg, const ir_node *node, void *pre, void *post) {}
1378
1379 void stat_merge_nodes(
1380     ir_node **new_node_array, int new_num_entries,
1381     ir_node **old_node_array, int old_num_entries,
1382     stat_opt_kind opt) {}
1383
1384 void stat_reassociate(int start) {}
1385
1386 void stat_lower(ir_node *node) {}
1387
1388 void stat_inline(ir_node *call, ir_graph *irg) {}
1389
1390 void stat_tail_rec(ir_graph *irg) {}
1391
1392 void stat_strength_red(ir_graph *irg, ir_node *strong, ir_node *cmp) {}
1393
1394 void stat_dead_node_elim_start(ir_graph *irg) {}
1395
1396 void stat_dead_node_elim_stop(ir_graph *irg) {}
1397
1398 void stat_arch_dep_replace_mul_with_shifts(ir_node *mul) {}
1399
1400 void stat_arch_dep_replace_div_by_const(ir_node *div) {}
1401
1402 void stat_arch_dep_replace_mod_by_const(ir_node *mod) {}
1403
1404 void stat_arch_dep_replace_DivMod_by_const(ir_node *divmod) {}
1405
1406 #endif