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 == Eq, mode_b) */
445 return new_tarval_from_long (proj_nr & 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 pnc_number flags = tarval_cmp (taa, tab);
453 if (flags != 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 & 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 *sel = get_Mux_sel(n);
1087 tarval *ts = value_of(sel);
1089 if (ts == get_tarval_b_true())
1090 return get_Mux_true(n);
1091 else if (ts == get_tarval_b_false())
1092 return get_Mux_false(n);
1093 else if(get_Mux_false(n) == get_Mux_true(n))
1094 return get_Mux_true(n);
1100 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1101 * perform no actual computation, as, e.g., the Id nodes. It does not create
1102 * new nodes. It is therefore safe to free n if the node returned is not n.
1103 * If a node returns a Tuple we can not just skip it. If the size of the
1104 * in array fits, we transform n into a tuple (e.g., Div).
1107 equivalent_node(ir_node *n)
1109 if (n->op->equivalent_node)
1110 return n->op->equivalent_node(n);
1115 * set the default equivalent node operation
1117 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1121 op->equivalent_node = equivalent_node_##a; \
1149 op->equivalent_node = NULL;
1157 * Do node specific optimizations of nodes predecessors.
1160 optimize_preds(ir_node *n) {
1161 ir_node *a = NULL, *b = NULL;
1163 /* get the operands we will work on for simple cases. */
1165 a = get_binop_left(n);
1166 b = get_binop_right(n);
1167 } else if (is_unop(n)) {
1171 switch (get_irn_opcode(n)) {
1174 /* We don't want Cast as input to Cmp. */
1175 if (get_irn_op(a) == op_Cast) {
1179 if (get_irn_op(b) == op_Cast) {
1181 set_Cmp_right(n, b);
1190 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1191 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1193 static ir_node *transform_node_AddSub(ir_node *n)
1195 ir_mode *mode = get_irn_mode(n);
1197 if (mode_is_reference(mode)) {
1198 ir_node *left = get_binop_left(n);
1199 ir_node *right = get_binop_right(n);
1200 int ref_bits = get_mode_size_bits(mode);
1202 if (get_irn_op(left) == op_Conv) {
1203 ir_mode *mode = get_irn_mode(left);
1204 int bits = get_mode_size_bits(mode);
1206 if (ref_bits == bits &&
1207 mode_is_int(mode) &&
1208 get_mode_arithmetic(mode) == irma_twos_complement) {
1209 ir_node *pre = get_Conv_op(left);
1210 ir_mode *pre_mode = get_irn_mode(pre);
1212 if (mode_is_int(pre_mode) &&
1213 get_mode_size_bits(pre_mode) == bits &&
1214 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1215 /* ok, this conv just changes to sign, moreover the calculation
1216 * is done with same number of bits as our address mode, so
1217 * we can ignore the conv as address calculation can be viewed
1218 * as either signed or unsigned
1220 set_binop_left(n, pre);
1225 if (get_irn_op(right) == op_Conv) {
1226 ir_mode *mode = get_irn_mode(right);
1227 int bits = get_mode_size_bits(mode);
1229 if (ref_bits == bits &&
1230 mode_is_int(mode) &&
1231 get_mode_arithmetic(mode) == irma_twos_complement) {
1232 ir_node *pre = get_Conv_op(right);
1233 ir_mode *pre_mode = get_irn_mode(pre);
1235 if (mode_is_int(pre_mode) &&
1236 get_mode_size_bits(pre_mode) == bits &&
1237 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1238 /* ok, this conv just changes to sign, moreover the calculation
1239 * is done with same number of bits as our address mode, so
1240 * we can ignore the conv as address calculation can be viewed
1241 * as either signed or unsigned
1243 set_binop_right(n, pre);
1251 #define transform_node_Add transform_node_AddSub
1254 * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
1256 static ir_node *transform_node_Sub(ir_node *n)
1260 n = transform_node_AddSub(n);
1262 mode = get_irn_mode(n);
1263 if (mode_is_num(mode)) {
1264 if (classify_Const(get_Sub_left(n)) == CNST_NULL) {
1266 get_irn_dbg_info(n),
1277 /** Do architecture dependend optimizations on Mul nodes */
1278 static ir_node *transform_node_Mul(ir_node *n) {
1279 return arch_dep_replace_mul_with_shifts(n);
1282 static ir_node *transform_node_Div(ir_node *n)
1284 tarval *tv = value_of(n);
1287 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1289 if (tv != tarval_bad)
1290 value = new_Const(get_tarval_mode(tv), tv);
1291 else /* Try architecture dependand optimization */
1292 value = arch_dep_replace_div_by_const(n);
1295 /* Turn Div into a tuple (mem, bad, value) */
1296 ir_node *mem = get_Div_mem(n);
1298 turn_into_tuple(n, 3);
1299 set_Tuple_pred(n, pn_Div_M, mem);
1300 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1301 set_Tuple_pred(n, pn_Div_res, value);
1306 static ir_node *transform_node_Mod(ir_node *n)
1308 tarval *tv = value_of(n);
1311 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1313 if (tv != tarval_bad)
1314 value = new_Const(get_tarval_mode(tv), tv);
1315 else /* Try architecture dependand optimization */
1316 value = arch_dep_replace_mod_by_const(n);
1319 /* Turn Mod into a tuple (mem, bad, value) */
1320 ir_node *mem = get_Mod_mem(n);
1322 turn_into_tuple(n, 3);
1323 set_Tuple_pred(n, pn_Mod_M, mem);
1324 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1325 set_Tuple_pred(n, pn_Mod_res, value);
1330 static ir_node *transform_node_DivMod(ir_node *n)
1334 ir_node *a = get_DivMod_left(n);
1335 ir_node *b = get_DivMod_right(n);
1336 ir_mode *mode = get_irn_mode(a);
1337 tarval *ta = value_of(a);
1338 tarval *tb = value_of(b);
1340 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1343 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1345 if (tb != tarval_bad) {
1346 if (tb == get_mode_one(get_tarval_mode(tb))) {
1347 b = new_Const (mode, get_mode_null(mode));
1349 } else if (ta != tarval_bad) {
1350 tarval *resa, *resb;
1351 resa = tarval_div (ta, tb);
1352 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1353 Jmp for X result!? */
1354 resb = tarval_mod (ta, tb);
1355 if (resb == tarval_bad) return n; /* Causes exception! */
1356 a = new_Const (mode, resa);
1357 b = new_Const (mode, resb);
1360 else { /* Try architecture dependand optimization */
1361 arch_dep_replace_divmod_by_const(&a, &b, n);
1362 evaluated = a != NULL;
1364 } else if (ta == get_mode_null(mode)) {
1365 /* 0 / non-Const = 0 */
1370 if (evaluated) { /* replace by tuple */
1371 ir_node *mem = get_DivMod_mem(n);
1372 turn_into_tuple(n, 4);
1373 set_Tuple_pred(n, pn_DivMod_M, mem);
1374 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1375 set_Tuple_pred(n, pn_DivMod_res_div, a);
1376 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1377 assert(get_nodes_block(n));
1383 static ir_node *transform_node_Cond(ir_node *n)
1385 /* Replace the Cond by a Jmp if it branches on a constant
1388 ir_node *a = get_Cond_selector(n);
1389 tarval *ta = value_of(a);
1391 if ((ta != tarval_bad) &&
1392 (get_irn_mode(a) == mode_b) &&
1393 (get_opt_unreachable_code())) {
1394 /* It's a boolean Cond, branching on a boolean constant.
1395 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1396 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1397 turn_into_tuple(n, 2);
1398 if (ta == tarval_b_true) {
1399 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1400 set_Tuple_pred(n, pn_Cond_true, jmp);
1402 set_Tuple_pred(n, pn_Cond_false, jmp);
1403 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1405 /* We might generate an endless loop, so keep it alive. */
1406 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1407 } else if ((ta != tarval_bad) &&
1408 (get_irn_mode(a) == mode_Iu) &&
1409 (get_Cond_kind(n) == dense) &&
1410 (get_opt_unreachable_code())) {
1411 /* I don't want to allow Tuples smaller than the biggest Proj.
1412 Also this tuple might get really big...
1413 I generate the Jmp here, and remember it in link. Link is used
1414 when optimizing Proj. */
1415 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1416 /* We might generate an endless loop, so keep it alive. */
1417 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1418 } else if ((get_irn_op(a) == op_Eor)
1419 && (get_irn_mode(a) == mode_b)
1420 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1421 /* The Eor is a negate. Generate a new Cond without the negate,
1422 simulate the negate by exchanging the results. */
1423 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1425 } else if ((get_irn_op(a) == op_Not)
1426 && (get_irn_mode(a) == mode_b)) {
1427 /* A Not before the Cond. Generate a new Cond without the Not,
1428 simulate the Not by exchanging the results. */
1429 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1438 static ir_node *transform_node_Eor(ir_node *n)
1440 ir_node *a = get_Eor_left(n);
1441 ir_node *b = get_Eor_right(n);
1443 if ((get_irn_mode(n) == mode_b)
1444 && (get_irn_op(a) == op_Proj)
1445 && (get_irn_mode(a) == mode_b)
1446 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1447 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1448 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1449 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1450 mode_b, get_negated_pnc(get_Proj_proj(a)));
1451 else if ((get_irn_mode(n) == mode_b)
1452 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1453 /* The Eor is a Not. Replace it by a Not. */
1454 /* ????!!!Extend to bitfield 1111111. */
1455 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1461 * Transform a boolean Not.
1463 static ir_node *transform_node_Not(ir_node *n)
1465 ir_node *a = get_Not_op(n);
1467 if ( (get_irn_mode(n) == mode_b)
1468 && (get_irn_op(a) == op_Proj)
1469 && (get_irn_mode(a) == mode_b)
1470 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1471 /* We negate a Cmp. The Cmp has the negated result anyways! */
1472 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1473 mode_b, get_negated_pnc(get_Proj_proj(a)));
1479 * Transform a Cast of a Const into a new Const
1481 static ir_node *transform_node_Cast(ir_node *n) {
1482 ir_node *pred = get_Cast_op(n);
1483 type *tp = get_irn_type(pred);
1485 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1486 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1487 get_Const_tarval(pred), tp);
1488 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1489 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1490 get_SymConst_kind(pred), tp);
1496 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1497 * done here instead of equivalent node because it creates new
1499 * Removes the exceptions and routes the memory to the NoMem node.
1501 * Further, it optimizes jump tables by removing all impossible cases.
1503 static ir_node *transform_node_Proj(ir_node *proj)
1505 ir_node *n = get_Proj_pred(proj);
1510 switch (get_irn_opcode(n)) {
1512 b = get_Div_right(n);
1515 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1516 proj_nr = get_Proj_proj(proj);
1518 /* this node may float */
1519 set_irn_pinned(n, op_pin_state_floats);
1521 if (proj_nr == pn_Div_X_except) {
1522 /* we found an exception handler, remove it */
1525 /* the memory Proj can be removed */
1526 ir_node *res = get_Div_mem(n);
1527 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1528 if (proj_nr == pn_Div_M)
1534 b = get_Mod_right(n);
1537 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1538 proj_nr = get_Proj_proj(proj);
1540 /* this node may float */
1541 set_irn_pinned(n, op_pin_state_floats);
1543 if (proj_nr == pn_Mod_X_except) {
1544 /* we found an exception handler, remove it */
1547 /* the memory Proj can be removed */
1548 ir_node *res = get_Mod_mem(n);
1549 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1550 if (proj_nr == pn_Mod_M)
1556 b = get_DivMod_right(n);
1559 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1560 proj_nr = get_Proj_proj(proj);
1562 /* this node may float */
1563 set_irn_pinned(n, op_pin_state_floats);
1565 if (proj_nr == pn_DivMod_X_except) {
1566 /* we found an exception handler, remove it */
1570 /* the memory Proj can be removed */
1571 ir_node *res = get_DivMod_mem(n);
1572 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1573 if (proj_nr == pn_DivMod_M)
1580 if (get_opt_unreachable_code()) {
1581 b = get_Cond_selector(n);
1584 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1585 /* we have a constant switch */
1586 long num = get_Proj_proj(proj);
1588 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1589 if (get_tarval_long(tb) == num) {
1590 /* Do NOT create a jump here, or we will have 2 control flow ops
1591 * in a block. This case is optimized away in optimize_cf(). */
1602 /* should not happen, but if it does will be optimized away */
1610 /* we have added a Tuple, optimize it for the current Proj away */
1611 return equivalent_node_Proj(proj);
1615 * returns the operands of a commutative bin-op, if one operand is
1616 * a const, it is returned as the second one.
1618 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1620 ir_node *op_a = get_binop_left(binop);
1621 ir_node *op_b = get_binop_right(binop);
1623 assert(is_op_commutative(get_irn_op(binop)));
1625 if (get_irn_op(op_a) == op_Const) {
1636 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1637 * Such pattern may arise in bitfield stores.
1639 * value c4 value c4 & c2
1640 * AND c3 AND c1 | c3
1645 static ir_node *transform_node_Or_bf_store(ir_node *or)
1649 ir_node *and_l, *c3;
1650 ir_node *value, *c4;
1651 ir_node *new_and, *new_const, *block;
1652 ir_mode *mode = get_irn_mode(or);
1654 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1656 get_comm_Binop_Ops(or, &and, &c1);
1657 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1660 get_comm_Binop_Ops(and, &or_l, &c2);
1661 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1664 get_comm_Binop_Ops(or_l, &and_l, &c3);
1665 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1668 get_comm_Binop_Ops(and_l, &value, &c4);
1669 if (get_irn_op(c4) != op_Const)
1672 /* ok, found the pattern, check for conditions */
1673 assert(mode == get_irn_mode(and));
1674 assert(mode == get_irn_mode(or_l));
1675 assert(mode == get_irn_mode(and_l));
1677 tv1 = get_Const_tarval(c1);
1678 tv2 = get_Const_tarval(c2);
1679 tv3 = get_Const_tarval(c3);
1680 tv4 = get_Const_tarval(c4);
1682 tv = tarval_or(tv4, tv2);
1683 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1684 /* have at least one 0 at the same bit position */
1688 n_tv4 = tarval_not(tv4);
1689 if (tv3 != tarval_and(tv3, n_tv4)) {
1690 /* bit in the or_mask is outside the and_mask */
1694 n_tv2 = tarval_not(tv2);
1695 if (tv1 != tarval_and(tv1, n_tv2)) {
1696 /* bit in the or_mask is outside the and_mask */
1700 /* ok, all conditions met */
1701 block = get_nodes_block(or);
1703 new_and = new_r_And(current_ir_graph, block,
1704 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1706 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1708 set_Or_left(or, new_and);
1709 set_Or_right(or, new_const);
1711 /* check for more */
1712 return transform_node_Or_bf_store(or);
1716 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
1718 static ir_node *transform_node_Or_Rot(ir_node *or)
1720 ir_mode *mode = get_irn_mode(or);
1721 ir_node *shl, *shr, *block;
1722 ir_node *irn, *x, *c1, *c2, *v, *sub;
1725 if (! mode_is_int(mode))
1728 shl = get_binop_left(or);
1729 shr = get_binop_right(or);
1731 if (get_irn_op(shl) == op_Shr) {
1732 if (get_irn_op(shr) != op_Shl)
1739 else if (get_irn_op(shl) != op_Shl)
1741 else if (get_irn_op(shr) != op_Shr)
1744 x = get_Shl_left(shl);
1745 if (x != get_Shr_left(shr))
1748 c1 = get_Shl_right(shl);
1749 c2 = get_Shr_right(shr);
1750 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
1751 tv1 = get_Const_tarval(c1);
1752 if (! tarval_is_long(tv1))
1755 tv2 = get_Const_tarval(c2);
1756 if (! tarval_is_long(tv2))
1759 if (get_tarval_long(tv1) + get_tarval_long(tv2)
1760 != get_mode_size_bits(mode))
1763 /* yet, condition met */
1764 block = get_nodes_block(or);
1766 return new_r_Rot(current_ir_graph, block, x, c1, mode);
1768 else if (get_irn_op(c1) == op_Sub) {
1772 if (get_Sub_right(sub) != v)
1775 c1 = get_Sub_left(sub);
1776 if (get_irn_op(c1) != op_Const)
1779 tv1 = get_Const_tarval(c1);
1780 if (! tarval_is_long(tv1))
1783 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1786 /* yet, condition met */
1787 block = get_nodes_block(or);
1789 /* a Rot right is not supported, so use a rot left */
1790 return new_r_Rot(current_ir_graph, block, x, sub, mode);
1792 else if (get_irn_op(c2) == op_Sub) {
1796 c1 = get_Sub_left(sub);
1797 if (get_irn_op(c1) != op_Const)
1800 tv1 = get_Const_tarval(c1);
1801 if (! tarval_is_long(tv1))
1804 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1807 /* yet, condition met */
1808 block = get_nodes_block(or);
1811 return new_r_Rot(current_ir_graph, block, x, v, mode);
1820 static ir_node *transform_node_Or(ir_node *or)
1822 or = transform_node_Or_bf_store(or);
1823 or = transform_node_Or_Rot(or);
1829 static ir_node *transform_node(ir_node *n);
1832 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1834 static ir_node * transform_node_shift(ir_node *n)
1837 tarval *tv1, *tv2, *res;
1839 int modulo_shf, flag;
1841 left = get_binop_left(n);
1843 /* different operations */
1844 if (get_irn_op(left) != get_irn_op(n))
1847 tv1 = value_of(get_binop_right(n));
1848 if (tv1 == tarval_bad)
1851 tv2 = value_of(get_binop_right(left));
1852 if (tv2 == tarval_bad)
1855 res = tarval_add(tv1, tv2);
1857 /* beware: a simple replacement works only, if res < modulo shift */
1858 mode = get_irn_mode(n);
1862 modulo_shf = get_mode_modulo_shift(mode);
1863 if (modulo_shf > 0) {
1864 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1866 if (tarval_cmp(res, modulo) & Lt)
1873 /* ok, we can replace it */
1874 ir_node *in[2], *irn, *block = get_nodes_block(n);
1876 in[0] = get_binop_left(left);
1877 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1879 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1881 return transform_node(irn);
1886 static ir_node * transform_node_End(ir_node *n) {
1887 int i, n_keepalives = get_End_n_keepalives(n);
1889 /* Remove dead blocks in keepalive list.
1890 We do not generate a new End node. */
1891 for (i = 0; i < n_keepalives; ++i) {
1892 ir_node *ka = get_End_keepalive(n, i);
1893 if (is_Block(ka) && is_Block_dead(ka))
1894 set_End_keepalive(n, i, new_Bad());
1901 * Tries several [inplace] [optimizing] transformations and returns an
1902 * equivalent node. The difference to equivalent_node() is that these
1903 * transformations _do_ generate new nodes, and thus the old node must
1904 * not be freed even if the equivalent node isn't the old one.
1906 static ir_node *transform_node(ir_node *n)
1908 if (n->op->transform_node)
1909 n = n->op->transform_node(n);
1914 * set the default transform node operation
1916 static ir_op *firm_set_default_transform_node(ir_op *op)
1920 op->transform_node = transform_node_##a; \
1940 op->transform_node = transform_node_shift;
1943 op->transform_node = NULL;
1951 /* **************** Common Subexpression Elimination **************** */
1953 /** The size of the hash table used, should estimate the number of nodes
1955 #define N_IR_NODES 512
1957 /** Compares the attributes of two Const nodes. */
1958 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1960 return (get_Const_tarval(a) != get_Const_tarval(b))
1961 || (get_Const_type(a) != get_Const_type(b));
1964 /** Compares the attributes of two Proj nodes. */
1965 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1967 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1970 /** Compares the attributes of two Filter nodes. */
1971 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1973 return get_Filter_proj(a) != get_Filter_proj(b);
1976 /** Compares the attributes of two Alloc nodes. */
1977 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1979 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1980 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1983 /** Compares the attributes of two Free nodes. */
1984 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1986 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
1987 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
1990 /** Compares the attributes of two SymConst nodes. */
1991 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1993 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1994 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1995 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1998 /** Compares the attributes of two Call nodes. */
1999 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2001 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2004 /** Compares the attributes of two Sel nodes. */
2005 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2007 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2008 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2009 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2010 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2011 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2014 /** Compares the attributes of two Phi nodes. */
2015 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2017 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2020 /** Compares the attributes of two Cast nodes. */
2021 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2023 return get_Cast_type(a) != get_Cast_type(b);
2026 /** Compares the attributes of two Load nodes. */
2027 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2029 if (get_Load_volatility(a) == volatility_is_volatile ||
2030 get_Load_volatility(b) == volatility_is_volatile)
2031 /* NEVER do CSE on volatile Loads */
2034 return get_Load_mode(a) != get_Load_mode(b);
2037 /** Compares the attributes of two Store nodes. */
2038 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2040 /* NEVER do CSE on volatile Stores */
2041 return (get_Store_volatility(a) == volatility_is_volatile ||
2042 get_Store_volatility(b) == volatility_is_volatile);
2046 * set the default node attribute compare operation
2048 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2052 op->node_cmp_attr = node_cmp_attr_##a; \
2069 op->node_cmp_attr = NULL;
2077 * Compare function for two nodes in the hash table. Gets two
2078 * nodes as parameters. Returns 0 if the nodes are a cse.
2081 vt_cmp (const void *elt, const void *key)
2089 if (a == b) return 0;
2091 if ((get_irn_op(a) != get_irn_op(b)) ||
2092 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2094 /* compare if a's in and b's in are of equal length */
2095 irn_arity_a = get_irn_intra_arity (a);
2096 if (irn_arity_a != get_irn_intra_arity(b))
2099 /* for block-local cse and op_pin_state_pinned nodes: */
2100 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2101 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2105 /* compare a->in[0..ins] with b->in[0..ins] */
2106 for (i = 0; i < irn_arity_a; i++)
2107 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2111 * here, we already now that the nodes are identical except their
2114 if (a->op->node_cmp_attr)
2115 return a->op->node_cmp_attr(a, b);
2121 * Calculate a hash value of a node.
2124 ir_node_hash (ir_node *node)
2129 if (node->op == op_Const) {
2130 /* special value for const, as they only differ in their tarval. */
2131 h = HASH_PTR(node->attr.con.tv);
2132 h = 9*h + HASH_PTR(get_irn_mode(node));
2133 } else if (node->op == op_SymConst) {
2134 /* special value for const, as they only differ in their symbol. */
2135 h = HASH_PTR(node->attr.i.sym.type_p);
2136 h = 9*h + HASH_PTR(get_irn_mode(node));
2139 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2140 h = irn_arity = get_irn_intra_arity(node);
2142 /* consider all in nodes... except the block if not a control flow. */
2143 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2144 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2148 h = 9*h + HASH_PTR(get_irn_mode(node));
2150 h = 9*h + HASH_PTR(get_irn_op(node));
2157 new_identities(void) {
2158 return new_pset(vt_cmp, N_IR_NODES);
2162 del_identities(pset *value_table) {
2163 del_pset(value_table);
2167 * Return the canonical node computing the same value as n.
2168 * Looks up the node in a hash table.
2170 * For Const nodes this is performed in the constructor, too. Const
2171 * nodes are extremely time critical because of their frequent use in
2172 * constant string arrays.
2174 static INLINE ir_node *
2175 identify (pset *value_table, ir_node *n)
2179 if (!value_table) return n;
2181 if (get_opt_reassociation()) {
2182 if (is_op_commutative(get_irn_op(n))) {
2183 ir_node *l = get_binop_left(n);
2184 ir_node *r = get_binop_right(n);
2186 /* for commutative operators perform a OP b == b OP a */
2188 set_binop_left(n, r);
2189 set_binop_right(n, l);
2194 o = pset_find (value_table, n, ir_node_hash (n));
2203 * During construction we set the op_pin_state_pinned flag in the graph right when the
2204 * optimization is performed. The flag turning on procedure global cse could
2205 * be changed between two allocations. This way we are safe.
2207 static INLINE ir_node *
2208 identify_cons (pset *value_table, ir_node *n) {
2211 n = identify(value_table, n);
2212 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2213 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2218 * Return the canonical node computing the same value as n.
2219 * Looks up the node in a hash table, enters it in the table
2220 * if it isn't there yet.
2223 identify_remember (pset *value_table, ir_node *n)
2227 if (!value_table) return n;
2229 if (get_opt_reassociation()) {
2230 if (is_op_commutative(get_irn_op(n))) {
2231 ir_node *l = get_binop_left(n);
2232 ir_node *r = get_binop_right(n);
2234 /* for commutative operators perform a OP b == b OP a */
2236 set_binop_left(n, r);
2237 set_binop_right(n, l);
2242 /* lookup or insert in hash table with given hash key. */
2243 o = pset_insert (value_table, n, ir_node_hash (n));
2253 add_identities (pset *value_table, ir_node *node) {
2254 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2255 identify_remember (value_table, node);
2259 * garbage in, garbage out. If a node has a dead input, i.e., the
2260 * Bad node is input to the node, return the Bad node.
2262 static INLINE ir_node *
2263 gigo (ir_node *node)
2266 ir_op* op = get_irn_op(node);
2268 /* remove garbage blocks by looking at control flow that leaves the block
2269 and replacing the control flow by Bad. */
2270 if (get_irn_mode(node) == mode_X) {
2271 ir_node *block = get_nodes_block(node);
2272 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2273 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2275 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2276 irn_arity = get_irn_arity(block);
2277 for (i = 0; i < irn_arity; i++) {
2278 if (!is_Bad(get_irn_n(block, i))) break;
2280 if (i == irn_arity) return new_Bad();
2284 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2285 blocks predecessors is dead. */
2286 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2287 irn_arity = get_irn_arity(node);
2289 if (is_Block_dead(get_nodes_block(node)))
2292 for (i = 0; i < irn_arity; i++) {
2293 if (is_Bad(get_irn_n(node, i))) {
2299 /* With this code we violate the agreement that local_optimize
2300 only leaves Bads in Block, Phi and Tuple nodes. */
2301 /* If Block has only Bads as predecessors it's garbage. */
2302 /* If Phi has only Bads as predecessors it's garbage. */
2303 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2304 irn_arity = get_irn_arity(node);
2305 for (i = 0; i < irn_arity; i++) {
2306 if (!is_Bad(get_irn_n(node, i))) break;
2308 if (i == irn_arity) node = new_Bad();
2316 * These optimizations deallocate nodes from the obstack.
2317 * It can only be called if it is guaranteed that no other nodes
2318 * reference this one, i.e., right after construction of a node.
2321 optimize_node (ir_node *n)
2325 opcode iro = get_irn_opcode(n);
2327 type *old_tp = get_irn_type(n);
2329 int i, arity = get_irn_arity(n);
2330 for (i = 0; i < arity && !old_tp; ++i)
2331 old_tp = get_irn_type(get_irn_n(n, i));
2334 /* Allways optimize Phi nodes: part of the construction. */
2335 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2337 /* constant expression evaluation / constant folding */
2338 if (get_opt_constant_folding()) {
2339 /* constants can not be evaluated */
2340 if (iro != iro_Const) {
2341 /* try to evaluate */
2342 tv = computed_value(n);
2343 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2347 * we MUST copy the node here temporary, because it's still needed
2348 * for DBG_OPT_CSTEVAL
2350 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2351 oldn = alloca(node_size);
2353 memcpy(oldn, n, node_size);
2354 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2356 /* ARG, copy the in array, we need it for statistics */
2357 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2360 edges_node_deleted(n, current_ir_graph);
2362 /* evaluation was successful -- replace the node. */
2363 obstack_free (current_ir_graph->obst, n);
2364 nw = new_Const (get_tarval_mode (tv), tv);
2366 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2367 set_Const_type(nw, old_tp);
2368 DBG_OPT_CSTEVAL(oldn, nw);
2374 /* remove unnecessary nodes */
2375 if (get_opt_constant_folding() ||
2376 (iro == iro_Phi) || /* always optimize these nodes. */
2378 (iro == iro_Proj) ||
2379 (iro == iro_Block) ) /* Flags tested local. */
2380 n = equivalent_node (n);
2382 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2384 /** common subexpression elimination **/
2385 /* Checks whether n is already available. */
2386 /* The block input is used to distinguish different subexpressions. Right
2387 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2388 subexpressions within a block. */
2390 n = identify_cons (current_ir_graph->value_table, n);
2393 edges_node_deleted(oldn, current_ir_graph);
2395 /* We found an existing, better node, so we can deallocate the old node. */
2396 obstack_free (current_ir_graph->obst, oldn);
2401 /* Some more constant expression evaluation that does not allow to
2403 iro = get_irn_opcode(n);
2404 if (get_opt_constant_folding() ||
2405 (iro == iro_Cond) ||
2406 (iro == iro_Proj)) /* Flags tested local. */
2407 n = transform_node (n);
2409 /* Remove nodes with dead (Bad) input.
2410 Run always for transformation induced Bads. */
2413 /* Now we have a legal, useful node. Enter it in hash table for cse */
2414 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2415 n = identify_remember (current_ir_graph->value_table, n);
2423 * These optimizations never deallocate nodes (in place). This can cause dead
2424 * nodes lying on the obstack. Remove these by a dead node elimination,
2425 * i.e., a copying garbage collection.
2428 optimize_in_place_2 (ir_node *n)
2432 opcode iro = get_irn_opcode(n);
2434 type *old_tp = get_irn_type(n);
2436 int i, arity = get_irn_arity(n);
2437 for (i = 0; i < arity && !old_tp; ++i)
2438 old_tp = get_irn_type(get_irn_n(n, i));
2441 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2443 /* if not optimize return n */
2446 /* Here this is possible. Why? */
2450 /* constant expression evaluation / constant folding */
2451 if (get_opt_constant_folding()) {
2452 /* constants can not be evaluated */
2453 if (iro != iro_Const) {
2454 /* try to evaluate */
2455 tv = computed_value(n);
2456 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2457 /* evaluation was successful -- replace the node. */
2458 n = new_Const (get_tarval_mode (tv), tv);
2460 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2461 set_Const_type(n, old_tp);
2463 DBG_OPT_CSTEVAL(oldn, n);
2469 /* remove unnecessary nodes */
2470 if (get_opt_constant_folding() ||
2471 (iro == iro_Phi) || /* always optimize these nodes. */
2472 (iro == iro_Id) || /* ... */
2473 (iro == iro_Proj) || /* ... */
2474 (iro == iro_Block) ) /* Flags tested local. */
2475 n = equivalent_node (n);
2477 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2479 /** common subexpression elimination **/
2480 /* Checks whether n is already available. */
2481 /* The block input is used to distinguish different subexpressions. Right
2482 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2483 subexpressions within a block. */
2484 if (get_opt_cse()) {
2485 n = identify (current_ir_graph->value_table, n);
2488 /* Some more constant expression evaluation. */
2489 iro = get_irn_opcode(n);
2490 if (get_opt_constant_folding() ||
2491 (iro == iro_Cond) ||
2492 (iro == iro_Proj)) /* Flags tested local. */
2493 n = transform_node (n);
2495 /* Remove nodes with dead (Bad) input.
2496 Run always for transformation induced Bads. */
2499 /* Now we can verify the node, as it has no dead inputs any more. */
2502 /* Now we have a legal, useful node. Enter it in hash table for cse.
2503 Blocks should be unique anyways. (Except the successor of start:
2504 is cse with the start block!) */
2505 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2506 n = identify_remember (current_ir_graph->value_table, n);
2512 * Wrapper for external use, set proper status bits after optimization.
2515 optimize_in_place (ir_node *n)
2517 /* Handle graph state */
2518 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2520 if (get_opt_global_cse())
2521 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2522 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2523 set_irg_outs_inconsistent(current_ir_graph);
2525 /* Maybe we could also test whether optimizing the node can
2526 change the control graph. */
2527 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2528 set_irg_dom_inconsistent(current_ir_graph);
2529 return optimize_in_place_2 (n);
2533 * set the default ir op operations
2535 ir_op *firm_set_default_operations(ir_op *op)
2537 op = firm_set_default_computed_value(op);
2538 op = firm_set_default_equivalent_node(op);
2539 op = firm_set_default_transform_node(op);
2540 op = firm_set_default_node_cmp_attr(op);