nsz Git - libfirm/blob - ir/be/grgen/ana_vs.c

   1 /*
   2  * Project:     libFIRM/extension module/graph rewriting system
   3  * File name:   ext/grs/ana_vs.c
   4  * Purpose:     implements the interfaces in analyze.h by a
   5  *                              v-structure (vs) statistic (see [D"orr95],[Batz05b])
   6  * Author:      Veit Batz
   7  * Created:             22. June 2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * @file        ext/grs/ana_vs.c
  15  * @brief       implements the interfaces in analyze.h by a
  16  *                      v-structure (vs) statistic (see [D"orr95],[Batz05b])
  17  */
  18
  19 #include "iredges_t.h"
  20 #include "irgwalk.h"
  21
  22 #include "common_t.h"
  23 #include "analyze.h"
  24 #include "auxilary_t.h"
  25 #include "base_t.h"
  26 #include "ana_vs_t.h"
  27
  28
  29
  30 /* counter for isomorphic arguments and result uses during analyses */
  31 static int *n_isomorphics;
  32 static int op_dim, mode_dim;
  33 #define N_ISOMORPHICS(opc, mc) n_isomorphics[(opc)*mode_dim + (mc)]
  34
  35
  36 /*  Counts isomorphic edeges incident at the current node
  37  *  and stores some information in vs table.
  38  *  To be called by an irg walker
  39  *
  40  * node   the current ir node
  41  * env    the vs statistics object of the current ir graph
  42  */
  43 static void ana_nodes_vs(ir_node *node, void *env)
  44 {
  45
  46         ext_grs_vs_stat_t *vs_stat = (ext_grs_vs_stat_t *) env;
  47         ir_graph *irg = vs_stat->irg;
  48         ext_grs_irg_private_t *pr_g = _ext_grs_get_irg_private(irg);
  49         ext_grs_irn_private_t *pr_n = _ext_grs_get_irn_private(node);
  50
  51         const ir_edge_t *edge;
  52
  53         int j, k;
  54         int n_ins = get_irn_arity(node);
  55
  56         int i = -1; /* for non Block nodes start at pos -1 */
  57         ir_opcode opc = get_irn_opcode(node);
  58         modecode mc = get_irn_modecode(node);
  59
  60
  61
  62         assert(vs_stat->irg == get_irn_irg(node) && "got wrong vs statistics");
  63
  64
  65
  66
  67         /* add the current node to the appropriate node list */
  68         lc_list_add(& pr_n->node_list, & _ext_grs_NODE_LIST(pr_g, opc, mc));
  69         /* increment the node counter counting the node in that list */
  70         (_ext_grs_N_INSTANCES(pr_g, opc, mc))++;
  71         /* increment the counter counting the instances of an op for ANY mode */
  72         if (mc != irm_ANY)
  73                 (_ext_grs_N_INSTANCES(pr_g, opc, irm_ANY))++;
  74
  75         /* count isomorphic arguments of the current node */
  76         if (get_irn_op(node) == op_Block) i = 0;
  77         for ( ; i < n_ins; i++) {
  78
  79                 ir_node *arg = get_irn_n(node, i);
  80                 ir_opcode opc_arg = get_irn_opcode(arg);
  81                 modecode mc_arg = get_irn_modecode(arg);
  82                 ir_opcode super_opc_arg;
  83
  84
  85                 int n_super_ops = ARR_LEN(_ext_grs_all_super_ops_of_op[opc_arg]);
  86
  87                 /* increment counters for the apropriate op and all super ops */
  88                 for (j = 0; j < n_super_ops; j++) {
  89                         super_opc_arg = get_op_code(_ext_grs_all_super_ops_of_op[opc_arg][j]);
  90                         N_ISOMORPHICS(super_opc_arg, mc_arg)++;
  91                         N_ISOMORPHICS(super_opc_arg, irm_ANY)++;
  92                 }
  93         }
  94         /* store resulting number of v structures */
  95         i = -1;
  96         if (get_irn_op(node) == op_Block) i = 0;
  97         n_ins = get_irn_arity(node);
  98         for ( ; i < n_ins; i++) {
  99
 100                 ir_node *arg = get_irn_n(node, i);
 101                 ir_opcode opc_arg = get_irn_opcode(arg);
 102                 modecode mc_arg = get_irn_modecode(arg);
 103                 ir_opcode super_opc_arg;
 104
 105
 106 #if(0)
 107                 int n_occ_add = 0;
 108                 int n_occ_any_add = 0;
 109                 int n_any_occ_add = 0;
 110                 int n_any_occ_any_add = 0;
 111 #endif
 112
 113                 int n_super_ops = ARR_LEN(_ext_grs_all_super_ops_of_op[opc_arg]);
 114
 115                 for (j = 0; j < n_super_ops; j++) {
 116                         super_opc_arg = get_op_code(_ext_grs_all_super_ops_of_op[opc_arg][j]);
 117                         if (N_ISOMORPHICS(super_opc_arg, mc_arg) > 0) {
 118                                 double x = _log2(N_ISOMORPHICS(super_opc_arg, mc_arg));
 119
 120 #if(0)
 121                                 /* count the occurence of nodes with such an edge */
 122                                 n_occ_add++;
 123                                 if (mc != irm_ANY)
 124                                         n_occ_any_add++;
 125 #endif
 126
 127                                 /* accumulate multiplicity of such an edge */
 128                                 if (x > 0) {
 129                                         /* and also add for all super ops of curent nodes op */
 130                                         int n_super_ops_func = ARR_LEN(_ext_grs_all_super_ops_of_op[opc]);
 131                                         for (k = 0; k < n_super_ops_func; k++) {
 132                                                 ir_opcode super_opc_func = get_op_code(_ext_grs_all_super_ops_of_op[opc][k]);
 133
 134                                                 _add_n_v_structures(
 135                                                         vs_stat, super_opc_func, mc, super_opc_arg, mc_arg, ext_grs_in, x);
 136                                                 if (mc != irm_ANY)
 137                                                         _add_n_v_structures(vs_stat,
 138                                                                 super_opc_func, irm_ANY, super_opc_arg, mc_arg, ext_grs_in, x);
 139
 140                                         }
 141                                 }
 142                                 N_ISOMORPHICS(super_opc_arg, mc_arg) = 0;
 143                         }
 144                         if (N_ISOMORPHICS(super_opc_arg, irm_ANY) > 0) {
 145                                 double x = _log2(N_ISOMORPHICS(super_opc_arg, irm_ANY));
 146
 147 #if(0)
 148                                 /* count the occurence of nodes with such an edge */
 149                                 n_any_occ_add++;
 150                                 if (mc != irm_ANY)
 151                                         n_any_occ_any_add++;
 152 #endif
 153
 154                                 /* accumulate multiplicity of such an edge */
 155                                 if (x > 0) {
 156                                         /* and also add for all super ops of curent nodes op */
 157                                         int n_super_ops_func = ARR_LEN(_ext_grs_all_super_ops_of_op[opc]);
 158                                         for (k = 0; k < n_super_ops_func; k++) {
 159                                                 ir_opcode super_opc_func = get_op_code(_ext_grs_all_super_ops_of_op[opc][k]);
 160
 161                                                 _add_n_v_structures(
 162                                                         vs_stat, super_opc_func, mc, super_opc_arg, irm_ANY, ext_grs_in, x);
 163                                                 if (mc != irm_ANY)
 164                                                         _add_n_v_structures(vs_stat,
 165                                                                 super_opc_func, irm_ANY, super_opc_arg, irm_ANY, ext_grs_in, x);
 166                                         }
 167                                 }
 168                                 N_ISOMORPHICS(super_opc_arg, irm_ANY) = 0;
 169                         }
 170                 }
 171 #if(0)
 172                 if (n_occ_add > 0)
 173                         _add_n_occurence(vs_stat, opc, mc, opc_arg, mc_arg, ext_grs_in, n_occ_add);
 174                 if (n_occ_any_add > 0)
 175                         _add_n_occurence(vs_stat, opc, irm_ANY, opc_arg, mc_arg, ext_grs_in, n_any_occ_add);
 176                 if (n_any_occ_add > 0)
 177                         _add_n_occurence(vs_stat, opc, mc, opc_arg, irm_ANY, ext_grs_in, n_occ_any_add);
 178                 if (n_any_occ_any_add > 0)
 179                         _add_n_occurence(vs_stat, opc, irm_ANY, opc_arg, irm_ANY, ext_grs_in, n_any_occ_any_add);
 180 #endif
 181
 182         }
 183
 184
 185
 186         /* count isomorphic uses of the current nodes result */
 187         foreach_out_edge(node, edge) {
 188
 189                 ir_node *res = get_edge_src_irn(edge);
 190                 ir_opcode opc_res = get_irn_opcode(res);
 191                 modecode mc_res = get_irn_modecode(res);
 192
 193                 modecode super_opc_res;
 194
 195                 int n_super_ops = ARR_LEN( _ext_grs_all_super_ops_of_op[opc_res]);
 196
 197                 /* increment counters for the apropriate op and all super ops */
 198                 for (j = 0; j < n_super_ops; j++) {
 199                         super_opc_res = get_op_code(_ext_grs_all_super_ops_of_op[opc_res][j]);
 200                         N_ISOMORPHICS(super_opc_res, mc_res)++;
 201                         N_ISOMORPHICS(super_opc_res, irm_ANY)++;
 202                 }
 203         }
 204         /* store resulting number of v structures */
 205         foreach_out_edge(node, edge) {
 206
 207                 ir_node *res = get_edge_src_irn(edge);
 208                 ir_opcode opc_res = get_irn_opcode(res);
 209                 modecode mc_res = get_irn_modecode(res);
 210                 modecode super_opc_res;
 211
 212 #if(0)
 213                 int n_occ_add = 0;
 214                 int n_occ_any_add = 0;
 215                 int n_any_occ_add = 0;
 216                 int n_any_occ_any_add = 0;
 217 #endif
 218
 219                 int n_super_ops = ARR_LEN( _ext_grs_all_super_ops_of_op[opc_res]);
 220
 221                 for (j = 0; j < n_super_ops; j++) {
 222                         super_opc_res = get_op_code(_ext_grs_all_super_ops_of_op[opc_res][j]);
 223                         if (N_ISOMORPHICS(super_opc_res, mc_res) > 0) {
 224
 225                                 double x = _log2(N_ISOMORPHICS(super_opc_res, mc_res));
 226
 227 #if(0)
 228                                 /* count the occurence of nodes with such an edge */
 229                                 n_occ_add++;
 230                                 if (mc != irm_ANY)
 231                                         n_any_occ_add++;
 232 #endif
 233
 234                                 /* accumulate multiplicity of such an edge */
 235                                 if (x > 0) {
 236                                         /* and also add for all super ops of curent nodes op */
 237                                         int n_super_ops_func = ARR_LEN(_ext_grs_all_super_ops_of_op[opc]);
 238                                         for (k = 0; k < n_super_ops_func; k++) {
 239                                                 ir_opcode super_opc_func = get_op_code(_ext_grs_all_super_ops_of_op[opc][k]);
 240
 241                                                 _add_n_v_structures(
 242                                                         vs_stat, super_opc_func, mc, super_opc_res, mc_res, ext_grs_out, x);
 243                                                 if (mc != irm_ANY)
 244                                                         _add_n_v_structures(vs_stat,
 245                                                                 super_opc_func, irm_ANY, super_opc_res, mc_res, ext_grs_out, x);
 246                                         }
 247                                 }
 248                                 N_ISOMORPHICS(super_opc_res, mc_res) = 0;
 249                         }
 250                         if (N_ISOMORPHICS(super_opc_res, irm_ANY) > 0) {
 251
 252                                 double x = _log2(N_ISOMORPHICS(super_opc_res, irm_ANY));
 253
 254 #if(0)
 255                                 /* count the occurence of nodes with such an edge */
 256                                 n_occ_any_add++;
 257                                 if (mc != irm_ANY)
 258                                         n_any_occ_any_add++;
 259 #endif
 260
 261                                 /* accumulate multiplicity of such an edge */
 262                                 if (x > 0) {
 263                                         /* and also add for all super ops of curent nodes op */
 264                                         int n_super_ops_func = ARR_LEN(_ext_grs_all_super_ops_of_op[opc]);
 265                                         for (k = 0; k < n_super_ops_func; k++) {
 266                                                 ir_opcode super_opc_func = get_op_code(_ext_grs_all_super_ops_of_op[opc][k]);
 267
 268                                                 _add_n_v_structures(
 269                                                         vs_stat, super_opc_func, mc, super_opc_res, irm_ANY, ext_grs_out, x);
 270                                                 if (mc != irm_ANY)
 271                                                         _add_n_v_structures(vs_stat,
 272                                                                 super_opc_func, irm_ANY, super_opc_res, irm_ANY, ext_grs_out, x);
 273                                         }
 274                                 }
 275                                 N_ISOMORPHICS(super_opc_res, irm_ANY) = 0;
 276                         }
 277                 }
 278 #if(0)
 279                 if (n_occ_add > 0)
 280                         _add_n_occurence(vs_stat, opc, mc, opc_res, mc_res, ext_grs_out, n_occ_add);
 281                 if (n_any_occ_add > 0)
 282                         _add_n_occurence(vs_stat, opc, irm_ANY, opc_res, mc_res, ext_grs_out, n_any_occ_add);
 283                 if (n_occ_any_add > 0)
 284                         _add_n_occurence(vs_stat, opc, mc, opc_res, irm_ANY, ext_grs_out, n_occ_add);
 285                 if (n_any_occ_any_add > 0)
 286                         _add_n_occurence(vs_stat, opc, irm_ANY, opc_res, irm_ANY, ext_grs_out, n_any_occ_add);
 287 #endif
 288
 289         }
 290
 291 }
 292
 293 /* initialize an vs analyzer */
 294 static void init(ext_grs_analyzer_t *alz) {
 295
 296         ext_grs_ana_vs_private_t *pr_a = malloc(sizeof(*pr_a));
 297
 298         /* init isomorphic edge counters with 0 */
 299         op_dim = 170;
 300         mode_dim = 25;
 301         n_isomorphics = malloc(170*25*sizeof(int));
 302         memset(n_isomorphics, 0, 170*25*sizeof(int));
 303
 304         /* init the pset mapping ir_graphs to that ir_graphs vs statistic */
 305         pr_a->ana_results = lc_pset_new(_stat_cmp_func, 256);
 306         /* init the global vs statistic */
 307         pr_a->global_vs_stat.irg = NULL;
 308         pr_a->global_vs_stat.stat = lc_pset_new(_vs_cmp_func, 256);
 309         obstack_init(& pr_a->global_vs_stat.obst);
 310
 311         alz->data = pr_a;
 312 }
 313
 314 /* perform string v structure analysis for a given graph */
 315 static void analyze(ext_grs_analyzer_t *alz, ir_graph *irg)
 316 {
 317         int j,k;
 318         ext_grs_irg_private_t *pr_g = _ext_grs_get_irg_private(irg);
 319         ext_grs_vs_stat_t *vs_stat;
 320
 321         assert(pr_g->matching_enabled && "matching not enabled for this graph");
 322
 323         edges_assure(irg);
 324
 325         /* check whether the array of instance counters is great enough */
 326         if (_ext_grs_max_opcode >= op_dim) {
 327                 free(n_isomorphics);
 328                 op_dim = _ext_grs_max_opcode + 50;
 329                 n_isomorphics = malloc(op_dim*mode_dim*sizeof(int));
 330                 memset(n_isomorphics, 0, op_dim*mode_dim*sizeof(int));
 331         }
 332
 333         if (_ext_grs_max_modecode >= mode_dim) {
 334                 free(n_isomorphics);
 335                 mode_dim = _ext_grs_max_modecode + 50;
 336                 n_isomorphics = malloc(op_dim*mode_dim*sizeof(int));
 337                 memset(n_isomorphics, 0, op_dim*mode_dim*sizeof(int));
 338         }
 339
 340
 341         /* init the op list heads */
 342         for (j = 0; j < _ext_grs_irgpr_op_dim; j++)
 343                 for (k = 0; k < _ext_grs_irgpr_mode_dim; k++) {
 344                         LC_INIT_LIST_HEAD(& _ext_grs_NODE_LIST(pr_g, j, k));
 345                         _ext_grs_N_INSTANCES(pr_g, j, k) = 0;
 346                 }
 347         /* init the number of (op,mode)-instances with zero */
 348         memset(pr_g->n_instances, 0,
 349                 _ext_grs_irgpr_op_dim * _ext_grs_irgpr_mode_dim *
 350                         sizeof(*(pr_g->n_instances)));
 351
 352         /* get the statistics object of the given irg and remove its complete contents */
 353         vs_stat = _get_irg_vs_stat(alz, irg);
 354         assert(vs_stat->irg == irg);
 355
 356         lc_pset_del(vs_stat->stat);
 357         vs_stat->stat = lc_pset_new(_vs_cmp_func, 256);
 358         obstack_free(& vs_stat->obst, NULL);
 359         obstack_init(& vs_stat->obst);
 360
 361
 362
 363         irg_walk_graph(irg, ana_nodes_vs, NULL, vs_stat);
 364 }
 365
 366 static void free_ana_result(ext_grs_analyzer_t *alz, ir_graph *irg)
 367 {
 368         ext_grs_vs_stat_t *vs_stat = _get_irg_vs_stat(alz, irg);
 369
 370         if (vs_stat->stat) {
 371                 lc_pset_del(vs_stat->stat);
 372                 vs_stat->stat = lc_pset_new(_vs_cmp_func, 256);
 373         }
 374
 375         obstack_free(& vs_stat->obst, NULL);
 376         obstack_init(& vs_stat->obst);
 377 }
 378
 379 /* dump the current analysis result for a given ir graph */
 380 static void dump_ana_result(ext_grs_analyzer_t *alz, ir_graph *irg)
 381 {
 382         int i,j,k,l,r;
 383         double x;
 384         ext_grs_vs_stat_t *vs_stat = _get_irg_vs_stat(alz, irg);
 385         ext_grs_irg_private_t *pr_g = _ext_grs_get_irg_private(irg);
 386
 387         printf("Dump vs-statistics for ir graph %ld...\n", get_irg_graph_nr(irg));
 388
 389         for (i=0; i <= _ext_grs_max_opcode; i++)
 390                 for (j=0; j <= _ext_grs_max_modecode; j++)
 391                         for (k=0; k <= _ext_grs_max_opcode; k++)
 392                                 for (l=0; l <= _ext_grs_max_modecode; l++) {
 393                                         x = _get_n_v_structures(vs_stat,i,j,k,l,ext_grs_in);
 394                                         if (x > (double)0) {
 395
 396                                                 int occ = _get_n_occurence(vs_stat, i, j, k, l, ext_grs_in);
 397                                                 int n_inst = 0;
 398                                                 double acc_div_occ = 0.0;
 399                                                 double acc_div_inst = 0.0;
 400
 401                                                 /* compute the number of instances present for the
 402                                                  * func node (including all sub ops) */
 403                                                 for (r = 0; r < ARR_LEN(_ext_grs_all_sub_ops_of_op[i]); r++) {
 404                                                         ir_opcode sub_opc = get_op_code(_ext_grs_all_sub_ops_of_op[i][r]);
 405                                                         n_inst += _ext_grs_N_INSTANCES(pr_g, sub_opc, j);
 406                                                 }
 407
 408                                                 if (occ > 0)
 409                                                         acc_div_occ = x / occ;
 410
 411                                                 if (n_inst > 0)
 412                                                         acc_div_inst = x / (double)n_inst;
 413
 414                                                 printf("# (%s, %s) -in-> (%s, %s): acc, occ, n_inst, acc/n_inst\n",
 415                                                         get_op_name(_ext_grs_op_map[i]),
 416                                                         get_mode_name(_ext_grs_mode_map[j]),
 417                                                         get_op_name(_ext_grs_op_map[k]),
 418                                                         get_mode_name(_ext_grs_mode_map[l])
 419                                                 );
 420                                                 printf("(%d,%d,%d,%d,in): %lf, %d, %d, %lf\n",
 421                                                         i,j,k,l,
 422                                                         x, occ, n_inst,
 423                                                         acc_div_inst
 424                                                 );
 425                                         }
 426                                         x = _get_n_v_structures(vs_stat,i,j,k,l,ext_grs_out);
 427                                         if (x > (double)0) {
 428
 429                                                 int occ = _get_n_occurence(vs_stat, i, j, k, l, ext_grs_out);
 430                                                 int n_inst = 0;
 431                                                 double acc_div_occ = 0.0;
 432                                                 double acc_div_inst = 0.0;
 433
 434                                                 /* compute the number of instnaces present for the
 435                                                  * func node (including all sub ops) */
 436                                                 for (r = 0; r < ARR_LEN(_ext_grs_all_sub_ops_of_op[i]); r++) {
 437                                                         ir_opcode sub_opc = get_op_code(_ext_grs_all_sub_ops_of_op[i][r]);
 438                                                         n_inst += _ext_grs_N_INSTANCES(pr_g, sub_opc, j);
 439                                                 }
 440
 441                                                 if (occ > 0)
 442                                                         acc_div_occ = x / occ;
 443
 444                                                 if (n_inst > 0)
 445                                                         acc_div_inst = x / (double)n_inst;
 446
 447                                                 printf("# (%s, %s) <-out- (%s, %s): acc, occ, n_inst, acc/n_inst\n",
 448                                                         get_op_name(_ext_grs_op_map[i]),
 449                                                         get_mode_name(_ext_grs_mode_map[j]),
 450                                                         get_op_name(_ext_grs_op_map[k]),
 451                                                         get_mode_name(_ext_grs_mode_map[l])
 452                                                 );
 453                                                 printf("(%d,%d,%d,%d,out): %lf, %d, %d, %lf\n",
 454                                                         i,j,k,l,
 455                                                         x, occ, n_inst,
 456                                                         acc_div_inst
 457                                                 );
 458                                         }
 459                                 }
 460
 461         for (i=0; i <= _ext_grs_max_opcode; i++)
 462                 for (j=0; j <= _ext_grs_max_modecode; j++) {
 463                         int n_inst = 0;
 464                         const char *opname;
 465                         const char *modename;
 466
 467                         for (r = 0; r < ARR_LEN(_ext_grs_all_sub_ops_of_op[i]); r++) {
 468                                 ir_opcode sub_opc = get_op_code(_ext_grs_all_sub_ops_of_op[i][r]);
 469                                 n_inst += _ext_grs_N_INSTANCES(pr_g, sub_opc, j);
 470                         }
 471
 472                         if (_ext_grs_op_map[i] != NULL)
 473                                 opname = get_op_name(_ext_grs_op_map[i]);
 474                         else opname = NULL;
 475
 476                         if (_ext_grs_mode_map[j] != NULL)
 477                                 modename = get_mode_name(_ext_grs_mode_map[j]);
 478                         else modename = NULL;
 479
 480                         if (opname == NULL) opname = "dummy";
 481                         if (modename == NULL) modename = "dummy";
 482
 483                         if (n_inst != 0 || _ext_grs_N_INSTANCES(pr_g, i,j) != 0)
 484                                 printf("Number of instances (%s, %s): direct = %d, with sub ops = %d\n",
 485                                         opname, modename, _ext_grs_N_INSTANCES(pr_g, i,j), n_inst);
 486                 }
 487
 488
 489         printf(" done\n");
 490 }
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500 static ext_grs_analyzer_t vs_analyzer;
 501
 502
 503 /** yields an analyzer performing a v-structure statisitc */
 504 ext_grs_analyzer_t *ext_grs_get_vs_analyzer(void)
 505 {
 506         memset(&vs_analyzer, 0, sizeof(vs_analyzer));
 507         vs_analyzer.tag = "vs_analyzer";
 508         vs_analyzer.dump_ana_result = dump_ana_result;
 509         vs_analyzer.analyze = analyze;
 510         vs_analyzer.free_ana_result = free_ana_result;
 511
 512         init(&vs_analyzer);
 513         return &vs_analyzer;
 514 }