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