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 * @fixme -(-a) == a, but might overflow two times.
792 * We handle it anyway here but the better way would be a
793 * flag. This would be needed for Pascal for instance.
795 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
798 ir_node *pred = get_unop_op(n);
800 /* optimize symmetric unop */
801 if (get_irn_op(pred) == get_irn_op(n)) {
802 n = get_unop_op(pred);
803 DBG_OPT_ALGSIM2(oldn, pred, n);
809 #define equivalent_node_Not equivalent_node_symmetric_unop
811 /* --x == x */ /* ??? Is this possible or can --x raise an
812 out of bounds exception if min =! max? */
813 #define equivalent_node_Minus equivalent_node_symmetric_unop
816 * Optimize a * 1 = 1 * a = a.
818 static ir_node *equivalent_node_Mul(ir_node *n)
822 ir_node *a = get_Mul_left(n);
823 ir_node *b = get_Mul_right(n);
825 /* Mul is commutative and has again an other neutral element. */
826 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
828 DBG_OPT_ALGSIM1(oldn, a, b, n);
829 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
831 DBG_OPT_ALGSIM1(oldn, a, b, n);
837 * Optimize a / 1 = a.
839 static ir_node *equivalent_node_Div(ir_node *n)
841 ir_node *a = get_Div_left(n);
842 ir_node *b = get_Div_right(n);
844 /* Div is not commutative. */
845 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
846 /* Turn Div into a tuple (mem, bad, a) */
847 ir_node *mem = get_Div_mem(n);
848 turn_into_tuple(n, 3);
849 set_Tuple_pred(n, pn_Div_M, mem);
850 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
851 set_Tuple_pred(n, pn_Div_res, a);
857 * Optimize a / 1 = a.
859 static ir_node *equivalent_node_DivMod(ir_node *n)
861 ir_node *a = get_DivMod_left(n);
862 ir_node *b = get_DivMod_right(n);
864 /* Div is not commutative. */
865 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
866 /* Turn DivMod into a tuple (mem, bad, a, 0) */
867 ir_node *mem = get_Div_mem(n);
868 ir_mode *mode = get_irn_mode(b);
870 turn_into_tuple(n, 4);
871 set_Tuple_pred(n, pn_DivMod_M, mem);
872 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
873 set_Tuple_pred(n, pn_DivMod_res_div, a);
874 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
880 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
882 static ir_node *equivalent_node_Or(ir_node *n)
886 ir_node *a = get_Or_left(n);
887 ir_node *b = get_Or_right(n);
890 n = a; /* Or has it's own neutral element */
891 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
893 DBG_OPT_ALGSIM1(oldn, a, b, n);
894 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
896 DBG_OPT_ALGSIM1(oldn, a, b, n);
903 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
905 static ir_node *equivalent_node_And(ir_node *n)
909 ir_node *a = get_And_left(n);
910 ir_node *b = get_And_right(n);
913 n = a; /* And has it's own neutral element */
914 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
916 DBG_OPT_ALGSIM1(oldn, a, b, n);
917 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
919 DBG_OPT_ALGSIM1(oldn, a, b, n);
925 * Try to remove useless conv's:
927 static ir_node *equivalent_node_Conv(ir_node *n)
930 ir_node *a = get_Conv_op(n);
933 ir_mode *n_mode = get_irn_mode(n);
934 ir_mode *a_mode = get_irn_mode(a);
936 if (n_mode == a_mode) { /* No Conv necessary */
938 DBG_OPT_ALGSIM3(oldn, a, n);
939 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
943 n_mode = get_irn_mode(n);
944 b_mode = get_irn_mode(b);
946 if (n_mode == b_mode) {
947 if (n_mode == mode_b) {
948 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
949 DBG_OPT_ALGSIM1(oldn, a, b, n);
951 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
952 if (smaller_mode(b_mode, a_mode)){
953 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
954 DBG_OPT_ALGSIM1(oldn, a, b, n);
963 * A Cast may be removed if the type of the previous node
964 * is already the type of the Cast.
966 static ir_node *equivalent_node_Cast(ir_node *n) {
967 ir_node *pred = get_Cast_op(n);
968 if (get_irn_type(pred) == get_Cast_type(n))
973 /* Several optimizations:
974 - no Phi in start block.
975 - remove Id operators that are inputs to Phi
976 - fold Phi-nodes, iff they have only one predecessor except
979 static ir_node *equivalent_node_Phi(ir_node *n)
984 ir_node *block = NULL; /* to shutup gcc */
985 ir_node *first_val = NULL; /* to shutup gcc */
986 ir_node *scnd_val = NULL; /* to shutup gcc */
988 if (!get_opt_normalize()) return n;
990 n_preds = get_Phi_n_preds(n);
992 block = get_nodes_block(n);
993 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
994 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
995 if ((is_Block_dead(block)) || /* Control dead */
996 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
997 return new_Bad(); /* in the Start Block. */
999 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
1002 /* first we test for a special case: */
1003 /* Confirm is a special node fixing additional information for a
1004 value that is known at a certain point. This is useful for
1005 dataflow analysis. */
1007 ir_node *a = get_Phi_pred(n, 0);
1008 ir_node *b = get_Phi_pred(n, 1);
1009 if ( (get_irn_op(a) == op_Confirm)
1010 && (get_irn_op(b) == op_Confirm)
1011 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
1012 && (get_irn_n(a, 1) == get_irn_n (b, 1))
1013 && (a->data.num == (~b->data.num & irpn_True) )) {
1014 return get_irn_n(a, 0);
1019 /* If the Block has a Bad pred, we also have one. */
1020 for (i = 0; i < n_preds; ++i)
1021 if (is_Bad (get_Block_cfgpred(block, i)))
1022 set_Phi_pred(n, i, new_Bad());
1024 /* Find first non-self-referencing input */
1025 for (i = 0; i < n_preds; ++i) {
1026 first_val = get_Phi_pred(n, i);
1027 if ( (first_val != n) /* not self pointer */
1029 && (get_irn_op(first_val) != op_Bad)
1031 ) { /* value not dead */
1032 break; /* then found first value. */
1036 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1037 if (i >= n_preds) { return new_Bad(); }
1041 /* follow_Id () for rest of inputs, determine if any of these
1042 are non-self-referencing */
1043 while (++i < n_preds) {
1044 scnd_val = get_Phi_pred(n, i);
1045 if ( (scnd_val != n)
1046 && (scnd_val != first_val)
1048 && (get_irn_op(scnd_val) != op_Bad)
1055 /* Fold, if no multiple distinct non-self-referencing inputs */
1058 DBG_OPT_PHI(oldn, first_val, n);
1060 /* skip the remaining Ids (done in get_Phi_pred). */
1061 /* superfluous, since we walk all to propagate Block's Bads.
1062 while (++i < n_preds) get_Phi_pred(n, i); */
1068 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1070 static ir_node *equivalent_node_Proj(ir_node *n)
1074 ir_node *a = get_Proj_pred(n);
1076 if ( get_irn_op(a) == op_Tuple) {
1077 /* Remove the Tuple/Proj combination. */
1078 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1079 n = get_Tuple_pred(a, get_Proj_proj(n));
1080 DBG_OPT_TUPLE(oldn, a, n);
1082 assert(0); /* This should not happen! */
1085 } else if (get_irn_mode(n) == mode_X &&
1086 is_Block_dead(get_nodes_block(n))) {
1087 /* Remove dead control flow -- early gigo. */
1096 static ir_node *equivalent_node_Id(ir_node *n)
1101 DBG_OPT_ID(oldn, n);
1108 static ir_node *equivalent_node_Mux(ir_node *n)
1110 ir_node *oldn = n, *sel = get_Mux_sel(n);
1111 tarval *ts = value_of(sel);
1113 /* Mux(true, f, t) == t */
1114 if (ts == get_tarval_b_true()) {
1115 n = get_Mux_true(n);
1116 DBG_OPT_ALGSIM0(oldn, n);
1118 /* Mux(false, f, t) == f */
1119 else if (ts == get_tarval_b_false()) {
1120 n = get_Mux_false(n);
1121 DBG_OPT_ALGSIM0(oldn, n);
1123 /* Mux(v, x, x) == x */
1124 else if (get_Mux_false(n) == get_Mux_true(n)) {
1125 n = get_Mux_true(n);
1126 DBG_OPT_ALGSIM0(oldn, n);
1128 else if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(get_irn_mode(n))) {
1129 ir_node *cmp = get_Proj_pred(sel);
1130 long proj_nr = get_Proj_proj(sel);
1131 ir_node *b = get_Mux_false(n);
1132 ir_node *a = get_Mux_true(n);
1135 * Note: normalization puts the constant on the right site,
1136 * so we check only one case.
1138 * Note further that these optimization work even for floating point
1139 * with NaN's because -NaN == NaN.
1140 * However, if +0 and -0 is handled differently, we cannot use the first one.
1142 if (get_irn_op(cmp) == op_Cmp && get_Cmp_left(cmp) == a) {
1143 if (classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
1144 /* Mux(a CMP 0, X, a) */
1145 if (get_irn_op(b) == op_Minus && get_Minus_op(b) == a) {
1146 /* Mux(a CMP 0, -a, a) */
1147 if (proj_nr == pn_Cmp_Eq) {
1148 /* Mux(a == 0, -a, a) ==> -a */
1150 DBG_OPT_ALGSIM0(oldn, n);
1152 else if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1153 /* Mux(a != 0, -a, a) ==> a */
1155 DBG_OPT_ALGSIM0(oldn, n);
1158 else if (classify_Const(b) == CNST_NULL) {
1159 /* Mux(a CMP 0, 0, a) */
1160 if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1161 /* Mux(a != 0, 0, a) ==> a */
1163 DBG_OPT_ALGSIM0(oldn, n);
1165 else if (proj_nr == pn_Cmp_Eq) {
1166 /* Mux(a == 0, 0, a) ==> 0 */
1168 DBG_OPT_ALGSIM0(oldn, n);
1179 * Optimize -a CMP -b into b CMP a.
1180 * This works only for for modes where unary Minus
1182 * Note that two-complement integers can Overflow
1183 * so it will NOT work.
1185 static ir_node *equivalent_node_Cmp(ir_node *n)
1187 ir_node *left = get_Cmp_left(n);
1188 ir_node *right = get_Cmp_right(n);
1190 if (get_irn_op(left) == op_Minus && get_irn_op(right) == op_Minus &&
1191 !mode_overflow_on_unary_Minus(get_irn_mode(left))) {
1192 left = get_Minus_op(left);
1193 right = get_Minus_op(right);
1194 set_Cmp_left(n, right);
1195 set_Cmp_right(n, left);
1201 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1202 * perform no actual computation, as, e.g., the Id nodes. It does not create
1203 * new nodes. It is therefore safe to free n if the node returned is not n.
1204 * If a node returns a Tuple we can not just skip it. If the size of the
1205 * in array fits, we transform n into a tuple (e.g., Div).
1208 equivalent_node(ir_node *n)
1210 if (n->op->equivalent_node)
1211 return n->op->equivalent_node(n);
1216 * set the default equivalent node operation
1218 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1222 op->equivalent_node = equivalent_node_##a; \
1251 op->equivalent_node = NULL;
1259 * Do node specific optimizations of nodes predecessors.
1262 optimize_preds(ir_node *n) {
1263 ir_node *a = NULL, *b = NULL;
1265 /* get the operands we will work on for simple cases. */
1267 a = get_binop_left(n);
1268 b = get_binop_right(n);
1269 } else if (is_unop(n)) {
1273 switch (get_irn_opcode(n)) {
1276 /* We don't want Cast as input to Cmp. */
1277 if (get_irn_op(a) == op_Cast) {
1281 if (get_irn_op(b) == op_Cast) {
1283 set_Cmp_right(n, b);
1292 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1293 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)).
1294 * If possible, remove the Conv's.
1296 static ir_node *transform_node_AddSub(ir_node *n)
1298 ir_mode *mode = get_irn_mode(n);
1300 if (mode_is_reference(mode)) {
1301 ir_node *left = get_binop_left(n);
1302 ir_node *right = get_binop_right(n);
1303 int ref_bits = get_mode_size_bits(mode);
1305 if (get_irn_op(left) == op_Conv) {
1306 ir_mode *mode = get_irn_mode(left);
1307 int bits = get_mode_size_bits(mode);
1309 if (ref_bits == bits &&
1310 mode_is_int(mode) &&
1311 get_mode_arithmetic(mode) == irma_twos_complement) {
1312 ir_node *pre = get_Conv_op(left);
1313 ir_mode *pre_mode = get_irn_mode(pre);
1315 if (mode_is_int(pre_mode) &&
1316 get_mode_size_bits(pre_mode) == bits &&
1317 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1318 /* ok, this conv just changes to sign, moreover the calculation
1319 * is done with same number of bits as our address mode, so
1320 * we can ignore the conv as address calculation can be viewed
1321 * as either signed or unsigned
1323 set_binop_left(n, pre);
1328 if (get_irn_op(right) == op_Conv) {
1329 ir_mode *mode = get_irn_mode(right);
1330 int bits = get_mode_size_bits(mode);
1332 if (ref_bits == bits &&
1333 mode_is_int(mode) &&
1334 get_mode_arithmetic(mode) == irma_twos_complement) {
1335 ir_node *pre = get_Conv_op(right);
1336 ir_mode *pre_mode = get_irn_mode(pre);
1338 if (mode_is_int(pre_mode) &&
1339 get_mode_size_bits(pre_mode) == bits &&
1340 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1341 /* ok, this conv just changes to sign, moreover the calculation
1342 * is done with same number of bits as our address mode, so
1343 * we can ignore the conv as address calculation can be viewed
1344 * as either signed or unsigned
1346 set_binop_right(n, pre);
1355 * Do the AddSub optimization, then Transform Add(a,a) into Mul(a, 2)
1356 * if the mode is integer or float.
1357 * Reassociation might fold this further.
1359 static ir_node *transform_node_Add(ir_node *n)
1364 n = transform_node_AddSub(n);
1366 mode = get_irn_mode(n);
1367 if (mode_is_num(mode)) {
1368 ir_node *a = get_Add_left(n);
1370 if (a == get_Add_right(n)) {
1371 ir_node *block = get_nodes_block(n);
1374 get_irn_dbg_info(n),
1378 new_r_Const_long(current_ir_graph, block, mode, 2),
1380 DBG_OPT_ALGSIM0(oldn, n);
1387 * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
1389 static ir_node *transform_node_Sub(ir_node *n)
1394 n = transform_node_AddSub(n);
1396 mode = get_irn_mode(n);
1397 if (mode_is_num(mode) && (classify_Const(get_Sub_left(n)) == CNST_NULL)) {
1399 get_irn_dbg_info(n),
1404 DBG_OPT_ALGSIM0(oldn, n);
1410 /** Do architecture dependend optimizations on Mul nodes */
1411 static ir_node *transform_node_Mul(ir_node *n) {
1412 return arch_dep_replace_mul_with_shifts(n);
1416 * transform a Div Node
1418 static ir_node *transform_node_Div(ir_node *n)
1420 tarval *tv = value_of(n);
1423 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1425 if (tv != tarval_bad) {
1426 value = new_Const(get_tarval_mode(tv), tv);
1428 DBG_OPT_CSTEVAL(n, value);
1430 else /* Try architecture dependand optimization */
1431 value = arch_dep_replace_div_by_const(n);
1434 /* Turn Div into a tuple (mem, bad, value) */
1435 ir_node *mem = get_Div_mem(n);
1437 turn_into_tuple(n, 3);
1438 set_Tuple_pred(n, pn_Div_M, mem);
1439 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1440 set_Tuple_pred(n, pn_Div_res, value);
1446 * transform a Mod node
1448 static ir_node *transform_node_Mod(ir_node *n)
1450 tarval *tv = value_of(n);
1453 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1455 if (tv != tarval_bad) {
1456 value = new_Const(get_tarval_mode(tv), tv);
1458 DBG_OPT_CSTEVAL(n, value);
1460 else /* Try architecture dependand optimization */
1461 value = arch_dep_replace_mod_by_const(n);
1464 /* Turn Mod into a tuple (mem, bad, value) */
1465 ir_node *mem = get_Mod_mem(n);
1467 turn_into_tuple(n, 3);
1468 set_Tuple_pred(n, pn_Mod_M, mem);
1469 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1470 set_Tuple_pred(n, pn_Mod_res, value);
1476 * transform a DivMod node
1478 static ir_node *transform_node_DivMod(ir_node *n)
1482 ir_node *a = get_DivMod_left(n);
1483 ir_node *b = get_DivMod_right(n);
1484 ir_mode *mode = get_irn_mode(a);
1485 tarval *ta = value_of(a);
1486 tarval *tb = value_of(b);
1488 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1491 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1493 if (tb != tarval_bad) {
1494 if (tb == get_mode_one(get_tarval_mode(tb))) {
1495 b = new_Const (mode, get_mode_null(mode));
1498 DBG_OPT_CSTEVAL(n, b);
1500 else if (ta != tarval_bad) {
1501 tarval *resa, *resb;
1502 resa = tarval_div (ta, tb);
1503 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1504 Jmp for X result!? */
1505 resb = tarval_mod (ta, tb);
1506 if (resb == tarval_bad) return n; /* Causes exception! */
1507 a = new_Const (mode, resa);
1508 b = new_Const (mode, resb);
1511 DBG_OPT_CSTEVAL(n, a);
1512 DBG_OPT_CSTEVAL(n, b);
1514 else { /* Try architecture dependand optimization */
1515 arch_dep_replace_divmod_by_const(&a, &b, n);
1516 evaluated = a != NULL;
1518 } else if (ta == get_mode_null(mode)) {
1519 /* 0 / non-Const = 0 */
1524 if (evaluated) { /* replace by tuple */
1525 ir_node *mem = get_DivMod_mem(n);
1526 turn_into_tuple(n, 4);
1527 set_Tuple_pred(n, pn_DivMod_M, mem);
1528 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1529 set_Tuple_pred(n, pn_DivMod_res_div, a);
1530 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1531 assert(get_nodes_block(n));
1538 * transform a Cond node
1540 static ir_node *transform_node_Cond(ir_node *n)
1542 /* Replace the Cond by a Jmp if it branches on a constant
1545 ir_node *a = get_Cond_selector(n);
1546 tarval *ta = value_of(a);
1548 if ((ta != tarval_bad) &&
1549 (get_irn_mode(a) == mode_b) &&
1550 (get_opt_unreachable_code())) {
1551 /* It's a boolean Cond, branching on a boolean constant.
1552 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1553 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1554 turn_into_tuple(n, 2);
1555 if (ta == tarval_b_true) {
1556 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1557 set_Tuple_pred(n, pn_Cond_true, jmp);
1559 set_Tuple_pred(n, pn_Cond_false, jmp);
1560 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1562 /* We might generate an endless loop, so keep it alive. */
1563 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1564 } else if ((ta != tarval_bad) &&
1565 (get_irn_mode(a) == mode_Iu) &&
1566 (get_Cond_kind(n) == dense) &&
1567 (get_opt_unreachable_code())) {
1568 /* I don't want to allow Tuples smaller than the biggest Proj.
1569 Also this tuple might get really big...
1570 I generate the Jmp here, and remember it in link. Link is used
1571 when optimizing Proj. */
1572 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1573 /* We might generate an endless loop, so keep it alive. */
1574 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1575 } else if ((get_irn_op(a) == op_Eor)
1576 && (get_irn_mode(a) == mode_b)
1577 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1578 /* The Eor is a negate. Generate a new Cond without the negate,
1579 simulate the negate by exchanging the results. */
1580 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1582 } else if ((get_irn_op(a) == op_Not)
1583 && (get_irn_mode(a) == mode_b)) {
1584 /* A Not before the Cond. Generate a new Cond without the Not,
1585 simulate the Not by exchanging the results. */
1586 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1595 static ir_node *transform_node_Eor(ir_node *n)
1598 ir_node *a = get_Eor_left(n);
1599 ir_node *b = get_Eor_right(n);
1601 if ((get_irn_mode(n) == mode_b)
1602 && (get_irn_op(a) == op_Proj)
1603 && (get_irn_mode(a) == mode_b)
1604 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1605 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1606 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1607 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1608 mode_b, get_negated_pnc(get_Proj_proj(a)));
1610 DBG_OPT_ALGSIM0(oldn, n);
1612 else if ((get_irn_mode(n) == mode_b)
1613 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
1614 /* The Eor is a Not. Replace it by a Not. */
1615 /* ????!!!Extend to bitfield 1111111. */
1616 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1618 DBG_OPT_ALGSIM0(oldn, n);
1625 * Transform a boolean Not.
1627 static ir_node *transform_node_Not(ir_node *n)
1630 ir_node *a = get_Not_op(n);
1632 if ( (get_irn_mode(n) == mode_b)
1633 && (get_irn_op(a) == op_Proj)
1634 && (get_irn_mode(a) == mode_b)
1635 && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
1636 /* We negate a Cmp. The Cmp has the negated result anyways! */
1637 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1638 mode_b, get_negated_pnc(get_Proj_proj(a)));
1639 DBG_OPT_ALGSIM0(oldn, n);
1646 * Transform a Cast of a Const into a new Const
1648 static ir_node *transform_node_Cast(ir_node *n) {
1650 ir_node *pred = get_Cast_op(n);
1651 type *tp = get_irn_type(n);
1653 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1654 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1655 get_Const_tarval(pred), tp);
1656 DBG_OPT_CSTEVAL(oldn, n);
1657 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1658 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1659 get_SymConst_kind(pred), tp);
1660 DBG_OPT_CSTEVAL(oldn, n);
1667 * Does all optimizations on nodes that must be done on it's Proj's
1668 * because of creating new nodes.
1670 * Transform a Div/Mod/DivMod with a non-zero constant.
1671 * Removes the exceptions and routes the memory to the NoMem node.
1673 * Optimizes jump tables by removing all impossible cases.
1675 * Normalizes and optimizes Cmp nodes.
1677 static ir_node *transform_node_Proj(ir_node *proj)
1679 ir_node *n = get_Proj_pred(proj);
1684 switch (get_irn_opcode(n)) {
1686 b = get_Div_right(n);
1689 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1690 proj_nr = get_Proj_proj(proj);
1692 /* this node may float */
1693 set_irn_pinned(n, op_pin_state_floats);
1695 if (proj_nr == pn_Div_X_except) {
1696 /* we found an exception handler, remove it */
1699 /* the memory Proj can be removed */
1700 ir_node *res = get_Div_mem(n);
1701 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1702 if (proj_nr == pn_Div_M)
1708 b = get_Mod_right(n);
1711 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1712 proj_nr = get_Proj_proj(proj);
1714 /* this node may float */
1715 set_irn_pinned(n, op_pin_state_floats);
1717 if (proj_nr == pn_Mod_X_except) {
1718 /* we found an exception handler, remove it */
1721 /* the memory Proj can be removed */
1722 ir_node *res = get_Mod_mem(n);
1723 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1724 if (proj_nr == pn_Mod_M)
1730 b = get_DivMod_right(n);
1733 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1734 proj_nr = get_Proj_proj(proj);
1736 /* this node may float */
1737 set_irn_pinned(n, op_pin_state_floats);
1739 if (proj_nr == pn_DivMod_X_except) {
1740 /* we found an exception handler, remove it */
1744 /* the memory Proj can be removed */
1745 ir_node *res = get_DivMod_mem(n);
1746 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1747 if (proj_nr == pn_DivMod_M)
1754 if (get_opt_unreachable_code()) {
1755 b = get_Cond_selector(n);
1758 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1759 /* we have a constant switch */
1760 long num = get_Proj_proj(proj);
1762 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1763 if (get_tarval_long(tb) == num) {
1764 /* Do NOT create a jump here, or we will have 2 control flow ops
1765 * in a block. This case is optimized away in optimize_cf(). */
1776 if (get_opt_reassociation()) {
1777 ir_node *left = get_Cmp_left(n);
1778 ir_node *right = get_Cmp_right(n);
1782 ir_mode *mode = NULL;
1784 proj_nr = get_Proj_proj(proj);
1787 * First step: normalize the compare op
1788 * by placing the constant on the right site
1789 * or moving the lower address node to the left.
1790 * We ignore the case that both are constants, then
1791 * this compare should be optimized away.
1793 if (get_irn_op(right) == op_Const)
1795 else if (get_irn_op(left) == op_Const) {
1800 proj_nr = get_swapped_pnc(proj_nr);
1803 else if (left > right) {
1809 proj_nr = get_swapped_pnc(proj_nr);
1814 * Second step: Try to reduce the magnitude
1815 * of a constant. This may help to generate better code
1816 * later and may help to normalize more compares.
1817 * Of course this is only possible for integer values.
1820 mode = get_irn_mode(c);
1821 tv = get_Const_tarval(c);
1823 if (tv != tarval_bad) {
1824 /* the following optimization is possibe on modes without Overflow
1825 * on Unary Minus or on == and !=:
1826 * -a CMP c ==> a swap(CMP) -c
1828 * Beware: for two-complement Overflow may occur, so only == and != can
1829 * be optimized, see this:
1830 * -MININT < 0 =/=> MININT > 0 !!!
1832 if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
1833 (!mode_overflow_on_unary_Minus(mode) ||
1834 (mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
1835 left = get_Minus_op(left);
1836 tv = tarval_sub(get_tarval_null(mode), tv);
1838 proj_nr = get_swapped_pnc(proj_nr);
1842 /* for integer modes, we have more */
1843 if (mode_is_int(mode)) {
1844 /* Ne includes Unordered which is not possible on integers.
1845 * However, frontends often use this wrong, so fix it here */
1846 if (proj_nr == pn_Cmp_Ne) {
1847 proj_nr = pn_Cmp_Lg;
1848 set_Proj_proj(proj, proj_nr);
1851 /* c > 0 : a < c ==> a <= (c-1) a >= c ==> a > (c-1) */
1852 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
1853 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Gt) {
1854 tv = tarval_sub(tv, get_tarval_one(mode));
1856 proj_nr ^= pn_Cmp_Eq;
1859 /* c < 0 : a > c ==> a >= (c+1) a <= c ==> a < (c+1) */
1860 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
1861 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Lt) {
1862 tv = tarval_add(tv, get_tarval_one(mode));
1864 proj_nr ^= pn_Cmp_Eq;
1868 /* the following reassociations work only for == and != */
1870 /* a-b == 0 ==> a == b, a-b != 0 ==> a != b */
1871 if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
1872 if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
1873 right = get_Sub_right(left);
1874 left = get_Sub_left(left);
1876 tv = value_of(right);
1881 if ((tv != tarval_bad) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)) {
1882 ir_op *op = get_irn_op(left);
1884 /* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */
1886 ir_node *c1 = get_Sub_right(left);
1887 tarval *tv2 = value_of(c1);
1889 if (tv2 != tarval_bad) {
1890 tv2 = tarval_add(tv, value_of(c1));
1892 if (tv2 != tarval_bad) {
1893 left = get_Sub_left(left);
1899 /* a+c1 == c2 ==> a == c2-c1, a+c1 != c2 ==> a != c2-c1 */
1900 else if (op == op_Add) {
1901 ir_node *a_l = get_Add_left(left);
1902 ir_node *a_r = get_Add_right(left);
1906 if (get_irn_op(a_l) == op_Const) {
1908 tv2 = value_of(a_l);
1912 tv2 = value_of(a_r);
1915 if (tv2 != tarval_bad) {
1916 tv2 = tarval_sub(tv, tv2);
1918 if (tv2 != tarval_bad) {
1931 ir_node *block = get_nodes_block(n);
1933 if (changed & 2) /* need a new Const */
1934 right = new_Const(mode, tv);
1936 /* create a new compare */
1937 n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
1940 set_Proj_pred(proj, n);
1941 set_Proj_proj(proj, proj_nr);
1947 /* should not happen, but if it does will be optimized away */
1955 /* we have added a Tuple, optimize it for the current Proj away */
1956 return equivalent_node_Proj(proj);
1960 * returns the operands of a commutative bin-op, if one operand is
1961 * a const, it is returned as the second one.
1963 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1965 ir_node *op_a = get_binop_left(binop);
1966 ir_node *op_b = get_binop_right(binop);
1968 assert(is_op_commutative(get_irn_op(binop)));
1970 if (get_irn_op(op_a) == op_Const) {
1981 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1982 * Such pattern may arise in bitfield stores.
1984 * value c4 value c4 & c2
1985 * AND c3 AND c1 | c3
1990 static ir_node *transform_node_Or_bf_store(ir_node *or)
1994 ir_node *and_l, *c3;
1995 ir_node *value, *c4;
1996 ir_node *new_and, *new_const, *block;
1997 ir_mode *mode = get_irn_mode(or);
1999 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
2001 get_comm_Binop_Ops(or, &and, &c1);
2002 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
2005 get_comm_Binop_Ops(and, &or_l, &c2);
2006 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
2009 get_comm_Binop_Ops(or_l, &and_l, &c3);
2010 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2013 get_comm_Binop_Ops(and_l, &value, &c4);
2014 if (get_irn_op(c4) != op_Const)
2017 /* ok, found the pattern, check for conditions */
2018 assert(mode == get_irn_mode(and));
2019 assert(mode == get_irn_mode(or_l));
2020 assert(mode == get_irn_mode(and_l));
2022 tv1 = get_Const_tarval(c1);
2023 tv2 = get_Const_tarval(c2);
2024 tv3 = get_Const_tarval(c3);
2025 tv4 = get_Const_tarval(c4);
2027 tv = tarval_or(tv4, tv2);
2028 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2029 /* have at least one 0 at the same bit position */
2033 n_tv4 = tarval_not(tv4);
2034 if (tv3 != tarval_and(tv3, n_tv4)) {
2035 /* bit in the or_mask is outside the and_mask */
2039 n_tv2 = tarval_not(tv2);
2040 if (tv1 != tarval_and(tv1, n_tv2)) {
2041 /* bit in the or_mask is outside the and_mask */
2045 /* ok, all conditions met */
2046 block = get_nodes_block(or);
2048 new_and = new_r_And(current_ir_graph, block,
2049 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
2051 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
2053 set_Or_left(or, new_and);
2054 set_Or_right(or, new_const);
2056 /* check for more */
2057 return transform_node_Or_bf_store(or);
2061 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
2063 static ir_node *transform_node_Or_Rot(ir_node *or)
2065 ir_mode *mode = get_irn_mode(or);
2066 ir_node *shl, *shr, *block;
2067 ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
2070 if (! mode_is_int(mode))
2073 shl = get_binop_left(or);
2074 shr = get_binop_right(or);
2076 if (get_irn_op(shl) == op_Shr) {
2077 if (get_irn_op(shr) != op_Shl)
2084 else if (get_irn_op(shl) != op_Shl)
2086 else if (get_irn_op(shr) != op_Shr)
2089 x = get_Shl_left(shl);
2090 if (x != get_Shr_left(shr))
2093 c1 = get_Shl_right(shl);
2094 c2 = get_Shr_right(shr);
2095 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
2096 tv1 = get_Const_tarval(c1);
2097 if (! tarval_is_long(tv1))
2100 tv2 = get_Const_tarval(c2);
2101 if (! tarval_is_long(tv2))
2104 if (get_tarval_long(tv1) + get_tarval_long(tv2)
2105 != get_mode_size_bits(mode))
2108 /* yet, condition met */
2109 block = get_nodes_block(or);
2111 n = new_r_Rot(current_ir_graph, block, x, c1, mode);
2113 DBG_OPT_ALGSIM1(or, shl, shr, n);
2116 else if (get_irn_op(c1) == op_Sub) {
2120 if (get_Sub_right(sub) != v)
2123 c1 = get_Sub_left(sub);
2124 if (get_irn_op(c1) != op_Const)
2127 tv1 = get_Const_tarval(c1);
2128 if (! tarval_is_long(tv1))
2131 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2134 /* yet, condition met */
2135 block = get_nodes_block(or);
2137 /* a Rot right is not supported, so use a rot left */
2138 n = new_r_Rot(current_ir_graph, block, x, sub, mode);
2140 DBG_OPT_ALGSIM0(or, n);
2143 else if (get_irn_op(c2) == op_Sub) {
2147 c1 = get_Sub_left(sub);
2148 if (get_irn_op(c1) != op_Const)
2151 tv1 = get_Const_tarval(c1);
2152 if (! tarval_is_long(tv1))
2155 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2158 /* yet, condition met */
2159 block = get_nodes_block(or);
2162 n = new_r_Rot(current_ir_graph, block, x, v, mode);
2164 DBG_OPT_ALGSIM0(or, n);
2174 static ir_node *transform_node_Or(ir_node *or)
2176 or = transform_node_Or_bf_store(or);
2177 or = transform_node_Or_Rot(or);
2183 static ir_node *transform_node(ir_node *n);
2186 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
2188 static ir_node *transform_node_shift(ir_node *n)
2190 ir_node *left, *right;
2191 tarval *tv1, *tv2, *res;
2193 int modulo_shf, flag;
2195 left = get_binop_left(n);
2197 /* different operations */
2198 if (get_irn_op(left) != get_irn_op(n))
2201 right = get_binop_right(n);
2202 tv1 = value_of(right);
2203 if (tv1 == tarval_bad)
2206 tv2 = value_of(get_binop_right(left));
2207 if (tv2 == tarval_bad)
2210 res = tarval_add(tv1, tv2);
2212 /* beware: a simple replacement works only, if res < modulo shift */
2213 mode = get_irn_mode(n);
2217 modulo_shf = get_mode_modulo_shift(mode);
2218 if (modulo_shf > 0) {
2219 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
2221 if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
2228 /* ok, we can replace it */
2229 ir_node *in[2], *irn, *block = get_nodes_block(n);
2231 in[0] = get_binop_left(left);
2232 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
2234 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
2236 DBG_OPT_ALGSIM0(n, irn);
2238 return transform_node(irn);
2243 #define transform_node_Shr transform_node_shift
2244 #define transform_node_Shrs transform_node_shift
2245 #define transform_node_Shl transform_node_shift
2248 * Remove dead blocks in keepalive list. We do not generate a new End node.
2250 static ir_node *transform_node_End(ir_node *n) {
2251 int i, n_keepalives = get_End_n_keepalives(n);
2253 for (i = 0; i < n_keepalives; ++i) {
2254 ir_node *ka = get_End_keepalive(n, i);
2255 if (is_Block(ka) && is_Block_dead(ka))
2256 set_End_keepalive(n, i, new_Bad());
2262 * Optimize a Mux into some simplier cases.
2264 static ir_node *transform_node_Mux(ir_node *n)
2266 ir_node *oldn = n, *sel = get_Mux_sel(n);
2267 ir_mode *mode = get_irn_mode(n);
2269 if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
2270 ir_node *cmp = get_Proj_pred(sel);
2271 long proj_nr = get_Proj_proj(sel);
2272 ir_node *f = get_Mux_false(n);
2273 ir_node *t = get_Mux_true(n);
2275 if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
2276 ir_node *block = get_nodes_block(n);
2279 * Note: normalization puts the constant on the right site,
2280 * so we check only one case.
2282 * Note further that these optimization work even for floating point
2283 * with NaN's because -NaN == NaN.
2284 * However, if +0 and -0 is handled differently, we cannot use the first one.
2286 if (get_irn_op(f) == op_Minus &&
2287 get_Minus_op(f) == t &&
2288 get_Cmp_left(cmp) == t) {
2290 if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2291 /* Mux(a >=/> 0, -a, a) ==> Abs(a) */
2292 n = new_rd_Abs(get_irn_dbg_info(n),
2296 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2299 else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2300 /* Mux(a <=/< 0, -a, a) ==> Minus(Abs(a)) */
2301 n = new_rd_Abs(get_irn_dbg_info(n),
2305 n = new_rd_Minus(get_irn_dbg_info(n),
2310 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2314 else if (get_irn_op(t) == op_Minus &&
2315 get_Minus_op(t) == f &&
2316 get_Cmp_left(cmp) == f) {
2318 if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2319 /* Mux(a <=/< 0, a, -a) ==> Abs(a) */
2320 n = new_rd_Abs(get_irn_dbg_info(n),
2324 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2327 else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2328 /* Mux(a >=/> 0, a, -a) ==> Minus(Abs(a)) */
2329 n = new_rd_Abs(get_irn_dbg_info(n),
2333 n = new_rd_Minus(get_irn_dbg_info(n),
2338 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2343 if (mode_is_int(mode) && mode_is_signed(mode) &&
2344 get_mode_arithmetic(mode) == irma_twos_complement) {
2345 ir_node *x = get_Cmp_left(cmp);
2347 /* the following optimization works only with signed integer two-complement mode */
2349 if (mode == get_irn_mode(x)) {
2351 * FIXME: this restriction is two rigid, as it would still
2352 * work if mode(x) = Hs and mode == Is, but at least it removes
2355 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
2356 classify_Const(t) == CNST_ALL_ONE &&
2357 classify_Const(f) == CNST_NULL) {
2359 * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
2363 n = new_rd_Shrs(get_irn_dbg_info(n),
2364 current_ir_graph, block, x,
2365 new_r_Const_long(current_ir_graph, block, mode_Iu,
2366 get_mode_size_bits(mode) - 1),
2368 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2371 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
2372 classify_Const(t) == CNST_ONE &&
2373 classify_Const(f) == CNST_NULL) {
2375 * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
2379 n = new_rd_Shr(get_irn_dbg_info(n),
2380 current_ir_graph, block,
2381 new_r_Minus(current_ir_graph, block, x, mode),
2382 new_r_Const_long(current_ir_graph, block, mode_Iu,
2383 get_mode_size_bits(mode) - 1),
2385 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2392 return arch_transform_node_Mux(n);
2396 * Tries several [inplace] [optimizing] transformations and returns an
2397 * equivalent node. The difference to equivalent_node() is that these
2398 * transformations _do_ generate new nodes, and thus the old node must
2399 * not be freed even if the equivalent node isn't the old one.
2401 static ir_node *transform_node(ir_node *n)
2403 if (n->op->transform_node)
2404 n = n->op->transform_node(n);
2409 * set the default transform node operation
2411 static ir_op *firm_set_default_transform_node(ir_op *op)
2415 op->transform_node = transform_node_##a; \
2438 op->transform_node = NULL;
2446 /* **************** Common Subexpression Elimination **************** */
2448 /** The size of the hash table used, should estimate the number of nodes
2450 #define N_IR_NODES 512
2452 /** Compares the attributes of two Const nodes. */
2453 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2455 return (get_Const_tarval(a) != get_Const_tarval(b))
2456 || (get_Const_type(a) != get_Const_type(b));
2459 /** Compares the attributes of two Proj nodes. */
2460 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2462 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2465 /** Compares the attributes of two Filter nodes. */
2466 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2468 return get_Filter_proj(a) != get_Filter_proj(b);
2471 /** Compares the attributes of two Alloc nodes. */
2472 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2474 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2475 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2478 /** Compares the attributes of two Free nodes. */
2479 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2481 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2482 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2485 /** Compares the attributes of two SymConst nodes. */
2486 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2488 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2489 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2490 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2493 /** Compares the attributes of two Call nodes. */
2494 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2496 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2499 /** Compares the attributes of two Sel nodes. */
2500 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2502 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2503 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2504 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2505 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2506 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2509 /** Compares the attributes of two Phi nodes. */
2510 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2512 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2515 /** Compares the attributes of two Cast nodes. */
2516 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2518 return get_Cast_type(a) != get_Cast_type(b);
2521 /** Compares the attributes of two Load nodes. */
2522 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2524 if (get_Load_volatility(a) == volatility_is_volatile ||
2525 get_Load_volatility(b) == volatility_is_volatile)
2526 /* NEVER do CSE on volatile Loads */
2529 return get_Load_mode(a) != get_Load_mode(b);
2532 /** Compares the attributes of two Store nodes. */
2533 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2535 /* NEVER do CSE on volatile Stores */
2536 return (get_Store_volatility(a) == volatility_is_volatile ||
2537 get_Store_volatility(b) == volatility_is_volatile);
2541 * set the default node attribute compare operation
2543 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2547 op->node_cmp_attr = node_cmp_attr_##a; \
2564 op->node_cmp_attr = NULL;
2572 * Compare function for two nodes in the hash table. Gets two
2573 * nodes as parameters. Returns 0 if the nodes are a cse.
2576 vt_cmp (const void *elt, const void *key)
2584 if (a == b) return 0;
2586 if ((get_irn_op(a) != get_irn_op(b)) ||
2587 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2589 /* compare if a's in and b's in are of equal length */
2590 irn_arity_a = get_irn_intra_arity (a);
2591 if (irn_arity_a != get_irn_intra_arity(b))
2594 /* for block-local cse and op_pin_state_pinned nodes: */
2595 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2596 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2600 /* compare a->in[0..ins] with b->in[0..ins] */
2601 for (i = 0; i < irn_arity_a; i++)
2602 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2606 * here, we already now that the nodes are identical except their
2609 if (a->op->node_cmp_attr)
2610 return a->op->node_cmp_attr(a, b);
2616 * Calculate a hash value of a node.
2619 ir_node_hash (ir_node *node)
2624 if (node->op == op_Const) {
2625 /* special value for const, as they only differ in their tarval. */
2626 h = HASH_PTR(node->attr.con.tv);
2627 h = 9*h + HASH_PTR(get_irn_mode(node));
2628 } else if (node->op == op_SymConst) {
2629 /* special value for const, as they only differ in their symbol. */
2630 h = HASH_PTR(node->attr.i.sym.type_p);
2631 h = 9*h + HASH_PTR(get_irn_mode(node));
2634 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2635 h = irn_arity = get_irn_intra_arity(node);
2637 /* consider all in nodes... except the block if not a control flow. */
2638 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2639 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2643 h = 9*h + HASH_PTR(get_irn_mode(node));
2645 h = 9*h + HASH_PTR(get_irn_op(node));
2652 new_identities(void) {
2653 return new_pset(vt_cmp, N_IR_NODES);
2657 del_identities(pset *value_table) {
2658 del_pset(value_table);
2662 * Return the canonical node computing the same value as n.
2663 * Looks up the node in a hash table.
2665 * For Const nodes this is performed in the constructor, too. Const
2666 * nodes are extremely time critical because of their frequent use in
2667 * constant string arrays.
2669 static INLINE ir_node *
2670 identify (pset *value_table, ir_node *n)
2674 if (!value_table) return n;
2676 if (get_opt_reassociation()) {
2677 if (is_op_commutative(get_irn_op(n))) {
2678 ir_node *l = get_binop_left(n);
2679 ir_node *r = get_binop_right(n);
2681 /* for commutative operators perform a OP b == b OP a */
2683 set_binop_left(n, r);
2684 set_binop_right(n, l);
2689 o = pset_find (value_table, n, ir_node_hash (n));
2698 * During construction we set the op_pin_state_pinned flag in the graph right when the
2699 * optimization is performed. The flag turning on procedure global cse could
2700 * be changed between two allocations. This way we are safe.
2702 static INLINE ir_node *
2703 identify_cons (pset *value_table, ir_node *n) {
2706 n = identify(value_table, n);
2707 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2708 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2713 * Return the canonical node computing the same value as n.
2714 * Looks up the node in a hash table, enters it in the table
2715 * if it isn't there yet.
2718 identify_remember (pset *value_table, ir_node *n)
2722 if (!value_table) return n;
2724 if (get_opt_reassociation()) {
2725 if (is_op_commutative(get_irn_op(n))) {
2726 ir_node *l = get_binop_left(n);
2727 ir_node *r = get_binop_right(n);
2729 /* for commutative operators perform a OP b == b OP a */
2731 set_binop_left(n, r);
2732 set_binop_right(n, l);
2737 /* lookup or insert in hash table with given hash key. */
2738 o = pset_insert (value_table, n, ir_node_hash (n));
2748 add_identities (pset *value_table, ir_node *node) {
2749 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2750 identify_remember (value_table, node);
2754 * garbage in, garbage out. If a node has a dead input, i.e., the
2755 * Bad node is input to the node, return the Bad node.
2757 static INLINE ir_node *
2758 gigo (ir_node *node)
2761 ir_op* op = get_irn_op(node);
2763 /* remove garbage blocks by looking at control flow that leaves the block
2764 and replacing the control flow by Bad. */
2765 if (get_irn_mode(node) == mode_X) {
2766 ir_node *block = get_nodes_block(node);
2767 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2768 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2770 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2771 irn_arity = get_irn_arity(block);
2772 for (i = 0; i < irn_arity; i++) {
2773 if (!is_Bad(get_irn_n(block, i))) break;
2775 if (i == irn_arity) return new_Bad();
2779 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2780 blocks predecessors is dead. */
2781 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2782 irn_arity = get_irn_arity(node);
2784 if (is_Block_dead(get_nodes_block(node)))
2787 for (i = 0; i < irn_arity; i++) {
2788 if (is_Bad(get_irn_n(node, i))) {
2794 /* With this code we violate the agreement that local_optimize
2795 only leaves Bads in Block, Phi and Tuple nodes. */
2796 /* If Block has only Bads as predecessors it's garbage. */
2797 /* If Phi has only Bads as predecessors it's garbage. */
2798 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2799 irn_arity = get_irn_arity(node);
2800 for (i = 0; i < irn_arity; i++) {
2801 if (!is_Bad(get_irn_n(node, i))) break;
2803 if (i == irn_arity) node = new_Bad();
2811 * These optimizations deallocate nodes from the obstack.
2812 * It can only be called if it is guaranteed that no other nodes
2813 * reference this one, i.e., right after construction of a node.
2816 optimize_node (ir_node *n)
2820 opcode iro = get_irn_opcode(n);
2822 type *old_tp = get_irn_type(n);
2824 int i, arity = get_irn_arity(n);
2825 for (i = 0; i < arity && !old_tp; ++i)
2826 old_tp = get_irn_type(get_irn_n(n, i));
2829 /* Always optimize Phi nodes: part of the construction. */
2830 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2832 /* constant expression evaluation / constant folding */
2833 if (get_opt_constant_folding()) {
2834 /* constants can not be evaluated */
2835 if (iro != iro_Const) {
2836 /* try to evaluate */
2837 tv = computed_value(n);
2838 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2842 * we MUST copy the node here temporary, because it's still needed
2843 * for DBG_OPT_CSTEVAL
2845 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2846 oldn = alloca(node_size);
2848 memcpy(oldn, n, node_size);
2849 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2851 /* ARG, copy the in array, we need it for statistics */
2852 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2855 edges_node_deleted(n, current_ir_graph);
2857 /* evaluation was successful -- replace the node. */
2858 obstack_free (current_ir_graph->obst, n);
2859 nw = new_Const (get_tarval_mode (tv), tv);
2861 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2862 set_Const_type(nw, old_tp);
2863 DBG_OPT_CSTEVAL(oldn, nw);
2869 /* remove unnecessary nodes */
2870 if (get_opt_constant_folding() ||
2871 (iro == iro_Phi) || /* always optimize these nodes. */
2873 (iro == iro_Proj) ||
2874 (iro == iro_Block) ) /* Flags tested local. */
2875 n = equivalent_node (n);
2877 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2879 /** common subexpression elimination **/
2880 /* Checks whether n is already available. */
2881 /* The block input is used to distinguish different subexpressions. Right
2882 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2883 subexpressions within a block. */
2885 n = identify_cons (current_ir_graph->value_table, n);
2888 edges_node_deleted(oldn, current_ir_graph);
2890 /* We found an existing, better node, so we can deallocate the old node. */
2891 obstack_free (current_ir_graph->obst, oldn);
2896 /* Some more constant expression evaluation that does not allow to
2898 iro = get_irn_opcode(n);
2899 if (get_opt_constant_folding() ||
2900 (iro == iro_Cond) ||
2901 (iro == iro_Proj) ||
2902 (iro == iro_Sel)) /* Flags tested local. */
2903 n = transform_node (n);
2905 /* Remove nodes with dead (Bad) input.
2906 Run always for transformation induced Bads. */
2909 /* Now we have a legal, useful node. Enter it in hash table for cse */
2910 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2911 n = identify_remember (current_ir_graph->value_table, n);
2919 * These optimizations never deallocate nodes (in place). This can cause dead
2920 * nodes lying on the obstack. Remove these by a dead node elimination,
2921 * i.e., a copying garbage collection.
2924 optimize_in_place_2 (ir_node *n)
2928 opcode iro = get_irn_opcode(n);
2930 type *old_tp = get_irn_type(n);
2932 int i, arity = get_irn_arity(n);
2933 for (i = 0; i < arity && !old_tp; ++i)
2934 old_tp = get_irn_type(get_irn_n(n, i));
2937 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2939 /* if not optimize return n */
2942 /* Here this is possible. Why? */
2946 /* constant expression evaluation / constant folding */
2947 if (get_opt_constant_folding()) {
2948 /* constants can not be evaluated */
2949 if (iro != iro_Const) {
2950 /* try to evaluate */
2951 tv = computed_value(n);
2952 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2953 /* evaluation was successful -- replace the node. */
2954 n = new_Const (get_tarval_mode (tv), tv);
2956 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2957 set_Const_type(n, old_tp);
2959 DBG_OPT_CSTEVAL(oldn, n);
2965 /* remove unnecessary nodes */
2966 if (get_opt_constant_folding() ||
2967 (iro == iro_Phi) || /* always optimize these nodes. */
2968 (iro == iro_Id) || /* ... */
2969 (iro == iro_Proj) || /* ... */
2970 (iro == iro_Block) ) /* Flags tested local. */
2971 n = equivalent_node (n);
2973 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2975 /** common subexpression elimination **/
2976 /* Checks whether n is already available. */
2977 /* The block input is used to distinguish different subexpressions. Right
2978 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2979 subexpressions within a block. */
2980 if (get_opt_cse()) {
2981 n = identify (current_ir_graph->value_table, n);
2984 /* Some more constant expression evaluation. */
2985 iro = get_irn_opcode(n);
2986 if (get_opt_constant_folding() ||
2987 (iro == iro_Cond) ||
2988 (iro == iro_Proj) ||
2989 (iro == iro_Sel)) /* Flags tested local. */
2990 n = transform_node (n);
2992 /* Remove nodes with dead (Bad) input.
2993 Run always for transformation induced Bads. */
2996 /* Now we can verify the node, as it has no dead inputs any more. */
2999 /* Now we have a legal, useful node. Enter it in hash table for cse.
3000 Blocks should be unique anyways. (Except the successor of start:
3001 is cse with the start block!) */
3002 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
3003 n = identify_remember (current_ir_graph->value_table, n);
3009 * Wrapper for external use, set proper status bits after optimization.
3012 optimize_in_place (ir_node *n)
3014 /* Handle graph state */
3015 assert(get_irg_phase_state(current_ir_graph) != phase_building);
3017 if (get_opt_global_cse())
3018 set_irg_pinned(current_ir_graph, op_pin_state_floats);
3019 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
3020 set_irg_outs_inconsistent(current_ir_graph);
3022 /* Maybe we could also test whether optimizing the node can
3023 change the control graph. */
3024 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
3025 set_irg_dom_inconsistent(current_ir_graph);
3026 return optimize_in_place_2 (n);
3030 * set the default ir op operations
3032 ir_op *firm_set_default_operations(ir_op *op)
3034 op = firm_set_default_computed_value(op);
3035 op = firm_set_default_equivalent_node(op);
3036 op = firm_set_default_transform_node(op);
3037 op = firm_set_default_node_cmp_attr(op);
3038 op = firm_set_default_get_type(op);