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_Cast(ir_node *n) {
893 ir_node *pred = get_Cast_op(n);
894 if (get_irn_type(pred) == get_Cast_type(n))
899 static ir_node *equivalent_node_Phi(ir_node *n)
901 /* Several optimizations:
902 - no Phi in start block.
903 - remove Id operators that are inputs to Phi
904 - fold Phi-nodes, iff they have only one predecessor except
910 ir_node *block = NULL; /* to shutup gcc */
911 ir_node *first_val = NULL; /* to shutup gcc */
912 ir_node *scnd_val = NULL; /* to shutup gcc */
914 if (!get_opt_normalize()) return n;
916 n_preds = get_Phi_n_preds(n);
918 block = get_nodes_block(n);
919 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
920 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
921 if ((is_Bad(block)) || /* Control dead */
922 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
923 return new_Bad(); /* in the Start Block. */
925 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
928 /* first we test for a special case: */
929 /* Confirm is a special node fixing additional information for a
930 value that is known at a certain point. This is useful for
931 dataflow analysis. */
933 ir_node *a = get_Phi_pred(n, 0);
934 ir_node *b = get_Phi_pred(n, 1);
935 if ( (get_irn_op(a) == op_Confirm)
936 && (get_irn_op(b) == op_Confirm)
937 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
938 && (get_irn_n(a, 1) == get_irn_n (b, 1))
939 && (a->data.num == (~b->data.num & irpn_True) )) {
940 return get_irn_n(a, 0);
945 /* If the Block has a Bad pred, we also have one. */
946 for (i = 0; i < n_preds; ++i)
947 if (is_Bad (get_Block_cfgpred(block, i)))
948 set_Phi_pred(n, i, new_Bad());
950 /* Find first non-self-referencing input */
951 for (i = 0; i < n_preds; ++i) {
952 first_val = get_Phi_pred(n, i);
953 if ( (first_val != n) /* not self pointer */
955 && (get_irn_op(first_val) != op_Bad)
957 ) { /* value not dead */
958 break; /* then found first value. */
962 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
963 if (i >= n_preds) { return new_Bad(); }
967 /* follow_Id () for rest of inputs, determine if any of these
968 are non-self-referencing */
969 while (++i < n_preds) {
970 scnd_val = get_Phi_pred(n, i);
972 && (scnd_val != first_val)
974 && (get_irn_op(scnd_val) != op_Bad)
981 /* Fold, if no multiple distinct non-self-referencing inputs */
984 DBG_OPT_PHI(oldn, first_val, n);
986 /* skip the remaining Ids (done in get_Phi_pred). */
987 /* superfluous, since we walk all to propagate Block's Bads.
988 while (++i < n_preds) get_Phi_pred(n, i); */
994 * optimize Proj(Tuple) and gigo for ProjX in Bad block
996 static ir_node *equivalent_node_Proj(ir_node *n)
1000 ir_node *a = get_Proj_pred(n);
1002 if ( get_irn_op(a) == op_Tuple) {
1003 /* Remove the Tuple/Proj combination. */
1004 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1005 n = get_Tuple_pred(a, get_Proj_proj(n));
1006 DBG_OPT_TUPLE(oldn, a, n);
1008 assert(0); /* This should not happen! */
1011 } else if (get_irn_mode(n) == mode_X &&
1012 is_Bad(get_nodes_block(n))) {
1013 /* Remove dead control flow -- early gigo. */
1022 static ir_node *equivalent_node_Id(ir_node *n)
1027 DBG_OPT_ID(oldn, n);
1032 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1033 * perform no actual computation, as, e.g., the Id nodes. It does not create
1034 * new nodes. It is therefore safe to free n if the node returned is not n.
1035 * If a node returns a Tuple we can not just skip it. If the size of the
1036 * in array fits, we transform n into a tuple (e.g., Div).
1039 equivalent_node(ir_node *n)
1041 if (n->op->equivalent_node)
1042 return n->op->equivalent_node(n);
1047 * set the default equivalent node operation
1049 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1053 op->equivalent_node = equivalent_node_##a; \
1080 op->equivalent_node = NULL;
1088 * Do node specific optimizations of nodes predecessors.
1091 optimize_preds(ir_node *n) {
1092 ir_node *a = NULL, *b = NULL;
1094 /* get the operands we will work on for simple cases. */
1096 a = get_binop_left(n);
1097 b = get_binop_right(n);
1098 } else if (is_unop(n)) {
1102 switch (get_irn_opcode(n)) {
1105 /* We don't want Cast as input to Cmp. */
1106 if (get_irn_op(a) == op_Cast) {
1110 if (get_irn_op(b) == op_Cast) {
1112 set_Cmp_right(n, b);
1120 /** Do architecture dependend optimizations on Mul nodes */
1121 static ir_node *transform_node_Mul(ir_node *n) {
1122 return arch_dep_replace_mul_with_shifts(n);
1125 static ir_node *transform_node_Div(ir_node *n)
1127 tarval *tv = computed_value(n);
1130 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1132 if (tv != tarval_bad)
1133 value = new_Const(get_tarval_mode(tv), tv);
1134 else /* Try architecture dependand optimization */
1135 value = arch_dep_replace_div_by_const(n);
1138 /* Turn Div into a tuple (mem, bad, value) */
1139 ir_node *mem = get_Div_mem(n);
1141 turn_into_tuple(n, 3);
1142 set_Tuple_pred(n, pn_Div_M, mem);
1143 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1144 set_Tuple_pred(n, pn_Div_res, value);
1149 static ir_node *transform_node_Mod(ir_node *n)
1151 tarval *tv = computed_value(n);
1154 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1156 if (tv != tarval_bad)
1157 value = new_Const(get_tarval_mode(tv), tv);
1158 else /* Try architecture dependand optimization */
1159 value = arch_dep_replace_mod_by_const(n);
1162 /* Turn Mod into a tuple (mem, bad, value) */
1163 ir_node *mem = get_Mod_mem(n);
1165 turn_into_tuple(n, 3);
1166 set_Tuple_pred(n, pn_Mod_M, mem);
1167 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1168 set_Tuple_pred(n, pn_Mod_res, value);
1173 static ir_node *transform_node_DivMod(ir_node *n)
1177 ir_node *a = get_DivMod_left(n);
1178 ir_node *b = get_DivMod_right(n);
1179 ir_mode *mode = get_irn_mode(a);
1180 tarval *ta = value_of(a);
1181 tarval *tb = value_of(b);
1183 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1186 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1188 if (tb != tarval_bad) {
1189 if (tb == get_mode_one(get_tarval_mode(tb))) {
1190 b = new_Const (mode, get_mode_null(mode));
1192 } else if (ta != tarval_bad) {
1193 tarval *resa, *resb;
1194 resa = tarval_div (ta, tb);
1195 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1196 Jmp for X result!? */
1197 resb = tarval_mod (ta, tb);
1198 if (resb == tarval_bad) return n; /* Causes exception! */
1199 a = new_Const (mode, resa);
1200 b = new_Const (mode, resb);
1203 else { /* Try architecture dependand optimization */
1204 arch_dep_replace_divmod_by_const(&a, &b, n);
1205 evaluated = a != NULL;
1207 } else if (ta == get_mode_null(mode)) {
1208 /* 0 / non-Const = 0 */
1213 if (evaluated) { /* replace by tuple */
1214 ir_node *mem = get_DivMod_mem(n);
1215 turn_into_tuple(n, 4);
1216 set_Tuple_pred(n, pn_DivMod_M, mem);
1217 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1218 set_Tuple_pred(n, pn_DivMod_res_div, a);
1219 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1220 assert(get_nodes_block(n));
1226 static ir_node *transform_node_Cond(ir_node *n)
1228 /* Replace the Cond by a Jmp if it branches on a constant
1231 ir_node *a = get_Cond_selector(n);
1232 tarval *ta = value_of(a);
1234 if ((ta != tarval_bad) &&
1235 (get_irn_mode(a) == mode_b) &&
1236 (get_opt_unreachable_code())) {
1237 /* It's a boolean Cond, branching on a boolean constant.
1238 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1239 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1240 turn_into_tuple(n, 2);
1241 if (ta == tarval_b_true) {
1242 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1243 set_Tuple_pred(n, pn_Cond_true, jmp);
1245 set_Tuple_pred(n, pn_Cond_false, jmp);
1246 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1248 /* We might generate an endless loop, so keep it alive. */
1249 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1250 } else if ((ta != tarval_bad) &&
1251 (get_irn_mode(a) == mode_Iu) &&
1252 (get_Cond_kind(n) == dense) &&
1253 (get_opt_unreachable_code())) {
1254 /* I don't want to allow Tuples smaller than the biggest Proj.
1255 Also this tuple might get really big...
1256 I generate the Jmp here, and remember it in link. Link is used
1257 when optimizing Proj. */
1258 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1259 /* We might generate an endless loop, so keep it alive. */
1260 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1261 } else if ((get_irn_op(a) == op_Eor)
1262 && (get_irn_mode(a) == mode_b)
1263 && (classify_tarval(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1264 /* The Eor is a negate. Generate a new Cond without the negate,
1265 simulate the negate by exchanging the results. */
1266 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1268 } else if ((get_irn_op(a) == op_Not)
1269 && (get_irn_mode(a) == mode_b)) {
1270 /* A Not before the Cond. Generate a new Cond without the Not,
1271 simulate the Not by exchanging the results. */
1272 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1278 static ir_node *transform_node_Eor(ir_node *n)
1280 ir_node *a = get_Eor_left(n);
1281 ir_node *b = get_Eor_right(n);
1283 if ((get_irn_mode(n) == mode_b)
1284 && (get_irn_op(a) == op_Proj)
1285 && (get_irn_mode(a) == mode_b)
1286 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE)
1287 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1288 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1289 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1290 mode_b, get_negated_pnc(get_Proj_proj(a)));
1291 else if ((get_irn_mode(n) == mode_b)
1292 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE))
1293 /* The Eor is a Not. Replace it by a Not. */
1294 /* ????!!!Extend to bitfield 1111111. */
1295 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1301 * Transform a boolean Not.
1303 static ir_node *transform_node_Not(ir_node *n)
1305 ir_node *a = get_Not_op(n);
1307 if ( (get_irn_mode(n) == mode_b)
1308 && (get_irn_op(a) == op_Proj)
1309 && (get_irn_mode(a) == mode_b)
1310 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1311 /* We negate a Cmp. The Cmp has the negated result anyways! */
1312 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1313 mode_b, get_negated_pnc(get_Proj_proj(a)));
1318 static ir_node *transform_node_Cast(ir_node *n) {
1319 ir_node *pred = get_Cast_op(n);
1320 type *tp = get_irn_type(pred);
1321 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1322 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1323 get_Const_tarval(pred), tp);
1324 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1325 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1326 get_SymConst_kind(pred), tp);
1332 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1333 * done here instead of equivalent node because it creates new
1335 * Removes the exceptions and routes the memory to the initial mem.
1337 * Further, it optimizes jump tables by removing all impossible cases.
1339 static ir_node *transform_node_Proj(ir_node *proj)
1341 ir_node *n = get_Proj_pred(proj);
1346 switch (get_irn_opcode(n)) {
1348 b = get_Div_right(n);
1349 tb = computed_value(b);
1351 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1352 proj_nr = get_Proj_proj(proj);
1354 /* this node may float */
1355 set_irn_pinned(n, op_pin_state_floats);
1357 if (proj_nr == pn_Div_X_except) {
1358 /* we found an exception handler, remove it */
1362 /* the memory Proj can be removed */
1363 ir_node *res = get_Div_mem(n);
1364 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1366 if (proj_nr == pn_Div_M)
1372 b = get_Mod_right(n);
1373 tb = computed_value(b);
1375 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1376 proj_nr = get_Proj_proj(proj);
1378 /* this node may float */
1379 set_irn_pinned(n, op_pin_state_floats);
1381 if (proj_nr == pn_Mod_X_except) {
1382 /* we found an exception handler, remove it */
1386 /* the memory Proj can be removed */
1387 ir_node *res = get_Mod_mem(n);
1388 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1389 if (proj_nr == pn_Mod_M)
1395 b = get_DivMod_right(n);
1396 tb = computed_value(b);
1398 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1399 proj_nr = get_Proj_proj(proj);
1401 /* this node may float */
1402 set_irn_pinned(n, op_pin_state_floats);
1404 if (proj_nr == pn_DivMod_X_except) {
1405 /* we found an exception handler, remove it */
1409 /* the memory Proj can be removed */
1410 ir_node *res = get_DivMod_mem(n);
1411 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1412 if (proj_nr == pn_DivMod_M)
1419 if (get_opt_unreachable_code()) {
1420 b = get_Cond_selector(n);
1421 tb = computed_value(b);
1423 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1424 /* we have a constant switch */
1425 long num = get_Proj_proj(proj);
1427 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1428 if (get_tarval_long(tb) == num) {
1429 /* Do NOT create a jump here, or we will have 2 control flow ops
1430 * in a block. This case is optimized away in optimize_cf(). */
1441 /* should not happen, but if it does will be optimized away */
1449 /* we have added a Tuple, optimize it for the current Proj away */
1450 return equivalent_node_Proj(proj);
1454 * returns the operands of a commutative bin-op, if one operand is
1455 * a const, it is returned as the second one.
1457 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1459 ir_node *op_a = get_binop_left(binop);
1460 ir_node *op_b = get_binop_right(binop);
1462 assert(is_op_commutative(get_irn_op(binop)));
1464 if (get_irn_op(op_a) == op_Const) {
1475 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1476 * Such pattern may arise in bitfield stores.
1478 * value c4 value c4 & c2
1479 * AND c3 AND c1 | c3
1484 static ir_node *transform_node_Or(ir_node *or)
1488 ir_node *and_l, *c3;
1489 ir_node *value, *c4;
1490 ir_node *new_and, *new_const, *block;
1491 ir_mode *mode = get_irn_mode(or);
1493 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1495 get_comm_Binop_Ops(or, &and, &c1);
1496 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1499 get_comm_Binop_Ops(and, &or_l, &c2);
1500 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1503 get_comm_Binop_Ops(or_l, &and_l, &c3);
1504 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1507 get_comm_Binop_Ops(and_l, &value, &c4);
1508 if (get_irn_op(c4) != op_Const)
1511 /* ok, found the pattern, check for conditions */
1512 assert(mode == get_irn_mode(and));
1513 assert(mode == get_irn_mode(or_l));
1514 assert(mode == get_irn_mode(and_l));
1516 tv1 = get_Const_tarval(c1);
1517 tv2 = get_Const_tarval(c2);
1518 tv3 = get_Const_tarval(c3);
1519 tv4 = get_Const_tarval(c4);
1521 tv = tarval_or(tv4, tv2);
1522 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1523 /* have at least one 0 at the same bit position */
1527 n_tv4 = tarval_not(tv4);
1528 if (tv3 != tarval_and(tv3, n_tv4)) {
1529 /* bit in the or_mask is outside the and_mask */
1533 n_tv2 = tarval_not(tv2);
1534 if (tv1 != tarval_and(tv1, n_tv2)) {
1535 /* bit in the or_mask is outside the and_mask */
1539 /* ok, all conditions met */
1540 block = get_nodes_block(or);
1542 new_and = new_r_And(current_ir_graph, block,
1543 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1545 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1547 set_Or_left(or, new_and);
1548 set_Or_right(or, new_const);
1550 /* check for more */
1551 return transform_node_Or(or);
1555 static ir_node *transform_node(ir_node *n);
1558 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1560 static ir_node * transform_node_shift(ir_node *n)
1563 tarval *tv1, *tv2, *res;
1565 int modulo_shf, flag;
1567 left = get_binop_left(n);
1569 /* different operations */
1570 if (get_irn_op(left) != get_irn_op(n))
1573 tv1 = computed_value(get_binop_right(n));
1574 if (tv1 == tarval_bad)
1577 tv2 = computed_value(get_binop_right(left));
1578 if (tv2 == tarval_bad)
1581 res = tarval_add(tv1, tv2);
1583 /* beware: a simple replacement works only, if res < modulo shift */
1584 mode = get_irn_mode(n);
1588 modulo_shf = get_mode_modulo_shift(mode);
1589 if (modulo_shf > 0) {
1590 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1592 if (tarval_cmp(res, modulo) & Lt)
1599 /* ok, we can replace it */
1600 ir_node *in[2], *irn, *block = get_nodes_block(n);
1602 in[0] = get_binop_left(left);
1603 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1605 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1607 return transform_node(irn);
1614 * Tries several [inplace] [optimizing] transformations and returns an
1615 * equivalent node. The difference to equivalent_node() is that these
1616 * transformations _do_ generate new nodes, and thus the old node must
1617 * not be freed even if the equivalent node isn't the old one.
1619 static ir_node *transform_node(ir_node *n)
1621 if (n->op->transform_node)
1622 n = n->op->transform_node(n);
1627 * set the default transform node operation
1629 static ir_op *firm_set_default_transform_node(ir_op *op)
1633 op->transform_node = transform_node_##a; \
1650 op->transform_node = transform_node_shift;
1653 op->transform_node = NULL;
1661 /* **************** Common Subexpression Elimination **************** */
1663 /** The size of the hash table used, should estimate the number of nodes
1665 #define N_IR_NODES 512
1667 /** Compares the attributes of two Const nodes. */
1668 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1670 return (get_Const_tarval(a) != get_Const_tarval(b))
1671 || (get_Const_type(a) != get_Const_type(b));
1674 /** Compares the attributes of two Proj nodes. */
1675 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1677 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1680 /** Compares the attributes of two Filter nodes. */
1681 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1683 return get_Filter_proj(a) != get_Filter_proj(b);
1686 /** Compares the attributes of two Alloc nodes. */
1687 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1689 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1690 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1693 /** Compares the attributes of two Free nodes. */
1694 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1696 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1699 /** Compares the attributes of two SymConst nodes. */
1700 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1702 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1703 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1704 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1707 /** Compares the attributes of two Call nodes. */
1708 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1710 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1713 /** Compares the attributes of two FuncCall nodes. */
1714 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1716 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1719 /** Compares the attributes of two Sel nodes. */
1720 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1722 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1723 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1724 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1725 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1726 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1729 /** Compares the attributes of two Phi nodes. */
1730 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1732 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1735 /** Compares the attributes of two Cast nodes. */
1736 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1738 return get_Cast_type(a) != get_Cast_type(b);
1741 /** Compares the attributes of two Load nodes. */
1742 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1744 if (get_Load_volatility(a) == volatility_is_volatile ||
1745 get_Load_volatility(b) == volatility_is_volatile)
1746 /* NEVER do CSE on volatile Loads */
1749 return get_Load_mode(a) != get_Load_mode(b);
1752 /** Compares the attributes of two Store nodes. */
1753 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1755 /* NEVER do CSE on volatile Stores */
1756 return (get_Store_volatility(a) == volatility_is_volatile ||
1757 get_Store_volatility(b) == volatility_is_volatile);
1761 * set the default node attribute compare operation
1763 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1767 op->node_cmp_attr = node_cmp_attr_##a; \
1785 op->node_cmp_attr = NULL;
1793 * Compare function for two nodes in the hash table. Gets two
1794 * nodes as parameters. Returns 0 if the nodes are a cse.
1797 vt_cmp (const void *elt, const void *key)
1805 if (a == b) return 0;
1807 if ((get_irn_op(a) != get_irn_op(b)) ||
1808 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1810 /* compare if a's in and b's in are equal */
1811 irn_arity_a = get_irn_arity (a);
1812 if (irn_arity_a != get_irn_arity(b))
1815 /* for block-local cse and op_pin_state_pinned nodes: */
1816 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1817 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1821 /* compare a->in[0..ins] with b->in[0..ins] */
1822 for (i = 0; i < irn_arity_a; i++)
1823 if (get_irn_n(a, i) != get_irn_n(b, i))
1827 * here, we already now that the nodes are identical except their
1830 if (a->op->node_cmp_attr)
1831 return a->op->node_cmp_attr(a, b);
1837 * Calculate a hash value of a node.
1840 ir_node_hash (ir_node *node)
1845 if (node->op == op_Const) {
1846 /* special value for const, as they only differ in their tarval. */
1847 h = ((unsigned) node->attr.con.tv)>>3 ;
1848 h = 9*h + (unsigned)get_irn_mode(node);
1849 } else if (node->op == op_SymConst) {
1850 /* special value for const, as they only differ in their symbol. */
1851 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1852 h = 9*h + (unsigned)get_irn_mode(node);
1855 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1856 h = irn_arity = get_irn_arity(node);
1858 /* consider all in nodes... except the block. */
1859 for (i = 0; i < irn_arity; i++) {
1860 h = 9*h + (unsigned)get_irn_n(node, i);
1864 h = 9*h + (unsigned) get_irn_mode (node);
1866 h = 9*h + (unsigned) get_irn_op (node);
1873 new_identities (void)
1875 return new_pset (vt_cmp, N_IR_NODES);
1879 del_identities (pset *value_table)
1881 del_pset (value_table);
1885 * Return the canonical node computing the same value as n.
1886 * Looks up the node in a hash table.
1888 * For Const nodes this is performed in the constructor, too. Const
1889 * nodes are extremely time critical because of their frequent use in
1890 * constant string arrays.
1892 static INLINE ir_node *
1893 identify (pset *value_table, ir_node *n)
1897 if (!value_table) return n;
1899 if (get_opt_reassociation()) {
1900 if (is_op_commutative(get_irn_op(n))) {
1901 ir_node *l = get_binop_left(n);
1902 ir_node *r = get_binop_right(n);
1904 /* for commutative operators perform a OP b == b OP a */
1906 set_binop_left(n, r);
1907 set_binop_right(n, l);
1912 o = pset_find (value_table, n, ir_node_hash (n));
1921 * During construction we set the op_pin_state_pinned flag in the graph right when the
1922 * optimization is performed. The flag turning on procedure global cse could
1923 * be changed between two allocations. This way we are safe.
1925 static INLINE ir_node *
1926 identify_cons (pset *value_table, ir_node *n) {
1929 n = identify(value_table, n);
1930 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1931 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1936 * Return the canonical node computing the same value as n.
1937 * Looks up the node in a hash table, enters it in the table
1938 * if it isn't there yet.
1941 identify_remember (pset *value_table, ir_node *n)
1945 if (!value_table) return n;
1947 if (get_opt_reassociation()) {
1948 if (is_op_commutative(get_irn_op(n))) {
1949 ir_node *l = get_binop_left(n);
1950 ir_node *r = get_binop_right(n);
1952 /* for commutative operators perform a OP b == b OP a */
1954 set_binop_left(n, r);
1955 set_binop_right(n, l);
1960 /* lookup or insert in hash table with given hash key. */
1961 o = pset_insert (value_table, n, ir_node_hash (n));
1971 add_identities (pset *value_table, ir_node *node) {
1972 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1973 identify_remember (value_table, node);
1977 * garbage in, garbage out. If a node has a dead input, i.e., the
1978 * Bad node is input to the node, return the Bad node.
1980 static INLINE ir_node *
1981 gigo (ir_node *node)
1984 ir_op* op = get_irn_op(node);
1986 /* remove garbage blocks by looking at control flow that leaves the block
1987 and replacing the control flow by Bad. */
1988 if (get_irn_mode(node) == mode_X) {
1989 ir_node *block = get_nodes_block(node);
1990 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1991 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1992 irn_arity = get_irn_arity(block);
1993 for (i = 0; i < irn_arity; i++) {
1994 if (!is_Bad(get_irn_n(block, i))) break;
1996 if (i == irn_arity) return new_Bad();
2000 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2001 blocks predecessors is dead. */
2002 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2003 irn_arity = get_irn_arity(node);
2004 for (i = -1; i < irn_arity; i++) {
2005 if (is_Bad(get_irn_n(node, i))) {
2011 /* With this code we violate the agreement that local_optimize
2012 only leaves Bads in Block, Phi and Tuple nodes. */
2013 /* If Block has only Bads as predecessors it's garbage. */
2014 /* If Phi has only Bads as predecessors it's garbage. */
2015 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2016 irn_arity = get_irn_arity(node);
2017 for (i = 0; i < irn_arity; i++) {
2018 if (!is_Bad(get_irn_n(node, i))) break;
2020 if (i == irn_arity) node = new_Bad();
2028 * These optimizations deallocate nodes from the obstack.
2029 * It can only be called if it is guaranteed that no other nodes
2030 * reference this one, i.e., right after construction of a node.
2033 optimize_node (ir_node *n)
2037 opcode iro = get_irn_opcode(n);
2039 type *old_tp = get_irn_type(n);
2041 int i, arity = get_irn_arity(n);
2042 for (i = 0; i < arity && !old_tp; ++i)
2043 old_tp = get_irn_type(get_irn_n(n, i));
2046 /* Allways optimize Phi nodes: part of the construction. */
2047 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2049 /* constant expression evaluation / constant folding */
2050 if (get_opt_constant_folding()) {
2051 /* constants can not be evaluated */
2052 if (iro != iro_Const) {
2053 /* try to evaluate */
2054 tv = computed_value (n);
2055 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2057 * we MUST copy the node here temporary, because it's still needed
2058 * for DBG_OPT_ALGSIM0
2060 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2061 oldn = alloca(node_size);
2063 memcpy(oldn, n, node_size);
2064 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2066 /* ARG, copy the in array, we need it for statistics */
2067 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2069 /* evaluation was successful -- replace the node. */
2070 obstack_free (current_ir_graph->obst, n);
2071 n = new_Const (get_tarval_mode (tv), tv);
2072 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2073 set_Const_type(n, old_tp);
2074 DBG_OPT_ALGSIM0(oldn, n);
2080 /* remove unnecessary nodes */
2081 if (get_opt_constant_folding() ||
2082 (iro == iro_Phi) || /* always optimize these nodes. */
2084 (iro == iro_Proj) ||
2085 (iro == iro_Block) ) /* Flags tested local. */
2086 n = equivalent_node (n);
2088 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2090 /** common subexpression elimination **/
2091 /* Checks whether n is already available. */
2092 /* The block input is used to distinguish different subexpressions. Right
2093 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2094 subexpressions within a block. */
2096 n = identify_cons (current_ir_graph->value_table, n);
2099 /* We found an existing, better node, so we can deallocate the old node. */
2100 obstack_free (current_ir_graph->obst, oldn);
2105 /* Some more constant expression evaluation that does not allow to
2107 iro = get_irn_opcode(n);
2108 if (get_opt_constant_folding() ||
2109 (iro == iro_Cond) ||
2110 (iro == iro_Proj)) /* Flags tested local. */
2111 n = transform_node (n);
2113 /* Remove nodes with dead (Bad) input.
2114 Run always for transformation induced Bads. */
2117 /* Now we have a legal, useful node. Enter it in hash table for cse */
2118 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2119 n = identify_remember (current_ir_graph->value_table, n);
2127 * These optimizations never deallocate nodes. This can cause dead
2128 * nodes lying on the obstack. Remove these by a dead node elimination,
2129 * i.e., a copying garbage collection.
2132 optimize_in_place_2 (ir_node *n)
2136 opcode iro = get_irn_opcode(n);
2138 type *old_tp = get_irn_type(n);
2140 int i, arity = get_irn_arity(n);
2141 for (i = 0; i < arity && !old_tp; ++i)
2142 old_tp = get_irn_type(get_irn_n(n, i));
2145 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2147 /* if not optimize return n */
2150 /* Here this is possible. Why? */
2154 /* constant expression evaluation / constant folding */
2155 if (get_opt_constant_folding()) {
2156 /* constants can not be evaluated */
2157 if (iro != iro_Const) {
2158 /* try to evaluate */
2159 tv = computed_value (n);
2160 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2161 /* evaluation was successful -- replace the node. */
2162 n = new_Const (get_tarval_mode (tv), tv);
2163 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2164 set_Const_type(n, old_tp);
2165 DBG_OPT_ALGSIM0(oldn, n);
2171 /* remove unnecessary nodes */
2172 if (get_opt_constant_folding() ||
2173 (iro == iro_Phi) || /* always optimize these nodes. */
2174 (iro == iro_Id) || /* ... */
2175 (iro == iro_Proj) || /* ... */
2176 (iro == iro_Block) ) /* Flags tested local. */
2177 n = equivalent_node (n);
2179 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2181 /** common subexpression elimination **/
2182 /* Checks whether n is already available. */
2183 /* The block input is used to distinguish different subexpressions. Right
2184 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2185 subexpressions within a block. */
2186 if (get_opt_cse()) {
2187 n = identify (current_ir_graph->value_table, n);
2190 /* Some more constant expression evaluation. */
2191 iro = get_irn_opcode(n);
2192 if (get_opt_constant_folding() ||
2193 (iro == iro_Cond) ||
2194 (iro == iro_Proj)) /* Flags tested local. */
2195 n = transform_node (n);
2197 /* Remove nodes with dead (Bad) input.
2198 Run always for transformation induced Bads. */
2201 /* Now we can verify the node, as it has no dead inputs any more. */
2204 /* Now we have a legal, useful node. Enter it in hash table for cse.
2205 Blocks should be unique anyways. (Except the successor of start:
2206 is cse with the start block!) */
2207 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2208 n = identify_remember (current_ir_graph->value_table, n);
2214 * Wrapper for external use, set proper status bits after optimization.
2217 optimize_in_place (ir_node *n)
2219 /* Handle graph state */
2220 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2222 if (get_opt_global_cse())
2223 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2224 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2225 set_irg_outs_inconsistent(current_ir_graph);
2227 /* Maybe we could also test whether optimizing the node can
2228 change the control graph. */
2229 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2230 set_irg_dom_inconsistent(current_ir_graph);
2231 return optimize_in_place_2 (n);
2235 * set the default ir op operations
2237 ir_op *firm_set_default_operations(ir_op *op)
2239 op = firm_set_default_computed_value(op);
2240 op = firm_set_default_equivalent_node(op);
2241 op = firm_set_default_transform_node(op);
2242 op = firm_set_default_node_cmp_attr(op);