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