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);
900 * A Cast may be removed if the type of the previous node
901 * is already to type of the Cast.
903 static ir_node *equivalent_node_Cast(ir_node *n) {
904 ir_node *pred = get_Cast_op(n);
905 if (get_irn_type(pred) == get_Cast_type(n))
910 /* Several optimizations:
911 - no Phi in start block.
912 - remove Id operators that are inputs to Phi
913 - fold Phi-nodes, iff they have only one predecessor except
916 static ir_node *equivalent_node_Phi(ir_node *n)
921 ir_node *block = NULL; /* to shutup gcc */
922 ir_node *first_val = NULL; /* to shutup gcc */
923 ir_node *scnd_val = NULL; /* to shutup gcc */
925 if (!get_opt_normalize()) return n;
927 n_preds = get_Phi_n_preds(n);
929 block = get_nodes_block(n);
930 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
931 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
932 if ((is_Bad(block)) || /* Control dead */
933 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
934 return new_Bad(); /* in the Start Block. */
936 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
939 /* first we test for a special case: */
940 /* Confirm is a special node fixing additional information for a
941 value that is known at a certain point. This is useful for
942 dataflow analysis. */
944 ir_node *a = get_Phi_pred(n, 0);
945 ir_node *b = get_Phi_pred(n, 1);
946 if ( (get_irn_op(a) == op_Confirm)
947 && (get_irn_op(b) == op_Confirm)
948 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
949 && (get_irn_n(a, 1) == get_irn_n (b, 1))
950 && (a->data.num == (~b->data.num & irpn_True) )) {
951 return get_irn_n(a, 0);
956 /* If the Block has a Bad pred, we also have one. */
957 for (i = 0; i < n_preds; ++i)
958 if (is_Bad (get_Block_cfgpred(block, i)))
959 set_Phi_pred(n, i, new_Bad());
961 /* Find first non-self-referencing input */
962 for (i = 0; i < n_preds; ++i) {
963 first_val = get_Phi_pred(n, i);
964 if ( (first_val != n) /* not self pointer */
966 && (get_irn_op(first_val) != op_Bad)
968 ) { /* value not dead */
969 break; /* then found first value. */
973 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
974 if (i >= n_preds) { return new_Bad(); }
978 /* follow_Id () for rest of inputs, determine if any of these
979 are non-self-referencing */
980 while (++i < n_preds) {
981 scnd_val = get_Phi_pred(n, i);
983 && (scnd_val != first_val)
985 && (get_irn_op(scnd_val) != op_Bad)
992 /* Fold, if no multiple distinct non-self-referencing inputs */
995 DBG_OPT_PHI(oldn, first_val, n);
997 /* skip the remaining Ids (done in get_Phi_pred). */
998 /* superfluous, since we walk all to propagate Block's Bads.
999 while (++i < n_preds) get_Phi_pred(n, i); */
1005 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1007 static ir_node *equivalent_node_Proj(ir_node *n)
1011 ir_node *a = get_Proj_pred(n);
1013 if ( get_irn_op(a) == op_Tuple) {
1014 /* Remove the Tuple/Proj combination. */
1015 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1016 n = get_Tuple_pred(a, get_Proj_proj(n));
1017 DBG_OPT_TUPLE(oldn, a, n);
1019 assert(0); /* This should not happen! */
1022 } else if (get_irn_mode(n) == mode_X &&
1023 is_Bad(get_nodes_block(n))) {
1024 /* Remove dead control flow -- early gigo. */
1033 static ir_node *equivalent_node_Id(ir_node *n)
1038 DBG_OPT_ID(oldn, n);
1043 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1044 * perform no actual computation, as, e.g., the Id nodes. It does not create
1045 * new nodes. It is therefore safe to free n if the node returned is not n.
1046 * If a node returns a Tuple we can not just skip it. If the size of the
1047 * in array fits, we transform n into a tuple (e.g., Div).
1050 equivalent_node(ir_node *n)
1052 if (n->op->equivalent_node)
1053 return n->op->equivalent_node(n);
1058 * set the default equivalent node operation
1060 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1064 op->equivalent_node = equivalent_node_##a; \
1091 op->equivalent_node = NULL;
1099 * Do node specific optimizations of nodes predecessors.
1102 optimize_preds(ir_node *n) {
1103 ir_node *a = NULL, *b = NULL;
1105 /* get the operands we will work on for simple cases. */
1107 a = get_binop_left(n);
1108 b = get_binop_right(n);
1109 } else if (is_unop(n)) {
1113 switch (get_irn_opcode(n)) {
1116 /* We don't want Cast as input to Cmp. */
1117 if (get_irn_op(a) == op_Cast) {
1121 if (get_irn_op(b) == op_Cast) {
1123 set_Cmp_right(n, b);
1132 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1133 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1135 static ir_node *transform_node_AddSub(ir_node *n)
1137 ir_mode *mode = get_irn_mode(n);
1139 if (mode_is_reference(mode)) {
1140 ir_node *left = get_binop_left(n);
1141 ir_node *right = get_binop_right(n);
1142 int ref_bits = get_mode_size_bits(mode);
1144 if (get_irn_op(left) == op_Conv) {
1145 ir_mode *mode = get_irn_mode(left);
1146 int bits = get_mode_size_bits(mode);
1148 if (ref_bits == bits &&
1149 mode_is_int(mode) &&
1150 get_mode_arithmetic(mode) == irma_twos_complement) {
1151 ir_node *pre = get_Conv_op(left);
1152 ir_mode *pre_mode = get_irn_mode(pre);
1154 if (mode_is_int(pre_mode) &&
1155 get_mode_size_bits(pre_mode) == bits &&
1156 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1157 /* ok, this conv just changes to sign, moreover the calculation
1158 * is done with same number of bits as our address mode, so
1159 * we can ignore the conv as address calculation can be viewed
1160 * as either signed or unsigned
1162 set_binop_left(n, pre);
1167 if (get_irn_op(right) == op_Conv) {
1168 ir_mode *mode = get_irn_mode(right);
1169 int bits = get_mode_size_bits(mode);
1171 if (ref_bits == bits &&
1172 mode_is_int(mode) &&
1173 get_mode_arithmetic(mode) == irma_twos_complement) {
1174 ir_node *pre = get_Conv_op(right);
1175 ir_mode *pre_mode = get_irn_mode(pre);
1177 if (mode_is_int(pre_mode) &&
1178 get_mode_size_bits(pre_mode) == bits &&
1179 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1180 /* ok, this conv just changes to sign, moreover the calculation
1181 * is done with same number of bits as our address mode, so
1182 * we can ignore the conv as address calculation can be viewed
1183 * as either signed or unsigned
1185 set_binop_right(n, pre);
1193 #define transform_node_Add transform_node_AddSub
1194 #define transform_node_Sub transform_node_AddSub
1196 /** Do architecture dependend optimizations on Mul nodes */
1197 static ir_node *transform_node_Mul(ir_node *n) {
1198 return arch_dep_replace_mul_with_shifts(n);
1201 static ir_node *transform_node_Div(ir_node *n)
1203 tarval *tv = value_of(n);
1206 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1208 if (tv != tarval_bad)
1209 value = new_Const(get_tarval_mode(tv), tv);
1210 else /* Try architecture dependand optimization */
1211 value = arch_dep_replace_div_by_const(n);
1214 /* Turn Div into a tuple (mem, bad, value) */
1215 ir_node *mem = get_Div_mem(n);
1217 turn_into_tuple(n, 3);
1218 set_Tuple_pred(n, pn_Div_M, mem);
1219 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1220 set_Tuple_pred(n, pn_Div_res, value);
1225 static ir_node *transform_node_Mod(ir_node *n)
1227 tarval *tv = value_of(n);
1230 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1232 if (tv != tarval_bad)
1233 value = new_Const(get_tarval_mode(tv), tv);
1234 else /* Try architecture dependand optimization */
1235 value = arch_dep_replace_mod_by_const(n);
1238 /* Turn Mod into a tuple (mem, bad, value) */
1239 ir_node *mem = get_Mod_mem(n);
1241 turn_into_tuple(n, 3);
1242 set_Tuple_pred(n, pn_Mod_M, mem);
1243 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1244 set_Tuple_pred(n, pn_Mod_res, value);
1249 static ir_node *transform_node_DivMod(ir_node *n)
1253 ir_node *a = get_DivMod_left(n);
1254 ir_node *b = get_DivMod_right(n);
1255 ir_mode *mode = get_irn_mode(a);
1256 tarval *ta = value_of(a);
1257 tarval *tb = value_of(b);
1259 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1262 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1264 if (tb != tarval_bad) {
1265 if (tb == get_mode_one(get_tarval_mode(tb))) {
1266 b = new_Const (mode, get_mode_null(mode));
1268 } else if (ta != tarval_bad) {
1269 tarval *resa, *resb;
1270 resa = tarval_div (ta, tb);
1271 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1272 Jmp for X result!? */
1273 resb = tarval_mod (ta, tb);
1274 if (resb == tarval_bad) return n; /* Causes exception! */
1275 a = new_Const (mode, resa);
1276 b = new_Const (mode, resb);
1279 else { /* Try architecture dependand optimization */
1280 arch_dep_replace_divmod_by_const(&a, &b, n);
1281 evaluated = a != NULL;
1283 } else if (ta == get_mode_null(mode)) {
1284 /* 0 / non-Const = 0 */
1289 if (evaluated) { /* replace by tuple */
1290 ir_node *mem = get_DivMod_mem(n);
1291 turn_into_tuple(n, 4);
1292 set_Tuple_pred(n, pn_DivMod_M, mem);
1293 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1294 set_Tuple_pred(n, pn_DivMod_res_div, a);
1295 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1296 assert(get_nodes_block(n));
1302 static ir_node *transform_node_Cond(ir_node *n)
1304 /* Replace the Cond by a Jmp if it branches on a constant
1307 ir_node *a = get_Cond_selector(n);
1308 tarval *ta = value_of(a);
1310 if ((ta != tarval_bad) &&
1311 (get_irn_mode(a) == mode_b) &&
1312 (get_opt_unreachable_code())) {
1313 /* It's a boolean Cond, branching on a boolean constant.
1314 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1315 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1316 turn_into_tuple(n, 2);
1317 if (ta == tarval_b_true) {
1318 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1319 set_Tuple_pred(n, pn_Cond_true, jmp);
1321 set_Tuple_pred(n, pn_Cond_false, jmp);
1322 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1324 /* We might generate an endless loop, so keep it alive. */
1325 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1326 } else if ((ta != tarval_bad) &&
1327 (get_irn_mode(a) == mode_Iu) &&
1328 (get_Cond_kind(n) == dense) &&
1329 (get_opt_unreachable_code())) {
1330 /* I don't want to allow Tuples smaller than the biggest Proj.
1331 Also this tuple might get really big...
1332 I generate the Jmp here, and remember it in link. Link is used
1333 when optimizing Proj. */
1334 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1335 /* We might generate an endless loop, so keep it alive. */
1336 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1337 } else if ((get_irn_op(a) == op_Eor)
1338 && (get_irn_mode(a) == mode_b)
1339 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1340 /* The Eor is a negate. Generate a new Cond without the negate,
1341 simulate the negate by exchanging the results. */
1342 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1344 } else if ((get_irn_op(a) == op_Not)
1345 && (get_irn_mode(a) == mode_b)) {
1346 /* A Not before the Cond. Generate a new Cond without the Not,
1347 simulate the Not by exchanging the results. */
1348 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1357 static ir_node *transform_node_Eor(ir_node *n)
1359 ir_node *a = get_Eor_left(n);
1360 ir_node *b = get_Eor_right(n);
1362 if ((get_irn_mode(n) == mode_b)
1363 && (get_irn_op(a) == op_Proj)
1364 && (get_irn_mode(a) == mode_b)
1365 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1366 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1367 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1368 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1369 mode_b, get_negated_pnc(get_Proj_proj(a)));
1370 else if ((get_irn_mode(n) == mode_b)
1371 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1372 /* The Eor is a Not. Replace it by a Not. */
1373 /* ????!!!Extend to bitfield 1111111. */
1374 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1380 * Transform a boolean Not.
1382 static ir_node *transform_node_Not(ir_node *n)
1384 ir_node *a = get_Not_op(n);
1386 if ( (get_irn_mode(n) == mode_b)
1387 && (get_irn_op(a) == op_Proj)
1388 && (get_irn_mode(a) == mode_b)
1389 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1390 /* We negate a Cmp. The Cmp has the negated result anyways! */
1391 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1392 mode_b, get_negated_pnc(get_Proj_proj(a)));
1398 * Transform a Cast of a Const into a new Const
1400 static ir_node *transform_node_Cast(ir_node *n) {
1401 ir_node *pred = get_Cast_op(n);
1402 type *tp = get_irn_type(pred);
1404 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1405 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1406 get_Const_tarval(pred), tp);
1407 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1408 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1409 get_SymConst_kind(pred), tp);
1415 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1416 * done here instead of equivalent node because it creates new
1418 * Removes the exceptions and routes the memory to the NoMem node.
1420 * Further, it optimizes jump tables by removing all impossible cases.
1422 static ir_node *transform_node_Proj(ir_node *proj)
1424 ir_node *n = get_Proj_pred(proj);
1429 switch (get_irn_opcode(n)) {
1431 b = get_Div_right(n);
1434 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1435 proj_nr = get_Proj_proj(proj);
1437 /* this node may float */
1438 set_irn_pinned(n, op_pin_state_floats);
1440 if (proj_nr == pn_Div_X_except) {
1441 /* we found an exception handler, remove it */
1444 /* the memory Proj can be removed */
1445 ir_node *res = get_Div_mem(n);
1447 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1448 # endif /* defined USE_NOMEM */
1449 if (proj_nr == pn_Div_M)
1455 b = get_Mod_right(n);
1458 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1459 proj_nr = get_Proj_proj(proj);
1461 /* this node may float */
1462 set_irn_pinned(n, op_pin_state_floats);
1464 if (proj_nr == pn_Mod_X_except) {
1465 /* we found an exception handler, remove it */
1468 /* the memory Proj can be removed */
1469 ir_node *res = get_Mod_mem(n);
1471 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1472 # endif /* defined USE_NOMEM */
1473 if (proj_nr == pn_Mod_M)
1479 b = get_DivMod_right(n);
1482 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1483 proj_nr = get_Proj_proj(proj);
1485 /* this node may float */
1486 set_irn_pinned(n, op_pin_state_floats);
1488 if (proj_nr == pn_DivMod_X_except) {
1489 /* we found an exception handler, remove it */
1493 /* the memory Proj can be removed */
1494 ir_node *res = get_DivMod_mem(n);
1496 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1497 # endif /* defined USE_NOMEM */
1498 if (proj_nr == pn_DivMod_M)
1505 if (get_opt_unreachable_code()) {
1506 b = get_Cond_selector(n);
1509 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1510 /* we have a constant switch */
1511 long num = get_Proj_proj(proj);
1513 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1514 if (get_tarval_long(tb) == num) {
1515 /* Do NOT create a jump here, or we will have 2 control flow ops
1516 * in a block. This case is optimized away in optimize_cf(). */
1527 /* should not happen, but if it does will be optimized away */
1535 /* we have added a Tuple, optimize it for the current Proj away */
1536 return equivalent_node_Proj(proj);
1540 * returns the operands of a commutative bin-op, if one operand is
1541 * a const, it is returned as the second one.
1543 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1545 ir_node *op_a = get_binop_left(binop);
1546 ir_node *op_b = get_binop_right(binop);
1548 assert(is_op_commutative(get_irn_op(binop)));
1550 if (get_irn_op(op_a) == op_Const) {
1561 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1562 * Such pattern may arise in bitfield stores.
1564 * value c4 value c4 & c2
1565 * AND c3 AND c1 | c3
1570 static ir_node *transform_node_Or(ir_node *or)
1574 ir_node *and_l, *c3;
1575 ir_node *value, *c4;
1576 ir_node *new_and, *new_const, *block;
1577 ir_mode *mode = get_irn_mode(or);
1579 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1581 get_comm_Binop_Ops(or, &and, &c1);
1582 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1585 get_comm_Binop_Ops(and, &or_l, &c2);
1586 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1589 get_comm_Binop_Ops(or_l, &and_l, &c3);
1590 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1593 get_comm_Binop_Ops(and_l, &value, &c4);
1594 if (get_irn_op(c4) != op_Const)
1597 /* ok, found the pattern, check for conditions */
1598 assert(mode == get_irn_mode(and));
1599 assert(mode == get_irn_mode(or_l));
1600 assert(mode == get_irn_mode(and_l));
1602 tv1 = get_Const_tarval(c1);
1603 tv2 = get_Const_tarval(c2);
1604 tv3 = get_Const_tarval(c3);
1605 tv4 = get_Const_tarval(c4);
1607 tv = tarval_or(tv4, tv2);
1608 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1609 /* have at least one 0 at the same bit position */
1613 n_tv4 = tarval_not(tv4);
1614 if (tv3 != tarval_and(tv3, n_tv4)) {
1615 /* bit in the or_mask is outside the and_mask */
1619 n_tv2 = tarval_not(tv2);
1620 if (tv1 != tarval_and(tv1, n_tv2)) {
1621 /* bit in the or_mask is outside the and_mask */
1625 /* ok, all conditions met */
1626 block = get_nodes_block(or);
1628 new_and = new_r_And(current_ir_graph, block,
1629 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1631 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1633 set_Or_left(or, new_and);
1634 set_Or_right(or, new_const);
1636 /* check for more */
1637 return transform_node_Or(or);
1641 static ir_node *transform_node(ir_node *n);
1644 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1646 static ir_node * transform_node_shift(ir_node *n)
1649 tarval *tv1, *tv2, *res;
1651 int modulo_shf, flag;
1653 left = get_binop_left(n);
1655 /* different operations */
1656 if (get_irn_op(left) != get_irn_op(n))
1659 tv1 = value_of(get_binop_right(n));
1660 if (tv1 == tarval_bad)
1663 tv2 = value_of(get_binop_right(left));
1664 if (tv2 == tarval_bad)
1667 res = tarval_add(tv1, tv2);
1669 /* beware: a simple replacement works only, if res < modulo shift */
1670 mode = get_irn_mode(n);
1674 modulo_shf = get_mode_modulo_shift(mode);
1675 if (modulo_shf > 0) {
1676 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1678 if (tarval_cmp(res, modulo) & Lt)
1685 /* ok, we can replace it */
1686 ir_node *in[2], *irn, *block = get_nodes_block(n);
1688 in[0] = get_binop_left(left);
1689 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1691 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1693 return transform_node(irn);
1700 * Tries several [inplace] [optimizing] transformations and returns an
1701 * equivalent node. The difference to equivalent_node() is that these
1702 * transformations _do_ generate new nodes, and thus the old node must
1703 * not be freed even if the equivalent node isn't the old one.
1705 static ir_node *transform_node(ir_node *n)
1707 if (n->op->transform_node)
1708 n = n->op->transform_node(n);
1713 * set the default transform node operation
1715 static ir_op *firm_set_default_transform_node(ir_op *op)
1719 op->transform_node = transform_node_##a; \
1738 op->transform_node = transform_node_shift;
1741 op->transform_node = NULL;
1749 /* **************** Common Subexpression Elimination **************** */
1751 /** The size of the hash table used, should estimate the number of nodes
1753 #define N_IR_NODES 512
1755 /** Compares the attributes of two Const nodes. */
1756 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1758 return (get_Const_tarval(a) != get_Const_tarval(b))
1759 || (get_Const_type(a) != get_Const_type(b));
1762 /** Compares the attributes of two Proj nodes. */
1763 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1765 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1768 /** Compares the attributes of two Filter nodes. */
1769 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1771 return get_Filter_proj(a) != get_Filter_proj(b);
1774 /** Compares the attributes of two Alloc nodes. */
1775 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1777 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1778 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1781 /** Compares the attributes of two Free nodes. */
1782 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1784 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1787 /** Compares the attributes of two SymConst nodes. */
1788 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1790 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1791 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1792 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1795 /** Compares the attributes of two Call nodes. */
1796 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1798 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1801 /** Compares the attributes of two Sel nodes. */
1802 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1804 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1805 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1806 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1807 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1808 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1811 /** Compares the attributes of two Phi nodes. */
1812 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1814 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1817 /** Compares the attributes of two Cast nodes. */
1818 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1820 return get_Cast_type(a) != get_Cast_type(b);
1823 /** Compares the attributes of two Load nodes. */
1824 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1826 if (get_Load_volatility(a) == volatility_is_volatile ||
1827 get_Load_volatility(b) == volatility_is_volatile)
1828 /* NEVER do CSE on volatile Loads */
1831 return get_Load_mode(a) != get_Load_mode(b);
1834 /** Compares the attributes of two Store nodes. */
1835 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1837 /* NEVER do CSE on volatile Stores */
1838 return (get_Store_volatility(a) == volatility_is_volatile ||
1839 get_Store_volatility(b) == volatility_is_volatile);
1843 * set the default node attribute compare operation
1845 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1849 op->node_cmp_attr = node_cmp_attr_##a; \
1866 op->node_cmp_attr = NULL;
1874 * Compare function for two nodes in the hash table. Gets two
1875 * nodes as parameters. Returns 0 if the nodes are a cse.
1878 vt_cmp (const void *elt, const void *key)
1886 if (a == b) return 0;
1888 if ((get_irn_op(a) != get_irn_op(b)) ||
1889 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1891 /* compare if a's in and b's in are of equal length */
1892 irn_arity_a = get_irn_intra_arity (a);
1893 if (irn_arity_a != get_irn_intra_arity(b))
1896 /* for block-local cse and op_pin_state_pinned nodes: */
1897 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1898 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1902 /* compare a->in[0..ins] with b->in[0..ins] */
1903 for (i = 0; i < irn_arity_a; i++)
1904 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1908 * here, we already now that the nodes are identical except their
1911 if (a->op->node_cmp_attr)
1912 return a->op->node_cmp_attr(a, b);
1917 #define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3)
1920 * Calculate a hash value of a node.
1923 ir_node_hash (ir_node *node)
1928 if (node->op == op_Const) {
1929 /* special value for const, as they only differ in their tarval. */
1930 h = ADDR_TO_VAL(node->attr.con.tv);
1931 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1932 } else if (node->op == op_SymConst) {
1933 /* special value for const, as they only differ in their symbol. */
1934 h = ADDR_TO_VAL(node->attr.i.sym.type_p);
1935 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1938 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1939 h = irn_arity = get_irn_intra_arity(node);
1941 /* consider all in nodes... except the block if not a control flow. */
1942 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1943 h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i));
1947 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1949 h = 9*h + ADDR_TO_VAL(get_irn_op(node));
1956 new_identities(void) {
1957 return new_pset(vt_cmp, N_IR_NODES);
1961 del_identities(pset *value_table) {
1962 del_pset(value_table);
1966 * Return the canonical node computing the same value as n.
1967 * Looks up the node in a hash table.
1969 * For Const nodes this is performed in the constructor, too. Const
1970 * nodes are extremely time critical because of their frequent use in
1971 * constant string arrays.
1973 static INLINE ir_node *
1974 identify (pset *value_table, ir_node *n)
1978 if (!value_table) return n;
1980 if (get_opt_reassociation()) {
1981 if (is_op_commutative(get_irn_op(n))) {
1982 ir_node *l = get_binop_left(n);
1983 ir_node *r = get_binop_right(n);
1985 /* for commutative operators perform a OP b == b OP a */
1987 set_binop_left(n, r);
1988 set_binop_right(n, l);
1993 o = pset_find (value_table, n, ir_node_hash (n));
2002 * During construction we set the op_pin_state_pinned flag in the graph right when the
2003 * optimization is performed. The flag turning on procedure global cse could
2004 * be changed between two allocations. This way we are safe.
2006 static INLINE ir_node *
2007 identify_cons (pset *value_table, ir_node *n) {
2010 n = identify(value_table, n);
2011 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2012 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2017 * Return the canonical node computing the same value as n.
2018 * Looks up the node in a hash table, enters it in the table
2019 * if it isn't there yet.
2022 identify_remember (pset *value_table, ir_node *n)
2026 if (!value_table) return n;
2028 if (get_opt_reassociation()) {
2029 if (is_op_commutative(get_irn_op(n))) {
2030 ir_node *l = get_binop_left(n);
2031 ir_node *r = get_binop_right(n);
2033 /* for commutative operators perform a OP b == b OP a */
2035 set_binop_left(n, r);
2036 set_binop_right(n, l);
2041 /* lookup or insert in hash table with given hash key. */
2042 o = pset_insert (value_table, n, ir_node_hash (n));
2052 add_identities (pset *value_table, ir_node *node) {
2053 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2054 identify_remember (value_table, node);
2058 * garbage in, garbage out. If a node has a dead input, i.e., the
2059 * Bad node is input to the node, return the Bad node.
2061 static INLINE ir_node *
2062 gigo (ir_node *node)
2065 ir_op* op = get_irn_op(node);
2067 /* remove garbage blocks by looking at control flow that leaves the block
2068 and replacing the control flow by Bad. */
2069 if (get_irn_mode(node) == mode_X) {
2070 ir_node *block = get_nodes_block(node);
2071 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2072 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2073 irn_arity = get_irn_arity(block);
2074 for (i = 0; i < irn_arity; i++) {
2075 if (!is_Bad(get_irn_n(block, i))) break;
2077 if (i == irn_arity) return new_Bad();
2081 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2082 blocks predecessors is dead. */
2083 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2084 irn_arity = get_irn_arity(node);
2085 for (i = -1; i < irn_arity; i++) {
2086 if (is_Bad(get_irn_n(node, i))) {
2092 /* With this code we violate the agreement that local_optimize
2093 only leaves Bads in Block, Phi and Tuple nodes. */
2094 /* If Block has only Bads as predecessors it's garbage. */
2095 /* If Phi has only Bads as predecessors it's garbage. */
2096 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2097 irn_arity = get_irn_arity(node);
2098 for (i = 0; i < irn_arity; i++) {
2099 if (!is_Bad(get_irn_n(node, i))) break;
2101 if (i == irn_arity) node = new_Bad();
2109 * These optimizations deallocate nodes from the obstack.
2110 * It can only be called if it is guaranteed that no other nodes
2111 * reference this one, i.e., right after construction of a node.
2114 optimize_node (ir_node *n)
2118 opcode iro = get_irn_opcode(n);
2120 type *old_tp = get_irn_type(n);
2122 int i, arity = get_irn_arity(n);
2123 for (i = 0; i < arity && !old_tp; ++i)
2124 old_tp = get_irn_type(get_irn_n(n, i));
2127 /* Allways optimize Phi nodes: part of the construction. */
2128 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2130 /* constant expression evaluation / constant folding */
2131 if (get_opt_constant_folding()) {
2132 /* constants can not be evaluated */
2133 if (iro != iro_Const) {
2134 /* try to evaluate */
2135 tv = computed_value(n);
2136 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2138 * we MUST copy the node here temporary, because it's still needed
2139 * for DBG_OPT_CSTEVAL
2141 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2142 oldn = alloca(node_size);
2144 memcpy(oldn, n, node_size);
2145 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2147 /* ARG, copy the in array, we need it for statistics */
2148 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2150 /* evaluation was successful -- replace the node. */
2151 obstack_free (current_ir_graph->obst, n);
2152 n = new_Const (get_tarval_mode (tv), tv);
2153 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2154 set_Const_type(n, old_tp);
2155 DBG_OPT_CSTEVAL(oldn, n);
2161 /* remove unnecessary nodes */
2162 if (get_opt_constant_folding() ||
2163 (iro == iro_Phi) || /* always optimize these nodes. */
2165 (iro == iro_Proj) ||
2166 (iro == iro_Block) ) /* Flags tested local. */
2167 n = equivalent_node (n);
2169 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2171 /** common subexpression elimination **/
2172 /* Checks whether n is already available. */
2173 /* The block input is used to distinguish different subexpressions. Right
2174 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2175 subexpressions within a block. */
2177 n = identify_cons (current_ir_graph->value_table, n);
2180 /* We found an existing, better node, so we can deallocate the old node. */
2181 obstack_free (current_ir_graph->obst, oldn);
2186 /* Some more constant expression evaluation that does not allow to
2188 iro = get_irn_opcode(n);
2189 if (get_opt_constant_folding() ||
2190 (iro == iro_Cond) ||
2191 (iro == iro_Proj)) /* Flags tested local. */
2192 n = transform_node (n);
2194 /* Remove nodes with dead (Bad) input.
2195 Run always for transformation induced Bads. */
2198 /* Now we have a legal, useful node. Enter it in hash table for cse */
2199 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2200 n = identify_remember (current_ir_graph->value_table, n);
2208 * These optimizations never deallocate nodes. This can cause dead
2209 * nodes lying on the obstack. Remove these by a dead node elimination,
2210 * i.e., a copying garbage collection.
2213 optimize_in_place_2 (ir_node *n)
2217 opcode iro = get_irn_opcode(n);
2219 type *old_tp = get_irn_type(n);
2221 int i, arity = get_irn_arity(n);
2222 for (i = 0; i < arity && !old_tp; ++i)
2223 old_tp = get_irn_type(get_irn_n(n, i));
2226 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2228 /* if not optimize return n */
2231 /* Here this is possible. Why? */
2235 /* constant expression evaluation / constant folding */
2236 if (get_opt_constant_folding()) {
2237 /* constants can not be evaluated */
2238 if (iro != iro_Const) {
2239 /* try to evaluate */
2240 tv = computed_value(n);
2241 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2242 /* evaluation was successful -- replace the node. */
2243 n = new_Const (get_tarval_mode (tv), tv);
2245 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2246 set_Const_type(n, old_tp);
2248 DBG_OPT_CSTEVAL(oldn, n);
2254 /* remove unnecessary nodes */
2255 if (get_opt_constant_folding() ||
2256 (iro == iro_Phi) || /* always optimize these nodes. */
2257 (iro == iro_Id) || /* ... */
2258 (iro == iro_Proj) || /* ... */
2259 (iro == iro_Block) ) /* Flags tested local. */
2260 n = equivalent_node (n);
2262 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2264 /** common subexpression elimination **/
2265 /* Checks whether n is already available. */
2266 /* The block input is used to distinguish different subexpressions. Right
2267 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2268 subexpressions within a block. */
2269 if (get_opt_cse()) {
2270 n = identify (current_ir_graph->value_table, n);
2273 /* Some more constant expression evaluation. */
2274 iro = get_irn_opcode(n);
2275 if (get_opt_constant_folding() ||
2276 (iro == iro_Cond) ||
2277 (iro == iro_Proj)) /* Flags tested local. */
2278 n = transform_node (n);
2280 /* Remove nodes with dead (Bad) input.
2281 Run always for transformation induced Bads. */
2284 /* Now we can verify the node, as it has no dead inputs any more. */
2287 /* Now we have a legal, useful node. Enter it in hash table for cse.
2288 Blocks should be unique anyways. (Except the successor of start:
2289 is cse with the start block!) */
2290 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2291 n = identify_remember (current_ir_graph->value_table, n);
2297 * Wrapper for external use, set proper status bits after optimization.
2300 optimize_in_place (ir_node *n)
2302 /* Handle graph state */
2303 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2305 if (get_opt_global_cse())
2306 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2307 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2308 set_irg_outs_inconsistent(current_ir_graph);
2310 /* Maybe we could also test whether optimizing the node can
2311 change the control graph. */
2312 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2313 set_irg_dom_inconsistent(current_ir_graph);
2314 return optimize_in_place_2 (n);
2318 * set the default ir op operations
2320 ir_op *firm_set_default_operations(ir_op *op)
2322 op = firm_set_default_computed_value(op);
2323 op = firm_set_default_equivalent_node(op);
2324 op = firm_set_default_transform_node(op);
2325 op = firm_set_default_node_cmp_attr(op);