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

   1 /*
   2  * Copyright (C) 1995-2008 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   Representation of opcode of intermediate operation.
  23  * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
  24  */
  25 #include "config.h"
  26
  27 #include <string.h>
  28
  29 #include "error.h"
  30 #include "irop_t.h"
  31 #include "irnode_t.h"
  32 #include "irhooks.h"
  33 #include "irbackedge_t.h"
  34
  35 #include "iropt_t.h"
  36 #include "irverify_t.h"
  37 #include "reassoc_t.h"
  38
  39 #include "xmalloc.h"
  40 #include "benode.h"
  41
  42 static ir_op **opcodes;
  43 /** the available next opcode */
  44 static unsigned next_iro = iro_MaxOpcode;
  45
  46 static ir_type *default_get_type_attr(const ir_node *node);
  47 static ir_entity *default_get_entity_attr(const ir_node *node);
  48 static unsigned default_hash_node(const ir_node *node);
  49 static void default_copy_attr(ir_graph *irg, const ir_node *old_node,
  50                               ir_node *new_node);
  51
  52 ir_op *new_ir_op(unsigned code, const char *name, op_pin_state p,
  53                  irop_flags flags, op_arity opar, int op_index,
  54                  size_t attr_size)
  55 {
  56         ir_op *res = XMALLOCZ(ir_op);
  57
  58         res->code      = code;
  59         res->name      = new_id_from_chars(name, strlen(name));
  60         res->pin_state = p;
  61         res->attr_size = attr_size;
  62         res->flags     = flags;
  63         res->opar      = opar;
  64         res->op_index  = op_index;
  65         res->tag       = 0;
  66
  67         memset(&res->ops, 0, sizeof(res->ops));
  68         res->ops.hash            = default_hash_node;
  69         res->ops.copy_attr       = default_copy_attr;
  70         res->ops.get_type_attr   = default_get_type_attr;
  71         res->ops.get_entity_attr = default_get_entity_attr;
  72
  73         {
  74                 size_t len = ARR_LEN(opcodes);
  75                 if ((size_t)code >= len) {
  76                         ARR_RESIZE(ir_op*, opcodes, (size_t)code+1);
  77                         memset(&opcodes[len], 0, (code-len+1) * sizeof(opcodes[0]));
  78                 }
  79                 if (opcodes[code] != NULL)
  80                         panic("opcode registered twice");
  81                 opcodes[code] = res;
  82         }
  83
  84         hook_new_ir_op(res);
  85         return res;
  86 }
  87
  88 void free_ir_op(ir_op *code)
  89 {
  90         hook_free_ir_op(code);
  91
  92         assert(opcodes[code->code] == code);
  93         opcodes[code->code] = NULL;
  94
  95         free(code);
  96 }
  97
  98 unsigned ir_get_n_opcodes(void)
  99 {
 100         return ARR_LEN(opcodes);
 101 }
 102
 103 ir_op *ir_get_opcode(unsigned code)
 104 {
 105         assert((size_t)code < ARR_LEN(opcodes));
 106         return opcodes[code];
 107 }
 108
 109 void ir_clear_opcodes_generic_func(void)
 110 {
 111         size_t n = ir_get_n_opcodes();
 112         size_t i;
 113
 114         for (i = 0; i < n; ++i) {
 115                 ir_op *op = ir_get_opcode(i);
 116                 if (op == NULL)
 117                         continue;
 118                 op->ops.generic  = (op_func)NULL;
 119                 op->ops.generic1 = (op_func)NULL;
 120                 op->ops.generic2 = (op_func)NULL;
 121         }
 122 }
 123
 124 void ir_op_set_memory_index(ir_op *op, int memory_index)
 125 {
 126         assert(op->flags & irop_flag_uses_memory);
 127         op->memory_index = memory_index;
 128 }
 129
 130 void ir_op_set_fragile_indices(ir_op *op, int pn_x_regular, int pn_x_except)
 131 {
 132         assert(op->flags & irop_flag_fragile);
 133         op->pn_x_regular = pn_x_regular;
 134         op->pn_x_except = pn_x_except;
 135 }
 136
 137 const char *get_op_name (const ir_op *op)
 138 {
 139         return get_id_str(op->name);
 140 }
 141
 142 unsigned (get_op_code)(const ir_op *op)
 143 {
 144   return get_op_code_(op);
 145 }
 146
 147 ident *(get_op_ident)(const ir_op *op)
 148 {
 149   return get_op_ident_(op);
 150 }
 151
 152 const char *get_op_pin_state_name(op_pin_state s)
 153 {
 154         switch (s) {
 155 #define XXX(s) case s: return #s
 156         XXX(op_pin_state_floats);
 157         XXX(op_pin_state_pinned);
 158         XXX(op_pin_state_exc_pinned);
 159         XXX(op_pin_state_mem_pinned);
 160 #undef XXX
 161         }
 162         return "<none>";
 163 }
 164
 165 op_pin_state (get_op_pinned)(const ir_op *op)
 166 {
 167         return get_op_pinned_(op);
 168 }
 169
 170 void set_op_pinned(ir_op *op, op_pin_state pinned)
 171 {
 172         if (op == op_Block || op == op_Phi || is_op_cfopcode(op)) return;
 173         op->pin_state = pinned;
 174 }
 175
 176 unsigned get_next_ir_opcode(void)
 177 {
 178         return next_iro++;
 179 }
 180
 181 unsigned get_next_ir_opcodes(unsigned num)
 182 {
 183         unsigned base = next_iro;
 184         next_iro += num;
 185         return base;
 186 }
 187
 188 op_func (get_generic_function_ptr)(const ir_op *op)
 189 {
 190         return get_generic_function_ptr_(op);
 191 }
 192
 193 void (set_generic_function_ptr)(ir_op *op, op_func func)
 194 {
 195         set_generic_function_ptr_(op, func);
 196 }
 197
 198 ir_op_ops *(get_op_ops)(ir_op *op)
 199 {
 200         return get_op_ops_(op);
 201 }
 202
 203 irop_flags get_op_flags(const ir_op *op)
 204 {
 205         return (irop_flags)op->flags;
 206 }
 207
 208 static ir_type *default_get_type_attr(const ir_node *node)
 209 {
 210         (void)node;
 211         return get_unknown_type();
 212 }
 213
 214 static ir_entity *default_get_entity_attr(const ir_node *node)
 215 {
 216         (void)node;
 217         return NULL;
 218 }
 219
 220 static unsigned default_hash_node(const ir_node *node)
 221 {
 222         unsigned h;
 223         int i, irn_arity;
 224
 225         /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 226         h = irn_arity = get_irn_arity(node);
 227
 228         /* consider all in nodes... except the block if not a control flow. */
 229         for (i = is_cfop(node) ? -1 : 0;  i < irn_arity;  ++i) {
 230                 ir_node *pred = get_irn_n(node, i);
 231                 if (is_irn_cse_neutral(pred))
 232                         h *= 9;
 233                 else
 234                         h = 9*h + hash_ptr(pred);
 235         }
 236
 237         /* ...mode,... */
 238         h = 9*h + hash_ptr(get_irn_mode(node));
 239         /* ...and code */
 240         h = 9*h + hash_ptr(get_irn_op(node));
 241
 242         return h;
 243 }
 244
 245 /**
 246  * Calculate a hash value of a Const node.
 247  */
 248 static unsigned hash_Const(const ir_node *node)
 249 {
 250         unsigned h;
 251
 252         /* special value for const, as they only differ in their tarval. */
 253         h = hash_ptr(node->attr.con.tarval);
 254
 255         return h;
 256 }
 257
 258 /**
 259  * Calculate a hash value of a SymConst node.
 260  */
 261 static unsigned hash_SymConst(const ir_node *node)
 262 {
 263         unsigned h;
 264
 265         /* all others are pointers */
 266         h = hash_ptr(node->attr.symc.sym.type_p);
 267
 268         return h;
 269 }
 270
 271 /** Compares two exception attributes */
 272 static int node_cmp_exception(const ir_node *a, const ir_node *b)
 273 {
 274         const except_attr *ea = &a->attr.except;
 275         const except_attr *eb = &b->attr.except;
 276         return ea->pin_state != eb->pin_state;
 277 }
 278
 279 /** Compares the attributes of two Const nodes. */
 280 static int node_cmp_attr_Const(const ir_node *a, const ir_node *b)
 281 {
 282         return get_Const_tarval(a) != get_Const_tarval(b);
 283 }
 284
 285 /** Compares the attributes of two Proj nodes. */
 286 static int node_cmp_attr_Proj(const ir_node *a, const ir_node *b)
 287 {
 288         return a->attr.proj.proj != b->attr.proj.proj;
 289 }
 290
 291 /** Compares the attributes of two Alloc nodes. */
 292 static int node_cmp_attr_Alloc(const ir_node *a, const ir_node *b)
 293 {
 294         const alloc_attr *pa = &a->attr.alloc;
 295         const alloc_attr *pb = &b->attr.alloc;
 296         if (pa->where != pb->where || pa->type != pb->type)
 297                 return 1;
 298         return node_cmp_exception(a, b);
 299 }
 300
 301 /** Compares the attributes of two Free nodes. */
 302 static int node_cmp_attr_Free(const ir_node *a, const ir_node *b)
 303 {
 304         const free_attr *pa = &a->attr.free;
 305         const free_attr *pb = &b->attr.free;
 306         return (pa->where != pb->where) || (pa->type != pb->type);
 307 }
 308
 309 /** Compares the attributes of two SymConst nodes. */
 310 static int node_cmp_attr_SymConst(const ir_node *a, const ir_node *b)
 311 {
 312         const symconst_attr *pa = &a->attr.symc;
 313         const symconst_attr *pb = &b->attr.symc;
 314         return (pa->kind       != pb->kind)
 315             || (pa->sym.type_p != pb->sym.type_p);
 316 }
 317
 318 /** Compares the attributes of two Call nodes. */
 319 static int node_cmp_attr_Call(const ir_node *a, const ir_node *b)
 320 {
 321         const call_attr *pa = &a->attr.call;
 322         const call_attr *pb = &b->attr.call;
 323         if (pa->type != pb->type)
 324                 return 1;
 325         return node_cmp_exception(a, b);
 326 }
 327
 328 /** Compares the attributes of two Sel nodes. */
 329 static int node_cmp_attr_Sel(const ir_node *a, const ir_node *b)
 330 {
 331         const ir_entity *a_ent = get_Sel_entity(a);
 332         const ir_entity *b_ent = get_Sel_entity(b);
 333         return a_ent != b_ent;
 334 }
 335
 336 /** Compares the attributes of two Phi nodes. */
 337 static int node_cmp_attr_Phi(const ir_node *a, const ir_node *b)
 338 {
 339         (void) b;
 340         /* do not CSE Phi-nodes without any inputs when building new graphs */
 341         if (get_irn_arity(a) == 0 &&
 342                 irg_is_constrained(get_irn_irg(a), IR_GRAPH_CONSTRAINT_CONSTRUCTION)) {
 343             return 1;
 344         }
 345         return 0;
 346 }
 347
 348 /** Compares the attributes of two Load nodes. */
 349 static int node_cmp_attr_Load(const ir_node *a, const ir_node *b)
 350 {
 351         if (get_Load_volatility(a) == volatility_is_volatile ||
 352             get_Load_volatility(b) == volatility_is_volatile)
 353                 /* NEVER do CSE on volatile Loads */
 354                 return 1;
 355         /* do not CSE Loads with different alignment. Be conservative. */
 356         if (get_Load_unaligned(a) != get_Load_unaligned(b))
 357                 return 1;
 358         if (get_Load_mode(a) != get_Load_mode(b))
 359                 return 1;
 360         return node_cmp_exception(a, b);
 361 }
 362
 363 /** Compares the attributes of two Store nodes. */
 364 static int node_cmp_attr_Store(const ir_node *a, const ir_node *b)
 365 {
 366         /* do not CSE Stores with different alignment. Be conservative. */
 367         if (get_Store_unaligned(a) != get_Store_unaligned(b))
 368                 return 1;
 369         /* NEVER do CSE on volatile Stores */
 370         if (get_Store_volatility(a) == volatility_is_volatile ||
 371             get_Store_volatility(b) == volatility_is_volatile)
 372                 return 1;
 373         return node_cmp_exception(a, b);
 374 }
 375
 376 static int node_cmp_attr_CopyB(const ir_node *a, const ir_node *b)
 377 {
 378         if (get_CopyB_type(a) != get_CopyB_type(b))
 379                 return 1;
 380
 381         return node_cmp_exception(a, b);
 382 }
 383
 384 /** Compares the attributes of two Div nodes. */
 385 static int node_cmp_attr_Div(const ir_node *a, const ir_node *b)
 386 {
 387         const div_attr *ma = &a->attr.div;
 388         const div_attr *mb = &b->attr.div;
 389         if (ma->resmode != mb->resmode || ma->no_remainder  != mb->no_remainder)
 390                 return 1;
 391         return node_cmp_exception(a, b);
 392 }
 393
 394 /** Compares the attributes of two Mod nodes. */
 395 static int node_cmp_attr_Mod(const ir_node *a, const ir_node *b)
 396 {
 397         const mod_attr *ma = &a->attr.mod;
 398         const mod_attr *mb = &b->attr.mod;
 399         if (ma->resmode != mb->resmode)
 400                 return 1;
 401         return node_cmp_exception(a, b);
 402 }
 403
 404 static int node_cmp_attr_Cmp(const ir_node *a, const ir_node *b)
 405 {
 406         const cmp_attr *ma = &a->attr.cmp;
 407         const cmp_attr *mb = &b->attr.cmp;
 408         return ma->relation != mb->relation;
 409 }
 410
 411 /** Compares the attributes of two Confirm nodes. */
 412 static int node_cmp_attr_Confirm(const ir_node *a, const ir_node *b)
 413 {
 414         const confirm_attr *ma = &a->attr.confirm;
 415         const confirm_attr *mb = &b->attr.confirm;
 416         return ma->relation != mb->relation;
 417 }
 418
 419 /** Compares the attributes of two Builtin nodes. */
 420 static int node_cmp_attr_Builtin(const ir_node *a, const ir_node *b)
 421 {
 422         if (get_Builtin_kind(a) != get_Builtin_kind(b))
 423                 return 1;
 424         if (get_Builtin_type(a) != get_Builtin_type(b))
 425                 return 1;
 426         return node_cmp_exception(a, b);
 427 }
 428
 429 /** Compares the attributes of two ASM nodes. */
 430 static int node_cmp_attr_ASM(const ir_node *a, const ir_node *b)
 431 {
 432         if (get_ASM_text(a) != get_ASM_text(b))
 433                 return 1;
 434
 435         int n_inputs = get_ASM_n_inputs(a);
 436         if (n_inputs != get_ASM_n_inputs(b))
 437                 return 1;
 438
 439         const ir_asm_constraint *in_a = get_ASM_input_constraints(a);
 440         const ir_asm_constraint *in_b = get_ASM_input_constraints(b);
 441         for (int i = 0; i < n_inputs; ++i) {
 442                 if (in_a[i].pos != in_b[i].pos
 443                     || in_a[i].constraint != in_b[i].constraint
 444                     || in_a[i].mode != in_b[i].mode)
 445                         return 1;
 446         }
 447
 448         size_t n_outputs = get_ASM_n_output_constraints(a);
 449         if (n_outputs != get_ASM_n_output_constraints(b))
 450                 return 1;
 451
 452         const ir_asm_constraint *out_a = get_ASM_output_constraints(a);
 453         const ir_asm_constraint *out_b = get_ASM_output_constraints(b);
 454         for (size_t i = 0; i < n_outputs; ++i) {
 455                 if (out_a[i].pos != out_b[i].pos
 456                     || out_a[i].constraint != out_b[i].constraint
 457                     || out_a[i].mode != out_b[i].mode)
 458                         return 1;
 459         }
 460
 461         size_t n_clobbers = get_ASM_n_clobbers(a);
 462         if (n_clobbers != get_ASM_n_clobbers(b))
 463                 return 1;
 464
 465         ident **cla = get_ASM_clobbers(a);
 466         ident **clb = get_ASM_clobbers(b);
 467         for (size_t i = 0; i < n_clobbers; ++i) {
 468                 if (cla[i] != clb[i])
 469                         return 1;
 470         }
 471
 472         return node_cmp_exception(a, b);
 473 }
 474
 475 /** Compares the inexistent attributes of two Dummy nodes. */
 476 static int node_cmp_attr_Dummy(const ir_node *a, const ir_node *b)
 477 {
 478         (void) a;
 479         (void) b;
 480         /* Dummy nodes never equal by definition */
 481         return 1;
 482 }
 483
 484 static int node_cmp_attr_InstOf(const ir_node *a, const ir_node *b)
 485 {
 486         if (get_InstOf_type(a) != get_InstOf_type(b))
 487                 return 1;
 488         return node_cmp_exception(a, b);
 489 }
 490
 491 static void default_copy_attr(ir_graph *irg, const ir_node *old_node,
 492                               ir_node *new_node)
 493 {
 494         (void) irg;
 495
 496         assert(get_irn_op(old_node) == get_irn_op(new_node));
 497         memcpy(&new_node->attr, &old_node->attr, get_op_attr_size(get_irn_op(old_node)));
 498 }
 499
 500 /**
 501  * Copies all Call attributes stored in the old node to the new node.
 502  */
 503 static void call_copy_attr(ir_graph *irg, const ir_node *old_node,
 504                            ir_node *new_node)
 505 {
 506         default_copy_attr(irg, old_node, new_node);
 507         remove_Call_callee_arr(new_node);
 508 }
 509
 510 /**
 511  * Copies all Block attributes stored in the old node to the new node.
 512  */
 513 static void block_copy_attr(ir_graph *irg, const ir_node *old_node,
 514                             ir_node *new_node)
 515 {
 516         default_copy_attr(irg, old_node, new_node);
 517         new_node->attr.block.irg.irg       = irg;
 518         new_node->attr.block.phis          = NULL;
 519         new_node->attr.block.backedge      = new_backedge_arr(get_irg_obstack(irg), get_irn_arity(new_node));
 520         new_node->attr.block.block_visited = 0;
 521         memset(&new_node->attr.block.dom, 0, sizeof(new_node->attr.block.dom));
 522         memset(&new_node->attr.block.pdom, 0, sizeof(new_node->attr.block.pdom));
 523         /* It should be safe to copy the entity here, as it has no back-link to the old block.
 524          * It serves just as a label number, so copying a labeled block results in an exact copy.
 525          * This is at least what we need for DCE to work. */
 526         new_node->attr.block.entity         = old_node->attr.block.entity;
 527         new_node->attr.block.phis           = NULL;
 528 }
 529
 530 /**
 531  * Copies all phi attributes stored in old node to the new node
 532  */
 533 static void phi_copy_attr(ir_graph *irg, const ir_node *old_node,
 534                           ir_node *new_node)
 535 {
 536         default_copy_attr(irg, old_node, new_node);
 537         new_node->attr.phi.next       = NULL;
 538         new_node->attr.phi.u.backedge = new_backedge_arr(get_irg_obstack(irg), get_irn_arity(new_node));
 539 }
 540
 541 /**
 542  * Copies all ASM attributes stored in old node to the new node
 543  */
 544 static void ASM_copy_attr(ir_graph *irg, const ir_node *old_node,
 545                           ir_node *new_node)
 546 {
 547         default_copy_attr(irg, old_node, new_node);
 548         struct obstack *const obst = get_irg_obstack(irg);
 549         new_node->attr.assem.input_constraints  = DUP_ARR_D(ir_asm_constraint, obst, old_node->attr.assem.input_constraints);
 550         new_node->attr.assem.output_constraints = DUP_ARR_D(ir_asm_constraint, obst, old_node->attr.assem.output_constraints);
 551         new_node->attr.assem.clobbers           = DUP_ARR_D(ident*,            obst, old_node->attr.assem.clobbers);
 552 }
 553
 554 static void switch_copy_attr(ir_graph *irg, const ir_node *old_node,
 555                              ir_node *new_node)
 556 {
 557         const ir_switch_table *table = get_Switch_table(old_node);
 558         new_node->attr.switcha.table = ir_switch_table_duplicate(irg, table);
 559         new_node->attr.switcha.n_outs = old_node->attr.switcha.n_outs;
 560 }
 561
 562 static void register_node_cmp_func(ir_op *op, node_cmp_attr_func func)
 563 {
 564         op->ops.node_cmp_attr = func;
 565 }
 566
 567 static void register_node_hash_func(ir_op *op, hash_func func)
 568 {
 569         op->ops.hash = func;
 570 }
 571
 572 static void register_node_copy_attr_func(ir_op *op, copy_attr_func func)
 573 {
 574         op->ops.copy_attr = func;
 575 }
 576
 577 static void generated_init_op(void);
 578 static void generated_finish_op(void);
 579
 580 void firm_init_op(void)
 581 {
 582         opcodes = NEW_ARR_F(ir_op*, 0);
 583         generated_init_op();
 584         be_init_op();
 585
 586         register_node_cmp_func(op_ASM,      node_cmp_attr_ASM);
 587         register_node_cmp_func(op_Alloc,    node_cmp_attr_Alloc);
 588         register_node_cmp_func(op_Builtin,  node_cmp_attr_Builtin);
 589         register_node_cmp_func(op_Call,     node_cmp_attr_Call);
 590         register_node_cmp_func(op_Cmp,      node_cmp_attr_Cmp);
 591         register_node_cmp_func(op_Confirm,  node_cmp_attr_Confirm);
 592         register_node_cmp_func(op_Const,    node_cmp_attr_Const);
 593         register_node_cmp_func(op_CopyB,    node_cmp_attr_CopyB);
 594         register_node_cmp_func(op_Div,      node_cmp_attr_Div);
 595         register_node_cmp_func(op_Dummy,    node_cmp_attr_Dummy);
 596         register_node_cmp_func(op_Free,     node_cmp_attr_Free);
 597         register_node_cmp_func(op_InstOf,   node_cmp_attr_InstOf);
 598         register_node_cmp_func(op_Load,     node_cmp_attr_Load);
 599         register_node_cmp_func(op_Mod,      node_cmp_attr_Mod);
 600         register_node_cmp_func(op_Phi,      node_cmp_attr_Phi);
 601         register_node_cmp_func(op_Proj,     node_cmp_attr_Proj);
 602         register_node_cmp_func(op_Sel,      node_cmp_attr_Sel);
 603         register_node_cmp_func(op_Store,    node_cmp_attr_Store);
 604         register_node_cmp_func(op_SymConst, node_cmp_attr_SymConst);
 605
 606         register_node_hash_func(op_Const,    hash_Const);
 607         register_node_hash_func(op_SymConst, hash_SymConst);
 608
 609         register_node_copy_attr_func(op_Call,   call_copy_attr);
 610         register_node_copy_attr_func(op_Block,  block_copy_attr);
 611         register_node_copy_attr_func(op_Phi,    phi_copy_attr);
 612         register_node_copy_attr_func(op_ASM,    ASM_copy_attr);
 613         register_node_copy_attr_func(op_Switch, switch_copy_attr);
 614
 615         ir_register_opt_node_ops();
 616         ir_register_reassoc_node_ops();
 617         ir_register_verify_node_ops();
 618 }
 619
 620 void firm_finish_op(void)
 621 {
 622         be_finish_op();
 623         generated_finish_op();
 624         DEL_ARR_F(opcodes);
 625         opcodes = NULL;
 626 }
 627
 628 #include "gen_irop.c.inl"