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 to 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(pred);
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);
1666 * Does all optimizations on nodes that must be done on it's Proj's
1667 * because of creating new nodes.
1669 * Transform a Div/Mod/DivMod with a non-zero constant.
1670 * Removes the exceptions and routes the memory to the NoMem node.
1672 * Optimizes jump tables by removing all impossible cases.
1674 * Normalizes and optimizes Cmp nodes.
1676 static ir_node *transform_node_Proj(ir_node *proj)
1678 ir_node *n = get_Proj_pred(proj);
1683 switch (get_irn_opcode(n)) {
1685 b = get_Div_right(n);
1688 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1689 proj_nr = get_Proj_proj(proj);
1691 /* this node may float */
1692 set_irn_pinned(n, op_pin_state_floats);
1694 if (proj_nr == pn_Div_X_except) {
1695 /* we found an exception handler, remove it */
1698 /* the memory Proj can be removed */
1699 ir_node *res = get_Div_mem(n);
1700 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1701 if (proj_nr == pn_Div_M)
1707 b = get_Mod_right(n);
1710 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1711 proj_nr = get_Proj_proj(proj);
1713 /* this node may float */
1714 set_irn_pinned(n, op_pin_state_floats);
1716 if (proj_nr == pn_Mod_X_except) {
1717 /* we found an exception handler, remove it */
1720 /* the memory Proj can be removed */
1721 ir_node *res = get_Mod_mem(n);
1722 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1723 if (proj_nr == pn_Mod_M)
1729 b = get_DivMod_right(n);
1732 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1733 proj_nr = get_Proj_proj(proj);
1735 /* this node may float */
1736 set_irn_pinned(n, op_pin_state_floats);
1738 if (proj_nr == pn_DivMod_X_except) {
1739 /* we found an exception handler, remove it */
1743 /* the memory Proj can be removed */
1744 ir_node *res = get_DivMod_mem(n);
1745 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1746 if (proj_nr == pn_DivMod_M)
1753 if (get_opt_unreachable_code()) {
1754 b = get_Cond_selector(n);
1757 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1758 /* we have a constant switch */
1759 long num = get_Proj_proj(proj);
1761 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1762 if (get_tarval_long(tb) == num) {
1763 /* Do NOT create a jump here, or we will have 2 control flow ops
1764 * in a block. This case is optimized away in optimize_cf(). */
1775 if (get_opt_reassociation()) {
1776 ir_node *left = get_Cmp_left(n);
1777 ir_node *right = get_Cmp_right(n);
1781 ir_mode *mode = NULL;
1783 proj_nr = get_Proj_proj(proj);
1786 * First step: normalize the compare op
1787 * by placing the constant on the right site
1788 * or moving the lower address node to the left.
1789 * We ignore the case that both are constants, then
1790 * this compare should be optimized away.
1792 if (get_irn_op(right) == op_Const)
1794 else if (get_irn_op(left) == op_Const) {
1799 proj_nr = get_swapped_pnc(proj_nr);
1802 else if (left > right) {
1808 proj_nr = get_swapped_pnc(proj_nr);
1813 * Second step: Try to reduce the magnitude
1814 * of a constant. This may help to generate better code
1815 * later and may help to normalize more compares.
1816 * Of course this is only possible for integer values.
1819 mode = get_irn_mode(c);
1820 tv = get_Const_tarval(c);
1822 if (tv != tarval_bad) {
1823 /* the following optimization is possibe on modes without Overflow
1824 * on Unary Minus or on == and !=:
1825 * -a CMP c ==> a swap(CMP) -c
1827 * Beware: for two-complement Overflow may occur, so only == and != can
1828 * be optimized, see this:
1829 * -MININT < 0 =/=> MININT > 0 !!!
1831 if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
1832 (!mode_overflow_on_unary_Minus(mode) ||
1833 (mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
1834 left = get_Minus_op(left);
1835 tv = tarval_sub(get_tarval_null(mode), tv);
1837 proj_nr = get_swapped_pnc(proj_nr);
1841 /* for integer modes, we have more */
1842 if (mode_is_int(mode)) {
1843 /* Ne includes Unordered which is not possible on integers.
1844 * However, frontends often use this wrong, so fix it here */
1845 if (proj_nr == pn_Cmp_Ne) {
1846 proj_nr = pn_Cmp_Lg;
1847 set_Proj_proj(proj, proj_nr);
1850 /* c > 0 : a < c ==> a <= (c-1) a >= c ==> a > (c-1) */
1851 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
1852 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Gt) {
1853 tv = tarval_sub(tv, get_tarval_one(mode));
1855 proj_nr ^= pn_Cmp_Eq;
1858 /* c < 0 : a > c ==> a >= (c+1) a <= c ==> a < (c+1) */
1859 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
1860 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Lt) {
1861 tv = tarval_add(tv, get_tarval_one(mode));
1863 proj_nr ^= pn_Cmp_Eq;
1867 /* the following reassociations work only for == and != */
1869 /* a-b == 0 ==> a == b, a-b != 0 ==> a != b */
1870 if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
1871 if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
1872 right = get_Sub_right(left);
1873 left = get_Sub_left(left);
1875 tv = value_of(right);
1880 if (tv != tarval_bad) {
1881 ir_op *op = get_irn_op(left);
1883 /* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */
1885 ir_node *c1 = get_Sub_right(left);
1886 tarval *tv2 = value_of(c1);
1888 if (tv2 != tarval_bad) {
1889 tv2 = tarval_add(tv, value_of(c1));
1891 if (tv2 != tarval_bad) {
1892 left = get_Sub_left(left);
1898 /* a+c1 == c2 ==> a == c2-c1, a+c1 != c2 ==> a != c2-c1 */
1899 else if (op == op_Add) {
1900 ir_node *a_l = get_Add_left(left);
1901 ir_node *a_r = get_Add_right(left);
1905 if (get_irn_op(a_l) == op_Const) {
1907 tv2 = value_of(a_l);
1911 tv2 = value_of(a_r);
1914 if (tv2 != tarval_bad) {
1915 tv2 = tarval_sub(tv, tv2);
1917 if (tv2 != tarval_bad) {
1930 ir_node *block = get_nodes_block(n);
1932 if (changed & 2) /* need a new Const */
1933 right = new_Const(mode, tv);
1935 /* create a new compare */
1936 n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
1939 set_Proj_pred(proj, n);
1940 set_Proj_proj(proj, proj_nr);
1946 /* should not happen, but if it does will be optimized away */
1954 /* we have added a Tuple, optimize it for the current Proj away */
1955 return equivalent_node_Proj(proj);
1959 * returns the operands of a commutative bin-op, if one operand is
1960 * a const, it is returned as the second one.
1962 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1964 ir_node *op_a = get_binop_left(binop);
1965 ir_node *op_b = get_binop_right(binop);
1967 assert(is_op_commutative(get_irn_op(binop)));
1969 if (get_irn_op(op_a) == op_Const) {
1980 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1981 * Such pattern may arise in bitfield stores.
1983 * value c4 value c4 & c2
1984 * AND c3 AND c1 | c3
1989 static ir_node *transform_node_Or_bf_store(ir_node *or)
1993 ir_node *and_l, *c3;
1994 ir_node *value, *c4;
1995 ir_node *new_and, *new_const, *block;
1996 ir_mode *mode = get_irn_mode(or);
1998 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
2000 get_comm_Binop_Ops(or, &and, &c1);
2001 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
2004 get_comm_Binop_Ops(and, &or_l, &c2);
2005 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
2008 get_comm_Binop_Ops(or_l, &and_l, &c3);
2009 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2012 get_comm_Binop_Ops(and_l, &value, &c4);
2013 if (get_irn_op(c4) != op_Const)
2016 /* ok, found the pattern, check for conditions */
2017 assert(mode == get_irn_mode(and));
2018 assert(mode == get_irn_mode(or_l));
2019 assert(mode == get_irn_mode(and_l));
2021 tv1 = get_Const_tarval(c1);
2022 tv2 = get_Const_tarval(c2);
2023 tv3 = get_Const_tarval(c3);
2024 tv4 = get_Const_tarval(c4);
2026 tv = tarval_or(tv4, tv2);
2027 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2028 /* have at least one 0 at the same bit position */
2032 n_tv4 = tarval_not(tv4);
2033 if (tv3 != tarval_and(tv3, n_tv4)) {
2034 /* bit in the or_mask is outside the and_mask */
2038 n_tv2 = tarval_not(tv2);
2039 if (tv1 != tarval_and(tv1, n_tv2)) {
2040 /* bit in the or_mask is outside the and_mask */
2044 /* ok, all conditions met */
2045 block = get_nodes_block(or);
2047 new_and = new_r_And(current_ir_graph, block,
2048 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
2050 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
2052 set_Or_left(or, new_and);
2053 set_Or_right(or, new_const);
2055 /* check for more */
2056 return transform_node_Or_bf_store(or);
2060 * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
2062 static ir_node *transform_node_Or_Rot(ir_node *or)
2064 ir_mode *mode = get_irn_mode(or);
2065 ir_node *shl, *shr, *block;
2066 ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
2069 if (! mode_is_int(mode))
2072 shl = get_binop_left(or);
2073 shr = get_binop_right(or);
2075 if (get_irn_op(shl) == op_Shr) {
2076 if (get_irn_op(shr) != op_Shl)
2083 else if (get_irn_op(shl) != op_Shl)
2085 else if (get_irn_op(shr) != op_Shr)
2088 x = get_Shl_left(shl);
2089 if (x != get_Shr_left(shr))
2092 c1 = get_Shl_right(shl);
2093 c2 = get_Shr_right(shr);
2094 if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
2095 tv1 = get_Const_tarval(c1);
2096 if (! tarval_is_long(tv1))
2099 tv2 = get_Const_tarval(c2);
2100 if (! tarval_is_long(tv2))
2103 if (get_tarval_long(tv1) + get_tarval_long(tv2)
2104 != get_mode_size_bits(mode))
2107 /* yet, condition met */
2108 block = get_nodes_block(or);
2110 n = new_r_Rot(current_ir_graph, block, x, c1, mode);
2112 DBG_OPT_ALGSIM1(or, shl, shr, n);
2115 else if (get_irn_op(c1) == op_Sub) {
2119 if (get_Sub_right(sub) != v)
2122 c1 = get_Sub_left(sub);
2123 if (get_irn_op(c1) != op_Const)
2126 tv1 = get_Const_tarval(c1);
2127 if (! tarval_is_long(tv1))
2130 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2133 /* yet, condition met */
2134 block = get_nodes_block(or);
2136 /* a Rot right is not supported, so use a rot left */
2137 n = new_r_Rot(current_ir_graph, block, x, sub, mode);
2139 DBG_OPT_ALGSIM0(or, n);
2142 else if (get_irn_op(c2) == op_Sub) {
2146 c1 = get_Sub_left(sub);
2147 if (get_irn_op(c1) != op_Const)
2150 tv1 = get_Const_tarval(c1);
2151 if (! tarval_is_long(tv1))
2154 if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2157 /* yet, condition met */
2158 block = get_nodes_block(or);
2161 n = new_r_Rot(current_ir_graph, block, x, v, mode);
2163 DBG_OPT_ALGSIM0(or, n);
2173 static ir_node *transform_node_Or(ir_node *or)
2175 or = transform_node_Or_bf_store(or);
2176 or = transform_node_Or_Rot(or);
2182 static ir_node *transform_node(ir_node *n);
2185 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
2187 static ir_node *transform_node_shift(ir_node *n)
2189 ir_node *left, *right;
2190 tarval *tv1, *tv2, *res;
2192 int modulo_shf, flag;
2194 left = get_binop_left(n);
2196 /* different operations */
2197 if (get_irn_op(left) != get_irn_op(n))
2200 right = get_binop_right(n);
2201 tv1 = value_of(right);
2202 if (tv1 == tarval_bad)
2205 tv2 = value_of(get_binop_right(left));
2206 if (tv2 == tarval_bad)
2209 res = tarval_add(tv1, tv2);
2211 /* beware: a simple replacement works only, if res < modulo shift */
2212 mode = get_irn_mode(n);
2216 modulo_shf = get_mode_modulo_shift(mode);
2217 if (modulo_shf > 0) {
2218 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
2220 if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
2227 /* ok, we can replace it */
2228 ir_node *in[2], *irn, *block = get_nodes_block(n);
2230 in[0] = get_binop_left(left);
2231 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
2233 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
2235 DBG_OPT_ALGSIM0(n, irn);
2237 return transform_node(irn);
2242 #define transform_node_Shr transform_node_shift
2243 #define transform_node_Shrs transform_node_shift
2244 #define transform_node_Shl transform_node_shift
2247 * Remove dead blocks in keepalive list. We do not generate a new End node.
2249 static ir_node *transform_node_End(ir_node *n) {
2250 int i, n_keepalives = get_End_n_keepalives(n);
2252 for (i = 0; i < n_keepalives; ++i) {
2253 ir_node *ka = get_End_keepalive(n, i);
2254 if (is_Block(ka) && is_Block_dead(ka))
2255 set_End_keepalive(n, i, new_Bad());
2261 * Optimize a Mux into some simplier cases.
2263 static ir_node *transform_node_Mux(ir_node *n)
2265 ir_node *oldn = n, *sel = get_Mux_sel(n);
2266 ir_mode *mode = get_irn_mode(n);
2268 if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
2269 ir_node *cmp = get_Proj_pred(sel);
2270 long proj_nr = get_Proj_proj(sel);
2271 ir_node *f = get_Mux_false(n);
2272 ir_node *t = get_Mux_true(n);
2274 if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
2275 ir_node *block = get_nodes_block(n);
2278 * Note: normalization puts the constant on the right site,
2279 * so we check only one case.
2281 * Note further that these optimization work even for floating point
2282 * with NaN's because -NaN == NaN.
2283 * However, if +0 and -0 is handled differently, we cannot use the first one.
2285 if (get_irn_op(f) == op_Minus &&
2286 get_Minus_op(f) == t &&
2287 get_Cmp_left(cmp) == t) {
2289 if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2290 /* Mux(a >=/> 0, -a, a) ==> Abs(a) */
2291 n = new_rd_Abs(get_irn_dbg_info(n),
2295 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2298 else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2299 /* Mux(a <=/< 0, -a, a) ==> Minus(Abs(a)) */
2300 n = new_rd_Abs(get_irn_dbg_info(n),
2304 n = new_rd_Minus(get_irn_dbg_info(n),
2309 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2313 else if (get_irn_op(t) == op_Minus &&
2314 get_Minus_op(t) == f &&
2315 get_Cmp_left(cmp) == f) {
2317 if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2318 /* Mux(a <=/< 0, a, -a) ==> Abs(a) */
2319 n = new_rd_Abs(get_irn_dbg_info(n),
2323 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2326 else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2327 /* Mux(a >=/> 0, a, -a) ==> Minus(Abs(a)) */
2328 n = new_rd_Abs(get_irn_dbg_info(n),
2332 n = new_rd_Minus(get_irn_dbg_info(n),
2337 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2342 if (mode_is_int(mode) && mode_is_signed(mode) &&
2343 get_mode_arithmetic(mode) == irma_twos_complement) {
2344 ir_node *x = get_Cmp_left(cmp);
2346 /* the following optimization works only with signed integer two-complement mode */
2348 if (mode == get_irn_mode(x)) {
2350 * FIXME: this restriction is two rigid, as it would still
2351 * work if mode(x) = Hs and mode == Is, but at least it removes
2354 if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
2355 classify_Const(t) == CNST_ALL_ONE &&
2356 classify_Const(f) == CNST_NULL) {
2358 * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
2362 n = new_rd_Shrs(get_irn_dbg_info(n),
2363 current_ir_graph, block, x,
2364 new_r_Const_long(current_ir_graph, block, mode_Iu,
2365 get_mode_size_bits(mode) - 1),
2367 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2370 else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
2371 classify_Const(t) == CNST_ONE &&
2372 classify_Const(f) == CNST_NULL) {
2374 * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
2378 n = new_rd_Shr(get_irn_dbg_info(n),
2379 current_ir_graph, block,
2380 new_r_Minus(current_ir_graph, block, x, mode),
2381 new_r_Const_long(current_ir_graph, block, mode_Iu,
2382 get_mode_size_bits(mode) - 1),
2384 DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2391 return arch_transform_node_Mux(n);
2395 * Tries several [inplace] [optimizing] transformations and returns an
2396 * equivalent node. The difference to equivalent_node() is that these
2397 * transformations _do_ generate new nodes, and thus the old node must
2398 * not be freed even if the equivalent node isn't the old one.
2400 static ir_node *transform_node(ir_node *n)
2402 if (n->op->transform_node)
2403 n = n->op->transform_node(n);
2408 * set the default transform node operation
2410 static ir_op *firm_set_default_transform_node(ir_op *op)
2414 op->transform_node = transform_node_##a; \
2437 op->transform_node = NULL;
2445 /* **************** Common Subexpression Elimination **************** */
2447 /** The size of the hash table used, should estimate the number of nodes
2449 #define N_IR_NODES 512
2451 /** Compares the attributes of two Const nodes. */
2452 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2454 return (get_Const_tarval(a) != get_Const_tarval(b))
2455 || (get_Const_type(a) != get_Const_type(b));
2458 /** Compares the attributes of two Proj nodes. */
2459 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2461 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2464 /** Compares the attributes of two Filter nodes. */
2465 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2467 return get_Filter_proj(a) != get_Filter_proj(b);
2470 /** Compares the attributes of two Alloc nodes. */
2471 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2473 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2474 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2477 /** Compares the attributes of two Free nodes. */
2478 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2480 return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2481 || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2484 /** Compares the attributes of two SymConst nodes. */
2485 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2487 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2488 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2489 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2492 /** Compares the attributes of two Call nodes. */
2493 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2495 return (get_irn_call_attr(a) != get_irn_call_attr(b));
2498 /** Compares the attributes of two Sel nodes. */
2499 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2501 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
2502 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
2503 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
2504 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2505 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
2508 /** Compares the attributes of two Phi nodes. */
2509 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2511 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2514 /** Compares the attributes of two Cast nodes. */
2515 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2517 return get_Cast_type(a) != get_Cast_type(b);
2520 /** Compares the attributes of two Load nodes. */
2521 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2523 if (get_Load_volatility(a) == volatility_is_volatile ||
2524 get_Load_volatility(b) == volatility_is_volatile)
2525 /* NEVER do CSE on volatile Loads */
2528 return get_Load_mode(a) != get_Load_mode(b);
2531 /** Compares the attributes of two Store nodes. */
2532 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2534 /* NEVER do CSE on volatile Stores */
2535 return (get_Store_volatility(a) == volatility_is_volatile ||
2536 get_Store_volatility(b) == volatility_is_volatile);
2540 * set the default node attribute compare operation
2542 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2546 op->node_cmp_attr = node_cmp_attr_##a; \
2563 op->node_cmp_attr = NULL;
2571 * Compare function for two nodes in the hash table. Gets two
2572 * nodes as parameters. Returns 0 if the nodes are a cse.
2575 vt_cmp (const void *elt, const void *key)
2583 if (a == b) return 0;
2585 if ((get_irn_op(a) != get_irn_op(b)) ||
2586 (get_irn_mode(a) != get_irn_mode(b))) return 1;
2588 /* compare if a's in and b's in are of equal length */
2589 irn_arity_a = get_irn_intra_arity (a);
2590 if (irn_arity_a != get_irn_intra_arity(b))
2593 /* for block-local cse and op_pin_state_pinned nodes: */
2594 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2595 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2599 /* compare a->in[0..ins] with b->in[0..ins] */
2600 for (i = 0; i < irn_arity_a; i++)
2601 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2605 * here, we already now that the nodes are identical except their
2608 if (a->op->node_cmp_attr)
2609 return a->op->node_cmp_attr(a, b);
2615 * Calculate a hash value of a node.
2618 ir_node_hash (ir_node *node)
2623 if (node->op == op_Const) {
2624 /* special value for const, as they only differ in their tarval. */
2625 h = HASH_PTR(node->attr.con.tv);
2626 h = 9*h + HASH_PTR(get_irn_mode(node));
2627 } else if (node->op == op_SymConst) {
2628 /* special value for const, as they only differ in their symbol. */
2629 h = HASH_PTR(node->attr.i.sym.type_p);
2630 h = 9*h + HASH_PTR(get_irn_mode(node));
2633 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2634 h = irn_arity = get_irn_intra_arity(node);
2636 /* consider all in nodes... except the block if not a control flow. */
2637 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
2638 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2642 h = 9*h + HASH_PTR(get_irn_mode(node));
2644 h = 9*h + HASH_PTR(get_irn_op(node));
2651 new_identities(void) {
2652 return new_pset(vt_cmp, N_IR_NODES);
2656 del_identities(pset *value_table) {
2657 del_pset(value_table);
2661 * Return the canonical node computing the same value as n.
2662 * Looks up the node in a hash table.
2664 * For Const nodes this is performed in the constructor, too. Const
2665 * nodes are extremely time critical because of their frequent use in
2666 * constant string arrays.
2668 static INLINE ir_node *
2669 identify (pset *value_table, ir_node *n)
2673 if (!value_table) return n;
2675 if (get_opt_reassociation()) {
2676 if (is_op_commutative(get_irn_op(n))) {
2677 ir_node *l = get_binop_left(n);
2678 ir_node *r = get_binop_right(n);
2680 /* for commutative operators perform a OP b == b OP a */
2682 set_binop_left(n, r);
2683 set_binop_right(n, l);
2688 o = pset_find (value_table, n, ir_node_hash (n));
2697 * During construction we set the op_pin_state_pinned flag in the graph right when the
2698 * optimization is performed. The flag turning on procedure global cse could
2699 * be changed between two allocations. This way we are safe.
2701 static INLINE ir_node *
2702 identify_cons (pset *value_table, ir_node *n) {
2705 n = identify(value_table, n);
2706 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2707 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2712 * Return the canonical node computing the same value as n.
2713 * Looks up the node in a hash table, enters it in the table
2714 * if it isn't there yet.
2717 identify_remember (pset *value_table, ir_node *n)
2721 if (!value_table) return n;
2723 if (get_opt_reassociation()) {
2724 if (is_op_commutative(get_irn_op(n))) {
2725 ir_node *l = get_binop_left(n);
2726 ir_node *r = get_binop_right(n);
2728 /* for commutative operators perform a OP b == b OP a */
2730 set_binop_left(n, r);
2731 set_binop_right(n, l);
2736 /* lookup or insert in hash table with given hash key. */
2737 o = pset_insert (value_table, n, ir_node_hash (n));
2747 add_identities (pset *value_table, ir_node *node) {
2748 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2749 identify_remember (value_table, node);
2753 * garbage in, garbage out. If a node has a dead input, i.e., the
2754 * Bad node is input to the node, return the Bad node.
2756 static INLINE ir_node *
2757 gigo (ir_node *node)
2760 ir_op* op = get_irn_op(node);
2762 /* remove garbage blocks by looking at control flow that leaves the block
2763 and replacing the control flow by Bad. */
2764 if (get_irn_mode(node) == mode_X) {
2765 ir_node *block = get_nodes_block(node);
2766 if (!get_Block_matured(block)) return node; /* Don't optimize nodes in immature blocks. */
2767 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2769 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2770 irn_arity = get_irn_arity(block);
2771 for (i = 0; i < irn_arity; i++) {
2772 if (!is_Bad(get_irn_n(block, i))) break;
2774 if (i == irn_arity) return new_Bad();
2778 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2779 blocks predecessors is dead. */
2780 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2781 irn_arity = get_irn_arity(node);
2783 if (is_Block_dead(get_nodes_block(node)))
2786 for (i = 0; i < irn_arity; i++) {
2787 if (is_Bad(get_irn_n(node, i))) {
2793 /* With this code we violate the agreement that local_optimize
2794 only leaves Bads in Block, Phi and Tuple nodes. */
2795 /* If Block has only Bads as predecessors it's garbage. */
2796 /* If Phi has only Bads as predecessors it's garbage. */
2797 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2798 irn_arity = get_irn_arity(node);
2799 for (i = 0; i < irn_arity; i++) {
2800 if (!is_Bad(get_irn_n(node, i))) break;
2802 if (i == irn_arity) node = new_Bad();
2810 * These optimizations deallocate nodes from the obstack.
2811 * It can only be called if it is guaranteed that no other nodes
2812 * reference this one, i.e., right after construction of a node.
2815 optimize_node (ir_node *n)
2819 opcode iro = get_irn_opcode(n);
2821 type *old_tp = get_irn_type(n);
2823 int i, arity = get_irn_arity(n);
2824 for (i = 0; i < arity && !old_tp; ++i)
2825 old_tp = get_irn_type(get_irn_n(n, i));
2828 /* Always optimize Phi nodes: part of the construction. */
2829 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2831 /* constant expression evaluation / constant folding */
2832 if (get_opt_constant_folding()) {
2833 /* constants can not be evaluated */
2834 if (iro != iro_Const) {
2835 /* try to evaluate */
2836 tv = computed_value(n);
2837 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2841 * we MUST copy the node here temporary, because it's still needed
2842 * for DBG_OPT_CSTEVAL
2844 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2845 oldn = alloca(node_size);
2847 memcpy(oldn, n, node_size);
2848 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2850 /* ARG, copy the in array, we need it for statistics */
2851 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2854 edges_node_deleted(n, current_ir_graph);
2856 /* evaluation was successful -- replace the node. */
2857 obstack_free (current_ir_graph->obst, n);
2858 nw = new_Const (get_tarval_mode (tv), tv);
2860 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2861 set_Const_type(nw, old_tp);
2862 DBG_OPT_CSTEVAL(oldn, nw);
2868 /* remove unnecessary nodes */
2869 if (get_opt_constant_folding() ||
2870 (iro == iro_Phi) || /* always optimize these nodes. */
2872 (iro == iro_Proj) ||
2873 (iro == iro_Block) ) /* Flags tested local. */
2874 n = equivalent_node (n);
2876 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2878 /** common subexpression elimination **/
2879 /* Checks whether n is already available. */
2880 /* The block input is used to distinguish different subexpressions. Right
2881 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2882 subexpressions within a block. */
2884 n = identify_cons (current_ir_graph->value_table, n);
2887 edges_node_deleted(oldn, current_ir_graph);
2889 /* We found an existing, better node, so we can deallocate the old node. */
2890 obstack_free (current_ir_graph->obst, oldn);
2895 /* Some more constant expression evaluation that does not allow to
2897 iro = get_irn_opcode(n);
2898 if (get_opt_constant_folding() ||
2899 (iro == iro_Cond) ||
2900 (iro == iro_Proj) ||
2901 (iro == iro_Sel)) /* Flags tested local. */
2902 n = transform_node (n);
2904 /* Remove nodes with dead (Bad) input.
2905 Run always for transformation induced Bads. */
2908 /* Now we have a legal, useful node. Enter it in hash table for cse */
2909 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2910 n = identify_remember (current_ir_graph->value_table, n);
2918 * These optimizations never deallocate nodes (in place). This can cause dead
2919 * nodes lying on the obstack. Remove these by a dead node elimination,
2920 * i.e., a copying garbage collection.
2923 optimize_in_place_2 (ir_node *n)
2927 opcode iro = get_irn_opcode(n);
2929 type *old_tp = get_irn_type(n);
2931 int i, arity = get_irn_arity(n);
2932 for (i = 0; i < arity && !old_tp; ++i)
2933 old_tp = get_irn_type(get_irn_n(n, i));
2936 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2938 /* if not optimize return n */
2941 /* Here this is possible. Why? */
2945 /* constant expression evaluation / constant folding */
2946 if (get_opt_constant_folding()) {
2947 /* constants can not be evaluated */
2948 if (iro != iro_Const) {
2949 /* try to evaluate */
2950 tv = computed_value(n);
2951 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2952 /* evaluation was successful -- replace the node. */
2953 n = new_Const (get_tarval_mode (tv), tv);
2955 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2956 set_Const_type(n, old_tp);
2958 DBG_OPT_CSTEVAL(oldn, n);
2964 /* remove unnecessary nodes */
2965 if (get_opt_constant_folding() ||
2966 (iro == iro_Phi) || /* always optimize these nodes. */
2967 (iro == iro_Id) || /* ... */
2968 (iro == iro_Proj) || /* ... */
2969 (iro == iro_Block) ) /* Flags tested local. */
2970 n = equivalent_node (n);
2972 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2974 /** common subexpression elimination **/
2975 /* Checks whether n is already available. */
2976 /* The block input is used to distinguish different subexpressions. Right
2977 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2978 subexpressions within a block. */
2979 if (get_opt_cse()) {
2980 n = identify (current_ir_graph->value_table, n);
2983 /* Some more constant expression evaluation. */
2984 iro = get_irn_opcode(n);
2985 if (get_opt_constant_folding() ||
2986 (iro == iro_Cond) ||
2987 (iro == iro_Proj) ||
2988 (iro == iro_Sel)) /* Flags tested local. */
2989 n = transform_node (n);
2991 /* Remove nodes with dead (Bad) input.
2992 Run always for transformation induced Bads. */
2995 /* Now we can verify the node, as it has no dead inputs any more. */
2998 /* Now we have a legal, useful node. Enter it in hash table for cse.
2999 Blocks should be unique anyways. (Except the successor of start:
3000 is cse with the start block!) */
3001 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
3002 n = identify_remember (current_ir_graph->value_table, n);
3008 * Wrapper for external use, set proper status bits after optimization.
3011 optimize_in_place (ir_node *n)
3013 /* Handle graph state */
3014 assert(get_irg_phase_state(current_ir_graph) != phase_building);
3016 if (get_opt_global_cse())
3017 set_irg_pinned(current_ir_graph, op_pin_state_floats);
3018 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
3019 set_irg_outs_inconsistent(current_ir_graph);
3021 /* Maybe we could also test whether optimizing the node can
3022 change the control graph. */
3023 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
3024 set_irg_dom_inconsistent(current_ir_graph);
3025 return optimize_in_place_2 (n);
3029 * set the default ir op operations
3031 ir_op *firm_set_default_operations(ir_op *op)
3033 op = firm_set_default_computed_value(op);
3034 op = firm_set_default_equivalent_node(op);
3035 op = firm_set_default_transform_node(op);
3036 op = firm_set_default_node_cmp_attr(op);
3037 op = firm_set_default_get_type(op);