3 * File name: ir/ir/iropt.c
4 * Purpose: iropt --- optimizations intertwined with IR construction.
5 * Author: Christian Schaefer
6 * Modified by: Goetz Lindenmaier
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 # include "irnode_t.h"
18 # include "irgraph_t.h"
19 # include "irmode_t.h"
21 # include "ircons_t.h"
25 # include "dbginfo_t.h"
26 # include "iropt_dbg.h"
27 # include "irflag_t.h"
28 # include "firmstat.h"
31 /* Make types visible to allow most efficient access */
32 # include "entity_t.h"
35 * Trivial INLINEable routine for copy propagation.
36 * Does follow Ids, needed to optimize INLINEd code.
38 static INLINE ir_node *
39 follow_Id (ir_node *n)
41 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
46 * return the value of a Constant
48 static tarval *computed_value_Const(ir_node *n)
50 return get_Const_tarval(n);
54 * return the value of a 'sizeof' SymConst
56 static tarval *computed_value_SymConst(ir_node *n)
58 if ((get_SymConst_kind(n) == symconst_size) &&
59 (get_type_state(get_SymConst_type(n))) == layout_fixed)
60 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
65 * return the value of an Add
67 static tarval *computed_value_Add(ir_node *n)
69 ir_node *a = get_Add_left(n);
70 ir_node *b = get_Add_right(n);
72 tarval *ta = value_of(a);
73 tarval *tb = value_of(b);
75 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
76 return tarval_add(ta, tb);
82 * return the value of a Sub
85 static tarval *computed_value_Sub(ir_node *n)
87 ir_node *a = get_Sub_left(n);
88 ir_node *b = get_Sub_right(n);
94 return get_tarval_null(get_irn_mode(n));
99 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
100 return tarval_sub(ta, tb);
106 * return the value of an unary Minus
108 static tarval *computed_value_Minus(ir_node *n)
110 ir_node *a = get_Minus_op(n);
111 tarval *ta = value_of(a);
113 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
114 return tarval_neg(ta);
120 * return the value of a Mul
122 static tarval *computed_value_Mul(ir_node *n)
124 ir_node *a = get_Mul_left(n);
125 ir_node *b = get_Mul_right(n);
127 tarval *ta = value_of(a);
128 tarval *tb = value_of(b);
130 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
131 return tarval_mul(ta, tb);
133 /* a*0 = 0 or 0*b = 0:
134 calls computed_value recursive and returns the 0 with proper
136 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
138 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
145 * return the value of a floating point Quot
147 static tarval *computed_value_Quot(ir_node *n)
149 ir_node *a = get_Quot_left(n);
150 ir_node *b = get_Quot_right(n);
152 tarval *ta = value_of(a);
153 tarval *tb = value_of(b);
155 /* This was missing in original implementation. Why? */
156 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
157 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
158 return tarval_quo(ta, tb);
164 * calculate the value of an integer Div of two nodes
165 * Special case: 0 / b
167 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
169 tarval *ta = value_of(a);
170 tarval *tb = value_of(b);
172 /* Compute c1 / c2 or 0 / a, a != 0 */
173 if (ta != tarval_bad) {
174 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
175 return tarval_div(ta, tb);
176 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
183 * return the value of an integer Div
185 static tarval *computed_value_Div(ir_node *n)
187 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
191 * calculate the value of an integer Mod of two nodes
192 * Special case: a % 1
194 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
196 tarval *ta = value_of(a);
197 tarval *tb = value_of(b);
199 /* Compute c1 % c2 or a % 1 */
200 if (tb != tarval_bad) {
201 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
202 return tarval_mod(ta, tb);
203 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
204 return get_mode_null(get_irn_mode(a));
211 * return the value of an integer Mod
213 static tarval *computed_value_Mod(ir_node *n)
215 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
219 * return the value of an Abs
221 static tarval *computed_value_Abs(ir_node *n)
223 ir_node *a = get_Abs_op(n);
224 tarval *ta = value_of(a);
226 if (ta != tarval_bad)
227 return tarval_abs(ta);
233 * return the value of an And
234 * Special case: a & 0, 0 & b
236 static tarval *computed_value_And(ir_node *n)
238 ir_node *a = get_And_left(n);
239 ir_node *b = get_And_right(n);
241 tarval *ta = value_of(a);
242 tarval *tb = value_of(b);
244 if ((ta != tarval_bad) && (tb != tarval_bad)) {
245 return tarval_and (ta, tb);
249 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
250 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
258 * return the value of an Or
259 * Special case: a | 1...1, 1...1 | b
261 static tarval *computed_value_Or(ir_node *n)
263 ir_node *a = get_Or_left(n);
264 ir_node *b = get_Or_right(n);
266 tarval *ta = value_of(a);
267 tarval *tb = value_of(b);
269 if ((ta != tarval_bad) && (tb != tarval_bad)) {
270 return tarval_or (ta, tb);
273 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
274 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
282 * return the value of an Eor
284 static tarval *computed_value_Eor(ir_node *n)
286 ir_node *a = get_Eor_left(n);
287 ir_node *b = get_Eor_right(n);
292 return get_tarval_null(get_irn_mode(n));
297 if ((ta != tarval_bad) && (tb != tarval_bad)) {
298 return tarval_eor (ta, tb);
304 * return the value of a Not
306 static tarval *computed_value_Not(ir_node *n)
308 ir_node *a = get_Not_op(n);
309 tarval *ta = value_of(a);
311 if (ta != tarval_bad)
312 return tarval_not(ta);
318 * return the value of a Shl
320 static tarval *computed_value_Shl(ir_node *n)
322 ir_node *a = get_Shl_left(n);
323 ir_node *b = get_Shl_right(n);
325 tarval *ta = value_of(a);
326 tarval *tb = value_of(b);
328 if ((ta != tarval_bad) && (tb != tarval_bad)) {
329 return tarval_shl (ta, tb);
335 * return the value of a Shr
337 static tarval *computed_value_Shr(ir_node *n)
339 ir_node *a = get_Shr_left(n);
340 ir_node *b = get_Shr_right(n);
342 tarval *ta = value_of(a);
343 tarval *tb = value_of(b);
345 if ((ta != tarval_bad) && (tb != tarval_bad)) {
346 return tarval_shr (ta, tb);
352 * return the value of a Shrs
354 static tarval *computed_value_Shrs(ir_node *n)
356 ir_node *a = get_Shrs_left(n);
357 ir_node *b = get_Shrs_right(n);
359 tarval *ta = value_of(a);
360 tarval *tb = value_of(b);
362 if ((ta != tarval_bad) && (tb != tarval_bad)) {
363 return tarval_shrs (ta, tb);
369 * return the value of a Rot
371 static tarval *computed_value_Rot(ir_node *n)
373 ir_node *a = get_Rot_left(n);
374 ir_node *b = get_Rot_right(n);
376 tarval *ta = value_of(a);
377 tarval *tb = value_of(b);
379 if ((ta != tarval_bad) && (tb != tarval_bad)) {
380 return tarval_rot (ta, tb);
386 * return the value of a Conv
388 static tarval *computed_value_Conv(ir_node *n)
390 ir_node *a = get_Conv_op(n);
391 tarval *ta = value_of(a);
393 if (ta != tarval_bad)
394 return tarval_convert_to(ta, get_irn_mode(n));
400 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
402 static tarval *computed_value_Proj(ir_node *n)
404 ir_node *a = get_Proj_pred(n);
408 /* Optimize Cmp nodes.
409 This performs a first step of unreachable code elimination.
410 Proj can not be computed, but folding a Cmp above the Proj here is
411 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
413 There are several case where we can evaluate a Cmp node:
414 1. The nodes compared are both the same. If we compare for
415 equal, greater equal, ... this will return true, else it
416 will return false. This step relies on cse.
417 2. The predecessors of Cmp are target values. We can evaluate
419 3. The predecessors are Allocs or void* constants. Allocs never
420 return NULL, they raise an exception. Therefore we can predict
422 switch (get_irn_opcode(a)) {
424 aa = get_Cmp_left(a);
425 ab = get_Cmp_right(a);
426 proj_nr = get_Proj_proj(n);
428 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
429 /* BEWARE: a == a is NOT always True for floating Point!!! */
430 /* This is a trick with the bits used for encoding the Cmp
431 Proj numbers, the following statement is not the same:
432 return new_tarval_from_long (proj_nr == Eq, mode_b) */
433 return new_tarval_from_long (proj_nr & Eq, mode_b);
435 tarval *taa = value_of(aa);
436 tarval *tab = value_of(ab);
438 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
439 /* strange checks... */
440 pnc_number flags = tarval_cmp (taa, tab);
441 if (flags != False) {
442 return new_tarval_from_long (proj_nr & flags, mode_b);
444 } else { /* check for 3.: */
445 ir_node *aaa = skip_Id(skip_Proj(aa));
446 ir_node *aba = skip_Id(skip_Proj(ab));
448 if ( ( (/* aa is ProjP and aaa is Alloc */
449 (get_irn_op(aa) == op_Proj)
450 && (mode_is_reference(get_irn_mode(aa)))
451 && (get_irn_op(aaa) == op_Alloc))
452 && ( (/* ab is constant void */
453 (get_irn_op(ab) == op_Const)
454 && (mode_is_reference(get_irn_mode(ab)))
455 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
456 || (/* ab is other Alloc */
457 (get_irn_op(ab) == op_Proj)
458 && (mode_is_reference(get_irn_mode(ab)))
459 && (get_irn_op(aba) == op_Alloc)
461 || (/* aa is void and aba is Alloc */
462 (get_irn_op(aa) == op_Const)
463 && (mode_is_reference(get_irn_mode(aa)))
464 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
465 && (get_irn_op(ab) == op_Proj)
466 && (mode_is_reference(get_irn_mode(ab)))
467 && (get_irn_op(aba) == op_Alloc)))
469 return new_tarval_from_long (proj_nr & Ne, mode_b);
475 /* compute either the Div or the Mod part */
476 proj_nr = get_Proj_proj(n);
477 if (proj_nr == pn_DivMod_res_div)
478 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
479 else if (proj_nr == pn_DivMod_res_mod)
480 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
484 if (get_Proj_proj(n) == pn_Div_res)
485 return computed_value(a);
489 if (get_Proj_proj(n) == pn_Mod_res)
490 return computed_value(a);
500 * If the parameter n can be computed, return its value, else tarval_bad.
501 * Performs constant folding.
503 * @param n The node this should be evaluated
505 tarval *computed_value(ir_node *n)
507 if (n->op->computed_value)
508 return n->op->computed_value(n);
513 * set the default computed_value evaluator
515 static ir_op *firm_set_default_computed_value(ir_op *op)
519 op->computed_value = computed_value_##a; \
544 op->computed_value = NULL;
552 /* returns 1 if the a and b are pointers to different locations. */
554 different_identity (ir_node *a, ir_node *b)
556 assert (mode_is_reference(get_irn_mode (a))
557 && mode_is_reference(get_irn_mode (b)));
559 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
560 ir_node *a1 = get_Proj_pred (a);
561 ir_node *b1 = get_Proj_pred (b);
562 if (a1 != b1 && get_irn_op (a1) == op_Alloc
563 && get_irn_op (b1) == op_Alloc)
570 static ir_node *equivalent_node_Block(ir_node *n)
574 /* The Block constructor does not call optimize, but mature_immBlock
575 calls the optimization. */
576 assert(get_Block_matured(n));
578 /* Straightening: a single entry Block following a single exit Block
579 can be merged, if it is not the Start block. */
580 /* !!! Beware, all Phi-nodes of n must have been optimized away.
581 This should be true, as the block is matured before optimize is called.
582 But what about Phi-cycles with the Phi0/Id that could not be resolved?
583 Remaining Phi nodes are just Ids. */
584 if ((get_Block_n_cfgpreds(n) == 1) &&
585 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
586 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
587 if (predblock == oldn) {
588 /* Jmp jumps into the block it is in -- deal self cycle. */
590 DBG_OPT_DEAD(oldn, n);
591 } else if (get_opt_control_flow_straightening()) {
593 DBG_OPT_STG(oldn, n);
596 else if ((get_Block_n_cfgpreds(n) == 1) &&
597 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
598 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
599 if (predblock == oldn) {
600 /* Jmp jumps into the block it is in -- deal self cycle. */
602 DBG_OPT_DEAD(oldn, n);
605 else if ((get_Block_n_cfgpreds(n) == 2) &&
606 (get_opt_control_flow_weak_simplification())) {
607 /* Test whether Cond jumps twice to this block
608 @@@ we could do this also with two loops finding two preds from several ones. */
609 ir_node *a = get_Block_cfgpred(n, 0);
610 ir_node *b = get_Block_cfgpred(n, 1);
612 if ((get_irn_op(a) == op_Proj) &&
613 (get_irn_op(b) == op_Proj) &&
614 (get_Proj_pred(a) == get_Proj_pred(b)) &&
615 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
616 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
617 /* Also a single entry Block following a single exit Block. Phis have
618 twice the same operand and will be optimized away. */
619 n = get_nodes_block(a);
620 DBG_OPT_IFSIM(oldn, a, b, n);
622 } else if (get_opt_unreachable_code() &&
623 (n != current_ir_graph->start_block) &&
624 (n != current_ir_graph->end_block) ) {
626 /* If all inputs are dead, this block is dead too, except if it is
627 the start or end block. This is a step of unreachable code
629 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
630 if (!is_Bad(get_Block_cfgpred(n, i))) break;
632 if (i == get_Block_n_cfgpreds(n))
640 * Returns a equivalent node for a Jmp, a Bad :-)
641 * Of course this only happens if the Block of the Jmp is Bad.
643 static ir_node *equivalent_node_Jmp(ir_node *n)
645 /* GL: Why not same for op_Raise?? */
646 /* unreachable code elimination */
647 if (is_Bad(get_nodes_block(n)))
653 static ir_node *equivalent_node_Cond(ir_node *n)
655 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
656 See cases for iro_Cond and iro_Proj in transform_node. */
661 * optimize operations that are commutative and have neutral 0,
662 * so a op 0 = 0 op a = a.
664 static ir_node *equivalent_node_neutral_zero(ir_node *n)
668 ir_node *a = get_binop_left(n);
669 ir_node *b = get_binop_right(n);
674 /* After running compute_node there is only one constant predecessor.
675 Find this predecessors value and remember the other node: */
676 if ((tv = value_of(a)) != tarval_bad) {
678 } else if ((tv = value_of(b)) != tarval_bad) {
683 /* If this predecessors constant value is zero, the operation is
684 unnecessary. Remove it: */
685 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
688 DBG_OPT_ALGSIM1(oldn, a, b, n);
694 #define equivalent_node_Add equivalent_node_neutral_zero
695 #define equivalent_node_Eor equivalent_node_neutral_zero
698 * optimize operations that are not commutative but have neutral 0 on left,
701 static ir_node *equivalent_node_left_zero(ir_node *n)
705 ir_node *a = get_binop_left(n);
706 ir_node *b = get_binop_right(n);
708 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
711 DBG_OPT_ALGSIM1(oldn, a, b, n);
717 #define equivalent_node_Sub equivalent_node_left_zero
718 #define equivalent_node_Shl equivalent_node_left_zero
719 #define equivalent_node_Shr equivalent_node_left_zero
720 #define equivalent_node_Shrs equivalent_node_left_zero
721 #define equivalent_node_Rot equivalent_node_left_zero
724 * Er, a "symmetic unop", ie op(op(n)) = n.
726 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
729 ir_node *pred = get_unop_op(n);
731 /* optimize symmetric unop */
732 if (get_irn_op(pred) == get_irn_op(n)) {
733 n = get_unop_op(pred);
734 DBG_OPT_ALGSIM2(oldn, pred, n);
740 #define equivalent_node_Not equivalent_node_symmetric_unop
742 /* --x == x */ /* ??? Is this possible or can --x raise an
743 out of bounds exception if min =! max? */
744 #define equivalent_node_Minus equivalent_node_symmetric_unop
747 * Optimize a * 1 = 1 * a = a.
749 static ir_node *equivalent_node_Mul(ir_node *n)
753 ir_node *a = get_Mul_left(n);
754 ir_node *b = get_Mul_right(n);
756 /* Mul is commutative and has again an other neutral element. */
757 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
759 DBG_OPT_ALGSIM1(oldn, a, b, n);
760 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
762 DBG_OPT_ALGSIM1(oldn, a, b, n);
768 * Optimize a / 1 = a.
770 static ir_node *equivalent_node_Div(ir_node *n)
772 ir_node *a = get_Div_left(n);
773 ir_node *b = get_Div_right(n);
775 /* Div is not commutative. */
776 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
777 /* Turn Div into a tuple (mem, bad, a) */
778 ir_node *mem = get_Div_mem(n);
779 turn_into_tuple(n, 3);
780 set_Tuple_pred(n, pn_Div_M, mem);
781 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
782 set_Tuple_pred(n, pn_Div_res, a);
788 * Optimize a / 1 = a.
790 static ir_node *equivalent_node_DivMod(ir_node *n)
792 ir_node *a = get_DivMod_left(n);
793 ir_node *b = get_DivMod_right(n);
795 /* Div is not commutative. */
796 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
797 /* Turn DivMod into a tuple (mem, bad, a, 0) */
798 ir_node *mem = get_Div_mem(n);
799 ir_mode *mode = get_irn_mode(b);
801 turn_into_tuple(n, 4);
802 set_Tuple_pred(n, pn_DivMod_M, mem);
803 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
804 set_Tuple_pred(n, pn_DivMod_res_div, a);
805 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
811 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
813 static ir_node *equivalent_node_Or(ir_node *n)
817 ir_node *a = get_Or_left(n);
818 ir_node *b = get_Or_right(n);
821 n = a; /* Or has it's own neutral element */
822 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
824 DBG_OPT_ALGSIM1(oldn, a, b, n);
825 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
827 DBG_OPT_ALGSIM1(oldn, a, b, n);
834 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
836 static ir_node *equivalent_node_And(ir_node *n)
840 ir_node *a = get_And_left(n);
841 ir_node *b = get_And_right(n);
844 n = a; /* And has it's own neutral element */
845 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
847 DBG_OPT_ALGSIM1(oldn, a, b, n);
848 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
850 DBG_OPT_ALGSIM1(oldn, a, b, n);
856 * Try to remove useless conv's:
858 static ir_node *equivalent_node_Conv(ir_node *n)
861 ir_node *a = get_Conv_op(n);
864 ir_mode *n_mode = get_irn_mode(n);
865 ir_mode *a_mode = get_irn_mode(a);
867 if (n_mode == a_mode) { /* No Conv necessary */
869 DBG_OPT_ALGSIM3(oldn, a, n);
870 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
874 n_mode = get_irn_mode(n);
875 b_mode = get_irn_mode(b);
877 if (n_mode == b_mode) {
878 if (n_mode == mode_b) {
879 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
880 DBG_OPT_ALGSIM1(oldn, a, b, n);
882 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
883 if (smaller_mode(b_mode, a_mode)){
884 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
885 DBG_OPT_ALGSIM1(oldn, a, b, n);
893 static ir_node *equivalent_node_Cast(ir_node *n) {
894 ir_node *pred = get_Cast_op(n);
895 if (get_irn_type(pred) == get_Cast_type(n))
900 static ir_node *equivalent_node_Phi(ir_node *n)
902 /* Several optimizations:
903 - no Phi in start block.
904 - remove Id operators that are inputs to Phi
905 - fold Phi-nodes, iff they have only one predecessor except
911 ir_node *block = NULL; /* to shutup gcc */
912 ir_node *first_val = NULL; /* to shutup gcc */
913 ir_node *scnd_val = NULL; /* to shutup gcc */
915 if (!get_opt_normalize()) return n;
917 n_preds = get_Phi_n_preds(n);
919 block = get_nodes_block(n);
920 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
921 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
922 if ((is_Bad(block)) || /* Control dead */
923 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
924 return new_Bad(); /* in the Start Block. */
926 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
929 /* first we test for a special case: */
930 /* Confirm is a special node fixing additional information for a
931 value that is known at a certain point. This is useful for
932 dataflow analysis. */
934 ir_node *a = get_Phi_pred(n, 0);
935 ir_node *b = get_Phi_pred(n, 1);
936 if ( (get_irn_op(a) == op_Confirm)
937 && (get_irn_op(b) == op_Confirm)
938 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
939 && (get_irn_n(a, 1) == get_irn_n (b, 1))
940 && (a->data.num == (~b->data.num & irpn_True) )) {
941 return get_irn_n(a, 0);
946 /* If the Block has a Bad pred, we also have one. */
947 for (i = 0; i < n_preds; ++i)
948 if (is_Bad (get_Block_cfgpred(block, i)))
949 set_Phi_pred(n, i, new_Bad());
951 /* Find first non-self-referencing input */
952 for (i = 0; i < n_preds; ++i) {
953 first_val = get_Phi_pred(n, i);
954 if ( (first_val != n) /* not self pointer */
956 && (get_irn_op(first_val) != op_Bad)
958 ) { /* value not dead */
959 break; /* then found first value. */
963 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
964 if (i >= n_preds) { return new_Bad(); }
968 /* follow_Id () for rest of inputs, determine if any of these
969 are non-self-referencing */
970 while (++i < n_preds) {
971 scnd_val = get_Phi_pred(n, i);
973 && (scnd_val != first_val)
975 && (get_irn_op(scnd_val) != op_Bad)
982 /* Fold, if no multiple distinct non-self-referencing inputs */
985 DBG_OPT_PHI(oldn, first_val, n);
987 /* skip the remaining Ids (done in get_Phi_pred). */
988 /* superfluous, since we walk all to propagate Block's Bads.
989 while (++i < n_preds) get_Phi_pred(n, i); */
995 * optimize Proj(Tuple) and gigo for ProjX in Bad block
997 static ir_node *equivalent_node_Proj(ir_node *n)
1001 ir_node *a = get_Proj_pred(n);
1003 if ( get_irn_op(a) == op_Tuple) {
1004 /* Remove the Tuple/Proj combination. */
1005 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1006 n = get_Tuple_pred(a, get_Proj_proj(n));
1007 DBG_OPT_TUPLE(oldn, a, n);
1009 assert(0); /* This should not happen! */
1012 } else if (get_irn_mode(n) == mode_X &&
1013 is_Bad(get_nodes_block(n))) {
1014 /* Remove dead control flow -- early gigo. */
1023 static ir_node *equivalent_node_Id(ir_node *n)
1028 DBG_OPT_ID(oldn, n);
1033 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1034 * perform no actual computation, as, e.g., the Id nodes. It does not create
1035 * new nodes. It is therefore safe to free n if the node returned is not n.
1036 * If a node returns a Tuple we can not just skip it. If the size of the
1037 * in array fits, we transform n into a tuple (e.g., Div).
1040 equivalent_node(ir_node *n)
1042 if (n->op->equivalent_node)
1043 return n->op->equivalent_node(n);
1048 * set the default equivalent node operation
1050 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1054 op->equivalent_node = equivalent_node_##a; \
1081 op->equivalent_node = NULL;
1089 * Do node specific optimizations of nodes predecessors.
1092 optimize_preds(ir_node *n) {
1093 ir_node *a = NULL, *b = NULL;
1095 /* get the operands we will work on for simple cases. */
1097 a = get_binop_left(n);
1098 b = get_binop_right(n);
1099 } else if (is_unop(n)) {
1103 switch (get_irn_opcode(n)) {
1106 /* We don't want Cast as input to Cmp. */
1107 if (get_irn_op(a) == op_Cast) {
1111 if (get_irn_op(b) == op_Cast) {
1113 set_Cmp_right(n, b);
1121 /** Do architecture dependend optimizations on Mul nodes */
1122 static ir_node *transform_node_Mul(ir_node *n) {
1123 return arch_dep_replace_mul_with_shifts(n);
1126 static ir_node *transform_node_Div(ir_node *n)
1128 tarval *tv = value_of(n);
1131 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1133 if (tv != tarval_bad)
1134 value = new_Const(get_tarval_mode(tv), tv);
1135 else /* Try architecture dependand optimization */
1136 value = arch_dep_replace_div_by_const(n);
1139 /* Turn Div into a tuple (mem, bad, value) */
1140 ir_node *mem = get_Div_mem(n);
1142 turn_into_tuple(n, 3);
1143 set_Tuple_pred(n, pn_Div_M, mem);
1144 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1145 set_Tuple_pred(n, pn_Div_res, value);
1150 static ir_node *transform_node_Mod(ir_node *n)
1152 tarval *tv = value_of(n);
1155 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1157 if (tv != tarval_bad)
1158 value = new_Const(get_tarval_mode(tv), tv);
1159 else /* Try architecture dependand optimization */
1160 value = arch_dep_replace_mod_by_const(n);
1163 /* Turn Mod into a tuple (mem, bad, value) */
1164 ir_node *mem = get_Mod_mem(n);
1166 turn_into_tuple(n, 3);
1167 set_Tuple_pred(n, pn_Mod_M, mem);
1168 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1169 set_Tuple_pred(n, pn_Mod_res, value);
1174 static ir_node *transform_node_DivMod(ir_node *n)
1178 ir_node *a = get_DivMod_left(n);
1179 ir_node *b = get_DivMod_right(n);
1180 ir_mode *mode = get_irn_mode(a);
1181 tarval *ta = value_of(a);
1182 tarval *tb = value_of(b);
1184 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1187 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1189 if (tb != tarval_bad) {
1190 if (tb == get_mode_one(get_tarval_mode(tb))) {
1191 b = new_Const (mode, get_mode_null(mode));
1193 } else if (ta != tarval_bad) {
1194 tarval *resa, *resb;
1195 resa = tarval_div (ta, tb);
1196 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1197 Jmp for X result!? */
1198 resb = tarval_mod (ta, tb);
1199 if (resb == tarval_bad) return n; /* Causes exception! */
1200 a = new_Const (mode, resa);
1201 b = new_Const (mode, resb);
1204 else { /* Try architecture dependand optimization */
1205 arch_dep_replace_divmod_by_const(&a, &b, n);
1206 evaluated = a != NULL;
1208 } else if (ta == get_mode_null(mode)) {
1209 /* 0 / non-Const = 0 */
1214 if (evaluated) { /* replace by tuple */
1215 ir_node *mem = get_DivMod_mem(n);
1216 turn_into_tuple(n, 4);
1217 set_Tuple_pred(n, pn_DivMod_M, mem);
1218 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1219 set_Tuple_pred(n, pn_DivMod_res_div, a);
1220 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1221 assert(get_nodes_block(n));
1227 static ir_node *transform_node_Cond(ir_node *n)
1229 /* Replace the Cond by a Jmp if it branches on a constant
1232 ir_node *a = get_Cond_selector(n);
1233 tarval *ta = value_of(a);
1235 if ((ta != tarval_bad) &&
1236 (get_irn_mode(a) == mode_b) &&
1237 (get_opt_unreachable_code())) {
1238 /* It's a boolean Cond, branching on a boolean constant.
1239 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1240 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1241 turn_into_tuple(n, 2);
1242 if (ta == tarval_b_true) {
1243 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1244 set_Tuple_pred(n, pn_Cond_true, jmp);
1246 set_Tuple_pred(n, pn_Cond_false, jmp);
1247 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1249 /* We might generate an endless loop, so keep it alive. */
1250 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1251 } else if ((ta != tarval_bad) &&
1252 (get_irn_mode(a) == mode_Iu) &&
1253 (get_Cond_kind(n) == dense) &&
1254 (get_opt_unreachable_code())) {
1255 /* I don't want to allow Tuples smaller than the biggest Proj.
1256 Also this tuple might get really big...
1257 I generate the Jmp here, and remember it in link. Link is used
1258 when optimizing Proj. */
1259 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1260 /* We might generate an endless loop, so keep it alive. */
1261 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1262 } else if ((get_irn_op(a) == op_Eor)
1263 && (get_irn_mode(a) == mode_b)
1264 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1265 /* The Eor is a negate. Generate a new Cond without the negate,
1266 simulate the negate by exchanging the results. */
1267 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1269 } else if ((get_irn_op(a) == op_Not)
1270 && (get_irn_mode(a) == mode_b)) {
1271 /* A Not before the Cond. Generate a new Cond without the Not,
1272 simulate the Not by exchanging the results. */
1273 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1279 static ir_node *transform_node_Eor(ir_node *n)
1281 ir_node *a = get_Eor_left(n);
1282 ir_node *b = get_Eor_right(n);
1284 if ((get_irn_mode(n) == mode_b)
1285 && (get_irn_op(a) == op_Proj)
1286 && (get_irn_mode(a) == mode_b)
1287 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1288 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1289 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1290 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1291 mode_b, get_negated_pnc(get_Proj_proj(a)));
1292 else if ((get_irn_mode(n) == mode_b)
1293 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1294 /* The Eor is a Not. Replace it by a Not. */
1295 /* ????!!!Extend to bitfield 1111111. */
1296 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1302 * Transform a boolean Not.
1304 static ir_node *transform_node_Not(ir_node *n)
1306 ir_node *a = get_Not_op(n);
1308 if ( (get_irn_mode(n) == mode_b)
1309 && (get_irn_op(a) == op_Proj)
1310 && (get_irn_mode(a) == mode_b)
1311 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1312 /* We negate a Cmp. The Cmp has the negated result anyways! */
1313 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1314 mode_b, get_negated_pnc(get_Proj_proj(a)));
1320 * Transform a Cast of a Const into a new Const
1322 static ir_node *transform_node_Cast(ir_node *n) {
1323 ir_node *pred = get_Cast_op(n);
1324 type *tp = get_irn_type(pred);
1326 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1327 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1328 get_Const_tarval(pred), tp);
1329 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1330 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1331 get_SymConst_kind(pred), tp);
1337 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1338 * done here instead of equivalent node because it creates new
1340 * Removes the exceptions and routes the memory to the NoMem node.
1342 * Further, it optimizes jump tables by removing all impossible cases.
1344 static ir_node *transform_node_Proj(ir_node *proj)
1346 ir_node *n = get_Proj_pred(proj);
1351 switch (get_irn_opcode(n)) {
1353 b = get_Div_right(n);
1356 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1357 proj_nr = get_Proj_proj(proj);
1359 /* this node may float */
1360 set_irn_pinned(n, op_pin_state_floats);
1362 if (proj_nr == pn_Div_X_except) {
1363 /* we found an exception handler, remove it */
1367 /* the memory Proj can be removed */
1368 ir_node *res = get_Div_mem(n);
1369 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1371 if (proj_nr == pn_Div_M)
1377 b = get_Mod_right(n);
1380 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1381 proj_nr = get_Proj_proj(proj);
1383 /* this node may float */
1384 set_irn_pinned(n, op_pin_state_floats);
1386 if (proj_nr == pn_Mod_X_except) {
1387 /* we found an exception handler, remove it */
1391 /* the memory Proj can be removed */
1392 ir_node *res = get_Mod_mem(n);
1393 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1394 if (proj_nr == pn_Mod_M)
1400 b = get_DivMod_right(n);
1403 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1404 proj_nr = get_Proj_proj(proj);
1406 /* this node may float */
1407 set_irn_pinned(n, op_pin_state_floats);
1409 if (proj_nr == pn_DivMod_X_except) {
1410 /* we found an exception handler, remove it */
1414 /* the memory Proj can be removed */
1415 ir_node *res = get_DivMod_mem(n);
1416 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1417 if (proj_nr == pn_DivMod_M)
1424 if (get_opt_unreachable_code()) {
1425 b = get_Cond_selector(n);
1428 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1429 /* we have a constant switch */
1430 long num = get_Proj_proj(proj);
1432 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1433 if (get_tarval_long(tb) == num) {
1434 /* Do NOT create a jump here, or we will have 2 control flow ops
1435 * in a block. This case is optimized away in optimize_cf(). */
1446 /* should not happen, but if it does will be optimized away */
1454 /* we have added a Tuple, optimize it for the current Proj away */
1455 return equivalent_node_Proj(proj);
1459 * returns the operands of a commutative bin-op, if one operand is
1460 * a const, it is returned as the second one.
1462 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1464 ir_node *op_a = get_binop_left(binop);
1465 ir_node *op_b = get_binop_right(binop);
1467 assert(is_op_commutative(get_irn_op(binop)));
1469 if (get_irn_op(op_a) == op_Const) {
1480 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1481 * Such pattern may arise in bitfield stores.
1483 * value c4 value c4 & c2
1484 * AND c3 AND c1 | c3
1489 static ir_node *transform_node_Or(ir_node *or)
1493 ir_node *and_l, *c3;
1494 ir_node *value, *c4;
1495 ir_node *new_and, *new_const, *block;
1496 ir_mode *mode = get_irn_mode(or);
1498 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1500 get_comm_Binop_Ops(or, &and, &c1);
1501 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1504 get_comm_Binop_Ops(and, &or_l, &c2);
1505 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1508 get_comm_Binop_Ops(or_l, &and_l, &c3);
1509 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1512 get_comm_Binop_Ops(and_l, &value, &c4);
1513 if (get_irn_op(c4) != op_Const)
1516 /* ok, found the pattern, check for conditions */
1517 assert(mode == get_irn_mode(and));
1518 assert(mode == get_irn_mode(or_l));
1519 assert(mode == get_irn_mode(and_l));
1521 tv1 = get_Const_tarval(c1);
1522 tv2 = get_Const_tarval(c2);
1523 tv3 = get_Const_tarval(c3);
1524 tv4 = get_Const_tarval(c4);
1526 tv = tarval_or(tv4, tv2);
1527 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1528 /* have at least one 0 at the same bit position */
1532 n_tv4 = tarval_not(tv4);
1533 if (tv3 != tarval_and(tv3, n_tv4)) {
1534 /* bit in the or_mask is outside the and_mask */
1538 n_tv2 = tarval_not(tv2);
1539 if (tv1 != tarval_and(tv1, n_tv2)) {
1540 /* bit in the or_mask is outside the and_mask */
1544 /* ok, all conditions met */
1545 block = get_nodes_block(or);
1547 new_and = new_r_And(current_ir_graph, block,
1548 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1550 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1552 set_Or_left(or, new_and);
1553 set_Or_right(or, new_const);
1555 /* check for more */
1556 return transform_node_Or(or);
1560 static ir_node *transform_node(ir_node *n);
1563 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1565 static ir_node * transform_node_shift(ir_node *n)
1568 tarval *tv1, *tv2, *res;
1570 int modulo_shf, flag;
1572 left = get_binop_left(n);
1574 /* different operations */
1575 if (get_irn_op(left) != get_irn_op(n))
1578 tv1 = value_of(get_binop_right(n));
1579 if (tv1 == tarval_bad)
1582 tv2 = value_of(get_binop_right(left));
1583 if (tv2 == tarval_bad)
1586 res = tarval_add(tv1, tv2);
1588 /* beware: a simple replacement works only, if res < modulo shift */
1589 mode = get_irn_mode(n);
1593 modulo_shf = get_mode_modulo_shift(mode);
1594 if (modulo_shf > 0) {
1595 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1597 if (tarval_cmp(res, modulo) & Lt)
1604 /* ok, we can replace it */
1605 ir_node *in[2], *irn, *block = get_nodes_block(n);
1607 in[0] = get_binop_left(left);
1608 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1610 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1612 return transform_node(irn);
1619 * Tries several [inplace] [optimizing] transformations and returns an
1620 * equivalent node. The difference to equivalent_node() is that these
1621 * transformations _do_ generate new nodes, and thus the old node must
1622 * not be freed even if the equivalent node isn't the old one.
1624 static ir_node *transform_node(ir_node *n)
1626 if (n->op->transform_node)
1627 n = n->op->transform_node(n);
1632 * set the default transform node operation
1634 static ir_op *firm_set_default_transform_node(ir_op *op)
1638 op->transform_node = transform_node_##a; \
1655 op->transform_node = transform_node_shift;
1658 op->transform_node = NULL;
1666 /* **************** Common Subexpression Elimination **************** */
1668 /** The size of the hash table used, should estimate the number of nodes
1670 #define N_IR_NODES 512
1672 /** Compares the attributes of two Const nodes. */
1673 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1675 return (get_Const_tarval(a) != get_Const_tarval(b))
1676 || (get_Const_type(a) != get_Const_type(b));
1679 /** Compares the attributes of two Proj nodes. */
1680 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1682 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1685 /** Compares the attributes of two Filter nodes. */
1686 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1688 return get_Filter_proj(a) != get_Filter_proj(b);
1691 /** Compares the attributes of two Alloc nodes. */
1692 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1694 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1695 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1698 /** Compares the attributes of two Free nodes. */
1699 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1701 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1704 /** Compares the attributes of two SymConst nodes. */
1705 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1707 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1708 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1709 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1712 /** Compares the attributes of two Call nodes. */
1713 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1715 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1718 /** Compares the attributes of two Sel nodes. */
1719 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1721 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1722 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1723 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1724 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1725 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1728 /** Compares the attributes of two Phi nodes. */
1729 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1731 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1734 /** Compares the attributes of two Cast nodes. */
1735 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1737 return get_Cast_type(a) != get_Cast_type(b);
1740 /** Compares the attributes of two Load nodes. */
1741 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1743 if (get_Load_volatility(a) == volatility_is_volatile ||
1744 get_Load_volatility(b) == volatility_is_volatile)
1745 /* NEVER do CSE on volatile Loads */
1748 return get_Load_mode(a) != get_Load_mode(b);
1751 /** Compares the attributes of two Store nodes. */
1752 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1754 /* NEVER do CSE on volatile Stores */
1755 return (get_Store_volatility(a) == volatility_is_volatile ||
1756 get_Store_volatility(b) == volatility_is_volatile);
1760 * set the default node attribute compare operation
1762 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1766 op->node_cmp_attr = node_cmp_attr_##a; \
1783 op->node_cmp_attr = NULL;
1791 * Compare function for two nodes in the hash table. Gets two
1792 * nodes as parameters. Returns 0 if the nodes are a cse.
1795 vt_cmp (const void *elt, const void *key)
1803 if (a == b) return 0;
1805 if ((get_irn_op(a) != get_irn_op(b)) ||
1806 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1808 /* compare if a's in and b's in are of equal length */
1809 irn_arity_a = get_irn_intra_arity (a);
1810 if (irn_arity_a != get_irn_intra_arity(b))
1813 /* for block-local cse and op_pin_state_pinned nodes: */
1814 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1815 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1819 /* compare a->in[0..ins] with b->in[0..ins] */
1820 for (i = 0; i < irn_arity_a; i++)
1821 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1825 * here, we already now that the nodes are identical except their
1828 if (a->op->node_cmp_attr)
1829 return a->op->node_cmp_attr(a, b);
1834 #define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3)
1837 * Calculate a hash value of a node.
1840 ir_node_hash (ir_node *node)
1845 if (node->op == op_Const) {
1846 /* special value for const, as they only differ in their tarval. */
1847 h = ADDR_TO_VAL(node->attr.con.tv);
1848 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1849 } else if (node->op == op_SymConst) {
1850 /* special value for const, as they only differ in their symbol. */
1851 h = ADDR_TO_VAL(node->attr.i.sym.type_p);
1852 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1855 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1856 h = irn_arity = get_irn_intra_arity(node);
1858 /* consider all in nodes... except the block if not a control flow. */
1859 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1860 h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i));
1864 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1866 h = 9*h + ADDR_TO_VAL(get_irn_op(node));
1873 new_identities(void) {
1874 return new_pset(vt_cmp, N_IR_NODES);
1878 del_identities(pset *value_table) {
1879 del_pset(value_table);
1883 * Return the canonical node computing the same value as n.
1884 * Looks up the node in a hash table.
1886 * For Const nodes this is performed in the constructor, too. Const
1887 * nodes are extremely time critical because of their frequent use in
1888 * constant string arrays.
1890 static INLINE ir_node *
1891 identify (pset *value_table, ir_node *n)
1895 if (!value_table) return n;
1897 if (get_opt_reassociation()) {
1898 if (is_op_commutative(get_irn_op(n))) {
1899 ir_node *l = get_binop_left(n);
1900 ir_node *r = get_binop_right(n);
1902 /* for commutative operators perform a OP b == b OP a */
1904 set_binop_left(n, r);
1905 set_binop_right(n, l);
1910 o = pset_find (value_table, n, ir_node_hash (n));
1919 * During construction we set the op_pin_state_pinned flag in the graph right when the
1920 * optimization is performed. The flag turning on procedure global cse could
1921 * be changed between two allocations. This way we are safe.
1923 static INLINE ir_node *
1924 identify_cons (pset *value_table, ir_node *n) {
1927 n = identify(value_table, n);
1928 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1929 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1934 * Return the canonical node computing the same value as n.
1935 * Looks up the node in a hash table, enters it in the table
1936 * if it isn't there yet.
1939 identify_remember (pset *value_table, ir_node *n)
1943 if (!value_table) return n;
1945 if (get_opt_reassociation()) {
1946 if (is_op_commutative(get_irn_op(n))) {
1947 ir_node *l = get_binop_left(n);
1948 ir_node *r = get_binop_right(n);
1950 /* for commutative operators perform a OP b == b OP a */
1952 set_binop_left(n, r);
1953 set_binop_right(n, l);
1958 /* lookup or insert in hash table with given hash key. */
1959 o = pset_insert (value_table, n, ir_node_hash (n));
1969 add_identities (pset *value_table, ir_node *node) {
1970 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1971 identify_remember (value_table, node);
1975 * garbage in, garbage out. If a node has a dead input, i.e., the
1976 * Bad node is input to the node, return the Bad node.
1978 static INLINE ir_node *
1979 gigo (ir_node *node)
1982 ir_op* op = get_irn_op(node);
1984 /* remove garbage blocks by looking at control flow that leaves the block
1985 and replacing the control flow by Bad. */
1986 if (get_irn_mode(node) == mode_X) {
1987 ir_node *block = get_nodes_block(node);
1988 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1989 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1990 irn_arity = get_irn_arity(block);
1991 for (i = 0; i < irn_arity; i++) {
1992 if (!is_Bad(get_irn_n(block, i))) break;
1994 if (i == irn_arity) return new_Bad();
1998 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1999 blocks predecessors is dead. */
2000 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2001 irn_arity = get_irn_arity(node);
2002 for (i = -1; i < irn_arity; i++) {
2003 if (is_Bad(get_irn_n(node, i))) {
2009 /* With this code we violate the agreement that local_optimize
2010 only leaves Bads in Block, Phi and Tuple nodes. */
2011 /* If Block has only Bads as predecessors it's garbage. */
2012 /* If Phi has only Bads as predecessors it's garbage. */
2013 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2014 irn_arity = get_irn_arity(node);
2015 for (i = 0; i < irn_arity; i++) {
2016 if (!is_Bad(get_irn_n(node, i))) break;
2018 if (i == irn_arity) node = new_Bad();
2026 * These optimizations deallocate nodes from the obstack.
2027 * It can only be called if it is guaranteed that no other nodes
2028 * reference this one, i.e., right after construction of a node.
2031 optimize_node (ir_node *n)
2035 opcode iro = get_irn_opcode(n);
2037 type *old_tp = get_irn_type(n);
2039 int i, arity = get_irn_arity(n);
2040 for (i = 0; i < arity && !old_tp; ++i)
2041 old_tp = get_irn_type(get_irn_n(n, i));
2044 /* Allways optimize Phi nodes: part of the construction. */
2045 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2047 /* constant expression evaluation / constant folding */
2048 if (get_opt_constant_folding()) {
2049 /* constants can not be evaluated */
2050 if (iro != iro_Const) {
2051 /* try to evaluate */
2052 tv = computed_value(n);
2053 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2055 * we MUST copy the node here temporary, because it's still needed
2056 * for DBG_OPT_CSTEVAL
2058 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2059 oldn = alloca(node_size);
2061 memcpy(oldn, n, node_size);
2062 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2064 /* ARG, copy the in array, we need it for statistics */
2065 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2067 /* evaluation was successful -- replace the node. */
2068 obstack_free (current_ir_graph->obst, n);
2069 n = new_Const (get_tarval_mode (tv), tv);
2070 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2071 set_Const_type(n, old_tp);
2072 DBG_OPT_CSTEVAL(oldn, n);
2078 /* remove unnecessary nodes */
2079 if (get_opt_constant_folding() ||
2080 (iro == iro_Phi) || /* always optimize these nodes. */
2082 (iro == iro_Proj) ||
2083 (iro == iro_Block) ) /* Flags tested local. */
2084 n = equivalent_node (n);
2086 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2088 /** common subexpression elimination **/
2089 /* Checks whether n is already available. */
2090 /* The block input is used to distinguish different subexpressions. Right
2091 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2092 subexpressions within a block. */
2094 n = identify_cons (current_ir_graph->value_table, n);
2097 /* We found an existing, better node, so we can deallocate the old node. */
2098 obstack_free (current_ir_graph->obst, oldn);
2103 /* Some more constant expression evaluation that does not allow to
2105 iro = get_irn_opcode(n);
2106 if (get_opt_constant_folding() ||
2107 (iro == iro_Cond) ||
2108 (iro == iro_Proj)) /* Flags tested local. */
2109 n = transform_node (n);
2111 /* Remove nodes with dead (Bad) input.
2112 Run always for transformation induced Bads. */
2115 /* Now we have a legal, useful node. Enter it in hash table for cse */
2116 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2117 n = identify_remember (current_ir_graph->value_table, n);
2125 * These optimizations never deallocate nodes. This can cause dead
2126 * nodes lying on the obstack. Remove these by a dead node elimination,
2127 * i.e., a copying garbage collection.
2130 optimize_in_place_2 (ir_node *n)
2134 opcode iro = get_irn_opcode(n);
2136 type *old_tp = get_irn_type(n);
2138 int i, arity = get_irn_arity(n);
2139 for (i = 0; i < arity && !old_tp; ++i)
2140 old_tp = get_irn_type(get_irn_n(n, i));
2143 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2145 /* if not optimize return n */
2148 /* Here this is possible. Why? */
2152 /* constant expression evaluation / constant folding */
2153 if (get_opt_constant_folding()) {
2154 /* constants can not be evaluated */
2155 if (iro != iro_Const) {
2156 /* try to evaluate */
2157 tv = computed_value(n);
2158 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2159 /* evaluation was successful -- replace the node. */
2160 n = new_Const (get_tarval_mode (tv), tv);
2162 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2163 set_Const_type(n, old_tp);
2165 DBG_OPT_CSTEVAL(oldn, n);
2171 /* remove unnecessary nodes */
2172 if (get_opt_constant_folding() ||
2173 (iro == iro_Phi) || /* always optimize these nodes. */
2174 (iro == iro_Id) || /* ... */
2175 (iro == iro_Proj) || /* ... */
2176 (iro == iro_Block) ) /* Flags tested local. */
2177 n = equivalent_node (n);
2179 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2181 /** common subexpression elimination **/
2182 /* Checks whether n is already available. */
2183 /* The block input is used to distinguish different subexpressions. Right
2184 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2185 subexpressions within a block. */
2186 if (get_opt_cse()) {
2187 n = identify (current_ir_graph->value_table, n);
2190 /* Some more constant expression evaluation. */
2191 iro = get_irn_opcode(n);
2192 if (get_opt_constant_folding() ||
2193 (iro == iro_Cond) ||
2194 (iro == iro_Proj)) /* Flags tested local. */
2195 n = transform_node (n);
2197 /* Remove nodes with dead (Bad) input.
2198 Run always for transformation induced Bads. */
2201 /* Now we can verify the node, as it has no dead inputs any more. */
2204 /* Now we have a legal, useful node. Enter it in hash table for cse.
2205 Blocks should be unique anyways. (Except the successor of start:
2206 is cse with the start block!) */
2207 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2208 n = identify_remember (current_ir_graph->value_table, n);
2214 * Wrapper for external use, set proper status bits after optimization.
2217 optimize_in_place (ir_node *n)
2219 /* Handle graph state */
2220 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2222 if (get_opt_global_cse())
2223 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2224 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2225 set_irg_outs_inconsistent(current_ir_graph);
2227 /* Maybe we could also test whether optimizing the node can
2228 change the control graph. */
2229 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2230 set_irg_dom_inconsistent(current_ir_graph);
2231 return optimize_in_place_2 (n);
2235 * set the default ir op operations
2237 ir_op *firm_set_default_operations(ir_op *op)
2239 op = firm_set_default_computed_value(op);
2240 op = firm_set_default_equivalent_node(op);
2241 op = firm_set_default_transform_node(op);
2242 op = firm_set_default_node_cmp_attr(op);