3db58b77bb3cddce0d2ee92f797118a8044e2b1d
[libfirm] / ir / stat / stat_dmp.c
1 /*
2  * Project:     libFIRM
3  * File name:   ir/ir/stat_dmp.c
4  * Purpose:     Statistics for Firm.
5  * Author:      Michael Beck
6  * Created:
7  * CVS-ID:      $Id$
8  * Copyright:   (c) 2004 Universität Karlsruhe
9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
10  */
11 #ifdef HAVE_CONFIG_H
12 # include "config.h"
13 #endif
14
15 #include "stat_dmp.h"
16 #include "irhooks.h"
17
18 /**
19  * names of the optimizations
20  */
21 static const struct {
22   hook_opt_kind kind;
23   const char    *name;
24 } opt_names[] = {
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" },
90 };
91
92 static const char *if_conv_names[IF_RESULT_LAST] = {
93   "if conv done             ",
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   ",
99 };
100
101 /**
102  * dumps a opcode hash into human readable form
103  */
104 static void simple_dump_opcode_hash(dumper_t *dmp, pset *set)
105 {
106   node_entry_t *entry;
107   counter_t f_alive;
108   counter_t f_new_node;
109   counter_t f_Id;
110
111   cnt_clr(&f_alive);
112   cnt_clr(&f_new_node);
113   cnt_clr(&f_Id);
114
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]);
119
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);
123   }
124   fprintf(dmp->f, "-------------------------------------------\n");
125   fprintf(dmp->f, "%-16s %8u %8u %8u\n", "Sum",
126      f_alive.cnt[0],
127      f_new_node.cnt[0],
128      f_Id.cnt[0]);
129 }
130
131 /**
132  * dumps an optimization hash into human readable form
133  */
134 static void simple_dump_opt_hash(dumper_t *dmp, pset *set, int index)
135 {
136   opt_entry_t *entry = pset_first(set);
137
138   assert(index < ARR_SIZE(opt_names) && "index out of range");
139   assert(opt_names[index].kind == index && "opt_names broken");
140   if (entry) {
141     fprintf(dmp->f, "\n%s:\n", opt_names[index].name);
142     fprintf(dmp->f, "%-16s %-8s\n", "Opcode", "deref");
143
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]);
147     }
148   }
149 }
150
151 /**
152  * dumps the register pressure for each block and for each register class
153  */
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;
157
158   /* return if no reg pressure information available */
159   if (! b_entry)
160           return;
161
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);
166        rp_entry;
167            rp_entry = pset_next(b_entry->reg_pressure))
168   {
169     fprintf(dmp->f, "%15s", get_id_str(rp_entry->id_name));
170   }
171   fprintf(dmp->f, "\n");
172
173   /* print the reg pressure for all blocks and register classes */
174   for (/* b_entry is already initialized */ ;
175        b_entry;
176            b_entry = pset_next(entry->be_block_hash))
177   {
178         fprintf(dmp->f, "BLK   %6ld", b_entry->block_nr);
179         for (rp_entry = pset_first(b_entry->reg_pressure);
180              rp_entry;
181                  rp_entry = pset_next(b_entry->reg_pressure))
182         {
183       fprintf(dmp->f, "%15d", rp_entry->pressure);
184         }
185     fprintf(dmp->f, "\n");
186   }
187 }
188
189 void dump_block_sched_ready_distrib(const distrib_entry_t *entry, void *env) {
190   FILE *dmp_f = env;
191   char buf[12];
192   snprintf(buf, sizeof(buf), "%d:%d", (int)entry->object, entry->cnt.cnt[0]);
193   fprintf(dmp_f, "%6s", buf);
194 }
195
196 /**
197  * dumps the distribution of the amount of ready nodes for each block
198  */
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);
201
202   /* return if no reg pressure information available */
203   if (! b_entry)
204           return;
205
206   fprintf(dmp->f, "\nSCHED READY:\n");
207   for (/* b_entry is already initialized */ ;
208        b_entry;
209            b_entry = pset_next(entry->be_block_hash))
210   {
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");
215   }
216 }
217
218 /**
219  * dumps the number of real_function_call optimization
220  */
221 static void simple_dump_real_func_calls(dumper_t *dmp, counter_t *cnt)
222 {
223   if (! dmp->f)
224     return;
225
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]);
230   }
231 }
232
233 /**
234  * dumps the number of tail_recursion optimization
235  */
236 static void simple_dump_tail_recursion(dumper_t *dmp, unsigned num_tail_recursion)
237 {
238   if (! dmp->f)
239     return;
240
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);
244   }
245 }
246
247 /**
248  * dumps the edges count
249  */
250 static void simple_dump_edges(dumper_t *dmp, counter_t *cnt)
251 {
252   if (! dmp->f)
253     return;
254
255   fprintf(dmp->f, "%-16s %8d\n", "Edges", cnt->cnt[0]);
256 }
257
258 /**
259  * dumps the IRG
260  */
261 static void simple_dump_graph(dumper_t *dmp, graph_entry_t *entry)
262 {
263   int i, dump_opts = 1;
264   block_entry_t *b_entry;
265   extbb_entry_t *eb_entry;
266
267   if (! dmp->f)
268     return;
269
270   if (entry->irg) {
271     ir_graph *const_irg = get_const_code_irg();
272
273     if (entry->irg == const_irg) {
274       fprintf(dmp->f, "\nConst code Irg %p", (void *)entry->irg);
275     }
276     else {
277       if (entry->ent)
278         fprintf(dmp->f, "\nEntity %s, Irg %p", get_entity_ld_name(entry->ent), (void *)entry->irg);
279       else
280         fprintf(dmp->f, "\nIrg %p", (void *)entry->irg);
281     }
282
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"
289                 " recursive                 : %s\n"
290                 " chain call                : %s\n"
291         " calls                     : %u\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]
304         );
305
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]);
308     }
309
310   }
311   else {
312     fprintf(dmp->f, "\nGlobals counts:\n");
313     fprintf(dmp->f, "--------------\n");
314     dump_opts = 0;
315   }
316
317   simple_dump_opcode_hash(dmp, entry->opcode_hash);
318   simple_dump_edges(dmp, &entry->cnt_edges);
319
320   /* effects of optimizations */
321   if (dump_opts) {
322     int i;
323
324     simple_dump_real_func_calls(dmp, &entry->cnt_real_func_call);
325     simple_dump_tail_recursion(dmp, entry->num_tail_recursion);
326
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);
329     }
330
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);
334                b_entry;
335                b_entry = pset_next(entry->block_hash)) {
336       fprintf(dmp->f, "BLK   %6ld %12u %12u %12u %12u %12u %4.8f\n",
337               b_entry->block_nr,
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]
344       );
345     }
346
347     /* dump block reg pressure */
348         simple_dump_be_block_reg_pressure(dmp, entry);
349
350     /* dump block ready nodes distribution */
351         simple_dump_be_block_sched_ready(dmp, entry);
352
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);
357            eb_entry;
358            eb_entry = pset_next(entry->extbb_hash)) {
359         fprintf(dmp->f, "ExtBB %6ld %12u %12u %12u %12u %12u %4.8f\n",
360           eb_entry->block_nr,
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]
367         );
368       }
369     }
370   }
371 }
372
373 /**
374  * dumps the IRG
375  */
376 static void simple_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
377 {
378   int i;
379   counter_t sum;
380
381   if (! dmp->f)
382     return;
383
384   cnt_clr(&sum);
385
386   fprintf(dmp->f, "\nConstant Information:\n");
387   fprintf(dmp->f, "---------------------\n");
388
389   fprintf(dmp->f, "\nBit usage for integer constants\n");
390   fprintf(dmp->f, "-------------------------------\n");
391
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]);
395   }
396   fprintf(dmp->f, "-------------------------------\n");
397
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]);
403   }
404   fprintf(dmp->f, "--------------------------------------\n");
405
406   fprintf(dmp->f, "other %12u\n", tbl->others.cnt[0]);
407   cnt_add(&sum, &tbl->others);
408   fprintf(dmp->f, "-------------------------------\n");
409
410   fprintf(dmp->f, "sum   %12u\n", sum.cnt[0]);
411 }
412
413 /**
414  * initialize the simple dumper
415  */
416 static void simple_init(dumper_t *dmp, const char *name)
417 {
418   char fname[2048];
419
420   snprintf(fname, sizeof(fname), "%s.txt", name);
421   dmp->f = fopen(fname, "w");
422   if (! dmp->f) {
423     perror(fname);
424   }
425 }
426
427 /**
428  * finishes the simple dumper
429  */
430 static void simple_finish(dumper_t *dmp)
431 {
432   if (dmp->f)
433     fclose(dmp->f);
434   dmp->f = NULL;
435 }
436
437 /**
438  * the simple human readable dumper
439  */
440 const dumper_t simple_dumper = {
441   simple_dump_graph,
442   simple_dump_const_tbl,
443   simple_init,
444   simple_finish,
445   NULL,
446   NULL,
447   NULL,
448 };
449
450 /* ---------------------------------------------------------------------- */
451
452 /**
453  * count the nodes as needed:
454  *
455  * 1 normal (data) Phi's
456  * 2 memory Phi's
457  * 3 Proj
458  * 0 all other nodes
459  */
460 static void csv_count_nodes(dumper_t *dmp, graph_entry_t *graph, counter_t cnt[])
461 {
462   node_entry_t *entry;
463   int i;
464
465   for (i = 0; i < 4; ++i)
466     cnt_clr(&cnt[i]);
467
468   for (entry = pset_first(graph->opcode_hash); entry; entry = pset_next(graph->opcode_hash)) {
469     if (entry->op == op_Phi) {
470       /* normal Phi */
471       cnt_add(&cnt[1], &entry->cnt_alive);
472     }
473     else if (entry->op == dmp->status->op_PhiM) {
474       /* memory Phi */
475       cnt_add(&cnt[2], &entry->cnt_alive);
476     }
477     else if (entry->op == op_Proj) {
478       /* Proj */
479       cnt_add(&cnt[3], &entry->cnt_alive);
480     }
481     else {
482       /* all other nodes */
483       cnt_add(&cnt[0], &entry->cnt_alive);
484     }
485   }
486 }
487
488 /**
489  * dumps the IRG
490  */
491 static void csv_dump_graph(dumper_t *dmp, graph_entry_t *entry)
492 {
493   const char *name;
494   counter_t cnt[4];
495
496   if (! dmp->f)
497     return;
498
499   if (entry->irg && !entry->is_deleted) {
500     ir_graph *const_irg = get_const_code_irg();
501
502     if (entry->irg == const_irg) {
503       name = "<Const code Irg>";
504       return;
505     }
506     else {
507       if (entry->ent)
508         name = get_entity_name(entry->ent);
509       else
510         name = "<UNKNOWN IRG>";
511     }
512
513     csv_count_nodes(dmp, entry, cnt);
514
515     fprintf(dmp->f, "%-40s, %p, %d, %d, %d, %d\n",
516         name,
517         (void *)entry->irg,
518         cnt[0].cnt[0],
519         cnt[1].cnt[0],
520         cnt[2].cnt[0],
521         cnt[3].cnt[0]
522     );
523   }
524 }
525
526 /**
527  * dumps the IRG
528  */
529 static void csv_dump_const_tbl(dumper_t *dmp, const constant_info_t *tbl)
530 {
531   /* FIXME: NYI */
532 }
533
534 /**
535  * initialize the simple dumper
536  */
537 static void csv_init(dumper_t *dmp, const char *name)
538 {
539   char fname[2048];
540
541   snprintf(fname, sizeof(fname), "%s.csv", name);
542   dmp->f = fopen(fname, "a");
543   if (! dmp->f) {
544     perror(fname);
545   }
546 }
547
548 /**
549  * finishes the simple dumper
550  */
551 static void csv_finish(dumper_t *dmp)
552 {
553   if (dmp->f)
554     fclose(dmp->f);
555   dmp->f = NULL;
556 }
557
558 /**
559  * the simple human readable dumper
560  */
561 const dumper_t csv_dumper = {
562   csv_dump_graph,
563   csv_dump_const_tbl,
564   csv_init,
565   csv_finish,
566   NULL,
567   NULL,
568   NULL,
569 };