nsz Git - libfirm/blob - ir/ir/irreflect.c

   1 /**
   2  * @file irreflect.c
   3  * @date 9.9.2004
   4  * @author Sebastian Hack
   5  * @brief Reflection for Firm operands.
   6  *
   7  * $Id$
   8  */
   9 #ifdef HAVE_CONFIG_H
  10 # include "config.h"
  11 #endif
  12
  13 #include <assert.h>
  14
  15 #ifdef HAVE_STDLIB_H
  16 # include <stdlib.h>
  17 #endif
  18 #ifdef HAVE_STRING_H
  19 # include <string.h>
  20 #endif
  21 #ifdef HAVE_STRINGS_H
  22 # include <strings.h>
  23 #endif
  24
  25 #include "obst.h"
  26
  27 #include "irnode_t.h"
  28 #include "irmode.h"
  29 #include "irreflect.h"
  30
  31 #define obstack_grow_str(obst,s) obstack_grow((obst), (s), strlen((s)))
  32 #define obstack_grow_str_const(obst,s) obstack_grow((obst), (s), sizeof((s)))
  33
  34 /**
  35  * Get the number of bits set in a word.
  36  */
  37 static INLINE int pop(int i) {
  38         unsigned x = (unsigned) i;
  39         x = ((x >> 1) & 0x55555555);
  40         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  41         x = (x + (x >> 4)) & 0x0f0f0f0f;
  42         x = x + (x >> 8);
  43         x = x + (x >> 16);
  44         return (int) (x & 0x3f);
  45 }
  46
  47 /**
  48  * Get the number of bits differing in two variables.
  49  */
  50 static INLINE int dist(int x, int y) {
  51         return pop(x ^ y);
  52 }
  53
  54
  55 #define MAX_SIG_COUNT 8
  56 #define MAX_ARG_COUNT 10
  57
  58 typedef struct {
  59         int num;    /**< A sequential number (one opcode can have multiple signatures. */
  60         rflct_arg_t args[]; /**< The signature. */
  61 } rflct_args_t;
  62
  63 typedef struct {
  64         opcode opc;
  65         const char *name;
  66         int commutative;
  67         int sig_count;
  68         rflct_arg_t *sigs[MAX_SIG_COUNT];
  69 } rflct_opcode_t;
  70
  71 static struct obstack obst;
  72
  73 static rflct_opcode_t **opcodes = NULL;
  74
  75 static int opcodes_size = 0;
  76
  77 static INLINE void assure_opcode_capacity(int opcode)
  78 {
  79         if(opcode >= opcodes_size) {
  80                 int new_size = 2 * opcode;
  81                 rflct_opcode_t **new_opcodes = xcalloc(new_size, sizeof(new_opcodes[0]));
  82
  83                 if(opcodes != NULL) {
  84                         memcpy(new_opcodes, opcodes, sizeof(*opcodes) * opcodes_size);
  85                         free(opcodes);
  86                 }
  87
  88                 opcodes = new_opcodes;
  89                 opcodes_size = new_size;
  90         }
  91 }
  92
  93
  94 #if 0
  95 #define OPCODES_COUNT (sizeof(opcodes) / sizeof(opcodes[0]))
  96 #endif
  97 #define OPCODES_COUNT opcodes_size
  98
  99
 100 rflct_mode_class_t rflct_get_mode_class(const ir_mode *mode) {
 101         mode_sort sort = get_mode_sort(mode);
 102
 103         switch(sort) {
 104                 case irms_auxiliary:
 105                 case irms_control_flow:
 106                         if(mode == mode_BB)
 107                                 return RFLCT_MC(BB);
 108                         else if(mode == mode_X)
 109                                 return RFLCT_MC(X);
 110                 case irms_memory:
 111                         return RFLCT_MC(Mem);
 112                 case irms_internal_boolean:
 113                         return RFLCT_MC(Bool);
 114                 case irms_int_number:
 115                         return mode_is_signed(mode) ? RFLCT_MC(IntS) : RFLCT_MC(IntU);
 116                 case irms_float_number:
 117                         return RFLCT_MC(Float);
 118                 case irms_reference:
 119                         return RFLCT_MC(Ref);
 120                 case irms_character:
 121                         return RFLCT_MC(Char);
 122         }
 123
 124         return RFLCT_MC(None);
 125 }
 126
 127 static INLINE const rflct_opcode_t *get_opcode(opcode opc) {
 128         assert(opc >= 0 && opc < OPCODES_COUNT && "Invalid opcode");
 129         return opcodes[opc];
 130 }
 131
 132 static INLINE const rflct_arg_t *get_args(opcode opc, int sig) {
 133         const rflct_opcode_t *opcode = get_opcode(opc);
 134         assert(sig >= 0 && sig < opcode->sig_count
 135                         && "Invalid signature");
 136         return opcode->sigs[sig];
 137 }
 138
 139 #define GET_OPCODE(opc) get_opcode(opc)
 140 #define GET_ARGS(opc,args) get_args(opc, args)
 141
 142 int rflct_get_signature_count(opcode opc) {
 143         const rflct_opcode_t *opcode = GET_OPCODE(opc);
 144         return opcode->sig_count;
 145 }
 146
 147 int rflct_get_in_args_count(opcode opc, int sig) {
 148         const rflct_arg_t *args = GET_ARGS(opc, sig);
 149         int res = 0, i = 0;
 150
 151         for(i = 0; args[i].name != NULL; i++);
 152         for(res = 0, i += 1; args[i].name != NULL; res++, i++);
 153         return res;
 154 }
 155
 156 int rflct_get_out_args_count(opcode opc, int sig) {
 157         const rflct_arg_t *args = GET_ARGS(opc, sig);
 158         int i = 0;
 159         for(i = 0; args[i].name != NULL; i++);
 160         return i;
 161 }
 162
 163
 164 const rflct_arg_t *rflct_get_in_args(opcode opc, int sig) {
 165         const rflct_arg_t *args = GET_ARGS(opc, sig);
 166         int i;
 167
 168         for(i = 0; args[i].name != NULL; i++);
 169         return &args[i + 1];
 170 }
 171
 172 const rflct_arg_t *rflct_get_out_args(opcode opc, int sig) {
 173         return GET_ARGS(opc, sig);
 174 }
 175
 176 int rflct_signature_match(const ir_node *irn, int sig) {
 177         opcode op = get_irn_opcode(irn);
 178         const rflct_arg_t *args = rflct_get_in_args(op, sig);
 179         int dst = 0;
 180         int i, j;
 181
 182         for(i = 0, j = -1; RFLCT_ARG_VALID(&args[i])
 183                         && j < get_irn_arity(irn); j++) {
 184
 185                 ir_node *child = get_irn_n(irn, j);
 186                 const rflct_arg_t *arg = &args[i];
 187                 rflct_mode_class_t mc = rflct_get_mode_class(get_irn_mode(child));
 188
 189                 if(arg->accepted_modes & mc)
 190                         dst += dist(arg->accepted_modes, mc);
 191                 else
 192                         return INT_MAX;
 193
 194                 if(!arg->is_variadic)
 195                         i++;
 196         }
 197
 198         return dst;
 199 }
 200
 201 int rflct_get_signature(const ir_node *irn) {
 202         const rflct_opcode_t *opc = GET_OPCODE(get_irn_opcode(irn));
 203         int min_dist = INT_MAX;
 204         int min_sig = INT_MAX;
 205         int i;
 206
 207         for(i = 0; i < opc->sig_count; i++) {
 208                 int dist = rflct_signature_match(irn, i);
 209                 if(dist < min_dist) {
 210                         min_dist = dist;
 211                         min_sig = i;
 212                 }
 213         }
 214
 215         return min_sig;
 216 }
 217
 218 static const char *rflct_mode_class_atomic_name(rflct_mode_class_t mc) {
 219 #define XXX(_mc) case RFLCT_MC(_mc): return #_mc
 220         switch(mc) {
 221                 XXX(None);
 222                 XXX(Mem);
 223                 XXX(Bool);
 224                 XXX(IntS);
 225                 XXX(IntU);
 226                 XXX(Float);
 227                 XXX(Ref);
 228                 XXX(Char);
 229                 XXX(X);
 230                 XXX(BB);
 231                 XXX(Int);
 232                 XXX(Intb);
 233                 XXX(Num);
 234                 XXX(NumP);
 235                 XXX(Data);
 236                 XXX(Datab);
 237                 XXX(DataM);
 238                 XXX(DataMX);
 239                 XXX(Lh);
 240                 default:
 241                 return "";
 242         }
 243 #undef XXX
 244 }
 245
 246 static void rflct_mode_class_comb_name_obst(struct obstack *obst,
 247                 rflct_mode_class_t mc) {
 248         const char *res = rflct_mode_class_atomic_name(mc);
 249
 250         if(strlen(res) == 0) {
 251                 const char *prefix = "";
 252                 int mask;
 253
 254                 obstack_1grow(obst, '{');
 255                 for(mask = 1; mask != 0; mask <<= 1) {
 256                         if(mask & mc) {
 257                                 const char *s = rflct_mode_class_atomic_name(mask);
 258                                 obstack_grow_str(obst, s);
 259                                 obstack_grow_str(obst, prefix);
 260                                 prefix = "|";
 261                         }
 262                 }
 263                 obstack_1grow(obst, '}');
 264
 265         } else
 266                 obstack_grow(obst, res, strlen(res));
 267 }
 268
 269 char *rflct_mode_class_name(char *str, int n, rflct_mode_class_t mc) {
 270         struct obstack obst;
 271         const char *res;
 272
 273         obstack_init(&obst);
 274
 275         rflct_mode_class_comb_name_obst(&obst, mc);
 276         obstack_1grow(&obst, 0);
 277         res = obstack_finish(&obst);
 278
 279         strncpy(str, res, n);
 280
 281         obstack_free(&obst, NULL);
 282
 283         return str;
 284 }
 285
 286 static void rflct_obstack_grow_args(struct obstack *obst,
 287                 const rflct_arg_t *args) {
 288         const rflct_arg_t *arg;
 289         const char *prefix = "";
 290
 291         for(arg = args; RFLCT_ARG_VALID(arg); arg++) {
 292                 obstack_grow_str(obst, prefix);
 293                 obstack_grow_str(obst, arg->name);
 294                 if(arg->is_variadic)
 295                         obstack_1grow(obst, '*');
 296                 obstack_1grow(obst, ':');
 297                 rflct_mode_class_comb_name_obst(obst, arg->accepted_modes);
 298                 prefix = ", ";
 299         }
 300
 301 }
 302
 303 char *rflct_to_string(char *buf, int n, opcode opc, int sig) {
 304         struct obstack obst;
 305         char *s;
 306         const rflct_opcode_t *opcode = GET_OPCODE(opc);
 307
 308         obstack_init(&obst);
 309
 310         obstack_1grow(&obst, '(');
 311         rflct_obstack_grow_args(&obst, rflct_get_out_args(opc, sig));
 312
 313         obstack_grow_str(&obst, ") = ");
 314         obstack_grow_str(&obst, opcode->name);
 315         obstack_1grow(&obst, '(');
 316
 317         rflct_obstack_grow_args(&obst, rflct_get_in_args(opc, sig));
 318
 319         obstack_1grow(&obst, ')');
 320         obstack_1grow(&obst, 0);
 321         s = obstack_finish(&obst);
 322         strncpy(buf, s, n);
 323         obstack_free(&obst, NULL);
 324
 325         return buf;
 326 }
 327
 328 #define NON_VARIADIC 0
 329 #define VARIADIC     1
 330
 331 #define ARG(name,modes) \
 332 _ARG(name, modes, NON_VARIADIC, -1)
 333
 334 #define ARG_SAME(name,modes,mode_same) \
 335 _ARG(name, modes, NON_VARIADIC, mode_same)
 336
 337 #define VARG(name,modes) \
 338 _ARG(name, modes, VARIADIC, 0)
 339
 340 #define VARG_SAME(name,modes) \
 341 _ARG(name, modes, VARIADIC, 1)
 342
 343 #define MARK \
 344 _ARG(NULL, None, NON_VARIADIC, -1)
 345
 346 #define FINISH \
 347 _ARG(NULL, None, NON_VARIADIC, 0)
 348
 349 #define BLOCK ARG("Block", BB)
 350
 351         static void init_ops(void) {
 352
 353                 int curr_sig;
 354                 rflct_opcode_t *opcode;
 355
 356                 obstack_init(&obst);
 357
 358                 assure_opcode_capacity(iro_MaxOpcode);
 359
 360
 361 #define BEGIN_OP(op)  \
 362                 curr_sig = 0; \
 363                         opcode = obstack_alloc(&obst, sizeof(*opcode)); \
 364                         opcode->opc = iro_ ## op; \
 365                         opcode->name = #op; \
 366                         opcodes[opcode->opc] = opcode;
 367
 368
 369 #define BEGIN_ARGS
 370
 371 #define _ARG(_name,_modes,_variadic,_mode_equals) \
 372                 { \
 373                         rflct_arg_t args; \
 374                                 args.name = _name; \
 375                                 args.accepted_modes = RFLCT_MC(_modes); \
 376                                 args.is_variadic = _variadic; \
 377                                 args.mode_equals = _mode_equals; \
 378                                 obstack_grow(&obst, &args, sizeof(args)); \
 379                 }
 380
 381 #define END_ARGS \
 382                 { \
 383                         FINISH; \
 384                         assert(curr_sig < MAX_SIG_COUNT && "Mind the maximum number of signatures"); \
 385                         opcode->sigs[curr_sig++] = obstack_finish(&obst); \
 386                         opcode->sig_count = curr_sig; \
 387                 }
 388
 389 #define END_OP
 390
 391 #include "irreflect.def"
 392
 393 #undef BEGIN_ARGS
 394 #undef END_ARGS
 395 #undef BEGIN_OP
 396 #undef END_OP
 397         }
 398
 399 #undef _ARG
 400 #define _ARG(_name,_modes,_var,_me) \
 401 arg->name = _name; \
 402         arg->accepted_modes = RFLCT_MC(_modes); \
 403         arg->is_variadic = _var; \
 404         arg->mode_equals = _me;
 405
 406 void rflct_new_opcode(opcode opc, const char *name, int commutative)
 407 {
 408         rflct_opcode_t *ropc = obstack_alloc(&obst, sizeof(*ropc));
 409
 410         ropc->opc = opc;
 411         ropc->name = name;
 412         ropc->sig_count = 0;
 413         memset(ropc->sigs, 0, sizeof(ropc->sigs));
 414
 415         assure_opcode_capacity(opc);
 416         opcodes[opc] = ropc;
 417 }
 418
 419 int rflct_opcode_add_signature(opcode opc, rflct_sig_t *sig)
 420 {
 421         rflct_arg_t *args = sig->args;
 422         rflct_opcode_t *op = opcodes[opc];
 423         int i;
 424
 425         assert(op && "Illegal opcode");
 426
 427         for(i = 0; i < MAX_SIG_COUNT && op->sigs[i] != NULL; i++);
 428
 429         if(i >= MAX_SIG_COUNT)
 430                 return 0;
 431
 432         op->sigs[op->sig_count++] = args;
 433
 434         free(sig);
 435         return 1;
 436 }
 437
 438
 439 rflct_sig_t *rflct_signature_allocate(int defs, int uses)
 440 {
 441         rflct_sig_t *sig = xmalloc(sizeof(*sig));
 442
 443         rflct_arg_t *args =
 444                 obstack_alloc(&obst, sizeof(*args) * (defs + uses + 2));
 445
 446         rflct_arg_t *arg = args + defs;
 447         MARK;
 448
 449         arg = args + defs + uses + 1;
 450         FINISH;
 451
 452         sig->defs = defs;
 453         sig->uses = uses;
 454         sig->args = args;
 455
 456         return sig;
 457 }
 458
 459 int rflct_signature_get_index(const rflct_sig_t *sig, int is_use, int num)
 460 {
 461         return is_use ? num + sig->defs + 1 : num;
 462 }
 463
 464 #undef _ARG
 465 #define _ARG(_name,_modes,_var,_me) \
 466 arg->name = _name; \
 467         arg->accepted_modes = _modes; \
 468         arg->is_variadic = _var; \
 469         arg->mode_equals = _me;
 470
 471 int rflct_signature_set_arg(rflct_sig_t *sig, int is_use, int num,
 472                 const char *name, rflct_mode_class_t mc, int is_variadic, int mode_equals)
 473 {
 474         int index = rflct_signature_get_index(sig, is_use, num);
 475         rflct_arg_t *arg = sig->args + index;
 476         _ARG(name, mc, is_variadic, mode_equals);
 477         return index;
 478 }
 479
 480
 481 void firm_init_rflct(void) {
 482         init_ops();
 483 }
 484
 485 #undef VARIADIC
 486 #undef NON_VARIADIC