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)
76 && (get_irn_mode(a) == get_irn_mode(b))
77 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
78 return tarval_add(ta, tb);
84 * return the value of a Sub
87 static tarval *computed_value_Sub(ir_node *n)
89 ir_node *a = get_Sub_left(n);
90 ir_node *b = get_Sub_right(n);
96 return get_tarval_null(get_irn_mode(n));
101 if ((ta != tarval_bad) && (tb != tarval_bad)
102 && (get_irn_mode(a) == get_irn_mode(b))
103 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
104 return tarval_sub(ta, tb);
110 * return the value of an unary Minus
112 static tarval *computed_value_Minus(ir_node *n)
114 ir_node *a = get_Minus_op(n);
115 tarval *ta = value_of(a);
117 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
118 return tarval_neg(ta);
124 * return the value of a Mul
126 static tarval *computed_value_Mul(ir_node *n)
128 ir_node *a = get_Mul_left(n);
129 ir_node *b = get_Mul_right(n);
131 tarval *ta = value_of(a);
132 tarval *tb = value_of(b);
134 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
135 return tarval_mul(ta, tb);
137 /* a*0 = 0 or 0*b = 0:
138 calls computed_value recursive and returns the 0 with proper
142 if ( ( ((v = ta) != tarval_bad)
143 && (v == get_mode_null(get_tarval_mode(v))) )
144 || ( ((v = tb) != tarval_bad)
145 && (v == get_mode_null(get_tarval_mode(v))) )) {
153 * return the value of a floating point Quot
155 static tarval *computed_value_Quot(ir_node *n)
157 ir_node *a = get_Quot_left(n);
158 ir_node *b = get_Quot_right(n);
160 tarval *ta = value_of(a);
161 tarval *tb = value_of(b);
163 /* This was missing in original implementation. Why? */
164 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
165 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
166 return tarval_quo(ta, tb);
172 * calculate the value of an integer Div of two nodes
173 * Special case: 0 / b
175 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
177 tarval *ta = value_of(a);
178 tarval *tb = value_of(b);
180 /* Compute c1 / c2 or 0 / a, a != 0 */
181 if ((ta != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) {
182 if (tb != tarval_bad) /* div by zero: return tarval_bad */
183 return tarval_div(ta, tb);
184 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
191 * return the value of an integer Div
193 static tarval *computed_value_Div(ir_node *n)
195 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
199 * calculate the value of an integer Mod of two nodes
200 * Special case: a % 1
202 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
204 tarval *ta = value_of(a);
205 tarval *tb = value_of(b);
207 /* Compute c1 % c2 or a % 1 */
208 if (tb != tarval_bad) {
209 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
210 return tarval_mod(ta, tb);
211 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
212 return get_mode_null(get_irn_mode(a));
219 * return the value of an integer Mod
221 static tarval *computed_value_Mod(ir_node *n)
223 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
227 * return the value of an Abs
229 static tarval *computed_value_Abs(ir_node *n)
231 ir_node *a = get_Abs_op(n);
232 tarval *ta = value_of(a);
234 if (ta != tarval_bad)
235 return tarval_abs(ta);
241 * return the value of an And
242 * Special case: a & 0, 0 & b
244 static tarval *computed_value_And(ir_node *n)
246 ir_node *a = get_And_left(n);
247 ir_node *b = get_And_right(n);
249 tarval *ta = value_of(a);
250 tarval *tb = value_of(b);
252 if ((ta != tarval_bad) && (tb != tarval_bad)) {
253 return tarval_and (ta, tb);
257 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_NULL)
258 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
266 * return the value of an Or
267 * Special case: a | 1...1, 1...1 | b
269 static tarval *computed_value_Or(ir_node *n)
271 ir_node *a = get_Or_left(n);
272 ir_node *b = get_Or_right(n);
274 tarval *ta = value_of(a);
275 tarval *tb = value_of(b);
277 if ((ta != tarval_bad) && (tb != tarval_bad)) {
278 return tarval_or (ta, tb);
281 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
282 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
290 * return the value of an Eor
292 static tarval *computed_value_Eor(ir_node *n)
294 ir_node *a = get_Eor_left(n);
295 ir_node *b = get_Eor_right(n);
297 tarval *ta = value_of(a);
298 tarval *tb = value_of(b);
300 if ((ta != tarval_bad) && (tb != tarval_bad)) {
301 return tarval_eor (ta, tb);
307 * return the value of a Not
309 static tarval *computed_value_Not(ir_node *n)
311 ir_node *a = get_Not_op(n);
312 tarval *ta = value_of(a);
314 if (ta != tarval_bad)
315 return tarval_not(ta);
321 * return the value of a Shl
323 static tarval *computed_value_Shl(ir_node *n)
325 ir_node *a = get_Shl_left(n);
326 ir_node *b = get_Shl_right(n);
328 tarval *ta = value_of(a);
329 tarval *tb = value_of(b);
331 if ((ta != tarval_bad) && (tb != tarval_bad)) {
332 return tarval_shl (ta, tb);
338 * return the value of a Shr
340 static tarval *computed_value_Shr(ir_node *n)
342 ir_node *a = get_Shr_left(n);
343 ir_node *b = get_Shr_right(n);
345 tarval *ta = value_of(a);
346 tarval *tb = value_of(b);
348 if ((ta != tarval_bad) && (tb != tarval_bad)) {
349 return tarval_shr (ta, tb);
355 * return the value of a Shrs
357 static tarval *computed_value_Shrs(ir_node *n)
359 ir_node *a = get_Shrs_left(n);
360 ir_node *b = get_Shrs_right(n);
362 tarval *ta = value_of(a);
363 tarval *tb = value_of(b);
365 if ((ta != tarval_bad) && (tb != tarval_bad)) {
366 return tarval_shrs (ta, tb);
372 * return the value of a Rot
374 static tarval *computed_value_Rot(ir_node *n)
376 ir_node *a = get_Rot_left(n);
377 ir_node *b = get_Rot_right(n);
379 tarval *ta = value_of(a);
380 tarval *tb = value_of(b);
382 if ((ta != tarval_bad) && (tb != tarval_bad)) {
383 return tarval_rot (ta, tb);
389 * return the value of a Conv
391 static tarval *computed_value_Conv(ir_node *n)
393 ir_node *a = get_Conv_op(n);
394 tarval *ta = value_of(a);
396 if (ta != tarval_bad)
397 return tarval_convert_to(ta, get_irn_mode(n));
403 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
405 static tarval *computed_value_Proj(ir_node *n)
407 ir_node *a = get_Proj_pred(n);
411 /* Optimize Cmp nodes.
412 This performs a first step of unreachable code elimination.
413 Proj can not be computed, but folding a Cmp above the Proj here is
414 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
416 There are several case where we can evaluate a Cmp node:
417 1. The nodes compared are both the same. If we compare for
418 equal, greater equal, ... this will return true, else it
419 will return false. This step relies on cse.
420 2. The predecessors of Cmp are target values. We can evaluate
422 3. The predecessors are Allocs or void* constants. Allocs never
423 return NULL, they raise an exception. Therefore we can predict
425 switch (get_irn_opcode(a)) {
427 aa = get_Cmp_left(a);
428 ab = get_Cmp_right(a);
429 proj_nr = get_Proj_proj(n);
431 if (aa == ab) { /* 1.: */
432 /* This is a trick with the bits used for encoding the Cmp
433 Proj numbers, the following statement is not the same:
434 return new_tarval_from_long (proj_nr == Eq, mode_b) */
435 return new_tarval_from_long (proj_nr & Eq, mode_b);
437 tarval *taa = computed_value (aa);
438 tarval *tab = computed_value (ab);
440 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
441 /* strange checks... */
442 pnc_number flags = tarval_cmp (taa, tab);
443 if (flags != False) {
444 return new_tarval_from_long (proj_nr & flags, mode_b);
446 } else { /* check for 3.: */
447 ir_node *aaa = skip_Id(skip_Proj(aa));
448 ir_node *aba = skip_Id(skip_Proj(ab));
450 if ( ( (/* aa is ProjP and aaa is Alloc */
451 (get_irn_op(aa) == op_Proj)
452 && (mode_is_reference(get_irn_mode(aa)))
453 && (get_irn_op(aaa) == op_Alloc))
454 && ( (/* ab is constant void */
455 (get_irn_op(ab) == op_Const)
456 && (mode_is_reference(get_irn_mode(ab)))
457 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
458 || (/* ab is other Alloc */
459 (get_irn_op(ab) == op_Proj)
460 && (mode_is_reference(get_irn_mode(ab)))
461 && (get_irn_op(aba) == op_Alloc)
463 || (/* aa is void and aba is Alloc */
464 (get_irn_op(aa) == op_Const)
465 && (mode_is_reference(get_irn_mode(aa)))
466 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
467 && (get_irn_op(ab) == op_Proj)
468 && (mode_is_reference(get_irn_mode(ab)))
469 && (get_irn_op(aba) == op_Alloc)))
471 return new_tarval_from_long (proj_nr & Ne, mode_b);
477 /* compute either the Div or the Mod part */
478 proj_nr = get_Proj_proj(n);
479 if (proj_nr == pn_DivMod_res_div)
480 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
481 else if (proj_nr == pn_DivMod_res_mod)
482 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
486 if (get_Proj_proj(n) == pn_Div_res)
487 return computed_value(a);
491 if (get_Proj_proj(n) == pn_Mod_res)
492 return computed_value(a);
502 * If the parameter n can be computed, return its value, else tarval_bad.
503 * Performs constant folding.
505 * @param n The node this should be evaluated
507 tarval *computed_value(ir_node *n)
509 if (n->op->computed_value)
510 return n->op->computed_value(n);
515 * set the default computed_value evaluator
517 static ir_op *firm_set_default_computed_value(ir_op *op)
521 op->computed_value = computed_value_##a; \
546 op->computed_value = NULL;
554 /* returns 1 if the a and b are pointers to different locations. */
556 different_identity (ir_node *a, ir_node *b)
558 assert (mode_is_reference(get_irn_mode (a))
559 && mode_is_reference(get_irn_mode (b)));
561 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
562 ir_node *a1 = get_Proj_pred (a);
563 ir_node *b1 = get_Proj_pred (b);
564 if (a1 != b1 && get_irn_op (a1) == op_Alloc
565 && get_irn_op (b1) == op_Alloc)
572 static ir_node *equivalent_node_Block(ir_node *n)
576 /* The Block constructor does not call optimize, but mature_immBlock
577 calls the optimization. */
578 assert(get_Block_matured(n));
580 /* Straightening: a single entry Block following a single exit Block
581 can be merged, if it is not the Start block. */
582 /* !!! Beware, all Phi-nodes of n must have been optimized away.
583 This should be true, as the block is matured before optimize is called.
584 But what about Phi-cycles with the Phi0/Id that could not be resolved?
585 Remaining Phi nodes are just Ids. */
586 if ((get_Block_n_cfgpreds(n) == 1) &&
587 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
588 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
589 if (predblock == oldn) {
590 /* Jmp jumps into the block it is in -- deal self cycle. */
592 DBG_OPT_DEAD(oldn, n);
593 } else if (get_opt_control_flow_straightening()) {
595 DBG_OPT_STG(oldn, n);
598 else if ((get_Block_n_cfgpreds(n) == 1) &&
599 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
600 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
601 if (predblock == oldn) {
602 /* Jmp jumps into the block it is in -- deal self cycle. */
604 DBG_OPT_DEAD(oldn, n);
607 else if ((get_Block_n_cfgpreds(n) == 2) &&
608 (get_opt_control_flow_weak_simplification())) {
609 /* Test whether Cond jumps twice to this block
610 @@@ we could do this also with two loops finding two preds from several ones. */
611 ir_node *a = get_Block_cfgpred(n, 0);
612 ir_node *b = get_Block_cfgpred(n, 1);
614 if ((get_irn_op(a) == op_Proj) &&
615 (get_irn_op(b) == op_Proj) &&
616 (get_Proj_pred(a) == get_Proj_pred(b)) &&
617 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
618 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
619 /* Also a single entry Block following a single exit Block. Phis have
620 twice the same operand and will be optimized away. */
621 n = get_nodes_block(a);
622 DBG_OPT_IFSIM(oldn, a, b, n);
624 } else if (get_opt_unreachable_code() &&
625 (n != current_ir_graph->start_block) &&
626 (n != current_ir_graph->end_block) ) {
628 /* If all inputs are dead, this block is dead too, except if it is
629 the start or end block. This is a step of unreachable code
631 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
632 if (!is_Bad(get_Block_cfgpred(n, i))) break;
634 if (i == get_Block_n_cfgpreds(n))
642 * Returns a equivalent node for a Jmp, a Bad :-)
643 * Of course this only happens if the Block of the Jmp is Bad.
645 static ir_node *equivalent_node_Jmp(ir_node *n)
647 /* GL: Why not same for op_Raise?? */
648 /* unreachable code elimination */
649 if (is_Bad(get_nodes_block(n)))
655 static ir_node *equivalent_node_Cond(ir_node *n)
657 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
658 See cases for iro_Cond and iro_Proj in transform_node. */
663 * Use algebraic simplification a v a = a.
665 static ir_node *equivalent_node_Or(ir_node *n)
669 ir_node *a = get_Or_left(n);
670 ir_node *b = get_Or_right(n);
676 DBG_OPT_ALGSIM1(oldn, a, b, n);
683 * optimize operations that are commutative and have neutral 0,
684 * so a op 0 = 0 op a = a.
686 static ir_node *equivalent_node_neutral_zero(ir_node *n)
690 ir_node *a = get_binop_left(n);
691 ir_node *b = get_binop_right(n);
696 /* After running compute_node there is only one constant predecessor.
697 Find this predecessors value and remember the other node: */
698 if ((tv = computed_value(a)) != tarval_bad) {
700 } else if ((tv = computed_value(b)) != tarval_bad) {
705 /* If this predecessors constant value is zero, the operation is
706 unnecessary. Remove it: */
707 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
710 DBG_OPT_ALGSIM1(oldn, a, b, n);
716 #define equivalent_node_Add equivalent_node_neutral_zero
717 #define equivalent_node_Eor equivalent_node_neutral_zero
720 * optimize operations that are not commutative but have neutral 0 on left,
723 static ir_node *equivalent_node_left_zero(ir_node *n)
727 ir_node *a = get_binop_left(n);
728 ir_node *b = get_binop_right(n);
730 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_NULL) {
733 DBG_OPT_ALGSIM1(oldn, a, b, n);
739 #define equivalent_node_Sub equivalent_node_left_zero
740 #define equivalent_node_Shl equivalent_node_left_zero
741 #define equivalent_node_Shr equivalent_node_left_zero
742 #define equivalent_node_Shrs equivalent_node_left_zero
743 #define equivalent_node_Rot equivalent_node_left_zero
746 * Er, a "symmetic unop", ie op(op(n)) = n.
748 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
751 ir_node *pred = get_unop_op(n);
753 /* optimize symmetric unop */
754 if (get_irn_op(pred) == get_irn_op(n)) {
755 n = get_unop_op(pred);
756 DBG_OPT_ALGSIM2(oldn, pred, n);
762 #define equivalent_node_Not equivalent_node_symmetric_unop
764 /* --x == x */ /* ??? Is this possible or can --x raise an
765 out of bounds exception if min =! max? */
766 #define equivalent_node_Minus equivalent_node_symmetric_unop
769 * Optimize a * 1 = 1 * a = a.
771 static ir_node *equivalent_node_Mul(ir_node *n)
775 ir_node *a = get_Mul_left(n);
776 ir_node *b = get_Mul_right(n);
778 /* Mul is commutative and has again an other neutral element. */
779 if (classify_tarval (computed_value (a)) == TV_CLASSIFY_ONE) {
781 DBG_OPT_ALGSIM1(oldn, a, b, n);
782 } else if (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE) {
784 DBG_OPT_ALGSIM1(oldn, a, b, n);
790 * Optimize a / 1 = a.
792 static ir_node *equivalent_node_Div(ir_node *n)
794 ir_node *a = get_Div_left(n);
795 ir_node *b = get_Div_right(n);
797 /* Div is not commutative. */
798 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
799 /* Turn Div into a tuple (mem, bad, a) */
800 ir_node *mem = get_Div_mem(n);
801 turn_into_tuple(n, 3);
802 set_Tuple_pred(n, pn_Div_M, mem);
803 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
804 set_Tuple_pred(n, pn_Div_res, a);
810 * Optimize a / 1 = a.
812 static ir_node *equivalent_node_DivMod(ir_node *n)
814 ir_node *a = get_DivMod_left(n);
815 ir_node *b = get_DivMod_right(n);
817 /* Div is not commutative. */
818 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
819 /* Turn DivMod into a tuple (mem, bad, a, 0) */
820 ir_node *mem = get_Div_mem(n);
821 ir_mode *mode = get_irn_mode(b);
823 turn_into_tuple(n, 4);
824 set_Tuple_pred(n, pn_DivMod_M, mem);
825 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
826 set_Tuple_pred(n, pn_DivMod_res_div, a);
827 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
833 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
835 static ir_node *equivalent_node_And(ir_node *n)
839 ir_node *a = get_And_left(n);
840 ir_node *b = get_And_right(n);
843 n = a; /* And has it's own neutral element */
844 } else if (classify_tarval(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
846 DBG_OPT_ALGSIM1(oldn, a, b, n);
847 } else if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
849 DBG_OPT_ALGSIM1(oldn, a, b, n);
855 * Try to remove useless conv's:
857 static ir_node *equivalent_node_Conv(ir_node *n)
860 ir_node *a = get_Conv_op(n);
863 ir_mode *n_mode = get_irn_mode(n);
864 ir_mode *a_mode = get_irn_mode(a);
866 if (n_mode == a_mode) { /* No Conv necessary */
868 DBG_OPT_ALGSIM3(oldn, a, n);
869 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
873 n_mode = get_irn_mode(n);
874 b_mode = get_irn_mode(b);
876 if (n_mode == b_mode) {
877 if (n_mode == mode_b) {
878 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
879 DBG_OPT_ALGSIM1(oldn, a, b, n);
881 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
882 if (smaller_mode(b_mode, a_mode)){
883 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
884 DBG_OPT_ALGSIM1(oldn, a, b, n);
892 static ir_node *equivalent_node_Phi(ir_node *n)
894 /* Several optimizations:
895 - no Phi in start block.
896 - remove Id operators that are inputs to Phi
897 - fold Phi-nodes, iff they have only one predecessor except
903 ir_node *block = NULL; /* to shutup gcc */
904 ir_node *first_val = NULL; /* to shutup gcc */
905 ir_node *scnd_val = NULL; /* to shutup gcc */
907 if (!get_opt_normalize()) return n;
909 n_preds = get_Phi_n_preds(n);
911 block = get_nodes_block(n);
912 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
913 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
914 if ((is_Bad(block)) || /* Control dead */
915 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
916 return new_Bad(); /* in the Start Block. */
918 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
921 /* first we test for a special case: */
922 /* Confirm is a special node fixing additional information for a
923 value that is known at a certain point. This is useful for
924 dataflow analysis. */
926 ir_node *a = get_Phi_pred(n, 0);
927 ir_node *b = get_Phi_pred(n, 1);
928 if ( (get_irn_op(a) == op_Confirm)
929 && (get_irn_op(b) == op_Confirm)
930 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
931 && (get_irn_n(a, 1) == get_irn_n (b, 1))
932 && (a->data.num == (~b->data.num & irpn_True) )) {
933 return get_irn_n(a, 0);
938 /* If the Block has a Bad pred, we also have one. */
939 for (i = 0; i < n_preds; ++i)
940 if (is_Bad (get_Block_cfgpred(block, i)))
941 set_Phi_pred(n, i, new_Bad());
943 /* Find first non-self-referencing input */
944 for (i = 0; i < n_preds; ++i) {
945 first_val = get_Phi_pred(n, i);
946 if ( (first_val != n) /* not self pointer */
948 && (get_irn_op(first_val) != op_Bad)
950 ) { /* value not dead */
951 break; /* then found first value. */
955 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
956 if (i >= n_preds) { return new_Bad(); }
960 /* follow_Id () for rest of inputs, determine if any of these
961 are non-self-referencing */
962 while (++i < n_preds) {
963 scnd_val = get_Phi_pred(n, i);
965 && (scnd_val != first_val)
967 && (get_irn_op(scnd_val) != op_Bad)
974 /* Fold, if no multiple distinct non-self-referencing inputs */
977 DBG_OPT_PHI(oldn, first_val, n);
979 /* skip the remaining Ids (done in get_Phi_pred). */
980 /* superfluous, since we walk all to propagate Block's Bads.
981 while (++i < n_preds) get_Phi_pred(n, i); */
987 * optimize Proj(Tuple) and gigo for ProjX in Bad block
989 static ir_node *equivalent_node_Proj(ir_node *n)
993 ir_node *a = get_Proj_pred(n);
995 if ( get_irn_op(a) == op_Tuple) {
996 /* Remove the Tuple/Proj combination. */
997 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
998 n = get_Tuple_pred(a, get_Proj_proj(n));
999 DBG_OPT_TUPLE(oldn, a, n);
1001 assert(0); /* This should not happen! */
1004 } else if (get_irn_mode(n) == mode_X &&
1005 is_Bad(get_nodes_block(n))) {
1006 /* Remove dead control flow -- early gigo. */
1015 static ir_node *equivalent_node_Id(ir_node *n)
1020 DBG_OPT_ID(oldn, n);
1025 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1026 * perform no actual computation, as, e.g., the Id nodes. It does not create
1027 * new nodes. It is therefore safe to free n if the node returned is not n.
1028 * If a node returns a Tuple we can not just skip it. If the size of the
1029 * in array fits, we transform n into a tuple (e.g., Div).
1032 equivalent_node(ir_node *n)
1034 if (n->op->equivalent_node)
1035 return n->op->equivalent_node(n);
1040 * set the default equivalent node operation
1042 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1046 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 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 = computed_value(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 = computed_value(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(computed_value(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 (computed_value (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 (computed_value (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)));
1311 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1312 * done here instead of equivalent node because in creates new
1314 * Removes the exceptions and routes the memory to the initial mem.
1316 * Further, it optimizes jump tables by removing all impossible cases.
1318 static ir_node *transform_node_Proj(ir_node *proj)
1320 ir_node *n = get_Proj_pred(proj);
1325 switch (get_irn_opcode(n)) {
1327 b = get_Div_right(n);
1328 tb = computed_value(b);
1330 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1331 proj_nr = get_Proj_proj(proj);
1333 /* this node may float */
1334 set_irn_pinned(n, op_pin_state_floats);
1336 if (proj_nr == pn_Div_X_except) {
1337 /* we found an exception handler, remove it */
1341 /* the memory Proj can be removed */
1342 ir_node *res = get_Div_mem(n);
1343 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1345 if (proj_nr == pn_Div_M)
1351 b = get_Mod_right(n);
1352 tb = computed_value(b);
1354 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1355 proj_nr = get_Proj_proj(proj);
1357 /* this node may float */
1358 set_irn_pinned(n, op_pin_state_floats);
1360 if (proj_nr == pn_Mod_X_except) {
1361 /* we found an exception handler, remove it */
1365 /* the memory Proj can be removed */
1366 ir_node *res = get_Mod_mem(n);
1367 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1368 if (proj_nr == pn_Mod_M)
1374 b = get_DivMod_right(n);
1375 tb = computed_value(b);
1377 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1378 proj_nr = get_Proj_proj(proj);
1380 /* this node may float */
1381 set_irn_pinned(n, op_pin_state_floats);
1383 if (proj_nr == pn_DivMod_X_except) {
1384 /* we found an exception handler, remove it */
1388 /* the memory Proj can be removed */
1389 ir_node *res = get_DivMod_mem(n);
1390 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1391 if (proj_nr == pn_DivMod_M)
1398 if (get_opt_unreachable_code()) {
1399 b = get_Cond_selector(n);
1400 tb = computed_value(b);
1402 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1403 /* we have a constant switch */
1404 long num = get_Proj_proj(proj);
1406 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1407 if (get_tarval_long(tb) == num) {
1408 /* Do NOT create a jump here, or we will have 2 control flow ops
1409 * in a block. This case is optimized away in optimize_cf(). */
1420 /* should not happen, but if it does will be optimized away */
1428 /* we have added a Tuple, optimize it for the current Proj away */
1429 return equivalent_node_Proj(proj);
1433 * returns the operands of a commutative bin-op, if one operand is
1434 * a const, it is returned as the second one.
1436 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1438 ir_node *op_a = get_binop_left(binop);
1439 ir_node *op_b = get_binop_right(binop);
1441 assert(is_op_commutative(get_irn_op(binop)));
1443 if (get_irn_op(op_a) == op_Const) {
1454 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1455 * Such pattern may arise in bitfield stores.
1457 * value c4 value c4 & c2
1458 * AND c3 AND c1 | c3
1463 static ir_node *transform_node_Or(ir_node *or)
1467 ir_node *and_l, *c3;
1468 ir_node *value, *c4;
1469 ir_node *new_and, *new_const, *block;
1470 ir_mode *mode = get_irn_mode(or);
1472 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1474 get_comm_Binop_Ops(or, &and, &c1);
1475 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1478 get_comm_Binop_Ops(and, &or_l, &c2);
1479 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1482 get_comm_Binop_Ops(or_l, &and_l, &c3);
1483 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1486 get_comm_Binop_Ops(and_l, &value, &c4);
1487 if (get_irn_op(c4) != op_Const)
1490 /* ok, found the pattern, check for conditions */
1491 assert(mode == get_irn_mode(and));
1492 assert(mode == get_irn_mode(or_l));
1493 assert(mode == get_irn_mode(and_l));
1495 tv1 = get_Const_tarval(c1);
1496 tv2 = get_Const_tarval(c2);
1497 tv3 = get_Const_tarval(c3);
1498 tv4 = get_Const_tarval(c4);
1500 tv = tarval_or(tv4, tv2);
1501 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1502 /* have at least one 0 at the same bit position */
1506 n_tv4 = tarval_not(tv4);
1507 if (tv3 != tarval_and(tv3, n_tv4)) {
1508 /* bit in the or_mask is outside the and_mask */
1512 n_tv2 = tarval_not(tv2);
1513 if (tv1 != tarval_and(tv1, n_tv2)) {
1514 /* bit in the or_mask is outside the and_mask */
1518 /* ok, all conditions met */
1519 block = get_nodes_block(or);
1521 new_and = new_r_And(current_ir_graph, block,
1522 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1524 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1526 set_Or_left(or, new_and);
1527 set_Or_right(or, new_const);
1529 /* check for more */
1530 return transform_node_Or(or);
1534 static ir_node *transform_node(ir_node *n);
1537 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1539 static ir_node * transform_node_shift(ir_node *n)
1542 tarval *tv1, *tv2, *res;
1544 int modulo_shf, flag;
1546 left = get_binop_left(n);
1548 /* different operations */
1549 if (get_irn_op(left) != get_irn_op(n))
1552 tv1 = computed_value(get_binop_right(n));
1553 if (tv1 == tarval_bad)
1556 tv2 = computed_value(get_binop_right(left));
1557 if (tv1 == tarval_bad)
1560 res = tarval_add(tv1, tv2);
1562 /* beware: a simple replacement works only, if res < modulo shift */
1563 mode = get_irn_mode(n);
1567 modulo_shf = get_mode_modulo_shift(mode);
1568 if (modulo_shf > 0) {
1569 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1571 if (tarval_cmp(res, modulo) & Lt)
1578 /* ok, we can replace it */
1579 ir_node *in[2], *irn, *block = get_nodes_block(n);
1581 in[0] = get_binop_left(left);
1582 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1584 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1586 return transform_node(irn);
1593 * Tries several [inplace] [optimizing] transformations and returns an
1594 * equivalent node. The difference to equivalent_node() is that these
1595 * transformations _do_ generate new nodes, and thus the old node must
1596 * not be freed even if the equivalent node isn't the old one.
1598 static ir_node *transform_node(ir_node *n)
1600 if (n->op->transform_node)
1601 n = n->op->transform_node(n);
1606 * set the default transform node operation
1608 static ir_op *firm_set_default_transform_node(ir_op *op)
1612 op->transform_node = transform_node_##a; \
1628 op->transform_node = transform_node_shift;
1631 op->transform_node = NULL;
1639 /* **************** Common Subexpression Elimination **************** */
1641 /** The size of the hash table used, should estimate the number of nodes
1643 #define N_IR_NODES 512
1645 /** Compares the attributes of two Const nodes. */
1646 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1648 return (get_Const_tarval(a) != get_Const_tarval(b))
1649 || (get_Const_type(a) != get_Const_type(b));
1652 /** Compares the attributes of two Proj nodes. */
1653 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1655 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1658 /** Compares the attributes of two Filter nodes. */
1659 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1661 return get_Filter_proj(a) != get_Filter_proj(b);
1664 /** Compares the attributes of two Alloc nodes. */
1665 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1667 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1668 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1671 /** Compares the attributes of two Free nodes. */
1672 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1674 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1677 /** Compares the attributes of two SymConst nodes. */
1678 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1680 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1681 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1684 /** Compares the attributes of two Call nodes. */
1685 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1687 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1690 /** Compares the attributes of two FuncCall nodes. */
1691 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1693 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1696 /** Compares the attributes of two Sel nodes. */
1697 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1699 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1700 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1701 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1702 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1703 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1706 /** Compares the attributes of two Phi nodes. */
1707 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1709 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1712 /** Compares the attributes of two Cast nodes. */
1713 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1715 return get_Cast_type(a) != get_Cast_type(b);
1718 /** Compares the attributes of two Load nodes. */
1719 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1721 if (get_Load_volatility(a) == volatility_is_volatile ||
1722 get_Load_volatility(b) == volatility_is_volatile)
1723 /* NEVER do CSE on volatile Loads */
1726 return get_Load_mode(a) != get_Load_mode(b);
1729 /** Compares the attributes of two Store nodes. */
1730 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1732 /* NEVER do CSE on volatile Stores */
1733 return (get_Store_volatility(a) == volatility_is_volatile ||
1734 get_Store_volatility(b) == volatility_is_volatile);
1738 * set the default node attribute compare operation
1740 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1744 op->node_cmp_attr = node_cmp_attr_##a; \
1762 op->node_cmp_attr = NULL;
1770 * Compare function for two nodes in the hash table. Gets two
1771 * nodes as parameters. Returns 0 if the nodes are a cse.
1774 vt_cmp (const void *elt, const void *key)
1782 if (a == b) return 0;
1784 if ((get_irn_op(a) != get_irn_op(b)) ||
1785 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1787 /* compare if a's in and b's in are equal */
1788 irn_arity_a = get_irn_arity (a);
1789 if (irn_arity_a != get_irn_arity(b))
1792 /* for block-local cse and op_pin_state_pinned nodes: */
1793 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1794 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1798 /* compare a->in[0..ins] with b->in[0..ins] */
1799 for (i = 0; i < irn_arity_a; i++)
1800 if (get_irn_n(a, i) != get_irn_n(b, i))
1804 * here, we already now that the nodes are identical except their
1807 if (a->op->node_cmp_attr)
1808 return a->op->node_cmp_attr(a, b);
1814 * Calculate a hash value of a node.
1817 ir_node_hash (ir_node *node)
1822 if (node->op == op_Const) {
1823 /* special value for const, as they only differ in their tarval. */
1824 h = ((unsigned) node->attr.con.tv)>>3 ;
1825 h = 9*h + (unsigned)get_irn_mode(node);
1826 } else if (node->op == op_SymConst) {
1827 /* special value for const, as they only differ in their symbol. */
1828 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1829 h = 9*h + (unsigned)get_irn_mode(node);
1832 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1833 h = irn_arity = get_irn_arity(node);
1835 /* consider all in nodes... except the block. */
1836 for (i = 0; i < irn_arity; i++) {
1837 h = 9*h + (unsigned)get_irn_n(node, i);
1841 h = 9*h + (unsigned) get_irn_mode (node);
1843 h = 9*h + (unsigned) get_irn_op (node);
1850 new_identities (void)
1852 return new_pset (vt_cmp, N_IR_NODES);
1856 del_identities (pset *value_table)
1858 del_pset (value_table);
1862 * Return the canonical node computing the same value as n.
1863 * Looks up the node in a hash table.
1865 * For Const nodes this is performed in the constructor, too. Const
1866 * nodes are extremely time critical because of their frequent use in
1867 * constant string arrays.
1869 static INLINE ir_node *
1870 identify (pset *value_table, ir_node *n)
1874 if (!value_table) return n;
1876 if (get_opt_reassociation()) {
1877 if (is_op_commutative(get_irn_op(n))) {
1878 ir_node *l = get_binop_left(n);
1879 ir_node *r = get_binop_right(n);
1881 /* for commutative operators perform a OP b == b OP a */
1883 set_binop_left(n, r);
1884 set_binop_right(n, l);
1889 o = pset_find (value_table, n, ir_node_hash (n));
1898 * During construction we set the op_pin_state_pinned flag in the graph right when the
1899 * optimization is performed. The flag turning on procedure global cse could
1900 * be changed between two allocations. This way we are safe.
1902 static INLINE ir_node *
1903 identify_cons (pset *value_table, ir_node *n) {
1906 n = identify(value_table, n);
1907 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1908 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1913 * Return the canonical node computing the same value as n.
1914 * Looks up the node in a hash table, enters it in the table
1915 * if it isn't there yet.
1918 identify_remember (pset *value_table, ir_node *n)
1922 if (!value_table) return n;
1924 if (get_opt_reassociation()) {
1925 if (is_op_commutative(get_irn_op(n))) {
1926 ir_node *l = get_binop_left(n);
1927 ir_node *r = get_binop_right(n);
1929 /* for commutative operators perform a OP b == b OP a */
1931 set_binop_left(n, r);
1932 set_binop_right(n, l);
1937 /* lookup or insert in hash table with given hash key. */
1938 o = pset_insert (value_table, n, ir_node_hash (n));
1948 add_identities (pset *value_table, ir_node *node) {
1949 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1950 identify_remember (value_table, node);
1954 * garbage in, garbage out. If a node has a dead input, i.e., the
1955 * Bad node is input to the node, return the Bad node.
1957 static INLINE ir_node *
1958 gigo (ir_node *node)
1961 ir_op* op = get_irn_op(node);
1963 /* remove garbage blocks by looking at control flow that leaves the block
1964 and replacing the control flow by Bad. */
1965 if (get_irn_mode(node) == mode_X) {
1966 ir_node *block = get_nodes_block(node);
1967 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1968 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1969 irn_arity = get_irn_arity(block);
1970 for (i = 0; i < irn_arity; i++) {
1971 if (!is_Bad(get_irn_n(block, i))) break;
1973 if (i == irn_arity) return new_Bad();
1977 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1978 blocks predecessors is dead. */
1979 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1980 irn_arity = get_irn_arity(node);
1981 for (i = -1; i < irn_arity; i++) {
1982 if (is_Bad(get_irn_n(node, i))) {
1988 /* With this code we violate the agreement that local_optimize
1989 only leaves Bads in Block, Phi and Tuple nodes. */
1990 /* If Block has only Bads as predecessors it's garbage. */
1991 /* If Phi has only Bads as predecessors it's garbage. */
1992 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1993 irn_arity = get_irn_arity(node);
1994 for (i = 0; i < irn_arity; i++) {
1995 if (!is_Bad(get_irn_n(node, i))) break;
1997 if (i == irn_arity) node = new_Bad();
2005 * These optimizations deallocate nodes from the obstack.
2006 * It can only be called if it is guaranteed that no other nodes
2007 * reference this one, i.e., right after construction of a node.
2010 optimize_node (ir_node *n)
2014 opcode iro = get_irn_opcode(n);
2016 /* Always optimize Phi nodes: part of the construction. */
2017 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2019 /* constant expression evaluation / constant folding */
2020 if (get_opt_constant_folding()) {
2021 /* constants can not be evaluated */
2022 if (iro != iro_Const) {
2023 /* try to evaluate */
2024 tv = computed_value (n);
2025 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2027 * we MUST copy the node here temporary, because it's still needed
2028 * for DBG_OPT_ALGSIM0
2030 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2031 oldn = alloca(node_size);
2033 memcpy(oldn, n, node_size);
2034 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2036 /* ARG, copy the in array, we need it for statistics */
2037 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2039 /* evaluation was successful -- replace the node. */
2040 obstack_free (current_ir_graph->obst, n);
2041 n = new_Const (get_tarval_mode (tv), tv);
2043 DBG_OPT_ALGSIM0(oldn, n);
2049 /* remove unnecessary nodes */
2050 if (get_opt_constant_folding() ||
2051 (iro == iro_Phi) || /* always optimize these nodes. */
2053 (iro == iro_Proj) ||
2054 (iro == iro_Block) ) /* Flags tested local. */
2055 n = equivalent_node (n);
2057 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2059 /** common subexpression elimination **/
2060 /* Checks whether n is already available. */
2061 /* The block input is used to distinguish different subexpressions. Right
2062 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2063 subexpressions within a block. */
2065 n = identify_cons (current_ir_graph->value_table, n);
2068 /* We found an existing, better node, so we can deallocate the old node. */
2069 obstack_free (current_ir_graph->obst, oldn);
2074 /* Some more constant expression evaluation that does not allow to
2076 iro = get_irn_opcode(n);
2077 if (get_opt_constant_folding() ||
2078 (iro == iro_Cond) ||
2079 (iro == iro_Proj)) /* Flags tested local. */
2080 n = transform_node (n);
2082 /* Remove nodes with dead (Bad) input.
2083 Run always for transformation induced Bads. */
2086 /* Now we have a legal, useful node. Enter it in hash table for cse */
2087 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2088 n = identify_remember (current_ir_graph->value_table, n);
2096 * These optimizations never deallocate nodes. This can cause dead
2097 * nodes lying on the obstack. Remove these by a dead node elimination,
2098 * i.e., a copying garbage collection.
2101 optimize_in_place_2 (ir_node *n)
2105 opcode iro = get_irn_opcode(n);
2107 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2109 /* if not optimize return n */
2112 /* Here this is possible. Why? */
2117 /* constant expression evaluation / constant folding */
2118 if (get_opt_constant_folding()) {
2119 /* constants can not be evaluated */
2120 if (iro != iro_Const) {
2121 /* try to evaluate */
2122 tv = computed_value (n);
2123 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2124 /* evaluation was successful -- replace the node. */
2125 n = new_Const (get_tarval_mode (tv), tv);
2127 DBG_OPT_ALGSIM0(oldn, n);
2133 /* remove unnecessary nodes */
2134 if (get_opt_constant_folding() ||
2135 (iro == iro_Phi) || /* always optimize these nodes. */
2136 (iro == iro_Id) || /* ... */
2137 (iro == iro_Proj) || /* ... */
2138 (iro == iro_Block) ) /* Flags tested local. */
2139 n = equivalent_node (n);
2141 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2143 /** common subexpression elimination **/
2144 /* Checks whether n is already available. */
2145 /* The block input is used to distinguish different subexpressions. Right
2146 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2147 subexpressions within a block. */
2148 if (get_opt_cse()) {
2149 n = identify (current_ir_graph->value_table, n);
2152 /* Some more constant expression evaluation. */
2153 iro = get_irn_opcode(n);
2154 if (get_opt_constant_folding() ||
2155 (iro == iro_Cond) ||
2156 (iro == iro_Proj)) /* Flags tested local. */
2157 n = transform_node (n);
2159 /* Remove nodes with dead (Bad) input.
2160 Run always for transformation induced Bads. */
2163 /* Now we can verify the node, as it has no dead inputs any more. */
2166 /* Now we have a legal, useful node. Enter it in hash table for cse.
2167 Blocks should be unique anyways. (Except the successor of start:
2168 is cse with the start block!) */
2169 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2170 n = identify_remember (current_ir_graph->value_table, n);
2176 * Wrapper for external use, set proper status bits after optimization.
2179 optimize_in_place (ir_node *n)
2181 /* Handle graph state */
2182 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2184 if (get_opt_global_cse())
2185 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2186 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2187 set_irg_outs_inconsistent(current_ir_graph);
2189 /* Maybe we could also test whether optimizing the node can
2190 change the control graph. */
2191 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2192 set_irg_dom_inconsistent(current_ir_graph);
2193 return optimize_in_place_2 (n);
2197 * set the default ir op operations
2199 ir_op *firm_set_default_operations(ir_op *op)
2201 op = firm_set_default_computed_value(op);
2202 op = firm_set_default_equivalent_node(op);
2203 op = firm_set_default_transform_node(op);
2204 op = firm_set_default_node_cmp_attr(op);