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