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);
100 if (a == b && !is_Bad(a))
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. */
596 n = set_Block_dead(n);
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. */
608 n = set_Block_dead(n);
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) ) {
632 int i, n_cfg = get_Block_n_cfgpreds(n);
634 /* If all inputs are dead, this block is dead too, except if it is
635 the start or end block. This is a step of unreachable code
637 for (i = 0; i < n_cfg; i++) {
638 ir_node *pred = get_Block_cfgpred(n, i);
641 if (is_Bad(pred)) continue;
642 pred_blk = get_nodes_block(pred);
644 if (is_Block_dead(pred_blk)) continue;
647 /* really found a living input */
652 n = set_Block_dead(n);
659 * Returns a equivalent node for a Jmp, a Bad :-)
660 * Of course this only happens if the Block of the Jmp is Bad.
662 static ir_node *equivalent_node_Jmp(ir_node *n)
664 /* GL: Why not same for op_Raise?? */
665 /* unreachable code elimination */
666 if (is_Block_dead(get_nodes_block(n)))
672 static ir_node *equivalent_node_Cond(ir_node *n)
674 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
675 See cases for iro_Cond and iro_Proj in transform_node. */
680 * optimize operations that are commutative and have neutral 0,
681 * so a op 0 = 0 op a = a.
683 static ir_node *equivalent_node_neutral_zero(ir_node *n)
687 ir_node *a = get_binop_left(n);
688 ir_node *b = get_binop_right(n);
693 /* After running compute_node there is only one constant predecessor.
694 Find this predecessors value and remember the other node: */
695 if ((tv = value_of(a)) != tarval_bad) {
697 } else if ((tv = value_of(b)) != tarval_bad) {
702 /* If this predecessors constant value is zero, the operation is
703 unnecessary. Remove it: */
704 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
707 DBG_OPT_ALGSIM1(oldn, a, b, n);
713 #define equivalent_node_Add equivalent_node_neutral_zero
714 #define equivalent_node_Eor equivalent_node_neutral_zero
717 * optimize operations that are not commutative but have neutral 0 on left,
720 static ir_node *equivalent_node_left_zero(ir_node *n)
724 ir_node *a = get_binop_left(n);
725 ir_node *b = get_binop_right(n);
727 if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
730 DBG_OPT_ALGSIM1(oldn, a, b, n);
736 #define equivalent_node_Sub equivalent_node_left_zero
737 #define equivalent_node_Shl equivalent_node_left_zero
738 #define equivalent_node_Shr equivalent_node_left_zero
739 #define equivalent_node_Shrs equivalent_node_left_zero
740 #define equivalent_node_Rot equivalent_node_left_zero
743 * Er, a "symmetic unop", ie op(op(n)) = n.
745 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
748 ir_node *pred = get_unop_op(n);
750 /* optimize symmetric unop */
751 if (get_irn_op(pred) == get_irn_op(n)) {
752 n = get_unop_op(pred);
753 DBG_OPT_ALGSIM2(oldn, pred, n);
759 #define equivalent_node_Not equivalent_node_symmetric_unop
761 /* --x == x */ /* ??? Is this possible or can --x raise an
762 out of bounds exception if min =! max? */
763 #define equivalent_node_Minus equivalent_node_symmetric_unop
766 * Optimize a * 1 = 1 * a = a.
768 static ir_node *equivalent_node_Mul(ir_node *n)
772 ir_node *a = get_Mul_left(n);
773 ir_node *b = get_Mul_right(n);
775 /* Mul is commutative and has again an other neutral element. */
776 if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
778 DBG_OPT_ALGSIM1(oldn, a, b, n);
779 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
781 DBG_OPT_ALGSIM1(oldn, a, b, n);
787 * Optimize a / 1 = a.
789 static ir_node *equivalent_node_Div(ir_node *n)
791 ir_node *a = get_Div_left(n);
792 ir_node *b = get_Div_right(n);
794 /* Div is not commutative. */
795 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
796 /* Turn Div into a tuple (mem, bad, a) */
797 ir_node *mem = get_Div_mem(n);
798 turn_into_tuple(n, 3);
799 set_Tuple_pred(n, pn_Div_M, mem);
800 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
801 set_Tuple_pred(n, pn_Div_res, a);
807 * Optimize a / 1 = a.
809 static ir_node *equivalent_node_DivMod(ir_node *n)
811 ir_node *a = get_DivMod_left(n);
812 ir_node *b = get_DivMod_right(n);
814 /* Div is not commutative. */
815 if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
816 /* Turn DivMod into a tuple (mem, bad, a, 0) */
817 ir_node *mem = get_Div_mem(n);
818 ir_mode *mode = get_irn_mode(b);
820 turn_into_tuple(n, 4);
821 set_Tuple_pred(n, pn_DivMod_M, mem);
822 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
823 set_Tuple_pred(n, pn_DivMod_res_div, a);
824 set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
830 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
832 static ir_node *equivalent_node_Or(ir_node *n)
836 ir_node *a = get_Or_left(n);
837 ir_node *b = get_Or_right(n);
840 n = a; /* Or has it's own neutral element */
841 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
843 DBG_OPT_ALGSIM1(oldn, a, b, n);
844 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
846 DBG_OPT_ALGSIM1(oldn, a, b, n);
853 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
855 static ir_node *equivalent_node_And(ir_node *n)
859 ir_node *a = get_And_left(n);
860 ir_node *b = get_And_right(n);
863 n = a; /* And has it's own neutral element */
864 } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
866 DBG_OPT_ALGSIM1(oldn, a, b, n);
867 } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
869 DBG_OPT_ALGSIM1(oldn, a, b, n);
875 * Try to remove useless conv's:
877 static ir_node *equivalent_node_Conv(ir_node *n)
880 ir_node *a = get_Conv_op(n);
883 ir_mode *n_mode = get_irn_mode(n);
884 ir_mode *a_mode = get_irn_mode(a);
886 if (n_mode == a_mode) { /* No Conv necessary */
888 DBG_OPT_ALGSIM3(oldn, a, n);
889 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
893 n_mode = get_irn_mode(n);
894 b_mode = get_irn_mode(b);
896 if (n_mode == b_mode) {
897 if (n_mode == mode_b) {
898 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
899 DBG_OPT_ALGSIM1(oldn, a, b, n);
901 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
902 if (smaller_mode(b_mode, a_mode)){
903 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
904 DBG_OPT_ALGSIM1(oldn, a, b, n);
913 * A Cast may be removed if the type of the previous node
914 * is already to type of the Cast.
916 static ir_node *equivalent_node_Cast(ir_node *n) {
917 ir_node *pred = get_Cast_op(n);
918 if (get_irn_type(pred) == get_Cast_type(n))
923 /* Several optimizations:
924 - no Phi in start block.
925 - remove Id operators that are inputs to Phi
926 - fold Phi-nodes, iff they have only one predecessor except
929 static ir_node *equivalent_node_Phi(ir_node *n)
934 ir_node *block = NULL; /* to shutup gcc */
935 ir_node *first_val = NULL; /* to shutup gcc */
936 ir_node *scnd_val = NULL; /* to shutup gcc */
938 if (!get_opt_normalize()) return n;
940 n_preds = get_Phi_n_preds(n);
942 block = get_nodes_block(n);
943 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
944 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
945 if ((is_Block_dead(block)) || /* Control dead */
946 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
947 return new_Bad(); /* in the Start Block. */
949 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
952 /* first we test for a special case: */
953 /* Confirm is a special node fixing additional information for a
954 value that is known at a certain point. This is useful for
955 dataflow analysis. */
957 ir_node *a = get_Phi_pred(n, 0);
958 ir_node *b = get_Phi_pred(n, 1);
959 if ( (get_irn_op(a) == op_Confirm)
960 && (get_irn_op(b) == op_Confirm)
961 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
962 && (get_irn_n(a, 1) == get_irn_n (b, 1))
963 && (a->data.num == (~b->data.num & irpn_True) )) {
964 return get_irn_n(a, 0);
969 /* If the Block has a Bad pred, we also have one. */
970 for (i = 0; i < n_preds; ++i)
971 if (is_Bad (get_Block_cfgpred(block, i)))
972 set_Phi_pred(n, i, new_Bad());
974 /* Find first non-self-referencing input */
975 for (i = 0; i < n_preds; ++i) {
976 first_val = get_Phi_pred(n, i);
977 if ( (first_val != n) /* not self pointer */
979 && (get_irn_op(first_val) != op_Bad)
981 ) { /* value not dead */
982 break; /* then found first value. */
986 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
987 if (i >= n_preds) { return new_Bad(); }
991 /* follow_Id () for rest of inputs, determine if any of these
992 are non-self-referencing */
993 while (++i < n_preds) {
994 scnd_val = get_Phi_pred(n, i);
996 && (scnd_val != first_val)
998 && (get_irn_op(scnd_val) != op_Bad)
1005 /* Fold, if no multiple distinct non-self-referencing inputs */
1008 DBG_OPT_PHI(oldn, first_val, n);
1010 /* skip the remaining Ids (done in get_Phi_pred). */
1011 /* superfluous, since we walk all to propagate Block's Bads.
1012 while (++i < n_preds) get_Phi_pred(n, i); */
1018 * optimize Proj(Tuple) and gigo for ProjX in Bad block
1020 static ir_node *equivalent_node_Proj(ir_node *n)
1024 ir_node *a = get_Proj_pred(n);
1026 if ( get_irn_op(a) == op_Tuple) {
1027 /* Remove the Tuple/Proj combination. */
1028 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1029 n = get_Tuple_pred(a, get_Proj_proj(n));
1030 DBG_OPT_TUPLE(oldn, a, n);
1032 assert(0); /* This should not happen! */
1035 } else if (get_irn_mode(n) == mode_X &&
1036 is_Block_dead(get_nodes_block(n))) {
1037 /* Remove dead control flow -- early gigo. */
1046 static ir_node *equivalent_node_Id(ir_node *n)
1051 DBG_OPT_ID(oldn, n);
1056 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1057 * perform no actual computation, as, e.g., the Id nodes. It does not create
1058 * new nodes. It is therefore safe to free n if the node returned is not n.
1059 * If a node returns a Tuple we can not just skip it. If the size of the
1060 * in array fits, we transform n into a tuple (e.g., Div).
1063 equivalent_node(ir_node *n)
1065 if (n->op->equivalent_node)
1066 return n->op->equivalent_node(n);
1071 * set the default equivalent node operation
1073 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1077 op->equivalent_node = equivalent_node_##a; \
1104 op->equivalent_node = NULL;
1112 * Do node specific optimizations of nodes predecessors.
1115 optimize_preds(ir_node *n) {
1116 ir_node *a = NULL, *b = NULL;
1118 /* get the operands we will work on for simple cases. */
1120 a = get_binop_left(n);
1121 b = get_binop_right(n);
1122 } else if (is_unop(n)) {
1126 switch (get_irn_opcode(n)) {
1129 /* We don't want Cast as input to Cmp. */
1130 if (get_irn_op(a) == op_Cast) {
1134 if (get_irn_op(b) == op_Cast) {
1136 set_Cmp_right(n, b);
1145 * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1146 * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1148 static ir_node *transform_node_AddSub(ir_node *n)
1150 ir_mode *mode = get_irn_mode(n);
1152 if (mode_is_reference(mode)) {
1153 ir_node *left = get_binop_left(n);
1154 ir_node *right = get_binop_right(n);
1155 int ref_bits = get_mode_size_bits(mode);
1157 if (get_irn_op(left) == op_Conv) {
1158 ir_mode *mode = get_irn_mode(left);
1159 int bits = get_mode_size_bits(mode);
1161 if (ref_bits == bits &&
1162 mode_is_int(mode) &&
1163 get_mode_arithmetic(mode) == irma_twos_complement) {
1164 ir_node *pre = get_Conv_op(left);
1165 ir_mode *pre_mode = get_irn_mode(pre);
1167 if (mode_is_int(pre_mode) &&
1168 get_mode_size_bits(pre_mode) == bits &&
1169 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1170 /* ok, this conv just changes to sign, moreover the calculation
1171 * is done with same number of bits as our address mode, so
1172 * we can ignore the conv as address calculation can be viewed
1173 * as either signed or unsigned
1175 set_binop_left(n, pre);
1180 if (get_irn_op(right) == op_Conv) {
1181 ir_mode *mode = get_irn_mode(right);
1182 int bits = get_mode_size_bits(mode);
1184 if (ref_bits == bits &&
1185 mode_is_int(mode) &&
1186 get_mode_arithmetic(mode) == irma_twos_complement) {
1187 ir_node *pre = get_Conv_op(right);
1188 ir_mode *pre_mode = get_irn_mode(pre);
1190 if (mode_is_int(pre_mode) &&
1191 get_mode_size_bits(pre_mode) == bits &&
1192 get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1193 /* ok, this conv just changes to sign, moreover the calculation
1194 * is done with same number of bits as our address mode, so
1195 * we can ignore the conv as address calculation can be viewed
1196 * as either signed or unsigned
1198 set_binop_right(n, pre);
1206 #define transform_node_Add transform_node_AddSub
1207 #define transform_node_Sub transform_node_AddSub
1209 /** Do architecture dependend optimizations on Mul nodes */
1210 static ir_node *transform_node_Mul(ir_node *n) {
1211 return arch_dep_replace_mul_with_shifts(n);
1214 static ir_node *transform_node_Div(ir_node *n)
1216 tarval *tv = value_of(n);
1219 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1221 if (tv != tarval_bad)
1222 value = new_Const(get_tarval_mode(tv), tv);
1223 else /* Try architecture dependand optimization */
1224 value = arch_dep_replace_div_by_const(n);
1227 /* Turn Div into a tuple (mem, bad, value) */
1228 ir_node *mem = get_Div_mem(n);
1230 turn_into_tuple(n, 3);
1231 set_Tuple_pred(n, pn_Div_M, mem);
1232 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1233 set_Tuple_pred(n, pn_Div_res, value);
1238 static ir_node *transform_node_Mod(ir_node *n)
1240 tarval *tv = value_of(n);
1243 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1245 if (tv != tarval_bad)
1246 value = new_Const(get_tarval_mode(tv), tv);
1247 else /* Try architecture dependand optimization */
1248 value = arch_dep_replace_mod_by_const(n);
1251 /* Turn Mod into a tuple (mem, bad, value) */
1252 ir_node *mem = get_Mod_mem(n);
1254 turn_into_tuple(n, 3);
1255 set_Tuple_pred(n, pn_Mod_M, mem);
1256 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1257 set_Tuple_pred(n, pn_Mod_res, value);
1262 static ir_node *transform_node_DivMod(ir_node *n)
1266 ir_node *a = get_DivMod_left(n);
1267 ir_node *b = get_DivMod_right(n);
1268 ir_mode *mode = get_irn_mode(a);
1269 tarval *ta = value_of(a);
1270 tarval *tb = value_of(b);
1272 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1275 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1277 if (tb != tarval_bad) {
1278 if (tb == get_mode_one(get_tarval_mode(tb))) {
1279 b = new_Const (mode, get_mode_null(mode));
1281 } else if (ta != tarval_bad) {
1282 tarval *resa, *resb;
1283 resa = tarval_div (ta, tb);
1284 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1285 Jmp for X result!? */
1286 resb = tarval_mod (ta, tb);
1287 if (resb == tarval_bad) return n; /* Causes exception! */
1288 a = new_Const (mode, resa);
1289 b = new_Const (mode, resb);
1292 else { /* Try architecture dependand optimization */
1293 arch_dep_replace_divmod_by_const(&a, &b, n);
1294 evaluated = a != NULL;
1296 } else if (ta == get_mode_null(mode)) {
1297 /* 0 / non-Const = 0 */
1302 if (evaluated) { /* replace by tuple */
1303 ir_node *mem = get_DivMod_mem(n);
1304 turn_into_tuple(n, 4);
1305 set_Tuple_pred(n, pn_DivMod_M, mem);
1306 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1307 set_Tuple_pred(n, pn_DivMod_res_div, a);
1308 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1309 assert(get_nodes_block(n));
1315 static ir_node *transform_node_Cond(ir_node *n)
1317 /* Replace the Cond by a Jmp if it branches on a constant
1320 ir_node *a = get_Cond_selector(n);
1321 tarval *ta = value_of(a);
1323 if ((ta != tarval_bad) &&
1324 (get_irn_mode(a) == mode_b) &&
1325 (get_opt_unreachable_code())) {
1326 /* It's a boolean Cond, branching on a boolean constant.
1327 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1328 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1329 turn_into_tuple(n, 2);
1330 if (ta == tarval_b_true) {
1331 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1332 set_Tuple_pred(n, pn_Cond_true, jmp);
1334 set_Tuple_pred(n, pn_Cond_false, jmp);
1335 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1337 /* We might generate an endless loop, so keep it alive. */
1338 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1339 } else if ((ta != tarval_bad) &&
1340 (get_irn_mode(a) == mode_Iu) &&
1341 (get_Cond_kind(n) == dense) &&
1342 (get_opt_unreachable_code())) {
1343 /* I don't want to allow Tuples smaller than the biggest Proj.
1344 Also this tuple might get really big...
1345 I generate the Jmp here, and remember it in link. Link is used
1346 when optimizing Proj. */
1347 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1348 /* We might generate an endless loop, so keep it alive. */
1349 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1350 } else if ((get_irn_op(a) == op_Eor)
1351 && (get_irn_mode(a) == mode_b)
1352 && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1353 /* The Eor is a negate. Generate a new Cond without the negate,
1354 simulate the negate by exchanging the results. */
1355 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1357 } else if ((get_irn_op(a) == op_Not)
1358 && (get_irn_mode(a) == mode_b)) {
1359 /* A Not before the Cond. Generate a new Cond without the Not,
1360 simulate the Not by exchanging the results. */
1361 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1370 static ir_node *transform_node_Eor(ir_node *n)
1372 ir_node *a = get_Eor_left(n);
1373 ir_node *b = get_Eor_right(n);
1375 if ((get_irn_mode(n) == mode_b)
1376 && (get_irn_op(a) == op_Proj)
1377 && (get_irn_mode(a) == mode_b)
1378 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1379 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1380 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1381 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1382 mode_b, get_negated_pnc(get_Proj_proj(a)));
1383 else if ((get_irn_mode(n) == mode_b)
1384 && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1385 /* The Eor is a Not. Replace it by a Not. */
1386 /* ????!!!Extend to bitfield 1111111. */
1387 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1393 * Transform a boolean Not.
1395 static ir_node *transform_node_Not(ir_node *n)
1397 ir_node *a = get_Not_op(n);
1399 if ( (get_irn_mode(n) == mode_b)
1400 && (get_irn_op(a) == op_Proj)
1401 && (get_irn_mode(a) == mode_b)
1402 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1403 /* We negate a Cmp. The Cmp has the negated result anyways! */
1404 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1405 mode_b, get_negated_pnc(get_Proj_proj(a)));
1411 * Transform a Cast of a Const into a new Const
1413 static ir_node *transform_node_Cast(ir_node *n) {
1414 ir_node *pred = get_Cast_op(n);
1415 type *tp = get_irn_type(pred);
1417 if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1418 n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1419 get_Const_tarval(pred), tp);
1420 } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1421 n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1422 get_SymConst_kind(pred), tp);
1428 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1429 * done here instead of equivalent node because it creates new
1431 * Removes the exceptions and routes the memory to the NoMem node.
1433 * Further, it optimizes jump tables by removing all impossible cases.
1435 static ir_node *transform_node_Proj(ir_node *proj)
1437 ir_node *n = get_Proj_pred(proj);
1442 switch (get_irn_opcode(n)) {
1444 b = get_Div_right(n);
1447 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1448 proj_nr = get_Proj_proj(proj);
1450 /* this node may float */
1451 set_irn_pinned(n, op_pin_state_floats);
1453 if (proj_nr == pn_Div_X_except) {
1454 /* we found an exception handler, remove it */
1457 /* the memory Proj can be removed */
1458 ir_node *res = get_Div_mem(n);
1460 set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1461 # endif /* defined USE_NOMEM */
1462 if (proj_nr == pn_Div_M)
1468 b = get_Mod_right(n);
1471 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1472 proj_nr = get_Proj_proj(proj);
1474 /* this node may float */
1475 set_irn_pinned(n, op_pin_state_floats);
1477 if (proj_nr == pn_Mod_X_except) {
1478 /* we found an exception handler, remove it */
1481 /* the memory Proj can be removed */
1482 ir_node *res = get_Mod_mem(n);
1484 set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1485 # endif /* defined USE_NOMEM */
1486 if (proj_nr == pn_Mod_M)
1492 b = get_DivMod_right(n);
1495 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1496 proj_nr = get_Proj_proj(proj);
1498 /* this node may float */
1499 set_irn_pinned(n, op_pin_state_floats);
1501 if (proj_nr == pn_DivMod_X_except) {
1502 /* we found an exception handler, remove it */
1506 /* the memory Proj can be removed */
1507 ir_node *res = get_DivMod_mem(n);
1509 set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1510 # endif /* defined USE_NOMEM */
1511 if (proj_nr == pn_DivMod_M)
1518 if (get_opt_unreachable_code()) {
1519 b = get_Cond_selector(n);
1522 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1523 /* we have a constant switch */
1524 long num = get_Proj_proj(proj);
1526 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1527 if (get_tarval_long(tb) == num) {
1528 /* Do NOT create a jump here, or we will have 2 control flow ops
1529 * in a block. This case is optimized away in optimize_cf(). */
1540 /* should not happen, but if it does will be optimized away */
1548 /* we have added a Tuple, optimize it for the current Proj away */
1549 return equivalent_node_Proj(proj);
1553 * returns the operands of a commutative bin-op, if one operand is
1554 * a const, it is returned as the second one.
1556 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1558 ir_node *op_a = get_binop_left(binop);
1559 ir_node *op_b = get_binop_right(binop);
1561 assert(is_op_commutative(get_irn_op(binop)));
1563 if (get_irn_op(op_a) == op_Const) {
1574 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1575 * Such pattern may arise in bitfield stores.
1577 * value c4 value c4 & c2
1578 * AND c3 AND c1 | c3
1583 static ir_node *transform_node_Or(ir_node *or)
1587 ir_node *and_l, *c3;
1588 ir_node *value, *c4;
1589 ir_node *new_and, *new_const, *block;
1590 ir_mode *mode = get_irn_mode(or);
1592 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1594 get_comm_Binop_Ops(or, &and, &c1);
1595 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1598 get_comm_Binop_Ops(and, &or_l, &c2);
1599 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1602 get_comm_Binop_Ops(or_l, &and_l, &c3);
1603 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1606 get_comm_Binop_Ops(and_l, &value, &c4);
1607 if (get_irn_op(c4) != op_Const)
1610 /* ok, found the pattern, check for conditions */
1611 assert(mode == get_irn_mode(and));
1612 assert(mode == get_irn_mode(or_l));
1613 assert(mode == get_irn_mode(and_l));
1615 tv1 = get_Const_tarval(c1);
1616 tv2 = get_Const_tarval(c2);
1617 tv3 = get_Const_tarval(c3);
1618 tv4 = get_Const_tarval(c4);
1620 tv = tarval_or(tv4, tv2);
1621 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1622 /* have at least one 0 at the same bit position */
1626 n_tv4 = tarval_not(tv4);
1627 if (tv3 != tarval_and(tv3, n_tv4)) {
1628 /* bit in the or_mask is outside the and_mask */
1632 n_tv2 = tarval_not(tv2);
1633 if (tv1 != tarval_and(tv1, n_tv2)) {
1634 /* bit in the or_mask is outside the and_mask */
1638 /* ok, all conditions met */
1639 block = get_nodes_block(or);
1641 new_and = new_r_And(current_ir_graph, block,
1642 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1644 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1646 set_Or_left(or, new_and);
1647 set_Or_right(or, new_const);
1649 /* check for more */
1650 return transform_node_Or(or);
1654 static ir_node *transform_node(ir_node *n);
1657 * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1659 static ir_node * transform_node_shift(ir_node *n)
1662 tarval *tv1, *tv2, *res;
1664 int modulo_shf, flag;
1666 left = get_binop_left(n);
1668 /* different operations */
1669 if (get_irn_op(left) != get_irn_op(n))
1672 tv1 = value_of(get_binop_right(n));
1673 if (tv1 == tarval_bad)
1676 tv2 = value_of(get_binop_right(left));
1677 if (tv2 == tarval_bad)
1680 res = tarval_add(tv1, tv2);
1682 /* beware: a simple replacement works only, if res < modulo shift */
1683 mode = get_irn_mode(n);
1687 modulo_shf = get_mode_modulo_shift(mode);
1688 if (modulo_shf > 0) {
1689 tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1691 if (tarval_cmp(res, modulo) & Lt)
1698 /* ok, we can replace it */
1699 ir_node *in[2], *irn, *block = get_nodes_block(n);
1701 in[0] = get_binop_left(left);
1702 in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1704 irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1706 return transform_node(irn);
1713 * Tries several [inplace] [optimizing] transformations and returns an
1714 * equivalent node. The difference to equivalent_node() is that these
1715 * transformations _do_ generate new nodes, and thus the old node must
1716 * not be freed even if the equivalent node isn't the old one.
1718 static ir_node *transform_node(ir_node *n)
1720 if (n->op->transform_node)
1721 n = n->op->transform_node(n);
1726 * set the default transform node operation
1728 static ir_op *firm_set_default_transform_node(ir_op *op)
1732 op->transform_node = transform_node_##a; \
1751 op->transform_node = transform_node_shift;
1754 op->transform_node = NULL;
1762 /* **************** Common Subexpression Elimination **************** */
1764 /** The size of the hash table used, should estimate the number of nodes
1766 #define N_IR_NODES 512
1768 /** Compares the attributes of two Const nodes. */
1769 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1771 return (get_Const_tarval(a) != get_Const_tarval(b))
1772 || (get_Const_type(a) != get_Const_type(b));
1775 /** Compares the attributes of two Proj nodes. */
1776 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1778 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1781 /** Compares the attributes of two Filter nodes. */
1782 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1784 return get_Filter_proj(a) != get_Filter_proj(b);
1787 /** Compares the attributes of two Alloc nodes. */
1788 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1790 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1791 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1794 /** Compares the attributes of two Free nodes. */
1795 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1797 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1800 /** Compares the attributes of two SymConst nodes. */
1801 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1803 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1804 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1805 || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1808 /** Compares the attributes of two Call nodes. */
1809 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1811 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1814 /** Compares the attributes of two Sel nodes. */
1815 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1817 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1818 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1819 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1820 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1821 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1824 /** Compares the attributes of two Phi nodes. */
1825 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1827 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1830 /** Compares the attributes of two Cast nodes. */
1831 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1833 return get_Cast_type(a) != get_Cast_type(b);
1836 /** Compares the attributes of two Load nodes. */
1837 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1839 if (get_Load_volatility(a) == volatility_is_volatile ||
1840 get_Load_volatility(b) == volatility_is_volatile)
1841 /* NEVER do CSE on volatile Loads */
1844 return get_Load_mode(a) != get_Load_mode(b);
1847 /** Compares the attributes of two Store nodes. */
1848 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1850 /* NEVER do CSE on volatile Stores */
1851 return (get_Store_volatility(a) == volatility_is_volatile ||
1852 get_Store_volatility(b) == volatility_is_volatile);
1856 * set the default node attribute compare operation
1858 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1862 op->node_cmp_attr = node_cmp_attr_##a; \
1879 op->node_cmp_attr = NULL;
1887 * Compare function for two nodes in the hash table. Gets two
1888 * nodes as parameters. Returns 0 if the nodes are a cse.
1891 vt_cmp (const void *elt, const void *key)
1899 if (a == b) return 0;
1901 if ((get_irn_op(a) != get_irn_op(b)) ||
1902 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1904 /* compare if a's in and b's in are of equal length */
1905 irn_arity_a = get_irn_intra_arity (a);
1906 if (irn_arity_a != get_irn_intra_arity(b))
1909 /* for block-local cse and op_pin_state_pinned nodes: */
1910 if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
1911 if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
1915 /* compare a->in[0..ins] with b->in[0..ins] */
1916 for (i = 0; i < irn_arity_a; i++)
1917 if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
1921 * here, we already now that the nodes are identical except their
1924 if (a->op->node_cmp_attr)
1925 return a->op->node_cmp_attr(a, b);
1931 * Calculate a hash value of a node.
1934 ir_node_hash (ir_node *node)
1939 if (node->op == op_Const) {
1940 /* special value for const, as they only differ in their tarval. */
1941 h = HASH_PTR(node->attr.con.tv);
1942 h = 9*h + HASH_PTR(get_irn_mode(node));
1943 } else if (node->op == op_SymConst) {
1944 /* special value for const, as they only differ in their symbol. */
1945 h = HASH_PTR(node->attr.i.sym.type_p);
1946 h = 9*h + HASH_PTR(get_irn_mode(node));
1949 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1950 h = irn_arity = get_irn_intra_arity(node);
1952 /* consider all in nodes... except the block if not a control flow. */
1953 for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
1954 h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
1958 h = 9*h + HASH_PTR(get_irn_mode(node));
1960 h = 9*h + HASH_PTR(get_irn_op(node));
1967 new_identities(void) {
1968 return new_pset(vt_cmp, N_IR_NODES);
1972 del_identities(pset *value_table) {
1973 del_pset(value_table);
1977 * Return the canonical node computing the same value as n.
1978 * Looks up the node in a hash table.
1980 * For Const nodes this is performed in the constructor, too. Const
1981 * nodes are extremely time critical because of their frequent use in
1982 * constant string arrays.
1984 static INLINE ir_node *
1985 identify (pset *value_table, ir_node *n)
1989 if (!value_table) return n;
1991 if (get_opt_reassociation()) {
1992 if (is_op_commutative(get_irn_op(n))) {
1993 ir_node *l = get_binop_left(n);
1994 ir_node *r = get_binop_right(n);
1996 /* for commutative operators perform a OP b == b OP a */
1998 set_binop_left(n, r);
1999 set_binop_right(n, l);
2004 o = pset_find (value_table, n, ir_node_hash (n));
2013 * During construction we set the op_pin_state_pinned flag in the graph right when the
2014 * optimization is performed. The flag turning on procedure global cse could
2015 * be changed between two allocations. This way we are safe.
2017 static INLINE ir_node *
2018 identify_cons (pset *value_table, ir_node *n) {
2021 n = identify(value_table, n);
2022 if (get_irn_n(old, -1) != get_irn_n(n, -1))
2023 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2028 * Return the canonical node computing the same value as n.
2029 * Looks up the node in a hash table, enters it in the table
2030 * if it isn't there yet.
2033 identify_remember (pset *value_table, ir_node *n)
2037 if (!value_table) return n;
2039 if (get_opt_reassociation()) {
2040 if (is_op_commutative(get_irn_op(n))) {
2041 ir_node *l = get_binop_left(n);
2042 ir_node *r = get_binop_right(n);
2044 /* for commutative operators perform a OP b == b OP a */
2046 set_binop_left(n, r);
2047 set_binop_right(n, l);
2052 /* lookup or insert in hash table with given hash key. */
2053 o = pset_insert (value_table, n, ir_node_hash (n));
2063 add_identities (pset *value_table, ir_node *node) {
2064 if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2065 identify_remember (value_table, node);
2069 * garbage in, garbage out. If a node has a dead input, i.e., the
2070 * Bad node is input to the node, return the Bad node.
2072 static INLINE ir_node *
2073 gigo (ir_node *node)
2076 ir_op* op = get_irn_op(node);
2078 /* remove garbage blocks by looking at control flow that leaves the block
2079 and replacing the control flow by Bad. */
2080 if (get_irn_mode(node) == mode_X) {
2081 ir_node *block = get_nodes_block(node);
2082 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
2084 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2085 irn_arity = get_irn_arity(block);
2086 for (i = 0; i < irn_arity; i++) {
2087 if (!is_Bad(get_irn_n(block, i))) break;
2089 if (i == irn_arity) return new_Bad();
2093 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2094 blocks predecessors is dead. */
2095 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2096 irn_arity = get_irn_arity(node);
2098 if (is_Block_dead(get_nodes_block(node)))
2101 for (i = 0; i < irn_arity; i++) {
2102 if (is_Bad(get_irn_n(node, i))) {
2108 /* With this code we violate the agreement that local_optimize
2109 only leaves Bads in Block, Phi and Tuple nodes. */
2110 /* If Block has only Bads as predecessors it's garbage. */
2111 /* If Phi has only Bads as predecessors it's garbage. */
2112 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
2113 irn_arity = get_irn_arity(node);
2114 for (i = 0; i < irn_arity; i++) {
2115 if (!is_Bad(get_irn_n(node, i))) break;
2117 if (i == irn_arity) node = new_Bad();
2125 * These optimizations deallocate nodes from the obstack.
2126 * It can only be called if it is guaranteed that no other nodes
2127 * reference this one, i.e., right after construction of a node.
2130 optimize_node (ir_node *n)
2134 opcode iro = get_irn_opcode(n);
2136 type *old_tp = get_irn_type(n);
2138 int i, arity = get_irn_arity(n);
2139 for (i = 0; i < arity && !old_tp; ++i)
2140 old_tp = get_irn_type(get_irn_n(n, i));
2143 /* Allways optimize Phi nodes: part of the construction. */
2144 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2146 /* constant expression evaluation / constant folding */
2147 if (get_opt_constant_folding()) {
2148 /* constants can not be evaluated */
2149 if (iro != iro_Const) {
2150 /* try to evaluate */
2151 tv = computed_value(n);
2152 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2154 * we MUST copy the node here temporary, because it's still needed
2155 * for DBG_OPT_CSTEVAL
2157 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
2158 oldn = alloca(node_size);
2160 memcpy(oldn, n, node_size);
2161 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2163 /* ARG, copy the in array, we need it for statistics */
2164 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2166 /* evaluation was successful -- replace the node. */
2167 obstack_free (current_ir_graph->obst, n);
2168 n = new_Const (get_tarval_mode (tv), tv);
2169 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2170 set_Const_type(n, old_tp);
2171 DBG_OPT_CSTEVAL(oldn, n);
2177 /* remove unnecessary nodes */
2178 if (get_opt_constant_folding() ||
2179 (iro == iro_Phi) || /* always optimize these nodes. */
2181 (iro == iro_Proj) ||
2182 (iro == iro_Block) ) /* Flags tested local. */
2183 n = equivalent_node (n);
2185 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2187 /** common subexpression elimination **/
2188 /* Checks whether n is already available. */
2189 /* The block input is used to distinguish different subexpressions. Right
2190 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2191 subexpressions within a block. */
2193 n = identify_cons (current_ir_graph->value_table, n);
2196 /* We found an existing, better node, so we can deallocate the old node. */
2197 obstack_free (current_ir_graph->obst, oldn);
2202 /* Some more constant expression evaluation that does not allow to
2204 iro = get_irn_opcode(n);
2205 if (get_opt_constant_folding() ||
2206 (iro == iro_Cond) ||
2207 (iro == iro_Proj)) /* Flags tested local. */
2208 n = transform_node (n);
2210 /* Remove nodes with dead (Bad) input.
2211 Run always for transformation induced Bads. */
2214 /* Now we have a legal, useful node. Enter it in hash table for cse */
2215 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2216 n = identify_remember (current_ir_graph->value_table, n);
2224 * These optimizations never deallocate nodes. This can cause dead
2225 * nodes lying on the obstack. Remove these by a dead node elimination,
2226 * i.e., a copying garbage collection.
2229 optimize_in_place_2 (ir_node *n)
2233 opcode iro = get_irn_opcode(n);
2235 type *old_tp = get_irn_type(n);
2237 int i, arity = get_irn_arity(n);
2238 for (i = 0; i < arity && !old_tp; ++i)
2239 old_tp = get_irn_type(get_irn_n(n, i));
2242 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2244 /* if not optimize return n */
2247 /* Here this is possible. Why? */
2251 /* constant expression evaluation / constant folding */
2252 if (get_opt_constant_folding()) {
2253 /* constants can not be evaluated */
2254 if (iro != iro_Const) {
2255 /* try to evaluate */
2256 tv = computed_value(n);
2257 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2258 /* evaluation was successful -- replace the node. */
2259 n = new_Const (get_tarval_mode (tv), tv);
2261 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2262 set_Const_type(n, old_tp);
2264 DBG_OPT_CSTEVAL(oldn, n);
2270 /* remove unnecessary nodes */
2271 if (get_opt_constant_folding() ||
2272 (iro == iro_Phi) || /* always optimize these nodes. */
2273 (iro == iro_Id) || /* ... */
2274 (iro == iro_Proj) || /* ... */
2275 (iro == iro_Block) ) /* Flags tested local. */
2276 n = equivalent_node (n);
2278 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2280 /** common subexpression elimination **/
2281 /* Checks whether n is already available. */
2282 /* The block input is used to distinguish different subexpressions. Right
2283 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2284 subexpressions within a block. */
2285 if (get_opt_cse()) {
2286 n = identify (current_ir_graph->value_table, n);
2289 /* Some more constant expression evaluation. */
2290 iro = get_irn_opcode(n);
2291 if (get_opt_constant_folding() ||
2292 (iro == iro_Cond) ||
2293 (iro == iro_Proj)) /* Flags tested local. */
2294 n = transform_node (n);
2296 /* Remove nodes with dead (Bad) input.
2297 Run always for transformation induced Bads. */
2300 /* Now we can verify the node, as it has no dead inputs any more. */
2303 /* Now we have a legal, useful node. Enter it in hash table for cse.
2304 Blocks should be unique anyways. (Except the successor of start:
2305 is cse with the start block!) */
2306 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2307 n = identify_remember (current_ir_graph->value_table, n);
2313 * Wrapper for external use, set proper status bits after optimization.
2316 optimize_in_place (ir_node *n)
2318 /* Handle graph state */
2319 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2321 if (get_opt_global_cse())
2322 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2323 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2324 set_irg_outs_inconsistent(current_ir_graph);
2326 /* Maybe we could also test whether optimizing the node can
2327 change the control graph. */
2328 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2329 set_irg_dom_inconsistent(current_ir_graph);
2330 return optimize_in_place_2 (n);
2334 * set the default ir op operations
2336 ir_op *firm_set_default_operations(ir_op *op)
2338 op = firm_set_default_computed_value(op);
2339 op = firm_set_default_equivalent_node(op);
2340 op = firm_set_default_transform_node(op);
2341 op = firm_set_default_node_cmp_attr(op);