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) { /* 1.: */
429 /* This is a trick with the bits used for encoding the Cmp
430 Proj numbers, the following statement is not the same:
431 return new_tarval_from_long (proj_nr == Eq, mode_b) */
432 return new_tarval_from_long (proj_nr & Eq, mode_b);
434 tarval *taa = value_of(aa);
435 tarval *tab = value_of(ab);
437 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
438 /* strange checks... */
439 pnc_number flags = tarval_cmp (taa, tab);
440 if (flags != False) {
441 return new_tarval_from_long (proj_nr & flags, mode_b);
443 } else { /* check for 3.: */
444 ir_node *aaa = skip_Id(skip_Proj(aa));
445 ir_node *aba = skip_Id(skip_Proj(ab));
447 if ( ( (/* aa is ProjP and aaa is Alloc */
448 (get_irn_op(aa) == op_Proj)
449 && (mode_is_reference(get_irn_mode(aa)))
450 && (get_irn_op(aaa) == op_Alloc))
451 && ( (/* ab is constant void */
452 (get_irn_op(ab) == op_Const)
453 && (mode_is_reference(get_irn_mode(ab)))
454 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
455 || (/* ab is other Alloc */
456 (get_irn_op(ab) == op_Proj)
457 && (mode_is_reference(get_irn_mode(ab)))
458 && (get_irn_op(aba) == op_Alloc)
460 || (/* aa is void and aba is Alloc */
461 (get_irn_op(aa) == op_Const)
462 && (mode_is_reference(get_irn_mode(aa)))
463 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
464 && (get_irn_op(ab) == op_Proj)
465 && (mode_is_reference(get_irn_mode(ab)))
466 && (get_irn_op(aba) == op_Alloc)))
468 return new_tarval_from_long (proj_nr & Ne, mode_b);
474 /* compute either the Div or the Mod part */
475 proj_nr = get_Proj_proj(n);
476 if (proj_nr == pn_DivMod_res_div)
477 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
478 else if (proj_nr == pn_DivMod_res_mod)
479 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
483 if (get_Proj_proj(n) == pn_Div_res)
484 return computed_value(a);
488 if (get_Proj_proj(n) == pn_Mod_res)
489 return computed_value(a);
499 * If the parameter n can be computed, return its value, else tarval_bad.
500 * Performs constant folding.
502 * @param n The node this should be evaluated
504 tarval *computed_value(ir_node *n)
506 if (n->op->computed_value)
507 return n->op->computed_value(n);
512 * set the default computed_value evaluator
514 static ir_op *firm_set_default_computed_value(ir_op *op)
518 op->computed_value = computed_value_##a; \
543 op->computed_value = NULL;
551 /* returns 1 if the a and b are pointers to different locations. */
553 different_identity (ir_node *a, ir_node *b)
555 assert (mode_is_reference(get_irn_mode (a))
556 && mode_is_reference(get_irn_mode (b)));
558 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
559 ir_node *a1 = get_Proj_pred (a);
560 ir_node *b1 = get_Proj_pred (b);
561 if (a1 != b1 && get_irn_op (a1) == op_Alloc
562 && get_irn_op (b1) == op_Alloc)
569 static ir_node *equivalent_node_Block(ir_node *n)
573 /* The Block constructor does not call optimize, but mature_immBlock
574 calls the optimization. */
575 assert(get_Block_matured(n));
577 /* Straightening: a single entry Block following a single exit Block
578 can be merged, if it is not the Start block. */
579 /* !!! Beware, all Phi-nodes of n must have been optimized away.
580 This should be true, as the block is matured before optimize is called.
581 But what about Phi-cycles with the Phi0/Id that could not be resolved?
582 Remaining Phi nodes are just Ids. */
583 if ((get_Block_n_cfgpreds(n) == 1) &&
584 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
585 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
586 if (predblock == oldn) {
587 /* Jmp jumps into the block it is in -- deal self cycle. */
589 DBG_OPT_DEAD(oldn, n);
590 } else if (get_opt_control_flow_straightening()) {
592 DBG_OPT_STG(oldn, n);
595 else if ((get_Block_n_cfgpreds(n) == 1) &&
596 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
597 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
598 if (predblock == oldn) {
599 /* Jmp jumps into the block it is in -- deal self cycle. */
601 DBG_OPT_DEAD(oldn, n);
604 else if ((get_Block_n_cfgpreds(n) == 2) &&
605 (get_opt_control_flow_weak_simplification())) {
606 /* Test whether Cond jumps twice to this block
607 @@@ we could do this also with two loops finding two preds from several ones. */
608 ir_node *a = get_Block_cfgpred(n, 0);
609 ir_node *b = get_Block_cfgpred(n, 1);
611 if ((get_irn_op(a) == op_Proj) &&
612 (get_irn_op(b) == op_Proj) &&
613 (get_Proj_pred(a) == get_Proj_pred(b)) &&
614 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
615 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
616 /* Also a single entry Block following a single exit Block. Phis have
617 twice the same operand and will be optimized away. */
618 n = get_nodes_block(a);
619 DBG_OPT_IFSIM(oldn, a, b, n);
621 } else if (get_opt_unreachable_code() &&
622 (n != current_ir_graph->start_block) &&
623 (n != current_ir_graph->end_block) ) {
625 /* If all inputs are dead, this block is dead too, except if it is
626 the start or end block. This is a step of unreachable code
628 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
629 if (!is_Bad(get_Block_cfgpred(n, i))) break;
631 if (i == get_Block_n_cfgpreds(n))
639 * Returns a equivalent node for a Jmp, a Bad :-)
640 * Of course this only happens if the Block of the Jmp is Bad.
642 static ir_node *equivalent_node_Jmp(ir_node *n)
644 /* GL: Why not same for op_Raise?? */
645 /* unreachable code elimination */
646 if (is_Bad(get_nodes_block(n)))
652 static ir_node *equivalent_node_Cond(ir_node *n)
654 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
655 See cases for iro_Cond and iro_Proj in transform_node. */
660 * optimize operations that are commutative and have neutral 0,
661 * so a op 0 = 0 op a = a.
663 static ir_node *equivalent_node_neutral_zero(ir_node *n)
667 ir_node *a = get_binop_left(n);
668 ir_node *b = get_binop_right(n);
673 /* After running compute_node there is only one constant predecessor.
674 Find this predecessors value and remember the other node: */
675 if ((tv = value_of(a)) != tarval_bad) {
677 } else if ((tv = value_of(b)) != tarval_bad) {
682 /* If this predecessors constant value is zero, the operation is
683 unnecessary. Remove it: */
684 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
687 DBG_OPT_ALGSIM1(oldn, a, b, n);
693 #define equivalent_node_Add equivalent_node_neutral_zero
694 #define equivalent_node_Eor equivalent_node_neutral_zero
697 * optimize operations that are not commutative but have neutral 0 on left,
700 static ir_node *equivalent_node_left_zero(ir_node *n)
704 ir_node *a = get_binop_left(n);
705 ir_node *b = get_binop_right(n);
707 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
710 DBG_OPT_ALGSIM1(oldn, a, b, n);
716 #define equivalent_node_Sub equivalent_node_left_zero
717 #define equivalent_node_Shl equivalent_node_left_zero
718 #define equivalent_node_Shr equivalent_node_left_zero
719 #define equivalent_node_Shrs equivalent_node_left_zero
720 #define equivalent_node_Rot equivalent_node_left_zero
723 * Er, a "symmetic unop", ie op(op(n)) = n.
725 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
728 ir_node *pred = get_unop_op(n);
730 /* optimize symmetric unop */
731 if (get_irn_op(pred) == get_irn_op(n)) {
732 n = get_unop_op(pred);
733 DBG_OPT_ALGSIM2(oldn, pred, n);
739 #define equivalent_node_Not equivalent_node_symmetric_unop
741 /* --x == x */ /* ??? Is this possible or can --x raise an
742 out of bounds exception if min =! max? */
743 #define equivalent_node_Minus equivalent_node_symmetric_unop
746 * Optimize a * 1 = 1 * a = a.
748 static ir_node *equivalent_node_Mul(ir_node *n)
752 ir_node *a = get_Mul_left(n);
753 ir_node *b = get_Mul_right(n);
755 /* Mul is commutative and has again an other neutral element. */
756 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
758 DBG_OPT_ALGSIM1(oldn, a, b, n);
759 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
761 DBG_OPT_ALGSIM1(oldn, a, b, n);
767 * Optimize a / 1 = a.
769 static ir_node *equivalent_node_Div(ir_node *n)
771 ir_node *a = get_Div_left(n);
772 ir_node *b = get_Div_right(n);
774 /* Div is not commutative. */
775 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
776 /* Turn Div into a tuple (mem, bad, a) */
777 ir_node *mem = get_Div_mem(n);
778 turn_into_tuple(n, 3);
779 set_Tuple_pred(n, pn_Div_M, mem);
780 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
781 set_Tuple_pred(n, pn_Div_res, a);
787 * Optimize a / 1 = a.
789 static ir_node *equivalent_node_DivMod(ir_node *n)
791 ir_node *a = get_DivMod_left(n);
792 ir_node *b = get_DivMod_right(n);
794 /* Div is not commutative. */
795 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
796 /* Turn DivMod into a tuple (mem, bad, a, 0) */
797 ir_node *mem = get_Div_mem(n);
798 ir_mode *mode = get_irn_mode(b);
800 turn_into_tuple(n, 4);
801 set_Tuple_pred(n, pn_DivMod_M, mem);
802 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
803 set_Tuple_pred(n, pn_DivMod_res_div, a);
804 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
810 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
812 static ir_node *equivalent_node_Or(ir_node *n)
816 ir_node *a = get_Or_left(n);
817 ir_node *b = get_Or_right(n);
820 n = a; /* Or has it's own neutral element */
821 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
823 DBG_OPT_ALGSIM1(oldn, a, b, n);
824 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
826 DBG_OPT_ALGSIM1(oldn, a, b, n);
833 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
835 static ir_node *equivalent_node_And(ir_node *n)
839 ir_node *a = get_And_left(n);
840 ir_node *b = get_And_right(n);
843 n = a; /* And has it's own neutral element */
844 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
846 DBG_OPT_ALGSIM1(oldn, a, b, n);
847 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
849 DBG_OPT_ALGSIM1(oldn, a, b, n);
855 * Try to remove useless conv's:
857 static ir_node *equivalent_node_Conv(ir_node *n)
860 ir_node *a = get_Conv_op(n);
863 ir_mode *n_mode = get_irn_mode(n);
864 ir_mode *a_mode = get_irn_mode(a);
866 if (n_mode == a_mode) { /* No Conv necessary */
868 DBG_OPT_ALGSIM3(oldn, a, n);
869 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
873 n_mode = get_irn_mode(n);
874 b_mode = get_irn_mode(b);
876 if (n_mode == b_mode) {
877 if (n_mode == mode_b) {
878 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
879 DBG_OPT_ALGSIM1(oldn, a, b, n);
881 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
882 if (smaller_mode(b_mode, a_mode)){
883 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
884 DBG_OPT_ALGSIM1(oldn, a, b, n);
892 static ir_node *equivalent_node_Cast(ir_node *n) {
893 ir_node *pred = get_Cast_op(n);
894 if (get_irn_type(pred) == get_Cast_type(n))
899 static ir_node *equivalent_node_Phi(ir_node *n)
901 /* Several optimizations:
902 - no Phi in start block.
903 - remove Id operators that are inputs to Phi
904 - fold Phi-nodes, iff they have only one predecessor except
910 ir_node *block = NULL; /* to shutup gcc */
911 ir_node *first_val = NULL; /* to shutup gcc */
912 ir_node *scnd_val = NULL; /* to shutup gcc */
914 if (!get_opt_normalize()) return n;
916 n_preds = get_Phi_n_preds(n);
918 block = get_nodes_block(n);
919 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
920 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
921 if ((is_Bad(block)) || /* Control dead */
922 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
923 return new_Bad(); /* in the Start Block. */
925 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
928 /* first we test for a special case: */
929 /* Confirm is a special node fixing additional information for a
930 value that is known at a certain point. This is useful for
931 dataflow analysis. */
933 ir_node *a = get_Phi_pred(n, 0);
934 ir_node *b = get_Phi_pred(n, 1);
935 if ( (get_irn_op(a) == op_Confirm)
936 && (get_irn_op(b) == op_Confirm)
937 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
938 && (get_irn_n(a, 1) == get_irn_n (b, 1))
939 && (a->data.num == (~b->data.num & irpn_True) )) {
940 return get_irn_n(a, 0);
945 /* If the Block has a Bad pred, we also have one. */
946 for (i = 0; i < n_preds; ++i)
947 if (is_Bad (get_Block_cfgpred(block, i)))
948 set_Phi_pred(n, i, new_Bad());
950 /* Find first non-self-referencing input */
951 for (i = 0; i < n_preds; ++i) {
952 first_val = get_Phi_pred(n, i);
953 if ( (first_val != n) /* not self pointer */
955 && (get_irn_op(first_val) != op_Bad)
957 ) { /* value not dead */
958 break; /* then found first value. */
962 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
963 if (i >= n_preds) { return new_Bad(); }
967 /* follow_Id () for rest of inputs, determine if any of these
968 are non-self-referencing */
969 while (++i < n_preds) {
970 scnd_val = get_Phi_pred(n, i);
972 && (scnd_val != first_val)
974 && (get_irn_op(scnd_val) != op_Bad)
981 /* Fold, if no multiple distinct non-self-referencing inputs */
984 DBG_OPT_PHI(oldn, first_val, n);
986 /* skip the remaining Ids (done in get_Phi_pred). */
987 /* superfluous, since we walk all to propagate Block's Bads.
988 while (++i < n_preds) get_Phi_pred(n, i); */
994 * optimize Proj(Tuple) and gigo for ProjX in Bad block
996 static ir_node *equivalent_node_Proj(ir_node *n)
1000 ir_node *a = get_Proj_pred(n);
1002 if ( get_irn_op(a) == op_Tuple) {
1003 /* Remove the Tuple/Proj combination. */
1004 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1005 n = get_Tuple_pred(a, get_Proj_proj(n));
1006 DBG_OPT_TUPLE(oldn, a, n);
1008 assert(0); /* This should not happen! */
1011 } else if (get_irn_mode(n) == mode_X &&
1012 is_Bad(get_nodes_block(n))) {
1013 /* Remove dead control flow -- early gigo. */
1022 static ir_node *equivalent_node_Id(ir_node *n)
1027 DBG_OPT_ID(oldn, n);
1032 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1033 * perform no actual computation, as, e.g., the Id nodes. It does not create
1034 * new nodes. It is therefore safe to free n if the node returned is not n.
1035 * If a node returns a Tuple we can not just skip it. If the size of the
1036 * in array fits, we transform n into a tuple (e.g., Div).
1039 equivalent_node(ir_node *n)
1041 if (n->op->equivalent_node)
1042 return n->op->equivalent_node(n);
1047 * set the default equivalent node operation
1049 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1053 op->equivalent_node = equivalent_node_##a; \
1080 op->equivalent_node = NULL;
1088 * Do node specific optimizations of nodes predecessors.
1091 optimize_preds(ir_node *n) {
1092 ir_node *a = NULL, *b = NULL;
1094 /* get the operands we will work on for simple cases. */
1096 a = get_binop_left(n);
1097 b = get_binop_right(n);
1098 } else if (is_unop(n)) {
1102 switch (get_irn_opcode(n)) {
1105 /* We don't want Cast as input to Cmp. */
1106 if (get_irn_op(a) == op_Cast) {
1110 if (get_irn_op(b) == op_Cast) {
1112 set_Cmp_right(n, b);
1120 /** Do architecture dependend optimizations on Mul nodes */
1121 static ir_node *transform_node_Mul(ir_node *n) {
1122 return arch_dep_replace_mul_with_shifts(n);
1125 static ir_node *transform_node_Div(ir_node *n)
1127 tarval *tv = value_of(n);
1130 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1132 if (tv != tarval_bad)
1133 value = new_Const(get_tarval_mode(tv), tv);
1134 else /* Try architecture dependand optimization */
1135 value = arch_dep_replace_div_by_const(n);
1138 /* Turn Div into a tuple (mem, bad, value) */
1139 ir_node *mem = get_Div_mem(n);
1141 turn_into_tuple(n, 3);
1142 set_Tuple_pred(n, pn_Div_M, mem);
1143 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1144 set_Tuple_pred(n, pn_Div_res, value);
1149 static ir_node *transform_node_Mod(ir_node *n)
1151 tarval *tv = value_of(n);
1154 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1156 if (tv != tarval_bad)
1157 value = new_Const(get_tarval_mode(tv), tv);
1158 else /* Try architecture dependand optimization */
1159 value = arch_dep_replace_mod_by_const(n);
1162 /* Turn Mod into a tuple (mem, bad, value) */
1163 ir_node *mem = get_Mod_mem(n);
1165 turn_into_tuple(n, 3);
1166 set_Tuple_pred(n, pn_Mod_M, mem);
1167 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1168 set_Tuple_pred(n, pn_Mod_res, value);
1173 static ir_node *transform_node_DivMod(ir_node *n)
1177 ir_node *a = get_DivMod_left(n);
1178 ir_node *b = get_DivMod_right(n);
1179 ir_mode *mode = get_irn_mode(a);
1180 tarval *ta = value_of(a);
1181 tarval *tb = value_of(b);
1183 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1186 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1188 if (tb != tarval_bad) {
1189 if (tb == get_mode_one(get_tarval_mode(tb))) {
1190 b = new_Const (mode, get_mode_null(mode));
1192 } else if (ta != tarval_bad) {
1193 tarval *resa, *resb;
1194 resa = tarval_div (ta, tb);
1195 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1196 Jmp for X result!? */
1197 resb = tarval_mod (ta, tb);
1198 if (resb == tarval_bad) return n; /* Causes exception! */
1199 a = new_Const (mode, resa);
1200 b = new_Const (mode, resb);
1203 else { /* Try architecture dependand optimization */
1204 arch_dep_replace_divmod_by_const(&a, &b, n);
1205 evaluated = a != NULL;
1207 } else if (ta == get_mode_null(mode)) {
1208 /* 0 / non-Const = 0 */
1213 if (evaluated) { /* replace by tuple */
1214 ir_node *mem = get_DivMod_mem(n);
1215 turn_into_tuple(n, 4);
1216 set_Tuple_pred(n, pn_DivMod_M, mem);
1217 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1218 set_Tuple_pred(n, pn_DivMod_res_div, a);
1219 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1220 assert(get_nodes_block(n));
1226 static ir_node *transform_node_Cond(ir_node *n)
1228 /* Replace the Cond by a Jmp if it branches on a constant
1231 ir_node *a = get_Cond_selector(n);
1232 tarval *ta = value_of(a);
1234 if ((ta != tarval_bad) &&
1235 (get_irn_mode(a) == mode_b) &&
1236 (get_opt_unreachable_code())) {
1237 /* It's a boolean Cond, branching on a boolean constant.
1238 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1239 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1240 turn_into_tuple(n, 2);
1241 if (ta == tarval_b_true) {
1242 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1243 set_Tuple_pred(n, pn_Cond_true, jmp);
1245 set_Tuple_pred(n, pn_Cond_false, jmp);
1246 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1248 /* We might generate an endless loop, so keep it alive. */
1249 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1250 } else if ((ta != tarval_bad) &&
1251 (get_irn_mode(a) == mode_Iu) &&
1252 (get_Cond_kind(n) == dense) &&
1253 (get_opt_unreachable_code())) {
1254 /* I don't want to allow Tuples smaller than the biggest Proj.
1255 Also this tuple might get really big...
1256 I generate the Jmp here, and remember it in link. Link is used
1257 when optimizing Proj. */
1258 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1259 /* We might generate an endless loop, so keep it alive. */
1260 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1261 } else if ((get_irn_op(a) == op_Eor)
1262 && (get_irn_mode(a) == mode_b)
1263 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1264 /* The Eor is a negate. Generate a new Cond without the negate,
1265 simulate the negate by exchanging the results. */
1266 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1268 } else if ((get_irn_op(a) == op_Not)
1269 && (get_irn_mode(a) == mode_b)) {
1270 /* A Not before the Cond. Generate a new Cond without the Not,
1271 simulate the Not by exchanging the results. */
1272 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1278 static ir_node *transform_node_Eor(ir_node *n)
1280 ir_node *a = get_Eor_left(n);
1281 ir_node *b = get_Eor_right(n);
1283 if ((get_irn_mode(n) == mode_b)
1284 && (get_irn_op(a) == op_Proj)
1285 && (get_irn_mode(a) == mode_b)
1286 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1287 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1288 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1289 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1290 mode_b, get_negated_pnc(get_Proj_proj(a)));
1291 else if ((get_irn_mode(n) == mode_b)
1292 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1293 /* The Eor is a Not. Replace it by a Not. */
1294 /* ????!!!Extend to bitfield 1111111. */
1295 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1301 * Transform a boolean Not.
1303 static ir_node *transform_node_Not(ir_node *n)
1305 ir_node *a = get_Not_op(n);
1307 if ( (get_irn_mode(n) == mode_b)
1308 && (get_irn_op(a) == op_Proj)
1309 && (get_irn_mode(a) == mode_b)
1310 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1311 /* We negate a Cmp. The Cmp has the negated result anyways! */
1312 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1313 mode_b, get_negated_pnc(get_Proj_proj(a)));
1319 * Transform a Cast of a Const into a new Const
1321 static ir_node *transform_node_Cast(ir_node *n) {
1322 ir_node *pred = get_Cast_op(n);
1323 type *tp = get_irn_type(pred);
1325 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1326 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1327 get_Const_tarval(pred), tp);
1328 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1329 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1330 get_SymConst_kind(pred), tp);
1336 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1337 * done here instead of equivalent node because it creates new
1339 * Removes the exceptions and routes the memory to the initial mem.
1341 * Further, it optimizes jump tables by removing all impossible cases.
1343 static ir_node *transform_node_Proj(ir_node *proj)
1345 ir_node *n = get_Proj_pred(proj);
1350 switch (get_irn_opcode(n)) {
1352 b = get_Div_right(n);
1355 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1356 proj_nr = get_Proj_proj(proj);
1358 /* this node may float */
1359 set_irn_pinned(n, op_pin_state_floats);
1361 if (proj_nr == pn_Div_X_except) {
1362 /* we found an exception handler, remove it */
1366 /* the memory Proj can be removed */
1367 ir_node *res = get_Div_mem(n);
1368 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1370 if (proj_nr == pn_Div_M)
1376 b = get_Mod_right(n);
1379 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1380 proj_nr = get_Proj_proj(proj);
1382 /* this node may float */
1383 set_irn_pinned(n, op_pin_state_floats);
1385 if (proj_nr == pn_Mod_X_except) {
1386 /* we found an exception handler, remove it */
1390 /* the memory Proj can be removed */
1391 ir_node *res = get_Mod_mem(n);
1392 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1393 if (proj_nr == pn_Mod_M)
1399 b = get_DivMod_right(n);
1402 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1403 proj_nr = get_Proj_proj(proj);
1405 /* this node may float */
1406 set_irn_pinned(n, op_pin_state_floats);
1408 if (proj_nr == pn_DivMod_X_except) {
1409 /* we found an exception handler, remove it */
1413 /* the memory Proj can be removed */
1414 ir_node *res = get_DivMod_mem(n);
1415 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1416 if (proj_nr == pn_DivMod_M)
1423 if (get_opt_unreachable_code()) {
1424 b = get_Cond_selector(n);
1427 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1428 /* we have a constant switch */
1429 long num = get_Proj_proj(proj);
1431 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1432 if (get_tarval_long(tb) == num) {
1433 /* Do NOT create a jump here, or we will have 2 control flow ops
1434 * in a block. This case is optimized away in optimize_cf(). */
1445 /* should not happen, but if it does will be optimized away */
1453 /* we have added a Tuple, optimize it for the current Proj away */
1454 return equivalent_node_Proj(proj);
1458 * returns the operands of a commutative bin-op, if one operand is
1459 * a const, it is returned as the second one.
1461 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1463 ir_node *op_a = get_binop_left(binop);
1464 ir_node *op_b = get_binop_right(binop);
1466 assert(is_op_commutative(get_irn_op(binop)));
1468 if (get_irn_op(op_a) == op_Const) {
1479 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1480 * Such pattern may arise in bitfield stores.
1482 * value c4 value c4 & c2
1483 * AND c3 AND c1 | c3
1488 static ir_node *transform_node_Or(ir_node *or)
1492 ir_node *and_l, *c3;
1493 ir_node *value, *c4;
1494 ir_node *new_and, *new_const, *block;
1495 ir_mode *mode = get_irn_mode(or);
1497 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1499 get_comm_Binop_Ops(or, &and, &c1);
1500 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1503 get_comm_Binop_Ops(and, &or_l, &c2);
1504 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1507 get_comm_Binop_Ops(or_l, &and_l, &c3);
1508 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1511 get_comm_Binop_Ops(and_l, &value, &c4);
1512 if (get_irn_op(c4) != op_Const)
1515 /* ok, found the pattern, check for conditions */
1516 assert(mode == get_irn_mode(and));
1517 assert(mode == get_irn_mode(or_l));
1518 assert(mode == get_irn_mode(and_l));
1520 tv1 = get_Const_tarval(c1);
1521 tv2 = get_Const_tarval(c2);
1522 tv3 = get_Const_tarval(c3);
1523 tv4 = get_Const_tarval(c4);
1525 tv = tarval_or(tv4, tv2);
1526 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1527 /* have at least one 0 at the same bit position */
1531 n_tv4 = tarval_not(tv4);
1532 if (tv3 != tarval_and(tv3, n_tv4)) {
1533 /* bit in the or_mask is outside the and_mask */
1537 n_tv2 = tarval_not(tv2);
1538 if (tv1 != tarval_and(tv1, n_tv2)) {
1539 /* bit in the or_mask is outside the and_mask */
1543 /* ok, all conditions met */
1544 block = get_nodes_block(or);
1546 new_and = new_r_And(current_ir_graph, block,
1547 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1549 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1551 set_Or_left(or, new_and);
1552 set_Or_right(or, new_const);
1554 /* check for more */
1555 return transform_node_Or(or);
1559 static ir_node *transform_node(ir_node *n);
1562 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1564 static ir_node * transform_node_shift(ir_node *n)
1567 tarval *tv1, *tv2, *res;
1569 int modulo_shf, flag;
1571 left = get_binop_left(n);
1573 /* different operations */
1574 if (get_irn_op(left) != get_irn_op(n))
1577 tv1 = value_of(get_binop_right(n));
1578 if (tv1 == tarval_bad)
1581 tv2 = value_of(get_binop_right(left));
1582 if (tv2 == tarval_bad)
1585 res = tarval_add(tv1, tv2);
1587 /* beware: a simple replacement works only, if res < modulo shift */
1588 mode = get_irn_mode(n);
1592 modulo_shf = get_mode_modulo_shift(mode);
1593 if (modulo_shf > 0) {
1594 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1596 if (tarval_cmp(res, modulo) & Lt)
1603 /* ok, we can replace it */
1604 ir_node *in[2], *irn, *block = get_nodes_block(n);
1606 in[0] = get_binop_left(left);
1607 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1609 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1611 return transform_node(irn);
1618 * Tries several [inplace] [optimizing] transformations and returns an
1619 * equivalent node. The difference to equivalent_node() is that these
1620 * transformations _do_ generate new nodes, and thus the old node must
1621 * not be freed even if the equivalent node isn't the old one.
1623 static ir_node *transform_node(ir_node *n)
1625 if (n->op->transform_node)
1626 n = n->op->transform_node(n);
1631 * set the default transform node operation
1633 static ir_op *firm_set_default_transform_node(ir_op *op)
1637 op->transform_node = transform_node_##a; \
1654 op->transform_node = transform_node_shift;
1657 op->transform_node = NULL;
1665 /* **************** Common Subexpression Elimination **************** */
1667 /** The size of the hash table used, should estimate the number of nodes
1669 #define N_IR_NODES 512
1671 /** Compares the attributes of two Const nodes. */
1672 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1674 return (get_Const_tarval(a) != get_Const_tarval(b))
1675 || (get_Const_type(a) != get_Const_type(b));
1678 /** Compares the attributes of two Proj nodes. */
1679 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1681 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1684 /** Compares the attributes of two Filter nodes. */
1685 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1687 return get_Filter_proj(a) != get_Filter_proj(b);
1690 /** Compares the attributes of two Alloc nodes. */
1691 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1693 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1694 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1697 /** Compares the attributes of two Free nodes. */
1698 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1700 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1703 /** Compares the attributes of two SymConst nodes. */
1704 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1706 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1707 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1708 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1711 /** Compares the attributes of two Call nodes. */
1712 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1714 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1717 /** Compares the attributes of two FuncCall nodes. */
1718 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1720 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1723 /** Compares the attributes of two Sel nodes. */
1724 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1726 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1727 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1728 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1729 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1730 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1733 /** Compares the attributes of two Phi nodes. */
1734 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1736 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1739 /** Compares the attributes of two Cast nodes. */
1740 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1742 return get_Cast_type(a) != get_Cast_type(b);
1745 /** Compares the attributes of two Load nodes. */
1746 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1748 if (get_Load_volatility(a) == volatility_is_volatile ||
1749 get_Load_volatility(b) == volatility_is_volatile)
1750 /* NEVER do CSE on volatile Loads */
1753 return get_Load_mode(a) != get_Load_mode(b);
1756 /** Compares the attributes of two Store nodes. */
1757 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1759 /* NEVER do CSE on volatile Stores */
1760 return (get_Store_volatility(a) == volatility_is_volatile ||
1761 get_Store_volatility(b) == volatility_is_volatile);
1765 * set the default node attribute compare operation
1767 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1771 op->node_cmp_attr = node_cmp_attr_##a; \
1789 op->node_cmp_attr = NULL;
1797 * Compare function for two nodes in the hash table. Gets two
1798 * nodes as parameters. Returns 0 if the nodes are a cse.
1801 vt_cmp (const void *elt, const void *key)
1809 if (a == b) return 0;
1811 if ((get_irn_op(a) != get_irn_op(b)) ||
1812 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1814 /* compare if a's in and b's in are of equal length */
1815 irn_arity_a = get_irn_intra_arity (a);
1816 if (irn_arity_a != get_irn_intra_arity(b))
1819 /* for block-local cse and op_pin_state_pinned nodes: */
1820 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1821 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1825 /* compare a->in[0..ins] with b->in[0..ins] */
1826 for (i = 0; i < irn_arity_a; i++)
1827 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1831 * here, we already now that the nodes are identical except their
1834 if (a->op->node_cmp_attr)
1835 return a->op->node_cmp_attr(a, b);
1840 #define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3)
1843 * Calculate a hash value of a node.
1846 ir_node_hash (ir_node *node)
1851 if (node->op == op_Const) {
1852 /* special value for const, as they only differ in their tarval. */
1853 h = ADDR_TO_VAL(node->attr.con.tv);
1854 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1855 } else if (node->op == op_SymConst) {
1856 /* special value for const, as they only differ in their symbol. */
1857 h = ADDR_TO_VAL(node->attr.i.sym.type_p);
1858 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1861 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1862 h = irn_arity = get_irn_intra_arity(node);
1864 /* consider all in nodes... except the block if not a control flow. */
1865 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1866 h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i));
1870 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1872 h = 9*h + ADDR_TO_VAL(get_irn_op(node));
1879 new_identities(void) {
1880 return new_pset(vt_cmp, N_IR_NODES);
1884 del_identities(pset *value_table) {
1885 del_pset(value_table);
1889 * Return the canonical node computing the same value as n.
1890 * Looks up the node in a hash table.
1892 * For Const nodes this is performed in the constructor, too. Const
1893 * nodes are extremely time critical because of their frequent use in
1894 * constant string arrays.
1896 static INLINE ir_node *
1897 identify (pset *value_table, ir_node *n)
1901 if (!value_table) return n;
1903 if (get_opt_reassociation()) {
1904 if (is_op_commutative(get_irn_op(n))) {
1905 ir_node *l = get_binop_left(n);
1906 ir_node *r = get_binop_right(n);
1908 /* for commutative operators perform a OP b == b OP a */
1910 set_binop_left(n, r);
1911 set_binop_right(n, l);
1916 o = pset_find (value_table, n, ir_node_hash (n));
1925 * During construction we set the op_pin_state_pinned flag in the graph right when the
1926 * optimization is performed. The flag turning on procedure global cse could
1927 * be changed between two allocations. This way we are safe.
1929 static INLINE ir_node *
1930 identify_cons (pset *value_table, ir_node *n) {
1933 n = identify(value_table, n);
1934 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1935 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1940 * Return the canonical node computing the same value as n.
1941 * Looks up the node in a hash table, enters it in the table
1942 * if it isn't there yet.
1945 identify_remember (pset *value_table, ir_node *n)
1949 if (!value_table) return n;
1951 if (get_opt_reassociation()) {
1952 if (is_op_commutative(get_irn_op(n))) {
1953 ir_node *l = get_binop_left(n);
1954 ir_node *r = get_binop_right(n);
1956 /* for commutative operators perform a OP b == b OP a */
1958 set_binop_left(n, r);
1959 set_binop_right(n, l);
1964 /* lookup or insert in hash table with given hash key. */
1965 o = pset_insert (value_table, n, ir_node_hash (n));
1975 add_identities (pset *value_table, ir_node *node) {
1976 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1977 identify_remember (value_table, node);
1981 * garbage in, garbage out. If a node has a dead input, i.e., the
1982 * Bad node is input to the node, return the Bad node.
1984 static INLINE ir_node *
1985 gigo (ir_node *node)
1988 ir_op* op = get_irn_op(node);
1990 /* remove garbage blocks by looking at control flow that leaves the block
1991 and replacing the control flow by Bad. */
1992 if (get_irn_mode(node) == mode_X) {
1993 ir_node *block = get_nodes_block(node);
1994 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1995 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1996 irn_arity = get_irn_arity(block);
1997 for (i = 0; i < irn_arity; i++) {
1998 if (!is_Bad(get_irn_n(block, i))) break;
2000 if (i == irn_arity) return new_Bad();
2004 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2005 blocks predecessors is dead. */
2006 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2007 irn_arity = get_irn_arity(node);
2008 for (i = -1; i < irn_arity; i++) {
2009 if (is_Bad(get_irn_n(node, i))) {
2015 /* With this code we violate the agreement that local_optimize
2016 only leaves Bads in Block, Phi and Tuple nodes. */
2017 /* If Block has only Bads as predecessors it's garbage. */
2018 /* If Phi has only Bads as predecessors it's garbage. */
2019 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2020 irn_arity = get_irn_arity(node);
2021 for (i = 0; i < irn_arity; i++) {
2022 if (!is_Bad(get_irn_n(node, i))) break;
2024 if (i == irn_arity) node = new_Bad();
2032 * These optimizations deallocate nodes from the obstack.
2033 * It can only be called if it is guaranteed that no other nodes
2034 * reference this one, i.e., right after construction of a node.
2037 optimize_node (ir_node *n)
2041 opcode iro = get_irn_opcode(n);
2043 type *old_tp = get_irn_type(n);
2045 int i, arity = get_irn_arity(n);
2046 for (i = 0; i < arity && !old_tp; ++i)
2047 old_tp = get_irn_type(get_irn_n(n, i));
2050 /* Allways optimize Phi nodes: part of the construction. */
2051 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2053 /* constant expression evaluation / constant folding */
2054 if (get_opt_constant_folding()) {
2055 /* constants can not be evaluated */
2056 if (iro != iro_Const) {
2057 /* try to evaluate */
2058 tv = computed_value(n);
2059 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2061 * we MUST copy the node here temporary, because it's still needed
2062 * for DBG_OPT_ALGSIM0
2064 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2065 oldn = alloca(node_size);
2067 memcpy(oldn, n, node_size);
2068 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2070 /* ARG, copy the in array, we need it for statistics */
2071 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2073 /* evaluation was successful -- replace the node. */
2074 obstack_free (current_ir_graph->obst, n);
2075 n = new_Const (get_tarval_mode (tv), tv);
2076 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2077 set_Const_type(n, old_tp);
2078 DBG_OPT_ALGSIM0(oldn, n);
2084 /* remove unnecessary nodes */
2085 if (get_opt_constant_folding() ||
2086 (iro == iro_Phi) || /* always optimize these nodes. */
2088 (iro == iro_Proj) ||
2089 (iro == iro_Block) ) /* Flags tested local. */
2090 n = equivalent_node (n);
2092 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2094 /** common subexpression elimination **/
2095 /* Checks whether n is already available. */
2096 /* The block input is used to distinguish different subexpressions. Right
2097 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2098 subexpressions within a block. */
2100 n = identify_cons (current_ir_graph->value_table, n);
2103 /* We found an existing, better node, so we can deallocate the old node. */
2104 obstack_free (current_ir_graph->obst, oldn);
2109 /* Some more constant expression evaluation that does not allow to
2111 iro = get_irn_opcode(n);
2112 if (get_opt_constant_folding() ||
2113 (iro == iro_Cond) ||
2114 (iro == iro_Proj)) /* Flags tested local. */
2115 n = transform_node (n);
2117 /* Remove nodes with dead (Bad) input.
2118 Run always for transformation induced Bads. */
2121 /* Now we have a legal, useful node. Enter it in hash table for cse */
2122 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2123 n = identify_remember (current_ir_graph->value_table, n);
2131 * These optimizations never deallocate nodes. This can cause dead
2132 * nodes lying on the obstack. Remove these by a dead node elimination,
2133 * i.e., a copying garbage collection.
2136 optimize_in_place_2 (ir_node *n)
2140 opcode iro = get_irn_opcode(n);
2142 type *old_tp = get_irn_type(n);
2144 int i, arity = get_irn_arity(n);
2145 for (i = 0; i < arity && !old_tp; ++i)
2146 old_tp = get_irn_type(get_irn_n(n, i));
2149 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2151 /* if not optimize return n */
2154 /* Here this is possible. Why? */
2158 /* constant expression evaluation / constant folding */
2159 if (get_opt_constant_folding()) {
2160 /* constants can not be evaluated */
2161 if (iro != iro_Const) {
2162 /* try to evaluate */
2163 tv = computed_value(n);
2164 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2165 /* evaluation was successful -- replace the node. */
2166 n = new_Const (get_tarval_mode (tv), tv);
2168 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2169 set_Const_type(n, old_tp);
2171 DBG_OPT_ALGSIM0(oldn, n);
2177 /* remove unnecessary nodes */
2178 if (get_opt_constant_folding() ||
2179 (iro == iro_Phi) || /* always optimize these nodes. */
2180 (iro == iro_Id) || /* ... */
2181 (iro == iro_Proj) || /* ... */
2182 (iro == iro_Block) ) /* Flags tested local. */
2183 n = equivalent_node (n);
2185 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2187 /** common subexpression elimination **/
2188 /* Checks whether n is already available. */
2189 /* The block input is used to distinguish different subexpressions. Right
2190 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2191 subexpressions within a block. */
2192 if (get_opt_cse()) {
2193 n = identify (current_ir_graph->value_table, n);
2196 /* Some more constant expression evaluation. */
2197 iro = get_irn_opcode(n);
2198 if (get_opt_constant_folding() ||
2199 (iro == iro_Cond) ||
2200 (iro == iro_Proj)) /* Flags tested local. */
2201 n = transform_node (n);
2203 /* Remove nodes with dead (Bad) input.
2204 Run always for transformation induced Bads. */
2207 /* Now we can verify the node, as it has no dead inputs any more. */
2210 /* Now we have a legal, useful node. Enter it in hash table for cse.
2211 Blocks should be unique anyways. (Except the successor of start:
2212 is cse with the start block!) */
2213 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2214 n = identify_remember (current_ir_graph->value_table, n);
2220 * Wrapper for external use, set proper status bits after optimization.
2223 optimize_in_place (ir_node *n)
2225 /* Handle graph state */
2226 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2228 if (get_opt_global_cse())
2229 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2230 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2231 set_irg_outs_inconsistent(current_ir_graph);
2233 /* Maybe we could also test whether optimizing the node can
2234 change the control graph. */
2235 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2236 set_irg_dom_inconsistent(current_ir_graph);
2237 return optimize_in_place_2 (n);
2241 * set the default ir op operations
2243 ir_op *firm_set_default_operations(ir_op *op)
2245 op = firm_set_default_computed_value(op);
2246 op = firm_set_default_equivalent_node(op);
2247 op = firm_set_default_transform_node(op);
2248 op = firm_set_default_node_cmp_attr(op);