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)) if possible.
1199 static ir_node *transform_node_AddSub(ir_node *n)
1201 ir_mode *mode = get_irn_mode(n);
1203 if (mode_is_reference(mode)) {
1204 ir_node *left = get_binop_left(n);
1205 ir_node *right = get_binop_right(n);
1206 int ref_bits = get_mode_size_bits(mode);
1208 if (get_irn_op(left) == op_Conv) {
1209 ir_mode *mode = get_irn_mode(left);
1210 int bits = get_mode_size_bits(mode);
1212 if (ref_bits == bits &&
1213 mode_is_int(mode) &&
1214 get_mode_arithmetic(mode) == irma_twos_complement) {
1215 ir_node *pre = get_Conv_op(left);
1216 ir_mode *pre_mode = get_irn_mode(pre);
1218 if (mode_is_int(pre_mode) &&
1219 get_mode_size_bits(pre_mode) == bits &&
1220 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1221 /* ok, this conv just changes to sign, moreover the calculation
1222 * is done with same number of bits as our address mode, so
1223 * we can ignore the conv as address calculation can be viewed
1224 * as either signed or unsigned
1226 set_binop_left(n, pre);
1231 if (get_irn_op(right) == op_Conv) {
1232 ir_mode *mode = get_irn_mode(right);
1233 int bits = get_mode_size_bits(mode);
1235 if (ref_bits == bits &&
1236 mode_is_int(mode) &&
1237 get_mode_arithmetic(mode) == irma_twos_complement) {
1238 ir_node *pre = get_Conv_op(right);
1239 ir_mode *pre_mode = get_irn_mode(pre);
1241 if (mode_is_int(pre_mode) &&
1242 get_mode_size_bits(pre_mode) == bits &&
1243 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1244 /* ok, this conv just changes to sign, moreover the calculation
1245 * is done with same number of bits as our address mode, so
1246 * we can ignore the conv as address calculation can be viewed
1247 * as either signed or unsigned
1249 set_binop_right(n, pre);
1257 #define transform_node_Add transform_node_AddSub
1260 * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
1262 static ir_node *transform_node_Sub(ir_node *n)
1267 n = transform_node_AddSub(n);
1269 mode = get_irn_mode(n);
1270 if (mode_is_num(mode)) {
1271 if (classify_Const(get_Sub_left(n)) == CNST_NULL) {
1273 get_irn_dbg_info(n),
1278 DBG_OPT_ALGSIM0(oldn, n);
1285 /** Do architecture dependend optimizations on Mul nodes */
1286 static ir_node *transform_node_Mul(ir_node *n) {
1287 return arch_dep_replace_mul_with_shifts(n);
1290 static ir_node *transform_node_Div(ir_node *n)
1292 tarval *tv = value_of(n);
1295 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1297 if (tv != tarval_bad) {
1298 value = new_Const(get_tarval_mode(tv), tv);
1300 DBG_OPT_CSTEVAL(n, value);
1302 else /* Try architecture dependand optimization */
1303 value = arch_dep_replace_div_by_const(n);
1306 /* Turn Div into a tuple (mem, bad, value) */
1307 ir_node *mem = get_Div_mem(n);
1309 turn_into_tuple(n, 3);
1310 set_Tuple_pred(n, pn_Div_M, mem);
1311 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1312 set_Tuple_pred(n, pn_Div_res, value);
1317 static ir_node *transform_node_Mod(ir_node *n)
1319 tarval *tv = value_of(n);
1322 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1324 if (tv != tarval_bad) {
1325 value = new_Const(get_tarval_mode(tv), tv);
1327 DBG_OPT_CSTEVAL(n, value);
1329 else /* Try architecture dependand optimization */
1330 value = arch_dep_replace_mod_by_const(n);
1333 /* Turn Mod into a tuple (mem, bad, value) */
1334 ir_node *mem = get_Mod_mem(n);
1336 turn_into_tuple(n, 3);
1337 set_Tuple_pred(n, pn_Mod_M, mem);
1338 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1339 set_Tuple_pred(n, pn_Mod_res, value);
1344 static ir_node *transform_node_DivMod(ir_node *n)
1348 ir_node *a = get_DivMod_left(n);
1349 ir_node *b = get_DivMod_right(n);
1350 ir_mode *mode = get_irn_mode(a);
1351 tarval *ta = value_of(a);
1352 tarval *tb = value_of(b);
1354 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1357 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1359 if (tb != tarval_bad) {
1360 if (tb == get_mode_one(get_tarval_mode(tb))) {
1361 b = new_Const (mode, get_mode_null(mode));
1364 DBG_OPT_CSTEVAL(n, b);
1366 else if (ta != tarval_bad) {
1367 tarval *resa, *resb;
1368 resa = tarval_div (ta, tb);
1369 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1370 Jmp for X result!? */
1371 resb = tarval_mod (ta, tb);
1372 if (resb == tarval_bad) return n; /* Causes exception! */
1373 a = new_Const (mode, resa);
1374 b = new_Const (mode, resb);
1377 DBG_OPT_CSTEVAL(n, a);
1378 DBG_OPT_CSTEVAL(n, b);
1380 else { /* Try architecture dependand optimization */
1381 arch_dep_replace_divmod_by_const(&a, &b, n);
1382 evaluated = a != NULL;
1384 } else if (ta == get_mode_null(mode)) {
1385 /* 0 / non-Const = 0 */
1390 if (evaluated) { /* replace by tuple */
1391 ir_node *mem = get_DivMod_mem(n);
1392 turn_into_tuple(n, 4);
1393 set_Tuple_pred(n, pn_DivMod_M, mem);
1394 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1395 set_Tuple_pred(n, pn_DivMod_res_div, a);
1396 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1397 assert(get_nodes_block(n));
1403 static ir_node *transform_node_Cond(ir_node *n)
1405 /* Replace the Cond by a Jmp if it branches on a constant
1408 ir_node *a = get_Cond_selector(n);
1409 tarval *ta = value_of(a);
1411 if ((ta != tarval_bad) &&
1412 (get_irn_mode(a) == mode_b) &&
1413 (get_opt_unreachable_code())) {
1414 /* It's a boolean Cond, branching on a boolean constant.
1415 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1416 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1417 turn_into_tuple(n, 2);
1418 if (ta == tarval_b_true) {
1419 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1420 set_Tuple_pred(n, pn_Cond_true, jmp);
1422 set_Tuple_pred(n, pn_Cond_false, jmp);
1423 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1425 /* We might generate an endless loop, so keep it alive. */
1426 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1427 } else if ((ta != tarval_bad) &&
1428 (get_irn_mode(a) == mode_Iu) &&
1429 (get_Cond_kind(n) == dense) &&
1430 (get_opt_unreachable_code())) {
1431 /* I don't want to allow Tuples smaller than the biggest Proj.
1432 Also this tuple might get really big...
1433 I generate the Jmp here, and remember it in link. Link is used
1434 when optimizing Proj. */
1435 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1436 /* We might generate an endless loop, so keep it alive. */
1437 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1438 } else if ((get_irn_op(a) == op_Eor)
1439 && (get_irn_mode(a) == mode_b)
1440 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1441 /* The Eor is a negate. Generate a new Cond without the negate,
1442 simulate the negate by exchanging the results. */
1443 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1445 } else if ((get_irn_op(a) == op_Not)
1446 && (get_irn_mode(a) == mode_b)) {
1447 /* A Not before the Cond. Generate a new Cond without the Not,
1448 simulate the Not by exchanging the results. */
1449 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1458 static ir_node *transform_node_Eor(ir_node *n)
1461 ir_node *a = get_Eor_left(n);
1462 ir_node *b = get_Eor_right(n);
1464 if ((get_irn_mode(n) == mode_b)
1465 && (get_irn_op(a) == op_Proj)
1466 && (get_irn_mode(a) == mode_b)
1467 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1468 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1469 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1470 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1471 mode_b, get_negated_pnc(get_Proj_proj(a)));
1473 DBG_OPT_ALGSIM0(oldn, n);
1475 else if ((get_irn_mode(n) == mode_b)
1476 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
1477 /* The Eor is a Not. Replace it by a Not. */
1478 /* ????!!!Extend to bitfield 1111111. */
1479 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1481 DBG_OPT_ALGSIM0(oldn, n);
1488 * Transform a boolean Not.
1490 static ir_node *transform_node_Not(ir_node *n)
1493 ir_node *a = get_Not_op(n);
1495 if ( (get_irn_mode(n) == mode_b)
1496 && (get_irn_op(a) == op_Proj)
1497 && (get_irn_mode(a) == mode_b)
1498 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1499 /* We negate a Cmp. The Cmp has the negated result anyways! */
1500 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1501 mode_b, get_negated_pnc(get_Proj_proj(a)));
1502 DBG_OPT_ALGSIM0(oldn, n);
1509 * Transform a Cast of a Const into a new Const
1511 static ir_node *transform_node_Cast(ir_node *n) {
1513 ir_node *pred = get_Cast_op(n);
1514 type *tp = get_irn_type(pred);
1516 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1517 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1518 get_Const_tarval(pred), tp);
1519 DBG_OPT_CSTEVAL(oldn, n);
1520 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1521 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1522 get_SymConst_kind(pred), tp);
1523 DBG_OPT_CSTEVAL(oldn, n);
1529 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1530 * done here instead of equivalent node because it creates new
1532 * Removes the exceptions and routes the memory to the NoMem node.
1534 * Further, it optimizes jump tables by removing all impossible cases.
1536 static ir_node *transform_node_Proj(ir_node *proj)
1538 ir_node *n = get_Proj_pred(proj);
1543 switch (get_irn_opcode(n)) {
1545 b = get_Div_right(n);
1548 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1549 proj_nr = get_Proj_proj(proj);
1551 /* this node may float */
1552 set_irn_pinned(n, op_pin_state_floats);
1554 if (proj_nr == pn_Div_X_except) {
1555 /* we found an exception handler, remove it */
1558 /* the memory Proj can be removed */
1559 ir_node *res = get_Div_mem(n);
1560 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1561 if (proj_nr == pn_Div_M)
1567 b = get_Mod_right(n);
1570 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1571 proj_nr = get_Proj_proj(proj);
1573 /* this node may float */
1574 set_irn_pinned(n, op_pin_state_floats);
1576 if (proj_nr == pn_Mod_X_except) {
1577 /* we found an exception handler, remove it */
1580 /* the memory Proj can be removed */
1581 ir_node *res = get_Mod_mem(n);
1582 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1583 if (proj_nr == pn_Mod_M)
1589 b = get_DivMod_right(n);
1592 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1593 proj_nr = get_Proj_proj(proj);
1595 /* this node may float */
1596 set_irn_pinned(n, op_pin_state_floats);
1598 if (proj_nr == pn_DivMod_X_except) {
1599 /* we found an exception handler, remove it */
1603 /* the memory Proj can be removed */
1604 ir_node *res = get_DivMod_mem(n);
1605 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1606 if (proj_nr == pn_DivMod_M)
1613 if (get_opt_unreachable_code()) {
1614 b = get_Cond_selector(n);
1617 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1618 /* we have a constant switch */
1619 long num = get_Proj_proj(proj);
1621 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1622 if (get_tarval_long(tb) == num) {
1623 /* Do NOT create a jump here, or we will have 2 control flow ops
1624 * in a block. This case is optimized away in optimize_cf(). */
1635 /* should not happen, but if it does will be optimized away */
1643 /* we have added a Tuple, optimize it for the current Proj away */
1644 return equivalent_node_Proj(proj);
1648 * returns the operands of a commutative bin-op, if one operand is
1649 * a const, it is returned as the second one.
1651 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1653 ir_node *op_a = get_binop_left(binop);
1654 ir_node *op_b = get_binop_right(binop);
1656 assert(is_op_commutative(get_irn_op(binop)));
1658 if (get_irn_op(op_a) == op_Const) {
1669 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1670 * Such pattern may arise in bitfield stores.
1672 * value c4 value c4 & c2
1673 * AND c3 AND c1 | c3
1678 static ir_node *transform_node_Or_bf_store(ir_node *or)
1682 ir_node *and_l, *c3;
1683 ir_node *value, *c4;
1684 ir_node *new_and, *new_const, *block;
1685 ir_mode *mode = get_irn_mode(or);
1687 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1689 get_comm_Binop_Ops(or, &and, &c1);
1690 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1693 get_comm_Binop_Ops(and, &or_l, &c2);
1694 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1697 get_comm_Binop_Ops(or_l, &and_l, &c3);
1698 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1701 get_comm_Binop_Ops(and_l, &value, &c4);
1702 if (get_irn_op(c4) != op_Const)
1705 /* ok, found the pattern, check for conditions */
1706 assert(mode == get_irn_mode(and));
1707 assert(mode == get_irn_mode(or_l));
1708 assert(mode == get_irn_mode(and_l));
1710 tv1 = get_Const_tarval(c1);
1711 tv2 = get_Const_tarval(c2);
1712 tv3 = get_Const_tarval(c3);
1713 tv4 = get_Const_tarval(c4);
1715 tv = tarval_or(tv4, tv2);
1716 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1717 /* have at least one 0 at the same bit position */
1721 n_tv4 = tarval_not(tv4);
1722 if (tv3 != tarval_and(tv3, n_tv4)) {
1723 /* bit in the or_mask is outside the and_mask */
1727 n_tv2 = tarval_not(tv2);
1728 if (tv1 != tarval_and(tv1, n_tv2)) {
1729 /* bit in the or_mask is outside the and_mask */
1733 /* ok, all conditions met */
1734 block = get_nodes_block(or);
1736 new_and = new_r_And(current_ir_graph, block,
1737 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1739 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1741 set_Or_left(or, new_and);
1742 set_Or_right(or, new_const);
1744 /* check for more */
1745 return transform_node_Or_bf_store(or);
1749 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
1751 static ir_node *transform_node_Or_Rot(ir_node *or)
1753 ir_mode *mode = get_irn_mode(or);
1754 ir_node *shl, *shr, *block;
1755 ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
1758 if (! mode_is_int(mode))
1761 shl = get_binop_left(or);
1762 shr = get_binop_right(or);
1764 if (get_irn_op(shl) == op_Shr) {
1765 if (get_irn_op(shr) != op_Shl)
1772 else if (get_irn_op(shl) != op_Shl)
1774 else if (get_irn_op(shr) != op_Shr)
1777 x = get_Shl_left(shl);
1778 if (x != get_Shr_left(shr))
1781 c1 = get_Shl_right(shl);
1782 c2 = get_Shr_right(shr);
1783 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
1784 tv1 = get_Const_tarval(c1);
1785 if (! tarval_is_long(tv1))
1788 tv2 = get_Const_tarval(c2);
1789 if (! tarval_is_long(tv2))
1792 if (get_tarval_long(tv1) + get_tarval_long(tv2)
1793 != get_mode_size_bits(mode))
1796 /* yet, condition met */
1797 block = get_nodes_block(or);
1799 n = new_r_Rot(current_ir_graph, block, x, c1, mode);
1801 DBG_OPT_ALGSIM1(or, shl, shr, n);
1804 else if (get_irn_op(c1) == op_Sub) {
1808 if (get_Sub_right(sub) != v)
1811 c1 = get_Sub_left(sub);
1812 if (get_irn_op(c1) != op_Const)
1815 tv1 = get_Const_tarval(c1);
1816 if (! tarval_is_long(tv1))
1819 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1822 /* yet, condition met */
1823 block = get_nodes_block(or);
1825 /* a Rot right is not supported, so use a rot left */
1826 n = new_r_Rot(current_ir_graph, block, x, sub, mode);
1828 DBG_OPT_ALGSIM0(or, n);
1831 else if (get_irn_op(c2) == op_Sub) {
1835 c1 = get_Sub_left(sub);
1836 if (get_irn_op(c1) != op_Const)
1839 tv1 = get_Const_tarval(c1);
1840 if (! tarval_is_long(tv1))
1843 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1846 /* yet, condition met */
1847 block = get_nodes_block(or);
1850 n = new_r_Rot(current_ir_graph, block, x, v, mode);
1852 DBG_OPT_ALGSIM0(or, n);
1862 static ir_node *transform_node_Or(ir_node *or)
1864 or = transform_node_Or_bf_store(or);
1865 or = transform_node_Or_Rot(or);
1871 static ir_node *transform_node(ir_node *n);
1874 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1876 static ir_node * transform_node_shift(ir_node *n)
1878 ir_node *left, *right;
1879 tarval *tv1, *tv2, *res;
1881 int modulo_shf, flag;
1883 left = get_binop_left(n);
1885 /* different operations */
1886 if (get_irn_op(left) != get_irn_op(n))
1889 right = get_binop_right(n);
1890 tv1 = value_of(right);
1891 if (tv1 == tarval_bad)
1894 tv2 = value_of(get_binop_right(left));
1895 if (tv2 == tarval_bad)
1898 res = tarval_add(tv1, tv2);
1900 /* beware: a simple replacement works only, if res < modulo shift */
1901 mode = get_irn_mode(n);
1905 modulo_shf = get_mode_modulo_shift(mode);
1906 if (modulo_shf > 0) {
1907 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1909 if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
1916 /* ok, we can replace it */
1917 ir_node *in[2], *irn, *block = get_nodes_block(n);
1919 in[0] = get_binop_left(left);
1920 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1922 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1924 DBG_OPT_ALGSIM0(n, irn);
1926 return transform_node(irn);
1931 static ir_node * transform_node_End(ir_node *n) {
1932 int i, n_keepalives = get_End_n_keepalives(n);
1934 /* Remove dead blocks in keepalive list.
1935 We do not generate a new End node. */
1936 for (i = 0; i < n_keepalives; ++i) {
1937 ir_node *ka = get_End_keepalive(n, i);
1938 if (is_Block(ka) && is_Block_dead(ka))
1939 set_End_keepalive(n, i, new_Bad());
1946 * Tries several [inplace] [optimizing] transformations and returns an
1947 * equivalent node. The difference to equivalent_node() is that these
1948 * transformations _do_ generate new nodes, and thus the old node must
1949 * not be freed even if the equivalent node isn't the old one.
1951 static ir_node *transform_node(ir_node *n)
1953 if (n->op->transform_node)
1954 n = n->op->transform_node(n);
1959 * set the default transform node operation
1961 static ir_op *firm_set_default_transform_node(ir_op *op)
1965 op->transform_node = transform_node_##a; \
1985 op->transform_node = transform_node_shift;
1988 op->transform_node = NULL;
1996 /* **************** Common Subexpression Elimination **************** */
1998 /** The size of the hash table used, should estimate the number of nodes
2000 #define N_IR_NODES 512
2002 /** Compares the attributes of two Const nodes. */
2003 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2005 return (get_Const_tarval(a) != get_Const_tarval(b))
2006 || (get_Const_type(a) != get_Const_type(b));
2009 /** Compares the attributes of two Proj nodes. */
2010 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2012 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2015 /** Compares the attributes of two Filter nodes. */
2016 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2018 return get_Filter_proj(a) != get_Filter_proj(b);
2021 /** Compares the attributes of two Alloc nodes. */
2022 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2024 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2025 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2028 /** Compares the attributes of two Free nodes. */
2029 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2031 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2032 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2035 /** Compares the attributes of two SymConst nodes. */
2036 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2038 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2039 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2040 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2043 /** Compares the attributes of two Call nodes. */
2044 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2046 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2049 /** Compares the attributes of two Sel nodes. */
2050 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2052 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2053 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2054 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2055 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2056 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2059 /** Compares the attributes of two Phi nodes. */
2060 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2062 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2065 /** Compares the attributes of two Cast nodes. */
2066 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2068 return get_Cast_type(a) != get_Cast_type(b);
2071 /** Compares the attributes of two Load nodes. */
2072 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2074 if (get_Load_volatility(a) == volatility_is_volatile ||
2075 get_Load_volatility(b) == volatility_is_volatile)
2076 /* NEVER do CSE on volatile Loads */
2079 return get_Load_mode(a) != get_Load_mode(b);
2082 /** Compares the attributes of two Store nodes. */
2083 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2085 /* NEVER do CSE on volatile Stores */
2086 return (get_Store_volatility(a) == volatility_is_volatile ||
2087 get_Store_volatility(b) == volatility_is_volatile);
2091 * set the default node attribute compare operation
2093 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2097 op->node_cmp_attr = node_cmp_attr_##a; \
2114 op->node_cmp_attr = NULL;
2122 * Compare function for two nodes in the hash table. Gets two
2123 * nodes as parameters. Returns 0 if the nodes are a cse.
2126 vt_cmp (const void *elt, const void *key)
2134 if (a == b) return 0;
2136 if ((get_irn_op(a) != get_irn_op(b)) ||
2137 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2139 /* compare if a's in and b's in are of equal length */
2140 irn_arity_a = get_irn_intra_arity (a);
2141 if (irn_arity_a != get_irn_intra_arity(b))
2144 /* for block-local cse and op_pin_state_pinned nodes: */
2145 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2146 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2150 /* compare a->in[0..ins] with b->in[0..ins] */
2151 for (i = 0; i < irn_arity_a; i++)
2152 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2156 * here, we already now that the nodes are identical except their
2159 if (a->op->node_cmp_attr)
2160 return a->op->node_cmp_attr(a, b);
2166 * Calculate a hash value of a node.
2169 ir_node_hash (ir_node *node)
2174 if (node->op == op_Const) {
2175 /* special value for const, as they only differ in their tarval. */
2176 h = HASH_PTR(node->attr.con.tv);
2177 h = 9*h + HASH_PTR(get_irn_mode(node));
2178 } else if (node->op == op_SymConst) {
2179 /* special value for const, as they only differ in their symbol. */
2180 h = HASH_PTR(node->attr.i.sym.type_p);
2181 h = 9*h + HASH_PTR(get_irn_mode(node));
2184 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2185 h = irn_arity = get_irn_intra_arity(node);
2187 /* consider all in nodes... except the block if not a control flow. */
2188 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2189 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2193 h = 9*h + HASH_PTR(get_irn_mode(node));
2195 h = 9*h + HASH_PTR(get_irn_op(node));
2202 new_identities(void) {
2203 return new_pset(vt_cmp, N_IR_NODES);
2207 del_identities(pset *value_table) {
2208 del_pset(value_table);
2212 * Return the canonical node computing the same value as n.
2213 * Looks up the node in a hash table.
2215 * For Const nodes this is performed in the constructor, too. Const
2216 * nodes are extremely time critical because of their frequent use in
2217 * constant string arrays.
2219 static INLINE ir_node *
2220 identify (pset *value_table, ir_node *n)
2224 if (!value_table) return n;
2226 if (get_opt_reassociation()) {
2227 if (is_op_commutative(get_irn_op(n))) {
2228 ir_node *l = get_binop_left(n);
2229 ir_node *r = get_binop_right(n);
2231 /* for commutative operators perform a OP b == b OP a */
2233 set_binop_left(n, r);
2234 set_binop_right(n, l);
2239 o = pset_find (value_table, n, ir_node_hash (n));
2248 * During construction we set the op_pin_state_pinned flag in the graph right when the
2249 * optimization is performed. The flag turning on procedure global cse could
2250 * be changed between two allocations. This way we are safe.
2252 static INLINE ir_node *
2253 identify_cons (pset *value_table, ir_node *n) {
2256 n = identify(value_table, n);
2257 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2258 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2263 * Return the canonical node computing the same value as n.
2264 * Looks up the node in a hash table, enters it in the table
2265 * if it isn't there yet.
2268 identify_remember (pset *value_table, ir_node *n)
2272 if (!value_table) return n;
2274 if (get_opt_reassociation()) {
2275 if (is_op_commutative(get_irn_op(n))) {
2276 ir_node *l = get_binop_left(n);
2277 ir_node *r = get_binop_right(n);
2279 /* for commutative operators perform a OP b == b OP a */
2281 set_binop_left(n, r);
2282 set_binop_right(n, l);
2287 /* lookup or insert in hash table with given hash key. */
2288 o = pset_insert (value_table, n, ir_node_hash (n));
2298 add_identities (pset *value_table, ir_node *node) {
2299 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2300 identify_remember (value_table, node);
2304 * garbage in, garbage out. If a node has a dead input, i.e., the
2305 * Bad node is input to the node, return the Bad node.
2307 static INLINE ir_node *
2308 gigo (ir_node *node)
2311 ir_op* op = get_irn_op(node);
2313 /* remove garbage blocks by looking at control flow that leaves the block
2314 and replacing the control flow by Bad. */
2315 if (get_irn_mode(node) == mode_X) {
2316 ir_node *block = get_nodes_block(node);
2317 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2318 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2320 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2321 irn_arity = get_irn_arity(block);
2322 for (i = 0; i < irn_arity; i++) {
2323 if (!is_Bad(get_irn_n(block, i))) break;
2325 if (i == irn_arity) return new_Bad();
2329 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2330 blocks predecessors is dead. */
2331 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2332 irn_arity = get_irn_arity(node);
2334 if (is_Block_dead(get_nodes_block(node)))
2337 for (i = 0; i < irn_arity; i++) {
2338 if (is_Bad(get_irn_n(node, i))) {
2344 /* With this code we violate the agreement that local_optimize
2345 only leaves Bads in Block, Phi and Tuple nodes. */
2346 /* If Block has only Bads as predecessors it's garbage. */
2347 /* If Phi has only Bads as predecessors it's garbage. */
2348 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2349 irn_arity = get_irn_arity(node);
2350 for (i = 0; i < irn_arity; i++) {
2351 if (!is_Bad(get_irn_n(node, i))) break;
2353 if (i == irn_arity) node = new_Bad();
2361 * These optimizations deallocate nodes from the obstack.
2362 * It can only be called if it is guaranteed that no other nodes
2363 * reference this one, i.e., right after construction of a node.
2366 optimize_node (ir_node *n)
2370 opcode iro = get_irn_opcode(n);
2372 type *old_tp = get_irn_type(n);
2374 int i, arity = get_irn_arity(n);
2375 for (i = 0; i < arity && !old_tp; ++i)
2376 old_tp = get_irn_type(get_irn_n(n, i));
2379 /* Always optimize Phi nodes: part of the construction. */
2380 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2382 /* constant expression evaluation / constant folding */
2383 if (get_opt_constant_folding()) {
2384 /* constants can not be evaluated */
2385 if (iro != iro_Const) {
2386 /* try to evaluate */
2387 tv = computed_value(n);
2388 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2392 * we MUST copy the node here temporary, because it's still needed
2393 * for DBG_OPT_CSTEVAL
2395 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2396 oldn = alloca(node_size);
2398 memcpy(oldn, n, node_size);
2399 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2401 /* ARG, copy the in array, we need it for statistics */
2402 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2405 edges_node_deleted(n, current_ir_graph);
2407 /* evaluation was successful -- replace the node. */
2408 obstack_free (current_ir_graph->obst, n);
2409 nw = new_Const (get_tarval_mode (tv), tv);
2411 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2412 set_Const_type(nw, old_tp);
2413 DBG_OPT_CSTEVAL(oldn, nw);
2419 /* remove unnecessary nodes */
2420 if (get_opt_constant_folding() ||
2421 (iro == iro_Phi) || /* always optimize these nodes. */
2423 (iro == iro_Proj) ||
2424 (iro == iro_Block) ) /* Flags tested local. */
2425 n = equivalent_node (n);
2427 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2429 /** common subexpression elimination **/
2430 /* Checks whether n is already available. */
2431 /* The block input is used to distinguish different subexpressions. Right
2432 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2433 subexpressions within a block. */
2435 n = identify_cons (current_ir_graph->value_table, n);
2438 edges_node_deleted(oldn, current_ir_graph);
2440 /* We found an existing, better node, so we can deallocate the old node. */
2441 obstack_free (current_ir_graph->obst, oldn);
2446 /* Some more constant expression evaluation that does not allow to
2448 iro = get_irn_opcode(n);
2449 if (get_opt_constant_folding() ||
2450 (iro == iro_Cond) ||
2451 (iro == iro_Proj)) /* Flags tested local. */
2452 n = transform_node (n);
2454 /* Remove nodes with dead (Bad) input.
2455 Run always for transformation induced Bads. */
2458 /* Now we have a legal, useful node. Enter it in hash table for cse */
2459 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2460 n = identify_remember (current_ir_graph->value_table, n);
2468 * These optimizations never deallocate nodes (in place). This can cause dead
2469 * nodes lying on the obstack. Remove these by a dead node elimination,
2470 * i.e., a copying garbage collection.
2473 optimize_in_place_2 (ir_node *n)
2477 opcode iro = get_irn_opcode(n);
2479 type *old_tp = get_irn_type(n);
2481 int i, arity = get_irn_arity(n);
2482 for (i = 0; i < arity && !old_tp; ++i)
2483 old_tp = get_irn_type(get_irn_n(n, i));
2486 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2488 /* if not optimize return n */
2491 /* Here this is possible. Why? */
2495 /* constant expression evaluation / constant folding */
2496 if (get_opt_constant_folding()) {
2497 /* constants can not be evaluated */
2498 if (iro != iro_Const) {
2499 /* try to evaluate */
2500 tv = computed_value(n);
2501 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2502 /* evaluation was successful -- replace the node. */
2503 n = new_Const (get_tarval_mode (tv), tv);
2505 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2506 set_Const_type(n, old_tp);
2508 DBG_OPT_CSTEVAL(oldn, n);
2514 /* remove unnecessary nodes */
2515 if (get_opt_constant_folding() ||
2516 (iro == iro_Phi) || /* always optimize these nodes. */
2517 (iro == iro_Id) || /* ... */
2518 (iro == iro_Proj) || /* ... */
2519 (iro == iro_Block) ) /* Flags tested local. */
2520 n = equivalent_node (n);
2522 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2524 /** common subexpression elimination **/
2525 /* Checks whether n is already available. */
2526 /* The block input is used to distinguish different subexpressions. Right
2527 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2528 subexpressions within a block. */
2529 if (get_opt_cse()) {
2530 n = identify (current_ir_graph->value_table, n);
2533 /* Some more constant expression evaluation. */
2534 iro = get_irn_opcode(n);
2535 if (get_opt_constant_folding() ||
2536 (iro == iro_Cond) ||
2537 (iro == iro_Proj)) /* Flags tested local. */
2538 n = transform_node (n);
2540 /* Remove nodes with dead (Bad) input.
2541 Run always for transformation induced Bads. */
2544 /* Now we can verify the node, as it has no dead inputs any more. */
2547 /* Now we have a legal, useful node. Enter it in hash table for cse.
2548 Blocks should be unique anyways. (Except the successor of start:
2549 is cse with the start block!) */
2550 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2551 n = identify_remember (current_ir_graph->value_table, n);
2557 * Wrapper for external use, set proper status bits after optimization.
2560 optimize_in_place (ir_node *n)
2562 /* Handle graph state */
2563 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2565 if (get_opt_global_cse())
2566 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2567 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2568 set_irg_outs_inconsistent(current_ir_graph);
2570 /* Maybe we could also test whether optimizing the node can
2571 change the control graph. */
2572 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2573 set_irg_dom_inconsistent(current_ir_graph);
2574 return optimize_in_place_2 (n);
2578 * set the default ir op operations
2580 ir_op *firm_set_default_operations(ir_op *op)
2582 op = firm_set_default_computed_value(op);
2583 op = firm_set_default_equivalent_node(op);
2584 op = firm_set_default_transform_node(op);
2585 op = firm_set_default_node_cmp_attr(op);
2586 op = firm_set_default_get_type(op);