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 for (entry = pset_first(set); entry; entry = pset_next(set)) {
117 fprintf(dmp->f, "%-16s %8u %8u %8u\n",
118 get_id_str(entry->op->name),
119 cnt_to_int(&entry->cnt_alive),
120 cnt_to_int(&entry->new_node),
121 cnt_to_int(&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_int(&f_alive),
131 cnt_to_int(&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 opt_entry_t *entry = pset_first(set);
143 assert(index < ARR_SIZE(opt_names) && "index out of range");
144 assert(opt_names[index].kind == index && "opt_names broken");
146 fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
147 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
149 for (; entry; entry = pset_next(set)) {
150 fprintf(dmp->f, "%-16s %8u\n",
151 get_id_str(entry->op->name), cnt_to_int(&entry->count));
157 * dumps the register pressure for each block and for each register class
159 static void simple_dump_be_block_reg_pressure(dumper_t *dmp, graph_entry_t *entry)
161 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
162 reg_pressure_entry_t *rp_entry;
164 /* return if no be statistic information available */
168 fprintf(dmp->f, "\nREG PRESSURE:\n");
169 fprintf(dmp->f, "%12s", "Block Nr");
171 /* print table head (register class names) */
172 for (rp_entry = pset_first(b_entry->reg_pressure);
174 rp_entry = pset_next(b_entry->reg_pressure))
176 fprintf(dmp->f, "%15s", rp_entry->class_name);
178 fprintf(dmp->f, "\n");
180 /* print the reg pressure for all blocks and register classes */
181 for (/* b_entry is already initialized */ ;
183 b_entry = pset_next(entry->be_block_hash))
185 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
187 for (rp_entry = pset_first(b_entry->reg_pressure);
189 rp_entry = pset_next(b_entry->reg_pressure))
191 fprintf(dmp->f, "%15d", rp_entry->pressure);
193 fprintf(dmp->f, "\n");
197 /** prints a distribution entry */
198 void dump_block_sched_ready_distrib(const distrib_entry_t *entry, void *env)
201 fprintf(dmp_f, "%12d", cnt_to_int(&entry->cnt));
205 * dumps the distribution of the amount of ready nodes for each block
207 static void simple_dump_be_block_sched_ready(dumper_t *dmp, graph_entry_t *entry)
209 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
212 /* return if no be statistic information available */
216 fprintf(dmp->f, "\nSCHEDULING: NUMBER OF READY NODES\n");
217 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s %12s\n",
218 "Block Nr", "1 node", "2 nodes", "3 nodes", "4 nodes", "5 or more", "AVERAGE");
220 for (/* b_entry is already initialized */ ;
222 b_entry = pset_next(entry->be_block_hash))
224 /* this ensures that all keys from 1 to 5 are in the table */
225 for (i = 1; i < 6; i++)
226 stat_insert_int_distrib_tbl(b_entry->sched_ready, i);
228 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
229 stat_iterate_distrib_tbl(b_entry->sched_ready, dump_block_sched_ready_distrib, dmp->f);
230 fprintf(dmp->f, "%12.2lf", stat_calc_avg_distrib_tbl(b_entry->sched_ready));
231 fprintf(dmp->f, "\n");
236 * dumps permutation statistics for one and block and one class
238 static void simple_dump_be_block_permstat_class(dumper_t *dmp, perm_class_entry_t *entry)
240 perm_stat_entry_t *ps_ent;
242 fprintf(dmp->f, "%12s %12s %12s %12s\n", "size", "real size", "# chains", "# cycles");
243 for (ps_ent = pset_first(entry->perm_stat);
245 ps_ent = pset_next(entry->perm_stat))
247 fprintf(dmp->f, "%12d %12d %12d %12d\n",
250 stat_get_count_distrib_tbl(ps_ent->chains),
251 stat_get_count_distrib_tbl(ps_ent->cycles)
257 * dumps statistics about perms
259 static void simple_dump_be_block_permstat(dumper_t *dmp, graph_entry_t *entry)
261 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
263 /* return if no be statistic information available */
267 fprintf(dmp->f, "\nPERMUTATION STATISTICS BEGIN:\n");
268 for (/* b_entry is already initialized */ ;
270 b_entry = pset_next(entry->be_block_hash))
272 perm_class_entry_t *pc_ent;
274 fprintf(dmp->f, "BLOCK %ld:\n", b_entry->block_nr);
276 if (! b_entry->perm_class_stat)
279 for (pc_ent = pset_first(b_entry->perm_class_stat);
281 pc_ent = pset_next(b_entry->perm_class_stat))
283 fprintf(dmp->f, "register class %s:\n", pc_ent->class_name);
284 simple_dump_be_block_permstat_class(dmp, pc_ent);
288 fprintf(dmp->f, "PERMUTATION STATISTICS END\n");
292 * dumps the number of real_function_call optimization
294 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
299 if (! cnt_eq(cnt, 0)) {
300 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
301 fprintf(dmp->f, "%-16s %8u\n", "Call", cnt_to_int(cnt));
306 * dumps the number of tail_recursion optimization
308 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
313 if (num_tail_recursion > 0) {
314 fprintf(dmp->f, "\nTail recursion optimized:\n");
315 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
320 * dumps the edges count
322 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
327 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt_to_int(cnt));
333 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
335 int i, dump_opts = 1;
336 block_entry_t *b_entry;
337 extbb_entry_t *eb_entry;
343 ir_graph *const_irg = get_const_code_irg();
345 if (entry->irg == const_irg) {
346 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
350 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
352 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
355 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
356 " was inlined : %u\n"
357 " got inlined : %u\n"
358 " strength red : %u\n"
359 " leaf function : %s\n"
360 " calls only leaf functions : %s\n"
364 " indirect calls : %u\n",
365 entry->is_deleted ? "DELETED " : "",
366 cnt_to_int(&entry->cnt_walked), cnt_to_int(&entry->cnt_walked_blocks),
367 cnt_to_int(&entry->cnt_was_inlined),
368 cnt_to_int(&entry->cnt_got_inlined),
369 cnt_to_int(&entry->cnt_strength_red),
370 entry->is_leaf ? "YES" : "NO",
371 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
372 entry->is_recursive ? "YES" : "NO",
373 entry->is_chain_call ? "YES" : "NO",
374 cnt_to_int(&entry->cnt_all_calls),
375 cnt_to_int(&entry->cnt_indirect_calls)
378 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
379 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], cnt_to_int(&entry->cnt_if_conv[i]));
384 fprintf(dmp->f, "\nGlobals counts:\n");
385 fprintf(dmp->f, "--------------\n");
389 simple_dump_opcode_hash(dmp, entry->opcode_hash);
390 simple_dump_edges(dmp, &entry->cnt_edges);
392 /* effects of optimizations */
396 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
397 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
399 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
400 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
403 /* dump block info */
404 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
405 for (b_entry = pset_first(entry->block_hash);
407 b_entry = pset_next(entry->block_hash))
409 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
411 cnt_to_int(&b_entry->cnt_nodes),
412 cnt_to_int(&b_entry->cnt_edges),
413 cnt_to_int(&b_entry->cnt_in_edges),
414 cnt_to_int(&b_entry->cnt_out_edges),
415 cnt_to_int(&b_entry->cnt_phi_data),
416 cnt_to_dbl(&b_entry->cnt_edges) / cnt_to_dbl(&b_entry->cnt_nodes)
420 /* dump block reg pressure */
421 simple_dump_be_block_reg_pressure(dmp, entry);
423 /* dump block ready nodes distribution */
424 simple_dump_be_block_sched_ready(dmp, entry);
426 /* dump block permutation statistics */
427 simple_dump_be_block_permstat(dmp, entry);
429 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB) {
430 /* dump extended block info */
431 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
432 for (eb_entry = pset_first(entry->extbb_hash);
434 eb_entry = pset_next(entry->extbb_hash))
436 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
438 cnt_to_int(&eb_entry->cnt_nodes),
439 cnt_to_int(&eb_entry->cnt_edges),
440 cnt_to_int(&eb_entry->cnt_in_edges),
441 cnt_to_int(&eb_entry->cnt_out_edges),
442 cnt_to_int(&eb_entry->cnt_phi_data),
443 cnt_to_dbl(&eb_entry->cnt_edges) / cnt_to_dbl(&eb_entry->cnt_nodes)
453 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
463 fprintf(dmp->f, "\nConstant Information:\n");
464 fprintf(dmp->f, "---------------------\n");
466 fprintf(dmp->f, "\nBit usage for integer constants\n");
467 fprintf(dmp->f, "-------------------------------\n");
469 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
470 fprintf(dmp->f, "%5d %12u\n", i + 1, cnt_to_int(&tbl->int_bits_count[i]));
471 cnt_add(&sum, &tbl->int_bits_count[i]);
473 fprintf(dmp->f, "-------------------------------\n");
475 fprintf(dmp->f, "\nFloating point constants classification\n");
476 fprintf(dmp->f, "--------------------------------------\n");
477 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
478 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), cnt_to_int(&tbl->floats[i]));
479 cnt_add(&sum, &tbl->floats[i]);
481 fprintf(dmp->f, "--------------------------------------\n");
483 fprintf(dmp->f, "other %12u\n", cnt_to_int(&tbl->others));
484 cnt_add(&sum, &tbl->others);
485 fprintf(dmp->f, "-------------------------------\n");
487 fprintf(dmp->f, "sum %12u\n", cnt_to_int(&sum));
491 * initialize the simple dumper
493 static void simple_init(dumper_t *dmp, const char *name)
497 snprintf(fname, sizeof(fname), "%s.txt", name);
498 dmp->f = fopen(fname, "w");
505 * finishes the simple dumper
507 static void simple_finish(dumper_t *dmp)
515 * the simple human readable dumper
517 const dumper_t simple_dumper = {
519 simple_dump_const_tbl,
527 /* ---------------------------------------------------------------------- */
530 * count the nodes as needed:
532 * 1 normal (data) Phi's
537 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
542 for (i = 0; i < 4; ++i)
545 for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
546 if (entry->op == op_Phi) {
548 cnt_add(&cnt[1], &entry->cnt_alive);
550 else if (entry->op == dmp->status->op_PhiM) {
552 cnt_add(&cnt[2], &entry->cnt_alive);
554 else if (entry->op == op_Proj) {
556 cnt_add(&cnt[3], &entry->cnt_alive);
559 /* all other nodes */
560 cnt_add(&cnt[0], &entry->cnt_alive);
568 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
576 if (entry->irg && !entry->is_deleted) {
577 ir_graph *const_irg = get_const_code_irg();
579 if (entry->irg == const_irg) {
580 name = "<Const code Irg>";
585 name = get_entity_name(entry->ent);
587 name = "<UNKNOWN IRG>";
590 csv_count_nodes(dmp, entry, cnt);
592 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
606 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
612 * initialize the simple dumper
614 static void csv_init(dumper_t *dmp, const char *name)
618 snprintf(fname, sizeof(fname), "%s.csv", name);
619 dmp->f = fopen(fname, "a");
626 * finishes the simple dumper
628 static void csv_finish(dumper_t *dmp)
636 * the simple human readable dumper
638 const dumper_t csv_dumper = {