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.
27 # include "irnode_t.h"
28 # include "irgraph_t.h"
29 # include "irmode_t.h"
31 # include "ircons_t.h"
35 # include "dbginfo_t.h"
36 # include "iropt_dbg.h"
37 # include "irflag_t.h"
38 # include "firmstat.h"
42 /* Make types visible to allow most efficient access */
43 # include "entity_t.h"
45 # ifdef DO_HEAPANALYSIS
46 /* heapanal can't cope with NoMems */
47 # else /* if defined DO_HEAPANALYSIS */
49 # endif /* defined DO_HEAPANALYSIS */
52 * Trivial INLINEable routine for copy propagation.
53 * Does follow Ids, needed to optimize INLINEd code.
55 static INLINE ir_node *
56 follow_Id (ir_node *n)
58 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
63 * return the value of a Constant
65 static tarval *computed_value_Const(ir_node *n)
67 return get_Const_tarval(n);
71 * return the value of a 'sizeof' SymConst
73 static tarval *computed_value_SymConst(ir_node *n)
75 if ((get_SymConst_kind(n) == symconst_size) &&
76 (get_type_state(get_SymConst_type(n))) == layout_fixed)
77 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
82 * return the value of an Add
84 static tarval *computed_value_Add(ir_node *n)
86 ir_node *a = get_Add_left(n);
87 ir_node *b = get_Add_right(n);
89 tarval *ta = value_of(a);
90 tarval *tb = value_of(b);
92 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
93 return tarval_add(ta, tb);
99 * return the value of a Sub
100 * Special case: a - a
102 static tarval *computed_value_Sub(ir_node *n)
104 ir_node *a = get_Sub_left(n);
105 ir_node *b = get_Sub_right(n);
110 if (a == b && !is_Bad(a))
111 return get_tarval_null(get_irn_mode(n));
116 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
117 return tarval_sub(ta, tb);
123 * return the value of an unary Minus
125 static tarval *computed_value_Minus(ir_node *n)
127 ir_node *a = get_Minus_op(n);
128 tarval *ta = value_of(a);
130 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
131 return tarval_neg(ta);
137 * return the value of a Mul
139 static tarval *computed_value_Mul(ir_node *n)
141 ir_node *a = get_Mul_left(n);
142 ir_node *b = get_Mul_right(n);
144 tarval *ta = value_of(a);
145 tarval *tb = value_of(b);
147 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
148 return tarval_mul(ta, tb);
150 /* a*0 = 0 or 0*b = 0:
151 calls computed_value recursive and returns the 0 with proper
153 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
155 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
162 * return the value of a floating point Quot
164 static tarval *computed_value_Quot(ir_node *n)
166 ir_node *a = get_Quot_left(n);
167 ir_node *b = get_Quot_right(n);
169 tarval *ta = value_of(a);
170 tarval *tb = value_of(b);
172 /* This was missing in original implementation. Why? */
173 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
174 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
175 return tarval_quo(ta, tb);
181 * calculate the value of an integer Div of two nodes
182 * Special case: 0 / b
184 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
186 tarval *ta = value_of(a);
187 tarval *tb = value_of(b);
189 /* Compute c1 / c2 or 0 / a, a != 0 */
190 if (ta != tarval_bad) {
191 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
192 return tarval_div(ta, tb);
193 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
200 * return the value of an integer Div
202 static tarval *computed_value_Div(ir_node *n)
204 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
208 * calculate the value of an integer Mod of two nodes
209 * Special case: a % 1
211 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
213 tarval *ta = value_of(a);
214 tarval *tb = value_of(b);
216 /* Compute c1 % c2 or a % 1 */
217 if (tb != tarval_bad) {
218 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
219 return tarval_mod(ta, tb);
220 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
221 return get_mode_null(get_irn_mode(a));
228 * return the value of an integer Mod
230 static tarval *computed_value_Mod(ir_node *n)
232 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
236 * return the value of an Abs
238 static tarval *computed_value_Abs(ir_node *n)
240 ir_node *a = get_Abs_op(n);
241 tarval *ta = value_of(a);
243 if (ta != tarval_bad)
244 return tarval_abs(ta);
250 * return the value of an And
251 * Special case: a & 0, 0 & b
253 static tarval *computed_value_And(ir_node *n)
255 ir_node *a = get_And_left(n);
256 ir_node *b = get_And_right(n);
258 tarval *ta = value_of(a);
259 tarval *tb = value_of(b);
261 if ((ta != tarval_bad) && (tb != tarval_bad)) {
262 return tarval_and (ta, tb);
266 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
267 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
275 * return the value of an Or
276 * Special case: a | 1...1, 1...1 | b
278 static tarval *computed_value_Or(ir_node *n)
280 ir_node *a = get_Or_left(n);
281 ir_node *b = get_Or_right(n);
283 tarval *ta = value_of(a);
284 tarval *tb = value_of(b);
286 if ((ta != tarval_bad) && (tb != tarval_bad)) {
287 return tarval_or (ta, tb);
290 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
291 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
299 * return the value of an Eor
301 static tarval *computed_value_Eor(ir_node *n)
303 ir_node *a = get_Eor_left(n);
304 ir_node *b = get_Eor_right(n);
309 return get_tarval_null(get_irn_mode(n));
314 if ((ta != tarval_bad) && (tb != tarval_bad)) {
315 return tarval_eor (ta, tb);
321 * return the value of a Not
323 static tarval *computed_value_Not(ir_node *n)
325 ir_node *a = get_Not_op(n);
326 tarval *ta = value_of(a);
328 if (ta != tarval_bad)
329 return tarval_not(ta);
335 * return the value of a Shl
337 static tarval *computed_value_Shl(ir_node *n)
339 ir_node *a = get_Shl_left(n);
340 ir_node *b = get_Shl_right(n);
342 tarval *ta = value_of(a);
343 tarval *tb = value_of(b);
345 if ((ta != tarval_bad) && (tb != tarval_bad)) {
346 return tarval_shl (ta, tb);
352 * return the value of a Shr
354 static tarval *computed_value_Shr(ir_node *n)
356 ir_node *a = get_Shr_left(n);
357 ir_node *b = get_Shr_right(n);
359 tarval *ta = value_of(a);
360 tarval *tb = value_of(b);
362 if ((ta != tarval_bad) && (tb != tarval_bad)) {
363 return tarval_shr (ta, tb);
369 * return the value of a Shrs
371 static tarval *computed_value_Shrs(ir_node *n)
373 ir_node *a = get_Shrs_left(n);
374 ir_node *b = get_Shrs_right(n);
376 tarval *ta = value_of(a);
377 tarval *tb = value_of(b);
379 if ((ta != tarval_bad) && (tb != tarval_bad)) {
380 return tarval_shrs (ta, tb);
386 * return the value of a Rot
388 static tarval *computed_value_Rot(ir_node *n)
390 ir_node *a = get_Rot_left(n);
391 ir_node *b = get_Rot_right(n);
393 tarval *ta = value_of(a);
394 tarval *tb = value_of(b);
396 if ((ta != tarval_bad) && (tb != tarval_bad)) {
397 return tarval_rot (ta, tb);
403 * return the value of a Conv
405 static tarval *computed_value_Conv(ir_node *n)
407 ir_node *a = get_Conv_op(n);
408 tarval *ta = value_of(a);
410 if (ta != tarval_bad)
411 return tarval_convert_to(ta, get_irn_mode(n));
417 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
419 static tarval *computed_value_Proj(ir_node *n)
421 ir_node *a = get_Proj_pred(n);
425 /* Optimize Cmp nodes.
426 This performs a first step of unreachable code elimination.
427 Proj can not be computed, but folding a Cmp above the Proj here is
428 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
430 There are several case where we can evaluate a Cmp node:
431 1. The nodes compared are both the same. If we compare for
432 equal, greater equal, ... this will return true, else it
433 will return false. This step relies on cse.
434 2. The predecessors of Cmp are target values. We can evaluate
436 3. The predecessors are Allocs or void* constants. Allocs never
437 return NULL, they raise an exception. Therefore we can predict
439 switch (get_irn_opcode(a)) {
441 aa = get_Cmp_left(a);
442 ab = get_Cmp_right(a);
443 proj_nr = get_Proj_proj(n);
445 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
446 /* BEWARE: a == a is NOT always True for floating Point!!! */
447 /* This is a trick with the bits used for encoding the Cmp
448 Proj numbers, the following statement is not the same:
449 return new_tarval_from_long (proj_nr == Eq, mode_b) */
450 return new_tarval_from_long (proj_nr & Eq, mode_b);
452 tarval *taa = value_of(aa);
453 tarval *tab = value_of(ab);
455 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
456 /* strange checks... */
457 pnc_number flags = tarval_cmp (taa, tab);
458 if (flags != False) {
459 return new_tarval_from_long (proj_nr & flags, mode_b);
461 } else { /* check for 3.: */
462 ir_node *aaa = skip_Id(skip_Proj(aa));
463 ir_node *aba = skip_Id(skip_Proj(ab));
465 if ( ( (/* aa is ProjP and aaa is Alloc */
466 (get_irn_op(aa) == op_Proj)
467 && (mode_is_reference(get_irn_mode(aa)))
468 && (get_irn_op(aaa) == op_Alloc))
469 && ( (/* ab is constant void */
470 (get_irn_op(ab) == op_Const)
471 && (mode_is_reference(get_irn_mode(ab)))
472 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
473 || (/* ab is other Alloc */
474 (get_irn_op(ab) == op_Proj)
475 && (mode_is_reference(get_irn_mode(ab)))
476 && (get_irn_op(aba) == op_Alloc)
478 || (/* aa is void and aba is Alloc */
479 (get_irn_op(aa) == op_Const)
480 && (mode_is_reference(get_irn_mode(aa)))
481 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
482 && (get_irn_op(ab) == op_Proj)
483 && (mode_is_reference(get_irn_mode(ab)))
484 && (get_irn_op(aba) == op_Alloc)))
486 return new_tarval_from_long (proj_nr & Ne, mode_b);
492 /* compute either the Div or the Mod part */
493 proj_nr = get_Proj_proj(n);
494 if (proj_nr == pn_DivMod_res_div)
495 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
496 else if (proj_nr == pn_DivMod_res_mod)
497 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
501 if (get_Proj_proj(n) == pn_Div_res)
502 return computed_value(a);
506 if (get_Proj_proj(n) == pn_Mod_res)
507 return computed_value(a);
517 * If the parameter n can be computed, return its value, else tarval_bad.
518 * Performs constant folding.
520 * @param n The node this should be evaluated
522 tarval *computed_value(ir_node *n)
524 if (n->op->computed_value)
525 return n->op->computed_value(n);
530 * set the default computed_value evaluator
532 static ir_op *firm_set_default_computed_value(ir_op *op)
536 op->computed_value = computed_value_##a; \
561 op->computed_value = NULL;
569 /* returns 1 if the a and b are pointers to different locations. */
571 different_identity (ir_node *a, ir_node *b)
573 assert (mode_is_reference(get_irn_mode (a))
574 && mode_is_reference(get_irn_mode (b)));
576 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
577 ir_node *a1 = get_Proj_pred (a);
578 ir_node *b1 = get_Proj_pred (b);
579 if (a1 != b1 && get_irn_op (a1) == op_Alloc
580 && get_irn_op (b1) == op_Alloc)
587 static ir_node *equivalent_node_Block(ir_node *n)
591 /* The Block constructor does not call optimize, but mature_immBlock
592 calls the optimization. */
593 assert(get_Block_matured(n));
595 /* Straightening: a single entry Block following a single exit Block
596 can be merged, if it is not the Start block. */
597 /* !!! Beware, all Phi-nodes of n must have been optimized away.
598 This should be true, as the block is matured before optimize is called.
599 But what about Phi-cycles with the Phi0/Id that could not be resolved?
600 Remaining Phi nodes are just Ids. */
601 if ((get_Block_n_cfgpreds(n) == 1) &&
602 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
603 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
604 if (predblock == oldn) {
605 /* Jmp jumps into the block it is in -- deal self cycle. */
606 n = set_Block_dead(n);
607 DBG_OPT_DEAD(oldn, n);
608 } else if (get_opt_control_flow_straightening()) {
610 DBG_OPT_STG(oldn, n);
613 else if ((get_Block_n_cfgpreds(n) == 1) &&
614 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
615 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
616 if (predblock == oldn) {
617 /* Jmp jumps into the block it is in -- deal self cycle. */
618 n = set_Block_dead(n);
619 DBG_OPT_DEAD(oldn, n);
622 else if ((get_Block_n_cfgpreds(n) == 2) &&
623 (get_opt_control_flow_weak_simplification())) {
624 /* Test whether Cond jumps twice to this block
625 @@@ we could do this also with two loops finding two preds from several ones. */
626 ir_node *a = get_Block_cfgpred(n, 0);
627 ir_node *b = get_Block_cfgpred(n, 1);
629 if ((get_irn_op(a) == op_Proj) &&
630 (get_irn_op(b) == op_Proj) &&
631 (get_Proj_pred(a) == get_Proj_pred(b)) &&
632 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
633 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
634 /* Also a single entry Block following a single exit Block. Phis have
635 twice the same operand and will be optimized away. */
636 n = get_nodes_block(a);
637 DBG_OPT_IFSIM(oldn, a, b, n);
639 } else if (get_opt_unreachable_code() &&
640 (n != current_ir_graph->start_block) &&
641 (n != current_ir_graph->end_block) ) {
642 int i, n_cfg = get_Block_n_cfgpreds(n);
644 /* If all inputs are dead, this block is dead too, except if it is
645 the start or end block. This is a step of unreachable code
647 for (i = 0; i < n_cfg; i++) {
648 ir_node *pred = get_Block_cfgpred(n, i);
651 if (is_Bad(pred)) continue;
652 pred_blk = get_nodes_block(pred);
654 if (is_Block_dead(pred_blk)) continue;
657 /* really found a living input */
662 n = set_Block_dead(n);
669 * Returns a equivalent node for a Jmp, a Bad :-)
670 * Of course this only happens if the Block of the Jmp is Bad.
672 static ir_node *equivalent_node_Jmp(ir_node *n)
674 /* GL: Why not same for op_Raise?? */
675 /* unreachable code elimination */
676 if (is_Block_dead(get_nodes_block(n)))
682 static ir_node *equivalent_node_Cond(ir_node *n)
684 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
685 See cases for iro_Cond and iro_Proj in transform_node. */
690 * optimize operations that are commutative and have neutral 0,
691 * so a op 0 = 0 op a = a.
693 static ir_node *equivalent_node_neutral_zero(ir_node *n)
697 ir_node *a = get_binop_left(n);
698 ir_node *b = get_binop_right(n);
703 /* After running compute_node there is only one constant predecessor.
704 Find this predecessors value and remember the other node: */
705 if ((tv = value_of(a)) != tarval_bad) {
707 } else if ((tv = value_of(b)) != tarval_bad) {
712 /* If this predecessors constant value is zero, the operation is
713 unnecessary. Remove it: */
714 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
717 DBG_OPT_ALGSIM1(oldn, a, b, n);
723 #define equivalent_node_Add equivalent_node_neutral_zero
724 #define equivalent_node_Eor equivalent_node_neutral_zero
727 * optimize operations that are not commutative but have neutral 0 on left,
730 static ir_node *equivalent_node_left_zero(ir_node *n)
734 ir_node *a = get_binop_left(n);
735 ir_node *b = get_binop_right(n);
737 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
740 DBG_OPT_ALGSIM1(oldn, a, b, n);
746 #define equivalent_node_Sub equivalent_node_left_zero
747 #define equivalent_node_Shl equivalent_node_left_zero
748 #define equivalent_node_Shr equivalent_node_left_zero
749 #define equivalent_node_Shrs equivalent_node_left_zero
750 #define equivalent_node_Rot equivalent_node_left_zero
753 * Er, a "symmetic unop", ie op(op(n)) = n.
755 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
758 ir_node *pred = get_unop_op(n);
760 /* optimize symmetric unop */
761 if (get_irn_op(pred) == get_irn_op(n)) {
762 n = get_unop_op(pred);
763 DBG_OPT_ALGSIM2(oldn, pred, n);
769 #define equivalent_node_Not equivalent_node_symmetric_unop
771 /* --x == x */ /* ??? Is this possible or can --x raise an
772 out of bounds exception if min =! max? */
773 #define equivalent_node_Minus equivalent_node_symmetric_unop
776 * Optimize a * 1 = 1 * a = a.
778 static ir_node *equivalent_node_Mul(ir_node *n)
782 ir_node *a = get_Mul_left(n);
783 ir_node *b = get_Mul_right(n);
785 /* Mul is commutative and has again an other neutral element. */
786 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
788 DBG_OPT_ALGSIM1(oldn, a, b, n);
789 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
791 DBG_OPT_ALGSIM1(oldn, a, b, n);
797 * Optimize a / 1 = a.
799 static ir_node *equivalent_node_Div(ir_node *n)
801 ir_node *a = get_Div_left(n);
802 ir_node *b = get_Div_right(n);
804 /* Div is not commutative. */
805 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
806 /* Turn Div into a tuple (mem, bad, a) */
807 ir_node *mem = get_Div_mem(n);
808 turn_into_tuple(n, 3);
809 set_Tuple_pred(n, pn_Div_M, mem);
810 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
811 set_Tuple_pred(n, pn_Div_res, a);
817 * Optimize a / 1 = a.
819 static ir_node *equivalent_node_DivMod(ir_node *n)
821 ir_node *a = get_DivMod_left(n);
822 ir_node *b = get_DivMod_right(n);
824 /* Div is not commutative. */
825 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
826 /* Turn DivMod into a tuple (mem, bad, a, 0) */
827 ir_node *mem = get_Div_mem(n);
828 ir_mode *mode = get_irn_mode(b);
830 turn_into_tuple(n, 4);
831 set_Tuple_pred(n, pn_DivMod_M, mem);
832 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
833 set_Tuple_pred(n, pn_DivMod_res_div, a);
834 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
840 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
842 static ir_node *equivalent_node_Or(ir_node *n)
846 ir_node *a = get_Or_left(n);
847 ir_node *b = get_Or_right(n);
850 n = a; /* Or has it's own neutral element */
851 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
853 DBG_OPT_ALGSIM1(oldn, a, b, n);
854 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
856 DBG_OPT_ALGSIM1(oldn, a, b, n);
863 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
865 static ir_node *equivalent_node_And(ir_node *n)
869 ir_node *a = get_And_left(n);
870 ir_node *b = get_And_right(n);
873 n = a; /* And has it's own neutral element */
874 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
876 DBG_OPT_ALGSIM1(oldn, a, b, n);
877 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
879 DBG_OPT_ALGSIM1(oldn, a, b, n);
885 * Try to remove useless conv's:
887 static ir_node *equivalent_node_Conv(ir_node *n)
890 ir_node *a = get_Conv_op(n);
893 ir_mode *n_mode = get_irn_mode(n);
894 ir_mode *a_mode = get_irn_mode(a);
896 if (n_mode == a_mode) { /* No Conv necessary */
898 DBG_OPT_ALGSIM3(oldn, a, n);
899 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
903 n_mode = get_irn_mode(n);
904 b_mode = get_irn_mode(b);
906 if (n_mode == b_mode) {
907 if (n_mode == mode_b) {
908 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
909 DBG_OPT_ALGSIM1(oldn, a, b, n);
911 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
912 if (smaller_mode(b_mode, a_mode)){
913 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
914 DBG_OPT_ALGSIM1(oldn, a, b, n);
923 * A Cast may be removed if the type of the previous node
924 * is already to type of the Cast.
926 static ir_node *equivalent_node_Cast(ir_node *n) {
927 ir_node *pred = get_Cast_op(n);
928 if (get_irn_type(pred) == get_Cast_type(n))
933 /* Several optimizations:
934 - no Phi in start block.
935 - remove Id operators that are inputs to Phi
936 - fold Phi-nodes, iff they have only one predecessor except
939 static ir_node *equivalent_node_Phi(ir_node *n)
944 ir_node *block = NULL; /* to shutup gcc */
945 ir_node *first_val = NULL; /* to shutup gcc */
946 ir_node *scnd_val = NULL; /* to shutup gcc */
948 if (!get_opt_normalize()) return n;
950 n_preds = get_Phi_n_preds(n);
952 block = get_nodes_block(n);
953 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
954 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
955 if ((is_Block_dead(block)) || /* Control dead */
956 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
957 return new_Bad(); /* in the Start Block. */
959 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
962 /* first we test for a special case: */
963 /* Confirm is a special node fixing additional information for a
964 value that is known at a certain point. This is useful for
965 dataflow analysis. */
967 ir_node *a = get_Phi_pred(n, 0);
968 ir_node *b = get_Phi_pred(n, 1);
969 if ( (get_irn_op(a) == op_Confirm)
970 && (get_irn_op(b) == op_Confirm)
971 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
972 && (get_irn_n(a, 1) == get_irn_n (b, 1))
973 && (a->data.num == (~b->data.num & irpn_True) )) {
974 return get_irn_n(a, 0);
979 /* If the Block has a Bad pred, we also have one. */
980 for (i = 0; i < n_preds; ++i)
981 if (is_Bad (get_Block_cfgpred(block, i)))
982 set_Phi_pred(n, i, new_Bad());
984 /* Find first non-self-referencing input */
985 for (i = 0; i < n_preds; ++i) {
986 first_val = get_Phi_pred(n, i);
987 if ( (first_val != n) /* not self pointer */
989 && (get_irn_op(first_val) != op_Bad)
991 ) { /* value not dead */
992 break; /* then found first value. */
996 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
997 if (i >= n_preds) { return new_Bad(); }
1001 /* follow_Id () for rest of inputs, determine if any of these
1002 are non-self-referencing */
1003 while (++i < n_preds) {
1004 scnd_val = get_Phi_pred(n, i);
1005 if ( (scnd_val != n)
1006 && (scnd_val != first_val)
1008 && (get_irn_op(scnd_val) != op_Bad)
1015 /* Fold, if no multiple distinct non-self-referencing inputs */
1018 DBG_OPT_PHI(oldn, first_val, n);
1020 /* skip the remaining Ids (done in get_Phi_pred). */
1021 /* superfluous, since we walk all to propagate Block's Bads.
1022 while (++i < n_preds) get_Phi_pred(n, i); */
1028 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1030 static ir_node *equivalent_node_Proj(ir_node *n)
1034 ir_node *a = get_Proj_pred(n);
1036 if ( get_irn_op(a) == op_Tuple) {
1037 /* Remove the Tuple/Proj combination. */
1038 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1039 n = get_Tuple_pred(a, get_Proj_proj(n));
1040 DBG_OPT_TUPLE(oldn, a, n);
1042 assert(0); /* This should not happen! */
1045 } else if (get_irn_mode(n) == mode_X &&
1046 is_Block_dead(get_nodes_block(n))) {
1047 /* Remove dead control flow -- early gigo. */
1056 static ir_node *equivalent_node_Id(ir_node *n)
1061 DBG_OPT_ID(oldn, n);
1066 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1067 * perform no actual computation, as, e.g., the Id nodes. It does not create
1068 * new nodes. It is therefore safe to free n if the node returned is not n.
1069 * If a node returns a Tuple we can not just skip it. If the size of the
1070 * in array fits, we transform n into a tuple (e.g., Div).
1073 equivalent_node(ir_node *n)
1075 if (n->op->equivalent_node)
1076 return n->op->equivalent_node(n);
1081 * set the default equivalent node operation
1083 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1087 op->equivalent_node = equivalent_node_##a; \
1114 op->equivalent_node = NULL;
1122 * Do node specific optimizations of nodes predecessors.
1125 optimize_preds(ir_node *n) {
1126 ir_node *a = NULL, *b = NULL;
1128 /* get the operands we will work on for simple cases. */
1130 a = get_binop_left(n);
1131 b = get_binop_right(n);
1132 } else if (is_unop(n)) {
1136 switch (get_irn_opcode(n)) {
1139 /* We don't want Cast as input to Cmp. */
1140 if (get_irn_op(a) == op_Cast) {
1144 if (get_irn_op(b) == op_Cast) {
1146 set_Cmp_right(n, b);
1155 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1156 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1158 static ir_node *transform_node_AddSub(ir_node *n)
1160 ir_mode *mode = get_irn_mode(n);
1162 if (mode_is_reference(mode)) {
1163 ir_node *left = get_binop_left(n);
1164 ir_node *right = get_binop_right(n);
1165 int ref_bits = get_mode_size_bits(mode);
1167 if (get_irn_op(left) == op_Conv) {
1168 ir_mode *mode = get_irn_mode(left);
1169 int bits = get_mode_size_bits(mode);
1171 if (ref_bits == bits &&
1172 mode_is_int(mode) &&
1173 get_mode_arithmetic(mode) == irma_twos_complement) {
1174 ir_node *pre = get_Conv_op(left);
1175 ir_mode *pre_mode = get_irn_mode(pre);
1177 if (mode_is_int(pre_mode) &&
1178 get_mode_size_bits(pre_mode) == bits &&
1179 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1180 /* ok, this conv just changes to sign, moreover the calculation
1181 * is done with same number of bits as our address mode, so
1182 * we can ignore the conv as address calculation can be viewed
1183 * as either signed or unsigned
1185 set_binop_left(n, pre);
1190 if (get_irn_op(right) == op_Conv) {
1191 ir_mode *mode = get_irn_mode(right);
1192 int bits = get_mode_size_bits(mode);
1194 if (ref_bits == bits &&
1195 mode_is_int(mode) &&
1196 get_mode_arithmetic(mode) == irma_twos_complement) {
1197 ir_node *pre = get_Conv_op(right);
1198 ir_mode *pre_mode = get_irn_mode(pre);
1200 if (mode_is_int(pre_mode) &&
1201 get_mode_size_bits(pre_mode) == bits &&
1202 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1203 /* ok, this conv just changes to sign, moreover the calculation
1204 * is done with same number of bits as our address mode, so
1205 * we can ignore the conv as address calculation can be viewed
1206 * as either signed or unsigned
1208 set_binop_right(n, pre);
1216 #define transform_node_Add transform_node_AddSub
1217 #define transform_node_Sub transform_node_AddSub
1219 /** Do architecture dependend optimizations on Mul nodes */
1220 static ir_node *transform_node_Mul(ir_node *n) {
1221 return arch_dep_replace_mul_with_shifts(n);
1224 static ir_node *transform_node_Div(ir_node *n)
1226 tarval *tv = value_of(n);
1229 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1231 if (tv != tarval_bad)
1232 value = new_Const(get_tarval_mode(tv), tv);
1233 else /* Try architecture dependand optimization */
1234 value = arch_dep_replace_div_by_const(n);
1237 /* Turn Div into a tuple (mem, bad, value) */
1238 ir_node *mem = get_Div_mem(n);
1240 turn_into_tuple(n, 3);
1241 set_Tuple_pred(n, pn_Div_M, mem);
1242 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1243 set_Tuple_pred(n, pn_Div_res, value);
1248 static ir_node *transform_node_Mod(ir_node *n)
1250 tarval *tv = value_of(n);
1253 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1255 if (tv != tarval_bad)
1256 value = new_Const(get_tarval_mode(tv), tv);
1257 else /* Try architecture dependand optimization */
1258 value = arch_dep_replace_mod_by_const(n);
1261 /* Turn Mod into a tuple (mem, bad, value) */
1262 ir_node *mem = get_Mod_mem(n);
1264 turn_into_tuple(n, 3);
1265 set_Tuple_pred(n, pn_Mod_M, mem);
1266 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1267 set_Tuple_pred(n, pn_Mod_res, value);
1272 static ir_node *transform_node_DivMod(ir_node *n)
1276 ir_node *a = get_DivMod_left(n);
1277 ir_node *b = get_DivMod_right(n);
1278 ir_mode *mode = get_irn_mode(a);
1279 tarval *ta = value_of(a);
1280 tarval *tb = value_of(b);
1282 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1285 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1287 if (tb != tarval_bad) {
1288 if (tb == get_mode_one(get_tarval_mode(tb))) {
1289 b = new_Const (mode, get_mode_null(mode));
1291 } else if (ta != tarval_bad) {
1292 tarval *resa, *resb;
1293 resa = tarval_div (ta, tb);
1294 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1295 Jmp for X result!? */
1296 resb = tarval_mod (ta, tb);
1297 if (resb == tarval_bad) return n; /* Causes exception! */
1298 a = new_Const (mode, resa);
1299 b = new_Const (mode, resb);
1302 else { /* Try architecture dependand optimization */
1303 arch_dep_replace_divmod_by_const(&a, &b, n);
1304 evaluated = a != NULL;
1306 } else if (ta == get_mode_null(mode)) {
1307 /* 0 / non-Const = 0 */
1312 if (evaluated) { /* replace by tuple */
1313 ir_node *mem = get_DivMod_mem(n);
1314 turn_into_tuple(n, 4);
1315 set_Tuple_pred(n, pn_DivMod_M, mem);
1316 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1317 set_Tuple_pred(n, pn_DivMod_res_div, a);
1318 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1319 assert(get_nodes_block(n));
1325 static ir_node *transform_node_Cond(ir_node *n)
1327 /* Replace the Cond by a Jmp if it branches on a constant
1330 ir_node *a = get_Cond_selector(n);
1331 tarval *ta = value_of(a);
1333 if ((ta != tarval_bad) &&
1334 (get_irn_mode(a) == mode_b) &&
1335 (get_opt_unreachable_code())) {
1336 /* It's a boolean Cond, branching on a boolean constant.
1337 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1338 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1339 turn_into_tuple(n, 2);
1340 if (ta == tarval_b_true) {
1341 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1342 set_Tuple_pred(n, pn_Cond_true, jmp);
1344 set_Tuple_pred(n, pn_Cond_false, jmp);
1345 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1347 /* We might generate an endless loop, so keep it alive. */
1348 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1349 } else if ((ta != tarval_bad) &&
1350 (get_irn_mode(a) == mode_Iu) &&
1351 (get_Cond_kind(n) == dense) &&
1352 (get_opt_unreachable_code())) {
1353 /* I don't want to allow Tuples smaller than the biggest Proj.
1354 Also this tuple might get really big...
1355 I generate the Jmp here, and remember it in link. Link is used
1356 when optimizing Proj. */
1357 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1358 /* We might generate an endless loop, so keep it alive. */
1359 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1360 } else if ((get_irn_op(a) == op_Eor)
1361 && (get_irn_mode(a) == mode_b)
1362 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1363 /* The Eor is a negate. Generate a new Cond without the negate,
1364 simulate the negate by exchanging the results. */
1365 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1367 } else if ((get_irn_op(a) == op_Not)
1368 && (get_irn_mode(a) == mode_b)) {
1369 /* A Not before the Cond. Generate a new Cond without the Not,
1370 simulate the Not by exchanging the results. */
1371 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1380 static ir_node *transform_node_Eor(ir_node *n)
1382 ir_node *a = get_Eor_left(n);
1383 ir_node *b = get_Eor_right(n);
1385 if ((get_irn_mode(n) == mode_b)
1386 && (get_irn_op(a) == op_Proj)
1387 && (get_irn_mode(a) == mode_b)
1388 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1389 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1390 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1391 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1392 mode_b, get_negated_pnc(get_Proj_proj(a)));
1393 else if ((get_irn_mode(n) == mode_b)
1394 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1395 /* The Eor is a Not. Replace it by a Not. */
1396 /* ????!!!Extend to bitfield 1111111. */
1397 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1403 * Transform a boolean Not.
1405 static ir_node *transform_node_Not(ir_node *n)
1407 ir_node *a = get_Not_op(n);
1409 if ( (get_irn_mode(n) == mode_b)
1410 && (get_irn_op(a) == op_Proj)
1411 && (get_irn_mode(a) == mode_b)
1412 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1413 /* We negate a Cmp. The Cmp has the negated result anyways! */
1414 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1415 mode_b, get_negated_pnc(get_Proj_proj(a)));
1421 * Transform a Cast of a Const into a new Const
1423 static ir_node *transform_node_Cast(ir_node *n) {
1424 ir_node *pred = get_Cast_op(n);
1425 type *tp = get_irn_type(pred);
1427 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1428 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1429 get_Const_tarval(pred), tp);
1430 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1431 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1432 get_SymConst_kind(pred), tp);
1438 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1439 * done here instead of equivalent node because it creates new
1441 * Removes the exceptions and routes the memory to the NoMem node.
1443 * Further, it optimizes jump tables by removing all impossible cases.
1445 static ir_node *transform_node_Proj(ir_node *proj)
1447 ir_node *n = get_Proj_pred(proj);
1452 switch (get_irn_opcode(n)) {
1454 b = get_Div_right(n);
1457 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1458 proj_nr = get_Proj_proj(proj);
1460 /* this node may float */
1461 set_irn_pinned(n, op_pin_state_floats);
1463 if (proj_nr == pn_Div_X_except) {
1464 /* we found an exception handler, remove it */
1467 /* the memory Proj can be removed */
1468 ir_node *res = get_Div_mem(n);
1470 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1471 # endif /* defined USE_NOMEM */
1472 if (proj_nr == pn_Div_M)
1478 b = get_Mod_right(n);
1481 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1482 proj_nr = get_Proj_proj(proj);
1484 /* this node may float */
1485 set_irn_pinned(n, op_pin_state_floats);
1487 if (proj_nr == pn_Mod_X_except) {
1488 /* we found an exception handler, remove it */
1491 /* the memory Proj can be removed */
1492 ir_node *res = get_Mod_mem(n);
1494 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1495 # endif /* defined USE_NOMEM */
1496 if (proj_nr == pn_Mod_M)
1502 b = get_DivMod_right(n);
1505 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1506 proj_nr = get_Proj_proj(proj);
1508 /* this node may float */
1509 set_irn_pinned(n, op_pin_state_floats);
1511 if (proj_nr == pn_DivMod_X_except) {
1512 /* we found an exception handler, remove it */
1516 /* the memory Proj can be removed */
1517 ir_node *res = get_DivMod_mem(n);
1519 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1520 # endif /* defined USE_NOMEM */
1521 if (proj_nr == pn_DivMod_M)
1528 if (get_opt_unreachable_code()) {
1529 b = get_Cond_selector(n);
1532 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1533 /* we have a constant switch */
1534 long num = get_Proj_proj(proj);
1536 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1537 if (get_tarval_long(tb) == num) {
1538 /* Do NOT create a jump here, or we will have 2 control flow ops
1539 * in a block. This case is optimized away in optimize_cf(). */
1550 /* should not happen, but if it does will be optimized away */
1558 /* we have added a Tuple, optimize it for the current Proj away */
1559 return equivalent_node_Proj(proj);
1563 * returns the operands of a commutative bin-op, if one operand is
1564 * a const, it is returned as the second one.
1566 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1568 ir_node *op_a = get_binop_left(binop);
1569 ir_node *op_b = get_binop_right(binop);
1571 assert(is_op_commutative(get_irn_op(binop)));
1573 if (get_irn_op(op_a) == op_Const) {
1584 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1585 * Such pattern may arise in bitfield stores.
1587 * value c4 value c4 & c2
1588 * AND c3 AND c1 | c3
1593 static ir_node *transform_node_Or(ir_node *or)
1597 ir_node *and_l, *c3;
1598 ir_node *value, *c4;
1599 ir_node *new_and, *new_const, *block;
1600 ir_mode *mode = get_irn_mode(or);
1602 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1604 get_comm_Binop_Ops(or, &and, &c1);
1605 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1608 get_comm_Binop_Ops(and, &or_l, &c2);
1609 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1612 get_comm_Binop_Ops(or_l, &and_l, &c3);
1613 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1616 get_comm_Binop_Ops(and_l, &value, &c4);
1617 if (get_irn_op(c4) != op_Const)
1620 /* ok, found the pattern, check for conditions */
1621 assert(mode == get_irn_mode(and));
1622 assert(mode == get_irn_mode(or_l));
1623 assert(mode == get_irn_mode(and_l));
1625 tv1 = get_Const_tarval(c1);
1626 tv2 = get_Const_tarval(c2);
1627 tv3 = get_Const_tarval(c3);
1628 tv4 = get_Const_tarval(c4);
1630 tv = tarval_or(tv4, tv2);
1631 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1632 /* have at least one 0 at the same bit position */
1636 n_tv4 = tarval_not(tv4);
1637 if (tv3 != tarval_and(tv3, n_tv4)) {
1638 /* bit in the or_mask is outside the and_mask */
1642 n_tv2 = tarval_not(tv2);
1643 if (tv1 != tarval_and(tv1, n_tv2)) {
1644 /* bit in the or_mask is outside the and_mask */
1648 /* ok, all conditions met */
1649 block = get_nodes_block(or);
1651 new_and = new_r_And(current_ir_graph, block,
1652 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1654 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1656 set_Or_left(or, new_and);
1657 set_Or_right(or, new_const);
1659 /* check for more */
1660 return transform_node_Or(or);
1664 static ir_node *transform_node(ir_node *n);
1667 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1669 static ir_node * transform_node_shift(ir_node *n)
1672 tarval *tv1, *tv2, *res;
1674 int modulo_shf, flag;
1676 left = get_binop_left(n);
1678 /* different operations */
1679 if (get_irn_op(left) != get_irn_op(n))
1682 tv1 = value_of(get_binop_right(n));
1683 if (tv1 == tarval_bad)
1686 tv2 = value_of(get_binop_right(left));
1687 if (tv2 == tarval_bad)
1690 res = tarval_add(tv1, tv2);
1692 /* beware: a simple replacement works only, if res < modulo shift */
1693 mode = get_irn_mode(n);
1697 modulo_shf = get_mode_modulo_shift(mode);
1698 if (modulo_shf > 0) {
1699 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1701 if (tarval_cmp(res, modulo) & Lt)
1708 /* ok, we can replace it */
1709 ir_node *in[2], *irn, *block = get_nodes_block(n);
1711 in[0] = get_binop_left(left);
1712 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1714 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1716 return transform_node(irn);
1723 * Tries several [inplace] [optimizing] transformations and returns an
1724 * equivalent node. The difference to equivalent_node() is that these
1725 * transformations _do_ generate new nodes, and thus the old node must
1726 * not be freed even if the equivalent node isn't the old one.
1728 static ir_node *transform_node(ir_node *n)
1730 if (n->op->transform_node)
1731 n = n->op->transform_node(n);
1736 * set the default transform node operation
1738 static ir_op *firm_set_default_transform_node(ir_op *op)
1742 op->transform_node = transform_node_##a; \
1761 op->transform_node = transform_node_shift;
1764 op->transform_node = NULL;
1772 /* **************** Common Subexpression Elimination **************** */
1774 /** The size of the hash table used, should estimate the number of nodes
1776 #define N_IR_NODES 512
1778 /** Compares the attributes of two Const nodes. */
1779 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1781 return (get_Const_tarval(a) != get_Const_tarval(b))
1782 || (get_Const_type(a) != get_Const_type(b));
1785 /** Compares the attributes of two Proj nodes. */
1786 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1788 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1791 /** Compares the attributes of two Filter nodes. */
1792 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1794 return get_Filter_proj(a) != get_Filter_proj(b);
1797 /** Compares the attributes of two Alloc nodes. */
1798 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1800 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1801 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1804 /** Compares the attributes of two Free nodes. */
1805 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1807 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1810 /** Compares the attributes of two SymConst nodes. */
1811 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1813 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1814 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1815 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1818 /** Compares the attributes of two Call nodes. */
1819 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1821 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1824 /** Compares the attributes of two Sel nodes. */
1825 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1827 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1828 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1829 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1830 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1831 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1834 /** Compares the attributes of two Phi nodes. */
1835 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1837 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1840 /** Compares the attributes of two Cast nodes. */
1841 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1843 return get_Cast_type(a) != get_Cast_type(b);
1846 /** Compares the attributes of two Load nodes. */
1847 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1849 if (get_Load_volatility(a) == volatility_is_volatile ||
1850 get_Load_volatility(b) == volatility_is_volatile)
1851 /* NEVER do CSE on volatile Loads */
1854 return get_Load_mode(a) != get_Load_mode(b);
1857 /** Compares the attributes of two Store nodes. */
1858 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1860 /* NEVER do CSE on volatile Stores */
1861 return (get_Store_volatility(a) == volatility_is_volatile ||
1862 get_Store_volatility(b) == volatility_is_volatile);
1866 * set the default node attribute compare operation
1868 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1872 op->node_cmp_attr = node_cmp_attr_##a; \
1889 op->node_cmp_attr = NULL;
1897 * Compare function for two nodes in the hash table. Gets two
1898 * nodes as parameters. Returns 0 if the nodes are a cse.
1901 vt_cmp (const void *elt, const void *key)
1909 if (a == b) return 0;
1911 if ((get_irn_op(a) != get_irn_op(b)) ||
1912 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1914 /* compare if a's in and b's in are of equal length */
1915 irn_arity_a = get_irn_intra_arity (a);
1916 if (irn_arity_a != get_irn_intra_arity(b))
1919 /* for block-local cse and op_pin_state_pinned nodes: */
1920 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1921 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1925 /* compare a->in[0..ins] with b->in[0..ins] */
1926 for (i = 0; i < irn_arity_a; i++)
1927 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1931 * here, we already now that the nodes are identical except their
1934 if (a->op->node_cmp_attr)
1935 return a->op->node_cmp_attr(a, b);
1941 * Calculate a hash value of a node.
1944 ir_node_hash (ir_node *node)
1949 if (node->op == op_Const) {
1950 /* special value for const, as they only differ in their tarval. */
1951 h = HASH_PTR(node->attr.con.tv);
1952 h = 9*h + HASH_PTR(get_irn_mode(node));
1953 } else if (node->op == op_SymConst) {
1954 /* special value for const, as they only differ in their symbol. */
1955 h = HASH_PTR(node->attr.i.sym.type_p);
1956 h = 9*h + HASH_PTR(get_irn_mode(node));
1959 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1960 h = irn_arity = get_irn_intra_arity(node);
1962 /* consider all in nodes... except the block if not a control flow. */
1963 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1964 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
1968 h = 9*h + HASH_PTR(get_irn_mode(node));
1970 h = 9*h + HASH_PTR(get_irn_op(node));
1977 new_identities(void) {
1978 return new_pset(vt_cmp, N_IR_NODES);
1982 del_identities(pset *value_table) {
1983 del_pset(value_table);
1987 * Return the canonical node computing the same value as n.
1988 * Looks up the node in a hash table.
1990 * For Const nodes this is performed in the constructor, too. Const
1991 * nodes are extremely time critical because of their frequent use in
1992 * constant string arrays.
1994 static INLINE ir_node *
1995 identify (pset *value_table, ir_node *n)
1999 if (!value_table) return n;
2001 if (get_opt_reassociation()) {
2002 if (is_op_commutative(get_irn_op(n))) {
2003 ir_node *l = get_binop_left(n);
2004 ir_node *r = get_binop_right(n);
2006 /* for commutative operators perform a OP b == b OP a */
2008 set_binop_left(n, r);
2009 set_binop_right(n, l);
2014 o = pset_find (value_table, n, ir_node_hash (n));
2023 * During construction we set the op_pin_state_pinned flag in the graph right when the
2024 * optimization is performed. The flag turning on procedure global cse could
2025 * be changed between two allocations. This way we are safe.
2027 static INLINE ir_node *
2028 identify_cons (pset *value_table, ir_node *n) {
2031 n = identify(value_table, n);
2032 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2033 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2038 * Return the canonical node computing the same value as n.
2039 * Looks up the node in a hash table, enters it in the table
2040 * if it isn't there yet.
2043 identify_remember (pset *value_table, ir_node *n)
2047 if (!value_table) return n;
2049 if (get_opt_reassociation()) {
2050 if (is_op_commutative(get_irn_op(n))) {
2051 ir_node *l = get_binop_left(n);
2052 ir_node *r = get_binop_right(n);
2054 /* for commutative operators perform a OP b == b OP a */
2056 set_binop_left(n, r);
2057 set_binop_right(n, l);
2062 /* lookup or insert in hash table with given hash key. */
2063 o = pset_insert (value_table, n, ir_node_hash (n));
2073 add_identities (pset *value_table, ir_node *node) {
2074 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2075 identify_remember (value_table, node);
2079 * garbage in, garbage out. If a node has a dead input, i.e., the
2080 * Bad node is input to the node, return the Bad node.
2082 static INLINE ir_node *
2083 gigo (ir_node *node)
2086 ir_op* op = get_irn_op(node);
2088 /* remove garbage blocks by looking at control flow that leaves the block
2089 and replacing the control flow by Bad. */
2090 if (get_irn_mode(node) == mode_X) {
2091 ir_node *block = get_nodes_block(node);
2092 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2094 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2095 irn_arity = get_irn_arity(block);
2096 for (i = 0; i < irn_arity; i++) {
2097 if (!is_Bad(get_irn_n(block, i))) break;
2099 if (i == irn_arity) return new_Bad();
2103 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2104 blocks predecessors is dead. */
2105 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2106 irn_arity = get_irn_arity(node);
2108 if (is_Block_dead(get_nodes_block(node)))
2111 for (i = 0; i < irn_arity; i++) {
2112 if (is_Bad(get_irn_n(node, i))) {
2118 /* With this code we violate the agreement that local_optimize
2119 only leaves Bads in Block, Phi and Tuple nodes. */
2120 /* If Block has only Bads as predecessors it's garbage. */
2121 /* If Phi has only Bads as predecessors it's garbage. */
2122 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2123 irn_arity = get_irn_arity(node);
2124 for (i = 0; i < irn_arity; i++) {
2125 if (!is_Bad(get_irn_n(node, i))) break;
2127 if (i == irn_arity) node = new_Bad();
2135 * These optimizations deallocate nodes from the obstack.
2136 * It can only be called if it is guaranteed that no other nodes
2137 * reference this one, i.e., right after construction of a node.
2140 optimize_node (ir_node *n)
2144 opcode iro = get_irn_opcode(n);
2146 type *old_tp = get_irn_type(n);
2148 int i, arity = get_irn_arity(n);
2149 for (i = 0; i < arity && !old_tp; ++i)
2150 old_tp = get_irn_type(get_irn_n(n, i));
2153 /* Allways optimize Phi nodes: part of the construction. */
2154 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2156 /* constant expression evaluation / constant folding */
2157 if (get_opt_constant_folding()) {
2158 /* constants can not be evaluated */
2159 if (iro != iro_Const) {
2160 /* try to evaluate */
2161 tv = computed_value(n);
2162 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2164 * we MUST copy the node here temporary, because it's still needed
2165 * for DBG_OPT_CSTEVAL
2167 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2168 oldn = alloca(node_size);
2170 memcpy(oldn, n, node_size);
2171 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2173 /* ARG, copy the in array, we need it for statistics */
2174 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2176 /* evaluation was successful -- replace the node. */
2177 obstack_free (current_ir_graph->obst, n);
2178 n = new_Const (get_tarval_mode (tv), tv);
2179 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2180 set_Const_type(n, old_tp);
2181 DBG_OPT_CSTEVAL(oldn, n);
2187 /* remove unnecessary nodes */
2188 if (get_opt_constant_folding() ||
2189 (iro == iro_Phi) || /* always optimize these nodes. */
2191 (iro == iro_Proj) ||
2192 (iro == iro_Block) ) /* Flags tested local. */
2193 n = equivalent_node (n);
2195 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2197 /** common subexpression elimination **/
2198 /* Checks whether n is already available. */
2199 /* The block input is used to distinguish different subexpressions. Right
2200 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2201 subexpressions within a block. */
2203 n = identify_cons (current_ir_graph->value_table, n);
2206 /* We found an existing, better node, so we can deallocate the old node. */
2207 obstack_free (current_ir_graph->obst, oldn);
2212 /* Some more constant expression evaluation that does not allow to
2214 iro = get_irn_opcode(n);
2215 if (get_opt_constant_folding() ||
2216 (iro == iro_Cond) ||
2217 (iro == iro_Proj)) /* Flags tested local. */
2218 n = transform_node (n);
2220 /* Remove nodes with dead (Bad) input.
2221 Run always for transformation induced Bads. */
2224 /* Now we have a legal, useful node. Enter it in hash table for cse */
2225 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2226 n = identify_remember (current_ir_graph->value_table, n);
2234 * These optimizations never deallocate nodes. This can cause dead
2235 * nodes lying on the obstack. Remove these by a dead node elimination,
2236 * i.e., a copying garbage collection.
2239 optimize_in_place_2 (ir_node *n)
2243 opcode iro = get_irn_opcode(n);
2245 type *old_tp = get_irn_type(n);
2247 int i, arity = get_irn_arity(n);
2248 for (i = 0; i < arity && !old_tp; ++i)
2249 old_tp = get_irn_type(get_irn_n(n, i));
2252 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2254 /* if not optimize return n */
2257 /* Here this is possible. Why? */
2261 /* constant expression evaluation / constant folding */
2262 if (get_opt_constant_folding()) {
2263 /* constants can not be evaluated */
2264 if (iro != iro_Const) {
2265 /* try to evaluate */
2266 tv = computed_value(n);
2267 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2268 /* evaluation was successful -- replace the node. */
2269 n = new_Const (get_tarval_mode (tv), tv);
2271 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2272 set_Const_type(n, old_tp);
2274 DBG_OPT_CSTEVAL(oldn, n);
2280 /* remove unnecessary nodes */
2281 if (get_opt_constant_folding() ||
2282 (iro == iro_Phi) || /* always optimize these nodes. */
2283 (iro == iro_Id) || /* ... */
2284 (iro == iro_Proj) || /* ... */
2285 (iro == iro_Block) ) /* Flags tested local. */
2286 n = equivalent_node (n);
2288 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2290 /** common subexpression elimination **/
2291 /* Checks whether n is already available. */
2292 /* The block input is used to distinguish different subexpressions. Right
2293 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2294 subexpressions within a block. */
2295 if (get_opt_cse()) {
2296 n = identify (current_ir_graph->value_table, n);
2299 /* Some more constant expression evaluation. */
2300 iro = get_irn_opcode(n);
2301 if (get_opt_constant_folding() ||
2302 (iro == iro_Cond) ||
2303 (iro == iro_Proj)) /* Flags tested local. */
2304 n = transform_node (n);
2306 /* Remove nodes with dead (Bad) input.
2307 Run always for transformation induced Bads. */
2310 /* Now we can verify the node, as it has no dead inputs any more. */
2313 /* Now we have a legal, useful node. Enter it in hash table for cse.
2314 Blocks should be unique anyways. (Except the successor of start:
2315 is cse with the start block!) */
2316 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2317 n = identify_remember (current_ir_graph->value_table, n);
2323 * Wrapper for external use, set proper status bits after optimization.
2326 optimize_in_place (ir_node *n)
2328 /* Handle graph state */
2329 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2331 if (get_opt_global_cse())
2332 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2333 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2334 set_irg_outs_inconsistent(current_ir_graph);
2336 /* Maybe we could also test whether optimizing the node can
2337 change the control graph. */
2338 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2339 set_irg_dom_inconsistent(current_ir_graph);
2340 return optimize_in_place_2 (n);
2344 * set the default ir op operations
2346 ir_op *firm_set_default_operations(ir_op *op)
2348 op = firm_set_default_computed_value(op);
2349 op = firm_set_default_equivalent_node(op);
2350 op = firm_set_default_transform_node(op);
2351 op = firm_set_default_node_cmp_attr(op);