3 * File name: ir/ir/iropt.c
4 * Purpose: iropt --- optimizations intertwined with IR construction.
5 * Author: Christian Schaefer
6 * Modified by: Goetz Lindenmaier
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 # include "irnode_t.h"
18 # include "irgraph_t.h"
19 # include "irmode_t.h"
21 # include "ircons_t.h"
25 # include "dbginfo_t.h"
26 # include "iropt_dbg.h"
27 # include "irflag_t.h"
28 # include "firmstat.h"
31 /* Make types visible to allow most efficient access */
32 # include "entity_t.h"
35 * Trivial INLINEable routine for copy propagation.
36 * Does follow Ids, needed to optimize INLINEd code.
38 static INLINE ir_node *
39 follow_Id (ir_node *n)
41 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
46 * Returns the tarval of a Const node or tarval_bad for all other nodes.
48 static INLINE tarval *
51 if ((n != NULL) && (get_irn_op(n) == op_Const))
52 return get_Const_tarval(n); /* might return tarval_bad */
58 * return the value of a Constant
60 static tarval *computed_value_Const(ir_node *n)
62 return get_Const_tarval(n);
66 * return the value of a 'sizeof' SymConst
68 static tarval *computed_value_SymConst(ir_node *n)
70 if ((get_SymConst_kind(n) == symconst_size) &&
71 (get_type_state(get_SymConst_type(n))) == layout_fixed)
72 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
77 * return the value of an Add
79 static tarval *computed_value_Add(ir_node *n)
81 ir_node *a = get_Add_left(n);
82 ir_node *b = get_Add_right(n);
84 tarval *ta = value_of(a);
85 tarval *tb = value_of(b);
87 if ((ta != tarval_bad) && (tb != tarval_bad)
88 && (get_irn_mode(a) == get_irn_mode(b))
89 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
90 return tarval_add(ta, tb);
96 * return the value of a Sub
99 static tarval *computed_value_Sub(ir_node *n)
101 ir_node *a = get_Sub_left(n);
102 ir_node *b = get_Sub_right(n);
108 return get_tarval_null(get_irn_mode(n));
113 if ((ta != tarval_bad) && (tb != tarval_bad)
114 && (get_irn_mode(a) == get_irn_mode(b))
115 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
116 return tarval_sub(ta, tb);
122 * return the value of an unary Minus
124 static tarval *computed_value_Minus(ir_node *n)
126 ir_node *a = get_Minus_op(n);
127 tarval *ta = value_of(a);
129 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
130 return tarval_neg(ta);
136 * return the value of a Mul
138 static tarval *computed_value_Mul(ir_node *n)
140 ir_node *a = get_Mul_left(n);
141 ir_node *b = get_Mul_right(n);
143 tarval *ta = value_of(a);
144 tarval *tb = value_of(b);
146 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
147 return tarval_mul(ta, tb);
149 /* a*0 = 0 or 0*b = 0:
150 calls computed_value recursive and returns the 0 with proper
154 if ( ( ((v = ta) != tarval_bad)
155 && (v == get_mode_null(get_tarval_mode(v))) )
156 || ( ((v = tb) != tarval_bad)
157 && (v == get_mode_null(get_tarval_mode(v))) )) {
165 * return the value of a floating point Quot
167 static tarval *computed_value_Quot(ir_node *n)
169 ir_node *a = get_Quot_left(n);
170 ir_node *b = get_Quot_right(n);
172 tarval *ta = value_of(a);
173 tarval *tb = value_of(b);
175 /* This was missing in original implementation. Why? */
176 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
177 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
178 return tarval_quo(ta, tb);
184 * calculate the value of an integer Div of two nodes
185 * Special case: 0 / b
187 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
189 tarval *ta = value_of(a);
190 tarval *tb = value_of(b);
192 /* Compute c1 / c2 or 0 / a, a != 0 */
193 if ((ta != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) {
194 if (tb != tarval_bad) /* div by zero: return tarval_bad */
195 return tarval_div(ta, tb);
196 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
203 * return the value of an integer Div
205 static tarval *computed_value_Div(ir_node *n)
207 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
211 * calculate the value of an integer Mod of two nodes
212 * Special case: a % 1
214 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
216 tarval *ta = value_of(a);
217 tarval *tb = value_of(b);
219 /* Compute c1 % c2 or a % 1 */
220 if (tb != tarval_bad) {
221 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
222 return tarval_mod(ta, tb);
223 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
224 return get_mode_null(get_irn_mode(a));
231 * return the value of an integer Mod
233 static tarval *computed_value_Mod(ir_node *n)
235 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
239 * return the value of an Abs
241 static tarval *computed_value_Abs(ir_node *n)
243 ir_node *a = get_Abs_op(n);
244 tarval *ta = value_of(a);
246 if (ta != tarval_bad)
247 return tarval_abs(ta);
253 * return the value of an And
254 * Special case: a & 0, 0 & b
256 static tarval *computed_value_And(ir_node *n)
258 ir_node *a = get_And_left(n);
259 ir_node *b = get_And_right(n);
261 tarval *ta = value_of(a);
262 tarval *tb = value_of(b);
264 if ((ta != tarval_bad) && (tb != tarval_bad)) {
265 return tarval_and (ta, tb);
269 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_NULL)
270 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
278 * return the value of an Or
279 * Special case: a | 1...1, 1...1 | b
281 static tarval *computed_value_Or(ir_node *n)
283 ir_node *a = get_Or_left(n);
284 ir_node *b = get_Or_right(n);
286 tarval *ta = value_of(a);
287 tarval *tb = value_of(b);
289 if ((ta != tarval_bad) && (tb != tarval_bad)) {
290 return tarval_or (ta, tb);
293 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
294 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
302 * return the value of an Eor
304 static tarval *computed_value_Eor(ir_node *n)
306 ir_node *a = get_Eor_left(n);
307 ir_node *b = get_Eor_right(n);
309 tarval *ta = value_of(a);
310 tarval *tb = value_of(b);
312 if ((ta != tarval_bad) && (tb != tarval_bad)) {
313 return tarval_eor (ta, tb);
319 * return the value of a Not
321 static tarval *computed_value_Not(ir_node *n)
323 ir_node *a = get_Not_op(n);
324 tarval *ta = value_of(a);
326 if (ta != tarval_bad)
327 return tarval_not(ta);
333 * return the value of a Shl
335 static tarval *computed_value_Shl(ir_node *n)
337 ir_node *a = get_Shl_left(n);
338 ir_node *b = get_Shl_right(n);
340 tarval *ta = value_of(a);
341 tarval *tb = value_of(b);
343 if ((ta != tarval_bad) && (tb != tarval_bad)) {
344 return tarval_shl (ta, tb);
350 * return the value of a Shr
352 static tarval *computed_value_Shr(ir_node *n)
354 ir_node *a = get_Shr_left(n);
355 ir_node *b = get_Shr_right(n);
357 tarval *ta = value_of(a);
358 tarval *tb = value_of(b);
360 if ((ta != tarval_bad) && (tb != tarval_bad)) {
361 return tarval_shr (ta, tb);
367 * return the value of a Shrs
369 static tarval *computed_value_Shrs(ir_node *n)
371 ir_node *a = get_Shrs_left(n);
372 ir_node *b = get_Shrs_right(n);
374 tarval *ta = value_of(a);
375 tarval *tb = value_of(b);
377 if ((ta != tarval_bad) && (tb != tarval_bad)) {
378 return tarval_shrs (ta, tb);
384 * return the value of a Rot
386 static tarval *computed_value_Rot(ir_node *n)
388 ir_node *a = get_Rot_left(n);
389 ir_node *b = get_Rot_right(n);
391 tarval *ta = value_of(a);
392 tarval *tb = value_of(b);
394 if ((ta != tarval_bad) && (tb != tarval_bad)) {
395 return tarval_rot (ta, tb);
401 * return the value of a Conv
403 static tarval *computed_value_Conv(ir_node *n)
405 ir_node *a = get_Conv_op(n);
406 tarval *ta = value_of(a);
408 if (ta != tarval_bad)
409 return tarval_convert_to(ta, get_irn_mode(n));
415 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
417 static tarval *computed_value_Proj(ir_node *n)
419 ir_node *a = get_Proj_pred(n);
423 /* Optimize Cmp nodes.
424 This performs a first step of unreachable code elimination.
425 Proj can not be computed, but folding a Cmp above the Proj here is
426 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
428 There are several case where we can evaluate a Cmp node:
429 1. The nodes compared are both the same. If we compare for
430 equal, greater equal, ... this will return true, else it
431 will return false. This step relies on cse.
432 2. The predecessors of Cmp are target values. We can evaluate
434 3. The predecessors are Allocs or void* constants. Allocs never
435 return NULL, they raise an exception. Therefore we can predict
437 switch (get_irn_opcode(a)) {
439 aa = get_Cmp_left(a);
440 ab = get_Cmp_right(a);
441 proj_nr = get_Proj_proj(n);
443 if (aa == ab) { /* 1.: */
444 /* This is a trick with the bits used for encoding the Cmp
445 Proj numbers, the following statement is not the same:
446 return new_tarval_from_long (proj_nr == Eq, mode_b) */
447 return new_tarval_from_long (proj_nr & Eq, mode_b);
449 tarval *taa = computed_value (aa);
450 tarval *tab = computed_value (ab);
452 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
453 /* strange checks... */
454 pnc_number flags = tarval_cmp (taa, tab);
455 if (flags != False) {
456 return new_tarval_from_long (proj_nr & flags, mode_b);
458 } else { /* check for 3.: */
459 ir_node *aaa = skip_Id(skip_Proj(aa));
460 ir_node *aba = skip_Id(skip_Proj(ab));
462 if ( ( (/* aa is ProjP and aaa is Alloc */
463 (get_irn_op(aa) == op_Proj)
464 && (mode_is_reference(get_irn_mode(aa)))
465 && (get_irn_op(aaa) == op_Alloc))
466 && ( (/* ab is constant void */
467 (get_irn_op(ab) == op_Const)
468 && (mode_is_reference(get_irn_mode(ab)))
469 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
470 || (/* ab is other Alloc */
471 (get_irn_op(ab) == op_Proj)
472 && (mode_is_reference(get_irn_mode(ab)))
473 && (get_irn_op(aba) == op_Alloc)
475 || (/* aa is void and aba is Alloc */
476 (get_irn_op(aa) == op_Const)
477 && (mode_is_reference(get_irn_mode(aa)))
478 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
479 && (get_irn_op(ab) == op_Proj)
480 && (mode_is_reference(get_irn_mode(ab)))
481 && (get_irn_op(aba) == op_Alloc)))
483 return new_tarval_from_long (proj_nr & Ne, mode_b);
489 /* compute either the Div or the Mod part */
490 proj_nr = get_Proj_proj(n);
491 if (proj_nr == pn_DivMod_res_div)
492 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
493 else if (proj_nr == pn_DivMod_res_mod)
494 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
498 if (get_Proj_proj(n) == pn_Div_res)
499 return computed_value(a);
503 if (get_Proj_proj(n) == pn_Mod_res)
504 return computed_value(a);
514 * If the parameter n can be computed, return its value, else tarval_bad.
515 * Performs constant folding.
517 * @param n The node this should be evaluated
519 tarval *computed_value(ir_node *n)
521 if (n->op->computed_value)
522 return n->op->computed_value(n);
527 * set the default computed_value evaluator
529 static ir_op *firm_set_default_computed_value(ir_op *op)
533 op->computed_value = computed_value_##a; \
558 op->computed_value = NULL;
566 /* returns 1 if the a and b are pointers to different locations. */
568 different_identity (ir_node *a, ir_node *b)
570 assert (mode_is_reference(get_irn_mode (a))
571 && mode_is_reference(get_irn_mode (b)));
573 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
574 ir_node *a1 = get_Proj_pred (a);
575 ir_node *b1 = get_Proj_pred (b);
576 if (a1 != b1 && get_irn_op (a1) == op_Alloc
577 && get_irn_op (b1) == op_Alloc)
584 static ir_node *equivalent_node_Block(ir_node *n)
588 /* The Block constructor does not call optimize, but mature_immBlock
589 calls the optimization. */
590 assert(get_Block_matured(n));
592 /* Straightening: a single entry Block following a single exit Block
593 can be merged, if it is not the Start block. */
594 /* !!! Beware, all Phi-nodes of n must have been optimized away.
595 This should be true, as the block is matured before optimize is called.
596 But what about Phi-cycles with the Phi0/Id that could not be resolved?
597 Remaining Phi nodes are just Ids. */
598 if ((get_Block_n_cfgpreds(n) == 1) &&
599 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
600 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
601 if (predblock == oldn) {
602 /* Jmp jumps into the block it is in -- deal self cycle. */
604 DBG_OPT_DEAD(oldn, n);
605 } else if (get_opt_control_flow_straightening()) {
607 DBG_OPT_STG(oldn, n);
610 else if ((get_Block_n_cfgpreds(n) == 1) &&
611 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
612 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
613 if (predblock == oldn) {
614 /* Jmp jumps into the block it is in -- deal self cycle. */
616 DBG_OPT_DEAD(oldn, n);
619 else if ((get_Block_n_cfgpreds(n) == 2) &&
620 (get_opt_control_flow_weak_simplification())) {
621 /* Test whether Cond jumps twice to this block
622 @@@ we could do this also with two loops finding two preds from several ones. */
623 ir_node *a = get_Block_cfgpred(n, 0);
624 ir_node *b = get_Block_cfgpred(n, 1);
626 if ((get_irn_op(a) == op_Proj) &&
627 (get_irn_op(b) == op_Proj) &&
628 (get_Proj_pred(a) == get_Proj_pred(b)) &&
629 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
630 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
631 /* Also a single entry Block following a single exit Block. Phis have
632 twice the same operand and will be optimized away. */
633 n = get_nodes_block(a);
634 DBG_OPT_IFSIM(oldn, a, b, n);
636 } else if (get_opt_unreachable_code() &&
637 (n != current_ir_graph->start_block) &&
638 (n != current_ir_graph->end_block) ) {
640 /* If all inputs are dead, this block is dead too, except if it is
641 the start or end block. This is a step of unreachable code
643 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
644 if (!is_Bad(get_Block_cfgpred(n, i))) break;
646 if (i == get_Block_n_cfgpreds(n))
654 * Returns a equivalent node for a Jmp, a Bad :-)
655 * Of course this only happens if the Block of the Jmp is Bad.
657 static ir_node *equivalent_node_Jmp(ir_node *n)
659 /* GL: Why not same for op_Raise?? */
660 /* unreachable code elimination */
661 if (is_Bad(get_nodes_block(n)))
667 static ir_node *equivalent_node_Cond(ir_node *n)
669 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
670 See cases for iro_Cond and iro_Proj in transform_node. */
675 * Use algebraic simplification a v a = a.
677 static ir_node *equivalent_node_Or(ir_node *n)
681 ir_node *a = get_Or_left(n);
682 ir_node *b = get_Or_right(n);
688 DBG_OPT_ALGSIM1(oldn, a, b, n);
695 * optimize operations that are commutative and have neutral 0,
696 * so a op 0 = 0 op a = a.
698 static ir_node *equivalent_node_neutral_zero(ir_node *n)
702 ir_node *a = get_binop_left(n);
703 ir_node *b = get_binop_right(n);
708 /* After running compute_node there is only one constant predecessor.
709 Find this predecessors value and remember the other node: */
710 if ((tv = computed_value(a)) != tarval_bad) {
712 } else if ((tv = computed_value(b)) != tarval_bad) {
717 /* If this predecessors constant value is zero, the operation is
718 unnecessary. Remove it: */
719 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
722 DBG_OPT_ALGSIM1(oldn, a, b, n);
728 #define equivalent_node_Add equivalent_node_neutral_zero
729 #define equivalent_node_Eor equivalent_node_neutral_zero
732 * optimize operations that are not commutative but have neutral 0 on left,
735 static ir_node *equivalent_node_left_zero(ir_node *n)
739 ir_node *a = get_binop_left(n);
740 ir_node *b = get_binop_right(n);
742 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_NULL) {
745 DBG_OPT_ALGSIM1(oldn, a, b, n);
751 #define equivalent_node_Sub equivalent_node_left_zero
752 #define equivalent_node_Shl equivalent_node_left_zero
753 #define equivalent_node_Shr equivalent_node_left_zero
754 #define equivalent_node_Shrs equivalent_node_left_zero
755 #define equivalent_node_Rot equivalent_node_left_zero
758 * Er, a "symmetic unop", ie op(op(n)) = n.
760 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
763 ir_node *pred = get_unop_op(n);
765 /* optimize symmetric unop */
766 if (get_irn_op(pred) == get_irn_op(n)) {
767 n = get_unop_op(pred);
768 DBG_OPT_ALGSIM2(oldn, pred, n);
774 #define equivalent_node_Not equivalent_node_symmetric_unop
776 /* --x == x */ /* ??? Is this possible or can --x raise an
777 out of bounds exception if min =! max? */
778 #define equivalent_node_Minus equivalent_node_symmetric_unop
781 * Optimize a * 1 = 1 * a = a.
783 static ir_node *equivalent_node_Mul(ir_node *n)
787 ir_node *a = get_Mul_left(n);
788 ir_node *b = get_Mul_right(n);
790 /* Mul is commutative and has again an other neutral element. */
791 if (classify_tarval (computed_value (a)) == TV_CLASSIFY_ONE) {
793 DBG_OPT_ALGSIM1(oldn, a, b, n);
794 } else if (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE) {
796 DBG_OPT_ALGSIM1(oldn, a, b, n);
802 * Optimize a / 1 = a.
804 static ir_node *equivalent_node_Div(ir_node *n)
806 ir_node *a = get_Div_left(n);
807 ir_node *b = get_Div_right(n);
809 /* Div is not commutative. */
810 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
811 /* Turn Div into a tuple (mem, bad, a) */
812 ir_node *mem = get_Div_mem(n);
813 turn_into_tuple(n, 3);
814 set_Tuple_pred(n, pn_Div_M, mem);
815 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
816 set_Tuple_pred(n, pn_Div_res, a);
822 * Optimize a / 1 = a.
824 static ir_node *equivalent_node_DivMod(ir_node *n)
826 ir_node *a = get_DivMod_left(n);
827 ir_node *b = get_DivMod_right(n);
829 /* Div is not commutative. */
830 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
831 /* Turn DivMod into a tuple (mem, bad, a, 0) */
832 ir_node *mem = get_Div_mem(n);
833 ir_mode *mode = get_irn_mode(b);
835 turn_into_tuple(n, 4);
836 set_Tuple_pred(n, pn_DivMod_M, mem);
837 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
838 set_Tuple_pred(n, pn_DivMod_res_div, a);
839 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
845 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
847 static ir_node *equivalent_node_And(ir_node *n)
851 ir_node *a = get_And_left(n);
852 ir_node *b = get_And_right(n);
855 n = a; /* And has it's own neutral element */
856 } else if (classify_tarval(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
858 DBG_OPT_ALGSIM1(oldn, a, b, n);
859 } else if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
861 DBG_OPT_ALGSIM1(oldn, a, b, n);
867 * Try to remove useless conv's:
869 static ir_node *equivalent_node_Conv(ir_node *n)
872 ir_node *a = get_Conv_op(n);
875 ir_mode *n_mode = get_irn_mode(n);
876 ir_mode *a_mode = get_irn_mode(a);
878 if (n_mode == a_mode) { /* No Conv necessary */
880 DBG_OPT_ALGSIM3(oldn, a, n);
881 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
885 n_mode = get_irn_mode(n);
886 b_mode = get_irn_mode(b);
888 if (n_mode == b_mode) {
889 if (n_mode == mode_b) {
890 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
891 DBG_OPT_ALGSIM1(oldn, a, b, n);
893 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
894 if (smaller_mode(b_mode, a_mode)){
895 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
896 DBG_OPT_ALGSIM1(oldn, a, b, n);
904 static ir_node *equivalent_node_Phi(ir_node *n)
906 /* Several optimizations:
907 - no Phi in start block.
908 - remove Id operators that are inputs to Phi
909 - fold Phi-nodes, iff they have only one predecessor except
915 ir_node *block = NULL; /* to shutup gcc */
916 ir_node *first_val = NULL; /* to shutup gcc */
917 ir_node *scnd_val = NULL; /* to shutup gcc */
919 if (!get_opt_normalize()) return n;
921 n_preds = get_Phi_n_preds(n);
923 block = get_nodes_block(n);
924 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
925 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
926 if ((is_Bad(block)) || /* Control dead */
927 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
928 return new_Bad(); /* in the Start Block. */
930 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
933 /* first we test for a special case: */
934 /* Confirm is a special node fixing additional information for a
935 value that is known at a certain point. This is useful for
936 dataflow analysis. */
938 ir_node *a = get_Phi_pred(n, 0);
939 ir_node *b = get_Phi_pred(n, 1);
940 if ( (get_irn_op(a) == op_Confirm)
941 && (get_irn_op(b) == op_Confirm)
942 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
943 && (get_irn_n(a, 1) == get_irn_n (b, 1))
944 && (a->data.num == (~b->data.num & irpn_True) )) {
945 return get_irn_n(a, 0);
950 /* If the Block has a Bad pred, we also have one. */
951 for (i = 0; i < n_preds; ++i)
952 if (is_Bad (get_Block_cfgpred(block, i)))
953 set_Phi_pred(n, i, new_Bad());
955 /* Find first non-self-referencing input */
956 for (i = 0; i < n_preds; ++i) {
957 first_val = get_Phi_pred(n, i);
958 if ( (first_val != n) /* not self pointer */
960 && (get_irn_op(first_val) != op_Bad)
962 ) { /* value not dead */
963 break; /* then found first value. */
967 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
968 if (i >= n_preds) { return new_Bad(); }
972 /* follow_Id () for rest of inputs, determine if any of these
973 are non-self-referencing */
974 while (++i < n_preds) {
975 scnd_val = get_Phi_pred(n, i);
977 && (scnd_val != first_val)
979 && (get_irn_op(scnd_val) != op_Bad)
986 /* Fold, if no multiple distinct non-self-referencing inputs */
989 DBG_OPT_PHI(oldn, first_val, n);
991 /* skip the remaining Ids (done in get_Phi_pred). */
992 /* superfluous, since we walk all to propagate Block's Bads.
993 while (++i < n_preds) get_Phi_pred(n, i); */
999 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1001 static ir_node *equivalent_node_Proj(ir_node *n)
1005 ir_node *a = get_Proj_pred(n);
1007 if ( get_irn_op(a) == op_Tuple) {
1008 /* Remove the Tuple/Proj combination. */
1009 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1010 n = get_Tuple_pred(a, get_Proj_proj(n));
1011 DBG_OPT_TUPLE(oldn, a, n);
1013 assert(0); /* This should not happen! */
1016 } else if (get_irn_mode(n) == mode_X &&
1017 is_Bad(get_nodes_block(n))) {
1018 /* Remove dead control flow -- early gigo. */
1027 static ir_node *equivalent_node_Id(ir_node *n)
1032 DBG_OPT_ID(oldn, n);
1037 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1038 * perform no actual computation, as, e.g., the Id nodes. It does not create
1039 * new nodes. It is therefore safe to free n if the node returned is not n.
1040 * If a node returns a Tuple we can not just skip it. If the size of the
1041 * in array fits, we transform n into a tuple (e.g., Div).
1044 equivalent_node(ir_node *n)
1046 if (n->op->equivalent_node)
1047 return n->op->equivalent_node(n);
1052 * set the default equivalent node operation
1054 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1058 op->equivalent_node = equivalent_node_##a; \
1084 op->equivalent_node = NULL;
1092 * Do node specific optimizations of nodes predecessors.
1095 optimize_preds(ir_node *n) {
1096 ir_node *a = NULL, *b = NULL;
1098 /* get the operands we will work on for simple cases. */
1100 a = get_binop_left(n);
1101 b = get_binop_right(n);
1102 } else if (is_unop(n)) {
1106 switch (get_irn_opcode(n)) {
1109 /* We don't want Cast as input to Cmp. */
1110 if (get_irn_op(a) == op_Cast) {
1114 if (get_irn_op(b) == op_Cast) {
1116 set_Cmp_right(n, b);
1124 static ir_node *transform_node_Mul(ir_node *n)
1126 return arch_dep_replace_mul_with_shifts(n);
1129 static ir_node *transform_node_Div(ir_node *n)
1131 tarval *tv = computed_value(n);
1134 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1136 if (tv != tarval_bad)
1137 value = new_Const(get_tarval_mode(tv), tv);
1138 else /* Try architecture dependand optimization */
1139 value = arch_dep_replace_div_with_shifts(n);
1142 /* Turn Div into a tuple (mem, bad, value) */
1143 ir_node *mem = get_Div_mem(n);
1145 turn_into_tuple(n, 3);
1146 set_Tuple_pred(n, pn_Div_M, mem);
1147 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1148 set_Tuple_pred(n, pn_Div_res, value);
1153 static ir_node *transform_node_Mod(ir_node *n)
1155 tarval *tv = computed_value(n);
1158 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1160 if (tv != tarval_bad)
1161 value = new_Const(get_tarval_mode(tv), tv);
1162 else /* Try architecture dependand optimization */
1163 value = arch_dep_replace_mod_with_shifts(n);
1166 /* Turn Mod into a tuple (mem, bad, value) */
1167 ir_node *mem = get_Mod_mem(n);
1169 turn_into_tuple(n, 3);
1170 set_Tuple_pred(n, pn_Mod_M, mem);
1171 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1172 set_Tuple_pred(n, pn_Mod_res, value);
1177 static ir_node *transform_node_DivMod(ir_node *n)
1181 ir_node *a = get_DivMod_left(n);
1182 ir_node *b = get_DivMod_right(n);
1183 ir_mode *mode = get_irn_mode(a);
1184 tarval *ta = value_of(a);
1185 tarval *tb = value_of(b);
1187 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1190 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1192 if (tb != tarval_bad) {
1193 if (tb == get_mode_one(get_tarval_mode(tb))) {
1194 b = new_Const (mode, get_mode_null(mode));
1196 } else if (ta != tarval_bad) {
1197 tarval *resa, *resb;
1198 resa = tarval_div (ta, tb);
1199 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1200 Jmp for X result!? */
1201 resb = tarval_mod (ta, tb);
1202 if (resb == tarval_bad) return n; /* Causes exception! */
1203 a = new_Const (mode, resa);
1204 b = new_Const (mode, resb);
1207 else { /* Try architecture dependand optimization */
1208 arch_dep_replace_divmod_with_shifts(&a, &b, n);
1209 evaluated = a != NULL;
1211 } else if (ta == get_mode_null(mode)) {
1212 /* 0 / non-Const = 0 */
1217 if (evaluated) { /* replace by tuple */
1218 ir_node *mem = get_DivMod_mem(n);
1219 turn_into_tuple(n, 4);
1220 set_Tuple_pred(n, pn_DivMod_M, mem);
1221 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1222 set_Tuple_pred(n, pn_DivMod_res_div, a);
1223 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1224 assert(get_nodes_block(n));
1230 static ir_node *transform_node_Cond(ir_node *n)
1232 /* Replace the Cond by a Jmp if it branches on a constant
1235 ir_node *a = get_Cond_selector(n);
1236 tarval *ta = value_of(a);
1238 if ((ta != tarval_bad) &&
1239 (get_irn_mode(a) == mode_b) &&
1240 (get_opt_unreachable_code())) {
1241 /* It's a boolean Cond, branching on a boolean constant.
1242 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1243 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1244 turn_into_tuple(n, 2);
1245 if (ta == tarval_b_true) {
1246 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1247 set_Tuple_pred(n, pn_Cond_true, jmp);
1249 set_Tuple_pred(n, pn_Cond_false, jmp);
1250 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1252 /* We might generate an endless loop, so keep it alive. */
1253 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1254 } else if ((ta != tarval_bad) &&
1255 (get_irn_mode(a) == mode_Iu) &&
1256 (get_Cond_kind(n) == dense) &&
1257 (get_opt_unreachable_code())) {
1258 /* I don't want to allow Tuples smaller than the biggest Proj.
1259 Also this tuple might get really big...
1260 I generate the Jmp here, and remember it in link. Link is used
1261 when optimizing Proj. */
1262 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1263 /* We might generate an endless loop, so keep it alive. */
1264 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1265 } else if ((get_irn_op(a) == op_Eor)
1266 && (get_irn_mode(a) == mode_b)
1267 && (classify_tarval(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1268 /* The Eor is a negate. Generate a new Cond without the negate,
1269 simulate the negate by exchanging the results. */
1270 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1272 } else if ((get_irn_op(a) == op_Not)
1273 && (get_irn_mode(a) == mode_b)) {
1274 /* A Not before the Cond. Generate a new Cond without the Not,
1275 simulate the Not by exchanging the results. */
1276 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1282 static ir_node *transform_node_Eor(ir_node *n)
1284 ir_node *a = get_Eor_left(n);
1285 ir_node *b = get_Eor_right(n);
1287 if ((get_irn_mode(n) == mode_b)
1288 && (get_irn_op(a) == op_Proj)
1289 && (get_irn_mode(a) == mode_b)
1290 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE)
1291 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1292 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1293 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1294 mode_b, get_negated_pnc(get_Proj_proj(a)));
1295 else if ((get_irn_mode(n) == mode_b)
1296 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE))
1297 /* The Eor is a Not. Replace it by a Not. */
1298 /* ????!!!Extend to bitfield 1111111. */
1299 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1305 * Transform a boolean Not.
1307 static ir_node *transform_node_Not(ir_node *n)
1309 ir_node *a = get_Not_op(n);
1311 if ( (get_irn_mode(n) == mode_b)
1312 && (get_irn_op(a) == op_Proj)
1313 && (get_irn_mode(a) == mode_b)
1314 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1315 /* We negate a Cmp. The Cmp has the negated result anyways! */
1316 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1317 mode_b, get_negated_pnc(get_Proj_proj(a)));
1323 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1324 * done here instead of equivalent node because in creates new
1326 * Removes the exceptions and routes the memory to the initial mem.
1328 * Further, it optimizes jump tables by removing all impossible cases.
1330 static ir_node *transform_node_Proj(ir_node *proj)
1332 ir_node *n = get_Proj_pred(proj);
1337 switch (get_irn_opcode(n)) {
1339 b = get_Div_right(n);
1340 tb = computed_value(b);
1342 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1343 proj_nr = get_Proj_proj(proj);
1345 if (proj_nr == pn_Div_X_except) {
1346 /* we found an exception handler, remove it */
1350 /* the memory Proj can be removed */
1351 ir_node *res = get_Div_mem(n);
1352 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1353 if (proj_nr == pn_Div_M)
1359 b = get_Mod_right(n);
1360 tb = computed_value(b);
1362 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1363 proj_nr = get_Proj_proj(proj);
1365 if (proj_nr == pn_Mod_X_except) {
1366 /* we found an exception handler, remove it */
1370 /* the memory Proj can be removed */
1371 ir_node *res = get_Mod_mem(n);
1372 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1373 if (proj_nr == pn_Mod_M)
1379 b = get_DivMod_right(n);
1380 tb = computed_value(b);
1382 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1383 proj_nr = get_Proj_proj(proj);
1385 if (proj_nr == pn_DivMod_X_except) {
1386 /* we found an exception handler, remove it */
1390 /* the memory Proj can be removed */
1391 ir_node *res = get_DivMod_mem(n);
1392 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1393 if (proj_nr == pn_DivMod_M)
1400 if (get_opt_unreachable_code()) {
1401 b = get_Cond_selector(n);
1402 tb = computed_value(b);
1404 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1405 /* we have a constant switch */
1406 long num = get_Proj_proj(proj);
1408 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1409 if (get_tarval_long(tb) == num) {
1410 /* Do NOT create a jump here, or we will have 2 control flow ops
1411 * in a block. This case is optimized away in optimize_cf(). */
1422 /* should not happen, but if it does will be optimized away */
1430 /* we have added a Tuple, optimize it for the current Proj away */
1431 return equivalent_node_Proj(proj);
1435 * returns the operands of a commutative bin-op, if one operand is
1436 * a const, it is returned as the second one.
1438 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1440 ir_node *op_a = get_binop_left(binop);
1441 ir_node *op_b = get_binop_right(binop);
1443 assert(is_op_commutative(get_irn_op(binop)));
1445 if (get_irn_op(op_a) == op_Const) {
1456 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1457 * Such pattern may arise in bitfield stores.
1459 * value c4 value c4 & c2
1460 * AND c3 AND c1 | c3
1465 static ir_node *transform_node_Or(ir_node *or)
1469 ir_node *and_l, *c3;
1470 ir_node *value, *c4;
1471 ir_node *new_and, *new_const, *block;
1472 ir_mode *mode = get_irn_mode(or);
1474 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1476 get_comm_Binop_Ops(or, &and, &c1);
1477 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1480 get_comm_Binop_Ops(and, &or_l, &c2);
1481 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1484 get_comm_Binop_Ops(or_l, &and_l, &c3);
1485 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1488 get_comm_Binop_Ops(and_l, &value, &c4);
1489 if (get_irn_op(c4) != op_Const)
1492 /* ok, found the pattern, check for conditions */
1493 assert(mode == get_irn_mode(and));
1494 assert(mode == get_irn_mode(or_l));
1495 assert(mode == get_irn_mode(and_l));
1497 tv1 = get_Const_tarval(c1);
1498 tv2 = get_Const_tarval(c2);
1499 tv3 = get_Const_tarval(c3);
1500 tv4 = get_Const_tarval(c4);
1502 tv = tarval_or(tv4, tv2);
1503 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1504 /* have at least one 0 at the same bit position */
1508 n_tv4 = tarval_not(tv4);
1509 if (tv3 != tarval_and(tv3, n_tv4)) {
1510 /* bit in the or_mask is outside the and_mask */
1514 n_tv2 = tarval_not(tv2);
1515 if (tv1 != tarval_and(tv1, n_tv2)) {
1516 /* bit in the or_mask is outside the and_mask */
1520 /* ok, all conditions met */
1521 block = get_nodes_block(or);
1523 new_and = new_r_And(current_ir_graph, block,
1524 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1526 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1528 set_Or_left(or, new_and);
1529 set_Or_right(or, new_const);
1531 /* check for more */
1532 return transform_node_Or(or);
1536 * Tries several [inplace] [optimizing] transformations and returns an
1537 * equivalent node. The difference to equivalent_node() is that these
1538 * transformations _do_ generate new nodes, and thus the old node must
1539 * not be freed even if the equivalent node isn't the old one.
1541 static ir_node *transform_node(ir_node *n)
1543 if (n->op->transform_node)
1544 n = n->op->transform_node(n);
1549 * set the default transform node operation
1551 static ir_op *firm_set_default_transform_node(ir_op *op)
1555 op->transform_node = transform_node_##a; \
1569 op->transform_node = NULL;
1577 /* **************** Common Subexpression Elimination **************** */
1579 /** The size of the hash table used, should estimate the number of nodes
1581 #define N_IR_NODES 512
1583 /** Compares the attributes of two Const nodes. */
1584 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1586 return (get_Const_tarval(a) != get_Const_tarval(b))
1587 || (get_Const_type(a) != get_Const_type(b));
1590 /** Compares the attributes of two Proj nodes. */
1591 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1593 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1596 /** Compares the attributes of two Filter nodes. */
1597 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1599 return get_Filter_proj(a) != get_Filter_proj(b);
1602 /** Compares the attributes of two Alloc nodes. */
1603 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1605 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1606 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1609 /** Compares the attributes of two Free nodes. */
1610 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1612 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1615 /** Compares the attributes of two SymConst nodes. */
1616 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1618 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1619 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1622 /** Compares the attributes of two Call nodes. */
1623 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1625 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1628 /** Compares the attributes of two FuncCall nodes. */
1629 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1631 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1634 /** Compares the attributes of two Sel nodes. */
1635 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1637 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1638 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1639 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1640 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1641 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1644 /** Compares the attributes of two Phi nodes. */
1645 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1647 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1650 /** Compares the attributes of two Cast nodes. */
1651 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1653 return get_Cast_type(a) != get_Cast_type(b);
1656 /** Compares the attributes of two Load nodes. */
1657 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1659 if (get_Load_volatility(a) == volatility_is_volatile ||
1660 get_Load_volatility(b) == volatility_is_volatile)
1661 /* NEVER do CSE on volatile Loads */
1664 return get_Load_mode(a) != get_Load_mode(b);
1667 /** Compares the attributes of two Store nodes. */
1668 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1670 /* NEVER do CSE on volatile Stores */
1671 return (get_Store_volatility(a) == volatility_is_volatile ||
1672 get_Load_volatility(b) == volatility_is_volatile);
1676 * set the default node attribute compare operation
1678 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1682 op->node_cmp_attr = node_cmp_attr_##a; \
1700 op->node_cmp_attr = NULL;
1708 * Compare function for two nodes in the hash table. Gets two
1709 * nodes as parameters. Returns 0 if the nodes are a cse.
1712 vt_cmp (const void *elt, const void *key)
1720 if (a == b) return 0;
1722 if ((get_irn_op(a) != get_irn_op(b)) ||
1723 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1725 /* compare if a's in and b's in are equal */
1726 irn_arity_a = get_irn_arity (a);
1727 if (irn_arity_a != get_irn_arity(b))
1730 /* for block-local cse and op_pin_state_pinned nodes: */
1731 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == op_pin_state_pinned)) {
1732 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1736 /* compare a->in[0..ins] with b->in[0..ins] */
1737 for (i = 0; i < irn_arity_a; i++)
1738 if (get_irn_n(a, i) != get_irn_n(b, i))
1742 * here, we already now that the nodes are identical except their
1745 if (a->op->node_cmp_attr)
1746 return a->op->node_cmp_attr(a, b);
1752 * Calculate a hash value of a node.
1755 ir_node_hash (ir_node *node)
1760 if (node->op == op_Const) {
1761 /* special value for const, as they only differ in their tarval. */
1762 h = ((unsigned) node->attr.con.tv)>>3 ;
1763 h = 9*h + (unsigned)get_irn_mode(node);
1764 } else if (node->op == op_SymConst) {
1765 /* special value for const, as they only differ in their symbol. */
1766 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1767 h = 9*h + (unsigned)get_irn_mode(node);
1770 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1771 h = irn_arity = get_irn_arity(node);
1773 /* consider all in nodes... except the block. */
1774 for (i = 0; i < irn_arity; i++) {
1775 h = 9*h + (unsigned)get_irn_n(node, i);
1779 h = 9*h + (unsigned) get_irn_mode (node);
1781 h = 9*h + (unsigned) get_irn_op (node);
1788 new_identities (void)
1790 return new_pset (vt_cmp, N_IR_NODES);
1794 del_identities (pset *value_table)
1796 del_pset (value_table);
1800 * Return the canonical node computing the same value as n.
1801 * Looks up the node in a hash table.
1803 * For Const nodes this is performed in the constructor, too. Const
1804 * nodes are extremely time critical because of their frequent use in
1805 * constant string arrays.
1807 static INLINE ir_node *
1808 identify (pset *value_table, ir_node *n)
1812 if (!value_table) return n;
1814 if (get_opt_reassociation()) {
1815 if (is_op_commutative(get_irn_op(n))) {
1816 ir_node *l = get_binop_left(n);
1817 ir_node *r = get_binop_right(n);
1819 /* for commutative operators perform a OP b == b OP a */
1821 set_binop_left(n, r);
1822 set_binop_right(n, l);
1827 o = pset_find (value_table, n, ir_node_hash (n));
1836 * During construction we set the op_pin_state_pinned flag in the graph right when the
1837 * optimization is performed. The flag turning on procedure global cse could
1838 * be changed between two allocations. This way we are safe.
1840 static INLINE ir_node *
1841 identify_cons (pset *value_table, ir_node *n) {
1844 n = identify(value_table, n);
1845 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1846 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1851 * Return the canonical node computing the same value as n.
1852 * Looks up the node in a hash table, enters it in the table
1853 * if it isn't there yet.
1856 identify_remember (pset *value_table, ir_node *n)
1860 if (!value_table) return n;
1862 if (get_opt_reassociation()) {
1863 if (is_op_commutative(get_irn_op(n))) {
1864 ir_node *l = get_binop_left(n);
1865 ir_node *r = get_binop_right(n);
1867 /* for commutative operators perform a OP b == b OP a */
1869 set_binop_left(n, r);
1870 set_binop_right(n, l);
1875 /* lookup or insert in hash table with given hash key. */
1876 o = pset_insert (value_table, n, ir_node_hash (n));
1886 add_identities (pset *value_table, ir_node *node) {
1887 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1888 identify_remember (value_table, node);
1892 * garbage in, garbage out. If a node has a dead input, i.e., the
1893 * Bad node is input to the node, return the Bad node.
1895 static INLINE ir_node *
1896 gigo (ir_node *node)
1899 ir_op* op = get_irn_op(node);
1901 /* remove garbage blocks by looking at control flow that leaves the block
1902 and replacing the control flow by Bad. */
1903 if (get_irn_mode(node) == mode_X) {
1904 ir_node *block = get_nodes_block(node);
1905 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1906 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1907 irn_arity = get_irn_arity(block);
1908 for (i = 0; i < irn_arity; i++) {
1909 if (!is_Bad(get_irn_n(block, i))) break;
1911 if (i == irn_arity) return new_Bad();
1915 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1916 blocks predecessors is dead. */
1917 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1918 irn_arity = get_irn_arity(node);
1919 for (i = -1; i < irn_arity; i++) {
1920 if (is_Bad(get_irn_n(node, i))) {
1926 /* With this code we violate the agreement that local_optimize
1927 only leaves Bads in Block, Phi and Tuple nodes. */
1928 /* If Block has only Bads as predecessors it's garbage. */
1929 /* If Phi has only Bads as predecessors it's garbage. */
1930 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1931 irn_arity = get_irn_arity(node);
1932 for (i = 0; i < irn_arity; i++) {
1933 if (!is_Bad(get_irn_n(node, i))) break;
1935 if (i == irn_arity) node = new_Bad();
1943 * These optimizations deallocate nodes from the obstack.
1944 * It can only be called if it is guaranteed that no other nodes
1945 * reference this one, i.e., right after construction of a node.
1948 optimize_node (ir_node *n)
1952 opcode iro = get_irn_opcode(n);
1954 /* Always optimize Phi nodes: part of the construction. */
1955 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1957 /* constant expression evaluation / constant folding */
1958 if (get_opt_constant_folding()) {
1959 /* constants can not be evaluated */
1960 if (iro != iro_Const) {
1961 /* try to evaluate */
1962 tv = computed_value (n);
1963 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1965 * we MUST copy the node here temporary, because it's still needed
1966 * for DBG_OPT_ALGSIM0
1968 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1969 oldn = alloca(node_size);
1971 memcpy(oldn, n, node_size);
1972 CLONE_ARR_A(ir_node *, oldn->in, n->in);
1974 /* ARG, copy the in array, we need it for statistics */
1975 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
1977 /* evaluation was successful -- replace the node. */
1978 obstack_free (current_ir_graph->obst, n);
1979 n = new_Const (get_tarval_mode (tv), tv);
1981 DBG_OPT_ALGSIM0(oldn, n);
1987 /* remove unnecessary nodes */
1988 if (get_opt_constant_folding() ||
1989 (iro == iro_Phi) || /* always optimize these nodes. */
1991 (iro == iro_Proj) ||
1992 (iro == iro_Block) ) /* Flags tested local. */
1993 n = equivalent_node (n);
1995 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1997 /** common subexpression elimination **/
1998 /* Checks whether n is already available. */
1999 /* The block input is used to distinguish different subexpressions. Right
2000 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2001 subexpressions within a block. */
2003 n = identify_cons (current_ir_graph->value_table, n);
2006 /* We found an existing, better node, so we can deallocate the old node. */
2007 obstack_free (current_ir_graph->obst, oldn);
2012 /* Some more constant expression evaluation that does not allow to
2014 iro = get_irn_opcode(n);
2015 if (get_opt_constant_folding() ||
2016 (iro == iro_Cond) ||
2017 (iro == iro_Proj)) /* Flags tested local. */
2018 n = transform_node (n);
2020 /* Remove nodes with dead (Bad) input.
2021 Run always for transformation induced Bads. */
2024 /* Now we have a legal, useful node. Enter it in hash table for cse */
2025 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2026 n = identify_remember (current_ir_graph->value_table, n);
2034 * These optimizations never deallocate nodes. This can cause dead
2035 * nodes lying on the obstack. Remove these by a dead node elimination,
2036 * i.e., a copying garbage collection.
2039 optimize_in_place_2 (ir_node *n)
2043 opcode iro = get_irn_opcode(n);
2045 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2047 /* if not optimize return n */
2050 /* Here this is possible. Why? */
2055 /* constant expression evaluation / constant folding */
2056 if (get_opt_constant_folding()) {
2057 /* constants can not be evaluated */
2058 if (iro != iro_Const) {
2059 /* try to evaluate */
2060 tv = computed_value (n);
2061 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2062 /* evaluation was successful -- replace the node. */
2063 n = new_Const (get_tarval_mode (tv), tv);
2065 DBG_OPT_ALGSIM0(oldn, n);
2071 /* remove unnecessary nodes */
2072 if (get_opt_constant_folding() ||
2073 (iro == iro_Phi) || /* always optimize these nodes. */
2074 (iro == iro_Id) || /* ... */
2075 (iro == iro_Proj) || /* ... */
2076 (iro == iro_Block) ) /* Flags tested local. */
2077 n = equivalent_node (n);
2079 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2081 /** common subexpression elimination **/
2082 /* Checks whether n is already available. */
2083 /* The block input is used to distinguish different subexpressions. Right
2084 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2085 subexpressions within a block. */
2086 if (get_opt_cse()) {
2087 n = identify (current_ir_graph->value_table, n);
2090 /* Some more constant expression evaluation. */
2091 iro = get_irn_opcode(n);
2092 if (get_opt_constant_folding() ||
2093 (iro == iro_Cond) ||
2094 (iro == iro_Proj)) /* Flags tested local. */
2095 n = transform_node (n);
2097 /* Remove nodes with dead (Bad) input.
2098 Run always for transformation induced Bads. */
2101 /* Now we can verify the node, as it has no dead inputs any more. */
2104 /* Now we have a legal, useful node. Enter it in hash table for cse.
2105 Blocks should be unique anyways. (Except the successor of start:
2106 is cse with the start block!) */
2107 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2108 n = identify_remember (current_ir_graph->value_table, n);
2114 * Wrapper for external use, set proper status bits after optimization.
2117 optimize_in_place (ir_node *n)
2119 /* Handle graph state */
2120 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2122 if (get_opt_global_cse())
2123 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2124 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2125 set_irg_outs_inconsistent(current_ir_graph);
2127 /* Maybe we could also test whether optimizing the node can
2128 change the control graph. */
2129 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2130 set_irg_dom_inconsistent(current_ir_graph);
2131 return optimize_in_place_2 (n);
2135 * set the default ir op operations
2137 ir_op *firm_set_default_operations(ir_op *op)
2139 op = firm_set_default_computed_value(op);
2140 op = firm_set_default_equivalent_node(op);
2141 op = firm_set_default_transform_node(op);
2142 op = firm_set_default_node_cmp_attr(op);