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