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"
32 /* Make types visible to allow most efficient access */
33 # include "entity_t.h"
35 # ifdef DO_HEAPANALYSIS
36 /* heapanal can't cope with NoMems */
37 # else /* if defined DO_HEAPANALYSIS */
39 # endif /* defined DO_HEAPANALYSIS */
42 * Trivial INLINEable routine for copy propagation.
43 * Does follow Ids, needed to optimize INLINEd code.
45 static INLINE ir_node *
46 follow_Id (ir_node *n)
48 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
53 * return the value of a Constant
55 static tarval *computed_value_Const(ir_node *n)
57 return get_Const_tarval(n);
61 * return the value of a 'sizeof' SymConst
63 static tarval *computed_value_SymConst(ir_node *n)
65 if ((get_SymConst_kind(n) == symconst_size) &&
66 (get_type_state(get_SymConst_type(n))) == layout_fixed)
67 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
72 * return the value of an Add
74 static tarval *computed_value_Add(ir_node *n)
76 ir_node *a = get_Add_left(n);
77 ir_node *b = get_Add_right(n);
79 tarval *ta = value_of(a);
80 tarval *tb = value_of(b);
82 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
83 return tarval_add(ta, tb);
89 * return the value of a Sub
92 static tarval *computed_value_Sub(ir_node *n)
94 ir_node *a = get_Sub_left(n);
95 ir_node *b = get_Sub_right(n);
101 return get_tarval_null(get_irn_mode(n));
106 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
107 return tarval_sub(ta, tb);
113 * return the value of an unary Minus
115 static tarval *computed_value_Minus(ir_node *n)
117 ir_node *a = get_Minus_op(n);
118 tarval *ta = value_of(a);
120 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
121 return tarval_neg(ta);
127 * return the value of a Mul
129 static tarval *computed_value_Mul(ir_node *n)
131 ir_node *a = get_Mul_left(n);
132 ir_node *b = get_Mul_right(n);
134 tarval *ta = value_of(a);
135 tarval *tb = value_of(b);
137 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
138 return tarval_mul(ta, tb);
140 /* a*0 = 0 or 0*b = 0:
141 calls computed_value recursive and returns the 0 with proper
143 if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
145 if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
152 * return the value of a floating point Quot
154 static tarval *computed_value_Quot(ir_node *n)
156 ir_node *a = get_Quot_left(n);
157 ir_node *b = get_Quot_right(n);
159 tarval *ta = value_of(a);
160 tarval *tb = value_of(b);
162 /* This was missing in original implementation. Why? */
163 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
164 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
165 return tarval_quo(ta, tb);
171 * calculate the value of an integer Div of two nodes
172 * Special case: 0 / b
174 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
176 tarval *ta = value_of(a);
177 tarval *tb = value_of(b);
179 /* Compute c1 / c2 or 0 / a, a != 0 */
180 if (ta != tarval_bad) {
181 if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b)))) /* div by zero: return tarval_bad */
182 return tarval_div(ta, tb);
183 else if (ta == get_mode_null(get_tarval_mode(ta))) /* 0 / b == 0 */
190 * return the value of an integer Div
192 static tarval *computed_value_Div(ir_node *n)
194 return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
198 * calculate the value of an integer Mod of two nodes
199 * Special case: a % 1
201 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
203 tarval *ta = value_of(a);
204 tarval *tb = value_of(b);
206 /* Compute c1 % c2 or a % 1 */
207 if (tb != tarval_bad) {
208 if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb)))) /* div by zero: return tarval_bad */
209 return tarval_mod(ta, tb);
210 else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
211 return get_mode_null(get_irn_mode(a));
218 * return the value of an integer Mod
220 static tarval *computed_value_Mod(ir_node *n)
222 return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
226 * return the value of an Abs
228 static tarval *computed_value_Abs(ir_node *n)
230 ir_node *a = get_Abs_op(n);
231 tarval *ta = value_of(a);
233 if (ta != tarval_bad)
234 return tarval_abs(ta);
240 * return the value of an And
241 * Special case: a & 0, 0 & b
243 static tarval *computed_value_And(ir_node *n)
245 ir_node *a = get_And_left(n);
246 ir_node *b = get_And_right(n);
248 tarval *ta = value_of(a);
249 tarval *tb = value_of(b);
251 if ((ta != tarval_bad) && (tb != tarval_bad)) {
252 return tarval_and (ta, tb);
256 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
257 || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
265 * return the value of an Or
266 * Special case: a | 1...1, 1...1 | b
268 static tarval *computed_value_Or(ir_node *n)
270 ir_node *a = get_Or_left(n);
271 ir_node *b = get_Or_right(n);
273 tarval *ta = value_of(a);
274 tarval *tb = value_of(b);
276 if ((ta != tarval_bad) && (tb != tarval_bad)) {
277 return tarval_or (ta, tb);
280 if ( (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
281 || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
289 * return the value of an Eor
291 static tarval *computed_value_Eor(ir_node *n)
293 ir_node *a = get_Eor_left(n);
294 ir_node *b = get_Eor_right(n);
299 return get_tarval_null(get_irn_mode(n));
304 if ((ta != tarval_bad) && (tb != tarval_bad)) {
305 return tarval_eor (ta, tb);
311 * return the value of a Not
313 static tarval *computed_value_Not(ir_node *n)
315 ir_node *a = get_Not_op(n);
316 tarval *ta = value_of(a);
318 if (ta != tarval_bad)
319 return tarval_not(ta);
325 * return the value of a Shl
327 static tarval *computed_value_Shl(ir_node *n)
329 ir_node *a = get_Shl_left(n);
330 ir_node *b = get_Shl_right(n);
332 tarval *ta = value_of(a);
333 tarval *tb = value_of(b);
335 if ((ta != tarval_bad) && (tb != tarval_bad)) {
336 return tarval_shl (ta, tb);
342 * return the value of a Shr
344 static tarval *computed_value_Shr(ir_node *n)
346 ir_node *a = get_Shr_left(n);
347 ir_node *b = get_Shr_right(n);
349 tarval *ta = value_of(a);
350 tarval *tb = value_of(b);
352 if ((ta != tarval_bad) && (tb != tarval_bad)) {
353 return tarval_shr (ta, tb);
359 * return the value of a Shrs
361 static tarval *computed_value_Shrs(ir_node *n)
363 ir_node *a = get_Shrs_left(n);
364 ir_node *b = get_Shrs_right(n);
366 tarval *ta = value_of(a);
367 tarval *tb = value_of(b);
369 if ((ta != tarval_bad) && (tb != tarval_bad)) {
370 return tarval_shrs (ta, tb);
376 * return the value of a Rot
378 static tarval *computed_value_Rot(ir_node *n)
380 ir_node *a = get_Rot_left(n);
381 ir_node *b = get_Rot_right(n);
383 tarval *ta = value_of(a);
384 tarval *tb = value_of(b);
386 if ((ta != tarval_bad) && (tb != tarval_bad)) {
387 return tarval_rot (ta, tb);
393 * return the value of a Conv
395 static tarval *computed_value_Conv(ir_node *n)
397 ir_node *a = get_Conv_op(n);
398 tarval *ta = value_of(a);
400 if (ta != tarval_bad)
401 return tarval_convert_to(ta, get_irn_mode(n));
407 * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
409 static tarval *computed_value_Proj(ir_node *n)
411 ir_node *a = get_Proj_pred(n);
415 /* Optimize Cmp nodes.
416 This performs a first step of unreachable code elimination.
417 Proj can not be computed, but folding a Cmp above the Proj here is
418 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
420 There are several case where we can evaluate a Cmp node:
421 1. The nodes compared are both the same. If we compare for
422 equal, greater equal, ... this will return true, else it
423 will return false. This step relies on cse.
424 2. The predecessors of Cmp are target values. We can evaluate
426 3. The predecessors are Allocs or void* constants. Allocs never
427 return NULL, they raise an exception. Therefore we can predict
429 switch (get_irn_opcode(a)) {
431 aa = get_Cmp_left(a);
432 ab = get_Cmp_right(a);
433 proj_nr = get_Proj_proj(n);
435 if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
436 /* BEWARE: a == a is NOT always True for floating Point!!! */
437 /* This is a trick with the bits used for encoding the Cmp
438 Proj numbers, the following statement is not the same:
439 return new_tarval_from_long (proj_nr == Eq, mode_b) */
440 return new_tarval_from_long (proj_nr & Eq, mode_b);
442 tarval *taa = value_of(aa);
443 tarval *tab = value_of(ab);
445 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
446 /* strange checks... */
447 pnc_number flags = tarval_cmp (taa, tab);
448 if (flags != False) {
449 return new_tarval_from_long (proj_nr & flags, mode_b);
451 } else { /* check for 3.: */
452 ir_node *aaa = skip_Id(skip_Proj(aa));
453 ir_node *aba = skip_Id(skip_Proj(ab));
455 if ( ( (/* aa is ProjP and aaa is Alloc */
456 (get_irn_op(aa) == op_Proj)
457 && (mode_is_reference(get_irn_mode(aa)))
458 && (get_irn_op(aaa) == op_Alloc))
459 && ( (/* ab is constant void */
460 (get_irn_op(ab) == op_Const)
461 && (mode_is_reference(get_irn_mode(ab)))
462 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
463 || (/* ab is other Alloc */
464 (get_irn_op(ab) == op_Proj)
465 && (mode_is_reference(get_irn_mode(ab)))
466 && (get_irn_op(aba) == op_Alloc)
468 || (/* aa is void and aba is Alloc */
469 (get_irn_op(aa) == op_Const)
470 && (mode_is_reference(get_irn_mode(aa)))
471 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
472 && (get_irn_op(ab) == op_Proj)
473 && (mode_is_reference(get_irn_mode(ab)))
474 && (get_irn_op(aba) == op_Alloc)))
476 return new_tarval_from_long (proj_nr & Ne, mode_b);
482 /* compute either the Div or the Mod part */
483 proj_nr = get_Proj_proj(n);
484 if (proj_nr == pn_DivMod_res_div)
485 return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
486 else if (proj_nr == pn_DivMod_res_mod)
487 return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
491 if (get_Proj_proj(n) == pn_Div_res)
492 return computed_value(a);
496 if (get_Proj_proj(n) == pn_Mod_res)
497 return computed_value(a);
507 * If the parameter n can be computed, return its value, else tarval_bad.
508 * Performs constant folding.
510 * @param n The node this should be evaluated
512 tarval *computed_value(ir_node *n)
514 if (n->op->computed_value)
515 return n->op->computed_value(n);
520 * set the default computed_value evaluator
522 static ir_op *firm_set_default_computed_value(ir_op *op)
526 op->computed_value = computed_value_##a; \
551 op->computed_value = NULL;
559 /* returns 1 if the a and b are pointers to different locations. */
561 different_identity (ir_node *a, ir_node *b)
563 assert (mode_is_reference(get_irn_mode (a))
564 && mode_is_reference(get_irn_mode (b)));
566 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
567 ir_node *a1 = get_Proj_pred (a);
568 ir_node *b1 = get_Proj_pred (b);
569 if (a1 != b1 && get_irn_op (a1) == op_Alloc
570 && get_irn_op (b1) == op_Alloc)
577 static ir_node *equivalent_node_Block(ir_node *n)
581 /* The Block constructor does not call optimize, but mature_immBlock
582 calls the optimization. */
583 assert(get_Block_matured(n));
585 /* Straightening: a single entry Block following a single exit Block
586 can be merged, if it is not the Start block. */
587 /* !!! Beware, all Phi-nodes of n must have been optimized away.
588 This should be true, as the block is matured before optimize is called.
589 But what about Phi-cycles with the Phi0/Id that could not be resolved?
590 Remaining Phi nodes are just Ids. */
591 if ((get_Block_n_cfgpreds(n) == 1) &&
592 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
593 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
594 if (predblock == oldn) {
595 /* Jmp jumps into the block it is in -- deal self cycle. */
597 DBG_OPT_DEAD(oldn, n);
598 } else if (get_opt_control_flow_straightening()) {
600 DBG_OPT_STG(oldn, n);
603 else if ((get_Block_n_cfgpreds(n) == 1) &&
604 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
605 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
606 if (predblock == oldn) {
607 /* Jmp jumps into the block it is in -- deal self cycle. */
609 DBG_OPT_DEAD(oldn, n);
612 else if ((get_Block_n_cfgpreds(n) == 2) &&
613 (get_opt_control_flow_weak_simplification())) {
614 /* Test whether Cond jumps twice to this block
615 @@@ we could do this also with two loops finding two preds from several ones. */
616 ir_node *a = get_Block_cfgpred(n, 0);
617 ir_node *b = get_Block_cfgpred(n, 1);
619 if ((get_irn_op(a) == op_Proj) &&
620 (get_irn_op(b) == op_Proj) &&
621 (get_Proj_pred(a) == get_Proj_pred(b)) &&
622 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
623 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
624 /* Also a single entry Block following a single exit Block. Phis have
625 twice the same operand and will be optimized away. */
626 n = get_nodes_block(a);
627 DBG_OPT_IFSIM(oldn, a, b, n);
629 } else if (get_opt_unreachable_code() &&
630 (n != current_ir_graph->start_block) &&
631 (n != current_ir_graph->end_block) ) {
633 /* If all inputs are dead, this block is dead too, except if it is
634 the start or end block. This is a step of unreachable code
636 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
637 if (!is_Bad(get_Block_cfgpred(n, i))) break;
639 if (i == get_Block_n_cfgpreds(n))
647 * Returns a equivalent node for a Jmp, a Bad :-)
648 * Of course this only happens if the Block of the Jmp is Bad.
650 static ir_node *equivalent_node_Jmp(ir_node *n)
652 /* GL: Why not same for op_Raise?? */
653 /* unreachable code elimination */
654 if (is_Bad(get_nodes_block(n)))
660 static ir_node *equivalent_node_Cond(ir_node *n)
662 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
663 See cases for iro_Cond and iro_Proj in transform_node. */
668 * optimize operations that are commutative and have neutral 0,
669 * so a op 0 = 0 op a = a.
671 static ir_node *equivalent_node_neutral_zero(ir_node *n)
675 ir_node *a = get_binop_left(n);
676 ir_node *b = get_binop_right(n);
681 /* After running compute_node there is only one constant predecessor.
682 Find this predecessors value and remember the other node: */
683 if ((tv = value_of(a)) != tarval_bad) {
685 } else if ((tv = value_of(b)) != tarval_bad) {
690 /* If this predecessors constant value is zero, the operation is
691 unnecessary. Remove it: */
692 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
695 DBG_OPT_ALGSIM1(oldn, a, b, n);
701 #define equivalent_node_Add equivalent_node_neutral_zero
702 #define equivalent_node_Eor equivalent_node_neutral_zero
705 * optimize operations that are not commutative but have neutral 0 on left,
708 static ir_node *equivalent_node_left_zero(ir_node *n)
712 ir_node *a = get_binop_left(n);
713 ir_node *b = get_binop_right(n);
715 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
718 DBG_OPT_ALGSIM1(oldn, a, b, n);
724 #define equivalent_node_Sub equivalent_node_left_zero
725 #define equivalent_node_Shl equivalent_node_left_zero
726 #define equivalent_node_Shr equivalent_node_left_zero
727 #define equivalent_node_Shrs equivalent_node_left_zero
728 #define equivalent_node_Rot equivalent_node_left_zero
731 * Er, a "symmetic unop", ie op(op(n)) = n.
733 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
736 ir_node *pred = get_unop_op(n);
738 /* optimize symmetric unop */
739 if (get_irn_op(pred) == get_irn_op(n)) {
740 n = get_unop_op(pred);
741 DBG_OPT_ALGSIM2(oldn, pred, n);
747 #define equivalent_node_Not equivalent_node_symmetric_unop
749 /* --x == x */ /* ??? Is this possible or can --x raise an
750 out of bounds exception if min =! max? */
751 #define equivalent_node_Minus equivalent_node_symmetric_unop
754 * Optimize a * 1 = 1 * a = a.
756 static ir_node *equivalent_node_Mul(ir_node *n)
760 ir_node *a = get_Mul_left(n);
761 ir_node *b = get_Mul_right(n);
763 /* Mul is commutative and has again an other neutral element. */
764 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
766 DBG_OPT_ALGSIM1(oldn, a, b, n);
767 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
769 DBG_OPT_ALGSIM1(oldn, a, b, n);
775 * Optimize a / 1 = a.
777 static ir_node *equivalent_node_Div(ir_node *n)
779 ir_node *a = get_Div_left(n);
780 ir_node *b = get_Div_right(n);
782 /* Div is not commutative. */
783 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
784 /* Turn Div into a tuple (mem, bad, a) */
785 ir_node *mem = get_Div_mem(n);
786 turn_into_tuple(n, 3);
787 set_Tuple_pred(n, pn_Div_M, mem);
788 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
789 set_Tuple_pred(n, pn_Div_res, a);
795 * Optimize a / 1 = a.
797 static ir_node *equivalent_node_DivMod(ir_node *n)
799 ir_node *a = get_DivMod_left(n);
800 ir_node *b = get_DivMod_right(n);
802 /* Div is not commutative. */
803 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
804 /* Turn DivMod into a tuple (mem, bad, a, 0) */
805 ir_node *mem = get_Div_mem(n);
806 ir_mode *mode = get_irn_mode(b);
808 turn_into_tuple(n, 4);
809 set_Tuple_pred(n, pn_DivMod_M, mem);
810 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
811 set_Tuple_pred(n, pn_DivMod_res_div, a);
812 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
818 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
820 static ir_node *equivalent_node_Or(ir_node *n)
824 ir_node *a = get_Or_left(n);
825 ir_node *b = get_Or_right(n);
828 n = a; /* Or has it's own neutral element */
829 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
831 DBG_OPT_ALGSIM1(oldn, a, b, n);
832 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
834 DBG_OPT_ALGSIM1(oldn, a, b, n);
841 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
843 static ir_node *equivalent_node_And(ir_node *n)
847 ir_node *a = get_And_left(n);
848 ir_node *b = get_And_right(n);
851 n = a; /* And has it's own neutral element */
852 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
854 DBG_OPT_ALGSIM1(oldn, a, b, n);
855 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
857 DBG_OPT_ALGSIM1(oldn, a, b, n);
863 * Try to remove useless conv's:
865 static ir_node *equivalent_node_Conv(ir_node *n)
868 ir_node *a = get_Conv_op(n);
871 ir_mode *n_mode = get_irn_mode(n);
872 ir_mode *a_mode = get_irn_mode(a);
874 if (n_mode == a_mode) { /* No Conv necessary */
876 DBG_OPT_ALGSIM3(oldn, a, n);
877 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
881 n_mode = get_irn_mode(n);
882 b_mode = get_irn_mode(b);
884 if (n_mode == b_mode) {
885 if (n_mode == mode_b) {
886 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
887 DBG_OPT_ALGSIM1(oldn, a, b, n);
889 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
890 if (smaller_mode(b_mode, a_mode)){
891 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
892 DBG_OPT_ALGSIM1(oldn, a, b, n);
901 * A Cast may be removed if the type of the previous node
902 * is already to type of the Cast.
904 static ir_node *equivalent_node_Cast(ir_node *n) {
905 ir_node *pred = get_Cast_op(n);
906 if (get_irn_type(pred) == get_Cast_type(n))
911 /* Several optimizations:
912 - no Phi in start block.
913 - remove Id operators that are inputs to Phi
914 - fold Phi-nodes, iff they have only one predecessor except
917 static ir_node *equivalent_node_Phi(ir_node *n)
922 ir_node *block = NULL; /* to shutup gcc */
923 ir_node *first_val = NULL; /* to shutup gcc */
924 ir_node *scnd_val = NULL; /* to shutup gcc */
926 if (!get_opt_normalize()) return n;
928 n_preds = get_Phi_n_preds(n);
930 block = get_nodes_block(n);
931 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
932 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
933 if ((is_Bad(block)) || /* Control dead */
934 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
935 return new_Bad(); /* in the Start Block. */
937 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
940 /* first we test for a special case: */
941 /* Confirm is a special node fixing additional information for a
942 value that is known at a certain point. This is useful for
943 dataflow analysis. */
945 ir_node *a = get_Phi_pred(n, 0);
946 ir_node *b = get_Phi_pred(n, 1);
947 if ( (get_irn_op(a) == op_Confirm)
948 && (get_irn_op(b) == op_Confirm)
949 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
950 && (get_irn_n(a, 1) == get_irn_n (b, 1))
951 && (a->data.num == (~b->data.num & irpn_True) )) {
952 return get_irn_n(a, 0);
957 /* If the Block has a Bad pred, we also have one. */
958 for (i = 0; i < n_preds; ++i)
959 if (is_Bad (get_Block_cfgpred(block, i)))
960 set_Phi_pred(n, i, new_Bad());
962 /* Find first non-self-referencing input */
963 for (i = 0; i < n_preds; ++i) {
964 first_val = get_Phi_pred(n, i);
965 if ( (first_val != n) /* not self pointer */
967 && (get_irn_op(first_val) != op_Bad)
969 ) { /* value not dead */
970 break; /* then found first value. */
974 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
975 if (i >= n_preds) { return new_Bad(); }
979 /* follow_Id () for rest of inputs, determine if any of these
980 are non-self-referencing */
981 while (++i < n_preds) {
982 scnd_val = get_Phi_pred(n, i);
984 && (scnd_val != first_val)
986 && (get_irn_op(scnd_val) != op_Bad)
993 /* Fold, if no multiple distinct non-self-referencing inputs */
996 DBG_OPT_PHI(oldn, first_val, n);
998 /* skip the remaining Ids (done in get_Phi_pred). */
999 /* superfluous, since we walk all to propagate Block's Bads.
1000 while (++i < n_preds) get_Phi_pred(n, i); */
1006 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1008 static ir_node *equivalent_node_Proj(ir_node *n)
1012 ir_node *a = get_Proj_pred(n);
1014 if ( get_irn_op(a) == op_Tuple) {
1015 /* Remove the Tuple/Proj combination. */
1016 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1017 n = get_Tuple_pred(a, get_Proj_proj(n));
1018 DBG_OPT_TUPLE(oldn, a, n);
1020 assert(0); /* This should not happen! */
1023 } else if (get_irn_mode(n) == mode_X &&
1024 is_Bad(get_nodes_block(n))) {
1025 /* Remove dead control flow -- early gigo. */
1034 static ir_node *equivalent_node_Id(ir_node *n)
1039 DBG_OPT_ID(oldn, n);
1044 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1045 * perform no actual computation, as, e.g., the Id nodes. It does not create
1046 * new nodes. It is therefore safe to free n if the node returned is not n.
1047 * If a node returns a Tuple we can not just skip it. If the size of the
1048 * in array fits, we transform n into a tuple (e.g., Div).
1051 equivalent_node(ir_node *n)
1053 if (n->op->equivalent_node)
1054 return n->op->equivalent_node(n);
1059 * set the default equivalent node operation
1061 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1065 op->equivalent_node = equivalent_node_##a; \
1092 op->equivalent_node = NULL;
1100 * Do node specific optimizations of nodes predecessors.
1103 optimize_preds(ir_node *n) {
1104 ir_node *a = NULL, *b = NULL;
1106 /* get the operands we will work on for simple cases. */
1108 a = get_binop_left(n);
1109 b = get_binop_right(n);
1110 } else if (is_unop(n)) {
1114 switch (get_irn_opcode(n)) {
1117 /* We don't want Cast as input to Cmp. */
1118 if (get_irn_op(a) == op_Cast) {
1122 if (get_irn_op(b) == op_Cast) {
1124 set_Cmp_right(n, b);
1133 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1134 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1136 static ir_node *transform_node_AddSub(ir_node *n)
1138 ir_mode *mode = get_irn_mode(n);
1140 if (mode_is_reference(mode)) {
1141 ir_node *left = get_binop_left(n);
1142 ir_node *right = get_binop_right(n);
1143 int ref_bits = get_mode_size_bits(mode);
1145 if (get_irn_op(left) == op_Conv) {
1146 ir_mode *mode = get_irn_mode(left);
1147 int bits = get_mode_size_bits(mode);
1149 if (ref_bits == bits &&
1150 mode_is_int(mode) &&
1151 get_mode_arithmetic(mode) == irma_twos_complement) {
1152 ir_node *pre = get_Conv_op(left);
1153 ir_mode *pre_mode = get_irn_mode(pre);
1155 if (mode_is_int(pre_mode) &&
1156 get_mode_size_bits(pre_mode) == bits &&
1157 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1158 /* ok, this conv just changes to sign, moreover the calculation
1159 * is done with same number of bits as our address mode, so
1160 * we can ignore the conv as address calculation can be viewed
1161 * as either signed or unsigned
1163 set_binop_left(n, pre);
1168 if (get_irn_op(right) == op_Conv) {
1169 ir_mode *mode = get_irn_mode(right);
1170 int bits = get_mode_size_bits(mode);
1172 if (ref_bits == bits &&
1173 mode_is_int(mode) &&
1174 get_mode_arithmetic(mode) == irma_twos_complement) {
1175 ir_node *pre = get_Conv_op(right);
1176 ir_mode *pre_mode = get_irn_mode(pre);
1178 if (mode_is_int(pre_mode) &&
1179 get_mode_size_bits(pre_mode) == bits &&
1180 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1181 /* ok, this conv just changes to sign, moreover the calculation
1182 * is done with same number of bits as our address mode, so
1183 * we can ignore the conv as address calculation can be viewed
1184 * as either signed or unsigned
1186 set_binop_right(n, pre);
1194 #define transform_node_Add transform_node_AddSub
1195 #define transform_node_Sub transform_node_AddSub
1197 /** Do architecture dependend optimizations on Mul nodes */
1198 static ir_node *transform_node_Mul(ir_node *n) {
1199 return arch_dep_replace_mul_with_shifts(n);
1202 static ir_node *transform_node_Div(ir_node *n)
1204 tarval *tv = value_of(n);
1207 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1209 if (tv != tarval_bad)
1210 value = new_Const(get_tarval_mode(tv), tv);
1211 else /* Try architecture dependand optimization */
1212 value = arch_dep_replace_div_by_const(n);
1215 /* Turn Div into a tuple (mem, bad, value) */
1216 ir_node *mem = get_Div_mem(n);
1218 turn_into_tuple(n, 3);
1219 set_Tuple_pred(n, pn_Div_M, mem);
1220 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1221 set_Tuple_pred(n, pn_Div_res, value);
1226 static ir_node *transform_node_Mod(ir_node *n)
1228 tarval *tv = value_of(n);
1231 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1233 if (tv != tarval_bad)
1234 value = new_Const(get_tarval_mode(tv), tv);
1235 else /* Try architecture dependand optimization */
1236 value = arch_dep_replace_mod_by_const(n);
1239 /* Turn Mod into a tuple (mem, bad, value) */
1240 ir_node *mem = get_Mod_mem(n);
1242 turn_into_tuple(n, 3);
1243 set_Tuple_pred(n, pn_Mod_M, mem);
1244 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1245 set_Tuple_pred(n, pn_Mod_res, value);
1250 static ir_node *transform_node_DivMod(ir_node *n)
1254 ir_node *a = get_DivMod_left(n);
1255 ir_node *b = get_DivMod_right(n);
1256 ir_mode *mode = get_irn_mode(a);
1257 tarval *ta = value_of(a);
1258 tarval *tb = value_of(b);
1260 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1263 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1265 if (tb != tarval_bad) {
1266 if (tb == get_mode_one(get_tarval_mode(tb))) {
1267 b = new_Const (mode, get_mode_null(mode));
1269 } else if (ta != tarval_bad) {
1270 tarval *resa, *resb;
1271 resa = tarval_div (ta, tb);
1272 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1273 Jmp for X result!? */
1274 resb = tarval_mod (ta, tb);
1275 if (resb == tarval_bad) return n; /* Causes exception! */
1276 a = new_Const (mode, resa);
1277 b = new_Const (mode, resb);
1280 else { /* Try architecture dependand optimization */
1281 arch_dep_replace_divmod_by_const(&a, &b, n);
1282 evaluated = a != NULL;
1284 } else if (ta == get_mode_null(mode)) {
1285 /* 0 / non-Const = 0 */
1290 if (evaluated) { /* replace by tuple */
1291 ir_node *mem = get_DivMod_mem(n);
1292 turn_into_tuple(n, 4);
1293 set_Tuple_pred(n, pn_DivMod_M, mem);
1294 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1295 set_Tuple_pred(n, pn_DivMod_res_div, a);
1296 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1297 assert(get_nodes_block(n));
1303 static ir_node *transform_node_Cond(ir_node *n)
1305 /* Replace the Cond by a Jmp if it branches on a constant
1308 ir_node *a = get_Cond_selector(n);
1309 tarval *ta = value_of(a);
1311 if ((ta != tarval_bad) &&
1312 (get_irn_mode(a) == mode_b) &&
1313 (get_opt_unreachable_code())) {
1314 /* It's a boolean Cond, branching on a boolean constant.
1315 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1316 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1317 turn_into_tuple(n, 2);
1318 if (ta == tarval_b_true) {
1319 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1320 set_Tuple_pred(n, pn_Cond_true, jmp);
1322 set_Tuple_pred(n, pn_Cond_false, jmp);
1323 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1325 /* We might generate an endless loop, so keep it alive. */
1326 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1327 } else if ((ta != tarval_bad) &&
1328 (get_irn_mode(a) == mode_Iu) &&
1329 (get_Cond_kind(n) == dense) &&
1330 (get_opt_unreachable_code())) {
1331 /* I don't want to allow Tuples smaller than the biggest Proj.
1332 Also this tuple might get really big...
1333 I generate the Jmp here, and remember it in link. Link is used
1334 when optimizing Proj. */
1335 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1336 /* We might generate an endless loop, so keep it alive. */
1337 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1338 } else if ((get_irn_op(a) == op_Eor)
1339 && (get_irn_mode(a) == mode_b)
1340 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1341 /* The Eor is a negate. Generate a new Cond without the negate,
1342 simulate the negate by exchanging the results. */
1343 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1345 } else if ((get_irn_op(a) == op_Not)
1346 && (get_irn_mode(a) == mode_b)) {
1347 /* A Not before the Cond. Generate a new Cond without the Not,
1348 simulate the Not by exchanging the results. */
1349 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1358 static ir_node *transform_node_Eor(ir_node *n)
1360 ir_node *a = get_Eor_left(n);
1361 ir_node *b = get_Eor_right(n);
1363 if ((get_irn_mode(n) == mode_b)
1364 && (get_irn_op(a) == op_Proj)
1365 && (get_irn_mode(a) == mode_b)
1366 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1367 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1368 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1369 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1370 mode_b, get_negated_pnc(get_Proj_proj(a)));
1371 else if ((get_irn_mode(n) == mode_b)
1372 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1373 /* The Eor is a Not. Replace it by a Not. */
1374 /* ????!!!Extend to bitfield 1111111. */
1375 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1381 * Transform a boolean Not.
1383 static ir_node *transform_node_Not(ir_node *n)
1385 ir_node *a = get_Not_op(n);
1387 if ( (get_irn_mode(n) == mode_b)
1388 && (get_irn_op(a) == op_Proj)
1389 && (get_irn_mode(a) == mode_b)
1390 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1391 /* We negate a Cmp. The Cmp has the negated result anyways! */
1392 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1393 mode_b, get_negated_pnc(get_Proj_proj(a)));
1399 * Transform a Cast of a Const into a new Const
1401 static ir_node *transform_node_Cast(ir_node *n) {
1402 ir_node *pred = get_Cast_op(n);
1403 type *tp = get_irn_type(pred);
1405 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1406 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1407 get_Const_tarval(pred), tp);
1408 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1409 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1410 get_SymConst_kind(pred), tp);
1416 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1417 * done here instead of equivalent node because it creates new
1419 * Removes the exceptions and routes the memory to the NoMem node.
1421 * Further, it optimizes jump tables by removing all impossible cases.
1423 static ir_node *transform_node_Proj(ir_node *proj)
1425 ir_node *n = get_Proj_pred(proj);
1430 switch (get_irn_opcode(n)) {
1432 b = get_Div_right(n);
1435 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1436 proj_nr = get_Proj_proj(proj);
1438 /* this node may float */
1439 set_irn_pinned(n, op_pin_state_floats);
1441 if (proj_nr == pn_Div_X_except) {
1442 /* we found an exception handler, remove it */
1445 /* the memory Proj can be removed */
1446 ir_node *res = get_Div_mem(n);
1448 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1449 # endif /* defined USE_NOMEM */
1450 if (proj_nr == pn_Div_M)
1456 b = get_Mod_right(n);
1459 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1460 proj_nr = get_Proj_proj(proj);
1462 /* this node may float */
1463 set_irn_pinned(n, op_pin_state_floats);
1465 if (proj_nr == pn_Mod_X_except) {
1466 /* we found an exception handler, remove it */
1469 /* the memory Proj can be removed */
1470 ir_node *res = get_Mod_mem(n);
1472 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1473 # endif /* defined USE_NOMEM */
1474 if (proj_nr == pn_Mod_M)
1480 b = get_DivMod_right(n);
1483 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1484 proj_nr = get_Proj_proj(proj);
1486 /* this node may float */
1487 set_irn_pinned(n, op_pin_state_floats);
1489 if (proj_nr == pn_DivMod_X_except) {
1490 /* we found an exception handler, remove it */
1494 /* the memory Proj can be removed */
1495 ir_node *res = get_DivMod_mem(n);
1497 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1498 # endif /* defined USE_NOMEM */
1499 if (proj_nr == pn_DivMod_M)
1506 if (get_opt_unreachable_code()) {
1507 b = get_Cond_selector(n);
1510 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1511 /* we have a constant switch */
1512 long num = get_Proj_proj(proj);
1514 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1515 if (get_tarval_long(tb) == num) {
1516 /* Do NOT create a jump here, or we will have 2 control flow ops
1517 * in a block. This case is optimized away in optimize_cf(). */
1528 /* should not happen, but if it does will be optimized away */
1536 /* we have added a Tuple, optimize it for the current Proj away */
1537 return equivalent_node_Proj(proj);
1541 * returns the operands of a commutative bin-op, if one operand is
1542 * a const, it is returned as the second one.
1544 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1546 ir_node *op_a = get_binop_left(binop);
1547 ir_node *op_b = get_binop_right(binop);
1549 assert(is_op_commutative(get_irn_op(binop)));
1551 if (get_irn_op(op_a) == op_Const) {
1562 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1563 * Such pattern may arise in bitfield stores.
1565 * value c4 value c4 & c2
1566 * AND c3 AND c1 | c3
1571 static ir_node *transform_node_Or(ir_node *or)
1575 ir_node *and_l, *c3;
1576 ir_node *value, *c4;
1577 ir_node *new_and, *new_const, *block;
1578 ir_mode *mode = get_irn_mode(or);
1580 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1582 get_comm_Binop_Ops(or, &and, &c1);
1583 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1586 get_comm_Binop_Ops(and, &or_l, &c2);
1587 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1590 get_comm_Binop_Ops(or_l, &and_l, &c3);
1591 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1594 get_comm_Binop_Ops(and_l, &value, &c4);
1595 if (get_irn_op(c4) != op_Const)
1598 /* ok, found the pattern, check for conditions */
1599 assert(mode == get_irn_mode(and));
1600 assert(mode == get_irn_mode(or_l));
1601 assert(mode == get_irn_mode(and_l));
1603 tv1 = get_Const_tarval(c1);
1604 tv2 = get_Const_tarval(c2);
1605 tv3 = get_Const_tarval(c3);
1606 tv4 = get_Const_tarval(c4);
1608 tv = tarval_or(tv4, tv2);
1609 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1610 /* have at least one 0 at the same bit position */
1614 n_tv4 = tarval_not(tv4);
1615 if (tv3 != tarval_and(tv3, n_tv4)) {
1616 /* bit in the or_mask is outside the and_mask */
1620 n_tv2 = tarval_not(tv2);
1621 if (tv1 != tarval_and(tv1, n_tv2)) {
1622 /* bit in the or_mask is outside the and_mask */
1626 /* ok, all conditions met */
1627 block = get_nodes_block(or);
1629 new_and = new_r_And(current_ir_graph, block,
1630 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1632 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1634 set_Or_left(or, new_and);
1635 set_Or_right(or, new_const);
1637 /* check for more */
1638 return transform_node_Or(or);
1642 static ir_node *transform_node(ir_node *n);
1645 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1647 static ir_node * transform_node_shift(ir_node *n)
1650 tarval *tv1, *tv2, *res;
1652 int modulo_shf, flag;
1654 left = get_binop_left(n);
1656 /* different operations */
1657 if (get_irn_op(left) != get_irn_op(n))
1660 tv1 = value_of(get_binop_right(n));
1661 if (tv1 == tarval_bad)
1664 tv2 = value_of(get_binop_right(left));
1665 if (tv2 == tarval_bad)
1668 res = tarval_add(tv1, tv2);
1670 /* beware: a simple replacement works only, if res < modulo shift */
1671 mode = get_irn_mode(n);
1675 modulo_shf = get_mode_modulo_shift(mode);
1676 if (modulo_shf > 0) {
1677 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1679 if (tarval_cmp(res, modulo) & Lt)
1686 /* ok, we can replace it */
1687 ir_node *in[2], *irn, *block = get_nodes_block(n);
1689 in[0] = get_binop_left(left);
1690 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1692 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1694 return transform_node(irn);
1701 * Tries several [inplace] [optimizing] transformations and returns an
1702 * equivalent node. The difference to equivalent_node() is that these
1703 * transformations _do_ generate new nodes, and thus the old node must
1704 * not be freed even if the equivalent node isn't the old one.
1706 static ir_node *transform_node(ir_node *n)
1708 if (n->op->transform_node)
1709 n = n->op->transform_node(n);
1714 * set the default transform node operation
1716 static ir_op *firm_set_default_transform_node(ir_op *op)
1720 op->transform_node = transform_node_##a; \
1739 op->transform_node = transform_node_shift;
1742 op->transform_node = NULL;
1750 /* **************** Common Subexpression Elimination **************** */
1752 /** The size of the hash table used, should estimate the number of nodes
1754 #define N_IR_NODES 512
1756 /** Compares the attributes of two Const nodes. */
1757 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1759 return (get_Const_tarval(a) != get_Const_tarval(b))
1760 || (get_Const_type(a) != get_Const_type(b));
1763 /** Compares the attributes of two Proj nodes. */
1764 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1766 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1769 /** Compares the attributes of two Filter nodes. */
1770 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1772 return get_Filter_proj(a) != get_Filter_proj(b);
1775 /** Compares the attributes of two Alloc nodes. */
1776 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1778 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1779 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1782 /** Compares the attributes of two Free nodes. */
1783 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1785 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1788 /** Compares the attributes of two SymConst nodes. */
1789 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1791 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1792 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1793 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1796 /** Compares the attributes of two Call nodes. */
1797 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1799 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1802 /** Compares the attributes of two Sel nodes. */
1803 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1805 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1806 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1807 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1808 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1809 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1812 /** Compares the attributes of two Phi nodes. */
1813 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1815 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1818 /** Compares the attributes of two Cast nodes. */
1819 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1821 return get_Cast_type(a) != get_Cast_type(b);
1824 /** Compares the attributes of two Load nodes. */
1825 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1827 if (get_Load_volatility(a) == volatility_is_volatile ||
1828 get_Load_volatility(b) == volatility_is_volatile)
1829 /* NEVER do CSE on volatile Loads */
1832 return get_Load_mode(a) != get_Load_mode(b);
1835 /** Compares the attributes of two Store nodes. */
1836 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1838 /* NEVER do CSE on volatile Stores */
1839 return (get_Store_volatility(a) == volatility_is_volatile ||
1840 get_Store_volatility(b) == volatility_is_volatile);
1844 * set the default node attribute compare operation
1846 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1850 op->node_cmp_attr = node_cmp_attr_##a; \
1867 op->node_cmp_attr = NULL;
1875 * Compare function for two nodes in the hash table. Gets two
1876 * nodes as parameters. Returns 0 if the nodes are a cse.
1879 vt_cmp (const void *elt, const void *key)
1887 if (a == b) return 0;
1889 if ((get_irn_op(a) != get_irn_op(b)) ||
1890 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1892 /* compare if a's in and b's in are of equal length */
1893 irn_arity_a = get_irn_intra_arity (a);
1894 if (irn_arity_a != get_irn_intra_arity(b))
1897 /* for block-local cse and op_pin_state_pinned nodes: */
1898 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1899 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1903 /* compare a->in[0..ins] with b->in[0..ins] */
1904 for (i = 0; i < irn_arity_a; i++)
1905 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1909 * here, we already now that the nodes are identical except their
1912 if (a->op->node_cmp_attr)
1913 return a->op->node_cmp_attr(a, b);
1919 * Calculate a hash value of a node.
1922 ir_node_hash (ir_node *node)
1927 if (node->op == op_Const) {
1928 /* special value for const, as they only differ in their tarval. */
1929 h = HASHPTR(node->attr.con.tv);
1930 h = 9*h + HASHPTR(get_irn_mode(node));
1931 } else if (node->op == op_SymConst) {
1932 /* special value for const, as they only differ in their symbol. */
1933 h = HASHPTR(node->attr.i.sym.type_p);
1934 h = 9*h + HASHPTR(get_irn_mode(node));
1937 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1938 h = irn_arity = get_irn_intra_arity(node);
1940 /* consider all in nodes... except the block if not a control flow. */
1941 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1942 h = 9*h + HASHPTR(get_irn_intra_n(node, i));
1946 h = 9*h + HASHPTR(get_irn_mode(node));
1948 h = 9*h + HASHPTR(get_irn_op(node));
1955 new_identities(void) {
1956 return new_pset(vt_cmp, N_IR_NODES);
1960 del_identities(pset *value_table) {
1961 del_pset(value_table);
1965 * Return the canonical node computing the same value as n.
1966 * Looks up the node in a hash table.
1968 * For Const nodes this is performed in the constructor, too. Const
1969 * nodes are extremely time critical because of their frequent use in
1970 * constant string arrays.
1972 static INLINE ir_node *
1973 identify (pset *value_table, ir_node *n)
1977 if (!value_table) return n;
1979 if (get_opt_reassociation()) {
1980 if (is_op_commutative(get_irn_op(n))) {
1981 ir_node *l = get_binop_left(n);
1982 ir_node *r = get_binop_right(n);
1984 /* for commutative operators perform a OP b == b OP a */
1986 set_binop_left(n, r);
1987 set_binop_right(n, l);
1992 o = pset_find (value_table, n, ir_node_hash (n));
2001 * During construction we set the op_pin_state_pinned flag in the graph right when the
2002 * optimization is performed. The flag turning on procedure global cse could
2003 * be changed between two allocations. This way we are safe.
2005 static INLINE ir_node *
2006 identify_cons (pset *value_table, ir_node *n) {
2009 n = identify(value_table, n);
2010 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2011 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2016 * Return the canonical node computing the same value as n.
2017 * Looks up the node in a hash table, enters it in the table
2018 * if it isn't there yet.
2021 identify_remember (pset *value_table, ir_node *n)
2025 if (!value_table) return n;
2027 if (get_opt_reassociation()) {
2028 if (is_op_commutative(get_irn_op(n))) {
2029 ir_node *l = get_binop_left(n);
2030 ir_node *r = get_binop_right(n);
2032 /* for commutative operators perform a OP b == b OP a */
2034 set_binop_left(n, r);
2035 set_binop_right(n, l);
2040 /* lookup or insert in hash table with given hash key. */
2041 o = pset_insert (value_table, n, ir_node_hash (n));
2051 add_identities (pset *value_table, ir_node *node) {
2052 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2053 identify_remember (value_table, node);
2057 * garbage in, garbage out. If a node has a dead input, i.e., the
2058 * Bad node is input to the node, return the Bad node.
2060 static INLINE ir_node *
2061 gigo (ir_node *node)
2064 ir_op* op = get_irn_op(node);
2066 /* remove garbage blocks by looking at control flow that leaves the block
2067 and replacing the control flow by Bad. */
2068 if (get_irn_mode(node) == mode_X) {
2069 ir_node *block = get_nodes_block(node);
2070 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2071 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2072 irn_arity = get_irn_arity(block);
2073 for (i = 0; i < irn_arity; i++) {
2074 if (!is_Bad(get_irn_n(block, i))) break;
2076 if (i == irn_arity) return new_Bad();
2080 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2081 blocks predecessors is dead. */
2082 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2083 irn_arity = get_irn_arity(node);
2084 for (i = -1; i < irn_arity; i++) {
2085 if (is_Bad(get_irn_n(node, i))) {
2091 /* With this code we violate the agreement that local_optimize
2092 only leaves Bads in Block, Phi and Tuple nodes. */
2093 /* If Block has only Bads as predecessors it's garbage. */
2094 /* If Phi has only Bads as predecessors it's garbage. */
2095 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2096 irn_arity = get_irn_arity(node);
2097 for (i = 0; i < irn_arity; i++) {
2098 if (!is_Bad(get_irn_n(node, i))) break;
2100 if (i == irn_arity) node = new_Bad();
2108 * These optimizations deallocate nodes from the obstack.
2109 * It can only be called if it is guaranteed that no other nodes
2110 * reference this one, i.e., right after construction of a node.
2113 optimize_node (ir_node *n)
2117 opcode iro = get_irn_opcode(n);
2119 type *old_tp = get_irn_type(n);
2121 int i, arity = get_irn_arity(n);
2122 for (i = 0; i < arity && !old_tp; ++i)
2123 old_tp = get_irn_type(get_irn_n(n, i));
2126 /* Allways optimize Phi nodes: part of the construction. */
2127 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2129 /* constant expression evaluation / constant folding */
2130 if (get_opt_constant_folding()) {
2131 /* constants can not be evaluated */
2132 if (iro != iro_Const) {
2133 /* try to evaluate */
2134 tv = computed_value(n);
2135 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2137 * we MUST copy the node here temporary, because it's still needed
2138 * for DBG_OPT_CSTEVAL
2140 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2141 oldn = alloca(node_size);
2143 memcpy(oldn, n, node_size);
2144 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2146 /* ARG, copy the in array, we need it for statistics */
2147 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2149 /* evaluation was successful -- replace the node. */
2150 obstack_free (current_ir_graph->obst, n);
2151 n = new_Const (get_tarval_mode (tv), tv);
2152 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2153 set_Const_type(n, old_tp);
2154 DBG_OPT_CSTEVAL(oldn, n);
2160 /* remove unnecessary nodes */
2161 if (get_opt_constant_folding() ||
2162 (iro == iro_Phi) || /* always optimize these nodes. */
2164 (iro == iro_Proj) ||
2165 (iro == iro_Block) ) /* Flags tested local. */
2166 n = equivalent_node (n);
2168 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2170 /** common subexpression elimination **/
2171 /* Checks whether n is already available. */
2172 /* The block input is used to distinguish different subexpressions. Right
2173 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2174 subexpressions within a block. */
2176 n = identify_cons (current_ir_graph->value_table, n);
2179 /* We found an existing, better node, so we can deallocate the old node. */
2180 obstack_free (current_ir_graph->obst, oldn);
2185 /* Some more constant expression evaluation that does not allow to
2187 iro = get_irn_opcode(n);
2188 if (get_opt_constant_folding() ||
2189 (iro == iro_Cond) ||
2190 (iro == iro_Proj)) /* Flags tested local. */
2191 n = transform_node (n);
2193 /* Remove nodes with dead (Bad) input.
2194 Run always for transformation induced Bads. */
2197 /* Now we have a legal, useful node. Enter it in hash table for cse */
2198 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2199 n = identify_remember (current_ir_graph->value_table, n);
2207 * These optimizations never deallocate nodes. This can cause dead
2208 * nodes lying on the obstack. Remove these by a dead node elimination,
2209 * i.e., a copying garbage collection.
2212 optimize_in_place_2 (ir_node *n)
2216 opcode iro = get_irn_opcode(n);
2218 type *old_tp = get_irn_type(n);
2220 int i, arity = get_irn_arity(n);
2221 for (i = 0; i < arity && !old_tp; ++i)
2222 old_tp = get_irn_type(get_irn_n(n, i));
2225 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2227 /* if not optimize return n */
2230 /* Here this is possible. Why? */
2234 /* constant expression evaluation / constant folding */
2235 if (get_opt_constant_folding()) {
2236 /* constants can not be evaluated */
2237 if (iro != iro_Const) {
2238 /* try to evaluate */
2239 tv = computed_value(n);
2240 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2241 /* evaluation was successful -- replace the node. */
2242 n = new_Const (get_tarval_mode (tv), tv);
2244 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2245 set_Const_type(n, old_tp);
2247 DBG_OPT_CSTEVAL(oldn, n);
2253 /* remove unnecessary nodes */
2254 if (get_opt_constant_folding() ||
2255 (iro == iro_Phi) || /* always optimize these nodes. */
2256 (iro == iro_Id) || /* ... */
2257 (iro == iro_Proj) || /* ... */
2258 (iro == iro_Block) ) /* Flags tested local. */
2259 n = equivalent_node (n);
2261 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2263 /** common subexpression elimination **/
2264 /* Checks whether n is already available. */
2265 /* The block input is used to distinguish different subexpressions. Right
2266 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2267 subexpressions within a block. */
2268 if (get_opt_cse()) {
2269 n = identify (current_ir_graph->value_table, n);
2272 /* Some more constant expression evaluation. */
2273 iro = get_irn_opcode(n);
2274 if (get_opt_constant_folding() ||
2275 (iro == iro_Cond) ||
2276 (iro == iro_Proj)) /* Flags tested local. */
2277 n = transform_node (n);
2279 /* Remove nodes with dead (Bad) input.
2280 Run always for transformation induced Bads. */
2283 /* Now we can verify the node, as it has no dead inputs any more. */
2286 /* Now we have a legal, useful node. Enter it in hash table for cse.
2287 Blocks should be unique anyways. (Except the successor of start:
2288 is cse with the start block!) */
2289 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2290 n = identify_remember (current_ir_graph->value_table, n);
2296 * Wrapper for external use, set proper status bits after optimization.
2299 optimize_in_place (ir_node *n)
2301 /* Handle graph state */
2302 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2304 if (get_opt_global_cse())
2305 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2306 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2307 set_irg_outs_inconsistent(current_ir_graph);
2309 /* Maybe we could also test whether optimizing the node can
2310 change the control graph. */
2311 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2312 set_irg_dom_inconsistent(current_ir_graph);
2313 return optimize_in_place_2 (n);
2317 * set the default ir op operations
2319 ir_op *firm_set_default_operations(ir_op *op)
2321 op = firm_set_default_computed_value(op);
2322 op = firm_set_default_equivalent_node(op);
2323 op = firm_set_default_transform_node(op);
2324 op = firm_set_default_node_cmp_attr(op);