3 * File name: ir/ir/stat_dmp.c
4 * Purpose: Statistics for Firm.
8 * Copyright: (c) 2004 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 * names of the optimizations
25 { HOOK_OPT_DEAD_BLOCK, "dead block elimination" },
26 { HOOK_OPT_STG, "straightening optimization" },
27 { HOOK_OPT_IFSIM, "if simplification" },
28 { HOOK_OPT_CONST_EVAL, "constant evaluation" },
29 { HOOK_OPT_ALGSIM, "algebraic simplification" },
30 { HOOK_OPT_PHI, "Phi optmization" },
31 { HOOK_OPT_SYNC, "Sync optmization" },
32 { HOOK_OPT_WAW, "Write-After-Write optimization" },
33 { HOOK_OPT_WAR, "Write-After-Read optimization" },
34 { HOOK_OPT_RAW, "Read-After-Write optimization" },
35 { HOOK_OPT_RAR, "Read-After-Read optimization" },
36 { HOOK_OPT_RC, "Read-a-Const optimization" },
37 { HOOK_OPT_TUPLE, "Tuple optimization" },
38 { HOOK_OPT_ID, "ID optimization" },
39 { HOOK_OPT_CSE, "Common subexpression elimination" },
40 { HOOK_OPT_STRENGTH_RED, "Strength reduction" },
41 { HOOK_OPT_ARCH_DEP, "Architecture dependant optimization" },
42 { HOOK_OPT_REASSOC, "Reassociation optimization" },
43 { HOOK_OPT_POLY_CALL, "Polymorphic call optimization" },
44 { HOOK_OPT_IF_CONV, "an if conversion was tried" },
45 { HOOK_OPT_FUNC_CALL, "Real function call optimization" },
46 { HOOK_OPT_CONFIRM, "Confirm-based optimization: replacement" },
47 { HOOK_OPT_CONFIRM_C, "Confirm-based optimization: replaced by const" },
48 { HOOK_OPT_CONFIRM_E, "Confirm-based optimization: evaluated" },
49 { HOOK_OPT_EXC_REM, "a exception edge was removed due to a Confirmation prove" },
50 { HOOK_LOWERED, "Lowered" },
51 { HOOK_BACKEND, "Backend transformation" },
52 { FS_OPT_NEUTRAL_0, "algebraic simplification: a op 0 = 0 op a = a" },
53 { FS_OPT_NEUTRAL_1, "algebraic simplification: a op 1 = 1 op a = a" },
54 { FS_OPT_ADD_A_A, "algebraic simplification: a + a = a * 2" },
55 { FS_OPT_ADD_A_MINUS_B, "algebraic simplification: a + -b = a - b" },
56 { FS_OPT_ADD_SUB, "algebraic simplification: (a + x) - x = (a - x) + x = a" },
57 { FS_OPT_ADD_MUL_A_X_A, "algebraic simplification: a * x + a = a * (x + 1)" },
58 { FS_OPT_SUB_0_A, "algebraic simplification: 0 - a = -a" },
59 { FS_OPT_SUB_MUL_A_X_A, "algebraic simplification: a * x - a = a * (x - 1)" },
60 { FS_OPT_MUL_MINUS_1, "algebraic simplification: a * -1 = -a" },
61 { FS_OPT_OR, "algebraic simplification: a | a = a | 0 = 0 | a = a" },
62 { FS_OPT_AND, "algebraic simplification: a & 0b1...1 = 0b1...1 & a = a & a = a" },
63 { FS_OPT_EOR_A_A, "algebraic simplification: a ^ a = 0" },
64 { FS_OPT_EOR_TO_NOT_BOOL,"algebraic simplification: bool ^ 1 = !bool" },
65 { FS_OPT_EOR_TO_NOT, "algebraic simplification: x ^ 0b1..1 = ~x" },
66 { FS_OPT_NOT_CMP, "algebraic simplification: !(a cmp b) = a !cmp b" },
67 { FS_OPT_OR_SHFT_TO_ROT, "algebraic simplification: (x << c) | (x >> (bits - c)) == Rot(x, c)" },
68 { FS_OPT_REASSOC_SHIFT, "algebraic simplification: (x SHF c1) SHF c2 = x SHF (c1+c2)" },
69 { FS_OPT_CONV, "algebraic simplification: Conv could be removed" },
70 { FS_OPT_CAST, "algebraic simplification: a Cast could be removed" },
71 { FS_OPT_MIN_MAX_EQ, "algebraic simplification: Min(a,a) = Max(a,a) = a" },
72 { FS_OPT_MUX_C, "algebraic simplification: Mux(C, f, t) = C ? t : f" },
73 { FS_OPT_MUX_EQ, "algebraic simplification: Mux(v, x, x) = x" },
74 { FS_OPT_MUX_TRANSFORM, "algebraic simplification: Mux(a, b, c) = b OR Mux(a,b, c) = c" },
75 { FS_OPT_MUX_TO_MIN, "algebraic simplification: Mux(a < b, a, b) = Min(a,b)" },
76 { FS_OPT_MUX_TO_MAX, "algebraic simplification: Mux(a > b, a, b) = Max(a,b)" },
77 { FS_OPT_MUX_TO_ABS, "algebraic simplification: Mux(a > b, a, b) = Abs(a,b)" },
78 { FS_OPT_MUX_TO_SHR, "algebraic simplification: Mux(a > b, a, b) = a >> b" },
79 { FS_BE_IA32_LEA, "ia32 Backend transformation: Lea was created" },
80 { FS_BE_IA32_LOAD_LEA, "ia32 Backend transformation: Load merged with a Lea" },
81 { FS_BE_IA32_STORE_LEA, "ia32 Backend transformation: Store merged with a Lea" },
82 { FS_BE_IA32_AM_S, "ia32 Backend transformation: Source address mode node created" },
83 { FS_BE_IA32_AM_D, "ia32 Backend transformation: Destination address mode node created" },
84 { FS_BE_IA32_CJMP, "ia32 Backend transformation: CJmp created to save a cmp/test" },
85 { FS_BE_IA32_2ADDRCPY, "ia32 Backend transformation: Copy created due to 2-Addresscode constraints" },
86 { FS_BE_IA32_SPILL2ST, "ia32 Backend transformation: Created Store for a Spill" },
87 { FS_BE_IA32_RELOAD2LD, "ia32 Backend transformation: Created Load for a Reload" },
88 { FS_BE_IA32_SUB2NEGADD, "ia32 Backend transformation: Created Neg-Add for a Sub due to 2-Addresscode constraints" },
89 { FS_BE_IA32_LEA2ADD, "ia32 Backend transformation: Transformed Lea back into Add" },
92 static const char *if_conv_names[IF_RESULT_LAST] = {
94 "if conv side effect ",
95 "if conv Phi node found ",
96 "if conv to deep DAG's ",
97 "if conv bad control flow ",
98 "if conv denied by arch ",
102 * dumps a opcode hash into human readable form
104 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
108 counter_t f_new_node;
112 cnt_clr(&f_new_node);
115 fprintf(dmp->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
116 foreach_pset(set, entry) {
117 fprintf(dmp->f, "%-16s %8u %8u %8u\n",
118 get_id_str(entry->op->name),
119 cnt_to_uint(&entry->cnt_alive),
120 cnt_to_uint(&entry->new_node),
121 cnt_to_uint(&entry->into_Id)
124 cnt_add(&f_alive, &entry->cnt_alive);
125 cnt_add(&f_new_node, &entry->new_node);
126 cnt_add(&f_Id, &entry->into_Id);
128 fprintf(dmp->f, "-------------------------------------------\n");
129 fprintf(dmp->f, "%-16s %8u %8u %8u\n", "Sum",
130 cnt_to_uint(&f_alive),
131 cnt_to_uint(&f_new_node),
137 * dumps an optimization hash into human readable form
139 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
141 assert(index < ARR_SIZE(opt_names) && "index out of range");
142 assert(opt_names[index].kind == index && "opt_names broken");
144 if (pset_count(set) > 0) {
147 fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
148 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
150 foreach_pset(set, entry) {
151 fprintf(dmp->f, "%-16s %8u\n",
152 get_id_str(entry->op->name), cnt_to_uint(&entry->count));
158 * dumps the register pressure for each block and for each register class
160 static void simple_dump_be_block_reg_pressure(dumper_t *dmp, graph_entry_t *entry)
162 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
163 reg_pressure_entry_t *rp_entry;
165 /* return if no be statistic information available */
169 fprintf(dmp->f, "\nREG PRESSURE:\n");
170 fprintf(dmp->f, "%12s", "Block Nr");
172 /* print table head (register class names) */
173 foreach_pset(b_entry->reg_pressure, rp_entry)
174 fprintf(dmp->f, "%15s", rp_entry->class_name);
175 fprintf(dmp->f, "\n");
177 /* print the reg pressure for all blocks and register classes */
178 for (/* b_entry is already initialized */ ;
180 b_entry = pset_next(entry->be_block_hash)) {
181 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
183 foreach_pset(b_entry->reg_pressure, rp_entry)
184 fprintf(dmp->f, "%15d", rp_entry->pressure);
185 fprintf(dmp->f, "\n");
189 /** prints a distribution entry */
190 static void simple_dump_distrib_entry(const distrib_entry_t *entry, void *env)
193 fprintf(dmp_f, "%12d", cnt_to_uint(&entry->cnt));
197 * dumps the distribution of the amount of ready nodes for each block
199 static void simple_dump_be_block_sched_ready(dumper_t *dmp, graph_entry_t *entry)
201 if (pset_count(entry->be_block_hash) > 0) {
202 be_block_entry_t *b_entry;
205 fprintf(dmp->f, "\nSCHEDULING: NUMBER OF READY NODES\n");
206 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s %12s\n",
207 "Block Nr", "1 node", "2 nodes", "3 nodes", "4 nodes", "5 or more", "AVERAGE");
209 foreach_pset(entry->be_block_hash, b_entry) {
210 /* this ensures that all keys from 1 to 5 are in the table */
211 for (i = 1; i < 6; ++i)
212 stat_insert_int_distrib_tbl(b_entry->sched_ready, i);
214 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
215 stat_iterate_distrib_tbl(b_entry->sched_ready, simple_dump_distrib_entry, dmp->f);
216 fprintf(dmp->f, "%12.2lf", stat_calc_avg_distrib_tbl(b_entry->sched_ready));
217 fprintf(dmp->f, "\n");
223 * Adds the counter for given entry to another distribution table.
225 static void add_distrib_entry(const distrib_entry_t *entry, void *env) {
226 distrib_tbl_t *sum_tbl = env;
228 stat_add_int_distrib_tbl(sum_tbl, (int)(entry->object), &entry->cnt);
232 * dumps permutation statistics for one and block and one class
234 static void simple_dump_be_block_permstat_class(dumper_t *dmp, perm_class_entry_t *entry)
236 perm_stat_entry_t *ps_ent;
237 distrib_tbl_t *sum_chains = stat_new_int_distrib_tbl();
238 distrib_tbl_t *sum_cycles = stat_new_int_distrib_tbl();
242 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s\n",
251 foreach_pset(entry->perm_stat, ps_ent) {
252 fprintf(dmp->f, "%12d %12d %12d %12d %12d %12d\n",
255 stat_get_count_distrib_tbl(ps_ent->chains),
256 stat_get_count_distrib_tbl(ps_ent->cycles),
261 /* sum up distribution table for chains */
262 stat_iterate_distrib_tbl(ps_ent->chains, add_distrib_entry, sum_chains);
264 /* sum up distribution table for cycles */
265 stat_iterate_distrib_tbl(ps_ent->cycles, add_distrib_entry, sum_cycles);
268 /* print chain distribution for all perms of this class in this block */
269 fprintf(dmp->f, "chain distribution:\n");
271 /* add all missing entries to chain distribution table */
272 for (i = 1; i <= entry->n_regs; i++) {
273 snprintf(buf, sizeof(buf), "length %d", i);
274 fprintf(dmp->f, "%12s", buf);
275 stat_insert_int_distrib_tbl(sum_chains, i);
277 fprintf(dmp->f, "\n");
278 stat_iterate_distrib_tbl(sum_chains, simple_dump_distrib_entry, dmp->f);
279 fprintf(dmp->f, "\n");
281 /* print cycle distribution for all perms of this class in this block */
282 fprintf(dmp->f, "cycle distribution:\n");
284 /* add all missing entries to cycle distribution table */
285 for (i = 1; i <= entry->n_regs; i++) {
286 snprintf(buf, sizeof(buf), "length %d", i);
287 fprintf(dmp->f, "%12s", buf);
288 stat_insert_int_distrib_tbl(sum_cycles, i);
290 fprintf(dmp->f, "\n");
291 stat_iterate_distrib_tbl(sum_cycles, simple_dump_distrib_entry, dmp->f);
292 fprintf(dmp->f, "\n");
294 /* delete temporary sum distribution tables */
295 stat_delete_distrib_tbl(sum_chains);
296 stat_delete_distrib_tbl(sum_cycles);
301 * dumps statistics about perms
303 static void simple_dump_be_block_permstat(dumper_t *dmp, graph_entry_t *entry)
305 if (pset_count(entry->be_block_hash) > 0) {
306 be_block_entry_t *b_entry;
308 fprintf(dmp->f, "\nPERMUTATION STATISTICS BEGIN:\n");
309 foreach_pset(entry->be_block_hash, b_entry) {
310 perm_class_entry_t *pc_ent;
312 fprintf(dmp->f, "BLOCK %ld:\n", b_entry->block_nr);
314 if (b_entry->perm_class_stat)
315 foreach_pset(b_entry->perm_class_stat, pc_ent) {
316 fprintf(dmp->f, "register class %s:\n", pc_ent->class_name);
317 simple_dump_be_block_permstat_class(dmp, pc_ent);
321 fprintf(dmp->f, "PERMUTATION STATISTICS END\n");
326 * dumps the number of real_function_call optimization
328 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
333 if (! cnt_eq(cnt, 0)) {
334 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
335 fprintf(dmp->f, "%-16s %8u\n", "Call", cnt_to_uint(cnt));
340 * dumps the number of tail_recursion optimization
342 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
347 if (num_tail_recursion > 0) {
348 fprintf(dmp->f, "\nTail recursion optimized:\n");
349 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
354 * dumps the edges count
356 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
361 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt_to_uint(cnt));
367 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
369 int i, dump_opts = 1;
370 block_entry_t *b_entry;
371 extbb_entry_t *eb_entry;
377 ir_graph *const_irg = get_const_code_irg();
379 if (entry->irg == const_irg)
380 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
383 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
385 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
388 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
389 " was inlined : %u\n"
390 " got inlined : %u\n"
391 " strength red : %u\n"
392 " leaf function : %s\n"
393 " calls only leaf functions : %s\n"
397 " indirect calls : %u\n",
398 entry->is_deleted ? "DELETED " : "",
399 cnt_to_uint(&entry->cnt_walked), cnt_to_uint(&entry->cnt_walked_blocks),
400 cnt_to_uint(&entry->cnt_was_inlined),
401 cnt_to_uint(&entry->cnt_got_inlined),
402 cnt_to_uint(&entry->cnt_strength_red),
403 entry->is_leaf ? "YES" : "NO",
404 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
405 entry->is_recursive ? "YES" : "NO",
406 entry->is_chain_call ? "YES" : "NO",
407 cnt_to_uint(&entry->cnt_all_calls),
408 cnt_to_uint(&entry->cnt_indirect_calls)
411 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
412 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], cnt_to_uint(&entry->cnt_if_conv[i]));
416 fprintf(dmp->f, "\nGlobals counts:\n");
417 fprintf(dmp->f, "--------------\n");
421 simple_dump_opcode_hash(dmp, entry->opcode_hash);
422 simple_dump_edges(dmp, &entry->cnt_edges);
424 /* effects of optimizations */
428 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
429 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
431 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
432 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
435 /* dump block info */
436 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
437 foreach_pset(entry->block_hash, b_entry) {
438 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
440 cnt_to_uint(&b_entry->cnt_nodes),
441 cnt_to_uint(&b_entry->cnt_edges),
442 cnt_to_uint(&b_entry->cnt_in_edges),
443 cnt_to_uint(&b_entry->cnt_out_edges),
444 cnt_to_uint(&b_entry->cnt_phi_data),
445 cnt_to_dbl(&b_entry->cnt_edges) / cnt_to_dbl(&b_entry->cnt_nodes)
449 /* dump block reg pressure */
450 simple_dump_be_block_reg_pressure(dmp, entry);
452 /* dump block ready nodes distribution */
453 simple_dump_be_block_sched_ready(dmp, entry);
455 /* dump block permutation statistics */
456 simple_dump_be_block_permstat(dmp, entry);
458 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB && entry->extbb_hash) {
459 /* dump extended block info */
460 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
461 foreach_pset(entry->extbb_hash, eb_entry) {
462 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
464 cnt_to_uint(&eb_entry->cnt_nodes),
465 cnt_to_uint(&eb_entry->cnt_edges),
466 cnt_to_uint(&eb_entry->cnt_in_edges),
467 cnt_to_uint(&eb_entry->cnt_out_edges),
468 cnt_to_uint(&eb_entry->cnt_phi_data),
469 cnt_to_dbl(&eb_entry->cnt_edges) / cnt_to_dbl(&eb_entry->cnt_nodes)
479 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
489 fprintf(dmp->f, "\nConstant Information:\n");
490 fprintf(dmp->f, "---------------------\n");
492 fprintf(dmp->f, "\nBit usage for integer constants\n");
493 fprintf(dmp->f, "-------------------------------\n");
495 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
496 fprintf(dmp->f, "%5d %12u\n", i + 1, cnt_to_uint(&tbl->int_bits_count[i]));
497 cnt_add(&sum, &tbl->int_bits_count[i]);
499 fprintf(dmp->f, "-------------------------------\n");
501 fprintf(dmp->f, "\nFloating point constants classification\n");
502 fprintf(dmp->f, "--------------------------------------\n");
503 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
504 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), cnt_to_uint(&tbl->floats[i]));
505 cnt_add(&sum, &tbl->floats[i]);
507 fprintf(dmp->f, "--------------------------------------\n");
509 fprintf(dmp->f, "other %12u\n", cnt_to_uint(&tbl->others));
510 cnt_add(&sum, &tbl->others);
511 fprintf(dmp->f, "-------------------------------\n");
513 fprintf(dmp->f, "sum %12u\n", cnt_to_uint(&sum));
517 * initialize the simple dumper
519 static void simple_init(dumper_t *dmp, const char *name)
523 snprintf(fname, sizeof(fname), "%s.txt", name);
524 dmp->f = fopen(fname, "w");
531 * finishes the simple dumper
533 static void simple_finish(dumper_t *dmp)
541 * the simple human readable dumper
543 const dumper_t simple_dumper = {
545 simple_dump_const_tbl,
553 /* ---------------------------------------------------------------------- */
556 * count the nodes as needed:
558 * 1 normal (data) Phi's
563 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
568 for (i = 0; i < 4; ++i)
571 foreach_pset(graph->opcode_hash, entry) {
572 if (entry->op == op_Phi) {
574 cnt_add(&cnt[1], &entry->cnt_alive);
576 else if (entry->op == dmp->status->op_PhiM) {
578 cnt_add(&cnt[2], &entry->cnt_alive);
580 else if (entry->op == op_Proj) {
582 cnt_add(&cnt[3], &entry->cnt_alive);
585 /* all other nodes */
586 cnt_add(&cnt[0], &entry->cnt_alive);
594 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
602 if (entry->irg && !entry->is_deleted) {
603 ir_graph *const_irg = get_const_code_irg();
605 if (entry->irg == const_irg) {
606 name = "<Const code Irg>";
611 name = get_entity_name(entry->ent);
613 name = "<UNKNOWN IRG>";
616 csv_count_nodes(dmp, entry, cnt);
618 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
621 cnt_to_uint(&cnt[0]),
622 cnt_to_uint(&cnt[1]),
623 cnt_to_uint(&cnt[2]),
632 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
638 * initialize the simple dumper
640 static void csv_init(dumper_t *dmp, const char *name)
644 snprintf(fname, sizeof(fname), "%s.csv", name);
645 dmp->f = fopen(fname, "a");
651 * finishes the simple dumper
653 static void csv_finish(dumper_t *dmp)
661 * the simple human readable dumper
663 const dumper_t csv_dumper = {