1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Christian Schaefer, Goetz Lindenmaier
6 ** iropt --- optimizations intertwined with IR construction.
13 # include "irnode_t.h"
14 # include "irgraph_t.h"
23 /* Make types visible to allow most efficient access */
24 # include "entity_t.h"
26 /* Trivial inlineable routine for copy propagation.
27 Does follow Ids, needed to optimize inlined code. */
28 static inline ir_node *
29 follow_Id (ir_node *n)
31 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
35 static inline tarval *
38 if ((n != NULL) && (get_irn_op(n) == op_Const))
39 return get_Const_tarval(n);
44 /* if n can be computed, return the value, else NULL. Performs
45 constant folding. GL: Only if n is arithmetic operator? */
47 computed_value (ir_node *n)
51 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
52 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
56 /* get the operands we will work on for simple cases. */
58 a = get_binop_left(n);
59 b = get_binop_right(n);
60 } else if (is_unop(n)) {
64 /* if the operands are constants, get the target value, else set it NULL.
65 (a and b may be NULL if we treat a node that is no computation.) */
69 /* Perform the constant evaluation / computation. */
70 switch (get_irn_opcode(n)) {
72 res = get_Const_tarval(n);
74 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
75 && (get_irn_mode(a) != mode_p)) {
76 res = tarval_add (ta, tb);
80 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
81 && (get_irn_mode(a) != mode_p)) {
82 res = tarval_sub (ta, tb);
84 res = tarval_mode_null [get_irn_modecode (n)];
88 if (ta && mode_is_float(get_irn_mode(a)))
89 res = /*tarval_minus (ta);*/ res;
92 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
93 res = tarval_mul (ta, tb);
95 /* calls computed_value recursive and returns the 0 with proper
96 mode. Why is this an extra case? */
98 if ( (tarval_classify ((v = computed_value (a))) == 0)
99 || (tarval_classify ((v = computed_value (b))) == 0)) {
106 res = /*tarval_abs (ta);*/ res;
107 /* allowed or problems with max/min ?? */
111 res = tarval_and (ta, tb);
114 if ( (tarval_classify ((v = computed_value (a))) == 0)
115 || (tarval_classify ((v = computed_value (b))) == 0)) {
122 res = tarval_or (ta, tb);
125 if ( (tarval_classify ((v = computed_value (a))) == -1)
126 || (tarval_classify ((v = computed_value (b))) == -1)) {
131 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
132 case iro_Not: if (ta) { /*res = tarval_not (ta)*/; } break;
133 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
134 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
135 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
136 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
137 case iro_Conv: if(ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
143 a = get_Proj_pred(n);
144 /* Optimize Cmp nodes.
145 This performs a first step of unreachable code elimination.
146 Proj can not be computed, but folding a Cmp above the Proj here is
147 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
149 There are several case where we can evaluate a Cmp node:
150 1. The nodes compared are both the same. If we compare for
151 equal, this will return true, else it will return false.
152 This step relies on cse.
153 2. The predecessors of Cmp are target values. We can evaluate
155 3. The predecessors are Allocs or void* constants. Allocs never
156 return NULL, they raise an exception. Therefore we can predict
158 if (get_irn_op(a) == op_Cmp) {
159 aa = get_Cmp_left(a);
160 ab = get_Cmp_right(a);
161 if (aa == ab) { /* 1.: */
162 /* This is a tric with the bits used for encoding the Cmp
163 Proj numbers, the following statement is not the same:
164 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
165 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
167 tarval *taa = computed_value (aa);
168 tarval *tab = computed_value (ab);
169 if (taa && tab) { /* 2.: */
170 /* strange checks... */
171 ir_pncmp flags = tarval_comp (taa, tab);
172 if (flags != irpn_False) {
173 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
175 } else { /* check for 3.: */
176 ir_node *aaa = skip_nop(skip_Proj(aa));
177 ir_node *aba = skip_nop(skip_Proj(ab));
178 if ( ( (/* aa is ProjP and aaa is Alloc */
179 (get_irn_op(aa) == op_Proj)
180 && (get_irn_mode(aa) == mode_p)
181 && (get_irn_op(aaa) == op_Alloc))
182 && ( (/* ab is constant void */
183 (get_irn_op(ab) == op_Const)
184 && (get_irn_mode(ab) == mode_p)
185 && (get_Const_tarval(ab) == tarval_p_void))
186 || (/* ab is other Alloc */
187 (get_irn_op(ab) == op_Proj)
188 && (get_irn_mode(ab) == mode_p)
189 && (get_irn_op(aba) == op_Alloc)
191 || (/* aa is void and aba is Alloc */
192 (get_irn_op(aa) == op_Const)
193 && (get_irn_mode(aa) == mode_p)
194 && (get_Const_tarval(aa) == tarval_p_void)
195 && (get_irn_op(ab) == op_Proj)
196 && (get_irn_mode(ab) == mode_p)
197 && (get_irn_op(aba) == op_Alloc)))
199 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
203 /* printf(" # comp_val: Proj node, not optimized\n"); */
215 /* returns 1 if the a and b are pointers to different locations. */
217 different_identity (ir_node *a, ir_node *b)
219 assert (get_irn_mode (a) == mode_p
220 && get_irn_mode (b) == mode_p);
222 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
223 ir_node *a1 = get_Proj_pred (a);
224 ir_node *b1 = get_Proj_pred (b);
225 if (a1 != b1 && get_irn_op (a1) == op_Alloc
226 && get_irn_op (b1) == op_Alloc)
233 /* equivalent_node returns a node equivalent to N. It skips all nodes that
234 perform no actual computation, as, e.g., the Id nodes. It does not create
235 new nodes. It is therefore safe to free N if the node returned is not N.
236 If a node returns a Tuple we can not just skip it. If the size of the
237 in array fits, we transform n into a tuple (e.g., Div). */
239 equivalent_node (ir_node *n)
242 ir_node *a = NULL; /* to shutup gcc */
243 ir_node *b = NULL; /* to shutup gcc */
244 ir_node *c = NULL; /* to shutup gcc */
246 ins = get_irn_arity (n);
248 /* get the operands we will work on */
250 a = get_binop_left(n);
251 b = get_binop_right(n);
252 } else if (is_unop(n)) {
256 /* skip unnecessary nodes. */
257 switch (get_irn_opcode (n)) {
260 /* The Block constructor does not call optimize, but mature_block
261 calls the optimization. */
262 assert(get_Block_matured(n));
264 /* A single entry Block following a single exit Block can be merged,
265 if it is not the Start block. */
266 /* !!! Beware, all Phi-nodes of n must have been optimized away.
267 This should be true, as the block is matured before optimize is called.
268 But what about Phi-cycles with the Phi0/Id that could not be resolved? */
269 if (get_Block_n_cfgpreds(n) == 1
270 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
271 n = get_nodes_Block(get_Block_cfgpred(n, 0));
273 } else if ((n != current_ir_graph->start_block) &&
274 (n != current_ir_graph->end_block) ) {
276 /* If all inputs are dead, this block is dead too, except if it is
277 the start or end block. This is a step of unreachable code
279 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
280 if (!is_Bad(get_Block_cfgpred(n, i))) break;
282 if (i == get_Block_n_cfgpreds(n))
288 case iro_Jmp: /* GL: Why not same for op_Raise?? */
289 /* unreachable code elimination */
290 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
292 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
293 See cases for iro_Cond and iro_Proj in transform_node. */
294 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
295 case iro_Or: if (a == b) {n = a; break;}
300 /* After running compute_node there is only one constant predecessor.
301 Find this predecessors value and remember the other node: */
302 if ((tv = computed_value (a))) {
304 } else if ((tv = computed_value (b))) {
308 /* If this predecessors constant value is zero, the operation is
309 unnecessary. Remove it: */
310 if (tarval_classify (tv) == 0) {
320 /* these operations are not commutative. Test only one predecessor. */
321 if (tarval_classify (computed_value (b)) == 0) {
323 /* Test if b > #bits of a ==> return 0 / divide b by #bits
324 --> transform node? */
327 case iro_Not: /* NotNot x == x */
328 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
329 out of bounds exception if min =! max? */
330 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
331 n = get_unop_op(get_unop_op(n));
334 /* Mul is commutative and has again an other neutral element. */
335 if (tarval_classify (computed_value (a)) == 1) {
337 } else if (tarval_classify (computed_value (b)) == 1) {
342 /* Div is not commutative. */
343 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
344 /* Turn Div into a tuple (mem, bad, a) */
345 ir_node *mem = get_Div_mem(n);
346 turn_into_tuple(n, 3);
347 set_Tuple_pred(n, 0, mem);
348 set_Tuple_pred(n, 1, new_Bad());
349 set_Tuple_pred(n, 2, a);
352 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
353 teated in transform node.
354 case iro_Mod, Quot, DivMod
358 /* And has it's own neutral element */
359 else if (tarval_classify (computed_value (a)) == -1) {
361 } else if (tarval_classify (computed_value (b)) == -1) {
366 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
368 } else if (get_irn_mode(n) == mode_b) {
369 if (get_irn_op(a) == op_Conv &&
370 get_irn_mode (get_Conv_op(a)) == mode_b) {
371 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
378 /* Several optimizations:
379 - no Phi in start block.
380 - remove Id operators that are inputs to Phi
381 - fold Phi-nodes, iff they have only one predecessor except
387 ir_node *block = NULL; /* to shutup gcc */
388 ir_node *first_val = NULL; /* to shutup gcc */
389 ir_node *scnd_val = NULL; /* to shutup gcc */
391 n_preds = get_Phi_n_preds(n);
393 block = get_nodes_Block(n);
394 assert(get_irn_op (block) == op_Block);
396 /* there should be no Phi nodes in the Start region. */
397 if (block == current_ir_graph->start_block) {
402 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
403 /* GL: why not return new_Bad? */
408 /* first we test for a special case: */
409 /* Confirm is a special node fixing additional information for a
410 value that is known at a certain point. This is useful for
411 dataflow analysis. */
413 ir_node *a = follow_Id (get_Phi_pred(n, 0));
414 ir_node *b = follow_Id (get_Phi_pred(n, 1));
415 if ( (get_irn_op(a) == op_Confirm)
416 && (get_irn_op(b) == op_Confirm)
417 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
418 && (get_irn_n(a, 1) == get_irn_n (b, 1))
419 && (a->data.num == (~b->data.num & irpn_True) )) {
420 n = follow_Id (get_irn_n(a, 0));
426 /* Find first non-self-referencing input */
427 for (i = 0; i < n_preds; ++i) {
428 first_val = follow_Id(get_Phi_pred(n, i));
430 set_Phi_pred(n, i, first_val);
431 if ( (first_val != n) /* not self pointer */
432 && (get_irn_op(first_val) != op_Bad) /* value not dead */
433 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
434 break; /* then found first value. */
438 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
439 if (i >= n_preds) { n = new_Bad(); break; }
443 /* follow_Id () for rest of inputs, determine if any of these
444 are non-self-referencing */
445 while (++i < n_preds) {
446 scnd_val = follow_Id(get_Phi_pred(n, i));
448 set_Phi_pred(n, i, scnd_val);
450 && (scnd_val != first_val)
451 && (get_irn_op(scnd_val) != op_Bad)
452 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
457 /* Fold, if no multiple distinct non-self-referencing inputs */
461 /* skip the remaining Ids. */
462 while (++i < n_preds) {
463 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
471 a = skip_Proj(get_Load_mem(n));
472 b = skip_Proj(get_Load_ptr(n));
474 if (get_irn_op(a) == op_Store) {
475 if ( different_identity (b, get_Store_ptr(a))) {
476 /* load and store use different pointers, therefore load
477 needs not take store's memory but the state before. */
478 set_Load_mem (n, get_Store_mem(a));
479 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
485 /* remove unnecessary store. */
487 a = skip_Proj(get_Store_mem(n));
488 b = get_Store_ptr(n);
489 c = skip_Proj(get_Store_value(n));
491 if (get_irn_op(a) == op_Store
492 && get_Store_ptr(a) == b
493 && skip_Proj(get_Store_value(a)) == c) {
494 /* We have twice exactly the same store -- a write after write. */
496 } else if (get_irn_op(c) == op_Load
497 && (a == c || skip_Proj(get_Load_mem(c)) == a)
498 && get_Load_ptr(c) == b )
499 /* !!!??? and a cryptic test */ {
500 /* We just loaded the value from the same memory, i.e., the store
501 doesn't change the memory -- a write after read. */
502 turn_into_tuple(n, 2);
503 set_Tuple_pred(n, 0, a);
504 set_Tuple_pred(n, 1, new_Bad());
511 a = get_Proj_pred(n);
513 if ( get_irn_op(a) == op_Tuple) {
514 /* Remove the Tuple/Proj combination. */
515 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
516 n = get_Tuple_pred(a, get_Proj_proj(n));
518 assert(0); /* This should not happen! (GL added this assert) */
521 } else if (get_irn_mode(n) == mode_X &&
522 is_Bad(get_nodes_Block(n))) {
523 /* Remove dead control flow. */
537 } /* end equivalent_node() */
540 /* tries several [inplace] [optimizing] transformations and returns a
541 equivalent node. The difference to equivalent_node is that these
542 transformations _do_ generate new nodes, and thus the old node must
543 not be freed even if the equivalent node isn't the old one. */
545 transform_node (ir_node *n)
548 ir_node *a = NULL, *b;
551 switch (get_irn_opcode(n)) {
557 a = get_DivMod_left(n);
558 b = get_DivMod_right(n);
559 mode = get_irn_mode(a);
561 if (!( mode_is_int(get_irn_mode(a))
562 && mode_is_int(get_irn_mode(b))))
566 a = new_Const (mode, tarval_from_long (mode, 1));
567 b = new_Const (mode, tarval_from_long (mode, 0));
574 if (tarval_classify(tb) == 1) {
575 b = new_Const (mode, tarval_from_long (mode, 0));
579 resa = tarval_div (ta, tb);
580 if (!resa) break; /* Causes exception!!! Model by replacing through
581 Jmp for X result!? */
582 resb = tarval_mod (ta, tb);
583 if (!resb) break; /* Causes exception! */
584 a = new_Const (mode, resa);
585 b = new_Const (mode, resb);
588 } else if (tarval_classify (ta) == 0) {
593 if (evaluated) { /* replace by tuple */
594 ir_node *mem = get_DivMod_mem(n);
595 turn_into_tuple(n, 4);
596 set_Tuple_pred(n, 0, mem);
597 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
598 set_Tuple_pred(n, 2, a);
599 set_Tuple_pred(n, 3, b);
600 assert(get_nodes_Block(n));
606 /* Replace the Cond by a Jmp if it branches on a constant
609 a = get_Cond_selector(n);
612 if (ta && (get_irn_mode(a) == mode_b)) {
613 /* It's a boolean Cond, branching on a boolean constant.
614 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
615 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
616 turn_into_tuple(n, 2);
617 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
618 set_Tuple_pred(n, 0, new_Bad());
619 set_Tuple_pred(n, 1, jmp);
621 set_Tuple_pred(n, 0, jmp);
622 set_Tuple_pred(n, 1, new_Bad());
624 } else if (ta && (get_irn_mode(a) == mode_I)) {
625 /* I don't want to allow Tuples smaller than the biggest Proj.
626 Also this tuple might get really big...
627 I generate the Jmp here, and remember it in link. Link is used
628 when optimizing Proj. */
629 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
630 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
631 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
632 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
633 /* The Eor is a negate. Generate a new Cond without the negate,
634 simulate the negate by exchanging the results. */
635 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
637 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
638 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
639 /* A Not before the Cond. Generate a new Cond without the Not,
640 simulate the Not by exchanging the results. */
641 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
648 a = get_Proj_pred(n);
650 if ( (get_irn_op(a) == op_Cond)
652 && get_irn_op(get_irn_link(a)) == op_Cond) {
653 /* Use the better Cond if the Proj projs from a Cond which get's
654 its result from an Eor/Not. */
655 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
656 || (get_irn_op(get_Cond_selector(a)) == op_Not))
657 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
658 && (get_irn_op(get_irn_link(a)) == op_Cond)
659 && (get_Cond_selector(get_irn_link(a)) ==
660 get_Eor_left(get_Cond_selector(a))));
661 set_Proj_pred(n, get_irn_link(a));
662 if (get_Proj_proj(n) == 0)
666 } else if ( (get_irn_op(a) == op_Cond)
667 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
669 /* The Cond is a Switch on a Constant */
670 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
671 /* The always taken branch, reuse the existing Jmp. */
672 if (!get_irn_link(a)) /* well, if it exists ;-> */
673 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
674 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
677 /* a never taken branch */
683 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
685 b = get_Eor_right(n);
687 if ( (get_irn_mode(n) == mode_b)
688 && (get_irn_op(a) == op_Proj)
689 && (get_irn_mode(a) == mode_b)
690 && (tarval_classify (computed_value (b)) == 1)
691 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
692 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
693 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
694 mode_b, get_negated_pnc(get_Proj_proj(a)));
695 else if ( (get_irn_mode(n) == mode_b)
696 && (tarval_classify (computed_value (b)) == 1))
697 /* The Eor is a Not. Replace it by a Not. */
698 /* ????!!!Extend to bitfield 1111111. */
699 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
705 if ( (get_irn_mode(n) == mode_b)
706 && (get_irn_op(a) == op_Proj)
707 && (get_irn_mode(a) == mode_b)
708 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
709 /* We negate a Cmp. The Cmp has the negated result anyways! */
710 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
711 mode_b, get_negated_pnc(get_Proj_proj(a)));
719 /* **************** Common Subexpression Elimination **************** */
721 /* Compare function for two nodes in the hash table. Gets two */
722 /* nodes as parameters. */
723 /* @@@ a+b != b+a ? */
725 vt_cmp (const void *elt, const void *key)
733 if (a == b) return 0;
735 if ((get_irn_op(a) != get_irn_op(b)) ||
736 (get_irn_mode(a) != get_irn_mode(b))) return 1;
738 /* compare if a's in and b's in are equal */
739 /* GL: we optimize only nodes with in arrays of fixed sizes.
740 if (get_irn_arity (a) != -2) {
741 ins = get_irn_arity (a);
742 if (ins != get_irn_arity (b)) return 1;
743 ain = get_irn_in (a);
744 bin = get_irn_in (b);
747 if (get_irn_arity (a) != get_irn_arity(b))
750 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
751 /* do if (*ain++ != *bin++) return 1; while (ins--); */
752 for (i = -1; i < get_irn_arity(a); i++)
753 if (get_irn_n(a, i) != get_irn_n(b, i))
757 switch (get_irn_opcode(a)) {
759 return get_irn_const_attr (a) != get_irn_const_attr (b);
761 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
763 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
764 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
766 return (get_irn_free_attr(a) != get_irn_free_attr(b));
768 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
769 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
771 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
772 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
774 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
775 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
776 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
777 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
778 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
779 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
781 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
789 ir_node_hash (ir_node *node)
794 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
795 h = get_irn_arity(node);
797 /* consider all in nodes... except the block. */
798 for (i = 0; i < get_irn_arity(node); i++) {
799 h = 9*h + (unsigned long)get_irn_n(node, i);
803 h = 9*h + (unsigned long) get_irn_mode (node);
805 h = 9*h + (unsigned long) get_irn_op (node);
811 new_identities (void)
813 return new_pset (vt_cmp, TUNE_NIR_NODES);
817 del_identities (pset *value_table)
819 del_pset (value_table);
822 /* Return the canonical node computing the same value as n.
823 Looks up the node in a hash table. */
824 static inline ir_node *
825 identify (pset *value_table, ir_node *n)
829 if (!value_table) return n;
831 switch (get_irn_opcode (n)) {
838 /* for commutative operators perform a OP b == b OP a */
839 if (get_binop_left(n) > get_binop_right(n)) {
840 ir_node *h = get_binop_left(n);
841 set_binop_left(n, get_binop_right(n));
842 set_binop_right(n, h);
848 o = pset_find (value_table, n, ir_node_hash (n));
854 /* Return the canonical node computing the same value as n.
855 Looks up the node in a hash table, enters it in the table
856 if it isn't there yet. */
858 identify_remember (pset *value_table, ir_node *node)
862 if (!value_table) return node;
864 /* lookup or insert in hash table with given hash key. */
865 o = pset_insert (value_table, node, ir_node_hash (node));
867 if (o == node) return node;
872 /* garbage in, garbage out. If a node has a dead input, i.e., the
873 Bad node is input to the node, return the Bad node. */
874 static inline ir_node *
878 ir_op* op = get_irn_op(node);
880 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
881 blocks predecessors is dead. */
882 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
883 for (i = -1; i < get_irn_arity(node); i++) {
884 if (is_Bad(get_irn_n(node, i))) {
890 /* If Block has only Bads as predecessors it's garbage. */
891 /* If Phi has only Bads as predecessors it's garbage. */
892 if (op == op_Block || op == op_Phi) {
893 for (i = 0; i < get_irn_arity(node); i++) {
894 if (!is_Bad(get_irn_n(node, i))) break;
896 if (i = get_irn_arity(node)) node = new_Bad();
903 /* These optimizations deallocate nodes from the obstack.
904 It can only be called if it is guaranteed that no other nodes
905 reference this one, i.e., right after construction of a node. */
907 optimize (ir_node *n)
912 /* Allways optimize Phi nodes: part of the construction. */
913 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
915 /* if not optimize return n */
917 printf(" attention: empty node!!! \n");
921 /* constant expression evaluation / constant folding */
922 if (get_opt_constant_folding()) {
923 /* constants can not be evaluated */
924 if (get_irn_op(n) != op_Const) {
925 /* try to evaluate */
926 tv = computed_value (n);
928 /* evaluation was succesful -- replace the node. */
929 obstack_free (current_ir_graph->obst, n);
930 return new_Const (get_tv_mode (tv), tv);
935 /* remove unnecessary nodes */
936 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
937 n = equivalent_node (n);
939 /** common subexpression elimination **/
940 /* Checks whether n is already available. */
941 /* The block input is used to distinguish different subexpressions. Right
942 now all nodes are pinned to blocks, i.e., the cse only finds common
943 subexpressions within a block. */
945 n = identify (current_ir_graph->value_table, n);
946 /* identify found a cse, so deallocate the old node. */
948 obstack_free (current_ir_graph->obst, old_n);
949 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
952 /* Some more constant expression evaluation that does not allow to
954 if (get_opt_constant_folding())
955 n = transform_node (n);
957 /* Remove nodes with dead (Bad) input. */
959 /* Now we can verify the node, as it has no dead inputs any more. */
962 /* Now we have a legal, useful node. Enter it in hash table for cse */
964 n = identify_remember (current_ir_graph->value_table, n);
967 #if 0 /* GL: what's the use of this?? */
968 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
969 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
970 pdeq_putr (current_ir_graph->keep.living, n);
977 /* These optimizations never deallocate nodes. This can cause dead
978 nodes lying on the obstack. Remove these by a dead node elimination,
979 i.e., a copying garbage collection. */
981 optimize_in_place (ir_node *n)
986 if (!get_optimize()) return n;
988 /* if not optimize return n */
990 /* Here this is possible. Why? */
994 /* constant expression evaluation / constant folding */
995 if (get_opt_constant_folding()) {
996 /* constants can not be evaluated */
997 if (get_irn_op(n) != op_Const) {
998 /* try to evaluate */
999 tv = computed_value (n);
1001 /* evaluation was succesful -- replace the node. */
1002 n = new_Const (get_tv_mode (tv), tv);
1003 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1005 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1010 /* remove unnecessary nodes */
1011 /*if (get_opt_constant_folding()) */
1012 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1013 n = equivalent_node (n);
1015 /** common subexpression elimination **/
1016 /* Checks whether n is already available. */
1017 /* The block input is used to distinguish different subexpressions. Right
1018 now all nodes are pinned to blocks, i.e., the cse only finds common
1019 subexpressions within a block. */
1021 n = identify (current_ir_graph->value_table, n);
1023 /* identify found a cse, so deallocate the old node. */
1025 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1028 /* Some more constant expression evaluation. */
1029 if (get_opt_constant_folding())
1030 n = transform_node (n);
1032 /* Remove nodes with dead (Bad) input. */
1034 /* Now we can verify the node, as it has no dead inputs any more. */
1037 /* Now we have a legal, useful node. Enter it in hash table for cse.
1038 Blocks should be unique anyways. (Except the successor of start:
1039 is cse with the start block!) */
1040 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1041 n = identify_remember (current_ir_graph->value_table, n);