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

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