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_SUB_SUB_X_Y_Z, "algebraic simplification: (x - y) - z = x - (y + z)" },
61 { FS_OPT_MUL_MINUS_1, "algebraic simplification: a * -1 = -a" },
62 { FS_OPT_OR, "algebraic simplification: a | a = a | 0 = 0 | a = a" },
63 { FS_OPT_AND, "algebraic simplification: a & 0b1...1 = 0b1...1 & a = a & a = a" },
64 { FS_OPT_EOR_A_A, "algebraic simplification: a ^ a = 0" },
65 { FS_OPT_EOR_TO_NOT_BOOL,"algebraic simplification: bool ^ 1 = !bool" },
66 { FS_OPT_EOR_TO_NOT, "algebraic simplification: x ^ 0b1..1 = ~x" },
67 { FS_OPT_NOT_CMP, "algebraic simplification: !(a cmp b) = a !cmp b" },
68 { FS_OPT_OR_SHFT_TO_ROT, "algebraic simplification: (x << c) | (x >> (bits - c)) == Rot(x, c)" },
69 { FS_OPT_REASSOC_SHIFT, "algebraic simplification: (x SHF c1) SHF c2 = x SHF (c1+c2)" },
70 { FS_OPT_CONV, "algebraic simplification: Conv could be removed" },
71 { FS_OPT_CAST, "algebraic simplification: a Cast could be removed" },
72 { FS_OPT_MIN_MAX_EQ, "algebraic simplification: Min(a,a) = Max(a,a) = a" },
73 { FS_OPT_MUX_C, "algebraic simplification: Mux(C, f, t) = C ? t : f" },
74 { FS_OPT_MUX_EQ, "algebraic simplification: Mux(v, x, x) = x" },
75 { FS_OPT_MUX_TRANSFORM, "algebraic simplification: Mux(a, b, c) = b OR Mux(a,b, c) = c" },
76 { FS_OPT_MUX_TO_MIN, "algebraic simplification: Mux(a < b, a, b) = Min(a,b)" },
77 { FS_OPT_MUX_TO_MAX, "algebraic simplification: Mux(a > b, a, b) = Max(a,b)" },
78 { FS_OPT_MUX_TO_ABS, "algebraic simplification: Mux(a > b, a, b) = Abs(a,b)" },
79 { FS_OPT_MUX_TO_SHR, "algebraic simplification: Mux(a > b, a, b) = a >> b" },
80 { FS_OPT_CONST_PHI, "constant evaluation on Phi node" },
81 { FS_BE_IA32_LEA, "ia32 Backend transformation: Lea was created" },
82 { FS_BE_IA32_LOAD_LEA, "ia32 Backend transformation: Load merged with a Lea" },
83 { FS_BE_IA32_STORE_LEA, "ia32 Backend transformation: Store merged with a Lea" },
84 { FS_BE_IA32_AM_S, "ia32 Backend transformation: Source address mode node created" },
85 { FS_BE_IA32_AM_D, "ia32 Backend transformation: Destination address mode node created" },
86 { FS_BE_IA32_CJMP, "ia32 Backend transformation: CJmp created to save a cmp/test" },
87 { FS_BE_IA32_2ADDRCPY, "ia32 Backend transformation: Copy created due to 2-Addresscode constraints" },
88 { FS_BE_IA32_SPILL2ST, "ia32 Backend transformation: Created Store for a Spill" },
89 { FS_BE_IA32_RELOAD2LD, "ia32 Backend transformation: Created Load for a Reload" },
90 { FS_BE_IA32_SUB2NEGADD, "ia32 Backend transformation: Created Neg-Add for a Sub due to 2-Addresscode constraints" },
91 { FS_BE_IA32_LEA2ADD, "ia32 Backend transformation: Transformed Lea back into Add" },
94 static const char *if_conv_names[IF_RESULT_LAST] = {
96 "if conv side effect ",
97 "if conv Phi node found ",
98 "if conv to deep DAG's ",
99 "if conv bad control flow ",
100 "if conv denied by arch ",
104 * dumps a opcode hash into human readable form
106 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
110 counter_t f_new_node;
114 cnt_clr(&f_new_node);
117 fprintf(dmp->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
118 foreach_pset(set, entry) {
119 fprintf(dmp->f, "%-16s %8u %8u %8u\n",
120 get_id_str(entry->op->name),
121 cnt_to_uint(&entry->cnt_alive),
122 cnt_to_uint(&entry->new_node),
123 cnt_to_uint(&entry->into_Id)
126 cnt_add(&f_alive, &entry->cnt_alive);
127 cnt_add(&f_new_node, &entry->new_node);
128 cnt_add(&f_Id, &entry->into_Id);
130 fprintf(dmp->f, "-------------------------------------------\n");
131 fprintf(dmp->f, "%-16s %8u %8u %8u\n", "Sum",
132 cnt_to_uint(&f_alive),
133 cnt_to_uint(&f_new_node),
139 * dumps an optimization hash into human readable form
141 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
143 assert(index < ARR_SIZE(opt_names) && "index out of range");
144 assert(opt_names[index].kind == index && "opt_names broken");
146 if (pset_count(set) > 0) {
149 fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
150 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
152 foreach_pset(set, entry) {
153 fprintf(dmp->f, "%-16s %8u\n",
154 get_id_str(entry->op->name), cnt_to_uint(&entry->count));
160 * dumps the register pressure for each block and for each register class
162 static void simple_dump_be_block_reg_pressure(dumper_t *dmp, graph_entry_t *entry)
164 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
165 reg_pressure_entry_t *rp_entry;
167 /* return if no be statistic information available */
171 fprintf(dmp->f, "\nREG PRESSURE:\n");
172 fprintf(dmp->f, "%12s", "Block Nr");
174 /* print table head (register class names) */
175 foreach_pset(b_entry->reg_pressure, rp_entry)
176 fprintf(dmp->f, "%15s", rp_entry->class_name);
177 fprintf(dmp->f, "\n");
179 /* print the reg pressure for all blocks and register classes */
180 for (/* b_entry is already initialized */ ;
182 b_entry = pset_next(entry->be_block_hash)) {
183 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
185 foreach_pset(b_entry->reg_pressure, rp_entry)
186 fprintf(dmp->f, "%15d", rp_entry->pressure);
187 fprintf(dmp->f, "\n");
191 /** prints a distribution entry */
192 static void simple_dump_distrib_entry(const distrib_entry_t *entry, void *env)
195 fprintf(dmp_f, "%12d", cnt_to_uint(&entry->cnt));
199 * dumps the distribution of the amount of ready nodes for each block
201 static void simple_dump_be_block_sched_ready(dumper_t *dmp, graph_entry_t *entry)
203 if (pset_count(entry->be_block_hash) > 0) {
204 be_block_entry_t *b_entry;
207 fprintf(dmp->f, "\nSCHEDULING: NUMBER OF READY NODES\n");
208 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s %12s\n",
209 "Block Nr", "1 node", "2 nodes", "3 nodes", "4 nodes", "5 or more", "AVERAGE");
211 foreach_pset(entry->be_block_hash, b_entry) {
212 /* this ensures that all keys from 1 to 5 are in the table */
213 for (i = 1; i < 6; ++i)
214 stat_insert_int_distrib_tbl(b_entry->sched_ready, i);
216 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
217 stat_iterate_distrib_tbl(b_entry->sched_ready, simple_dump_distrib_entry, dmp->f);
218 fprintf(dmp->f, "%12.2lf", stat_calc_avg_distrib_tbl(b_entry->sched_ready));
219 fprintf(dmp->f, "\n");
225 * Adds the counter for given entry to another distribution table.
227 static void add_distrib_entry(const distrib_entry_t *entry, void *env) {
228 distrib_tbl_t *sum_tbl = env;
230 stat_add_int_distrib_tbl(sum_tbl, (int)(entry->object), &entry->cnt);
234 * dumps permutation statistics for one and block and one class
236 static void simple_dump_be_block_permstat_class(dumper_t *dmp, perm_class_entry_t *entry)
238 perm_stat_entry_t *ps_ent;
239 distrib_tbl_t *sum_chains = stat_new_int_distrib_tbl();
240 distrib_tbl_t *sum_cycles = stat_new_int_distrib_tbl();
244 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s\n",
253 foreach_pset(entry->perm_stat, ps_ent) {
254 fprintf(dmp->f, "%12d %12d %12d %12d %12d %12d\n",
257 stat_get_count_distrib_tbl(ps_ent->chains),
258 stat_get_count_distrib_tbl(ps_ent->cycles),
263 /* sum up distribution table for chains */
264 stat_iterate_distrib_tbl(ps_ent->chains, add_distrib_entry, sum_chains);
266 /* sum up distribution table for cycles */
267 stat_iterate_distrib_tbl(ps_ent->cycles, add_distrib_entry, sum_cycles);
270 /* print chain distribution for all perms of this class in this block */
271 fprintf(dmp->f, "chain distribution:\n");
273 /* add all missing entries to chain distribution table */
274 for (i = 1; i <= entry->n_regs; i++) {
275 snprintf(buf, sizeof(buf), "length %d", i);
276 fprintf(dmp->f, "%12s", buf);
277 stat_insert_int_distrib_tbl(sum_chains, i);
279 fprintf(dmp->f, "\n");
280 stat_iterate_distrib_tbl(sum_chains, simple_dump_distrib_entry, dmp->f);
281 fprintf(dmp->f, "\n");
283 /* print cycle distribution for all perms of this class in this block */
284 fprintf(dmp->f, "cycle distribution:\n");
286 /* add all missing entries to cycle distribution table */
287 for (i = 1; i <= entry->n_regs; i++) {
288 snprintf(buf, sizeof(buf), "length %d", i);
289 fprintf(dmp->f, "%12s", buf);
290 stat_insert_int_distrib_tbl(sum_cycles, i);
292 fprintf(dmp->f, "\n");
293 stat_iterate_distrib_tbl(sum_cycles, simple_dump_distrib_entry, dmp->f);
294 fprintf(dmp->f, "\n");
296 /* delete temporary sum distribution tables */
297 stat_delete_distrib_tbl(sum_chains);
298 stat_delete_distrib_tbl(sum_cycles);
303 * dumps statistics about perms
305 static void simple_dump_be_block_permstat(dumper_t *dmp, graph_entry_t *entry)
307 if (pset_count(entry->be_block_hash) > 0) {
308 be_block_entry_t *b_entry;
310 fprintf(dmp->f, "\nPERMUTATION STATISTICS BEGIN:\n");
311 foreach_pset(entry->be_block_hash, b_entry) {
312 perm_class_entry_t *pc_ent;
314 fprintf(dmp->f, "BLOCK %ld:\n", b_entry->block_nr);
316 if (b_entry->perm_class_stat)
317 foreach_pset(b_entry->perm_class_stat, pc_ent) {
318 fprintf(dmp->f, "register class %s:\n", pc_ent->class_name);
319 simple_dump_be_block_permstat_class(dmp, pc_ent);
323 fprintf(dmp->f, "PERMUTATION STATISTICS END\n");
328 * dumps the number of real_function_call optimization
330 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
335 if (! cnt_eq(cnt, 0)) {
336 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
337 fprintf(dmp->f, "%-16s %8u\n", "Call", cnt_to_uint(cnt));
342 * dumps the number of tail_recursion optimization
344 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
349 if (num_tail_recursion > 0) {
350 fprintf(dmp->f, "\nTail recursion optimized:\n");
351 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
356 * dumps the edges count
358 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
363 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt_to_uint(cnt));
369 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
371 int i, dump_opts = 1;
372 block_entry_t *b_entry;
373 extbb_entry_t *eb_entry;
379 ir_graph *const_irg = get_const_code_irg();
381 if (entry->irg == const_irg)
382 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
385 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
387 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
390 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
391 " was inlined : %u\n"
392 " got inlined : %u\n"
393 " strength red : %u\n"
394 " leaf function : %s\n"
395 " calls only leaf functions : %s\n"
399 " indirect calls : %u\n",
400 entry->is_deleted ? "DELETED " : "",
401 cnt_to_uint(&entry->cnt_walked), cnt_to_uint(&entry->cnt_walked_blocks),
402 cnt_to_uint(&entry->cnt_was_inlined),
403 cnt_to_uint(&entry->cnt_got_inlined),
404 cnt_to_uint(&entry->cnt_strength_red),
405 entry->is_leaf ? "YES" : "NO",
406 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
407 entry->is_recursive ? "YES" : "NO",
408 entry->is_chain_call ? "YES" : "NO",
409 cnt_to_uint(&entry->cnt_all_calls),
410 cnt_to_uint(&entry->cnt_indirect_calls)
413 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
414 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], cnt_to_uint(&entry->cnt_if_conv[i]));
418 fprintf(dmp->f, "\nGlobals counts:\n");
419 fprintf(dmp->f, "--------------\n");
423 simple_dump_opcode_hash(dmp, entry->opcode_hash);
424 simple_dump_edges(dmp, &entry->cnt_edges);
426 /* effects of optimizations */
430 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
431 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
433 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
434 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
437 /* dump block info */
438 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
439 foreach_pset(entry->block_hash, b_entry) {
440 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
442 cnt_to_uint(&b_entry->cnt_nodes),
443 cnt_to_uint(&b_entry->cnt_edges),
444 cnt_to_uint(&b_entry->cnt_in_edges),
445 cnt_to_uint(&b_entry->cnt_out_edges),
446 cnt_to_uint(&b_entry->cnt_phi_data),
447 cnt_to_dbl(&b_entry->cnt_edges) / cnt_to_dbl(&b_entry->cnt_nodes)
451 /* dump block reg pressure */
452 simple_dump_be_block_reg_pressure(dmp, entry);
454 /* dump block ready nodes distribution */
455 simple_dump_be_block_sched_ready(dmp, entry);
457 /* dump block permutation statistics */
458 simple_dump_be_block_permstat(dmp, entry);
460 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB && entry->extbb_hash) {
461 /* dump extended block info */
462 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
463 foreach_pset(entry->extbb_hash, eb_entry) {
464 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
466 cnt_to_uint(&eb_entry->cnt_nodes),
467 cnt_to_uint(&eb_entry->cnt_edges),
468 cnt_to_uint(&eb_entry->cnt_in_edges),
469 cnt_to_uint(&eb_entry->cnt_out_edges),
470 cnt_to_uint(&eb_entry->cnt_phi_data),
471 cnt_to_dbl(&eb_entry->cnt_edges) / cnt_to_dbl(&eb_entry->cnt_nodes)
481 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
491 fprintf(dmp->f, "\nConstant Information:\n");
492 fprintf(dmp->f, "---------------------\n");
494 fprintf(dmp->f, "\nBit usage for integer constants\n");
495 fprintf(dmp->f, "-------------------------------\n");
497 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
498 fprintf(dmp->f, "%5d %12u\n", i + 1, cnt_to_uint(&tbl->int_bits_count[i]));
499 cnt_add(&sum, &tbl->int_bits_count[i]);
501 fprintf(dmp->f, "-------------------------------\n");
503 fprintf(dmp->f, "\nFloating point constants classification\n");
504 fprintf(dmp->f, "--------------------------------------\n");
505 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
506 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), cnt_to_uint(&tbl->floats[i]));
507 cnt_add(&sum, &tbl->floats[i]);
509 fprintf(dmp->f, "--------------------------------------\n");
511 fprintf(dmp->f, "other %12u\n", cnt_to_uint(&tbl->others));
512 cnt_add(&sum, &tbl->others);
513 fprintf(dmp->f, "-------------------------------\n");
515 fprintf(dmp->f, "sum %12u\n", cnt_to_uint(&sum));
519 * initialize the simple dumper
521 static void simple_init(dumper_t *dmp, const char *name)
525 snprintf(fname, sizeof(fname), "%s.txt", name);
526 dmp->f = fopen(fname, "w");
533 * finishes the simple dumper
535 static void simple_finish(dumper_t *dmp)
543 * the simple human readable dumper
545 const dumper_t simple_dumper = {
547 simple_dump_const_tbl,
554 FOURCC('S', 'M', 'P', 'L'),
557 /* ---------------------------------------------------------------------- */
560 * count the nodes as needed:
562 * 1 normal (data) Phi's
567 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
572 for (i = 0; i < 4; ++i)
575 foreach_pset(graph->opcode_hash, entry) {
576 if (entry->op == op_Phi) {
578 cnt_add(&cnt[1], &entry->cnt_alive);
580 else if (entry->op == dmp->status->op_PhiM) {
582 cnt_add(&cnt[2], &entry->cnt_alive);
584 else if (entry->op == op_Proj) {
586 cnt_add(&cnt[3], &entry->cnt_alive);
589 /* all other nodes */
590 cnt_add(&cnt[0], &entry->cnt_alive);
598 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
606 if (entry->irg && !entry->is_deleted) {
607 ir_graph *const_irg = get_const_code_irg();
609 if (entry->irg == const_irg) {
610 name = "<Const code Irg>";
615 name = get_entity_name(entry->ent);
617 name = "<UNKNOWN IRG>";
620 csv_count_nodes(dmp, entry, cnt);
622 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
625 cnt_to_uint(&cnt[0]),
626 cnt_to_uint(&cnt[1]),
627 cnt_to_uint(&cnt[2]),
636 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
642 * initialize the simple dumper
644 static void csv_init(dumper_t *dmp, const char *name)
648 snprintf(fname, sizeof(fname), "%s.csv", name);
649 dmp->f = fopen(fname, "a");
655 * finishes the simple dumper
657 static void csv_finish(dumper_t *dmp)
665 * the simple human readable dumper
667 const dumper_t csv_dumper = {
676 FOURCC('C', 'S', 'V', '\0')