3 * File name: ir/ir/firmstat.c
4 * Purpose: Statistics for Firm.
8 * Copyright: (c) 2004 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
21 #ifdef FIRM_STATISTICS
25 # include "irnode_t.h"
26 # include "irgraph_t.h"
34 * just be make some things clear :-), the
37 #define HASH_MAP(type) pset_##type
39 typedef pset pset_node_entry_t;
40 typedef pset pset_graph_entry_t;
41 typedef pset pset_opt_entry_t;
44 * An entry for ir_nodes
46 typedef struct _node_entry_t {
47 counter_t cnt_alive; /**< amount of nodes in this entry */
48 counter_t new_node; /**< amount of new nodes for this entry */
49 counter_t into_Id; /**< amount of nodes that turned into Id's for this entry */
50 const ir_op *op; /**< the op for this entry */
54 * An entry for ir_graphs
56 typedef struct _graph_entry_t {
57 HASH_MAP(node_entry_t) *opcode_hash; /**< hash map containing the opcode counter */
58 counter_t cnt_walked; /**< walker walked over the graph */
59 counter_t cnt_walked_blocks; /**< walker walked over the graph blocks */
60 counter_t cnt_was_inlined; /**< number of times other graph were inlined */
61 counter_t cnt_got_inlined; /**< number of times this graph was inlined */
62 counter_t cnt_edges; /**< number of DF edges in this graph */
63 HASH_MAP(opt_entry_t) *opt_hash[STAT_OPT_MAX]; /**< hash maps containing opcode counter for optimizations */
64 ir_graph *irg; /**< the graph of this object */
65 entity *ent; /**< the entity of this graph if one exists */
66 int deleted; /**< set if this irg was deleted */
70 * An entry for optimized ir_nodes
72 typedef struct _opt_entry_t {
73 counter_t count; /**< optimization counter */
74 const ir_op *op; /**< the op for this entry */
78 typedef struct _dumper_t dumper_t;
81 * handler for dumping an IRG
83 * @param dmp the dumper
84 * @param entry the IR-graph hash map entry
86 typedef void (*dump_graph_FUNC)(dumper_t *dmp, graph_entry_t *entry);
89 * handler for dumper init
91 * @param dmp the dumper
92 * @param name name of the file to dump to
94 typedef void (*dump_init_FUNC)(dumper_t *dmp, const char *name);
97 * handler for dumper finish
99 * @param dmp the dumper
101 typedef void (*dump_finish_FUNC)(dumper_t *dmp);
105 * a dumper description
108 dump_graph_FUNC dump_graph; /**< handler for dumping an irg */
109 dump_init_FUNC init; /**< handler for init */
110 dump_finish_FUNC finish; /**< handler for finish */
111 FILE *f; /**< the file to dump to */
112 dumper_t *next; /**< link to the next dumper */
118 typedef struct _statistic_info_t {
119 struct obstack cnts; /**< obstack containing the counters */
120 HASH_MAP(graph_entry_t) *irg_hash; /**< hash map containing the counter for irgs */
121 int recursive; /**< flag for detecting recursive hook calls */
122 int in_dead_node_elim; /**< set, if dead node elimination runs */
123 ir_op *op_Phi0; /**< needed pseudo op */
124 ir_op *op_PhiM; /**< needed pseudo op */
125 dumper_t *dumper; /**< list of dumper */
126 int enable; /**< if set, statistic is enabled */
130 * names of the optimizations
132 static const char *opt_names[] = {
133 "straightening optimization",
135 "algebraic simplification",
137 "Write-After-Write optimization",
138 "Write-After-Read optimization",
139 "Tuple optimization",
141 "Constant evaluation",
146 * need this to be static
148 static ir_op _op_Phi0, _op_PhiM;
150 /* ---------------------------------------------------------------------------------- */
152 #define STAT_ENTER ++status->recursive
153 #define STAT_LEAVE --status->recursive
154 #define STAT_ENTER_SINGLE do { if (status->recursive > 0) return; ++status->recursive; } while (0)
159 static stat_info_t _status, *status = &_status;
162 * compare two elements of the opcode hash
164 static int opcode_cmp(const void *elt, const void *key)
166 const node_entry_t *e1 = elt;
167 const node_entry_t *e2 = key;
169 return e1->op->code - e2->op->code;
173 * compare two elements of the graph hash
175 static int graph_cmp(const void *elt, const void *key)
177 const graph_entry_t *e1 = elt;
178 const graph_entry_t *e2 = key;
180 return e1->irg != e2->irg;
184 * compare two elements of the optimization hash
186 static int opt_cmp(const void *elt, const void *key)
188 const opt_entry_t *e1 = elt;
189 const opt_entry_t *e2 = key;
191 return e1->op->code != e2->op->code;
195 * Returns the associates node_entry_t for an ir_op
197 static node_entry_t *opcode_get_entry(const ir_op *op, pset *set)
204 elem = pset_find(set, &key, op->code);
208 elem = obstack_alloc(&status->cnts, sizeof(*elem));
211 cnt_clr(&elem->cnt_alive);
212 cnt_clr(&elem->new_node);
213 cnt_clr(&elem->into_Id);
217 return pset_insert(set, elem, op->code);
221 * calculates a hash value for an irg
222 * Addresses are typically aligned at 32bit, so we ignore the lowest bits
224 static INLINE unsigned irg_hash(const ir_graph *irg)
226 return (unsigned)irg >> 3;
230 * Returns the acssociates graph_entry_t for an irg
232 static graph_entry_t *graph_get_entry(ir_graph *irg, pset *set)
240 elem = pset_find(set, &key, irg_hash(irg));
244 elem = obstack_alloc(&status->cnts, sizeof(*elem));
246 cnt_clr(&elem->cnt_walked);
247 cnt_clr(&elem->cnt_walked_blocks);
248 cnt_clr(&elem->cnt_got_inlined);
249 cnt_clr(&elem->cnt_was_inlined);
250 cnt_clr(&elem->cnt_edges);
252 /* new hash table for opcodes here */
253 elem->opcode_hash = new_pset(opcode_cmp, 5);
256 for (i = 0; i < sizeof(elem->opt_hash)/sizeof(elem->opt_hash[0]); ++i)
257 elem->opt_hash[i] = new_pset(opt_cmp, 4);
259 return pset_insert(set, elem, irg_hash(irg));
263 * Returns the associates opt_entry_t for an ir_op
265 static opt_entry_t *opt_get_entry(const ir_op *op, pset *set)
272 elem = pset_find(set, &key, op->code);
276 elem = obstack_alloc(&status->cnts, sizeof(*elem));
278 /* clear new counter */
279 cnt_clr(&elem->count);
283 return pset_insert(set, elem, op->code);
287 * Returns the ir_op for an IR-node,
288 * handles special cases and return pseudo op codes
290 static ir_op *stat_get_irn_op(const ir_node *node)
292 ir_op *op = get_irn_op(node);
294 if (op->code == iro_Phi && get_irn_arity(node) == 0) {
295 /* special case, a Phi0 node, count on extra counter */
296 op = status->op_Phi0;
298 else if (op->code == iro_Phi && get_irn_mode(node) == mode_M) {
299 /* special case, a Memory Phi node, count on extra counter */
300 op = status->op_PhiM;
307 * environment for the count walker
309 typedef struct _cnt_env_t {
310 pset *set; /**< the hash map containing the ir_ops */
311 counter_t *cnt_edges; /**< the edges counter */
315 * walker for reachable nodes count
317 static void count_nodes(ir_node *node, void *env)
319 cnt_env_t *cenv = env;
321 ir_op *op = stat_get_irn_op(node);
322 int arity = get_irn_arity(node);
324 entry = opcode_get_entry(op, cenv->set);
326 cnt_inc(&entry->cnt_alive);
327 cnt_add_i(cenv->cnt_edges, arity);
331 * count all alive nodes in a graph
333 static void count_nodes_in_graph(graph_entry_t * global, graph_entry_t * graph)
338 env.set = graph->opcode_hash;
339 env.cnt_edges = &graph->cnt_edges;
341 irg_walk_graph(graph->irg, count_nodes, NULL, &env);
343 /* assume we walk every graph only ONCE, we could sum here the global count */
344 for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
345 node_entry_t *g_entry = opcode_get_entry(entry->op, global->opcode_hash);
347 /* update the node counter */
348 cnt_add(&g_entry->cnt_alive, &entry->cnt_alive);
351 /* update the edge counter */
352 cnt_add(&global->cnt_edges, &graph->cnt_edges);
358 static void stat_register_dumper(dumper_t *dumper, const char *name)
360 dumper->next = status->dumper;
361 status->dumper = dumper;
364 dumper->init(dumper, name);
370 static void dump_graph(graph_entry_t *entry)
374 for (dumper = status->dumper; dumper; dumper = dumper->next) {
375 if (dumper->dump_graph)
376 dumper->dump_graph(dumper, entry);
383 static void dump_finish(void)
387 for (dumper = status->dumper; dumper; dumper = dumper->next) {
389 dumper->finish(dumper);
393 /* ---------------------------------------------------------------------- */
396 * dumps a opcode hash into human readable form
398 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
402 counter_t f_new_node;
406 cnt_clr(&f_new_node);
409 fprintf(dmp->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
410 for (entry = pset_first(set); entry; entry = pset_next(set)) {
411 fprintf(dmp->f, "%-16s %8d %8d %8d\n",
412 get_id_str(entry->op->name), entry->cnt_alive.cnt[0], entry->new_node.cnt[0], entry->into_Id.cnt[0]);
414 cnt_add(&f_alive, &entry->cnt_alive);
415 cnt_add(&f_new_node, &entry->new_node);
416 cnt_add(&f_Id, &entry->into_Id);
418 fprintf(dmp->f, "-------------------------------------------\n");
419 fprintf(dmp->f, "%-16s %8d %8d %8d\n", "Sum",
426 * dumps a optimization hash into human readable form
428 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
430 opt_entry_t *entry = pset_first(set);
433 fprintf(dmp->f, "\n%s:\n", opt_names[index]);
434 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
436 for (; entry; entry = pset_next(set)) {
437 fprintf(dmp->f, "%-16s %8d\n",
438 get_id_str(entry->op->name), entry->count.cnt[0]);
444 * dumps the endges count
446 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
448 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt->cnt[0]);
454 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
459 ir_graph *const_irg = get_const_code_irg();
461 if (entry->irg == const_irg) {
462 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
466 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_name(entry->ent), (void *)entry->irg);
468 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
471 fprintf(dmp->f, " %swalked %d over blocks %d was inlined %d got inlined %d:\n",
472 entry->deleted ? "DELETED " : "",
473 entry->cnt_walked.cnt[0], entry->cnt_walked_blocks.cnt[0],
474 entry->cnt_was_inlined.cnt[0],
475 entry->cnt_got_inlined.cnt[0]
479 fprintf(dmp->f, "\nGlobals counts:\n");
483 simple_dump_opcode_hash(dmp, entry->opcode_hash);
484 simple_dump_edges(dmp, &entry->cnt_edges);
486 /* effects of optimizations */
490 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
491 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
497 * initialise the simple dumper
499 static void simple_init(dumper_t *dmp, const char *name)
501 dmp->f = fopen(name, "w");
505 * finishes the simple dumper
507 static void simple_finish(dumper_t *dmp)
514 * the simple human readable dumper
516 static dumper_t simple_dumper = {
524 /* ---------------------------------------------------------------------- */
527 * count the nodes as needed:
529 * 1 normal (data) Phi's
534 static void csv_count_nodes(graph_entry_t *graph, counter_t cnt[])
539 for (i = 0; i < 4; ++i)
542 for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
543 if (entry->op == op_Phi) {
545 cnt_add(&cnt[1], &entry->cnt_alive);
547 else if (entry->op == status->op_PhiM) {
549 cnt_add(&cnt[2], &entry->cnt_alive);
551 else if (entry->op == op_Proj) {
553 cnt_add(&cnt[3], &entry->cnt_alive);
556 /* all other nodes */
557 cnt_add(&cnt[0], &entry->cnt_alive);
565 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
572 ir_graph *const_irg = get_const_code_irg();
574 if (entry->irg == const_irg) {
575 name = "<Const code Irg>";
580 name = get_entity_name(entry->ent);
582 name = "<UNKNOWN IRG>";
585 csv_count_nodes(entry, cnt);
587 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
599 * initialise the simple dumper
601 static void csv_init(dumper_t *dmp, const char *name)
603 dmp->f = fopen(name, "a");
607 * finishes the simple dumper
609 static void csv_finish(dumper_t *dmp)
616 * the simple human readable dumper
618 static dumper_t csv_dumper = {
627 /* ---------------------------------------------------------------------- */
629 /* initialize the statistics module. */
632 #define X(a) a, sizeof(a)-1
636 /* enable statistics */
639 if (! status->enable)
642 obstack_init(&status->cnts);
644 /* build the pseudo-ops */
645 _op_Phi0.code = --pseudo_id;
646 _op_Phi0.name = id_from_str(X("Phi0"));
648 _op_PhiM.code = --pseudo_id;
649 _op_PhiM.name = id_from_str(X("PhiM"));
651 /* create the hash-tables */
652 status->irg_hash = new_pset(graph_cmp, 8);
654 status->op_Phi0 = &_op_Phi0;
655 status->op_PhiM = &_op_PhiM;
657 stat_register_dumper(&simple_dumper, "firmstat.txt");
658 stat_register_dumper(&csv_dumper, "firmstat.csv");
660 /* initialize the pattern hash */
661 stat_init_pattern_history(status->enable);
665 /* A new IR op is registered. */
666 void stat_new_ir_op(const ir_op *op)
668 if (! status->enable)
673 graph_entry_t *graph = graph_get_entry(NULL, status->irg_hash);
675 /* execute for side effect :-) */
676 opcode_get_entry(op, graph->opcode_hash);
681 /* An IR op is freed. */
682 void stat_free_ir_op(const ir_op *op)
684 if (! status->enable)
693 /* A new node is created. */
694 void stat_new_node(const ir_node *node)
696 if (! status->enable)
699 /* do NOT count during dead node elimination */
700 if (status->in_dead_node_elim > 0)
706 graph_entry_t *graph;
707 ir_op *op = stat_get_irn_op(node);
709 /* increase global value */
710 graph = graph_get_entry(NULL, status->irg_hash);
711 entry = opcode_get_entry(op, graph->opcode_hash);
712 cnt_inc(&entry->new_node);
714 /* increase local value */
715 graph = graph_get_entry(current_ir_graph, status->irg_hash);
716 entry = opcode_get_entry(op, graph->opcode_hash);
717 cnt_inc(&entry->new_node);
722 /* A node is changed into a Id node */
723 void stat_turn_into_id(const ir_node *node)
725 if (! status->enable)
731 graph_entry_t *graph;
732 ir_op *op = stat_get_irn_op(node);
734 /* increase global value */
735 graph = graph_get_entry(NULL, status->irg_hash);
736 entry = opcode_get_entry(op, graph->opcode_hash);
737 cnt_inc(&entry->into_Id);
739 /* increase local value */
740 graph = graph_get_entry(current_ir_graph, status->irg_hash);
741 entry = opcode_get_entry(op, graph->opcode_hash);
742 cnt_inc(&entry->into_Id);
747 /* A new graph was created */
748 void stat_new_graph(ir_graph *irg, entity *ent)
750 if (! status->enable)
755 /* execute for side effect :-) */
756 graph_entry_t * graph = graph_get_entry(irg, status->irg_hash);
765 * A graph was deleted
767 void stat_free_graph(ir_graph *irg)
769 if (! status->enable)
774 graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
775 graph_entry_t *global = graph_get_entry(NULL, status->irg_hash);
779 /* count the nodes of the graph yet, it will be destroyed later */
780 count_nodes_in_graph(global, graph);
782 /* calculate the pattern */
783 stat_calc_pattern_history(irg);
789 * A walk over a graph is initiated. Do not count walks from statistic code.
791 void stat_irg_walk(ir_graph *irg, void *pre, void *post)
793 if (! status->enable)
798 graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
800 cnt_inc(&graph->cnt_walked);
806 * A walk over the graph's blocks is initiated. Do not count walks from statistic code.
808 void stat_irg_block_walk(ir_graph *irg, const ir_node *node, void *pre, void *post)
810 if (! status->enable)
815 graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
817 cnt_inc(&graph->cnt_walked_blocks);
823 * called for every node that is removed due to an optimization
825 static void removed_due_opt(ir_node *n, pset *set)
827 ir_op *op = get_irn_op(n);
828 opt_entry_t *entry = opt_get_entry(op, set);
830 /* increase global value */
831 cnt_inc(&entry->count);
835 * Some nodes were optimized into some others due to an optimization
837 void stat_merge_nodes(
838 ir_node **new_node_array, int new_num_entries,
839 ir_node **old_node_array, int old_num_entries,
842 if (! status->enable)
848 graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
850 for (i = 0; i < old_num_entries; ++i) {
851 for (j = 0; j < new_num_entries; ++j)
852 if (old_node_array[i] == new_node_array[j])
855 /* nodes might be in new and old, these are NOT removed */
856 if (j >= new_num_entries) {
857 removed_due_opt(old_node_array[i], graph->opt_hash[opt]);
865 * A node was lowered into other nodes
867 void stat_lower(ir_node *node)
869 if (! status->enable)
874 graph_entry_t *graph = graph_get_entry(current_ir_graph, status->irg_hash);
876 removed_due_opt(node, graph->opt_hash[STAT_LOWERED]);
882 * A graph was inlined
884 void stat_inline(ir_node *call, ir_graph *called_irg)
886 if (! status->enable)
891 ir_graph *irg = get_irn_irg(call);
892 graph_entry_t *i_graph = graph_get_entry(called_irg, status->irg_hash);
893 graph_entry_t *graph = graph_get_entry(irg, status->irg_hash);
895 cnt_inc(&graph->cnt_got_inlined);
896 cnt_inc(&i_graph->cnt_was_inlined);
902 * Start the dead node elimination.
904 void stat_dead_node_elim_start(ir_graph *irg)
906 if (! status->enable)
909 ++status->in_dead_node_elim;
913 * Stops the dead node elimination.
915 void stat_dead_node_elim_stop(ir_graph *irg)
917 if (! status->enable)
920 --status->in_dead_node_elim;
923 /* Finish the statistics */
924 void stat_finish(void)
926 if (! status->enable)
931 graph_entry_t *entry;
932 graph_entry_t *global = graph_get_entry(NULL, status->irg_hash);
935 for (entry = pset_first(status->irg_hash); entry; entry = pset_next(status->irg_hash)) {
937 if (entry->irg == NULL) {
938 /* special entry for the global count */
942 if (! entry->deleted) {
943 /* the graph is still alive, count the nodes on it */
944 count_nodes_in_graph(global, entry);
946 /* calculate the pattern */
947 stat_calc_pattern_history(entry->irg);
957 stat_finish_pattern_history();
967 /* need this for prototypes */
968 #define FIRM_STATISTICS
969 #include "firmstat.h"
971 void stat_init(void) {}
973 void stat_finish(void) {}
975 void stat_new_ir_op(const ir_op *op) {}
977 void stat_free_ir_op(const ir_op *op) {}
979 void stat_new_node(const ir_node *node) {}
981 void stat_turn_into_id(const ir_node *node) {}
983 void stat_new_graph(ir_graph *irg, entity *ent) {}
985 void stat_free_graph(ir_graph *irg) {}
987 void stat_irg_walk(ir_graph *irg, void *pre, void *post) {}
989 void stat_irg_block_walk(ir_graph *irg, const ir_node *node, void *pre, void *post) {}
991 void stat_merge_nodes(
992 ir_node **new_node_array, int new_num_entries,
993 ir_node **old_node_array, int old_num_entries,
994 stat_opt_kind opt) {}
996 void stat_lower(ir_node *node) {}
998 void stat_inline(ir_node *call, ir_graph *irg) {}
1000 void stat_dead_node_elim_start(ir_graph *irg) {}
1002 void stat_dead_node_elim_stop(ir_graph *irg) {}