f11728a36a2af6559c7ee168f3989ddb785443ee
[libfirm] / 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 Cast nodes. */
349 static int node_cmp_attr_Cast(const ir_node *a, const ir_node *b)
350 {
351         return get_Cast_type(a) != get_Cast_type(b);
352 }
353
354 /** Compares the attributes of two Load nodes. */
355 static int node_cmp_attr_Load(const ir_node *a, const ir_node *b)
356 {
357         if (get_Load_volatility(a) == volatility_is_volatile ||
358             get_Load_volatility(b) == volatility_is_volatile)
359                 /* NEVER do CSE on volatile Loads */
360                 return 1;
361         /* do not CSE Loads with different alignment. Be conservative. */
362         if (get_Load_unaligned(a) != get_Load_unaligned(b))
363                 return 1;
364         if (get_Load_mode(a) != get_Load_mode(b))
365                 return 1;
366         return node_cmp_exception(a, b);
367 }
368
369 /** Compares the attributes of two Store nodes. */
370 static int node_cmp_attr_Store(const ir_node *a, const ir_node *b)
371 {
372         /* do not CSE Stores with different alignment. Be conservative. */
373         if (get_Store_unaligned(a) != get_Store_unaligned(b))
374                 return 1;
375         /* NEVER do CSE on volatile Stores */
376         if (get_Store_volatility(a) == volatility_is_volatile ||
377             get_Store_volatility(b) == volatility_is_volatile)
378                 return 1;
379         return node_cmp_exception(a, b);
380 }
381
382 static int node_cmp_attr_CopyB(const ir_node *a, const ir_node *b)
383 {
384         if (get_CopyB_type(a) != get_CopyB_type(b))
385                 return 1;
386
387         return node_cmp_exception(a, b);
388 }
389
390 static int node_cmp_attr_Bound(const ir_node *a, const ir_node *b)
391 {
392         return node_cmp_exception(a, b);
393 }
394
395 /** Compares the attributes of two Div nodes. */
396 static int node_cmp_attr_Div(const ir_node *a, const ir_node *b)
397 {
398         const div_attr *ma = &a->attr.div;
399         const div_attr *mb = &b->attr.div;
400         if (ma->resmode != mb->resmode || ma->no_remainder  != mb->no_remainder)
401                 return 1;
402         return node_cmp_exception(a, b);
403 }
404
405 /** Compares the attributes of two Mod nodes. */
406 static int node_cmp_attr_Mod(const ir_node *a, const ir_node *b)
407 {
408         const mod_attr *ma = &a->attr.mod;
409         const mod_attr *mb = &b->attr.mod;
410         if (ma->resmode != mb->resmode)
411                 return 1;
412         return node_cmp_exception(a, b);
413 }
414
415 static int node_cmp_attr_Cmp(const ir_node *a, const ir_node *b)
416 {
417         const cmp_attr *ma = &a->attr.cmp;
418         const cmp_attr *mb = &b->attr.cmp;
419         return ma->relation != mb->relation;
420 }
421
422 /** Compares the attributes of two Confirm nodes. */
423 static int node_cmp_attr_Confirm(const ir_node *a, const ir_node *b)
424 {
425         const confirm_attr *ma = &a->attr.confirm;
426         const confirm_attr *mb = &b->attr.confirm;
427         return ma->relation != mb->relation;
428 }
429
430 /** Compares the attributes of two Builtin nodes. */
431 static int node_cmp_attr_Builtin(const ir_node *a, const ir_node *b)
432 {
433         if (get_Builtin_kind(a) != get_Builtin_kind(b))
434                 return 1;
435         if (get_Builtin_type(a) != get_Builtin_type(b))
436                 return 1;
437         return node_cmp_exception(a, b);
438 }
439
440 /** Compares the attributes of two ASM nodes. */
441 static int node_cmp_attr_ASM(const ir_node *a, const ir_node *b)
442 {
443         if (get_ASM_text(a) != get_ASM_text(b))
444                 return 1;
445
446         int n_inputs = get_ASM_n_inputs(a);
447         if (n_inputs != get_ASM_n_inputs(b))
448                 return 1;
449
450         const ir_asm_constraint *in_a = get_ASM_input_constraints(a);
451         const ir_asm_constraint *in_b = get_ASM_input_constraints(b);
452         for (int i = 0; i < n_inputs; ++i) {
453                 if (in_a[i].pos != in_b[i].pos
454                     || in_a[i].constraint != in_b[i].constraint
455                     || in_a[i].mode != in_b[i].mode)
456                         return 1;
457         }
458
459         size_t n_outputs = get_ASM_n_output_constraints(a);
460         if (n_outputs != get_ASM_n_output_constraints(b))
461                 return 1;
462
463         const ir_asm_constraint *out_a = get_ASM_output_constraints(a);
464         const ir_asm_constraint *out_b = get_ASM_output_constraints(b);
465         for (size_t i = 0; i < n_outputs; ++i) {
466                 if (out_a[i].pos != out_b[i].pos
467                     || out_a[i].constraint != out_b[i].constraint
468                     || out_a[i].mode != out_b[i].mode)
469                         return 1;
470         }
471
472         size_t n_clobbers = get_ASM_n_clobbers(a);
473         if (n_clobbers != get_ASM_n_clobbers(b))
474                 return 1;
475
476         ident **cla = get_ASM_clobbers(a);
477         ident **clb = get_ASM_clobbers(b);
478         for (size_t i = 0; i < n_clobbers; ++i) {
479                 if (cla[i] != clb[i])
480                         return 1;
481         }
482
483         return node_cmp_exception(a, b);
484 }
485
486 /** Compares the inexistent attributes of two Dummy nodes. */
487 static int node_cmp_attr_Dummy(const ir_node *a, const ir_node *b)
488 {
489         (void) a;
490         (void) b;
491         /* Dummy nodes never equal by definition */
492         return 1;
493 }
494
495 static int node_cmp_attr_InstOf(const ir_node *a, const ir_node *b)
496 {
497         if (get_InstOf_type(a) != get_InstOf_type(b))
498                 return 1;
499         return node_cmp_exception(a, b);
500 }
501
502 static void default_copy_attr(ir_graph *irg, const ir_node *old_node,
503                               ir_node *new_node)
504 {
505         (void) irg;
506
507         assert(get_irn_op(old_node) == get_irn_op(new_node));
508         memcpy(&new_node->attr, &old_node->attr, get_op_attr_size(get_irn_op(old_node)));
509 }
510
511 /**
512  * Copies all Call attributes stored in the old node to the new node.
513  */
514 static void call_copy_attr(ir_graph *irg, const ir_node *old_node,
515                            ir_node *new_node)
516 {
517         default_copy_attr(irg, old_node, new_node);
518         remove_Call_callee_arr(new_node);
519 }
520
521 /**
522  * Copies all Block attributes stored in the old node to the new node.
523  */
524 static void block_copy_attr(ir_graph *irg, const ir_node *old_node,
525                             ir_node *new_node)
526 {
527         default_copy_attr(irg, old_node, new_node);
528         new_node->attr.block.irg.irg       = irg;
529         new_node->attr.block.phis          = NULL;
530         new_node->attr.block.backedge      = new_backedge_arr(get_irg_obstack(irg), get_irn_arity(new_node));
531         new_node->attr.block.block_visited = 0;
532         memset(&new_node->attr.block.dom, 0, sizeof(new_node->attr.block.dom));
533         memset(&new_node->attr.block.pdom, 0, sizeof(new_node->attr.block.pdom));
534         /* It should be safe to copy the entity here, as it has no back-link to the old block.
535          * It serves just as a label number, so copying a labeled block results in an exact copy.
536          * This is at least what we need for DCE to work. */
537         new_node->attr.block.entity         = old_node->attr.block.entity;
538         new_node->attr.block.phis           = NULL;
539 }
540
541 /**
542  * Copies all phi attributes stored in old node to the new node
543  */
544 static void phi_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         new_node->attr.phi.next       = NULL;
549         new_node->attr.phi.u.backedge = new_backedge_arr(get_irg_obstack(irg), get_irn_arity(new_node));
550 }
551
552 /**
553  * Copies all ASM attributes stored in old node to the new node
554  */
555 static void ASM_copy_attr(ir_graph *irg, const ir_node *old_node,
556                           ir_node *new_node)
557 {
558         default_copy_attr(irg, old_node, new_node);
559         struct obstack *const obst = get_irg_obstack(irg);
560         new_node->attr.assem.input_constraints  = DUP_ARR_D(ir_asm_constraint, obst, old_node->attr.assem.input_constraints);
561         new_node->attr.assem.output_constraints = DUP_ARR_D(ir_asm_constraint, obst, old_node->attr.assem.output_constraints);
562         new_node->attr.assem.clobbers           = DUP_ARR_D(ident*,            obst, old_node->attr.assem.clobbers);
563 }
564
565 static void switch_copy_attr(ir_graph *irg, const ir_node *old_node,
566                              ir_node *new_node)
567 {
568         const ir_switch_table *table = get_Switch_table(old_node);
569         new_node->attr.switcha.table = ir_switch_table_duplicate(irg, table);
570         new_node->attr.switcha.n_outs = old_node->attr.switcha.n_outs;
571 }
572
573 static void register_node_cmp_func(ir_op *op, node_cmp_attr_func func)
574 {
575         op->ops.node_cmp_attr = func;
576 }
577
578 static void register_node_hash_func(ir_op *op, hash_func func)
579 {
580         op->ops.hash = func;
581 }
582
583 static void register_node_copy_attr_func(ir_op *op, copy_attr_func func)
584 {
585         op->ops.copy_attr = func;
586 }
587
588 static void generated_init_op(void);
589 static void generated_finish_op(void);
590
591 void firm_init_op(void)
592 {
593         opcodes = NEW_ARR_F(ir_op*, 0);
594         generated_init_op();
595         be_init_op();
596
597         register_node_cmp_func(op_ASM,      node_cmp_attr_ASM);
598         register_node_cmp_func(op_Alloc,    node_cmp_attr_Alloc);
599         register_node_cmp_func(op_Bound,    node_cmp_attr_Bound);
600         register_node_cmp_func(op_Builtin,  node_cmp_attr_Builtin);
601         register_node_cmp_func(op_Call,     node_cmp_attr_Call);
602         register_node_cmp_func(op_Cast,     node_cmp_attr_Cast);
603         register_node_cmp_func(op_Cmp,      node_cmp_attr_Cmp);
604         register_node_cmp_func(op_Confirm,  node_cmp_attr_Confirm);
605         register_node_cmp_func(op_Const,    node_cmp_attr_Const);
606         register_node_cmp_func(op_CopyB,    node_cmp_attr_CopyB);
607         register_node_cmp_func(op_Div,      node_cmp_attr_Div);
608         register_node_cmp_func(op_Dummy,    node_cmp_attr_Dummy);
609         register_node_cmp_func(op_Free,     node_cmp_attr_Free);
610         register_node_cmp_func(op_InstOf,   node_cmp_attr_InstOf);
611         register_node_cmp_func(op_Load,     node_cmp_attr_Load);
612         register_node_cmp_func(op_Mod,      node_cmp_attr_Mod);
613         register_node_cmp_func(op_Phi,      node_cmp_attr_Phi);
614         register_node_cmp_func(op_Proj,     node_cmp_attr_Proj);
615         register_node_cmp_func(op_Sel,      node_cmp_attr_Sel);
616         register_node_cmp_func(op_Store,    node_cmp_attr_Store);
617         register_node_cmp_func(op_SymConst, node_cmp_attr_SymConst);
618
619         register_node_hash_func(op_Const,    hash_Const);
620         register_node_hash_func(op_SymConst, hash_SymConst);
621
622         register_node_copy_attr_func(op_Call,   call_copy_attr);
623         register_node_copy_attr_func(op_Block,  block_copy_attr);
624         register_node_copy_attr_func(op_Phi,    phi_copy_attr);
625         register_node_copy_attr_func(op_ASM,    ASM_copy_attr);
626         register_node_copy_attr_func(op_Switch, switch_copy_attr);
627
628         ir_register_opt_node_ops();
629         ir_register_reassoc_node_ops();
630         ir_register_verify_node_ops();
631 }
632
633 void firm_finish_op(void)
634 {
635         be_finish_op();
636         generated_finish_op();
637         DEL_ARR_F(opcodes);
638         opcodes = NULL;
639 }
640
641 #include "gen_irop.c.inl"