3 * File name: ir/ir/iropt.c
4 * Purpose: iropt --- optimizations intertwined with IR construction.
5 * Author: Christian Schaefer
6 * Modified by: Goetz Lindenmaier
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 # include "irnode_t.h"
18 # include "irgraph_t.h"
19 # include "irmode_t.h"
21 # include "ircons_t.h"
25 # include "dbginfo_t.h"
26 # include "iropt_dbg.h"
27 # include "irflag_t.h"
28 # include "firmstat.h"
31 /* Make types visible to allow most efficient access */
32 # include "entity_t.h"
35 * Trivial INLINEable routine for copy propagation.
36 * Does follow Ids, needed to optimize INLINEd code.
38 static INLINE ir_node *
39 follow_Id (ir_node *n)
41 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
46 * return the value of a Constant
48 static tarval *computed_value_Const(ir_node *n)
50 return get_Const_tarval(n);
54 * return the value of a 'sizeof' SymConst
56 static tarval *computed_value_SymConst(ir_node *n)
58 if ((get_SymConst_kind(n) == symconst_size) &&
59 (get_type_state(get_SymConst_type(n))) == layout_fixed)
60 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
65 * return the value of an Add
67 static tarval *computed_value_Add(ir_node *n)
69 ir_node *a = get_Add_left(n);
70 ir_node *b = get_Add_right(n);
72 tarval *ta = value_of(a);
73 tarval *tb = value_of(b);
75 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
76 return tarval_add(ta, tb);
82 * return the value of a Sub
85 static tarval *computed_value_Sub(ir_node *n)
87 ir_node *a = get_Sub_left(n);
88 ir_node *b = get_Sub_right(n);
94 return get_tarval_null(get_irn_mode(n));
99 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
100 return tarval_sub(ta, tb);
106 * return the value of an unary Minus
108 static tarval *computed_value_Minus(ir_node *n)
110 ir_node *a = get_Minus_op(n);
111 tarval *ta = value_of(a);
113 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
114 return tarval_neg(ta);
120 * return the value of a Mul
122 static tarval *computed_value_Mul(ir_node *n)
124 ir_node *a = get_Mul_left(n);
125 ir_node *b = get_Mul_right(n);
127 tarval *ta = value_of(a);
128 tarval *tb = value_of(b);
130 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
131 return tarval_mul(ta, tb);
133 /* a*0 = 0 or 0*b = 0:
134 calls computed_value recursive and returns the 0 with proper
136 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
138 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
145 * return the value of a floating point Quot
147 static tarval *computed_value_Quot(ir_node *n)
149 ir_node *a = get_Quot_left(n);
150 ir_node *b = get_Quot_right(n);
152 tarval *ta = value_of(a);
153 tarval *tb = value_of(b);
155 /* This was missing in original implementation. Why? */
156 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
157 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
158 return tarval_quo(ta, tb);
164 * calculate the value of an integer Div of two nodes
165 * Special case: 0 / b
167 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
169 tarval *ta = value_of(a);
170 tarval *tb = value_of(b);
172 /* Compute c1 / c2 or 0 / a, a != 0 */
173 if (ta != tarval_bad) {
174 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
175 return tarval_div(ta, tb);
176 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
183 * return the value of an integer Div
185 static tarval *computed_value_Div(ir_node *n)
187 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
191 * calculate the value of an integer Mod of two nodes
192 * Special case: a % 1
194 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
196 tarval *ta = value_of(a);
197 tarval *tb = value_of(b);
199 /* Compute c1 % c2 or a % 1 */
200 if (tb != tarval_bad) {
201 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
202 return tarval_mod(ta, tb);
203 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
204 return get_mode_null(get_irn_mode(a));
211 * return the value of an integer Mod
213 static tarval *computed_value_Mod(ir_node *n)
215 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
219 * return the value of an Abs
221 static tarval *computed_value_Abs(ir_node *n)
223 ir_node *a = get_Abs_op(n);
224 tarval *ta = value_of(a);
226 if (ta != tarval_bad)
227 return tarval_abs(ta);
233 * return the value of an And
234 * Special case: a & 0, 0 & b
236 static tarval *computed_value_And(ir_node *n)
238 ir_node *a = get_And_left(n);
239 ir_node *b = get_And_right(n);
241 tarval *ta = value_of(a);
242 tarval *tb = value_of(b);
244 if ((ta != tarval_bad) && (tb != tarval_bad)) {
245 return tarval_and (ta, tb);
249 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
250 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
258 * return the value of an Or
259 * Special case: a | 1...1, 1...1 | b
261 static tarval *computed_value_Or(ir_node *n)
263 ir_node *a = get_Or_left(n);
264 ir_node *b = get_Or_right(n);
266 tarval *ta = value_of(a);
267 tarval *tb = value_of(b);
269 if ((ta != tarval_bad) && (tb != tarval_bad)) {
270 return tarval_or (ta, tb);
273 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
274 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
282 * return the value of an Eor
284 static tarval *computed_value_Eor(ir_node *n)
286 ir_node *a = get_Eor_left(n);
287 ir_node *b = get_Eor_right(n);
289 tarval *ta = value_of(a);
290 tarval *tb = value_of(b);
292 if ((ta != tarval_bad) && (tb != tarval_bad)) {
293 return tarval_eor (ta, tb);
299 * return the value of a Not
301 static tarval *computed_value_Not(ir_node *n)
303 ir_node *a = get_Not_op(n);
304 tarval *ta = value_of(a);
306 if (ta != tarval_bad)
307 return tarval_not(ta);
313 * return the value of a Shl
315 static tarval *computed_value_Shl(ir_node *n)
317 ir_node *a = get_Shl_left(n);
318 ir_node *b = get_Shl_right(n);
320 tarval *ta = value_of(a);
321 tarval *tb = value_of(b);
323 if ((ta != tarval_bad) && (tb != tarval_bad)) {
324 return tarval_shl (ta, tb);
330 * return the value of a Shr
332 static tarval *computed_value_Shr(ir_node *n)
334 ir_node *a = get_Shr_left(n);
335 ir_node *b = get_Shr_right(n);
337 tarval *ta = value_of(a);
338 tarval *tb = value_of(b);
340 if ((ta != tarval_bad) && (tb != tarval_bad)) {
341 return tarval_shr (ta, tb);
347 * return the value of a Shrs
349 static tarval *computed_value_Shrs(ir_node *n)
351 ir_node *a = get_Shrs_left(n);
352 ir_node *b = get_Shrs_right(n);
354 tarval *ta = value_of(a);
355 tarval *tb = value_of(b);
357 if ((ta != tarval_bad) && (tb != tarval_bad)) {
358 return tarval_shrs (ta, tb);
364 * return the value of a Rot
366 static tarval *computed_value_Rot(ir_node *n)
368 ir_node *a = get_Rot_left(n);
369 ir_node *b = get_Rot_right(n);
371 tarval *ta = value_of(a);
372 tarval *tb = value_of(b);
374 if ((ta != tarval_bad) && (tb != tarval_bad)) {
375 return tarval_rot (ta, tb);
381 * return the value of a Conv
383 static tarval *computed_value_Conv(ir_node *n)
385 ir_node *a = get_Conv_op(n);
386 tarval *ta = value_of(a);
388 if (ta != tarval_bad)
389 return tarval_convert_to(ta, get_irn_mode(n));
395 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
397 static tarval *computed_value_Proj(ir_node *n)
399 ir_node *a = get_Proj_pred(n);
403 /* Optimize Cmp nodes.
404 This performs a first step of unreachable code elimination.
405 Proj can not be computed, but folding a Cmp above the Proj here is
406 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
408 There are several case where we can evaluate a Cmp node:
409 1. The nodes compared are both the same. If we compare for
410 equal, greater equal, ... this will return true, else it
411 will return false. This step relies on cse.
412 2. The predecessors of Cmp are target values. We can evaluate
414 3. The predecessors are Allocs or void* constants. Allocs never
415 return NULL, they raise an exception. Therefore we can predict
417 switch (get_irn_opcode(a)) {
419 aa = get_Cmp_left(a);
420 ab = get_Cmp_right(a);
421 proj_nr = get_Proj_proj(n);
423 if (aa == ab) { /* 1.: */
424 /* This is a trick with the bits used for encoding the Cmp
425 Proj numbers, the following statement is not the same:
426 return new_tarval_from_long (proj_nr == Eq, mode_b) */
427 return new_tarval_from_long (proj_nr & Eq, mode_b);
429 tarval *taa = value_of(aa);
430 tarval *tab = value_of(ab);
432 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
433 /* strange checks... */
434 pnc_number flags = tarval_cmp (taa, tab);
435 if (flags != False) {
436 return new_tarval_from_long (proj_nr & flags, mode_b);
438 } else { /* check for 3.: */
439 ir_node *aaa = skip_Id(skip_Proj(aa));
440 ir_node *aba = skip_Id(skip_Proj(ab));
442 if ( ( (/* aa is ProjP and aaa is Alloc */
443 (get_irn_op(aa) == op_Proj)
444 && (mode_is_reference(get_irn_mode(aa)))
445 && (get_irn_op(aaa) == op_Alloc))
446 && ( (/* ab is constant void */
447 (get_irn_op(ab) == op_Const)
448 && (mode_is_reference(get_irn_mode(ab)))
449 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
450 || (/* ab is other Alloc */
451 (get_irn_op(ab) == op_Proj)
452 && (mode_is_reference(get_irn_mode(ab)))
453 && (get_irn_op(aba) == op_Alloc)
455 || (/* aa is void and aba is Alloc */
456 (get_irn_op(aa) == op_Const)
457 && (mode_is_reference(get_irn_mode(aa)))
458 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
459 && (get_irn_op(ab) == op_Proj)
460 && (mode_is_reference(get_irn_mode(ab)))
461 && (get_irn_op(aba) == op_Alloc)))
463 return new_tarval_from_long (proj_nr & Ne, mode_b);
469 /* compute either the Div or the Mod part */
470 proj_nr = get_Proj_proj(n);
471 if (proj_nr == pn_DivMod_res_div)
472 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
473 else if (proj_nr == pn_DivMod_res_mod)
474 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
478 if (get_Proj_proj(n) == pn_Div_res)
479 return computed_value(a);
483 if (get_Proj_proj(n) == pn_Mod_res)
484 return computed_value(a);
494 * If the parameter n can be computed, return its value, else tarval_bad.
495 * Performs constant folding.
497 * @param n The node this should be evaluated
499 tarval *computed_value(ir_node *n)
501 if (n->op->computed_value)
502 return n->op->computed_value(n);
507 * set the default computed_value evaluator
509 static ir_op *firm_set_default_computed_value(ir_op *op)
513 op->computed_value = computed_value_##a; \
538 op->computed_value = NULL;
546 /* returns 1 if the a and b are pointers to different locations. */
548 different_identity (ir_node *a, ir_node *b)
550 assert (mode_is_reference(get_irn_mode (a))
551 && mode_is_reference(get_irn_mode (b)));
553 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
554 ir_node *a1 = get_Proj_pred (a);
555 ir_node *b1 = get_Proj_pred (b);
556 if (a1 != b1 && get_irn_op (a1) == op_Alloc
557 && get_irn_op (b1) == op_Alloc)
564 static ir_node *equivalent_node_Block(ir_node *n)
568 /* The Block constructor does not call optimize, but mature_immBlock
569 calls the optimization. */
570 assert(get_Block_matured(n));
572 /* Straightening: a single entry Block following a single exit Block
573 can be merged, if it is not the Start block. */
574 /* !!! Beware, all Phi-nodes of n must have been optimized away.
575 This should be true, as the block is matured before optimize is called.
576 But what about Phi-cycles with the Phi0/Id that could not be resolved?
577 Remaining Phi nodes are just Ids. */
578 if ((get_Block_n_cfgpreds(n) == 1) &&
579 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
580 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
581 if (predblock == oldn) {
582 /* Jmp jumps into the block it is in -- deal self cycle. */
584 DBG_OPT_DEAD(oldn, n);
585 } else if (get_opt_control_flow_straightening()) {
587 DBG_OPT_STG(oldn, n);
590 else if ((get_Block_n_cfgpreds(n) == 1) &&
591 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
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);
599 else if ((get_Block_n_cfgpreds(n) == 2) &&
600 (get_opt_control_flow_weak_simplification())) {
601 /* Test whether Cond jumps twice to this block
602 @@@ we could do this also with two loops finding two preds from several ones. */
603 ir_node *a = get_Block_cfgpred(n, 0);
604 ir_node *b = get_Block_cfgpred(n, 1);
606 if ((get_irn_op(a) == op_Proj) &&
607 (get_irn_op(b) == op_Proj) &&
608 (get_Proj_pred(a) == get_Proj_pred(b)) &&
609 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
610 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
611 /* Also a single entry Block following a single exit Block. Phis have
612 twice the same operand and will be optimized away. */
613 n = get_nodes_block(a);
614 DBG_OPT_IFSIM(oldn, a, b, n);
616 } else if (get_opt_unreachable_code() &&
617 (n != current_ir_graph->start_block) &&
618 (n != current_ir_graph->end_block) ) {
620 /* If all inputs are dead, this block is dead too, except if it is
621 the start or end block. This is a step of unreachable code
623 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
624 if (!is_Bad(get_Block_cfgpred(n, i))) break;
626 if (i == get_Block_n_cfgpreds(n))
634 * Returns a equivalent node for a Jmp, a Bad :-)
635 * Of course this only happens if the Block of the Jmp is Bad.
637 static ir_node *equivalent_node_Jmp(ir_node *n)
639 /* GL: Why not same for op_Raise?? */
640 /* unreachable code elimination */
641 if (is_Bad(get_nodes_block(n)))
647 static ir_node *equivalent_node_Cond(ir_node *n)
649 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
650 See cases for iro_Cond and iro_Proj in transform_node. */
655 * Use algebraic simplification a v a = a.
657 static ir_node *equivalent_node_Or(ir_node *n)
661 ir_node *a = get_Or_left(n);
662 ir_node *b = get_Or_right(n);
668 DBG_OPT_ALGSIM1(oldn, a, b, n);
675 * optimize operations that are commutative and have neutral 0,
676 * so a op 0 = 0 op a = a.
678 static ir_node *equivalent_node_neutral_zero(ir_node *n)
682 ir_node *a = get_binop_left(n);
683 ir_node *b = get_binop_right(n);
688 /* After running compute_node there is only one constant predecessor.
689 Find this predecessors value and remember the other node: */
690 if ((tv = value_of(a)) != tarval_bad) {
692 } else if ((tv = value_of(b)) != tarval_bad) {
697 /* If this predecessors constant value is zero, the operation is
698 unnecessary. Remove it: */
699 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
702 DBG_OPT_ALGSIM1(oldn, a, b, n);
708 #define equivalent_node_Add equivalent_node_neutral_zero
709 #define equivalent_node_Eor equivalent_node_neutral_zero
712 * optimize operations that are not commutative but have neutral 0 on left,
715 static ir_node *equivalent_node_left_zero(ir_node *n)
719 ir_node *a = get_binop_left(n);
720 ir_node *b = get_binop_right(n);
722 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
725 DBG_OPT_ALGSIM1(oldn, a, b, n);
731 #define equivalent_node_Sub equivalent_node_left_zero
732 #define equivalent_node_Shl equivalent_node_left_zero
733 #define equivalent_node_Shr equivalent_node_left_zero
734 #define equivalent_node_Shrs equivalent_node_left_zero
735 #define equivalent_node_Rot equivalent_node_left_zero
738 * Er, a "symmetic unop", ie op(op(n)) = n.
740 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
743 ir_node *pred = get_unop_op(n);
745 /* optimize symmetric unop */
746 if (get_irn_op(pred) == get_irn_op(n)) {
747 n = get_unop_op(pred);
748 DBG_OPT_ALGSIM2(oldn, pred, n);
754 #define equivalent_node_Not equivalent_node_symmetric_unop
756 /* --x == x */ /* ??? Is this possible or can --x raise an
757 out of bounds exception if min =! max? */
758 #define equivalent_node_Minus equivalent_node_symmetric_unop
761 * Optimize a * 1 = 1 * a = a.
763 static ir_node *equivalent_node_Mul(ir_node *n)
767 ir_node *a = get_Mul_left(n);
768 ir_node *b = get_Mul_right(n);
770 /* Mul is commutative and has again an other neutral element. */
771 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
773 DBG_OPT_ALGSIM1(oldn, a, b, n);
774 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
776 DBG_OPT_ALGSIM1(oldn, a, b, n);
782 * Optimize a / 1 = a.
784 static ir_node *equivalent_node_Div(ir_node *n)
786 ir_node *a = get_Div_left(n);
787 ir_node *b = get_Div_right(n);
789 /* Div is not commutative. */
790 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
791 /* Turn Div into a tuple (mem, bad, a) */
792 ir_node *mem = get_Div_mem(n);
793 turn_into_tuple(n, 3);
794 set_Tuple_pred(n, pn_Div_M, mem);
795 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
796 set_Tuple_pred(n, pn_Div_res, a);
802 * Optimize a / 1 = a.
804 static ir_node *equivalent_node_DivMod(ir_node *n)
806 ir_node *a = get_DivMod_left(n);
807 ir_node *b = get_DivMod_right(n);
809 /* Div is not commutative. */
810 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
811 /* Turn DivMod into a tuple (mem, bad, a, 0) */
812 ir_node *mem = get_Div_mem(n);
813 ir_mode *mode = get_irn_mode(b);
815 turn_into_tuple(n, 4);
816 set_Tuple_pred(n, pn_DivMod_M, mem);
817 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
818 set_Tuple_pred(n, pn_DivMod_res_div, a);
819 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
825 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
827 static ir_node *equivalent_node_And(ir_node *n)
831 ir_node *a = get_And_left(n);
832 ir_node *b = get_And_right(n);
835 n = a; /* And has it's own neutral element */
836 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
838 DBG_OPT_ALGSIM1(oldn, a, b, n);
839 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
841 DBG_OPT_ALGSIM1(oldn, a, b, n);
847 * Try to remove useless conv's:
849 static ir_node *equivalent_node_Conv(ir_node *n)
852 ir_node *a = get_Conv_op(n);
855 ir_mode *n_mode = get_irn_mode(n);
856 ir_mode *a_mode = get_irn_mode(a);
858 if (n_mode == a_mode) { /* No Conv necessary */
860 DBG_OPT_ALGSIM3(oldn, a, n);
861 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
865 n_mode = get_irn_mode(n);
866 b_mode = get_irn_mode(b);
868 if (n_mode == b_mode) {
869 if (n_mode == mode_b) {
870 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
871 DBG_OPT_ALGSIM1(oldn, a, b, n);
873 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
874 if (smaller_mode(b_mode, a_mode)){
875 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
876 DBG_OPT_ALGSIM1(oldn, a, b, n);
884 static ir_node *equivalent_node_Cast(ir_node *n) {
885 ir_node *pred = get_Cast_op(n);
886 if (get_irn_type(pred) == get_Cast_type(n))
891 static ir_node *equivalent_node_Phi(ir_node *n)
893 /* Several optimizations:
894 - no Phi in start block.
895 - remove Id operators that are inputs to Phi
896 - fold Phi-nodes, iff they have only one predecessor except
902 ir_node *block = NULL; /* to shutup gcc */
903 ir_node *first_val = NULL; /* to shutup gcc */
904 ir_node *scnd_val = NULL; /* to shutup gcc */
906 if (!get_opt_normalize()) return n;
908 n_preds = get_Phi_n_preds(n);
910 block = get_nodes_block(n);
911 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
912 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
913 if ((is_Bad(block)) || /* Control dead */
914 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
915 return new_Bad(); /* in the Start Block. */
917 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
920 /* first we test for a special case: */
921 /* Confirm is a special node fixing additional information for a
922 value that is known at a certain point. This is useful for
923 dataflow analysis. */
925 ir_node *a = get_Phi_pred(n, 0);
926 ir_node *b = get_Phi_pred(n, 1);
927 if ( (get_irn_op(a) == op_Confirm)
928 && (get_irn_op(b) == op_Confirm)
929 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
930 && (get_irn_n(a, 1) == get_irn_n (b, 1))
931 && (a->data.num == (~b->data.num & irpn_True) )) {
932 return get_irn_n(a, 0);
937 /* If the Block has a Bad pred, we also have one. */
938 for (i = 0; i < n_preds; ++i)
939 if (is_Bad (get_Block_cfgpred(block, i)))
940 set_Phi_pred(n, i, new_Bad());
942 /* Find first non-self-referencing input */
943 for (i = 0; i < n_preds; ++i) {
944 first_val = get_Phi_pred(n, i);
945 if ( (first_val != n) /* not self pointer */
947 && (get_irn_op(first_val) != op_Bad)
949 ) { /* value not dead */
950 break; /* then found first value. */
954 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
955 if (i >= n_preds) { return new_Bad(); }
959 /* follow_Id () for rest of inputs, determine if any of these
960 are non-self-referencing */
961 while (++i < n_preds) {
962 scnd_val = get_Phi_pred(n, i);
964 && (scnd_val != first_val)
966 && (get_irn_op(scnd_val) != op_Bad)
973 /* Fold, if no multiple distinct non-self-referencing inputs */
976 DBG_OPT_PHI(oldn, first_val, n);
978 /* skip the remaining Ids (done in get_Phi_pred). */
979 /* superfluous, since we walk all to propagate Block's Bads.
980 while (++i < n_preds) get_Phi_pred(n, i); */
986 * optimize Proj(Tuple) and gigo for ProjX in Bad block
988 static ir_node *equivalent_node_Proj(ir_node *n)
992 ir_node *a = get_Proj_pred(n);
994 if ( get_irn_op(a) == op_Tuple) {
995 /* Remove the Tuple/Proj combination. */
996 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
997 n = get_Tuple_pred(a, get_Proj_proj(n));
998 DBG_OPT_TUPLE(oldn, a, n);
1000 assert(0); /* This should not happen! */
1003 } else if (get_irn_mode(n) == mode_X &&
1004 is_Bad(get_nodes_block(n))) {
1005 /* Remove dead control flow -- early gigo. */
1014 static ir_node *equivalent_node_Id(ir_node *n)
1019 DBG_OPT_ID(oldn, n);
1024 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1025 * perform no actual computation, as, e.g., the Id nodes. It does not create
1026 * new nodes. It is therefore safe to free n if the node returned is not n.
1027 * If a node returns a Tuple we can not just skip it. If the size of the
1028 * in array fits, we transform n into a tuple (e.g., Div).
1031 equivalent_node(ir_node *n)
1033 if (n->op->equivalent_node)
1034 return n->op->equivalent_node(n);
1039 * set the default equivalent node operation
1041 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1045 op->equivalent_node = equivalent_node_##a; \
1072 op->equivalent_node = NULL;
1080 * Do node specific optimizations of nodes predecessors.
1083 optimize_preds(ir_node *n) {
1084 ir_node *a = NULL, *b = NULL;
1086 /* get the operands we will work on for simple cases. */
1088 a = get_binop_left(n);
1089 b = get_binop_right(n);
1090 } else if (is_unop(n)) {
1094 switch (get_irn_opcode(n)) {
1097 /* We don't want Cast as input to Cmp. */
1098 if (get_irn_op(a) == op_Cast) {
1102 if (get_irn_op(b) == op_Cast) {
1104 set_Cmp_right(n, b);
1112 /** Do architecture dependend optimizations on Mul nodes */
1113 static ir_node *transform_node_Mul(ir_node *n) {
1114 return arch_dep_replace_mul_with_shifts(n);
1117 static ir_node *transform_node_Div(ir_node *n)
1119 tarval *tv = value_of(n);
1122 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1124 if (tv != tarval_bad)
1125 value = new_Const(get_tarval_mode(tv), tv);
1126 else /* Try architecture dependand optimization */
1127 value = arch_dep_replace_div_by_const(n);
1130 /* Turn Div into a tuple (mem, bad, value) */
1131 ir_node *mem = get_Div_mem(n);
1133 turn_into_tuple(n, 3);
1134 set_Tuple_pred(n, pn_Div_M, mem);
1135 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1136 set_Tuple_pred(n, pn_Div_res, value);
1141 static ir_node *transform_node_Mod(ir_node *n)
1143 tarval *tv = value_of(n);
1146 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1148 if (tv != tarval_bad)
1149 value = new_Const(get_tarval_mode(tv), tv);
1150 else /* Try architecture dependand optimization */
1151 value = arch_dep_replace_mod_by_const(n);
1154 /* Turn Mod into a tuple (mem, bad, value) */
1155 ir_node *mem = get_Mod_mem(n);
1157 turn_into_tuple(n, 3);
1158 set_Tuple_pred(n, pn_Mod_M, mem);
1159 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1160 set_Tuple_pred(n, pn_Mod_res, value);
1165 static ir_node *transform_node_DivMod(ir_node *n)
1169 ir_node *a = get_DivMod_left(n);
1170 ir_node *b = get_DivMod_right(n);
1171 ir_mode *mode = get_irn_mode(a);
1172 tarval *ta = value_of(a);
1173 tarval *tb = value_of(b);
1175 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1178 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1180 if (tb != tarval_bad) {
1181 if (tb == get_mode_one(get_tarval_mode(tb))) {
1182 b = new_Const (mode, get_mode_null(mode));
1184 } else if (ta != tarval_bad) {
1185 tarval *resa, *resb;
1186 resa = tarval_div (ta, tb);
1187 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1188 Jmp for X result!? */
1189 resb = tarval_mod (ta, tb);
1190 if (resb == tarval_bad) return n; /* Causes exception! */
1191 a = new_Const (mode, resa);
1192 b = new_Const (mode, resb);
1195 else { /* Try architecture dependand optimization */
1196 arch_dep_replace_divmod_by_const(&a, &b, n);
1197 evaluated = a != NULL;
1199 } else if (ta == get_mode_null(mode)) {
1200 /* 0 / non-Const = 0 */
1205 if (evaluated) { /* replace by tuple */
1206 ir_node *mem = get_DivMod_mem(n);
1207 turn_into_tuple(n, 4);
1208 set_Tuple_pred(n, pn_DivMod_M, mem);
1209 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1210 set_Tuple_pred(n, pn_DivMod_res_div, a);
1211 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1212 assert(get_nodes_block(n));
1218 static ir_node *transform_node_Cond(ir_node *n)
1220 /* Replace the Cond by a Jmp if it branches on a constant
1223 ir_node *a = get_Cond_selector(n);
1224 tarval *ta = value_of(a);
1226 if ((ta != tarval_bad) &&
1227 (get_irn_mode(a) == mode_b) &&
1228 (get_opt_unreachable_code())) {
1229 /* It's a boolean Cond, branching on a boolean constant.
1230 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1231 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1232 turn_into_tuple(n, 2);
1233 if (ta == tarval_b_true) {
1234 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1235 set_Tuple_pred(n, pn_Cond_true, jmp);
1237 set_Tuple_pred(n, pn_Cond_false, jmp);
1238 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1240 /* We might generate an endless loop, so keep it alive. */
1241 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1242 } else if ((ta != tarval_bad) &&
1243 (get_irn_mode(a) == mode_Iu) &&
1244 (get_Cond_kind(n) == dense) &&
1245 (get_opt_unreachable_code())) {
1246 /* I don't want to allow Tuples smaller than the biggest Proj.
1247 Also this tuple might get really big...
1248 I generate the Jmp here, and remember it in link. Link is used
1249 when optimizing Proj. */
1250 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1251 /* We might generate an endless loop, so keep it alive. */
1252 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1253 } else if ((get_irn_op(a) == op_Eor)
1254 && (get_irn_mode(a) == mode_b)
1255 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1256 /* The Eor is a negate. Generate a new Cond without the negate,
1257 simulate the negate by exchanging the results. */
1258 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1260 } else if ((get_irn_op(a) == op_Not)
1261 && (get_irn_mode(a) == mode_b)) {
1262 /* A Not before the Cond. Generate a new Cond without the Not,
1263 simulate the Not by exchanging the results. */
1264 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1270 static ir_node *transform_node_Eor(ir_node *n)
1272 ir_node *a = get_Eor_left(n);
1273 ir_node *b = get_Eor_right(n);
1275 if ((get_irn_mode(n) == mode_b)
1276 && (get_irn_op(a) == op_Proj)
1277 && (get_irn_mode(a) == mode_b)
1278 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1279 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1280 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1281 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1282 mode_b, get_negated_pnc(get_Proj_proj(a)));
1283 else if ((get_irn_mode(n) == mode_b)
1284 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1285 /* The Eor is a Not. Replace it by a Not. */
1286 /* ????!!!Extend to bitfield 1111111. */
1287 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1293 * Transform a boolean Not.
1295 static ir_node *transform_node_Not(ir_node *n)
1297 ir_node *a = get_Not_op(n);
1299 if ( (get_irn_mode(n) == mode_b)
1300 && (get_irn_op(a) == op_Proj)
1301 && (get_irn_mode(a) == mode_b)
1302 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1303 /* We negate a Cmp. The Cmp has the negated result anyways! */
1304 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1305 mode_b, get_negated_pnc(get_Proj_proj(a)));
1310 static ir_node *transform_node_Cast(ir_node *n) {
1311 ir_node *pred = get_Cast_op(n);
1312 type *tp = get_irn_type(pred);
1313 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1314 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1315 get_Const_tarval(pred), tp);
1316 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1317 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1318 get_SymConst_kind(pred), tp);
1324 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1325 * done here instead of equivalent node because it creates new
1327 * Removes the exceptions and routes the memory to the initial mem.
1329 * Further, it optimizes jump tables by removing all impossible cases.
1331 static ir_node *transform_node_Proj(ir_node *proj)
1333 ir_node *n = get_Proj_pred(proj);
1338 switch (get_irn_opcode(n)) {
1340 b = get_Div_right(n);
1343 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1344 proj_nr = get_Proj_proj(proj);
1346 /* this node may float */
1347 set_irn_pinned(n, op_pin_state_floats);
1349 if (proj_nr == pn_Div_X_except) {
1350 /* we found an exception handler, remove it */
1354 /* the memory Proj can be removed */
1355 ir_node *res = get_Div_mem(n);
1356 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1358 if (proj_nr == pn_Div_M)
1364 b = get_Mod_right(n);
1367 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1368 proj_nr = get_Proj_proj(proj);
1370 /* this node may float */
1371 set_irn_pinned(n, op_pin_state_floats);
1373 if (proj_nr == pn_Mod_X_except) {
1374 /* we found an exception handler, remove it */
1378 /* the memory Proj can be removed */
1379 ir_node *res = get_Mod_mem(n);
1380 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1381 if (proj_nr == pn_Mod_M)
1387 b = get_DivMod_right(n);
1390 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1391 proj_nr = get_Proj_proj(proj);
1393 /* this node may float */
1394 set_irn_pinned(n, op_pin_state_floats);
1396 if (proj_nr == pn_DivMod_X_except) {
1397 /* we found an exception handler, remove it */
1401 /* the memory Proj can be removed */
1402 ir_node *res = get_DivMod_mem(n);
1403 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1404 if (proj_nr == pn_DivMod_M)
1411 if (get_opt_unreachable_code()) {
1412 b = get_Cond_selector(n);
1415 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1416 /* we have a constant switch */
1417 long num = get_Proj_proj(proj);
1419 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1420 if (get_tarval_long(tb) == num) {
1421 /* Do NOT create a jump here, or we will have 2 control flow ops
1422 * in a block. This case is optimized away in optimize_cf(). */
1433 /* should not happen, but if it does will be optimized away */
1441 /* we have added a Tuple, optimize it for the current Proj away */
1442 return equivalent_node_Proj(proj);
1446 * returns the operands of a commutative bin-op, if one operand is
1447 * a const, it is returned as the second one.
1449 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1451 ir_node *op_a = get_binop_left(binop);
1452 ir_node *op_b = get_binop_right(binop);
1454 assert(is_op_commutative(get_irn_op(binop)));
1456 if (get_irn_op(op_a) == op_Const) {
1467 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1468 * Such pattern may arise in bitfield stores.
1470 * value c4 value c4 & c2
1471 * AND c3 AND c1 | c3
1476 static ir_node *transform_node_Or(ir_node *or)
1480 ir_node *and_l, *c3;
1481 ir_node *value, *c4;
1482 ir_node *new_and, *new_const, *block;
1483 ir_mode *mode = get_irn_mode(or);
1485 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1487 get_comm_Binop_Ops(or, &and, &c1);
1488 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1491 get_comm_Binop_Ops(and, &or_l, &c2);
1492 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1495 get_comm_Binop_Ops(or_l, &and_l, &c3);
1496 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1499 get_comm_Binop_Ops(and_l, &value, &c4);
1500 if (get_irn_op(c4) != op_Const)
1503 /* ok, found the pattern, check for conditions */
1504 assert(mode == get_irn_mode(and));
1505 assert(mode == get_irn_mode(or_l));
1506 assert(mode == get_irn_mode(and_l));
1508 tv1 = get_Const_tarval(c1);
1509 tv2 = get_Const_tarval(c2);
1510 tv3 = get_Const_tarval(c3);
1511 tv4 = get_Const_tarval(c4);
1513 tv = tarval_or(tv4, tv2);
1514 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1515 /* have at least one 0 at the same bit position */
1519 n_tv4 = tarval_not(tv4);
1520 if (tv3 != tarval_and(tv3, n_tv4)) {
1521 /* bit in the or_mask is outside the and_mask */
1525 n_tv2 = tarval_not(tv2);
1526 if (tv1 != tarval_and(tv1, n_tv2)) {
1527 /* bit in the or_mask is outside the and_mask */
1531 /* ok, all conditions met */
1532 block = get_nodes_block(or);
1534 new_and = new_r_And(current_ir_graph, block,
1535 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1537 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1539 set_Or_left(or, new_and);
1540 set_Or_right(or, new_const);
1542 /* check for more */
1543 return transform_node_Or(or);
1547 static ir_node *transform_node(ir_node *n);
1550 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1552 static ir_node * transform_node_shift(ir_node *n)
1555 tarval *tv1, *tv2, *res;
1557 int modulo_shf, flag;
1559 left = get_binop_left(n);
1561 /* different operations */
1562 if (get_irn_op(left) != get_irn_op(n))
1565 tv1 = value_of(get_binop_right(n));
1566 if (tv1 == tarval_bad)
1569 tv2 = value_of(get_binop_right(left));
1570 if (tv2 == tarval_bad)
1573 res = tarval_add(tv1, tv2);
1575 /* beware: a simple replacement works only, if res < modulo shift */
1576 mode = get_irn_mode(n);
1580 modulo_shf = get_mode_modulo_shift(mode);
1581 if (modulo_shf > 0) {
1582 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1584 if (tarval_cmp(res, modulo) & Lt)
1591 /* ok, we can replace it */
1592 ir_node *in[2], *irn, *block = get_nodes_block(n);
1594 in[0] = get_binop_left(left);
1595 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1597 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1599 return transform_node(irn);
1606 * Tries several [inplace] [optimizing] transformations and returns an
1607 * equivalent node. The difference to equivalent_node() is that these
1608 * transformations _do_ generate new nodes, and thus the old node must
1609 * not be freed even if the equivalent node isn't the old one.
1611 static ir_node *transform_node(ir_node *n)
1613 if (n->op->transform_node)
1614 n = n->op->transform_node(n);
1619 * set the default transform node operation
1621 static ir_op *firm_set_default_transform_node(ir_op *op)
1625 op->transform_node = transform_node_##a; \
1642 op->transform_node = transform_node_shift;
1645 op->transform_node = NULL;
1653 /* **************** Common Subexpression Elimination **************** */
1655 /** The size of the hash table used, should estimate the number of nodes
1657 #define N_IR_NODES 512
1659 /** Compares the attributes of two Const nodes. */
1660 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1662 return (get_Const_tarval(a) != get_Const_tarval(b))
1663 || (get_Const_type(a) != get_Const_type(b));
1666 /** Compares the attributes of two Proj nodes. */
1667 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1669 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1672 /** Compares the attributes of two Filter nodes. */
1673 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1675 return get_Filter_proj(a) != get_Filter_proj(b);
1678 /** Compares the attributes of two Alloc nodes. */
1679 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1681 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1682 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1685 /** Compares the attributes of two Free nodes. */
1686 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1688 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1691 /** Compares the attributes of two SymConst nodes. */
1692 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1694 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1695 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1696 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1699 /** Compares the attributes of two Call nodes. */
1700 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1702 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1705 /** Compares the attributes of two FuncCall nodes. */
1706 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1708 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1711 /** Compares the attributes of two Sel nodes. */
1712 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1714 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1715 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1716 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1717 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1718 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1721 /** Compares the attributes of two Phi nodes. */
1722 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1724 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1727 /** Compares the attributes of two Cast nodes. */
1728 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1730 return get_Cast_type(a) != get_Cast_type(b);
1733 /** Compares the attributes of two Load nodes. */
1734 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1736 if (get_Load_volatility(a) == volatility_is_volatile ||
1737 get_Load_volatility(b) == volatility_is_volatile)
1738 /* NEVER do CSE on volatile Loads */
1741 return get_Load_mode(a) != get_Load_mode(b);
1744 /** Compares the attributes of two Store nodes. */
1745 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1747 /* NEVER do CSE on volatile Stores */
1748 return (get_Store_volatility(a) == volatility_is_volatile ||
1749 get_Store_volatility(b) == volatility_is_volatile);
1753 * set the default node attribute compare operation
1755 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1759 op->node_cmp_attr = node_cmp_attr_##a; \
1777 op->node_cmp_attr = NULL;
1785 * Compare function for two nodes in the hash table. Gets two
1786 * nodes as parameters. Returns 0 if the nodes are a cse.
1789 vt_cmp (const void *elt, const void *key)
1797 if (a == b) return 0;
1799 if ((get_irn_op(a) != get_irn_op(b)) ||
1800 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1802 /* compare if a's in and b's in are of equal length */
1803 irn_arity_a = get_irn_intra_arity (a);
1804 if (irn_arity_a != get_irn_intra_arity(b))
1807 /* for block-local cse and op_pin_state_pinned nodes: */
1808 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1809 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1813 /* compare a->in[0..ins] with b->in[0..ins] */
1814 for (i = 0; i < irn_arity_a; i++)
1815 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1819 * here, we already now that the nodes are identical except their
1822 if (a->op->node_cmp_attr)
1823 return a->op->node_cmp_attr(a, b);
1828 #define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3)
1831 * Calculate a hash value of a node.
1834 ir_node_hash (ir_node *node)
1839 if (node->op == op_Const) {
1840 /* special value for const, as they only differ in their tarval. */
1841 h = ADDR_TO_VAL(node->attr.con.tv);
1842 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1843 } else if (node->op == op_SymConst) {
1844 /* special value for const, as they only differ in their symbol. */
1845 h = ADDR_TO_VAL(node->attr.i.sym.type_p);
1846 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1849 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1850 h = irn_arity = get_irn_intra_arity(node);
1852 /* consider all in nodes... except the block if not a control flow. */
1853 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1854 h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i));
1858 h = 9*h + ADDR_TO_VAL(get_irn_mode(node));
1860 h = 9*h + ADDR_TO_VAL(get_irn_op(node));
1867 new_identities(void) {
1868 return new_pset(vt_cmp, N_IR_NODES);
1872 del_identities(pset *value_table) {
1873 del_pset(value_table);
1877 * Return the canonical node computing the same value as n.
1878 * Looks up the node in a hash table.
1880 * For Const nodes this is performed in the constructor, too. Const
1881 * nodes are extremely time critical because of their frequent use in
1882 * constant string arrays.
1884 static INLINE ir_node *
1885 identify (pset *value_table, ir_node *n)
1889 if (!value_table) return n;
1891 if (get_opt_reassociation()) {
1892 if (is_op_commutative(get_irn_op(n))) {
1893 ir_node *l = get_binop_left(n);
1894 ir_node *r = get_binop_right(n);
1896 /* for commutative operators perform a OP b == b OP a */
1898 set_binop_left(n, r);
1899 set_binop_right(n, l);
1904 o = pset_find (value_table, n, ir_node_hash (n));
1913 * During construction we set the op_pin_state_pinned flag in the graph right when the
1914 * optimization is performed. The flag turning on procedure global cse could
1915 * be changed between two allocations. This way we are safe.
1917 static INLINE ir_node *
1918 identify_cons (pset *value_table, ir_node *n) {
1921 n = identify(value_table, n);
1922 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1923 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1928 * Return the canonical node computing the same value as n.
1929 * Looks up the node in a hash table, enters it in the table
1930 * if it isn't there yet.
1933 identify_remember (pset *value_table, ir_node *n)
1937 if (!value_table) return n;
1939 if (get_opt_reassociation()) {
1940 if (is_op_commutative(get_irn_op(n))) {
1941 ir_node *l = get_binop_left(n);
1942 ir_node *r = get_binop_right(n);
1944 /* for commutative operators perform a OP b == b OP a */
1946 set_binop_left(n, r);
1947 set_binop_right(n, l);
1952 /* lookup or insert in hash table with given hash key. */
1953 o = pset_insert (value_table, n, ir_node_hash (n));
1963 add_identities (pset *value_table, ir_node *node) {
1964 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1965 identify_remember (value_table, node);
1969 * garbage in, garbage out. If a node has a dead input, i.e., the
1970 * Bad node is input to the node, return the Bad node.
1972 static INLINE ir_node *
1973 gigo (ir_node *node)
1976 ir_op* op = get_irn_op(node);
1978 /* remove garbage blocks by looking at control flow that leaves the block
1979 and replacing the control flow by Bad. */
1980 if (get_irn_mode(node) == mode_X) {
1981 ir_node *block = get_nodes_block(node);
1982 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1983 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1984 irn_arity = get_irn_arity(block);
1985 for (i = 0; i < irn_arity; i++) {
1986 if (!is_Bad(get_irn_n(block, i))) break;
1988 if (i == irn_arity) return new_Bad();
1992 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1993 blocks predecessors is dead. */
1994 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1995 irn_arity = get_irn_arity(node);
1996 for (i = -1; i < irn_arity; i++) {
1997 if (is_Bad(get_irn_n(node, i))) {
2003 /* With this code we violate the agreement that local_optimize
2004 only leaves Bads in Block, Phi and Tuple nodes. */
2005 /* If Block has only Bads as predecessors it's garbage. */
2006 /* If Phi has only Bads as predecessors it's garbage. */
2007 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2008 irn_arity = get_irn_arity(node);
2009 for (i = 0; i < irn_arity; i++) {
2010 if (!is_Bad(get_irn_n(node, i))) break;
2012 if (i == irn_arity) node = new_Bad();
2020 * These optimizations deallocate nodes from the obstack.
2021 * It can only be called if it is guaranteed that no other nodes
2022 * reference this one, i.e., right after construction of a node.
2025 optimize_node (ir_node *n)
2029 opcode iro = get_irn_opcode(n);
2031 type *old_tp = get_irn_type(n);
2033 int i, arity = get_irn_arity(n);
2034 for (i = 0; i < arity && !old_tp; ++i)
2035 old_tp = get_irn_type(get_irn_n(n, i));
2038 /* Allways optimize Phi nodes: part of the construction. */
2039 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2041 /* constant expression evaluation / constant folding */
2042 if (get_opt_constant_folding()) {
2043 /* constants can not be evaluated */
2044 if (iro != iro_Const) {
2045 /* try to evaluate */
2046 tv = computed_value(n);
2047 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2049 * we MUST copy the node here temporary, because it's still needed
2050 * for DBG_OPT_ALGSIM0
2052 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2053 oldn = alloca(node_size);
2055 memcpy(oldn, n, node_size);
2056 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2058 /* ARG, copy the in array, we need it for statistics */
2059 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2061 /* evaluation was successful -- replace the node. */
2062 obstack_free (current_ir_graph->obst, n);
2063 n = new_Const (get_tarval_mode (tv), tv);
2064 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2065 set_Const_type(n, old_tp);
2066 DBG_OPT_ALGSIM0(oldn, n);
2072 /* remove unnecessary nodes */
2073 if (get_opt_constant_folding() ||
2074 (iro == iro_Phi) || /* always optimize these nodes. */
2076 (iro == iro_Proj) ||
2077 (iro == iro_Block) ) /* Flags tested local. */
2078 n = equivalent_node (n);
2080 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2082 /** common subexpression elimination **/
2083 /* Checks whether n is already available. */
2084 /* The block input is used to distinguish different subexpressions. Right
2085 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2086 subexpressions within a block. */
2088 n = identify_cons (current_ir_graph->value_table, n);
2091 /* We found an existing, better node, so we can deallocate the old node. */
2092 obstack_free (current_ir_graph->obst, oldn);
2097 /* Some more constant expression evaluation that does not allow to
2099 iro = get_irn_opcode(n);
2100 if (get_opt_constant_folding() ||
2101 (iro == iro_Cond) ||
2102 (iro == iro_Proj)) /* Flags tested local. */
2103 n = transform_node (n);
2105 /* Remove nodes with dead (Bad) input.
2106 Run always for transformation induced Bads. */
2109 /* Now we have a legal, useful node. Enter it in hash table for cse */
2110 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2111 n = identify_remember (current_ir_graph->value_table, n);
2119 * These optimizations never deallocate nodes. This can cause dead
2120 * nodes lying on the obstack. Remove these by a dead node elimination,
2121 * i.e., a copying garbage collection.
2124 optimize_in_place_2 (ir_node *n)
2128 opcode iro = get_irn_opcode(n);
2130 type *old_tp = get_irn_type(n);
2132 int i, arity = get_irn_arity(n);
2133 for (i = 0; i < arity && !old_tp; ++i)
2134 old_tp = get_irn_type(get_irn_n(n, i));
2137 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2139 /* if not optimize return n */
2142 /* Here this is possible. Why? */
2146 /* constant expression evaluation / constant folding */
2147 if (get_opt_constant_folding()) {
2148 /* constants can not be evaluated */
2149 if (iro != iro_Const) {
2150 /* try to evaluate */
2151 tv = computed_value(n);
2152 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2153 /* evaluation was successful -- replace the node. */
2154 n = new_Const (get_tarval_mode (tv), tv);
2156 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2157 set_Const_type(n, old_tp);
2159 DBG_OPT_ALGSIM0(oldn, n);
2165 /* remove unnecessary nodes */
2166 if (get_opt_constant_folding() ||
2167 (iro == iro_Phi) || /* always optimize these nodes. */
2168 (iro == iro_Id) || /* ... */
2169 (iro == iro_Proj) || /* ... */
2170 (iro == iro_Block) ) /* Flags tested local. */
2171 n = equivalent_node (n);
2173 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2175 /** common subexpression elimination **/
2176 /* Checks whether n is already available. */
2177 /* The block input is used to distinguish different subexpressions. Right
2178 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2179 subexpressions within a block. */
2180 if (get_opt_cse()) {
2181 n = identify (current_ir_graph->value_table, n);
2184 /* Some more constant expression evaluation. */
2185 iro = get_irn_opcode(n);
2186 if (get_opt_constant_folding() ||
2187 (iro == iro_Cond) ||
2188 (iro == iro_Proj)) /* Flags tested local. */
2189 n = transform_node (n);
2191 /* Remove nodes with dead (Bad) input.
2192 Run always for transformation induced Bads. */
2195 /* Now we can verify the node, as it has no dead inputs any more. */
2198 /* Now we have a legal, useful node. Enter it in hash table for cse.
2199 Blocks should be unique anyways. (Except the successor of start:
2200 is cse with the start block!) */
2201 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2202 n = identify_remember (current_ir_graph->value_table, n);
2208 * Wrapper for external use, set proper status bits after optimization.
2211 optimize_in_place (ir_node *n)
2213 /* Handle graph state */
2214 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2216 if (get_opt_global_cse())
2217 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2218 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2219 set_irg_outs_inconsistent(current_ir_graph);
2221 /* Maybe we could also test whether optimizing the node can
2222 change the control graph. */
2223 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2224 set_irg_dom_inconsistent(current_ir_graph);
2225 return optimize_in_place_2 (n);
2229 * set the default ir op operations
2231 ir_op *firm_set_default_operations(ir_op *op)
2233 op = firm_set_default_computed_value(op);
2234 op = firm_set_default_equivalent_node(op);
2235 op = firm_set_default_transform_node(op);
2236 op = firm_set_default_node_cmp_attr(op);