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