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