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.
27 # include "irnode_t.h"
28 # include "irgraph_t.h"
29 # include "iredges_t.h"
30 # include "irmode_t.h"
32 # include "ircons_t.h"
36 # include "dbginfo_t.h"
37 # include "iropt_dbg.h"
38 # include "irflag_t.h"
43 /* Make types visible to allow most efficient access */
44 # include "entity_t.h"
47 * Trivial INLINEable routine for copy propagation.
48 * Does follow Ids, needed to optimize INLINEd code.
50 static INLINE ir_node *
51 follow_Id (ir_node *n)
53 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
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) && (get_irn_mode(a) == get_irn_mode(b)))
88 return tarval_add(ta, tb);
94 * return the value of a Sub
97 static tarval *computed_value_Sub(ir_node *n)
99 ir_node *a = get_Sub_left(n);
100 ir_node *b = get_Sub_right(n);
105 if (a == b && !is_Bad(a))
106 return get_tarval_null(get_irn_mode(n));
111 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
112 return tarval_sub(ta, tb);
118 * return the value of an unary Minus
120 static tarval *computed_value_Minus(ir_node *n)
122 ir_node *a = get_Minus_op(n);
123 tarval *ta = value_of(a);
125 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
126 return tarval_neg(ta);
132 * return the value of a Mul
134 static tarval *computed_value_Mul(ir_node *n)
136 ir_node *a = get_Mul_left(n);
137 ir_node *b = get_Mul_right(n);
139 tarval *ta = value_of(a);
140 tarval *tb = value_of(b);
142 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
143 return tarval_mul(ta, tb);
145 /* a*0 = 0 or 0*b = 0:
146 calls computed_value recursive and returns the 0 with proper
148 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
150 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
157 * return the value of a floating point Quot
159 static tarval *computed_value_Quot(ir_node *n)
161 ir_node *a = get_Quot_left(n);
162 ir_node *b = get_Quot_right(n);
164 tarval *ta = value_of(a);
165 tarval *tb = value_of(b);
167 /* This was missing in original implementation. Why? */
168 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
169 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
170 return tarval_quo(ta, tb);
176 * calculate the value of an integer Div of two nodes
177 * Special case: 0 / b
179 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
181 tarval *ta = value_of(a);
182 tarval *tb = value_of(b);
184 /* Compute c1 / c2 or 0 / a, a != 0 */
185 if (ta != tarval_bad) {
186 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
187 return tarval_div(ta, tb);
188 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
195 * return the value of an integer Div
197 static tarval *computed_value_Div(ir_node *n)
199 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
203 * calculate the value of an integer Mod of two nodes
204 * Special case: a % 1
206 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
208 tarval *ta = value_of(a);
209 tarval *tb = value_of(b);
211 /* Compute c1 % c2 or a % 1 */
212 if (tb != tarval_bad) {
213 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
214 return tarval_mod(ta, tb);
215 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
216 return get_mode_null(get_irn_mode(a));
223 * return the value of an integer Mod
225 static tarval *computed_value_Mod(ir_node *n)
227 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
231 * return the value of an Abs
233 static tarval *computed_value_Abs(ir_node *n)
235 ir_node *a = get_Abs_op(n);
236 tarval *ta = value_of(a);
238 if (ta != tarval_bad)
239 return tarval_abs(ta);
245 * return the value of an And
246 * Special case: a & 0, 0 & b
248 static tarval *computed_value_And(ir_node *n)
250 ir_node *a = get_And_left(n);
251 ir_node *b = get_And_right(n);
253 tarval *ta = value_of(a);
254 tarval *tb = value_of(b);
256 if ((ta != tarval_bad) && (tb != tarval_bad)) {
257 return tarval_and (ta, tb);
261 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
262 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
270 * return the value of an Or
271 * Special case: a | 1...1, 1...1 | b
273 static tarval *computed_value_Or(ir_node *n)
275 ir_node *a = get_Or_left(n);
276 ir_node *b = get_Or_right(n);
278 tarval *ta = value_of(a);
279 tarval *tb = value_of(b);
281 if ((ta != tarval_bad) && (tb != tarval_bad)) {
282 return tarval_or (ta, tb);
285 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
286 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
294 * return the value of an Eor
296 static tarval *computed_value_Eor(ir_node *n)
298 ir_node *a = get_Eor_left(n);
299 ir_node *b = get_Eor_right(n);
304 return get_tarval_null(get_irn_mode(n));
309 if ((ta != tarval_bad) && (tb != tarval_bad)) {
310 return tarval_eor (ta, tb);
316 * return the value of a Not
318 static tarval *computed_value_Not(ir_node *n)
320 ir_node *a = get_Not_op(n);
321 tarval *ta = value_of(a);
323 if (ta != tarval_bad)
324 return tarval_not(ta);
330 * return the value of a Shl
332 static tarval *computed_value_Shl(ir_node *n)
334 ir_node *a = get_Shl_left(n);
335 ir_node *b = get_Shl_right(n);
337 tarval *ta = value_of(a);
338 tarval *tb = value_of(b);
340 if ((ta != tarval_bad) && (tb != tarval_bad)) {
341 return tarval_shl (ta, tb);
347 * return the value of a Shr
349 static tarval *computed_value_Shr(ir_node *n)
351 ir_node *a = get_Shr_left(n);
352 ir_node *b = get_Shr_right(n);
354 tarval *ta = value_of(a);
355 tarval *tb = value_of(b);
357 if ((ta != tarval_bad) && (tb != tarval_bad)) {
358 return tarval_shr (ta, tb);
364 * return the value of a Shrs
366 static tarval *computed_value_Shrs(ir_node *n)
368 ir_node *a = get_Shrs_left(n);
369 ir_node *b = get_Shrs_right(n);
371 tarval *ta = value_of(a);
372 tarval *tb = value_of(b);
374 if ((ta != tarval_bad) && (tb != tarval_bad)) {
375 return tarval_shrs (ta, tb);
381 * return the value of a Rot
383 static tarval *computed_value_Rot(ir_node *n)
385 ir_node *a = get_Rot_left(n);
386 ir_node *b = get_Rot_right(n);
388 tarval *ta = value_of(a);
389 tarval *tb = value_of(b);
391 if ((ta != tarval_bad) && (tb != tarval_bad)) {
392 return tarval_rot (ta, tb);
398 * return the value of a Conv
400 static tarval *computed_value_Conv(ir_node *n)
402 ir_node *a = get_Conv_op(n);
403 tarval *ta = value_of(a);
405 if (ta != tarval_bad)
406 return tarval_convert_to(ta, get_irn_mode(n));
412 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
414 static tarval *computed_value_Proj(ir_node *n)
416 ir_node *a = get_Proj_pred(n);
420 /* Optimize Cmp nodes.
421 This performs a first step of unreachable code elimination.
422 Proj can not be computed, but folding a Cmp above the Proj here is
423 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
425 There are several case where we can evaluate a Cmp node:
426 1. The nodes compared are both the same. If we compare for
427 equal, greater equal, ... this will return true, else it
428 will return false. This step relies on cse.
429 2. The predecessors of Cmp are target values. We can evaluate
431 3. The predecessors are Allocs or void* constants. Allocs never
432 return NULL, they raise an exception. Therefore we can predict
434 switch (get_irn_opcode(a)) {
436 aa = get_Cmp_left(a);
437 ab = get_Cmp_right(a);
438 proj_nr = get_Proj_proj(n);
440 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
441 /* BEWARE: a == a is NOT always True for floating Point!!! */
442 /* This is a trick with the bits used for encoding the Cmp
443 Proj numbers, the following statement is not the same:
444 return new_tarval_from_long (proj_nr == pn_Cmp_Eq, mode_b) */
445 return new_tarval_from_long (proj_nr & pn_Cmp_Eq, mode_b);
447 tarval *taa = value_of(aa);
448 tarval *tab = value_of(ab);
450 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
451 /* strange checks... */
452 pn_Cmp flags = tarval_cmp (taa, tab);
453 if (flags != pn_Cmp_False) {
454 return new_tarval_from_long (proj_nr & flags, mode_b);
456 } else { /* check for 3.: */
457 ir_node *aaa = skip_Id(skip_Proj(aa));
458 ir_node *aba = skip_Id(skip_Proj(ab));
460 if ( ( (/* aa is ProjP and aaa is Alloc */
461 (get_irn_op(aa) == op_Proj)
462 && (mode_is_reference(get_irn_mode(aa)))
463 && (get_irn_op(aaa) == op_Alloc))
464 && ( (/* ab is constant void */
465 (get_irn_op(ab) == op_Const)
466 && (mode_is_reference(get_irn_mode(ab)))
467 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
468 || (/* ab is other Alloc */
469 (get_irn_op(ab) == op_Proj)
470 && (mode_is_reference(get_irn_mode(ab)))
471 && (get_irn_op(aba) == op_Alloc)
473 || (/* aa is void and aba is Alloc */
474 (get_irn_op(aa) == op_Const)
475 && (mode_is_reference(get_irn_mode(aa)))
476 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
477 && (get_irn_op(ab) == op_Proj)
478 && (mode_is_reference(get_irn_mode(ab)))
479 && (get_irn_op(aba) == op_Alloc)))
481 return new_tarval_from_long (proj_nr & pn_Cmp_Ne, mode_b);
487 /* compute either the Div or the Mod part */
488 proj_nr = get_Proj_proj(n);
489 if (proj_nr == pn_DivMod_res_div)
490 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
491 else if (proj_nr == pn_DivMod_res_mod)
492 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
496 if (get_Proj_proj(n) == pn_Div_res)
497 return computed_value(a);
501 if (get_Proj_proj(n) == pn_Mod_res)
502 return computed_value(a);
512 * calculate the value of a Mux: can be evaluated, if the
513 * sel and the right input are known
515 static tarval *computed_value_Mux(ir_node *n)
517 ir_node *sel = get_Mux_sel(n);
518 tarval *ts = value_of(sel);
520 if (ts == get_tarval_b_true()) {
521 ir_node *v = get_Mux_true(n);
524 else if (ts == get_tarval_b_false()) {
525 ir_node *v = get_Mux_false(n);
532 * If the parameter n can be computed, return its value, else tarval_bad.
533 * Performs constant folding.
535 * @param n The node this should be evaluated
537 tarval *computed_value(ir_node *n)
539 if (n->op->computed_value)
540 return n->op->computed_value(n);
545 * set the default computed_value evaluator
547 static ir_op *firm_set_default_computed_value(ir_op *op)
551 op->computed_value = computed_value_##a; \
577 op->computed_value = NULL;
585 /* returns 1 if the a and b are pointers to different locations. */
587 different_identity (ir_node *a, ir_node *b)
589 assert (mode_is_reference(get_irn_mode (a))
590 && mode_is_reference(get_irn_mode (b)));
592 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
593 ir_node *a1 = get_Proj_pred (a);
594 ir_node *b1 = get_Proj_pred (b);
595 if (a1 != b1 && get_irn_op (a1) == op_Alloc
596 && get_irn_op (b1) == op_Alloc)
603 static ir_node *equivalent_node_Block(ir_node *n)
607 /* The Block constructor does not call optimize, but mature_immBlock
608 calls the optimization. */
609 assert(get_Block_matured(n));
611 /* Straightening: a single entry Block following a single exit Block
612 can be merged, if it is not the Start block. */
613 /* !!! Beware, all Phi-nodes of n must have been optimized away.
614 This should be true, as the block is matured before optimize is called.
615 But what about Phi-cycles with the Phi0/Id that could not be resolved?
616 Remaining Phi nodes are just Ids. */
617 if ((get_Block_n_cfgpreds(n) == 1) &&
618 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
619 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
620 if (predblock == oldn) {
621 /* Jmp jumps into the block it is in -- deal self cycle. */
622 n = set_Block_dead(n);
623 DBG_OPT_DEAD(oldn, n);
624 } else if (get_opt_control_flow_straightening()) {
626 DBG_OPT_STG(oldn, n);
629 else if ((get_Block_n_cfgpreds(n) == 1) &&
630 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
631 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
632 if (predblock == oldn) {
633 /* Jmp jumps into the block it is in -- deal self cycle. */
634 n = set_Block_dead(n);
635 DBG_OPT_DEAD(oldn, n);
638 else if ((get_Block_n_cfgpreds(n) == 2) &&
639 (get_opt_control_flow_weak_simplification())) {
640 /* Test whether Cond jumps twice to this block
641 @@@ we could do this also with two loops finding two preds from several ones. */
642 ir_node *a = get_Block_cfgpred(n, 0);
643 ir_node *b = get_Block_cfgpred(n, 1);
645 if ((get_irn_op(a) == op_Proj) &&
646 (get_irn_op(b) == op_Proj) &&
647 (get_Proj_pred(a) == get_Proj_pred(b)) &&
648 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
649 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
650 /* Also a single entry Block following a single exit Block. Phis have
651 twice the same operand and will be optimized away. */
652 n = get_nodes_block(a);
653 DBG_OPT_IFSIM(oldn, a, b, n);
655 } else if (get_opt_unreachable_code() &&
656 (n != current_ir_graph->start_block) &&
657 (n != current_ir_graph->end_block) ) {
658 int i, n_cfg = get_Block_n_cfgpreds(n);
660 /* If all inputs are dead, this block is dead too, except if it is
661 the start or end block. This is a step of unreachable code
663 for (i = 0; i < n_cfg; i++) {
664 ir_node *pred = get_Block_cfgpred(n, i);
667 if (is_Bad(pred)) continue;
668 pred_blk = get_nodes_block(pred);
670 if (is_Block_dead(pred_blk)) continue;
673 /* really found a living input */
678 n = set_Block_dead(n);
685 * Returns a equivalent node for a Jmp, a Bad :-)
686 * Of course this only happens if the Block of the Jmp is Bad.
688 static ir_node *equivalent_node_Jmp(ir_node *n)
690 /* GL: Why not same for op_Raise?? */
691 /* unreachable code elimination */
692 if (is_Block_dead(get_nodes_block(n)))
698 static ir_node *equivalent_node_Cond(ir_node *n)
700 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
701 See cases for iro_Cond and iro_Proj in transform_node. */
706 * optimize operations that are commutative and have neutral 0,
707 * so a op 0 = 0 op a = a.
709 static ir_node *equivalent_node_neutral_zero(ir_node *n)
713 ir_node *a = get_binop_left(n);
714 ir_node *b = get_binop_right(n);
719 /* After running compute_node there is only one constant predecessor.
720 Find this predecessors value and remember the other node: */
721 if ((tv = value_of(a)) != tarval_bad) {
723 } else if ((tv = value_of(b)) != tarval_bad) {
728 /* If this predecessors constant value is zero, the operation is
729 unnecessary. Remove it: */
730 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
733 DBG_OPT_ALGSIM1(oldn, a, b, n);
739 #define equivalent_node_Add equivalent_node_neutral_zero
740 #define equivalent_node_Eor equivalent_node_neutral_zero
743 * optimize operations that are not commutative but have neutral 0 on left,
746 static ir_node *equivalent_node_left_zero(ir_node *n)
750 ir_node *a = get_binop_left(n);
751 ir_node *b = get_binop_right(n);
753 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
756 DBG_OPT_ALGSIM1(oldn, a, b, n);
762 #define equivalent_node_Sub equivalent_node_left_zero
763 #define equivalent_node_Shl equivalent_node_left_zero
764 #define equivalent_node_Shr equivalent_node_left_zero
765 #define equivalent_node_Shrs equivalent_node_left_zero
766 #define equivalent_node_Rot equivalent_node_left_zero
769 * Er, a "symmetic unop", ie op(op(n)) = n.
771 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
774 ir_node *pred = get_unop_op(n);
776 /* optimize symmetric unop */
777 if (get_irn_op(pred) == get_irn_op(n)) {
778 n = get_unop_op(pred);
779 DBG_OPT_ALGSIM2(oldn, pred, n);
785 #define equivalent_node_Not equivalent_node_symmetric_unop
787 /* --x == x */ /* ??? Is this possible or can --x raise an
788 out of bounds exception if min =! max? */
789 #define equivalent_node_Minus equivalent_node_symmetric_unop
792 * Optimize a * 1 = 1 * a = a.
794 static ir_node *equivalent_node_Mul(ir_node *n)
798 ir_node *a = get_Mul_left(n);
799 ir_node *b = get_Mul_right(n);
801 /* Mul is commutative and has again an other neutral element. */
802 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
804 DBG_OPT_ALGSIM1(oldn, a, b, n);
805 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
807 DBG_OPT_ALGSIM1(oldn, a, b, n);
813 * Optimize a / 1 = a.
815 static ir_node *equivalent_node_Div(ir_node *n)
817 ir_node *a = get_Div_left(n);
818 ir_node *b = get_Div_right(n);
820 /* Div is not commutative. */
821 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
822 /* Turn Div into a tuple (mem, bad, a) */
823 ir_node *mem = get_Div_mem(n);
824 turn_into_tuple(n, 3);
825 set_Tuple_pred(n, pn_Div_M, mem);
826 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
827 set_Tuple_pred(n, pn_Div_res, a);
833 * Optimize a / 1 = a.
835 static ir_node *equivalent_node_DivMod(ir_node *n)
837 ir_node *a = get_DivMod_left(n);
838 ir_node *b = get_DivMod_right(n);
840 /* Div is not commutative. */
841 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
842 /* Turn DivMod into a tuple (mem, bad, a, 0) */
843 ir_node *mem = get_Div_mem(n);
844 ir_mode *mode = get_irn_mode(b);
846 turn_into_tuple(n, 4);
847 set_Tuple_pred(n, pn_DivMod_M, mem);
848 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
849 set_Tuple_pred(n, pn_DivMod_res_div, a);
850 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
856 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
858 static ir_node *equivalent_node_Or(ir_node *n)
862 ir_node *a = get_Or_left(n);
863 ir_node *b = get_Or_right(n);
866 n = a; /* Or has it's own neutral element */
867 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
869 DBG_OPT_ALGSIM1(oldn, a, b, n);
870 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
872 DBG_OPT_ALGSIM1(oldn, a, b, n);
879 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
881 static ir_node *equivalent_node_And(ir_node *n)
885 ir_node *a = get_And_left(n);
886 ir_node *b = get_And_right(n);
889 n = a; /* And has it's own neutral element */
890 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
892 DBG_OPT_ALGSIM1(oldn, a, b, n);
893 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
895 DBG_OPT_ALGSIM1(oldn, a, b, n);
901 * Try to remove useless conv's:
903 static ir_node *equivalent_node_Conv(ir_node *n)
906 ir_node *a = get_Conv_op(n);
909 ir_mode *n_mode = get_irn_mode(n);
910 ir_mode *a_mode = get_irn_mode(a);
912 if (n_mode == a_mode) { /* No Conv necessary */
914 DBG_OPT_ALGSIM3(oldn, a, n);
915 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
919 n_mode = get_irn_mode(n);
920 b_mode = get_irn_mode(b);
922 if (n_mode == b_mode) {
923 if (n_mode == mode_b) {
924 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
925 DBG_OPT_ALGSIM1(oldn, a, b, n);
927 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
928 if (smaller_mode(b_mode, a_mode)){
929 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
930 DBG_OPT_ALGSIM1(oldn, a, b, n);
939 * A Cast may be removed if the type of the previous node
940 * is already to type of the Cast.
942 static ir_node *equivalent_node_Cast(ir_node *n) {
943 ir_node *pred = get_Cast_op(n);
944 if (get_irn_type(pred) == get_Cast_type(n))
949 /* Several optimizations:
950 - no Phi in start block.
951 - remove Id operators that are inputs to Phi
952 - fold Phi-nodes, iff they have only one predecessor except
955 static ir_node *equivalent_node_Phi(ir_node *n)
960 ir_node *block = NULL; /* to shutup gcc */
961 ir_node *first_val = NULL; /* to shutup gcc */
962 ir_node *scnd_val = NULL; /* to shutup gcc */
964 if (!get_opt_normalize()) return n;
966 n_preds = get_Phi_n_preds(n);
968 block = get_nodes_block(n);
969 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
970 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
971 if ((is_Block_dead(block)) || /* Control dead */
972 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
973 return new_Bad(); /* in the Start Block. */
975 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
978 /* first we test for a special case: */
979 /* Confirm is a special node fixing additional information for a
980 value that is known at a certain point. This is useful for
981 dataflow analysis. */
983 ir_node *a = get_Phi_pred(n, 0);
984 ir_node *b = get_Phi_pred(n, 1);
985 if ( (get_irn_op(a) == op_Confirm)
986 && (get_irn_op(b) == op_Confirm)
987 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
988 && (get_irn_n(a, 1) == get_irn_n (b, 1))
989 && (a->data.num == (~b->data.num & irpn_True) )) {
990 return get_irn_n(a, 0);
995 /* If the Block has a Bad pred, we also have one. */
996 for (i = 0; i < n_preds; ++i)
997 if (is_Bad (get_Block_cfgpred(block, i)))
998 set_Phi_pred(n, i, new_Bad());
1000 /* Find first non-self-referencing input */
1001 for (i = 0; i < n_preds; ++i) {
1002 first_val = get_Phi_pred(n, i);
1003 if ( (first_val != n) /* not self pointer */
1005 && (get_irn_op(first_val) != op_Bad)
1007 ) { /* value not dead */
1008 break; /* then found first value. */
1012 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1013 if (i >= n_preds) { return new_Bad(); }
1017 /* follow_Id () for rest of inputs, determine if any of these
1018 are non-self-referencing */
1019 while (++i < n_preds) {
1020 scnd_val = get_Phi_pred(n, i);
1021 if ( (scnd_val != n)
1022 && (scnd_val != first_val)
1024 && (get_irn_op(scnd_val) != op_Bad)
1031 /* Fold, if no multiple distinct non-self-referencing inputs */
1034 DBG_OPT_PHI(oldn, first_val, n);
1036 /* skip the remaining Ids (done in get_Phi_pred). */
1037 /* superfluous, since we walk all to propagate Block's Bads.
1038 while (++i < n_preds) get_Phi_pred(n, i); */
1044 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1046 static ir_node *equivalent_node_Proj(ir_node *n)
1050 ir_node *a = get_Proj_pred(n);
1052 if ( get_irn_op(a) == op_Tuple) {
1053 /* Remove the Tuple/Proj combination. */
1054 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1055 n = get_Tuple_pred(a, get_Proj_proj(n));
1056 DBG_OPT_TUPLE(oldn, a, n);
1058 assert(0); /* This should not happen! */
1061 } else if (get_irn_mode(n) == mode_X &&
1062 is_Block_dead(get_nodes_block(n))) {
1063 /* Remove dead control flow -- early gigo. */
1072 static ir_node *equivalent_node_Id(ir_node *n)
1077 DBG_OPT_ID(oldn, n);
1084 static ir_node *equivalent_node_Mux(ir_node *n)
1086 ir_node *oldn = n, *sel = get_Mux_sel(n);
1087 tarval *ts = value_of(sel);
1089 if (ts == get_tarval_b_true()) {
1090 n = get_Mux_true(n);
1091 DBG_OPT_ALGSIM0(oldn, n);
1093 else if (ts == get_tarval_b_false()) {
1094 n = get_Mux_false(n);
1095 DBG_OPT_ALGSIM0(oldn, n);
1097 else if(get_Mux_false(n) == get_Mux_true(n)) {
1098 n = get_Mux_true(n);
1099 DBG_OPT_ALGSIM0(oldn, n);
1106 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1107 * perform no actual computation, as, e.g., the Id nodes. It does not create
1108 * new nodes. It is therefore safe to free n if the node returned is not n.
1109 * If a node returns a Tuple we can not just skip it. If the size of the
1110 * in array fits, we transform n into a tuple (e.g., Div).
1113 equivalent_node(ir_node *n)
1115 if (n->op->equivalent_node)
1116 return n->op->equivalent_node(n);
1121 * set the default equivalent node operation
1123 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1127 op->equivalent_node = equivalent_node_##a; \
1155 op->equivalent_node = NULL;
1163 * Do node specific optimizations of nodes predecessors.
1166 optimize_preds(ir_node *n) {
1167 ir_node *a = NULL, *b = NULL;
1169 /* get the operands we will work on for simple cases. */
1171 a = get_binop_left(n);
1172 b = get_binop_right(n);
1173 } else if (is_unop(n)) {
1177 switch (get_irn_opcode(n)) {
1180 /* We don't want Cast as input to Cmp. */
1181 if (get_irn_op(a) == op_Cast) {
1185 if (get_irn_op(b) == op_Cast) {
1187 set_Cmp_right(n, b);
1196 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1197 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)).
1198 * If possible, remove the Conv's.
1200 static ir_node *transform_node_AddSub(ir_node *n)
1202 ir_mode *mode = get_irn_mode(n);
1204 if (mode_is_reference(mode)) {
1205 ir_node *left = get_binop_left(n);
1206 ir_node *right = get_binop_right(n);
1207 int ref_bits = get_mode_size_bits(mode);
1209 if (get_irn_op(left) == op_Conv) {
1210 ir_mode *mode = get_irn_mode(left);
1211 int bits = get_mode_size_bits(mode);
1213 if (ref_bits == bits &&
1214 mode_is_int(mode) &&
1215 get_mode_arithmetic(mode) == irma_twos_complement) {
1216 ir_node *pre = get_Conv_op(left);
1217 ir_mode *pre_mode = get_irn_mode(pre);
1219 if (mode_is_int(pre_mode) &&
1220 get_mode_size_bits(pre_mode) == bits &&
1221 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1222 /* ok, this conv just changes to sign, moreover the calculation
1223 * is done with same number of bits as our address mode, so
1224 * we can ignore the conv as address calculation can be viewed
1225 * as either signed or unsigned
1227 set_binop_left(n, pre);
1232 if (get_irn_op(right) == op_Conv) {
1233 ir_mode *mode = get_irn_mode(right);
1234 int bits = get_mode_size_bits(mode);
1236 if (ref_bits == bits &&
1237 mode_is_int(mode) &&
1238 get_mode_arithmetic(mode) == irma_twos_complement) {
1239 ir_node *pre = get_Conv_op(right);
1240 ir_mode *pre_mode = get_irn_mode(pre);
1242 if (mode_is_int(pre_mode) &&
1243 get_mode_size_bits(pre_mode) == bits &&
1244 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1245 /* ok, this conv just changes to sign, moreover the calculation
1246 * is done with same number of bits as our address mode, so
1247 * we can ignore the conv as address calculation can be viewed
1248 * as either signed or unsigned
1250 set_binop_right(n, pre);
1259 * Do the AddSub optimization, then Transform Add(a,a) into Mul(a, 2)
1260 * if the mode is integer or float.
1261 * Reassociation might fold this further.
1263 static ir_node *transform_node_Add(ir_node *n)
1268 n = transform_node_AddSub(n);
1270 mode = get_irn_mode(n);
1271 if (mode_is_num(mode)) {
1272 ir_node *a = get_Add_left(n);
1274 if (a == get_Add_right(n)) {
1275 ir_node *block = get_nodes_block(n);
1278 get_irn_dbg_info(n),
1282 new_r_Const_long(current_ir_graph, block, mode, 2),
1284 DBG_OPT_ALGSIM0(oldn, n);
1291 * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
1293 static ir_node *transform_node_Sub(ir_node *n)
1298 n = transform_node_AddSub(n);
1300 mode = get_irn_mode(n);
1301 if (mode_is_num(mode)) {
1302 if (classify_Const(get_Sub_left(n)) == CNST_NULL) {
1304 get_irn_dbg_info(n),
1309 DBG_OPT_ALGSIM0(oldn, n);
1316 /** Do architecture dependend optimizations on Mul nodes */
1317 static ir_node *transform_node_Mul(ir_node *n) {
1318 return arch_dep_replace_mul_with_shifts(n);
1321 static ir_node *transform_node_Div(ir_node *n)
1323 tarval *tv = value_of(n);
1326 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1328 if (tv != tarval_bad) {
1329 value = new_Const(get_tarval_mode(tv), tv);
1331 DBG_OPT_CSTEVAL(n, value);
1333 else /* Try architecture dependand optimization */
1334 value = arch_dep_replace_div_by_const(n);
1337 /* Turn Div into a tuple (mem, bad, value) */
1338 ir_node *mem = get_Div_mem(n);
1340 turn_into_tuple(n, 3);
1341 set_Tuple_pred(n, pn_Div_M, mem);
1342 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1343 set_Tuple_pred(n, pn_Div_res, value);
1348 static ir_node *transform_node_Mod(ir_node *n)
1350 tarval *tv = value_of(n);
1353 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1355 if (tv != tarval_bad) {
1356 value = new_Const(get_tarval_mode(tv), tv);
1358 DBG_OPT_CSTEVAL(n, value);
1360 else /* Try architecture dependand optimization */
1361 value = arch_dep_replace_mod_by_const(n);
1364 /* Turn Mod into a tuple (mem, bad, value) */
1365 ir_node *mem = get_Mod_mem(n);
1367 turn_into_tuple(n, 3);
1368 set_Tuple_pred(n, pn_Mod_M, mem);
1369 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1370 set_Tuple_pred(n, pn_Mod_res, value);
1375 static ir_node *transform_node_DivMod(ir_node *n)
1379 ir_node *a = get_DivMod_left(n);
1380 ir_node *b = get_DivMod_right(n);
1381 ir_mode *mode = get_irn_mode(a);
1382 tarval *ta = value_of(a);
1383 tarval *tb = value_of(b);
1385 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1388 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1390 if (tb != tarval_bad) {
1391 if (tb == get_mode_one(get_tarval_mode(tb))) {
1392 b = new_Const (mode, get_mode_null(mode));
1395 DBG_OPT_CSTEVAL(n, b);
1397 else if (ta != tarval_bad) {
1398 tarval *resa, *resb;
1399 resa = tarval_div (ta, tb);
1400 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1401 Jmp for X result!? */
1402 resb = tarval_mod (ta, tb);
1403 if (resb == tarval_bad) return n; /* Causes exception! */
1404 a = new_Const (mode, resa);
1405 b = new_Const (mode, resb);
1408 DBG_OPT_CSTEVAL(n, a);
1409 DBG_OPT_CSTEVAL(n, b);
1411 else { /* Try architecture dependand optimization */
1412 arch_dep_replace_divmod_by_const(&a, &b, n);
1413 evaluated = a != NULL;
1415 } else if (ta == get_mode_null(mode)) {
1416 /* 0 / non-Const = 0 */
1421 if (evaluated) { /* replace by tuple */
1422 ir_node *mem = get_DivMod_mem(n);
1423 turn_into_tuple(n, 4);
1424 set_Tuple_pred(n, pn_DivMod_M, mem);
1425 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1426 set_Tuple_pred(n, pn_DivMod_res_div, a);
1427 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1428 assert(get_nodes_block(n));
1434 static ir_node *transform_node_Cond(ir_node *n)
1436 /* Replace the Cond by a Jmp if it branches on a constant
1439 ir_node *a = get_Cond_selector(n);
1440 tarval *ta = value_of(a);
1442 if ((ta != tarval_bad) &&
1443 (get_irn_mode(a) == mode_b) &&
1444 (get_opt_unreachable_code())) {
1445 /* It's a boolean Cond, branching on a boolean constant.
1446 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1447 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1448 turn_into_tuple(n, 2);
1449 if (ta == tarval_b_true) {
1450 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1451 set_Tuple_pred(n, pn_Cond_true, jmp);
1453 set_Tuple_pred(n, pn_Cond_false, jmp);
1454 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1456 /* We might generate an endless loop, so keep it alive. */
1457 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1458 } else if ((ta != tarval_bad) &&
1459 (get_irn_mode(a) == mode_Iu) &&
1460 (get_Cond_kind(n) == dense) &&
1461 (get_opt_unreachable_code())) {
1462 /* I don't want to allow Tuples smaller than the biggest Proj.
1463 Also this tuple might get really big...
1464 I generate the Jmp here, and remember it in link. Link is used
1465 when optimizing Proj. */
1466 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1467 /* We might generate an endless loop, so keep it alive. */
1468 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1469 } else if ((get_irn_op(a) == op_Eor)
1470 && (get_irn_mode(a) == mode_b)
1471 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1472 /* The Eor is a negate. Generate a new Cond without the negate,
1473 simulate the negate by exchanging the results. */
1474 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1476 } else if ((get_irn_op(a) == op_Not)
1477 && (get_irn_mode(a) == mode_b)) {
1478 /* A Not before the Cond. Generate a new Cond without the Not,
1479 simulate the Not by exchanging the results. */
1480 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1489 static ir_node *transform_node_Eor(ir_node *n)
1492 ir_node *a = get_Eor_left(n);
1493 ir_node *b = get_Eor_right(n);
1495 if ((get_irn_mode(n) == mode_b)
1496 && (get_irn_op(a) == op_Proj)
1497 && (get_irn_mode(a) == mode_b)
1498 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1499 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1500 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1501 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1502 mode_b, get_negated_pnc(get_Proj_proj(a)));
1504 DBG_OPT_ALGSIM0(oldn, n);
1506 else if ((get_irn_mode(n) == mode_b)
1507 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
1508 /* The Eor is a Not. Replace it by a Not. */
1509 /* ????!!!Extend to bitfield 1111111. */
1510 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1512 DBG_OPT_ALGSIM0(oldn, n);
1519 * Transform a boolean Not.
1521 static ir_node *transform_node_Not(ir_node *n)
1524 ir_node *a = get_Not_op(n);
1526 if ( (get_irn_mode(n) == mode_b)
1527 && (get_irn_op(a) == op_Proj)
1528 && (get_irn_mode(a) == mode_b)
1529 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1530 /* We negate a Cmp. The Cmp has the negated result anyways! */
1531 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1532 mode_b, get_negated_pnc(get_Proj_proj(a)));
1533 DBG_OPT_ALGSIM0(oldn, n);
1540 * Transform a Cast of a Const into a new Const
1542 static ir_node *transform_node_Cast(ir_node *n) {
1544 ir_node *pred = get_Cast_op(n);
1545 type *tp = get_irn_type(pred);
1547 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1548 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1549 get_Const_tarval(pred), tp);
1550 DBG_OPT_CSTEVAL(oldn, n);
1551 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1552 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1553 get_SymConst_kind(pred), tp);
1554 DBG_OPT_CSTEVAL(oldn, n);
1560 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1561 * done here instead of equivalent node because it creates new
1563 * Removes the exceptions and routes the memory to the NoMem node.
1565 * Further, it optimizes jump tables by removing all impossible cases.
1567 static ir_node *transform_node_Proj(ir_node *proj)
1569 ir_node *n = get_Proj_pred(proj);
1574 switch (get_irn_opcode(n)) {
1576 b = get_Div_right(n);
1579 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1580 proj_nr = get_Proj_proj(proj);
1582 /* this node may float */
1583 set_irn_pinned(n, op_pin_state_floats);
1585 if (proj_nr == pn_Div_X_except) {
1586 /* we found an exception handler, remove it */
1589 /* the memory Proj can be removed */
1590 ir_node *res = get_Div_mem(n);
1591 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1592 if (proj_nr == pn_Div_M)
1598 b = get_Mod_right(n);
1601 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1602 proj_nr = get_Proj_proj(proj);
1604 /* this node may float */
1605 set_irn_pinned(n, op_pin_state_floats);
1607 if (proj_nr == pn_Mod_X_except) {
1608 /* we found an exception handler, remove it */
1611 /* the memory Proj can be removed */
1612 ir_node *res = get_Mod_mem(n);
1613 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1614 if (proj_nr == pn_Mod_M)
1620 b = get_DivMod_right(n);
1623 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1624 proj_nr = get_Proj_proj(proj);
1626 /* this node may float */
1627 set_irn_pinned(n, op_pin_state_floats);
1629 if (proj_nr == pn_DivMod_X_except) {
1630 /* we found an exception handler, remove it */
1634 /* the memory Proj can be removed */
1635 ir_node *res = get_DivMod_mem(n);
1636 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1637 if (proj_nr == pn_DivMod_M)
1644 if (get_opt_unreachable_code()) {
1645 b = get_Cond_selector(n);
1648 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1649 /* we have a constant switch */
1650 long num = get_Proj_proj(proj);
1652 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1653 if (get_tarval_long(tb) == num) {
1654 /* Do NOT create a jump here, or we will have 2 control flow ops
1655 * in a block. This case is optimized away in optimize_cf(). */
1666 /* should not happen, but if it does will be optimized away */
1674 /* we have added a Tuple, optimize it for the current Proj away */
1675 return equivalent_node_Proj(proj);
1679 * returns the operands of a commutative bin-op, if one operand is
1680 * a const, it is returned as the second one.
1682 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1684 ir_node *op_a = get_binop_left(binop);
1685 ir_node *op_b = get_binop_right(binop);
1687 assert(is_op_commutative(get_irn_op(binop)));
1689 if (get_irn_op(op_a) == op_Const) {
1700 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1701 * Such pattern may arise in bitfield stores.
1703 * value c4 value c4 & c2
1704 * AND c3 AND c1 | c3
1709 static ir_node *transform_node_Or_bf_store(ir_node *or)
1713 ir_node *and_l, *c3;
1714 ir_node *value, *c4;
1715 ir_node *new_and, *new_const, *block;
1716 ir_mode *mode = get_irn_mode(or);
1718 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1720 get_comm_Binop_Ops(or, &and, &c1);
1721 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1724 get_comm_Binop_Ops(and, &or_l, &c2);
1725 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1728 get_comm_Binop_Ops(or_l, &and_l, &c3);
1729 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1732 get_comm_Binop_Ops(and_l, &value, &c4);
1733 if (get_irn_op(c4) != op_Const)
1736 /* ok, found the pattern, check for conditions */
1737 assert(mode == get_irn_mode(and));
1738 assert(mode == get_irn_mode(or_l));
1739 assert(mode == get_irn_mode(and_l));
1741 tv1 = get_Const_tarval(c1);
1742 tv2 = get_Const_tarval(c2);
1743 tv3 = get_Const_tarval(c3);
1744 tv4 = get_Const_tarval(c4);
1746 tv = tarval_or(tv4, tv2);
1747 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1748 /* have at least one 0 at the same bit position */
1752 n_tv4 = tarval_not(tv4);
1753 if (tv3 != tarval_and(tv3, n_tv4)) {
1754 /* bit in the or_mask is outside the and_mask */
1758 n_tv2 = tarval_not(tv2);
1759 if (tv1 != tarval_and(tv1, n_tv2)) {
1760 /* bit in the or_mask is outside the and_mask */
1764 /* ok, all conditions met */
1765 block = get_nodes_block(or);
1767 new_and = new_r_And(current_ir_graph, block,
1768 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1770 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1772 set_Or_left(or, new_and);
1773 set_Or_right(or, new_const);
1775 /* check for more */
1776 return transform_node_Or_bf_store(or);
1780 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
1782 static ir_node *transform_node_Or_Rot(ir_node *or)
1784 ir_mode *mode = get_irn_mode(or);
1785 ir_node *shl, *shr, *block;
1786 ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
1789 if (! mode_is_int(mode))
1792 shl = get_binop_left(or);
1793 shr = get_binop_right(or);
1795 if (get_irn_op(shl) == op_Shr) {
1796 if (get_irn_op(shr) != op_Shl)
1803 else if (get_irn_op(shl) != op_Shl)
1805 else if (get_irn_op(shr) != op_Shr)
1808 x = get_Shl_left(shl);
1809 if (x != get_Shr_left(shr))
1812 c1 = get_Shl_right(shl);
1813 c2 = get_Shr_right(shr);
1814 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
1815 tv1 = get_Const_tarval(c1);
1816 if (! tarval_is_long(tv1))
1819 tv2 = get_Const_tarval(c2);
1820 if (! tarval_is_long(tv2))
1823 if (get_tarval_long(tv1) + get_tarval_long(tv2)
1824 != get_mode_size_bits(mode))
1827 /* yet, condition met */
1828 block = get_nodes_block(or);
1830 n = new_r_Rot(current_ir_graph, block, x, c1, mode);
1832 DBG_OPT_ALGSIM1(or, shl, shr, n);
1835 else if (get_irn_op(c1) == op_Sub) {
1839 if (get_Sub_right(sub) != v)
1842 c1 = get_Sub_left(sub);
1843 if (get_irn_op(c1) != op_Const)
1846 tv1 = get_Const_tarval(c1);
1847 if (! tarval_is_long(tv1))
1850 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1853 /* yet, condition met */
1854 block = get_nodes_block(or);
1856 /* a Rot right is not supported, so use a rot left */
1857 n = new_r_Rot(current_ir_graph, block, x, sub, mode);
1859 DBG_OPT_ALGSIM0(or, n);
1862 else if (get_irn_op(c2) == op_Sub) {
1866 c1 = get_Sub_left(sub);
1867 if (get_irn_op(c1) != op_Const)
1870 tv1 = get_Const_tarval(c1);
1871 if (! tarval_is_long(tv1))
1874 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1877 /* yet, condition met */
1878 block = get_nodes_block(or);
1881 n = new_r_Rot(current_ir_graph, block, x, v, mode);
1883 DBG_OPT_ALGSIM0(or, n);
1893 static ir_node *transform_node_Or(ir_node *or)
1895 or = transform_node_Or_bf_store(or);
1896 or = transform_node_Or_Rot(or);
1902 static ir_node *transform_node(ir_node *n);
1905 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1907 static ir_node * transform_node_shift(ir_node *n)
1909 ir_node *left, *right;
1910 tarval *tv1, *tv2, *res;
1912 int modulo_shf, flag;
1914 left = get_binop_left(n);
1916 /* different operations */
1917 if (get_irn_op(left) != get_irn_op(n))
1920 right = get_binop_right(n);
1921 tv1 = value_of(right);
1922 if (tv1 == tarval_bad)
1925 tv2 = value_of(get_binop_right(left));
1926 if (tv2 == tarval_bad)
1929 res = tarval_add(tv1, tv2);
1931 /* beware: a simple replacement works only, if res < modulo shift */
1932 mode = get_irn_mode(n);
1936 modulo_shf = get_mode_modulo_shift(mode);
1937 if (modulo_shf > 0) {
1938 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1940 if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
1947 /* ok, we can replace it */
1948 ir_node *in[2], *irn, *block = get_nodes_block(n);
1950 in[0] = get_binop_left(left);
1951 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1953 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1955 DBG_OPT_ALGSIM0(n, irn);
1957 return transform_node(irn);
1962 static ir_node * transform_node_End(ir_node *n) {
1963 int i, n_keepalives = get_End_n_keepalives(n);
1965 /* Remove dead blocks in keepalive list.
1966 We do not generate a new End node. */
1967 for (i = 0; i < n_keepalives; ++i) {
1968 ir_node *ka = get_End_keepalive(n, i);
1969 if (is_Block(ka) && is_Block_dead(ka))
1970 set_End_keepalive(n, i, new_Bad());
1977 * Tries several [inplace] [optimizing] transformations and returns an
1978 * equivalent node. The difference to equivalent_node() is that these
1979 * transformations _do_ generate new nodes, and thus the old node must
1980 * not be freed even if the equivalent node isn't the old one.
1982 static ir_node *transform_node(ir_node *n)
1984 if (n->op->transform_node)
1985 n = n->op->transform_node(n);
1990 * set the default transform node operation
1992 static ir_op *firm_set_default_transform_node(ir_op *op)
1996 op->transform_node = transform_node_##a; \
2016 op->transform_node = transform_node_shift;
2019 op->transform_node = NULL;
2027 /* **************** Common Subexpression Elimination **************** */
2029 /** The size of the hash table used, should estimate the number of nodes
2031 #define N_IR_NODES 512
2033 /** Compares the attributes of two Const nodes. */
2034 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2036 return (get_Const_tarval(a) != get_Const_tarval(b))
2037 || (get_Const_type(a) != get_Const_type(b));
2040 /** Compares the attributes of two Proj nodes. */
2041 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2043 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2046 /** Compares the attributes of two Filter nodes. */
2047 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2049 return get_Filter_proj(a) != get_Filter_proj(b);
2052 /** Compares the attributes of two Alloc nodes. */
2053 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2055 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2056 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2059 /** Compares the attributes of two Free nodes. */
2060 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2062 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2063 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2066 /** Compares the attributes of two SymConst nodes. */
2067 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2069 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2070 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2071 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2074 /** Compares the attributes of two Call nodes. */
2075 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2077 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2080 /** Compares the attributes of two Sel nodes. */
2081 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2083 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2084 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2085 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2086 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2087 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2090 /** Compares the attributes of two Phi nodes. */
2091 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2093 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2096 /** Compares the attributes of two Cast nodes. */
2097 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2099 return get_Cast_type(a) != get_Cast_type(b);
2102 /** Compares the attributes of two Load nodes. */
2103 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2105 if (get_Load_volatility(a) == volatility_is_volatile ||
2106 get_Load_volatility(b) == volatility_is_volatile)
2107 /* NEVER do CSE on volatile Loads */
2110 return get_Load_mode(a) != get_Load_mode(b);
2113 /** Compares the attributes of two Store nodes. */
2114 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2116 /* NEVER do CSE on volatile Stores */
2117 return (get_Store_volatility(a) == volatility_is_volatile ||
2118 get_Store_volatility(b) == volatility_is_volatile);
2122 * set the default node attribute compare operation
2124 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2128 op->node_cmp_attr = node_cmp_attr_##a; \
2145 op->node_cmp_attr = NULL;
2153 * Compare function for two nodes in the hash table. Gets two
2154 * nodes as parameters. Returns 0 if the nodes are a cse.
2157 vt_cmp (const void *elt, const void *key)
2165 if (a == b) return 0;
2167 if ((get_irn_op(a) != get_irn_op(b)) ||
2168 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2170 /* compare if a's in and b's in are of equal length */
2171 irn_arity_a = get_irn_intra_arity (a);
2172 if (irn_arity_a != get_irn_intra_arity(b))
2175 /* for block-local cse and op_pin_state_pinned nodes: */
2176 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2177 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2181 /* compare a->in[0..ins] with b->in[0..ins] */
2182 for (i = 0; i < irn_arity_a; i++)
2183 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2187 * here, we already now that the nodes are identical except their
2190 if (a->op->node_cmp_attr)
2191 return a->op->node_cmp_attr(a, b);
2197 * Calculate a hash value of a node.
2200 ir_node_hash (ir_node *node)
2205 if (node->op == op_Const) {
2206 /* special value for const, as they only differ in their tarval. */
2207 h = HASH_PTR(node->attr.con.tv);
2208 h = 9*h + HASH_PTR(get_irn_mode(node));
2209 } else if (node->op == op_SymConst) {
2210 /* special value for const, as they only differ in their symbol. */
2211 h = HASH_PTR(node->attr.i.sym.type_p);
2212 h = 9*h + HASH_PTR(get_irn_mode(node));
2215 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2216 h = irn_arity = get_irn_intra_arity(node);
2218 /* consider all in nodes... except the block if not a control flow. */
2219 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2220 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2224 h = 9*h + HASH_PTR(get_irn_mode(node));
2226 h = 9*h + HASH_PTR(get_irn_op(node));
2233 new_identities(void) {
2234 return new_pset(vt_cmp, N_IR_NODES);
2238 del_identities(pset *value_table) {
2239 del_pset(value_table);
2243 * Return the canonical node computing the same value as n.
2244 * Looks up the node in a hash table.
2246 * For Const nodes this is performed in the constructor, too. Const
2247 * nodes are extremely time critical because of their frequent use in
2248 * constant string arrays.
2250 static INLINE ir_node *
2251 identify (pset *value_table, ir_node *n)
2255 if (!value_table) return n;
2257 if (get_opt_reassociation()) {
2258 if (is_op_commutative(get_irn_op(n))) {
2259 ir_node *l = get_binop_left(n);
2260 ir_node *r = get_binop_right(n);
2262 /* for commutative operators perform a OP b == b OP a */
2264 set_binop_left(n, r);
2265 set_binop_right(n, l);
2270 o = pset_find (value_table, n, ir_node_hash (n));
2279 * During construction we set the op_pin_state_pinned flag in the graph right when the
2280 * optimization is performed. The flag turning on procedure global cse could
2281 * be changed between two allocations. This way we are safe.
2283 static INLINE ir_node *
2284 identify_cons (pset *value_table, ir_node *n) {
2287 n = identify(value_table, n);
2288 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2289 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2294 * Return the canonical node computing the same value as n.
2295 * Looks up the node in a hash table, enters it in the table
2296 * if it isn't there yet.
2299 identify_remember (pset *value_table, ir_node *n)
2303 if (!value_table) return n;
2305 if (get_opt_reassociation()) {
2306 if (is_op_commutative(get_irn_op(n))) {
2307 ir_node *l = get_binop_left(n);
2308 ir_node *r = get_binop_right(n);
2310 /* for commutative operators perform a OP b == b OP a */
2312 set_binop_left(n, r);
2313 set_binop_right(n, l);
2318 /* lookup or insert in hash table with given hash key. */
2319 o = pset_insert (value_table, n, ir_node_hash (n));
2329 add_identities (pset *value_table, ir_node *node) {
2330 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2331 identify_remember (value_table, node);
2335 * garbage in, garbage out. If a node has a dead input, i.e., the
2336 * Bad node is input to the node, return the Bad node.
2338 static INLINE ir_node *
2339 gigo (ir_node *node)
2342 ir_op* op = get_irn_op(node);
2344 /* remove garbage blocks by looking at control flow that leaves the block
2345 and replacing the control flow by Bad. */
2346 if (get_irn_mode(node) == mode_X) {
2347 ir_node *block = get_nodes_block(node);
2348 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2349 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2351 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2352 irn_arity = get_irn_arity(block);
2353 for (i = 0; i < irn_arity; i++) {
2354 if (!is_Bad(get_irn_n(block, i))) break;
2356 if (i == irn_arity) return new_Bad();
2360 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2361 blocks predecessors is dead. */
2362 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2363 irn_arity = get_irn_arity(node);
2365 if (is_Block_dead(get_nodes_block(node)))
2368 for (i = 0; i < irn_arity; i++) {
2369 if (is_Bad(get_irn_n(node, i))) {
2375 /* With this code we violate the agreement that local_optimize
2376 only leaves Bads in Block, Phi and Tuple nodes. */
2377 /* If Block has only Bads as predecessors it's garbage. */
2378 /* If Phi has only Bads as predecessors it's garbage. */
2379 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2380 irn_arity = get_irn_arity(node);
2381 for (i = 0; i < irn_arity; i++) {
2382 if (!is_Bad(get_irn_n(node, i))) break;
2384 if (i == irn_arity) node = new_Bad();
2392 * These optimizations deallocate nodes from the obstack.
2393 * It can only be called if it is guaranteed that no other nodes
2394 * reference this one, i.e., right after construction of a node.
2397 optimize_node (ir_node *n)
2401 opcode iro = get_irn_opcode(n);
2403 type *old_tp = get_irn_type(n);
2405 int i, arity = get_irn_arity(n);
2406 for (i = 0; i < arity && !old_tp; ++i)
2407 old_tp = get_irn_type(get_irn_n(n, i));
2410 /* Always optimize Phi nodes: part of the construction. */
2411 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2413 /* constant expression evaluation / constant folding */
2414 if (get_opt_constant_folding()) {
2415 /* constants can not be evaluated */
2416 if (iro != iro_Const) {
2417 /* try to evaluate */
2418 tv = computed_value(n);
2419 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2423 * we MUST copy the node here temporary, because it's still needed
2424 * for DBG_OPT_CSTEVAL
2426 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2427 oldn = alloca(node_size);
2429 memcpy(oldn, n, node_size);
2430 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2432 /* ARG, copy the in array, we need it for statistics */
2433 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2436 edges_node_deleted(n, current_ir_graph);
2438 /* evaluation was successful -- replace the node. */
2439 obstack_free (current_ir_graph->obst, n);
2440 nw = new_Const (get_tarval_mode (tv), tv);
2442 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2443 set_Const_type(nw, old_tp);
2444 DBG_OPT_CSTEVAL(oldn, nw);
2450 /* remove unnecessary nodes */
2451 if (get_opt_constant_folding() ||
2452 (iro == iro_Phi) || /* always optimize these nodes. */
2454 (iro == iro_Proj) ||
2455 (iro == iro_Block) ) /* Flags tested local. */
2456 n = equivalent_node (n);
2458 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2460 /** common subexpression elimination **/
2461 /* Checks whether n is already available. */
2462 /* The block input is used to distinguish different subexpressions. Right
2463 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2464 subexpressions within a block. */
2466 n = identify_cons (current_ir_graph->value_table, n);
2469 edges_node_deleted(oldn, current_ir_graph);
2471 /* We found an existing, better node, so we can deallocate the old node. */
2472 obstack_free (current_ir_graph->obst, oldn);
2477 /* Some more constant expression evaluation that does not allow to
2479 iro = get_irn_opcode(n);
2480 if (get_opt_constant_folding() ||
2481 (iro == iro_Cond) ||
2482 (iro == iro_Proj)) /* Flags tested local. */
2483 n = transform_node (n);
2485 /* Remove nodes with dead (Bad) input.
2486 Run always for transformation induced Bads. */
2489 /* Now we have a legal, useful node. Enter it in hash table for cse */
2490 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2491 n = identify_remember (current_ir_graph->value_table, n);
2499 * These optimizations never deallocate nodes (in place). This can cause dead
2500 * nodes lying on the obstack. Remove these by a dead node elimination,
2501 * i.e., a copying garbage collection.
2504 optimize_in_place_2 (ir_node *n)
2508 opcode iro = get_irn_opcode(n);
2510 type *old_tp = get_irn_type(n);
2512 int i, arity = get_irn_arity(n);
2513 for (i = 0; i < arity && !old_tp; ++i)
2514 old_tp = get_irn_type(get_irn_n(n, i));
2517 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2519 /* if not optimize return n */
2522 /* Here this is possible. Why? */
2526 /* constant expression evaluation / constant folding */
2527 if (get_opt_constant_folding()) {
2528 /* constants can not be evaluated */
2529 if (iro != iro_Const) {
2530 /* try to evaluate */
2531 tv = computed_value(n);
2532 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2533 /* evaluation was successful -- replace the node. */
2534 n = new_Const (get_tarval_mode (tv), tv);
2536 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2537 set_Const_type(n, old_tp);
2539 DBG_OPT_CSTEVAL(oldn, n);
2545 /* remove unnecessary nodes */
2546 if (get_opt_constant_folding() ||
2547 (iro == iro_Phi) || /* always optimize these nodes. */
2548 (iro == iro_Id) || /* ... */
2549 (iro == iro_Proj) || /* ... */
2550 (iro == iro_Block) ) /* Flags tested local. */
2551 n = equivalent_node (n);
2553 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2555 /** common subexpression elimination **/
2556 /* Checks whether n is already available. */
2557 /* The block input is used to distinguish different subexpressions. Right
2558 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2559 subexpressions within a block. */
2560 if (get_opt_cse()) {
2561 n = identify (current_ir_graph->value_table, n);
2564 /* Some more constant expression evaluation. */
2565 iro = get_irn_opcode(n);
2566 if (get_opt_constant_folding() ||
2567 (iro == iro_Cond) ||
2568 (iro == iro_Proj)) /* Flags tested local. */
2569 n = transform_node (n);
2571 /* Remove nodes with dead (Bad) input.
2572 Run always for transformation induced Bads. */
2575 /* Now we can verify the node, as it has no dead inputs any more. */
2578 /* Now we have a legal, useful node. Enter it in hash table for cse.
2579 Blocks should be unique anyways. (Except the successor of start:
2580 is cse with the start block!) */
2581 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2582 n = identify_remember (current_ir_graph->value_table, n);
2588 * Wrapper for external use, set proper status bits after optimization.
2591 optimize_in_place (ir_node *n)
2593 /* Handle graph state */
2594 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2596 if (get_opt_global_cse())
2597 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2598 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2599 set_irg_outs_inconsistent(current_ir_graph);
2601 /* Maybe we could also test whether optimizing the node can
2602 change the control graph. */
2603 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2604 set_irg_dom_inconsistent(current_ir_graph);
2605 return optimize_in_place_2 (n);
2609 * set the default ir op operations
2611 ir_op *firm_set_default_operations(ir_op *op)
2613 op = firm_set_default_computed_value(op);
2614 op = firm_set_default_equivalent_node(op);
2615 op = firm_set_default_transform_node(op);
2616 op = firm_set_default_node_cmp_attr(op);
2617 op = firm_set_default_get_type(op);