nsz Git - libfirm/blob - ir/be/becopystat.c

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                19.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #include <string.h>
  12 #include "irgraph.h"
  13 #include "irprog.h"
  14 #include "phiclass_t.h"
  15 #include "becopyopt.h"
  16 #include "becopystat.h"
  17 #include "xmalloc.h"
  18
  19 #ifdef DO_STAT
  20
  21 #define DEBUG_LVL SET_LEVEL_1
  22 static firm_dbg_module_t *dbg = NULL;
  23
  24 #define MAX_ARITY 10
  25 #define MAX_CLS_SIZE 10
  26 #define MAX_CLS_PHIS 10
  27
  28 /**
  29  * For an explanation of these values see the code of copystat_dump_pretty
  30  */
  31 enum vals_t {
  32         /* FROM HERE: PROBLEM CHARACTERIZATION */
  33
  34         I_ALL_NODES = 0,
  35         I_BLOCKS,
  36
  37         /* phi nodes */
  38         I_PHI_CNT,                      /* number of phi nodes */
  39         I_PHI_ARG_CNT,          /* number of arguments of phis */
  40         I_PHI_ARG_SELF,         /* number of arguments of phis being the phi itself */
  41         I_PHI_ARG_CONST,        /* number of arguments of phis being consts */
  42         I_PHI_ARG_PRED,         /* ... being defined in a cf-pred */
  43         I_PHI_ARG_GLOB,         /* ... being defined elsewhere */
  44         I_PHI_ARITY_S,
  45         I_PHI_ARITY_E    = I_PHI_ARITY_S+MAX_ARITY,
  46
  47         /* copy nodes */
  48         I_CPY_CNT,                      /* number of copynodes */
  49
  50         /* phi classes */
  51         I_CLS_CNT,                      /* number of phi classes */
  52         I_CLS_IF_FREE,          /* number of pc having no interference */
  53         I_CLS_IF_MAX,           /* number of possible interferences in all classes */
  54         I_CLS_IF_CNT,           /* number of actual interferences in all classes */
  55         I_CLS_SIZE_S,
  56         I_CLS_SIZE_E = I_CLS_SIZE_S+MAX_CLS_SIZE,
  57         I_CLS_PHIS_S,
  58         I_CLS_PHIS_E = I_CLS_PHIS_S+MAX_CLS_PHIS,
  59
  60         /* FROM HERE: RESULT VLAUES */
  61
  62         /* ilp values */
  63         I_ILP_TIME,                     /* !external set! solving time in seconds */
  64         I_ILP_ITER,                     /* !external set! number of simplex iterations */
  65
  66         /* copy instructions */
  67         I_COPIES_MAX,           /* !external set! max possible costs of copies*/
  68         I_COPIES_INIT,          /* !external set! number of copies in initial allocation */
  69         I_COPIES_HEUR,          /* !external set! number of copies after heuristic */
  70         I_COPIES_OPT,           /* !external set! number of copies after ilp */
  71         I_COPIES_IF,            /* !external set! number of copies inevitable due to root-arg-interf */
  72
  73         ASIZE
  74 };
  75
  76 /**
  77  * Holds current values. Values are added till next copystat_reset
  78  */
  79 int curr_vals[ASIZE];
  80
  81 static pset *all_phi_nodes;
  82 static pset *all_phi_classes;
  83 static pset *all_copy_nodes;
  84
  85 void copystat_init(void) {
  86         dbg = firm_dbg_register("ir.be.copystat");
  87         firm_dbg_set_mask(dbg, DEBUG_LVL);
  88
  89         all_phi_nodes = pset_new_ptr_default();
  90         all_phi_classes = pset_new_ptr_default();
  91         all_copy_nodes = pset_new_ptr_default();
  92         phi_class_init();
  93 }
  94
  95 void copystat_reset(void) {
  96         int i;
  97         for (i = 0; i < ASIZE; ++i)
  98                 curr_vals[i] = 0;
  99         del_pset(all_phi_nodes);
 100         del_pset(all_phi_classes);
 101         del_pset(all_copy_nodes);
 102         all_phi_nodes = pset_new_ptr_default();
 103         all_phi_classes = pset_new_ptr_default();
 104         all_copy_nodes = pset_new_ptr_default();
 105 }
 106
 107 /**
 108  * Collect general data
 109  */
 110 static void irg_stat_walker(ir_node *node, void *env) {
 111         arch_env_t *arch_env = env;
 112         curr_vals[I_ALL_NODES]++; /* count all nodes */
 113
 114         if (is_Block(node)) /* count all blocks */
 115                 curr_vals[I_BLOCKS]++;
 116
 117         if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) /* collect phis */
 118                 pset_insert_ptr(all_phi_nodes, node);
 119
 120         if (is_Copy(arch_env, node))
 121                 pset_insert_ptr(all_copy_nodes, node);
 122 }
 123
 124 void copystat_collect_irg(ir_graph *irg, arch_env_t *arch_env) {
 125         irg_walk_graph(irg, irg_stat_walker, NULL, arch_env);
 126         curr_vals[I_BLOCKS] -= 2; /* substract 2 for start and end block */
 127         all_phi_classes = phi_class_compute_by_phis(all_phi_nodes);
 128 }
 129
 130 /**
 131  * Collect phi node data
 132  */
 133 static void stat_phi_node(be_chordal_env_t *chordal_env, ir_node *phi) {
 134         int arity, i;
 135         assert(is_Phi(phi));
 136
 137         /* count all phi phis */
 138         curr_vals[I_PHI_CNT]++;
 139
 140         /* argument count */
 141         arity = get_irn_arity(phi);
 142         curr_vals[I_PHI_ARG_CNT] += arity;
 143         if (arity > MAX_ARITY)
 144                 curr_vals[I_PHI_ARITY_E]++;
 145         else
 146                 curr_vals[I_PHI_ARITY_S + arity]++;
 147
 148         /* type of argument {self, const, pred, glob} */
 149         for (i = 0; i < arity; i++) {
 150         ir_node *block_of_arg, *block_ith_pred;
 151                 ir_node *cfg_node, *arg = get_irn_n(phi, i);
 152
 153                 if (arg == phi) {
 154                         curr_vals[I_PHI_ARG_SELF]++;
 155                         continue;
 156                 }
 157
 158                 if (iro_Const == get_irn_opcode(arg)) {
 159                         curr_vals[I_PHI_ARG_CONST]++;
 160                         continue;
 161                 }
 162
 163                 block_of_arg = get_nodes_block(arg);
 164
 165                 /* get the pred block skipping blocks on critical edges */
 166                 cfg_node = get_irn_n(get_nodes_block(phi), i);
 167                 block_ith_pred = get_nodes_block(cfg_node);
 168                 if (get_irn_opcode(cfg_node) == iro_Jmp && get_irn_arity(block_ith_pred) == 1) {
 169                         /* Then cfg_node_block has exactly 1 pred and 1 succ block,
 170                          * thus it must have been inserted during remove_critical_edges */
 171                         block_ith_pred = get_Block_cfgpred_block(block_ith_pred, 0);
 172                 }
 173
 174                 if (block_of_arg == block_ith_pred) {
 175                         curr_vals[I_PHI_ARG_PRED]++;
 176                         continue;
 177                 }
 178
 179                 curr_vals[I_PHI_ARG_GLOB]++;
 180         }
 181 }
 182
 183 /**
 184  * Collect register-constrained node data
 185  */
 186 static void stat_copy_node(be_chordal_env_t *chordal_env, ir_node *root) {
 187         curr_vals[I_CPY_CNT]++;
 188         curr_vals[I_COPIES_MAX]++;
 189         if (nodes_interfere(chordal_env, root, get_Copy_src(root))) {
 190                 curr_vals[I_COPIES_IF]++;
 191                 assert(0 && "A Perm pair (in/out) should never interfere!");
 192         }
 193 }
 194
 195 /**
 196  * Collect phi class data
 197  */
 198 static void stat_phi_class(be_chordal_env_t *chordal_env, pset *pc) {
 199         int i, o, size, if_free, phis;
 200         ir_node **members, *p;
 201
 202         /* phi class count */
 203         curr_vals[I_CLS_CNT]++;
 204
 205         /* phi class size */
 206         size = pset_count(pc);
 207         if (size > MAX_CLS_SIZE)
 208                 curr_vals[I_CLS_SIZE_E]++;
 209         else
 210                 curr_vals[I_CLS_SIZE_S + size]++;
 211
 212         /* get an array of all members for double iterating */
 213         members = xmalloc(size * sizeof(*members));
 214         for (i = 0, p = pset_first(pc); p; p = pset_next(pc))
 215                 members[i++] = p;
 216         assert(i == size);
 217
 218         /* determine number of phis on this class */
 219         phis = 0;
 220         for (i = 0; i < size; ++i)
 221                 if (is_Phi(members[i]))
 222                         phis++;
 223         if (phis > MAX_CLS_PHIS)
 224                 curr_vals[I_CLS_PHIS_E]++;
 225         else
 226                 curr_vals[I_CLS_PHIS_S + phis]++;
 227
 228         /* determine interference of phi class members */
 229         curr_vals[I_CLS_IF_MAX] += size*(size-1)/2;
 230         if_free = 1;
 231         for (i = 0; i < size-1; ++i)
 232                 for (o = i+1; o < size; ++o)
 233                         if (nodes_interfere(chordal_env, members[i], members[o])) {
 234                                 if_free = 0;
 235                                 curr_vals[I_CLS_IF_CNT]++;
 236                         }
 237
 238         /* Does this phi class have an inner interference? */
 239         curr_vals[I_CLS_IF_FREE] += if_free;
 240
 241         xfree(members);
 242 }
 243
 244 #define is_curr_reg_class(irn) \
 245   (arch_get_irn_reg_class(chordal_env->session_env->main_env->arch_env, irn, \
 246                           arch_pos_make_out(0)) == chordal_env->cls)
 247
 248 void copystat_collect_cls(be_chordal_env_t *chordal_env) {
 249         ir_node *n;
 250         pset *pc;
 251
 252         for (n = pset_first(all_phi_nodes); n; n = pset_next(all_phi_nodes))
 253                 if (is_curr_reg_class(n))
 254                         stat_phi_node(chordal_env, n);
 255
 256         for (n = pset_first(all_copy_nodes); n; n = pset_next(all_copy_nodes))
 257                 if (is_curr_reg_class(n))
 258                         stat_copy_node(chordal_env, n);
 259
 260         for (pc = pset_first(all_phi_classes); pc; pc = pset_next(all_phi_classes)) {
 261                 ir_node *member = pset_first(pc);
 262                 pset_break(pc);
 263                 if (is_curr_reg_class(member))
 264                         stat_phi_class(chordal_env, pc);
 265         }
 266 }
 267
 268 void copystat_add_max_costs(int costs) {
 269         curr_vals[I_COPIES_MAX] += costs;
 270 }
 271 void copystat_add_inevit_costs(int costs) {
 272         curr_vals[I_COPIES_IF] += costs;
 273 }
 274 void copystat_add_init_costs(int costs) {
 275         curr_vals[I_COPIES_INIT] += costs;
 276 }
 277 void copystat_add_heur_costs(int costs) {
 278         curr_vals[I_COPIES_HEUR] += costs;
 279 }
 280 void copystat_add_opt_costs(int costs) {
 281         curr_vals[I_COPIES_OPT] += costs;
 282 }
 283 void copystat_add_ilp_time(int time) {
 284         curr_vals[I_ILP_TIME] += time;
 285 }
 286 void copystat_add_ilp_iter(int iters) {
 287         curr_vals[I_ILP_ITER] += iters;
 288 }
 289
 290 void copystat_dump(ir_graph *irg) {
 291         int i;
 292         char buf[1024];
 293         FILE *out;
 294
 295         snprintf(buf, sizeof(buf), "%s__%s", get_irp_prog_name(), get_entity_name(get_irg_entity(irg)));
 296         out = ffopen(buf, "stat", "wt");
 297
 298         fprintf(out, "%d\n", ASIZE);
 299         for (i = 0; i < ASIZE; i++) {
 300 #if 0
 301                 if (i >= I_PHI_ARITY_S && i <= I_PHI_ARITY_E)
 302                         fprintf(out, "%i %i\n", curr_vals[i], curr_vals[I_PHI_CNT]);
 303                 else if (i >= I_CLS_SIZE_S && i <= I_CLS_SIZE_E)
 304                         fprintf(out, "%i %i\n", curr_vals[i], curr_vals[I_CLS_CNT]);
 305                 else
 306 #endif
 307                         fprintf(out, "%i\n", curr_vals[i]);
 308         }
 309
 310     fclose(out);
 311 }
 312
 313 void copystat_dump_pretty(ir_graph *irg) {
 314         int i;
 315         char buf[1024];
 316         FILE *out;
 317
 318         snprintf(buf, sizeof(buf), "%s__%s", get_irp_prog_name(), get_entity_name(get_irg_entity(irg)));
 319         out = ffopen(buf, "pstat", "wt");
 320
 321         fprintf(out, "Nodes     %4d\n", curr_vals[I_ALL_NODES]);
 322         fprintf(out, "Blocks    %4d\n", curr_vals[I_BLOCKS]);
 323         fprintf(out, "CopyIrn   %4d\n", curr_vals[I_CPY_CNT]);
 324
 325         fprintf(out, "\nPhis      %4d\n", curr_vals[I_PHI_CNT]);
 326         fprintf(out, "... argument types\n");
 327         fprintf(out, " Total      %4d\n", curr_vals[I_PHI_ARG_CNT]);
 328         fprintf(out, " Self       %4d\n", curr_vals[I_PHI_ARG_SELF]);
 329         fprintf(out, " Constants  %4d\n", curr_vals[I_PHI_ARG_CONST]);
 330         fprintf(out, " CF-Pred    %4d\n", curr_vals[I_PHI_ARG_PRED]);
 331         fprintf(out, " Others     %4d\n", curr_vals[I_PHI_ARG_GLOB]);
 332         fprintf(out, "... arities\n");
 333         for (i = I_PHI_ARITY_S; i<=I_PHI_ARITY_E; i++)
 334                 fprintf(out, " %2i %4d\n", i-I_PHI_ARITY_S, curr_vals[i]);
 335
 336         fprintf(out, "\nPhi classes   %4d\n", curr_vals[I_CLS_CNT]);
 337         fprintf(out, " compl. free  %4d\n", curr_vals[I_CLS_IF_FREE]);
 338         fprintf(out, " inner intf.  %4d / %4d\n", curr_vals[I_CLS_IF_CNT], curr_vals[I_CLS_IF_MAX]);
 339         fprintf(out, "... sizes\n");
 340         for (i = I_CLS_SIZE_S; i<=I_CLS_SIZE_E; i++)
 341                 fprintf(out, " %2i %4d\n", i-I_CLS_SIZE_S, curr_vals[i]);
 342         fprintf(out, "... contained phis\n");
 343         for (i = I_CLS_PHIS_S; i<=I_CLS_PHIS_E; i++)
 344                 fprintf(out, " %2i %4d\n", i-I_CLS_PHIS_S, curr_vals[i]);
 345
 346         fprintf(out, "\nILP stat\n");
 347         fprintf(out, " Time %8d\n", curr_vals[I_ILP_TIME]);
 348         fprintf(out, " Iter %8d\n", curr_vals[I_ILP_ITER]);
 349
 350         fprintf(out, "\nCopy stat\n");
 351         fprintf(out, " Max  %4d\n", curr_vals[I_COPIES_MAX]);
 352         fprintf(out, " Init %4d\n", curr_vals[I_COPIES_INIT]);
 353         fprintf(out, " Heur %4d\n", curr_vals[I_COPIES_HEUR]);
 354         fprintf(out, " Opt  %4d\n", curr_vals[I_COPIES_OPT]);
 355         fprintf(out, " Intf %4d\n", curr_vals[I_COPIES_IF]);
 356
 357         fclose(out);
 358 }
 359
 360 #endif