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