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
1252 #define transform_node_Sub transform_node_AddSub
1254 /** Do architecture dependend optimizations on Mul nodes */
1255 static ir_node *transform_node_Mul(ir_node *n) {
1256 return arch_dep_replace_mul_with_shifts(n);
1259 static ir_node *transform_node_Div(ir_node *n)
1261 tarval *tv = value_of(n);
1264 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1266 if (tv != tarval_bad)
1267 value = new_Const(get_tarval_mode(tv), tv);
1268 else /* Try architecture dependand optimization */
1269 value = arch_dep_replace_div_by_const(n);
1272 /* Turn Div into a tuple (mem, bad, value) */
1273 ir_node *mem = get_Div_mem(n);
1275 turn_into_tuple(n, 3);
1276 set_Tuple_pred(n, pn_Div_M, mem);
1277 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1278 set_Tuple_pred(n, pn_Div_res, value);
1283 static ir_node *transform_node_Mod(ir_node *n)
1285 tarval *tv = value_of(n);
1288 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1290 if (tv != tarval_bad)
1291 value = new_Const(get_tarval_mode(tv), tv);
1292 else /* Try architecture dependand optimization */
1293 value = arch_dep_replace_mod_by_const(n);
1296 /* Turn Mod into a tuple (mem, bad, value) */
1297 ir_node *mem = get_Mod_mem(n);
1299 turn_into_tuple(n, 3);
1300 set_Tuple_pred(n, pn_Mod_M, mem);
1301 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1302 set_Tuple_pred(n, pn_Mod_res, value);
1307 static ir_node *transform_node_DivMod(ir_node *n)
1311 ir_node *a = get_DivMod_left(n);
1312 ir_node *b = get_DivMod_right(n);
1313 ir_mode *mode = get_irn_mode(a);
1314 tarval *ta = value_of(a);
1315 tarval *tb = value_of(b);
1317 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1320 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1322 if (tb != tarval_bad) {
1323 if (tb == get_mode_one(get_tarval_mode(tb))) {
1324 b = new_Const (mode, get_mode_null(mode));
1326 } else if (ta != tarval_bad) {
1327 tarval *resa, *resb;
1328 resa = tarval_div (ta, tb);
1329 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1330 Jmp for X result!? */
1331 resb = tarval_mod (ta, tb);
1332 if (resb == tarval_bad) return n; /* Causes exception! */
1333 a = new_Const (mode, resa);
1334 b = new_Const (mode, resb);
1337 else { /* Try architecture dependand optimization */
1338 arch_dep_replace_divmod_by_const(&a, &b, n);
1339 evaluated = a != NULL;
1341 } else if (ta == get_mode_null(mode)) {
1342 /* 0 / non-Const = 0 */
1347 if (evaluated) { /* replace by tuple */
1348 ir_node *mem = get_DivMod_mem(n);
1349 turn_into_tuple(n, 4);
1350 set_Tuple_pred(n, pn_DivMod_M, mem);
1351 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1352 set_Tuple_pred(n, pn_DivMod_res_div, a);
1353 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1354 assert(get_nodes_block(n));
1360 static ir_node *transform_node_Cond(ir_node *n)
1362 /* Replace the Cond by a Jmp if it branches on a constant
1365 ir_node *a = get_Cond_selector(n);
1366 tarval *ta = value_of(a);
1368 if ((ta != tarval_bad) &&
1369 (get_irn_mode(a) == mode_b) &&
1370 (get_opt_unreachable_code())) {
1371 /* It's a boolean Cond, branching on a boolean constant.
1372 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1373 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1374 turn_into_tuple(n, 2);
1375 if (ta == tarval_b_true) {
1376 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1377 set_Tuple_pred(n, pn_Cond_true, jmp);
1379 set_Tuple_pred(n, pn_Cond_false, jmp);
1380 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1382 /* We might generate an endless loop, so keep it alive. */
1383 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1384 } else if ((ta != tarval_bad) &&
1385 (get_irn_mode(a) == mode_Iu) &&
1386 (get_Cond_kind(n) == dense) &&
1387 (get_opt_unreachable_code())) {
1388 /* I don't want to allow Tuples smaller than the biggest Proj.
1389 Also this tuple might get really big...
1390 I generate the Jmp here, and remember it in link. Link is used
1391 when optimizing Proj. */
1392 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1393 /* We might generate an endless loop, so keep it alive. */
1394 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1395 } else if ((get_irn_op(a) == op_Eor)
1396 && (get_irn_mode(a) == mode_b)
1397 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1398 /* The Eor is a negate. Generate a new Cond without the negate,
1399 simulate the negate by exchanging the results. */
1400 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1402 } else if ((get_irn_op(a) == op_Not)
1403 && (get_irn_mode(a) == mode_b)) {
1404 /* A Not before the Cond. Generate a new Cond without the Not,
1405 simulate the Not by exchanging the results. */
1406 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1415 static ir_node *transform_node_Eor(ir_node *n)
1417 ir_node *a = get_Eor_left(n);
1418 ir_node *b = get_Eor_right(n);
1420 if ((get_irn_mode(n) == mode_b)
1421 && (get_irn_op(a) == op_Proj)
1422 && (get_irn_mode(a) == mode_b)
1423 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1424 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1425 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1426 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1427 mode_b, get_negated_pnc(get_Proj_proj(a)));
1428 else if ((get_irn_mode(n) == mode_b)
1429 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1430 /* The Eor is a Not. Replace it by a Not. */
1431 /* ????!!!Extend to bitfield 1111111. */
1432 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1438 * Transform a boolean Not.
1440 static ir_node *transform_node_Not(ir_node *n)
1442 ir_node *a = get_Not_op(n);
1444 if ( (get_irn_mode(n) == mode_b)
1445 && (get_irn_op(a) == op_Proj)
1446 && (get_irn_mode(a) == mode_b)
1447 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1448 /* We negate 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)));
1456 * Transform a Cast of a Const into a new Const
1458 static ir_node *transform_node_Cast(ir_node *n) {
1459 ir_node *pred = get_Cast_op(n);
1460 type *tp = get_irn_type(pred);
1462 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1463 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1464 get_Const_tarval(pred), tp);
1465 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1466 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1467 get_SymConst_kind(pred), tp);
1473 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1474 * done here instead of equivalent node because it creates new
1476 * Removes the exceptions and routes the memory to the NoMem node.
1478 * Further, it optimizes jump tables by removing all impossible cases.
1480 static ir_node *transform_node_Proj(ir_node *proj)
1482 ir_node *n = get_Proj_pred(proj);
1487 switch (get_irn_opcode(n)) {
1489 b = get_Div_right(n);
1492 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1493 proj_nr = get_Proj_proj(proj);
1495 /* this node may float */
1496 set_irn_pinned(n, op_pin_state_floats);
1498 if (proj_nr == pn_Div_X_except) {
1499 /* we found an exception handler, remove it */
1502 /* the memory Proj can be removed */
1503 ir_node *res = get_Div_mem(n);
1504 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1505 if (proj_nr == pn_Div_M)
1511 b = get_Mod_right(n);
1514 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1515 proj_nr = get_Proj_proj(proj);
1517 /* this node may float */
1518 set_irn_pinned(n, op_pin_state_floats);
1520 if (proj_nr == pn_Mod_X_except) {
1521 /* we found an exception handler, remove it */
1524 /* the memory Proj can be removed */
1525 ir_node *res = get_Mod_mem(n);
1526 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1527 if (proj_nr == pn_Mod_M)
1533 b = get_DivMod_right(n);
1536 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1537 proj_nr = get_Proj_proj(proj);
1539 /* this node may float */
1540 set_irn_pinned(n, op_pin_state_floats);
1542 if (proj_nr == pn_DivMod_X_except) {
1543 /* we found an exception handler, remove it */
1547 /* the memory Proj can be removed */
1548 ir_node *res = get_DivMod_mem(n);
1549 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1550 if (proj_nr == pn_DivMod_M)
1557 if (get_opt_unreachable_code()) {
1558 b = get_Cond_selector(n);
1561 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1562 /* we have a constant switch */
1563 long num = get_Proj_proj(proj);
1565 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1566 if (get_tarval_long(tb) == num) {
1567 /* Do NOT create a jump here, or we will have 2 control flow ops
1568 * in a block. This case is optimized away in optimize_cf(). */
1579 /* should not happen, but if it does will be optimized away */
1587 /* we have added a Tuple, optimize it for the current Proj away */
1588 return equivalent_node_Proj(proj);
1592 * returns the operands of a commutative bin-op, if one operand is
1593 * a const, it is returned as the second one.
1595 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1597 ir_node *op_a = get_binop_left(binop);
1598 ir_node *op_b = get_binop_right(binop);
1600 assert(is_op_commutative(get_irn_op(binop)));
1602 if (get_irn_op(op_a) == op_Const) {
1613 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1614 * Such pattern may arise in bitfield stores.
1616 * value c4 value c4 & c2
1617 * AND c3 AND c1 | c3
1622 static ir_node *transform_node_Or_bf_store(ir_node *or)
1626 ir_node *and_l, *c3;
1627 ir_node *value, *c4;
1628 ir_node *new_and, *new_const, *block;
1629 ir_mode *mode = get_irn_mode(or);
1631 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1633 get_comm_Binop_Ops(or, &and, &c1);
1634 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1637 get_comm_Binop_Ops(and, &or_l, &c2);
1638 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1641 get_comm_Binop_Ops(or_l, &and_l, &c3);
1642 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1645 get_comm_Binop_Ops(and_l, &value, &c4);
1646 if (get_irn_op(c4) != op_Const)
1649 /* ok, found the pattern, check for conditions */
1650 assert(mode == get_irn_mode(and));
1651 assert(mode == get_irn_mode(or_l));
1652 assert(mode == get_irn_mode(and_l));
1654 tv1 = get_Const_tarval(c1);
1655 tv2 = get_Const_tarval(c2);
1656 tv3 = get_Const_tarval(c3);
1657 tv4 = get_Const_tarval(c4);
1659 tv = tarval_or(tv4, tv2);
1660 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1661 /* have at least one 0 at the same bit position */
1665 n_tv4 = tarval_not(tv4);
1666 if (tv3 != tarval_and(tv3, n_tv4)) {
1667 /* bit in the or_mask is outside the and_mask */
1671 n_tv2 = tarval_not(tv2);
1672 if (tv1 != tarval_and(tv1, n_tv2)) {
1673 /* bit in the or_mask is outside the and_mask */
1677 /* ok, all conditions met */
1678 block = get_nodes_block(or);
1680 new_and = new_r_And(current_ir_graph, block,
1681 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1683 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1685 set_Or_left(or, new_and);
1686 set_Or_right(or, new_const);
1688 /* check for more */
1689 return transform_node_Or_bf_store(or);
1693 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
1695 static ir_node *transform_node_Or_Rot(ir_node *or)
1697 ir_mode *mode = get_irn_mode(or);
1698 ir_node *shl, *shr, *block;
1699 ir_node *irn, *x, *c1, *c2, *v, *sub;
1702 if (! mode_is_int(mode))
1705 shl = get_binop_left(or);
1706 shr = get_binop_right(or);
1708 if (get_irn_op(shl) == op_Shr) {
1709 if (get_irn_op(shr) != op_Shl)
1716 else if (get_irn_op(shl) != op_Shl)
1718 else if (get_irn_op(shr) != op_Shr)
1721 x = get_Shl_left(shl);
1722 if (x != get_Shr_left(shr))
1725 c1 = get_Shl_right(shl);
1726 c2 = get_Shr_right(shr);
1727 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
1728 tv1 = get_Const_tarval(c1);
1729 if (! tarval_is_long(tv1))
1732 tv2 = get_Const_tarval(c2);
1733 if (! tarval_is_long(tv2))
1736 if (get_tarval_long(tv1) + get_tarval_long(tv2)
1737 != get_mode_size_bits(mode))
1740 /* yet, condition met */
1741 block = get_nodes_block(or);
1743 return new_r_Rot(current_ir_graph, block, x, c1, mode);
1745 else if (get_irn_op(c1) == op_Sub) {
1749 if (get_Sub_right(sub) != v)
1752 c1 = get_Sub_left(sub);
1753 if (get_irn_op(c1) != op_Const)
1756 tv1 = get_Const_tarval(c1);
1757 if (! tarval_is_long(tv1))
1760 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1763 /* yet, condition met */
1764 block = get_nodes_block(or);
1766 /* a Rot right is not supported, so use a rot left */
1767 return new_r_Rot(current_ir_graph, block, x, sub, mode);
1769 else if (get_irn_op(c2) == op_Sub) {
1773 c1 = get_Sub_left(sub);
1774 if (get_irn_op(c1) != op_Const)
1777 tv1 = get_Const_tarval(c1);
1778 if (! tarval_is_long(tv1))
1781 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1784 /* yet, condition met */
1785 block = get_nodes_block(or);
1788 return new_r_Rot(current_ir_graph, block, x, v, mode);
1797 static ir_node *transform_node_Or(ir_node *or)
1799 or = transform_node_Or_bf_store(or);
1800 or = transform_node_Or_Rot(or);
1806 static ir_node *transform_node(ir_node *n);
1809 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1811 static ir_node * transform_node_shift(ir_node *n)
1814 tarval *tv1, *tv2, *res;
1816 int modulo_shf, flag;
1818 left = get_binop_left(n);
1820 /* different operations */
1821 if (get_irn_op(left) != get_irn_op(n))
1824 tv1 = value_of(get_binop_right(n));
1825 if (tv1 == tarval_bad)
1828 tv2 = value_of(get_binop_right(left));
1829 if (tv2 == tarval_bad)
1832 res = tarval_add(tv1, tv2);
1834 /* beware: a simple replacement works only, if res < modulo shift */
1835 mode = get_irn_mode(n);
1839 modulo_shf = get_mode_modulo_shift(mode);
1840 if (modulo_shf > 0) {
1841 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1843 if (tarval_cmp(res, modulo) & Lt)
1850 /* ok, we can replace it */
1851 ir_node *in[2], *irn, *block = get_nodes_block(n);
1853 in[0] = get_binop_left(left);
1854 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1856 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1858 return transform_node(irn);
1863 static ir_node * transform_node_End(ir_node *n) {
1864 int i, n_keepalives = get_End_n_keepalives(n);
1866 /* Remove dead blocks in keepalive list.
1867 We do not generate a new End node. */
1868 for (i = 0; i < n_keepalives; ++i) {
1869 ir_node *ka = get_End_keepalive(n, i);
1870 if (is_Block(ka) && is_Block_dead(ka))
1871 set_End_keepalive(n, i, new_Bad());
1878 * Tries several [inplace] [optimizing] transformations and returns an
1879 * equivalent node. The difference to equivalent_node() is that these
1880 * transformations _do_ generate new nodes, and thus the old node must
1881 * not be freed even if the equivalent node isn't the old one.
1883 static ir_node *transform_node(ir_node *n)
1885 if (n->op->transform_node)
1886 n = n->op->transform_node(n);
1891 * set the default transform node operation
1893 static ir_op *firm_set_default_transform_node(ir_op *op)
1897 op->transform_node = transform_node_##a; \
1917 op->transform_node = transform_node_shift;
1920 op->transform_node = NULL;
1928 /* **************** Common Subexpression Elimination **************** */
1930 /** The size of the hash table used, should estimate the number of nodes
1932 #define N_IR_NODES 512
1934 /** Compares the attributes of two Const nodes. */
1935 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1937 return (get_Const_tarval(a) != get_Const_tarval(b))
1938 || (get_Const_type(a) != get_Const_type(b));
1941 /** Compares the attributes of two Proj nodes. */
1942 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1944 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1947 /** Compares the attributes of two Filter nodes. */
1948 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1950 return get_Filter_proj(a) != get_Filter_proj(b);
1953 /** Compares the attributes of two Alloc nodes. */
1954 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1956 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1957 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1960 /** Compares the attributes of two Free nodes. */
1961 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1963 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
1964 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
1967 /** Compares the attributes of two SymConst nodes. */
1968 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1970 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1971 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1972 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1975 /** Compares the attributes of two Call nodes. */
1976 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1978 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1981 /** Compares the attributes of two Sel nodes. */
1982 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1984 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1985 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1986 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1987 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1988 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1991 /** Compares the attributes of two Phi nodes. */
1992 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1994 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1997 /** Compares the attributes of two Cast nodes. */
1998 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2000 return get_Cast_type(a) != get_Cast_type(b);
2003 /** Compares the attributes of two Load nodes. */
2004 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2006 if (get_Load_volatility(a) == volatility_is_volatile ||
2007 get_Load_volatility(b) == volatility_is_volatile)
2008 /* NEVER do CSE on volatile Loads */
2011 return get_Load_mode(a) != get_Load_mode(b);
2014 /** Compares the attributes of two Store nodes. */
2015 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2017 /* NEVER do CSE on volatile Stores */
2018 return (get_Store_volatility(a) == volatility_is_volatile ||
2019 get_Store_volatility(b) == volatility_is_volatile);
2023 * set the default node attribute compare operation
2025 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2029 op->node_cmp_attr = node_cmp_attr_##a; \
2046 op->node_cmp_attr = NULL;
2054 * Compare function for two nodes in the hash table. Gets two
2055 * nodes as parameters. Returns 0 if the nodes are a cse.
2058 vt_cmp (const void *elt, const void *key)
2066 if (a == b) return 0;
2068 if ((get_irn_op(a) != get_irn_op(b)) ||
2069 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2071 /* compare if a's in and b's in are of equal length */
2072 irn_arity_a = get_irn_intra_arity (a);
2073 if (irn_arity_a != get_irn_intra_arity(b))
2076 /* for block-local cse and op_pin_state_pinned nodes: */
2077 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2078 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2082 /* compare a->in[0..ins] with b->in[0..ins] */
2083 for (i = 0; i < irn_arity_a; i++)
2084 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2088 * here, we already now that the nodes are identical except their
2091 if (a->op->node_cmp_attr)
2092 return a->op->node_cmp_attr(a, b);
2098 * Calculate a hash value of a node.
2101 ir_node_hash (ir_node *node)
2106 if (node->op == op_Const) {
2107 /* special value for const, as they only differ in their tarval. */
2108 h = HASH_PTR(node->attr.con.tv);
2109 h = 9*h + HASH_PTR(get_irn_mode(node));
2110 } else if (node->op == op_SymConst) {
2111 /* special value for const, as they only differ in their symbol. */
2112 h = HASH_PTR(node->attr.i.sym.type_p);
2113 h = 9*h + HASH_PTR(get_irn_mode(node));
2116 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2117 h = irn_arity = get_irn_intra_arity(node);
2119 /* consider all in nodes... except the block if not a control flow. */
2120 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2121 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2125 h = 9*h + HASH_PTR(get_irn_mode(node));
2127 h = 9*h + HASH_PTR(get_irn_op(node));
2134 new_identities(void) {
2135 return new_pset(vt_cmp, N_IR_NODES);
2139 del_identities(pset *value_table) {
2140 del_pset(value_table);
2144 * Return the canonical node computing the same value as n.
2145 * Looks up the node in a hash table.
2147 * For Const nodes this is performed in the constructor, too. Const
2148 * nodes are extremely time critical because of their frequent use in
2149 * constant string arrays.
2151 static INLINE ir_node *
2152 identify (pset *value_table, ir_node *n)
2156 if (!value_table) return n;
2158 if (get_opt_reassociation()) {
2159 if (is_op_commutative(get_irn_op(n))) {
2160 ir_node *l = get_binop_left(n);
2161 ir_node *r = get_binop_right(n);
2163 /* for commutative operators perform a OP b == b OP a */
2165 set_binop_left(n, r);
2166 set_binop_right(n, l);
2171 o = pset_find (value_table, n, ir_node_hash (n));
2180 * During construction we set the op_pin_state_pinned flag in the graph right when the
2181 * optimization is performed. The flag turning on procedure global cse could
2182 * be changed between two allocations. This way we are safe.
2184 static INLINE ir_node *
2185 identify_cons (pset *value_table, ir_node *n) {
2188 n = identify(value_table, n);
2189 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2190 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2195 * Return the canonical node computing the same value as n.
2196 * Looks up the node in a hash table, enters it in the table
2197 * if it isn't there yet.
2200 identify_remember (pset *value_table, ir_node *n)
2204 if (!value_table) return n;
2206 if (get_opt_reassociation()) {
2207 if (is_op_commutative(get_irn_op(n))) {
2208 ir_node *l = get_binop_left(n);
2209 ir_node *r = get_binop_right(n);
2211 /* for commutative operators perform a OP b == b OP a */
2213 set_binop_left(n, r);
2214 set_binop_right(n, l);
2219 /* lookup or insert in hash table with given hash key. */
2220 o = pset_insert (value_table, n, ir_node_hash (n));
2230 add_identities (pset *value_table, ir_node *node) {
2231 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2232 identify_remember (value_table, node);
2236 * garbage in, garbage out. If a node has a dead input, i.e., the
2237 * Bad node is input to the node, return the Bad node.
2239 static INLINE ir_node *
2240 gigo (ir_node *node)
2243 ir_op* op = get_irn_op(node);
2245 /* remove garbage blocks by looking at control flow that leaves the block
2246 and replacing the control flow by Bad. */
2247 if (get_irn_mode(node) == mode_X) {
2248 ir_node *block = get_nodes_block(node);
2249 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2250 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2252 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2253 irn_arity = get_irn_arity(block);
2254 for (i = 0; i < irn_arity; i++) {
2255 if (!is_Bad(get_irn_n(block, i))) break;
2257 if (i == irn_arity) return new_Bad();
2261 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2262 blocks predecessors is dead. */
2263 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2264 irn_arity = get_irn_arity(node);
2266 if (is_Block_dead(get_nodes_block(node)))
2269 for (i = 0; i < irn_arity; i++) {
2270 if (is_Bad(get_irn_n(node, i))) {
2276 /* With this code we violate the agreement that local_optimize
2277 only leaves Bads in Block, Phi and Tuple nodes. */
2278 /* If Block has only Bads as predecessors it's garbage. */
2279 /* If Phi has only Bads as predecessors it's garbage. */
2280 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2281 irn_arity = get_irn_arity(node);
2282 for (i = 0; i < irn_arity; i++) {
2283 if (!is_Bad(get_irn_n(node, i))) break;
2285 if (i == irn_arity) node = new_Bad();
2293 * These optimizations deallocate nodes from the obstack.
2294 * It can only be called if it is guaranteed that no other nodes
2295 * reference this one, i.e., right after construction of a node.
2298 optimize_node (ir_node *n)
2302 opcode iro = get_irn_opcode(n);
2304 type *old_tp = get_irn_type(n);
2306 int i, arity = get_irn_arity(n);
2307 for (i = 0; i < arity && !old_tp; ++i)
2308 old_tp = get_irn_type(get_irn_n(n, i));
2311 /* Allways optimize Phi nodes: part of the construction. */
2312 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2314 /* constant expression evaluation / constant folding */
2315 if (get_opt_constant_folding()) {
2316 /* constants can not be evaluated */
2317 if (iro != iro_Const) {
2318 /* try to evaluate */
2319 tv = computed_value(n);
2320 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2324 * we MUST copy the node here temporary, because it's still needed
2325 * for DBG_OPT_CSTEVAL
2327 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2328 oldn = alloca(node_size);
2330 memcpy(oldn, n, node_size);
2331 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2333 /* ARG, copy the in array, we need it for statistics */
2334 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2337 edges_node_deleted(n, current_ir_graph);
2339 /* evaluation was successful -- replace the node. */
2340 obstack_free (current_ir_graph->obst, n);
2341 nw = new_Const (get_tarval_mode (tv), tv);
2343 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2344 set_Const_type(nw, old_tp);
2345 DBG_OPT_CSTEVAL(oldn, nw);
2351 /* remove unnecessary nodes */
2352 if (get_opt_constant_folding() ||
2353 (iro == iro_Phi) || /* always optimize these nodes. */
2355 (iro == iro_Proj) ||
2356 (iro == iro_Block) ) /* Flags tested local. */
2357 n = equivalent_node (n);
2359 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2361 /** common subexpression elimination **/
2362 /* Checks whether n is already available. */
2363 /* The block input is used to distinguish different subexpressions. Right
2364 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2365 subexpressions within a block. */
2367 n = identify_cons (current_ir_graph->value_table, n);
2370 edges_node_deleted(oldn, current_ir_graph);
2372 /* We found an existing, better node, so we can deallocate the old node. */
2373 obstack_free (current_ir_graph->obst, oldn);
2378 /* Some more constant expression evaluation that does not allow to
2380 iro = get_irn_opcode(n);
2381 if (get_opt_constant_folding() ||
2382 (iro == iro_Cond) ||
2383 (iro == iro_Proj)) /* Flags tested local. */
2384 n = transform_node (n);
2386 /* Remove nodes with dead (Bad) input.
2387 Run always for transformation induced Bads. */
2390 /* Now we have a legal, useful node. Enter it in hash table for cse */
2391 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2392 n = identify_remember (current_ir_graph->value_table, n);
2400 * These optimizations never deallocate nodes (in place). This can cause dead
2401 * nodes lying on the obstack. Remove these by a dead node elimination,
2402 * i.e., a copying garbage collection.
2405 optimize_in_place_2 (ir_node *n)
2409 opcode iro = get_irn_opcode(n);
2411 type *old_tp = get_irn_type(n);
2413 int i, arity = get_irn_arity(n);
2414 for (i = 0; i < arity && !old_tp; ++i)
2415 old_tp = get_irn_type(get_irn_n(n, i));
2418 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2420 /* if not optimize return n */
2423 /* Here this is possible. Why? */
2427 /* constant expression evaluation / constant folding */
2428 if (get_opt_constant_folding()) {
2429 /* constants can not be evaluated */
2430 if (iro != iro_Const) {
2431 /* try to evaluate */
2432 tv = computed_value(n);
2433 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2434 /* evaluation was successful -- replace the node. */
2435 n = new_Const (get_tarval_mode (tv), tv);
2437 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2438 set_Const_type(n, old_tp);
2440 DBG_OPT_CSTEVAL(oldn, n);
2446 /* remove unnecessary nodes */
2447 if (get_opt_constant_folding() ||
2448 (iro == iro_Phi) || /* always optimize these nodes. */
2449 (iro == iro_Id) || /* ... */
2450 (iro == iro_Proj) || /* ... */
2451 (iro == iro_Block) ) /* Flags tested local. */
2452 n = equivalent_node (n);
2454 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2456 /** common subexpression elimination **/
2457 /* Checks whether n is already available. */
2458 /* The block input is used to distinguish different subexpressions. Right
2459 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2460 subexpressions within a block. */
2461 if (get_opt_cse()) {
2462 n = identify (current_ir_graph->value_table, n);
2465 /* Some more constant expression evaluation. */
2466 iro = get_irn_opcode(n);
2467 if (get_opt_constant_folding() ||
2468 (iro == iro_Cond) ||
2469 (iro == iro_Proj)) /* Flags tested local. */
2470 n = transform_node (n);
2472 /* Remove nodes with dead (Bad) input.
2473 Run always for transformation induced Bads. */
2476 /* Now we can verify the node, as it has no dead inputs any more. */
2479 /* Now we have a legal, useful node. Enter it in hash table for cse.
2480 Blocks should be unique anyways. (Except the successor of start:
2481 is cse with the start block!) */
2482 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2483 n = identify_remember (current_ir_graph->value_table, n);
2489 * Wrapper for external use, set proper status bits after optimization.
2492 optimize_in_place (ir_node *n)
2494 /* Handle graph state */
2495 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2497 if (get_opt_global_cse())
2498 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2499 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2500 set_irg_outs_inconsistent(current_ir_graph);
2502 /* Maybe we could also test whether optimizing the node can
2503 change the control graph. */
2504 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2505 set_irg_dom_inconsistent(current_ir_graph);
2506 return optimize_in_place_2 (n);
2510 * set the default ir op operations
2512 ir_op *firm_set_default_operations(ir_op *op)
2514 op = firm_set_default_computed_value(op);
2515 op = firm_set_default_equivalent_node(op);
2516 op = firm_set_default_transform_node(op);
2517 op = firm_set_default_node_cmp_attr(op);