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 "irmode_t.h"
31 # include "ircons_t.h"
35 # include "dbginfo_t.h"
36 # include "iropt_dbg.h"
37 # include "irflag_t.h"
38 # include "firmstat.h"
42 /* Make types visible to allow most efficient access */
43 # include "entity_t.h"
45 # ifdef DO_HEAPANALYSIS
46 /* heapanal can't cope with NoMems */
47 # else /* if defined DO_HEAPANALYSIS */
49 # endif /* defined DO_HEAPANALYSIS */
52 * Trivial INLINEable routine for copy propagation.
53 * Does follow Ids, needed to optimize INLINEd code.
55 static INLINE ir_node *
56 follow_Id (ir_node *n)
58 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
63 * return the value of a Constant
65 static tarval *computed_value_Const(ir_node *n)
67 return get_Const_tarval(n);
71 * return the value of a 'sizeof' SymConst
73 static tarval *computed_value_SymConst(ir_node *n)
75 if ((get_SymConst_kind(n) == symconst_size) &&
76 (get_type_state(get_SymConst_type(n))) == layout_fixed)
77 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
82 * return the value of an Add
84 static tarval *computed_value_Add(ir_node *n)
86 ir_node *a = get_Add_left(n);
87 ir_node *b = get_Add_right(n);
89 tarval *ta = value_of(a);
90 tarval *tb = value_of(b);
92 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
93 return tarval_add(ta, tb);
99 * return the value of a Sub
100 * Special case: a - a
102 static tarval *computed_value_Sub(ir_node *n)
104 ir_node *a = get_Sub_left(n);
105 ir_node *b = get_Sub_right(n);
110 if (a == b && !is_Bad(a))
111 return get_tarval_null(get_irn_mode(n));
116 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
117 return tarval_sub(ta, tb);
123 * return the value of an unary Minus
125 static tarval *computed_value_Minus(ir_node *n)
127 ir_node *a = get_Minus_op(n);
128 tarval *ta = value_of(a);
130 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
131 return tarval_neg(ta);
137 * return the value of a Mul
139 static tarval *computed_value_Mul(ir_node *n)
141 ir_node *a = get_Mul_left(n);
142 ir_node *b = get_Mul_right(n);
144 tarval *ta = value_of(a);
145 tarval *tb = value_of(b);
147 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
148 return tarval_mul(ta, tb);
150 /* a*0 = 0 or 0*b = 0:
151 calls computed_value recursive and returns the 0 with proper
153 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
155 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
162 * return the value of a floating point Quot
164 static tarval *computed_value_Quot(ir_node *n)
166 ir_node *a = get_Quot_left(n);
167 ir_node *b = get_Quot_right(n);
169 tarval *ta = value_of(a);
170 tarval *tb = value_of(b);
172 /* This was missing in original implementation. Why? */
173 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
174 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
175 return tarval_quo(ta, tb);
181 * calculate the value of an integer Div of two nodes
182 * Special case: 0 / b
184 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
186 tarval *ta = value_of(a);
187 tarval *tb = value_of(b);
189 /* Compute c1 / c2 or 0 / a, a != 0 */
190 if (ta != tarval_bad) {
191 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
192 return tarval_div(ta, tb);
193 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
200 * return the value of an integer Div
202 static tarval *computed_value_Div(ir_node *n)
204 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
208 * calculate the value of an integer Mod of two nodes
209 * Special case: a % 1
211 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
213 tarval *ta = value_of(a);
214 tarval *tb = value_of(b);
216 /* Compute c1 % c2 or a % 1 */
217 if (tb != tarval_bad) {
218 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
219 return tarval_mod(ta, tb);
220 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
221 return get_mode_null(get_irn_mode(a));
228 * return the value of an integer Mod
230 static tarval *computed_value_Mod(ir_node *n)
232 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
236 * return the value of an Abs
238 static tarval *computed_value_Abs(ir_node *n)
240 ir_node *a = get_Abs_op(n);
241 tarval *ta = value_of(a);
243 if (ta != tarval_bad)
244 return tarval_abs(ta);
250 * return the value of an And
251 * Special case: a & 0, 0 & b
253 static tarval *computed_value_And(ir_node *n)
255 ir_node *a = get_And_left(n);
256 ir_node *b = get_And_right(n);
258 tarval *ta = value_of(a);
259 tarval *tb = value_of(b);
261 if ((ta != tarval_bad) && (tb != tarval_bad)) {
262 return tarval_and (ta, tb);
266 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
267 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
275 * return the value of an Or
276 * Special case: a | 1...1, 1...1 | b
278 static tarval *computed_value_Or(ir_node *n)
280 ir_node *a = get_Or_left(n);
281 ir_node *b = get_Or_right(n);
283 tarval *ta = value_of(a);
284 tarval *tb = value_of(b);
286 if ((ta != tarval_bad) && (tb != tarval_bad)) {
287 return tarval_or (ta, tb);
290 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
291 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
299 * return the value of an Eor
301 static tarval *computed_value_Eor(ir_node *n)
303 ir_node *a = get_Eor_left(n);
304 ir_node *b = get_Eor_right(n);
309 return get_tarval_null(get_irn_mode(n));
314 if ((ta != tarval_bad) && (tb != tarval_bad)) {
315 return tarval_eor (ta, tb);
321 * return the value of a Not
323 static tarval *computed_value_Not(ir_node *n)
325 ir_node *a = get_Not_op(n);
326 tarval *ta = value_of(a);
328 if (ta != tarval_bad)
329 return tarval_not(ta);
335 * return the value of a Shl
337 static tarval *computed_value_Shl(ir_node *n)
339 ir_node *a = get_Shl_left(n);
340 ir_node *b = get_Shl_right(n);
342 tarval *ta = value_of(a);
343 tarval *tb = value_of(b);
345 if ((ta != tarval_bad) && (tb != tarval_bad)) {
346 return tarval_shl (ta, tb);
352 * return the value of a Shr
354 static tarval *computed_value_Shr(ir_node *n)
356 ir_node *a = get_Shr_left(n);
357 ir_node *b = get_Shr_right(n);
359 tarval *ta = value_of(a);
360 tarval *tb = value_of(b);
362 if ((ta != tarval_bad) && (tb != tarval_bad)) {
363 return tarval_shr (ta, tb);
369 * return the value of a Shrs
371 static tarval *computed_value_Shrs(ir_node *n)
373 ir_node *a = get_Shrs_left(n);
374 ir_node *b = get_Shrs_right(n);
376 tarval *ta = value_of(a);
377 tarval *tb = value_of(b);
379 if ((ta != tarval_bad) && (tb != tarval_bad)) {
380 return tarval_shrs (ta, tb);
386 * return the value of a Rot
388 static tarval *computed_value_Rot(ir_node *n)
390 ir_node *a = get_Rot_left(n);
391 ir_node *b = get_Rot_right(n);
393 tarval *ta = value_of(a);
394 tarval *tb = value_of(b);
396 if ((ta != tarval_bad) && (tb != tarval_bad)) {
397 return tarval_rot (ta, tb);
403 * return the value of a Conv
405 static tarval *computed_value_Conv(ir_node *n)
407 ir_node *a = get_Conv_op(n);
408 tarval *ta = value_of(a);
410 if (ta != tarval_bad)
411 return tarval_convert_to(ta, get_irn_mode(n));
417 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
419 static tarval *computed_value_Proj(ir_node *n)
421 ir_node *a = get_Proj_pred(n);
425 /* Optimize Cmp nodes.
426 This performs a first step of unreachable code elimination.
427 Proj can not be computed, but folding a Cmp above the Proj here is
428 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
430 There are several case where we can evaluate a Cmp node:
431 1. The nodes compared are both the same. If we compare for
432 equal, greater equal, ... this will return true, else it
433 will return false. This step relies on cse.
434 2. The predecessors of Cmp are target values. We can evaluate
436 3. The predecessors are Allocs or void* constants. Allocs never
437 return NULL, they raise an exception. Therefore we can predict
439 switch (get_irn_opcode(a)) {
441 aa = get_Cmp_left(a);
442 ab = get_Cmp_right(a);
443 proj_nr = get_Proj_proj(n);
445 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
446 /* BEWARE: a == a is NOT always True for floating Point!!! */
447 /* This is a trick with the bits used for encoding the Cmp
448 Proj numbers, the following statement is not the same:
449 return new_tarval_from_long (proj_nr == Eq, mode_b) */
450 return new_tarval_from_long (proj_nr & Eq, mode_b);
452 tarval *taa = value_of(aa);
453 tarval *tab = value_of(ab);
455 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
456 /* strange checks... */
457 pnc_number flags = tarval_cmp (taa, tab);
458 if (flags != False) {
459 return new_tarval_from_long (proj_nr & flags, mode_b);
461 } else { /* check for 3.: */
462 ir_node *aaa = skip_Id(skip_Proj(aa));
463 ir_node *aba = skip_Id(skip_Proj(ab));
465 if ( ( (/* aa is ProjP and aaa is Alloc */
466 (get_irn_op(aa) == op_Proj)
467 && (mode_is_reference(get_irn_mode(aa)))
468 && (get_irn_op(aaa) == op_Alloc))
469 && ( (/* ab is constant void */
470 (get_irn_op(ab) == op_Const)
471 && (mode_is_reference(get_irn_mode(ab)))
472 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
473 || (/* ab is other Alloc */
474 (get_irn_op(ab) == op_Proj)
475 && (mode_is_reference(get_irn_mode(ab)))
476 && (get_irn_op(aba) == op_Alloc)
478 || (/* aa is void and aba is Alloc */
479 (get_irn_op(aa) == op_Const)
480 && (mode_is_reference(get_irn_mode(aa)))
481 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
482 && (get_irn_op(ab) == op_Proj)
483 && (mode_is_reference(get_irn_mode(ab)))
484 && (get_irn_op(aba) == op_Alloc)))
486 return new_tarval_from_long (proj_nr & Ne, mode_b);
492 /* compute either the Div or the Mod part */
493 proj_nr = get_Proj_proj(n);
494 if (proj_nr == pn_DivMod_res_div)
495 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
496 else if (proj_nr == pn_DivMod_res_mod)
497 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
501 if (get_Proj_proj(n) == pn_Div_res)
502 return computed_value(a);
506 if (get_Proj_proj(n) == pn_Mod_res)
507 return computed_value(a);
517 * calculate the value of a Mux: can be evaluated, if the
518 * sel and the right input are known
520 static tarval *computed_value_Mux(ir_node *n)
522 ir_node *sel = get_Mux_sel(n);
523 tarval *ts = value_of(sel);
525 if (ts == get_tarval_b_true()) {
526 ir_node *v = get_Mux_true(n);
529 else if (ts == get_tarval_b_false()) {
530 ir_node *v = get_Mux_false(n);
537 * If the parameter n can be computed, return its value, else tarval_bad.
538 * Performs constant folding.
540 * @param n The node this should be evaluated
542 tarval *computed_value(ir_node *n)
544 if (n->op->computed_value)
545 return n->op->computed_value(n);
550 * set the default computed_value evaluator
552 static ir_op *firm_set_default_computed_value(ir_op *op)
556 op->computed_value = computed_value_##a; \
582 op->computed_value = NULL;
590 /* returns 1 if the a and b are pointers to different locations. */
592 different_identity (ir_node *a, ir_node *b)
594 assert (mode_is_reference(get_irn_mode (a))
595 && mode_is_reference(get_irn_mode (b)));
597 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
598 ir_node *a1 = get_Proj_pred (a);
599 ir_node *b1 = get_Proj_pred (b);
600 if (a1 != b1 && get_irn_op (a1) == op_Alloc
601 && get_irn_op (b1) == op_Alloc)
608 static ir_node *equivalent_node_Block(ir_node *n)
612 /* The Block constructor does not call optimize, but mature_immBlock
613 calls the optimization. */
614 assert(get_Block_matured(n));
616 /* Straightening: a single entry Block following a single exit Block
617 can be merged, if it is not the Start block. */
618 /* !!! Beware, all Phi-nodes of n must have been optimized away.
619 This should be true, as the block is matured before optimize is called.
620 But what about Phi-cycles with the Phi0/Id that could not be resolved?
621 Remaining Phi nodes are just Ids. */
622 if ((get_Block_n_cfgpreds(n) == 1) &&
623 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
624 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
625 if (predblock == oldn) {
626 /* Jmp jumps into the block it is in -- deal self cycle. */
627 n = set_Block_dead(n);
628 DBG_OPT_DEAD(oldn, n);
629 } else if (get_opt_control_flow_straightening()) {
631 DBG_OPT_STG(oldn, n);
634 else if ((get_Block_n_cfgpreds(n) == 1) &&
635 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
636 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
637 if (predblock == oldn) {
638 /* Jmp jumps into the block it is in -- deal self cycle. */
639 n = set_Block_dead(n);
640 DBG_OPT_DEAD(oldn, n);
643 else if ((get_Block_n_cfgpreds(n) == 2) &&
644 (get_opt_control_flow_weak_simplification())) {
645 /* Test whether Cond jumps twice to this block
646 @@@ we could do this also with two loops finding two preds from several ones. */
647 ir_node *a = get_Block_cfgpred(n, 0);
648 ir_node *b = get_Block_cfgpred(n, 1);
650 if ((get_irn_op(a) == op_Proj) &&
651 (get_irn_op(b) == op_Proj) &&
652 (get_Proj_pred(a) == get_Proj_pred(b)) &&
653 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
654 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
655 /* Also a single entry Block following a single exit Block. Phis have
656 twice the same operand and will be optimized away. */
657 n = get_nodes_block(a);
658 DBG_OPT_IFSIM(oldn, a, b, n);
660 } else if (get_opt_unreachable_code() &&
661 (n != current_ir_graph->start_block) &&
662 (n != current_ir_graph->end_block) ) {
663 int i, n_cfg = get_Block_n_cfgpreds(n);
665 /* If all inputs are dead, this block is dead too, except if it is
666 the start or end block. This is a step of unreachable code
668 for (i = 0; i < n_cfg; i++) {
669 ir_node *pred = get_Block_cfgpred(n, i);
672 if (is_Bad(pred)) continue;
673 pred_blk = get_nodes_block(pred);
675 if (is_Block_dead(pred_blk)) continue;
678 /* really found a living input */
683 n = set_Block_dead(n);
690 * Returns a equivalent node for a Jmp, a Bad :-)
691 * Of course this only happens if the Block of the Jmp is Bad.
693 static ir_node *equivalent_node_Jmp(ir_node *n)
695 /* GL: Why not same for op_Raise?? */
696 /* unreachable code elimination */
697 if (is_Block_dead(get_nodes_block(n)))
703 static ir_node *equivalent_node_Cond(ir_node *n)
705 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
706 See cases for iro_Cond and iro_Proj in transform_node. */
711 * optimize operations that are commutative and have neutral 0,
712 * so a op 0 = 0 op a = a.
714 static ir_node *equivalent_node_neutral_zero(ir_node *n)
718 ir_node *a = get_binop_left(n);
719 ir_node *b = get_binop_right(n);
724 /* After running compute_node there is only one constant predecessor.
725 Find this predecessors value and remember the other node: */
726 if ((tv = value_of(a)) != tarval_bad) {
728 } else if ((tv = value_of(b)) != tarval_bad) {
733 /* If this predecessors constant value is zero, the operation is
734 unnecessary. Remove it: */
735 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
738 DBG_OPT_ALGSIM1(oldn, a, b, n);
744 #define equivalent_node_Add equivalent_node_neutral_zero
745 #define equivalent_node_Eor equivalent_node_neutral_zero
748 * optimize operations that are not commutative but have neutral 0 on left,
751 static ir_node *equivalent_node_left_zero(ir_node *n)
755 ir_node *a = get_binop_left(n);
756 ir_node *b = get_binop_right(n);
758 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
761 DBG_OPT_ALGSIM1(oldn, a, b, n);
767 #define equivalent_node_Sub equivalent_node_left_zero
768 #define equivalent_node_Shl equivalent_node_left_zero
769 #define equivalent_node_Shr equivalent_node_left_zero
770 #define equivalent_node_Shrs equivalent_node_left_zero
771 #define equivalent_node_Rot equivalent_node_left_zero
774 * Er, a "symmetic unop", ie op(op(n)) = n.
776 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
779 ir_node *pred = get_unop_op(n);
781 /* optimize symmetric unop */
782 if (get_irn_op(pred) == get_irn_op(n)) {
783 n = get_unop_op(pred);
784 DBG_OPT_ALGSIM2(oldn, pred, n);
790 #define equivalent_node_Not equivalent_node_symmetric_unop
792 /* --x == x */ /* ??? Is this possible or can --x raise an
793 out of bounds exception if min =! max? */
794 #define equivalent_node_Minus equivalent_node_symmetric_unop
797 * Optimize a * 1 = 1 * a = a.
799 static ir_node *equivalent_node_Mul(ir_node *n)
803 ir_node *a = get_Mul_left(n);
804 ir_node *b = get_Mul_right(n);
806 /* Mul is commutative and has again an other neutral element. */
807 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
809 DBG_OPT_ALGSIM1(oldn, a, b, n);
810 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
812 DBG_OPT_ALGSIM1(oldn, a, b, n);
818 * Optimize a / 1 = a.
820 static ir_node *equivalent_node_Div(ir_node *n)
822 ir_node *a = get_Div_left(n);
823 ir_node *b = get_Div_right(n);
825 /* Div is not commutative. */
826 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
827 /* Turn Div into a tuple (mem, bad, a) */
828 ir_node *mem = get_Div_mem(n);
829 turn_into_tuple(n, 3);
830 set_Tuple_pred(n, pn_Div_M, mem);
831 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
832 set_Tuple_pred(n, pn_Div_res, a);
838 * Optimize a / 1 = a.
840 static ir_node *equivalent_node_DivMod(ir_node *n)
842 ir_node *a = get_DivMod_left(n);
843 ir_node *b = get_DivMod_right(n);
845 /* Div is not commutative. */
846 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
847 /* Turn DivMod into a tuple (mem, bad, a, 0) */
848 ir_node *mem = get_Div_mem(n);
849 ir_mode *mode = get_irn_mode(b);
851 turn_into_tuple(n, 4);
852 set_Tuple_pred(n, pn_DivMod_M, mem);
853 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
854 set_Tuple_pred(n, pn_DivMod_res_div, a);
855 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
861 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
863 static ir_node *equivalent_node_Or(ir_node *n)
867 ir_node *a = get_Or_left(n);
868 ir_node *b = get_Or_right(n);
871 n = a; /* Or has it's own neutral element */
872 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
874 DBG_OPT_ALGSIM1(oldn, a, b, n);
875 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
877 DBG_OPT_ALGSIM1(oldn, a, b, n);
884 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
886 static ir_node *equivalent_node_And(ir_node *n)
890 ir_node *a = get_And_left(n);
891 ir_node *b = get_And_right(n);
894 n = a; /* And has it's own neutral element */
895 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
897 DBG_OPT_ALGSIM1(oldn, a, b, n);
898 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
900 DBG_OPT_ALGSIM1(oldn, a, b, n);
906 * Try to remove useless conv's:
908 static ir_node *equivalent_node_Conv(ir_node *n)
911 ir_node *a = get_Conv_op(n);
914 ir_mode *n_mode = get_irn_mode(n);
915 ir_mode *a_mode = get_irn_mode(a);
917 if (n_mode == a_mode) { /* No Conv necessary */
919 DBG_OPT_ALGSIM3(oldn, a, n);
920 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
924 n_mode = get_irn_mode(n);
925 b_mode = get_irn_mode(b);
927 if (n_mode == b_mode) {
928 if (n_mode == mode_b) {
929 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
930 DBG_OPT_ALGSIM1(oldn, a, b, n);
932 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
933 if (smaller_mode(b_mode, a_mode)){
934 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
935 DBG_OPT_ALGSIM1(oldn, a, b, n);
944 * A Cast may be removed if the type of the previous node
945 * is already to type of the Cast.
947 static ir_node *equivalent_node_Cast(ir_node *n) {
948 ir_node *pred = get_Cast_op(n);
949 if (get_irn_type(pred) == get_Cast_type(n))
954 /* Several optimizations:
955 - no Phi in start block.
956 - remove Id operators that are inputs to Phi
957 - fold Phi-nodes, iff they have only one predecessor except
960 static ir_node *equivalent_node_Phi(ir_node *n)
965 ir_node *block = NULL; /* to shutup gcc */
966 ir_node *first_val = NULL; /* to shutup gcc */
967 ir_node *scnd_val = NULL; /* to shutup gcc */
969 if (!get_opt_normalize()) return n;
971 n_preds = get_Phi_n_preds(n);
973 block = get_nodes_block(n);
974 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
975 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
976 if ((is_Block_dead(block)) || /* Control dead */
977 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
978 return new_Bad(); /* in the Start Block. */
980 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
983 /* first we test for a special case: */
984 /* Confirm is a special node fixing additional information for a
985 value that is known at a certain point. This is useful for
986 dataflow analysis. */
988 ir_node *a = get_Phi_pred(n, 0);
989 ir_node *b = get_Phi_pred(n, 1);
990 if ( (get_irn_op(a) == op_Confirm)
991 && (get_irn_op(b) == op_Confirm)
992 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
993 && (get_irn_n(a, 1) == get_irn_n (b, 1))
994 && (a->data.num == (~b->data.num & irpn_True) )) {
995 return get_irn_n(a, 0);
1000 /* If the Block has a Bad pred, we also have one. */
1001 for (i = 0; i < n_preds; ++i)
1002 if (is_Bad (get_Block_cfgpred(block, i)))
1003 set_Phi_pred(n, i, new_Bad());
1005 /* Find first non-self-referencing input */
1006 for (i = 0; i < n_preds; ++i) {
1007 first_val = get_Phi_pred(n, i);
1008 if ( (first_val != n) /* not self pointer */
1010 && (get_irn_op(first_val) != op_Bad)
1012 ) { /* value not dead */
1013 break; /* then found first value. */
1017 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1018 if (i >= n_preds) { return new_Bad(); }
1022 /* follow_Id () for rest of inputs, determine if any of these
1023 are non-self-referencing */
1024 while (++i < n_preds) {
1025 scnd_val = get_Phi_pred(n, i);
1026 if ( (scnd_val != n)
1027 && (scnd_val != first_val)
1029 && (get_irn_op(scnd_val) != op_Bad)
1036 /* Fold, if no multiple distinct non-self-referencing inputs */
1039 DBG_OPT_PHI(oldn, first_val, n);
1041 /* skip the remaining Ids (done in get_Phi_pred). */
1042 /* superfluous, since we walk all to propagate Block's Bads.
1043 while (++i < n_preds) get_Phi_pred(n, i); */
1049 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1051 static ir_node *equivalent_node_Proj(ir_node *n)
1055 ir_node *a = get_Proj_pred(n);
1057 if ( get_irn_op(a) == op_Tuple) {
1058 /* Remove the Tuple/Proj combination. */
1059 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1060 n = get_Tuple_pred(a, get_Proj_proj(n));
1061 DBG_OPT_TUPLE(oldn, a, n);
1063 assert(0); /* This should not happen! */
1066 } else if (get_irn_mode(n) == mode_X &&
1067 is_Block_dead(get_nodes_block(n))) {
1068 /* Remove dead control flow -- early gigo. */
1077 static ir_node *equivalent_node_Id(ir_node *n)
1082 DBG_OPT_ID(oldn, n);
1089 static ir_node *equivalent_node_Mux(ir_node *n)
1091 ir_node *sel = get_Mux_sel(n);
1092 tarval *ts = value_of(sel);
1094 if (ts == get_tarval_b_true())
1095 return get_Mux_true(n);
1096 else if (ts == get_tarval_b_false())
1097 return get_Mux_false(n);
1103 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1104 * perform no actual computation, as, e.g., the Id nodes. It does not create
1105 * new nodes. It is therefore safe to free n if the node returned is not n.
1106 * If a node returns a Tuple we can not just skip it. If the size of the
1107 * in array fits, we transform n into a tuple (e.g., Div).
1110 equivalent_node(ir_node *n)
1112 if (n->op->equivalent_node)
1113 return n->op->equivalent_node(n);
1118 * set the default equivalent node operation
1120 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1124 op->equivalent_node = equivalent_node_##a; \
1152 op->equivalent_node = NULL;
1160 * Do node specific optimizations of nodes predecessors.
1163 optimize_preds(ir_node *n) {
1164 ir_node *a = NULL, *b = NULL;
1166 /* get the operands we will work on for simple cases. */
1168 a = get_binop_left(n);
1169 b = get_binop_right(n);
1170 } else if (is_unop(n)) {
1174 switch (get_irn_opcode(n)) {
1177 /* We don't want Cast as input to Cmp. */
1178 if (get_irn_op(a) == op_Cast) {
1182 if (get_irn_op(b) == op_Cast) {
1184 set_Cmp_right(n, b);
1193 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1194 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1196 static ir_node *transform_node_AddSub(ir_node *n)
1198 ir_mode *mode = get_irn_mode(n);
1200 if (mode_is_reference(mode)) {
1201 ir_node *left = get_binop_left(n);
1202 ir_node *right = get_binop_right(n);
1203 int ref_bits = get_mode_size_bits(mode);
1205 if (get_irn_op(left) == op_Conv) {
1206 ir_mode *mode = get_irn_mode(left);
1207 int bits = get_mode_size_bits(mode);
1209 if (ref_bits == bits &&
1210 mode_is_int(mode) &&
1211 get_mode_arithmetic(mode) == irma_twos_complement) {
1212 ir_node *pre = get_Conv_op(left);
1213 ir_mode *pre_mode = get_irn_mode(pre);
1215 if (mode_is_int(pre_mode) &&
1216 get_mode_size_bits(pre_mode) == bits &&
1217 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1218 /* ok, this conv just changes to sign, moreover the calculation
1219 * is done with same number of bits as our address mode, so
1220 * we can ignore the conv as address calculation can be viewed
1221 * as either signed or unsigned
1223 set_binop_left(n, pre);
1228 if (get_irn_op(right) == op_Conv) {
1229 ir_mode *mode = get_irn_mode(right);
1230 int bits = get_mode_size_bits(mode);
1232 if (ref_bits == bits &&
1233 mode_is_int(mode) &&
1234 get_mode_arithmetic(mode) == irma_twos_complement) {
1235 ir_node *pre = get_Conv_op(right);
1236 ir_mode *pre_mode = get_irn_mode(pre);
1238 if (mode_is_int(pre_mode) &&
1239 get_mode_size_bits(pre_mode) == bits &&
1240 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1241 /* ok, this conv just changes to sign, moreover the calculation
1242 * is done with same number of bits as our address mode, so
1243 * we can ignore the conv as address calculation can be viewed
1244 * as either signed or unsigned
1246 set_binop_right(n, pre);
1254 #define transform_node_Add transform_node_AddSub
1255 #define transform_node_Sub transform_node_AddSub
1257 /** Do architecture dependend optimizations on Mul nodes */
1258 static ir_node *transform_node_Mul(ir_node *n) {
1259 return arch_dep_replace_mul_with_shifts(n);
1262 static ir_node *transform_node_Div(ir_node *n)
1264 tarval *tv = value_of(n);
1267 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1269 if (tv != tarval_bad)
1270 value = new_Const(get_tarval_mode(tv), tv);
1271 else /* Try architecture dependand optimization */
1272 value = arch_dep_replace_div_by_const(n);
1275 /* Turn Div into a tuple (mem, bad, value) */
1276 ir_node *mem = get_Div_mem(n);
1278 turn_into_tuple(n, 3);
1279 set_Tuple_pred(n, pn_Div_M, mem);
1280 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1281 set_Tuple_pred(n, pn_Div_res, value);
1286 static ir_node *transform_node_Mod(ir_node *n)
1288 tarval *tv = value_of(n);
1291 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1293 if (tv != tarval_bad)
1294 value = new_Const(get_tarval_mode(tv), tv);
1295 else /* Try architecture dependand optimization */
1296 value = arch_dep_replace_mod_by_const(n);
1299 /* Turn Mod into a tuple (mem, bad, value) */
1300 ir_node *mem = get_Mod_mem(n);
1302 turn_into_tuple(n, 3);
1303 set_Tuple_pred(n, pn_Mod_M, mem);
1304 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1305 set_Tuple_pred(n, pn_Mod_res, value);
1310 static ir_node *transform_node_DivMod(ir_node *n)
1314 ir_node *a = get_DivMod_left(n);
1315 ir_node *b = get_DivMod_right(n);
1316 ir_mode *mode = get_irn_mode(a);
1317 tarval *ta = value_of(a);
1318 tarval *tb = value_of(b);
1320 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1323 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1325 if (tb != tarval_bad) {
1326 if (tb == get_mode_one(get_tarval_mode(tb))) {
1327 b = new_Const (mode, get_mode_null(mode));
1329 } else if (ta != tarval_bad) {
1330 tarval *resa, *resb;
1331 resa = tarval_div (ta, tb);
1332 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1333 Jmp for X result!? */
1334 resb = tarval_mod (ta, tb);
1335 if (resb == tarval_bad) return n; /* Causes exception! */
1336 a = new_Const (mode, resa);
1337 b = new_Const (mode, resb);
1340 else { /* Try architecture dependand optimization */
1341 arch_dep_replace_divmod_by_const(&a, &b, n);
1342 evaluated = a != NULL;
1344 } else if (ta == get_mode_null(mode)) {
1345 /* 0 / non-Const = 0 */
1350 if (evaluated) { /* replace by tuple */
1351 ir_node *mem = get_DivMod_mem(n);
1352 turn_into_tuple(n, 4);
1353 set_Tuple_pred(n, pn_DivMod_M, mem);
1354 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1355 set_Tuple_pred(n, pn_DivMod_res_div, a);
1356 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1357 assert(get_nodes_block(n));
1363 static ir_node *transform_node_Cond(ir_node *n)
1365 /* Replace the Cond by a Jmp if it branches on a constant
1368 ir_node *a = get_Cond_selector(n);
1369 tarval *ta = value_of(a);
1371 if ((ta != tarval_bad) &&
1372 (get_irn_mode(a) == mode_b) &&
1373 (get_opt_unreachable_code())) {
1374 /* It's a boolean Cond, branching on a boolean constant.
1375 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1376 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1377 turn_into_tuple(n, 2);
1378 if (ta == tarval_b_true) {
1379 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1380 set_Tuple_pred(n, pn_Cond_true, jmp);
1382 set_Tuple_pred(n, pn_Cond_false, jmp);
1383 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1385 /* We might generate an endless loop, so keep it alive. */
1386 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1387 } else if ((ta != tarval_bad) &&
1388 (get_irn_mode(a) == mode_Iu) &&
1389 (get_Cond_kind(n) == dense) &&
1390 (get_opt_unreachable_code())) {
1391 /* I don't want to allow Tuples smaller than the biggest Proj.
1392 Also this tuple might get really big...
1393 I generate the Jmp here, and remember it in link. Link is used
1394 when optimizing Proj. */
1395 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1396 /* We might generate an endless loop, so keep it alive. */
1397 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1398 } else if ((get_irn_op(a) == op_Eor)
1399 && (get_irn_mode(a) == mode_b)
1400 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1401 /* The Eor is a negate. Generate a new Cond without the negate,
1402 simulate the negate by exchanging the results. */
1403 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1405 } else if ((get_irn_op(a) == op_Not)
1406 && (get_irn_mode(a) == mode_b)) {
1407 /* A Not before the Cond. Generate a new Cond without the Not,
1408 simulate the Not by exchanging the results. */
1409 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1418 static ir_node *transform_node_Eor(ir_node *n)
1420 ir_node *a = get_Eor_left(n);
1421 ir_node *b = get_Eor_right(n);
1423 if ((get_irn_mode(n) == mode_b)
1424 && (get_irn_op(a) == op_Proj)
1425 && (get_irn_mode(a) == mode_b)
1426 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1427 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1428 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1429 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1430 mode_b, get_negated_pnc(get_Proj_proj(a)));
1431 else if ((get_irn_mode(n) == mode_b)
1432 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1433 /* The Eor is a Not. Replace it by a Not. */
1434 /* ????!!!Extend to bitfield 1111111. */
1435 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1441 * Transform a boolean Not.
1443 static ir_node *transform_node_Not(ir_node *n)
1445 ir_node *a = get_Not_op(n);
1447 if ( (get_irn_mode(n) == mode_b)
1448 && (get_irn_op(a) == op_Proj)
1449 && (get_irn_mode(a) == mode_b)
1450 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1451 /* We negate a Cmp. The Cmp has the negated result anyways! */
1452 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1453 mode_b, get_negated_pnc(get_Proj_proj(a)));
1459 * Transform a Cast of a Const into a new Const
1461 static ir_node *transform_node_Cast(ir_node *n) {
1462 ir_node *pred = get_Cast_op(n);
1463 type *tp = get_irn_type(pred);
1465 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1466 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1467 get_Const_tarval(pred), tp);
1468 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1469 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1470 get_SymConst_kind(pred), tp);
1476 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1477 * done here instead of equivalent node because it creates new
1479 * Removes the exceptions and routes the memory to the NoMem node.
1481 * Further, it optimizes jump tables by removing all impossible cases.
1483 static ir_node *transform_node_Proj(ir_node *proj)
1485 ir_node *n = get_Proj_pred(proj);
1490 switch (get_irn_opcode(n)) {
1492 b = get_Div_right(n);
1495 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1496 proj_nr = get_Proj_proj(proj);
1498 /* this node may float */
1499 set_irn_pinned(n, op_pin_state_floats);
1501 if (proj_nr == pn_Div_X_except) {
1502 /* we found an exception handler, remove it */
1505 /* the memory Proj can be removed */
1506 ir_node *res = get_Div_mem(n);
1508 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1509 # endif /* defined USE_NOMEM */
1510 if (proj_nr == pn_Div_M)
1516 b = get_Mod_right(n);
1519 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1520 proj_nr = get_Proj_proj(proj);
1522 /* this node may float */
1523 set_irn_pinned(n, op_pin_state_floats);
1525 if (proj_nr == pn_Mod_X_except) {
1526 /* we found an exception handler, remove it */
1529 /* the memory Proj can be removed */
1530 ir_node *res = get_Mod_mem(n);
1532 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1533 # endif /* defined USE_NOMEM */
1534 if (proj_nr == pn_Mod_M)
1540 b = get_DivMod_right(n);
1543 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1544 proj_nr = get_Proj_proj(proj);
1546 /* this node may float */
1547 set_irn_pinned(n, op_pin_state_floats);
1549 if (proj_nr == pn_DivMod_X_except) {
1550 /* we found an exception handler, remove it */
1554 /* the memory Proj can be removed */
1555 ir_node *res = get_DivMod_mem(n);
1557 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1558 # endif /* defined USE_NOMEM */
1559 if (proj_nr == pn_DivMod_M)
1566 if (get_opt_unreachable_code()) {
1567 b = get_Cond_selector(n);
1570 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1571 /* we have a constant switch */
1572 long num = get_Proj_proj(proj);
1574 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1575 if (get_tarval_long(tb) == num) {
1576 /* Do NOT create a jump here, or we will have 2 control flow ops
1577 * in a block. This case is optimized away in optimize_cf(). */
1588 /* should not happen, but if it does will be optimized away */
1596 /* we have added a Tuple, optimize it for the current Proj away */
1597 return equivalent_node_Proj(proj);
1601 * returns the operands of a commutative bin-op, if one operand is
1602 * a const, it is returned as the second one.
1604 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1606 ir_node *op_a = get_binop_left(binop);
1607 ir_node *op_b = get_binop_right(binop);
1609 assert(is_op_commutative(get_irn_op(binop)));
1611 if (get_irn_op(op_a) == op_Const) {
1622 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1623 * Such pattern may arise in bitfield stores.
1625 * value c4 value c4 & c2
1626 * AND c3 AND c1 | c3
1631 static ir_node *transform_node_Or(ir_node *or)
1635 ir_node *and_l, *c3;
1636 ir_node *value, *c4;
1637 ir_node *new_and, *new_const, *block;
1638 ir_mode *mode = get_irn_mode(or);
1640 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1642 get_comm_Binop_Ops(or, &and, &c1);
1643 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1646 get_comm_Binop_Ops(and, &or_l, &c2);
1647 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1650 get_comm_Binop_Ops(or_l, &and_l, &c3);
1651 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1654 get_comm_Binop_Ops(and_l, &value, &c4);
1655 if (get_irn_op(c4) != op_Const)
1658 /* ok, found the pattern, check for conditions */
1659 assert(mode == get_irn_mode(and));
1660 assert(mode == get_irn_mode(or_l));
1661 assert(mode == get_irn_mode(and_l));
1663 tv1 = get_Const_tarval(c1);
1664 tv2 = get_Const_tarval(c2);
1665 tv3 = get_Const_tarval(c3);
1666 tv4 = get_Const_tarval(c4);
1668 tv = tarval_or(tv4, tv2);
1669 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1670 /* have at least one 0 at the same bit position */
1674 n_tv4 = tarval_not(tv4);
1675 if (tv3 != tarval_and(tv3, n_tv4)) {
1676 /* bit in the or_mask is outside the and_mask */
1680 n_tv2 = tarval_not(tv2);
1681 if (tv1 != tarval_and(tv1, n_tv2)) {
1682 /* bit in the or_mask is outside the and_mask */
1686 /* ok, all conditions met */
1687 block = get_nodes_block(or);
1689 new_and = new_r_And(current_ir_graph, block,
1690 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1692 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1694 set_Or_left(or, new_and);
1695 set_Or_right(or, new_const);
1697 /* check for more */
1698 return transform_node_Or(or);
1702 static ir_node *transform_node(ir_node *n);
1705 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1707 static ir_node * transform_node_shift(ir_node *n)
1710 tarval *tv1, *tv2, *res;
1712 int modulo_shf, flag;
1714 left = get_binop_left(n);
1716 /* different operations */
1717 if (get_irn_op(left) != get_irn_op(n))
1720 tv1 = value_of(get_binop_right(n));
1721 if (tv1 == tarval_bad)
1724 tv2 = value_of(get_binop_right(left));
1725 if (tv2 == tarval_bad)
1728 res = tarval_add(tv1, tv2);
1730 /* beware: a simple replacement works only, if res < modulo shift */
1731 mode = get_irn_mode(n);
1735 modulo_shf = get_mode_modulo_shift(mode);
1736 if (modulo_shf > 0) {
1737 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1739 if (tarval_cmp(res, modulo) & Lt)
1746 /* ok, we can replace it */
1747 ir_node *in[2], *irn, *block = get_nodes_block(n);
1749 in[0] = get_binop_left(left);
1750 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1752 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1754 return transform_node(irn);
1761 * Tries several [inplace] [optimizing] transformations and returns an
1762 * equivalent node. The difference to equivalent_node() is that these
1763 * transformations _do_ generate new nodes, and thus the old node must
1764 * not be freed even if the equivalent node isn't the old one.
1766 static ir_node *transform_node(ir_node *n)
1768 if (n->op->transform_node)
1769 n = n->op->transform_node(n);
1774 * set the default transform node operation
1776 static ir_op *firm_set_default_transform_node(ir_op *op)
1780 op->transform_node = transform_node_##a; \
1799 op->transform_node = transform_node_shift;
1802 op->transform_node = NULL;
1810 /* **************** Common Subexpression Elimination **************** */
1812 /** The size of the hash table used, should estimate the number of nodes
1814 #define N_IR_NODES 512
1816 /** Compares the attributes of two Const nodes. */
1817 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1819 return (get_Const_tarval(a) != get_Const_tarval(b))
1820 || (get_Const_type(a) != get_Const_type(b));
1823 /** Compares the attributes of two Proj nodes. */
1824 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1826 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1829 /** Compares the attributes of two Filter nodes. */
1830 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1832 return get_Filter_proj(a) != get_Filter_proj(b);
1835 /** Compares the attributes of two Alloc nodes. */
1836 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1838 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1839 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1842 /** Compares the attributes of two Free nodes. */
1843 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1845 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1848 /** Compares the attributes of two SymConst nodes. */
1849 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1851 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1852 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1853 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1856 /** Compares the attributes of two Call nodes. */
1857 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1859 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1862 /** Compares the attributes of two Sel nodes. */
1863 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1865 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1866 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1867 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1868 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1869 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1872 /** Compares the attributes of two Phi nodes. */
1873 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1875 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1878 /** Compares the attributes of two Cast nodes. */
1879 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1881 return get_Cast_type(a) != get_Cast_type(b);
1884 /** Compares the attributes of two Load nodes. */
1885 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1887 if (get_Load_volatility(a) == volatility_is_volatile ||
1888 get_Load_volatility(b) == volatility_is_volatile)
1889 /* NEVER do CSE on volatile Loads */
1892 return get_Load_mode(a) != get_Load_mode(b);
1895 /** Compares the attributes of two Store nodes. */
1896 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1898 /* NEVER do CSE on volatile Stores */
1899 return (get_Store_volatility(a) == volatility_is_volatile ||
1900 get_Store_volatility(b) == volatility_is_volatile);
1904 * set the default node attribute compare operation
1906 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1910 op->node_cmp_attr = node_cmp_attr_##a; \
1927 op->node_cmp_attr = NULL;
1935 * Compare function for two nodes in the hash table. Gets two
1936 * nodes as parameters. Returns 0 if the nodes are a cse.
1939 vt_cmp (const void *elt, const void *key)
1947 if (a == b) return 0;
1949 if ((get_irn_op(a) != get_irn_op(b)) ||
1950 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1952 /* compare if a's in and b's in are of equal length */
1953 irn_arity_a = get_irn_intra_arity (a);
1954 if (irn_arity_a != get_irn_intra_arity(b))
1957 /* for block-local cse and op_pin_state_pinned nodes: */
1958 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1959 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1963 /* compare a->in[0..ins] with b->in[0..ins] */
1964 for (i = 0; i < irn_arity_a; i++)
1965 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1969 * here, we already now that the nodes are identical except their
1972 if (a->op->node_cmp_attr)
1973 return a->op->node_cmp_attr(a, b);
1979 * Calculate a hash value of a node.
1982 ir_node_hash (ir_node *node)
1987 if (node->op == op_Const) {
1988 /* special value for const, as they only differ in their tarval. */
1989 h = HASH_PTR(node->attr.con.tv);
1990 h = 9*h + HASH_PTR(get_irn_mode(node));
1991 } else if (node->op == op_SymConst) {
1992 /* special value for const, as they only differ in their symbol. */
1993 h = HASH_PTR(node->attr.i.sym.type_p);
1994 h = 9*h + HASH_PTR(get_irn_mode(node));
1997 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1998 h = irn_arity = get_irn_intra_arity(node);
2000 /* consider all in nodes... except the block if not a control flow. */
2001 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2002 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2006 h = 9*h + HASH_PTR(get_irn_mode(node));
2008 h = 9*h + HASH_PTR(get_irn_op(node));
2015 new_identities(void) {
2016 return new_pset(vt_cmp, N_IR_NODES);
2020 del_identities(pset *value_table) {
2021 del_pset(value_table);
2025 * Return the canonical node computing the same value as n.
2026 * Looks up the node in a hash table.
2028 * For Const nodes this is performed in the constructor, too. Const
2029 * nodes are extremely time critical because of their frequent use in
2030 * constant string arrays.
2032 static INLINE ir_node *
2033 identify (pset *value_table, ir_node *n)
2037 if (!value_table) return n;
2039 if (get_opt_reassociation()) {
2040 if (is_op_commutative(get_irn_op(n))) {
2041 ir_node *l = get_binop_left(n);
2042 ir_node *r = get_binop_right(n);
2044 /* for commutative operators perform a OP b == b OP a */
2046 set_binop_left(n, r);
2047 set_binop_right(n, l);
2052 o = pset_find (value_table, n, ir_node_hash (n));
2061 * During construction we set the op_pin_state_pinned flag in the graph right when the
2062 * optimization is performed. The flag turning on procedure global cse could
2063 * be changed between two allocations. This way we are safe.
2065 static INLINE ir_node *
2066 identify_cons (pset *value_table, ir_node *n) {
2069 n = identify(value_table, n);
2070 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2071 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2076 * Return the canonical node computing the same value as n.
2077 * Looks up the node in a hash table, enters it in the table
2078 * if it isn't there yet.
2081 identify_remember (pset *value_table, ir_node *n)
2085 if (!value_table) return n;
2087 if (get_opt_reassociation()) {
2088 if (is_op_commutative(get_irn_op(n))) {
2089 ir_node *l = get_binop_left(n);
2090 ir_node *r = get_binop_right(n);
2092 /* for commutative operators perform a OP b == b OP a */
2094 set_binop_left(n, r);
2095 set_binop_right(n, l);
2100 /* lookup or insert in hash table with given hash key. */
2101 o = pset_insert (value_table, n, ir_node_hash (n));
2111 add_identities (pset *value_table, ir_node *node) {
2112 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2113 identify_remember (value_table, node);
2117 * garbage in, garbage out. If a node has a dead input, i.e., the
2118 * Bad node is input to the node, return the Bad node.
2120 static INLINE ir_node *
2121 gigo (ir_node *node)
2124 ir_op* op = get_irn_op(node);
2126 /* remove garbage blocks by looking at control flow that leaves the block
2127 and replacing the control flow by Bad. */
2128 if (get_irn_mode(node) == mode_X) {
2129 ir_node *block = get_nodes_block(node);
2130 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2132 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2133 irn_arity = get_irn_arity(block);
2134 for (i = 0; i < irn_arity; i++) {
2135 if (!is_Bad(get_irn_n(block, i))) break;
2137 if (i == irn_arity) return new_Bad();
2141 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2142 blocks predecessors is dead. */
2143 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2144 irn_arity = get_irn_arity(node);
2146 if (is_Block_dead(get_nodes_block(node)))
2149 for (i = 0; i < irn_arity; i++) {
2150 if (is_Bad(get_irn_n(node, i))) {
2156 /* With this code we violate the agreement that local_optimize
2157 only leaves Bads in Block, Phi and Tuple nodes. */
2158 /* If Block has only Bads as predecessors it's garbage. */
2159 /* If Phi has only Bads as predecessors it's garbage. */
2160 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2161 irn_arity = get_irn_arity(node);
2162 for (i = 0; i < irn_arity; i++) {
2163 if (!is_Bad(get_irn_n(node, i))) break;
2165 if (i == irn_arity) node = new_Bad();
2173 * These optimizations deallocate nodes from the obstack.
2174 * It can only be called if it is guaranteed that no other nodes
2175 * reference this one, i.e., right after construction of a node.
2178 optimize_node (ir_node *n)
2182 opcode iro = get_irn_opcode(n);
2184 type *old_tp = get_irn_type(n);
2186 int i, arity = get_irn_arity(n);
2187 for (i = 0; i < arity && !old_tp; ++i)
2188 old_tp = get_irn_type(get_irn_n(n, i));
2191 /* Allways optimize Phi nodes: part of the construction. */
2192 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2194 /* constant expression evaluation / constant folding */
2195 if (get_opt_constant_folding()) {
2196 /* constants can not be evaluated */
2197 if (iro != iro_Const) {
2198 /* try to evaluate */
2199 tv = computed_value(n);
2200 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2202 * we MUST copy the node here temporary, because it's still needed
2203 * for DBG_OPT_CSTEVAL
2205 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2206 oldn = alloca(node_size);
2208 memcpy(oldn, n, node_size);
2209 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2211 /* ARG, copy the in array, we need it for statistics */
2212 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2214 /* evaluation was successful -- replace the node. */
2215 obstack_free (current_ir_graph->obst, n);
2216 n = new_Const (get_tarval_mode (tv), tv);
2217 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2218 set_Const_type(n, old_tp);
2219 DBG_OPT_CSTEVAL(oldn, n);
2225 /* remove unnecessary nodes */
2226 if (get_opt_constant_folding() ||
2227 (iro == iro_Phi) || /* always optimize these nodes. */
2229 (iro == iro_Proj) ||
2230 (iro == iro_Block) ) /* Flags tested local. */
2231 n = equivalent_node (n);
2233 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2235 /** common subexpression elimination **/
2236 /* Checks whether n is already available. */
2237 /* The block input is used to distinguish different subexpressions. Right
2238 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2239 subexpressions within a block. */
2241 n = identify_cons (current_ir_graph->value_table, n);
2244 /* We found an existing, better node, so we can deallocate the old node. */
2245 obstack_free (current_ir_graph->obst, oldn);
2250 /* Some more constant expression evaluation that does not allow to
2252 iro = get_irn_opcode(n);
2253 if (get_opt_constant_folding() ||
2254 (iro == iro_Cond) ||
2255 (iro == iro_Proj)) /* Flags tested local. */
2256 n = transform_node (n);
2258 /* Remove nodes with dead (Bad) input.
2259 Run always for transformation induced Bads. */
2262 /* Now we have a legal, useful node. Enter it in hash table for cse */
2263 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2264 n = identify_remember (current_ir_graph->value_table, n);
2272 * These optimizations never deallocate nodes. This can cause dead
2273 * nodes lying on the obstack. Remove these by a dead node elimination,
2274 * i.e., a copying garbage collection.
2277 optimize_in_place_2 (ir_node *n)
2281 opcode iro = get_irn_opcode(n);
2283 type *old_tp = get_irn_type(n);
2285 int i, arity = get_irn_arity(n);
2286 for (i = 0; i < arity && !old_tp; ++i)
2287 old_tp = get_irn_type(get_irn_n(n, i));
2290 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2292 /* if not optimize return n */
2295 /* Here this is possible. Why? */
2299 /* constant expression evaluation / constant folding */
2300 if (get_opt_constant_folding()) {
2301 /* constants can not be evaluated */
2302 if (iro != iro_Const) {
2303 /* try to evaluate */
2304 tv = computed_value(n);
2305 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2306 /* evaluation was successful -- replace the node. */
2307 n = new_Const (get_tarval_mode (tv), tv);
2309 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2310 set_Const_type(n, old_tp);
2312 DBG_OPT_CSTEVAL(oldn, n);
2318 /* remove unnecessary nodes */
2319 if (get_opt_constant_folding() ||
2320 (iro == iro_Phi) || /* always optimize these nodes. */
2321 (iro == iro_Id) || /* ... */
2322 (iro == iro_Proj) || /* ... */
2323 (iro == iro_Block) ) /* Flags tested local. */
2324 n = equivalent_node (n);
2326 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2328 /** common subexpression elimination **/
2329 /* Checks whether n is already available. */
2330 /* The block input is used to distinguish different subexpressions. Right
2331 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2332 subexpressions within a block. */
2333 if (get_opt_cse()) {
2334 n = identify (current_ir_graph->value_table, n);
2337 /* Some more constant expression evaluation. */
2338 iro = get_irn_opcode(n);
2339 if (get_opt_constant_folding() ||
2340 (iro == iro_Cond) ||
2341 (iro == iro_Proj)) /* Flags tested local. */
2342 n = transform_node (n);
2344 /* Remove nodes with dead (Bad) input.
2345 Run always for transformation induced Bads. */
2348 /* Now we can verify the node, as it has no dead inputs any more. */
2351 /* Now we have a legal, useful node. Enter it in hash table for cse.
2352 Blocks should be unique anyways. (Except the successor of start:
2353 is cse with the start block!) */
2354 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2355 n = identify_remember (current_ir_graph->value_table, n);
2361 * Wrapper for external use, set proper status bits after optimization.
2364 optimize_in_place (ir_node *n)
2366 /* Handle graph state */
2367 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2369 if (get_opt_global_cse())
2370 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2371 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2372 set_irg_outs_inconsistent(current_ir_graph);
2374 /* Maybe we could also test whether optimizing the node can
2375 change the control graph. */
2376 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2377 set_irg_dom_inconsistent(current_ir_graph);
2378 return optimize_in_place_2 (n);
2382 * set the default ir op operations
2384 ir_op *firm_set_default_operations(ir_op *op)
2386 op = firm_set_default_computed_value(op);
2387 op = firm_set_default_equivalent_node(op);
2388 op = firm_set_default_transform_node(op);
2389 op = firm_set_default_node_cmp_attr(op);