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"
34 # ifdef DO_HEAPANALYSIS
35 /* heapanal can't cope with NoMems */
36 # else /* if defined DO_HEAPANALYSIS */
38 # endif /* defined DO_HEAPANALYSIS */
41 * Trivial INLINEable routine for copy propagation.
42 * Does follow Ids, needed to optimize INLINEd code.
44 static INLINE ir_node *
45 follow_Id (ir_node *n)
47 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
52 * return the value of a Constant
54 static tarval *computed_value_Const(ir_node *n)
56 return get_Const_tarval(n);
60 * return the value of a 'sizeof' SymConst
62 static tarval *computed_value_SymConst(ir_node *n)
64 if ((get_SymConst_kind(n) == symconst_size) &&
65 (get_type_state(get_SymConst_type(n))) == layout_fixed)
66 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
71 * return the value of an Add
73 static tarval *computed_value_Add(ir_node *n)
75 ir_node *a = get_Add_left(n);
76 ir_node *b = get_Add_right(n);
78 tarval *ta = value_of(a);
79 tarval *tb = value_of(b);
81 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
82 return tarval_add(ta, tb);
88 * return the value of a Sub
91 static tarval *computed_value_Sub(ir_node *n)
93 ir_node *a = get_Sub_left(n);
94 ir_node *b = get_Sub_right(n);
100 return get_tarval_null(get_irn_mode(n));
105 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
106 return tarval_sub(ta, tb);
112 * return the value of an unary Minus
114 static tarval *computed_value_Minus(ir_node *n)
116 ir_node *a = get_Minus_op(n);
117 tarval *ta = value_of(a);
119 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
120 return tarval_neg(ta);
126 * return the value of a Mul
128 static tarval *computed_value_Mul(ir_node *n)
130 ir_node *a = get_Mul_left(n);
131 ir_node *b = get_Mul_right(n);
133 tarval *ta = value_of(a);
134 tarval *tb = value_of(b);
136 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
137 return tarval_mul(ta, tb);
139 /* a*0 = 0 or 0*b = 0:
140 calls computed_value recursive and returns the 0 with proper
142 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
144 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
151 * return the value of a floating point Quot
153 static tarval *computed_value_Quot(ir_node *n)
155 ir_node *a = get_Quot_left(n);
156 ir_node *b = get_Quot_right(n);
158 tarval *ta = value_of(a);
159 tarval *tb = value_of(b);
161 /* This was missing in original implementation. Why? */
162 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
163 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
164 return tarval_quo(ta, tb);
170 * calculate the value of an integer Div of two nodes
171 * Special case: 0 / b
173 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
175 tarval *ta = value_of(a);
176 tarval *tb = value_of(b);
178 /* Compute c1 / c2 or 0 / a, a != 0 */
179 if (ta != tarval_bad) {
180 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
181 return tarval_div(ta, tb);
182 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
189 * return the value of an integer Div
191 static tarval *computed_value_Div(ir_node *n)
193 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
197 * calculate the value of an integer Mod of two nodes
198 * Special case: a % 1
200 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
202 tarval *ta = value_of(a);
203 tarval *tb = value_of(b);
205 /* Compute c1 % c2 or a % 1 */
206 if (tb != tarval_bad) {
207 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
208 return tarval_mod(ta, tb);
209 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
210 return get_mode_null(get_irn_mode(a));
217 * return the value of an integer Mod
219 static tarval *computed_value_Mod(ir_node *n)
221 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
225 * return the value of an Abs
227 static tarval *computed_value_Abs(ir_node *n)
229 ir_node *a = get_Abs_op(n);
230 tarval *ta = value_of(a);
232 if (ta != tarval_bad)
233 return tarval_abs(ta);
239 * return the value of an And
240 * Special case: a & 0, 0 & b
242 static tarval *computed_value_And(ir_node *n)
244 ir_node *a = get_And_left(n);
245 ir_node *b = get_And_right(n);
247 tarval *ta = value_of(a);
248 tarval *tb = value_of(b);
250 if ((ta != tarval_bad) && (tb != tarval_bad)) {
251 return tarval_and (ta, tb);
255 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
256 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
264 * return the value of an Or
265 * Special case: a | 1...1, 1...1 | b
267 static tarval *computed_value_Or(ir_node *n)
269 ir_node *a = get_Or_left(n);
270 ir_node *b = get_Or_right(n);
272 tarval *ta = value_of(a);
273 tarval *tb = value_of(b);
275 if ((ta != tarval_bad) && (tb != tarval_bad)) {
276 return tarval_or (ta, tb);
279 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
280 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
288 * return the value of an Eor
290 static tarval *computed_value_Eor(ir_node *n)
292 ir_node *a = get_Eor_left(n);
293 ir_node *b = get_Eor_right(n);
298 return get_tarval_null(get_irn_mode(n));
303 if ((ta != tarval_bad) && (tb != tarval_bad)) {
304 return tarval_eor (ta, tb);
310 * return the value of a Not
312 static tarval *computed_value_Not(ir_node *n)
314 ir_node *a = get_Not_op(n);
315 tarval *ta = value_of(a);
317 if (ta != tarval_bad)
318 return tarval_not(ta);
324 * return the value of a Shl
326 static tarval *computed_value_Shl(ir_node *n)
328 ir_node *a = get_Shl_left(n);
329 ir_node *b = get_Shl_right(n);
331 tarval *ta = value_of(a);
332 tarval *tb = value_of(b);
334 if ((ta != tarval_bad) && (tb != tarval_bad)) {
335 return tarval_shl (ta, tb);
341 * return the value of a Shr
343 static tarval *computed_value_Shr(ir_node *n)
345 ir_node *a = get_Shr_left(n);
346 ir_node *b = get_Shr_right(n);
348 tarval *ta = value_of(a);
349 tarval *tb = value_of(b);
351 if ((ta != tarval_bad) && (tb != tarval_bad)) {
352 return tarval_shr (ta, tb);
358 * return the value of a Shrs
360 static tarval *computed_value_Shrs(ir_node *n)
362 ir_node *a = get_Shrs_left(n);
363 ir_node *b = get_Shrs_right(n);
365 tarval *ta = value_of(a);
366 tarval *tb = value_of(b);
368 if ((ta != tarval_bad) && (tb != tarval_bad)) {
369 return tarval_shrs (ta, tb);
375 * return the value of a Rot
377 static tarval *computed_value_Rot(ir_node *n)
379 ir_node *a = get_Rot_left(n);
380 ir_node *b = get_Rot_right(n);
382 tarval *ta = value_of(a);
383 tarval *tb = value_of(b);
385 if ((ta != tarval_bad) && (tb != tarval_bad)) {
386 return tarval_rot (ta, tb);
392 * return the value of a Conv
394 static tarval *computed_value_Conv(ir_node *n)
396 ir_node *a = get_Conv_op(n);
397 tarval *ta = value_of(a);
399 if (ta != tarval_bad)
400 return tarval_convert_to(ta, get_irn_mode(n));
406 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
408 static tarval *computed_value_Proj(ir_node *n)
410 ir_node *a = get_Proj_pred(n);
414 /* Optimize Cmp nodes.
415 This performs a first step of unreachable code elimination.
416 Proj can not be computed, but folding a Cmp above the Proj here is
417 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
419 There are several case where we can evaluate a Cmp node:
420 1. The nodes compared are both the same. If we compare for
421 equal, greater equal, ... this will return true, else it
422 will return false. This step relies on cse.
423 2. The predecessors of Cmp are target values. We can evaluate
425 3. The predecessors are Allocs or void* constants. Allocs never
426 return NULL, they raise an exception. Therefore we can predict
428 switch (get_irn_opcode(a)) {
430 aa = get_Cmp_left(a);
431 ab = get_Cmp_right(a);
432 proj_nr = get_Proj_proj(n);
434 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
435 /* BEWARE: a == a is NOT always True for floating Point!!! */
436 /* This is a trick with the bits used for encoding the Cmp
437 Proj numbers, the following statement is not the same:
438 return new_tarval_from_long (proj_nr == Eq, mode_b) */
439 return new_tarval_from_long (proj_nr & Eq, mode_b);
441 tarval *taa = value_of(aa);
442 tarval *tab = value_of(ab);
444 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
445 /* strange checks... */
446 pnc_number flags = tarval_cmp (taa, tab);
447 if (flags != False) {
448 return new_tarval_from_long (proj_nr & flags, mode_b);
450 } else { /* check for 3.: */
451 ir_node *aaa = skip_Id(skip_Proj(aa));
452 ir_node *aba = skip_Id(skip_Proj(ab));
454 if ( ( (/* aa is ProjP and aaa is Alloc */
455 (get_irn_op(aa) == op_Proj)
456 && (mode_is_reference(get_irn_mode(aa)))
457 && (get_irn_op(aaa) == op_Alloc))
458 && ( (/* ab is constant void */
459 (get_irn_op(ab) == op_Const)
460 && (mode_is_reference(get_irn_mode(ab)))
461 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
462 || (/* ab is other Alloc */
463 (get_irn_op(ab) == op_Proj)
464 && (mode_is_reference(get_irn_mode(ab)))
465 && (get_irn_op(aba) == op_Alloc)
467 || (/* aa is void and aba is Alloc */
468 (get_irn_op(aa) == op_Const)
469 && (mode_is_reference(get_irn_mode(aa)))
470 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
471 && (get_irn_op(ab) == op_Proj)
472 && (mode_is_reference(get_irn_mode(ab)))
473 && (get_irn_op(aba) == op_Alloc)))
475 return new_tarval_from_long (proj_nr & Ne, mode_b);
481 /* compute either the Div or the Mod part */
482 proj_nr = get_Proj_proj(n);
483 if (proj_nr == pn_DivMod_res_div)
484 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
485 else if (proj_nr == pn_DivMod_res_mod)
486 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
490 if (get_Proj_proj(n) == pn_Div_res)
491 return computed_value(a);
495 if (get_Proj_proj(n) == pn_Mod_res)
496 return computed_value(a);
506 * If the parameter n can be computed, return its value, else tarval_bad.
507 * Performs constant folding.
509 * @param n The node this should be evaluated
511 tarval *computed_value(ir_node *n)
513 if (n->op->computed_value)
514 return n->op->computed_value(n);
519 * set the default computed_value evaluator
521 static ir_op *firm_set_default_computed_value(ir_op *op)
525 op->computed_value = computed_value_##a; \
550 op->computed_value = NULL;
558 /* returns 1 if the a and b are pointers to different locations. */
560 different_identity (ir_node *a, ir_node *b)
562 assert (mode_is_reference(get_irn_mode (a))
563 && mode_is_reference(get_irn_mode (b)));
565 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
566 ir_node *a1 = get_Proj_pred (a);
567 ir_node *b1 = get_Proj_pred (b);
568 if (a1 != b1 && get_irn_op (a1) == op_Alloc
569 && get_irn_op (b1) == op_Alloc)
576 static ir_node *equivalent_node_Block(ir_node *n)
580 /* The Block constructor does not call optimize, but mature_immBlock
581 calls the optimization. */
582 assert(get_Block_matured(n));
584 /* Straightening: a single entry Block following a single exit Block
585 can be merged, if it is not the Start block. */
586 /* !!! Beware, all Phi-nodes of n must have been optimized away.
587 This should be true, as the block is matured before optimize is called.
588 But what about Phi-cycles with the Phi0/Id that could not be resolved?
589 Remaining Phi nodes are just Ids. */
590 if ((get_Block_n_cfgpreds(n) == 1) &&
591 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
592 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
593 if (predblock == oldn) {
594 /* Jmp jumps into the block it is in -- deal self cycle. */
596 DBG_OPT_DEAD(oldn, n);
597 } else if (get_opt_control_flow_straightening()) {
599 DBG_OPT_STG(oldn, n);
602 else if ((get_Block_n_cfgpreds(n) == 1) &&
603 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
604 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
605 if (predblock == oldn) {
606 /* Jmp jumps into the block it is in -- deal self cycle. */
608 DBG_OPT_DEAD(oldn, n);
611 else if ((get_Block_n_cfgpreds(n) == 2) &&
612 (get_opt_control_flow_weak_simplification())) {
613 /* Test whether Cond jumps twice to this block
614 @@@ we could do this also with two loops finding two preds from several ones. */
615 ir_node *a = get_Block_cfgpred(n, 0);
616 ir_node *b = get_Block_cfgpred(n, 1);
618 if ((get_irn_op(a) == op_Proj) &&
619 (get_irn_op(b) == op_Proj) &&
620 (get_Proj_pred(a) == get_Proj_pred(b)) &&
621 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
622 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
623 /* Also a single entry Block following a single exit Block. Phis have
624 twice the same operand and will be optimized away. */
625 n = get_nodes_block(a);
626 DBG_OPT_IFSIM(oldn, a, b, n);
628 } else if (get_opt_unreachable_code() &&
629 (n != current_ir_graph->start_block) &&
630 (n != current_ir_graph->end_block) ) {
632 /* If all inputs are dead, this block is dead too, except if it is
633 the start or end block. This is a step of unreachable code
635 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
636 if (!is_Bad(get_Block_cfgpred(n, i))) break;
638 if (i == get_Block_n_cfgpreds(n))
646 * Returns a equivalent node for a Jmp, a Bad :-)
647 * Of course this only happens if the Block of the Jmp is Bad.
649 static ir_node *equivalent_node_Jmp(ir_node *n)
651 /* GL: Why not same for op_Raise?? */
652 /* unreachable code elimination */
653 if (is_Bad(get_nodes_block(n)))
659 static ir_node *equivalent_node_Cond(ir_node *n)
661 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
662 See cases for iro_Cond and iro_Proj in transform_node. */
667 * optimize operations that are commutative and have neutral 0,
668 * so a op 0 = 0 op a = a.
670 static ir_node *equivalent_node_neutral_zero(ir_node *n)
674 ir_node *a = get_binop_left(n);
675 ir_node *b = get_binop_right(n);
680 /* After running compute_node there is only one constant predecessor.
681 Find this predecessors value and remember the other node: */
682 if ((tv = value_of(a)) != tarval_bad) {
684 } else if ((tv = value_of(b)) != tarval_bad) {
689 /* If this predecessors constant value is zero, the operation is
690 unnecessary. Remove it: */
691 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
694 DBG_OPT_ALGSIM1(oldn, a, b, n);
700 #define equivalent_node_Add equivalent_node_neutral_zero
701 #define equivalent_node_Eor equivalent_node_neutral_zero
704 * optimize operations that are not commutative but have neutral 0 on left,
707 static ir_node *equivalent_node_left_zero(ir_node *n)
711 ir_node *a = get_binop_left(n);
712 ir_node *b = get_binop_right(n);
714 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
717 DBG_OPT_ALGSIM1(oldn, a, b, n);
723 #define equivalent_node_Sub equivalent_node_left_zero
724 #define equivalent_node_Shl equivalent_node_left_zero
725 #define equivalent_node_Shr equivalent_node_left_zero
726 #define equivalent_node_Shrs equivalent_node_left_zero
727 #define equivalent_node_Rot equivalent_node_left_zero
730 * Er, a "symmetic unop", ie op(op(n)) = n.
732 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
735 ir_node *pred = get_unop_op(n);
737 /* optimize symmetric unop */
738 if (get_irn_op(pred) == get_irn_op(n)) {
739 n = get_unop_op(pred);
740 DBG_OPT_ALGSIM2(oldn, pred, n);
746 #define equivalent_node_Not equivalent_node_symmetric_unop
748 /* --x == x */ /* ??? Is this possible or can --x raise an
749 out of bounds exception if min =! max? */
750 #define equivalent_node_Minus equivalent_node_symmetric_unop
753 * Optimize a * 1 = 1 * a = a.
755 static ir_node *equivalent_node_Mul(ir_node *n)
759 ir_node *a = get_Mul_left(n);
760 ir_node *b = get_Mul_right(n);
762 /* Mul is commutative and has again an other neutral element. */
763 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
765 DBG_OPT_ALGSIM1(oldn, a, b, n);
766 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
768 DBG_OPT_ALGSIM1(oldn, a, b, n);
774 * Optimize a / 1 = a.
776 static ir_node *equivalent_node_Div(ir_node *n)
778 ir_node *a = get_Div_left(n);
779 ir_node *b = get_Div_right(n);
781 /* Div is not commutative. */
782 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
783 /* Turn Div into a tuple (mem, bad, a) */
784 ir_node *mem = get_Div_mem(n);
785 turn_into_tuple(n, 3);
786 set_Tuple_pred(n, pn_Div_M, mem);
787 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
788 set_Tuple_pred(n, pn_Div_res, a);
794 * Optimize a / 1 = a.
796 static ir_node *equivalent_node_DivMod(ir_node *n)
798 ir_node *a = get_DivMod_left(n);
799 ir_node *b = get_DivMod_right(n);
801 /* Div is not commutative. */
802 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
803 /* Turn DivMod into a tuple (mem, bad, a, 0) */
804 ir_node *mem = get_Div_mem(n);
805 ir_mode *mode = get_irn_mode(b);
807 turn_into_tuple(n, 4);
808 set_Tuple_pred(n, pn_DivMod_M, mem);
809 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
810 set_Tuple_pred(n, pn_DivMod_res_div, a);
811 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
817 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
819 static ir_node *equivalent_node_Or(ir_node *n)
823 ir_node *a = get_Or_left(n);
824 ir_node *b = get_Or_right(n);
827 n = a; /* Or has it's own neutral element */
828 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
830 DBG_OPT_ALGSIM1(oldn, a, b, n);
831 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
833 DBG_OPT_ALGSIM1(oldn, a, b, n);
840 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
842 static ir_node *equivalent_node_And(ir_node *n)
846 ir_node *a = get_And_left(n);
847 ir_node *b = get_And_right(n);
850 n = a; /* And has it's own neutral element */
851 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
853 DBG_OPT_ALGSIM1(oldn, a, b, n);
854 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
856 DBG_OPT_ALGSIM1(oldn, a, b, n);
862 * Try to remove useless conv's:
864 static ir_node *equivalent_node_Conv(ir_node *n)
867 ir_node *a = get_Conv_op(n);
870 ir_mode *n_mode = get_irn_mode(n);
871 ir_mode *a_mode = get_irn_mode(a);
873 if (n_mode == a_mode) { /* No Conv necessary */
875 DBG_OPT_ALGSIM3(oldn, a, n);
876 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
880 n_mode = get_irn_mode(n);
881 b_mode = get_irn_mode(b);
883 if (n_mode == b_mode) {
884 if (n_mode == mode_b) {
885 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
886 DBG_OPT_ALGSIM1(oldn, a, b, n);
888 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
889 if (smaller_mode(b_mode, a_mode)){
890 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
891 DBG_OPT_ALGSIM1(oldn, a, b, n);
899 static ir_node *equivalent_node_Cast(ir_node *n) {
900 ir_node *pred = get_Cast_op(n);
901 if (get_irn_type(pred) == get_Cast_type(n))
906 static ir_node *equivalent_node_Phi(ir_node *n)
908 /* Several optimizations:
909 - no Phi in start block.
910 - remove Id operators that are inputs to Phi
911 - fold Phi-nodes, iff they have only one predecessor except
917 ir_node *block = NULL; /* to shutup gcc */
918 ir_node *first_val = NULL; /* to shutup gcc */
919 ir_node *scnd_val = NULL; /* to shutup gcc */
921 if (!get_opt_normalize()) return n;
923 n_preds = get_Phi_n_preds(n);
925 block = get_nodes_block(n);
926 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
927 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
928 if ((is_Bad(block)) || /* Control dead */
929 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
930 return new_Bad(); /* in the Start Block. */
932 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
935 /* first we test for a special case: */
936 /* Confirm is a special node fixing additional information for a
937 value that is known at a certain point. This is useful for
938 dataflow analysis. */
940 ir_node *a = get_Phi_pred(n, 0);
941 ir_node *b = get_Phi_pred(n, 1);
942 if ( (get_irn_op(a) == op_Confirm)
943 && (get_irn_op(b) == op_Confirm)
944 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
945 && (get_irn_n(a, 1) == get_irn_n (b, 1))
946 && (a->data.num == (~b->data.num & irpn_True) )) {
947 return get_irn_n(a, 0);
952 /* If the Block has a Bad pred, we also have one. */
953 for (i = 0; i < n_preds; ++i)
954 if (is_Bad (get_Block_cfgpred(block, i)))
955 set_Phi_pred(n, i, new_Bad());
957 /* Find first non-self-referencing input */
958 for (i = 0; i < n_preds; ++i) {
959 first_val = get_Phi_pred(n, i);
960 if ( (first_val != n) /* not self pointer */
962 && (get_irn_op(first_val) != op_Bad)
964 ) { /* value not dead */
965 break; /* then found first value. */
969 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
970 if (i >= n_preds) { return new_Bad(); }
974 /* follow_Id () for rest of inputs, determine if any of these
975 are non-self-referencing */
976 while (++i < n_preds) {
977 scnd_val = get_Phi_pred(n, i);
979 && (scnd_val != first_val)
981 && (get_irn_op(scnd_val) != op_Bad)
988 /* Fold, if no multiple distinct non-self-referencing inputs */
991 DBG_OPT_PHI(oldn, first_val, n);
993 /* skip the remaining Ids (done in get_Phi_pred). */
994 /* superfluous, since we walk all to propagate Block's Bads.
995 while (++i < n_preds) get_Phi_pred(n, i); */
1001 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1003 static ir_node *equivalent_node_Proj(ir_node *n)
1007 ir_node *a = get_Proj_pred(n);
1009 if ( get_irn_op(a) == op_Tuple) {
1010 /* Remove the Tuple/Proj combination. */
1011 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1012 n = get_Tuple_pred(a, get_Proj_proj(n));
1013 DBG_OPT_TUPLE(oldn, a, n);
1015 assert(0); /* This should not happen! */
1018 } else if (get_irn_mode(n) == mode_X &&
1019 is_Bad(get_nodes_block(n))) {
1020 /* Remove dead control flow -- early gigo. */
1029 static ir_node *equivalent_node_Id(ir_node *n)
1034 DBG_OPT_ID(oldn, n);
1039 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1040 * perform no actual computation, as, e.g., the Id nodes. It does not create
1041 * new nodes. It is therefore safe to free n if the node returned is not n.
1042 * If a node returns a Tuple we can not just skip it. If the size of the
1043 * in array fits, we transform n into a tuple (e.g., Div).
1046 equivalent_node(ir_node *n)
1048 if (n->op->equivalent_node)
1049 return n->op->equivalent_node(n);
1054 * set the default equivalent node operation
1056 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1060 op->equivalent_node = equivalent_node_##a; \
1087 op->equivalent_node = NULL;
1095 * Do node specific optimizations of nodes predecessors.
1098 optimize_preds(ir_node *n) {
1099 ir_node *a = NULL, *b = NULL;
1101 /* get the operands we will work on for simple cases. */
1103 a = get_binop_left(n);
1104 b = get_binop_right(n);
1105 } else if (is_unop(n)) {
1109 switch (get_irn_opcode(n)) {
1112 /* We don't want Cast as input to Cmp. */
1113 if (get_irn_op(a) == op_Cast) {
1117 if (get_irn_op(b) == op_Cast) {
1119 set_Cmp_right(n, b);
1127 /** Do architecture dependend optimizations on Mul nodes */
1128 static ir_node *transform_node_Mul(ir_node *n) {
1129 return arch_dep_replace_mul_with_shifts(n);
1132 static ir_node *transform_node_Div(ir_node *n)
1134 tarval *tv = value_of(n);
1137 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1139 if (tv != tarval_bad)
1140 value = new_Const(get_tarval_mode(tv), tv);
1141 else /* Try architecture dependand optimization */
1142 value = arch_dep_replace_div_by_const(n);
1145 /* Turn Div into a tuple (mem, bad, value) */
1146 ir_node *mem = get_Div_mem(n);
1148 turn_into_tuple(n, 3);
1149 set_Tuple_pred(n, pn_Div_M, mem);
1150 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1151 set_Tuple_pred(n, pn_Div_res, value);
1156 static ir_node *transform_node_Mod(ir_node *n)
1158 tarval *tv = value_of(n);
1161 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1163 if (tv != tarval_bad)
1164 value = new_Const(get_tarval_mode(tv), tv);
1165 else /* Try architecture dependand optimization */
1166 value = arch_dep_replace_mod_by_const(n);
1169 /* Turn Mod into a tuple (mem, bad, value) */
1170 ir_node *mem = get_Mod_mem(n);
1172 turn_into_tuple(n, 3);
1173 set_Tuple_pred(n, pn_Mod_M, mem);
1174 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1175 set_Tuple_pred(n, pn_Mod_res, value);
1180 static ir_node *transform_node_DivMod(ir_node *n)
1184 ir_node *a = get_DivMod_left(n);
1185 ir_node *b = get_DivMod_right(n);
1186 ir_mode *mode = get_irn_mode(a);
1187 tarval *ta = value_of(a);
1188 tarval *tb = value_of(b);
1190 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1193 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1195 if (tb != tarval_bad) {
1196 if (tb == get_mode_one(get_tarval_mode(tb))) {
1197 b = new_Const (mode, get_mode_null(mode));
1199 } else if (ta != tarval_bad) {
1200 tarval *resa, *resb;
1201 resa = tarval_div (ta, tb);
1202 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1203 Jmp for X result!? */
1204 resb = tarval_mod (ta, tb);
1205 if (resb == tarval_bad) return n; /* Causes exception! */
1206 a = new_Const (mode, resa);
1207 b = new_Const (mode, resb);
1210 else { /* Try architecture dependand optimization */
1211 arch_dep_replace_divmod_by_const(&a, &b, n);
1212 evaluated = a != NULL;
1214 } else if (ta == get_mode_null(mode)) {
1215 /* 0 / non-Const = 0 */
1220 if (evaluated) { /* replace by tuple */
1221 ir_node *mem = get_DivMod_mem(n);
1222 turn_into_tuple(n, 4);
1223 set_Tuple_pred(n, pn_DivMod_M, mem);
1224 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1225 set_Tuple_pred(n, pn_DivMod_res_div, a);
1226 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1227 assert(get_nodes_block(n));
1233 static ir_node *transform_node_Cond(ir_node *n)
1235 /* Replace the Cond by a Jmp if it branches on a constant
1238 ir_node *a = get_Cond_selector(n);
1239 tarval *ta = value_of(a);
1241 if ((ta != tarval_bad) &&
1242 (get_irn_mode(a) == mode_b) &&
1243 (get_opt_unreachable_code())) {
1244 /* It's a boolean Cond, branching on a boolean constant.
1245 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1246 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1247 turn_into_tuple(n, 2);
1248 if (ta == tarval_b_true) {
1249 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1250 set_Tuple_pred(n, pn_Cond_true, jmp);
1252 set_Tuple_pred(n, pn_Cond_false, jmp);
1253 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1255 /* We might generate an endless loop, so keep it alive. */
1256 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1257 } else if ((ta != tarval_bad) &&
1258 (get_irn_mode(a) == mode_Iu) &&
1259 (get_Cond_kind(n) == dense) &&
1260 (get_opt_unreachable_code())) {
1261 /* I don't want to allow Tuples smaller than the biggest Proj.
1262 Also this tuple might get really big...
1263 I generate the Jmp here, and remember it in link. Link is used
1264 when optimizing Proj. */
1265 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1266 /* We might generate an endless loop, so keep it alive. */
1267 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1268 } else if ((get_irn_op(a) == op_Eor)
1269 && (get_irn_mode(a) == mode_b)
1270 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1271 /* The Eor is a negate. Generate a new Cond without the negate,
1272 simulate the negate by exchanging the results. */
1273 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1275 } else if ((get_irn_op(a) == op_Not)
1276 && (get_irn_mode(a) == mode_b)) {
1277 /* A Not before the Cond. Generate a new Cond without the Not,
1278 simulate the Not by exchanging the results. */
1279 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1285 static ir_node *transform_node_Eor(ir_node *n)
1287 ir_node *a = get_Eor_left(n);
1288 ir_node *b = get_Eor_right(n);
1290 if ((get_irn_mode(n) == mode_b)
1291 && (get_irn_op(a) == op_Proj)
1292 && (get_irn_mode(a) == mode_b)
1293 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1294 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1295 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1296 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1297 mode_b, get_negated_pnc(get_Proj_proj(a)));
1298 else if ((get_irn_mode(n) == mode_b)
1299 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1300 /* The Eor is a Not. Replace it by a Not. */
1301 /* ????!!!Extend to bitfield 1111111. */
1302 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1308 * Transform a boolean Not.
1310 static ir_node *transform_node_Not(ir_node *n)
1312 ir_node *a = get_Not_op(n);
1314 if ( (get_irn_mode(n) == mode_b)
1315 && (get_irn_op(a) == op_Proj)
1316 && (get_irn_mode(a) == mode_b)
1317 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1318 /* We negate a Cmp. The Cmp has the negated result anyways! */
1319 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1320 mode_b, get_negated_pnc(get_Proj_proj(a)));
1326 * Transform a Cast of a Const into a new Const
1328 static ir_node *transform_node_Cast(ir_node *n) {
1329 ir_node *pred = get_Cast_op(n);
1330 type *tp = get_irn_type(pred);
1332 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1333 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1334 get_Const_tarval(pred), tp);
1335 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1336 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1337 get_SymConst_kind(pred), tp);
1343 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1344 * done here instead of equivalent node because it creates new
1346 * Removes the exceptions and routes the memory to the NoMem node.
1348 * Further, it optimizes jump tables by removing all impossible cases.
1350 static ir_node *transform_node_Proj(ir_node *proj)
1352 ir_node *n = get_Proj_pred(proj);
1357 switch (get_irn_opcode(n)) {
1359 b = get_Div_right(n);
1362 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1363 proj_nr = get_Proj_proj(proj);
1365 /* this node may float */
1366 set_irn_pinned(n, op_pin_state_floats);
1368 if (proj_nr == pn_Div_X_except) {
1369 /* we found an exception handler, remove it */
1372 /* the memory Proj can be removed */
1373 ir_node *res = get_Div_mem(n);
1375 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1376 # endif /* defined USE_NOMEM */
1377 if (proj_nr == pn_Div_M)
1383 b = get_Mod_right(n);
1386 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1387 proj_nr = get_Proj_proj(proj);
1389 /* this node may float */
1390 set_irn_pinned(n, op_pin_state_floats);
1392 if (proj_nr == pn_Mod_X_except) {
1393 /* we found an exception handler, remove it */
1396 /* the memory Proj can be removed */
1397 ir_node *res = get_Mod_mem(n);
1399 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1400 # endif /* defined USE_NOMEM */
1401 if (proj_nr == pn_Mod_M)
1407 b = get_DivMod_right(n);
1410 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1411 proj_nr = get_Proj_proj(proj);
1413 /* this node may float */
1414 set_irn_pinned(n, op_pin_state_floats);
1416 if (proj_nr == pn_DivMod_X_except) {
1417 /* we found an exception handler, remove it */
1421 /* the memory Proj can be removed */
1422 ir_node *res = get_DivMod_mem(n);
1424 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1425 # endif /* defined USE_NOMEM */
1426 if (proj_nr == pn_DivMod_M)
1433 if (get_opt_unreachable_code()) {
1434 b = get_Cond_selector(n);
1437 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1438 /* we have a constant switch */
1439 long num = get_Proj_proj(proj);
1441 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1442 if (get_tarval_long(tb) == num) {
1443 /* Do NOT create a jump here, or we will have 2 control flow ops
1444 * in a block. This case is optimized away in optimize_cf(). */
1455 /* should not happen, but if it does will be optimized away */
1463 /* we have added a Tuple, optimize it for the current Proj away */
1464 return equivalent_node_Proj(proj);
1468 * returns the operands of a commutative bin-op, if one operand is
1469 * a const, it is returned as the second one.
1471 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1473 ir_node *op_a = get_binop_left(binop);
1474 ir_node *op_b = get_binop_right(binop);
1476 assert(is_op_commutative(get_irn_op(binop)));
1478 if (get_irn_op(op_a) == op_Const) {
1489 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1490 * Such pattern may arise in bitfield stores.
1492 * value c4 value c4 & c2
1493 * AND c3 AND c1 | c3
1498 static ir_node *transform_node_Or(ir_node *or)
1502 ir_node *and_l, *c3;
1503 ir_node *value, *c4;
1504 ir_node *new_and, *new_const, *block;
1505 ir_mode *mode = get_irn_mode(or);
1507 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1509 get_comm_Binop_Ops(or, &and, &c1);
1510 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1513 get_comm_Binop_Ops(and, &or_l, &c2);
1514 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1517 get_comm_Binop_Ops(or_l, &and_l, &c3);
1518 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1521 get_comm_Binop_Ops(and_l, &value, &c4);
1522 if (get_irn_op(c4) != op_Const)
1525 /* ok, found the pattern, check for conditions */
1526 assert(mode == get_irn_mode(and));
1527 assert(mode == get_irn_mode(or_l));
1528 assert(mode == get_irn_mode(and_l));
1530 tv1 = get_Const_tarval(c1);
1531 tv2 = get_Const_tarval(c2);
1532 tv3 = get_Const_tarval(c3);
1533 tv4 = get_Const_tarval(c4);
1535 tv = tarval_or(tv4, tv2);
1536 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1537 /* have at least one 0 at the same bit position */
1541 n_tv4 = tarval_not(tv4);
1542 if (tv3 != tarval_and(tv3, n_tv4)) {
1543 /* bit in the or_mask is outside the and_mask */
1547 n_tv2 = tarval_not(tv2);
1548 if (tv1 != tarval_and(tv1, n_tv2)) {
1549 /* bit in the or_mask is outside the and_mask */
1553 /* ok, all conditions met */
1554 block = get_nodes_block(or);
1556 new_and = new_r_And(current_ir_graph, block,
1557 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1559 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1561 set_Or_left(or, new_and);
1562 set_Or_right(or, new_const);
1564 /* check for more */
1565 return transform_node_Or(or);
1569 static ir_node *transform_node(ir_node *n);
1572 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1574 static ir_node * transform_node_shift(ir_node *n)
1577 tarval *tv1, *tv2, *res;
1579 int modulo_shf, flag;
1581 left = get_binop_left(n);
1583 /* different operations */
1584 if (get_irn_op(left) != get_irn_op(n))
1587 tv1 = value_of(get_binop_right(n));
1588 if (tv1 == tarval_bad)
1591 tv2 = value_of(get_binop_right(left));
1592 if (tv2 == tarval_bad)
1595 res = tarval_add(tv1, tv2);
1597 /* beware: a simple replacement works only, if res < modulo shift */
1598 mode = get_irn_mode(n);
1602 modulo_shf = get_mode_modulo_shift(mode);
1603 if (modulo_shf > 0) {
1604 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1606 if (tarval_cmp(res, modulo) & Lt)
1613 /* ok, we can replace it */
1614 ir_node *in[2], *irn, *block = get_nodes_block(n);
1616 in[0] = get_binop_left(left);
1617 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1619 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1621 return transform_node(irn);
1628 * Tries several [inplace] [optimizing] transformations and returns an
1629 * equivalent node. The difference to equivalent_node() is that these
1630 * transformations _do_ generate new nodes, and thus the old node must
1631 * not be freed even if the equivalent node isn't the old one.
1633 static ir_node *transform_node(ir_node *n)
1635 if (n->op->transform_node)
1636 n = n->op->transform_node(n);
1641 * set the default transform node operation
1643 static ir_op *firm_set_default_transform_node(ir_op *op)
1647 op->transform_node = transform_node_##a; \
1664 op->transform_node = transform_node_shift;
1667 op->transform_node = NULL;
1675 /* **************** Common Subexpression Elimination **************** */
1677 /** The size of the hash table used, should estimate the number of nodes
1679 #define N_IR_NODES 512
1681 /** Compares the attributes of two Const nodes. */
1682 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1684 return (get_Const_tarval(a) != get_Const_tarval(b))
1685 || (get_Const_type(a) != get_Const_type(b));
1688 /** Compares the attributes of two Proj nodes. */
1689 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1691 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1694 /** Compares the attributes of two Filter nodes. */
1695 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1697 return get_Filter_proj(a) != get_Filter_proj(b);
1700 /** Compares the attributes of two Alloc nodes. */
1701 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1703 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1704 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1707 /** Compares the attributes of two Free nodes. */
1708 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1710 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1713 /** Compares the attributes of two SymConst nodes. */
1714 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1716 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1717 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1718 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1721 /** Compares the attributes of two Call nodes. */
1722 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1724 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1727 /** Compares the attributes of two Sel nodes. */
1728 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1730 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1731 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1732 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1733 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1734 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1737 /** Compares the attributes of two Phi nodes. */
1738 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1740 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1743 /** Compares the attributes of two Cast nodes. */
1744 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1746 return get_Cast_type(a) != get_Cast_type(b);
1749 /** Compares the attributes of two Load nodes. */
1750 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1752 if (get_Load_volatility(a) == volatility_is_volatile ||
1753 get_Load_volatility(b) == volatility_is_volatile)
1754 /* NEVER do CSE on volatile Loads */
1757 return get_Load_mode(a) != get_Load_mode(b);
1760 /** Compares the attributes of two Store nodes. */
1761 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1763 /* NEVER do CSE on volatile Stores */
1764 return (get_Store_volatility(a) == volatility_is_volatile ||
1765 get_Store_volatility(b) == volatility_is_volatile);
1769 * set the default node attribute compare operation
1771 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1775 op->node_cmp_attr = node_cmp_attr_##a; \
1792 op->node_cmp_attr = NULL;
1800 * Compare function for two nodes in the hash table. Gets two
1801 * nodes as parameters. Returns 0 if the nodes are a cse.
1804 vt_cmp (const void *elt, const void *key)
1812 if (a == b) return 0;
1814 if ((get_irn_op(a) != get_irn_op(b)) ||
1815 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1817 /* compare if a's in and b's in are of equal length */
1818 irn_arity_a = get_irn_intra_arity (a);
1819 if (irn_arity_a != get_irn_intra_arity(b))
1822 /* for block-local cse and op_pin_state_pinned nodes: */
1823 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1824 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1828 /* compare a->in[0..ins] with b->in[0..ins] */
1829 for (i = 0; i < irn_arity_a; i++)
1830 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1834 * here, we already now that the nodes are identical except their
1837 if (a->op->node_cmp_attr)
1838 return a->op->node_cmp_attr(a, b);
1843 #define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3)
1846 * Calculate a hash value of a node.
1849 ir_node_hash (ir_node *node)
1854 if (node->op == op_Const) {
1855 /* special value for const, as they only differ in their tarval. */
1856 h = ADDR_TO_VAL(node->attr.con.tv);
1857 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1858 } else if (node->op == op_SymConst) {
1859 /* special value for const, as they only differ in their symbol. */
1860 h = ADDR_TO_VAL(node->attr.i.sym.type_p);
1861 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1864 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1865 h = irn_arity = get_irn_intra_arity(node);
1867 /* consider all in nodes... except the block if not a control flow. */
1868 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1869 h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i));
1873 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1875 h = 9*h + ADDR_TO_VAL(get_irn_op(node));
1882 new_identities(void) {
1883 return new_pset(vt_cmp, N_IR_NODES);
1887 del_identities(pset *value_table) {
1888 del_pset(value_table);
1892 * Return the canonical node computing the same value as n.
1893 * Looks up the node in a hash table.
1895 * For Const nodes this is performed in the constructor, too. Const
1896 * nodes are extremely time critical because of their frequent use in
1897 * constant string arrays.
1899 static INLINE ir_node *
1900 identify (pset *value_table, ir_node *n)
1904 if (!value_table) return n;
1906 if (get_opt_reassociation()) {
1907 if (is_op_commutative(get_irn_op(n))) {
1908 ir_node *l = get_binop_left(n);
1909 ir_node *r = get_binop_right(n);
1911 /* for commutative operators perform a OP b == b OP a */
1913 set_binop_left(n, r);
1914 set_binop_right(n, l);
1919 o = pset_find (value_table, n, ir_node_hash (n));
1928 * During construction we set the op_pin_state_pinned flag in the graph right when the
1929 * optimization is performed. The flag turning on procedure global cse could
1930 * be changed between two allocations. This way we are safe.
1932 static INLINE ir_node *
1933 identify_cons (pset *value_table, ir_node *n) {
1936 n = identify(value_table, n);
1937 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1938 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1943 * Return the canonical node computing the same value as n.
1944 * Looks up the node in a hash table, enters it in the table
1945 * if it isn't there yet.
1948 identify_remember (pset *value_table, ir_node *n)
1952 if (!value_table) return n;
1954 if (get_opt_reassociation()) {
1955 if (is_op_commutative(get_irn_op(n))) {
1956 ir_node *l = get_binop_left(n);
1957 ir_node *r = get_binop_right(n);
1959 /* for commutative operators perform a OP b == b OP a */
1961 set_binop_left(n, r);
1962 set_binop_right(n, l);
1967 /* lookup or insert in hash table with given hash key. */
1968 o = pset_insert (value_table, n, ir_node_hash (n));
1978 add_identities (pset *value_table, ir_node *node) {
1979 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1980 identify_remember (value_table, node);
1984 * garbage in, garbage out. If a node has a dead input, i.e., the
1985 * Bad node is input to the node, return the Bad node.
1987 static INLINE ir_node *
1988 gigo (ir_node *node)
1991 ir_op* op = get_irn_op(node);
1993 /* remove garbage blocks by looking at control flow that leaves the block
1994 and replacing the control flow by Bad. */
1995 if (get_irn_mode(node) == mode_X) {
1996 ir_node *block = get_nodes_block(node);
1997 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1998 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1999 irn_arity = get_irn_arity(block);
2000 for (i = 0; i < irn_arity; i++) {
2001 if (!is_Bad(get_irn_n(block, i))) break;
2003 if (i == irn_arity) return new_Bad();
2007 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2008 blocks predecessors is dead. */
2009 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2010 irn_arity = get_irn_arity(node);
2011 for (i = -1; i < irn_arity; i++) {
2012 if (is_Bad(get_irn_n(node, i))) {
2018 /* With this code we violate the agreement that local_optimize
2019 only leaves Bads in Block, Phi and Tuple nodes. */
2020 /* If Block has only Bads as predecessors it's garbage. */
2021 /* If Phi has only Bads as predecessors it's garbage. */
2022 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2023 irn_arity = get_irn_arity(node);
2024 for (i = 0; i < irn_arity; i++) {
2025 if (!is_Bad(get_irn_n(node, i))) break;
2027 if (i == irn_arity) node = new_Bad();
2035 * These optimizations deallocate nodes from the obstack.
2036 * It can only be called if it is guaranteed that no other nodes
2037 * reference this one, i.e., right after construction of a node.
2040 optimize_node (ir_node *n)
2044 opcode iro = get_irn_opcode(n);
2046 type *old_tp = get_irn_type(n);
2048 int i, arity = get_irn_arity(n);
2049 for (i = 0; i < arity && !old_tp; ++i)
2050 old_tp = get_irn_type(get_irn_n(n, i));
2053 /* Allways optimize Phi nodes: part of the construction. */
2054 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2056 /* constant expression evaluation / constant folding */
2057 if (get_opt_constant_folding()) {
2058 /* constants can not be evaluated */
2059 if (iro != iro_Const) {
2060 /* try to evaluate */
2061 tv = computed_value(n);
2062 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2064 * we MUST copy the node here temporary, because it's still needed
2065 * for DBG_OPT_CSTEVAL
2067 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2068 oldn = alloca(node_size);
2070 memcpy(oldn, n, node_size);
2071 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2073 /* ARG, copy the in array, we need it for statistics */
2074 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2076 /* evaluation was successful -- replace the node. */
2077 obstack_free (current_ir_graph->obst, n);
2078 n = new_Const (get_tarval_mode (tv), tv);
2079 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2080 set_Const_type(n, old_tp);
2081 DBG_OPT_CSTEVAL(oldn, n);
2087 /* remove unnecessary nodes */
2088 if (get_opt_constant_folding() ||
2089 (iro == iro_Phi) || /* always optimize these nodes. */
2091 (iro == iro_Proj) ||
2092 (iro == iro_Block) ) /* Flags tested local. */
2093 n = equivalent_node (n);
2095 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2097 /** common subexpression elimination **/
2098 /* Checks whether n is already available. */
2099 /* The block input is used to distinguish different subexpressions. Right
2100 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2101 subexpressions within a block. */
2103 n = identify_cons (current_ir_graph->value_table, n);
2106 /* We found an existing, better node, so we can deallocate the old node. */
2107 obstack_free (current_ir_graph->obst, oldn);
2112 /* Some more constant expression evaluation that does not allow to
2114 iro = get_irn_opcode(n);
2115 if (get_opt_constant_folding() ||
2116 (iro == iro_Cond) ||
2117 (iro == iro_Proj)) /* Flags tested local. */
2118 n = transform_node (n);
2120 /* Remove nodes with dead (Bad) input.
2121 Run always for transformation induced Bads. */
2124 /* Now we have a legal, useful node. Enter it in hash table for cse */
2125 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2126 n = identify_remember (current_ir_graph->value_table, n);
2134 * These optimizations never deallocate nodes. This can cause dead
2135 * nodes lying on the obstack. Remove these by a dead node elimination,
2136 * i.e., a copying garbage collection.
2139 optimize_in_place_2 (ir_node *n)
2143 opcode iro = get_irn_opcode(n);
2145 type *old_tp = get_irn_type(n);
2147 int i, arity = get_irn_arity(n);
2148 for (i = 0; i < arity && !old_tp; ++i)
2149 old_tp = get_irn_type(get_irn_n(n, i));
2152 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2154 /* if not optimize return n */
2157 /* Here this is possible. Why? */
2161 /* constant expression evaluation / constant folding */
2162 if (get_opt_constant_folding()) {
2163 /* constants can not be evaluated */
2164 if (iro != iro_Const) {
2165 /* try to evaluate */
2166 tv = computed_value(n);
2167 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2168 /* evaluation was successful -- replace the node. */
2169 n = new_Const (get_tarval_mode (tv), tv);
2171 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2172 set_Const_type(n, old_tp);
2174 DBG_OPT_CSTEVAL(oldn, n);
2180 /* remove unnecessary nodes */
2181 if (get_opt_constant_folding() ||
2182 (iro == iro_Phi) || /* always optimize these nodes. */
2183 (iro == iro_Id) || /* ... */
2184 (iro == iro_Proj) || /* ... */
2185 (iro == iro_Block) ) /* Flags tested local. */
2186 n = equivalent_node (n);
2188 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2190 /** common subexpression elimination **/
2191 /* Checks whether n is already available. */
2192 /* The block input is used to distinguish different subexpressions. Right
2193 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2194 subexpressions within a block. */
2195 if (get_opt_cse()) {
2196 n = identify (current_ir_graph->value_table, n);
2199 /* Some more constant expression evaluation. */
2200 iro = get_irn_opcode(n);
2201 if (get_opt_constant_folding() ||
2202 (iro == iro_Cond) ||
2203 (iro == iro_Proj)) /* Flags tested local. */
2204 n = transform_node (n);
2206 /* Remove nodes with dead (Bad) input.
2207 Run always for transformation induced Bads. */
2210 /* Now we can verify the node, as it has no dead inputs any more. */
2213 /* Now we have a legal, useful node. Enter it in hash table for cse.
2214 Blocks should be unique anyways. (Except the successor of start:
2215 is cse with the start block!) */
2216 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2217 n = identify_remember (current_ir_graph->value_table, n);
2223 * Wrapper for external use, set proper status bits after optimization.
2226 optimize_in_place (ir_node *n)
2228 /* Handle graph state */
2229 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2231 if (get_opt_global_cse())
2232 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2233 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2234 set_irg_outs_inconsistent(current_ir_graph);
2236 /* Maybe we could also test whether optimizing the node can
2237 change the control graph. */
2238 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2239 set_irg_dom_inconsistent(current_ir_graph);
2240 return optimize_in_place_2 (n);
2244 * set the default ir op operations
2246 ir_op *firm_set_default_operations(ir_op *op)
2248 op = firm_set_default_computed_value(op);
2249 op = firm_set_default_equivalent_node(op);
2250 op = firm_set_default_transform_node(op);
2251 op = firm_set_default_node_cmp_attr(op);