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), entry->cnt_alive.cnt[0], entry->new_node.cnt[0], entry->into_Id.cnt[0]);
120 cnt_add(&f_alive, &entry->cnt_alive);
121 cnt_add(&f_new_node, &entry->new_node);
122 cnt_add(&f_Id, &entry->into_Id);
124 fprintf(dmp->f, "-------------------------------------------\n");
125 fprintf(dmp->f, "%-16s %8u %8u %8u\n", "Sum",
132 * dumps an optimization hash into human readable form
134 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
136 opt_entry_t *entry = pset_first(set);
138 assert(index < ARR_SIZE(opt_names) && "index out of range");
139 assert(opt_names[index].kind == index && "opt_names broken");
141 fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
142 fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
144 for (; entry; entry = pset_next(set)) {
145 fprintf(dmp->f, "%-16s %8u\n",
146 get_id_str(entry->op->name), entry->count.cnt[0]);
152 * dumps the register pressure for each block and for each register class
154 static void simple_dump_be_block_reg_pressure(dumper_t *dmp, graph_entry_t *entry)
156 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
157 reg_pressure_entry_t *rp_entry;
159 /* return if no be statistic information available */
163 fprintf(dmp->f, "\nREG PRESSURE:\n");
164 fprintf(dmp->f, "%12s", "Block Nr");
166 /* print table head (register class names) */
167 for (rp_entry = pset_first(b_entry->reg_pressure);
169 rp_entry = pset_next(b_entry->reg_pressure))
171 fprintf(dmp->f, "%15s", rp_entry->class_name);
173 fprintf(dmp->f, "\n");
175 /* print the reg pressure for all blocks and register classes */
176 for (/* b_entry is already initialized */ ;
178 b_entry = pset_next(entry->be_block_hash))
180 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
182 for (rp_entry = pset_first(b_entry->reg_pressure);
184 rp_entry = pset_next(b_entry->reg_pressure))
186 fprintf(dmp->f, "%15d", rp_entry->pressure);
188 fprintf(dmp->f, "\n");
192 /** prints a distribution entry */
193 void dump_block_sched_ready_distrib(const distrib_entry_t *entry, void *env)
196 fprintf(dmp_f, "%12d", entry->cnt.cnt[0]);
200 * dumps the distribution of the amount of ready nodes for each block
202 static void simple_dump_be_block_sched_ready(dumper_t *dmp, graph_entry_t *entry)
204 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
207 /* return if no be statistic information available */
211 fprintf(dmp->f, "\nSCHEDULING: NUMBER OF READY NODES\n");
212 fprintf(dmp->f, "%12s %12s %12s %12s %12s %12s %12s\n",
213 "Block Nr", "1 node", "2 nodes", "3 nodes", "4 nodes", "5 or more", "AVERAGE");
215 for (/* b_entry is already initialized */ ;
217 b_entry = pset_next(entry->be_block_hash))
219 /* this ensures that all keys from 1 to 5 are in the table */
220 for (i = 1; i < 6; i++)
221 stat_insert_int_distrib_tbl(b_entry->sched_ready, i);
223 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
224 stat_iterate_distrib_tbl(b_entry->sched_ready, dump_block_sched_ready_distrib, dmp->f);
225 fprintf(dmp->f, "%12.2lf", stat_calc_avg_distrib_tbl(b_entry->sched_ready));
226 fprintf(dmp->f, "\n");
231 * dumps permutation statistics for one and block and one class
233 static void simple_dump_be_block_permstat_class(dumper_t *dmp, perm_class_entry_t *entry)
235 perm_stat_entry_t *ps_ent;
237 fprintf(dmp->f, "%12s %12s %12s %12s\n", "size", "real size", "# chains", "# cycles");
238 for (ps_ent = pset_first(entry->perm_stat);
240 ps_ent = pset_next(entry->perm_stat))
242 fprintf(dmp->f, "%12d %12d %12d %12d\n",
245 pset_count(ps_ent->chains),
246 pset_count(ps_ent->cycles)
252 * dumps statistics about perms
254 static void simple_dump_be_block_permstat(dumper_t *dmp, graph_entry_t *entry)
256 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
258 /* return if no be statistic information available */
262 fprintf(dmp->f, "\nPERMUTATION STATISTICS BEGIN:\n");
263 for (/* b_entry is already initialized */ ;
265 b_entry = pset_next(entry->be_block_hash))
267 perm_class_entry_t *pc_ent;
269 fprintf(dmp->f, "BLOCK %ld:\n", b_entry->block_nr);
271 if (! b_entry->perm_class_stat)
274 for (pc_ent = pset_first(b_entry->perm_class_stat);
276 pc_ent = pset_next(b_entry->perm_class_stat))
278 fprintf(dmp->f, "register class %s:\n", pc_ent->class_name);
279 simple_dump_be_block_permstat_class(dmp, pc_ent);
283 fprintf(dmp->f, "PERMUTATION STATISTICS END\n");
287 * dumps the number of real_function_call optimization
289 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
294 if (! cnt_eq(cnt, 0)) {
295 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
296 fprintf(dmp->f, "%-16s %8u\n", "Call", cnt->cnt[0]);
301 * dumps the number of tail_recursion optimization
303 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
308 if (num_tail_recursion > 0) {
309 fprintf(dmp->f, "\nTail recursion optimized:\n");
310 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
315 * dumps the edges count
317 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
322 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt->cnt[0]);
328 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
330 int i, dump_opts = 1;
331 block_entry_t *b_entry;
332 extbb_entry_t *eb_entry;
338 ir_graph *const_irg = get_const_code_irg();
340 if (entry->irg == const_irg) {
341 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
345 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
347 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
350 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
351 " was inlined : %u\n"
352 " got inlined : %u\n"
353 " strength red : %u\n"
354 " leaf function : %s\n"
355 " calls only leaf functions : %s\n"
359 " indirect calls : %u\n",
360 entry->is_deleted ? "DELETED " : "",
361 entry->cnt_walked.cnt[0], entry->cnt_walked_blocks.cnt[0],
362 entry->cnt_was_inlined.cnt[0],
363 entry->cnt_got_inlined.cnt[0],
364 entry->cnt_strength_red.cnt[0],
365 entry->is_leaf ? "YES" : "NO",
366 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
367 entry->is_recursive ? "YES" : "NO",
368 entry->is_chain_call ? "YES" : "NO",
369 entry->cnt_all_calls.cnt[0],
370 entry->cnt_indirect_calls.cnt[0]
373 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
374 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], entry->cnt_if_conv[i].cnt[0]);
379 fprintf(dmp->f, "\nGlobals counts:\n");
380 fprintf(dmp->f, "--------------\n");
384 simple_dump_opcode_hash(dmp, entry->opcode_hash);
385 simple_dump_edges(dmp, &entry->cnt_edges);
387 /* effects of optimizations */
391 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
392 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
394 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
395 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
398 /* dump block info */
399 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
400 for (b_entry = pset_first(entry->block_hash);
402 b_entry = pset_next(entry->block_hash))
404 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
406 b_entry->cnt_nodes.cnt[0],
407 b_entry->cnt_edges.cnt[0],
408 b_entry->cnt_in_edges.cnt[0],
409 b_entry->cnt_out_edges.cnt[0],
410 b_entry->cnt_phi_data.cnt[0],
411 (double)b_entry->cnt_edges.cnt[0] / (double)b_entry->cnt_nodes.cnt[0]
415 /* dump block reg pressure */
416 simple_dump_be_block_reg_pressure(dmp, entry);
418 /* dump block ready nodes distribution */
419 simple_dump_be_block_sched_ready(dmp, entry);
421 /* dump block permutation statistics */
422 simple_dump_be_block_permstat(dmp, entry);
424 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB) {
425 /* dump extended block info */
426 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
427 for (eb_entry = pset_first(entry->extbb_hash);
429 eb_entry = pset_next(entry->extbb_hash))
431 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
433 eb_entry->cnt_nodes.cnt[0],
434 eb_entry->cnt_edges.cnt[0],
435 eb_entry->cnt_in_edges.cnt[0],
436 eb_entry->cnt_out_edges.cnt[0],
437 eb_entry->cnt_phi_data.cnt[0],
438 (double)eb_entry->cnt_edges.cnt[0] / (double)eb_entry->cnt_nodes.cnt[0]
448 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
458 fprintf(dmp->f, "\nConstant Information:\n");
459 fprintf(dmp->f, "---------------------\n");
461 fprintf(dmp->f, "\nBit usage for integer constants\n");
462 fprintf(dmp->f, "-------------------------------\n");
464 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
465 fprintf(dmp->f, "%5d %12u\n", i + 1, tbl->int_bits_count[i].cnt[0]);
466 cnt_add(&sum, &tbl->int_bits_count[i]);
468 fprintf(dmp->f, "-------------------------------\n");
470 fprintf(dmp->f, "\nFloating point constants classification\n");
471 fprintf(dmp->f, "--------------------------------------\n");
472 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
473 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), tbl->floats[i].cnt[0]);
474 cnt_add(&sum, &tbl->floats[i]);
476 fprintf(dmp->f, "--------------------------------------\n");
478 fprintf(dmp->f, "other %12u\n", tbl->others.cnt[0]);
479 cnt_add(&sum, &tbl->others);
480 fprintf(dmp->f, "-------------------------------\n");
482 fprintf(dmp->f, "sum %12u\n", sum.cnt[0]);
486 * initialize the simple dumper
488 static void simple_init(dumper_t *dmp, const char *name)
492 snprintf(fname, sizeof(fname), "%s.txt", name);
493 dmp->f = fopen(fname, "w");
500 * finishes the simple dumper
502 static void simple_finish(dumper_t *dmp)
510 * the simple human readable dumper
512 const dumper_t simple_dumper = {
514 simple_dump_const_tbl,
522 /* ---------------------------------------------------------------------- */
525 * count the nodes as needed:
527 * 1 normal (data) Phi's
532 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
537 for (i = 0; i < 4; ++i)
540 for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
541 if (entry->op == op_Phi) {
543 cnt_add(&cnt[1], &entry->cnt_alive);
545 else if (entry->op == dmp->status->op_PhiM) {
547 cnt_add(&cnt[2], &entry->cnt_alive);
549 else if (entry->op == op_Proj) {
551 cnt_add(&cnt[3], &entry->cnt_alive);
554 /* all other nodes */
555 cnt_add(&cnt[0], &entry->cnt_alive);
563 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
571 if (entry->irg && !entry->is_deleted) {
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(dmp, entry, cnt);
587 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
601 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
607 * initialize the simple dumper
609 static void csv_init(dumper_t *dmp, const char *name)
613 snprintf(fname, sizeof(fname), "%s.csv", name);
614 dmp->f = fopen(fname, "a");
621 * finishes the simple dumper
623 static void csv_finish(dumper_t *dmp)
631 * the simple human readable dumper
633 const dumper_t csv_dumper = {