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_BE_IA32_LEA, "ia32 Backend transformation: Lea was created" },
81 { FS_BE_IA32_LOAD_LEA, "ia32 Backend transformation: Load merged with a Lea" },
82 { FS_BE_IA32_STORE_LEA, "ia32 Backend transformation: Store merged with a Lea" },
83 { FS_BE_IA32_AM_S, "ia32 Backend transformation: Source address mode node created" },
84 { FS_BE_IA32_AM_D, "ia32 Backend transformation: Destination address mode node created" },
85 { FS_BE_IA32_CJMP, "ia32 Backend transformation: CJmp created to save a cmp/test" },
86 { FS_BE_IA32_2ADDRCPY, "ia32 Backend transformation: Copy created due to 2-Addresscode constraints" },
87 { FS_BE_IA32_SPILL2ST, "ia32 Backend transformation: Created Store for a Spill" },
88 { FS_BE_IA32_RELOAD2LD, "ia32 Backend transformation: Created Load for a Reload" },
89 { FS_BE_IA32_SUB2NEGADD, "ia32 Backend transformation: Created Neg-Add for a Sub due to 2-Addresscode constraints" },
90 { FS_BE_IA32_LEA2ADD, "ia32 Backend transformation: Transformed Lea back into Add" },
93 static const char *if_conv_names[IF_RESULT_LAST] = {
95 "if conv side effect ",
96 "if conv Phi node found ",
97 "if conv to deep DAG's ",
98 "if conv bad control flow ",
99 "if conv denied by arch ",
103 * dumps a opcode hash into human readable form
105 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
109 counter_t f_new_node;
113 cnt_clr(&f_new_node);
116 fprintf(dmp->f, "%-16s %-8s %-8s %-8s\n", "Opcode", "alive", "created", "->Id");
117 foreach_pset(set, entry) {
118 fprintf(dmp->f, "%-16s %8u %8u %8u\n",
119 get_id_str(entry->op->name),
120 cnt_to_uint(&entry->cnt_alive),
121 cnt_to_uint(&entry->new_node),
122 cnt_to_uint(&entry->into_Id)
125 cnt_add(&f_alive, &entry->cnt_alive);
126 cnt_add(&f_new_node, &entry->new_node);
127 cnt_add(&f_Id, &entry->into_Id);
129 fprintf(dmp->f, "-------------------------------------------\n");
130 fprintf(dmp->f, "%-16s %8u %8u %8u\n", "Sum",
131 cnt_to_uint(&f_alive),
132 cnt_to_uint(&f_new_node),
138 * dumps an optimization hash into human readable form
140 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
142 assert(index < ARR_SIZE(opt_names) && "index out of range");
143 assert(opt_names[index].kind == index && "opt_names broken");
145 if (pset_count(set) > 0) {
148 fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
149 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
151 foreach_pset(set, entry) {
152 fprintf(dmp->f, "%-16s %8u\n",
153 get_id_str(entry->op->name), cnt_to_uint(&entry->count));
159 * dumps the register pressure for each block and for each register class
161 static void simple_dump_be_block_reg_pressure(dumper_t *dmp, graph_entry_t *entry)
163 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
164 reg_pressure_entry_t *rp_entry;
166 /* return if no be statistic information available */
170 fprintf(dmp->f, "\nREG PRESSURE:\n");
171 fprintf(dmp->f, "%12s", "Block Nr");
173 /* print table head (register class names) */
174 foreach_pset(b_entry->reg_pressure, rp_entry)
175 fprintf(dmp->f, "%15s", rp_entry->class_name);
176 fprintf(dmp->f, "\n");
178 /* print the reg pressure for all blocks and register classes */
179 for (/* b_entry is already initialized */ ;
181 b_entry = pset_next(entry->be_block_hash)) {
182 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
184 foreach_pset(b_entry->reg_pressure, rp_entry)
185 fprintf(dmp->f, "%15d", rp_entry->pressure);
186 fprintf(dmp->f, "\n");
190 /** prints a distribution entry */
191 static void simple_dump_distrib_entry(const distrib_entry_t *entry, void *env)
194 fprintf(dmp_f, "%12d", cnt_to_uint(&entry->cnt));
198 * dumps the distribution of the amount of ready nodes for each block
200 static void simple_dump_be_block_sched_ready(dumper_t *dmp, graph_entry_t *entry)
202 if (pset_count(entry->be_block_hash) > 0) {
203 be_block_entry_t *b_entry;
206 fprintf(dmp->f, "\nSCHEDULING: NUMBER OF READY NODES\n");
207 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s %12s\n",
208 "Block Nr", "1 node", "2 nodes", "3 nodes", "4 nodes", "5 or more", "AVERAGE");
210 foreach_pset(entry->be_block_hash, b_entry) {
211 /* this ensures that all keys from 1 to 5 are in the table */
212 for (i = 1; i < 6; ++i)
213 stat_insert_int_distrib_tbl(b_entry->sched_ready, i);
215 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
216 stat_iterate_distrib_tbl(b_entry->sched_ready, simple_dump_distrib_entry, dmp->f);
217 fprintf(dmp->f, "%12.2lf", stat_calc_avg_distrib_tbl(b_entry->sched_ready));
218 fprintf(dmp->f, "\n");
224 * Adds the counter for given entry to another distribution table.
226 static void add_distrib_entry(const distrib_entry_t *entry, void *env) {
227 distrib_tbl_t *sum_tbl = env;
229 stat_add_int_distrib_tbl(sum_tbl, (int)(entry->object), &entry->cnt);
233 * dumps permutation statistics for one and block and one class
235 static void simple_dump_be_block_permstat_class(dumper_t *dmp, perm_class_entry_t *entry)
237 perm_stat_entry_t *ps_ent;
238 distrib_tbl_t *sum_chains = stat_new_int_distrib_tbl();
239 distrib_tbl_t *sum_cycles = stat_new_int_distrib_tbl();
243 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s\n",
252 foreach_pset(entry->perm_stat, ps_ent) {
253 fprintf(dmp->f, "%12d %12d %12d %12d %12d %12d\n",
256 stat_get_count_distrib_tbl(ps_ent->chains),
257 stat_get_count_distrib_tbl(ps_ent->cycles),
262 /* sum up distribution table for chains */
263 stat_iterate_distrib_tbl(ps_ent->chains, add_distrib_entry, sum_chains);
265 /* sum up distribution table for cycles */
266 stat_iterate_distrib_tbl(ps_ent->cycles, add_distrib_entry, sum_cycles);
269 /* print chain distribution for all perms of this class in this block */
270 fprintf(dmp->f, "chain distribution:\n");
272 /* add all missing entries to chain distribution table */
273 for (i = 1; i <= entry->n_regs; i++) {
274 snprintf(buf, sizeof(buf), "length %d", i);
275 fprintf(dmp->f, "%12s", buf);
276 stat_insert_int_distrib_tbl(sum_chains, i);
278 fprintf(dmp->f, "\n");
279 stat_iterate_distrib_tbl(sum_chains, simple_dump_distrib_entry, dmp->f);
280 fprintf(dmp->f, "\n");
282 /* print cycle distribution for all perms of this class in this block */
283 fprintf(dmp->f, "cycle distribution:\n");
285 /* add all missing entries to cycle distribution table */
286 for (i = 1; i <= entry->n_regs; i++) {
287 snprintf(buf, sizeof(buf), "length %d", i);
288 fprintf(dmp->f, "%12s", buf);
289 stat_insert_int_distrib_tbl(sum_cycles, i);
291 fprintf(dmp->f, "\n");
292 stat_iterate_distrib_tbl(sum_cycles, simple_dump_distrib_entry, dmp->f);
293 fprintf(dmp->f, "\n");
295 /* delete temporary sum distribution tables */
296 stat_delete_distrib_tbl(sum_chains);
297 stat_delete_distrib_tbl(sum_cycles);
302 * dumps statistics about perms
304 static void simple_dump_be_block_permstat(dumper_t *dmp, graph_entry_t *entry)
306 if (pset_count(entry->be_block_hash) > 0) {
307 be_block_entry_t *b_entry;
309 fprintf(dmp->f, "\nPERMUTATION STATISTICS BEGIN:\n");
310 foreach_pset(entry->be_block_hash, b_entry) {
311 perm_class_entry_t *pc_ent;
313 fprintf(dmp->f, "BLOCK %ld:\n", b_entry->block_nr);
315 if (b_entry->perm_class_stat)
316 foreach_pset(b_entry->perm_class_stat, pc_ent) {
317 fprintf(dmp->f, "register class %s:\n", pc_ent->class_name);
318 simple_dump_be_block_permstat_class(dmp, pc_ent);
322 fprintf(dmp->f, "PERMUTATION STATISTICS END\n");
327 * dumps the number of real_function_call optimization
329 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
334 if (! cnt_eq(cnt, 0)) {
335 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
336 fprintf(dmp->f, "%-16s %8u\n", "Call", cnt_to_uint(cnt));
341 * dumps the number of tail_recursion optimization
343 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
348 if (num_tail_recursion > 0) {
349 fprintf(dmp->f, "\nTail recursion optimized:\n");
350 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
355 * dumps the edges count
357 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
362 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt_to_uint(cnt));
368 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
370 int i, dump_opts = 1;
371 block_entry_t *b_entry;
372 extbb_entry_t *eb_entry;
378 ir_graph *const_irg = get_const_code_irg();
380 if (entry->irg == const_irg)
381 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
384 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
386 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
389 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
390 " was inlined : %u\n"
391 " got inlined : %u\n"
392 " strength red : %u\n"
393 " leaf function : %s\n"
394 " calls only leaf functions : %s\n"
398 " indirect calls : %u\n",
399 entry->is_deleted ? "DELETED " : "",
400 cnt_to_uint(&entry->cnt_walked), cnt_to_uint(&entry->cnt_walked_blocks),
401 cnt_to_uint(&entry->cnt_was_inlined),
402 cnt_to_uint(&entry->cnt_got_inlined),
403 cnt_to_uint(&entry->cnt_strength_red),
404 entry->is_leaf ? "YES" : "NO",
405 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
406 entry->is_recursive ? "YES" : "NO",
407 entry->is_chain_call ? "YES" : "NO",
408 cnt_to_uint(&entry->cnt_all_calls),
409 cnt_to_uint(&entry->cnt_indirect_calls)
412 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
413 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], cnt_to_uint(&entry->cnt_if_conv[i]));
417 fprintf(dmp->f, "\nGlobals counts:\n");
418 fprintf(dmp->f, "--------------\n");
422 simple_dump_opcode_hash(dmp, entry->opcode_hash);
423 simple_dump_edges(dmp, &entry->cnt_edges);
425 /* effects of optimizations */
429 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
430 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
432 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
433 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
436 /* dump block info */
437 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
438 foreach_pset(entry->block_hash, b_entry) {
439 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
441 cnt_to_uint(&b_entry->cnt_nodes),
442 cnt_to_uint(&b_entry->cnt_edges),
443 cnt_to_uint(&b_entry->cnt_in_edges),
444 cnt_to_uint(&b_entry->cnt_out_edges),
445 cnt_to_uint(&b_entry->cnt_phi_data),
446 cnt_to_dbl(&b_entry->cnt_edges) / cnt_to_dbl(&b_entry->cnt_nodes)
450 /* dump block reg pressure */
451 simple_dump_be_block_reg_pressure(dmp, entry);
453 /* dump block ready nodes distribution */
454 simple_dump_be_block_sched_ready(dmp, entry);
456 /* dump block permutation statistics */
457 simple_dump_be_block_permstat(dmp, entry);
459 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB && entry->extbb_hash) {
460 /* dump extended block info */
461 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
462 foreach_pset(entry->extbb_hash, eb_entry) {
463 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
465 cnt_to_uint(&eb_entry->cnt_nodes),
466 cnt_to_uint(&eb_entry->cnt_edges),
467 cnt_to_uint(&eb_entry->cnt_in_edges),
468 cnt_to_uint(&eb_entry->cnt_out_edges),
469 cnt_to_uint(&eb_entry->cnt_phi_data),
470 cnt_to_dbl(&eb_entry->cnt_edges) / cnt_to_dbl(&eb_entry->cnt_nodes)
480 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
490 fprintf(dmp->f, "\nConstant Information:\n");
491 fprintf(dmp->f, "---------------------\n");
493 fprintf(dmp->f, "\nBit usage for integer constants\n");
494 fprintf(dmp->f, "-------------------------------\n");
496 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
497 fprintf(dmp->f, "%5d %12u\n", i + 1, cnt_to_uint(&tbl->int_bits_count[i]));
498 cnt_add(&sum, &tbl->int_bits_count[i]);
500 fprintf(dmp->f, "-------------------------------\n");
502 fprintf(dmp->f, "\nFloating point constants classification\n");
503 fprintf(dmp->f, "--------------------------------------\n");
504 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
505 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), cnt_to_uint(&tbl->floats[i]));
506 cnt_add(&sum, &tbl->floats[i]);
508 fprintf(dmp->f, "--------------------------------------\n");
510 fprintf(dmp->f, "other %12u\n", cnt_to_uint(&tbl->others));
511 cnt_add(&sum, &tbl->others);
512 fprintf(dmp->f, "-------------------------------\n");
514 fprintf(dmp->f, "sum %12u\n", cnt_to_uint(&sum));
518 * initialize the simple dumper
520 static void simple_init(dumper_t *dmp, const char *name)
524 snprintf(fname, sizeof(fname), "%s.txt", name);
525 dmp->f = fopen(fname, "w");
532 * finishes the simple dumper
534 static void simple_finish(dumper_t *dmp)
542 * the simple human readable dumper
544 const dumper_t simple_dumper = {
546 simple_dump_const_tbl,
553 FOURCC('S', 'M', 'P', 'L'),
556 /* ---------------------------------------------------------------------- */
559 * count the nodes as needed:
561 * 1 normal (data) Phi's
566 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
571 for (i = 0; i < 4; ++i)
574 foreach_pset(graph->opcode_hash, entry) {
575 if (entry->op == op_Phi) {
577 cnt_add(&cnt[1], &entry->cnt_alive);
579 else if (entry->op == dmp->status->op_PhiM) {
581 cnt_add(&cnt[2], &entry->cnt_alive);
583 else if (entry->op == op_Proj) {
585 cnt_add(&cnt[3], &entry->cnt_alive);
588 /* all other nodes */
589 cnt_add(&cnt[0], &entry->cnt_alive);
597 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
605 if (entry->irg && !entry->is_deleted) {
606 ir_graph *const_irg = get_const_code_irg();
608 if (entry->irg == const_irg) {
609 name = "<Const code Irg>";
614 name = get_entity_name(entry->ent);
616 name = "<UNKNOWN IRG>";
619 csv_count_nodes(dmp, entry, cnt);
621 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
624 cnt_to_uint(&cnt[0]),
625 cnt_to_uint(&cnt[1]),
626 cnt_to_uint(&cnt[2]),
635 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
641 * initialize the simple dumper
643 static void csv_init(dumper_t *dmp, const char *name)
647 snprintf(fname, sizeof(fname), "%s.csv", name);
648 dmp->f = fopen(fname, "a");
654 * finishes the simple dumper
656 static void csv_finish(dumper_t *dmp)
664 * the simple human readable dumper
666 const dumper_t csv_dumper = {
675 FOURCC('C', 'S', 'V', '\0')