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) {
155 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
156 reg_pressure_entry_t *rp_entry;
158 /* return if no reg pressure information available */
162 /* print table head (register classes) */
163 fprintf(dmp->f, "\nREG PRESSURE:\n");
164 fprintf(dmp->f, "%12s", "Block Nr");
165 for (rp_entry = pset_first(b_entry->reg_pressure);
167 rp_entry = pset_next(b_entry->reg_pressure))
169 fprintf(dmp->f, "%15s", get_id_str(rp_entry->id_name));
171 fprintf(dmp->f, "\n");
173 /* print the reg pressure for all blocks and register classes */
174 for (/* b_entry is already initialized */ ;
176 b_entry = pset_next(entry->be_block_hash))
178 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
179 for (rp_entry = pset_first(b_entry->reg_pressure);
181 rp_entry = pset_next(b_entry->reg_pressure))
183 fprintf(dmp->f, "%15d", rp_entry->pressure);
185 fprintf(dmp->f, "\n");
189 void dump_block_sched_ready_distrib(const distrib_entry_t *entry, void *env) {
192 snprintf(buf, sizeof(buf), "%d:%d", (int)entry->object, entry->cnt.cnt[0]);
193 fprintf(dmp_f, "%6s", buf);
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) {
200 be_block_entry_t *b_entry = pset_first(entry->be_block_hash);
202 /* return if no reg pressure information available */
206 fprintf(dmp->f, "\nSCHED READY:\n");
207 for (/* b_entry is already initialized */ ;
209 b_entry = pset_next(entry->be_block_hash))
211 fprintf(dmp->f, "BLK %6ld", b_entry->block_nr);
212 stat_iterate_distrib_tbl(b_entry->sched_ready, dump_block_sched_ready_distrib, dmp->f);
213 fprintf(dmp->f, "%6.2lf", stat_calc_mean_distrib_tbl(b_entry->sched_ready));
214 fprintf(dmp->f, "\n");
219 * dumps the number of real_function_call optimization
221 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
226 if (! cnt_eq(cnt, 0)) {
227 fprintf(dmp->f, "\nReal Function Calls optimized:\n");
228 fprintf(dmp->f, "%-16s %8u\n",
229 "Call", cnt->cnt[0]);
234 * dumps the number of tail_recursion optimization
236 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
241 if (num_tail_recursion > 0) {
242 fprintf(dmp->f, "\nTail recursion optimized:\n");
243 fprintf(dmp->f, "%-16s %8u\n", "Call", num_tail_recursion);
248 * dumps the edges count
250 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
255 fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt->cnt[0]);
261 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
263 int i, dump_opts = 1;
264 block_entry_t *b_entry;
265 extbb_entry_t *eb_entry;
271 ir_graph *const_irg = get_const_code_irg();
273 if (entry->irg == const_irg) {
274 fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
278 fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
280 fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
283 fprintf(dmp->f, " %swalked %u over blocks %u:\n"
284 " was inlined : %u\n"
285 " got inlined : %u\n"
286 " strength red : %u\n"
287 " leaf function : %s\n"
288 " calls only leaf functions : %s\n"
292 " indirect calls : %u\n",
293 entry->is_deleted ? "DELETED " : "",
294 entry->cnt_walked.cnt[0], entry->cnt_walked_blocks.cnt[0],
295 entry->cnt_was_inlined.cnt[0],
296 entry->cnt_got_inlined.cnt[0],
297 entry->cnt_strength_red.cnt[0],
298 entry->is_leaf ? "YES" : "NO",
299 entry->is_leaf_call == LCS_NON_LEAF_CALL ? "NO" : (entry->is_leaf_call == LCS_LEAF_CALL ? "Yes" : "Maybe"),
300 entry->is_recursive ? "YES" : "NO",
301 entry->is_chain_call ? "YES" : "NO",
302 entry->cnt_all_calls.cnt[0],
303 entry->cnt_indirect_calls.cnt[0]
306 for (i = 0; i < sizeof(entry->cnt_if_conv)/sizeof(entry->cnt_if_conv[0]); ++i) {
307 fprintf(dmp->f, " %s : %u\n", if_conv_names[i], entry->cnt_if_conv[i].cnt[0]);
312 fprintf(dmp->f, "\nGlobals counts:\n");
313 fprintf(dmp->f, "--------------\n");
317 simple_dump_opcode_hash(dmp, entry->opcode_hash);
318 simple_dump_edges(dmp, &entry->cnt_edges);
320 /* effects of optimizations */
324 simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
325 simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
327 for (i = 0; i < sizeof(entry->opt_hash)/sizeof(entry->opt_hash[0]); ++i) {
328 simple_dump_opt_hash(dmp, entry->opt_hash[i], i);
331 /* dump block info */
332 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Block Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
333 for (b_entry = pset_first(entry->block_hash);
335 b_entry = pset_next(entry->block_hash)) {
336 fprintf(dmp->f, "BLK %6ld %12u %12u %12u %12u %12u %4.8f\n",
338 b_entry->cnt_nodes.cnt[0],
339 b_entry->cnt_edges.cnt[0],
340 b_entry->cnt_in_edges.cnt[0],
341 b_entry->cnt_out_edges.cnt[0],
342 b_entry->cnt_phi_data.cnt[0],
343 (double)b_entry->cnt_edges.cnt[0] / (double)b_entry->cnt_nodes.cnt[0]
347 /* dump block reg pressure */
348 simple_dump_be_block_reg_pressure(dmp, entry);
350 /* dump block ready nodes distribution */
351 simple_dump_be_block_sched_ready(dmp, entry);
353 if (dmp->status->stat_options & FIRMSTAT_COUNT_EXTBB) {
354 /* dump extended block info */
355 fprintf(dmp->f, "\n%12s %12s %12s %12s %12s %12s %12s\n", "Extbb Nr", "Nodes", "intern E", "incoming E", "outgoing E", "Phi", "quot");
356 for (eb_entry = pset_first(entry->extbb_hash);
358 eb_entry = pset_next(entry->extbb_hash)) {
359 fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
361 eb_entry->cnt_nodes.cnt[0],
362 eb_entry->cnt_edges.cnt[0],
363 eb_entry->cnt_in_edges.cnt[0],
364 eb_entry->cnt_out_edges.cnt[0],
365 eb_entry->cnt_phi_data.cnt[0],
366 (double)eb_entry->cnt_edges.cnt[0] / (double)eb_entry->cnt_nodes.cnt[0]
376 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
386 fprintf(dmp->f, "\nConstant Information:\n");
387 fprintf(dmp->f, "---------------------\n");
389 fprintf(dmp->f, "\nBit usage for integer constants\n");
390 fprintf(dmp->f, "-------------------------------\n");
392 for (i = 0; i < ARR_SIZE(tbl->int_bits_count); ++i) {
393 fprintf(dmp->f, "%5d %12u\n", i + 1, tbl->int_bits_count[i].cnt[0]);
394 cnt_add(&sum, &tbl->int_bits_count[i]);
396 fprintf(dmp->f, "-------------------------------\n");
398 fprintf(dmp->f, "\nFloating point constants classification\n");
399 fprintf(dmp->f, "--------------------------------------\n");
400 for (i = 0; i < ARR_SIZE(tbl->floats); ++i) {
401 fprintf(dmp->f, "%-10s %12u\n", stat_fc_name(i), tbl->floats[i].cnt[0]);
402 cnt_add(&sum, &tbl->floats[i]);
404 fprintf(dmp->f, "--------------------------------------\n");
406 fprintf(dmp->f, "other %12u\n", tbl->others.cnt[0]);
407 cnt_add(&sum, &tbl->others);
408 fprintf(dmp->f, "-------------------------------\n");
410 fprintf(dmp->f, "sum %12u\n", sum.cnt[0]);
414 * initialize the simple dumper
416 static void simple_init(dumper_t *dmp, const char *name)
420 snprintf(fname, sizeof(fname), "%s.txt", name);
421 dmp->f = fopen(fname, "w");
428 * finishes the simple dumper
430 static void simple_finish(dumper_t *dmp)
438 * the simple human readable dumper
440 const dumper_t simple_dumper = {
442 simple_dump_const_tbl,
450 /* ---------------------------------------------------------------------- */
453 * count the nodes as needed:
455 * 1 normal (data) Phi's
460 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
465 for (i = 0; i < 4; ++i)
468 for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
469 if (entry->op == op_Phi) {
471 cnt_add(&cnt[1], &entry->cnt_alive);
473 else if (entry->op == dmp->status->op_PhiM) {
475 cnt_add(&cnt[2], &entry->cnt_alive);
477 else if (entry->op == op_Proj) {
479 cnt_add(&cnt[3], &entry->cnt_alive);
482 /* all other nodes */
483 cnt_add(&cnt[0], &entry->cnt_alive);
491 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
499 if (entry->irg && !entry->is_deleted) {
500 ir_graph *const_irg = get_const_code_irg();
502 if (entry->irg == const_irg) {
503 name = "<Const code Irg>";
508 name = get_entity_name(entry->ent);
510 name = "<UNKNOWN IRG>";
513 csv_count_nodes(dmp, entry, cnt);
515 fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
529 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
535 * initialize the simple dumper
537 static void csv_init(dumper_t *dmp, const char *name)
541 snprintf(fname, sizeof(fname), "%s.csv", name);
542 dmp->f = fopen(fname, "a");
549 * finishes the simple dumper
551 static void csv_finish(dumper_t *dmp)
559 * the simple human readable dumper
561 const dumper_t csv_dumper = {