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

   1 /*
   2  * Project:     libFIRM/extension module/GRS-matcher
   3  * File name:   ext/base.c
   4  * Purpose:     Basic stuff for the firm graph rewriting module
   5  * Author:      Veit Batz
   6  * Created:             9. May 2005
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 2005 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 #ifdef HAVE_CONFIG_H
  12         #include "config.h"
  13 #endif
  14
  15 #include <stdlib.h>
  16
  17 #include "irnode.h"
  18
  19
  20 #include "common_t.h"
  21 #include "auxilary_t.h"
  22 #include "base_t.h"
  23 #include "match_t.h"
  24 #include "grshooks_t.h"
  25 #include "action_t.h"
  26
  27 /* maps opcodes to ops */
  28 ir_op **_ext_grs_op_map;
  29 /* maps modecodes to modes */
  30 ir_mode **_ext_grs_mode_map;
  31
  32 /* a 2-dim flexible array telling wether an opcode belongs
  33  * to a sub op of the op given by a second opcode. usage:
  34  * _ext_grs_op_is_a[o1][o2] != 0   IFF   o1 inherits o2 */
  35 //int *_ext_grs_op_is_a = NULL;
  36 unsigned char *_ext_grs_op_is_a = NULL;
  37 /* the width of the  */
  38 int _ext_grs_op_is_a_width;
  39
  40 /* a flexible array of flexible arrays each containing all inheriting
  41  * firm ops of that firm op, the opcode of wich is the index entered
  42  * in the array of arrays
  43  * USAGE: _ext_grs_all_sub_ops_of_op[opcode]
  44  * this yields an flexible array of ptrs to firm ops inheriting
  45  * form the given opcodes op */
  46 ir_op ***_ext_grs_all_sub_ops_of_op = NULL;
  47 /* a flexible array of flexible arrays each containing all firm ops
  48  * a given firm op inherits from, the given opcode is the index entered
  49  * in the array of arrays
  50  * USAGE: _ext_grs_all_super_ops_of_op[opcode]
  51  * this yields an flexible array of ptrs to firm ops inheriting
  52  * form the given opcodes op */
  53 ir_op ***_ext_grs_all_super_ops_of_op = NULL;
  54
  55 /* dimension of dynamic allocated 2-dim arrays in private data
  56  * area of firm graphs. These two arrays are the n_instances
  57  * and the node_list. Note that these two arrays have the same
  58  * dimension for all ir graphs. That means if the maximal
  59  * opcode/modecode exceeds the respsective dimension the
  60  * arrays of ALL ir graphs have to be reallcated (this is done
  61  * by the hooks of new ops and modes) */
  62 int _ext_grs_irgpr_op_dim;
  63 int _ext_grs_irgpr_mode_dim;
  64
  65 /* offset of custom data in ir nodes */
  66 unsigned _ext_grs_private_ofs_n;
  67 /* offset of custom data in ir graphs */
  68 unsigned _ext_grs_private_ofs_g;
  69 /* offset of custom data in ir edges */
  70 unsigned _ext_grs_private_ofs_e;
  71
  72 /* maps ir op names (e.g. "Add") to ir ops (i.e. *ir_op) */
  73 lc_pset *_ext_grs_op_name_table;
  74 /* maps mode names (e.g. "M") to modes (i.e. *ir_mode) */
  75 lc_pset *_ext_grs_mode_name_table;
  76 /* remembers the maximum opcode present */
  77 int _ext_grs_max_opcode = 0;
  78 /* remembers the maximum modecode present */
  79 int _ext_grs_max_modecode = 0;
  80
  81
  82 /* op compare function for the hash table mapping op
  83  * names to the appropriate firm objects */
  84 static int _op_cmp_func(const void *e1, const void *e2) {
  85         const char *s1 = get_op_name((ir_op *) e1);
  86         const char *s2 = get_op_name((ir_op *) e2);
  87         int ret = strcmp(s1, s2);
  88         assert ((ret != 0 || get_op_code((ir_op *) e1) == get_op_code((ir_op *) e1)) &&
  89                 "found different ir ops with an equal op name");
  90         return ret;
  91 }
  92
  93 /* mode compare function for the hash table mapping mode
  94  * names to the appropriate firm objects */
  95 static int _mode_cmp_func(const void *e1, const void *e2) {
  96         const char *s1 = get_mode_name((ir_mode *) e1);
  97         const char *s2 = get_mode_name((ir_mode *) e2);
  98         int ret = strcmp(s1, s2);
  99         assert ((ret != 0 ||
 100                 get_mode_modecode((ir_mode *) e1) == get_mode_modecode((ir_mode *) e1)) &&
 101                 "found different ir modes with an equal mode name");
 102         return ret;
 103 }
 104
 105
 106 #define INITAL_OP_SPACE 500
 107
 108 /* activate the libfirm grs module */
 109 void ext_grs_activate(void)
 110 {
 111         printf("activate libFIRM grs plugin... ");
 112         /* private data of ir graphs, ir nodes and ir edges */
 113         _ext_grs_private_ofs_n =
 114                 firm_register_additional_node_data(sizeof(ext_grs_irn_private_t));
 115         _ext_grs_private_ofs_g =
 116                 register_additional_graph_data(sizeof(ext_grs_irg_private_t));
 117         _ext_grs_private_ofs_e =
 118                 edges_register_private_data(sizeof(ext_grs_iredges_private_t));
 119
 120         /* init fast computation of log_2 */
 121         _ext_grs_log_table_init();
 122
 123         /* init the hash tables mapping op and mode names to the respective firm objects */
 124         _ext_grs_op_name_table = lc_pset_new(_op_cmp_func, 256);
 125         _ext_grs_mode_name_table = lc_pset_new(_mode_cmp_func, 64);
 126
 127         /* init the flexible array representing the inheritance
 128          * relation on firm ops */
 129         _ext_grs_op_is_a = malloc(INITAL_OP_SPACE * INITAL_OP_SPACE*sizeof(*_ext_grs_op_is_a));
 130         _ext_grs_op_is_a_width = INITAL_OP_SPACE;
 131         memset(_ext_grs_op_is_a, 0, INITAL_OP_SPACE*INITAL_OP_SPACE*sizeof(*_ext_grs_op_is_a));
 132
 133         /* init the flexible array mapping op- and modecodes to ptrs */
 134         _ext_grs_op_map = NEW_ARR_F(ir_op*, INITAL_OP_SPACE);
 135         memset(_ext_grs_op_map, 0, INITAL_OP_SPACE * sizeof(*_ext_grs_op_map));
 136         _ext_grs_mode_map = NEW_ARR_F(ir_mode*, 100);
 137         memset(_ext_grs_mode_map, 0, 100 * sizeof(*_ext_grs_mode_map));
 138
 139         /* init the flexible array of flexible arrays keeping arrays of
 140          * all sub ops of the op with the respective index as opcode */
 141         _ext_grs_all_sub_ops_of_op = NEW_ARR_F(ir_op**, INITAL_OP_SPACE);
 142         memset (_ext_grs_all_sub_ops_of_op, 0, INITAL_OP_SPACE * sizeof(ir_op**));
 143         /* init the flexible array of flexible arrays keeping arrays of
 144          * all sub ops of the op with the respective index as opcode */
 145         _ext_grs_all_super_ops_of_op = NEW_ARR_F(ir_op**, INITAL_OP_SPACE);
 146         memset (_ext_grs_all_super_ops_of_op, 0, INITAL_OP_SPACE* sizeof(ir_op**));
 147
 148         /* dimension of the dynamically 2-dim arrays n_instances and
 149          * node_list in the private date area of ir graphs. */
 150         _ext_grs_irgpr_op_dim = INITAL_OP_SPACE;
 151         _ext_grs_irgpr_mode_dim = 25;
 152
 153         /* register firm some firm hooks */
 154         _ext_grs_register_hooks();
 155
 156         /* init the matcher */
 157         _ext_grs_match_init();
 158         /* init the action part */
 159         _ext_grs_act_init();
 160
 161         printf("done\n");
 162 }
 163
 164 void ext_grs_finalize() {
 165         _ext_grs_act_finalize();
 166 }
 167
 168 /**
 169  *  announce that firm op o1 inherits from firm op o2
 170  */
 171 void ext_grs_appoint_heir(ir_op *o1, ir_op *o2) {
 172
 173         /* check params */
 174         if (get_op_code(o2) > _ext_grs_max_opcode || get_op_code(o1) > _ext_grs_max_opcode) {
 175                 printf("module ext/grs: ERROR in function ext_grs_appoint_heir()\n");
 176                 printf("  Bad paramter: Unknown firm op.\n");
 177                 return;
 178         }
 179         if (o1 == o2) {
 180                 printf("module ext/grs: ERROR in function ext_grs_appoint_heir()\n");
 181                 printf("  The parameters given are equal.\n");
 182                 return;
 183         }
 184
 185         /* the new entry into the inheritance table */
 186         _ext_grs_OP_IS_A(get_op_code(o1), get_op_code(o2)) = 1;
 187 }
 188
 189 void ext_grs_inheritance_mature(void) {
 190
 191         int i, j, k;
 192
 193         for (i = 0; i <= _ext_grs_max_opcode; i++) {
 194
 195                 if(_ext_grs_all_sub_ops_of_op[i])
 196                         DEL_ARR_F(_ext_grs_all_sub_ops_of_op[i]);
 197                 _ext_grs_all_sub_ops_of_op[i] = NEW_ARR_F(ir_op *, 1);
 198                 /* every op is subop of itself */
 199                 _ext_grs_all_sub_ops_of_op[i][0] = _ext_grs_op_map[i];
 200
 201                 if(_ext_grs_all_super_ops_of_op[i])
 202                         DEL_ARR_F(_ext_grs_all_super_ops_of_op[i]);
 203                 _ext_grs_all_super_ops_of_op[i] = NEW_ARR_F(ir_op *, 1);
 204                 /* every op is superop of itself */
 205                 _ext_grs_all_super_ops_of_op[i][0] = _ext_grs_op_map[i];
 206         }
 207
 208         /* compute the transitive closure of the modified table
 209          * using the Floyd-Warshall-Algorithm */
 210         for (k = 0; k <= _ext_grs_max_opcode; k++)
 211                 for (i = 0; i <= _ext_grs_max_opcode; i++)
 212                         for (j = 0; j <= _ext_grs_max_opcode; j++)
 213                                 _ext_grs_OP_IS_A(i,j) = _ext_grs_OP_IS_A(i,j) ||
 214                                                 (_ext_grs_OP_IS_A(i, k) && _ext_grs_OP_IS_A(k, j));
 215
 216         for (i = 0; i <= _ext_grs_max_opcode; i++)
 217                 for (j = 0; j <= _ext_grs_max_opcode; j++)
 218                         if (_ext_grs_OP_IS_A(i,j)) {
 219                                 ARR_APP1(ir_op *, _ext_grs_all_sub_ops_of_op[j], _ext_grs_op_map[i]);
 220                                 ARR_APP1(ir_op *, _ext_grs_all_super_ops_of_op[i], _ext_grs_op_map[j]);
 221                         }
 222
 223 }
 224
 225 ir_op *(ext_grs_lookup_op)(char *name) {
 226         return _ext_grs_lookup_op(name);
 227 }
 228
 229 ir_mode *(ext_grs_lookup_mode)(char *name) {
 230         return _ext_grs_lookup_mode(name);
 231 }
 232
 233
 234
 235
 236
 237
 238 void ext_grs_enable_irg(ir_graph *irg)
 239 {
 240         int i, j;
 241         ext_grs_irg_private_t *pr_g;
 242
 243         if (!irg) {
 244                 printf("module ext/grs: ERROR in function ext_grs_enable_matching()\n");
 245                 printf("  Given ir graph was NULL.\n\n");
 246                 return;
 247         }
 248         pr_g = _ext_grs_get_irg_private(irg);
 249
 250         /* if matching is already enabled for this ir graph, do nothing */
 251         if (pr_g->matching_enabled) return;
 252
 253         /* init the dyn array of the heads of all oplists */
 254         pr_g->node_list =
 255                 malloc(_ext_grs_irgpr_op_dim * _ext_grs_irgpr_mode_dim *
 256                         sizeof(*(pr_g->node_list)));
 257
 258         if (! pr_g->node_list) {
 259                 printf("module ext/grs: Internal ERROR in function ext_grs_enable_matching()\n");
 260                 printf("  Failed to allocate memory for internal data strucures.\n\n");
 261                 printf("  Aborting!\n\n");
 262                 abort();
 263         }
 264
 265         for (i = 0; i < _ext_grs_irgpr_op_dim; i++)
 266                 for (j = 0; j < _ext_grs_irgpr_mode_dim; j++)
 267                         LC_INIT_LIST_HEAD( &_ext_grs_NODE_LIST(pr_g, i, j) );
 268
 269         /* init the dyn array of number of instances of each pair (op,mode) */
 270         pr_g->n_instances =
 271                 malloc(_ext_grs_irgpr_op_dim * _ext_grs_irgpr_mode_dim *
 272                         sizeof(*(pr_g->n_instances)));
 273         memset(pr_g->n_instances, 0,
 274                 _ext_grs_irgpr_op_dim * _ext_grs_irgpr_mode_dim *
 275                         sizeof(*(pr_g->n_instances)));
 276
 277         /* matching now enabled */
 278         pr_g->matching_enabled = 1;
 279 }
 280
 281 void ext_grs_disable_irg(ir_graph *irg)
 282 {
 283         ext_grs_irg_private_t *pr_g;
 284
 285         if (!irg) {
 286                 printf("module ext/grs: ERROR in function ext_grs_enable_matching()\n");
 287                 printf("  Given ir graph was NULL.\n\n");
 288                 return;
 289         }
 290         pr_g = _ext_grs_get_irg_private(irg);
 291
 292         /* if matching is already disabled for this ir graph, do nothing */
 293         if (! pr_g->matching_enabled) return;
 294
 295         free(pr_g->node_list);
 296         free(pr_g->n_instances);
 297
 298         /* matching now disabled */
 299         pr_g->matching_enabled = 0;
 300 }