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