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-2005 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 # include "opt_polymorphy.h"
45 /* Make types visible to allow most efficient access */
46 # include "entity_t.h"
49 * Trivial INLINEable routine for copy propagation.
50 * Does follow Ids, needed to optimize INLINEd code.
52 static INLINE ir_node *
53 follow_Id (ir_node *n)
55 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
60 * return the value of a Constant
62 static tarval *computed_value_Const(ir_node *n)
64 return get_Const_tarval(n);
68 * return the value of a 'sizeof' SymConst
70 static tarval *computed_value_SymConst(ir_node *n)
72 if ((get_SymConst_kind(n) == symconst_size) &&
73 (get_type_state(get_SymConst_type(n))) == layout_fixed)
74 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
79 * return the value of an Add
81 static tarval *computed_value_Add(ir_node *n)
83 ir_node *a = get_Add_left(n);
84 ir_node *b = get_Add_right(n);
86 tarval *ta = value_of(a);
87 tarval *tb = value_of(b);
89 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
90 return tarval_add(ta, tb);
96 * return the value of a Sub
99 static tarval *computed_value_Sub(ir_node *n)
101 ir_node *a = get_Sub_left(n);
102 ir_node *b = get_Sub_right(n);
107 if (a == b && !is_Bad(a))
108 return get_tarval_null(get_irn_mode(n));
113 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
114 return tarval_sub(ta, tb);
120 * return the value of an unary Minus
122 static tarval *computed_value_Minus(ir_node *n)
124 ir_node *a = get_Minus_op(n);
125 tarval *ta = value_of(a);
127 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
128 return tarval_neg(ta);
134 * return the value of a Mul
136 static tarval *computed_value_Mul(ir_node *n)
138 ir_node *a = get_Mul_left(n);
139 ir_node *b = get_Mul_right(n);
141 tarval *ta = value_of(a);
142 tarval *tb = value_of(b);
144 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
145 return tarval_mul(ta, tb);
147 /* a*0 = 0 or 0*b = 0:
148 calls computed_value recursive and returns the 0 with proper
150 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
152 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
159 * return the value of a floating point Quot
161 static tarval *computed_value_Quot(ir_node *n)
163 ir_node *a = get_Quot_left(n);
164 ir_node *b = get_Quot_right(n);
166 tarval *ta = value_of(a);
167 tarval *tb = value_of(b);
169 /* This was missing in original implementation. Why? */
170 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
171 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
172 return tarval_quo(ta, tb);
178 * calculate the value of an integer Div of two nodes
179 * Special case: 0 / b
181 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
183 tarval *ta = value_of(a);
184 tarval *tb = value_of(b);
186 /* Compute c1 / c2 or 0 / a, a != 0 */
187 if (ta != tarval_bad) {
188 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
189 return tarval_div(ta, tb);
190 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
197 * return the value of an integer Div
199 static tarval *computed_value_Div(ir_node *n)
201 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
205 * calculate the value of an integer Mod of two nodes
206 * Special case: a % 1
208 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
210 tarval *ta = value_of(a);
211 tarval *tb = value_of(b);
213 /* Compute c1 % c2 or a % 1 */
214 if (tb != tarval_bad) {
215 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
216 return tarval_mod(ta, tb);
217 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
218 return get_mode_null(get_irn_mode(a));
225 * return the value of an integer Mod
227 static tarval *computed_value_Mod(ir_node *n)
229 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
233 * return the value of an Abs
235 static tarval *computed_value_Abs(ir_node *n)
237 ir_node *a = get_Abs_op(n);
238 tarval *ta = value_of(a);
240 if (ta != tarval_bad)
241 return tarval_abs(ta);
247 * return the value of an And
248 * Special case: a & 0, 0 & b
250 static tarval *computed_value_And(ir_node *n)
252 ir_node *a = get_And_left(n);
253 ir_node *b = get_And_right(n);
255 tarval *ta = value_of(a);
256 tarval *tb = value_of(b);
258 if ((ta != tarval_bad) && (tb != tarval_bad)) {
259 return tarval_and (ta, tb);
263 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
264 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
272 * return the value of an Or
273 * Special case: a | 1...1, 1...1 | b
275 static tarval *computed_value_Or(ir_node *n)
277 ir_node *a = get_Or_left(n);
278 ir_node *b = get_Or_right(n);
280 tarval *ta = value_of(a);
281 tarval *tb = value_of(b);
283 if ((ta != tarval_bad) && (tb != tarval_bad)) {
284 return tarval_or (ta, tb);
287 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
288 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
296 * return the value of an Eor
298 static tarval *computed_value_Eor(ir_node *n)
300 ir_node *a = get_Eor_left(n);
301 ir_node *b = get_Eor_right(n);
306 return get_tarval_null(get_irn_mode(n));
311 if ((ta != tarval_bad) && (tb != tarval_bad)) {
312 return tarval_eor (ta, tb);
318 * return the value of a Not
320 static tarval *computed_value_Not(ir_node *n)
322 ir_node *a = get_Not_op(n);
323 tarval *ta = value_of(a);
325 if (ta != tarval_bad)
326 return tarval_not(ta);
332 * return the value of a Shl
334 static tarval *computed_value_Shl(ir_node *n)
336 ir_node *a = get_Shl_left(n);
337 ir_node *b = get_Shl_right(n);
339 tarval *ta = value_of(a);
340 tarval *tb = value_of(b);
342 if ((ta != tarval_bad) && (tb != tarval_bad)) {
343 return tarval_shl (ta, tb);
349 * return the value of a Shr
351 static tarval *computed_value_Shr(ir_node *n)
353 ir_node *a = get_Shr_left(n);
354 ir_node *b = get_Shr_right(n);
356 tarval *ta = value_of(a);
357 tarval *tb = value_of(b);
359 if ((ta != tarval_bad) && (tb != tarval_bad)) {
360 return tarval_shr (ta, tb);
366 * return the value of a Shrs
368 static tarval *computed_value_Shrs(ir_node *n)
370 ir_node *a = get_Shrs_left(n);
371 ir_node *b = get_Shrs_right(n);
373 tarval *ta = value_of(a);
374 tarval *tb = value_of(b);
376 if ((ta != tarval_bad) && (tb != tarval_bad)) {
377 return tarval_shrs (ta, tb);
383 * return the value of a Rot
385 static tarval *computed_value_Rot(ir_node *n)
387 ir_node *a = get_Rot_left(n);
388 ir_node *b = get_Rot_right(n);
390 tarval *ta = value_of(a);
391 tarval *tb = value_of(b);
393 if ((ta != tarval_bad) && (tb != tarval_bad)) {
394 return tarval_rot (ta, tb);
400 * return the value of a Conv
402 static tarval *computed_value_Conv(ir_node *n)
404 ir_node *a = get_Conv_op(n);
405 tarval *ta = value_of(a);
407 if (ta != tarval_bad)
408 return tarval_convert_to(ta, get_irn_mode(n));
414 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
416 static tarval *computed_value_Proj(ir_node *n)
418 ir_node *a = get_Proj_pred(n);
422 /* Optimize Cmp nodes.
423 This performs a first step of unreachable code elimination.
424 Proj can not be computed, but folding a Cmp above the Proj here is
425 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
427 There are several case where we can evaluate a Cmp node:
428 1. The nodes compared are both the same. If we compare for
429 equal, greater equal, ... this will return true, else it
430 will return false. This step relies on cse.
431 2. The predecessors of Cmp are target values. We can evaluate
433 3. The predecessors are Allocs or void* constants. Allocs never
434 return NULL, they raise an exception. Therefore we can predict
436 switch (get_irn_opcode(a)) {
438 aa = get_Cmp_left(a);
439 ab = get_Cmp_right(a);
440 proj_nr = get_Proj_proj(n);
443 !mode_is_float(get_irn_mode(aa)) || proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Gt)
445 /* BEWARE: a == a is NOT always True for floating Point!!! */
446 /* This is a trick with the bits used for encoding the Cmp
447 Proj numbers, the following statement is not the same:
448 return new_tarval_from_long (proj_nr == pn_Cmp_Eq, mode_b) */
449 return new_tarval_from_long (proj_nr & pn_Cmp_Eq, mode_b);
451 tarval *taa = value_of(aa);
452 tarval *tab = value_of(ab);
454 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
455 /* strange checks... */
456 pn_Cmp flags = tarval_cmp (taa, tab);
457 if (flags != pn_Cmp_False) {
458 return new_tarval_from_long (proj_nr & flags, mode_b);
460 } else { /* check for 3.: */
461 ir_node *aaa = skip_Id(skip_Proj(aa));
462 ir_node *aba = skip_Id(skip_Proj(ab));
464 if ( ( (/* aa is ProjP and aaa is Alloc */
465 (get_irn_op(aa) == op_Proj)
466 && (mode_is_reference(get_irn_mode(aa)))
467 && (get_irn_op(aaa) == op_Alloc))
468 && ( (/* ab is constant void */
469 (get_irn_op(ab) == op_Const)
470 && (mode_is_reference(get_irn_mode(ab)))
471 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
472 || (/* ab is other Alloc */
473 (get_irn_op(ab) == op_Proj)
474 && (mode_is_reference(get_irn_mode(ab)))
475 && (get_irn_op(aba) == op_Alloc)
477 || (/* aa is void and aba is Alloc */
478 (get_irn_op(aa) == op_Const)
479 && (mode_is_reference(get_irn_mode(aa)))
480 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
481 && (get_irn_op(ab) == op_Proj)
482 && (mode_is_reference(get_irn_mode(ab)))
483 && (get_irn_op(aba) == op_Alloc)))
485 return new_tarval_from_long (proj_nr & pn_Cmp_Ne, mode_b);
491 /* compute either the Div or the Mod part */
492 proj_nr = get_Proj_proj(n);
493 if (proj_nr == pn_DivMod_res_div)
494 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
495 else if (proj_nr == pn_DivMod_res_mod)
496 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
500 if (get_Proj_proj(n) == pn_Div_res)
501 return computed_value(a);
505 if (get_Proj_proj(n) == pn_Mod_res)
506 return computed_value(a);
516 * calculate the value of a Mux: can be evaluated, if the
517 * sel and the right input are known
519 static tarval *computed_value_Mux(ir_node *n)
521 ir_node *sel = get_Mux_sel(n);
522 tarval *ts = value_of(sel);
524 if (ts == get_tarval_b_true()) {
525 ir_node *v = get_Mux_true(n);
528 else if (ts == get_tarval_b_false()) {
529 ir_node *v = get_Mux_false(n);
536 * If the parameter n can be computed, return its value, else tarval_bad.
537 * Performs constant folding.
539 * @param n The node this should be evaluated
541 tarval *computed_value(ir_node *n)
543 if (n->op->computed_value)
544 return n->op->computed_value(n);
549 * set the default computed_value evaluator
551 static ir_op *firm_set_default_computed_value(ir_op *op)
555 op->computed_value = computed_value_##a; \
581 op->computed_value = NULL;
589 /* returns 1 if the a and b are pointers to different locations. */
591 different_identity (ir_node *a, ir_node *b)
593 assert (mode_is_reference(get_irn_mode (a))
594 && mode_is_reference(get_irn_mode (b)));
596 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
597 ir_node *a1 = get_Proj_pred (a);
598 ir_node *b1 = get_Proj_pred (b);
599 if (a1 != b1 && get_irn_op (a1) == op_Alloc
600 && get_irn_op (b1) == op_Alloc)
608 * Returns a equivalent block for another block.
609 * If the block has only one predecessor, this is
610 * the equivalent one. If the only predecessor of a block is
611 * the block itself, this is a dead block.
613 * If both predecessors of a block are the branches of a binary
614 * Cond, the equivalent block is Cond's block.
616 * If all predecessors of a block are bad or lies in a dead
617 * block, the current block is dead as well.
619 * Note, that blocks are NEVER turned into Bad's, instead
620 * the dead_block flag is set. So, never test for is_Bad(block),
621 * always use is_dead_Block(block).
623 static ir_node *equivalent_node_Block(ir_node *n)
626 int n_preds = get_Block_n_cfgpreds(n);
628 /* The Block constructor does not call optimize, but mature_immBlock
629 calls the optimization. */
630 assert(get_Block_matured(n));
632 /* Straightening: a single entry Block following a single exit Block
633 can be merged, if it is not the Start block. */
634 /* !!! Beware, all Phi-nodes of n must have been optimized away.
635 This should be true, as the block is matured before optimize is called.
636 But what about Phi-cycles with the Phi0/Id that could not be resolved?
637 Remaining Phi nodes are just Ids. */
638 if ((n_preds == 1) && (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
639 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
640 if (predblock == oldn) {
641 /* Jmp jumps into the block it is in -- deal self cycle. */
642 n = set_Block_dead(n);
643 DBG_OPT_DEAD(oldn, n);
644 } else if (get_opt_control_flow_straightening()) {
646 DBG_OPT_STG(oldn, n);
649 else if ((n_preds == 1) &&
650 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
651 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
652 if (predblock == oldn) {
653 /* Jmp jumps into the block it is in -- deal self cycle. */
654 n = set_Block_dead(n);
655 DBG_OPT_DEAD(oldn, n);
658 else if ((n_preds == 2) &&
659 (get_opt_control_flow_weak_simplification())) {
660 /* Test whether Cond jumps twice to this block
661 @@@ we could do this also with two loops finding two preds from several ones. */
662 ir_node *a = get_Block_cfgpred(n, 0);
663 ir_node *b = get_Block_cfgpred(n, 1);
665 if ((get_irn_op(a) == op_Proj) &&
666 (get_irn_op(b) == op_Proj) &&
667 (get_Proj_pred(a) == get_Proj_pred(b)) &&
668 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
669 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
670 /* Also a single entry Block following a single exit Block. Phis have
671 twice the same operand and will be optimized away. */
672 n = get_nodes_block(a);
673 DBG_OPT_IFSIM(oldn, a, b, n);
675 } else if (get_opt_unreachable_code() &&
676 (n != current_ir_graph->start_block) &&
677 (n != current_ir_graph->end_block) ) {
678 int i, n_cfg = get_Block_n_cfgpreds(n);
680 /* If all inputs are dead, this block is dead too, except if it is
681 the start or end block. This is a step of unreachable code
683 for (i = 0; i < n_cfg; i++) {
684 ir_node *pred = get_Block_cfgpred(n, i);
687 if (is_Bad(pred)) continue;
688 pred_blk = get_nodes_block(pred);
690 if (is_Block_dead(pred_blk)) continue;
693 /* really found a living input */
698 n = set_Block_dead(n);
705 * Returns a equivalent node for a Jmp, a Bad :-)
706 * Of course this only happens if the Block of the Jmp is Bad.
708 static ir_node *equivalent_node_Jmp(ir_node *n)
710 /* GL: Why not same for op_Raise?? */
711 /* unreachable code elimination */
712 if (is_Block_dead(get_nodes_block(n)))
718 static ir_node *equivalent_node_Cond(ir_node *n)
720 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
721 See cases for iro_Cond and iro_Proj in transform_node. */
726 * optimize operations that are commutative and have neutral 0,
727 * so a op 0 = 0 op a = a.
729 static ir_node *equivalent_node_neutral_zero(ir_node *n)
733 ir_node *a = get_binop_left(n);
734 ir_node *b = get_binop_right(n);
739 /* After running compute_node there is only one constant predecessor.
740 Find this predecessors value and remember the other node: */
741 if ((tv = value_of(a)) != tarval_bad) {
743 } else if ((tv = value_of(b)) != tarval_bad) {
748 /* If this predecessors constant value is zero, the operation is
749 unnecessary. Remove it: */
750 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
753 DBG_OPT_ALGSIM1(oldn, a, b, n);
759 #define equivalent_node_Add equivalent_node_neutral_zero
760 #define equivalent_node_Eor equivalent_node_neutral_zero
763 * optimize operations that are not commutative but have neutral 0 on left,
766 static ir_node *equivalent_node_left_zero(ir_node *n)
770 ir_node *a = get_binop_left(n);
771 ir_node *b = get_binop_right(n);
773 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
776 DBG_OPT_ALGSIM1(oldn, a, b, n);
782 #define equivalent_node_Sub equivalent_node_left_zero
783 #define equivalent_node_Shl equivalent_node_left_zero
784 #define equivalent_node_Shr equivalent_node_left_zero
785 #define equivalent_node_Shrs equivalent_node_left_zero
786 #define equivalent_node_Rot equivalent_node_left_zero
789 * Er, a "symmetic unop", ie op(op(n)) = n.
791 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
794 ir_node *pred = get_unop_op(n);
796 /* optimize symmetric unop */
797 if (get_irn_op(pred) == get_irn_op(n)) {
798 n = get_unop_op(pred);
799 DBG_OPT_ALGSIM2(oldn, pred, n);
805 #define equivalent_node_Not equivalent_node_symmetric_unop
807 /* --x == x */ /* ??? Is this possible or can --x raise an
808 out of bounds exception if min =! max? */
809 #define equivalent_node_Minus equivalent_node_symmetric_unop
812 * Optimize a * 1 = 1 * a = a.
814 static ir_node *equivalent_node_Mul(ir_node *n)
818 ir_node *a = get_Mul_left(n);
819 ir_node *b = get_Mul_right(n);
821 /* Mul is commutative and has again an other neutral element. */
822 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
824 DBG_OPT_ALGSIM1(oldn, a, b, n);
825 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
827 DBG_OPT_ALGSIM1(oldn, a, b, n);
833 * Optimize a / 1 = a.
835 static ir_node *equivalent_node_Div(ir_node *n)
837 ir_node *a = get_Div_left(n);
838 ir_node *b = get_Div_right(n);
840 /* Div is not commutative. */
841 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
842 /* Turn Div into a tuple (mem, bad, a) */
843 ir_node *mem = get_Div_mem(n);
844 turn_into_tuple(n, 3);
845 set_Tuple_pred(n, pn_Div_M, mem);
846 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
847 set_Tuple_pred(n, pn_Div_res, a);
853 * Optimize a / 1 = a.
855 static ir_node *equivalent_node_DivMod(ir_node *n)
857 ir_node *a = get_DivMod_left(n);
858 ir_node *b = get_DivMod_right(n);
860 /* Div is not commutative. */
861 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
862 /* Turn DivMod into a tuple (mem, bad, a, 0) */
863 ir_node *mem = get_Div_mem(n);
864 ir_mode *mode = get_irn_mode(b);
866 turn_into_tuple(n, 4);
867 set_Tuple_pred(n, pn_DivMod_M, mem);
868 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
869 set_Tuple_pred(n, pn_DivMod_res_div, a);
870 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
876 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
878 static ir_node *equivalent_node_Or(ir_node *n)
882 ir_node *a = get_Or_left(n);
883 ir_node *b = get_Or_right(n);
886 n = a; /* Or has it's own neutral element */
887 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
889 DBG_OPT_ALGSIM1(oldn, a, b, n);
890 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
892 DBG_OPT_ALGSIM1(oldn, a, b, n);
899 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
901 static ir_node *equivalent_node_And(ir_node *n)
905 ir_node *a = get_And_left(n);
906 ir_node *b = get_And_right(n);
909 n = a; /* And has it's own neutral element */
910 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
912 DBG_OPT_ALGSIM1(oldn, a, b, n);
913 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
915 DBG_OPT_ALGSIM1(oldn, a, b, n);
921 * Try to remove useless conv's:
923 static ir_node *equivalent_node_Conv(ir_node *n)
926 ir_node *a = get_Conv_op(n);
929 ir_mode *n_mode = get_irn_mode(n);
930 ir_mode *a_mode = get_irn_mode(a);
932 if (n_mode == a_mode) { /* No Conv necessary */
934 DBG_OPT_ALGSIM3(oldn, a, n);
935 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
939 n_mode = get_irn_mode(n);
940 b_mode = get_irn_mode(b);
942 if (n_mode == b_mode) {
943 if (n_mode == mode_b) {
944 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
945 DBG_OPT_ALGSIM1(oldn, a, b, n);
947 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
948 if (smaller_mode(b_mode, a_mode)){
949 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
950 DBG_OPT_ALGSIM1(oldn, a, b, n);
959 * A Cast may be removed if the type of the previous node
960 * is already to type of the Cast.
962 static ir_node *equivalent_node_Cast(ir_node *n) {
963 ir_node *pred = get_Cast_op(n);
964 if (get_irn_type(pred) == get_Cast_type(n))
969 /* Several optimizations:
970 - no Phi in start block.
971 - remove Id operators that are inputs to Phi
972 - fold Phi-nodes, iff they have only one predecessor except
975 static ir_node *equivalent_node_Phi(ir_node *n)
980 ir_node *block = NULL; /* to shutup gcc */
981 ir_node *first_val = NULL; /* to shutup gcc */
982 ir_node *scnd_val = NULL; /* to shutup gcc */
984 if (!get_opt_normalize()) return n;
986 n_preds = get_Phi_n_preds(n);
988 block = get_nodes_block(n);
989 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
990 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
991 if ((is_Block_dead(block)) || /* Control dead */
992 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
993 return new_Bad(); /* in the Start Block. */
995 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
998 /* first we test for a special case: */
999 /* Confirm is a special node fixing additional information for a
1000 value that is known at a certain point. This is useful for
1001 dataflow analysis. */
1003 ir_node *a = get_Phi_pred(n, 0);
1004 ir_node *b = get_Phi_pred(n, 1);
1005 if ( (get_irn_op(a) == op_Confirm)
1006 && (get_irn_op(b) == op_Confirm)
1007 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
1008 && (get_irn_n(a, 1) == get_irn_n (b, 1))
1009 && (a->data.num == (~b->data.num & irpn_True) )) {
1010 return get_irn_n(a, 0);
1015 /* If the Block has a Bad pred, we also have one. */
1016 for (i = 0; i < n_preds; ++i)
1017 if (is_Bad (get_Block_cfgpred(block, i)))
1018 set_Phi_pred(n, i, new_Bad());
1020 /* Find first non-self-referencing input */
1021 for (i = 0; i < n_preds; ++i) {
1022 first_val = get_Phi_pred(n, i);
1023 if ( (first_val != n) /* not self pointer */
1025 && (get_irn_op(first_val) != op_Bad)
1027 ) { /* value not dead */
1028 break; /* then found first value. */
1032 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1033 if (i >= n_preds) { return new_Bad(); }
1037 /* follow_Id () for rest of inputs, determine if any of these
1038 are non-self-referencing */
1039 while (++i < n_preds) {
1040 scnd_val = get_Phi_pred(n, i);
1041 if ( (scnd_val != n)
1042 && (scnd_val != first_val)
1044 && (get_irn_op(scnd_val) != op_Bad)
1051 /* Fold, if no multiple distinct non-self-referencing inputs */
1054 DBG_OPT_PHI(oldn, first_val, n);
1056 /* skip the remaining Ids (done in get_Phi_pred). */
1057 /* superfluous, since we walk all to propagate Block's Bads.
1058 while (++i < n_preds) get_Phi_pred(n, i); */
1064 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1066 static ir_node *equivalent_node_Proj(ir_node *n)
1070 ir_node *a = get_Proj_pred(n);
1072 if ( get_irn_op(a) == op_Tuple) {
1073 /* Remove the Tuple/Proj combination. */
1074 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1075 n = get_Tuple_pred(a, get_Proj_proj(n));
1076 DBG_OPT_TUPLE(oldn, a, n);
1078 assert(0); /* This should not happen! */
1081 } else if (get_irn_mode(n) == mode_X &&
1082 is_Block_dead(get_nodes_block(n))) {
1083 /* Remove dead control flow -- early gigo. */
1092 static ir_node *equivalent_node_Id(ir_node *n)
1097 DBG_OPT_ID(oldn, n);
1104 static ir_node *equivalent_node_Mux(ir_node *n)
1106 ir_node *oldn = n, *sel = get_Mux_sel(n);
1107 tarval *ts = value_of(sel);
1109 /* Mux(true, f, t) == t */
1110 if (ts == get_tarval_b_true()) {
1111 n = get_Mux_true(n);
1112 DBG_OPT_ALGSIM0(oldn, n);
1114 /* Mux(false, f, t) == f */
1115 else if (ts == get_tarval_b_false()) {
1116 n = get_Mux_false(n);
1117 DBG_OPT_ALGSIM0(oldn, n);
1119 /* Mux(v, x, x) == x */
1120 else if (get_Mux_false(n) == get_Mux_true(n)) {
1121 n = get_Mux_true(n);
1122 DBG_OPT_ALGSIM0(oldn, n);
1124 else if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(get_irn_mode(n))) {
1125 ir_node *cmp = get_Proj_pred(sel);
1126 long proj_nr = get_Proj_proj(sel);
1127 ir_node *b = get_Mux_false(n);
1128 ir_node *a = get_Mux_true(n);
1131 * Note: normalization puts the constant on the right site,
1132 * so we check only one case.
1134 * Note further that these optimization work even for floating point
1135 * with NaN's because -NaN == NaN.
1136 * However, if +0 and -0 is handled differently, we cannot use the first one.
1138 if (get_irn_op(cmp) == op_Cmp && get_Cmp_left(cmp) == a) {
1139 if (classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
1140 /* Mux(a CMP 0, X, a) */
1141 if (get_irn_op(b) == op_Minus && get_Minus_op(b) == a) {
1142 /* Mux(a CMP 0, -a, a) */
1143 if (proj_nr == pn_Cmp_Eq) {
1144 /* Mux(a == 0, -a, a) ==> -a */
1146 DBG_OPT_ALGSIM0(oldn, n);
1148 else if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1149 /* Mux(a != 0, -a, a) ==> a */
1151 DBG_OPT_ALGSIM0(oldn, n);
1154 else if (classify_Const(b) == CNST_NULL) {
1155 /* Mux(a CMP 0, 0, a) */
1156 if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1157 /* Mux(a != 0, 0, a) ==> a */
1159 DBG_OPT_ALGSIM0(oldn, n);
1161 else if (proj_nr == pn_Cmp_Eq) {
1162 /* Mux(a == 0, 0, a) ==> 0 */
1164 DBG_OPT_ALGSIM0(oldn, n);
1175 * Optimize -a CMP -b into b CMP a.
1176 * This works even for floating point
1178 static ir_node *equivalent_node_Cmp(ir_node *n)
1180 ir_node *left = get_Cmp_left(n);
1181 ir_node *right = get_Cmp_right(n);
1183 if (get_irn_op(left) == op_Minus && get_irn_op(right) == op_Minus) {
1184 left = get_Minus_op(left);
1185 right = get_Minus_op(right);
1186 set_Cmp_left(n, right);
1187 set_Cmp_right(n, left);
1193 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1194 * perform no actual computation, as, e.g., the Id nodes. It does not create
1195 * new nodes. It is therefore safe to free n if the node returned is not n.
1196 * If a node returns a Tuple we can not just skip it. If the size of the
1197 * in array fits, we transform n into a tuple (e.g., Div).
1200 equivalent_node(ir_node *n)
1202 if (n->op->equivalent_node)
1203 return n->op->equivalent_node(n);
1208 * set the default equivalent node operation
1210 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1214 op->equivalent_node = equivalent_node_##a; \
1243 op->equivalent_node = NULL;
1251 * Do node specific optimizations of nodes predecessors.
1254 optimize_preds(ir_node *n) {
1255 ir_node *a = NULL, *b = NULL;
1257 /* get the operands we will work on for simple cases. */
1259 a = get_binop_left(n);
1260 b = get_binop_right(n);
1261 } else if (is_unop(n)) {
1265 switch (get_irn_opcode(n)) {
1268 /* We don't want Cast as input to Cmp. */
1269 if (get_irn_op(a) == op_Cast) {
1273 if (get_irn_op(b) == op_Cast) {
1275 set_Cmp_right(n, b);
1284 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1285 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)).
1286 * If possible, remove the Conv's.
1288 static ir_node *transform_node_AddSub(ir_node *n)
1290 ir_mode *mode = get_irn_mode(n);
1292 if (mode_is_reference(mode)) {
1293 ir_node *left = get_binop_left(n);
1294 ir_node *right = get_binop_right(n);
1295 int ref_bits = get_mode_size_bits(mode);
1297 if (get_irn_op(left) == op_Conv) {
1298 ir_mode *mode = get_irn_mode(left);
1299 int bits = get_mode_size_bits(mode);
1301 if (ref_bits == bits &&
1302 mode_is_int(mode) &&
1303 get_mode_arithmetic(mode) == irma_twos_complement) {
1304 ir_node *pre = get_Conv_op(left);
1305 ir_mode *pre_mode = get_irn_mode(pre);
1307 if (mode_is_int(pre_mode) &&
1308 get_mode_size_bits(pre_mode) == bits &&
1309 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1310 /* ok, this conv just changes to sign, moreover the calculation
1311 * is done with same number of bits as our address mode, so
1312 * we can ignore the conv as address calculation can be viewed
1313 * as either signed or unsigned
1315 set_binop_left(n, pre);
1320 if (get_irn_op(right) == op_Conv) {
1321 ir_mode *mode = get_irn_mode(right);
1322 int bits = get_mode_size_bits(mode);
1324 if (ref_bits == bits &&
1325 mode_is_int(mode) &&
1326 get_mode_arithmetic(mode) == irma_twos_complement) {
1327 ir_node *pre = get_Conv_op(right);
1328 ir_mode *pre_mode = get_irn_mode(pre);
1330 if (mode_is_int(pre_mode) &&
1331 get_mode_size_bits(pre_mode) == bits &&
1332 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1333 /* ok, this conv just changes to sign, moreover the calculation
1334 * is done with same number of bits as our address mode, so
1335 * we can ignore the conv as address calculation can be viewed
1336 * as either signed or unsigned
1338 set_binop_right(n, pre);
1347 * Do the AddSub optimization, then Transform Add(a,a) into Mul(a, 2)
1348 * if the mode is integer or float.
1349 * Reassociation might fold this further.
1351 static ir_node *transform_node_Add(ir_node *n)
1356 n = transform_node_AddSub(n);
1358 mode = get_irn_mode(n);
1359 if (mode_is_num(mode)) {
1360 ir_node *a = get_Add_left(n);
1362 if (a == get_Add_right(n)) {
1363 ir_node *block = get_nodes_block(n);
1366 get_irn_dbg_info(n),
1370 new_r_Const_long(current_ir_graph, block, mode, 2),
1372 DBG_OPT_ALGSIM0(oldn, n);
1379 * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
1381 static ir_node *transform_node_Sub(ir_node *n)
1386 n = transform_node_AddSub(n);
1388 mode = get_irn_mode(n);
1389 if (mode_is_num(mode)) {
1390 if (classify_Const(get_Sub_left(n)) == CNST_NULL) {
1392 get_irn_dbg_info(n),
1397 DBG_OPT_ALGSIM0(oldn, n);
1404 /** Do architecture dependend optimizations on Mul nodes */
1405 static ir_node *transform_node_Mul(ir_node *n) {
1406 return arch_dep_replace_mul_with_shifts(n);
1410 * transform a Div Node
1412 static ir_node *transform_node_Div(ir_node *n)
1414 tarval *tv = value_of(n);
1417 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1419 if (tv != tarval_bad) {
1420 value = new_Const(get_tarval_mode(tv), tv);
1422 DBG_OPT_CSTEVAL(n, value);
1424 else /* Try architecture dependand optimization */
1425 value = arch_dep_replace_div_by_const(n);
1428 /* Turn Div into a tuple (mem, bad, value) */
1429 ir_node *mem = get_Div_mem(n);
1431 turn_into_tuple(n, 3);
1432 set_Tuple_pred(n, pn_Div_M, mem);
1433 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1434 set_Tuple_pred(n, pn_Div_res, value);
1440 * transform a Mod node
1442 static ir_node *transform_node_Mod(ir_node *n)
1444 tarval *tv = value_of(n);
1447 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1449 if (tv != tarval_bad) {
1450 value = new_Const(get_tarval_mode(tv), tv);
1452 DBG_OPT_CSTEVAL(n, value);
1454 else /* Try architecture dependand optimization */
1455 value = arch_dep_replace_mod_by_const(n);
1458 /* Turn Mod into a tuple (mem, bad, value) */
1459 ir_node *mem = get_Mod_mem(n);
1461 turn_into_tuple(n, 3);
1462 set_Tuple_pred(n, pn_Mod_M, mem);
1463 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1464 set_Tuple_pred(n, pn_Mod_res, value);
1470 * transform a DivMod node
1472 static ir_node *transform_node_DivMod(ir_node *n)
1476 ir_node *a = get_DivMod_left(n);
1477 ir_node *b = get_DivMod_right(n);
1478 ir_mode *mode = get_irn_mode(a);
1479 tarval *ta = value_of(a);
1480 tarval *tb = value_of(b);
1482 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1485 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1487 if (tb != tarval_bad) {
1488 if (tb == get_mode_one(get_tarval_mode(tb))) {
1489 b = new_Const (mode, get_mode_null(mode));
1492 DBG_OPT_CSTEVAL(n, b);
1494 else if (ta != tarval_bad) {
1495 tarval *resa, *resb;
1496 resa = tarval_div (ta, tb);
1497 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1498 Jmp for X result!? */
1499 resb = tarval_mod (ta, tb);
1500 if (resb == tarval_bad) return n; /* Causes exception! */
1501 a = new_Const (mode, resa);
1502 b = new_Const (mode, resb);
1505 DBG_OPT_CSTEVAL(n, a);
1506 DBG_OPT_CSTEVAL(n, b);
1508 else { /* Try architecture dependand optimization */
1509 arch_dep_replace_divmod_by_const(&a, &b, n);
1510 evaluated = a != NULL;
1512 } else if (ta == get_mode_null(mode)) {
1513 /* 0 / non-Const = 0 */
1518 if (evaluated) { /* replace by tuple */
1519 ir_node *mem = get_DivMod_mem(n);
1520 turn_into_tuple(n, 4);
1521 set_Tuple_pred(n, pn_DivMod_M, mem);
1522 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1523 set_Tuple_pred(n, pn_DivMod_res_div, a);
1524 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1525 assert(get_nodes_block(n));
1532 * transform a Cond node
1534 static ir_node *transform_node_Cond(ir_node *n)
1536 /* Replace the Cond by a Jmp if it branches on a constant
1539 ir_node *a = get_Cond_selector(n);
1540 tarval *ta = value_of(a);
1542 if ((ta != tarval_bad) &&
1543 (get_irn_mode(a) == mode_b) &&
1544 (get_opt_unreachable_code())) {
1545 /* It's a boolean Cond, branching on a boolean constant.
1546 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1547 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1548 turn_into_tuple(n, 2);
1549 if (ta == tarval_b_true) {
1550 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1551 set_Tuple_pred(n, pn_Cond_true, jmp);
1553 set_Tuple_pred(n, pn_Cond_false, jmp);
1554 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1556 /* We might generate an endless loop, so keep it alive. */
1557 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1558 } else if ((ta != tarval_bad) &&
1559 (get_irn_mode(a) == mode_Iu) &&
1560 (get_Cond_kind(n) == dense) &&
1561 (get_opt_unreachable_code())) {
1562 /* I don't want to allow Tuples smaller than the biggest Proj.
1563 Also this tuple might get really big...
1564 I generate the Jmp here, and remember it in link. Link is used
1565 when optimizing Proj. */
1566 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1567 /* We might generate an endless loop, so keep it alive. */
1568 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1569 } else if ((get_irn_op(a) == op_Eor)
1570 && (get_irn_mode(a) == mode_b)
1571 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1572 /* The Eor is a negate. Generate a new Cond without the negate,
1573 simulate the negate by exchanging the results. */
1574 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1576 } else if ((get_irn_op(a) == op_Not)
1577 && (get_irn_mode(a) == mode_b)) {
1578 /* A Not before the Cond. Generate a new Cond without the Not,
1579 simulate the Not by exchanging the results. */
1580 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1589 static ir_node *transform_node_Eor(ir_node *n)
1592 ir_node *a = get_Eor_left(n);
1593 ir_node *b = get_Eor_right(n);
1595 if ((get_irn_mode(n) == mode_b)
1596 && (get_irn_op(a) == op_Proj)
1597 && (get_irn_mode(a) == mode_b)
1598 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1599 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1600 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1601 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1602 mode_b, get_negated_pnc(get_Proj_proj(a)));
1604 DBG_OPT_ALGSIM0(oldn, n);
1606 else if ((get_irn_mode(n) == mode_b)
1607 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
1608 /* The Eor is a Not. Replace it by a Not. */
1609 /* ????!!!Extend to bitfield 1111111. */
1610 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1612 DBG_OPT_ALGSIM0(oldn, n);
1619 * Transform a boolean Not.
1621 static ir_node *transform_node_Not(ir_node *n)
1624 ir_node *a = get_Not_op(n);
1626 if ( (get_irn_mode(n) == mode_b)
1627 && (get_irn_op(a) == op_Proj)
1628 && (get_irn_mode(a) == mode_b)
1629 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1630 /* We negate a Cmp. The Cmp has the negated result anyways! */
1631 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1632 mode_b, get_negated_pnc(get_Proj_proj(a)));
1633 DBG_OPT_ALGSIM0(oldn, n);
1640 * Transform a Cast of a Const into a new Const
1642 static ir_node *transform_node_Cast(ir_node *n) {
1644 ir_node *pred = get_Cast_op(n);
1645 type *tp = get_irn_type(pred);
1647 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1648 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1649 get_Const_tarval(pred), tp);
1650 DBG_OPT_CSTEVAL(oldn, n);
1651 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1652 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1653 get_SymConst_kind(pred), tp);
1654 DBG_OPT_CSTEVAL(oldn, n);
1660 * Does all optimizations on nodes that must be done on it's Proj's
1661 * because of creating new nodes.
1663 * Transform a Div/Mod/DivMod with a non-zero constant.
1664 * Removes the exceptions and routes the memory to the NoMem node.
1666 * Optimizes jump tables by removing all impossible cases.
1668 * Normalizes and optimizes Cmp nodes.
1670 static ir_node *transform_node_Proj(ir_node *proj)
1672 ir_node *n = get_Proj_pred(proj);
1677 switch (get_irn_opcode(n)) {
1679 b = get_Div_right(n);
1682 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1683 proj_nr = get_Proj_proj(proj);
1685 /* this node may float */
1686 set_irn_pinned(n, op_pin_state_floats);
1688 if (proj_nr == pn_Div_X_except) {
1689 /* we found an exception handler, remove it */
1692 /* the memory Proj can be removed */
1693 ir_node *res = get_Div_mem(n);
1694 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1695 if (proj_nr == pn_Div_M)
1701 b = get_Mod_right(n);
1704 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1705 proj_nr = get_Proj_proj(proj);
1707 /* this node may float */
1708 set_irn_pinned(n, op_pin_state_floats);
1710 if (proj_nr == pn_Mod_X_except) {
1711 /* we found an exception handler, remove it */
1714 /* the memory Proj can be removed */
1715 ir_node *res = get_Mod_mem(n);
1716 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1717 if (proj_nr == pn_Mod_M)
1723 b = get_DivMod_right(n);
1726 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1727 proj_nr = get_Proj_proj(proj);
1729 /* this node may float */
1730 set_irn_pinned(n, op_pin_state_floats);
1732 if (proj_nr == pn_DivMod_X_except) {
1733 /* we found an exception handler, remove it */
1737 /* the memory Proj can be removed */
1738 ir_node *res = get_DivMod_mem(n);
1739 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1740 if (proj_nr == pn_DivMod_M)
1747 if (get_opt_unreachable_code()) {
1748 b = get_Cond_selector(n);
1751 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1752 /* we have a constant switch */
1753 long num = get_Proj_proj(proj);
1755 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1756 if (get_tarval_long(tb) == num) {
1757 /* Do NOT create a jump here, or we will have 2 control flow ops
1758 * in a block. This case is optimized away in optimize_cf(). */
1769 if (get_opt_reassociation()) {
1770 ir_node *left = get_Cmp_left(n);
1771 ir_node *right = get_Cmp_right(n);
1775 ir_mode *mode = NULL;
1777 proj_nr = get_Proj_proj(proj);
1780 * First step: normalize the compare op
1781 * by placing the constant on the right site
1782 * or moving the lower address node to the left.
1783 * We ignore the case that both are constants, then
1784 * this compare should be optimized away.
1786 if (get_irn_op(right) == op_Const)
1788 else if (get_irn_op(left) == op_Const) {
1793 proj_nr = get_swapped_pnc(proj_nr);
1796 else if (left > right) {
1802 proj_nr = get_swapped_pnc(proj_nr);
1807 * Second step: Try to reduce the magnitude
1808 * of a constant. This may help to generate better code
1809 * later and may help to normalize more compares.
1810 * Of course this is only possible for integer values.
1813 mode = get_irn_mode(c);
1814 tv = get_Const_tarval(c);
1816 if (tv != tarval_bad) {
1817 /* the following optimization is possibe on floating point values only:
1818 * -a CMP c ==> a swap(CMP) -c
1820 * Beware: for two-complement it is NOT true, see this:
1821 * -MININT < 0 =/=> MININT > 0 !!!
1823 if (mode_is_float(mode) && get_opt_constant_folding() && get_irn_op(left) == op_Minus) {
1824 left = get_Minus_op(left);
1825 tv = tarval_sub(get_tarval_null(mode), tv);
1827 proj_nr = get_swapped_pnc(proj_nr);
1831 /* for integer modes, we have more */
1832 if (mode_is_int(mode)) {
1833 /* Ne includes Unordered which is not possible on integers.
1834 * However, frontends often use this wrong, so fix it here */
1835 if (proj_nr == pn_Cmp_Ne)
1836 proj_nr = pn_Cmp_Lg;
1838 /* c > 0 : a < c ==> a <= (c-1) a >= c ==> a > (c-1) */
1839 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
1840 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Gt) {
1841 tv = tarval_sub(tv, get_tarval_one(mode));
1843 proj_nr ^= pn_Cmp_Eq;
1846 /* c < 0 : a > c ==> a >= (c+1) a <= c ==> a < (c+1) */
1847 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
1848 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Lt) {
1849 tv = tarval_add(tv, get_tarval_one(mode));
1851 proj_nr ^= pn_Cmp_Eq;
1855 /* the following reassociations work only for == and != */
1857 /* a-b == 0 ==> a == b, a-b != 0 ==> a != b */
1858 if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
1859 if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
1860 right = get_Sub_right(left);
1861 left = get_Sub_left(left);
1863 tv = value_of(right);
1868 if (tv != tarval_bad) {
1869 ir_op *op = get_irn_op(left);
1871 /* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */
1873 ir_node *c1 = get_Sub_right(left);
1874 tarval *tv2 = value_of(c1);
1876 if (tv2 != tarval_bad) {
1877 tv2 = tarval_add(tv, value_of(c1));
1879 if (tv2 != tarval_bad) {
1880 left = get_Sub_left(left);
1886 /* a+c1 == c2 ==> a == c2-c1, a+c1 != c2 ==> a != c2-c1 */
1887 else if (op == op_Add) {
1888 ir_node *a_l = get_Add_left(left);
1889 ir_node *a_r = get_Add_right(left);
1893 if (get_irn_op(a_l) == op_Const) {
1895 tv2 = value_of(a_l);
1899 tv2 = value_of(a_r);
1902 if (tv2 != tarval_bad) {
1903 tv2 = tarval_sub(tv, tv2);
1905 if (tv2 != tarval_bad) {
1918 ir_node *block = get_nodes_block(n);
1920 if (changed & 2) /* need a new Const */
1921 right = new_Const(mode, tv);
1923 /* create a new compare */
1924 n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
1927 set_Proj_pred(proj, n);
1928 set_Proj_proj(proj, proj_nr);
1934 /* should not happen, but if it does will be optimized away */
1942 /* we have added a Tuple, optimize it for the current Proj away */
1943 return equivalent_node_Proj(proj);
1947 * returns the operands of a commutative bin-op, if one operand is
1948 * a const, it is returned as the second one.
1950 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1952 ir_node *op_a = get_binop_left(binop);
1953 ir_node *op_b = get_binop_right(binop);
1955 assert(is_op_commutative(get_irn_op(binop)));
1957 if (get_irn_op(op_a) == op_Const) {
1968 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1969 * Such pattern may arise in bitfield stores.
1971 * value c4 value c4 & c2
1972 * AND c3 AND c1 | c3
1977 static ir_node *transform_node_Or_bf_store(ir_node *or)
1981 ir_node *and_l, *c3;
1982 ir_node *value, *c4;
1983 ir_node *new_and, *new_const, *block;
1984 ir_mode *mode = get_irn_mode(or);
1986 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1988 get_comm_Binop_Ops(or, &and, &c1);
1989 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1992 get_comm_Binop_Ops(and, &or_l, &c2);
1993 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1996 get_comm_Binop_Ops(or_l, &and_l, &c3);
1997 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2000 get_comm_Binop_Ops(and_l, &value, &c4);
2001 if (get_irn_op(c4) != op_Const)
2004 /* ok, found the pattern, check for conditions */
2005 assert(mode == get_irn_mode(and));
2006 assert(mode == get_irn_mode(or_l));
2007 assert(mode == get_irn_mode(and_l));
2009 tv1 = get_Const_tarval(c1);
2010 tv2 = get_Const_tarval(c2);
2011 tv3 = get_Const_tarval(c3);
2012 tv4 = get_Const_tarval(c4);
2014 tv = tarval_or(tv4, tv2);
2015 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2016 /* have at least one 0 at the same bit position */
2020 n_tv4 = tarval_not(tv4);
2021 if (tv3 != tarval_and(tv3, n_tv4)) {
2022 /* bit in the or_mask is outside the and_mask */
2026 n_tv2 = tarval_not(tv2);
2027 if (tv1 != tarval_and(tv1, n_tv2)) {
2028 /* bit in the or_mask is outside the and_mask */
2032 /* ok, all conditions met */
2033 block = get_nodes_block(or);
2035 new_and = new_r_And(current_ir_graph, block,
2036 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
2038 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
2040 set_Or_left(or, new_and);
2041 set_Or_right(or, new_const);
2043 /* check for more */
2044 return transform_node_Or_bf_store(or);
2048 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
2050 static ir_node *transform_node_Or_Rot(ir_node *or)
2052 ir_mode *mode = get_irn_mode(or);
2053 ir_node *shl, *shr, *block;
2054 ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
2057 if (! mode_is_int(mode))
2060 shl = get_binop_left(or);
2061 shr = get_binop_right(or);
2063 if (get_irn_op(shl) == op_Shr) {
2064 if (get_irn_op(shr) != op_Shl)
2071 else if (get_irn_op(shl) != op_Shl)
2073 else if (get_irn_op(shr) != op_Shr)
2076 x = get_Shl_left(shl);
2077 if (x != get_Shr_left(shr))
2080 c1 = get_Shl_right(shl);
2081 c2 = get_Shr_right(shr);
2082 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
2083 tv1 = get_Const_tarval(c1);
2084 if (! tarval_is_long(tv1))
2087 tv2 = get_Const_tarval(c2);
2088 if (! tarval_is_long(tv2))
2091 if (get_tarval_long(tv1) + get_tarval_long(tv2)
2092 != get_mode_size_bits(mode))
2095 /* yet, condition met */
2096 block = get_nodes_block(or);
2098 n = new_r_Rot(current_ir_graph, block, x, c1, mode);
2100 DBG_OPT_ALGSIM1(or, shl, shr, n);
2103 else if (get_irn_op(c1) == op_Sub) {
2107 if (get_Sub_right(sub) != v)
2110 c1 = get_Sub_left(sub);
2111 if (get_irn_op(c1) != op_Const)
2114 tv1 = get_Const_tarval(c1);
2115 if (! tarval_is_long(tv1))
2118 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2121 /* yet, condition met */
2122 block = get_nodes_block(or);
2124 /* a Rot right is not supported, so use a rot left */
2125 n = new_r_Rot(current_ir_graph, block, x, sub, mode);
2127 DBG_OPT_ALGSIM0(or, n);
2130 else if (get_irn_op(c2) == op_Sub) {
2134 c1 = get_Sub_left(sub);
2135 if (get_irn_op(c1) != op_Const)
2138 tv1 = get_Const_tarval(c1);
2139 if (! tarval_is_long(tv1))
2142 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2145 /* yet, condition met */
2146 block = get_nodes_block(or);
2149 n = new_r_Rot(current_ir_graph, block, x, v, mode);
2151 DBG_OPT_ALGSIM0(or, n);
2161 static ir_node *transform_node_Or(ir_node *or)
2163 or = transform_node_Or_bf_store(or);
2164 or = transform_node_Or_Rot(or);
2170 static ir_node *transform_node(ir_node *n);
2173 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
2175 static ir_node *transform_node_shift(ir_node *n)
2177 ir_node *left, *right;
2178 tarval *tv1, *tv2, *res;
2180 int modulo_shf, flag;
2182 left = get_binop_left(n);
2184 /* different operations */
2185 if (get_irn_op(left) != get_irn_op(n))
2188 right = get_binop_right(n);
2189 tv1 = value_of(right);
2190 if (tv1 == tarval_bad)
2193 tv2 = value_of(get_binop_right(left));
2194 if (tv2 == tarval_bad)
2197 res = tarval_add(tv1, tv2);
2199 /* beware: a simple replacement works only, if res < modulo shift */
2200 mode = get_irn_mode(n);
2204 modulo_shf = get_mode_modulo_shift(mode);
2205 if (modulo_shf > 0) {
2206 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
2208 if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
2215 /* ok, we can replace it */
2216 ir_node *in[2], *irn, *block = get_nodes_block(n);
2218 in[0] = get_binop_left(left);
2219 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
2221 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
2223 DBG_OPT_ALGSIM0(n, irn);
2225 return transform_node(irn);
2230 #define transform_node_Shr transform_node_shift
2231 #define transform_node_Shrs transform_node_shift
2232 #define transform_node_Shl transform_node_shift
2235 * Remove dead blocks in keepalive list. We do not generate a new End node.
2237 static ir_node *transform_node_End(ir_node *n) {
2238 int i, n_keepalives = get_End_n_keepalives(n);
2240 for (i = 0; i < n_keepalives; ++i) {
2241 ir_node *ka = get_End_keepalive(n, i);
2242 if (is_Block(ka) && is_Block_dead(ka))
2243 set_End_keepalive(n, i, new_Bad());
2249 * Optimize a Mux into some simplier cases
2251 static ir_node *transform_node_Mux(ir_node *n)
2253 ir_node *oldn = n, *sel = get_Mux_sel(n);
2254 ir_mode *mode = get_irn_mode(n);
2256 if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
2257 ir_node *cmp = get_Proj_pred(sel);
2258 long proj_nr = get_Proj_proj(sel);
2259 ir_node *f = get_Mux_false(n);
2260 ir_node *t = get_Mux_true(n);
2262 if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
2263 ir_node *block = get_nodes_block(n);
2266 * Note: normalization puts the constant on the right site,
2267 * so we check only one case.
2269 * Note further that these optimization work even for floating point
2270 * with NaN's because -NaN == NaN.
2271 * However, if +0 and -0 is handled differently, we cannot use the first one.
2273 if (get_irn_op(f) == op_Minus &&
2274 get_Minus_op(f) == t &&
2275 get_Cmp_left(cmp) == t) {
2277 if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2278 /* Mux(a >=/> 0, -a, a) ==> Abs(a) */
2279 n = new_rd_Abs(get_irn_dbg_info(n),
2283 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2286 else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2287 /* Mux(a <=/< 0, -a, a) ==> Minus(Abs(a)) */
2288 n = new_rd_Abs(get_irn_dbg_info(n),
2292 n = new_rd_Minus(get_irn_dbg_info(n),
2297 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2301 else if (get_irn_op(t) == op_Minus &&
2302 get_Minus_op(t) == f &&
2303 get_Cmp_left(cmp) == f) {
2305 if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2306 /* Mux(a <=/< 0, a, -a) ==> Abs(a) */
2307 n = new_rd_Abs(get_irn_dbg_info(n),
2311 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2314 else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2315 /* Mux(a >=/> 0, a, -a) ==> Minus(Abs(a)) */
2316 n = new_rd_Abs(get_irn_dbg_info(n),
2320 n = new_rd_Minus(get_irn_dbg_info(n),
2325 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2330 if (mode_is_int(mode) && mode_is_signed(mode) &&
2331 get_mode_arithmetic(mode) == irma_twos_complement) {
2332 /* the following optimization works only with signed integer two-complement mode */
2334 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
2335 classify_Const(t) == CNST_ALL_ONE &&
2336 classify_Const(f) == CNST_NULL) {
2338 * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
2342 n = new_rd_Shrs(get_irn_dbg_info(n),
2343 current_ir_graph, block, get_Cmp_left(cmp),
2344 new_r_Const_long(current_ir_graph, block, mode_Iu,
2345 get_mode_size_bits(mode) - 1),
2347 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2350 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
2351 classify_Const(t) == CNST_ONE &&
2352 classify_Const(f) == CNST_NULL) {
2354 * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
2358 n = new_rd_Shr(get_irn_dbg_info(n),
2359 current_ir_graph, block,
2360 new_r_Minus(current_ir_graph, block,
2361 get_Cmp_left(cmp), mode),
2362 new_r_Const_long(current_ir_graph, block, mode_Iu,
2363 get_mode_size_bits(mode) - 1),
2365 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2371 return arch_transform_node_Mux(n);
2375 * Tries several [inplace] [optimizing] transformations and returns an
2376 * equivalent node. The difference to equivalent_node() is that these
2377 * transformations _do_ generate new nodes, and thus the old node must
2378 * not be freed even if the equivalent node isn't the old one.
2380 static ir_node *transform_node(ir_node *n)
2382 if (n->op->transform_node)
2383 n = n->op->transform_node(n);
2388 * set the default transform node operation
2390 static ir_op *firm_set_default_transform_node(ir_op *op)
2394 op->transform_node = transform_node_##a; \
2417 op->transform_node = NULL;
2425 /* **************** Common Subexpression Elimination **************** */
2427 /** The size of the hash table used, should estimate the number of nodes
2429 #define N_IR_NODES 512
2431 /** Compares the attributes of two Const nodes. */
2432 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2434 return (get_Const_tarval(a) != get_Const_tarval(b))
2435 || (get_Const_type(a) != get_Const_type(b));
2438 /** Compares the attributes of two Proj nodes. */
2439 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2441 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2444 /** Compares the attributes of two Filter nodes. */
2445 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2447 return get_Filter_proj(a) != get_Filter_proj(b);
2450 /** Compares the attributes of two Alloc nodes. */
2451 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2453 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2454 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2457 /** Compares the attributes of two Free nodes. */
2458 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2460 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2461 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2464 /** Compares the attributes of two SymConst nodes. */
2465 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2467 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2468 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2469 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2472 /** Compares the attributes of two Call nodes. */
2473 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2475 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2478 /** Compares the attributes of two Sel nodes. */
2479 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2481 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2482 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2483 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2484 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2485 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2488 /** Compares the attributes of two Phi nodes. */
2489 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2491 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2494 /** Compares the attributes of two Cast nodes. */
2495 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2497 return get_Cast_type(a) != get_Cast_type(b);
2500 /** Compares the attributes of two Load nodes. */
2501 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2503 if (get_Load_volatility(a) == volatility_is_volatile ||
2504 get_Load_volatility(b) == volatility_is_volatile)
2505 /* NEVER do CSE on volatile Loads */
2508 return get_Load_mode(a) != get_Load_mode(b);
2511 /** Compares the attributes of two Store nodes. */
2512 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2514 /* NEVER do CSE on volatile Stores */
2515 return (get_Store_volatility(a) == volatility_is_volatile ||
2516 get_Store_volatility(b) == volatility_is_volatile);
2520 * set the default node attribute compare operation
2522 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2526 op->node_cmp_attr = node_cmp_attr_##a; \
2543 op->node_cmp_attr = NULL;
2551 * Compare function for two nodes in the hash table. Gets two
2552 * nodes as parameters. Returns 0 if the nodes are a cse.
2555 vt_cmp (const void *elt, const void *key)
2563 if (a == b) return 0;
2565 if ((get_irn_op(a) != get_irn_op(b)) ||
2566 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2568 /* compare if a's in and b's in are of equal length */
2569 irn_arity_a = get_irn_intra_arity (a);
2570 if (irn_arity_a != get_irn_intra_arity(b))
2573 /* for block-local cse and op_pin_state_pinned nodes: */
2574 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2575 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2579 /* compare a->in[0..ins] with b->in[0..ins] */
2580 for (i = 0; i < irn_arity_a; i++)
2581 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2585 * here, we already now that the nodes are identical except their
2588 if (a->op->node_cmp_attr)
2589 return a->op->node_cmp_attr(a, b);
2595 * Calculate a hash value of a node.
2598 ir_node_hash (ir_node *node)
2603 if (node->op == op_Const) {
2604 /* special value for const, as they only differ in their tarval. */
2605 h = HASH_PTR(node->attr.con.tv);
2606 h = 9*h + HASH_PTR(get_irn_mode(node));
2607 } else if (node->op == op_SymConst) {
2608 /* special value for const, as they only differ in their symbol. */
2609 h = HASH_PTR(node->attr.i.sym.type_p);
2610 h = 9*h + HASH_PTR(get_irn_mode(node));
2613 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2614 h = irn_arity = get_irn_intra_arity(node);
2616 /* consider all in nodes... except the block if not a control flow. */
2617 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2618 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2622 h = 9*h + HASH_PTR(get_irn_mode(node));
2624 h = 9*h + HASH_PTR(get_irn_op(node));
2631 new_identities(void) {
2632 return new_pset(vt_cmp, N_IR_NODES);
2636 del_identities(pset *value_table) {
2637 del_pset(value_table);
2641 * Return the canonical node computing the same value as n.
2642 * Looks up the node in a hash table.
2644 * For Const nodes this is performed in the constructor, too. Const
2645 * nodes are extremely time critical because of their frequent use in
2646 * constant string arrays.
2648 static INLINE ir_node *
2649 identify (pset *value_table, ir_node *n)
2653 if (!value_table) return n;
2655 if (get_opt_reassociation()) {
2656 if (is_op_commutative(get_irn_op(n))) {
2657 ir_node *l = get_binop_left(n);
2658 ir_node *r = get_binop_right(n);
2660 /* for commutative operators perform a OP b == b OP a */
2662 set_binop_left(n, r);
2663 set_binop_right(n, l);
2668 o = pset_find (value_table, n, ir_node_hash (n));
2677 * During construction we set the op_pin_state_pinned flag in the graph right when the
2678 * optimization is performed. The flag turning on procedure global cse could
2679 * be changed between two allocations. This way we are safe.
2681 static INLINE ir_node *
2682 identify_cons (pset *value_table, ir_node *n) {
2685 n = identify(value_table, n);
2686 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2687 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2692 * Return the canonical node computing the same value as n.
2693 * Looks up the node in a hash table, enters it in the table
2694 * if it isn't there yet.
2697 identify_remember (pset *value_table, ir_node *n)
2701 if (!value_table) return n;
2703 if (get_opt_reassociation()) {
2704 if (is_op_commutative(get_irn_op(n))) {
2705 ir_node *l = get_binop_left(n);
2706 ir_node *r = get_binop_right(n);
2708 /* for commutative operators perform a OP b == b OP a */
2710 set_binop_left(n, r);
2711 set_binop_right(n, l);
2716 /* lookup or insert in hash table with given hash key. */
2717 o = pset_insert (value_table, n, ir_node_hash (n));
2727 add_identities (pset *value_table, ir_node *node) {
2728 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2729 identify_remember (value_table, node);
2733 * garbage in, garbage out. If a node has a dead input, i.e., the
2734 * Bad node is input to the node, return the Bad node.
2736 static INLINE ir_node *
2737 gigo (ir_node *node)
2740 ir_op* op = get_irn_op(node);
2742 /* remove garbage blocks by looking at control flow that leaves the block
2743 and replacing the control flow by Bad. */
2744 if (get_irn_mode(node) == mode_X) {
2745 ir_node *block = get_nodes_block(node);
2746 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2747 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2749 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2750 irn_arity = get_irn_arity(block);
2751 for (i = 0; i < irn_arity; i++) {
2752 if (!is_Bad(get_irn_n(block, i))) break;
2754 if (i == irn_arity) return new_Bad();
2758 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2759 blocks predecessors is dead. */
2760 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2761 irn_arity = get_irn_arity(node);
2763 if (is_Block_dead(get_nodes_block(node)))
2766 for (i = 0; i < irn_arity; i++) {
2767 if (is_Bad(get_irn_n(node, i))) {
2773 /* With this code we violate the agreement that local_optimize
2774 only leaves Bads in Block, Phi and Tuple nodes. */
2775 /* If Block has only Bads as predecessors it's garbage. */
2776 /* If Phi has only Bads as predecessors it's garbage. */
2777 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2778 irn_arity = get_irn_arity(node);
2779 for (i = 0; i < irn_arity; i++) {
2780 if (!is_Bad(get_irn_n(node, i))) break;
2782 if (i == irn_arity) node = new_Bad();
2790 * These optimizations deallocate nodes from the obstack.
2791 * It can only be called if it is guaranteed that no other nodes
2792 * reference this one, i.e., right after construction of a node.
2795 optimize_node (ir_node *n)
2799 opcode iro = get_irn_opcode(n);
2801 type *old_tp = get_irn_type(n);
2803 int i, arity = get_irn_arity(n);
2804 for (i = 0; i < arity && !old_tp; ++i)
2805 old_tp = get_irn_type(get_irn_n(n, i));
2808 /* Always optimize Phi nodes: part of the construction. */
2809 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2811 /* constant expression evaluation / constant folding */
2812 if (get_opt_constant_folding()) {
2813 /* constants can not be evaluated */
2814 if (iro != iro_Const) {
2815 /* try to evaluate */
2816 tv = computed_value(n);
2817 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2821 * we MUST copy the node here temporary, because it's still needed
2822 * for DBG_OPT_CSTEVAL
2824 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2825 oldn = alloca(node_size);
2827 memcpy(oldn, n, node_size);
2828 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2830 /* ARG, copy the in array, we need it for statistics */
2831 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2834 edges_node_deleted(n, current_ir_graph);
2836 /* evaluation was successful -- replace the node. */
2837 obstack_free (current_ir_graph->obst, n);
2838 nw = new_Const (get_tarval_mode (tv), tv);
2840 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2841 set_Const_type(nw, old_tp);
2842 DBG_OPT_CSTEVAL(oldn, nw);
2848 /* remove unnecessary nodes */
2849 if (get_opt_constant_folding() ||
2850 (iro == iro_Phi) || /* always optimize these nodes. */
2852 (iro == iro_Proj) ||
2853 (iro == iro_Block) ) /* Flags tested local. */
2854 n = equivalent_node (n);
2856 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2858 /** common subexpression elimination **/
2859 /* Checks whether n is already available. */
2860 /* The block input is used to distinguish different subexpressions. Right
2861 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2862 subexpressions within a block. */
2864 n = identify_cons (current_ir_graph->value_table, n);
2867 edges_node_deleted(oldn, current_ir_graph);
2869 /* We found an existing, better node, so we can deallocate the old node. */
2870 obstack_free (current_ir_graph->obst, oldn);
2875 /* Some more constant expression evaluation that does not allow to
2877 iro = get_irn_opcode(n);
2878 if (get_opt_constant_folding() ||
2879 (iro == iro_Cond) ||
2880 (iro == iro_Proj) ||
2881 (iro == iro_Sel)) /* Flags tested local. */
2882 n = transform_node (n);
2884 /* Remove nodes with dead (Bad) input.
2885 Run always for transformation induced Bads. */
2888 /* Now we have a legal, useful node. Enter it in hash table for cse */
2889 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2890 n = identify_remember (current_ir_graph->value_table, n);
2898 * These optimizations never deallocate nodes (in place). This can cause dead
2899 * nodes lying on the obstack. Remove these by a dead node elimination,
2900 * i.e., a copying garbage collection.
2903 optimize_in_place_2 (ir_node *n)
2907 opcode iro = get_irn_opcode(n);
2909 type *old_tp = get_irn_type(n);
2911 int i, arity = get_irn_arity(n);
2912 for (i = 0; i < arity && !old_tp; ++i)
2913 old_tp = get_irn_type(get_irn_n(n, i));
2916 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2918 /* if not optimize return n */
2921 /* Here this is possible. Why? */
2925 /* constant expression evaluation / constant folding */
2926 if (get_opt_constant_folding()) {
2927 /* constants can not be evaluated */
2928 if (iro != iro_Const) {
2929 /* try to evaluate */
2930 tv = computed_value(n);
2931 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2932 /* evaluation was successful -- replace the node. */
2933 n = new_Const (get_tarval_mode (tv), tv);
2935 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2936 set_Const_type(n, old_tp);
2938 DBG_OPT_CSTEVAL(oldn, n);
2944 /* remove unnecessary nodes */
2945 if (get_opt_constant_folding() ||
2946 (iro == iro_Phi) || /* always optimize these nodes. */
2947 (iro == iro_Id) || /* ... */
2948 (iro == iro_Proj) || /* ... */
2949 (iro == iro_Block) ) /* Flags tested local. */
2950 n = equivalent_node (n);
2952 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2954 /** common subexpression elimination **/
2955 /* Checks whether n is already available. */
2956 /* The block input is used to distinguish different subexpressions. Right
2957 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2958 subexpressions within a block. */
2959 if (get_opt_cse()) {
2960 n = identify (current_ir_graph->value_table, n);
2963 /* Some more constant expression evaluation. */
2964 iro = get_irn_opcode(n);
2965 if (get_opt_constant_folding() ||
2966 (iro == iro_Cond) ||
2967 (iro == iro_Proj) ||
2968 (iro == iro_Sel)) /* Flags tested local. */
2969 n = transform_node (n);
2971 /* Remove nodes with dead (Bad) input.
2972 Run always for transformation induced Bads. */
2975 /* Now we can verify the node, as it has no dead inputs any more. */
2978 /* Now we have a legal, useful node. Enter it in hash table for cse.
2979 Blocks should be unique anyways. (Except the successor of start:
2980 is cse with the start block!) */
2981 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2982 n = identify_remember (current_ir_graph->value_table, n);
2988 * Wrapper for external use, set proper status bits after optimization.
2991 optimize_in_place (ir_node *n)
2993 /* Handle graph state */
2994 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2996 if (get_opt_global_cse())
2997 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2998 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2999 set_irg_outs_inconsistent(current_ir_graph);
3001 /* Maybe we could also test whether optimizing the node can
3002 change the control graph. */
3003 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
3004 set_irg_dom_inconsistent(current_ir_graph);
3005 return optimize_in_place_2 (n);
3009 * set the default ir op operations
3011 ir_op *firm_set_default_operations(ir_op *op)
3013 op = firm_set_default_computed_value(op);
3014 op = firm_set_default_equivalent_node(op);
3015 op = firm_set_default_transform_node(op);
3016 op = firm_set_default_node_cmp_attr(op);
3017 op = firm_set_default_get_type(op);