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_with_shifts(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_with_shifts(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_with_shifts(&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 if (proj_nr == pn_Div_X_except) {
1334 /* we found an exception handler, remove it */
1338 /* the memory Proj can be removed */
1339 ir_node *res = get_Div_mem(n);
1340 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1341 if (proj_nr == pn_Div_M)
1347 b = get_Mod_right(n);
1348 tb = computed_value(b);
1350 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1351 proj_nr = get_Proj_proj(proj);
1353 if (proj_nr == pn_Mod_X_except) {
1354 /* we found an exception handler, remove it */
1358 /* the memory Proj can be removed */
1359 ir_node *res = get_Mod_mem(n);
1360 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1361 if (proj_nr == pn_Mod_M)
1367 b = get_DivMod_right(n);
1368 tb = computed_value(b);
1370 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1371 proj_nr = get_Proj_proj(proj);
1373 if (proj_nr == pn_DivMod_X_except) {
1374 /* we found an exception handler, remove it */
1378 /* the memory Proj can be removed */
1379 ir_node *res = get_DivMod_mem(n);
1380 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1381 if (proj_nr == pn_DivMod_M)
1388 if (get_opt_unreachable_code()) {
1389 b = get_Cond_selector(n);
1390 tb = computed_value(b);
1392 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1393 /* we have a constant switch */
1394 long num = get_Proj_proj(proj);
1396 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1397 if (get_tarval_long(tb) == num) {
1398 /* Do NOT create a jump here, or we will have 2 control flow ops
1399 * in a block. This case is optimized away in optimize_cf(). */
1410 /* should not happen, but if it does will be optimized away */
1418 /* we have added a Tuple, optimize it for the current Proj away */
1419 return equivalent_node_Proj(proj);
1423 * returns the operands of a commutative bin-op, if one operand is
1424 * a const, it is returned as the second one.
1426 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1428 ir_node *op_a = get_binop_left(binop);
1429 ir_node *op_b = get_binop_right(binop);
1431 assert(is_op_commutative(get_irn_op(binop)));
1433 if (get_irn_op(op_a) == op_Const) {
1444 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1445 * Such pattern may arise in bitfield stores.
1447 * value c4 value c4 & c2
1448 * AND c3 AND c1 | c3
1453 static ir_node *transform_node_Or(ir_node *or)
1457 ir_node *and_l, *c3;
1458 ir_node *value, *c4;
1459 ir_node *new_and, *new_const, *block;
1460 ir_mode *mode = get_irn_mode(or);
1462 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1464 get_comm_Binop_Ops(or, &and, &c1);
1465 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1468 get_comm_Binop_Ops(and, &or_l, &c2);
1469 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1472 get_comm_Binop_Ops(or_l, &and_l, &c3);
1473 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1476 get_comm_Binop_Ops(and_l, &value, &c4);
1477 if (get_irn_op(c4) != op_Const)
1480 /* ok, found the pattern, check for conditions */
1481 assert(mode == get_irn_mode(and));
1482 assert(mode == get_irn_mode(or_l));
1483 assert(mode == get_irn_mode(and_l));
1485 tv1 = get_Const_tarval(c1);
1486 tv2 = get_Const_tarval(c2);
1487 tv3 = get_Const_tarval(c3);
1488 tv4 = get_Const_tarval(c4);
1490 tv = tarval_or(tv4, tv2);
1491 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1492 /* have at least one 0 at the same bit position */
1496 n_tv4 = tarval_not(tv4);
1497 if (tv3 != tarval_and(tv3, n_tv4)) {
1498 /* bit in the or_mask is outside the and_mask */
1502 n_tv2 = tarval_not(tv2);
1503 if (tv1 != tarval_and(tv1, n_tv2)) {
1504 /* bit in the or_mask is outside the and_mask */
1508 /* ok, all conditions met */
1509 block = get_nodes_block(or);
1511 new_and = new_r_And(current_ir_graph, block,
1512 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1514 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1516 set_Or_left(or, new_and);
1517 set_Or_right(or, new_const);
1519 /* check for more */
1520 return transform_node_Or(or);
1524 * Tries several [inplace] [optimizing] transformations and returns an
1525 * equivalent node. The difference to equivalent_node() is that these
1526 * transformations _do_ generate new nodes, and thus the old node must
1527 * not be freed even if the equivalent node isn't the old one.
1529 static ir_node *transform_node(ir_node *n)
1531 if (n->op->transform_node)
1532 n = n->op->transform_node(n);
1537 * set the default transform node operation
1539 static ir_op *firm_set_default_transform_node(ir_op *op)
1543 op->transform_node = transform_node_##a; \
1557 op->transform_node = NULL;
1565 /* **************** Common Subexpression Elimination **************** */
1567 /** The size of the hash table used, should estimate the number of nodes
1569 #define N_IR_NODES 512
1571 /** Compares the attributes of two Const nodes. */
1572 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1574 return (get_Const_tarval(a) != get_Const_tarval(b))
1575 || (get_Const_type(a) != get_Const_type(b));
1578 /** Compares the attributes of two Proj nodes. */
1579 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1581 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1584 /** Compares the attributes of two Filter nodes. */
1585 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1587 return get_Filter_proj(a) != get_Filter_proj(b);
1590 /** Compares the attributes of two Alloc nodes. */
1591 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1593 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1594 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1597 /** Compares the attributes of two Free nodes. */
1598 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1600 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1603 /** Compares the attributes of two SymConst nodes. */
1604 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1606 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1607 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1610 /** Compares the attributes of two Call nodes. */
1611 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1613 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1616 /** Compares the attributes of two FuncCall nodes. */
1617 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1619 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1622 /** Compares the attributes of two Sel nodes. */
1623 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1625 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1626 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1627 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1628 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1629 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1632 /** Compares the attributes of two Phi nodes. */
1633 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1635 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1638 /** Compares the attributes of two Cast nodes. */
1639 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1641 return get_Cast_type(a) != get_Cast_type(b);
1644 /** Compares the attributes of two Load nodes. */
1645 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1647 if (get_Load_volatility(a) == volatility_is_volatile ||
1648 get_Load_volatility(b) == volatility_is_volatile)
1649 /* NEVER do CSE on volatile Loads */
1652 return get_Load_mode(a) != get_Load_mode(b);
1655 /** Compares the attributes of two Store nodes. */
1656 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1658 /* NEVER do CSE on volatile Stores */
1659 return (get_Store_volatility(a) == volatility_is_volatile ||
1660 get_Load_volatility(b) == volatility_is_volatile);
1664 * set the default node attribute compare operation
1666 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1670 op->node_cmp_attr = node_cmp_attr_##a; \
1688 op->node_cmp_attr = NULL;
1696 * Compare function for two nodes in the hash table. Gets two
1697 * nodes as parameters. Returns 0 if the nodes are a cse.
1700 vt_cmp (const void *elt, const void *key)
1708 if (a == b) return 0;
1710 if ((get_irn_op(a) != get_irn_op(b)) ||
1711 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1713 /* compare if a's in and b's in are equal */
1714 irn_arity_a = get_irn_arity (a);
1715 if (irn_arity_a != get_irn_arity(b))
1718 /* for block-local cse and op_pin_state_pinned nodes: */
1719 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1720 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1724 /* compare a->in[0..ins] with b->in[0..ins] */
1725 for (i = 0; i < irn_arity_a; i++)
1726 if (get_irn_n(a, i) != get_irn_n(b, i))
1730 * here, we already now that the nodes are identical except their
1733 if (a->op->node_cmp_attr)
1734 return a->op->node_cmp_attr(a, b);
1740 * Calculate a hash value of a node.
1743 ir_node_hash (ir_node *node)
1748 if (node->op == op_Const) {
1749 /* special value for const, as they only differ in their tarval. */
1750 h = ((unsigned) node->attr.con.tv)>>3 ;
1751 h = 9*h + (unsigned)get_irn_mode(node);
1752 } else if (node->op == op_SymConst) {
1753 /* special value for const, as they only differ in their symbol. */
1754 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1755 h = 9*h + (unsigned)get_irn_mode(node);
1758 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1759 h = irn_arity = get_irn_arity(node);
1761 /* consider all in nodes... except the block. */
1762 for (i = 0; i < irn_arity; i++) {
1763 h = 9*h + (unsigned)get_irn_n(node, i);
1767 h = 9*h + (unsigned) get_irn_mode (node);
1769 h = 9*h + (unsigned) get_irn_op (node);
1776 new_identities (void)
1778 return new_pset (vt_cmp, N_IR_NODES);
1782 del_identities (pset *value_table)
1784 del_pset (value_table);
1788 * Return the canonical node computing the same value as n.
1789 * Looks up the node in a hash table.
1791 * For Const nodes this is performed in the constructor, too. Const
1792 * nodes are extremely time critical because of their frequent use in
1793 * constant string arrays.
1795 static INLINE ir_node *
1796 identify (pset *value_table, ir_node *n)
1800 if (!value_table) return n;
1802 if (get_opt_reassociation()) {
1803 if (is_op_commutative(get_irn_op(n))) {
1804 ir_node *l = get_binop_left(n);
1805 ir_node *r = get_binop_right(n);
1807 /* for commutative operators perform a OP b == b OP a */
1809 set_binop_left(n, r);
1810 set_binop_right(n, l);
1815 o = pset_find (value_table, n, ir_node_hash (n));
1824 * During construction we set the op_pin_state_pinned flag in the graph right when the
1825 * optimization is performed. The flag turning on procedure global cse could
1826 * be changed between two allocations. This way we are safe.
1828 static INLINE ir_node *
1829 identify_cons (pset *value_table, ir_node *n) {
1832 n = identify(value_table, n);
1833 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1834 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1839 * Return the canonical node computing the same value as n.
1840 * Looks up the node in a hash table, enters it in the table
1841 * if it isn't there yet.
1844 identify_remember (pset *value_table, ir_node *n)
1848 if (!value_table) return n;
1850 if (get_opt_reassociation()) {
1851 if (is_op_commutative(get_irn_op(n))) {
1852 ir_node *l = get_binop_left(n);
1853 ir_node *r = get_binop_right(n);
1855 /* for commutative operators perform a OP b == b OP a */
1857 set_binop_left(n, r);
1858 set_binop_right(n, l);
1863 /* lookup or insert in hash table with given hash key. */
1864 o = pset_insert (value_table, n, ir_node_hash (n));
1874 add_identities (pset *value_table, ir_node *node) {
1875 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
1876 identify_remember (value_table, node);
1880 * garbage in, garbage out. If a node has a dead input, i.e., the
1881 * Bad node is input to the node, return the Bad node.
1883 static INLINE ir_node *
1884 gigo (ir_node *node)
1887 ir_op* op = get_irn_op(node);
1889 /* remove garbage blocks by looking at control flow that leaves the block
1890 and replacing the control flow by Bad. */
1891 if (get_irn_mode(node) == mode_X) {
1892 ir_node *block = get_nodes_block(node);
1893 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1894 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1895 irn_arity = get_irn_arity(block);
1896 for (i = 0; i < irn_arity; i++) {
1897 if (!is_Bad(get_irn_n(block, i))) break;
1899 if (i == irn_arity) return new_Bad();
1903 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1904 blocks predecessors is dead. */
1905 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1906 irn_arity = get_irn_arity(node);
1907 for (i = -1; i < irn_arity; i++) {
1908 if (is_Bad(get_irn_n(node, i))) {
1914 /* With this code we violate the agreement that local_optimize
1915 only leaves Bads in Block, Phi and Tuple nodes. */
1916 /* If Block has only Bads as predecessors it's garbage. */
1917 /* If Phi has only Bads as predecessors it's garbage. */
1918 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1919 irn_arity = get_irn_arity(node);
1920 for (i = 0; i < irn_arity; i++) {
1921 if (!is_Bad(get_irn_n(node, i))) break;
1923 if (i == irn_arity) node = new_Bad();
1931 * These optimizations deallocate nodes from the obstack.
1932 * It can only be called if it is guaranteed that no other nodes
1933 * reference this one, i.e., right after construction of a node.
1936 optimize_node (ir_node *n)
1940 opcode iro = get_irn_opcode(n);
1942 /* Always optimize Phi nodes: part of the construction. */
1943 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1945 /* constant expression evaluation / constant folding */
1946 if (get_opt_constant_folding()) {
1947 /* constants can not be evaluated */
1948 if (iro != iro_Const) {
1949 /* try to evaluate */
1950 tv = computed_value (n);
1951 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1953 * we MUST copy the node here temporary, because it's still needed
1954 * for DBG_OPT_ALGSIM0
1956 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1957 oldn = alloca(node_size);
1959 memcpy(oldn, n, node_size);
1960 CLONE_ARR_A(ir_node *, oldn->in, n->in);
1962 /* ARG, copy the in array, we need it for statistics */
1963 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
1965 /* evaluation was successful -- replace the node. */
1966 obstack_free (current_ir_graph->obst, n);
1967 n = new_Const (get_tarval_mode (tv), tv);
1969 DBG_OPT_ALGSIM0(oldn, n);
1975 /* remove unnecessary nodes */
1976 if (get_opt_constant_folding() ||
1977 (iro == iro_Phi) || /* always optimize these nodes. */
1979 (iro == iro_Proj) ||
1980 (iro == iro_Block) ) /* Flags tested local. */
1981 n = equivalent_node (n);
1983 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1985 /** common subexpression elimination **/
1986 /* Checks whether n is already available. */
1987 /* The block input is used to distinguish different subexpressions. Right
1988 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1989 subexpressions within a block. */
1991 n = identify_cons (current_ir_graph->value_table, n);
1994 /* We found an existing, better node, so we can deallocate the old node. */
1995 obstack_free (current_ir_graph->obst, oldn);
2000 /* Some more constant expression evaluation that does not allow to
2002 iro = get_irn_opcode(n);
2003 if (get_opt_constant_folding() ||
2004 (iro == iro_Cond) ||
2005 (iro == iro_Proj)) /* Flags tested local. */
2006 n = transform_node (n);
2008 /* Remove nodes with dead (Bad) input.
2009 Run always for transformation induced Bads. */
2012 /* Now we have a legal, useful node. Enter it in hash table for cse */
2013 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2014 n = identify_remember (current_ir_graph->value_table, n);
2022 * These optimizations never deallocate nodes. This can cause dead
2023 * nodes lying on the obstack. Remove these by a dead node elimination,
2024 * i.e., a copying garbage collection.
2027 optimize_in_place_2 (ir_node *n)
2031 opcode iro = get_irn_opcode(n);
2033 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2035 /* if not optimize return n */
2038 /* Here this is possible. Why? */
2043 /* constant expression evaluation / constant folding */
2044 if (get_opt_constant_folding()) {
2045 /* constants can not be evaluated */
2046 if (iro != iro_Const) {
2047 /* try to evaluate */
2048 tv = computed_value (n);
2049 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2050 /* evaluation was successful -- replace the node. */
2051 n = new_Const (get_tarval_mode (tv), tv);
2053 DBG_OPT_ALGSIM0(oldn, n);
2059 /* remove unnecessary nodes */
2060 if (get_opt_constant_folding() ||
2061 (iro == iro_Phi) || /* always optimize these nodes. */
2062 (iro == iro_Id) || /* ... */
2063 (iro == iro_Proj) || /* ... */
2064 (iro == iro_Block) ) /* Flags tested local. */
2065 n = equivalent_node (n);
2067 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2069 /** common subexpression elimination **/
2070 /* Checks whether n is already available. */
2071 /* The block input is used to distinguish different subexpressions. Right
2072 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2073 subexpressions within a block. */
2074 if (get_opt_cse()) {
2075 n = identify (current_ir_graph->value_table, n);
2078 /* Some more constant expression evaluation. */
2079 iro = get_irn_opcode(n);
2080 if (get_opt_constant_folding() ||
2081 (iro == iro_Cond) ||
2082 (iro == iro_Proj)) /* Flags tested local. */
2083 n = transform_node (n);
2085 /* Remove nodes with dead (Bad) input.
2086 Run always for transformation induced Bads. */
2089 /* Now we can verify the node, as it has no dead inputs any more. */
2092 /* Now we have a legal, useful node. Enter it in hash table for cse.
2093 Blocks should be unique anyways. (Except the successor of start:
2094 is cse with the start block!) */
2095 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2096 n = identify_remember (current_ir_graph->value_table, n);
2102 * Wrapper for external use, set proper status bits after optimization.
2105 optimize_in_place (ir_node *n)
2107 /* Handle graph state */
2108 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2110 if (get_opt_global_cse())
2111 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2112 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2113 set_irg_outs_inconsistent(current_ir_graph);
2115 /* Maybe we could also test whether optimizing the node can
2116 change the control graph. */
2117 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2118 set_irg_dom_inconsistent(current_ir_graph);
2119 return optimize_in_place_2 (n);
2123 * set the default ir op operations
2125 ir_op *firm_set_default_operations(ir_op *op)
2127 op = firm_set_default_computed_value(op);
2128 op = firm_set_default_equivalent_node(op);
2129 op = firm_set_default_transform_node(op);
2130 op = firm_set_default_node_cmp_attr(op);